| Approximation algorithms for reasoning in probabilistic graphical models have seen wide applicability and success in fields as diverse as artificial intelligence, machine learning, information theory, statistical physics, and computational biology. Belief propagation is perhaps the most influential such algorithm for approximate inference, and in the past decade, much of the research in this field has indeed focused on belief propagation and related methods.;We develop in this thesis a new perspective on approximate inference and belief propagation that is based on performing two steps. First, we relax the structure of a model so that it is amenable to exact reasoning. Second, we introduce auxiliary parameters into the simplified model, whose values we set so that we compensate for defects introduced in the relaxation. By framing algorithms such as belief propagation from this perspective, we are given the ability to trade the quality of an approximation with the complexity of computing it. This perspective further reveals new properties about approximate inference algorithms that suggest specific improvements, leading to significant gains in both accuracy and efficiency. We are further poised to design new approximations with their own unique properties, as well as design approximations for models used in more specialized domains, such as in satisfiability.;More specifically, this thesis identifies a generalization of sum-product and max-product belief propagation, based on structural relaxations. We further identify the Bethe approximation and the mini-buckets approximation in terms of these same relaxations. We further show how to effectively recover structure into these approximations, in order to identify more accurate and effective approximations. We further propose a new class of approximations for bounding probabilistic queries of interest, and propose an application in the context of weighted Max-SAT. |
