libsvm "reaching max number of iterations" warning and cross-validation

Question

I'm using libsvm in C-SVC mode with a polynomial kernel of degree 2 and I'm required to train multiple SVMs. Each training set has 10 features and 5000 vectors. During training, I am getting this warning for most of the SVMs that I train:

WARNING: reaching max number of iterations
optimization finished, #iter = 10000000

Could someone please explain what does this warning implies and, perhaps, how to avoid it?

I also want to apply cross-validation for my models in order to determine the best choices for gamma and C (regularization). My plan is to just try every combinations of these 10 values: 0.00001, 0.0001, 0.001, 0.01, 0.1, 1, 10, 100, 1000, 10000 for both parameters and see which combination produces the best accuracy during cross-validation. Is this enough? Should I use more values in this interval, or should I choose a wider interval?

Answer 1

This warning means that the iterative routine used by LIBSVM to solve quadratic optimization problem in order to find the maximum margin hyperplane (i.e., parameters $w$ and $b$) separating your data reached the maximum number of iterations and will have to stop, while the current approximation for $w$ can be further enhanced (i.e., $w$ can be changed to make the value of the objective function more extreme). In short, that means the LIBSVM thinks it failed to find the maximum margin hyperplane, which may or may not be true.

There are many reasons why this may happen, I'd suggest you to do the following:

• Normalize your data.
• Make sure your classes are more or less balanced (have similar size). If they don't, use parameter -w to assign them different weights.
• Try different $C$ and $\gamma$. Polynomial kernel in LIBSVM also has parameter 'coef0', as the kernel is $$\gamma \cdot u' \cdot v + \text{coeff}_0^{\text{ degree}}$$

It's a good idea to search optimal $C$ on a logarithmic scale, like you do. I think for normalized data the search range for $C$ that you suggested should be OK. A useful check: the accuracy of the classifier should not be changing much on the borders of that range and between two values of your set. If it does, extend the range or add intermediate values.

Note that LIBSVM distributive for Windows should contain a Python script called grid.py, which can do parameter selection for you (based on cross validation and specified search ranges). It can also produce contour plots for the accuracy of SVM. This tool may be quite helpful.

The following question on StackOverflow and its related questions might also help: libsvm Shrinking Heuristics