ORIE Colloquium on 12/4/2012 - Dorit Hochbaum: Combinatorial Algorithms for the Markov Random Fields Problem and Implications for Ranking, Clustering, Group Decision Making and Image Segmentation

ORIE Colloquium: Dorit Hochbaum (UC Berkeley) - Combinatorial algorithms for the Markov Random Fields problem and implications for ranking, clustering, group decision making and image segmentation Tuesday, December 4, 2012 at 12:00pm Frank H. T. Rhodes Hall, 253 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 singleton-deviation terms. This model is shown here to be powerful in representing classical problems of ranking, group decision making and clustering. The techniques presented are stronger than continuous techniques used in image segmentation, such as total variations, de-noising, level sets and some classes of Mumford-Shah functionals. This is manifested both in terms of running time and in terms of quality of solution for the prescribed optimization problem We present the first known efficient and flow-based, algorithms for the convex MRF (the non-convex is shown to be NP-hard). We then discuss 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 combinatorial approach is shown to have advantages over other pairwise-based methods for ranking, such as PageRank and the principal eigenvector technique.