Neigen RBF-Kernel-Matrizen dazu, schlecht konditioniert zu sein?

Ich verwende die RBF-Kernelfunktion, um einen kernelbasierten Algorithmus für maschinelles Lernen (KLPP) zu implementieren. Die resultierende Kernelmatrix ist extrem schlecht konditioniert. Die Bedingungsnummer der L2-Norm lautet $K$

K (i, j) = \exp (\frac{- (x_{i} - x_{j})^{2}}{σ_{m}^{2}})

$K(i,j)= \exp\left({\frac{-(x_{i}-x_{j})^2}{ \sigma_{m}^2}}\right)$

10^{17} - 10^{64}

$10^{17}-10^{64}$

Gibt es eine Möglichkeit, es gut konditioniert zu machen? Ich denke, Parameter muss eingestellt werden, aber ich weiß nicht genau, wie. $\sigma$

Vielen Dank!

linear-algebra machine-learning interpolation support-vector-machines ZeyuHu
quelle

, wenn Sie kleiner machen, verbessern Sie die Bedingungsnummer.

σ_{m}

$\sigma_m$

user189035

Antworten:

Durch Verringern der wird normalerweise die Bedingungsnummer verringert. $\sigma_m$

Kernelmatrizen können jedoch für jede Basisfunktion oder Punktverteilung singulär oder nahezu singulär werden, vorausgesetzt, die Basisfunktionen überlappen sich. Der Grund dafür ist eigentlich ganz einfach:

Die Kernmatrix ist singulär, wenn ihre Determinante Null ist. $K$ $\det(K)$
Das Vertauschen von zwei Punkten und in Ihrer Interpolation entspricht dem Austausch von zwei Zeilen in , vorausgesetzt, Ihre Versuchspunkte bleiben konstant. $x_i$ $x_j$ $K$
Durch Vertauschen von zwei Zeilen in einer Matrix wird das Vorzeichen der Determinante geändert.

Stellen Sie sich nun vor, Sie wählen zwei Punkte und und drehen sie langsam, sodass sie die Plätze wechseln. Währenddessen wechselt die Determinante von das Vorzeichen und wird irgendwann dazwischen Null. Zu diesem Zeitpunkt ist per Definition singulär. $x_i$ $x_j$ $K$ $K$

Pedro
quelle

Sind K-Matrizen nicht symmetrisch - beim Vertauschen von zwei Punkten werden Zeilen und Spalten ausgetauscht?

Denis

@Denis Dies ist nur dann der Fall, wenn Ihre Knoten und Testpunkte identisch sind und Sie beide verschieben. Aus diesem Grund schrieb ich in der zweiten Kugel "vorausgesetzt, Ihre Testpunkte bleiben konstant".

Pedro

Die Kernel-Matrix der Gaußschen (die Frage des OP) ist sowieso positiv semidefinit?

Denis

@Denis: Auch dies ist eine Frage, wie Sie Ihr RBF-Interpolationsproblem definieren. Betrachten Sie den allgemeinsten Fall, in dem RBFs auf den Punkten zentriert sind , , und Sie die Interpolation an den Punkten , minimieren möchten . Im Beispiel des Posters wird und . Wenn wir zunächst und und dann einfach , können wir trivial Singular erzeugen .

N

$N$

x_{i}

$x_i$

i = 1 \dots N

$i=1\dots N$

M

$M$

ξ_{j}

$\xi_j$

j = 1 \dots M

$j=1\dots M$

M = N

$M=N$

ξ_{j} = x_{i}

$\xi_j=x_i$

M \leftarrow N

$M\leftarrow N$

ξ_{j} \leftarrow x_{i}

$\xi_j \leftarrow x_i$

x_{i}

$x_i$

K

$K$

Pedro

Ein paar Vorschläge:

Wählen Sie die durchschnittliche Entfernung | zufälliges - am nächsten . (Eine billige Näherung für Punkte, die gleichmäßig im Einheitswürfel in , ist 0,5 / .) Wir wollen groß sein für Nähe von , klein für Hintergrundgeräusche; Zeichnen Sie das für ein paar zufällige . $\sigma \sim$ $x$ $x_i$ $N$ $\mathbb{R}^d, d\ 2 .. 5$ $N^{1/d}$
$\phi( |x - x_i| )$ $x_i$ $x$ $x$
Verschieben Sie von 0, , oder so; das heißt, regulieren. $K$ $K \to K + \lambda I$ $\lambda \sim 10^{-6}$
Schauen Sie sich die Gewichte aus der Lösung . Wenn einige immer noch riesig sind (unabhängig von der Bedingungsnummer), würde dies Boyd (unten) bestätigen, dass der Gaußsche RBF grundsätzlich schwach ist. $(K + \lambda I) w = f$

(Eine Alternative zu RBF ist die Inverse-Distance-Gewichtung (IDW). Sie hat den Vorteil der automatischen Skalierung, die für die nächsten Entfernungen 1 2 3 wie für 100 200 300 Außerdem finde ich die explizite Benutzerauswahl von , der Zahl von nahen Nachbarn zu berücksichtigen, klarer als Rastersuche auf .) $\dots$ $\dots$ $Nnear$ $\sigma, \lambda$

John P. Boyd, Die Nutzlosigkeit der schnellen Gauß-Transformation zur Summierung von Gaußschen radialen Basisfunktionsreihen , sagt

Der Gaußsche RBF-Interpolant ist für die meisten Reihen in dem Sinne schlecht konditioniert, dass der Interpolant die kleine Differenz von Termen mit exponentiell großen Koeffizienten ist.

Hoffe das hilft; Bitte teilen Sie Ihre Erfahrungen.

denis
quelle