0

We know that the SVM optimization problem with n data points has a solution in the form of

$$f(x)=\sum_{i=1}^n a_i k(x_i,x)+b$$

which has n+1 coefficients. But as I understands it we don't neccesarily need all n+1 of them. So what is the minimum amount of them that is required for the solution?

ChuckP
  • 743
  • 7
  • 17
  • If you train the SVM on a training sample you will find that a lot of the $a_i$ are equal to zero, so all these do not contribute to the sum. How many are zero depends on the data and on the kernel uses just as on the tuning parameters. –  Oct 23 '17 at 09:35
  • Ok so I'm guessing that non support vectors have a_i=0? I don't really see how it would differ for different kernels tho. What would the minimum amount be for linear and gaussian for some random data for instance? – ChuckP Oct 23 '17 at 09:58
  • It is not so difficult to try that out is it ? In R you have a package for SVM and you just generate some random data ? –  Oct 23 '17 at 10:38
  • I meant it in a theoretical sense. – ChuckP Oct 23 '17 at 11:45
  • The theory shows that it depends (for Gaussian kernel) on the radius chosen for your kernel, on your sample size, on your sample elements and on the capacity parameter C. –  Oct 23 '17 at 12:46

1 Answers1

1

The samples $\mathbf{x}_i$ for which you find that $\alpha_i\neq 0$ are your support vectors. In a separable problem and hard-margin SVM, these are simply the vectors that hit the margin on either side of the hyperplane.

In soft-margin SVM, you additionally get non-zero $\alpha$'s for vectors that are on the wrong side of the margin or even the wrong side of the hyperplane.

Generally, the number of non-zero $\alpha$'s increases when

appletree
  • 167
  • 4