Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
I don't understand what is the intuition behind the idea of finding a hyperplane that separate the training data from the origin if the feature space.
To me it would be more intuitive to create a boundary around the positive class from all direction not just from the origin (as the Support Vector Data Description SVDD does).
Can anyone clarify that for me?
Support Vector Machines come in a few flavors. Hard margin SVMs demand linear separability to construct the equidistant margins parallel to the hyperplane where all samples must sit either on or outside the margins. Soft margin SVMs allow samples to cross the margins by giving them 'slack'. In a soft margin SVM the problem involves minimising slack while maximising margin distance from the hyperplane.
In a one class SVM problem used to detect outliers the opposite is observed. This problem involves minimising both slack and margin distance, such that any samples which step outside the margins can be classified as outliers. By controlling hyperparameters C and gamma you have control over how the SVM priorities minimisation of slack and minimisation of margin distance.
If we assume the data is standardised with zero mean and unit variance we know that the 'hyperplane' will go through the origin, but this hyperplane isn't used for classification, it simply orients the margins, and the position of the samples relative to the margins is what 'classifies' samples as outliers.
To me it would be more intuitive to create a boundary around the positive class from all direction not just from the origin.
Again, SVMs work best with standardised data anyway, so you should be feeding that to your SVM anyway. And remember, SVMs don't necessarily create just linear hyperplanes and margins, through the use of the kernel trick with something like the RBF kernel it's possible for the 'outlier' boundary to very much be non-linear.
You refer to two ways to formulate the anomaly detection problem in terms of a max-margin approach which were first treated in detail in the paper Estimating Support of a High-Dimensional Distribution. See also the book kernel method for pattern analysis for an accessible and detailed analysis. One motivated by measure theory, and the second by geometry.
Let me start with the second (for me, the most intuitive one). You may say you want to find the smallest enclosing hypersphere
$$ \min_{c, r} r^2 \\ \text{subject to } ||\phi(x_i) - c||^2 \leq r^2 $$
where $c$ is the centre of the smallest hypersphere containing the set of positive training samples. That is, the solution to the problem
$$ \text{argmin}_c max || \phi(x_i) - c||^2 $$
And that gives you a valid solution. The advantage of the other formulation ($\nu$-SVM) is that the parameter $\nu$ has a nice interpretation which is useful in practice to find the best balance between true/false positives. Namely, it can be shown that $\nu$ places an upper bound on the fraction of outliers and a lower bound on the fraction of support vectors. The first formulation does not provide anything similar.
Finally, imagine you know the probability distribution of your data $P(x)$. Then the problem of anomaly detection would be that of finding the (highest!) threshold probability $\alpha$ such that all samples with $P(x) \leq \alpha$ are considered outliers. And this is precisely the sort of functions that they try to approximate, though expressed in the opposite manner: $w^T \phi(x) > \alpha$. Proposition 3 in the aforementioned paper gives a connection of this idea to classification problems, which they exploit to prove properties on the solution and the parameter $\nu$.
The idea is that a kernel function is essentially a similarity measure and that two points that are similar to eachother will be close to eachother in feature space. For example, condider three points $x_{i}$, $x_{j}$ and $x_{k}$. For the RBF kernel $k(x,x^\prime)$ = $\exp (-\frac{\left \| x-x^\prime \right \|^2}{2\sigma})$, let $k(x_{i},x_{j})=0.9$ and $k(x_{i},x_{k})=0.1$. You can interpret this as $x_{i}$ and $x_{j}$ being more similar than $x_{i}$ and $x_{k}$ and therefore $\phi(x_{i})$ and $\phi(x_{j})$ will be closer to eachother in feature space than $\phi(x_{i})$ and $\phi(x_{k})$. Additionally, note that a kernel function is just an inner product in some feature space, hence $k(x_{i},x_{j}) = \langle\phi(x_{i}),\phi(x_{j})\rangle$. Hence, we measure the similarity of two points in feature space by calculating their inner product. Note that in feature space the inner product of every point with the origin is 0, $\langle\phi(x),0\rangle=0$. Hence there is low similarity between the points in our training set and the origin. Therefore, the one class svm is trying to separate similar points from disimilar points, where the origin represents disimilar points. Therefore, the one class SVM (as defined by Scholkopf) tries to find a hyperplane in feature space that maximizes the distances from the origin (disimilar points) and minimizes the distance to the training data (similar points). When transforming the hyperplane back into the input space this will be a non-linear decision boundary, which essentially acts as a demarcation of a percentile of the probability distribution. For example the decision boundary could contain 95% of your data. Anything outside of this boundary would then be seen as unlikely to have come from the probability distribution generating the training data and therefore be classified as an outlier.
Additionally, note that the SVDD, which finds the smallest enclosing hypersphere that encloses all datapoints and may make more intuitive sense, is equivalent to the one Class SVM as defined by Scholkopf for translation invariant kernels. In other words, if you use the RBF kernel, the idea of separating the training points from the origin in feature space is equivalent to the idea of finding the smallest enclosing hypersphere.
