Structural Approximations for Genetic Analysis
Ydo Wexler, Technion
Probabilistic graphical models are an elegant framework
to represent joint probability distributions in a compact manner.
The dependency relationships between random variables
which are nodes in the graph are represented through the presence of arcs
in the model.
This intuitively appealing presentation also naturally enables
the design of efficient general-purpose algorithms
for computing marginal probabilities, called inference algorithms.
The general inference problem is NP-hard, and although there are many cases
where the model is small and exact inference algorithms are feasible,
there are others in which the time and space complexity makes the use of
such algorithms infeasible. In these cases fast yet accurate approximations
are desired.
The talk will focus on variational algorithms:
a powerful tool for efficient approximate inference
that offers guarantees in the form of a lower bound on the marginal
probabilities.
This family of approaches aims to minimize the KL distance between a
distribution Q and the target distribution P
by finding the best distribution Q from some
family of distributions for which inference is feasible.
We developed a novel algorithm, called VIP*, for structured variational
approximate inference. The development of the algorithm has been motivated
by challenges posed by genetic linkage analysis.
This algorithm extends known algorithms to allow efficient multiple
potential updates for overlapping clusters,
and overcomes the difficulties imposed by deterministic constraints, and its
applicability is demonstrated for genetic linkage analysis.