A Theory of Similarity Functions for Learning and Clustering

Machine Learning has become a highly successful discipline with
applications in many different areas of Computer Science. A critical advance that has spurred this success has been the development of learning methods using a special type of similarity functions known as kernel functions. These methods have proven very useful in practice for dealing with many different kinds of data and they also have a solid theoretical
foundation. However, it was not previously known whether the benefits of kernels can be realized by more general similarity functions. In our work, we develop a theory of learning with similarity functions that positively answers this question. Furthermore, our theory provides a new and much
simpler explanation for the effectiveness of kernel methods.

Technically speaking, the existing theory of kernel functions requires viewing them as implicit (and often difficult to characterize) mappings in high dimensional spaces. Our alternative framework instead views kernels directly as measures of similarity and it also generalizes the standard theory in important ways. Specifically, our notions of good similarity
functions can be described in terms of natural direct properties of the data, with no reference to implicit spaces, and no requirement that the similarity function be positive semi-definite (as in the standard theory).

We also show how our framework can be applied to Clustering: i.e., 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 provides the first framework for analyzing clustering accuracy without any strong probabilistic assumptions.
Maria-Florina Balcan is a Ph.D. candidate at Carnegie Mellon University under the supervision of Avrim Blum. She received B.S. and M.S. degrees from the Faculty of Mathematics, University of Bucharest, Romania. Her main research interests are Computational and Statistical Machine Learning, Computational Aspects in Economics and Game Theory, and Algorithms. She is a recipient of the IBM PhD Fellowship.