UC Davis Mathematics

Mathematics Colloquia and Seminars

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

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.