An analytical solution to support vector training: the recursive projection algorithm
Une solution analytique au problème de l'apprentissage des support vector machines : l'algorithme projection récursive.
Résumé
We propose an algorithm which provides an analytical solution to the problem of norm 2 margin support vector machines (svm) computation. We consider a geometric interpretation of the problem : the svm is defined as the point of a convex polyhedron which is the closest to a particular right line. Our algorithm performs iterative tests of facets of the polyhedron. Each test computes the point of the subspace defining the facet which is the closest to the right line. We show that the svm is such a point satisfying simple conditions. The non satisfaction of these conditions gives indications on the next facet to test. We prove the convergence of the algorithm, and of its use in a variant of the chunking strategy, in general. Our preliminary empirical study of the method suggests that the number of facet tests necessary to find the svm is linear with the number of support vectors. Therefore, the method is particularly interesting when the number of support vectors is low.
Nous proposons un algorithme qui apporte une solution analytique au problème du calcul de support vector machines (svm) dans le cas de l'utilisation de la norme 2 pour traiter les exemples mal classés. Nous considérons une interprétation géométrique du problème. Le svm est défini comme le point d'un polyèdre convexe qui est le plus proche d'une droite particulière de l'espace. Notre algorithme exécute des tests itératifs des facettes du polyèdre. Chaque test calcule le point du sous-espace définissant la facette qui est la plus proche de la droite. Nous montrons que le svm est un tel point satisfaisant des conditions particulières.La non satisfaction de ces conditions donne des indications sur la prochaine facette à tester. Nous prouvons la convergence de l'algorithme et de son utilisation dans une variante de la stratégie chunking, en général.Notre étude empirique préliminaire des méthodes suggère que le nombre de facettes nécessaires pour trouver le svm est linéaire avec le nombre de support vectors.Par conséquent, la méthode est particulièrement intéressante quand le nombre de support vectors est faible.