7
$\begingroup$

I wanted to check if I am understanding the concept of the support vectors correctly. Let's say I am not using any kind of kernel, and it is a hard-margin SVM.

In this case, whatever the number of the dimensions is for our features, the minimum possible number of support vectors equals to 2 (1 for +, 1 for -). Am I correct? Do we still need more support vectors even in such an ideal case in $R^{d}$?

$\endgroup$
6
$\begingroup$

Yes. The minimum number of support vectors is two for your scenario. You don't need more than two here.

All of the support vectors lie exactly on the margin. Regardless of the number of dimensions or size of data set, the number of support vectors could be as little as 2.

Reference: https://stackoverflow.com/questions/9480605/what-is-the-relation-between-the-number-of-support-vectors-and-training-data-and

enter image description here

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ @HyoseungRobinKang Please accept the answer if it helps you. That will make us happy and work harder to answer your next question! You also gain some points yourself. $\endgroup$ – SmallChess Feb 2 '17 at 2:31
  • $\begingroup$ You should provide an example figure with only 2 support vectors. The image you've provided doesn't illustrate the point of your answer. And, +1 for giving the reference to original and more detailed SO answer. $\endgroup$ – Nagabhushan S N Apr 7 at 1:52
2
$\begingroup$

Unfortunately the figure provided in the answer by @SmallChess still has 3 support vectors. The answer is correct - the minimum number of support vectors is 2. The best way to understand this issue is the convex hull model of SVM (for instance http://www.robots.ox.ac.uk/~cvrg/bennett00duality.pdf). The minimum case will have two convex hulls where the minimum distance between them is the distance between two vertices of the hull

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. I copied and pasted the image, but I didn't do anything to it. $\endgroup$ – SmallChess Oct 30 '17 at 11:20
0
$\begingroup$

If the training data involves only one class (which is a trivial problem) then there is no support vector at all.

Reference: Learning From Data - A Short Course, by Yaser S. Abu-Mostafa, Malik Magdon-Ismail and Hsuan-Tien Lin. e-Chapter 8, Exercise 8.12 and Page 31.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This is a misleading answer. One-class SVM do have support vectors - some of the data in the one-class are made to be "of the other class" so there are support vectors. A degenerate classification case where there is no example of one of the classes will not be solved by a SVM solver, an in a round-about way one can claim that there is no support vector - but only in this very roundabout way of looking to the problem. $\endgroup$ – Jacques Wainer Oct 30 '17 at 9:32

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.