vendredi 28 mars 2008

Support vector machine (SVM)

Les machines à vecteurs de support (ou machine à vaste marge) sont des techniques d’apprentissage supervisé qui reposent sur deux idées fortes : (1) il repose sur le principe de la maximisation de la marge ; (2) lorsque les données ne sont pas linéairement séparables, il est possible, par le principe des noyaux, de se projeter dans un espace de plus grande dimension pour trouver la solution adéquate, sans avoir à former explicitement ce nouvel espace de représentation (Wikipedia, voir références).

Dans ce tutoriel, nous montrons la mise en œuvre des SVM de TANAGRA. Notre implémentation reprend l’algorithme de Platt (1998 - Algorithme SMO), directement inspiré du code source en Java de Weka, un logiciel très populaire dans la communauté « apprentissage automatique ». Nous montrons que dans un problème avec un ratio nombre d’individus/nombre de variables défavorable, les SVM résistent mieux à la dimensionnalité que l’analyse discriminante. Nous verrons également qu’en passant à un noyau polynomial de degré 2, les performances sont encore améliorées.

Sur notre fichier, nous réduisons significativement le taux d’erreur, il passe de 25% (analyse discriminante) à 15% (SVM – Noyau polynomial). Le SVM linéaire propose un taux de 20%. Ce n’est qu’un exemple illustratif bien entendu, ça n’a pas valeur de preuve. Quoiqu'il en soit, il est avéré que les SVM, surtout linéaires, résistent fort bien à la fameuse « malédiction de la dimensionnalité ». Contrairement à l’analyse discriminante qui peut s’effondrer dramatiquement dans ce contexte.

Les taux d’erreur sont mesurés par bootstrap.

Mots clés : SVM, support vector machine, machine à vaste marge, analyse discriminante linéaire, fonction noyau
Composants : Supervised Learning, SVM, Linear discriminant analysis, Bootstrap
Lien : fr_Tanagra_SVM.pdf
Données : sonar.xls
Références:
Wikipédia (FR) – « Machine à vecteurs de support »
Wikipedia (US) – « Support vector machine »
Weka – « Weka 3: Data Mining Software in Java »