Qu'est-ce qui rend le noyau gaussien si magique pour la PCA et aussi en général?

67

Je lisais des informations sur la PCA dans le noyau ( 1 , 2 , 3 ) avec les noyaux gaussiens et polynomiaux.

  • Comment le noyau gaussien sépare-t-il apparemment toute sorte de données non linéaires exceptionnellement bien? S'il vous plaît donner une analyse intuitive, ainsi que mathématiquement impliqué si possible.

  • Quelle est la propriété du noyau gaussien (avec idéal ) que n’ont pas les autres noyaux? On pense notamment aux réseaux de neurones, aux SVM et aux réseaux RBF.σ

  • Pourquoi ne pas mettre la norme par exemple dans un PDF de Cauchy et attendre les mêmes résultats?
Simon Kuang
la source
1
+1 Excellente question que j'ai presque négligée, car elle n'avait pas de balise [pca]! Edité maintenant.
Amibe dit Réintégrer Monica
4
Bonne question. Je me demande si la réponse pourrait être "oh oui, beaucoup d'autres noyaux fonctionneraient bien aussi, mais le gaussien est bien connu / facile"
Stumpy Joe Pete
@StumpyJoePete Je ne pense pas que ce soit une réponse aussi triviale. Le paramètre de localisation de quelle autre distribution est aussi sa moyenne? Le paramètre d'échelle de quelle autre distribution est aussi sa variance? Quelle autre distribution est si universellement intuitive? Sûrement pas la distribution de Cauchy - il n'a même pas avoir une moyenne!
shadowtalker
3
@ssdecontrol Je suis heureux de pouvoir me tromper; J'ai voté à la fois pour la question et pour l'une des réponses - je pense juste que ma réponse ennuyeuse, défensive, déflationniste est un bon défaut qu'une vraie réponse doit réfuter.
Stumpy Joe Pete
Je pense que cela peut aider: stats.stackexchange.com/questions/168051/…

Réponses:

54

Je pense que la clé de la magie est la finesse. Ma longue réponse qui suit est simplement pour expliquer cette finesse. Ce peut être ou ne pas être une réponse à laquelle vous vous attendez.

Réponse courte:

Étant donné un noyau défini positif , il existe son espace correspondant de fonctions . Les propriétés des fonctions sont déterminées par le noyau. Il s’avère que si est un noyau gaussien, les fonctions dans sont très douces. Ainsi, une fonction apprise (par exemple, une fonction de régression, les composants principaux dans RKHS comme dans le noyau PCA) est très lisse. En règle générale, l'hypothèse de lissage est judicieuse pour la plupart des jeux de données que nous voulons aborder. Ceci explique pourquoi un noyau gaussien est magique.h k hkHkH

Réponse longue pour laquelle un noyau gaussien donne des fonctions lisses:

Un noyau défini positif définit (implicitement) un produit intérieur pour le vecteur de caractéristiques construit à partir de votre entrée et est un espace de Hilbert. La notation signifie un produit intérieur entre et . Pour notre propos, vous pouvez imaginer comme étant l’espace euclidien habituel mais éventuellement avec un nombre inifinite de dimensions. Imaginez le vecteur habituel infiniment long, commek ( x , y ) = φ ( x ) , φ ( y ) H φ ( x ) x H φ ( x ) , φ ( y ) φ ( x ) φ ( y ) H φ ( x ) = ( φ 1 ( xk(x,y)k(x,y)=ϕ(x),ϕ(y)Hϕ(x)xHϕ(x),ϕ(y)ϕ(x)ϕ(y)Hϕ(x)=(ϕ1(x),ϕ2(x),). Dans les méthodes du noyau, est un espace de fonctions appelé reproduction de l’espace de Hilbert (RKHS) du noyau. Cet espace a une propriété spéciale appelée "reproduire la propriété" qui est celle qui est . Cela dit que pour évaluer , vous devez d’abord construire un vecteur de fonctions (infiniment long comme indiqué) pour . Ensuite, vous construisez votre vecteur d'entité pour noté (infiniment long). L'évaluation de est donnée en prenant un produit interne des deux. Évidemment, en pratique, personne ne construira un vecteur infiniment long. Puisque nous ne nous soucions que de son produit intérieur, nous évaluons directement le noyauHf(x)=f,ϕ(x)f(x)fxϕ(x)f(x)k. Contourner le calcul des caractéristiques explicites et calculer directement son produit interne est appelé "l'astuce du noyau".

Quelles sont les fonctionnalités?

Je n'arrêtais pas de dire les caractéristiques sans spécifier ce qu'elles étaient. Étant donné un noyau , les fonctionnalités ne sont pas uniques. Mais est uniquement déterminé. Pour expliquer la régularité des fonctions, considérons les fonctionnalités de Fourier. Supposons un noyau invariant par traduction , ce qui signifie c’est-à-dire que le noyau ne dépend que de la différence des deux arguments. Le noyau gaussien a cette propriété. Soit la transformation de Fourier de .ϕ1(x),ϕ2(x),kϕ(x),ϕ(y)kk(x,y)=k(xy)k^k

Dans ce point de vue de Fourier, les caractéristiques de sont données par . Cela signifie que la fonction de représentation de votre fonction est donnée par sa transformation de Fourier divisée par la transformation de Fourer du noyau . La représentation caractéristique de , qui est est où . On peut montrer que la propriété de reproduction est valide (un exercice pour les lecteurs).ffkxφ(x)(,f:=(,f^l/k^l,)fkxϕ(x)i=(,k^lexp(ilx),)i=1

Comme dans tout espace de Hilbert, tous les éléments appartenant à cet espace doivent avoir une norme finie. Considérons la norme au carré d'un :fH

fH2=f,fH=l=f^l2k^l.

Alors, quand cette norme est-elle finie, c’est-à-dire que appartient à l’espace? C’est lorsque chute plus vite que sorte que la somme converge. Maintenant, la transformée de Fourier d'un noyau gaussienff^l2k^l k(x,y)=exp(xy2σ2)

est un autre Gaussien où décroît de façon exponentielle avec . Donc, si doit être dans cet espace, sa transformée de Fourier doit chuter encore plus vite que celle de . Cela signifie que la fonction n'aura effectivement que quelques composants basse fréquence avec des poids élevés. Un signal avec uniquement des composants basse fréquence ne «bouge pas» beaucoup. Ceci explique pourquoi un noyau gaussien vous donne une fonction fluide.k^llfk

Extra: Qu'en est-il d'un noyau Laplace?

Si vous considérez un noyau de Laplace , sa transformation de Fourier est une distribution de Cauchy qui tombe beaucoup plus lentement que l’exponentielle fonction dans la transformée de Fourier d'un noyau gaussien. Cela signifie qu'une fonction aura plus de composantes haute fréquence. En conséquence, la fonction donnée par un noyau Laplace est «plus rugueuse» que celle donnée par un noyau gaussien.k(x,y)=exp(xyσ)f

Quelle est la propriété du noyau gaussien que n’ont pas les autres noyaux?

Indépendamment de la largeur gaussienne, une des propriétés est que le noyau gaussien est «universel». Intuitivement, cela signifie que, étant donné une fonction continue bornée (arbitraire), il existe une fonction telle que et sont proches (au sens de jusqu'à une précision arbitraire nécessaire. Fondamentalement, cela signifie que le noyau gaussien donne des fonctions qui peuvent approcher des fonctions "sympas" (liées, continues) de manière arbitraire. Les noyaux gaussien et laplace sont universels. Un noyau polynomial, par exemple, ne l'est pas.gfHfg)

Pourquoi ne faisons-nous pas de la norme, disons, un fichier PDF de Cauchy et attendons-nous les mêmes résultats?

En général, vous pouvez faire tout ce que vous voulez tant que le résultat est positif défini. La définition positive est définie comme suit: pour tout , et tout (ensemble de nombres naturels) . Si n'est pas défini positif, il ne correspond pas à un espace de produit interne. Toutes les analyses sont interrompues car vous n’avez même pas un espace de fonctions comme mentionné. Néanmoins, cela peut fonctionner de manière empirique. Par exemple, le noyau hyperbolique tangent (voir le numéro 7 sur cette page )ki=1Nj=1Nk(xi,xj)αiαj>0αiR{xi}i=1NNNkH

k(x,y)=tanh(αxy+c)

qui est destiné à imiter les unités d'activation sigmoïde dans les réseaux de neurones, n'est défini comme positif que pour certains paramètres de et . Pourtant, il a été rapporté que cela fonctionne dans la pratique.αc

Qu'en est-il des autres types de fonctionnalités?

J'ai dit que les fonctionnalités ne sont pas uniques. Pour le noyau gaussien, un autre ensemble de fonctionnalités est fourni par l’extension Mercer . Voir la section 4.3.1 du célèbre livre de processus gaussien . Dans ce cas, les caractéristiques sont des polynômes d'Hermite évalués à .ϕ(x)x

wij
la source
2
Je ne suis pas sur le point d'attribuer la prime pour l'instant, mais je suis tenté de l'attribuer à cette réponse, car elle est très ciblée sur la question et fait des comparaisons explicites avec d'autres noyaux
shadowtalker
Enfin, cette question a eu une excellente réponse! (+1) J'ai été brièvement dérouté par la notation que vous avez utilisée ici: - et dans les paragraphes suivants. Une notation plus explicite serait-elle pas plus claire en séparant une fonction agissant sur l'espace d'origine et un vecteur , où est fonctionnel? À propos, quelles fonctions sont garanties d'être "reproduites" par la "propriété de reproduction"? Tout? Continu? Lisse? f(x)=f,ϕ(x)f(x)=Ψ(f),ϕ(x)f()Ψ(f)HΨ()
amibe dit de réintégrer Monica le
@ amoeba Dans la littérature, les gens ne distinguent pas une représentation de et la fonction elle-même. Si nécessaire, ils utilisent parfois pour la représentation et pour une fonction. Toutes les fonctions de l'espace ont la propriété de reproduction. Lisse ou non, cela est spécifié par le noyau. :)fff()H
lundi
Mis à jour le post. Ajout d'un peu plus sur le noyau tanh.
wij
Hmmm, je pense que je suis confus ici. Nous commençons par un espace vectoriel , où vivent des points de données . Ensuite , nous choisissons un noyau défini positif . Ensuite, nous affirmons que le théorème 1 tient: peut être réalisé comme un produit scalaire sur un espace de Hilbert , tel que , où . D'accord. Et maintenant, vous dites que toute fonction agissant sur peut être réalisée comme un produit scalaire de sa représentationXxk(,):X×XRkHk(x,y)=ϕ(x),ϕ(y)ϕ:XHf(x)XfHavec ? Est-ce correct? ϕ(x)
amibe dit de réintégrer Monica le
18

Je ferai de mon mieux pour répondre à cette question, non pas parce que je suis un expert sur le sujet (bien au contraire), mais parce que je suis curieux à propos du domaine et du sujet, combiné avec l'idée que cela pourrait être une bonne expérience éducative. . Quoi qu'il en soit, voici le résultat de ma brève recherche amateur sur le sujet.

TL; DR : Je considérerais le passage suivant du document de recherche "Le lien entre les opérateurs de régularisation et les noyaux de vecteurs de support" comme réponse courte à cette question:

Les noyaux gaussiens ont tendance à donner de bonnes performances sous des hypothèses de finesse générales et devraient être pris en compte, en particulier si aucune connaissance supplémentaire des données n'est disponible.

Maintenant, une réponse détaillée (pour autant que je sache; pour les détails en mathématiques, veuillez utiliser les références).

Comme nous le savons, l’ analyse en composantes principales (ACP) est une approche très populaire de la réduction de la dimensionnalité , seule et pour la classification ultérieure des données: http://www.visiondummy.com/2014/05/feature-extraction-using-pca . Toutefois, dans les situations où les données comportent des dépendances non linéaires (en d’autres termes, linéairement inséparables ), l’ACP traditionnelle n’est pas applicable (ne fonctionne pas bien). Pour ces cas, d'autres approches peuvent être utilisées, et l'ACP non linéaire en est une.

On se réfère généralement aux approches où PCA est basée sur l'utilisation de la fonction du noyau, en utilisant un terme générique "noyau PCA" ( kPCA ). L'utilisation du noyau à fonction de base radiale gaussienne (RBF) est probablement la variante la plus populaire. Cette approche est décrite en détail dans plusieurs sources, mais j’aime beaucoup l’excellente explication de Sebastian Raschka dans cet article de blog . Cependant, tout en mentionnant la possibilité d'utiliser des fonctions du noyau, autres que le RBF gaussien, l'article se concentre sur ce dernier en raison de sa popularité. Ce billet de blog , qui présente les approximations et les astuces du noyau , mentionne une autre raison possible de la popularité du noyau gaussien pour PCA: une dimensionnalité infinie.

Des informations supplémentaires peuvent être trouvées dans plusieurs réponses sur Quora. En particulier, la lecture de cette excellente discussion révèle plusieurs points sur les raisons potentielles de la popularité du noyau gaussien, comme suit.

  • Les noyaux gaussiens sont universels :

Les noyaux gaussiens sont des noyaux universels, c'est-à-dire que leur utilisation avec une régularisation appropriée garantit un prédicteur globalement optimal minimisant à la fois les erreurs d'estimation et d'approximation d'un classifieur.

  • Les noyaux gaussiens sont circulaires (ce qui conduit à la dimensionnalité infinie susmentionnée?)
  • Les noyaux gaussiens peuvent représenter des "terrains très variables"
  • Le point suivant, à l’appui de la conclusion principale ci-dessus, est mieux expliqué en citant l’auteur:

Le noyau gaussien RBF est très populaire et constitue un bon noyau par défaut, surtout en l’absence de connaissances approfondies des données et du domaine, car il subsume également les noyaux polynomiaux et linéaires. Les noyaux linéaires et les noyaux polynomiaux constituent un cas particulier du noyau gaussien RBF. Les noyaux gaussiens RBF sont des modèles non paramétriques, ce qui signifie essentiellement que la complexité du modèle est potentiellement infinie car le nombre de fonctions analytiques est infini.

  • Les noyaux gaussiens sont optimaux (pour la douceur , lisez plus ici - même auteur):

Un noyau gaussien n’est qu’un filtre passe-bande; il sélectionne la solution la plus fluide. [...] Un noyau gaussien fonctionne mieux lorsque la somme infinie de dérivés d'ordre élevé converge le plus rapidement - ce qui se produit pour les solutions les plus lisses.

Enfin, des points supplémentaires de cette belle réponse :

  • Les noyaux gaussiens supportent des modèles infiniment complexes
  • Les noyaux gaussiens sont plus flexibles

REMARQUES:

Le point mentionné ci-dessus sur le choix optimal du noyau gaussien , en particulier lorsqu'il n'y a aucune connaissance préalable des données, est corroboré par la phrase suivante de cette réponse CV :

En l'absence de connaissances approfondies, le noyau de la fonction de base radiale constitue un bon noyau par défaut (une fois que vous l'avez établi, le problème nécessite un modèle non linéaire).

Pour ceux qui sont curieux des différences non essentielles entre le noyau gaussien RBF et le noyau gaussien standard, cette réponse peut présenter un intérêt: https://stats.stackexchange.com/a/79193/31372 .

Pour ceux qui sont intéressés par la mise en œuvre de kPCA pour le plaisir ou pour les affaires, ce blog peut être utile. Il est écrit par l’un des auteurs (créateurs?) De Accord.NET - un très intéressant framework open source .NET pour l’analyse statistique, l’apprentissage automatique, le traitement du signal et bien plus encore.

Aleksandr Blekh
la source
5
J'apprécie et applaudis les efforts déployés pour composer cette réponse, mais je dois en même temps dire qu'elle cite un grand nombre de sources qui ne font pas très autorité et qui ne fournissent que ce type d'explications générales à la main qui pourraient être correctes mais pourraient aussi être complètement faux. Le noyau RBF est donc un noyau stationnaire isotrope avec un espace de Hilbert reproduisant les dimensions infinies. Bien! Y a-t-il d'autres noyaux avec ces propriétés? Si oui, pourquoi RBF serait-il meilleur que tous? En fait, existe-t-il un soutien empirique à l'affirmation selon laquelle RBF surperforme ces concurrents?
amibe dit de réintégrer Monica le
@ amoeba: Merci pour vos gentils mots. En ce qui concerne les sources que j'ai utilisées, vous avez partiellement raison: c'est un mélange et certaines sources ne sont que des opinions. Cependant, certaines sources (les blogs) citent elles-mêmes des articles solides. À ce stade, j'étais plus attiré par la qualité de l'explication que par sa rigueur. En ce qui concerne vos questions, je me prépare à y répondre plus tard. J'ai besoin de lire un peu plus de théorie. J'ai déjà compilé des sources avec un support empirique, mais j'ai besoin de plus de temps pour leur systématisation (et un peu de sommeil, :).
Aleksandr Blekh
1
J'ai le sentiment que le fait que la gaussienne ait une entropie maximale parmi les distributions symétriques réelles joue un rôle dans votre premier argument sur les bonnes performances sous hypothèse générale
shadowtalker
2
Aussi @AleksandrBlekh c'est une compilation fantastique. Les gens râlent contre Quora mais cela ne fait pas moins autorité que le lien vers une autre réponse ici
shadowtalker
@ssdecontrol: Merci pour vos gentils mots. Heureux que nous soyons sur la même page à propos du sujet. J'ai quelques informations supplémentaires pour répondre au commentaire d'amibe, alors surveillez cet espace, si cela vous intéresse.
Aleksandr Blekh
8

Laissez-moi mettre dans mes deux cents.

Je pense que les noyaux gaussiens sont en quelque sorte des classificateurs proches. Ce que fait un noyau gaussien, c'est qu'il représente chaque point avec la distance par rapport à tous les autres points de l'ensemble de données. Penser maintenant aux classificateurs avec des limites linéaires ou polynomiales, les limites sont limitées à certaines formes. Cependant, lorsque vous regardez le voisin le plus proche, la limite peut pratiquement prendre n'importe quelle forme. C’est la raison pour laquelle nous pensons que le noyau gaussien est également non paramétrique, c’est-à-dire qu’il faut ajuster la limite en fonction des données. Une autre façon de penser à cela est que le noyau gaussien s'adapte à la forme locale d'une région, de la même manière qu'un voisin le plus proche ajuste localement la limite en regardant la distance par rapport à d'autres points de la région.

Je n'ai pas d'argument mathématique à ce sujet, mais je pense que le fait que le noyau gaussien soit en fait mappé sur un espace dimensionnel infini a quelque chose à voir avec son succès. Pour les noyaux linéaires et polynomiaux, les produits scalaires sont pris dans des espaces de dimension finie; par conséquent, il semble plus puissant de faire les choses dans un espace plus grand. J'espère que quelqu'un comprend mieux ces choses. Cela signifie également que si nous pouvons trouver d'autres noyaux avec des espaces dimensionnels infinis, ils devraient également être assez puissants. Malheureusement, je ne connais aucun de ces noyaux.

Pour votre dernier point, je pense que le pdf de Cauchy ou tout autre pdf qui mesure en quelque sorte la distance par rapport à d’autres points devrait également fonctionner. Encore une fois, je n’ai pas un bon argument mathématique pour cela, mais la connexion avec le plus proche voisin rend cela plausible.

Modifier:

Voici quelques idées sur la façon de penser un classificateur utilisant les noyaux gaussiens comme classificateurs proches. Tout d’abord, réfléchissons à ce que fait un classificateur du plus proche voisin. Essentiellement, un classificateur voisin le plus proche est un classificateur standard qui utilise les distances entre les points comme entrées. Plus formellement, imaginons que nous créons une représentation d' pour chaque point de l'ensemble de données en calculant sa distance par rapport à tous les autres points. dessus, est une fonction de distance. Ensuite, ce que fait un classifieur voisin le plus proche consiste à prédire l'étiquette de classe pour un point en fonction de cette représentation d'entité et des étiquettes de classe pour les données. oùϕixi

ϕi=(d(xi,x1),d(xi,x2),,d(xi,xn))
d
pi=f(ϕi,y)
pi est la prédiction pour le point de données et est un vecteur d'étiquettes de classe pour .xiyx1,x2,,xn

Ce que je pense des noyaux, c'est qu'ils font la même chose. ils créent une représentation d'entité de chaque point en utilisant ses valeurs de noyau avec d'autres points de l'ensemble de données. Semblable au cas du voisin le plus proche, plus formellement, ce serait Maintenant, la connexion avec le plus proche voisin est assez évidente; si notre fonction de noyau est une mesure liée aux mesures de distance que nous utilisons dans les classificateurs les plus proches voisins, notre classificateur basé sur le noyau sera similaire au modèle le plus proche voisin.

ϕi=(k(xi,x1),k(xi,x2),,k(xi,xn))

Remarque: les classificateurs que nous entraînons à l'aide de noyaux ne fonctionnent pas directement avec ces représentations , mais je pense que c'est ce qu'ils font implicitement.ϕi

goker
la source
L'interprétation des voisins les plus proches est intéressante. Pensez-vous que vous pourriez développer un peu cela? Je pense l'avoir mais je ne suis pas sûr de le savoir.
shadowtalker
@ssdecontrol J'ai ajouté quelques commentaires. J'espère qu'ils sont serviables.
Goker
6

La raison en est que la dimension VC des noyaux gaussiens est infinie et qu'en conséquence, étant donné les valeurs correctes pour les paramètres (sigma), ils peuvent classer correctement un nombre arbitrairement grand d'échantillons.

Les RBF fonctionnent bien car ils permettent de s'assurer que la matrice est au rang complet. L'idée est que et les termes hors diagonale peuvent être rendus arbitrairement petits en diminuant la valeur de . Notez que le noyau correspond à un produit scalaire dans l'espace des fonctionnalités. Dans cet espace, la dimension est infinie (en considérant l'expansion en série de l'exponentielle). On pourrait donc voir cela comme une projection de ces points dans différentes dimensions afin de pouvoir les séparer.K(xi,xj)K(xi,xi)>0σ

Considérons au contraire le cas des noyaux linéaires, qui ne peuvent briser que quatre points du plan.

Vous pouvez consulter ce document , même s’il est très technique. L'un des ouvrages standard sur les SVM devrait rendre ce concept plus accessible.

jpmuc
la source
1
'Les fichiers RBF fonctionnent bien car ils garantissent que la matrice un rang complet': ceci est vrai pour chaque fonction de noyau valide (Mercer) (y compris la fonction linéaire). -performance du RBF. K(xi,xj)
user603
2
En plus de ce que @ user603 vient d'écrire: existe-t-il d'autres noyaux populaires avec une dimension infinie VC (dimension de l'espace cible)? Si oui, sont-ils alors aussi bons que RBF?
Amibe dit Réintégrer Monica
2
La dimension VC n'est-elle pas une propriété d'un ensemble de classificateurs, pas la propriété d'un noyau?
wij
2
@ user603: ce n'est pas vrai. Les noyaux Mercer exigent seulement que la matrice du noyau soit positive semi-définie; ils peuvent être singuliers. Par exemple, le noyau linéaire donne en fait des matrices de noyau singulières si est dans votre ensemble de points. (Bien entendu, la plupart des noyaux sont strictement positifs et ne constituent donc pas une propriété particulièrement distinctive du RBF gaussien.)xi=0
Dougal