Timezone: »
We introduce a new perspective on approximations to the maximum a posteriori (MAP) task in probabilistic graphical models, that is based on simplifying a given instance, and then tightening the approximation. First, we start with a structural relaxation of the original model. We then infer from the relaxation its deficiencies, and compensate for them. This perspective allows us to identify two distinct classes of approximations. First, we find that max-product belief propagation can be viewed as a way to compensate for a relaxation, based on a particular idealized case for exactness. We identify a second approach to compensation that is based on a more refined idealized case, resulting in a new approximation with distinct properties. We go on to propose a new class of algorithms that, starting with a relaxation, iteratively yields tighter approximations.
Author Information
Arthur Choi (UCLA)
Adnan Darwiche (UCLA)
More from the Same Authors
-
2021 : Causal Inference Using Tractable Circuits »
Adnan Darwiche -
2022 : On the Complexity of Counterfactual Reasoning »
Yunqiu Han · Yizuo Chen · Adnan Darwiche -
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: 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: 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