One of the common trends in machine learning has been an emphasis on the use of unlabeled data. The argument goes something like “there aren’t many labeled web pages out there, but there are a huge number of web pages, so we must find a way to take advantage of them.” There are several standard approaches for doing this:
- Unsupervised Learning. You use only unlabeled data. In a typical application, you cluster the data and hope that the clusters somehow correspond to what you care about.
- Semisupervised Learning. You use both unlabeled and labeled data to build a predictor. The unlabeled data influences the learned predictor in some way.
- Active Learning. You have unlabeled data and access to a labeling oracle. You interactively choose which examples to label so as to optimize prediction accuracy.
It seems there is a fourth approach worth serious investigation—automated labeling. The approach goes as follows:
- Identify some subset of observed values to predict from the others.
- Build a predictor.
- Use the output of the predictor to define a new prediction problem.
- Repeat…
Examples of this sort seem to come up in robotics very naturally. An extreme version of this is:
- Predict nearby things given touch sensor output.
- Predict medium distance things given the nearby predictor.
- Predict far distance things given the medium distance predictor.
Some of the participants in the LAGR project are using this approach.
A less extreme version was the DARPA grand challenge winner where the output of a laser range finder was used to form a road-or-not predictor for a camera image.
These automated labeling techniques transform an unsupervised learning problem into a supervised learning problem, which has huge implications: we understand supervised learning much better and can bring to bear a host of techniques.
The set of work on automated labeling is sketchy—right now it is mostly just an observed-as-useful technique for which we have no general understanding. Some relevant bits of algorithm and theory are:
- Reinforcement learning to classification reductions which convert rewards into labels.
- Cotraining which considers a setting containing multiple data sources. When predictors using different data sources agree on unlabeled data, an inferred label is automatically created.
It’s easy to imagine that undiscovered algorithms and theory exist to guide and use this empirically useful technique.
Ando and Zhang‘s work links 2 to 4, I think.
This self-training model is a very active research area in robotics. In fact, it’s a crucial part of some of the projects I’m working on right now. One of the best examples I’ve seen is:
C. Wellington and A. Stentz, “Online Adaptive Rough-Terrain Navigation in Vegetation”, IEEE International Conference on Robotics and Automation (ICRA), 2004.
(and related work, 2002-2005) where supporting surfaces predictions are learned online by vehicle traversal.
The UT Austin Intelligent Robotics Lab calls approaches like this Bootstrap Learning. The work that best matches the description above is probably Kuipers & Beeson “Bootstrap Learning for Place Recognition” (AAAI-2002). There the robot uses physical exploration and abduction to define place labels for sensor images; it then uses those labels to train a classifier to recognize the place directly from the image.
Here is a good survey of the lab’s bootstrap learning work.
The Ando and Zhang idea seems to be (roughly) creating a bunch of learning problems on the unlabeled or semisupervised data and then solving them with a shared representation that is hopefully useful for the original problem.
The applications in robotics seem very compelling because the sensory streams break down very nicely into internal sensors/touch sensors/near sensors (stereo vision or laser range finder)/far sensors (like vision). This means that a particularly compelling sequence of prediction problems exists. I don’t see the same yet for language.
I’m a newbie in Active Learning. Many thanks for any correction. I understand that:
Actually, I’m struggling to the problem of efficiently forming static test collections to compare multiple retrieval systems as in TREC context. We would like to obtain a function which can sort documents by their necessity to be labeled (more precisely only relevant documents are meaningful). This is an ill-posed problem, the feasible candidate set is quite huge and especially because there’s no clear definition of a right result of retrieval system comparison.
I don’t know if it is perspective to formulate this task as a particular problem of Active Learning or of Optimal Experimental Designing, or it is merely a meta-search task.
The answer might be “yes it’s active learning”. In a vision domain, Yoav Freund used active learning for object recognition. Whether or not this approach could be applied to TREC isn’t clear to me given the details, but you might want to read carefully and think about it.