Les machines à noyaux et leur mise en œuvre
41
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
41
pages
Français
Ebook
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Les machines à noyaux et leur mise en œuvre
le9novembre2007
GroupedetravailECAIS
StéphaneCanu
stephane.canu@litislab.eu L’apprentissagestatistique Lesoutils Interpolation noyauetparcimonie miseenœuvre Conclusion
Plan
1 L’apprentissage statistique
2 Les outils
3 Les méthodes à noyau non parcimonieuses
4 Les méthodes à noyau parcimonieuses
5 Aspects pratiques liés à la mise en œuvre des machines à
noyaux
6 Conclusion L’apprentissagestatistique Lesoutils Interpolation noyauetparcimonie miseenœuvre Conclusion
OCR : Base de données MNIST
Example (Base de données MNIST)
1I La base de donnée MNIST , données = couples
« imagette-étiquette »
I n = 60:000;d = 700;nbclasses = 10
I noyaux : taux d’erreur = 0,56 %,
I meilleur résultat = 0,4 % d’erreur).
7 8 7 9
1http://yann.lecun.com/exdb/mnist/index.html
Figure: Exemple d’imagettes pour la reconnaissance automatique de chiffres. L’apprentissagestatistique Lesoutils Interpolation noyauetparcimonie miseenœuvre Conclusion
deux autres exemples
Example (Base de données RCV 1)
2La base de données catégorisation, disponible en ligne , contient un
ensemble de textes chacun associé à plusieurs catégories. Cette base
contient 800.000 textes associés à plus d’un millier de catégories. Sur
cette base on peut, soit essayer de retrouver les catégories d’un document
(discrimination multiclasses), soit proposer une nouvelle hiérarchie de
classement des documents (classification automatique)
Example (Base de donnéescensus-house)
Cette base de données ...
Voir
le9novembre2007
GroupedetravailECAIS
StéphaneCanu
stephane.canu@litislab.eu L’apprentissagestatistique Lesoutils Interpolation noyauetparcimonie miseenœuvre Conclusion
Plan
1 L’apprentissage statistique
2 Les outils
3 Les méthodes à noyau non parcimonieuses
4 Les méthodes à noyau parcimonieuses
5 Aspects pratiques liés à la mise en œuvre des machines à
noyaux
6 Conclusion L’apprentissagestatistique Lesoutils Interpolation noyauetparcimonie miseenœuvre Conclusion
OCR : Base de données MNIST
Example (Base de données MNIST)
1I La base de donnée MNIST , données = couples
« imagette-étiquette »
I n = 60:000;d = 700;nbclasses = 10
I noyaux : taux d’erreur = 0,56 %,
I meilleur résultat = 0,4 % d’erreur).
7 8 7 9
1http://yann.lecun.com/exdb/mnist/index.html
Figure: Exemple d’imagettes pour la reconnaissance automatique de chiffres. L’apprentissagestatistique Lesoutils Interpolation noyauetparcimonie miseenœuvre Conclusion
deux autres exemples
Example (Base de données RCV 1)
2La base de données catégorisation, disponible en ligne , contient un
ensemble de textes chacun associé à plusieurs catégories. Cette base
contient 800.000 textes associés à plus d’un millier de catégories. Sur
cette base on peut, soit essayer de retrouver les catégories d’un document
(discrimination multiclasses), soit proposer une nouvelle hiérarchie de
classement des documents (classification automatique)
Example (Base de donnéescensus-house)
Cette base de données ...
Les machines à noyaux et leur mise en œuvre
le 9 novembre 2007 Groupe de travail ECAIS
Stéphane Canu stephane.canu@litislab.eu
1
2
3
4
L’apprentissage statistique
Plan
Les outils
Interpolation
L’apprentissage statistique
Les outils
noyau et parcimonie
Les méthodes à noyau non parcimonieuses
Les méthodes à noyau parcimonieuses
mise en œuvre
5Aspects pratiques liés à la mise en œuvre des machines à noyaux
6
Conclusion
Conclusion
Conclusion
La base de donnée MNIST1, données = couples « imagette-étiquette » n=60.000,d=700,nbclasses=10 noyaux : taux d’erreur = 0,56 %, meilleur résultat = 0,4 % d’erreur).
Example (Base de données MNIST)
I
noyau et parcimonie
I
Les outils
Interpolation
OCR : Base de données MNIST
L’apprentissage statistique
I
mise en œuvre
I
L’apprentissage statistique
Les outils
Interpolation
deux autres exemples
noyau et parcimonie
mise en œuvre
Example (Base de données RCV 1) La base de données catégorisation, disponible en ligne2, contient un ensemble de textes chacun associé à plusieurs catégories. Cette base contient 800.000 textes associés à plus d’un millier de catégories. Sur cette base on peut, soit essayer de retrouver les catégories d’un document (discrimination multiclasses), soit proposer une nouvelle hiérarchie de classement des documents (classification automatique)
Example (Base de donnéescensus-house) Cette base de données a été construite à partir du recensement de 1990 aux Etats Unis. Elle contient 22 784 cas avec chacun 139 variables explicatives. La variable à prévoir est le prix médian d’une maison dans un quartier. Le projet DELVE3, disponible sur le site internet de l’université de Toronto, recense un ensemble intéressant de problèmes type.
2//sno1vcrllcotiecs/cestteosru/mer.soceliwviddw.da//wwttp:h 3evd/ta/ade/ud~letoronto./www.cs.th/:ptstesatadlmth.
Conclusion
L’apprentissage statistique
Les outils
le facteur « taille »
Interpolation
noyau et parcimonie
mise en œuvre
Conclusion
L’apprentissage statistique
Notations
Les outils
Interpolation
Ixest le vecteur des variables observées Iyla variable non observée à prévoir. Ix∈Ωle domaine Iy∈ Yle codomaine. Iune fonctionfdeΩsurY Iun critère`
MNIST
RDV 1
census-house
Entrée - Forme DomaineΩ imagettes 28×28 pixels une dépèche Reuters l’ensemble des textes IR139
noyau et parcimonie
Sortie - étiquette CodomaineY {0,1, ...,9} 103 sujets classement Reuters IR
mise en œuvre
Conclusion
Fonction cout`
0/1
0/1 f(x)y2 −
Table:Exemples de domaines d’apprentissage, de codomaines et de fonctions cout.
L’apprentissage statistique
Les outils
Interpolation
apprentissage statistique
noyau et parcimonie
Definition (problème d’apprentissage théorique)
mise en œuvre
SoitΩetYdeux ensembles. SoitPune famille de probabilités sur (Ω,Y). SoitIP(x,y)∈ Pet`une fonction deY × YsurIR. Trouver la fonctionfdeΩsurYminimisantR(f) =IE`(f(X),Y). IPest inconnue on dispose d’un échantillon(xi,yi),i∈[1,n]
Definition (problème d’apprentissage effectif)
Soit(xi,yi)i=1,nun échantillon i.i.d. tiré selon une loiIP∈ P inconnue. ConstruireApour laquelle∀ε >0etδ >0, il existe un entiern0pour lequel∀n≥n0: IPRA(xi,yi)i=1,n−R(f)≥ε≤δ
∀IP∈ P
Conclusion
L’apprentissage statistique
Les outils
machines à noyaux
Definition (machine à noyaux)
Interpolation
noyau et parcimonie
mise en œuvre
n p A(xi,yi)i=1,n(x) =ψXαik(x,xi) +Xβjϕj(x) i=1j=1 αetβ: paramètres à estimer.
Exemples : n A(x) =Xαi(x−xi)3++β0+β1x i=1 A(x) =signeXαiexp−kx−bxik2+β0avecI⊂ {1, ...,n} i∈I IP(y|x) =Z1expXαi1I{y=yi}(x>xi+b)2 i∈I
Conclusion
1
2
3
4
L’apprentissage statistique
Plan
Les outils
Interpolation
L’apprentissage statistique
Les outils
noyau et parcimonie
Les méthodes à noyau non parcimonieuses
Les méthodes à noyau parcimonieuses
mise en œuvre
5Aspects pratiques liés à la mise en œuvre des machines à noyaux
6
Conclusion
Conclusion
L’apprentissage statistique
Les outilsInterpolation
Au début était le noyau...
Definition (Noyau)
noyau et parcimonie
mise en œuvre
une fonctionkde deux variables deΩ×Ωà valeur dansIR.
Definition (Noyau positif)
Un noyauk(s,t)surΩest dit positif s’il est symétrique et si
n n ∀{αi}i=1,n∈IR,∀{xi}i=1,n∈Ω,X Xαiαjk(xi,xj)≥0 i=1j=1
Definition (Matrice de Gram) Soitk(s,t)un noyau positif surΩet(xi)i=1,nune suite de points de Ωappelle matrice de Gram la matrice carrée. On Kde dimensionnet de terme généralKij=k(xi,xj).
Conclusion
L’apprentissage statistique
Les outils
Interpolation
Exemples de noyaux...
type radial radial radial radial
non stat projectif projectif projectif projectif
nom gaussien laplacien rationnel loc. gauss. χ2
polynôme affine cosinus corrélation
noyau et parcimonie
mise en œuvre
k(s,t) exp−br2,r=ks−tk exp(−r/b) 1−rb2r2+brbd2) max0,1−3rexp(− (−r/b),r=Pk(sk−tk)2 exp(s>t)p sk+tk (s>t+b)p s>t/kskktk expkssk>kttk−b
Table:Quelques exemples de noyaux usuels pourΩ =IRd noyaux. Les dépendent d’un paramètre de largeur de bandebqui caractérise l’amplitude de leur zone d’influence.
Conclusion
