About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
AAAI 2015
Conference paper
Weighted best-first search for W-Optimal solutions over graphical models
Abstract
The paper explores the potential of weighted best-first search schemes as anytime optimization algorithms for solving graphical models tasks such as MPE (Most Probable Explanation) or MAP (Maximum a Posteriori) and WCSP (Weighted Constraint Satisfaction Problem). While such schemes were widely investigated for path-finding tasks, their application for graphical models was largely ignored, possibly due to their memory requirements. Compared to the depth-first branch and bound, which has long been the algorithm of choice for optimization in graphical models, a valuable virtue of weighted best-first search is that they are tu-optimal, i.e. when terminated, they return a solution cost C and a weight w, such that C < w - C∗> where C∗ is the optimal cost. We report on a significant empirical evaluation, demonstrating the usefulness of weighted best-first search as approximation anytime schemes (that have suboptimality bounds) and compare against one of the best depth-first branch and bound solver to date. We also investigate the impact of different heuristic functions on the behaviour of the algorithms.