Rina Dechter

ECAI Conference 2024 Conference Paper

Estimating Causal Effects from Learned Causal Networks

• Anna Raichev
• Jin Tian
• Alexander Ihler
• Rina Dechter

The standard approach to answering an identifiable causal-effect query (e. g. , P(Y|do(X)) given a causal diagram and observational data is to first generate an estimand, or probabilistic expression over the observable variables, which is then evaluated using the observational data. In this paper, we propose an alternative paradigm for answering causal-effect queries over discrete observable variables. We propose to instead learn the causal Bayesian network and its confounding latent variables directly from the observational data. Then, efficient probabilistic graphical model (PGM) algorithms can be applied to the learned model to answer queries. Perhaps surprisingly, we show that this model completion learning approach can be more effective than estimand approaches, particularly for larger models in which the estimand expressions become computationally difficult. We illustrate our method’s potential using a benchmark collection of Bayesian networks and synthetically generated causal models.

UAI Conference 2024 Conference Paper

Value-Based Abstraction Functions for Abstraction Sampling

• Bobak Pezeshki
• Kalev Kask
• Alexander Ihler
• Rina Dechter

Monte Carlo methods are powerful tools for solving problems involving complex probability distributions. Despite their versatility, these methods often suffer from inefficiencies, especially when dealing with rare events. As such, importance sampling emerged as a prominent technique for alleviating these challenges. Recently, a new scheme called Abstraction Sampling was developed that incorporated stratification to importance sampling over graphical models. However, existing work only explored a limited set of abstraction functions that guide stratification. This study introduces three new classes of abstraction functions combined with seven distinct partitioning schemes, resulting in twenty-one new abstraction functions, each motivated by theory and intuition from both search and sampling domains. An extensive empirical analysis on over 400 problems compares these new schemes highlighting several well-performing candidates.

UAI Conference 2023 Conference Paper

Boosting AND/OR-based computational protein design: dynamic heuristics and generalizable UFO

• Bobak Pezeshki
• Radu Marinescu 0002
• Alexander Ihler
• Rina Dechter

Scientific computing has experienced a surge empowered by advancements in technologies such as neural networks. However, certain important tasks are less amenable to these technologies, benefiting from innovations to traditional inference schemes. One such task is protein re-design. Recently a new re-design algorithm, {AOBB-K\textsuperscript{*}}, was introduced and was competitive with state-of-the-art {BBK\textsuperscript{*}} on small protein re-design problems. However, {AOBB-K\textsuperscript{*}} did not scale well. In this work, we focus on scaling up {AOBB-K\textsuperscript{*}} and introduce three new versions: {AOBB-K\textsuperscript{*}}-b (boosted), {AOBB-K\textsuperscript{*}}-{DH} (with dynamic heuristics), and {AOBB-K\textsuperscript{*}}-{UFO} (with underflow optimization) that significantly enhance scalability.

UAI Conference 2022 Conference Paper

AND/OR branch-and-bound for computational protein design optimizing K

• Bobak Pezeshki
• Radu Marinescu 0002
• Alexander Ihler
• Rina Dechter

The importance of designing proteins, such as high affinity antibodies, has become ever more apparent. Computational Protein Design can cast such design problems as optimization tasks with the objective of maximizing K*, an approximation of binding affinity. Here we lay out a graphical model framework for K* optimization that enables use of compact AND/OR search algorithms. We designed an AND/OR branch-and-bound algorithm, AOBB-K*, for optimizing K* that is guided by a new K* heuristic and can incorporate specialized performance improvements with theoretical guarantees. As AOBB-K* is inspired by algorithms from the well studied task of Marginal MAP, this work provides a foundation for harnessing advancements in state-of-the-art mixed inference schemes and adapting them to protein design.

UAI Conference 2022 Conference Paper

NeuroBE: Escalating neural network approximations of Bucket Elimination

• Sakshi Agarwal
• Kalev Kask
• Alexander Ihler
• Rina Dechter

A major limiting factor in graphical model inference is the complexity of computing the partition function. Exact message-passing algorithms such as Bucket Elimination (BE) require exponential memory to compute the partition function; therefore, approximations are necessary. In this paper, we build upon a recently introduced methodology called Deep Bucket Elimination (DBE) that uses classical Neural Networks to approximate messages generated by BE for large buckets. The main feature of our new scheme, renamed NeuroBE, is that it customizes the architecture of the neural networks, their learning process and in particular, adapts the loss function to the internal form or distribution of messages. Our experiments demonstrate significant improvements in accuracy and time compared with the earlier DBE scheme.

AAAI Conference 2021 Conference Paper

A New Bounding Scheme for Influence Diagrams

• Radu Marinescu
• Junkyu Lee
• Rina Dechter

Influence diagrams provide a modeling and inference framework for sequential decision problems, representing the probabilistic knowledge by a Bayesian network and the preferences of an agent by utility functions over the random variables and decision variables. Computing the maximum expected utility (MEU) and the optimizing policy is exponential in the constrained induced width and therefore is notoriously difficult for larger models. In this paper, we develop a new bounding scheme for MEU that applies partitioning based approximations on top of the decomposition scheme called a multi-operator cluster DAG for influence diagrams that is more sensitive to the underlying structure of the model than the classical join-tree decomposition of influence diagrams. Our bounding scheme utilizes a cost-shifting mechanism to tighten the bound further. We demonstrate the effectiveness of the proposed scheme on various hard benchmarks.

AAMAS Conference 2021 Conference Paper

Approximating Spatial Evolutionary Games using Bayesian Networks

• Vincent Hsiao
• Xinyue Pan
• Dana Nau
• Rina Dechter

Evolutionary Game Theory is an application of game theory to evolving populations of organisms. Of recent interest are EGT models situated on structured populations or spatial evolutionary games. Due to the complexity added by introducing a population structure, model analysis is usually performed through agent-based Monte-Carlo simulations. However, it can be difficult to obtain desired quantities of interest from these simulations due to stochastic effects. We define a framework for modeling spatial evolutionary games using Dynamic Bayesian Networks that capture the underlying stochastic process. The resulting Dynamic Bayesian Networks can be queried for quantities of interest by performing exact inference on the network. We then propose a method for producing approximations of the spatial evolutionary game through the truncation of the corresponding DBN, taking advantage of the high symmetry of the model. This method generalizes mean-field and pair approximations in the literature for spatial evolutionary games. Furthermore, we show empirical results demonstrating the capability of the method to obtain much better accuracy than pair approximation with respect to stochastic simulations.

IJCAI Conference 2021 Conference Paper

Deep Bucket Elimination

• Yasaman Razeghi
• Kalev Kask
• Yadong Lu
• Pierre Baldi
• Sakshi Agarwal
• Rina Dechter

Bucket Elimination (BE) is a universal inference scheme that can solve most tasks over probabilistic and deterministic graphical models exactly. However, it often requires exponentially high levels of memory (in the induced-width) preventing its execution. In the spirit of exploiting Deep Learning for inference tasks, in this paper, we will use neural networks to approximate BE. The resulting Deep Bucket Elimination (DBE) algorithm is developed for computing the partition function. We provide a proof-of-concept empirically using instances from several different benchmarks, showing that DBE can be a more accurate approximation than current state-of-the-art approaches for approximating BE (e. g. the mini-bucket schemes), especially when problems are sufficiently hard.

AAAI Conference 2021 Conference Paper

Submodel Decomposition Bounds for Influence Diagrams

• Junkyu Lee
• Radu Marinescu
• Rina Dechter

Influence diagrams (IDs) are graphical models for representing and reasoning with sequential decision-making problems under uncertainty. Limited memory influence diagrams (LIMIDs) model a decision-maker (DM) who forgets the history in the course of making a sequence of decisions. The standard inference task in IDs and LIMIDs is to compute the maximum expected utility (MEU), which is one of the most challenging tasks in graphical models. We present a model decomposition framework in both IDs and LIMIDs, which we call submodel decomposition that generates a tree of single-stage decision problems through a tree clustering scheme. We also develop a valuation algebra over the submodels that leads to a hierarchical message passing algorithm that propagates conditional expected utility functions over a submodel-tree as external messages. We show that the overall complexity is bounded by the maximum tree-width over the submodels, common in graphical model algorithms. Finally, we present a new method for computing upper bounds over a submodel-tree by first exponentiating the utility functions yielding a standard probabilistic graphical model as an upper bound and then applying standard variational upper bounds for the marginal MAP inference, yielding tighter upper bounds compared with state-of-the-art bounding schemes for the MEU task.

SoCS Conference 2020 Conference Paper

Heuristic AND/OR Search for Solving Influence Diagram

• Junkyu Lee 0001
• Radu Marinescu 0002
• Rina Dechter

An influence diagram is a graphical representation of sequential decision-making under uncertainty, defining a structured decision problem by conditional probability functions and additive utility functions over discrete state and action variables. The task of finding the maximum expected utility of influence diagrams is closely related to the cost-optimal probabilistic planning, stochastic programmings, or model-based reinforcement learning. In this position paper, we address the heuristic search for solving influence diagram, where we generate admissible heuristic functions from graph decomposition schemes. Then, we demonstrate how such heuristics can guide an AND/OR branch and bound search. Finally, we briefly discuss the future directions for improving the quality of heuristic functions and search strategies.

IJCAI Conference 2020 Conference Paper

Scaling Up AND/OR Abstraction Sampling

• Kalev Kask
• Bobak Pezeshki
• Filjor Broka
• Alexander Ihler
• Rina Dechter

Abstraction Sampling (AS) is a recently introduced enhancement of Importance Sampling that exploits stratification by using a notion of abstractions: groupings of similar nodes into abstract states. It was previously shown that AS performs particularly well when sampling over an AND/OR search space; however, existing schemes were limited to ``proper'' abstractions in order to ensure unbiasedness, severely hindering scalability. In this paper, we introduce AOAS, a new Abstraction Sampling scheme on AND/OR search spaces that allow more flexible use of abstractions by circumventing the properness requirement. We analyze the properties of this new algorithm and, in an extensive empirical evaluation on five benchmarks, over 480 problems, and comparing against other state of the art algorithms, illustrate AOAS's properties and show that it provides a far more powerful and competitive Abstraction Sampling framework.

UAI Conference 2019 Conference Paper

A Weighted Mini-Bucket Bound for Solving Influence Diagram

• Junkyu Lee 0001
• Radu Marinescu 0002
• Alexander Ihler
• Rina Dechter

Influence diagrams provide a modeling and inference framework for sequential decision problems, representing the probabilistic knowledge by a Bayesian network and the preferences of an agent by utility functions over the random variables and decision variables. The time and space complexity of computing the maximum expected utility (MEU) and its maximizing policy are exponential in the induced width of the underlying graphical model, which is often prohibitively large. In this paper, we develop a weighted mini-bucket approach for bounding the MEU. These bounds can be used as a stand-alone approximation that can be improved as a function of a controlling i-bound parameter, or as a heuristic function to guide subsequent search. We evaluate the scheme empirically against the current state of the art, illustrating its potential.

AAAI Conference 2019 Conference Paper

Anytime Recursive Best-First Search for Bounding Marginal MAP

• Radu Marinescu
• Akihiro Kishimoto
• Adi Botea
• Rina Dechter
• Alexander Ihler

Marginal MAP is a difficult mixed inference task for graphical models. Existing state-of-the-art solvers for this task are based on a hybrid best-first and depth-first search scheme that allows them to compute upper and lower bounds on the optimal solution value in an anytime fashion. These methods however are memory intensive schemes (via the best-first component) and do not have an efficient memory management mechanism. For this reason, they are often less effective in practice, especially on difficult problem instances with very large search spaces. In this paper, we introduce a new recursive best-first search based bounding scheme that operates efficiently within limited memory and computes anytime upper and lower bounds that improve over time. An empirical evaluation demonstrates the effectiveness of our proposed approach against current solvers.

NeurIPS Conference 2019 Conference Paper

Counting the Optimal Solutions in Graphical Models

• Radu Marinescu
• Rina Dechter

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.

AAAI Conference 2019 Conference Paper

Interleave Variational Optimization with Monte Carlo Sampling: A Tale of Two Approximate Inference Paradigms

• Qi Lou
• Rina Dechter
• Alexander Ihler

Computing the partition function of a graphical model is a fundamental task in probabilistic inference. Variational bounds and Monte Carlo methods, two important approximate paradigms for this task, each has its respective strengths for solving different types of problems, but it is often nontrivial to decide which one to apply to a particular problem instance without significant prior knowledge and a high level of expertise. In this paper, we propose a general framework that interleaves optimization of variational bounds (via message passing) with Monte Carlo sampling. Our adaptive interleaving policy can automatically balance the computational effort between these two schemes in an instance-dependent way, which provides our framework with the strengths of both schemes, leads to tighter anytime bounds and an unbiased estimate of the partition function, and allows flexible tradeoffs between memory, time, and solution quality. We verify our approach empirically on real-world problems taken from recent UAI inference competitions.

UAI Conference 2018 Conference Paper

Abstraction Sampling in Graphical Models

• Filjor Broka
• Rina Dechter
• Alexander Ihler
• Kalev Kask

We present a new sampling scheme for approximating hard to compute queries over graphical models, such as computing the partition function. The scheme builds upon exact algorithms that traverse a weighted directed state-space graph representing a global function over a graphical model (e. g. , probability distribution). With the aid of an abstraction function and randomization, the state space can be compacted (or trimmed) to facilitate tractable computation, yielding a Monte Carlo Estimate that is unbiased. We present the general scheme and analyze its properties analytically and empirically, investigating two specific ideas for picking abstractions - targeting reduction of variance or search space size.

JAIR Journal 2018 Journal Article

AND/OR Search for Marginal MAP

• Radu Marinescu
• Junkyu Lee
• Rina Dechter
• Alexander Ihler

Mixed inference such as the marginal MAP query (some variables marginalized by summation and others by maximization) is key to many prediction and decision models. It is known to be extremely hard; the problem is NP PP -complete while the decision problem for MAP is only NP-complete and the summation problem is #P-complete. Consequently, approximation anytime schemes are essential. In this paper, we show that the framework of heuristic AND/OR search, which exploits conditional independence in the graphical model, coupled with variational-based mini-bucket heuristics can be extended to this task and yield powerful state-of-the-art schemes. Specifically, we explore the complementary properties of best-first search for reducing the number of conditional sums and providing time-improving upper bounds, with depth-first search for rapidly generating and improving solutions and lower bounds. We show empirically that a class of solvers that interleaves depth-first with best-first schemes emerges as the most competitive anytime scheme.

AAAI Conference 2018 Conference Paper

Anytime Anyspace AND/OR Best-First Search for Bounding Marginal MAP

• Qi Lou
• Rina Dechter
• Alexander Ihler

Marginal MAP is a key task in Bayesian inference and decision-making. It is known to be very difficult in general, particularly because the evaluation of each MAP assignment requires solving an internal summation problem. In this paper, we propose a best-first search algorithm that provides anytime upper bounds for marginal MAP in graphical models. It folds the computation of external maximization and internal summation into an AND/OR tree search framework, and solves them simultaneously using a unified best-first search algorithm. The algorithm avoids some unnecessary computation of summation sub-problems associated with MAP assignments, and thus yields significant time savings. Furthermore, our algorithm is able to operate within limited memory. Empirical evaluation on three challenging benchmarks demonstrates that our unified best-first search algorithm using pre-compiled variational heuristics often provides tighter anytime upper bounds compared to those state-of-the-art baselines.

UAI Conference 2018 Conference Paper

Finite-sample Bounds for Marginal MAP

• Qi Lou
• Rina Dechter
• Alexander Ihler

Marginal MAP is a key task in Bayesian inference and decision-making, and known to be very challenging in general. In this paper, we present an algorithm that blends heuristic search and importance sampling to provide anytime finite-sample bounds for marginal MAP along with predicted MAP solutions. We convert bounding marginal MAP to a surrogate task of bounding a series of summation problems of an augmented graphical model, and then adapt dynamic importance sampling [Lou et al. , 2017b], a recent advance in bounding the partition function, to provide finite-sample bounds for the surrogate task. Those bounds are guaranteed to be tight given enough time, and the values of the predicted MAP solutions will converge to the optimum. Our algorithm runs in an anytime/anyspace manner, which gives flexible trade-offs between memory, time, and solution quality. We demonstrate the effectiveness of our approach empirically on multiple challenging benchmarks in comparison with some state-of-the-art search algorithms.

UAI Conference 2018 Conference Paper

Join Graph Decomposition Bounds for Influence Diagrams

• Junkyu Lee 0001
• Alexander Ihler
• Rina Dechter

We introduce a new decomposition method for bounding the maximum expected utility of influence diagrams. While most current schemes use reductions to the Marginal Map task over a Bayesian Network, our approach is direct, aiming to avoid the large explosion in the model size that often results by such reductions. In this paper, we extend to influence diagrams the principles of decomposition methods that were applied earlier to probabilistic inference, utilizing an algebraic framework called valuation algebra which effectively captures both multiplicative and additive local structures present in influence diagrams. Empirical evaluation on four benchmarks demonstrates the effectiveness of our approach compared to reduction-based approaches and illustrates significant improvements in the upper bounds on maximum expected utility.

IJCAI Conference 2018 Conference Paper

Stochastic Anytime Search for Bounding Marginal MAP

• Radu Marinescu
• Rina Dechter
• Alexander Ihler

The Marginal MAP inference task is known to be extremely hard particularly because the evaluation of each complete MAP assignment involves an exact likelihood computation (a combinatorial sum). For this reason, most recent state-of-the-art solvers that focus on computing anytime upper and lower bounds on the optimal value are limited to solving instances with tractable conditioned summation subproblems. In this paper, we develop new search-based bounding schemes for Marginal MAP that produce anytime upper and lower bounds without performing exact likelihood computations. The empirical evaluation demonstrates the effectiveness of our new methods against the current best-performing search-based bounds.

JAIR Journal 2017 Journal Article

AND/OR Branch-and-Bound on a Computational Grid

• Lars Otten
• Rina Dechter

We present a parallel AND/OR Branch-and-Bound scheme that uses the power of a computational grid to push the boundaries of feasibility for combinatorial optimization. Two variants of the scheme are described, one of which aims to use machine learning techniques for parallel load balancing. In-depth analysis identifies two inherent sources of parallel search space redundancies that, together with general parallel execution overhead, can impede parallelization and render the problem far from embarrassingly parallel. We conduct extensive empirical evaluation on hundreds of CPUs, the first of its kind, with overall positive results. In a significant number of cases parallel speedup is close to the theoretical maximum and we are able to solve many very complex problem instances orders of magnitude faster than before; yet analysis of certain results also serves to demonstrate the inherent limitations of the approach due to the aforementioned redundancies.

AAAI Conference 2017 Conference Paper

Anytime Anyspace AND/OR Search for Bounding the Partition Function

• Qi Lou
• Rina Dechter
• Alexander Ihler

Bounding the partition function is a key inference task in many graphical models. In this paper, we develop an anytime anyspace search algorithm taking advantage of AND/OR tree structure and optimized variational heuristics to tighten deterministic bounds on the partition function. We study how our priority-driven best-first search scheme can improve on stateof-the-art variational bounds in an anytime way within limited memory resources, as well as the effect of the AND/OR framework to exploit conditional independence structure within the search process within the context of summation. We compare our resulting bounds to a number of existing methods, and show that our approach offers a number of advantages on realworld problem instances taken from recent UAI competitions.

AAAI Conference 2017 Conference Paper

Anytime Best+Depth-First Search for Bounding Marginal MAP

• Radu Marinescu
• Junkyu Lee
• Alexander Ihler
• Rina Dechter

We introduce new anytime search algorithms that combine best-first with depth-first search into hybrid schemes for Marginal MAP inference in graphical models. The main goal is to facilitate the generation of upper bounds (via the best- first part) alongside the lower bounds of solutions (via the depth-first part) in an anytime fashion. We compare against two of the best current state-of-the-art schemes and show that our best+depth search scheme produces higher quality solutions faster while also producing a bound on their accuracy, which can be used to measure solution quality during search. An extensive empirical evaluation demonstrates the effectiveness of our new methods which enjoy the strength of best-first (optimality of search) and of depth-first (memory robustness), leading to solutions for difficult instances where previous solvers were unable to find even a single solution.

NeurIPS Conference 2017 Conference Paper

Dynamic Importance Sampling for Anytime Bounds of the Partition Function

• Qi Lou
• Rina Dechter
• Alexander Ihler

Computing the partition function is a key inference task in many graphical models. In this paper, we propose a dynamic importance sampling scheme that provides anytime finite-sample bounds for the partition function. Our algorithm balances the advantages of the three major inference strategies, heuristic search, variational bounds, and Monte Carlo methods, blending sampling with search to refine a variationally defined proposal. Our algorithm combines and generalizes recent work on anytime search and probabilistic bounds of the partition function. By using an intelligently chosen weighted average over the samples, we construct an unbiased estimator of the partition function with strong finite-sample confidence intervals that inherit both the rapid early improvement rate of sampling and the long-term benefits of an improved proposal from search. This gives significantly improved anytime behavior, and more flexible trade-offs between memory, time, and solution quality. We demonstrate the effectiveness of our approach empirically on real-world problem instances taken from recent UAI competitions.

JAIR Journal 2017 Journal Article

Residual-Guided Look-Ahead in AND/OR Search for Graphical Models

• William Lam
• Kalev Kask
• Javier Larrosa
• Rina Dechter

We introduce the concept of local bucket error for the mini-bucket heuristics and show how it can be used to improve the power of AND/OR search for combinatorial optimization tasks in graphical models (e.g. MAP/MPE or weighted CSPs). The local bucket error illuminates how the heuristic errors are distributed in the search space, guided by the mini-bucket heuristic. We present and analyze methods for compiling the local bucket-errors (exactly and approximately) and show that they can be used to yield an effective tool for balancing look-ahead overhead during search. This can be especially instrumental when memory is restricted, accommodating the generation of only weak compiled heuristics. We illustrate the impact of the proposed schemes in an extensive empirical evaluation for both finding exact solutions and anytime suboptimal solutions.

AAAI Conference 2016 Conference Paper

From Exact to Anytime Solutions for Marginal MAP

• Junkyu Lee
• Radu Marinescu
• Rina Dechter
• Alexander Ihler

This paper explores the anytime performance of search-based algorithms for solving the Marginal MAP task over graphical models. The current state-of-the-art for solving this challenging task is based on best-first search exploring the AND/OR graph with the guidance of heuristics based on mini-bucket and variational cost-shifting principles. Yet, those schemes are uncompromising in that they solve the problem exactly, or not at all, and often suffer from memory problems. In this work, we explore the well known principle of weighted search for converting best-first search solvers into anytime schemes. The weighted best-first search schemes report a solution early in the process by using inadmissible heuristics, and subsequently improve the solution. While it was demonstrated recently that weighted schemes can yield effective anytime behavior for pure MAP tasks, Marginal MAP is far more challenging (e. g. , a conditional sum must be evaluated for every solution). Yet, in an extensive empirical analysis we show that weighted schemes are indeed highly effective anytime solvers for Marginal MAP yielding the most competitive schemes to date for this task.

IJCAI Conference 2016 Conference Paper

Limited Discrepancy AND/OR Search and Its Application to Optimization Tasks in Graphical Models

• Javier Larrosa
• Emma Rollon
• Rina Dechter

Many combinatorial problems are solved with a Depth-First search (DFS) guided by a heuristic and it is well-known that this method is very fragile with respect to heuristic mistakes. One standard way to make DFS more robust is to search by increasing number of discrepancies. This approach has been found useful in several domains where the search structure is a height-bounded OR tree. In this paper we investigate the generalization of discrepancy-based search to AND/OR search trees and propose an extension of the Limited Discrepancy Search (LDS) algorithm. We demonstrate the relevance of our proposal in the context of Graphical Models. In these problems, which can be solved with either a standard OR search tree or an AND/OR tree, we show the superiority of our approach. For a fixed number of discrepancies, the search space visited by the AND/OR algorithm strictly contains the search space visited by standard LDS, and many more nodes can be visited due to the multiplicative effect of the AND/OR decomposition. Besides, if the AND/OR tree achieves a significant size reduction with respect to the standard OR tree, the cost of each iteration of the AND/OR algorithm is asymptotically lower than in standard LDS. We report experiments on the minsum problem on different domains and show that the AND/OR version of LDS usually obtains better solutions given the same CPU time.

AAAI Conference 2016 Conference Paper

Look-Ahead with Mini-Bucket Heuristics for MPE

• Rina Dechter
• Kalev Kask
• William Lam
• Javier Larrosa

The paper investigates the potential of look-ahead in the context of AND/OR search in graphical models using the Mini- Bucket heuristic for combinatorial optimization tasks (e. g. , MAP/MPE or weighted CSPs). We present and analyze the complexity of computing the residual (a. k. a. Bellman update) of the Mini-Bucket heuristic and show how this can be used to identify which parts of the search space are more likely to benefit from look-ahead and how to bound its overhead. We also rephrase the look-ahead computation as a graphical model, to facilitate structure exploiting inference schemes. We demonstrate empirically that augmenting Mini-Bucket heuristics by look-ahead is a cost-effective way of increasing the power of Branch-And-Bound search.

ECAI Conference 2016 Conference Paper

On the Impact of Subproblem Orderings on Anytime AND/OR Best-First Search for Lower Bounds

• William Lam
• Kalev Kask
• Rina Dechter
• Javier Larrosa

Best-first search can be regarded as anytime scheme for producing lower bounds on the optimal solution, a characteristic that is mostly overlooked. We explore this topic in the context of AND/OR best-first search, guided by the MBE heuristic, when solving graphical models. In that context, the impact of the secondary heuristic for subproblem ordering may be significant, especially in the anytime context. Indeed, our paper illustrates this, showing that the new concept of bucket errors can advise in providing effective subproblem orderings in AND/OR search.

IJCAI Conference 2016 Conference Paper

Probabilistic Inference Modulo Theories

• Rodrigo de Salvo Braz
• Ciaran O'Reilly
• Vibhav Gogate
• Rina Dechter

We present SGDPLL(T), an algorithm that solves (among many other problems) probabilistic inference modulo theories, that is, inference problems over probabilistic models defined via a logic theory provided as a parameter (currently, propositional, equalities on discrete sorts, and inequalities, more specifically difference arithmetic, on bounded integers). While many solutions to probabilistic inference over logic representations have been proposed, SGDPLL(T) is simultaneously (1) lifted, (2) exact and (3) modulo theories, that is, parameterized by a background logic theory. This offers a foundation for extending it to rich logic languages such as data structures and relational data. By lifted, we mean algorithms with constant complexity in the domain size (the number of values that variables can take). We also detail a solver for summations with difference arithmetic and show experimental results from a scenario in which SGDPLL(T) is much faster than a state-of-the-art probabilistic solver.

JAIR Journal 2016 Journal Article

Searching for the M Best Solutions in Graphical Models

• Natalia Flerova
• Radu Marinescu
• Rina Dechter

The paper focuses on finding the m best solutions to combinatorial optimization problems using best-first or depth-first branch and bound search. Specifically, we present a new algorithm m-A*, extending the well-known A* to the m-best task, and for the first time prove that all its desirable properties, including soundness, completeness and optimal efficiency, are maintained. Since best-first algorithms require extensive memory, we also extend the memory-efficient depth-first branch and bound to the m-best task. We adapt both algorithms to optimization tasks over graphical models (e.g., Weighted CSP and MPE in Bayesian networks), provide complexity analysis and an empirical evaluation. Our experiments confirm theory that the best-first approach is largely superior when memory is available, but depth-first branch and bound is more robust. We also show that our algorithms are competitive with related schemes recently developed for the m-best task.

SoCS Conference 2015 Conference Paper

Caching in Context-Minimal OR Spaces

• Rina Dechter
• Levi H. S. Lelis
• Lars Otten

In empirical studies we observed that caching can have very little impact in reducing the search effort in Branch and Bound search over context-minimal OR spaces. For example, in one of the problem domains used in our experiments we reduce only by 1% the number of nodes expanded when using caching in context-minimal OR spaces. By contrast, we reduce by 74% the number of nodes expanded when using caching in context-minimal AND/OR spaces on the same instances. In this work we document this unexpected empirical finding and provide explanations for the phenomenon.

SoCS Conference 2015 Conference Paper

Empowering Mini-Bucket in Anytime Heuristic Search with Look-Ahead: Preliminary Evaluation

• William Lam
• Kalev Kask
• Rina Dechter

The paper explores the potential of look-ahead methods within the context of AND/OR search in graphical models using the Mini-Bucket heuristic for combinatorial optimization tasks (e. g. , weighted CSPS or MAP inference). We study how these methods can be used to compensate for the approximation error of the initially generated Mini-Bucket heuristics, within the context of anytime Branch-And-Bound search.

IJCAI Conference 2015 Conference Paper

Pushing Forward Marginal MAP with Best-First Search

• Radu Marinescu
• Rina Dechter
• Alexander Ihler

Marginal MAP is known to be a difficult task for graphical models, particularly because the evaluation of each MAP assignment involves a conditional likelihood computation. In order to minimize the number of likelihood evaluations, we focus in this paper on best-first search strategies for exploring the space of partial MAP assignments. We analyze the potential relative benefits of several bestfirst search algorithms and demonstrate their effectiveness against recent branch and bound schemes through extensive empirical evaluations. Our results show that best-first search improves significantly over existing depth-first approaches, in many cases by several orders of magnitude, especially when guided by relatively weak heuristics.

UAI Conference 2014 Conference Paper

AND/OR Search for Marginal MAP

• Radu Marinescu 0002
• Rina Dechter
• Alexander Ihler

Marginal MAP problems are known to be very difficult tasks for graphical models and are so far solved exactly by systematic search guided by a join-tree upper bound. In this paper, we develop new AND/OR branch and bound algorithms for marginal MAP that use heuristics extracted from weighted mini-buckets enhanced with messagepassing updates. We demonstrate the effectiveness of the resulting search algorithms against previous join-tree based approaches, which we also extend to accommodate high induced width models, through extensive empirical evaluations. Our results show not only orders-of-magnitude improvements over the state-of-the-art, but also the ability to solve problem instances well beyond the reach of previous approaches.

SoCS Conference 2014 Conference Paper

Beyond Static Mini-Bucket: Towards Integrating with Iterative Cost-Shifting Based Dynamic Heuristics

• William Lam
• Kalev Kask
• Rina Dechter
• Alexander Ihler

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.

SoCS Conference 2014 Conference Paper

Evaluating Weighted DFS Branch and Bound over Graphical Models

• Natalia Flerova
• Radu Marinescu 0002
• Rina Dechter

Weighted search was explored significantly in recent years for path-finding problems, but until now was barely considered for optimization tasks such as MPE/MAP and Weighted CSPs. An important virtue of weighted search schemes, especially in the context of anytime search, is that they are w-optimal, i. e. when terminated, they return a weight w, and a solution cost C, such that C ≤ w · C*, where C* is the optimal cost. In this paper we introduce Weighted Branch and Bound (WBB) for graphical models and provide a broad empirical evaluation of its performance compared with one of the best unweighted anytime search scheme, BRAOBB (won Pascal 2011 competition). We also compare against weighted best-first (WBF). Our results show that W BB can be superior to both unweighted BB and to weighted BF on a significant number of instances. We also illustrate the benefit of weighted search in providing suboptimality relative error bounds.

SoCS Conference 2014 Conference Paper

STLS: Cycle-Cutset-Driven Local Search For MPE

• Alon Milchgrub
• Rina Dechter

In this paper we present Stochastic Tree-based Local Search or STLS, a local search algorithm combining the notion of cycle-cutsets with the well-known Belief Propagation to approximatethe optimum of sums of unary and binary potentials. This is done by the previously unexplored concept oftraversal from one cutset to another and updating the induced forest, thus creating a local search algorithm, whose updatephase spans over all the forest variables. We study empirically two pure variants of STLS against the state-of-the art GLS+ scheme and against a hybrid.

IJCAI Conference 2013 Conference Paper

Predicting the Size of Depth-First Branch and Bound Search Trees

• Levi H. S. Lelis
• Lars Otten
• Rina Dechter

This paper provides algorithms for predicting the size of the Expanded Search Tree (EST) of Depthfirst Branch and Bound algorithms (DFBnB) for optimization tasks. The prediction algorithm is implemented and evaluated in the context of solving combinatorial optimization problems over graphical models such as Bayesian and Markov networks. Our methods extend to DFBnB the approaches provided by Knuth-Chen schemes that were designed and applied for predicting the EST size of backtracking search algorithms. Our empirical results demonstrate good predictions which are superior to competing schemes.

IJCAI Conference 2013 Conference Paper

Semiring-Based Mini-Bucket Partitioning Schemes

• Emma Rollon
• Javier Larrosa
• Rina Dechter

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.

UAI Conference 2012 Conference Paper

A Case Study in Complexity Estimation: Towards Parallel Branch-and-Bound over Graphical Models

• Lars Otten
• Rina Dechter

We study the problem of complexity estimation in the context of parallelizing an advanced Branch and Bound-type algorithm over graphical models. The algorithm’s pruning power makes load balancing, one crucial element of every distributed system, very challenging. We propose using a statistical regression model to identify and tackle disproportionally complex parallel subproblems, the cause of load imbalance, ahead of time. The proposed model is evaluated and analyzed on various levels and shown to yield robust predictions. We then demonstrate its effectiveness for load balancing in practice.

ECAI Conference 2012 Conference Paper

Advances in Distributed Branch and Bound

• Lars Otten
• Rina Dechter

We describe a distributed version of an advanced branch and bound algorithm over graphical models. The crucial issue of load balancing is addressed by estimating subproblem complexity through learning, yielding impressive speedups on various hard problems using hundreds of parallel CPUs.

AIJ Journal 2012 Journal Article

Importance sampling-based estimation over AND/OR search spaces for graphical models

• Vibhav Gogate
• Rina Dechter

It is well known that the accuracy of importance sampling can be improved by reducing the variance of its sample mean and therefore variance reduction schemes have been the subject of much research. In this paper, we introduce a family of variance reduction schemes that generalize the sample mean from the conventional OR search space to the AND/OR search space for graphical models. The new AND/OR sample means allow trading time and space with variance. At one end is the AND/OR sample tree mean which has the same time and space complexity as the conventional OR sample tree mean but has smaller variance. At other end is the AND/OR sample graph mean which requires more time and space to compute but has the smallest variance. Theoretically, we show that the variance is smaller in the AND/OR space because the AND/OR sample mean is defined over a larger virtual sample size compared with the OR sample mean. Empirically, we demonstrate that the AND/OR sample mean is far closer to the true mean than the OR sample mean.

UAI Conference 2012 Conference Paper

Join-graph based cost-shifting schemes

• Alexander Ihler
• Natalia Flerova
• Rina Dechter
• Lars Otten

We develop several algorithms taking advantage of two common approaches for bounding MPE queries in graphical models: minibucket 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.

AAAI Conference 2012 Conference Paper

Search Algorithms for m Best Solutions for Graphical Models

• Rina Dechter
• Natalia Flerova
• Radu Marinescu

The paper focuses on finding the m best solutions to combinatorial optimization problems using Best-First or Branchand-Bound search. Specifically, we present m-A*, extending the well-known A* to the m-best task, and prove that all its desirable properties, including soundness, completeness and optimal efficiency, are maintained. Since Best-First algorithms have memory problems, we also extend the memoryefficient Depth-First Branch-and-Bound to the m-best task. We extend both algorithms to optimization tasks over graphical models (e. g. , Weighted CSP and MPE in Bayesian networks), provide complexity analysis and an empirical evaluation. Our experiments with 5 variants of Best-First and Branch-and-Bound confirm that Best-First is largely superior when memory is available, but Branch-and-Bound is more robust, while both styles of search benefit greatly when the heuristic evaluation function has increased accuracy.

SoCS Conference 2011 Conference Paper

Anytime AND/OR Depth-First Search for Combinatorial Optimization

• Lars Otten
• Rina Dechter

One popular and efficient scheme for solving exactly combinatorial optimization problems over graphical models is depth-first Branch and Bound. However, when the algorithm exploits problem decomposition using AND/OR search spaces, its anytime behavior breaks down. This paper 1) analyzes and demonstrates this inherent conflict between effective exploitation of problem decomposition (through AND/OR search spaces) and the anytime behavior of depth-first search (DFS), 2) presents a first scheme to address this issue while maintaining desirable DFS memory properties, 3) analyzes and demonstrates its effectiveness. Our work is applicable to any problem that can be cast as search over an AND/OR search space.

AAAI Conference 2011 Conference Paper

Pushing the Power of Stochastic Greedy Ordering Schemes for Inference in Graphical Models

• Kalev Kask
• Andrew Gelfand
• Lars Otten
• Rina Dechter

We study iterative randomized greedy algorithms for generating (elimination) orderings with small induced width and state space size - two parameters known to bound the complexity of inference in graphical models. We propose and implement the Iterative Greedy Variable Ordering (IGVO) algorithm, a new variant within this algorithm class. An empirical evaluation using different ranking functions and conditions of randomness, demonstrates that IGVO finds significantly better orderings than standard greedy ordering implementations when evaluated within an anytime framework. Additional order of magnitude improvements are demonstrated on a multicore system, thus further expanding the set of solvable graphical models. The experiments also confirm the superiority of the MinFill heuristic within the iterative scheme.

AIJ Journal 2011 Journal Article

SampleSearch: Importance sampling in presence of determinism

• Vibhav Gogate
• Rina Dechter

The paper focuses on developing effective importance sampling algorithms for mixed probabilistic and deterministic graphical models. The use of importance sampling in such graphical models is problematic because it generates many useless zero weight samples which are rejected yielding an inefficient sampling process. To address this rejection problem, we propose the SampleSearch scheme that augments sampling with systematic constraint-based backtracking search. We characterize the bias introduced by the combination of search with sampling, and derive a weighting scheme which yields an unbiased estimate of the desired statistics (e. g. , probability of evidence). When computing the weights exactly is too complex, we propose an approximation which has a weaker guarantee of asymptotic unbiasedness. We present results of an extensive empirical evaluation demonstrating that SampleSearch outperforms other schemes in presence of significant amount of determinism.

AAAI Conference 2011 Conference Paper

Stopping Rules for Randomized Greedy Triangulation Schemes

• Andrew Gelfand
• Kalev Kask
• Rina Dechter

Many algorithms for performing inference in graphical models have complexity that is exponential in the treewidth - a parameter of the underlying graph structure. Computing the (minimal) treewidth is NPcomplete, so stochastic algorithms are sometimes used to find low width tree decompositions. A common approach for finding good decompositions is iteratively executing a greedy triangulation algorithm (e. g. min- fill) with randomized tie-breaking. However, utilizing a stochastic algorithm as part of the inference task introduces a new problem - namely, deciding how long the stochastic algorithm should be allowed to execute before performing inference on the best tree decomposition found so far. We refer to this dilemma as the Stopping Problem and formalize it in terms of the total time needed to answer a probabilistic query. We propose a rule for discontinuing the search for improved decompositions and demonstrate the benefit (in terms of time saved) of applying this rule to Bayes and Markov network instances.

UAI Conference 2010 Conference Paper

BEEM: Bucket Elimination with External Memory

• Kalev Kask
• Rina Dechter
• Andrew Gelfand

A major limitation of exact inference algorithms for probabilistic graphical models is their extensive memory usage, which often puts real-world problems out of their reach. In this paper we show how we can extend inference algorithms, particularly Bucket Elimination, a special case of cluster (join) tree decomposition, to utilize disk memory. We provide the underlying ideas and show promising empirical results of exactly solving large problems not solvable before.

AAAI Conference 2010 Conference Paper

New Mini-Bucket Partitioning Heuristics for Bounding the Probability of Evidence

• Emma Rollon
• Rina Dechter

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-ofthe-art bounding schemes.

AIJ Journal 2009 Journal Article

AND/OR Branch-and-Bound search for combinatorial optimization in graphical models

• Radu Marinescu
• Rina Dechter

This is the first of two papers presenting and evaluating the power of a new framework for combinatorial optimization in graphical models, based on AND/OR search spaces. We introduce a new generation of depth-first Branch-and-Bound algorithms that explore the AND/OR search tree using static and dynamic variable orderings. The virtue of the AND/OR representation of the search space is that its size may be far smaller than that of a traditional OR representation, which can translate into significant time savings for search algorithms. The focus of this paper is on linear space search which explores the AND/OR search tree. In the second paper we explore memory intensive AND/OR search algorithms. In conjunction with the AND/OR search space we investigate the power of the mini-bucket heuristics in both static and dynamic setups. We focus on two most common optimization problems in graphical models: finding the Most Probable Explanation in Bayesian networks and solving Weighted CSPs. In extensive empirical evaluations we demonstrate that the new AND/OR Branch-and-Bound approach improves considerably over the traditional OR search strategy and show how various variable ordering schemes impact the performance of the AND/OR search scheme.

AIJ Journal 2009 Journal Article

Memory intensive AND/OR search for combinatorial optimization in graphical models

• Radu Marinescu
• Rina Dechter

In this paper we explore the impact of caching during search in the context of the recent framework of AND/OR search in graphical models. Specifically, we extend the depth-first AND/OR Branch-and-Bound tree search algorithm to explore an AND/OR search graph by equipping it with an adaptive caching scheme similar to good and no-good recording. Furthermore, we present best-first search algorithms for traversing the same underlying AND/OR search graph and compare both algorithms empirically. We focus on two common optimization problems in graphical models: finding the Most Probable Explanation (MPE) in belief networks and solving Weighted CSPs (WCSP). In an extensive empirical evaluation we demonstrate conclusively the superiority of the memory intensive AND/OR search algorithms on a variety of benchmarks.

UAI Conference 2008 Conference Paper

AND/OR Importance Sampling

• Vibhav Gogate
• Rina Dechter

The paper introduces AND/OR importance sampling for probabilistic graphical models. In contrast to importance sampling, AND/OR importance sampling caches samples in the AND/OR space and then extracts a new sample mean from the stored samples. We prove that AND/OR importance sampling may have lower variance than importance sampling; thereby providing a theoretical justification for preferring it over importance sampling. Our empirical evaluation demonstrates that AND/OR importance sampling is far more accurate than importance sampling in many cases.

UAI Conference 2008 Conference Paper

Bounding Search Space Size via (Hyper)tree Decompositions

• Lars Otten
• Rina Dechter

This paper develops a measure for bounding the performance of AND/OR search algorithms for solving a variety of queries over graphical models. We show how drawing a connection to the recent notion of hypertree decompositions allows to exploit determinism in the problem specification and produce tighter bounds. We demonstrate on a variety of practical problem instances that we are often able to improve upon existing bounds by several orders of magnitude.

ECAI Conference 2008 Conference Paper

On the Practical Significance of Hypertree vs. TreeWidth

• Rina Dechter
• Lars Otten
• Radu Marinescu 0002

The recently introduced notion of hypertree width has been shown to provide a broader characterization of tractable constraint and probabilistic networks than the tree width. This paper demonstrates empirically that in practice the bounding power of the tree width is still superior to the hypertree width for many benchmark instances of both probabilistic and deterministic networks.

IJCAI Conference 2007 Conference Paper

• Robert Mateescu
• Rina Dechter

We investigate three parameterized algorithmic schemes for graphical models that can accommodate trade-offs between time and space: 1) AND/OR Adaptive Caching (AOC(i)); 2) Variable Elimination and Conditioning (VEC(i)); and 3) Tree Decomposition with Conditioning (TDC(i)). We show that AOC(i) is better than the vanilla versions of both VEC(i) and TDC(i), and use the guiding principles of AOC(i)to improve the other two schemes. Finally, we show that the improved versions of VEC(i) and TDCI can be simulated by AOC(i), which emphasizes the unifying power of the AND/OR framework.

UAI Conference 2007 Conference Paper

AND/OR Multi-Valued Decision Diagrams (AOMDDs) for Weighted Graphical Models

• Robert Mateescu
• Rina Dechter

Compiling graphical models has recently been under intense investigation, especially for probabilistic modeling and processing. We present here a novel data structure for compiling weighted graphical models (in particular, probabilistic models), called AND/OR Multi-Valued Decision Diagram (AOMDD). This is a generalization of our previous work on constraint networks, to weighted models. The AOMDD is based on the frameworks of AND/OR search spaces for graphical models, and Ordered Binary Decision Diagrams (OBDD). The AOMDD is a canonical representation of a graphical model, and its size and compilation time are bounded exponentially by the treewidth of the graph, rather than pathwidth as is known for OBDDs. We discuss a Variable Elimination schedule for compilation, and present the general APPLY algorithm that combines two weighted AOMDDs, and also present a search based method for compilation method. The preliminary experimental evaluation is quite encouraging, showing the potential of the AOMDD data structure.

AIJ Journal 2007 Journal Article

AND/OR search spaces for graphical models

• Rina Dechter
• Robert Mateescu

The paper introduces an AND/OR search space perspective for graphical models that include probabilistic networks (directed or undirected) and constraint networks. In contrast to the traditional (OR) search space view, the AND/OR search tree displays some of the independencies present in the graphical model explicitly and may sometimes reduce the search space exponentially. Indeed, most algorithmic advances in search-based constraint processing and probabilistic inference can be viewed as searching an AND/OR search tree or graph. Familiar parameters such as the depth of a spanning tree, treewidth and pathwidth are shown to play a key role in characterizing the effect of AND/OR search graphs vs. the traditional OR search graphs. We compare memory intensive AND/OR graph search with inference methods, and place various existing algorithms within the AND/OR search space.

UAI Conference 2007 Conference Paper

Best-First AND/OR Search for Most Probable Explanations

• Radu Marinescu 0002
• Rina Dechter

The paper evaluates the power of best-first search over AND/OR search spaces for solving the Most Probable Explanation (MPE) task in Bayesian networks. The main virtue of the AND/OR representation of the search space is its sensitivity to the structure of the problem, which can translate into significant time savings. In recent years depth-first AND/OR Branch-and- Bound algorithms were shown to be very effective when exploring such search spaces, especially when using caching. Since best-first strategies are known to be superior to depth-first when memory is utilized, exploring the best-first control strategy is called for. The main contribution of this paper is in showing that a recent extension of AND/OR search algorithms from depth-first Branch-and-Bound to best-first is indeed very effective for computing the MPE in Bayesian networks. We demonstrate empirically the superiority of the best-first search approach on various probabilistic networks.

UAI Conference 2007 Conference Paper

Studies in Lower Bounding Probabilities of Evidence using the Markov Inequality

• Vibhav Gogate
• Bozhena Bidyuk
• Rina Dechter

UAI Conference 2006 Conference Paper

Cutset Sampling with Likelihood Weighting

• Bozhena Bidyuk
• Rina Dechter

The paper analyzes theoretically and empirically the performance of likelihood weighting (LW) on a subset of nodes in Bayesian networks. The proposed scheme requires fewer samples to converge due to reduction in sampling variance. The method exploits the structure of the network to bound the complexity of exact inference used to compute sampling distributions, similar to Gibbs cutset sampling. Yet, the extension of the previosly proposed cutset sampling principles to likelihood weighting is non-trivial due to differences in the sampling processes of Gibbs sampler and LW. We demonstrate empirically that likelihood weighting on a cutset (LWLC) is effective time-wise and has a lower rejection rate than LW when applied to networks with many deterministic probabilities. Finally, we show that the performance of likelihood weighting on a cutset can be improved further by caching computed sampling distributions and, consequently, learning 'zeros' of the target distribution.

ECAI Conference 2006 Conference Paper

Dynamic Orderings for AND/OR Branch-and-Bound Search in Graphical Models

• Radu Marinescu 0002
• Rina Dechter

AND/OR search spaces have recently been introduced as a unifying paradigm for advanced algorithmic schemes for graphical models. The main virtue of this representation is its sensitivity to the structure of the model, which can translate into exponential time savings for search algorithms. Since the variable selection can have a dramatic impact on search performance when solving optimization tasks, we introduce in this paper a new dynamic AND/OR Branch-and-Bound algorithmic framework which accommodates variable ordering heuristics. The efficiency of the dynamic AND/OR approach is demonstrated empirically in a variety of domains.

ECAI Conference 2006 Conference Paper

Improving Bound Propagation

• Bozhena Bidyuk
• Rina Dechter

This paper extends previously proposed bound propagation algorithm [11] for computing lower and upper bounds on posterior marginals in Bayesian networks. We improve the bound propagation scheme by taking advantage of the directionality in Bayesian networks and applying the notion of relevant subnetwork. We also propose an approximation scheme for the linear optimization subproblems. We demonstrate empirically that while the resulting bounds loose some precision, we achieve 10-100 times speedup compared to original bound propagation using a simplex solver.

UAI Conference 2005 Conference Paper

Approximate Inference Algorithms for Hybrid Bayesian Networks with Discrete Constraints

• Vibhav Gogate
• Rina Dechter

In this paper, we consider Hybrid Mixed Networks (HMN) which are Hybrid Bayesian Networks that allow discrete deterministic information to be modeled explicitly in the form of constraints. We present two approximate inference algorithms for HMNs that integrate and adjust well known algorithmic principles such as Generalized Belief Propagation, Rao-Blackwellised Importance Sampling and Constraint Propagation to address the complexity of modeling and reasoning in HMNs. We demonstrate the performance of our approximate inference algorithms on randomly generated HMNs.

UAI Conference 2005 Conference Paper

Modeling Transportation Routines using Hybrid Dynamic Mixed Networks

• Vibhav Gogate
• Rina Dechter
• Bozhena Bidyuk
• Craig Rindt
• James Marca

This paper describes a general framework called Hybrid Dynamic Mixed Networks (HDMNs) which are Hybrid Dynamic Bayesian Networks that allow representation of discrete deterministic information in the form of constraints. We propose approximate inference algorithms that integrate and adjust well known algorithmic principles such as Generalized Belief Propagation, Rao-Blackwellised Particle Filtering and Constraint Propagation to address the complexity of modeling and reasoning in HDMNs. We use this framework to model a person's travel activity over time and to predict destination and routes given the current location. We present a preliminary empirical evaluation demonstrating the effectiveness of our modeling framework and algorithms using several variants of the activity model.

UAI Conference 2005 Conference Paper

The Relationship Between AND/OR Search and Variable Elimination

• Robert Mateescu
• Rina Dechter

In this paper we compare search and inference in graphical models through the new framework of AND/OR search. Specifically, we compare Variable Elimination (VE) and memoryintensive AND/OR Search (AO) and place algorithms such as graph-based backjumping and no-good and good learning, as well as Recursive Conditioning [7] and Value Elimination [2] within the AND/OR search framework.

AIJ Journal 2005 Journal Article

Unifying tree decompositions for reasoning in graphical models

• Kalev Kask
• Rina Dechter
• Javier Larrosa
• Avi Dechter

The paper provides a unifying perspective of tree-decomposition algorithms appearing in various automated reasoning areas such as join-tree clustering for constraint-satisfaction and the clique-tree algorithm for probabilistic reasoning. Within this framework, we introduce a new algorithm, called bucket-tree elimination (BTE), that extends Bucket Elimination (BE) to trees, and show that it can provide a speed-up of n over BE for various reasoning tasks. Time-space tradeoffs of tree-decomposition processing are analyzed.

UAI Conference 2004 Conference Paper

A Complete Anytime Algorithm for Treewidth

• Vibhav Gogate
• Rina Dechter

In this paper, we present a Branch and Bound algorithm called QuickBB for computing the treewidth of an undirected graph. This algorithm performs a search in the space of perfect elimination ordering of vertices of the graph. The algorithm uses novel pruning and propagation techniques which are derived from the theory of graph minors and graph isomorphism. We present a new algorithm called minor-min-width for computing a lower bound on treewidth that is used within the branch and bound algorithm and which improves over earlier available lower bounds. Empirical evaluation of QuickBB on randomly generated graphs and benchmarks in Graph Coloring and Bayesian Networks shows that it is consistently better than complete algorithms like QuickTree [Shoikhet and Geiger, 1997] in terms of cpu time. QuickBB also has good anytime performance, being able to generate a better upper bound on treewidth of some graphs whose optimal treewidth could not be computed up to now.

UAI Conference 2004 Conference Paper

Mixtures of Deterministic-Probabilistic Networks and their AND/OR Search Space

• Rina Dechter
• Robert Mateescu

The paper introduces mixed networks, a new framework for expressing and reasoning with probabilistic and deterministic information. The framework combines belief networks with constraint networks, defining the semantics and graphical representation. We also introduce the AND/OR search space for graphical models, and develop a new linear space search algorithm. This provides the basis for understanding the benefits of processing the constraint information separately, resulting in the pruning of the search space. When the constraint part is tractable or has a small number of solutions, using the mixed representation can be exponentially more effective than using pure belief networks which odel constraints as conditional probability tables.

UAI Conference 2004 Conference Paper

On Finding Minimal w-cutset

• Bozhena Bidyuk
• Rina Dechter

The complexity of a reasoning task over a graphical model is tied to the induced width of the underlying graph. It is well-known that the conditioning (assigning values) on a subset of variables yields a subproblem of the reduced complexity where instantiated variables are removed. If the assigned variables constitute a cycle-cutset, the rest of the network is singly-connected and therefore can be solved by linear propagation algorithms. A w-cutset is a generalization of a cycle-cutset defined as a subset of nodes such that the subgraph with cutset nodes removed has induced-width of w or less. In this paper we address the problem of finding a minimal w-cutset in a graph. We relate the problem to that of finding the minimal w-cutset of a treedecomposition. The latter can be mapped to the well-known set multi-cover problem. This relationship yields a proof of NP-completeness on one hand and a greedy algorithm for finding a w-cutset of a tree decomposition on the other. Empirical evaluation of the algorithms is presented.

UAI Conference 2003 Conference Paper

A Simple Insight into Iterative Belief Propagation's Success

• Rina Dechter
• Robert Mateescu

In Non - ergodic belief networks the posterior belief OF many queries given evidence may become zero.The paper shows that WHEN belief propagation IS applied iteratively OVER arbitrary networks(the so called, iterative OR loopy belief propagation(IBP)) it IS identical TO an arc - consistency algorithm relative TO zero - belief queries(namely assessing zero posterior probabilities ).This implies that zero - belief conclusions derived BY belief propagation converge AND are sound.More importantly it suggests that the inference power OF IBP IS AS strong AND AS weak, AS that OF arc - consistency.This allows the synthesis OF belief networks FOR which belief propagation IS useless ON one hand, AND focuses the investigation OF classes OF belief network FOR which belief propagation may be zero - complete.Finally, ALL the above conclusions apply also TO Generalized belief propagation algorithms that extend loopy belief propagation AND allow a crisper understanding OF their power

UAI Conference 2003 Conference Paper

An Empirical Study of w-Cutset Sampling for Bayesian Networks

• Bozhena Bidyuk
• Rina Dechter

The paper studies empirically the time-space trade-off between sampling and inference in a sl cutset sampling algorithm. The algorithm samples over a subset of nodes in a Bayesian network and applies exact inference over the rest. Consequently, while the size of the sampling space decreases, requiring less samples for convergence, the time for generating each single sample increases. The w-cutset sampling selects a sampling set such that the induced-width of the network when the sampling set is observed is bounded by w, thus requiring inference whose complexity is exponential in w. In this paper, we investigate performance of w-cutset sampling over a range of w values and measure the accuracy of w-cutset sampling as a function of w. Our experiments demonstrate that the cutset sampling idea is quite powerful showing that an optimal balance between inference and sampling benefits substantially from restricting the cutset size, even at the cost of more complex inference.

UAI Conference 2003 Conference Paper

Systematic vs. Non-systematic Algorithms for Solving the MPE Task

• Radu Marinescu 0002
• Kalev Kask
• Rina Dechter

The paper continues the study of partitioning based inference of heuristics for search in the context of solving the Most Probable Explanation task in Bayesian Networks. We compare two systematic Branch and Bound search algorithms, BBBT (for which the heuristic information is constructed during search and allows dynamic variable/value ordering) and its predecessor BBMB (for which the heuristic information is pre-compiled), against a number of popular local search algorithms for the MPE problem. We show empirically that, when viewed as approximation schemes, BBBT/BBMB are superior to all of these best known SLS algorithms, especially when the domain sizes increase beyond 2. This is in contrast with the performance of SLS vs. systematic search on CSP/SAT problems, where SLS often significantly outperforms systematic algorithms. As far as we know, BBBT/BBMB are currently the best performing algorithms for solving the MPE task

AIJ Journal 2002 Journal Article

Backjump-based backtracking for constraint satisfaction problems

• Rina Dechter
• Daniel Frost

The performance of backtracking algorithms for solving finite-domain constraint satisfaction problems can be improved substantially by look-back and look-ahead methods. Look-back techniques extract information by analyzing failing search paths that are terminated by dead-ends. Look-ahead techniques use constraint propagation algorithms to avoid such dead-ends altogether. This paper describes a number of look-back variants including backjumping and constraint recording which recognize and avoid some unnecessary explorations of the search space. The last portion of the paper gives an overview of look-ahead methods such as forward checking and dynamic variable ordering, and discusses their combination with backjumping.

UAI Conference 2002 Conference Paper

Iterative Join-Graph Propagation

• Rina Dechter
• Kalev Kask
• Robert Mateescu

The paper presents an iterative version of join-tree clustering that applies the message passing of join-tree clustering algorithm to join-graphs rather than to join-trees, iteratively. It is inspired by the success of Pearl's belief propagation algorithm as an iterative approximation scheme on one hand, and by a recently introduced mini-clustering i. success as an anytime approximation method, on the other. The proposed Iterative Join-graph Propagation IJGP belongs to the class of generalized belief propagation methods, recently proposed using analogy with algorithms in statistical physics. Empirical evaluation of this approach on a number of problem classes demonstrates that even the most time-efficient variant is almost always superior to IBP and MC i, and is sometimes more accurate by as much as several orders of magnitude.

AIJ Journal 2001 Journal Article

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-1-0617.

• Kalev Kask
• Rina Dechter

The 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.

AIJ Journal 2001 Journal Article

Heuristic search in artificial intelligence

• Weixiong Zhang
• Rina Dechter
• Richard E. Korf

UAI Conference 2001 Conference Paper

Hybrid Processing of Beliefs and Constraints

• Rina Dechter
• David Larkin 0001

This paper explores algorithms for processing probabilistic and deterministic information when the former is represented as a belief network and the latter as a set of boolean clauses. The motivating tasks are 1. evaluating beliefs networks having a large number of deterministic relationships and2. evaluating probabilities of complex boolean querie over a belief network. We propose a parameterized family of variable elimination algorithms that exploit both types of information, and that allows varying levels of constraint propagation inferences. The complexity of the scheme is controlled by the induced-width of the graph {em augmented} by the dependencies introduced by the boolean constraints. Preliminary empirical evaluation demonstrate the effect of constraint propagation on probabilistic computation.

AIJ Journal 2001 Journal Article

Topological parameters for time-space tradeoff

• Rina Dechter
• Yousri El Fattah

In this paper we propose a family of algorithms combining tree-clustering with conditioning that trade space for time. Such algorithms are useful for reasoning in probabilistic and deterministic networks as well as for accomplishing optimization tasks. By analyzing the problem structure, the user can select from a spectrum of algorithms, the one that best meets a given time-space specification. To determine the potential of this approach we analyze the structural properties of problems coming from the circuit diagnosis domain. The analysis demonstrates how the tradeoffs associated with various hybrids can be used for each problem instance.

ICAPS Conference 2000 Conference Paper

A New Perspective on Algorithms for Optimizing Policies under Uncertainty

• Rina Dechter

Thepapertakesa freshlook at algorithms for maximizing expected utility overa setofpolicies, thatis, a set of possible ways of reacting to observations abom an tmcertain statc of the world. Using the bucketelimination framework, we characterize the complcxity of this optimization task by gral)h-hased parameters, and devise an improvedvariant of existing algorithms. The improvementis shownto yield a dramatic gain in complexitywhenthe probabilistic subgraph (of the influence diagram)is sparse, regardless of the complexity introduced by its utility subgraph.

IJCAI Conference 1999 Conference Paper

Branch and Bound with Mini-Bucket Heuristics

• Kalev Kask
• Rina Dechter

The paper describes a branch and bound scheme that uses heuristics generated mechanically by the mini-bucket approximation. This scheme is presented and evaluated for optimization tasks such as finding the Most Probable Explanation (MPE ) in Bayesian networks. The mini-bucket scheme yields monotonic heuristics of varying strengths which cause different amounts of pruning, allowing a controlled tradeoff between preprocessing and search. The resulting Branch and Bound with Mini-Bucket heuristic (BBMB), is evaluated using random networks, probabilistic decoding and medical diagnosis networks. Results show that the B B M B scheme overcomes the memory explosion of bucket-elimination allowing a gradual tradeoff of space for time, and of time for accuracy.

AIJ Journal 1999 Journal Article

Bucket elimination: A unifying framework for reasoning

• Rina Dechter

Bucket elimination is an algorithmic framework that generalizes dynamic programming to accommodate many problem-solving and reasoning tasks. Algorithms such as directional-resolution for propositional satisfiability, adaptive-consistency for constraint satisfaction, Fourier and Gaussian elimination for solving linear equalities and inequalities, and dynamic programming for combinatorial optimization, can all be accommodated within the bucket elimination framework. Many probabilistic inference tasks can likewise be expressed as bucket-elimination algorithms. These include: belief updating, finding the most probable explanation, and expected utility maximization. These algorithms share the same performance guarantees; all are time and space exponential in the induced-width of the problem's interaction graph. While elimination strategies have extensive demands on memory, a contrasting class of algorithms called “conditioning search” require only linear space. Algorithms in this class split a problem into subproblems by instantiating a subset of variables, called a conditioning set, or a cutset. Typical examples of conditioning search algorithms are: backtracking (in constraint satisfaction), and branch and bound (for combinatorial optimization). The paper presents the bucket-elimination framework as a unifying theme across probabilistic and deterministic reasoning tasks and show how conditioning search can be augmented to systematically trade space for time.

UAI Conference 1999 Conference Paper

Mini-Bucket Heuristics for Improved Search

• Kalev Kask
• Rina Dechter

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.

UAI Conference 1998 Conference Paper

Empirical Evaluation of Approximation Algorithms for Probabilistic Decoding

• Irina Rish
• Kalev Kask
• Rina Dechter

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.

UAI Conference 1997 Conference Paper

A Scheme for Approximating Probabilistic Inference

• Rina Dechter
• Irina Rish

This paper describes a class of probabilistic approximation algorithms based on bucket elimination which offer adjustable levels of accuracy and efficiency. We analyze the approximation for several tasks: finding the most probable explanation, belief updating and finding the maximum a posteriori hypothesis. We identify regions of completeness and provide preliminary empirical evaluation on randomly generated networks.

TCS Journal 1997 Journal Article

Local and global relational consistency

• Rina Dechter
• Peter van Beek

Local consistency has proven to be an important concept in the theory and practice of constraint networks. In this paper, we present a new definition of local consistency, called relational consistency. The new definition is relation-based, in contrast with the previous definition of local consistency, which we characterize as variable-based. We show the conceptual power of the new definition by showing how it unifies known elimination operators such as resolution in theorem proving, joins in relational databases, and variable elimination for solving linear inequalities. Algorithms for enforcing various levels of relational consistency are introduced and analyzed. We also show the usefulness of the new definition in characterizing relationships between properties of constraint networks and the level of local consistency needed to ensure global consistency.

IJCAI Conference 1997 Conference Paper

Mini-Buckets: A General Scheme for Generating Approximations in Automated Reasoning

• Rina Dechter

AIJ Journal 1997 Journal Article

Processing disjunctions in temporal constraint networks

• Eddie Schwalb
• Rina Dechter

Temporal constraint satisfaction problems (TCSPs) provide a formal framework for representing and processing temporal knowledge. Deciding the consistency of TCSPs is known to be intractable. We demonstrate that even local consistency algorithms like path-consistency (PC) can be exponential on TCSPs due to the fragmentation problem. We present two new polynomial approximation algorithms, Upper-Lower Tightening (ULT) and Loose Path-Consistency (LPC), which are efficient yet effective in detecting inconsistencies and reducing fragmentation. Our experiments on hard problems in the transition region show that LPC has the best effectiveness-efficiency tradeoff for processing TCSPs. When incorporated within backtrack search, LPC is capable of improving search performance by orders of magnitude.

UAI Conference 1996 Conference Paper

An evaluation of structural parameters for probabilistic reasoning: Results on benchmark circuits

• Yousri El Fattah
• Rina Dechter

Many algorithms for processing probabilistic networks are dependent on the topological properties of the problem's structure. Such algorithms (e.g., clustering, conditioning) are effective only if the problem has a sparse graph captured by parameters such as tree width and cycle-cut set size. In this paper we initiate a study to determine the potential of structure-based algorithms in real-life applications. We analyze empirically the structural properties of problems coming from the circuit diagnosis domain. Specifically, we locate those properties that capture the effectiveness of clustering and conditioning as well as of a family of conditioning+clustering algorithms designed to gradually trade space for time. We perform our analysis on 11 benchmark circuits widely used in the testing community. We also report on the effect of ordering heuristics on tree-clustering and show that, on our benchmarks, the well-known max-cardinality ordering is substantially inferior to an ordering called min-degree.

UAI Conference 1996 Conference Paper

Bucket elimination: A unifying framework for probabilistic inference

• Rina Dechter

Probabilistic inference algorithms for finding the most probable explanation, the maximum aposteriori hypothesis, and the maximum expected utility and for updating belief are reformulated as an elimination--type algorithm called bucket elimination. This emphasizes the principle common to many of the algorithms appearing in that literature and clarifies their relationship to nonserial dynamic programming algorithms. We also present a general way of combining conditioning and elimination within this framework. Bounds on complexity are given for all the algorithms as a function of the problem's structure.

AIJ Journal 1996 Journal Article

Default reasoning using classical logic

• Rachel Ben-Eliyahu
• Rina Dechter

In this paper we show how propositional default theories can be characterized by classical propositional theories: for each finite default theory, we show a classical propositional theory such that there is a one-to-one correspondence between models for the latter and extensions of the former. This means that computing extensions and answering queries about coherence, set-membership and set-entailment are reducible to propositional satisfiability. The general transformation is exponential but tractable for a subset which we call 2-DT—a superset of network default theories and disjunction-free default theories. Consequently, coherence and set-membership for the class 2-DT is NP-complete and set-entailment is co-NP-complete. This work paves the way for the application of decades of research on efficient algorithms for the satisfiability problem to default reasoning. For example, since prepositional satisfiability can be regarded as a constraint satisfaction problem (CSP), this work enables us to use CSP techniques for default reasoning. To illustrate this point we use the taxonomy of tractable CSPs to identify new tractable subsets for Reiter's default logic. Our procedures allow also for computing stable models of extended logic programs.

UAI Conference 1996 Conference Paper

Identifying Independencies in Causal Graphs with Feedback

• Judea Pearl
• Rina Dechter

We show that the d -separation criterion constitutes a valid test for conditional independence relationships that are induced by feedback systems involving discrete variables.

TIME Conference 1996 Conference Paper

Processing Disjunctions of Temporal Constraints

• Eddie Schwalb
• Rina Dechter

Describes new algorithms for processing quantitative temporal constraint satisfaction problems (TCSPs). In contrast to discrete CSPs, enforcing path consistency on TCSPs is exponential due to the fragmentation problem. We present an efficient polynomial constraint propagation algorithm, called "loose-path consistency" (LPC), which is shown to improve the performance of backtrack search algorithms by orders of magnitude. The tradeoffs between the effectiveness and efficiency of LPC are analyzed. We report the presence of a phase transition on this domain and perform an empirical evaluation on problems which lie in the transition region.

AIJ Journal 1996 Journal Article

Structure-driven algorithms for truth maintenance

• Rina Dechter
• Avi Dechter

This paper studies truth maintenance and belief revision tasks on singly-connected structures for the purpose of understanding how structural features could be exploited in such tasks. We present distributed algorithms and show that, in the JTMS framework, both belief revision and consistency maintenance are linear in the size of the knowledge-base on singly-connected structures. However, the ATMS task is exponential in the branching degree of the network. The singly-connected model, while restrictive, is useful for three reasons. First, efficient algorithms on singly-connected models can be utilized in more general structures by employing well-known clustering techniques. Second, these algorithms can serve as approximations or as heuristics in algorithms that perform truth maintenance on general problems. Finally, the analysis provides insights for understanding the sources of the computational difficulties associated with JTMS and ATMS.

UAI Conference 1996 Conference Paper

Topological parameters for time-space tradeoff

• Rina Dechter

In this paper we propose a family of algorithms combining tree-clustering with conditioning that trade space for time. Such algorithms are useful for reasoning in probabilistic and deterministic networks as well as for accomplishing optimization tasks. By analyzing the problem structure it will be possible to select from a spectrum the algorithm that best meets a given time-space specification.

AIJ Journal 1996 Journal Article

Uncovering trees in constraint networks

• Itay Meiri
• Rina Dechter
• Judea Pearl

This paper examines the possibility of removing redundant information from a given knowledge base and restructuring it in the form of a tree to enable efficient problem-solving routines. We offer a novel approach that guarantees removal of all redandancies that hide a tree structure. We develop a polynomial-time algorithm that, given an arbitrary binary constraint network, either extracts (by edge removal) a precise tree representation from the path-consistent version of the network or acknowledges that no such tree can be extracted. In the latter case, a tree is generated that may serve as an approximation to the original network.

IJCAI Conference 1995 Conference Paper

GSAT and Local Consistency

• Kalev Kask
• Rina Dechter

It has been shown that hill-climbing constraint satisfaction methods like min-conflicts [Minton et a/. , 1990] and GSAT [Selman et a/. , 1992] can outperform complete systematic search methods like backtracking and backjumping on many large classes of problems. In this paper we investigate how preprocessing improves GSAT. In particular, we will focus on the effect of enforcing local consistency on the performance of GSAT. We will show that enforcing local consistency on uniform random problems has very little effect on the performance of GSAT. However, when the problem has hierarchical structure, local consistency can significantly improve GSAT. It has been shown [Konolige, 1994] that there are certain structured problems that are very hard for GSAT while being very easy for the Davis-Putnam procedure. We will show that they become very easy for GSAT once a certain level of local consistency is enforced.

IJCAI Conference 1995 Conference Paper

Look-ahead value ordering for constraint satisfaction problems

• Daniel Frost
• Rina Dechter

Looking ahead during search is often useful when solving constraint satisfaction problems. Previous studies have shown that looking ahead helps by causing dead-ends to occur earlier in the search, and by providing information that is useful for dynamic variable ordering. In this paper, we show that another benefit of looking ahead is a useful domain value ordering heuristic, which we call look-ahead value ordering or LVO. LVO counts the number of times each value of the current variable conflicts with some value of a future variable, and the value with the lowest number of conflicts is chosen first. Our experiments show that look-ahead value ordering can be of substantial benefit, especially on hard constraint satisfaction problems.

AIJ Journal 1994 Journal Article

Experimental evaluation of preprocessing algorithms for constraint satisfaction problems

• Rina Dechter
• Itay Meiri

This paper presents an experimental evaluation of two orthogonal schemes for pre-processing constraint satisfaction problems (CSPs). The first of these schemes involves a class of local consistency techniques that includes directional arc consistency, directional path consistency, and adaptive consistency. The other scheme concerns the prearrangement of variables in a linear order to facilitate an efficient search. In the first series of experiments, we evaluated the effect of each of the local consistency techniques on backtracking and backjumping. Surprisingly, although adaptive consistency has the best worst-case complexity bounds, we have found that it exhibits the worst performance, unless the constraint graph was very sparse. Directional arc consistency (followed by either backjumping or backtracking) and backjumping (without any preprocessing) outperformed all other techniques: moreover, the former dominated the latter in computationally intensive situations. The second series of experiments suggests that maximum cardinality and minimum width are the best preordering (i. e. , static ordering) strategies, while dynamic search rearrangement is superior to all the preorderings studied.

AIJ Journal 1992 Journal Article

From local to global consistency

• Rina Dechter

In reasoning tasks involving the maintenance of consistent databases (so-called QQconstraint networks/Q/Q), it is customary to enforce local consistency conditions in order to simplify the subsequent construction of a globally coherent model of the data. In this paper we present a relationship between the sizes of the variables' domains, the constraints' arity and the level of local consistency sufficient to ensure global consistency. Based on these parameters a new tractability classification of constraint networks is presented. We also show, based on this relationship, that any relation on bi-valued variables which is not representable by a network of binary constraints cannot be represented by networks with any number of hidden variables.

AIJ Journal 1992 Journal Article

Structure identification in relational data

• Rina Dechter
• Judea Pearl

This paper presents several investigations into the prospects for identifying meaningful structures in empirical data, namely, structures permitting effective organization of the data to meet requirements of future queries. We propose a general framework whereby the notion of identifiability is given a precise formal definition similar to that of learnability. Using this framework, we then explore if a tractable procedure exists for deciding whether a given relation is decomposable into a constraint network or a CNF theory with desirable topology and, if the answer is positive, identifying the desired decomposition. Finally, we address the problem of expressing a given relation as a Horn theory and, if this is impossible, finding the best k-Horn approximation to the given relation. We show that both problems can be solved in time polynomial in the length of the data.

IJCAI Conference 1991 Conference Paper

Directed Constraint Networks: A Relational Framework for Causal Modeling

• Rina Dechter
• Judea Pearl

IJCAI Conference 1991 Conference Paper

On the Feasibility of Distributed Constraint Satisfaction

• Zeev Collin
• Rina Dechter
• Shmuel

This paper characterizes connectionist-type ar­ chitectures that allow a distributed solution for classes of constraint-satisfaction problems. The main issue addressed is whether there ex­ ists a u n i f o r m model of computation (where all nodes are indistinguishable) that guarantees convergence to a solution from every initial state of the system, whenever such a solution exists. We show that even for relatively simple constraint networks, such as rings, there is no general solution using a completely uni­ form, asynchronous, model. However, some restricted topologies like trees can accommo­ date the uniform, asynchronous, model and a protocol demonstrating this fact is presented. An almost*uniform, asynchronous, networkconsistency protocol is also presented. We show that the algorithms are guaranteed to be selfstabilizing, which makes them suitable for dy­ namic or error-prone environments.

AIJ Journal 1991 Journal Article

Temporal constraint networks

• Rina Dechter
• Itay Meiri
• Judea Pearl

This paper extends network-based methods of constraint satisfaction to include continuous variables, thus providing a framework for processing temporal constraints. In this framework, called temporal constraint satisfaction problem (TCSP), variables represent time points and temporal information is represented by a set of unary and binary constraints, each specifying a set of permitted intervals. The unique feature of this framework lies in permitting the processing of metric information, namely, assessments of time differences between events. We present algorithms for performing the following reasoning tasks: finding all feasible times that a given event can occur, finding all possible relationships between two given events, and generating one or more scenarios consistent with the information provided. We distinguish between simple temporal problems (STPs) and general temporal problems, the former admitting at most one interval constraint on any pair of time points. We show that the STP, which subsumes the major part of Vilain and Kautz's point algebra, can be solved in polynomial time. For general TCSPs, we present a decomposition scheme that performs the three reasoning tasks considered, and introduce a variety of techniques for improving its efficiency. We also study the applicability of path consistency algorithms as preprocessing of temporal problems, demonstrate their termination and bound their complexities.

AIJ Journal 1990 Journal Article

Enhancement schemes for constraint processing: Backjumping, learning, and cutset decomposition

• Rina Dechter

Researchers in the areas of constraint satisfaction problems, logic programming, and truth maintenance systems have suggested various schemes for enhancing the performance of the backtracking algorithm. This paper defines and compares the performance of three such schemes: “backjumping, ” “learning, ” and “cycle-cutset. ” The backjumping and the cycle-cutset methods work best when the constraint graph is sparse, while the learning scheme mostly benefits problem instances with dense constraint graphs. An integrated strategy is described which utilizes the distinct advantages of each scheme. Experiments show that, in hard problems, the average improvement realized by the integrated scheme is 20–25% higher than any of the individual schemes.

AAAI Conference 1990 Conference Paper

On the Expressiveness of Networks with Hidden Variables

• Rina Dechter

IJCAI Conference 1989 Conference Paper

Experimental Evaluation of Preprocessing Techniques in Constraint Satisfaction Problems

• Rina Dechter
• Itay Meiri

AIJ Journal 1989 Journal Article

Tree clustering for constraint networks

• Rina Dechter
• Judea Pearl

The paper offers a systematic way of regrouping constraints into hierarchical structures capable of supporting search without backtracking. The method involves the formation and preprocessing of an acyclic database that permits a large variety of queries and local perturbations to be processed swiftly, either by sequential backtrack-free procedures, or by distributed constraint propagation processes.

AAAI Conference 1988 Conference Paper

Belief Maintenance in Dynamic Constraint Networks

• Rina Dechter

AAAI Conference 1988 Conference Paper

Tree-Clustering Schemes for Constraint-Processing

• Rina Dechter

AIJ Journal 1987 Journal Article

Network-based heuristics for constraint-satisfaction problems

• Rina Dechter
• Judea Pearl

Many AI tasks can be formulated as constraint-satisfaction problems (CSP), i. e. , the assignment of values to variables subject to a set of constraints. While some CSPs are hard, those that are easy can often be mapped into sparse networks of constraints which, in the extreme case, are trees. This paper identifies classes of problems that lend themselves to easy solutions, and develops algorithms that solve these problems optimally. The paper then presents a method of generating heuristic advice to guide the order of value assignments based on both the sparseness found in the constraint network and the simplicity of tree-structured CSPs. The advice is generated by simplifying the pending subproblems into trees, counting the number of consistent solutions in each simplified subproblem, and comparing these counts to decide among the choices pending in the original problem.

AAAI Conference 1986 Conference Paper

Learning While Searching in Constraint-Satisfaction-Problems

• Rina Dechter

The popular use of backtracking as a control strategy for theorem proving in PROLOG and in Truth-Maintenance-Systems (TMS) led to increased interest in various schemes for enhancing the efficiency of backtrack search. Researchers have referred to these enhancement schemes by the names "Intelligent Backtracking" (in PROLOG), "Dependency-directed-backtracking" (in TMS) and others. Those improvements center on the issue of "jumping-back" to the source of the problem in front of dead-end situations. This paper examines another issue (much less explored) which arises in dead-ends. Specifically, we concentrate on the idea of constraint recording, namely, analyzing and storing the reasons for the dead-ends, and using them to guide future decisions, so that the same conflicts will not arise again. We view constraint recording as a process of learning, and examine several possible learning schemes studying the tradeoffs between the amount of learning and the improvement in search efficiency.

IJCAI Conference 1985 Conference Paper

The Anatomy of Easy Problems: A Constraint-Satisfaction Formulation

• Rina Dechter
• Judea Pearl

AAAI Conference 1983 Conference Paper

The Optimality of A + Revisited

• Rina Dechter

This paper examines the optimality of A*, in the sense of expanding the least number of distinct nodes, over three classes of algorithms which return solutions of comparable costs to that found by A*. We first show that A* is optimal over those algorithms guaranteed to And a solution at least as good as A*’s for every heuristic assignment h. Second, we consider a wider class of algorithms which, like A*, are guaranteed to find an optimal solution (i.e., admissible) if all cost estimates are optimistic (i.e., h(h*). On this class we show that A* is not optimal and that no optimal algorithm exists unless h is also consistent, in which case A* is optimal. Finally we show that A* is optimal over the subclass of best-first algorithms which are admissible whenever h(h*).

AIJ Journal 1980 Journal Article

Probabilistic analysis of the complexity of A∗

• Nam Huyn
• Rina Dechter
• Judea Pearl

This paper analyzes the number of nodes expanded by A∗ as a function of the accuracy of its heuristic estimates by treating the errors h∗ - h as random variables whose distributions may vary over the nodes in the graph. Our model consists of an m-ary tree with unit branch costs and a unique goal state situated at a distance N from the root. Two results are established: 1. (1) for any error distribution, if A∗1 is stochastically more informed than A∗2, then A∗1 is stochastically more efficient than A∗2, and 2. (2) if the probability that the relative error be bounded away from zero is greater than 1/m, then the average complexity of A∗ is exponential with N, where as if the probability of zero error is greater than 1–1/m, the average complexity is O(N).