4
$\begingroup$

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?

$\endgroup$
5
  • 3
    $\begingroup$ The hyperplane doesn't have to go through the origin!! $\endgroup$
    – SmallChess
    Nov 15, 2017 at 10:48
  • 1
    $\begingroup$ yes I understand that. but what i can't see is how a hyperplane that separates the data from the origin can help you detect outliers located elsewhere, let's say above your data not beneath it. $\endgroup$
    – Dr.nina
    Nov 15, 2017 at 10:57
  • $\begingroup$ @Dr.nina: I think you miss-read SmallChess's comment (and the one class svm objective function). The directions are not from the origin but from the center of gravity of the data --which is the same thing ⟺ the data has been previously centered, which is sometimes assumed in expositions of OCSVM to lighten notations. For example, the center of gravity of the data appears as the $\pmb a$ parameter in the Tax and Duin paper $\endgroup$
    – user603
    Nov 15, 2017 at 14:51
  • 1
    $\begingroup$ I have doubts on the intuition of one-class SVM as well. Why separation from origin with a superplane helps with outlier detection? The SVDD approach of Tax and Duin (2004) makes perfect sense to me. SVDD is equivalent to one-class SVM only when the data points have all been normalized to have norm 1 (i.e., all data points are located on a sphere). Could you share your perspective after you figure it out? Thanks! $\endgroup$
    – XGS
    Oct 13, 2018 at 22:35
  • $\begingroup$ Even for SVDD, it turns out that the center, i.e., $\mathbf{a}$ vector is estimated with points only ON or OUTSIDE the sphere, which is also counter-intuitive. It would make better sense that the center be estimated from norm cases (ON or INSIDE the sphere. $\endgroup$
    – XGS
    Oct 13, 2018 at 22:42

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Does the kernel trick always produce non-linear margins? $\endgroup$ Jun 11, 2021 at 19:52
  • $\begingroup$ @SingleMalt not necessarily. The margins will be 'optimal' with respect to hyperparameters C and gamma, which may end up being linear for a particular training set and hyperparameter selection. In practice this is unlikely to actually occur, for example with the RBF kernel you may find your margins might look linear at the scale of your sample points, but upon 'zooming out' far beyond the space your samples occupy you might find the margins form a curved decision boundary. $\endgroup$
    – Avelina
    Jun 11, 2021 at 20:46
1
+50
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ The origin from which the Schoelkopf SVM seperates the data is the origin within feature space, not the origin of the data's original space, right? So my 2D data itself could have a sample (0,0) but $\phi((0,0))$ is not the 0-element in feature space, or am I mistaken? $\endgroup$
    – JMC
    Nov 12 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.