Active learning algorithms are producing substantial savings in label complexity over passive learning approaches.
If your email address has ever landed on a spammer’s list, you know what it’s like for your inbox to be flooded with junk email day after day after day. To prevent this, spam filters were created, relying on a mixture of brute force computing with passive learning and refined processing with active learning. And while spam filters have become more sophisticated and your inbox is increasingly free of junk email, the theory behind active learning has lagged. In the last few years, however, the field has taken off.
PhotograPh courtesy of steVe hanneke
“There’s been surprisingly rapid progress,” says Steve Hanneke, a Ph.D. student at Carnegie Mellon University. “If you look back five years, there was really very little known about what makes something an informative example, how important are they, and how much improvement we can expect. But we now have in the published literature a pretty clear picture of just how much improvement we can expect in active learning and what we mean by an informative example.”
The difference between passive learning and active learning is about the teacher, and how much time the teacher wants to spend teaching. Pas-
sive learning requires large data sets, and the teacher has to label countless examples for the learner. Once every example is labeled, the data set is given to the learner, which then finds patterns that will allow it to sort future
data correctly.
The obvious drawback is that passive learning requires a lot of time, and that’s where active learning enters the picture.
In active learning, all of the examples are provided to the learner unlabeled. An algorithm analyses the unlabeled data set, and asks the teacher for labels. After the algorithm determines the basic shape of each label set, it asks the teacher to define the ambiguous examples in-between the various labels. By labeling only the most informative examples, the hope is that fewer labels
At carnegie mellon, Steve hanneke’s new work has the benefit of using established passive learning, alongside active learning with its guaranteed improvements, on the number of labels needed.
APriL 2009 | voL. 52 | no. 4 | communicAtionS of the Acm
11
References:
Archives