Bottom-Up Approaches to Approximate Inference and Learning in Discrete Graphical Models

Probabilistic graphical models offer a convenient and compact way to describe complex and uncertain relationships in data. A graphical model defines a joint probability distribution over many random variables that factors over an underlying graph structure. Unfortunately, inference is generally intractable in graphical models which accurately describe the complex dependencies occurring in real data.;In this thesis, we focus on theory and algorithms for learning and approximate inference in graphical models. We propose and investigate a bottom-up approach to inference and learning, where we start with an initial, computationally cheap approximation and then improve upon the initial approximation through additional computation. We study the computation-accuracy trade-off inherent to the bottom-up approach in three different settings.;First, we consider the task of finding the most probable (MAP) configuration of a model. We focus on a class of graphical models corresponding to the weighted matching problem - a classic combinatorial optimization problem - and on MAP inference algorithms based on linear programming (LP) relaxations. In this setting, the optimum of the LP relaxation provides an upper bound on the MAP solution to the weighted matching problem that may be quite loose. We thus propose a bottom-up, cutting-plane algorithm which iteratively adds constraints that tighten the upper bound on the matching solution. We then derive a max-product belief propagation algorithm that provably solves the matching problem for certain choices of tightening constraints.;Second, we consider the task of computing the marginal probabilities of a model. Loopy Belief Propagation (BP) is an algorithm for obtaining marginal probability estimates by iteratively passing messages between neighboring nodes in a cyclic graphical model. Generalized Belief Propagation (GBP) is a class of approximate inference algorithms that builds upon Loopy BP by passing messages between clusters of nodes. GBP offers the promise to yield marginal estimates that are far more accurate than Loopy BP, but is also very sensitive to the choice of clusters used. We thus propose a criteria - tree-robustness - for choosing the collection of clusters used by GBP that is, in some sense, no worse than Loopy BP when the factors defining our model induce a tree. We propose a method to find a collection of clusters that are tree-robust and empirically demonstrate the effectiveness of the proposed criteria.;Third, we consider the task of learning the parameters of a model from data. Maximum likelihood estimation in graphical models is difficult to the intractability of computing the log-partition function and marginals. In surrogate likelihood training, one approximates these quantities using an approximate inference algorithm. We focus on approximate inference methods that utilize a control parameter to trade computation for accuracy and examine when investing more computation leads to more accurate parameter estimates and models that yield more accurate predictions. Surprisingly, we show that it is not always beneficial to increase computation during learning, particularly in data sets containing relatively few observations and also when the model being fit is heavily misspecified. We also expose an interesting bias-variance trade-off between low computation inference methods and high computation inference methods.