Support Vector Machine Action Set

In order to support nonlinear kernels such as the radial basis function (RBF), the svmTrain action also supports the active-set optimization method. This method supports linear, polynomial, RBF, and sigmoid kernels.

The active-set optimization method applies to the dual optimization problem. The active-set method seeks to form the solution by determining which inequality constraints are active at the solution, and they quickly converge as soon as the true active set is known. For the SVM case, active constraints correspond to the bound constraints where . If the active set is known, you can determine the optimal values of the remaining entries in by solving a single system of linear equations whose size is on the order of the number of inactive constraints. Because there are possible ways to partition the bound constraints into active and inactive sets, it is possible to create worst-case-scenario problems in which a prohibitive number of combinations are tried before a solution is reached. However, in practice, the number of combinations that are tried is usually much smaller. A consequence of this observation is that the run time of the active-set method for a particular problem is much harder to predict.

The computational costs of the active-set method are controlled by the number of support vectors, and this number is highly dependent on both the problem and the choice of kernel. As a rule, the run time increases with the number of inactive support vectors. A significant computational cost of the active-set method comes from the need to update the residual of the optimality error. Therefore, the svmTrain action is multithreaded to reduce the solution time.

For the same problem, you might observe that the number of support vectors that the interior point method finds is much larger than the number of support vectors that the active-set method finds. This can occur whenever the dual solution, , is not unique; it results when the interior point method tries to follow a positive trajectory of approximate minimizers to the solution. This implies that the interior point method initially treats every vector as a support vector and uncovers non-support vectors in the limit, when it is pushed sufficiently close to the boundary. In contrast, active-set methods add support vectors to the approximate solution incrementally and have a better chance of finding a sparser solution.

The model training of the active-set method is supported on a single-machine node. When data are distributed, the training is performed at the first worker node where the data are aggregated from other nodes before the computation. Unlike the interior point and coordinate descent methods, the active-set method supports only problems that involve relatively small data sets. For example, when the number of observations is greater than 100,000 and the number of features is greater than 1,000, the memory requirement can dramatically increase and the training time is much longer.

Note: Currently, the active-set method does not support SVR training.