Quelle est l'intuition derrière le fait qu'un SVM avec un noyau gaussien a un espace de fonctions infini dimensionnel?

Cette réponse explique ce qui suit:

1. Pourquoi une séparation parfaite est toujours possible avec des points distincts et un noyau gaussien (bande passante suffisamment petite)
2. Comment cette séparation peut être interprétée comme linéaire, mais uniquement dans un espace de fonction abstrait distinct de celui où vit les données
3. Comment le mappage de l'espace de données à l'espace de fonctionnalités est "trouvé". Spoiler: il n'est pas trouvé par SVM, il est implicitement défini par le noyau que vous choisissez.
4. Pourquoi l'espace d'entité est de dimension infinie.

1. Obtenir une séparation parfaite

Une séparation parfaite est toujours possible avec un noyau gaussien (à condition que deux points de classes différentes ne soient jamais exactement identiques) en raison des propriétés de localisation du noyau, qui conduisent à une limite de décision arbitrairement flexible. Pour une largeur de bande du noyau suffisamment petite, la limite de décision ressemblera à celle que vous venez de dessiner pour former des petits cercles autour des points chaque fois que cela est nécessaire 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 d'un point de vue mathématique?

Considérons la configuration standard: vous avez un noyau gaussien et données d'entraînement où les valeurs sont . Nous voulons apprendre une fonction de classificateur( x ( 1 ) , y ( 1 ) ) , ( x ( 2 ) , y ( 2 ) ) , … , ( x ( n ) , y ( n ) ) y $K(\mathbf{x},\mathbf{z}) = \exp(-||\mathbf{x}-\mathbf{z}||^2 / \sigma^2)$$(\mathbf{x}^{(1)},y^{(1)}), (\mathbf{x}^{(2)},y^{(2)}), \ldots, (\mathbf{x}^{(n)},y^{(n)})$ ±$y^{(i)}$$\pm 1$

$$\hat{y}(\mathbf{x}) = \sum_i w_i y^{(i)} K(\mathbf{x}^{(i)},\mathbf{x})$$

Maintenant, comment allons-nous assigner 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 séparer les points parfaitement. Donc, je fais un milliard de fois plus petit que la plus petite séparationentre deux exemples de formation, et je viens de définir . Cela signifie que tous les points d'apprentissage forment un milliard de sigmas en ce qui concerne le noyau, et que chaque point contrôle complètement le signe de dans son voisinage. Formellement, nous avons σ | | x ( i ) - x ( j ) | | w i = 1 $w_i$$\sigma$$||\mathbf{x}^{(i)} - \mathbf{x}^{(j)}||$$w_i = 1$$\hat{y}$

$$\hat{y}(\mathbf{x}^{(k)}) = \sum_{i=1}^n y^{(k)} K(\mathbf{x}^{(i)},\mathbf{x}^{(k)}) = y^{(k)} K(\mathbf{x}^{(k)},\mathbf{x}^{(k)}) + \sum_{i \neq k} y^{(i)} K(\mathbf{x}^{(i)},\mathbf{x}^{(k)}) = y^{(k)} + \epsilon$$

où est une valeur arbitrairement petite. Nous savons est minuscule , car est un milliard sigmas loin de tout autre point, donc pour tous nous avons reçuese x ( k ) i ≠ $\epsilon$$\epsilon$$\mathbf{x}^{(k)}$$i \neq k$

$$K(\mathbf{x}^{(i)},\mathbf{x}^{(k)}) = \exp(-||\mathbf{x}^{(i)} - \mathbf{x}^{(k)}||^2 / \sigma^2) \approx 0.$$

Puisque est si petit, certainement le même signe que et le classificateur obtient une précision parfaite sur les données d'apprentissage.y ( x ( k ) ) y ( k $\epsilon$$\hat{y}(\mathbf{x}^{(k)})$$y^{(k)}$

2. Apprentissage de la SVM dans le noyau en tant que séparation linéaire

Le fait que cela puisse être interprété comme une "séparation linéaire parfaite dans un espace de fonctions infiniment dimensionnel" vient de l'astuce du noyau, ce qui vous permet d'interpréter le noyau comme un produit interne dans un espace de fonctionnalités (potentiellement à dimension infinie):

$$K(\mathbf{x}^{(i)},\mathbf{x}^{(j)}) = \langle\Phi(\mathbf{x}^{(i)}),\Phi(\mathbf{x}^{(j)})\rangle$$

où est le mappage de l'espace de données vers l'espace de fonctions. Il s'ensuit immédiatement que fonctionne comme une fonction linéaire dans l'espace des fonctions:y ( x$\Phi(\mathbf{x})$$\hat{y}(\mathbf{x})$

$$\hat{y}(\mathbf{x}) = \sum_i w_i y^{(i)} \langle\Phi(\mathbf{x}^{(i)}),\Phi(\mathbf{x})\rangle = L(\Phi(\mathbf{x}))$$

où la fonction linéaire est définie sur les vecteurs d'espace d'entité comme$L(\mathbf{v})$$\mathbf{v}$

$$L(\mathbf{v}) = \sum_i w_i y^{(i)} \langle\Phi(\mathbf{x}^{(i)}),\mathbf{v}\rangle$$

Cette fonction est linéaire dans car il s’agit simplement d’une combinaison linéaire de produits internes avec des vecteurs fixes. Dans l'espace des fonctions, la limite de décision correspond simplement à , l'ensemble de niveaux d'une fonction linéaire. C'est la définition même d'un hyperplan dans l'espace des fonctionnalités.y ( x ) = 0 L ( v ) = $\mathbf{v}$$\hat{y}(\mathbf{x}) = 0$$L(\mathbf{v}) = 0$

3. Comprendre la cartographie et l'espace des fonctionnalités

Remarque: Dans cette section, la notationfait référence à un ensemble arbitraire depoints et non aux données d'apprentissage. Ceci est purement mathématique; les données d'entraînement ne figurent pas du tout dans cette section!$\mathbf{x}^{(i)}$$n$

En réalité, les méthodes du noyau ne "trouvent" ni ne "calculent" explicitement l'espace des fonctionnalités ou le mapping . Les méthodes d'apprentissage par le noyau telles que SVM n'en ont pas besoin pour fonctionner; ils ont seulement besoin de la fonction du noyau .$\Phi$$K$

Cela dit, il est possible d’écrire une formule pour . L'espace des fonctionnalités sur lequel est mappé est en quelque sorte abstrait (et potentiellement de dimension infinie), mais la cartographie utilise simplement le noyau pour faire de l'ingénierie de fonctionnalités simple. En termes de résultat final, le modèle que vous finissez par apprendre, en utilisant des noyaux, n'est pas différent de l'ingénierie des caractéristiques traditionnelle couramment appliquée à la régression linéaire et à la modélisation GLM, comme en prenant le journal d'une variable prédictive positive avant de l'insérer dans une formule de régression. Le calcul sert principalement à s'assurer que le noyau fonctionne bien avec l'algorithme SVM, qui présente des avantages réputés pour sa faible densité et sa bonne adaptation aux grands ensembles de données.$\Phi$$\Phi$

Si cela vous intéresse toujours, voici comment cela fonctionne. Nous prenons essentiellement l’identité que nous voulons posséder, et construire un espace et un produit intérieur tels qu’ils tiennent par définition. Pour ce faire, nous définissons un espace vectoriel abstrait où chaque vecteur est une fonction de l'espace dans lequel les données vivent, , aux nombres réels . Un vecteur dans est une fonction formée d’une combinaison linéaire finie de tranches de noyau: Il est commode d'écrire manière plus compacte V X R f V f ( x ) = n Σ i = 1 α i K ( x ( i ) , x ) f f = n Σ i = 1 α i K x ( i ) K $\langle \Phi(\mathbf{x}), \Phi(\mathbf{y}) \rangle = K(\mathbf{x},\mathbf{y})$$V$$\mathcal{X}$$\mathbb{R}$$f$$V$

$$f(\mathbf{x}) = \sum_{i=1}^n \alpha_i K(\mathbf{x}^{(i)},\mathbf{x})$$ $f$ $$f = \sum_{i=1}^n \alpha_i K_{\mathbf{x}^{(i)}}$$ où est une fonction donnant une "tranche" du noyau sous .$K_\mathbf{x}(\mathbf{y}) = K(\mathbf{x},\mathbf{y})$$\mathbf{x}$

Le produit interne de l'espace n'est pas le produit scalaire ordinaire, mais un produit interne abstrait basé sur le noyau:

$$\langle \sum_{i=1}^n \alpha_i K_{\mathbf{x}^{(i)}}, \sum_{j=1}^n \beta_j K_{\mathbf{x}^{(j)}} \rangle = \sum_{i,j} \alpha_i \beta_j K(\mathbf{x}^{(i)},\mathbf{x}^{(j)})$$

Avec l'espace caractéristique défini de cette façon, est une application , en prenant chaque point la "tranche du noyau" à ce moment - là:X → V $\Phi$$\mathcal{X} \rightarrow V$$\mathbf{x}$

$$\Phi(\mathbf{x}) = K_\mathbf{x}, \quad \text{where} \quad K_\mathbf{x}(\mathbf{y}) = K(\mathbf{x},\mathbf{y}).$$

Vous pouvez prouver que est un espace produit interne lorsque est un noyau défini positif. Voir ce document pour plus de détails. (Bravo à Coppens pour l'avoir signalé!)$V$$K$

4. Pourquoi l'espace des fonctions est-il infiniment dimensionnel?

Cette réponse donne une belle explication en algèbre linéaire, mais voici une perspective géométrique, avec à la fois intuition et preuve.

Intuition

Pour tout point fixe , nous avons une fonction de tranche de noyau . Le graphique de est juste une bosse gaussienne centrée sur . Maintenant, si l’espace caractéristique n’était que des dimensions finies, cela signifierait que nous pourrions prendre un ensemble fini de bosses en un ensemble fixe de points et former n’importe quel relief gaussien ailleurs. Mais il est clair que nous ne pouvons pas faire cela. vous ne pouvez pas créer une nouvelle bosse à partir d'anciennes bosse, car la nouvelle bosse pourrait être très loin des anciennes. Ainsi, quel que soit le nombre de vecteurs d'entité que nous avons, nous pouvons toujours en ajouter de nouveaux et, dans l'espace des entités, il s'agit de nouveaux vecteurs indépendants. Ainsi, l'espace des fonctions ne peut pas être de dimension finie; il doit être infini.K z ( x ) = K ( z , x ) K z$\mathbf{z}$$K_\mathbf{z}(\mathbf{x}) = K(\mathbf{z},\mathbf{x})$$K_\mathbf{z}$$\mathbf{z}$

Preuve

Nous utilisons l'induction. Supposons que vous avez un ensemble arbitraire de points tels que les vecteurs sont linéairement indépendants dans l'espace des fonctions. Maintenant, trouvez un point distinct de ces points, soit un milliard de sigmas. Nous affirmons que est linéairement indépendant des premiers vecteurs de caractéristiques . Φ( x ( i ) ) x ( n + 1 ) nΦ( x ( n + 1 ) )nΦ( x ( i )$\mathbf{x}^{(1)}, \mathbf{x}^{(2)}, \ldots, \mathbf{x}^{(n)}$$\Phi(\mathbf{x}^{(i)})$$\mathbf{x}^{(n+1)}$$n$$\Phi(\mathbf{x}^{(n+1)})$$n$$\Phi(\mathbf{x}^{(i)})$

Preuve par contradiction. Supposons au contraire que

$$\Phi(\mathbf{x}^{(n+1)}) = \sum_{i=1}^n \alpha_i \Phi(\mathbf{x}^{(i)})$$

Maintenant, prenons le produit interne des deux côtés avec un arbitraire . Par l'identité , nous obtenons ⟨ Φ ( z ) , Φ ( x ) ⟩ = K ( z , x$\mathbf{x}$$\langle \Phi(\mathbf{z}), \Phi(\mathbf{x}) \rangle = K(\mathbf{z},\mathbf{x})$

$$K(\mathbf{x}^{(n+1)},\mathbf{x}) = \sum_{i=1}^n \alpha_i K(\mathbf{x}^{(i)},\mathbf{x})$$

Ici, est une variable libre, cette équation est donc une identité indiquant que deux fonctions sont identiques. En particulier, il est indiqué qu'un gaussien centré sur peut être représenté comme une combinaison linéaire de Gaussiennes en un autre point . Il est évident, géométriquement, qu’il est impossible de créer une bosse gaussienne centrée en un point à partir d’une combinaison finie de bosses gaussiennes centrée sur d’autres points, en particulier lorsque toutes les autres bosses gaussiennes se trouvent à un milliard de sigmas. Notre hypothèse de dépendance linéaire a donc conduit à une contradiction, comme nous avons voulu le montrer.$\mathbf{x}$$\mathbf{x}^{(n+1)}$$\mathbf{x}^{(i)}$

La matrice du noyau gaussien a toujours le rang complet pour distinct . Cela signifie que chaque fois que vous ajoutez un nouvel exemple, le rang augmente de . La meilleure façon de voir cela si vous définissez très petit. La matrice du noyau est alors presque diagonale.$\mathbf x_1,...,\mathbf x_m$$1$$\sigma$

Le fait que le rang augmente toujours de un signifie que toutes les projections de l'espace des fonctions sont linéairement indépendantes (non orthogonales, mais indépendantes). Par conséquent, chaque exemple ajoute une nouvelle dimension à l'étendue des projections . Etant donné que vous pouvez ajouter un nombre infini d’exemples, l’espace de la fonction doit avoir une dimension infinie. Il est intéressant de noter que toutes les projections de l’espace d’entrée dans l’espace de caractéristiques reposent sur une sphère, puisque . Néanmoins, la géométrie de la sphère est plate. Vous pouvez en lire plus à ce sujet dans$\Phi(\mathbf x)$$\Phi(\mathbf x_1),...,\Phi(\mathbf x_m)$$||\Phi(\mathbf x)||_{\mathcal H}^²=k(\mathbf x,\mathbf x)=1$

Burges, CJC (1999). Géométrie et invariance dans les méthodes basées sur le noyau. Dans B. Schölkopf, CJC Burges, et AJ Smola (Eds.), Progrès dans les méthodes du noyau, apprentissage du vecteur d'apprentissage (pp. 89–116). MIT Appuyez sur.

Pour le fond et les notations, je me réfère à la réponse Comment calculer la limite de décision à partir de vecteurs de support? .

Les entités de l’espace «original» sont donc les vecteurs , le résultat binaire et les multiplicateurs de Lagrange sont .$x_i$$y_i \in \{-1, +1\}$$\alpha_i$

Il est connu que le noyau peut s’écrire comme (' ' représente le produit intérieur.) Où est un (implicite et inconnu) transformation en un nouvel espace de fonctionnalités.$K(x,y)=\Phi(x) \cdot \Phi(y)$$\cdot$$\Phi$

Je vais essayer de donner une explication «intuitive» de ce à quoi ressemble ce . Cette réponse n’est donc pas une preuve formelle, elle veut simplement donner une idée de la façon dont je pense que cela fonctionne. N'hésitez pas à me corriger si je me trompe. La base de mon explication est la section 2.2.1 de ce pdf$\Phi$

Je dois "transformer" mon espace de fonctions (donc mon ) en un "nouvel" espace de fonctions dans lequel la séparation linéaire sera résolue.$x_i$

Pour chaque observation , je définis les fonctions , donc j'ai une fonction pour chaque élément de mon échantillon d'apprentissage. Ces fonctions couvrent un espace vectoriel. L'espace vectoriel couvert par le , notez-le . ( est la taille de l'échantillon d'apprentissage).$x_i$$\phi_i(x)=K(x_i,x)$$\phi_i$$\phi_i$$\phi_i$$V=span(\phi_{i, i=1,2,\dots N})$$N$

Je vais essayer de faire valoir que cet espace vectoriel est l'espace vectoriel dans lequel une séparation linéaire sera possible. $V$ Par définition de l'étendue, chaque vecteur de l'espace vectoriel peut être écrit comme une combinaison linéaire de , c'est-à-dire: , où sont des nombres réels. Donc, en fait,$V$$\phi_i$$\sum_{i=1}^N \gamma_i \phi_i$$\gamma_i$$V=\{v=\sum_{i=1}^N \gamma_i \phi_i|(\gamma_1,\gamma_2,\dots\gamma_N) \in \mathbb{R}^N \}$

Notez que sont les coordonnées du vecteur dans l'espace vectoriel .$(\gamma_1,\gamma_2,\dots\gamma_N)$$v$$V$

$N$ est la taille de l'échantillon d'apprentissage et donc la dimension de l'espace vectoriel peut aller jusqu'à , selon que les sont linéairement indépendants. Comme (voir supra, nous avons défini de cette façon), cela signifie que la dimension de dépend du noyau utilisé et peut aller jusqu'à la taille de l'échantillon d'apprentissage.$V$$N$$\phi_i$$\phi_i(x)=K(x_i,x)$$\phi$$V$

Si le noyau est 'assez complexe', alors seront tous indépendants et la dimension de sera , la taille de l'échantillon d'apprentissage.$\phi_i(x)=K(x_i, x)$$V$$N$

La transformation qui mappe mon espace de fonction d'origine sur est définie comme suit:$V$

$\Phi: x_i \to \phi_i(x)=K(x_i, x)$ .

Cette carte mappe mon espace caractéristique original sur un espace vectoriel pouvant avoir une dimension allant jusqu’à la taille de mon échantillon d’entraînement. $\Phi$So mappe chaque observation de mon échantillon d’entraînement dans un espace vectoriel où les vecteurs sont des fonctions. Le vecteur de mon échantillon de formation est « cartographié » à un vecteur en , à savoir le vecteur avec coordonnées tous égaux à zéro, à l' exception de la -ème Coordinate est 1.$\Phi$$x_i$$V$$\phi_i$$i$

Évidemment, cette transformation (a) dépend du noyau, (b) des valeurs dans l'échantillon d'apprentissage et (c) peut, en fonction de mon noyau, avoir une dimension allant jusqu'à la taille de mon échantillon d'apprentissage et ( d) les vecteurs de ressemblent à , où sont des nombres réels.$x_i$$V$$\sum_{i=1}^N \gamma_i \phi_i$$\gamma_i$

En regardant la fonction dans Comment calculer la limite de décision à partir de vecteurs de support? on peut voir que . La limite de décision trouvée par le SVM est .$f(x)$$f(x)=\sum_i y_i \alpha_i \phi_i(x)+b$$f(x)=0$

En d’autres termes, est une combinaison linéaire de et est un hyperplan de séparation linéaire dans l’ espace : c’est un choix particulier de savoir ! $f(x)$$\phi_i$ $f(x)=0$$V$$\gamma_i$$\gamma_i=\alpha_i y_i$

Les sont connus d'après nos observations, les sont les multiplicateurs de Lagrange que le SVM a trouvés. En d’autres termes, SVM trouve, par l’utilisation d’un noyau et en résolvant un problème de programmation quadratique, une séparation linéaire dans l’ espace- .$y_i$$\alpha_i$$V$

C’est ma compréhension intuitive de la façon dont «l’astuce du noyau» permet de transformer «implicitement» l’espace des caractéristiques d’origine en un nouvel espace , de dimension différente. Cette dimension dépend du noyau que vous utilisez et pour le noyau RBF, cette dimension peut aller jusqu'à la taille de l'échantillon d'apprentissage. Comme les échantillons d'apprentissage peuvent avoir n'importe quelle taille, cela peut aller jusqu'à «infini» . De toute évidence, dans les espaces très dimensionnels, le risque de surajustement va augmenter.$V$

Les noyaux sont donc une technique qui permet à SVM de transformer votre espace fonctionnel, voir aussi Qu'est-ce qui rend le noyau gaussien aussi magique pour PCA, et aussi en général?

Malheureusement, l'explication de fcop est assez incorrecte. Tout d'abord, il dit: "Il est connu que le noyau peut être écrit en tant que ... où ... est une transformation (implicite et inconnue) en un nouvel espace de fonctions." Ce n'est pas inconnu. C’est en fait l’espace sur lequel les entités sont mappées et c’est l’espace qui pourrait être de dimension infinie, comme dans le cas RBF. Tout ce que le noyau fait, c'est prendre le produit interne de ce vecteur de caractéristiques transformé avec un vecteur de caractéristiques transformé d'un exemple d'apprentissage et appliquer une fonction au résultat. Ainsi, il représente implicitement ce vecteur de caractéristiques de dimension supérieure. Pensez à écrire (x + y) ^ 2 au lieu de x ^ 2 + 2xy + y ^ 2 par exemple. Maintenant, imaginez quelle série infinie est représentée implicitement par la fonction exponentielle ... voilà votre espace de fonctions infini.

La bonne façon de penser aux SVM consiste à mapper vos entités sur un espace d'entités dimensionnel éventuellement infini qui se trouve implicitement représentable dans un autre espace d'entités "noyau" à dimensions finies, dont la dimension pourrait être aussi grande que la taille du jeu d'apprentissage.