×

Error bounds for support vector machines with application to the identification of active constraints. (English) Zbl 1190.90115

Summary: We present a new global error bound for the dual formulation of the support vector machine (SVM) whose penalty terms are measured by 2-norm (L2-SVM). An further formulation in which an additional term is added to the objective function is also considered (SCL2-SVM). A global error bound for the dual of the latter problem is derived. This error bound is used to identify those constraints of primal SCL2-SVM that will be active at the solution. The correct identification of active constraints is important to find the support vectors and to build the working set of most iterative algorithms for SVM. Computational results are presented showing that the proposed method is able to quickly identify a large percentage of constraints that are active at the optimal solution.

MSC:

90C20 Quadratic programming
68T05 Learning and adaptive systems in artificial intelligence
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C46 Optimality conditions and duality in mathematical programming

Software:

SSVM; SVM
Full Text: DOI