Clustering and efficient use of unlabeled examples
Efficient learning with partially labeled data involves extracting structure from large unlabeled set and combining this information with limited labeled examples. A typical albeit unstated assumption in this context associates separable clusters in the unlabeled set with unique but unknown labels. When this assumption is valid, labeled examples are needed only to the extent that they can facilitate labeling of the clusters. We capture and formalize this intuition in a conditional probability model where soft clusters serve to regularize the labeling of the unlabeled examples. Clustering is achieved by defining a Markov diffusion process (cf. Tishby and Slonim, NIPS 2000). The associated time scale of this process determines the effective size of the clusters and is chosen through a margin based criterion that guarantees unambiguous classification of examples. We relate the time scale to the mixing time of the Markov process and extend the basic idea by combining multiple time scales to maximize classification accuracy. We demonstrate the performance of the approach on both real and synthetic datasets. 1 Representation based on Markov diffusion To achieve good learning performance, the data must be encoded in a suitable representation matched to the learning algorithm. Typically, we are provided data points in a space, and a distance metric that measures pairwise similarity between points. The provided distance metric is often quite accurate locally, as it is relatively easy to characterize small perturbations in the data. However, over larger distances, the given metric is frequently inadequate, and hurts the performance of the many learning algorithms that rely on global distances. Fortunately, in problems with many data points (with or without labels), we can use the locally accurate metric to construct an improved global distance measure that reflects the density of the data. For example, the data may lie on a submanifold of the space, revealed by the density, and we should measure distances along the manifold. Intuitively, the distances are smaller in directions of high density, and larger in low-density directions. We define a Markov diffusion process based on the locally accurate metric. The local metric defines probabilities of transitioning between two nearby points in one timestep, and we construct the global distance as the probability of transitioning between two points in t timesteps. Thus, we consider all the paths of length t on this graph. Formally, consider a set of points fx1; : : : ;xNg that need not be labeled. Construct a graph whose nodes correspond to data points, and whose undirected edges correspond to one step transitions. We only allow such immediate transitions from a point to its neighbors. Specifically, for each point, connect it with an undirected edge to its K nearest neighbors. Points in high density centers can be neighbors of many points and end up with more than K edges. Self-transitions back to the point itself are also included. Let the probability of transitioning from a state i at time t to a neighbor k at time t+ 1 be