SymCircuit: Bayesian Structure Inference for Tractable Probabilistic Circuits via Entropy-Regularized Reinforcement Learning

This cumulative habilitation thesis studies probabilistic circuits (PCs) as a powerful and tractable framework for reasoning and learning under uncertainty in artificial intelligence (AI). It first advocates for probability as a core language for AI, emphasizing its connections to logic and information theory; the conceptual simplicity of probabilistic reasoning---based primarily on the sum and product rules; the parallels between probabilistic inference and human cognition; and the role of probability in optimal decision making. However, probability also faces significant computational challenges, as probabilistic inference is NP-hard in almost all probabilistic models. PCs address these challenges through structural constraints that ensure exact computation of a wide range of inference queries in polynomial time, such as marginals, conditionals, most probable explanations, expectations, and more advanced inference tasks. This thesis synthesizes a decade of research across foundations, algorithmic developments, and empirical validation of PCs. Key contributions highlighted in this work are foundational theory of PCs, Bayesian approaches for learning PCs, scalable implementations and integration with deep learning, hybrid models that combine PCs with intractable models, and connections with symbolic machine learning paradigms. This is the first part of my Habilitation Thesis. The second part is omitted, as it comprises the cumulative part of the thesis and has been published at various venues (see Chapter 5).

Motivated by auto-proof generation and Valiant's VP vs. VNP conjecture, we study the problem of discovering efficient arithmetic circuits to compute polynomials, using addition and multiplication gates. We formulate this problem as a single-player game, where an RL agent attempts to build the circuit within a fixed number of operations. We implement an AlphaZero-style training loop and compare two approaches: Proximal Policy Optimization with Monte Carlo Tree Search (PPO+MCTS) and Soft Actor-Critic (SAC). SAC achieves the highest success rates on two-variable targets, while PPO+MCTS scales to three variables and demonstrates steady improvement on harder instances. These results suggest that polynomial circuit synthesis is a compact, verifiable setting for studying self-improving search policies.

Probabilistic circuits (PCs) are generative models that support efficient probabilistic inference. Adding latent states to a PC increases its representational capacity, but yields diminishing gains in likelihood. We use mutual information to examine how the dependence represented by a trained PC changes with latent size. Experiments with Hidden Chow-Liu Trees (HCLTs) on ImageNet32 show that learned dependence grows slowly and remains well below both the latent-state upper bound and estimates of dependence in the data. To understand how learning uses these states, we examine how strongly each sample favors particular latent states and how broadly states are used across the dataset. Tracking these measurements during HCLT training distinguishes rapid early posterior concentration from the more gradual stabilization of sample-dependent state preferences. Early measurements also guide initialization selection in HCLTs and hidden Markov models (HMMs), as well as tree selection in HCLTs. The resulting choices improve the ultimate performance across the tested latent sizes, providing a practical benefit from our study of latent-state utilization.