Timezone: »

 
Spotlight
Smoothing Structured Decomposable Circuits
Andy Shih · Guy Van den Broeck · Paul Beame · Antoine Amarilli

Wed Dec 11 10:30 AM -- 10:35 AM (PST) @ West Ballroom C
in Track 4 Session 3 »

We study the task of smoothing a circuit, i.e., ensuring that all children of a plus-gate mention the same variables. Circuits serve as the building blocks of state-of-the-art inference algorithms on discrete probabilistic graphical models and probabilistic programs. They are also important for discrete density estimation algorithms. Many of these tasks require the input circuit to be smooth. However, smoothing has not been studied in its own right yet, and only a trivial quadratic algorithm is known. This paper studies efficient smoothing for structured decomposable circuits. We propose a near-linear time algorithm for this task and explore lower bounds for smoothing decomposable circuits, using existing results on range-sum queries. Further, for the important case of All-Marginals, we show a more efficient linear-time algorithm. We validate experimentally the performance of our methods.

[ Paper]  [ Poster]  [ Slides] 

Author Information

Andy Shih (UCLA / Stanford)
Guy Van den Broeck (UCLA)

I am an Assistant Professor and Samueli Fellow at UCLA, in the Computer Science Department, where I direct the Statistical and Relational Artificial Intelligence (StarAI) lab. My research interests are in Machine Learning (Statistical Relational Learning, Tractable Learning), Knowledge Representation and Reasoning (Graphical Models, Lifted Probabilistic Inference, Knowledge Compilation), Applications of Probabilistic Reasoning and Learning (Probabilistic Programming, Probabilistic Databases), and Artificial Intelligence in general.

Paul Beame (University of Washington)
Antoine Amarilli (LTCI, Télécom ParisTech)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors