Technical Report PHD-2007-12

Title: Variational Approximations for Probabilistic Graphical Models
Authors: Ydo Wexler
Supervisors: Dan Geiger
Abstract: Graphical models are a framework that allows for the incorporation of prior knowledge in a convenient manner. These models are commonly used in a variety of fields, and were found useful in many applications. The computations required in some applications of interest are demanding or even infeasible, and existing approximations are not always sufficient. The focus of this thesis is the development of tighter and more efficient approximation methods to complex graphical models, based on a unified variational framework.

The specific contributions of this thesis include the following. We develop an algorithm, called VIP* that efficiently obtains tighter lower bounds on quantities of interest in graphical models (e.g., posterior probabilities, likelihood of data). We present a novel and simple proof of convergence for this algorithm, which also proves the convergence of previously suggested algorithms, without the need to use Lagrange multipliers. In addition, We develop a new technique that computes upper and lower bounds on the likelihood of data and the maximum aposteriory probability (MAP) of the most probable assignment in a graphical model. Finally, we propose an importance sampling algorithm that takes advantage of variational approximation schemes in order to incorporate evidence into the sample generation. The uniqueness of our algorithm is that it also performs well on graphical models with deterministic dependencies.

Our techniques were applied to three problems, with promising results. The first application is genetic linkage analysis, which given a family pedigree in which some individuals are affected with a genetic disease, along with marker readings from affected and/or healthy individuals, uses a graphical model representation to indicate high probability locations of a disease gene. The second application is phylogenic model selection which searches a most probable phylogenetic tree that explains evolution based on genomic data. The third application is image reconstruction where the perceived image content in low resolution images is improved by generating high-resolution images.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2007
To the main CS technical reports page

Computer science department, Technion