Techniques for incremental online learning of classifier on stream data

Question

Which may be good techniques to face this abstract problem?

You have a data stream of a continuous signal, as one from a physical sensor. That signal has real (discretized) values, no attribute; addictional features (e.g., power, auto-correlation, entropy) might be extracted. You can assign one label from a finite set to a window of the signal. Let this label be a training label. You have to choise start and end points of the window as well as the window label.

The task is to classify next windows online, as just as the signal is received.

I am asking for an incremental algorithm, in the sense that it should increase its detection performance given more training labels. But it must be able to classify even after only one training label.

If the problem turns out to be too hard because of windows-boundaries detection, let's say you can fix their size at a small constant. Thus the algorithm classifies little slices of the signal and then it merges adjacent ones with same labels. If you use that simplified approach, please justify why it is reasonable.

Answer 1

If this is a binary classification problem then it should be possible to apply an online SVM such as Bordes, A. and Bottou, L., "The Huller: a simple and efficient online SVM", ECML 2005.

If this is a non-binary classification (i.e. more than 2 possible labels) you could look into kernel recursive least-squares techniques. They are made for online regression, but they perform pretty well for online classification too. Here's one basic KRLS algorithm: Y. Engel, S. Mannor and R. Meir, "The Kernel Recusrive Least Squares Algorithm", IEEE Trans. Signal Processing, 2004.

Both of these approaches will require fixed window-sizes in order to compare input vectors of the same size.