Online supervised learning algorithm

Question

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?