Présentation des Machines à Vecteurs de Support

Présentation des Machines à Vecteurs de Support

Classification supervisée

Les Machines à Vecteurs de Support (SVM) font partie d’une vaste famille d’algorithmes originellement regroupés dans le domaine de la reconnaissance de formes (pattern recognition). Les données sont généralement modélisées sous forme d’un vecteur aléatoire réelle x ∈ R d dont la génération, gouvernée par une densité de probabilité p(x, y), est dépendante de y ∈ {1, . . . , C}, la classe d’appartenance de x. Dans le cas particulier de la discrimination (problème à deux classes), on suppose y ∈ {+1; −1}, où yi = +1 est associé à la classe 1, et yi = −1 à la classe 2, pour alléger les notations. La densité de probabilité de p(x, y) étant généralement inconnue, on se base sur un ensemble de n réalisations S = {(xi , yi)}i=1…n pour caractériser cette dernière. On distinguera par la suite les ensembles S1 = {(xi , yi), yi = +1} et S2 = {(xi , yi), yi = −1}, avec Card(S1) = n1 et Card(S2) = n2. Contrairement à d’autres méthodes de classification, comme les modèles à mélanges de gaussiennes (GMM), les SVM ne se basent pas sur l’estimation de la densité de probabilité, mais sur l’estimation d’une fonction de discrimination entre les exemples des deux classes. On cherche donc une fonction de décision f : R d → R telle que sign(f(x)) = yi . Les Machines à Vecteurs de Support se distinguent en premier lieu parmi les méthodes discriminatives par le critère d’optimalité guidant le choix d’une telle fonction, mais leur émergence fait écho à de nombreuses techniques antérieures de classification supervisée.

Machines à Vecteurs de Support linéaires

En 1964, Vapnik et Lerner introduisent le principe de maximisation de la marge dans un algorithme (Generalized Portrait Algorithm) qui constituera le principe fondamental des futures Machines à Vecteurs de Support [235]. Dans le cas de données séparables, il existe une infinité d’hyperplans permettant de séparer les deux classes, comme l’illustre la figure 3.1 (dont on ne retiendra pour l’instant que les hyperplans en trait plein). Néanmoins, les données étant considérées comme des réalisations d’une variable aléatoire, le choix de l’hyperplan doit être guidé par les propriétés de généralisation de la fonction de décision. La séparabilité des données implique que la contrainte yif(xi) > 0 est remplie pour chaque exemple. Il existe donc une valeur M, appelée marge, minimisant l’ensemble des distances yif(xi) ||w|| 36 3.3. MACHINES À VECTEURS DE SUPPORT LINÉAIRES entre les exemples et l’hyperplan : yif(xi) kwk ≥ M. (3.4) Le principe de l’algorithme consiste à déterminer le vecteur w maximisant la marge M. Il s’agit donc d’une optimisation de type minimax (ou plutôt maximin). Il est cependant nécessaire de fixer une contrainte additionnelle sur la norme de ||w|| afin de restreindre le champ infini de solutions ne différant que par un facteur d’échelle : M kwk = 1. (3.5) Ainsi, maximiser la marge M revient à minimiser la norme du vecteur ||w||. L’inéquation 3.4 devient donc la contrainte yif(xi) ≥ 1. On appelle ainsi hyperplans de marge les deux hyperplans satisfaisant la condition f(x) = ±1. La figure 3.1 montre trois exemples d’hyperplans de séparation (en trait plein) définis par des vecteurs w différents, ainsi que les hyperplans de marge correspondants (en pointillés). On peut voir que la marge, distance entre les hyperplans de marge et de séparation, diffère entre les trois cas, la figure centrale représentant la situation de marge maximale.

Principe de Minimisation du Risque Structurel

Le principe de maximisation de la marge induit donc l’émergence d’un sous-ensemble d’exemples, appelés vecteurs de support, décrivant à eux seuls le comportement du classifieur. Ce principe, appliqué à la séparation linéaire dans la section précédente, peut être étendu à une multitude d’algorithmes [208], par le biais de fonctions noyaux (voir la section 3.5). L’engouement pour les Machines à Vecteurs de Support s’explique ainsi par le fait que diverses méthodes de classifications se sont trouvées fédérées dans un cadre théorique commun, mais surtout parce que leur principe est validé par la théorie de l’apprentissage statistique développée par Vapnik et Chervonenkis dans les années 70 [236]. On peut en effet reformuler le processus d’apprentissage comme la détermination d’une fonction de décision fλ parmi un ensemble H = {fλ(x), λ ∈ Λ} avec fλ : R d → R, (3.16) où λ est l’ensemble des paramètres ajustés durant l’apprentissage (par exemple les variables w et b dans le cas des SVM). On cherche donc une fonction fλ∗ qui minimise le risque fonctionnel suivant : R(λ) = Z |fλ(x) − y| P(x, y)dx dy. Néanmoins, la probabilité P(x, y) étant inconnue, il est impossible d’évaluer le risque R(λ). N’ayant accès qu’à des réalisations de P(x, y), on calcule donc une approximation stochastique du risque, le risque empirique : Remp(λ) = 1 n Xn i=1 |fλ(xi) − y| . où les xi sont les exemples de l’ensemble d’apprentissage. La loi des grands nombres garantit la convergence du risque empirique vers le risque fonctionnel lorsque le nombre d’exemples est suffisamment conséquent. Cependant, seule une convergence uniforme peut garantir que le minimum 38 3.5. NOYAUX de Remp converge vers le minimum R. Vapnik et Chervonenkis ont montré [232][233] que la condition nécessaire et suffisante pour garantir cette convergence est la finitude de la dimension VC (d’après les initiales des auteurs), notée h, de l’espace H (éq. 3.16). Celle-ci est un nombre entier naturel ou infini, défini comme le nombre maximum d’exemples pouvant être séparés de toutes les façons possibles par les fonctions de H. Elle constitue une mesure de complexité de l’ensemble de classifieurs H.