Bayesian Structure Scores for Probabilistic Circuits

1 INTRODUCTION

• Existing PC structure learners commonly use heuristics, explicit objectives are absent, and many require numerous hyper-parameters or validation data.These methods include clustering-, decomposition-, information-bottleneck-, decision-tree-, and heuristic-score-based approaches.Source: §1 · pp. 1–2
• Bayesian structure scores marginalize PC parameters, providing a principled objective that can protect against overfitting complex structures.The approach targets deterministic PCs and averages over parameter choices under suitable priors.Source: §1 · p. 2
• The discrete-data specialization yields the Bayes-Dirichlet score, which is used with greedy cutset learning using ESS fixed at 0.1.The resulting procedure is effectively hyper-parameter-free while retaining a simple and fast search scheme.Source: §1 · p. 2
• The corrected BIC score improves on an earlier PC formulation and provides an efficient alternative to the full BD score.Both scores are asymptotically equivalent, but the earlier BIC version undercounted the number of parameters.Source: §1 · p. 2
• Across 20 benchmark density-estimation datasets, BD and BIC models are competitive with state of the art, while the learners often lie on the training-time/test-log-likelihood Pareto front.The comparisons include simple default-parameter learners and extensively tuned methods requiring orders of magnitude more computation.Source: §1 · p. 2
• Because Bayesian scores are marginal structure likelihoods, they support structural EM for PC mixtures, which consistently improves over single BD-learned PCs and approaches or exceeds state of the art.The structural E-step uses posterior-predictive responsibilities, and the structural M-step updates mixture weights and learns from fractional samples.Source: §1 · p. 2

2 PROBABILISTIC CIRCUITS

• A probabilistic circuit is a directed acyclic graph whose distribution, sum, and product nodes compute over variable scopes.Leaves represent parametric distributions, sums form convex combinations, and products multiply inputs.Source: §2 · pp. 2–3
• The circuit parameters comprise leaf-distribution parameters and weights attached to sum nodes, with a single output node representing the model distribution.The output can be evaluated by a feed-forward pass for any input sample.Source: §2 · p. 3
• Decomposability and smoothness ensure normalized node distributions and enable linear-time marginal and conditional inference.The paper assumes both properties throughout.Source: §2 · p. 3
• Determinism requires at most one nonzero sum-node input for each sample and additionally enables tractable MPE and exact maximum-likelihood parameter computation.In this paper, determinism also permits exact and efficient Bayesian structure-score computation.Source: §2 · p. 3
• Structured decomposability imposes a shared vtree pattern on product decompositions and supports expectations between circuits and divergence computation.These capabilities extend the inference operations available from ordinary decomposability and smoothness.Source: §2 · p. 3
• The paper positions Bayesian scores as principled objectives for the otherwise ad-hoc problem of PC structure learning.This motivates transferring score-based structure-learning ideas from probabilistic graphical models to PCs.Source: §2 · p. 3

Bayesian scores

• Bayesian structure scores evaluate PC structures through marginal likelihood after integrating out parameters under structure-dependent priors.The score can also serve as an optimization target or be embedded in structural Bayesian methods and structural EM.Source: §3 · p. 3

Determinism

• For deterministic PCs, structural and parameter-consistent determinism ensure that the active induced tree for each sample remains fixed across parameter values.This property enables the integrals to factor across sum weights and leaf parameters.Source: §3 · pp. 4–5

Tree decomposition

• The tree decomposition rewrites a deterministic PC as a mixture over induced trees, with each term containing the relevant sum weights and leaf distributions.For decomposable deterministic PCs, at most one induced-tree term is nonzero for each sample, and it can be found by tracing active inputs from root to leaves.Source: §3 · pp. 4–5

Closed-form scores

• The resulting score combines tractable local integrals for sum weights and leaves, recovering Bayes-Dirichlet scores for categorical leaves and allowing Bayesian-Gaussian scores for Gaussian leaves.Leaf integrals are tractable for several exponential-family distributions with conjugate priors.Source: §3 · pp. 4–5

BIC definition

• BIC scores PC structures using maximum-likelihood log-likelihood minus a complexity penalty based on independent parameters and training-set size.The penalty is proportional to ∥G∥ log|D|.Source: §4 · p. 5

Parameter counting

• Correctly counting Chow-Liu-tree parameters strengthens BIC’s penalty and improves generalization relative to an earlier CNet formulation.The earlier formulation counted conditioning nodes but omitted parameters in the contained trees.Source: §4 · p. 5

Search motivation

• The search is motivated by the presumed NP-hardness of globally optimizing over deterministic PC structures, so greedy navigation provides a practical alternative.The presented setting focuses on binary data, although cutset learning can be generalized to continuous data.Source: §5 · p. 5

Cutset networks

• Cutset networks are binary decision trees whose leaves are Chow-Liu trees over variables not previously conditioned along each root-to-leaf path.Decision-edge weights multiply with the selected leaf’s probability, and CNets compile to smooth, deterministic, decomposable PCs.Source: §5 · p. 6

Score-based cutset learning

• Cutset learning recursively selects conditioning variables whose resulting CNet and conditional Chow-Liu leaves obtain the highest structure score.The search compares candidate cuts against the unconditioned Chow-Liu tree and stops when no score improvement remains.Source: §5 · p. 6

Search efficiency

• The method restricts evaluation to the λ most promising variables according to information gain, reducing runtime while preserving reported performance.The candidate restriction scales linearly with the number of variables tested.Source: §5 · p. 6

• Bayesian structure scores can be incorporated into structural expectation-maximization because they are marginal likelihoods of circuit structures.Source: EXPECTATION-MAXIMIZATION · p. 6
• The approach applies structural expectation-maximization to mixtures of cutset networks.Source: EXPECTATION-MAXIMIZATION · p. 6
• Responsibilities computed during the structural E-step guide mixture-weight updates and fractional samples for cutset learning in the structural M-step.Source: EXPECTATION-MAXIMIZATION · p. 6

7 EXPERIMENTS

• The experiments cover density estimation and image completion with binary data, comparing Bayesian-score cutset learners against established probabilistic-circuit structure learners.Source: §7 · p. 7

7.1 Standard Density Estimation Benchmarks

• Fixed α = 0.1 for CNetBD and β = 0.01 for CNetBIC make both methods effectively hyper-parameter-free across benchmark data sets.Source: §7.1 · p. 7
• CNetBD and CNetBIC are Pareto-efficient on most data sets, leading fast methods and often outperforming or matching Strudel and LearnSPN.Source: §7.1 · p. 7
• Structural-EM mixtures consistently improve over single models and approach or surpass state-of-the-art probabilistic circuits.Source: §7.1 · p. 7

7.2 Binary MNIST

• CNetBD with 50K parameters reaches −118.71 test log-likelihood on Binary-MNIST, while its 300-component mixture reaches −103.95 with 470K parameters.Source: §7.2 · p. 7
• Binary-MNIST samples become more plausible as mixture components increase, and mixture models produce plausible reconstructions in approximate-MPE inpainting.Source: §7.2 · p. 7

8 CONCLUSION

• Bayesian and corrected BIC scores enabled a simple structure learner to work effectively without extensive cross-validation or early-stopping defenses.The authors report that both scores can protect against overfitting while remaining effective and efficient.Source: §8 · p. 9
• The proposed scores are restricted to deterministic circuits, with approximations to non-deterministic PCs identified as a future direction.Suggested routes include sampling, variational techniques, continuous relaxations, and numeric integration.Source: §8 · p. 9
• Theoretical consistency of Bayesian and BIC scores for PCs remains unproved, despite analogous results for probabilistic graphical models.The authors suggest that such properties might explain the similar experimental performance of BD and BIC scores.Source: §8 · p. 9

A Learning a Chow-Liu Tree

• LEARNCLT computes mutual information, constructs a maximum-spanning tree, directs its edges, and estimates posterior parameters, with complexity O(|X|^2|D|).The algorithm takes a dataset and equivalent sample size as inputs and returns a parameterized Chow-Liu tree.Source: A Learning a Chow-Liu Tree · p. 12

B Candidate Selection Heuristic

• The candidate-selection heuristic ranks variables by information gain and retains the top λ variables as conditioning candidates.Information gain is interpreted as expected entropy reduction from conditioning.Source: B Candidate Selection Heuristic · p. 12

C.1 Data Sets

• The twenty benchmark density-estimation datasets contain between 16 and 1556 variables.The dataset characteristics are summarized in Table 2.Source: §C.1 · p. 12, Table 2 · p. 13

C.2 Learning Time

• CNetBD and CNetBIC achieve a better trade-off between test log-likelihood and training time than the compared structure learners.Learning times are measured in total seconds during training.Source: §C.2 · p. 12, Table 3 · p. 13

C.3 Circuit Size

• CNetBD and CNetBIC produce much smaller circuits than other cutset learners on almost all datasets while often achieving leading performance.Circuit size is measured by the number of independent parameters.Source: §C.3 · p. 12, Table 4 · p. 13