February 25, 2014, 4:00pm
Marina Meila, Department of Statistics, UW.
Optimization for Ordered Data
This talk is concerned with summarizing — by means of statistical models — of data that expresses preferences. This data is typically a set of rankings of n items by a panel of experts; the simplest summary is the “consensus ranking”, or the “centroid” of the set of rankings.
I will describe how combinatorics, algorithms and statistics come together in this endeavor. At the center of the results is the _code_ of a permutation. This natural mathematical way to represent a permutation is key both to fast computing and to better understanding the models we create. The models have permutations _as parameters_ and fitting them to data leads to combinatorial optimization problems which are often NP-hard. The talk will introduce a class of algorithms to attack these problems, that are exact but intractable in the worst case, and will demonstrate that they are effective on real-world examples.
Joint work with Alnur Ali, Raman Arora, Le Bao, Jeff Bilmes, Harr Chen, Bhushan Mandhani, Chris Meek, Brendan Murphy, Kapil Phadnis, Arthur Patterson.