4

I have a few related questions:

  1. What is the total number of fitted paramaeters in Python Support Vector Machine: sklearn.svm.SVC(kernel='linear') and sklearn.svm.SVC(kernel='rbf')?

I am trying to find out the total number of fitted parameters in linear and kernel SVM. If I understand correctly, the fitted parameters include C (penalty parameter), gamma(for kernel='rbf', none for kernel='linear'), all the coefficients (for kernel = 'linear', equal to the number of features + 1 for the intercept; for kernel = 'rbf', equal to the number of training samples), and slack variables (equal to the number of samples) - is this correct?

  1. If the above is correct, does it imply that there is a high probability of overfitting for SVM with kernel = 'rbf' since the number of fitted parameters is always greater than the number of samples?

Thank you very much for your help!

Starz
  • 432
  • 1
  • 3
  • 11

3 Answers3

3

C + gamma (for kernel="rbf") or C + degree + coef0 (for kernel="poly") are usually the hyper-parameters of a SVM you want to tune with grid search (or randomized search). For the poly kernel, you don't have to tune all the coefficients by yourself, just specifify what order you want the polynomial to be. About the slacks, they are controlled by the C parameter so you don't have to set them yourself.

To answer your second question: it depends on the value of C. Lower values (<1) are going to make your SVM more regularized, with higher values it will go rogue.

mp85
  • 549
  • 2
  • 10
  • Thank you! How about the coefficients that correspond to each feature (in linear SVM) and kernel (in kernel SVM)? I am referring to the coefficient w in wT* x (w transponse multiplied by x)? The coefficient vector w (with length equal to the number of features + 1) are also fitted parameters computed by the algorithm right? I am just trying to count the actual number of parameters being fitted into the data vs the number of training samples. – Starz Nov 23 '16 at 03:42
  • For coefficients and slack variables, I am referring to page 19 of this note: http://cs229.stanford.edu/notes/cs229-notes3.pdf – Starz Nov 23 '16 at 04:05
  • 1
    Well, based on how an SVM is constructed, you won't need to calculate w. To solve the maximum margin optimization problem, you will need to solve the dual problem that involves the calculation of the coefficients alpha (see pages 10-13 of that note), which are 0 for all points except the support vectors. So, if I would have to answer I'd say that the number of fitted parameters would be equivalent to the number of support vectors. – mp85 Nov 23 '16 at 09:26
2

There are multiple misunderstandings in both the question and the answer posted by @mp85.

There are to sets of parameters, but one of them are called hyperparameters.

The SVM problem/formulation is $$ \min ||w||^2 + C \sum \xi_i $$ subject to $$ y_i(w·\phi(x_i)+b) \ge 1−\xi_i \quad \xi_i \ge 0 $$ for all data $(x_i, y_i)$. $\phi(x)$ is a transformation on the input data.

So, you must set $\phi()$ and you must set $C$, and then the SVM solver (that is the fit method of the SVC class in sklearn) will compute the $\xi_i$, the vector $w$ and the coefficient $b$. This is what is "fitted" - this is what is computed by the method. And you must set $C$ and $\phi()$ before running the svm solver.

But there is no way to set $\phi()$ directly. It turns out that one defines the transformation by defining a kernel - linear (no transformation) or rbf or poly (or others). Each of this kernels are defined by one or more parameters: rbf by the gamma, poly by coef0 and degree, and so on.

So to run the SVM you must set C, and must choose the kernel and for each kernel, set the appropriate parameter (or parameters). These are collectively known as hiper parameters and they are not computed by the SVM solver, they are set by you.

Finally, it is not 100% true that the SVM solver computes the $w$, the $b$ and the $\xi_i$. The SVC solver uses a different formulation of the svm problem, the dual of the formulation above, and it computes different variables. For the LinearSVC solver, which only works for the linear kernel, it does compute $w$, the $b$ and the $\xi_i$ (and returns $w$ and $b$).

Jacques Wainer
  • 5,032
  • 1
  • 20
  • 32
  • Thank you! I was considering the hyperparameters as also "fitted" in the case of, for instance, Grid Search CV, where we pick the right hyperparameter values to fit the model to the data (I completely agree with you that they are not actually calculated by the model). Sorry for the confusion in the question. But anyways, back to the main issue of the question, so what is the total number of parameters calculated by the model in linear and kernel SVM? We can exclude the hyperparameters from the discussion. – Starz Dec 07 '16 at 21:54
  • Just to simplify the question, what is the dimension of $w$? If I understand correctly, the length of $w$ is equal to the number of features (linear SVM) or number of samples (kernel SVM) if we don't include the intercept? Also, the other question is since the length of $\xi_i$ is equal to the number of samples, should we be very concerned that the number of parameters computed by the model is always greater than the number of samples? – Starz Dec 07 '16 at 22:25
  • 1
    $w$ has the same dimensions as $\phi(x)$ and in the case of the RBF kernel, that is infinite dimensions. That is why the SVM does not solve for the $w$. In the dual formulation, all one needs is a $\alpha_i$ for each data (and the $b$) , but only the data in the support vector has $\alpha_i > 0$ and usually the size of the support vector is smaller that the size of the data set. – Jacques Wainer Dec 09 '16 at 19:16
  • If you have some time, would you mind helping me with one more question? Sorry for the late reply, somehow I am not getting notifications when there is new comment.. This is the link to my question: http://stats.stackexchange.com/questions/250284/eigenvector-normalization-in-kernel-pca – Starz Dec 12 '16 at 19:18
0

Note: regarding the concern of overfitting with SVM, the following page from Sebastian Raschka is very helpful: https://sebastianraschka.com/blog/2016/model-evaluation-selection-part3.html#the-law-of-parsimony

Starz
  • 432
  • 1
  • 3
  • 11