Deep Homogeneous Mixture Models: Representation, Separation, and Approximation

Priyank Jaini, Pascal Poupart, Yaoliang YuNeurIPS 2018 · OpenReview

Overview

This paper provides a rigorous mathematical unification of several popular unsupervised learning models—including Hidden Markov Models (HMMs), Sum-Product Networks (SPNs), and Latent Tree Models (LTMs)—under the umbrella of "homogeneous mixture models." The authors prove that deep architectures are exponentially more efficient than shallow ones at representing complex probability distributions and introduce a practical conditional gradient algorithm (SPN-CG) to learn these structures efficiently.

What Problem Does This Paper Address?

In the world of unsupervised learning, we have a "zoo" of models used for density estimation (figuring out the underlying probability distribution of data). While models like SPNs, HMMs, and Tensorial Mixture Models (TMMs) all seem to do similar things, their formal relationships were historically fuzzy.

Furthermore, while the "deep vs. shallow" debate is well-settled in supervised learning (like CNNs), the theoretical justification for depth in probabilistic models was less complete. The authors set out to answer:

  1. How exactly do these different models relate to one another?
  2. Can we prove that deep probabilistic models are strictly better (more efficient) than shallow ones?
  3. How can we practically approximate complex densities using these insights?

Unifying the Model Zoo

The researchers use the language of tensors (multi-dimensional arrays) and linear algebra to bridge the gap between different model classes.

Model Unification: They establish a clear hierarchy: $\{HMM, TMM\} \subseteq LTM \subseteq HTF \subseteq SPN$. They show that moving from a "lower" class (like an HMM) to a "higher" one (like an SPN) can be done in linear time without increasing the model's size.

Shallow architectures of LTM, SPN, and HTF

Exponential Separation: Using the concept of "non-negative tensor rank," they prove that a "deep" SPN can represent certain distributions that would require a shallow SPN to have an exponentially large number of nodes. The benefit of depth isn't just about "accuracy"—it's about representation size. A deep model is essentially a massive compression tool for complex probability tensors.

SPN-CG Algorithm: For practical applications, they adapt the Conditional Gradient (Frank-Wolfe) algorithm. Instead of trying to find an "exact" representation, this algorithm iteratively adds "shallow" components to minimize the KL divergence between the model and the true data distribution.

Key Results and Insights

The authors evaluated their theories and the SPN-CG algorithm on synthetic data (16-dimensional Gaussian Mixture Models) and real-world datasets (MNIST and Small NORB) under missing data conditions.

  • Efficiency in Training: In synthetic tests, as the depth of the model increased, the number of iterations required for the SPN-CG algorithm to converge dropped sharply. Even though deeper iterations are more computationally expensive, the total running time was significantly lower for deep models.
Training efficiency improves with model depth
  • Robustness to Missing Data: On MNIST and NORB, the SPN-CG algorithm significantly outperformed standard data imputation techniques and other generative models when large portions of the image were missing.
  • Depth vs. Width: The experiments confirmed that adding a single layer of depth is often more effective than adding an exponential number of nodes to a shallow layer.

Limitations and Future Work

  • Target Density Knowledge: One of the theoretical proofs requires knowing the target density beforehand, which isn't possible in real-world scenarios. The SPN-CG algorithm addresses this practically, but a theoretical gap remains.
  • Homogeneity Constraint: The study focuses on "homogeneous" mixtures. While universal, the "homogenization trick" required for some datasets might introduce complexities in very high-dimensional spaces.
  • Scaling: Scaling these specific tensor-based mixture models to massive, high-resolution datasets like ImageNet remains a challenge for future research.

Summary updated

Abstract

At their core, many unsupervised learning models provide a compact representation of homogeneous density mixtures, but their similarities and differences are not always clearly understood. In this work, we formally establish the relationships among latent tree graphical models (including special cases such as hidden Markov models and tensorial mixture models), hierarchical tensor formats and sum-product networks. Based on this connection, we then give a unified treatment of exponential separation in \emph{exact} representation size between deep mixture architectures and shallow ones. In contrast, for \emph{approximate} representation, we show that the conditional gradient algorithm can approximate any homogeneous mixture within $\epsilon$ accuracy by combining $O(1/\epsilon^2)$ ``shallow'' architectures, where the hidden constant may decrease (exponentially) with respect to the depth. Our experiments on both synthetic and real datasets confirm the benefits of depth in density estimation.
BibTeX
@inproceedings{jaini2018deep,
  author = {Priyank Jaini and Pascal Poupart and Yaoliang Yu},
  title = {{Deep Homogeneous Mixture Models: Representation, Separation, and Approximation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=BJNhvw-uWH},
}
Figure