Curriculum Learning

Most machine learning algorithms look at their training data all at once. However, human usually learn in a different, more organized way. We start with simple cases, concepts, or skills, and then gradually increase the difficulty level of the learning. Can this learning strategy also apply to machines? This is what the ICML-09 paper "Curriculum Learning" tries to address. In their three experiments on toy classification problems, shape recognition and language modeling, curriculum learning was shown to be both faster and more accurate than learning without curriculum. Some important questions regarding curriculum learning are discussed but remain largely open. First of all, why does curriculum learning help (or in some cases, doesn't help)? One speculation is that at the beginning of learning, difficult samples can confuse the learner instead of help. A related question is, how shall we find, either for a specific problem or in general, a good curriculum? In their experiments they used some quite intuitive curriculum; but an intuitive curriculum doesn't always help (for example, see Hal Daume's comment on this paper in his blog).

Discretization for naive Bayes

When using naive Bayes, quantitative attributes are usually discretized (binning). Two simple ways of discretization are partitioning the data into k intervals of equal width, or into k intervals so each contains equal number of data points. There are also supervised methods, like the one used in Weka discretizer, which recursively selects the cut-point based on information gain (just like in some decision tree construction algorithms). In the paper "Discretization for naive-Bayes learning: managing discretization bias and variance" (MLJ, Jan 09), the authors find out that, increasing the number of intervals helps reduce the bias of the learned NB classifier, while the number of data points within each interval (called "interval frequency") shall be large enough to reduce the variance of the learned classifier. Therefore, when we have a fixed size of training data, there's a trade-off between the interval number and frequency. Based on this observation they propose two novel discretization methods. "Proportional discretization" requires the interval number and frequency to be the same; "fixed frequency discretization" simply fixes the interval frequency to a sufficiently large value. Their experiments showed that these two methods outperformed existing discretization techniques.

Learning to select features

Effective feature selection can be computationally expensive when the feature number is large; and in some cases feature values are expensive to get, so we don't want to examine every feature with the traditional feature selection methods (see budgeted learning). This paper, "Learning to Select Features using their Properties" (JMLR 08), proposes a simple idea to such problems, that they learn to predict good features based on a set of meta-features. Here meta-features are a set of properties of the features. For example, in object recognition people sometimes use the presence of a set of prototype patterns as features, then the meta-features could be the statistics of such prototype patterns. So in their method, they first evaluate only a subset of features using traditional feature selection methods, and then use the result to train a predictor that can be used to select unmeasured features. In their experiments they show their method achieved classification accuracy similar to the traditional methods but was much faster. Unfortunately meta-features have to be specified manually, but nevertheless in many cases it's much more obvious than selecting features.

Learn to filter spam

Almost everyday we receive lots of spam emails. Training classifiers to filter spam is one of the most successful real-life applications of machine learning. But spammers are getting smart to counteract spam filters! One trick they use is good word attack. By inserting a set of words that often appear in legitimate messages but not in spams, they make spams look legitimate and confuse the filters (increasing false negative). Even worse, when end users label such emails as spams, adaptive spam filters will learn from these new training samples, and may associate those good words with spam (increasing false positive). These days we do sometimes receive such emails, don't we?

So this paper, "A Multiple Instance Learning Strategy for Combating Good Word Attacks on Spam Filters" (JMLR Jun 08), proposed to use multi-instance learning for spam filters. Multi-instance learning learns from and makes predictions on bags of instances, instead of individual instances. If at least one of the instances in a bag is positive, then the bag is positive; otherwise, the bag is negative. Let a bag be an email, and an instance be a part of the email. You see this is a perfect match for good word attack. Now I'm wondering what spammers will do next....