vendredi 18 mai 2012

La librairie LIBCVM (Core Vector Machine)

Les Support Vector Machine (SVM) constituent des méthodes particulièrement efficaces en apprentissage supervisé. De par leur grande stabilité, elles sont bien adaptées aux problèmes comportant un grand nombre de descripteurs relativement à la taille d’échantillon .  Elles sont moins à leur avantage lorsque le nombre d’observations « n » devient important. En effet, une implémentation naïve est de complexité O(n^3) en temps de calcul et O(n^2) en espace de stockage. De fait, obtenir la solution optimale n’est pas possible en pratique. Les implémentations recherchent des solutions approchées, et en profitent au passage pour réduire les complexités.

J’ai découvert récemment la librairie LIBCVM. L’idée des auteurs est très astucieuse, ils tiennent le raisonnement suivant (traduction très libre) : « Puisqu’on ne peut obtenir que des solutions approchées, on peut s’appuyer sur une formulation équivalente de la recherche des points supports, la recherche de la plus petite boule englobante (Minimum Enclosing Ball) en géométrie computationnelle, et utiliser les résultats obtenus avec cette dernière ». A la sortie, tout comme les SVM, la technique produit une série de points supports utilisables pour la prédiction, les performances prédictives sont similaires voire améliorées, avec une capacité accrue d’appréhension des grandes bases (en nombre d’observations).

Les méthodes CVM (Core Vector Machine) et BVM (Ball Vector Machine) dédiées à l’apprentissage supervisé sont implémentées dans la librairie LIBCVM. Il s’agit une extrapolation de la bibliothèque LIBSVM (version 2.85), bien connue des chercheurs. Le code source en C++ étant disponible, j’ai compilé LIBCVM (version 2.2 [beta], 29 août 2011) en DLL et je l’ai intégrée dans TANAGRA 1.4.44. Dans ce tutoriel, nous décrivons le comportement des méthodes CVM et BVM sur la base « Web data set » accessible sur le site des auteurs. Nous comparons les performances (qualité de prédiction, temps de calcul) avec celles de la méthode C-SVC de la librairie LIBSVM.

Mots clés : support vector machine, machines à vecteur de support, séparateur à vaste marge, svm, libcvm, cvm, bvm, libsvm, c-svc
Composants : SELECT FIRST EXAMPLES, CVM, BVM, C-SVC
Lien : fr_Tanagra_LIBCVM_library.pdf
Données w8a.txt.zip
Références :
I.W. Tsang, A. Kocsor, J.T. Kwok : LIBCVM Toolkit, Version: 2.2 (beta)
C.C Chang, C.J. Lin : LIBSVM -- A Library for Support Vector Machines