The Experts below are selected from a list of 327 Experts worldwide ranked by ideXlab platform
Rina Dechter - One of the best experts on this subject based on the ideXlab platform.
-
A general scheme for automatic generation of search heuristics from specification dependencies☆☆Preliminary versions of this paper were presented in [15,16,18]. This work was supported in part by NSF grant IIS-0086529 and by MURI ONR award N00014-00-
Artificial Intelligence, 2020Co-Authors: Kalev Kask, Rina DechterAbstract:AbstractThe paper presents and evaluates the power of a new scheme that generates search heuristics mechanically for problems expressed using a set of functions or relations over a finite set of variables. The heuristics are extracted from a parameterized approximation scheme called Mini-Bucket Elimination that allows controlled trade-off between computation and accuracy. The heuristics are used to guide Branch-and-Bound and Best-First search. Their performance is compared on two optimization tasks: the Max-CSP task defined on deterministic databases and the Most Probable Explanation task defined on probabilistic databases. Benchmarks were random data sets as well as applications to coding and medical diagnosis problems. Our results demonstrate that the heuristics generated are effective for both search schemes, permitting controlled trade-off between preprocessing (for heuristic generation) and search
-
ISAIM - Evaluating Partition Strategies for Mini-Bucket Elimination
2020Co-Authors: Emma Rollón, Rina DechterAbstract:Mini-Bucket Elimination(MBE) is a well-known approximation algorithm for graphical models. It relies on a procedure to partition a set of funtions, called Bucket, into smaller subsets, called mini-Buckets. The impact of the partition process on the quality of the bound computed has never been investigated before. We take first steps to address this issue by presenting a framework within which partition strategies can be described, analyzed and compared. We derive a new class of partition heuristics from first-principles and demonstrate its impact on a number of benchmarks for probabilistic reasoning.
-
SOCS - Beyond Static Mini-Bucket: Towards Integrating with Iterative Cost-Shifting Based Dynamic Heuristics
2014Co-Authors: Kalev Kask, Rina Dechter, Alexander T IhlerAbstract:We explore the use of iterative cost-shifting as a dynamic heuristic generator for solving MPE in graphical models via Branch and Bound. When mini-Bucket Elimination is limited by its memory budget, it may not provide good heuristics. This can happen often when the graphical model has a very high induced width with large variable domain sizes. In addition, we explore a hybrid setup where both MBE and the iterative cost-shifting bound are used in a combined heuristic. We compare these approaches with the most advanced statically generated heuristics.
-
Reasoning with Probabilistic and Deterministic Graphical Models: Exact Algorithms
2013Co-Authors: Rina DechterAbstract:Graphical models (e.g., Bayesian and constraint networks, influence diagrams, and Markov decision processes) have become a central paradigm for knowledge representation and reasoning in both artificial intelligence and computer science in general. These models are used to perform many reasoning tasks, such as scheduling, planning and learning, diagnosis and prediction, design, hardware and software verification, and bioinformatics. These problems can be stated as the formal tasks of constraint satisfaction and satisfiability, combinatorial optimization, and probabilistic inference. It is well known that the tasks are computationally hard, but research during the past three decades has yielded a variety of principles and techniques that significantly advanced the state of the art. In this book we provide comprehensive coverage of the primary exact algorithms for reasoning with such models. The main feature exploited by the algorithms is the model's graph. We present inference-based, message-passing schemes (e.g., variable-Elimination) and search-based, conditioning schemes (e.g., cycle-cutset conditioning and AND/OR search). Each class possesses distinguished characteristics and in particular has different time vs. space behavior. We emphasize the dependence of both schemes on few graph parameters such as the treewidth, cycle-cutset, and (the pseudo-tree) height. We believe the principles outlined here would serve well in moving forward to approximation and anytime-based schemes. The target audience of this book is researchers and students in the artificial intelligence and machine learning area, and beyond. Table of Contents: Preface / Introduction / What are Graphical Models / Inference: Bucket Elimination for Deterministic Networks / Inference: Bucket Elimination for Probabilistic Networks / Tree-Clustering Schemes / AND/OR Search Spaces and Algorithms for Graphical Models / Combining Search and Inference: Trading Space for Time / Conclusion / Bibliography / Author's Biography
-
IJCAI - Semiring-based mini-Bucket partitioning schemes
2013Co-Authors: Emma Rollón, Javier Larrosa, Rina DechterAbstract:Graphical models are one of the most prominent frameworks to model complex systems and efficiently query them. Their underlying algebraic properties are captured by a valuation structure that, most usually, is a semiring. Depending on the semiring of choice, we can capture probabilistic models, constraint networks, cost networks, etc. In this paper we address the partitioning problem which occurs in many approximation techniques such as mini-Bucket Elimination and joingraph propagation algorithms. Roghly speaking, subject to complexity bounds, the algorithm needs to find a partition of a set of factors such that best approximates the whole set. While this problem has been addressed in the past in a particular case, we present here a general description. Furthermore, we also propose a general partitioning scheme. Our proposal is general in the sense that it is presented in terms of a generic semiring with the only additional requirements of a division operation and a refinement of its order. The proposed algorithm instantiates to the particular task of computing the probability of evidence, but also applies directly to other important reasoning tasks. We demonstrate its good empirical behaviour on the problem of computing the most probable explanation.
Javier Larrosa - One of the best experts on this subject based on the ideXlab platform.
-
ToolBar: a state-of-the-art platform for WCSP
2020Co-Authors: S. Bouveret, Javier Larrosa, Federico Heras, Martí Sánchez, Thomas SchiexAbstract:A lot of work has been done recently around soft constraints. Following the work on algebraic structures (valued, semiring CSP), the class of weighted networks is now identified as one of the most important class: it is among the most difficult one and many practical problems (satellite scheduling, frequency assignment, computer aided musical composition, pedigree analysis, Max-SAT – useful in electronic design – or maximum probability explanation in Bayesian nets for examples) are actually instances or can easily reduce to weighted CSP. Several algorithms have been proposed for WCSP resolution, making the comparison of all these algorithms difficult to establish. We have started the collaborative CVS based development of ToolBar, a C experimental platform that integrates WCSP algorithms and benchmarks in an efficient implementation. ToolBar includes several recently published algorithms maintaining some form of local consistency for solving WCSP and Max-SAT [2, 1]. Currently node, arc, directional arc and full directional arc consistencies are available. Algorithms such as tree decomposition, Bucket Elimination, dominance testing, singleton arc consistency are currently being integrated. ToolBar also offers two languages to describe problems: one is a very basic language (called wcsp), in the spirit of MPS for linear programming, and the other is a higher macro language that makes problem description much easier and which expands in the first language. On the Max-SAT side, ToolBar is also able to read classical propositional CNF files. Bayesian net (ERGO) and weighted CNF files are being developed. The wcsp format is also readable by other solvers for WCSP including Incop (a local search engine for WCSP), Lvcsp (a lisp library of soft constraint algorithms) and Vcsp (a C++ library for VCSP with simplification techniques). Several benchmarks and random problem generators in these formats are available on the SoftCSP collaborative WIKI based web site. The benchmarks, for a current total of 1606 instances, are either locally generated problems or instances of known problems (DIMACS, JNH, CELAR, SPOT5) in the community. For most problems, a known upper bound is also provided.
-
IJCAI - Semiring-based mini-Bucket partitioning schemes
2013Co-Authors: Emma Rollón, Javier Larrosa, Rina DechterAbstract:Graphical models are one of the most prominent frameworks to model complex systems and efficiently query them. Their underlying algebraic properties are captured by a valuation structure that, most usually, is a semiring. Depending on the semiring of choice, we can capture probabilistic models, constraint networks, cost networks, etc. In this paper we address the partitioning problem which occurs in many approximation techniques such as mini-Bucket Elimination and joingraph propagation algorithms. Roghly speaking, subject to complexity bounds, the algorithm needs to find a partition of a set of factors such that best approximates the whole set. While this problem has been addressed in the past in a particular case, we present here a general description. Furthermore, we also propose a general partitioning scheme. Our proposal is general in the sense that it is presented in terms of a generic semiring with the only additional requirements of a division operation and a refinement of its order. The proposed algorithm instantiates to the particular task of computing the probability of evidence, but also applies directly to other important reasoning tasks. We demonstrate its good empirical behaviour on the problem of computing the most probable explanation.
-
CP - On mini-Buckets and the min-fill Elimination ordering
Principles and Practice of Constraint Programming – CP 2011, 2011Co-Authors: Emma Rollón, Javier LarrosaAbstract:Mini-Bucket Elimination (MBE) is a well-known approximation of Bucket Elimination (BE), deriving bounds on quantities of interest over graphical models. Both algorithms are based on the sequential transformation of the original problem by eliminating variables, one at a time. The order in which variables are eliminated is usually computed using the greedy min-fill heuristic. In the BE case, this heuristic has a clear intuition, because it faithfully represents the structure of the sequence of sub-problems that BE generates and orders the variables using a greedy criteria based on such structure. However, MBE produces a sequence of sub-problems with a different structure. Therefore, using the min-fill heuristic with MBE means that decisions are made using the structure of the sub-problems that BE would produce, which is clearly meaningless. In this paper we propose a modification of the min-fill ordering heuristic that takes into account this fact. Our experiments on a number of benchmarks over two important tasks (i.e., computing the probability of evidence and optimization) show that MBE using the new ordering is often far more accurate than using the standard one.
-
Bucket Elimination for multiobjective optimization problems
Journal of Heuristics, 2006Co-Authors: Emma Rollón, Javier LarrosaAbstract:Multiobjective optimization deals with problems involving multiple measures of performance that should be optimized simultaneously. In this paper we extend Bucket Elimination (BE), a well known dynamic programming generic algorithm, from mono-objective to multiobjective optimization. We show that the resulting algorithm, MO-BE, can be applied to true multi-objective problems as well as mono-objective problems with knapsack (or related) global constraints. We also extend mini-Bucket Elimination (MBE), the approximation form of BE, to multiobjective optimization. The new algorithm MO-MBE can be used to obtain good quality multi-objective lower bounds or it can be integrated into multi-objective branch and bound in order to increase its pruning efficiency. Its accuracy is empirically evaluated in real scheduling problems, as well as in Max-SAT-ONE and biobjective weighted minimum vertex cover problems.
-
mini Bucket Elimination with Bucket propagation
Lecture Notes in Computer Science, 2006Co-Authors: Emma Rollón, Javier LarrosaAbstract:Many important combinatorial optimization problems can be expressed as constraint satisfaction problems with soft constraints. When problems are too difficult to be solved exactly, approximation methods become the best option. Mini-Bucket Elimination (MBE) is a well known approximation method for combinatorial optimization problems. It has a control parameter z that allow us to trade time and space for accuracy. In practice, it is the space and not the time that limits the execution with high values of z. In this paper we introduce a new propagation phase that MBE should execute at each Bucket. The purpose of this propagation is to jointly process as much information as possible. As a consequence, the undesirable lose of accuracy caused by MBE when splitting functions into different mini-Buckets is minimized. We demonstrate our approach in scheduling, combinatorial auction and max-clique problems, where the resulting algorithm MBE p gives important percentage increments of the lower bound (typically 50% and up to 1566%) with only doubling the cpu time.
Kalev Kask - One of the best experts on this subject based on the ideXlab platform.
-
CP - New Search Heuristics for Max-CSP
Principles and Practice of Constraint Programming – CP 2000, 2020Co-Authors: Kalev KaskAbstract:This paper evaluates the power of a new scheme that generates search heuristics mechanically. This approach was presented and evaluated first in the context of optimization in belief networks. In this paper we extend this work to Max-CSP. The approach involves extracting heuristics from a parameterized approximation scheme called Mini-Bucket Elimination that allows controlled trade-off between computation and accuracy. The heuristics are used to guide Branch-and-Bound and Best-First search, whose performance are compared on a number of constraint problems. Our results demonstrate that both search schemes exploit the heuristics effectively, permitting controlled trade-off between preprocessing (for heuristic generation) and search. These algorithms are compared with a state of the art complete algorithm as well as with the stochastic local search anytime approach, demonstrating superiority in some problem cases.
-
A general scheme for automatic generation of search heuristics from specification dependencies☆☆Preliminary versions of this paper were presented in [15,16,18]. This work was supported in part by NSF grant IIS-0086529 and by MURI ONR award N00014-00-
Artificial Intelligence, 2020Co-Authors: Kalev Kask, Rina DechterAbstract:AbstractThe paper presents and evaluates the power of a new scheme that generates search heuristics mechanically for problems expressed using a set of functions or relations over a finite set of variables. The heuristics are extracted from a parameterized approximation scheme called Mini-Bucket Elimination that allows controlled trade-off between computation and accuracy. The heuristics are used to guide Branch-and-Bound and Best-First search. Their performance is compared on two optimization tasks: the Max-CSP task defined on deterministic databases and the Most Probable Explanation task defined on probabilistic databases. Benchmarks were random data sets as well as applications to coding and medical diagnosis problems. Our results demonstrate that the heuristics generated are effective for both search schemes, permitting controlled trade-off between preprocessing (for heuristic generation) and search
-
SOCS - Beyond Static Mini-Bucket: Towards Integrating with Iterative Cost-Shifting Based Dynamic Heuristics
2014Co-Authors: Kalev Kask, Rina Dechter, Alexander T IhlerAbstract:We explore the use of iterative cost-shifting as a dynamic heuristic generator for solving MPE in graphical models via Branch and Bound. When mini-Bucket Elimination is limited by its memory budget, it may not provide good heuristics. This can happen often when the graphical model has a very high induced width with large variable domain sizes. In addition, we explore a hybrid setup where both MBE and the iterative cost-shifting bound are used in a combined heuristic. We compare these approaches with the most advanced statically generated heuristics.
-
Empirical Evaluation of Approximation Algorithms for Probabilistic Decoding
arXiv: Artificial Intelligence, 2013Co-Authors: Irina Rish, Kalev Kask, Rina DechterAbstract:It was recently shown that the problem of decoding messages transmitted through a noisy channel can be formulated as a belief updating task over a probabilistic network [McEliece]. Moreover, it was observed that iterative application of the (linear time) Pearl's belief propagation algorithm designed for polytrees outperformed state of the art decoding algorithms, even though the corresponding networks may have many cycles. This paper demonstrates empirically that an approximation algorithm approx-mpe for solving the most probable explanation (MPE) problem, developed within the recently proposed mini-Bucket Elimination framework [Dechter96], outperforms iterative belief propagation on classes of coding networks that have bounded induced width. Our experiments suggest that approximate MPE decoders can be good competitors to the approximate belief updating decoders.
-
Mini-Bucket Heuristics for Improved Search
arXiv: Artificial Intelligence, 2013Co-Authors: Kalev Kask, Rina DechterAbstract:The paper is a second in a series of two papers evaluating the power of a new scheme that generates search heuristics mechanically. The heuristics are extracted from an approximation scheme called mini-Bucket Elimination that was recently introduced. The first paper introduced the idea and evaluated it within Branch-and-Bound search. In the current paper the idea is further extended and evaluated within Best-First search. The resulting algorithms are compared on coding and medical diagnosis problems, using varying strength of the mini-Bucket heuristics. Our results demonstrate an effective search scheme that permits controlled tradeoff between preprocessing (for heuristic generation) and search. Best-first search is shown to outperform Branch-and-Bound, when supplied with good heuristics, and sufficient memory space.
Emma Rollón - One of the best experts on this subject based on the ideXlab platform.
-
ISAIM - Evaluating Partition Strategies for Mini-Bucket Elimination
2020Co-Authors: Emma Rollón, Rina DechterAbstract:Mini-Bucket Elimination(MBE) is a well-known approximation algorithm for graphical models. It relies on a procedure to partition a set of funtions, called Bucket, into smaller subsets, called mini-Buckets. The impact of the partition process on the quality of the bound computed has never been investigated before. We take first steps to address this issue by presenting a framework within which partition strategies can be described, analyzed and compared. We derive a new class of partition heuristics from first-principles and demonstrate its impact on a number of benchmarks for probabilistic reasoning.
-
IJCAI - Semiring-based mini-Bucket partitioning schemes
2013Co-Authors: Emma Rollón, Javier Larrosa, Rina DechterAbstract:Graphical models are one of the most prominent frameworks to model complex systems and efficiently query them. Their underlying algebraic properties are captured by a valuation structure that, most usually, is a semiring. Depending on the semiring of choice, we can capture probabilistic models, constraint networks, cost networks, etc. In this paper we address the partitioning problem which occurs in many approximation techniques such as mini-Bucket Elimination and joingraph propagation algorithms. Roghly speaking, subject to complexity bounds, the algorithm needs to find a partition of a set of factors such that best approximates the whole set. While this problem has been addressed in the past in a particular case, we present here a general description. Furthermore, we also propose a general partitioning scheme. Our proposal is general in the sense that it is presented in terms of a generic semiring with the only additional requirements of a division operation and a refinement of its order. The proposed algorithm instantiates to the particular task of computing the probability of evidence, but also applies directly to other important reasoning tasks. We demonstrate its good empirical behaviour on the problem of computing the most probable explanation.
-
CP - On mini-Buckets and the min-fill Elimination ordering
Principles and Practice of Constraint Programming – CP 2011, 2011Co-Authors: Emma Rollón, Javier LarrosaAbstract:Mini-Bucket Elimination (MBE) is a well-known approximation of Bucket Elimination (BE), deriving bounds on quantities of interest over graphical models. Both algorithms are based on the sequential transformation of the original problem by eliminating variables, one at a time. The order in which variables are eliminated is usually computed using the greedy min-fill heuristic. In the BE case, this heuristic has a clear intuition, because it faithfully represents the structure of the sequence of sub-problems that BE generates and orders the variables using a greedy criteria based on such structure. However, MBE produces a sequence of sub-problems with a different structure. Therefore, using the min-fill heuristic with MBE means that decisions are made using the structure of the sub-problems that BE would produce, which is clearly meaningless. In this paper we propose a modification of the min-fill ordering heuristic that takes into account this fact. Our experiments on a number of benchmarks over two important tasks (i.e., computing the probability of evidence and optimization) show that MBE using the new ordering is often far more accurate than using the standard one.
-
GKR - Bucket and mini-Bucket schemes for m best solutions over graphical models
Lecture Notes in Computer Science, 2011Co-Authors: Natalia Flerova, Emma Rollón, Rina DechterAbstract:The paper focuses on the task of generating the first m best solutions for a combinatorial optimization problem defined over a graphical model (e.g., the m most probable explanations for a Bayesian network). We show that the m-best task can be expressed within the unifying framework of semirings making known inference algorithms defined and their correctness and completeness for the m-best task immediately implied. We subsequently describe elim-m-opt, a new Bucket Elimination algorithm for solving the m-best task, provide algorithms for its defining combination and marginalization operators and analyze its worst-case performance. An extension of the algorithm to the mini-Bucket framework provides bounds for each of the m best solutions. Empirical demonstrations of the algorithms with emphasis on their potential for approximations are provided.
-
AAAI - New mini-Bucket partitioning heuristics for bounding the probability of evidence
2010Co-Authors: Emma Rollón, Rina DechterAbstract:Mini-Bucket Elimination (MBE) is a well-known approximation algorithm deriving lower and upper bounds on quantities of interest over graphical models. It relies on a procedure that partitions a set of functions, called Bucket, into smaller subsets, called mini-Buckets. The method has been used with a single partitioning heuristic throughout, so the impact of the partitioning algorithm on the quality of the generated bound has never been investigated. This paper addresses this issue by presenting a framework within which partitioning strategies can be described, analyzed and compared. We derive a new class of partitioning heuristics from first-principles geared for likelihood queries, demonstrate their impact on a number of benchmarks for probabilistic reasoning and show that the results are competitive (often superior) to state-of-the-art bounding schemes.
Alexander T Ihler - One of the best experts on this subject based on the ideXlab platform.
-
NeurIPS - Lifted Weighted Mini-Bucket
2018Co-Authors: Nicholas Gallo, Alexander T IhlerAbstract:Many real-world problems, such as Markov Logic Networks (MLNs) with evidence, possess highly symmetric sub-structures but no exact symmetries. Efficiently exploiting the symmetric substructure of these problems to perform approximate inference is a challenge for which few principled methods exist. In this paper, we present a lifted variant of the Weighted Mini-Bucket Elimination algorithm which provides a principled way to 1) exploit the highly symmetric substructure of MLN models, and 2) incorporate high-order inference terms, which are necessary for high quality approximate inference. Our method maintains a concrete connection to the ground problem and has significant control over the accuracy-time trade-off of the approximation. Experimental results demonstrate good anytime performance and the utility of this class of approximations, especially in models with strong repulsive potentials.
-
incremental region selection for mini Bucket Elimination bounds
Uncertainty in Artificial Intelligence, 2015Co-Authors: Sholeh Forouzan, Alexander T IhlerAbstract:Region choice is a key issue for many approximate inference bounds. Mini-Bucket Elimination avoids the space and time complexity of exact inference by using a top-down partitioning approach that mimics the construction of a junction tree and aims to minimize the number of regions subject to a bound on their size; however, these methods rarely take into account functions' values. In contrast, message passing algorithms often use "cluster pursuit" methods to select regions, a bottom-up approach in which a predefined set of clusters (such as triplets) is scored and incrementally added. In this work, we develop a hybrid approach that balances the advantages of both perspectives, providing larger regions chosen in an intelligent, energy-based way. Our method is applicable to bounds on a variety of inference tasks, and we demonstrate its power empirically on a broad array of problem types.
-
UAI - Incremental region selection for mini-Bucket Elimination bounds
2015Co-Authors: Sholeh Forouzan, Alexander T IhlerAbstract:Region choice is a key issue for many approximate inference bounds. Mini-Bucket Elimination avoids the space and time complexity of exact inference by using a top-down partitioning approach that mimics the construction of a junction tree and aims to minimize the number of regions subject to a bound on their size; however, these methods rarely take into account functions' values. In contrast, message passing algorithms often use "cluster pursuit" methods to select regions, a bottom-up approach in which a predefined set of clusters (such as triplets) is scored and incrementally added. In this work, we develop a hybrid approach that balances the advantages of both perspectives, providing larger regions chosen in an intelligent, energy-based way. Our method is applicable to bounds on a variety of inference tasks, and we demonstrate its power empirically on a broad array of problem types.
-
SOCS - Beyond Static Mini-Bucket: Towards Integrating with Iterative Cost-Shifting Based Dynamic Heuristics
2014Co-Authors: Kalev Kask, Rina Dechter, Alexander T IhlerAbstract:We explore the use of iterative cost-shifting as a dynamic heuristic generator for solving MPE in graphical models via Branch and Bound. When mini-Bucket Elimination is limited by its memory budget, it may not provide good heuristics. This can happen often when the graphical model has a very high induced width with large variable domain sizes. In addition, we explore a hybrid setup where both MBE and the iterative cost-shifting bound are used in a combined heuristic. We compare these approaches with the most advanced statically generated heuristics.
-
UAI - Join-graph based cost-shifting schemes
2012Co-Authors: Alexander T Ihler, Rina Dechter, Natalia Flerova, Lars OttenAbstract:We develop several algorithms taking advantage of two common approaches for bounding MPE queries in graphical models: mini-Bucket Elimination and message-passing updates for linear programming relaxations. Both methods are quite similar, and offer useful perspectives for the other; our hybrid approaches attempt to balance the advantages of each. We demonstrate the power of our hybrid algorithms through extensive empirical evaluation. Most notably, a Branch and Bound search guided by the heuristic function calculated by one of our new algorithms has recently won first place in the PASCAL2 inference challenge.
