Alexander Ihler

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.

AAAI Conference 2023 Conference Paper

Design Amortization for Bayesian Optimal Experimental Design

• Noble Kennamer
• Steven Walton
• Alexander Ihler

Bayesian optimal experimental design is a sub-field of statistics focused on developing methods to make efficient use of experimental resources. Any potential design is evaluated in terms of a utility function, such as the (theoretically well-justified) expected information gain (EIG); unfortunately however, under most circumstances the EIG is intractable to evaluate. In this work we build off of successful variational approaches, which optimize a parameterized variational model with respect to bounds on the EIG. Past work focused on learning a new variational model from scratch for each new design considered. Here we present a novel neural architecture that allows experimenters to optimize a single variational model that can estimate the EIG for potentially infinitely many designs. To further improve computational efficiency, we also propose to train the variational model on a significantly cheaper-to-evaluate lower bound, and show empirically that the resulting model provides an excellent guide for more accurate, but expensive to evaluate bounds on the EIG. We demonstrate the effectiveness of our technique on generalized linear models, a class of statistical models that is widely used in the analysis of controlled experiments. Experiments show that our method is able to greatly improve accuracy over existing approximation strategies, and achieve these results with far better sample efficiency.

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.

ICML Conference 2022 Conference Paper

Be Like Water: Adaptive Floating Point for Machine Learning

• Thomas Y. Yeh
• Max Sterner
• Zerlina Lai
• Brandon Chuang
• Alexander Ihler

In the pursuit of optimizing memory and compute density to accelerate machine learning applications, reduced precision training and inference has been an active area of research. While some approaches selectively apply low precision computations, this may require costly off-chip data transfers or mixed precision support. In this paper, we propose a novel numerical representation, Adaptive Floating Point (AFP), that dynamically adjusts to the characteristics of deep learning data. AFP requires no changes to the model topology, requires no additional training, and applies to all layers of DNN models. We evaluate AFP on a spectrum of representative models in computer vision and NLP, and show that our technique enables ultra-low precision inference of deep learning models while providing accuracy comparable to full precision inference. By dynamically adjusting to ML data, AFP increases memory density by 1. 6x, 1. 6x, and 3. 2x and compute density by 4x, 1. 3x, and 12x when compared to BFP, BFloat16, and FP32.

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.

ICML Conference 2022 Conference Paper

Reducing Variance in Temporal-Difference Value Estimation via Ensemble of Deep Networks

• Litian Liang
• Yaosheng Xu
• Stephen Marcus McAleer
• Dailin Hu
• Alexander Ihler
• Pieter Abbeel
• Roy Fox

In temporal-difference reinforcement learning algorithms, variance in value estimation can cause instability and overestimation of the maximal target value. Many algorithms have been proposed to reduce overestimation, including several recent ensemble methods, however none have shown success in sample-efficient learning through addressing estimation variance as the root cause of overestimation. In this paper, we propose MeanQ, a simple ensemble method that estimates target values as ensemble means. Despite its simplicity, MeanQ shows remarkable sample efficiency in experiments on the Atari Learning Environment benchmark. Importantly, we find that an ensemble of size 5 sufficiently reduces estimation variance to obviate the lagging target network, eliminating it as a source of bias and further gaining sample efficiency. We justify intuitively and empirically the design choices in MeanQ, including the necessity of independent experience sampling. On a set of 26 benchmark Atari environments, MeanQ outperforms all tested baselines, including the best available baseline, SUNRISE, at 100K interaction steps in 16/26 environments, and by 68% on average. MeanQ also outperforms Rainbow DQN at 500K steps in 21/26 environments, and by 49% on average, and achieves average human-level performance using 200K ($\pm$100K) interaction steps. Our implementation is available at https: //github. com/indylab/MeanQ.

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.

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.

ICML Conference 2018 Conference Paper

ContextNet: Deep learning for Star Galaxy Classification

• Noble Kennamer
• David Kirkby
• Alexander Ihler
• Francisco Javier Sanchez-Lopez

We present a framework to compose artificial neural networks in cases where the data cannot be treated as independent events. Our particular motivation is star galaxy classification for ground based optical surveys. Due to a turbulent atmosphere and imperfect instruments, a single image of an astronomical object is not enough to definitively classify it as a star or galaxy. Instead the context of the surrounding objects imaged at the same time need to be considered in order to make an optimal classification. The model we present is divided into three distinct ANNs: one designed to capture local features about each object, the second to compare these features across all objects in an image, and the third to make a final prediction for each object based on the local and compared features. By exploiting the ability to replicate the weights of an ANN, the model can handle an arbitrary and variable number of individual objects embedded in a larger exposure. We train and test our model on simulations of a large up and coming ground based survey, the Large Synoptic Survey Telescope (LSST). We compare to the state of the art approach, showing improved overall performance as well as better performance for a specific class of objects that is important for the LSST.

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.

AAAI Conference 2018 Conference Paper

Lifted Generalized Dual Decomposition

• Nicholas Gallo
• Alexander Ihler

Many real-world problems, such as Markov Logic Networks (MLNs) with evidence, can be represented as a highly symmetric graphical model perturbed by additional potentials. In these models, variational inference approaches that exploit exact model symmetries are often forced to ground the entire problem, while methods that exploit approximate symmetries (such as by constructing an over-symmetric approximate model) offer no guarantees on solution quality. In this paper, we present a method based on a lifted variant of the generalized dual decomposition (GenDD) for marginal MAP inference which provides a principled way to exploit symmetric sub-structures in a graphical model. We develop a coarse-to- fine inference procedure that provides any-time upper bounds on the objective. The upper bound property of GenDD provides a principled way to guide the refinement process, providing good any-time performance and eventually arriving at the ground optimal solution.

NeurIPS Conference 2018 Conference Paper

Lifted Weighted Mini-Bucket

• Nicholas Gallo
• Alexander Ihler

Many graphical models, such as Markov Logic Networks (MLNs) with evidence, possess highly symmetric substructures but no exact symmetries. Unfortunately, there are few principled methods that exploit these symmetric substructures to perform efficient approximate inference. In this paper, we present a lifted variant of the Weighted Mini-Bucket elimination algorithm which provides a principled way to (i) exploit the highly symmetric substructure of MLN models, and (ii) incorporate high-order inference terms which are necessary for high quality approximate inference. Our method has significant control over the accuracy-time trade-off of the approximation, allowing us to generate any-time approximations. Experimental results demonstrate the utility of this class of approximations, especially in models with strong repulsive potentials.

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.

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.

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.

NeurIPS Conference 2016 Conference Paper

Learning Infinite RBMs with Frank-Wolfe

• Wei Ping
• Qiang Liu
• Alexander Ihler

In this work, we propose an infinite restricted Boltzmann machine (RBM), whose maximum likelihood estimation (MLE) corresponds to a constrained convex optimization. We consider the Frank-Wolfe algorithm to solve the program, which provides a sparse solution that can be interpreted as inserting a hidden unit at each iteration, so that the optimization process takes the form of a sequence of finite models of increasing complexity. As a side benefit, this can be used to easily and efficiently identify an appropriate number of hidden units during the optimization. The resulting model can also be used as an initialization for typical state-of-the-art RBM training algorithms such as contrastive divergence, leading to models with consistently higher test likelihood than random initialization.

NeurIPS Conference 2015 Conference Paper

Decomposition Bounds for Marginal MAP

• Wei Ping
• Qiang Liu
• Alexander Ihler

Marginal MAP inference involves making MAP predictions in systems defined with latent variables or missing information. It is significantly more difficult than pure marginalization and MAP tasks, for which a large class of efficient and convergent variational algorithms, such as dual decomposition, exist. In this work, we generalize dual decomposition to a generic powered-sum inference task, which includes marginal MAP, along with pure marginalization and MAP, as special cases. Our method is based on a block coordinate descent algorithm on a new convex decomposition bound, that is guaranteed to converge monotonically, and can be parallelized efficiently. We demonstrate our approach on various inference queries over real-world problems from the UAI approximate inference challenge, showing that our framework is faster and more reliable than previous methods.

UAI Conference 2015 Conference Paper

Estimating the Partition Function by Discriminance Sampling

• Qiang Liu 0001
• Jian Peng 0001
• Alexander Ihler
• John W. Fisher III

models. As such, efficient approximations via variational inference and Monte Carlo methods are of great interest. Importance sampling (IS) and its variant, annealed IS (AIS) have been widely used for estimating the partition function in graphical models, such as Markov random fields and deep generative models. However, IS tends to underestimate the partition function and is subject to high variance when the proposal distribution is more peaked than the target distribution. On the other hand, “reverse” versions of IS and AIS tend to overestimate the partition function, and degenerate when the target distribution is more peaked than the proposal distribution. In this work, we present a simple, general method that gives much more reliable and robust estimates than either IS (AIS) or reverse IS (AIS). Our method works by converting the estimation problem into a simple classification problem that discriminates between the samples drawn from the target and the proposal. We give extensive theoretical and empirical justification; in particular, we show that an annealed version of our method significantly outperforms both AIS and reverse AIS as proposed by Burda et al. (2015), which has been the stateof-the-art for likelihood evaluation in deep generative models. Importance sampling (IS) and its variants, such as annealed importance sampling (AIS) (Neal, 2001), are probably the most widely used Monte Carlo methods for estimating the partition function. IS works by drawing samples from a tractable proposal (or reference) distribution R p0 (x), and estimates the target partition function Z = f (x) by averaging the importance weights f (x)/p0 (x) across the samples. Unfortunately, the IS estimate often has very high variance if the choice of proposal distribution is very different from the target, especially when the proposal is more peaked or has thinner tails than the target. In addition, in practice IS often underestimates the partition function due to the heavy-tailed nature of the importance weights, leading to overly optimistic likelihood estimates when used for model evaluation (e. g. , Burda et al. , 2015).

UAI Conference 2015 Conference Paper

Incremental Region Selection for Mini-bucket Elimination Bounds

• Sholeh Forouzan
• Alexander Ihler

Region choice is a key issue for many approximate inference bounds. Mini-bucket elimination avoids the space and time complexity of exact inference by using a top-down partitioning approach that mimics the construction of a junction tree and aims to minimize the number of regions subject to a bound on their size; however, these methods rarely take into account functions’ values. In contrast, message passing algorithms often use “cluster pursuit” methods to select regions, a bottom-up approach in which a predefined set of clusters (such as triplets) is scored and incrementally added. In this work, we develop a hybrid approach that balances the advantages of both perspectives, providing larger regions chosen in an intelligent, energy-based way. Our method is applicable to bounds on a variety of inference tasks, and we demonstrate its power empirically on a broad array of problem types.

NeurIPS Conference 2015 Conference Paper

Probabilistic Variational Bounds for Graphical Models

• Qiang Liu
• John Fisher III
• Alexander Ihler

Variational algorithms such as tree-reweighted belief propagation can provide deterministic bounds on the partition function, but are often loose and difficult to use in an any-time'' fashion, expending more computation for tighter bounds. On the other hand, Monte Carlo estimators such as importance sampling have excellent any-time behavior, but depend critically on the proposal distribution. We propose a simple Monte Carlo based inference method that augments convex variational bounds by adding importance sampling (IS). We argue that convex variational methods naturally provide good IS proposals that cover the probability of the target distribution, and reinterpret the variational optimization as designing a proposal to minimizes an upper bound on the variance of our IS estimator. This both provides an accurate estimator and enables the construction of any-time probabilistic bounds that improve quickly and directly on state of-the-art variational bounds, which provide certificates of accuracy given enough samples relative to the error in the initial bound.

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.

NeurIPS Conference 2014 Conference Paper

Distributed Estimation, Information Loss and Exponential Families

• Qiang Liu
• Alexander Ihler

Distributed learning of probabilistic models from multiple data repositories with minimum communication is increasingly important. We study a simple communication-efficient learning framework that first calculates the local maximum likelihood estimates (MLE) based on the data subsets, and then combines the local MLEs to achieve the best possible approximation to the global MLE, based on the whole dataset jointly. We study the statistical properties of this framework, showing that the loss of efficiency compared to the global setting relates to how much the underlying distribution families deviate from full exponential families, drawing connection to the theory of information loss by Fisher, Rao and Efron. We show that the full-exponential-family-ness" represents the lower bound of the error rate of arbitrary combinations of local MLEs, and is achieved by a KL-divergence-based combination method but not by a more common linear combination method. We also study the empirical properties of the KL and linear combination methods, showing that the KL method significantly outperforms linear combination in practical settings with issues such as model misspecification, non-convexity, and heterogeneous data partitions. "

ICML Conference 2014 Conference Paper

Marginal Structured SVM with Hidden Variables

• Wei Ping
• Qiang Liu 0001
• Alexander Ihler

In this work, we propose the marginal structured SVM (MSSVM) for structured prediction with hidden variables. MSSVM properly accounts for the uncertainty of hidden variables, and can significantly outperform the previously proposed latent structured SVM (LSSVM; Yu & Joachims (2009)) and other state-of-art methods, especially when that uncertainty is large. Our method also results in a smoother objective function, making gradient-based optimization of MSSVMs converge significantly faster than for LSSVMs. We also show that our method consistently outperforms hidden conditional random fields (HCRFs; Quattoni et al. (2007)) on both simulated and real-world datasets. Furthermore, we propose a unified framework that includes both our and several other existing methods as special cases, and provides insights into the comparison of different models in practice.

NeurIPS Conference 2013 Conference Paper

Scoring Workers in Crowdsourcing: How Many Control Questions are Enough?

• Qiang Liu
• Alexander Ihler
• Mark Steyvers

We study the problem of estimating continuous quantities, such as prices, probabilities, and point spreads, using a crowdsourcing approach. A challenging aspect of combining the crowd's answers is that workers' reliabilities and biases are usually unknown and highly diverse. Control items with known answers can be used to evaluate workers' performance, and hence improve the combined results on the target items with unknown answers. This raises the problem of how many control items to use when the total number of items each workers can answer is limited: more control items evaluates the workers better, but leaves fewer resources for the target items that are of direct interest, and vice versa. We give theoretical results for this problem under different scenarios, and provide a simple rule of thumb for crowdsourcing practitioners. As a byproduct, we also provide theoretical analysis of the accuracy of different consensus methods.

JMLR Journal 2013 Journal Article

Using Symmetry and Evolutionary Search to Minimize Sorting Networks

• Qiang Liu
• Alexander Ihler

The marginal maximum a posteriori probability (MAP) estimation problem, which calculates the mode of the marginal posterior distribution of a subset of variables with the remaining variables marginalized, is an important inference problem in many models, such as those with hidden variables or uncertain parameters. Unfortunately, marginal MAP can be NP-hard even on trees, and has attracted less attention in the literature compared to the joint MAP (maximization) and marginalization problems. We derive a general dual representation for marginal MAP that naturally integrates the marginalization and maximization operations into a joint variational optimization problem, making it possible to easily extend most or all variational-based algorithms to marginal MAP. In particular, we derive a set of 'mixed-product' message passing algorithms for marginal MAP, whose form is a hybrid of max-product, sum-product and a novel 'argmax-product' message updates. We also derive a class of convergent algorithms based on proximal point methods, including one that transforms the marginal MAP problem into a sequence of standard marginalization problems. Theoretically, we provide guarantees under which our algorithms give globally or locally optimal solutions, and provide novel upper bounds on the optimal objectives. Empirically, we demonstrate that our algorithms significantly outperform the existing approaches, including a state-of-the-art algorithm based on local search methods. [abs] [ pdf ][ bib ] &copy JMLR 2013. ( edit, beta )

NeurIPS Conference 2013 Conference Paper

Variational Planning for Graph-based MDPs

• Qiang Cheng
• Qiang Liu
• Feng Chen
• Alexander Ihler

Markov Decision Processes (MDPs) are extremely useful for modeling and solving sequential decision making problems. Graph-based MDPs provide a compact representation for MDPs with large numbers of random variables. However, the complexity of exactly solving a graph-based MDP usually grows exponentially in the number of variables, which limits their application. We present a new variational framework to describe and solve the planning problem of MDPs, and derive both exact and approximate planning algorithms. In particular, by exploiting the graph structure of graph-based MDPs, we propose a factored variational value iteration algorithm in which the value function is first approximated by the multiplication of local-scope value functions, then solved by minimizing a Kullback-Leibler (KL) divergence. The KL divergence is optimized using the belief propagation algorithm, with complexity exponential in only the cluster size of the graph. Experimental comparison on different models shows that our algorithm outperforms existing approximation algorithms at finding good policies.

UAI Conference 2012 Conference Paper

A Cluster-Cumulant Expansion at the Fixed Points of Belief Propagation

• Max Welling
• Andrew Gelfand
• Alexander Ihler

We introduce a new cluster-cumulant expansion (CCE) based on the fixed points of iterative belief propagation (IBP). This expansion is similar in spirit to the loop-series (LS) recently introduced in [1]. However, in contrast to the latter, the CCE enjoys the following important qualities: 1) it is defined for arbitrary state spaces 2) it is easily extended to fixed points of generalized belief propagation (GBP), 3) disconnected groups of variables will not contribute to the CCE and 4) the accuracy of the expansion empirically improves upon that of the LS. The CCE is based on the same Möbius transform as the Kikuchi approximation, but unlike GBP does not require storing the beliefs of the GBP-clusters nor does it suffer from convergence issues during belief updating.

AAAI Conference 2012 Conference Paper

Approximating the Sum Operation for Marginal-MAP Inference

• Qiang Cheng
• Feng Chen
• Jianwu Dong
• Wenli Xu
• Alexander Ihler

We study the marginal-MAP problem on graphical models, and present a novel approximation method based on direct approximation of the sum operation. A primary difficulty of marginal-MAP problems lies in the non-commutativity of the sum and max operations, so that even in highly structured models, marginalization may produce a densely connected graph over the variables to be maximized, resulting in an intractable potential function with exponential size. We propose a chain decomposition approach for summing over the marginalized variables, in which we produce a structured approximation to the MAP component of the problem consisting of only pairwise potentials. We show that this approach is equivalent to the maximization of a specific variational free energy, and it provides an upper bound of the optimal probability. Finally, experimental results demonstrate that our method performs favorably compared to previous methods.

UAI Conference 2012 Conference Paper

Belief Propagation for Structured Decision Making

• Qiang Liu 0001
• Alexander Ihler

Variational inference algorithms such as belief propagation have had tremendous impact on our ability to learn and use graphical models, and give many insights for developing or understanding exact and approximate inference. However, variational approaches have not been widely adoped for decision making in graphical models, often formulated through influence diagrams and including both centralized and decentralized (or multi-agent) decisions. In this work, we present a general variational framework for solving structured cooperative decisionmaking problems, use it to propose several belief propagation-like algorithms, and analyze them both theoretically and empirically.

ICML Conference 2012 Conference Paper

Distributed Parameter Estimation via Pseudo-likelihood

• Qiang Liu 0001
• Alexander Ihler

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.

NeurIPS Conference 2012 Conference Paper

Variational Inference for Crowdsourcing

• Qiang Liu
• Jian Peng
• Alexander Ihler

Crowdsourcing has become a popular paradigm for labeling large datasets. However, it has given rise to the computational task of aggregating the crowdsourced labels provided by a collection of unreliable annotators. We approach this problem by transforming it into a standard inference problem in graphical models, and applying approximate variational methods, including belief propagation (BP) and mean field (MF). We show that our BP algorithm generalizes both majority voting and a recent algorithm by Karger et al, while our MF method is closely related to a commonly used EM algorithm. In both cases, we find that the performance of the algorithms critically depends on the choice of a prior distribution on the workers' reliability; by choosing the prior properly, both BP and MF (and EM) perform surprisingly well on both simulated and real-world datasets, competitive with state-of-the-art algorithms based on more complicated modeling assumptions.

ICML Conference 2011 Conference Paper

Bounding the Partition Function using Holder's Inequality

• Qiang Liu 0001
• Alexander Ihler

AAAI Conference 2011 Conference Paper

Fast Parallel and Adaptive Updates for Dual-Decomposition Solvers

• Ozgur Sumer
• Umut Acar
• Alexander Ihler
• Ramgopal Mettu

Dual-decomposition (DD) methods are quickly becoming important tools for estimating the minimum energy state of a graphical model. DD methods decompose a complex model into a collection of simpler subproblems that can be solved exactly (such as trees), that in combination provide upper and lower bounds on the exact solution. Subproblem choice can play a major role: larger subproblems tend to improve the bound more per iteration, while smaller subproblems enable highly parallel solvers and can benefit from re-using past solutions when there are few changes between iterations. We propose an algorithm that can balance many of these aspects to speed up convergence. Our method uses a cluster tree data structure that has been proposed for adaptive exact inference tasks, and we apply it in this paper to dualdecomposition approximate inference. This approach allows us to process large subproblems to improve the bounds at each iteration, while allowing a high degree of parallelizability and taking advantage of subproblems with sparse updates. For both synthetic inputs and a real-world stereo matching problem, we demonstrate that our algorithm is able to achieve significant improvement in convergence time.

UAI Conference 2011 Conference Paper

Planar Cycle Covering Graphs

• Julian Yarkony
• Alexander Ihler
• Charless C. Fowlkes

UAI Conference 2011 Conference Paper

Tightening MRF Relaxations with Planar Subproblems

• Julian Yarkony
• Ragib Morshed
• Alexander Ihler
• Charless C. Fowlkes

UAI Conference 2011 Conference Paper

Variational Algorithms for Marginal MAP

• Qiang Liu 0001
• Alexander Ihler

UAI Conference 2010 Conference Paper

Negative Tree Reweighted Belief Propagation

• Qiang Liu 0001
• Alexander Ihler

We introduce a new class of lower bounds on the log partition function of a Markov random field which makes use of a reversed Jensen’s inequality. In particular, our method approximates the intractable distribution using a linear combination of spanning trees with negative weights. This technique is a lower-bound counterpart to the tree-reweighted belief propagation algorithm, which uses a convex combination of spanning trees with positive weights to provide corresponding upper bounds. We develop algorithms to optimize and tighten the lower bounds over the non-convex set of valid parameter values. Our algorithm generalizes mean field approaches (including naı̈ve and structured mean field approximations), which it includes as a limiting case.

ICML Conference 2010 Conference Paper

Particle Filtered MCMC-MLE with Connections to Contrastive Divergence

• Arthur U. Asuncion
• Qiang Liu 0001
• Alexander Ihler
• Padhraic Smyth

NeurIPS Conference 2009 Conference Paper

Particle-based Variational Inference for Continuous Systems

• Andrew Frank
• Padhraic Smyth
• Alexander Ihler

Since the development of loopy belief propagation, there has been considerable work on advancing the state of the art for approximate inference over distributions defined on discrete random variables. Improvements include guarantees of convergence, approximations that are provably more accurate, and bounds on the results of exact inference. However, extending these methods to continuous-valued systems has lagged behind. While several methods have been developed to use belief propagation on systems with continuous values, they have not as yet incorporated the recent advances for discrete variables. In this context we extend a recently proposed particle-based belief propagation algorithm to provide a general framework for adapting discrete message-passing algorithms to perform inference in continuous systems. The resulting algorithms behave similarly to their purely discrete counterparts, extending the benefits of these more advanced inference techniques to the continuous domain.

UAI Conference 2008 Conference Paper

Adaptive inference on general graphical models

• Umut A. Acar
• Alexander Ihler
• Ramgopal Mettu
• Özgür Sümer

Many algorithms and applications involve repeatedly solving variations of the same inference problem; for example we may want to introduce new evidence to the model or perform updates to conditional dependencies. The goal of adaptive inference is to take advantage of what is preserved in the model and perform inference more rapidly than from scratch. In this paper, we describe techniques for adaptive inference on general graphs that support marginal computation and updates to the conditional probabilities and dependencies in logarithmic time. We give experimental results for an implementation of our algorithm, and demonstrate its potential performance benefit in the study of protein structure.

UAI Conference 2007 Conference Paper

Accuracy Bounds for Belief Propagation

• Alexander Ihler

The belief propagation (BP) algorithm is widely applied to perform approximate inference on arbitrary graphical models, in part due to its excellent empirical properties and performance. However, little is known theoretically about when this algorithm will perform well. Using recent analysis of convergence and stability properties in BP and new results on approximations in binary systems, we derive a bound on the error in BP's estimates for pairwise Markov random fields over discrete-valued random variables. Our bound is relatively simple to compute, and compares favorably with a previous method of bounding the accuracy of BP.

NeurIPS Conference 2007 Conference Paper

Efficient Bayesian Inference for Dynamically Changing Graphs

• Ozgur Sumer
• Umut Acar
• Alexander Ihler
• Ramgopal Mettu

Motivated by stochastic systems in which observed evidence and conditional de- pendencies between states of the network change over time, and certain quantities of interest (marginal distributions, likelihood estimates etc. ) must be updated, we study the problem of adaptive inference in tree-structured Bayesian networks. We describe an algorithm for adaptive inference that handles a broad range of changes to the network and is able to maintain marginal distributions, MAP estimates, and data likelihoods in all expected logarithmic time. We give an implementation of our algorithm and provide experiments that show that the algorithm can yield up to two orders of magnitude speedups on answering queries and responding to dy- namic changes over the sum-product algorithm.

UAI Conference 2006 Conference Paper

Gibbs Sampling for (Coupled) Infinite Mixture Models in the Stick Breaking Representation

• Ian Porteous
• Alexander Ihler
• Padhraic Smyth
• Max Welling

NeurIPS Conference 2006 Conference Paper

Learning Time-Intensity Profiles of Human Activity using Non-Parametric Bayesian Models

• Alexander Ihler
• Padhraic Smyth

Data sets that characterize human activity over time through collections of timestamped events or counts are of increasing interest in application areas as humancomputer interaction, video surveillance, and Web data analysis. We propose a non-parametric Bayesian framework for modeling collections of such data. In particular, we use a Dirichlet process framework for learning a set of intensity functions corresponding to different categories, which form a basis set for representing individual time-periods (e. g. , several days) depending on which categories the time-periods are assigned to. This allows the model to learn in a data-driven fashion what "factors" are generating the observations on a particular day, including (for example) weekday versus weekend effects or day-specific effects corresponding to unique (single-day) occurrences of unusual behavior, sharing information where appropriate to obtain improved estimates of the behavior associated with each category. Applications to realworld data sets of count data involving both vehicles and people are used to illustrate the technique.

NeurIPS Conference 2004 Conference Paper

Message Errors in Belief Propagation

• Alexander Ihler
• John Fisher
• Alan Willsky

Belief propagation (BP) is an increasingly popular method of perform- ing approximate inference on arbitrary graphical models. At times, even further approximations are required, whether from quantization or other simplified message representations or from stochastic approxima- tion methods. Introducing such errors into the BP message computations has the potential to adversely affect the solution obtained. We analyze this effect with respect to a particular measure of message error, and show bounds on the accumulation of errors in the system. This leads both to convergence conditions and error bounds in traditional and approximate BP message passing.

NeurIPS Conference 2003 Conference Paper

Efficient Multiscale Sampling from Products of Gaussian Mixtures

• Alexander Ihler
• Erik Sudderth
• William Freeman
• Alan Willsky

The problem of approximating the product of several Gaussian mixture distributions arises in a number of contexts, including the nonparametric belief propagation (NBP) inference algorithm and the training of prod- uct of experts models. This paper develops two multiscale algorithms for sampling from a product of Gaussian mixtures, and compares their performance to existing methods. The first is a multiscale variant of pre- viously proposed Monte Carlo techniques, with comparable theoretical guarantees but improved empirical convergence rates. The second makes use of approximate kernel density evaluation methods to construct a fast approximate sampler, which is guaranteed to sample points to within a tunable parameter (cid: 15) of their true probability. We compare both multi- scale samplers on a set of computational examples motivated by NBP, demonstrating significant improvements over existing methods.

NeurIPS Conference 1999 Conference Paper

Learning Informative Statistics: A Nonparametnic Approach

• John Fisher III
• Alexander Ihler
• Paul Viola

We discuss an information theoretic approach for categorizing and mod(cid: 173) eling dynamic processes. The approach can learn a compact and informa(cid: 173) tive statistic which summarizes past states to predict future observations. Furthermore, the uncertainty of the prediction is characterized nonpara(cid: 173) metrically by a joint density over the learned statistic and present obser(cid: 173) vation. We discuss the application of the technique to both noise driven dynamical systems and random processes sampled from a density which is conditioned on the past. In the first case we show results in which both the dynamics of random walk and the statistics of the driving noise are captured. In the second case we present results in which a summarizing statistic is learned on noisy random telegraph waves with differing de(cid: 173) pendencies on past states. In both cases the algorithm yields a principled approach for discriminating processes with differing dynamics and/or de(cid: 173) pendencies. The method is grounded in ideas from information theory and nonparametric statistics.