Alors bien sur différentes approches sont envisageables comme de faire une linéarisation par partie (c’est à dire construire un découpage dans lequel les données sur ces segments peuvent etre reduites à une droite) mais la solution la plus efficace est encore l’emploi du kernel trick.
À la base, la question est simple: si le SVM est efficace sur un domaine linéaire alors est il possible de transformer d’une manière ou d’une autre des données non linéaire en données linéaires?
Bien sûr vous allez dire oui, sinon on ne serait pas la… et oui c’est ce que va nous permettre d’une certaine manière le kernel trick, pas juste en cherchant à retrouver de la linéarité dans les données mais en ajoutant des dimensions supplémentaires à ces données [2].
Comment ca des dimensions supplémentaire? oui oui car de l’idée de l’astuce du noyau est formellement de chercher à définir une fonction sur nos données dont l’espace cible sera plus grand que celui initial.
Bizarre? non, mais illustrons l’idée avec la suite.
Dans ce cas, on remarquera que l’ensemble qui nous intéresse est autour de zéro alors que les autres sont aux extrêmes… Si l’on veut user d’un changement de dimension, il nous faut ajouter une nouvelle composante. mais nous avons que x, comment obtenir un y?
Très simple, passons x au carré et disons que ca sera la valeur de y! Ainsi, on obtient des données en fonction de leur distance à zéro sur un axe y tout en les gardant avec la même valeur sur l’axe x. LATEX Cela aboutit à la transformation suivante:
À la base, la question est simple: si le SVM est efficace sur un domaine linéaire alors est il possible de transformer d’une manière ou d’une autre des données non linéaire en données linéaires?
Bien sûr vous allez dire oui, sinon on ne serait pas la… et oui c’est ce que va nous permettre d’une certaine manière le kernel trick, pas juste en cherchant à retrouver de la linéarité dans les données mais en ajoutant des dimensions supplémentaires à ces données [2].
Comment ca des dimensions supplémentaire? oui oui car de l’idée de l’astuce du noyau est formellement de chercher à définir une fonction sur nos données dont l’espace cible sera plus grand que celui initial.
Bizarre? non, mais illustrons l’idée avec la suite.
Le cas simple (très utilisé)
Le premier exemple est basique dans la littérature. Il s’agit de considérer des données de deux types différents répartis sur une même droite. Cela ressemble à cela:fig=plt.figure(1,figsize=(8,8)) nbrEl=20 front=5 f=0 plt.plot(np.linspace(-10,-front-1,nbrEl),[f for x in np.linspace(-10,-front-1,nbrEl)],"b.") plt.plot(np.linspace(-front,front,nbrEl),[f for x in np.linspace(-front,front,nbrEl)],"r.") plt.plot(np.linspace(front+1,10,nbrEl),[f for x in np.linspace(front+1,10,nbrEl)],"b.")
Dans ce cas, on remarquera que l’ensemble qui nous intéresse est autour de zéro alors que les autres sont aux extrêmes… Si l’on veut user d’un changement de dimension, il nous faut ajouter une nouvelle composante. mais nous avons que x, comment obtenir un y?
Très simple, passons x au carré et disons que ca sera la valeur de y! Ainsi, on obtient des données en fonction de leur distance à zéro sur un axe y tout en les gardant avec la même valeur sur l’axe x. LATEX Cela aboutit à la transformation suivante:
fig=plt.figure(1,figsize=(8,8)) nbrEl=20 f=lambda x: math.pow(x,2) plt.plot(np.linspace(-10,-front-1,nbrEl),[f(x) for x in np.linspace(-10,-front-1,nbrEl)],"b.") plt.plot(np.linspace(-front,front,nbrEl),[f(x) for x in np.linspace(-front,front,nbrEl)],"r.") plt.plot(np.linspace(front+1,10,nbrEl),[f(x) for x in np.linspace(front+1,10,nbrEl)],"b.")
Nous obtenons alors donc des données en dimension 2 tels que :
Et donc dans le cadre du SVC (SVM pour la classification), il est evident que l’on pourra tirer une droite séparatrice par exemple en y=30 et résoudre le problème de classification.
Ce cas est le cas simple [3] où l’on passe d’un espace de dimension 1 à 2. Que serait ce même cas en 2 dimensions?
Comme illustré par l’image précédente, si on doit séparer ce qui est dans le cercle de ce qui est en dehors, on à un gros problème …. pas de linéarité possible ici! (À noter les deux droites ajoutées dans l’images vont nous servir de mire pour comprendre la déformation appliquée à l’espace mais elles ne correspondent pas à des données particulières liées à l’exemple)
Et donc dans le cadre du SVC (SVM pour la classification), il est evident que l’on pourra tirer une droite séparatrice par exemple en y=30 et résoudre le problème de classification.
Ce cas est le cas simple [3] où l’on passe d’un espace de dimension 1 à 2. Que serait ce même cas en 2 dimensions?
Extension du cas simple
Lorsque l’on est en dimension 2 on peut souvent se retrouver avec un problème de classification dans lequel l’une des classes de données est inscrite dans un cercle. Pour illustrer cela, on considérera comme exemple directement la frontière que l’on souhaiterait linéariser.zline = np.linspace(0, 15, 100) X = np.sin(zline) Y = np.cos(zline) single= np.linspace(-1, 1, 40) singlerev= np.linspace(1, -1, 40) Xsingle=single Ysingle=single Xrev=single Yrev=singlerev fig=plt.figure(1,figsize=(8,8)) plt.plot(X,Y,"b.") plt.plot(Xsingle,Ysingle,"r.") plt.plot(Xrev,Yrev,"g.")
Comme illustré par l’image précédente, si on doit séparer ce qui est dans le cercle de ce qui est en dehors, on à un gros problème …. pas de linéarité possible ici! (À noter les deux droites ajoutées dans l’images vont nous servir de mire pour comprendre la déformation appliquée à l’espace mais elles ne correspondent pas à des données particulières liées à l’exemple)
Bien nous avons vu dans l’exemple précédent, qu’il suffisait d’augmenter le nombre de dimension pour faire apparaître des linéarités (enfin une au moins ca sera bien).
Ne sachant pas à priori quels sont les transformations qui seront adéquat, en plus de x et y, on propose du coup de construire les composantes supplémentaire suivantes: x², y² ou x*y.
On a donc maintenant un ensemble de données sur 5 dimensions: (x,y,x², y² ,x*y) alors attention, rien ne dit que la solution soit un hyperplan de dimensions 5, cela peut aussi être un plan défini en 3 dimensions:
Dans ce cas par exemple, ce n’est pas forcément très explicite cependant si on prend la représentation suivante, on voit que la partie interne du cercle est partie d’un côté du plan dans lequel se trouve le cercle et que la partie externe est de l’autre (un peu comme dans le cas précédent)
En fait, dans ce cas, nous ne sommes pas obligé de changer le nombre de dimension mais plutot de “juste” choisir le bon espace 2D, comme suit:
Il n’est clairement pas simple de choisir le nombre de dimension utile ni lesquelles seront à joindre pour être pertinentes. Ce qu’il faut retenir c’est que malgré tout, par l’augmentation des dimensions, les algorithmes de régression ou de classification auront plus de moyen pour trouver un hyperplan.
Encore un exemple?
Du coup comme pour les cas precedent, on va appliquer un noyau pour changer le nombre de dimensions:
Ne sachant pas à priori quels sont les transformations qui seront adéquat, en plus de x et y, on propose du coup de construire les composantes supplémentaire suivantes: x², y² ou x*y.
def Kernel4Circle(xdat,ydat): X=[] Y=[] Z=[] for (x,y) in zip(xdat,ydat): X=X+[x*x] Y=Y+[y*y] Z=Z+[math.sqrt(2)*x*y] return (X,Y,Z) (A,B,C)=Kernel4Circle(X,Y) (Asingle,Bsingle,Csingle)=Kernel4Circle(Xsingle,Ysingle) (Arev,Brev,Crev)=Kernel4Circle(Xrev,Yrev)
On a donc maintenant un ensemble de données sur 5 dimensions: (x,y,x², y² ,x*y) alors attention, rien ne dit que la solution soit un hyperplan de dimensions 5, cela peut aussi être un plan défini en 3 dimensions:
plt.figure(2,figsize=(10,10)) ax = plt.axes(projection='3d') plt.plot(A,B,C,"b.") plt.plot(Asingle,Bsingle,Csingle,"r.") plt.plot(Arev,Brev,Crev,"g.") ax.view_init(0,45)
Dans ce cas par exemple, ce n’est pas forcément très explicite cependant si on prend la représentation suivante, on voit que la partie interne du cercle est partie d’un côté du plan dans lequel se trouve le cercle et que la partie externe est de l’autre (un peu comme dans le cas précédent)
fig = plt.figure(1,figsize=(10,10)) ax = fig.add_subplot(111, projection='3d') plt.plot(A,B,C,"b.") plt.plot(Asingle,Bsingle,Csingle,"r.") plt.plot(Arev,Brev,Crev,"g.") ax.view_init(0,135)
En fait, dans ce cas, nous ne sommes pas obligé de changer le nombre de dimension mais plutot de “juste” choisir le bon espace 2D, comme suit:
Il n’est clairement pas simple de choisir le nombre de dimension utile ni lesquelles seront à joindre pour être pertinentes. Ce qu’il faut retenir c’est que malgré tout, par l’augmentation des dimensions, les algorithmes de régression ou de classification auront plus de moyen pour trouver un hyperplan.
Encore un exemple?
Le cas non linéaire classique
Prenons le cas une fonction non linéaire comme nous en avions parlé dans l’article [4]. LATEX Comme pour le cercle, nous allons ajouter des données mais ici de chaque côté de la frontière (on se placera dans le cadre d’un problème de classification) comme suit:Xin=np.linspace(-10,10,100) Yin=[2*math.pow(x,2)-5*x+1 for x in Xin] Xsingle=np.linspace(00, 0, 40) Ysingle=[x*25 for x in np.linspace(-10, 0, 40)] Xrev=np.linspace(00, 0, 40) Yrev=[x*25 for x in np.linspace(10, 0, 40)] plt.figure(1,figsize=(8,8)) plt.plot(Xin,Yin,"b.") plt.plot(Xsingle,Ysingle,"r.") plt.plot(Xrev,Yrev,"g.")
Du coup comme pour les cas precedent, on va appliquer un noyau pour changer le nombre de dimensions:
def Kernel4XSquare(xdat,ydat): X=[] Y=[] Z=[] U=[] V=[] for (x,y) in zip(xdat,ydat): X=X+[x] Y=Y+[y] Z=Z+[x*x] U=U+[math.sqrt(2)*y*x] V=V+[y*y] return (X,Y,Z,U,V) (X,Y,Z,U,V)=Kernel4XSquare(Xin,Yin) (Xs,Ys,Zs,Us,Vs)=Kernel4XSquare(Xsingle,Ysingle) (Xr,Yr,Zr,Ur,Vr)=Kernel4XSquare(Xrev,Yrev)
Du coup en choisissant bien les axes à exploiter, on voit que les deux ensembles deviennent séparable et qu’un algo de classification linéaire parviendra à retrouver ses petits:
angleBase=-100 altitude=30 fig = plt.figure(1,figsize=(15,15)) ax = plt.subplot(211, projection='3d')# equivalent a fig.addsubplot plt.plot(X,Y,Z,"b.") plt.plot(Xs,Ys,Zs,"r.") plt.plot(Xr,Yr,Zr,"g.") ax.view_init(altitude,angleBase) ax.set_title('x,y,x^2'); ax = plt.subplot(212, projection='3d')# equivalent a fig.addsubplot plt.plot(X,Y,V,"b.") plt.plot(Xs,Ys,Vs,"r.") plt.plot(Xr,Yr,Vr,"g.") ax.view_init(altitude,angleBase) ax.set_title('x,y,y^2');
Kernel Trick
C’est bien beau tout ca mais au final, c’est quoi le rapport avec le kernel trick?Ce que nous venons de voir est qu’il est possible de transformer l’espace initial des données vers un nouvel espace de définition où il est possible de trouver des relations de linéarité et donc d’appliquer des algo ne fonctionnant que sur des jeux de données ayant ces propriétés.
Dans le concret, nous avons donc une fonction de la forme: LATEX Et cette fonction est utilisable en lieu et place des données d’entrées dans par exemple la formule duale. Celle ci devient donc: LATEX Du coup on voit que l’on peut si on connaît bien phi, appliquer notre algo de machine learning. Pourtant il y à un hic… c’est que nous avons vu que pour trouver les linéarités, généralement, on augmente le nombre de dimension et la c’est problematique pour le produit scalaire qui va vite devenir incalculable.
Pour résoudre ce problème, on va alors appliquer l’astuce du noyau.
Celui ci consiste à considérer que le produit scalaire des fonctions de transformations est équivalent d’une fonction K prenant en paramètre nos données initiales. En gros: LATEX L'intérêt de K est que celui-ci s’il respecte les mêmes propriétés que le produit scalaire alors il peut nous permettre (faute d’en trouver une définition adéquate) de linéariser nos données au même titre que la fonction phi comme nous le faisions dans les exemples précédents.
À ce titre, il est même possible de calculer après coup la fonction K.
Par exemple si l’on reprend le cas du cercle, nous avions choisi comme fonction de redescription la fonction comme suit: LATEX Ainsi on peut en déduire K: LATEX Correspondant alors à utiliser un noyau polynomial.
Ce qu’il faut bien comprendre à ce stade est que ici nous avons réalisé une déduction du noyau à partir d’une fonction phi que nous avions pre-déterminé comme fonctionnant pour linéariser les données. Mais en fait, l’astuce du noyau est justement de ne pas faire cela et d’utiliser directement un noyau sans en connaître à priori la fonction phi.
Alors bien sur sachant qu une fonction phi efficace dans la linéarisation est complètement conditionné par la nature des données initiales, il en va de même pour le noyau.
Ainsi selon les données d’entrée, il faudra choisir un modèle de noyau adapté capable de rendre compte des même propriétés que le produit scalaire des données d'entrées sur lesquelles on applique une fonction de redescription.
Heureusement pour nous faciliter la vie, un certain nombre de noyau prédéfini on été élaboré et généralisé. Ainsi si tout à l’heure nous avons construit un noyau polynomial, il en existe d’autres comme le linéaire, polynomial, gaussien, exponentiel, laplacien, etc [5].
Nous ne les détaillerons pas ici car cela n'a pas d'intérêt.
Références
[1] https://un-est-tout-et-tout-est-un.blogspot.com/2018/12/ia-classification-svc-avec-scikit-learn.html[2] https://zestedesavoir.com/tutoriels/1760/un-peu-de-machine-learning-avec-les-svm/#5-systemes-non-lineaires--astuce-du-noyau
[3] https://towardsdatascience.com/the-kernel-trick-c98cdbcaeb3f
[4] https://un-est-tout-et-tout-est-un.blogspot.com/2019/04/math-linearite-or-not-linearite.html
[5] http://crsouza.com/2010/03/17/kernel-functions-for-machine-learning-applications/
Aucun commentaire:
Enregistrer un commentaire