Po co używać opadania gradientu do regresji liniowej, gdy dostępne jest rozwiązanie matematyczne w formie zamkniętej?

73

Biorę kursy uczenia maszynowego online i dowiedziałem się o spadku gradientu do obliczania optymalnych wartości w hipotezie.

h(x) = B0 + B1X

dlaczego musimy używać zejścia gradientu, jeśli możemy łatwo znaleźć wartości za pomocą poniższej formuły? To też wygląda na proste i łatwe. ale GD potrzebuje wielu iteracji, aby uzyskać wartość.

B1 = Correlation * (Std. Dev. of y/ Std. Dev. of x)

B0 = Mean(Y) – B1 * Mean(X)

UWAGA: Wykonano jak w https://www.dezyre.com/data-science-in-r-programming-tutorial/linear-regression-tutorial

Sprawdziłem poniższe pytania i dla mnie nie było to jasne do zrozumienia.

Dlaczego wymagane jest zejście gradientowe?

Dlaczego optymalizacja jest rozwiązywana za pomocą spadku gradientu, a nie rozwiązania analitycznego?

Powyższe odpowiedzi porównują GD z wykorzystaniem instrumentów pochodnych.

regression machine-learning gradient-descent

— Purus
źródło

5

Nie potrzebujesz opadania gradientu, aby oszacować współczynniki regresji liniowej.

— Sycorax,

8

@Sycorax „nie potrzebujesz” to mocne stwierdzenie. Metoda iteracyjna może być przydatna w przypadku dużych danych. Powiedzmy, że macierz danych jest bardzo duża i nie mieści się w pamięci.

— Haitao Du

8

@ hxd1011 Dziękujemy za wyjaśnienie tego praktycznego wymiaru problemu. Myślałem w kategoriach czysto matematycznych.

— Sycorax,

89

Głównym powodem stosowania spadku gradientu do regresji liniowej jest złożoność obliczeniowa: w niektórych przypadkach znalezienie rozwiązania wykorzystującego spadek gradientu jest tańsze (szybciej).

Formuła, którą napisałeś, wygląda na bardzo prostą, nawet obliczeniową, ponieważ działa tylko w przypadku wielkości pojedynczej, tj. Gdy masz tylko jedną zmienną. W przypadku wielu zmiennych, gdy masz wiele zmiennych, formuły są nieco bardziej skomplikowane na papierze i wymagają znacznie więcej obliczeń, gdy implementujesz je w oprogramowaniu: Tutaj trzeba obliczyć macierz a następnie odwrócić ją (patrz uwaga poniżej). To kosztowna kalkulacja. Dla odniesienia, macierz (projektowa) X ma K + 1 kolumn, gdzie K jest liczbą predyktorów i N rzędów obserwacji. W algorytmie uczenia maszynowego można uzyskać K> 1000 i N> 1 000 000. matryca sama zajmuje trochę czasu, aby obliczyć, to trzeba odwrócić

β = (X^{'} X)^{- 1} X^{'} Y

$\beta=(X'X)^{-1}X'Y$

X^{'} X

$X'X$

X^{'} X

$X'X$

K \times K

$K\times K$ Macierz - jest to droga.

Spadek gradientu pozwala więc zaoszczędzić dużo czasu na obliczeniach. Co więcej, sposób, w jaki to się robi, pozwala na trywialną równoległość, tj. Rozłożenie obliczeń na wiele procesorów lub maszyn. Rozwiązanie algebry liniowej można również zrównoleglać, ale jest ono bardziej skomplikowane i wciąż drogie.

Ponadto istnieją wersje gradientu zejścia, gdy przechowujesz tylko część danych w pamięci, co obniża wymagania dotyczące pamięci komputera. Ogólnie rzecz biorąc, w przypadku bardzo dużych problemów jest bardziej wydajne niż rozwiązanie algebry liniowej.

Staje się to jeszcze ważniejsze, gdy wzrasta wymiarowość, gdy masz tysiące zmiennych, takich jak uczenie maszynowe.

Uwaga . Byłem zaskoczony, jak wiele uwagi poświęcono gradientowi opadającemu w wykładach Ng. Mówi o tym nietrywialnie, może 20% całego kursu. Dla mnie to tylko szczegół implementacji, to jak dokładnie znaleźć optymalne. Kluczem jest sformułowanie problemu optymalizacji, a to, jak dokładnie go znajdziesz, nie jest konieczne. Nie martwiłbym się tym zbytnio. Pozostaw to informatykom i skoncentruj się na tym, co jest dla Ciebie ważne jako statystyk.

Mimo to muszę zakwalifikować się mówiąc, że to jest rzeczywiście ważne, aby zrozumieć o złożoności obliczeniowej i stabilności numerycznej algorytmów rozwiązania. Nadal nie sądzę, że musisz znać szczegóły implementacji i kod algorytmów. Zwykle nie jest to najlepsze wykorzystanie twojego czasu jako statystyki.

Uwaga 1 . Napisałem, że musisz odwrócić macierz dla celów dydaktycznych i nie tak zazwyczaj rozwiązujesz równanie. W praktyce problemy z algebrą liniową są rozwiązywane przez zastosowanie pewnego rodzaju faktoryzacji, takiej jak QR, gdzie nie odwracasz bezpośrednio macierzy, ale wykonujesz inne matematycznie równoważne manipulacje, aby uzyskać odpowiedź. Robisz to, ponieważ inwersja macierzy jest w wielu przypadkach kosztowną i niestabilną numerycznie operacją.

Daje to kolejną małą zaletę algorytmu spadku gradientu jako efekt uboczny: działa nawet wtedy, gdy macierz projektowa ma problemy z kolinearnością. Zwykła ścieżka algebry liniowej wybuchłaby, a opadanie gradientu trwałoby nawet w przypadku predyktorów współliniowych.

— Aksakal
źródło

17

Ale Ng jest informatykiem.

— ameba

21

Odnośnie twojej uwagi: Jako matematyk zwykłem się zgadzać. Ale rozumiem teraz, że we współczesnym uczeniu maszynowym metoda optymalizacji jest nieodłącznie związana z optymalizacją celu. Niektóre formy regularyzacji, takie jak porzucanie, są wyrażone bardziej czysto w kategoriach algorytmu zamiast celu. W skrócie: jeśli weźmiesz głęboką siatkę, zachowaj funkcję celu, ale zmienisz metodę optymalizacji, możesz uzyskać zupełnie inną wydajność. W rzeczywistości czasami lepszy optymalizator daje gorsze wyniki w praktyce ...

— A. Rex

14

Minor nitpick: nie, że z pewnością odwróci ; zamiast tego rozwiązałbyś układ równań liniowych dla . Streszczenie jest takie samo, ale liczbowo jest znacznie bardziej stabilne i potencjalnie nawet tańsze.

X^{'} X

$X'X$

X^{'} X β = X^{'} y

$X'X\beta=X'y$

β

$\beta$

— Stephan Kolassa

3

Z kolei rozwiązanie @AnderBiguri z faktoryzacją QR jest stabilne wstecz, dlatego zapewnia rozwiązanie tak dokładne, jak to możliwe, biorąc pod uwagę niepewność danych wejściowych.

— Federico Poloni

7

Myślę, że wszyscy powinniśmy przestać pisać i po prostu pisać cały czas.

β = (X^{t} X)^{- 1} X^{t} y

$\beta = (X^t X)^{-1} X^t y$

X^{t} X β = X^{t} y

$X^t X \beta = X^t y$

— Matthew Drury

21

Po pierwsze, zdecydowanie zalecam przeczytanie następujących dwóch postów (jeśli nie duplikowanie)

Sprawdź odpowiedź JM w

Jaki algorytm stosuje się w regresji liniowej?

Proszę sprawdzić odpowiedź Marka (z liczbowego punktu widzenia stabilności) w

Czy potrzebujemy spadku gradientu, aby znaleźć współczynniki modelu regresji liniowej?

Krótko mówiąc, załóżmy, że chcemy rozwiązać problem regresji liniowej z utratą do kwadratu Możemy ustawić pochodną na , i to rozwiązuje układ liniowy

minimize ‖ A x - b ‖^{2}

$\text{minimize}~ \|Ax-b\|^2$

2 A^{T} (A x - b)

$2A^T(Ax-b)$

0

$0$

A^{T} A x = A^{T} b

$A^TAx=A^Tb$

Na wysokim poziomie istnieją dwa sposoby rozwiązania układu liniowego. Metoda bezpośrednia i metoda iteracyjna. Zauważ, że metoda bezpośrednia rozwiązuje , a opadanie gradientu (jedna przykładowa metoda iteracyjna) bezpośrednio rozwiązuje . $A^TAx=A^Tb$ $\text{minimize}~ \|Ax-b\|^2$

Porównywanie do metod bezpośrednich (powiedz rozkład QR / LU ). Metody iteracyjne mają pewne zalety, gdy mamy dużą ilość danych lub dane są bardzo rzadkie.

Załóżmy, że nasza macierz danych jest ogromna i nie można zmieścić się w pamięci, można zastosować stochastyczne pochylenie gradientu. Mam odpowiedź, aby wyjaśnić, w jaki sposób stochastyczne obniżanie gradientu pozwala zaoszczędzić czas w porównaniu ze standardowym spadkiem gradientu? $A$
W przypadku rzadkich danych zapoznaj się z wielką książką Metody iteracyjne dla rzadkich układów liniowych

Z drugiej strony uważam, że jednym z powodów, dla których podkreśla Andrew Ng, jest to, że jest to metoda ogólna (najczęściej stosowana metoda uczenia maszynowego) i może być stosowana w innych modelach, takich jak regresja logistyczna lub sieć neuronowa.

— Haitao Du
źródło

Masz absolutną rację. SGD jest bardzo pomocny przy przetwarzaniu dużej ilości danych. Metoda pokazana przez prof. Ng jest najbardziej klasyczna i czysta. Od tego momentu należy zacząć od jasnego pomysłu. Jeśli zrozumiesz motto tego, wówczas cała liniowa ocena będzie dla niego / jej krystalicznie czysta.

— Sandipan Karmakar

1

Rozmiar maxtrix danych nie jest tak naprawdę problemem, używając relacji ; możesz obliczyć i jedną obserwację na raz. Tak właśnie zrobiono w SAS w czasach, gdy pamięć komputera była znacznie bardziej ograniczona niż dzisiaj. To liczba kolumn w jest czynnikiem ograniczającym.

X^{T} X = \sum x_{i} x_{i}^{T}

$X^TX = \sum x_ix_i^T$

X^{T} X

$X^TX$

X^{T} y

$X^Ty$

X

$X$

— jbowman

6

Sycorax ma rację, że nie potrzebujesz spadku gradientu podczas szacowania regresji liniowej. Twój kurs może być na prostym przykładzie, aby nauczyć cię zejścia gradientowego do wstępu do bardziej skomplikowanych wersji.

Jedną fajną rzeczą Chcę dodać jednak to, że nie ma obecnie niewielka nisza badania dotyczące zakończenia metoda gradientu prostego wcześnie , aby uniknąć nadmiernego dopasowania modelu.

— Tim Atreides
źródło

2

Czy w przypadku stwierdzenia przekroczenia wartości można podać link? czy dodanie terminu regularyzacji jest lepsze niż ograniczenie liczby iteracji?

— Haitao Du

Możesz spojrzeć na rozdział 7 głębokiego uczenia się autorstwa Goodfellow i in., W którym wspomniano o wczesnym zaprzestaniu, aby zapobiec nadmiernemu dopasowaniu w sieciach neuronowych.

— Batman

2

Regularyzacja poprzez wcześniejsze zatrzymanie nie jest w żadnym wypadku nową techniką; jest to dobrze znana technika, powiedzmy, w iteracji Landwebera: en.wikipedia.org/wiki/Landweber_iteration

— cfh

3

Jeśli się nie mylę, myślę, że wskazujesz na MOOC oferowany przez prof. Andrew Ng. Aby znaleźć optymalne współczynniki regresji, dostępne są rażąco dwie metody. Jednym z nich jest użycie równań normalnych, tj. Po prostu odkrycie a drugim przez zminimalizowanie najmniejszej kryterium kwadratów, które wywodzi się z cytowanej hipotezy. Nawiasem mówiąc, pierwsza metoda, tj. Równania normalne, jest iloczynem drugiej metody, tj. Metody optymalizacji. $(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y}$

Wspomniana metoda, tj. Wykorzystująca korelację, ma zastosowanie tylko do jednego predyktora i jednej wielkości przechwytywania. Po prostu zauważ formularz. Tak więc, kiedy liczba predyktorów jest większa niż jeden, to jakie jest wyjście? Następnie należy zastosować inne metody, tj. Równanie normalne lub optymalizację.

Po co więc optymalizacja (tutaj Gradient Descent), chociaż dostępne jest bezpośrednie równanie normalne. Zauważ, że w równaniu normalnym należy odwrócić macierz. Teraz odwrócenie macierzy kosztuje do obliczeń, gdzie jest liczbą wierszy w macierzy , tj. Obserwacjami. Ponadto, jeśli jest źle warunkowany, spowoduje to błędy obliczeniowe w oszacowaniu. Tak więc algorytm optymalizacji rodzaju zejścia gradientu może uchronić nas przed tego rodzaju problemem. Kolejnym problemem jest niedopasowanie i niedostateczne oszacowanie współczynników regresji. $\mathcal{O}(N^3)$ $N$ $\mathbf{X}$ $\mathbf{X}$

Moja propozycja dla ciebie nie polega na rozwiązywaniu problemu. Spróbuj zrozumieć teorię. Prof Ng jest jednym z najlepszych profesorów na świecie, który uprzejmie uczy uczenia maszynowego w MOOC. Tak więc, kiedy instruuje on w ten sposób, musi to mieć pewne ukryte intencje. Mam nadzieję, że nie będą ci przeszkadzać moje słowa.

Wszystkiego najlepszego.

— Sandipan Karmakar
źródło

5

„Odwracanie macierzy” zdecydowanie NIE jest zalecane. QR jest bardziej stabilny numerycznie, aby rozwiązać układ liniowy.

— Haitao Du

1

Zgadzam się z argumentem obliczeniowym. Nadmierne lub niedopasowanie nie ma jednak nic wspólnego z użyciem równania GD vs. normalnego, ale raczej ze złożonością modelu (regresyjnego). Obie metody (GD, jeśli działa poprawnie) znajdują to samo rozwiązanie najmniejszych kwadratów (jeśli istnieje), a zatem nadmiernie lub niedopasowane dane o tę samą ilość.

— Ruben van Bergen

2

Po pierwsze tak, prawdziwym powodem jest ten podany przez Tima Atreidesa; jest to ćwiczenie pedagogiczne.

Jest jednak możliwe, choć mało prawdopodobne, aby wykonać regresję liniową na powiedzmy kilka trylionów punktów danych przesyłanych strumieniowo z gniazda sieciowego. W tym przypadku naiwna ocena roztworu analitycznego byłaby niemożliwa, podczas gdy niektóre warianty stochastycznego / adaptacyjnego spadku gradientu byłyby zbieżne z prawidłowym rozwiązaniem przy minimalnym obciążeniu pamięci.

(dla regresji liniowej można przeformułować rozwiązanie analityczne jako system rekurencyjny, ale nie jest to technika ogólna).

— Timothy Teräväinen
źródło

2

Innym powodem jest to, że opadanie gradientu jest bardziej ogólną metodą. W przypadku wielu problemów związanych z uczeniem maszynowym funkcja kosztów nie jest wypukła (np. Rozkład macierzy, sieci neuronowe), więc nie można użyć rozwiązania w formie zamkniętej. W takich przypadkach zejście gradientowe służy do znalezienia dobrych lokalnych optymalnych punktów. Lub jeśli chcesz zaimplementować wersję online, musisz użyć algorytmu opartego na spadku gradientu.

— Sanyo Mn
źródło