Return to Colloquia & Seminar listing
Combinatorial algorithms for the Markov Random Fields problem and implications for ranking, clustering, group decision making and image segmentation
Algebra & Discrete Mathematics| Speaker: | Dorit Hochbaum, University of California, Berkeley |
| Location: | 1147 MSB |
| Start time: | Thu, Mar 8 2012, 3:10PM |
Description
One of the classical optimization models for image segmentation is the
well known Markov Random Fields (MRF) model. The MRF problem involves
minimizing pairwise-separation and deviation terms. This model is
shown to be powerful in representing classical problems of ranking,
group decision making and clustering. The techniques presented are
stronger than continuous techniques using in image segmentation, such as
total variations, denoising, level sets and some classes of Mumford-Shah
functionals. Nevertheless the MRF has been little used in applications as
the perception was that it is hard (in terms of high complexity) to solve.
We introduce efficient flow-based algorithms for the convex MRF (and the
non-convex is shown to be NP-hard). In this talk we illustrate the power
of the MRF model and algorithms in the context of aggregate ranking.
The aggregate ranking problem is to obtain a ranking that is fair and
representative of the individual decision makers' rankings. We argue here
that using cardinal pairwise comparisons provides several advantages
over score-wise or ordinal models. The aggregate group ranking problem
is formalized as the MRF model and is linked to the inverse equal paths
problem. This new approach is shown to have advantages over PageRank
and the principal eigenvector methods.