0
$\begingroup$

first of all, I apologize about asking this question again since a similar one was posted recently; I had to repost it since I still don't understand the answer and I had no other way to interact with those who answered.

That said, I can't fully get how the "training set vs. origin" logic can work in One-Class SVM, even though I think I pretty much understood binary SVM.

1) I can see how it might work with linear separation, but I can't get how it would work using Kernel functions. Let's take this binary SVM animation as a reference.

Imagine that we have the following training set in R^2 (training set -> red; origin -> blue).

Original feature space (R^2)

If we apply a Kernel function similar to the one used in the animation above, we would obtain something similar to the next figure (it is in R^3, the X axis would point towards you; sorry for the poor representation!)

Data projection in R^3

I guess that H3 would be the best hyperplane to choose, but I think that the one who maximizes the margin between the two classes would be H2 (which is still pretty good). My question is: what does prevent the algorithm to choose H1 as the decision boundary, since it would be very large (and therefore bad) while still having a decent margin between the classes? How would the $\nu$ parameter be "graphically" involved in this decision?

2) What would happend if the origin (0, ..., 0) was already INTO the training set?

Thank you in advance!

$\endgroup$
1
$\begingroup$

Huh this is an interesting problem. The cost function for a one-class SVM is :

\begin{align*} \text{min}_{w, \rho, \xi_i}&\frac{1}{2}||w||^2 + \frac{1}{\nu}\sum_i\xi_i-\rho \\ s.t. w^{T}\Phi(x_i) &\geq \rho - \xi_i \\ \xi_i \geq 0 \end{align*}

(apologies for formatting...)

From this we can see that we're trying to find a function $f(x|w) = w^Tx$ that is bigger than $\rho$ for all the training points (the slack variables $\xi_i$ prevent this from causing no solution if no function exists). $\nu$ controls how we trade-off the norm of the vector we find ($||w||^2$) and the amount of slack we allow. I think this gives an answer to your answer for your question (2), namely that it doesn't matter. Nothing about the problem formally changes if you have one of your training points as the origin, in particular because you assume the feature generating function $\Phi()$. If you assume that function is the identity then you see that $w^T\mathbf{0} \ngeq \rho$ and therefore this must be taken care of by the slack variables.

With respect to your question (1), look at the projection of your points onto the hyperplanes you've drawn. H2 and H3 are the same line except for an offset (approximately), which would fall under the question of what $\rho$ the training procedure returns. H1, if you look at the projections of the points onto the hyperplane clearly has less distance between projected origin and the closest projected point, which prevents it from being your answer. The $\nu$ parameter is actually not involved, since your points are perfectly separable (incidentally this also exposes a problem with the one-class SVM if you use a linear kernel, namely that it can only give you a half-space at best. It really can only be useful with the kernel trick, I would say)

It was an interesting question! Thanks :)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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