Kalev Kask
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Kalev Kask has a total of 11 co-authors. Here are the top co-authors by number of shared publications:
- Rina Dechter
University of California, Irvine
8 shared publications - Robert Mateescu
Microsoft Research 7 J J Thomson Avenue CB3 0FB Cambridge UK
2 shared publications - Vibhav Gogate
Computer Science & Engineering University of Washington 98195 Seattle WA USA
2 shared publications Avi Dechter
College of Business and Economics, California State University, Northridge, CA 91330, USA
1 shared publication- Irina Rish
Department of Information and Computer Science University of California Irvine
1 shared publication Javier Larrosa
Universitat Politècnica de Catalunya (UPC), Barcelona, Spain
1 shared publication
Latest Publications
- 1 June 2018
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 94, 41-62
Subproblem ordering heuristics for AND/OR best-first search
- 1 June 2018
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 94, 41-62
Subproblem ordering heuristics for AND/OR best-first search
- Open Access
Join-Graph Propagation Algorithms
The paper investigates parameterized approximate message-passing schemes that are based on bounded inference and are inspired by Pearl's belief propagation algorithm (BP). We start with the bounded inference mini-clustering algorithm and then move to the iterative scheme called Iterative Join-Graph Propagation (IJGP), that combines both iteration and bounded inference. Algorithm IJGP belongs to the class of Generalized Belief Propagation algorithms, a framework that allowed connections with approximate algorithms from statistical physics and is shown empirically to surpass the performance of mini-clustering and belief propagation, as well as a number of other state-of-the-art algorithms on several classes of networks. We also provide insight into the accuracy of iterative BP and IJGP by relating these algorithms to well known classes of constraint propagation schemes.
Open AccessJoin-Graph Propagation Algorithms
The paper investigates parameterized approximate message-passing schemes that are based on bounded inference and are inspired by Pearl's belief propagation algorithm (BP). We start with the bounded inference mini-clustering algorithm and then move to the iterative scheme called Iterative Join-Graph Propagation (IJGP), that combines both iteration and bounded inference. Algorithm IJGP belongs to the class of Generalized Belief Propagation algorithms, a framework that allowed connections with approximate algorithms from statistical physics and is shown empirically to surpass the performance of mini-clustering and belief propagation, as well as a number of other state-of-the-art algorithms on several classes of networks. We also provide insight into the accuracy of iterative BP and IJGP by relating these algorithms to well known classes of constraint propagation schemes.
- Open Access
Empirical Evaluation of Approximation Algorithms for Probabilistic Decoding
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.
Open AccessEmpirical Evaluation of Approximation Algorithms for Probabilistic Decoding
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.
- Open Access
Mini-Bucket Heuristics for Improved Search
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.
Open AccessMini-Bucket Heuristics for Improved Search
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.
- Open Access
Iterative Join-Graph Propagation
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.
Open AccessIterative Join-Graph Propagation
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.
- Open Access
Systematic vs. Non-systematic Algorithms for Solving the MPE Task
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.
Open AccessSystematic vs. Non-systematic Algorithms for Solving the MPE Task
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.
- Open Access
- 17 March 2010
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 37, 279-328
Join-Graph Propagation Algorithms
The paper investigates parameterized approximate message-passing schemes that are based on bounded inference and are inspired by Pearl’s belief propagation algorithm (BP). We start with the bounded inference mini-clustering algorithm and then move to the iterative scheme called Iterative Join-Graph Propagation (IJGP), that combines both iteration and bounded inference. Algorithm IJGP belongs to the class of Generalized Belief Propagation algorithms, a framework that allowed connections with approximate algorithms from statistical physics and is shown empirically to surpass the performance of mini-clustering and belief propagation, as well as a number of other state-of-the-art algorithms on several classes of networks. We also provide insight into the accuracy of iterative BP and IJGP by relating these algorithms to well known classes of constraint propagation schemes.
- 17 March 2010
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 37, 279-328
Open AccessJoin-Graph Propagation Algorithms
The paper investigates parameterized approximate message-passing schemes that are based on bounded inference and are inspired by Pearl’s belief propagation algorithm (BP). We start with the bounded inference mini-clustering algorithm and then move to the iterative scheme called Iterative Join-Graph Propagation (IJGP), that combines both iteration and bounded inference. Algorithm IJGP belongs to the class of Generalized Belief Propagation algorithms, a framework that allowed connections with approximate algorithms from statistical physics and is shown empirically to surpass the performance of mini-clustering and belief propagation, as well as a number of other state-of-the-art algorithms on several classes of networks. We also provide insight into the accuracy of iterative BP and IJGP by relating these algorithms to well known classes of constraint propagation schemes.
- 1 August 2005
- Published by Elsevier in Artificial Intelligence
- Vol. 166 (1-2) , 165-193
Unifying tree decompositions for reasoning in graphical models
- 1 August 2005
- Published by Elsevier in Artificial Intelligence
- Vol. 166 (1-2) , 165-193
Unifying tree decompositions for reasoning in graphical models
- 1 June 2001
- Published by Elsevier in Artificial Intelligence
- Vol. 129 (1-2) , 91-131
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.
- 1 June 2001
- Published by Elsevier in Artificial Intelligence
- Vol. 129 (1-2) , 91-131
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.