1Réunion biblio 13/12/00

Support VectorsSupport Vectors

Présentation générale

SSS Maintaining Algorithm

Réunion biblio 13/12/00

Réunion biblio 13/12/00

Réunion biblio 13/12/00

Réunion biblio 13/12/00

Réunion biblio 13/12/00

Problème quadratique sous Problème quadratique sous contraintescontraintes

On considère l’échantillon :

Le problème est de trouver (w, b) minimisant w.w, sous contraintes :

La fonction de classification :

Réunion biblio 13/12/00

Transformation lagrangienneTransformation lagrangienne

• Le problème devient :Minimiser :

• Sous contraintes :

Réunion biblio 13/12/00

Espaces déployésEspaces déployés

Exemple :

Réunion biblio 13/12/00

Réunion biblio 13/12/00

Ensembles non linéairement Ensembles non linéairement séparablesséparables

Introduction de variables permettant d’enfreindre les contraintes :

Minimiser :

Sous contraintes :

Equivalent à :

l

iiC

1

2. ww

iii by 1).( xw

li ,...,1

pqqppqqp

qpqpCC

yyK .1...),( 22 xxxxxx

Réunion biblio 13/12/00

Réunion biblio 13/12/00

Réunion biblio 13/12/00

Réunion biblio 13/12/00

Réunion biblio 13/12/00

Théorie de la généralisationThéorie de la généralisation

• Lorsqu’on arrive à séparer un ensemble de points (provenant d’une distribution à support fini K) par une séparation linéaire avec une marge , alors, on peut borner la probabilité que l’erreur en généralisation soit supérieure à , indépendamment de la dimension de l’espace.

Réunion biblio 13/12/00

RemarquesRemarques

• Pas d’algorithme qui calcule directement la support vector machine (approximations successives de type gradient)

• La minimisation est faite dans un espace de dimension souvent très grande (la taille de l’échantillon), avec un grand nombre de contraintes

Réunion biblio 13/12/00

Interprétation géométrique Interprétation géométrique

• recherche du point d’un polyèdre convexe, le plus proche de l’axe des b.

ContraintesEspace (w, b)

axe b

Réunion biblio 13/12/00

Mmcs(V)Mmcs(V)

• On considère l’intersection de sous-ensembles de contraintes (facette du polyèdre), et on calcule directement le point le plus proche de l’axe b.

• Pour cela, nécessaire de faire une projection orthogonale de l’axe b sur la facette. Pour ce faire, on utilise une base orthogonale définie à partir des normales aux contraintes.

• On appelle mmcs(V) (max. marg. Classifier supported by V) la fonction de classification obtenue

Réunion biblio 13/12/00

Self Supporting SetSelf Supporting Set

• Equivalence entre : pas de contrainte inutile, et « self supporting set » (SSS)

Réunion biblio 13/12/00

Caractérisation d’un SSSCaractérisation d’un SSS

• Si on enlève l’un des points, alors le mmcs associé au nouvel ensemble donne une marge inférieure à 1 pour le point enlevé

• Nécessité de maintenir autant de bases orthogonales qu’il y a de contraintes dans l’ensemble.

Réunion biblio 13/12/00

Réunion biblio 13/12/00

Réunion biblio 13/12/00

Réunion biblio 13/12/00

Réunion biblio 13/12/00

Réunion biblio 13/12/00

Réunion biblio 13/12/00

Extension à un espace déployéExtension à un espace déployé

• Il faut exprimer les vecteurs de base à partir des vecteurs initiaux (et non de la base déployée)

• Cela permet de traiter le cas non séparable avec une norme 2 pour les variables de dépassement.

Réunion biblio 13/12/00

ConclusionConclusion

• Très efficace lorsque le nombre de support vectors est petit. Dès qu’on atteint une centaine, beaucoup de temps de calcul et de place mémoire (en degré 4) du nombre de sv.

• Pistes possibles pour éviter de maintenir l’ensemble des bases (élimination systématique de la moitié des vecteurs considérés).