AIC Seminar: Algebraic Approaches for Reasoning in Very Noisy Multi-Target Tracking Problems
Abstract
Probabilistic reasoning and learning with permutation data arises as a fundamental problem in myriad applications such as modeling preference rankings over objects (such as webpages), tracking multiple moving objects, reconstructing the temporal ordering of events from multiple imperfect accounts, and more. Since the number of permutations scales factorially with the number of objects being ranked or tracked; however, it is not feasible to represent and reason with arbitrary probability distributions on permutations. Consequently, many approaches to probabilistic reasoning problems on the group of permutations have been either ad hoc, unscalable, and/or relied on rigid and unrealistic assumptions. For example, common factorized probability distribution representations, such as graphical models, are inefficient due to the mutual exclusivity constraints that are typically associated with permutations.
In this talk, I'll talk about an algebraic approach which we have developed to combat this combinatorial explosion and its implications for multi-target tracking. Our approach is based on the idea of projecting a distribution onto a group theoretic generalization of the Fourier basis. I'll discuss how the probabilistic decomposition leads to compact representations for distributions over permutations and that one can formulate efficient probabilistic inference algorithms by taking advantage of the combinatorial structure of the Fourier representation.
From the theoretical side, I'll address a number of problems in understanding the consequences of these Fourier based approximations. For example, I will present results which illuminate the nature of error propagation in the Fourier domain and propose methods for mitigating their effects.
Finally, time permitting, I will touch on other exciting applications of probabilistic reasoning with permutations including the staging of Alzheimer's diseases and modeling student behavior in a massive scale online course.
About Jonathan Huang
Jonathan Huang is an NSF Computing Innovation (CI) postdoctoral fellow at the geometric computing group at Stanford University. He completed his Ph.D. in 2011 with 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 reasoning with combinatorially structured data. 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.
Event hosted by Hung Bui.
