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} = (X^{'} X + a I_{d})^{- 1} X x

$\hat{y} = (\mathbf{X'X} + a\mathbf{I}_d)^{-1}\mathbf{X}x$

\hat{y}

$\hat{y}$

I_{d}

$\mathbf{I}_d$

d \times d

$d \times d$

x

$\mathbf{x}$

X

$\mathbf{X}$

n \times d

$n \times d$

n

$n$

x_{i} = (x_{i, 1}, . . ., x_{i, d}) \in R^{d}

$\mathbf{x}_i = (x_{i,1}, ..., x_{i,d})\in \mathbb{R}^d$

X = (\begin{matrix} x_{1, 1} & x_{1, 2} & \dots & x_{1, d} \\ x_{2, 1} & x_{2, 2} & \dots & x_{2, d} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ x_{n, 1} & x_{1, 2} & \dots & x_{n, d} \end{matrix})

$\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} = (K + a I_{d})^{- 1} k

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

K = (\begin{matrix} K (x_{1}, x_{1}) & K (x_{1}, x_{2}) & \dots & K (x_{1}, x_{n}) \\ K (x_{2}, x_{1}) & K (x_{2}, x_{2}) & \dots & K (x_{2}, x_{n}) \\ ⋮ & ⋮ & ⋱ & ⋮ \\ K (x_{n}, x_{1}) & K (x_{n}, x_{2}) & \dots & K (x_{n}, x_{n}) \end{matrix})

$\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 kolumna wektor funkcji jądra $\mathbf{k}$ $n \times 1$ $K$

k = (\begin{matrix} K (x_{1}, x) \\ K (x_{2}, x) \\ ⋮ \\ K (x_{n}, x) \end{matrix})

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

regression ridge-regression kernel-trick

— Spirala
źródło

„wydajność” ma inne znaczenie w statystyce. Miałeś na myśli „złożoność obliczeniową”? (w tytule)

— Memming

Miałem na myśli „wydajność algorytmiczną”. Chociaż prawdą jest, że moje pytania zasadniczo sprowadzają to do „złożoności obliczeniowej”.

— Helix

(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:

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.
Bernhard Schlkopf, Alexander J. Smola. Nauka za pomocą jąder: obsługa maszyn wektorowych, regularyzacja, optymalizacja i późniejsze wersje 2002

— Memming
źródło