We provide a principle for semi-supervised learning based on optimizing the rate of communicating labels for unlabeled points with side information. Theside information is expressed in terms of identities of sets of points or regions with the purpose of biasing the labels in each region to be the same. The resulting regularization objective is convex, has a unique solution, and the solution can be found with a pair of local propagation operationson graphs induced by the regions. We analyze the properties of the algorithm and demonstrate its performance on document classificationtasks.

We propose a "soft greedy" learning algorithm for building small conjunctions of simple threshold functions, called rays, defined on single real-valued attributes. We also propose a PAC-Bayes risk bound which is minimized for classifiers achieving a nontrivial tradeoff between sparsity (the number of rays used) and the magnitude ofthe separating margin of each ray. Finally, we test the soft greedy algorithm on four DNA micro-array data sets.

Statistical approaches to language learning typically focus on either short-range syntactic dependencies or long-range semantic dependencies between words. We present a generative model that uses both kinds of dependencies, and can be used to simultaneously find syntactic classes and semantic topics despite having no representation of syntax or semantics beyondstatistical dependency. This model is competitive on tasks like part-of-speech tagging and document classification with models that exclusively use short-and long-range dependencies respectively.

We relate the algorithm to the stochastic approximation literature.This enables us to specify conditions under which the algorithm is guaranteed to converge to the optimal solution (with probability 1).This includes necessary and sufficient conditions for the solution to be unbiased.

We present a novel approach to collaborative prediction, using low-norm instead of low-rank factorizations. The approach is inspired by, and has strong connections to, large-margin linear discrimination. We show how to learn low-norm factorizations by solving a semi-definite program, and discuss generalization error bounds for them.

Most existing tracking algorithms construct a representation of a target object prior to the tracking task starts, and utilize invariant features to handle appearance variation of the target caused by lighting, pose, and view angle change. In this paper, we present an efficient and effective onlinealgorithm that incrementally learns and adapts a low dimensional eigenspacerepresentation to reflect appearance changes of the target, thereby facilitating the tracking task. Furthermore, our incremental method correctly updates the sample mean and the eigenbasis, whereas existing incremental subspace update methods ignore the fact the sample mean varies over time. The tracking problem is formulated as a state inference problem within a Markov Chain Monte Carlo framework and a particle filter is incorporated for propagating sample distributions over time. Numerous experiments demonstrate the effectiveness of the proposed trackingalgorithm in indoor and outdoor environments where the target objects undergo large pose and lighting changes.

We propose a new method for clustering based on finding maximum margin hyperplanesthrough data. By reformulating the problem in terms of the implied equivalence relation matrix, we can pose the problem as a convex integer program. Although this still yields a difficult computational problem,the hard-clustering constraints can be relaxed to a soft-clustering formulation which can be feasibly solved with a semidefinite program.Since our clustering technique only depends on the data through the kernel matrix, we can easily achieve nonlinear clusterings in the same manner as spectral clustering. Experimental results show that our maximum margin clustering technique often obtains more accurate results than conventional clustering methods. The real benefit of our approach, however,is that it leads naturally to a semi-supervised training method for support vector machines. By maximizing the margin simultaneously onlabeled and unlabeled training data, we achieve state of the art performance by using a single, integrated learning principle.

We present a probabilistic approach to learning a Gaussian Process classifier in the presence of unlabeled data. Our approach involves a "null category noise model" (NCNM) inspired by ordered categorical noisemodels. The noise model reflects an assumption that the data density is lower between the class-conditional densities. We illustrate our approach on a toy problem and present comparative resultsfor the semi-supervised classification of handwritten digits.

We present an unsupervised algorithm for registering 3D surface scans of an object undergoing significant deformations. Our algorithm does not need markers, nor does it assume prior knowledge about object shape, the dynamics of its deformation, or scan alignment.

We describe a way of using multiple different types of similarity relationship tolearn a low-dimensional embedding of a dataset. Our method chooses different, possibly overlapping representations of similarity by individually reweighting the dimensions of a common underlying latent space. When applied to a single similarity relation that is based on Euclidean distancesbetween the input data points, the method reduces to simple dimensionality reduction. If additional information is available about the dataset or about subsets of it, we can use this information to clean up or otherwise improve the embedding. We demonstrate the potential usefulnessof this form of semi-supervised dimensionality reduction on some simple examples.