Abstract:

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.