Can SVM do stream learning one example at a time?

Question

I have a streaming data set, examples are available one at a time. I would need to do multi class classification on them. As soon as I fed a training example to the learning process, I have to discard the example. Concurrently, I'm also using the latest model to perform prediction on unlabelled data.

As far as I know, a neural network is able to do stream learning by feeding examples one at a time and performing forward propagation and backward propogation on the example.

Can a SVM perform stream learning one example at a time and discard the example straight away?

Answer 1

The streaming setting in machine learning is called "online learning". There is no exact support vector machine in the online setting (since the definition of the objective function is inherently for the batch setting). Probably the most straightforward generalization of the SVM to the online setting are passive-aggressive algorithms. Code is here http://webee.technion.ac.il/people/koby/code-index.html and an associated paper is here http://eprints.pascal-network.org/archive/00002147/01/CrammerDeKeShSi06.pdf

The basic idea is that one recieves data as $(\mathbf{x},y)\in\mathbb{R}^d\times [k]$ pairs with query points $\mathbf{x}\in \mathbb{R}$ where $k$ is the number of labels. The algorithm maintains a weight matrix $W_t\in \mathbb{R}^{k\times d}$ at iteration $t$ the algorithms recieves a data point $\mathbf{x}_t$ and then gives predicted scores $\hat{\mathbf{y}}_t=W\mathbf{x}_t$ for each of the labels and it predicts the highest scoring label as the true label. If the prediction is wrong then the algorithm makes the smallest change to $W_t$ such that it will avoid that mistake in the future. Smallest change is here defined in terms of the Frobenius norm.

Answer 2

I've always found the implicit updates framework (that includes the passive-aggressive algorithms mentioned in another answer here) to be unnecessarily more complex than the explicit updates framework (not to mention that implicit updates can be much slower than the explicit ones unless a closed-form solution for implicit update is available).

Online Importance Weight Aware Updates is an example of a state-of-the-art explicit update algorithm which is simpler, faster, and more flexible (supporting multiple loss functions, multiple penalties, cost-sensitive learning etc.) than its implicit counterparts. The paper deals with linear models only though (linear svm corresponds to the case of hinge loss function with quadratic penalty)

Since you need multi-class classification, one approach is to use the "reductions" functionality of vowpal wabbit (built on the top of the approach from the paper) which is not documented well unfortunately.

Answer 3

LASVM is one of the most popular online learning variants of the SVM.

Linear SVMs can also be trained using stochastic gradient descent, just like any linear model.

Answer 4

Please refer to paper SVM Incremental Learning, Adaptation, and Optimization, which proposed an online SVM for binary classification.

The code of above paper can be found here. In the code, two ways of online training are introduced:

1. train the SVM incrementally on one example at a time by calling svmtrain(), and
2. perform batch training, incrementing all the training examples into the solution simultaneously by calling svmtrain2().

Back to your question, the answer is obviously YES for stream learning one example at a time. And the code can also handle unlearn (discard) a example, i.e. exact and approximate leave-one-out (LOO) error estimation - the exact LOO error estimate can be efficiently computed by exactly unlearning one example at a time and testing the classifier on the example.

Answer 5

Online Learning with Kernels discusses online learning in general kernel settings.

Excerpt from the abstract -

"Kernel based algorithms such as support vector machines have achieved considerable success in various problems in the batch setting where all of the training data is available in advance. Support vector machines combine the so-called kernel trick with the large margin idea. There has been little use of these methods in an online setting suitable for real-time applications. In this paper we consider online learning in a Reproducing Kernel Hilbert Space. By considering classical stochastic gradient descent within a feature space, and the use of some straight-forward tricks, we develop simple and computationally efficient algorithms for a wide range of problems such as classification, regression, and novelty detection."