Timezone: »
We introduce #opt, a new inference task for graphical models which calls for counting the number of optimal solutions of the model. We describe a novel variable elimination based approach for solving this task, as well as a depth-first branch and bound algorithm that traverses the AND/OR search space of the model. The key feature of the proposed algorithms is that their complexity is exponential in the induced width of the model only. It does not depend on the actual number of optimal solutions. Our empirical evaluation on various benchmarks demonstrates the effectiveness of the proposed algorithms compared with existing depth-first and best-first search based approaches that enumerate explicitly the optimal solutions.
Author Information
Radu Marinescu (IBM Research)
Rina Dechter (UCI)
Related Events (a corresponding poster, oral, or spotlight)
-
2019 Spotlight: Counting the Optimal Solutions in Graphical Models »
Wed. Dec 11th 06:35 -- 06:40 PM Room West Ballroom C
More from the Same Authors
-
2023 Poster: Credal Marginal MAP »
Radu Marinescu · Debarun Bhattacharjya · Junkyu Lee · Fabio Cozman · Alexander Gray -
2022 Poster: Hedging as Reward Augmentation in Probabilistic Graphical Models »
Debarun Bhattacharjya · Radu Marinescu -
2022 Poster: Logical Credal Networks »
Radu Marinescu · Haifeng Qian · Alexander Gray · Debarun Bhattacharjya · Francisco Barahona · Tian Gao · Ryan Riegel · Pravinda Sahu -
2018 Poster: From Stochastic Planning to Marginal MAP »
Hao(Jackson) Cui · Radu Marinescu · Roni Khardon -
2017 Poster: Dynamic Importance Sampling for Anytime Bounds of the Partition Function »
Qi Lou · Rina Dechter · Alexander Ihler -
2015 : Discussion Panel with Morning Speakers (Day 1) »
Pedro Domingos · Stephen H Muggleton · Rina Dechter · Josh Tenenbaum -
2015 : Unifying Symbolic and Probabilistic Reasoning via Mixed Graphical Models »
Rina Dechter -
2015 Poster: Parallel Recursive Best-First AND/OR Search for Exact MAP Inference in Graphical Models »
Akihiro Kishimoto · Radu Marinescu · Adi Botea