Distance measures as prior probabilities
Thomas P. Minka · 2000
Many learning algorithms, especially nonparametric ones, use distance measures as a source of prior knowledge about the domain. This paper shows how the work of Baxter and Yianilos provides a formal equivalence between distance measures and prior probability distributions in Bayesian inference. The prior distribution applies either to how the data was generated or to the shape of the discrimination boundary. This perspective is useful for extending distance-based algorithms to new feature spaces and especially for learning distance measures on those spaces. 1 The canonical distance measure The canonical distance measure (CDM), developed by Baxter (1995; 1997) and further generalized here, provides the link explored in this paper between distance measures and prior probability distributions. Other links are possible but not emphasized here. Baxter developed the CDM in the context of “learning how to learn, ” where there are a series of related tasks that need to be solved. This paper shows that the CDM can be applied in a wider variety of situations, such as when there is only one task to solve. But Baxter’s perspective is still the simplest way to understand and derive the CDM, so the paper starts by reviewing his derivation. Baxter focused on function approximation, which is a perfectly general scenario but may be confusing for those interested in classification. Therefore this section reinterprets Baxter’s argument in the form of a thought experiment about building a classifier. What is useful about this thought experiment is that it forces us to convert a prior probability distribution on tasks into a distance measure for nearest-neighbor classification. The solution to the thought experiment necessarily provides a bridge between priors and distances. The problem: You’ve started a company called “Classifiers R Us ” and you’ve been hired to write a program for 1-nearest-neighbor classification. As you are trying to determine what distance measure to use, your client reveals that the program will always be run on one of 100 classification tasks, where the true classifications are known. Each task uses the same measurement space, say the physical attributes of a person, but one task is about determining gender while another is about determining occupation. Of course, the program gets none of this information: it only gets a set of vectors