Unsupervised and Semi-Supervised Learning

In collaboration with Ben Recht.

Learning Is Supposed to Save Us Time

When it comes to building image recognition systems, classifiers, trackers, spam filters, or anything else intelligent, we can choose from two extremes:

  • Carefully build a model that relates observables to the entity to estimate, and use standard inference techniques. This makes sense if good models are available, and inference with them is easy.
  • Make few modeling assumptions, and train the system using lots of training data. This makes sense if training data is cheap and design time is expensive. If the cost of spending one week designing a better model and inferene technique is the same as the cost spending one hour collecting data, then hybrids between these two techniques don't save us any additional effort.

    Unsupervised and semisupervised techniques appear to totally break this trend because they consume training data that is typically very easy to get.

    Semisupervised Learning for Tracking

    Our approach for building semisupervised algorithm is general: we regularize the output of standard regression techniques with a small amount of domain knowledge. This automatically allows the training algorithm to take advantage of unlabeled data. Using this methodology, we built an algorithm that learns to transform time series from a few examples.

    Semisupervised learning lets us solve some very difficult tracking problem. We can learn visual trackers using lots of unlabeled images that have no annotation whatsoever and a few examples that show how to map pixels in an image to the pose of an object of interest,

    Here is an example input video of Ben flailing his hands. For a few frames, we specified the position of his joints. From these examples and 2 minutes of unlabeled frames, the algorithm learned a function that took as input an image, and returned the position of Ben's shoulders, elbows, and hands. This video compares simple regression (black marketers) with semi-supervised regression (white markers).

    Specified examples

    Keyframes for lip tracking

    We have also applied the algorithm to the problem of tracking lips. The algorithm learns a mapping from images of my face to a spline contour. See the video(1.1Mb) for an example. To train the system, we used the 7 keyframes shown above.

    The technique is general. Below, the system learns how to track RFID tags from signal strengths harvested from antennas. Four examples provide the mapping from signal strength to position. In addition, 5 minutes of unlabeled signal strength data is also provided.

    The following publications describe this work in more detail.

  • Learning to Transform Time Series with a Few Examples, Ali Rahimi, Ben Recht, in Pattern Analysis and Machine Intelligence (PAMI) 2007 (to appear). (pdf)
  • Learning to Transform Time Series with a Few Examples, Ali Rahimi, PhD Thesis. (pdf)
  • Learning Appearance Manifolds from Video, Ali Rahimi, Ben Recht, Trevor Darrell, CVPR 2005. (pdf)

    Unsupervised Learning and Nonlinear System Identification

    Sometimes, we don't even need labeled examples! In many settings, to learn to track, it suffices to know that the target moves smoothly over time, and that the sensor report a smooth function of the target's state. Unlabeled data provides almost all the rest of the information (we can learn to recover the pose of the target up to a coordinate transform).

    The sensetable probelm above for example, can be solved without any labeled examples whatsoever.
    The trajectory of the RFID tag can be recovered up to a scale and rotation from just signal strength information (no labeled data). Once the mapping from signal strength to psoe is learned, we can use it to track the tag in real-time.

    This phenomenon is well known in a simpler form in the control theory literature, where linear system identification has been used for decades to learn the parameters of linear dynamical systems.

    In tracking, however, the relationship between pose and measurements is nonlinear. So we have been tackling the problem of nonlinear system identification, a notoriously difficult unsupervised learning problem due to the local minima problem. In this setting, the problem is more closely related to manifold learning.

    We have devised algorithms that can provably avoid these local minima in certain situations (the observation function must be observable and smooth, and the dynamics must be known apriori). This work is described here:

  • Estimating Observation Functions in Dynamical Systems using Unsupervised Regression, Ali Rahimi, Ben Recht,
    in Neural Information Processing Systems (NIPS) 2006. (pdf,,poster,slides)

    Interpretations of Normalized Cuts

    In these papers, we provide a geometric interpretation for the popular Normalized Cuts clustering algorithm. We show that Normalized Cuts lifts the data to an infinite-dimensional feature space, and splits it into two clusters using a hyperplane. We also show that this procedure is a relaxation of the Transductive SVMs problem, which is NP-hard.

  • Clustering with Normalized Cuts is Clustering with a Hyperplane, A. Rahimi, B. Recht, in Statistical Learning in Computer Vision (2004) (pdf).
  • Normalized Cuts is a Relaxation of Margin-Based Clustering, A. Rahimi, B. Recht, under revision.