Rozwiązywanie parametrów regresji w formie zamkniętej vs opadanie gradientu

71

Na kursie uczenia maszynowego Andrew Nga wprowadza regresję liniową i regresję logistyczną oraz pokazuje, jak dopasować parametry modelu za pomocą spadku gradientu i metody Newtona.

Wiem, że zejście gradientowe może być przydatne w niektórych aplikacjach uczenia maszynowego (np. Propagacja wsteczna), ale w bardziej ogólnym przypadku jest jakiś powód, dla którego nie rozwiązalibyśmy parametrów w formie zamkniętej - tj. Biorąc pochodną funkcja kosztów i rozwiązywanie za pomocą rachunku różniczkowego?

Jaka jest zaleta stosowania algorytmu iteracyjnego, takiego jak opadanie gradientu w porównaniu z rozwiązaniem w formie zamkniętej, jeśli jest ono dostępne?

Jeff
źródło
9
Nie sądzę, że istnieje rozwiązanie w formie zamkniętej dla MLE parametrów regresji w większości glms (np. Regresja logistyczna). Regresja liniowa z normalnymi błędami jest jednym wyjątkiem.
Makro
5
Interesujące ... Czy to oznacza, że ​​różne pakiety statystyk mogą dawać różne odpowiedzi na regresję logistyczną w zależności np. Od początkowych ustawień parametrów, liczby iteracji, wielu lokalnych minimów itp. - Czy istnieje konwencjonalna procedura, że ​​wszystkie dobre pakiety statystyk będą śledzić? (Chociaż jestem pewien, że wszelkie różnice, jeśli istnieją, w większości przypadków są niewielkie)
Jeff
3
(+1) Do twojego pytania i komentarza, Jeff. GLM wykorzystujące łącze kanoniczne (takie jak regresja logistyczna) korzystają z dobrych właściwości wypukłości. Może istnieć więcej niż jeden algorytm do rozwiązywania takich problemów, ale podstawową konsekwencją tego jest to, że (modulo kilka dość drobnych szczegółów), dobrze zaimplementowane algorytmy numeryczne zapewnią spójne wyniki między nimi.
kardynał
2
Osobiście nie lubię kursu Andrew Ng, ponieważ doprowadził ludzi do przekonania, że ​​regresja liniowa to „uczenie maszynowe”.
Digio

Odpowiedzi:

85

O ile rozwiązanie w formie zamkniętej nie jest niezwykle drogie w obliczeniach, to na ogół jest to droga, gdy jest dostępna. Jednak,

  1. W przypadku większości problemów z regresją nieliniową nie ma rozwiązania w postaci zamkniętej.

  2. Nawet w regresji liniowej (jeden z niewielu przypadków, w których dostępne jest rozwiązanie w postaci zamkniętej), stosowanie wzoru może być niepraktyczne. Poniższy przykład pokazuje jeden ze sposobów, w jaki może się to zdarzyć.

y=XβX

β^=argminXβy2

jest dany przez

β^=(XTX)1XTy

Teraz wyobraź sobie, że jest bardzo dużą, ale rzadką macierzą. np. może mieć 100 000 kolumn i 1 000 000 wierszy, ale tylko 0,001% wpisów w jest niezerowych. Istnieją wyspecjalizowane struktury danych do przechowywania tylko niezerowych wpisów takich rzadkich macierzy. XXX

Wyobraź sobie również, że mamy pecha, a to dość gęsta matryca ze znacznie wyższym odsetkiem niezerowych wpisów. Przechowywanie gęstej macierzy o wartości 100 000 na 100 000 elementów wymagałoby wówczas liczb zmiennoprzecinkowych (przy 8 bajtach na liczbę, to jest 80 gigabajtów). Niepraktyczne byłoby przechowywanie na czymkolwiek ale superkomputer. Co więcej, odwrotność tej macierzy (lub częściej czynnik Cholesky'ego) również miałaby zwykle w większości niezerowe wpisy. XTXXTX1×1010

Jednakże, istnieją sposoby iteracyjne rozwiązywanie problemów najmniejszych kwadratów, które nie wymagają więcej przestrzeni niż , i , a nie bezpośrednio tworzą iloczyn macierzy . Xyβ^XTX

W tej sytuacji zastosowanie metody iteracyjnej jest znacznie bardziej wydajne obliczeniowo niż zastosowanie rozwiązania formy zamkniętej dla problemu najmniejszych kwadratów.

Ten przykład może wydawać się absurdalnie duży. Jednak duże rzadkie problemy najmniejszych kwadratów tego rozmiaru są rutynowo rozwiązywane metodami iteracyjnymi na komputerach stacjonarnych w badaniach tomografii sejsmicznej.

Brian Borchers
źródło
4
Powinienem wspomnieć, że istnieją również problemy z dokładnością numeryczną, które mogą sprawić, że użycie rozwiązania w postaci zamkniętej dla problemu najmniejszych kwadratów jest niewskazane. Wymagałoby to jednak omówienia złych uwarunkowań, które prawdopodobnie wykraczają poza obecne rozumienie oryginalnego plakatu.
Brian Borchers,
17
proszę nie wahaj się opublikować odpowiedzi, ponieważ nie sądzisz, że ją zrozumiem. po pierwsze - nie zaszkodzi podać więcej informacji, nawet jeśli zajmie mi to trochę badań, aby je zrozumieć. po drugie - model stackexchange zakłada, że ​​to pytanie i odpowiedź przyniosą korzyści innym w przyszłości. innymi słowy, nie stęp głupią odpowiedź na podstawie tego, jak myślisz, że OP wie, bo inaczej wyrządzisz innym krzywdę.
Jeff
2
@Brian, mam wrażenie, że Twój komentarz jest bliżej sedna problemu i jest nieco sprzeczny z pierwszym zdaniem w odpowiedzi. Nie sądzę, aby jakiekolwiek oprogramowanie najmniejszych kwadratów (przy zdrowych zmysłach) używa rozwiązania w formie zamkniętej. :)
kardynał
4
Kardynał - w praktyce najlepiej jest użyć faktoryzacji QR lub SVD, aby rozwiązać problemy najmniejszych kwadratów na małą skalę. Twierdziłbym, że rozwiązanie wykorzystujące jedną z tych ortogonalnych faktoryzacji jest również „rozwiązaniem w formie zamkniętej” w porównaniu z zastosowaniem techniki iteracyjnej takiej jak LSQR. Nie zagłębiłem się w tę odpowiedź, ponieważ niepotrzebnie odwraca ona uwagę od mojego głównego punktu.
Brian Borchers
2
Źle warunkowane? Podręcznik zamknięty formularz? Uwielbiam zapach kwadratowych liczb stanu rano. Masz duży numer warunku? Dlaczego go nie wyrównać i nie uczynić jeszcze większym? Masz niezbyt duży numer warunku? Dlaczego nie wyprostować i nie zrobić dużego.
Mark L. Stone,
2

Było kilka postów na temat uczenia maszynowego (ML) i regresji. ML nie jest potrzebny do rozwiązywania zwykłych najmniejszych kwadratów (OLS), ponieważ obejmuje jednoetapową operację sandwiczowania macierzy w celu rozwiązania układu równań liniowych - tj. . Fakt, że wszystko jest liniowe, oznacza, że ​​do rozwiązania współczynników potrzebna jest tylko jednoetapowa operacja. Regresja logistyczna polega na maksymalizacji funkcji wiarygodności , którą można rozwiązać za pomocą Newtona-Raphsona lub innych metod wynurzania gradientu ML, metaheurystyki (wspinaczka, algorytmy genetyczne, inteligencja roju, optymalizacja kolonii mrówek itp.) . β=(XTX)1XTyL=ipi

Jeśli chodzi o parsimony, użycie ML dla OLS byłoby marnotrawstwem, ponieważ iteracyjne uczenie się jest nieskuteczne w rozwiązywaniu OLS.

Wróćmy teraz do twojego prawdziwego pytania na temat podejść pochodnych a metod ML do rozwiązywania problemów opartych na gradiencie. W szczególności w przypadku regresji logistycznej powszechnie stosuje się podejście gradientu Newtona-Raphsona (oparte na pochodnych). Newton-Raphson wymaga znajomości funkcji celu i jej częściowych pochodnych względem każdego parametru (ciągłego w granicy i różniczkowalnego). ML jest najczęściej używany, gdy funkcja celu jest zbyt złożona („wąska”) i nie znasz pochodnych. Na przykład sztuczna sieć neuronowa (ANN) może być wykorzystana do rozwiązania problemu aproksymacji funkcji lub nadzorowanego problemu klasyfikacji, gdy funkcja nie jest znana. W tym przypadku ANN jest funkcją.

Nie popełnij błędu przy użyciu metod ML do rozwiązania problemu regresji logistycznej, tylko dlatego, że możesz. W przypadku logistyki Newton-Raphson jest niezwykle szybki i jest odpowiednią techniką do rozwiązania problemu. ML jest powszechnie używany, gdy nie wiesz, co to za funkcja. (tak przy okazji, ANN są z zakresu inteligencji obliczeniowej, a nie ML).

JoleT
źródło