Deep Homogeneous Mixture Models: Representation, Separation, and Approximation
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 exact representation size between deep mixture architectures and shallow ones. In contrast, for approximate representation, we show that the conditional gradient algorithm can approximate any homogeneous mixture within accuracy by combining O(1/ 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.
{HM M, T M M } ⊆ LT M ⊆ HT F ⊆ SP N . Moreover, converting from a lower to an upper class can be achieved in linear time and without any increase in size. Our results not only clarify the similarities and subtle differences between these widely-used models, but also pave the way for a unified treatment of many properties of such models, using tools from linear algebra.
We next investigate the consequence of converting a deep mixture model into a shallow one. We first prove that the (nonnegative) tensor rank exactly characterizes the minimum size of a shallow SPN (or LTM or HTF due to equivalence) that represents a given homogeneous mixture. Then, we show that a generic "deep" SPN (with depth at least 2) can be exactly represented by a shallow SPN only when the latter contains exponentially many product nodes. Our result extends significantly those in [7; 26; 10; 18; 8] in various aspects, but most saliently from the restrictive full binary tree [7; 26] to any rooted tree. As a consequence, our results imply that a generic HMM (whose underlying tree is "completely" unbalanced) cannot be exactly represented by any polynomially-sized shallow SPN, which, to our best knowledge, has not been shown before.
From a practical point of view, exact representations are an overkill: it suffices to approximate a given density mixture with reasonable accuracy. Our third contribution demonstrates that under the ∞ metric, we can approximate any homogeneous density mixture within accuracy by combining O(1/ 2 ) shallow SPNs. However, our proof requires the knowledge of the target density hence is not practical. Instead, borrowing a classic idea from [17] we show that minimizing the KL divergence using the conditional gradient algorithm can also approximate any homogeneous mixture within accuracy by combining O(1/
2 ) base SPNs, where the hidden constant decreases exponentially wrt the depth of the base SPNs. Each iteration of the conditional gradient algorithm amounts to learning a base SPN hence can be efficiently implemented. We conduct thorough experiments on both synthetic and real datasets and confirm the benefits of depth in density estimation.
We proceed as follows: In §2 we introduce homogeneous density mixtures. In §3 we articulate the relationships among various popular mixture models. §4 examines the exponential separation in exact representation size between deep and shallow models while §5 turns into approximate representations. We report our experiments in §6 and finally we conclude in §7. All proofs are deferred to Appendix C.
The paper discusses connections between multiple density models within the unifying framework of homogeneous mixture models: tensorial mixtures models [1], hidden Markov models, latent tree models and sum-product networks [2] are discussed. The authors argue that there is a hierarchy among these models by showing that a model lower in the hierarchy can be cast into a model higher in the hierarchy using linear size transformations. Furthermore, the paper gives new theoretical insights in depth efficiency in these models, by establishing a connection between properties of the represented mixture coefficient tensor (e.g. nonnegative rank) and a shallow model. Finally, the paper gives positive and somewhat surprising approximation results using [3].  Strengths: + connections between various models, which so far were somewhat folk wisdom, are illustrated a unifying tensor mixture framework. + depth efficiency is analysed as a simple application of this framework. + approximation results and a greedy algorithm are potentially stimulating for future work.  Weaknesses: - experiment section is rather messy and not insightful - some prior work is not adequately addressed   Quality: The paper is quite timely in discussing and unifying the above mentioned models using homogeneous tensorial mixture models. In some sense, it compiles the gist of multiple research direction in a meaningful manner.  However, in some parts the authors exaggerate the contribution and do not well connect with prior art. For example, while it was perhaps not explicitly mentioned in literature that LTMs are a sub-class of SPNs, this connection is rather obvious, especially in light of well known latent variable semantics in SPNs [4]. I also wonder why SPNs are defined as trees in this paper, when they are usually defined as general DAGs [2]. Furthermore, the strict inclusion claims in Theorem 3.1 are not proven: none of the examples in B.2, B.4, and B.6 rule out the possibility that there exists _some_ polynomial-sized model representing the distribution of the respective "higher" model.  Clarity: The paper is rather clear, but the experimental section is quite messy. One has to actually guess what is going on here; experimental setup and comparison methods are not clearly described. The experiments are, however, not the main contribution in this paper, which is rather on the theoretical side.  Originality. While parts of the paper in isolation would be incremental, in total the paper is original and provides several new insights.  Significance: This paper is clearly of significance and has considerable potential impact.  [1] Sharir et al., "Tensorial mixture models", 2018. arXiv:1610.04167v5 [2] Poon and Domingos, "Sum-Product Networks: A New Deep Architecture", UAI 2011. [3] Li and Baron, "Mixture Density Estimation", NIPS 2000. [4] Peharz et al., "On the Latent Variable Interpretation in Sum-Product Networks", PAMI 2017.   *** EDIT *** I read the authors' rebuttal. I'm happy with it, as they said that they would adequately rephrase Theorem 3.1. Moreover, I'm glad that the authors aim to clean up the experimental section. A good paper, I actually got a new view on the covered material. Definitely worth an accept.