Fouille de données dans les corpus de textes Classification supervisée : SVM

1

Fouille de données dans les corpus de textesClassification supervisée : SVM

Michèle Jardinojardino@limsi.fr

Groupe Langues, Information et Représentationshttp://www.limsi.fr/Recherche/LIR

2

Mes sources

SVM, Support Vector Machines,Marti Hearst, Berkeley, http://www.sims.berkeley.edu/courses/is290-2/f04/sched.html

"Using Very Large Corpora / Spelling Correction / Clustering" (une partie du cours 10)

SVM, Séparateurs à Vastes Marges,

Antoine Cornuéjols, Orsay http://www.lri.fr/~antoine

3

Plan

Classification binairegénéralités

– exemples et définition– linéaire/non-linéaire– séparable/non séparable

PerceptronSéparateurs (classifieurs) à Vastes Marges Fonctions noyau

4

Généralités

5

Classification Binaire : exemples

Courrier électronique : filtrage des spams ( spam / non spam)Classification message (urgent / non urgent )Recherche d'informations (correct / incorrect )Classification émotions ( positive / négative )Transformation de classifications multiples en classification binaire : 1 classe contre toutes les autres

6

Classification Binaire

Données : quelques éléments (textes) qui appartiennent à deux classes différentes

classe 1 (+1 ) et classe 2 (-1 )ou

classe positive (+1 ) et classe negative (-1 )

Tâche : entrainer un classifieur sur ces données (dites d'apprentissage) puis prédire la classe d'un nouvel élément (nouveau texte)Géometriquement : trouver une séparation entre les deux classes

7

Séparation Linéaire / Non Linéaire

Données séparables linéairement : si tous les points associés aux données peuvent être séparés correctement par une frontière linéaire (hyperplan)

8

Données séparables linéairement

Classe 1Classe 2Frontière de décision linéaire

9

Données non séparables linéairement

Classe 1Classe 2

10

Données non séparables linéairement

Classifieur Non Linéaire

Classe 1Classe 2

11

AlgorithmesSéparation Linéaire / Non Linéaire

Données séparables Linéairement ou Non Linéairement ?réponse empirique

Algorithmes Linéaires (algorithmes qui trouvent une frontière linéaire)

Quand on pense que les données sont linéairement séparablesAvantages

– Simples, peu de paramètres à régler

Désavantages– Données dans espace de grande dimension sont souvent non

linéairement séparables

Exemples d'algorithmes : Perceptron, SVMNote : on peut utiliser des algorithmes linéaires pour des problèmes non linéaires (voir fonctions noyau)

12

AlgorithmesSéparation Linéaire / Non Linéaire

Non LinéairesQuand les données sont non linéairement séparablesAvantages

– Plus précis

Désavantages– Plus compliqués, plus de paramètres à régler

Exemple: méthodes à base de fonctions noyau

Note: la distinction entre linéaire et non linéaire est valable pour la classification multi-classes

13

Algorithmes Linéaires Simples

Algorithme du Perceptron LinéaireClassification BinaireEn ligne (apprentissage séquentiel, une donnée à la fois )Apprentissage sur les erreurs Réseau de neurones à une couche

14From Gert Lanckriet, Statistical Learning Theory Tutorial

Algorithmes Linéaires Simples

Données : {(xi,yi)}i=1...n

x dans Rd (x est un vecteur dans un espace de dimension d) vecteur de traits

y dans {-1,+1} étiquette de la classe

Question: Trouver une frontière linéaire : wx + b (equation de l'hyperplan) telle que la règle de classification associée donne une probabilité d'erreur minimalerègle de classification (décision):

– y = signe (w x + b) qui signifie :– si wx + b > 0 alors y = +1– si wx + b < 0 alors y = -1

15From Gert Lanckriet, Statistical Learning Theory Tutorial

Classification Binaire Linéaire

Trouver un hyperplan (w,b) dans Rd+1

qui classe aussi bien que possible les données (points) Progressivement : un point à la fois, en modifiant les poids si nécessaire

wx + b = 0

Règle de Classification : y = signe(wx + b)

16

Perceptron

17From Gert Lanckriet, Statistical Learning Theory Tutorial

Algorithme du PerceptronInitialisation : w1 = 0

Mise à jour des poids Pour chaque point x

Si classe(x) != decision(x,w)alors

wk+1 wk + yixi

k k + 1 sinon

wk+1 wk

Fonction de decision(x, w)Si wx + b > 0 retourne +1Sinon retourne -1

wk

0

+1

-1wk x + b = 0

wk+1

Wk+1 x + b = 0

18From Gert Lanckriet, Statistical Learning Theory Tutorial

Algorithme du Perceptron

Progressif : s'adapte toujours aux nouvelles données Avantages

Simple et efficace Garantie d'apprendre un problème linéairement séparable(convergence, optimum global)

LimitationsSeulement séparations linéaires Converge seulement pour données séparables Pas très efficace dès qu'il y a trop de traits

19

Séparateur (classifieur) à vaste marge

20From Gert Lanckriet, Statistical Learning Theory Tutorial

Une autre famille d'algorithmes linéairesIntuition (Vapnik, 1965) Si les classes sont linéairement séparables :

Séparer les données Mettre un hyper-plan “loin” des données : marge largerésultats statistiques garantis bonne généralisation

Classifieur à Vaste Marge

MAUVAIS

21From Gert Lanckriet, Statistical Learning Theory Tutorial

BON

Classifieur à Marge Maximale

Classifieur à Vaste Marge

Une autre famille d'algorithmes linéairesIntuition (Vapnik, 1965) Si les classes sont linéairement séparables :

Séparer les données Mettre un hyper-plan “loin” des données : marge largerésultats statistiques garantis bonne généralisation

22From Gert Lanckriet, Statistical Learning Theory Tutorial

Si non séparable linéairement

Permettre quelques erreursEssayer encore de placer un hyperplan “loin” de chaque classe

Classifieur à Vaste Marge

23

Classifieurs à Vaste Marge

AvantagesMeilleur théoriquement (barres d'erreurs mieux connues)

LimitationsCalculs plus coûteux, programmation quadratique

24From Gert Lanckriet, Statistical Learning Theory Tutorial

Vecteurs Support

Classifieur Vaste Marge

Cas Linéairement séparable

But : trouver l' hyperplan qui maximise la marge

wT x + b = 0

M wTxa + b = 1

wTxb + b = -1

Vecteurs Support

25

Hyperplan de plus vaste marge

Margemaximale

Hyperplan

optimal

Hyperplanvalide

26

Optimisation de la marge

Margemaximale

Hyperplan

optimal

Hyperplanvalide

D(x) = 0

D(x) = +1

D(x) = -1

Vecteursde support

D(x) > 1

D(x) < -1

w

1

w

27

Optimisation de la marge

La distance d’un point à l’hyperplan est :

L’hyperplan optimal est celui pour lequel la

distance aux points les plus proches est

maximale. La marge entre les deux classes

vaut

Maximiser la marge revient donc à minimiser ||

w|| sous contraintes:

2

w

w

xwx

bd

. )(

1 ).( min

2

2

1

by ii xwiw

28

SVMs : un problème d’optimisation quadratique

Il faut donc déterminer w et b minimisant :

(afin de maximiser le pouvoir de généralisation)

sous les contraintes (hyperplan séparateur) :

2

21 w

nibyi ,...,1 ,1 ).( ixw

EXPRESSIONPRIMAIRE

29

Résolution de la forme primaire du problème

Il faut régler d + 1 paramètres

Possible quand d est assez petit

avec des méthodes d'optimisation

quadratique

Impossible quand d est grand (> qqs 103)

d : dimension de l’espace d’entrée

30

Transformation du problème d’optimisation

Méthode des multiplicateurs de Lagrange

Problème dual

0

}1).{( ),,(1

2

2

1

i

n

i

iii

i

bbL

ywxww

n

iii

i

n

i

n

i

n

jjijijii

yi

yy

1

1 1 1

0 0

).(max2

1

xx

EXPRESSIONDUALE

31

Propriétés de la forme duale

La conversion est possible car les fonctions de

coût et les contraintes sont strictement convexes

(Th. de Kuhn-Tucker)

La complexité du problème d'optimisation est

n (taille de l'échantillon d'apprentissage)

et non d ( taille de l'espace d'entrée X )

Possible d'obtenir des solutions pour des problèmes

impliquant ≈ 105 exemples

32

Solution du problème d’optimisation

Propriété1 : seuls les i correspondant aux points

les plus proches sont non-nuls. On parle de points points

de supportde support (exemples critiques).

Propriété 2 : seuls interviennent les produits produits

scalaires scalaires entre les observations entre les observations xx dans le problème

d’optimisation.

* : estimé

(xS,yS) étant n'importe quel

point de support

m

i

siiis

m

i

iii

yyw

y

bD

1

**0

1

**

**

).(

).( )(

xx

xw

xwx

33

Problème Non Linéaire

34

Problèmes non linéairement séparables dans X

La majorité des problèmes !!!

Idée :

Si on projette dans un espace de redescription projette dans un espace de redescription

de très grande dimensionde très grande dimension ??

Presque toujours le problème devient linéairement

séparable

Mais : Fléau de la dimensionalitédVC explose !!?

35

Problème Non Linéaire

36

Problème Non Linéaire

37From Gert Lanckriet, Statistical Learning Theory Tutorial

Problème Non Linéaire

Fonctions noyauUne famille d'algorithms non linéaires Transforme un problème non linéaire en un problème linéaire (dans un espace de traits différents)Utilise algorithmes linéaires pour résoudre un problème linéaire dans le nouvel espace

38

Intuition principale des fonctions noyau

66 pièces de Corneille et Molière dans espace des 25 étiquettes grammaticales => mieux séparées dans espace des similarités entre pièces (dimension 66)

39From Gert Lanckriet, Statistical Learning Theory Tutorial

X=[x z]

Principe de méthodes à base de fonctions noyau

: Rd RD (D >> d)

(X)=[x2 z2 xz]

f(x) = signe(w1x2+w2z2+w3xz +b)

wT(x)+b=0

40

Principe de base méthodes noyaux

On peut utiliser les algorithmes linéaires vus auparavant (Perceptron, SVM) pour la classification dans un espace de plus grande dimension

41

Le nouveau problème d’optimisation

Soit : X -> (X), on peut remplacer partout x

par (x)

Si est bien choisie, K(x, x’) = (x).(x’) peut

être facile à calculer et le problème devient :

n

i

ii

i

n

i

n

i

n

j

jijijii

y

Ci

Kyy

1

1 1 1

0

0

),(max2

1

xx

42

Solution du nouveau problème d’optimisation

La fonction de décision devient :

Soit dans la forme duale :

D(x) w j g j(x)j1

n

n : nb de fcts

de base(peut être très grand)

bKyDSm

i

iii ),( )(1

xxx mS : nb de points de support

43

Schéma de fonctionnement des SVMs

K K K K

1 2 3

4

Sortie :

Comparaison : K(xi, x)

Échantillon x1, x2, x3, ...

Vecteur d'entrée x

sign(i ui K(xi,x) + w0)

sign(i ui K(xi,x) + w0)

44

Les conditions de Mercer

Si on prend une fonction K symétrique, il existe une fonction :

ssi, pour toute fonction f telle que :

l’on a :

Si cette condition est vérifiée, on peut appliquer les SVMs

MAIS cela ne dit pas comment construire

K(x , x' ) ( x).(x' ) gi (x). gi (x' )i1

m

f (x )2 dx est finieK (x, x' ) f (x ) f (x' ) dx dx' 0

45

Fonctions noyau usuelles (1/2)

Polynomiale :Les polynomes de degré q ont pour fonction noyau

associée :

RBF :

Les fcts à base radiale :

ont pour fct noyau associée :

Sigmoïde :Les réseaux de neurones à fcts d'activation :ont pour fct noyau associée :

K(x, x' ) (x . x' 1)q

K(x, x' ) e

x x' 2

2 2

K(x , x' ) tanh (ax . x' b )

h(x) sign i exp x xi

2

2

i1

n

h(x) sign i tanh v(x.xi) a bi1

n

46

Les fonctions noyau… encodent :

Une mesure de similarité sur les données

La forme fonctionnelle des fonctions de décision

Le type de régularisation réalisée

– (ex : les fcts gaussiennes favorisent les solutions régulières)

Le type de covariance dans l’espace des entrées

– (ex : fcts noyau invariantes par rotation)

Sorte de distribution de probabilité a priori sur l’espace des hypothèses

47

Cas du problème non séparable : marges douces

On introduit des variables “ressort” qui pénalisent l’erreur commise :

Le problème dual a la même forme à l’exception d’une constante C

n

i

ii

i

n

i

n

i

n

j

jijijii

y

Ci

yy

1

1 1 1

0

0

).(max2

1

xx

i

l

i

i

by

C

1 ).(

min1

2

2

1

ii xwi

w

48

Réalisations

49

La mise en pratiqueIl faut choisir :

Le type de fonction noyau K

– Sa forme

– Ses paramètres

La valeur de la constante C

La sélection rigoureuse de ces paramètres exige une estimation de la dimension de Vapnik-Chervonenkis et l’application de la borne de généralisation

Dans le cas séparable, il est possible de déterminer ces paramètresDans le cas non séparable, il faut tester avec des méthodes empiriques pour faire le meilleur choix

50

Exemple : données d'apprentissage

51

Effet des paramètres de contrôle

Apprentissage de deux classes

exemples tirés uniformément sur l'échiquier

SVM à fonctions noyau gaussienne

Ici deux valeurs de En haut : petite valeurEn bas : grande valeur

Les gros points sont des exemples critiques

Plus en haut qu'en bas

Dans les deux cas : Remp = 0

K(x, x' ) e

x x' 2

2 2

52

Paramètres de contrôle : les fonctions noyau

http://svm.dcs.rhbnc.ac.uk/pagesnew/GPat.shtml 47 exemples (22 +, 25 -)Exemples critiques : 4 + et 3 -Ici fonction polynomiale de degré 5 et C = 10000

53

Paramètres de contrôle : les fonctions noyau

47 exemples (22 +, 25 -)Exemples critiques : 4 + et 3 -

Ici fonction polynomiale de degré 2, 5, 8 et C = 10000

Ici fonction Gaussienne de = 2, 5, 10, 20 et C = 10000

(4-, 5+)(8-, 6+)(10-, 11+)

(5-, 4+) (3-, 4+) (5-, 4+)

54

Ajout de quelques points ...

http://svm.dcs.rhbnc.ac.uk/pagesnew/GPat.shtml 47 + 8 exemples (30 +, 25 -)Exemples critiques : 5 + et 8 -Ici fonction polynomiale de degré 5 et C = 10000

55

Exemples à voir sur :

Démo :http://svm.research.bell-labs.com/

http://svm.dcs.rhbnc.ac.uk/pagesnew/GPat.shtml

56

Domaines d’application des SVMs

Traitement d’images

– Reconnaissance de caractères manuscrits– Reconnaissance de scènes naturelles– Reconnaissance de visages

Entrées : image bidimensionnelle en couleur ou en niveaux de grisSortie : classe (chiffre / personne)

57

Domaines d’application des SVMs

Catégorisation de textes

– Classification d’e-mails– Classification de pages web

Entrées : document (texte ou html)– Approche « sac de mots »– Document = vecteur de mots (lemmatisés pondérés par tf-

idf) Sortie : catégorie (thème, spam/non-spam)Noyau :

– Produit scalaire des vecteurs– C = (marge dure)

58

Domaines d’application des SVMs

Diagnostic médical

– Évaluation du risque de cancer– Détection d’arythmie cardiaque– Évaluation du risque d’accidents cardio-vasculaires

à moins de 6 ans

Entrées : état du patient (sexe, age, bilan sanguin, …)Sortie :

– Classe : à risque ou non– Probabilité d’accident à échéance donnée

59

Domaines d’application des SVMs

Étude de séquences en bio-informatique

– Biologie structurale prédictive (prédiction de structure secondaire du génome)

– Identification de régions codantes de l’ADN génomique– Phylogénie …

Entrées : chaînes d’acides aminéesSortie :

– Structure secondaire– Intron / exon– Ancêtre

Noyau relationnel : – Modèle génératif

(chaînes de Markov : insertion, délétion, remplacement, …)

60

Implémentation des SVMs

Minimisation de fonctions différentiables convexes à plusieurs variables

Pas d’optima locauxMais :

– Problèmes de stockage de la matrice noyau (si milliers d’exemples)

– Long dans ce cas

D’où mise au point de méthodes spécifiques– Gradient sophistiqué– Méthodes itératives, optimisation par morceaux

Plusieurs packages publics disponibles– mySVM– SVMTorch– SVMLight – SMO– …

61

Pourquoi ça marche ?

La marge est liée à la capacité en généralisation

Normalement, la classe des hyperplans de Rd est de dH = d + 1

Mais la classe des hyperplans de marge

est bornée par : dH ≤ Min (R2 c, d) + 1

où R est le rayon de la plus petite sphère englobant

l'échantillon d'apprentissage S

Peut être beaucoup plus petit que la dimension d de l'espace d'entrée X

1

w tq. w

2 c

62

BilanSVMs très utilisés

Méthode générale

Facile d’emploi

Résultats en général équivalents et souvent meilleurs

Stimulent tout un ensemble de travaux sur des méthodes à base de noyaux (kernel-based methods)

Limites

Problèmes i.i.d. (données indépendantes et identiquement distribuées)

63

Sources documentaires

Ouvrages / articlesCornuéjols & Miclet (02) : Apprentisage artificiel. Concepts et algorithmes. Eyrolles, 2002.Cristianini & Shawe-Taylor (00) : Support Vector Machines and other kernel-based learning methods. Cambridge University Press, 2000.Herbrich (02) : Learning kernel classifiers. MIT Press, 2002.Schölkopf, Burges & Smola (eds) (98) : Advances in Kernel Methods : Support Vector Learning. MIT Press, 1998.Schölkopf & Smola (02) : Learning with kernels. MIT Press, 2002.Smola, Bartlett, Schölkopf & Schuurmans (00) : Advances in large margin classifiers. MIT Press, 2000.Vapnik (95) : The nature of statistical learning. Springer-Verlag, 1995.

Sites webhttp://www.kernel-machines.org/ (point d’entrée)http://www.support-vector.net (point d’entrée)