Speaker
Hakon Tjelmeland
(NTNU)
Description
In the presentation we propose computationally feasible
approximations to binary Markov random fields. The basis of
the approximation is the forward-backward algorithm. This
exact algorithm is computationally feasible only for fields
defined on small graphs. The forward part of the algorithm
computes a series of joint marginal distributions by
summing out each variable in turn. We construct an
approximate forward-backward algorithm by adapting
approximation results for pseudo-Boolean functions. By
using an approximation of the energy function which
minimises the error sum of squares we construct a forward-
backward algorithm which is computationally viable. We also
show how our approach gives us upper and lower bounds as
well as an approximate Viterbi algorithm. Through examples
we demonstrate the accuracy and flexibility of our
approximate algorithm.