Noyau polynomial

En apprentissage automatique, le noyau polynomial est une fonction noyau couramment utilisée avec les machines à vecteurs de support (SVMs) et d'autres modèles à noyaux. Il représente la similarité des vecteurs (échantillons d'apprentissage) dans un espace de degré polynomial plus grand que celui des variables d'origine, ce qui permet un apprentissage de modèles non-linéaires.

Intuitivement, le noyau polynomial ne tient pas compte uniquement des propriétés des échantillons d'entrée afin de déterminer leur similitude, mais aussi des combinaisons de ceux-ci. Dans le contexte de l'analyse de régression, de telles combinaisons sont connues comme les fonctionnalités d'interaction. L'espace caractéristique (implicite) d'un noyau polynomial est équivalent à celui de la régression polynomiale, mais sans l'explosion combinatoire du nombre de paramètres à apprendre. Lorsque les caractéristiques d'entrées sont des valeurs binaires (booléens), alors les caractéristiques correspondent à la conjonction logique des caractéristiques d'entrée[1].

Définition

Pour un polynôme de degré $d$ , le noyau polynomial est défini comme[2] :

K(x,y)=(x^{\mathsf {T}}y+c)^{d}

où $x$ et $y$ sont des vecteurs dans l' espace d'entrée, c'est-à-dire des vecteurs de caractéristiques calculées à partir d'échantillons d'apprentissage ou de test, et $c \geq 0$ est un paramètre libre équilibrant l'influence des termes d'ordre supérieur par rapport aux termes d'ordre inférieur dans le polynôme. Lorsque $c = 0$ , le noyau est appelé homogène[3]. (Un noyau polynomial plus généralisé divise $x T y$ par un paramètre scalaire $a$ spécifié par l'utilisateur.[4])

Comme noyau, $K$ correspond à un produit scalaire dans un espace caractéristique basée sur une certaine application $Φ$ :

K(x,y)=\langle \phi (x),\phi (y)\rangle

La nature de $Φ$ peut être vue à partir d'un exemple. Soit $d = 2$ , nous obtenons donc le cas particulier du noyau quadratique. Après avoir utilisé le théorème multinôme de Newton (deux fois de l'application externe est le théorème du binôme de newton) et le regroupement,

K(x,y)=\left(\sum _{i=1}^{n}x_{i}y_{i}+c\right)^{2}=\sum _{i=1}^{n}\left(x_{i}^{2}\right)\left(y_{i}^{2}\right)+\sum _{i=2}^{n}\sum _{j=1}^{i-1}\left({\sqrt {2}}x_{i}x_{j}\right)\left({\sqrt {2}}y_{i}y_{j}\right)+\sum _{i=1}^{n}\left({\sqrt {2c}}x_{i}\right)\left({\sqrt {2c}}y_{i}\right)+c^{2}

il resulte que la fonctionnalité de l'application est donnée par :

\varphi (x)=\langle x_{n}^{2},\ldots ,x_{1}^{2},{\sqrt {2}}x_{n}x_{n-1},\ldots ,{\sqrt {2}}x_{n}x_{1},{\sqrt {2}}x_{n-1}x_{n-2},\ldots ,{\sqrt {2}}x_{n-1}x_{1},\ldots ,{\sqrt {2}}x_{2}x_{1},{\sqrt {2c}}x_{n},\ldots ,{\sqrt {2c}}x_{1},c\rangle

Utilisation pratique

Bien que le noyau RBF soit plus populaire dans la classification SVM que le noyau polynomial, ce dernier est très populaire dans le traitement automatique du langage naturel (NLP)[1]^,[5]. Le degré le plus commun est $d = 2$ (quadratique), car les grands degrés tendent à surapprendre sur les problèmes de NLP.

Différentes manières de calculer le noyau polynomial (à la fois exacte et approchée) ont été conçues comme des alternatives à l'usage des algorithmes de formation SVM non-linéaire, y compris :

la pleine expansion du noyau avant l'apprentissage/test avec un SVM linéaire[5], c'est-à-dire le calcul complet de l'application $Φ$ comme dans la régression polynomiale ;
Règle d'association (à l'aide d'une variante de l'algorithme apriori) pour les plus fréquentes conjonctions de fonctionnalité en un ensemble de formation afin de produire une évaluation approximative de l'expansion[6] ;
Index inversé des vecteurs de support[6]^,[1].

Un problème avec le noyau polynomial est qu'il peut souffrir d'instabilité numérique : lorsque $x T y + c < 1, K (x, y) = (x T y + c) d$ tend vers zéro avec l'augmentation de $d$ , alors que quand $x T y + c > 1, K (x, y)$ tend vers l'infini[4].

Références

Yoav Goldberg and Michael Elhadad (2008). splitSVM: Fast, Space-Efficient, non-Heuristic, Polynomial Kernel Computation for NLP Applications. Proc. ACL-08: HLT.
http://www.cs.tufts.edu/~roni/Teaching/CLT/LN/lecture18.pdf
(en) Auteur inconnu « Introduction to Machine Learning: Class Notes 67577 », 2009.
(en) Chih-Jen Lin (2012). « Machine learning software: design and practical use » dans Machine Learning Summer School .
(en) Yin-Wen Chang, Cho-Jui Hsieh, Kai-Wei Chang, Michael Ringgaard et Chih-Jen Lin, « Training and testing low-degree polynomial data mappings via linear SVM », Journal of Machine Learning Research, vol. 11,‎ 2010, p. 1471–1490 (lire en ligne)
(en) T. Kudo et Y. Matsumoto (2003) « Fast methods for kernel-based text analysis » dans Proc. ACL .

Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[Goldberg2008-1] Yoav Goldberg and Michael Elhadad (2008). splitSVM: Fast, Space-Efficient, non-Heuristic, Polynomial Kernel Computation for NLP Applications. Proc. ACL-08: HLT.

[2] ttp://www.cs.tufts.edu/~roni/Teaching/CLT/LN/lecture18.pdf

[3] (en) Auteur inconnu « Introduction to Machine Learning: Class Notes 67577 », 2009.

[lin2012-4] (en) Chih-Jen Lin (2012). « Machine learning software: design and practical use » dans Machine Learning Summer School .

[Chang2010-5] (en) Yin-Wen Chang, Cho-Jui Hsieh, Kai-Wei Chang, Michael Ringgaard et Chih-Jen Lin, « Training and testing low-degree polynomial data mappings via linear SVM », Journal of Machine Learning Research, vol. 11,‎ 2010, p. 1471–1490 (lire en ligne)

[Kudo2003-6] (en) T. Kudo et Y. Matsumoto (2003) « Fast methods for kernel-based text analysis » dans Proc. ACL .