Metoda Nystroem dla aproksymacji jądra

Czytałem o metodzie Nyström do aproksymacji jądra niskiej rangi. Ta metoda jest zaimplementowana w scikit-learn [1] jako metoda rzutowania próbek danych na przybliżenie niskiego rzędu mapowania cech jądra.

Zgodnie z moją najlepszą wiedzą, biorąc pod uwagę zestaw szkoleniowy i funkcję jądra, generuje przybliżenie niskiego rzędu macierzy jądra poprzez zastosowanie SVD do a . $\{x_i\}_{i=1}^n$ $n \times n$ $K$ $W$ $C$

$K = \left [ \begin{array}{cc} W & K_{21}^T \\ K_{21} & K_{22} \end{array} \right ]$ $C = \left [\begin{array}{cc} W \\ K_{21} \end{array}\right ]$ , $W \in \mathbb{R}^{l\times l}$

Nie rozumiem jednak, w jaki sposób można zastosować przybliżenie niskiego rzędu macierzy jądra do projekcji nowych próbek w przybliżonej przestrzeni cech jądra . Artykuły, które znalazłem (np. [2]), nie są zbyt pomocne, ponieważ są mało dydaktyczne.

Ciekawi mnie też złożoność obliczeniowa tej metody, zarówno w fazie szkoleniowej, jak i testowej.

[1] http://scikit-learn.org/stable/modules/kernel_approximation.html#nystroem-kernel-approx

[2] http://www.jmlr.org/papers/volume13/kumar12a/kumar12a.pdf

— Daniel López
źródło

Przyjmijmy przybliżenie Nyström w taki sposób, aby wyjaśnić odpowiedzi na pytania.

Kluczowym założeniem w Nyström jest to, że funkcja jądra ma rangę . (Naprawdę zakładamy, że ma w przybliżeniu rangę , ale dla uproszczenia udajmy, że na razie ma dokładnie rangę .) Oznacza to, że każda macierz jądra będzie miała najwyżej , a w szczególności jest ranga $m$ $m$ $m$ $m$

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

$K = \begin{bmatrix} k(x_1, x_1) & \dots & k(x_1, x_n) \\ \vdots & \ddots & \vdots \\ k(x_n, x_1) & \dots & k(x_n, x_n) \end{bmatrix} ,$

m

$m$ . Dlatego są

m

$m$ niezerowe wartości własne i możemy napisać składową eigend

K

$K$ tak jak

K = U Λ U^{T}

$K = U \Lambda U^T$ z wektorami własnymi przechowywanymi w

U

$U$ , o kształcie

n \times m

$n \times m$ oraz wartości własne ułożone w

Λ

$\Lambda$ , an

m \times m

$m \times m$ macierz diagonalna.

Wybierzmy $m$ elementy, zwykle jednolicie losowe, ale możliwe, że według innych schematów - w tej uproszczonej wersji liczy się tylko to $K_{11}$ mieć pełną rangę. Kiedy to zrobimy, po prostu ponownie oznakuj punkty, aby otrzymać blok jądra w blokach:

K = [\begin{matrix} K_{11} & K_{21}^{T} \\ K_{21} & K_{22} \end{matrix}],

$K = \begin{bmatrix} K_{11} & K_{21}^T \\ K_{21} & K_{22} \end{bmatrix} ,$ gdzie oceniamy każdy wpis w

K_{11}

$K_{11}$ (który jest

m \times m

$m \times m$ ) i

K_{21}

$K_{21}$ (

(n - m) \times m

$(n-m) \times m$ ), ale nie chcę oceniać żadnych wpisów w

K_{22}

$K_{22}$ .

Teraz możemy podzielić skład eigend według tej struktury bloku:

\begin{aligned} K & = U Λ U^{T} \\ = [\begin{matrix} U_{1} \\ U_{2} \end{matrix}] Λ {[\begin{matrix} U_{1} \\ U_{2} \end{matrix}]}^{T} \\ = [\begin{matrix} U_{1} Λ U_{1}^{T} & U_{1} Λ U_{2}^{T} \\ U_{2} Λ U_{1}^{T} & U_{2} Λ U_{2}^{T} \end{matrix}], \end{aligned}

$\begin{align} K &= U \Lambda U^T \\&= \begin{bmatrix}U_1 \\ U_2\end{bmatrix} \Lambda \begin{bmatrix}U_1 \\ U_2\end{bmatrix}^T \\&= \begin{bmatrix} U_1 \Lambda U_1^T & U_1 \Lambda U_2^T \\ U_2 \Lambda U_1^T & U_2 \Lambda U_2^T \end{bmatrix} ,\end{align}$ gdzie

U_{1}

$U_1$ jest

m \times m

$m \times m$ i

U_{2}

$U_2$ jest

(n - m) \times m

$(n-m) \times m$ . Ale zauważ, że teraz mamy

K_{11} = U_{1} Λ U_{1}^{T}

$K_{11} = U_1 \Lambda U_1^T$ . Więc możemy znaleźć

U_{1}

$U_1$ i

Λ

$\Lambda$ poprzez składanie znanej matrycy

K_{11}

$K_{11}$ .

My też to wiemy $K_{21} = U_2 \Lambda U_1^T$ . Tutaj wiemy wszystko w tym równaniu oprócz $U_2$ , abyśmy mogli rozwiązać, co implikuje wartość własna: pomnóż przez prawo obie strony $(\Lambda U_1^T)^{-1} = U_1 \Lambda^{-1}$ dostać

U_{2} = K_{21} U_{1} Λ^{- 1} .

$U_2 = K_{21} U_1 \Lambda^{-1} .$ Teraz mamy wszystko, co musimy ocenić

K_{22}

$K_{22}$ :

\begin{aligned} K_{22} & = U_{2} Λ U_{2}^{T} \\ = (K_{21} U_{1} Λ^{- 1}) Λ {(K_{21} U_{1} Λ^{- 1})}^{T} \\ = K_{21} U_{1} (Λ^{- 1} Λ) Λ^{- 1} U_{1}^{T} K_{21}^{T} \\ = K_{21} U_{1} Λ^{- 1} U_{1}^{T} K_{21}^{T} \\ (*) & = K_{21} K_{11}^{- 1} K_{21}^{T} \\ (**) & = (K_{21} K_{11}^{- \frac{1}{2}}) {(K_{21} K_{11}^{- \frac{1}{2}})}^{T} . \end{aligned}

$\begin{align} K_{22} &= U_2 \Lambda U_2^T \\&= \left(K_{21} U_1 \Lambda^{-1}\right) \Lambda \left(K_{21} U_1 \Lambda^{-1}\right)^T \\&= K_{21} U_1 (\Lambda^{-1} \Lambda) \Lambda^{-1} U_1^T K_{21}^T \\&= K_{21} U_1 \Lambda^{-1} U_1^T K_{21}^T \\&= K_{21} K_{11}^{-1} K_{21}^T \tag{*} \\&= \left( K_{21} K_{11}^{-\frac12} \right) \left( K_{21} K_{11}^{-\frac12} \right)^T \tag{**} .\end{align}$

W (*) znaleźliśmy wersję osadzania Nyström, którą mogłeś zobaczyć jako definicję. To mówi nam o efektywnych wartościach jądra, które przypisujemy blokowi $K_{22}$ .

W (**) widzimy, że macierz funkcji $K_{21} K_{11}^{-\frac12}$ , który jest kształtem $(n-m) \times m$ , odpowiada tym przypisanym wartościom jądra. Jeśli użyjemy $K_{11}^{\frac12}$ dla $m$ punktów, mamy zestaw $m$ cechy wymiarowe

Φ = [\begin{matrix} K_{11}^{\frac{1}{2}} \\ K_{21} K_{11}^{- \frac{1}{2}} \end{matrix}] .

$\Phi = \begin{bmatrix} K_{11}^{\frac12} \\ K_{21} K_{11}^{-\frac12} \end{bmatrix} .$ Możemy to szybko zweryfikować

Φ

$\Phi$ odpowiada poprawnej macierzy jądra:

\begin{aligned} Φ Φ^{T} & = [\begin{matrix} K_{11}^{\frac{1}{2}} \\ K_{21} K_{11}^{- \frac{1}{2}} \end{matrix}] {[\begin{matrix} K_{11}^{\frac{1}{2}} \\ K_{21} K_{11}^{- \frac{1}{2}} \end{matrix}]}^{T} \\ = [\begin{matrix} K_{11}^{\frac{1}{2}} K_{11}^{\frac{1}{2}} & K_{11}^{\frac{1}{2}} K_{11}^{- \frac{1}{2}} K_{21}^{T} \\ K_{21} K_{11}^{- \frac{1}{2}} K_{11}^{\frac{1}{2}} & K_{21} K_{11}^{- \frac{1}{2}} K_{11}^{- \frac{1}{2}} K_{21}^{T} \end{matrix}] \\ = [\begin{matrix} K_{11} & K_{21}^{T} \\ K_{21} & K_{21} K_{11}^{- 1} K_{21}^{T} \end{matrix}] \\ = K . \end{aligned}

$\begin{align} \Phi \Phi^T &= \begin{bmatrix} K_{11}^{\frac12} \\ K_{21} K_{11}^{-\frac12} \end{bmatrix} \begin{bmatrix} K_{11}^{\frac12} \\ K_{21} K_{11}^{-\frac12} \end{bmatrix}^T \\&=\begin{bmatrix} K_{11}^{\frac12} K_{11}^{\frac12} & K_{11}^{\frac12} K_{11}^{-\frac12} K_{21}^T \\ K_{21} K_{11}^{-\frac12} K_{11}^{\frac12} & K_{21} K_{11}^{-\frac12} K_{11}^{-\frac12} K_{21}^T \end{bmatrix} \\&=\begin{bmatrix} K_{11} & K_{21}^T \\ K_{21} & K_{21} K_{11}^{-1} K_{21}^T \end{bmatrix} \\&= K .\end{align}$

Więc wszystko, co musimy zrobić, to trenować nasz regularny model uczenia się z $m$ cechy wymiarowe $\Phi$ . Będzie to dokładnie to samo (przy założonych przez nas założeniach), jak wersja jądra problemu uczenia się $K$ .

Teraz dla pojedynczego punktu danych $x$ , funkcje w $\Phi$ odpowiada

ϕ (x) = [\begin{matrix} k (x, x_{1}) & \dots & k (x, x_{m}) \end{matrix}] K_{11}^{- \frac{1}{2}} .

$\phi(x) = \begin{bmatrix} k(x, x_1) & \dots & k(x, x_m) \end{bmatrix} K_{11}^{-\frac12} .$ Za punkt

x

$x$ w partycji 2 wektor

[\begin{matrix} k (x, x_{1}) & \dots & k (x, x_{m}) \end{matrix}]

$\begin{bmatrix} k(x, x_1) & \dots & k(x, x_m) \end{bmatrix}$ to tylko odpowiedni wiersz

K_{21}

$K_{21}$ , dzięki czemu zestawienie ich daje nam

K_{21} K_{11}^{- \frac{1}{2}}

$K_{21} K_{11}^{-\frac12}$ - więc

ϕ (x)

$\phi(x)$ zgadza się na punkty w partycji 2. Działa również w partycji 1: tam wektor jest rzędem

K_{11}

$K_{11}$ , więc układanie ich w stos robi się

K_{11} K_{11}^{- \frac{1}{2}} = K_{11}^{\frac{1}{2}}

$K_{11} K_{11}^{-\frac12} = K_{11}^{\frac12}$ , ponownie zgadzając się z

Φ

$\Phi$ . Więc ... to nadal dotyczy punktu testowego, którego nie widać na szkoleniu

x_{new}

$x_\text{new}$ . Po prostu robisz to samo:

Φ_{test} = K_{test, 1} K_{11}^{- \frac{1}{2}} .

$\Phi_\text{test} = K_{\text{test},1} K_{11}^{-\frac12} .$ Ponieważ założyliśmy, że jądro ma rangę

m

$m$ , macierz

[\begin{matrix} K_{train} & K_{train,test} \\ K_{test,train} & K_{test} \end{matrix}]

$\begin{bmatrix}K_{\text{train}} & K_{\text{train,test}} \\ K_{\text{test,train}} & K_{\text{test}} \end{bmatrix}$ ma również rangę

m

$m$ oraz rekonstrukcję

K_{test}

$K_\text{test}$ jest wciąż dokładnie taka sama logika jak dla

K_{22}

$K_{22}$ .

Powyżej przyjęliśmy, że macierz jądra

K

$K$ był dokładnie w randze

m

$m$ . Zazwyczaj tak się nie dzieje; na przykład dla jądra Gaussa,

K

$K$ ma zawsze rangę

n

$n$ , ale te ostatnie wartości własne zwykle spadają dość szybko, więc będzie zbliżona do macierzy rangi

m

$m$ oraz nasze rekonstrukcje

K_{21}

$K_{21}$ lub

K_{test, 1}

$K_{\text{test},1}$ będą zbliżone do prawdziwych wartości, ale nie dokładnie takie same. Będą lepsze rekonstrukcje, im bliżej własnej przestrzeni

K_{11}

$K_{11}$ dojdzie do tego

K

$K$ ogólnie rzecz biorąc, dlatego wybór właściwego

m

$m$ punkty są ważne w praktyce.

Zauważ też, że jeśli $K_{11}$ ma dowolne zerowe wartości własne, możesz zamienić odwrotne na pseudoinwersyjne i wszystko nadal działa; po prostu wymieniasz $K_{21}$ w rekonstrukcji z $K_{21} K_{11}^\dagger K_{11}$ .

Możesz użyć SVD zamiast eigendecomposition, jeśli chcesz; od $K$ jest psd, są tym samym, ale SVD może być nieco bardziej odporny na niewielki błąd numeryczny w macierzy jądra i tym podobne, więc to właśnie robi scikit-learn. Rzeczywista implementacja scikit-learn to robi, chociaż wykorzystuje $\max(\lambda_i, 10^{-12})$ w odwrotnym zamiast pseudoinwersyjnym.

— Dougal
źródło

Kiedy

A

$A$ jest dodatnim półfinałem, eigendecomposition

U Λ U^{T}

$U \Lambda U^T$ pokrywa się z SVD. scikit-learn, ponieważ z powodu błędu numerycznego

A

$A$ może być nieco inny niż psd, zamiast tego oblicza

U Σ V^{T}

$U \Sigma V^T$ i używa

A^{- \frac{1}{2}} = V Σ^{- \frac{1}{2}} V^{T}

$A^{-\frac12} = V \Sigma^{-\frac12} V^T$ , tak że

A

$A$ stają się funkcje

A V Σ^{- \frac{1}{2}} V^{T} = U Σ V^{T} V Σ^{- \frac{1}{2}} V^{T} = U Σ^{\frac{1}{2}} V^{T} = A^{\frac{1}{2}}

$A V \Sigma^{-\frac12} V^T = U \Sigma V^T V \Sigma^{-\frac12} V^T = U \Sigma^{\frac12} V^T = A^{\frac12}$ . Zasadniczo to samo.

— Dougal

Ups, przepraszam, tak, używają

U Σ^{- \frac{1}{2}} V^{T} = K^{- \frac{1}{2}}

$U \Sigma^{-\frac12} V^T = K^{-\frac12}$ . Od tego czasu to wszystko nie ma znaczenia

U \approx V

$U \approx V$ , ale ponieważ dokonują transpozycji funkcji dla

K_{11}

$K_{11}$ skończy jako

U Σ V^{T} V Σ^{- \frac{1}{2}} U^{T} = U Σ^{\frac{1}{2}} U^{T}

$U\Sigma V^T V \Sigma^{-\frac12} U^T = U \Sigma^{\frac12} U^T$ .

— Dougal

Podniesienie macierzy diagonalnej do potęgi jest tym samym, co podniesienie każdego elementu do potęgi, i

x^{- \frac{1}{2}} = 1 / \sqrt{x}

$x^{-\frac12} = 1 / \sqrt x$ . W notacji nadawania numpy mnożenie elementarne przez wektor jest takie samo jak mnożenie przez prawo macierzy diagonalnej. Ponadto ten kod wykorzystuje

V

$V$ znaczy to, co dzwoniłem

V^{T}

$V^T$ .

— Dougal

Ups, przepraszam, to powinno być tylko do

x_{m}

$x_m$ (w zmienionym oznaczeniu, aby były to punkty bazowe Nyström). Naprawię.

— Dougal

x

$x$ jest punktem danych, jego wymiar nie jest tu określony.

x

$x$ może być w

R^{d}

$\mathbb R^d$ , lub może to być ciąg znaków lub coś takiego; po prostu to powiedz

x \in X

$x \in \mathcal X$ , tak że

k : X \times X \to R

$k : \mathcal X \times \mathcal X \to \mathbb R$ . Następnie

ϕ : X \to R^{m}

$\phi : \mathcal X \to \mathbb R^m$ po prostu się kumuluje

k (x, x_{i})

$k(x, x_i)$ dla

m

$m$ różne dane wejściowe.

— Dougal