Wydajność regresji grzbietu jądra

Regresję grzbietu można wyrazić jako gdzie jest przewidywaną etykietą , do identyfikacji macierzy pożądanego obiektu próbują znaleźć etykietę i macierz PRZEDMIOTY, takie, że:

$$\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}$$

Możemy jądro to w następujący sposób:

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

gdzie to macierzy funkcji jądra$\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}$$

i n \ razy 1 kolumna wektor funkcji jądra K$\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}$$

Pytania:

(a) jeśli istnieje więcej obiektów niż wymiary ma to sens, aby nie używać jądra? Np. Niech będzie macierzą , a następnie będzie a my skończymy odwracaniem macierzy zamiast macierzy musielibyśmy odwrócić, gdybyśmy użyli jąder. Czy to oznacza, że ​​jeśli nie powinniśmy używać jąder?$\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) czy należy używać najprostszego możliwego jądra? Wydaje się, że jądra w regresji grzbietowej są używane do negowania wpływów wymiarowości i do niewykorzystywania pewnych właściwości przestrzeni cech (w przeciwieństwie do maszyn wektorów nośnych). Chociaż jądra mogą zmieniać odległości między obiektami, czy są jakieś popularne jądra często używane w regresji grzbietu?

(c) co jest czas złożoność regresji kalenicy i / lub jądra regresji Ridge?$O$

(a) Celem użycia jądra jest rozwiązanie problemu regresji nieliniowej w tym przypadku. Dobre jądro pozwoli ci rozwiązać problemy w potencjalnie nieskończenie wymiarowej przestrzeni cech. Ale użycie liniowego jądra i wykonanie regresji grzbietu jądra w podwójnej przestrzeni jest równoznaczne z rozwiązaniem problemu w przestrzeni pierwotnej , tj. nie przynosi żadnej korzyści (jest po prostu znacznie wolniejszy, gdy liczba próbek rośnie, jak zauważyłeś).$K(\mathbf{x,y}) = \mathbf{x}^\top \mathbf{y}$

(b) Jednym z najpopularniejszych wyborów jest kwadratowe jądro wykładnicze który jest uniwersalny (patrz odnośnik poniżej). Istnieje wiele różnych jąder, a każde z nich wywoła inny produkt wewnętrzny (a zatem metryczny) do przestrzeni funkcji.$K(x,y) = \exp(-\frac{\tau}{2} ||\mathbf{x}-\mathbf{y}||^2)$

(c) Prosta implementacja wymaga rozwiązania liniowego równania wielkości , więc jest to . Istnieje wiele szybszych metod aproksymacji, takich jak aproksymacja Nyströma. Jest to obszar aktywnych badań.$n$$O(n^3)$

Bibliografia:

1. Bharath Sriperumbudur, Kenji Fukumizu i Gert Lanckriet. O związku między uniwersalnością, charakterystycznymi ziarnami a osadzaniem miar w RKHS. Journal of Machine Learning Research, 9: 773–780, 2010.
2. Bernhard Schlkopf, Alexander J. Smola. Nauka za pomocą jąder: obsługa maszyn wektorowych, regularyzacja, optymalizacja i późniejsze wersje 2002