UCL Logo




Politics, Preferences and Permutations: Probabilistic Reasoning with Rankings



Jonathan Huang

Ph.D. candidate in the School of Computer Science at Carnegie Mellon University where he also received a Masters degree in 2008.



Politics, Preferences and Permutations: Probabilistic Reasoning with Rankings



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.