5
$\begingroup$

I'm trying to work on an anomaly detection problem, so I am currently exploring my options on which algorithm is best to use for me.

I've been looking at the one-class SVM in the scikit-learn library for Python. It has a parameter nu that you pass it, which roughly determines what percentage of training data it is allowed to mislabel as an anomaly.

This might simply be a lack of understanding of something fundamental about the the one-class SVM, but I am wondering why I can't set the nu parameter to zero. In my application, it is more important for me to make sure I don't label something as an anomaly rather than to miss an actual anomaly.

Do I simply need more data so that I can set a very low nu?

$\endgroup$

2 Answers 2

7
$\begingroup$

As @Joe already mentioned, $\nu$:

  1. sets an upper bound on the fraction of outliers (training examples regarded out-of-class) and,
  2. serves as a lower bound on the number of training examples used as Support Vector.

Mathematically, the quadratic programming minimization function is:

enter image description here

So if $\nu$ is too small, the problem is becoming a hard margin algorithm (2nd item is infinity). And the algorithm will find the unique supporting hyperplane with the properties that it separates all data from the origin, and its distance to the origin is maximal among all such hyperplanes, which, as you said, a 100% training accuracy. You can try to set nu a small value rather than 0. Perhaps the package doesn't allow the -Inf occurrence in the cost function.

$\endgroup$
5
$\begingroup$

Can I achieve zero training error in an SVM?

Yes, but only if the data is separable. The separability of a dataset might depend on the kernel function you're using (e.g., if you're using the dot product, then "separable" = "linearly separable"), but some data sets aren't separable under any kernel function, for example, the following data set in $\mathbb{R}^2$:

positive_examples = [(0,0), (1,1), (2,2)]

negative_examples = [(0,0), (2,1), (3,2)] # (0,0) is in both categories

What do we do if it's not separable?

The "hard margin" SVM seeks to perfectly separate the data with a (hyper)plane (possibly in some wacky space implied by the kernel function) and then maximize the margin (the space on either side of that plane). Maximizing the margin controls the generalization error.

A "soft margin" SVM tries to do the same thing, but it allows for a small amount of misclassification. The tradeoff between minimizing mis-classification and maximizing the margin is controlled by a hyperparameter called $C$. The parameter you mentioned ($\nu$) is a reparameterization of $C$ that's easier to pick and interpret than $C$ is.

Ok, so what is the interpretation of $\nu$?

Quoting from this StackOverflow post on Hard margin vs Soft margin SVM (which I recommend you read):

The parameter nu is an upper bound on the fraction of margin errors and a lower bound of the fraction of support vectors relative to the total number of training examples. For example, if you set it to 0.05 you are guaranteed to find at most 5% of your training examples being misclassified (at the cost of a small margin, though) and at least 5% of your training examples being support vectors.

Why the hell do I want to allow errors?

You say "it is more important for me to make sure I don't label something as an anomaly rather than to miss an actual anomaly." That seems like a great argument, but we're talking about training error not generalization error here. Fitting the training data absolutely perfectly is a recipe for disaster overfitting. (Also, as a side note, it sounds like you might want to be optimizing for precision rather than accuracy, or at least weighting false positives as being worse errors than false negatives.)

Whenever we fit complex models to data, it's important that we understand the tradeoff of model complexity and generalization error. Simple models generalize well from very little data, but they may miss real complexities in the data. Complex models can match complexities in the data, but they also match noise in the data (which makes them generalize poorly). All machine learning models attempt to build in some sort of "regularization" which penalizes some measure of model complexity (which can be traded-off with accuracy, the parameter usually being chosen by cross validation).

$\endgroup$
2
  • $\begingroup$ Thanks for the reply, and while I learned something, most of that post seems to be talking about a supervised learning problem rather than unsupervised anomaly detection... unless I am missing the connection? $\endgroup$ Commented Jan 8, 2014 at 5:27
  • 1
    $\begingroup$ @w1res what? You can do unsupervised learning with SVMs? I feel a bit dumb. What's the objective function? $\endgroup$ Commented Jan 8, 2014 at 6:32

Your Answer

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

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