Kernel SVM: Je veux une compréhension intuitive de la mise en correspondance avec un espace d'entités de dimension supérieure, et comment cela rend possible la séparation linéaire

15

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?

Karnivaurus
la source
3
Si vous allez dans un espace dimensionnel suffisamment élevé, tous les points de données d'entraînement peuvent être parfaitement séparés par un plan. Cela ne signifie pas qu'il aura un quelconque pouvoir prédictif. Je pense qu'aller dans un espace dimensionnel très élevé est l'équivalent moral (une forme de) de sur-ajustement.
Mark L. Stone
@Mark L. Stone: c'est exact (+1) mais cela peut être une bonne question de se demander comment un noyau peut être mappé dans un espace de dimension infinie? Comment ça marche? J'ai essayé, voir ma réponse
Je ferais attention d'appeler le mappage de fonctionnalité une "projection". Le mappage d'entités est généralement une transformation non linéaire.
Paul
Un article très utile sur l'astuce du noyau visualise l'espace produit interne du noyau et décrit comment les vecteurs de caractéristiques de grande dimension sont utilisés pour y parvenir, j'espère que cela répond à la question de manière concise: eric-kim.net/eric-kim-net/ posts / 1 / kernel_trick.html
JStrahl

Réponses:

6

Soit h(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 dans F 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 noyau K(,) 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/

Lii
la source
voulez-vous dire que pour un noyau K(x,y) il y a un h ( x ) sous-jacent unique ? h(x)
2
@fcoppens No; pour un exemple trivial, considérons h et h . Cependant, il existe un espace Hilbert de noyau de reproduction unique correspondant à ce noyau.
Dougal
@Dougal: Alors je peux être d'accord avec vous, mais dans la réponse ci-dessus, il a été dit "un correspondant h", donc je voulais être sûr. Pour le RKHS je vois, mais pensez-vous qu'il est possible d'expliquer de manière «intuitive» à quoi ressemble cette transformation h pour un Kernel K(x,y) ?
@fcoppens En général, non; il est difficile de trouver des représentations explicites de ces cartes. Pour certains noyaux, ce n'est pas trop difficile ou fait avant, cependant.
Dougal
1
@fcoppens vous avez raison, le h (x) n'est pas unique. Vous pouvez facilement apporter des modifications à h (x) tout en gardant le produit intérieur <h (x), h (x ')> le même. Cependant, vous pouvez les considérer comme des fonctions de base et l'espace qu'elles couvrent (c'est-à-dire le RKHS) est unique.
Lii
4

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. Pourquoi une séparation parfaite des données d'entraînement positives et négatives est toujours possible avec un noyau gaussien de bande passante suffisamment petite (au prix d'un surajustement)
  2. Comment cette séparation peut être interprétée comme linéaire dans un espace d'entités.
  3. Comment le noyau est utilisé pour construire le mappage de l'espace de données à l'espace des fonctionnalités. Spoiler: l'espace caractéristique est un objet très abstrait mathématiquement, avec un produit intérieur abstrait inhabituel basé sur le noyau.

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:

Something like this

(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(||xz||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

y^(x)=iwiy(i)K(x(i),x)

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=1y^dans son quartier. Formellement, nous avons

y^(x(k))=i=1ny(k)K(x(i),x(k))=y(k)K(x(k),x(k))+iky(i)K(x(i),x(k))=y(k)+ϵ

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)ik

K(x(i),x(k))=exp(||x(i)x(k)||2/σ2)0.

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:

K(x(i),x(j))=Φ(x(i)),Φ(x(j))

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)

y^(x)=iwiy(i)Φ(x(i)),Φ(x)=L(Φ(x))

où la fonction linéaire est définie sur les vecteurs d'espace caractéristique v commeL(v)v

L(v)=iwiy(i)Φ(x(i)),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.vy^(x)=0L(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 space V 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:

f(x)=i=1nαiK(x(i),x)
(Here the x(i) are just an arbitrary set of points and need not be the same as the training set.) It is convenient to write f more compactly as
f=i=1nαiKx(i)
where Kx(y)=K(x,y) is a function giving a "slice" of the kernel at x.

The inner product on the space is not the ordinary dot product, but an abstract inner product based on the kernel:

i=1nαiKx(i),j=1nβjKx(j)=i,jαiβjK(x(i),x(j))

Φ(x),Φ(y)=K(x,y).

ΦXVx

Φ(x)=Kx,whereKx(y)=K(x,y).

V is an inner product space when K is a positive definite kernel. See this paper for details.

Paul
la source
Great explanation, but I think you have missed a minus for the definition of the gaussian kernel. K(x,z)=exp(-||x−z||2/σ2) . As it's written, it does not make sense with the ϵ found in the part (1)
hqxortn
1

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 vectors xi, the binary outcome yi{1,+1} and the Lagrange multipliers are αi.

As said by @Lii (+1) the Kernel can be written as K(x,y)=h(x)h(y) ('' represents the inner product.

I will try to give some 'intuitive' explanation of what this h 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 my xi) into some 'new' feature space in which the linear separation will be solved.

For each observation xi, 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 space V can be written as as a linear combination of the ϕi, i.e.: i=1Nγiϕi, where γi are real numbers.

N is the size of the training sample and therefore the dimension of the vector space V can go up to N, depending on whether the ϕi are linear independent. As ϕi(x)=K(xi,x) (see supra, we defined ϕ in this way), this means that the dimension of V depends on the kernel used and can go up to the size of the training sample.

The transformation, that maps my original feature space to V is defined as

Φ:xiϕ(x)=K(xi,x).

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 values xi 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 i=1Nγiϕi, where γi, γi are real numbers.

Looking at the function f(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 !

The yi 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 space V, 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?

Community
la source
"for each element of my training sample" -- is element here referring to a row or column (i.e. feature )
user1761806
what is x and x_i? If my X is an input of 5 columns, and 100 rows, what would x and x_i be?
user1761806
@user1761806 an element is a row. The notation is explained in the link at the beginning of the answer
1

Transformez les prédicteurs (données d'entrée) en un espace d'entités de grande dimension. Il suffit de spécifier le noyau pour cette étape et les données ne sont jamais explicitement transformées dans l'espace des fonctionnalités. Ce processus est communément appelé astuce du noyau.

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 )

enter image description here

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 matrix K(xi,x)=ϕ(xi)Tϕ(x) and not of the input x or transformed input ϕ directly. enter image description here

prashanth
la source
0

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 : 0en 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.

Hou
la source
1
As a different example, take the problem where the phenomenon results in observations of the form of [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 of x < 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.
Hou