Fourier Representations in Probabilistic Inference

on YouTube ↗31m

" summary

Claim: Boolean probability tables for bounded‑width factor graphs have most L2 mass on low‑degree Hadamard/Fourier basis coefficients, so truncating high‑order terms gives provable L2 approximations. Technical tool: an extension of the Håstad switching lemma via random restrictions to bound the Fourier tail. Implementation: variable‑elimination in the Fourier domain that keeps low‑degree or largest coefficients and drops the rest. Results: on UAI partition benchmarks exact solvers take ~2 hours, the Fourier method runs in minutes and cuts log10 error from ~3.9 down to ~10^-3–10^-6.

AI-written summary · about

" chapters (4)

1. 0:00Start
2. 6:28Linear Interpolation Formula
3. 22:10One Variable Elimination
4. 24:43Results

" related talks

• 01h 05mLogic and Probabilistic Circuits 1Guy Van den Broeck · Logic and Algorithms in Database Theory and AI Boot Camp
• 01h 03mLogic and Probabilistic Circuits 2YooJung Choi · Logic and Algorithms in Database Theory and AI Boot Camp
• 01h 23mAnalytic Methods for Supervised Learning IAdam R. Klivans · Real Analysis Boot Camp 2013
• 01h 30mAnalytic Methods for Supervised Learning IIAdam R. Klivans · Real Analysis Boot Camp 2013
• 01h 11mPedagogical Talk: Failure of Low-Degree PolynomialsAlex Wein · Computational Phase Transitions (Simons Institute, 2020)
• 20mStatic Posterior Inference of Bayesian Probabilistic Programming via Polynomial SolvingGuanyan Li, Peixin Wang, Hongfei Fu, Tengshun Yang, C.-H. Luke Ong · PLDI 2024
• 24mExact Bayesian Inference for Loopy Probabilistic Programs Using Generating FunctionsLutz Klinkenberg, Christian Blumenthal, Mingshuai Chen, Darion Haase, Joost-Pieter Katoen · OOPSLA 2024
• 30mPreconditioning In Sparse Linear Regression Using Graphical StructureFrederic Koehler · Algorithmic Aspects of Causal Inference 2022