Unsupervised learning of distributions on binary vectors using two layer networks

NeurIPS 1991

TL;DR

This paper introduces the "harmonium," a novel two-layer neural network architecture for modeling probability distributions over binary vectors. It offers a powerful yet computationally tractable alternative to general Boltzmann machines, demonstrating strong performance on synthetic and real-world data for tasks like image reconstruction and density estimation.

What Problem Does This Paper Address?

The paper tackles the challenge of unsupervised learning of probability distributions from binary data. Existing models like Hopfield networks are too limited in their representational power, while general Boltzmann machines, though universal, are computationally intractable for learning. The authors aim to bridge this gap by developing a model that is both powerful enough to approximate arbitrary distributions and efficient enough for practical learning. This is crucial for understanding the underlying structure in data where labels are absent, such as in image analysis or pattern recognition.

Methods

The core contribution is the harmonium, a specific type of Boltzmann machine with a bipartite graph structure. It consists of input units representing observed binary variables and hidden units representing unobserved variables. The key innovation lies in its restricted connectivity: only connections between input and hidden units exist, and no connections within input or hidden units. This structure leads to a tractable probability distribution that can be expressed as a product of terms, simplifying the learning process.

The paper proposes two learning algorithms:

  1. Gradient Ascent: A standard heuristic for maximum likelihood estimation, but significantly simplified for the harmonium due to its specific structure. The authors derive a closed-form gradient that avoids the computationally expensive stochastic approximation required for general Boltzmann machines.
  2. Greedy Projection Pursuit: A variant of projection pursuit density estimation. This method iteratively adds hidden units, estimating their weights and biases one by one. It's presented as a faster alternative to gradient ascent, especially for larger models.

Datasets

  • Synthetically generated data: Binary vectors of 64 bits representing 8x8 binary images. This data was generated using a harmonium model itself, allowing the authors to evaluate how well the learning algorithms can recover the true generating model.
  • NIST handwritten digits database: Real-world data consisting of 16x16 binary images of digits. This dataset is used to compare the harmonium model against a standard mixture model.

Key Insights and Ideas

  • Harmonium's Tractability: The bipartite structure of the harmonium is the key to its computational efficiency. It allows for a product-form probability distribution, which drastically simplifies gradient calculations compared to general Boltzmann machines.
  • Universal Approximation Power: Despite its structural simplicity, the harmonium is shown to be capable of arbitrarily approximating any distribution on binary vectors, given enough hidden units.
  • Interpretability of Hidden Units: The hidden units in a harmonium can be interpreted as representing "prototypical" directions or social groups, influencing the probability of input vectors that align with these directions.
  • Projection Pursuit as a Fast Alternative: The greedy projection pursuit algorithm offers a computationally efficient way to learn harmonium models, especially when dealing with a large number of hidden units. It's shown to be much faster than gradient ascent.
  • Harmonium vs. Mixture Models: The harmonium model can capture more complex correlations and combinations of features than standard mixture models, particularly when multiple hidden "influences" can be active simultaneously. This is demonstrated by its ability to learn local features in handwritten digits, whereas mixture models tend to learn more global prototypes.

Key Results

  • Synthetic Data:
    • Gradient ascent, while slow (1000 epochs), eventually recovers much of the underlying structure of the true model.
  • Projection pursuit is significantly faster and captures most features, though some hidden units might not directly correspond to the true model's components.
  • A combination of projection pursuit followed by gradient ascent yields the best results, recovering the true model almost exactly with fewer epochs than pure gradient ascent.
  • Handwritten Digits Data:
    • The harmonium model, learned using projection pursuit, shows a small but definite improvement in single-bit prediction and input reconstruction errors compared to a standard mixture model.
  • Qualitatively, the harmonium model learns weights corresponding to local features (lines, contrasts), while the mixture model learns more global prototypes of digits.

Limitations and Future Work

  • Computational Limits of Projection Pursuit: For very large numbers of hidden units, computing all terms in the projection pursuit algorithm can still become intractable. The authors suggest strategies like assuming a small number of dominant terms or dynamically searching for significant terms.
  • Learning Algorithm Improvements: The paper acknowledges that the experimental results are preliminary and that improved learning methods could further enhance the harmonium's performance, especially in comparison to specialized models.
  • Generalization: The harmonium model is a general distribution model and not specifically tuned to domains like handwritten digits. Comparisons with models specifically designed for such domains are not extensively explored.
  • Future Work: The authors suggest exploring further improvements to learning algorithms and investigating the harmonium's potential in other domains. They also hint at a variant of the model for continuous real-valued data.

Summary updated

BibTeX
@inproceedings{1991unsupervised,
  title = {{Unsupervised learning of distributions on binary vectors using two layer networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1991},
}
Figure