Author name cluster

Kalev Kask

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

22 papers

2 author rows

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.

Details

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.

Details

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.

PDF Details DOI

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.

PDF Details DOI

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.

Details

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.

PDF Details DOI

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 beneﬁt 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.

PDF Details

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.

Details

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.

Details

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.

Details

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 ﬁnds signiﬁcantly 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 conﬁrm the superiority of the MinFill heuristic within the iterative scheme.

PDF Details

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 ﬁnd low width tree decompositions. A common approach for ﬁnding good decompositions is iteratively executing a greedy triangulation algorithm (e. g. min- ﬁll) 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 beneﬁt (in terms of time saved) of applying this rule to Bayes and Markov network instances.

PDF Details

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.

Details

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.

Details DOI

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

Details

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.

Details

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.

Details DOI

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.

PDF

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.

Details

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.

Details

AAAI Conference 1996 Conference Paper

A Graph-Based Method for Improving GSAT

Kalev Kask

GSAT is a randomized greedy local repair procedure that was introduced for solving propositional satisfiability and constraint satisfaction problems. We present an improvement to GSAT that is sensitive to the problem’ s structure. When the problem has a tree structure the algorithm is guaranteed to find a solution in linear time. For non-tree networks, the algorithm designates a subset of nodes, called cutset, and executes a regular GSAT algorithm on this set of variables. On all the rest of the variables it executes a specialized local search algorithm for trees. This algorithm finds an assignment that, like GSAT, locally minimizes the sum of unsatisfied constraints and also globally minimizes the number of conflicts in every tree-like subnetwork. We will present results of experiments showing that this new algorithm outperforms regular GSAT on sparse networks whose cycle-cutset size is bounded by 3OYoof the nodes.

PDF Details

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.

PDF