Timezone: »
Poster
Tractable Learning for Complex Probability Queries
Jessa Bekker · Jesse Davis · Arthur Choi · Adnan Darwiche · Guy Van den Broeck
Tractable learning aims to learn probabilistic models where inference is guaranteed to be efficient. However, the particular class of queries that is tractable depends on the model and underlying representation. Usually this class is MPE or conditional probabilities $\Pr(\xs|\ys)$ for joint assignments~$\xs,\ys$. We propose a tractable learner that guarantees efficient inference for a broader class of queries. It simultaneously learns a Markov network and its tractable circuit representation, in order to guarantee and measure tractability. Our approach differs from earlier work by using Sentential Decision Diagrams (SDD) as the tractable language instead of Arithmetic Circuits (AC). SDDs have desirable properties, which more general representations such as ACs lack, that enable basic primitives for Boolean circuit compilation. This allows us to support a broader class of complex probability queries, including counting, threshold, and parity, in polytime.
Author Information
Jessa Bekker (KU Leuven)
Jesse Davis (KU Leuven)
Arthur Choi (UCLA)
Adnan Darwiche (UCLA)
Guy Van den Broeck (UCLA)
More from the Same Authors
-
2021 Spotlight: Tractable Regularization of Probabilistic Circuits »
Anji Liu · Guy Van den Broeck -
2021 : Causal Inference Using Tractable Circuits »
Adnan Darwiche -
2022 : On the Complexity of Counterfactual Reasoning »
Yunqiu Han · Yizuo Chen · Adnan Darwiche -
2021 Poster: A Compositional Atlas of Tractable Circuit Operations for Probabilistic Inference »
Antonio Vergari · YooJung Choi · Anji Liu · Stefano Teso · Guy Van den Broeck -
2021 Oral: A Compositional Atlas of Tractable Circuit Operations for Probabilistic Inference »
Antonio Vergari · YooJung Choi · Anji Liu · Stefano Teso · Guy Van den Broeck -
2021 Poster: Tractable Regularization of Probabilistic Circuits »
Anji Liu · Guy Van den Broeck -
2017 Poster: Tractability in Structured Probability Spaces »
Arthur Choi · Yujia Shen · Adnan Darwiche -
2016 Poster: Learning Bayesian networks with ancestral constraints »
Eunice Yuh-Jie Chen · Yujia Shen · Arthur Choi · Adnan Darwiche -
2016 Poster: New Liftable Classes for First-Order Probabilistic Inference »
Seyed Mehran Kazemi · Angelika Kimmig · Guy Van den Broeck · David Poole -
2016 Poster: Tractable Operations for Arithmetic Circuits of Probabilistic Models »
Yujia Shen · Arthur Choi · Adnan Darwiche -
2016 Oral: Tractable Operations for Arithmetic Circuits of Probabilistic Models »
Yujia Shen · Arthur Choi · Adnan Darwiche -
2014 Poster: Decomposing Parameter Estimation Problems »
Khaled Refaat · Arthur Choi · Adnan Darwiche -
2013 Poster: First-order Decomposition Trees »
Nima Taghipour · Jesse Davis · Hendrik Blockeel -
2013 Poster: On the Complexity and Approximation of Binary Evidence in Lifted Inference »
Guy Van den Broeck · Adnan Darwiche -
2013 Spotlight: On the Complexity and Approximation of Binary Evidence in Lifted Inference »
Guy Van den Broeck · Adnan Darwiche -
2013 Poster: EDML for Learning Parameters in Directed and Undirected Graphical Models »
Khaled Refaat · Arthur Choi · Adnan Darwiche -
2011 Poster: On the Completeness of First-Order Knowledge Compilation for Lifted Probabilistic Inference »
Guy Van den Broeck -
2011 Oral: On the Completeness of First-Order Knowledge Compilation for Lifted Probabilistic Inference »
Guy Van den Broeck -
2009 Poster: Approximating MAP by Compensating for Structural Relaxations »
Arthur Choi · Adnan Darwiche