Restructuring Tractable Probabilistic Circuits

• URL: http://arxiv.org/abs/2411.12256v1
• Date: Tue, 19 Nov 2024 06:10:22 GMT
• Title: Restructuring Tractable Probabilistic Circuits
• Authors: Honghua Zhang, Benjie Wang, Marcelo Arenas, Guy Van den Broeck,
• Abstract summary: Probabilistic circuits (PCs) are a unifying representation for probabilistic models that support tractable inference. Existing multiplication algorithms require that the circuits respect the same structure. We show that it leads to novel-time algorithms for multiplying circuits respecting different vtrees.
• Score: 33.76083310837078
• License:
• Abstract: Probabilistic circuits (PCs) is a unifying representation for probabilistic models that support tractable inference. Numerous applications of PCs like controllable text generation depend on the ability to efficiently multiply two circuits. Existing multiplication algorithms require that the circuits respect the same structure, i.e. variable scopes decomposes according to the same vtree. In this work, we propose and study the task of restructuring structured(-decomposable) PCs, that is, transforming a structured PC such that it conforms to a target vtree. We propose a generic approach for this problem and show that it leads to novel polynomial-time algorithms for multiplying circuits respecting different vtrees, as well as a practical depth-reduction algorithm that preserves structured decomposibility. Our work opens up new avenues for tractable PC inference, suggesting the possibility of training with less restrictive PC structures while enabling efficient inference by changing their structures at inference time.

Related papers

• On the Expressive Power of Tree-Structured Probabilistic Circuits [8.160496835449157]
  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.
  arXiv  Detail & Related papers  (2024-10-07T19:51:30Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  We discuss the problem of bounding partially identifiable queries, such as counterfactuals, in Pearlian structural causal models. A recently proposed iterated EM scheme yields an inner approximation of those bounds by sampling the initialisation parameters. We show how a single symbolic knowledge compilation allows us to obtain the circuit structure with symbolic parameters to be replaced by their actual values.
  arXiv  Detail & Related papers  (2023-10-05T07:10:40Z)
• Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection [88.23337313766353]
  This work first provides a comprehensive statistical theory for transformers to perform ICL. We show that transformers can implement a broad class of standard machine learning algorithms in context. A emphsingle transformer can adaptively select different base ICL algorithms.
  arXiv  Detail & Related papers  (2023-06-07T17:59:31Z)
• 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)
• Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning [53.17258888552998]
  This work proposes an exploration variant of the basic $Q$-learning protocol with linear function approximation. We show that the performance of the algorithm degrades very gracefully under a novel and more permissive notion of approximation error.
  arXiv  Detail & Related papers  (2022-06-01T23:26:51Z)
• The Dual PC Algorithm and the Role of Gaussianity for Structure Learning of Bayesian Networks [0.0]
  We show that the dual PC algorithm outperforms the classic PC algorithm in terms of run time and in recovering the underlying network structure. We also show that the dual PC algorithm applies for Gaussian copula models, and demonstrate its performance in that setting.
  arXiv  Detail & Related papers  (2021-12-16T17:27:29Z)
• Learning algorithms from circuit lower bounds [0.0]
  We revisit known constructions of efficient learning algorithms from various notions of constructive circuit lower bounds. We prove that if it is possible to find efficiently, in a particular interactive way, errors of many p-size circuits attempting to solve hard problems, then p-size circuits can be PAC learned over the uniform distribution.
  arXiv  Detail & Related papers  (2020-12-28T04:47:36Z)
• 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)
• Predictive Coding Approximates Backprop along Arbitrary Computation Graphs [68.8204255655161]
  We develop a strategy to translate core machine learning architectures into their predictive coding equivalents. Our models perform equivalently to backprop on challenging machine learning benchmarks. Our method raises the potential that standard machine learning algorithms could in principle be directly implemented in neural circuitry.
  arXiv  Detail & Related papers  (2020-06-07T15:35:47Z)
• Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic Circuits [99.59941892183454]
  We propose Einsum Networks (EiNets), a novel implementation design for PCs. At their core, EiNets combine a large number of arithmetic operations in a single monolithic einsum-operation. We show that the implementation of Expectation-Maximization (EM) can be simplified for PCs, by leveraging automatic differentiation.
  arXiv  Detail & Related papers  (2020-04-13T23:09:15Z)

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.