Różnica między regresją pierwotną, podwójną i regresją jądra

Jaka jest różnica między regresją pierwotną , podwójną i regresją jądra ? Ludzie używają wszystkich trzech, a ze względu na odmienną notację, którą wszyscy używają z różnych źródeł, trudno mi się naśladować.

Więc czy ktoś może mi powiedzieć prostymi słowami, jaka jest różnica między tymi trzema? Ponadto, jakie mogą być zalety lub wady każdego z nich i jaka może być ich złożoność?

Krótka odpowiedź: bez różnicy między Primal i Dual - chodzi tylko o sposób dotarcia do rozwiązania. Regresja grzbietu jądra jest zasadniczo taka sama jak zwykła regresja grzbietu, ale wykorzystuje sztuczkę jądra, aby przejść nieliniowo.

Regresja liniowa

Po pierwsze, zwykła regresja liniowa metodą najmniejszych kwadratów próbuje dopasować linię prostą do zbioru punktów danych w taki sposób, aby suma błędów kwadratu była minimalna.

Parametryzujemy linię najlepszego dopasowania za pomocą $\mathbb w$ dla każdego punktu danych $(\mathbf x_i, y_i)$ chcemy, aby $\mathbf w^T \mathbf x_i \approx y_i$ . Niech $e_i = y_i - \mathbf w^T \mathbf x_i$ będzie błędem - odległość między wartościami przewidywanymi i prawdziwymi. Naszym celem jest więc zminimalizowanie sumy błędów do kwadratu $\sum e_i^2 = \| \mathbf e \|^2 = \| X \mathbf w - \mathbf y \|^2$gdzie $X = \begin{bmatrix} — \mathbf x_1 \,— \\ — \mathbf x_2 \,— \\ \vdots \\ — \mathbf x_n \,— \end{bmatrix}$- macierz danych z każdego$\mathbf x_i$jest do tego rzędu, a$\mathbf y = (y_1 , \ ... \ , y_n)$wektora ze wszystkimi$y_i$„s.

Zatem celem jest , a rozwiązaniem jest (znane jako „równanie normalne”).$\min\limits_{\mathbf w} \| X \mathbf w - \mathbf y \|^2$$\mathbf w = (X^T X)^{-1} X^T \mathbf y$

Dla nowego niewidzialnego punktu danych przewidujemy jego wartość docelową jako .$\mathbf x$$\hat y$$\hat y = \mathbf w^T \mathbf x$

Regresja Ridge

Kiedy istnieje wiele skorelowanych zmiennych w modelach regresji liniowej, współczynniki mogą stać się słabo określone i mieć dużą wariancję. Jednym z rozwiązań tego problemu jest ograniczenie ciężary , żeby nie przekroczyć jakąś budżetową . Jest to równoważne z zastosowaniem -regulalizacji, znanej również jako „rozpad masy”: zmniejszy wariancję kosztem czasami utraty poprawnych wyników (tj. Poprzez wprowadzenie pewnej tendencyjności).$\mathbf w$$\mathbf w$$C$$L_2$

Cel staje się teraz , gdzie jest parametrem regularyzacji. Przechodząc przez matematykę, otrzymujemy następujące rozwiązanie: . Jest bardzo podobny do zwykłej regresji liniowej, ale tutaj dodajemy do każdego elementu diagonalnego .$\min\limits_{\mathbf w} \| X \mathbf w - y \|^2 + \lambda \, \| \mathbf w \|^2$$\lambda$$\mathbf w = (X^T X + \lambda \, I )^{-1} X^T \mathbf y$$\lambda$$X^T X$

Zauważ, że możemy ponownie napisać jako (szczegóły tutaj ). Dla nowego niewidzialnego punktu danych przewidujemy jego wartość docelową jako . Niech . Następnie .$\mathbf w$$\mathbf w = X^T \, (X X^T + \lambda \, I)^{-1} \mathbf y$$\mathbf x$$\hat y$$\hat y = \mathbf x^T \mathbf w = \mathbf x^T X^T \, (X X^T + \lambda \, I)^{-1} \mathbf y$$\boldsymbol \alpha = (X X^T + \lambda \, I)^{-1} \mathbf y$Y = x T X t α = n Σ i = 1 α i ⋅ x t x i$\hat y = \mathbf x^T X^T \boldsymbol \alpha = \sum\limits_{i=1}^{n} \alpha_i \cdot \mathbf x^T \mathbf x_i$

Regresja Ridge Dual Form

Możemy inaczej spojrzeć na nasz cel - i zdefiniować następujący problem programu kwadratowego:

$\min\limits_{\mathbf e, \mathbf w} \sum\limits_{i = 1}^n e_i^2$ st dla i .$e_i = y_i - \mathbf w^T \mathbf x_i$$i = 1 \, .. \, n$$\| \mathbf w \|^2 \leqslant C$

Jest to ten sam cel, ale wyrażony nieco inaczej, a tutaj ograniczenie wielkości jest wyraźne. Aby go rozwiązać, definiujemy Lagrangian - jest to pierwotna postać zawierająca zmienne pierwotne i . Następnie optymalizujemy go wrt i . Aby uzyskać podwójne sformułowanie, umieściliśmy znalezione i powrotem w .$\mathbf w$$\mathcal L_p(\mathbf w, \mathbf e ; C)$$\mathbf w$$\mathbf e$$\mathbf e$$\mathbf w$$\mathbf e$$\mathbf w$$\mathcal L_p(\mathbf w, \mathbf e ; C)$

Tak więc . Biorąc pochodne wrt i , otrzymujemy i . Pozwalając i umieszczenie i tylnej do , otrzymujemy podwójny Lagrangian$\mathcal L_p(\mathbf w, \mathbf e ; C) = \| \mathbf e \|^2 + \boldsymbol \beta^T (\mathbf y - X \mathbf w - \mathbf e) - \lambda \, (\| \mathbf w \|^2 - C)$$\mathbf w$$\mathbf e$$\mathbf e = \cfrac{1}{2} \boldsymbol \beta$$\mathbf w = \cfrac{1}{2 \lambda} X^T \boldsymbol \beta$$\boldsymbol \alpha = \cfrac{1}{2 \lambda} \boldsymbol \beta$$\mathbf e$$\mathbf w$$\mathcal L_p(\mathbf w, \mathbf e ; C)$$\mathcal L_d(\boldsymbol \alpha, \lambda; C) = -\lambda^2 \| \boldsymbol \alpha \|^2 + 2 \lambda \, \boldsymbol \alpha^T y - \lambda \| X^T \boldsymbol \alpha \| - \lambda C$ . Jeśli weźmiemy pochodną wrt , otrzymamy - taka sama odpowiedź, jak w przypadku zwykłej regresji Kernel Ridge. Nie ma potrzeby pobierania pochodnej wrt - zależy to od , który jest parametrem regularyzacji - i sprawia, że parametr regularyzacji.$\boldsymbol \alpha$$\boldsymbol \alpha = (XX^T - \lambda I)^{-1} \mathbf y$$\lambda$$C$$\lambda$

Następnie umieść w pierwotnym rozwiązaniu formy dla , i uzyskaj . Zatem podwójna forma daje takie samo rozwiązanie jak zwykle regresja Ridge'a i jest to tylko inny sposób na znalezienie tego samego rozwiązania.$\boldsymbol \alpha$$\mathbf w$$\mathbf w = \cfrac{1}{2 \lambda} X^T \boldsymbol \beta = X^T \boldsymbol \alpha$

Regresja grzbietu jądra

Jądra służą do obliczania iloczynu wewnętrznego dwóch wektorów w pewnej przestrzeni cech, nawet jej nie odwiedzając. Możemy wyświetlić jądro jako , chociaż nie wiemy, co to jest - wiemy tylko, że istnieje. Istnieje wiele jąder, np. RBF, Polynonial itp.$k$$k(\mathbf x_1, \mathbf x_2) = \phi(\mathbf x_1)^T \phi(\mathbf x_2)$$\phi(\cdot)$

Możemy użyć jąder, aby nasza regresja Ridge'a była nieliniowa. Załóżmy, że mamy jądro . Niech będzie macierzą, w której każdy wiersz to , tj.$k(\mathbf x_1, \mathbf x_2) = \phi(\mathbf x_1)^T \phi(\mathbf x_2)$$\Phi(X)$$\phi(\mathbf x_i)$$\Phi(X) = \begin{bmatrix} — \phi(\mathbf x_1) \,— \\ — \phi(\mathbf x_2) \,— \\ \vdots \\ — \phi(\mathbf x_n) \,— \end{bmatrix}$

Teraz właśnie się roztwór do Ridge regresji i zastąpienie co o : . Dla nowego niewidzialnego punktu danych przewidujemy jego wartość docelową jako .$X$$\Phi(X)$$\mathbf w = \Phi(X)^T \, (\Phi(X) \Phi(X)^T + \lambda \, I)^{-1} \mathbf y$$\mathbf x$$\hat y$$\hat y= \mathbf \phi(\mathbf x)^T \Phi(X)^T \, (\Phi(X) \Phi(X)^T + \lambda \, I)^{-1} \mathbf y$

Najpierw możemy zastąpić macierzą , obliczoną jako . Następnie to . Więc tutaj udało nam się wyrazić każdy produkt kropkowy problemu w postaci jąder.$\Phi(X) \Phi(X)^T$$K$$(K)_{ij} = k(\mathbf x_i, \mathbf x_j)$$\phi(\mathbf x)^T \Phi(X)^T$$\sum\limits_{i = 1}^n \phi(\mathbf x)^T \phi(\mathbf x_i) = \sum\limits_{i = 1}^n k(\mathbf x, \mathbf x_j)$

Wreszcie, pozwalając (jak poprzednio), otrzymujemy$\boldsymbol \alpha = (K + \lambda \, I)^{-1} \mathbf y$$\hat y= \sum\limits_{i = 1}^n \alpha_i k(\mathbf x, \mathbf x_j)$

Bibliografia

• Machine Learning I klasy w TU Berlin
• Elementy uczenia statystycznego, http://statweb.stanford.edu/~tibs/ElemStatLearn/
• http://0agr.ru/wiki/index.php/Normal_Equation
• http://stat.wikia.com/wiki/Kernel_Ridge_Regression
• http://stat.rutgers.edu/home/tzhang/papers/ml02_dual.pdf
• http://www.ics.uci.edu/~welling/classnotes/papers_class/Kernel-Ridge.pdf
• http://www.cs.nyu.edu/~mohri/mls/lecture_8.pdf