William Lam

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

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.

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.

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.

UAI Conference 2011 Conference Paper

Factored Filtering of Continuous-Time Systems

• E. Busra Celikkaya
• Christian R. Shelton
• William Lam

JMLR Journal 2010 Journal Article

Continuous Time Bayesian Network Reasoning and Learning Engine

• Christian R. Shelton
• Yu Fan
• William Lam
• Joon Lee
• Jing Xu

We present a continuous time Bayesian network reasoning and learning engine (CTBN-RLE). A continuous time Bayesian network (CTBN) provides a compact (factored) description of a continuous-time Markov process. This software provides libraries and programs for most of the algorithms developed for CTBNs. For learning, CTBN-RLE implements structure and parameter learning for both complete and partial data. For inference, it implements exact inference and Gibbs and importance sampling approximate inference for any type of evidence pattern. Additionally, the library supplies visualization methods for graphically displaying CTBNs or trajectories of evidence. [abs] [ pdf ][ bib ] [ code ] &copy JMLR 2010. ( edit, beta )