What is one class SVM and how does it work?

Question

I was using one class SVM, implemented in scikit-learn, for my research work. But I have no good understanding of this.

Can anyone please give a simple, good explanation of one class SVM?

Answer 1

The problem addressed by One Class SVM, as the documentation says, is novelty detection. The original paper describing how to use SVMs for this task is "Support Vector Method for Novelty Detection".

The idea of novelty detection is to detect rare events, i.e. events that happen rarely, and hence, of which you have very little samples. The problem is then, that the usual way of training a classifier will not work.

So how do you decide what a novel pattern is?. Many approaches are based on the estimation of the density of probability for the data. Novelty corresponds to those samples where the density of probability is "very low". How low depends on the application.

Now, SVMs are max-margin methods, i.e. they do not model a probability distribution. Here the idea is to find a function that is positive for regions with high density of points, and negative for small densities.

The gritty details are given in the paper. ;) If you really intend to go through the paper, make sure that you first understand the settings of the basic SVM algorithm for classification. It will make much easier to understand the bounds and the motivation the algorithm.

Answer 2

I will assume you understand how a standard SVM works. To summarise, it separates two classes using a hyperplane with the largest possible margin.

One-Class SVM is similar, but instead of using a hyperplane to separate two classes of instances, it uses a hypersphere to encompass all of the instances. Now think of the "margin" as referring to the outside of the hypersphere -- so by "the largest possible margin", we mean "the smallest possible hypersphere".

That's about it. Note the following facts, true of SVM, still apply to One-Class SVM:

• If we insist that there are no margin violations, by seeking the smallest hypersphere, the margin will end up touching a small number of instances. These are the "support vectors", and they fully determine the model. As long as they are within the hypersphere, all of the other instances can be changed without affecting the model.

• We can allow for some margin violations if we don't want the model to be too sensitive to noise.

• We can do this in the original space, or in an enlarged feature space (implicitly, using the kernel trick), which can result in a boundary with a complex shape in the original space.

Note: this is my account of the model as described here. I believe this is the version of One-Class SVM proposed by Tax and Duin. There are other approaches, such as that of Schölkopf et al, which is similar, but instead of using a small hypersphere, it uses a hyperplane which is far from the origin; this is the version implemented by LIBSVM and thus scikit-learn.

Answer 3

1. Traditional SVM

• Project point to higher dimensional space to separate two classes (initially inseparable in lower dimensional space)
• Find support vectors (on the edge of each class in feature space)
• Allow some soft margin for some points to lie in the region between support vectors (this is to avoid over-fitting)
• Final objective is to maximise the margin

2. One class SVM

a. According to Schölkopf et al.

• Project point to a higher dimensional space
• Separate all the data points from the origin in the feature space using hyper-plane
• Unlike traditional svm where we use soft margin for smoothness, we use a parameter that fixes fraction of outliers in the data
• maximise the distance between the hyper-plane and the origin
• The points lying below the hyper-plane and closer to origin are outliers

b. According to Tax et al.

• Project point to a higher dimensional space
• Separate all the data points from the origin in the feature space using hyper-sphere
• Like traditional svm where we use soft margin for smoothness
• minimise the volume of the hyper-sphere
• The points lying outside the hyper-sphere are outliers.

Answer 4

You can use One Class SVM for some pipeline for Active Learning in some semi-supervised way.

Ex: As SVM deals with a max-margin method as described before, you can consider those margin regions as boundaries for some specific class and perform the relabeling.