Logic and Probabilistic Circuits 1
summary
Main claim: represent probability models as layered computation graphs so many queries become provably efficient when the circuit enforces decomposability (products over disjoint variable sets) and smoothness (sum children share scope). Concrete contrasts: GANs and VAEs have no tractable likelihood; normalizing flows give likelihood but not marginals; Bayesian-network marginals are #P‑hard and marginal‑MAP is NP^PP‑complete, while treewidth ≤ ~20 is practical and Chow‑Liu learns optimal trees. Circuits evaluate likelihoods by feedforward sums/products, and with the right structure compute marginals and MAP in time linear in circuit size.
AI-written summary · about
chapters (12)
- 0:00Introduction to circuits
- 2:52Tutorial agenda and models
- 8:36Query types and tractability
- 12:12Intractable generative models
- 20:06Graphical models and width
- 24:29Tree distributions and mixtures
- 26:46Expressive efficiency challenges
- 31:43Advanced query classes
- 37:15Tractable distribution types
- 39:29Designing probabilistic circuits
- 52:15Circuit properties
- 1:00:10Q&A and break
related talks
37mTractable Probabilistic Circuits
37mSolving Marginal MAP Exactly by Probabilistic Circuit Transformations
52mCredal Models for Uncertainty and Logic Treatment
07mProbabilistic Reasoning and Learning for Trustworthy AI
24mHigher order programming with probabilistic effects: A model of stochastic memo...
52mSubtractive Mixture Models: Representation and Learning
01h 08mGenerative Models
24mExact Bayesian Inference for Loopy Probabilistic Programs Using Generating Functions