J'essaie de comprendre l'intuition derrière les SVM du noyau. Maintenant, je comprends comment fonctionne le SVM linéaire, par lequel une ligne de décision est faite qui divise les données du mieux qu'elle peut. Je comprends également le principe derrière le portage de données vers un espace de dimension supérieure, et comment cela peut faciliter la recherche d'une ligne de décision linéaire dans ce nouvel espace. Ce que je ne comprends pas, c'est comment un noyau est utilisé pour projeter des points de données vers ce nouvel espace.
Ce que je sais d'un noyau, c'est qu'il représente effectivement la "similitude" entre deux points de données. Mais comment cela se rapporte-t-il à la projection?
machine-learning
svm
kernel-trick
Karnivaurus
la source
la source
Réponses:
Soith(x) est la projection à l' espace haute dimension F . Fondamentalement , la fonction noyau K(x1,x2)=⟨h(x1),h(x2)⟩ , qui est le produit scalaire. Il n'est donc pas utilisé pour projeter des points de données, mais plutôt un résultat de la projection. Cela peut être considéré comme une mesure de similitude, mais dans un SVM, c'est plus que cela.
L'optimisation pour trouver le meilleur hyperplan de séparation dansF implique h(x) uniquement via la forme du produit interne. Autrement dit, si vous connaissez K(⋅,⋅) , vous n'avez pas besoin de connaître la forme exacte de h(x) , ce qui facilite l'optimisation.
Chaque noyauK(⋅,⋅) a également un correspondant h(x) . Donc, si vous utilisez un SVM avec ce noyau, vous trouvez implicitement la ligne de décision linéaire dans l'espace dans lequel h(x) mappé.
Le chapitre 12 de Elements of Statistical Learning donne une brève introduction à SVM. Cela donne plus de détails sur la connexion entre le noyau et le mappage de fonctionnalités: http://statweb.stanford.edu/~tibs/ElemStatLearn/
la source
Les propriétés utiles du noyau SVM ne sont pas universelles - elles dépendent du choix du noyau. Pour obtenir l'intuition, il est utile de regarder l'un des noyaux les plus couramment utilisés, le noyau gaussien. Remarquablement, ce noyau transforme SVM en quelque chose de très similaire à un classificateur de voisin k-plus proche.
Cette réponse explique ce qui suit:
1. Atteindre une séparation parfaite
Une séparation parfaite est toujours possible avec un noyau gaussien en raison des propriétés de localisation du noyau, qui conduisent à une frontière de décision arbitrairement flexible. Pour une bande passante du noyau suffisamment petite, la frontière de décision ressemblera à ce que vous venez de dessiner de petits cercles autour des points chaque fois qu'ils sont nécessaires pour séparer les exemples positifs et négatifs:
(Crédit: cours d'apprentissage automatique en ligne d'Andrew Ng ).
Alors, pourquoi cela se produit-il dans une perspective mathématique?
Considérez la configuration standard: vous avez un noyau gaussien et des données d'entraînement ( x ( 1 ) , y ( 1 ) ) , ( x ( 2 ) , y ( 2 ) ) , … , ( x ( n ) ,K(x,z)=exp(−||x−z||2/σ2) où lesvaleurs y ( i ) sont±1. Nous voulons apprendre une fonction de classificateur(x(1),y(1)),(x(2),y(2)),…,(x(n),y(n)) y(i) ±1
Maintenant, comment allons-nous jamais attribuer les poids ? Avons-nous besoin d'espaces de dimension infinie et d'un algorithme de programmation quadratique? Non, parce que je veux juste montrer que je peux parfaitement séparer les points. Je fais donc σ un milliard de fois plus petit que la plus petite séparation | | x ( i ) - x ( j ) | | entre deux exemples de formation, et je viens de définir w i = 1 . Cela signifie que tous les points de formation sont un milliard sigmas en dehors autant que le noyau est concerné, et chaque point contrôle complètement le signe de ywi σ ||x(i)−x(j)|| wi=1 y^ dans son quartier. Formellement, nous avons
où est une valeur arbitrairement minuscule. Nous savons que ϵ est minuscule parce que x ( k ) est à un milliard de sigmas de tout autre point, donc pour tout i ≠ k que nous avonsϵ ϵ x(k) i≠k
Puisque est si petit, y ( x ( k ) ) a certainement le même signe que y ( k )ϵ y^(x(k)) y(k) , et le classificateur permet d' obtenir une précision parfaite sur les données de formation. Dans la pratique, cela serait terriblement surajusté, mais cela montre la formidable flexibilité du noyau gaussien SVM, et comment il peut agir de manière très similaire à un classificateur de voisin le plus proche.
2. Apprentissage SVM du noyau comme séparation linéaire
Le fait que cela puisse être interprété comme une "séparation linéaire parfaite dans un espace d'entités de dimension infinie" vient de l'astuce du noyau, qui vous permet d'interpréter le noyau comme un produit intérieur abstrait d'un nouvel espace d'entités:
où est le mappage de l'espace de données dans l'espace d'entités. Il en résulte immédiatement que la y ( x ) fonction comme une fonction linéaire dans l'espace de caractéristiques:Φ(x) y^(x)
où la fonction linéaire est définie sur les vecteurs d'espace caractéristique v commeL(v) v
Cette fonction est linéaire en car c'est juste une combinaison linéaire de produits internes avec des vecteurs fixes. En l'espace de caractéristiques, la limite de décision y ( x ) = 0 est juste L ( v ) = 0 , le jeu de niveau d'une fonction linéaire. Il s'agit de la définition même d'un hyperplan dans l'espace des fonctionnalités.v y^(x)=0 L(v)=0
3. Comment le noyau est utilisé pour construire l'espace des fonctionnalités
Méthodes du noyau ne fait « trouver » ou « compute » l'espace de fonction ou la mise en correspondance explicitement. Les méthodes d'apprentissage du noyau telles que SVM n'en ont pas besoin pour fonctionner; ils ont seulement besoin de la fonction du noyau K . Il est possible d'écrire une formule pour Φ mais l'espace caractéristique auquel il correspond est assez abstrait et n'est vraiment utilisé que pour prouver des résultats théoriques sur SVM. Si vous êtes toujours intéressé, voici comment cela fonctionne.Φ K Φ
Basically we define an abstract vector spaceV where each vector is a function from X to R . A vector f in V is a function formed from a finite linear combination of kernel slices:
The inner product on the space is not the ordinary dot product, but an abstract inner product based on the kernel:
la source
For the background and the notations I refer to How to calculate decision boundary from support vectors?.
So the features in the 'original' space are the vectorsxi , the binary outcome yi∈{−1,+1} and the Lagrange multipliers are αi .
As said by @Lii (+1) the Kernel can be written asK(x,y)=h(x)⋅h(y) ('⋅ ' represents the inner product.
I will try to give some 'intuitive' explanation of what thish looks like, so this answer is no formal proof, it just wants to give some feeling of how I think that this works. Do not hesitate to correct me if I am wrong.
I have to 'transform' my feature space (so myxi ) into some 'new' feature space in which the linear separation will be solved.
For each observationxi , I define functions ϕi(x)=K(xi,x) , so I have a function ϕi for each element of my training sample. These functions ϕi span a vector space. The vector space spanned by the ϕi , note it V=span(ϕi,i=1,2,…N) .
I will try to argue that is the vector space in which linear separation will be possible. By definition of the span, each vector in the vector spaceV can be written as as a linear combination of the ϕi , i.e.: ∑Ni=1γiϕi , where γi are real numbers.
The transformation, that maps my original feature space toV is defined as
This mapΦ maps my original feature space onto a vector space that can have a dimension that goed up to the size of my training sample.
Obviously, this transformation (a) depends on the kernel, (b) depends on the valuesxi in the training sample and (c) can, depending on my kernel, have a dimension that goes up to the size of my training sample and (d) the vectors of V look like ∑Ni=1γiϕi , where γi , γi are real numbers.
Looking at the functionf(x) in How to calculate decision boundary from support vectors? it can be seen that f(x)=∑iyiαiϕi(x)+b .
In other words,f(x) is a linear combination of the ϕi and this is a linear separator in the V-space : it is a particular choice of the γi namely γi=αiyi !
Theyi are known from our observations, the αi are the Lagrange multipliers that the SVM has found. In other words SVM find, through the use of a kernel and by solving a quadratic programming problem, a linear separation in the V -spave.
This is my intuitive understanding of how the 'kernel trick' allows one to 'implicitly' transform the original feature space into a new feature spaceV , with a different dimension. This dimension depends on the kernel you use and for the RBF kernel this dimension can go up to the size of the training sample.
So kernels are a technique that allows SVM to transform your feature space , see also What makes the Gaussian kernel so magical for PCA, and also in general?
la source
Permettez-moi de l'expliquer. L'astuce du noyau est la clé ici. Considérons ici le cas d'un noyau RBF (Radial Basis Function). Il transforme l'entrée en espace de dimension infinie. La transformation de l'entréeX à ϕ ( x ) peut être représenté comme indiqué ci-dessous (extrait de http://www.csie.ntu.edu.tw/~cjlin/talks/kuleuven_svm.pdf )
L'espace d'entrée est de dimension finie mais l'espace transformé est de dimension infinie. Transformer l'entrée en un espace de dimension infinie est quelque chose qui se produit à la suite de l'astuce du noyau. IciX which is the input and ϕ is the transformed input. But ϕ is not computed as it is, instead the product ϕ(xi)Tϕ(x) is computed which is just the exponential of the norm between xi and x .
There is a related question Feature map for the Gaussian kernel to which there is a nice answer /stats//a/69767/86202.
The output or decision function is a function of the kernel matrixK(xi,x)=ϕ(xi)Tϕ(x) and not of the input x or transformed input ϕ directly.
la source
Le mappage vers une dimension supérieure n'est qu'une astuce pour résoudre un problème défini dans la dimension d'origine; des problèmes tels que le surajustement de vos données en entrant dans une dimension avec trop de degrés de liberté ne sont pas un sous-produit du processus de mappage, mais sont inhérents à la définition de votre problème.
Fondamentalement, tout ce que fait le mappage consiste à convertir la classification conditionnelle dans la dimension d'origine en une définition de plan dans la dimension supérieure, et comme il existe une relation 1 à 1 entre le plan dans la dimension supérieure et vos conditions dans la dimension inférieure, vous pouvez toujours se déplacer entre les deux.
En prenant le problème du sur-ajustement, vous pouvez clairement suréquiper n'importe quel ensemble d'observations en définissant suffisamment de conditions pour isoler chaque observation dans sa propre classe, ce qui équivaut à mapper vos données sur (n-1) D où n est le nombre de vos observations .
Prendre le problème le plus simple, où vos observations sont [[1, -1], [0,0], [1,1]] [[entité, valeur]], en vous déplaçant dans la dimension 2D et en séparant vos données avec une ligne , vous transformez simplement la classification conditionnelle de
feature < 1 && feature > -1 : 0
en définissant une ligne qui passe(-1 + epsilon, 1 - epsilon)
. Si vous aviez plus de points de données et que vous aviez besoin de plus de conditions, vous deviez simplement ajouter un degré de liberté supplémentaire à votre dimension supérieure à chaque nouvelle condition que vous définissez.You can replace the process of mapping to a higher dimension with any process that provides you with a 1 to 1 relationship between the conditions and the degrees of freedom of your new problem. Kernel tricks simply do that.
la source
[x, floor(sin(x))]
. Mapping your problem into a 2D dimension is not helpful here at all; in fact, mapping to any plane will not be helpful here, which is because defining the problem as a set ofx < a && x > b : z
is not helpful in this case. The simplest mapping in this case is mapping into a polar coordinate, or into the imaginary plane.