Was macht den Gaußschen Kernel so magisch für PCA und auch im Allgemeinen?

Ich habe über Kernel-PCA ( 1 , 2 , 3 ) mit Gauß- und Polynomkernen gelesen.

• Wie trennt der Gaußsche Kern scheinbar jede Art von nichtlinearen Daten außergewöhnlich gut? Bitte geben Sie eine intuitive Analyse sowie, wenn möglich, eine mathematische an.

• Was ist eine Eigenschaft des Gaußschen Kernels (mit ideal ), die andere Kernel nicht haben? Man denke an neuronale Netze, SVMs und RBF-Netze.$\sigma$

• Warum setzen wir die Norm nicht beispielsweise durch ein Cauchy-PDF und erwarten die gleichen Ergebnisse?

Ich denke, der Schlüssel zur Magie ist Geschmeidigkeit. Meine lange Antwort, die folgt, ist einfach, über diese Glätte zu erklären. Es kann eine Antwort sein oder auch nicht, die Sie erwarten.

Kurze Antwort:

Bei einem positiv definierten Kernel existiert der entsprechende Funktionsraum . Eigenschaften von Funktionen werden vom Kernel bestimmt. Es stellt sich heraus, dass wenn ein Gaußscher Kernel ist, die Funktionen in sehr glatt sind. Eine gelernte Funktion (z. B. eine Regressionsfunktion, Hauptkomponenten in RKHS wie in Kernel-PCA) ist also sehr glatt. Normalerweise ist die Annahme der Glätte für die meisten Datensätze, die wir behandeln möchten, sinnvoll. Dies erklärt, warum ein Gaußscher Kern magisch ist.$k$$\mathcal{H}$$k$$\mathcal{H}$

Lange Antwort, warum ein Gauß-Kernel reibungslose Funktionen bietet:

Ein positiver bestimmter Kernel definiert (implizit) ein inneres Produkt für den aus Ihrer Eingabe konstruierten Merkmalsvektor und ist ein Hilbert-Raum. Die Notation bedeutet ein inneres Produkt zwischen und . Für unseren Zweck können Sie sich vorstellen, dass der übliche euklidische Raum ist, aber möglicherweise mit einer unendlichen Anzahl von Dimensionen. Stellen Sie sich den üblichen Vektor vor, der unendlich lang ist wie$k(x,y)$$k(x,y)=\left\langle \phi(x),\phi(y)\right\rangle _{\mathcal{H}}$$\phi(x)$$x$$\mathcal{H}$$\left\langle \phi(x),\phi(y)\right\rangle$$\phi(x)$$\phi(y)$$\mathcal{H}$$\phi(x)=\left(\phi_{1}(x),\phi_{2}(x),\ldots\right)$. In Kernel-Methoden ist ein Funktionsraum, der als reproduzierender Kernel-Hilbert-Raum (RKHS) bezeichnet wird. Dieser Raum hat eine spezielle Eigenschaft namens "reproducing property", nämlich . Dies besagt, dass Sie zur Auswertung von zunächst einen Merkmalsvektor (unendlich lang wie erwähnt) für konstruieren . Dann konstruieren Sie Ihren Merkmalsvektor für mit (unendlich lang). Die Bewertung von wird gegeben, indem ein inneres Produkt der beiden genommen wird. Offensichtlich wird in der Praxis niemand einen unendlich langen Vektor konstruieren. Da wir uns nur um sein inneres Produkt kümmern, werten wir den Kernel direkt aus$\mathcal{H}$$f(x)=\left\langle f,\phi(x)\right\rangle$$f(x)$$f$$x$$\phi(x)$$f(x)$$k$. Das Umgehen der Berechnung expliziter Merkmale und das direkte Berechnen des inneren Produkts wird als "Kernel-Trick" bezeichnet.

Was sind die Features?

Ich sagte immer wieder features ohne anzugeben, was sie sind. Bei einem Kernel sind die Funktionen nicht eindeutig. Aber ist eindeutig bestimmt. Betrachten wir zur Erläuterung der Glätte der Funktionen die Fourier-Merkmale. Nehmen Sie an, dass der Kernel eine Übersetzungsinvariante ist , dh dh der Kernel hängt nur vom Unterschied der beiden Argumente ab. Der Gaußsche Kernel hat diese Eigenschaft. Es sei die Fourier-Transformation von .$\phi_{1}(x),\phi_{2}(x),\ldots$⟨ φ ( x ) , φ ( y ) ⟩ k k ( x , y ) = k ( x - y ) k$k$$\left\langle \phi(x),\phi(y)\right\rangle$$k$$k(x,y)=k(x-y)$$\hat{k}$$k$

In diesem Fourier-Standpunkt sind die Merkmale von gegeben durch . Dies bedeutet, dass die Merkmalsdarstellung Ihrer Funktion durch ihre Fouriertransformation geteilt durch die Fouriertransformation des Kernels . Die Merkmals Darstellung , welches wird , wo . Man kann zeigen, dass die Reproduktionseigenschaft hält (eine Übung für die Leser).f : = ( ⋯ , f l / $f$fkxφ(x)(⋯,$f:=\left(\cdots,\hat{f}_{l}/\sqrt{\hat{k}_{l}},\cdots\right)$$f$$k$$x$$\phi(x)$i=$\left(\cdots,\sqrt{\hat{k}_{l}}\exp\left(-ilx\right),\cdots\right)$$i=\sqrt{-1}$

Wie in jedem Hilbert-Raum müssen alle zum Raum gehörenden Elemente eine endliche Norm haben. Betrachten wir die quadratische Norm eines :$f\in\mathcal{H}$

$\|f\|_{\mathcal{H}}^{2}=\left\langle f,f\right\rangle _{\mathcal{H}}=\sum_{l=-\infty}^{\infty}\frac{\hat{f}_{l}^{2}}{\hat{k}_{l}}.$

Wann ist diese Norm endlich, dh gehört zum Raum? Es ist, wenn schneller fällt als so dass die Summe konvergiert. Nun ist die Fouriertransformation eines Gaußschen Kernels$f$$\hat{f}_{l}^{2}$$\hat{k}_{l}$ $k(x,y)=\exp\left(-\frac{\|x-y\|^{2}}{\sigma^{2}}\right)$

ist ein weiterer Gaußscher Wert, bei dem mit exponentiell schnell abnimmt . Wenn also in diesem Raum liegen soll, muss seine Fouriertransformation noch schneller abfallen als die von . Dies bedeutet, dass die Funktion effektiv nur wenige Niederfrequenzkomponenten mit hohen Gewichten aufweist. Ein Signal mit nur Niederfrequenzkomponenten wackelt nicht viel. Dies erklärt, warum ein Gauß-Kernel eine reibungslose Funktion bietet.$\hat{k}_{l}$$l$$f$$k$

Extra: Was ist mit einem Laplace-Kernel?

Wenn Sie einen Laplace-Kernel , ist seine Fourier-Transformation eine Cauchy-Verteilung, die viel langsamer abfällt als die Exponentialverteilung Funktion in der Fourier-Transformation eines Gaußschen Kernels. Dies bedeutet, dass eine Funktion mehr Hochfrequenzkomponenten hat. Infolgedessen ist die von einem Laplace-Kernel gegebene Funktion "rauer" als die von einem Gaußschen Kernel gegebene.$k(x,y)=\exp\left(-\frac{\|x-y\|}{\sigma}\right)$$f$

Was ist eine Eigenschaft des Gaußschen Kernels, die andere Kernel nicht haben?

Unabhängig von der Gaußschen Breite ist eine Eigenschaft, dass der Gaußsche Kern "universal" ist. Intuitiv bedeutet dies, dass bei gegebener begrenzter stetiger Funktion (willkürlich) eine Funktion so dass und nahe beieinander liegen (im Sinne von bis zu beliebiger Genauigkeit erforderlich. Grundsätzlich bedeutet dies, dass der Gaußsche Kern Funktionen liefert, die beliebig gut "schöne" (begrenzte, kontinuierliche) Funktionen approximieren können. Gauß- und Laplace-Kernel sind universell. Ein Polynomkern zum Beispiel ist es nicht.$g$$f\in\mathcal{H}$$f$$g$$\|\cdot\|_{\infty})$

Warum setzen wir die Norm nicht beispielsweise durch ein Cauchy-PDF und erwarten die gleichen Ergebnisse?

Im Allgemeinen können Sie alles tun, was Sie möchten, solange das resultierende eindeutig positiv ist. Positive Bestimmtheit ist definiert als für alle , und alle (Menge natürlicher Zahlen) . Wenn nicht positiv definit ist, dann entspricht es keinem inneren Produktraum. Die gesamte Analyse wird unterbrochen, da Sie nicht einmal wie erwähnt über einen Funktionsbereich verfügen . Trotzdem kann es empirisch funktionieren. Zum Beispiel der hyperbolische Tangenskern (siehe Nummer 7 auf dieser Seite )$k$$\sum_{i=1}^{N}\sum_{j=1}^{N}k(x_{i},x_{j})\alpha_{i}\alpha_{j}>0$$\alpha_{i}\in\mathbb{R}$$\{x_{i}\}_{i=1}^{N}$$N\in\mathbb{N}$$k$$\mathcal{H}$

$k(x,y) = tanh(\alpha x^\top y + c)$

die sigmoide Aktivierungseinheiten in neuronalen Netzen imitieren soll, ist nur für einige Einstellungen von und positiv bestimmt . Trotzdem wurde berichtet, dass es in der Praxis funktioniert.$\alpha$$c$

Was ist mit anderen Funktionen?

Ich sagte, Features sind nicht einzigartig. Für den Gaußschen Kernel bietet die Mercer-Erweiterung eine weitere Reihe von Funktionen . Siehe Abschnitt 4.3.1 des berühmten Gaußschen Prozessbuchs . In diesem Fall sind die Merkmale Hermite-Polynome, die mit bewertet werden .$\phi(x)$$x$

Ich werde mein Bestes tun, um diese Frage zu beantworten, nicht weil ich ein Experte auf dem Gebiet bin (im Gegenteil), sondern weil ich neugierig auf das Gebiet und das Thema bin, kombiniert mit der Idee, dass es eine gute pädagogische Erfahrung sein könnte . Wie auch immer, hier ist das Ergebnis meiner kurzen Amateurforschung zu diesem Thema.

TL; DR : Ich würde die folgende Passage aus dem Forschungspapier "Die Verbindung zwischen Regularisierungsoperatoren und Unterstützungsvektorkernen" als die kurze Antwort auf diese Frage betrachten:

Gaußsche Kerne liefern unter allgemeinen Annahmen zur Glätte in der Regel eine gute Leistung und sollten insbesondere dann berücksichtigt werden, wenn keine zusätzlichen Kenntnisse über die Daten verfügbar sind.

Nun eine ausführliche Antwort (nach meinem besten Verständnis; für mathematische Details verwenden Sie bitte Referenzen).

Wie wir wissen, ist die Hauptkomponentenanalyse (PCA) ein sehr beliebter Ansatz zur Dimensionsreduktion allein und zur anschließenden Klassifizierung von Daten: http://www.visiondummy.com/2014/05/feature-extraction-using-pca . In Situationen jedoch, in denen Daten nichtlineare Abhängigkeiten aufweisen (dh linear untrennbar sind ), ist die herkömmliche PCA nicht anwendbar (funktioniert nicht gut). Für diese Fälle können andere Ansätze verwendet werden, und nichtlineare PCA ist einer davon.

Ansätze, bei denen PCA auf der Verwendung der Kernelfunktion basiert, werden üblicherweise mit einem Überbegriff "Kernel-PCA" ( kPCA ) bezeichnet. Die Verwendung des Kernels mit der Gaußschen Radialbasisfunktion (RBF) ist wahrscheinlich die beliebteste Variante. Dieser Ansatz wird in mehreren Quellen ausführlich beschrieben, aber ich mag eine hervorragende Erklärung von Sebastian Raschka in diesem Blog-Beitrag sehr . Während jedoch die Möglichkeit erwähnt wird, andere Kernelfunktionen als das Gaußsche RBF zu verwenden, konzentriert sich der Beitrag aufgrund seiner Beliebtheit auf das letztere. In diesem netten Blog-Beitrag , in dem die Kernel-Approximationen und der Kernel-Trick vorgestellt werden , wird ein weiterer möglicher Grund für die Beliebtheit des Gaußschen Kernels für PCA genannt: Unendliche Dimensionalität.

Zusätzliche Erkenntnisse finden Sie in mehreren Antworten zu Quora. Insbesondere die Lektüre dieser hervorragenden Diskussion zeigt einige Punkte hinsichtlich möglicher Gründe für die Popularität des Gaußschen Kernels auf, wie folgt.

• Gaußsche Kerne sind universell :

Gaußsche Kerne sind universelle Kerne, dh ihre Verwendung mit entsprechender Regularisierung garantiert einen global optimalen Prädiktor, der sowohl Schätz- als auch Approximationsfehler eines Klassifikators minimiert.

• Gaußsche Kerne sind kreisförmig (was führt zu der oben erwähnten unendlichen Dimensionalität?)
• Gaußsche Kerne können "sehr unterschiedliche Gebiete" darstellen
• Der folgende Punkt, der die obige Hauptschlussfolgerung stützt, wird besser unter Berufung auf den Autor geliefert:

Der Gaußsche RBF-Kernel ist sehr beliebt und stellt einen guten Standardkernel dar, vor allem, wenn Expertenwissen über Daten und Domänen fehlt, da er auch polynomielle und lineare Kernel subsumiert. Lineare Kerne und Polynomkerne sind ein Sonderfall des Gaußschen RBF-Kernels. Gaußsche RBF-Kernel sind nicht parametrische Modelle, was im Wesentlichen bedeutet, dass die Komplexität des Modells möglicherweise unendlich ist, da die Anzahl der analytischen Funktionen unendlich ist.

• Gaußsche Kerne sind optimal (zur Glätte lesen Sie hier - derselbe Autor):

Ein Gaußscher Kern ist nur ein Bandpassfilter; es wählt die glatteste Lösung aus. [...] Ein Gaußscher Kern funktioniert am besten, wenn die unendliche Summe von Derivaten höherer Ordnung am schnellsten konvergiert - und das geschieht für die glattesten Lösungen.

Zum Schluss noch ein paar Punkte aus dieser schönen Antwort :

• Gaußsche Kernel unterstützen unendlich komplexe Modelle
• Gaußsche Kerne sind flexibler

ANMERKUNGEN:

Der oben erwähnte Punkt, wonach der Gaußsche Kern die optimale Wahl ist, insbesondere wenn keine Vorkenntnisse über die Daten vorliegen, wird durch den folgenden Satz aus dieser CV-Antwort gestützt :

In Ermangelung von Expertenwissen stellt der Radial Basis Function-Kernel einen guten Standard-Kernel dar (sobald Sie festgestellt haben, dass es sich um ein Problem handelt, das ein nicht lineares Modell erfordert).

Für diejenigen, die sich für nicht wesentliche Unterschiede zwischen dem Gaußschen RBF-Kernel und dem Standard-Gaußschen Kernel interessieren, könnte diese Antwort von Interesse sein: https://stats.stackexchange.com/a/79193/31372 .

Für diejenigen, die daran interessiert sind, kPCA zum Vergnügen oder geschäftlich zu implementieren , könnte dieser nette Blog-Beitrag hilfreich sein. Es wurde von einem der Autoren (Schöpfer?) Von Accord.NET geschrieben - einem sehr interessanten .NET-Open-Source-Framework für statistische Analysen, maschinelles Lernen, Signalverarbeitung und vieles mehr.

Lassen Sie mich meine zwei Cent setzen.

Die Art und Weise, wie ich Gauß'sche Kerne betrachte, ist in gewissem Sinne ein Klassifikator für den nächsten Nachbarn. Was ein Gaußscher Kernel tut, ist, dass er jeden Punkt mit der Entfernung zu allen anderen Punkten im Datensatz darstellt. Stellen Sie sich nun Klassifikatoren mit linearen oder polynomialen Grenzen vor, die Grenzen sind auf bestimmte Formen beschränkt. Wenn Sie jedoch auf den nächsten Nachbarn schauen, kann die Grenze praktisch jede Form annehmen. Das ist meiner Meinung nach der Grund, warum wir den Gaußschen Kernel auch als nicht parametrisch betrachten, dh die Grenze in Abhängigkeit von den Daten anpassen. Eine andere Möglichkeit ist, dass der Gaußsche Kernel sich an die lokale Form in einer Region anpasst, ähnlich wie ein nächster Nachbar die Grenze lokal anpasst, indem er den Abstand zu anderen Punkten in der lokalen Region betrachtet.

Ich habe kein mathematisches Argument dafür, aber ich denke, dass die Tatsache, dass der Gaußsche Kern tatsächlich auf einen unendlichen dimensionalen Raum abgebildet wird, etwas mit seinem Erfolg zu tun hat. Für den linearen und den polynomiellen Kern werden die Punktprodukte in endlichen dimensionalen Räumen genommen; daher scheint es mächtiger zu sein, Dinge in einem größeren Raum zu tun. Ich hoffe, jemand hat ein besseres Verständnis für diese Dinge. Das bedeutet auch, dass wenn wir andere Kerne mit unendlichen dimensionalen Räumen finden können, sie auch ziemlich mächtig sein sollten. Leider kenne ich keinen solchen Kernel.

Für Ihren letzten Punkt denke ich, dass Cauchy-PDF oder jedes andere PDF, das in irgendeiner Weise die Entfernung zu anderen Punkten misst, gleich gut funktionieren sollte. Auch hier habe ich kein gutes mathematisches Argument dafür, aber die Verbindung zum nächsten Nachbarn macht dies plausibel.

Bearbeiten:

Im Folgenden finden Sie einige Ideen, wie Sie sich einen Klassifikator vorstellen, der Gauß-Kernel als Klassifikatoren für die nächsten Nachbarn verwendet. Lassen Sie uns zunächst überlegen, was ein Klassifikator für den nächsten Nachbarn tut. Ein Klassifikator für den nächsten Nachbarn ist im Wesentlichen ein Standardklassifikator, der die Abstände zwischen Punkten als Eingaben verwendet. Stellen Sie sich formeller vor, wir erstellen eine Feature-Repräsentation für jeden Punkt im Datensatz, indem wir seinen Abstand zu allen anderen Punkten berechnen. Oben ist eine Abstandsfunktion. Ein Klassifikator für den nächsten Nachbarn sagt dann die Klassenbezeichnung für einen Punkt basierend auf dieser Feature-Darstellung und den Klassenbezeichnungen für die Daten voraus. wo$\phi_i$$x_i$

Die Art und Weise, wie ich über Kernel denke, ist, dass sie etwas Ähnliches tun. Sie erstellen eine Feature-Repräsentation jedes Punkts unter Verwendung seiner Kernel-Werte mit anderen Punkten im Dataset. Ähnlich wie im Fall des nächsten Nachbarn wäre dies formal gesehen Nun ist die Verbindung zum nächsten Nachbarn ganz offensichtlich; Wenn unsere Kernelfunktion ein Maß ist, das mit den Abstandsmaßen zusammenhängt, die wir in Klassifizierern für nächste Nachbarn verwenden, ähnelt unser kernelbasierter Klassifizierer einem Modell für nächste Nachbarn.

Hinweis: Die Klassifikatoren, die wir mit Hilfe von Kerneln trainieren, funktionieren nicht direkt mit diesen Repräsentationen, aber ich denke, das ist, was sie implizit tun.$\phi_i$

Der Grund dafür ist, dass die VC- Dimension für Gauß-Kernel unendlich ist und sie daher bei korrekten Werten für die Parameter (Sigma) eine beliebig große Anzahl von Samples korrekt klassifizieren können.

RBFs funktionieren gut, weil sie sicherstellen, dass die Matrix vollen Rang hat. Die Idee ist, dass und Terme außerhalb der Diagonale beliebig klein gemacht werden können, indem der Wert von verringert wird . Beachten Sie, dass der Kernel einem Skalarprodukt im Feature-Space entspricht. In diesem Merkmalsraum ist die Dimension unendlich (unter Berücksichtigung der Reihenexpansion des Exponentials). Man könnte dies so sehen, dass diese Punkte in verschiedenen Dimensionen projiziert werden, so dass Sie sie trennen können.$K(x_{i},x_{j})$$K(x_{i},x_{i}) > 0$$\sigma$

Betrachten Sie im Gegensatz dazu den Fall von linearen Körnern, die nur vier Punkte in der Ebene zerstören können.

Sie können sich dieses Papier ansehen , obwohl es sehr technisch ist. Eines der Standardbücher zu SVMs sollte dieses Konzept zugänglicher machen.