Who: Nina Balcan
Where: NSH 1507
When: 2008-01-22 Noon
Title: A Theory of Similarity Functions for Learning and Clustering
Kernel methods have proven to be extremely powerful tools in machine learning. They perform well in many applications, and there is also a well-developed theory of sufficient conditions for a kernel to be useful for a given learning problem. However, while a kernel can be thought of as just a pairwise similarity function that satisfies additional mathematical properties, this theory requires viewing kernels as implicit (and often difficult to characterize) maps into high-dimensional spaces. In this work we develop an alternative theory of learning with more general similarity functions, which requires neither reference to implicit spaces, nor the function to be positive semi-definite. Our results strictly generalize the standard theory, and any good kernel function under the usual definition can be shown to also be a good similarity function under our definition.
We then show how our framework can also be applied to clustering: multi-way classification from purely unlabeled data. In particular, using this perspective we develop a new model that directly addresses the fundamental question of what kind of information a clustering algorithm needs in order to produce a highly accurate partition of the data. Our work can be viewed as an approach to defining a PAC model for clustering with non-interactive feedback.
This talk is based on work joint with Avrim Blum and Santosh Vempala.