Méthode à noyau

mcd

Bonjour à tous,

Si j'ai des points dans $\mathbb{R}^{2}$ non linéairement séparable, je vais les projeter dans $\mathbb{R}^{d}$ voir même un espace de Hilbert via une application $\phi$. Une fois dans cette espace les points sont linéairement séparable. Je trace une droite qui les séparent.
Question : Comment en déduire la formule d'une courbe qui a la propriété de séparer mes points dans $\mathbb{R}^{2}$ ?

Merci.

PS : J'ai jamais réussi à trouver de réponse claire sous la formule d'une formule, ce serait top bien si c'est aussi simple que ça.

Chalk

Je ne connais pas de formule close toute faite pour retrouver la courbe de séparation (si ce n'est d'utiliser la définition en terme d'image réciproque mais ça n'apporte rien), et ça tombe bien car on n'en a absolument pas besoin.

Si tu veux vraiment la retrouver algorithmiquement, c'est un problème d'optim pas forcément jolie, sauf à discrétiser tout l'espace $\R^2$ pour trouver une approximation à la résolution près de ta discrétisation.

marsup

Je trace une droite qui les séparent.

Est-ce que c'est plutôt un hyperplan qui les sépare ?

mcd

@Marsup : Oui un hyperplan dans l'espace sur lequel on transporte les points. Merci

mcd

@Chalk : oui j'aimerais le retrouver pour comprendre les algorithmes qui font ce travail. C'est quand même magique de les voir passer dans un hilbert et venir avec un courbe bien sinueuse comme il faut.

mcd

Et du coup comment je peux faire pour comprendre les méthodes à noyaux ? Comprendre je veux dire écrire moi même l'algorithme qui à partir d'un nuage de points de $ \mathbb{R}^{2}$ me renvoi la courbe jolie qui sépare les points.

J'ai essayé de lire plusieurs livres mais je ne vois toujours pas comment écrire cette algorithme.

purple

L'astuce du noyau comme tu l'as dit plus haut consiste à chercher une séparation linéaire dans un nouvel espace, typiquement de dimension plus grande, par une transformation $\phi$ non-linéaire.
Ce que l'astuce du noyau a de si astucieux, c'est qu'on ne cherche jamais à connaître $\phi$, on ne l'a pas à disposition en général et surtout on n'en a pas besoin. En effet : le théorème du représentant nous garantit que dès lors qu'une solution existe au problème d'optimisation d'une SVM, celle-ci est portée par les données.
La solution est de la forme $$\sum_i \alpha_i k(X_i, \cdot),$$ où $k$ est notre noyau.

Pour en venir à une implémentation, on peut montrer que par dualité lagrangienne on se ramène à un problème d'optimisation de la forme :
$$ \textrm{maximiser}_{\alpha} -\frac{1}{2} \alpha^{t}A \alpha + \mathbb{1}^{t}\alpha,
$$ sous les contraintes $\alpha_i \in [0, C]$ et $Y^t \alpha = 0,$
où $A$ est la matrice $(k(X_i, X_j) Y_i Y_j )_{1\leq i , j \leq n}$.

Le gros du problème consistera à résoudre ce problème d'optimisation. L'approche classique est par SMO. Le choix de $C$ est central et dépendra de tes données.
Très concrètement si tu veux tracer ta courbe, tu peux le faire sous matplotlib par exemple avec une grille de discrétisation.

jma

Bonjour,

@mini_calli : je me demande si il n'est pas illusoire de rechercher cette courbe. En utilisant l'astuce des noyaux, on peut classifier deux groupes de points. Ceci étant fait, il est possible de reporter sur le plan les points qui appartiennent à l'une ou à l'autre classe puis de dessiner (la fameuse courbe) "à main levée" la frontière entre les deux classes. Ce n'est qu'une hypothèse.

Cordialement.