On the Expressive Power of Tree-Structured Probabilistic Circuits

• URL: http://arxiv.org/abs/2410.05465v2
• Date: Thu, 24 Oct 2024 21:15:42 GMT
• Title: On the Expressive Power of Tree-Structured Probabilistic Circuits
• Authors: Lang Yin, Han Zhao,
• Abstract summary: We show that for $n$ variables, there exists a quasi-polynomial upper bound $nO(log n)$ on the size of an equivalent tree computing the same probability distribution. We also show that given a depth restriction on the tree, there is a super-polynomial separation between tree and DAG-structured PCs.
• Score: 8.160496835449157
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Probabilistic circuits (PCs) have emerged as a powerful framework to compactly represent probability distributions for efficient and exact probabilistic inference. It has been shown that PCs with a general directed acyclic graph (DAG) structure can be understood as a mixture of exponentially (in its height) many components, each of which is a product distribution over univariate marginals. However, existing structure learning algorithms for PCs often generate tree-structured circuits or use tree-structured circuits as intermediate steps to compress them into DAG-structured circuits. This leads to the intriguing question of whether there exists an exponential gap between DAGs and trees for the PC structure. In this paper, we provide a negative answer to this conjecture by proving that, for $n$ variables, there exists a quasi-polynomial upper bound $n^{O(\log n)}$ on the size of an equivalent tree computing the same probability distribution. On the other hand, we also show that given a depth restriction on the tree, there is a super-polynomial separation between tree and DAG-structured PCs. Our work takes an important step towards understanding the expressive power of tree-structured PCs, and our techniques may be of independent interest in the study of structure learning algorithms for PCs.

Related papers

• Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
  In this paper we offer a new perspective on the well established agglomerative clustering algorithm, focusing on recovery of hierarchical structure. We recommend a simple variant of the standard algorithm, in which clusters are merged by maximum average dot product and not, for example, by minimum distance or within-cluster variance. We demonstrate that the tree output by this algorithm provides a bona fide estimate of generative hierarchical structure in data, under a generic probabilistic graphical model.
  arXiv  Detail & Related papers  (2023-05-24T11:05:12Z)
• Compositional Probabilistic and Causal Inference using Tractable Circuit Models [20.07977560803858]
  We introduce md-vtrees, a novel structural formulation of (marginal) determinism in structured decomposable PCs. We derive the first polytime algorithms for causal inference queries such as backdoor adjustment on PCs.
  arXiv  Detail & Related papers  (2023-04-17T13:48:16Z)
• Bayesian Structure Scores for Probabilistic Circuits [13.441379161477272]
  Probabilistic circuits (PCs) are a prominent representation of probability with tractable inference. We develop Bayesian structure scores for deterministic PCs, i.e., structure likelihood with parameters marginalized out. We achieve good trade-offs between training time and model fit in terms of log-likelihood.
  arXiv  Detail & Related papers  (2023-02-23T16:12:19Z)
• Strengthening Probabilistic Graphical Models: The Purge-and-merge Algorithm [0.0]
  purge-and-merge algorithm is designed to nudge a malleable graph structure towards a tree structure by selectively merging factors. This approach is evaluated on a number of constraint-satisfaction puzzles such as Sudoku, Fill-a-pix, and Kakuro. Although these tasks were limited to the binary logic of CSP, we believe it holds promise for extension to general PGM inference.
  arXiv  Detail & Related papers  (2021-09-30T21:20:52Z)
• Robustifying Algorithms of Learning Latent Trees with Vector Variables [92.18777020401484]
  We present the sample complexities of Recursive Grouping (RG) and Chow-Liu Recursive Grouping (CLRG) We robustify RG, CLRG, Neighbor Joining (NJ) and Spectral NJ (SNJ) by using the truncated inner product. We derive the first known instance-dependent impossibility result for structure learning of latent trees.
  arXiv  Detail & Related papers  (2021-06-02T01:37:52Z)
• Spectral Top-Down Recovery of Latent Tree Models [13.681975313065477]
  Spectral Top-Down Recovery (STDR) is a divide-and-conquer approach for inference of large latent tree models. STDR's partitioning step is non-random. Instead, it is based on the Fiedler vector of a suitable Laplacian matrix related to the observed nodes. We prove that STDR is statistically consistent, and bound the number of samples required to accurately recover the tree with high probability.
  arXiv  Detail & Related papers  (2021-02-26T02:47:42Z)
• Probabilistic Generating Circuits [50.98473654244851]
  We propose probabilistic generating circuits (PGCs) for their efficient representation. PGCs are not just a theoretical framework that unifies vastly different existing models, but also show huge potential in modeling realistic data. We exhibit a simple class of PGCs that are not trivially subsumed by simple combinations of PCs and DPPs, and obtain competitive performance on a suite of density estimation benchmarks.
  arXiv  Detail & Related papers  (2021-02-19T07:06:53Z)
• Visualizing hierarchies in scRNA-seq data using a density tree-biased autoencoder [50.591267188664666]
  We propose an approach for identifying a meaningful tree structure from high-dimensional scRNA-seq data. We then introduce DTAE, a tree-biased autoencoder that emphasizes the tree structure of the data in low dimensional space.
  arXiv  Detail & Related papers  (2021-02-11T08:48:48Z)
• SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples [75.32013242448151]
  We consider learning Ising tree models when the observations from the nodes are corrupted by independent but non-identically distributed noise. Katiyar et al. (2020) showed that although the exact tree structure cannot be recovered, one can recover a partial tree structure. We propose Symmetrized Geometric Averaging (SGA), a more statistically robust algorithm for partial tree recovery.
  arXiv  Detail & Related papers  (2021-01-22T01:57:35Z)
• Convex Polytope Trees [57.56078843831244]
  convex polytope trees (CPT) are proposed to expand the family of decision trees by an interpretable generalization of their decision boundary. We develop a greedy method to efficiently construct CPT and scalable end-to-end training algorithms for the tree parameters when the tree structure is given.
  arXiv  Detail & Related papers  (2020-10-21T19:38:57Z)
• Strudel: Learning Structured-Decomposable Probabilistic Circuits [37.153542210716004]
  Strudel is a simple, fast and accurate learning algorithm for structured-decomposable PCs. It delivers more accurate single PC models in fewer iterations, and dramatically scales learning when building ensembles of PCs. We show these advantages on standard density estimation benchmarks and challenging inference scenarios.
  arXiv  Detail & Related papers  (2020-07-18T04:51:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.