Kernel Ridge Regressionseffizienz

Die Ridge-Regression kann ausgedrückt werden als wobei die vorhergesagte Bezeichnung ist , die Identifizierungsmatrix, das Objekt, für das wir eine Bezeichnung finden möchten, und die Matrix von Objekten so dass:

$$\hat{y} = (\mathbf{X'X} + a\mathbf{I}_d)^{-1}\mathbf{X}x$$ $\hat{y}$$\mathbf{I}_d$$d \times d$$\mathbf{x}$$\mathbf{X}$$n \times d$$n$$\mathbf{x}_i = (x_{i,1}, ..., x_{i,d})\in \mathbb{R}^d$

$$\mathbf{X} = \begin{pmatrix} x_{1,1} & x_{1,2} & \ldots & x_{1,d}\\ x_{2,1} & x_{2,2} & \ldots & x_{2,d}\\ \vdots & \vdots & \ddots & \vdots\\ x_{n,1} & x_{1,2} &\ldots & x_{n,d} \end{pmatrix}$$

Wir können dies wie folgt kernelisieren:

$$\hat{y} = (\mathbf{\mathcal{K}} + a\mathbf{I}_d)^{-1} \mathbf{k}$$

Dabei ist die Matrix der Kernelfunktionen$\mathbf{\mathcal{K}}$$n \times n$$K$

$$\mathcal{K} = \begin{pmatrix} K(\mathbf{x}_1,\mathbf{x}_1) & K(\mathbf{x}_1,\mathbf{x}_2) & \ldots & K(\mathbf{x}_1,\mathbf{x}_n)\\ K(\mathbf{x}_2,\mathbf{x}_1) & K(\mathbf{x}_2,\mathbf{x}_2) & \ldots & K(\mathbf{x}_2,\mathbf{x}_n)\\ \vdots & \vdots & \ddots & \vdots\\ K(\mathbf{x}_n,\mathbf{x}_1) & K(\mathbf{x}_n,\mathbf{x}_2) &\ldots & K(\mathbf{x}_n,\mathbf{x}_n) \end{pmatrix}$$

und der Spaltenvektor der Kernfunktionen$\mathbf{k}$$n \times 1$$K$

$$\mathbf{k} = \begin{pmatrix} K(\mathbf{x}_1,\mathbf{x})\\ K(\mathbf{x}_2,\mathbf{x}) \\ \vdots \\ K(\mathbf{x}_n,\mathbf{x}) \end{pmatrix}$$

Fragen:

(a) Wenn es mehr Objekte als Dimensionen gibt, ist es sinnvoll, keine Kernel zu verwenden? Eg lassen sein Matrix dann wird eine sein und wir werden ein Ende Invertieren - Matrix anstelle der Matrix müssten wir invertieren, wenn wir Kernel verwenden würden. Bedeutet dies, dass wir keine Kernel verwenden sollten , wenn ?$\mathbf{x}_i$$\mathbf{X}$$50 \times 3$$\mathbf{X}'\mathbf{X}$$3 \times 3$$3 \times 3$$50 \times 50$$d \leq n$

(b) Sollte der einfachste Kernel verwendet werden? Es scheint, dass Kernel in der Ridge-Regression verwendet werden, um die Einflüsse der Dimensionalität zu negieren und bestimmte Eigenschaften des Merkmalsraums nicht zu nutzen (im Gegensatz zu Support-Vektor-Maschinen). Obwohl Kernel die Abstände zwischen Objekten ändern können, gibt es beliebte Kernel, die häufig bei der Ridge-Regression verwendet werden?

(c) Wie hoch ist die Zeit-Komplexität der Ridge-Regression und / oder der Kernel-Ridge-Regression?$O$

(a) Der Zweck der Verwendung eines Kernels besteht darin, in diesem Fall ein nichtlineares Regressionsproblem zu lösen. Mit einem guten Kernel können Sie Probleme in einem möglicherweise unendlich dimensionalen Merkmalsraum lösen. Die Verwendung eines linearen Kernels und die Durchführung der Kernel-Ridge-Regression im dualen Raum entspricht der Lösung des Problems im ursprünglichen Raum Das heißt, es bringt keinen Vorteil (es ist nur viel langsamer, wenn die Anzahl der Proben wächst, wie Sie beobachtet haben).$K(\mathbf{x,y}) = \mathbf{x}^\top \mathbf{y}$

(b) Eine der beliebtesten Optionen ist der quadratische Exponentialkern die universell ist (siehe unten). Es gibt viele, viele Kernel, und jeder von ihnen induziert ein anderes inneres Produkt (und damit eine andere Metrik) für Ihren Feature-Space.$K(x,y) = \exp(-\frac{\tau}{2} ||\mathbf{x}-\mathbf{y}||^2)$

(c) Eine einfache Implementierung erfordert das Lösen einer linearen Gleichung der Größe , also ist es . Es gibt viele schnellere Approximationsmethoden wie die Nyström-Approximation. Dies ist ein Bereich aktiver Forschung.$n$$O(n^3)$

Verweise:

1. Bharath Sriperumbudur, Kenji Fukumizu und Gert Lanckriet. Zum Verhältnis von Universalität, charakteristischen Kerneln und RKHS-Einbettung von Maßnahmen. Journal of Machine Learning Research, 9: 773–780, 2010.
2. Bernhard Schlkopf, Alexander J. Smola. Lernen mit Kerneln: Unterstützung von Vektormaschinen, Regularisierung, Optimierung und darüber hinaus 2002