Monday, November 26, 2007 4:00 PM 5130 Upson Hall 
Theory Seminar Fall 2007 CS 789 


MariaFlorina Balcan 

A Theory of Similarity Functions for Learning and Clustering 

Kernel methods have proven to be powerful tools in machine learning. They perform well in many applications, and there is also a welldeveloped 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 highdimensional spaces. In this work we develop an alternative theory of learning with similarity functions more generally that does not require reference to implicit spaces, and does not require the function to be positive semidefinite. Our results 