Abstract

Permutations arise fundamentally in a plethora of real world applications from multi-person tracking to preference ranking and election analysis. Real world data, often being noisy and incomplete, necessitates a probabilistic approach to learning and reasoning with permutations. However, representing arbitrary probability distributions over the space of permutations has been notoriously intractable due to the factorial number of permutations.

In this talk, I will present methods for efficiently representing and reasoning with such distributions. The main idea that I set forth is that distributions over permutations can be decomposed additively or multiplicatively into a series of simpler functions which can be dealt with more easily. As I show, additive decompositions turn out to correspond to generalized Fourier analysis on the symmetric groups, while multiplicative decompositions correspond to a generalized notion of probabilistic independence. Along the way, I will discuss applications of these methods for statistically analyzing political elections in Ireland, preference surveys for sushi, as well as for performing multi-person tracking using a networked array of cameras.

Biography: Jonathan Huang is a Ph.D. candidate in the School of Computer Science at Carnegie Mellon University where he also received a Masters degree in 2008. He received his B.S. degree in Mathematics from Stanford University in 2005. His research interests lie primarily in statistical machine learning and for his dissertation, he has developed efficient statistical techniques for modeling and performing inference with combinatorial objects such as permutations and rankings. His research has resulted in a number of publications in premier machine learning conferences and journals, receiving a paper award in NIPS 2007 for his work on applying group theoretic Fourier analysis to probabilistic reasoning with permutations.