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

Próbowałem nauczyć się uczenia maszynowego przy użyciu materiału Coursera . W tym wykładzie Andrew Ng wykorzystuje algorytm spadku gradientu do znalezienia współczynników modelu regresji liniowej, które zminimalizują funkcję błędu (funkcję kosztu).

Czy do regresji liniowej potrzebujemy spadku gradientu? Wydaje się, że potrafię analitycznie rozróżnić funkcję błędu i ustawić ją na zero, aby rozwiązać dla współczynników; czy to prawda?

— Zwycięzca
źródło

Modele liniowe są dość dobrze obsługiwane od 1700 roku. Istnieje mnóstwo sposobów radzenia sobie z nimi, które nie wymagają spadku gradientu (GD). Istnieją modele nieliniowe, w których większość z tych metod leży płasko na twarzy. Andrew sprawia, że używasz nieznanej, ale bardzo przydatnej metody przeciwko bardzo prostemu problemowi, dzięki czemu możesz debugować swoje podejście. Jeśli jesteś dobry w tej metodzie, możesz zastosować ją do oszałamiająco nieliniowych problemów, dla których GD jest jedyną metodą uzyskiwania wyników.

— EngrStudent - Przywróć Monikę

Nie, nie musisz używać metod takich jak opadanie gradientu (w każdym razie to nie jedyna metoda optymalizacji). Rzeczywiście możesz to rozwiązać analitycznie, jak sugerujesz; rozróżniasz w odniesieniu do każdego parametru, więc otrzymujesz jedno równanie na parametr. Ale przydatne jest rozwiązywanie prostych problemów, które można rozwiązać na inne sposoby; jeśli znasz już odpowiedź, możesz być pewien, kiedy uzyskasz właściwą odpowiedź z gradientowym spadkiem.

— Glen_b

Jeśli funkcją kosztu jest zwykła kara kwadratowa („odległość”), istnieje rozwiązanie w formie zamkniętej. Jednak opadanie gradientu jest na ogół znacznie szybsze, dlatego zwykle jest używane.

— aginensky,

Ponadto zejścia gradientowego można użyć do znalezienia numerycznych rozwiązań problemów, które są analitycznie trudne do rozwiązania. Podejrzewałbym, że używa wczesnego spadku gradientu, aby przyzwyczaić się do niego. Sądzę, że następnie korzysta z opadania gradientowego z sieciami neuronowymi. Nie trzeba dodawać, że sytuacja sieci neuronowej jest bardziej skomplikowana. Myślę, że z sytuacji pedagogicznej, widząc je wcześniej, z modelami liniowymi, zejście gradientowe do stosowania z sieciami neuronowymi wydaje się bardziej rozsądne.

— aginensky,

Dzięki za opublikowanie linku do filmów Andre Ng, które obejrzałem kilka. Wiedziałem już o tym, choć nie aż tak skrajnie, ale przerażające jest widzenie, czego uczy się większość „uczącej się” optymalizacji, a co dopiero niektórzy z nich uczą się o obliczeniach statystycznych. Gene Golub, pionier w dziedzinie obliczeń i korzystania z SVD, przewróciłby się w grobie, gdyby wiedział, czego obecnie uczy się w jego Stanford Computer Science Dept. „Najśmieszniejsze” wideo to youtube.com/watch?v=B3vseKmgi8E , które zaleca i porównuje 2 algorytmy WORST dla najmniejszych kwadratów

— Mark L. Stone z

Odpowiedzi:

Liniowe najmniejsze kwadraty można rozwiązać

0) Zastosowanie wysokiej jakości liniowego solwera najmniejszych kwadratów, opartego na SVD lub QR, jak opisano poniżej, dla nieograniczonego liniowego najmniejszego kwadratu, lub w oparciu o wersję programowania kwadratowego lub optymalizacji stożkowej dla ograniczonych lub liniowo ograniczonych najmniejszych kwadratów, jak opisano poniżej. Taki solver jest wstępnie konserwowany, dokładnie przetestowany i gotowy do użycia - użyj go.

1) SVD, która jest najbardziej niezawodną i dokładną numerycznie metodą, ale wymaga także więcej obliczeń niż rozwiązań alternatywnych. W programie MATLAB rozwiązaniem SVD nieograniczonego liniowego problemu najmniejszych kwadratów A * X = b jest pinv (A) * b, który jest bardzo dokładny i niezawodny.

2) QR, który jest dość niezawodny i dokładny numerycznie, ale nie tak bardzo jak SVD i jest szybszy niż SVD. W MATLAB rozwiązaniem QR dla nieograniczonego liniowego problemu najmniejszych kwadratów A * X = b jest A \ b, które jest dość dokładne i niezawodne, z wyjątkiem sytuacji, gdy A jest źle uwarunkowane, tj. Ma dużą liczbę stanów. Obliczenie A \ b jest szybsze niż pinv (A) * b, ale nie jest tak wiarygodne ani dokładne.

3) Formowanie równań normalnych (STANOWISKO z punktu widzenia niezawodności i dokładności numerycznej, ponieważ podnosi kwadrat warunku, co jest bardzo złym posunięciem) i

3a) rozwiązywanie przez faktoryzację Cholesky'ego (niezbyt dobre)

3b) jawnie odwracająca macierz (HORRIBLE)

4) Rozwiązanie jako problem z programowaniem kwadratowym lub problem ze stożkiem drugiego rzędu

4a) Rozwiąż za pomocą wysokiej jakości oprogramowania do programowania kwadratowego. Jest to wiarygodne i dokładne liczbowo, ale trwa dłużej niż SVD lub QR. Łatwo jest jednak dodawać ograniczenia lub ogólne ograniczenia liniowe lub liniowe lub kwadratowe (dwie normy) kary lub regularyzacyjne do funkcji celu i nadal rozwiązywać problem za pomocą oprogramowania do programowania kwadratowego.

4b) Rozwiąż problem stożka drugiego rzędu za pomocą wysokiej jakości oprogramowania do optymalizacji stożkowej. Uwagi są takie same, jak w przypadku oprogramowania do programowania kwadratowego, ale można również dodawać ograniczone lub ogólne ograniczenia liniowe i inne ograniczenia stożkowe lub terminy funkcji celu, takie jak warunki kary lub regularyzacji w różnych normach.

5) Rozwiązuj za pomocą wysokiej jakości oprogramowania do optymalizacji nieliniowej ogólnego zastosowania. To może nadal działać dobrze, ale ogólnie będzie wolniejsze niż oprogramowanie do programowania kwadratowego lub Conic Optimization i może nie być tak niezawodne. Jednak może być możliwe uwzględnienie nie tylko wiązań i ogólnych wiązań liniowych, ale także wiązań nieliniowych w optymalizacji najmniejszych kwadratów. Można go również stosować do nieliniowych najmniejszych kwadratów i jeśli inne funkcje nieliniowe są dodawane do funkcji celu.

6) Rozwiązuj za pomocą kiepskich algorytmów optymalizacji nieliniowej ogólnego zastosowania -> NIE NALEŻY TEGO ROBIĆ.

7) Rozwiąż za pomocą algorytmu optymalizacji nieliniowej optymalizacji NAJGORSZE MOŻLIWE ogólnego zastosowania, tj. Spadku gradientu. Użyj tego tylko, jeśli chcesz zobaczyć, jak zła i niewiarygodna może być metoda rozwiązania. Jeśli ktoś powie ci, abyś użył spadku gradientu do rozwiązania liniowych problemów z najmniejszymi kwadratami

7 i) Dowiedz się o obliczeniach statystycznych od kogoś, kto coś o tym wie

7 ii) Naucz się optymalizacji od kogoś, kto coś o tym wie.

— Mark L. Stone
źródło

Fajny post, dlaczego uważasz, że Cholesky nie jest dobry, skoro twój system to PD? (a nie z absurdalnym numerem warunku) BTW, myślę, że chcesz powiedzieć (lub dodać) pojęcie uogólnionej odwrotności (używanej głównie do celów edukacyjnych) albo w punkcie „SVD”, albo w punkcie „wyraźnie odwracającym”.

— usεr11852 mówi Przywróć Monic

BTW, to absurdalne, jak często generowane są macierze o bardzo wysokich liczbach warunków, szczególnie przez niemyte masy (tj. Większość ludzi robi liniowe najmniejsze kwadraty, szczególnie biorąc pod uwagę demokratyzację w dostępie), którzy nie są do tego dostrojeni.

— Mark L. Stone

mldiwide, tj. ukośnik odwrotny, tzn. \ używa QR, gdy m ~ = n (najmniejszych kwadratów), jak stwierdziłem w drugim zdaniu mojego akapitu (2) powyżej. Byłbyś zaskoczony, jak wiele badziewie jest w MATLAB - nie tylko w zestawach narzędzi, z których niektóre są absolutnie okropne, ale w mniejszym stopniu w niektórych podstawowych funkcjach.

— Mark L. Stone,

@ MarkL.Stone, świetna odpowiedź! czy mógłbyś wyjaśnić nieco więcej, dlaczego nie zaleca się używania zejścia gradientowego do rozwiązywania najmniejszych kwadratów! (w moim rozumieniu jest to tylko podejście iteracyjne w porównaniu do innych (podejścia ukierunkowane na rozwiązanie), o których wspomniałeś powyżej). Ponadto, czy mógłbyś również skomentować problem: „jeśli mam n> = 30 000 cech problemu, metoda równania normalnego będzie bardzo wolna, ponieważ odwracanie macierzy n * n byłoby straszne! Z drugiej strony, GD działałby w tym całkiem ładnie! wszelkie przemyślenia na temat działania SVD i QR ". każda sugestia byłaby pomocna.

— anu

@ anu Używaj zejścia gradientowego tylko w ostateczności. i tak byłoby tylko wtedy, gdy problem jest zbyt duży, aby rozwiązać go SVD lub QR. Nigdy nie twórz równań normalnych, a tym bardziej jawnie odwracaj macierz, aby rozwiązać równania normalne, NIGDY. 30 000 funkcji nie brzmi obecnie jak wiele.

— Mark L. Stone,

Znalezienie współczynników modelu liniowego jest technicznie procesem znajdowania rozwiązań dla zestawu równań liniowych .

Do obliczania takich rozwiązań opracowano wiele optimization techniquesi Gradient Descentjest jednym z nich.
Tak więc Gradient Descent nie jest jedynym sposobem, aby to zrobić.

Andrew Ng używa go w kursie, ponieważ jest prosty do zrozumienia, bez zajmowania się zaawansowaną algebrą liniową i obliczeniami numerycznymi.

— Vikas Raturi
źródło

Chociaż nie jest źle, myślę, że twoja odpowiedź pomija szerszy obraz, koncentrując się na niestandardowym przypadku. Zdecydowana większość liniowych modeli regresji jest zamontowane za pomocą rozkładu QR wykorzystujący rozwiązanie zamkniętej formy. GD-gradient przyzwoity- służy jako przykład do wprowadzenia bardziej zaawansowanych metod (np. SGD- stochastyczny GD).

— usεr11852 mówi Przywróć Monic

Czy potrafisz opracować rozkład QR?

— Victor

A x = b

$Ax=b$

A = Q R

$A=QR$

R

$R$

Q

$Q$

A x = b \Rightarrow Q R x = b \Leftrightarrow R x = Q^{T} b

$Ax=b \Rightarrow QRx=b \Leftrightarrow Rx = Q^Tb$

R

$R$

Q^{T} Q = I

$Q^T Q=I$ SGD. Ponieważ większość ludzi nie ma bardzo dużych matryc, rozkład QR jest lepszy. Ogólnie rozkład QR ukształtował świat liczb; SIAM wybrał go jako jeden z 10 najlepszych algorytmów XX wieku.

— usεr11852 mówi: Przywróć Monic

@ usεr11852 yes ofcourse. To dlatego, że chciałem, aby odpowiedź była prosta, aby uniknąć pojęć takich jak dekompostacja QR, pozostających istotnymi w dziedzinie poziomu kursu Ng.

— Vikas Raturi

QR był jednym z 10 najlepszych algorytmów XX wieku. Ale czas mija i choć skuteczne algorytmy obliczania SVD pochodzą z lat 60. XX wieku, trzeba przyjrzeć się znaczeniu obszarów zastosowań. Dlatego uważam, że SVD jest algorytmem TOP XXI wieku. Szczerze mówiąc, czy kiedykolwiek słyszałeś o tym, że QR jest używany do polecania filmów? Nie, SVD jest używany do tego krytycznego zastosowania. SVD najwyraźniej jest algorytmem wyboru, gdy Twitter wysyła niechciane stare zalecenia do konserwatywnych staruszków, które nastolatki powinny podążać. Zobaczmy, jak QR to robi !!!

— Mark L. Stone,