# Online supervised learning algorithm

I have labeled examples coming in on the fly, thus I need to create a classifier from sequential data instead of a static example set. Incoming data is fully labeled, there are no unlabeled examples. Each incoming example has a number of features.

E.g. let X by an incoming example with 3 features

X := (day = sunday, weather = sunny, season = summer, label = go to the beach)


I want to incrementally train a classifier such that whenever I see the next occurance of (sunday, sunny, summer) I want the classifier to suggest going to the beach.

Due to memory restrictions I am unable to keep the entire set of training examples.

Can you point me to adequate online/incremental learning algorithms for such a particular problem?

• How many dimensions? i.e., how many features are there? Also, how many classes are there? (i.e., how many possible labels?) What research/self-study have you done, and what resources have you read? Have you looked at en.wikipedia.org/wiki/Online_machine_learning? – D.W. Apr 6 '15 at 16:12
• So far I only have knowledge of offline learning algorithms, especially Decision Trees. I cannot predict how many features we're going to have, let alone enumerate the number of classes. I was under the impression that there was some general purpose approach to online learning (of course with some drawbacks). Infact I did look at the Wiki article prior posting the question - but somewhere I read that one could adapt offline methods such as a Naive Bayes for usage in online scenarios. Is this feasable at all? – nfusion Apr 7 '15 at 10:52

Wikipedia has an overview of online machine learning; I suggest you start there and then look at some of the references linked there, and take a trip to your library to check out some books.

One approach is to use learning algorithms that allow you to iteratively update the learned model, as you receive each training point.

Another approach might be to use an ensemble classifier: you learn multiple weak classifiers, each of which outputs its own prediction at the label, and then to classify any point you run all of the weak classifiers and you take a majority vote of their predictions.

One simplistic method would be to periodically train a new weak classifier and add it to your ensemble. For instance, suppose you have storage for $n$ points. You could add each point to storage as you receive it, then when your storage gets full, train a weak classifier on all $n$ of those points, add it to the ensemble, and clear out your storage.

It might be better to bias your storage strategy towards remembering points that you have classified wrong. For instance, as a simple example, you could reserve $n/3$ storage slots for remembering past points that were misclassified and $2/3$ storage slots for storing the last $2n/3$ points you received. When the latter gets full, you could train a new weak classifier on all of those $n$ points, add it to the ensemble, then classify all $n$ of those points with the ensemble classifier, discard all the ones that were correctly classified by the ensemble classifier, and keep a random sample of size $n/3$ chosen from the remaining points (moving them into the $n/3$ slots for misclassified points and emptying out the $2n/3$ slots for new points).

Finally, you might also be able to adapt boosting methods to an online setting. Boosting methods assign a weight to each training point; the higher the weight, the harder the weak classifier tries to classify that point correctly (i.e., the greater the penalty for misclassifying that point). The idea is that points which have been classified wrong in the past will receive a higher weight, and so future weak classifiers will be biased towards trying to classify those points correctly. Rather than trying to store all training points you've ever seen, I could imagine trying to store a random sample of the training points, where each point is selected with probability proportional to its weight. Thus, you could store $n$ training points and their weights; after you train each new weak classifier, you can update the weights of all $n$ remembered points and then sample $n/2$ of them (say, the $n/2$ with highest weights, or take a random sample with distribution given by the weights).

I don't know how well these methods would work, but you could give them a try in your setting and see. But start by exploring the literature. You know what they say: a week in the computer lab can save you a day in the library.