Timezone: »
Lifted inference algorithms exploit symmetries in probabilistic models to speed up inference. They show impressive performance when calculating unconditional probabilities in relational models, but often resort to non-lifted inference when computing conditional probabilities. The reason is that conditioning on evidence breaks many of the model's symmetries, which preempts standard lifting techniques. Recent theoretical results show, for example, that conditioning on evidence which corresponds to binary relations is #P-hard, suggesting that no lifting is to be expected in the worst case. In this paper, we balance this grim result by identifying the Boolean rank of the evidence as a key parameter for characterizing the complexity of conditioning in lifted inference. In particular, we show that conditioning on binary evidence with bounded Boolean rank is efficient. This opens up the possibility of approximating evidence by a low-rank Boolean matrix factorization, which we investigate both theoretically and empirically.
Author Information
Guy Van den Broeck (UCLA)
Adnan Darwiche (UCLA)
Related Events (a corresponding poster, oral, or spotlight)
-
2013 Spotlight: On the Complexity and Approximation of Binary Evidence in Lifted Inference »
Fri. Dec 6th 06:22 -- 06:26 PM Room Harvey's Convention Center Floor, CC
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 -
2015 Poster: Tractable Learning for Complex Probability Queries »
Jessa Bekker · Jesse Davis · Arthur Choi · Adnan Darwiche · Guy Van den Broeck -
2014 Poster: Decomposing Parameter Estimation Problems »
Khaled Refaat · Arthur Choi · 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