12
$\begingroup$

I have 2 general/more theoretical question.

1) I'm curious how SVMs handle variable interactions when building predictive models. E.g., if I have two features f1 and f2 and the target depends on f1, f2, and say f1 * f2 (or some function h(f1, f2)), does SVM fit (not just on OOS but even on training data) improve when including f1, f2 and h(f1, f2) in the features over just including f1 and f2? Does the SVM algorithm deal with feature interactions? It seems like it would with how the SVM tries to create hyperplanes in higher dimensional space, but not sure so wanted to ask.

2) When fitting a SVM on training data, given enough features and finding the optimal parameters (via brute force search or whatever), will a SVM always trivially fit the training data? Not sure if I worded that right, but basically, if there is enough variance/noise in the features, will a SVM always fit the training data 100%? Conversely, if the SVM does not fit the training data 100%, does that mean there is some information (or other features) which affect the target variable that are not captured in the data?

Thanks

Small clarification. I'm referring to kernel SVMs specifically

$\endgroup$
8
$\begingroup$

As highBandwidth suggests, it depends whether you are using a linear SVM or a non-linear one (being pedantic if a kernel is not used it is a maximal margin linear classifier rather than an SVM).

A maximal margin linear classifier is no different from any other linear classifier in that if the data generating process means that there are interactions between the attributes, then providing those interaction terms is likely to improve performance. The maximal margin linear classifier is rather like ridge regression, with a slight difference in the penalty term that is designed to avoid overfitting (given suitable values for the regularisation parameter), and in most cases ridge regression and maximal margin classifier will give similar performance.

If you think that interaction terms are likely to be important, then you can introduce them into the feature space of an SVM by using the polynomial kernel $K(x,x') = (x\cdot x' + c)^d$, which will give a feature space in which each axis represents a monomial of order $d$ or less, the parameter $c$ affects the relative weighting of monomials of different orders. So an SVM with a polynomial kernel is equivalent to fitting a polynomial model in the attribute space, which implicitly incorporates those interactions.

Given enough features, any linear classifier can trivially fit the data. IIRC an $n$ points in "general position" in an $n-1$ dimensional space can be shattered (separated in any arbitrary manner) by a hyper-plane (c.f. VC dimension). Doing this will generally result in severe over-fitting, and so should be avoided. The point of maximal margin classifcation is to limit this over-fitting by adding a penalty term that means that the largest separation possible is achieved (which would require the greatest deviation from any training example to produce a misclassification). This means you can transform the data into a very high dimensional space (where a linear model is very powerful) without incurring too much over-fitting.

Note that some kernels give rise to an infinite dimensional feature space, where a "trivial" classification is guaranteed to be possible for any finite training sample in general position. For example, the radial basis function kernel, $K(x,x') = \exp{-\gamma\|x - x'\|^2}$, where the feature space is the positive orthant of an infinite dimensional hypersphere. Such kernels make the SVM a universal approximator, that can represent essentially any decision boundary.

However this is only part of the story. In practice, we generally use a soft-margin SVM, where the margin constrain is allowed to be violated, and there is a regularisation parameter that control the trade-off between maximising the margin (which is a penalty term, similar to that used in ridge regression) and the magnitude of the slack variables (which is akin to the loss on the training sample). We then avoid over-fitting by tuning the regularsation parameter, for example by minimising the cross-validation error (or some bound on the leave-one-out error), just as we would do in the case of ridge regression.

So while the SVM can trivially classify the training set, it will generally only do so if the regularisation and kernel parameters are badly chosen. The key to achieving good results with any kernel model lies in choosing an appropriate kernel, and then in tuning the kernel and regularisation parameters to avoid over- or under-fitting the data.

$\endgroup$
  • $\begingroup$ Thanks Dikran. That was extremely detailed and helpful. I think I understand the answers to the questions. One quick follow up. How does one go about choosing the appropriate kernel for SVMs? Would it be similar to regularization/kernel parameters (e.g. via cross validation)? Or is there some theoretical basis for the choice? If the rbf kernel makes the SVM a universal approximator, I would guess the kernel selection is another parameter to tune, but not sure. As you can probably tell, I'm fairly new to this. $\endgroup$ – tomas Jan 19 '12 at 20:46
  • $\begingroup$ Choosing a kernel is often a good way of building in expert knowledge of the problem into the classifier, for instance for a handwritten character recognition system, you would probably want to use a kernel that was invariant to small rotations and translations of the image. Choosing a kernel automatically can be achieved by cross-validation (which is what I would do) or a bound on the leave-one-out error (which can be performed efficiently for SVMs). However if the dataset is small then choosing a kernel via cross-validation can be tricky due to overfitting the cross-validation error. $\endgroup$ – Dikran Marsupial Jan 20 '12 at 10:01
  • $\begingroup$ For many applications, linear or RBF kernels are good default choices, and there is often relatively little to gain from exploring a wider range of kernels (in the absence of expert knowledge of the problem). $\endgroup$ – Dikran Marsupial Jan 20 '12 at 10:02
1
$\begingroup$

The answers depend on whether you are using linear SVM or kernel SVM. With linear SVM, you are only using the features you give it, and it does not take into account interactions. With Kernel SVM, basically you are using a lot of different features, depending on which kernel you chose. If there is a separating hyperplane, i.e., if $sign(\sum_{i=1}^{K}\beta_i(x)-\beta_0)$ determines the class where $\beta_i,i \in \{1,2,...K\}$ are the features, then you can have complete fitting of the training data. Usually, you do not specify the features, but give a kernel $K$ that is related to the features as $K(x_1,x_2) = \sum_{i=1}^K \beta_i(x_1) \beta_i(x_2)$. Look up reproducing Kernel Hilbert spaces.

$\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.