Provable learning of noisy-OR networks

By Sanjeev Arora, Rong Ge, Tengyu Ma, Andrej Risteski. 2016

27 citations recorded by the source corpus.

Many machine learning applications use latent variable models to explain structure in data, whereby visible variables (= coordinates of the given datapoint) are explained as a probabilistic function of some hidden variables. Learning the model ---that is, the mapping from hidden variables to visible ones and vice versa---is NP-hard even in very simple settings. In recent years, provably efficient algorithms were nevertheless developed for models with linear structure: topic models, mixture models, hidden markov models, etc. These algorithms use matrix or tensor decomposition, and make some reasonable assumptions about the parameters of the underlying model. But matrix or tensor decomposition seems of little use when the latent variable model has nonlinearities. The current paper shows how to make progress: tensor decomposition is applied for learning the single-layer noisy-OR network, which is a textbook example of a bayes net, and used for example in the classic QMR-DT software for diagnosing which disease(s) a patient may have by observing the symptoms he/she exhibits. The technical novelty here, which should be useful in other settings in future, is analysis of tensor decomposition in presence of systematic error (i.e., where the noise/error is correlated with the signal, and doesn't decrease as number of samples goes to infinity). This requires rethinking all steps of tensor decomposition methods from the ground up. For simplicity our analysis is stated assuming that the network parameters were chosen from a probability distribution but the method seems more generally applicable.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Causal Effect Inference with Deep Latent-Variable Models (2017, neutral): “For example, if X includes three independent views of Z [4, 22, 16, 2]; if Z is categorical and X is a Gaussian mixture model with components determined by X [5]; or if Z is comprised of binary variables and X are so-called “noisy-or” functions of Z [23, 8].”
Improving the accuracy of medical diagnosis with causal machine learning (2020, background): “In addition, they support ef ﬁ cient inference 67 and learning 68,69 , and allow for large BNs to be described by a number of parameters that grows linearly with the size of the network 68,70 .”
Recovery Guarantees for One-hidden-layer Neural Networks (2017, methodology): “The recent empirical success of NNs has boosted their theoretical analyses (Feng et al., 2016; Balduzzi, 2016; Bal-duzzi et al., 2016; Sagun et al., 2016; Andoni et al., 2014; Arora et al., 2017; Goel et al., 2017).”
On the Convergence Rate of Training Recurrent Neural Networks (2018, methodology): “ed over-paramterization in the case of two-layer neural network under a linear-separable assumption. Some other works learn neural networks using more delicate algorithms—such as tensor decomposition [4, 13, 25, 43, 72] or tailored algorithm for the problem structure [3, 21, 80]— or design more spec”
SGD Learns the Conjugate Kernel Class of the Network (2017, background): “Various recent papers show that poly-time learning is possible in the case that the the learnt function can be realized by a neural network with certain (usually fairly strong) restrictions on the weights [23, 34, 33, 35], or under the assumption that the data is generated by a generative model that”
Learning One-hidden-layer ReLU Networks via Gradient Descent (2018, background): “…diﬀerent tasks, a line of research (Hornik, 1991; Montufar et al., 2014; Cohen et al., 2016; Telgarsky, 2016; Raghu et al., 2016; Poole et al., 2016; Arora et al., 2016; Daniely et al., 2016; Pan and Srikumar, 2016; Zhang et al., 2016; Lu et al., 2017) has studied on the expressive power of neural…”