Czy istnieje wiele lokalnych optymalnych rozwiązań, gdy rozwiązujemy regresję liniową?

19

Przeczytałem to oświadczenie na jednym starym egzaminie prawda / fałsz:

Możemy uzyskać wiele lokalnych optymalnych rozwiązań, jeśli rozwiążemy problem regresji liniowej, minimalizując sumę błędów kwadratu za pomocą spadku gradientu.

Rozwiązanie: Fałsz

Moje pytanie brzmi, która część tego pytania jest błędna? Dlaczego to stwierdzenie jest fałszywe?

Anjela Minoeu
źródło

Odpowiedzi:

8

To pytanie jest interesujące, ponieważ ujawnia pewne powiązania między teorią optymalizacji, metodami optymalizacji i metodami statystycznymi, które każdy zdolny użytkownik statystyki musi zrozumieć. Chociaż połączenia te są proste i łatwe do nauczenia, są subtelne i często pomijane.

Podsumowując niektóre pomysły z komentarzy do innych odpowiedzi, chciałbym zauważyć, że istnieją co najmniej dwa sposoby, dzięki którym „regresja liniowa” może dawać nie unikalne rozwiązania - nie tylko teoretycznie, ale w praktyce.

Brak możliwości identyfikacji

Po pierwsze, model nie jest możliwy do zidentyfikowania. Tworzy to wypukłą, ale niekoniecznie wypukłą funkcję celu, która ma wiele rozwiązań.

Rozważmy, na przykład, cofa się na i (z osią) dla danych . Jednym z rozwiązań jest . Innym jest . Aby zobaczyć, że musi istnieć wiele rozwiązań, sparametryzuj model trzema rzeczywistymi parametrami i terminem błędu w postacix pręd ( x , y , z ) ( 1 , - 1 , 0 ) , ( 2 , - 2 , - 1 ) , ( 3 , - 3 , - 2 ), z = 1 + R z = 1 - x ( λ , μ , ν ) εzxy(x,y,z)(1,1,0),(2,2,1),(3,3,2)z^=1+yz^=1x(λ,μ,ν)ε

z=1+μ+(λ+ν1)x+(λν)y+ε.

Suma kwadratów reszt upraszcza się

SSR=3)μ2)+24μν+56ν2).

(Jest to ograniczający przypadek funkcji obiektywnych, które pojawiają się w praktyce, takich jak omawiany w Czy empiryczny hessian estymatora M może być nieokreślony ? , w którym można czytać szczegółowe analizy i przeglądać wykresy funkcji.)

Ponieważ współczynniki kwadratów ( i ) są dodatnie, a wyznacznik jest dodatni, jest to dodatnia-pół-skończona postać kwadratowa w . Jest minimalizowany, gdy , ale może mieć dowolną wartość. Ponieważ funkcja celu nie zależy od , nie ma też jej gradientu (ani żadnych innych pochodnych). Dlatego każdy algorytm spadku gradientu - jeśli nie dokona żadnych arbitralnych zmian kierunku - ustawi wartość na dowolną wartość początkową.56 3 x 56 - ( 24 / 2 ) 2 = 24 ( μ , ν , λ ) μ = ν = 0 λ SSR λ λ3)563)×56-(24/2))2)=24(μ,ν,λ)μ=ν=0λSSRλλ

Nawet jeśli gradient nie jest używany, rozwiązanie może się różnić. Na Rprzykład istnieją dwa łatwe, równoważne sposoby określenia tego modelu: jako z ~ x + ylub z ~ y + x. Daje w wyniku pierwszych a drugi nadaje Ż = 1 + Y . z^=1-xz^=1+y

> x <- 1:3
> y <- -x
> z <- y+1

> lm(z ~ x + y)
Coefficients:
(Intercept)            x            y  
          1           -1           NA  


> lm(z ~ y + x)
Coefficients:
(Intercept)            y            x  
          1            1           NA 

( NAWartości należy interpretować jako zera, ale z ostrzeżeniem, że istnieje wiele rozwiązań. Ostrzeżenie było możliwe z powodu przeprowadzonych wstępnych analiz, Rktóre są niezależne od jego metody rozwiązania. Metoda opadania gradientu prawdopodobnie nie wykryłaby możliwości wielu rozwiązań, chociaż dobry ostrzegałby cię przed pewną niepewnością, że osiągnął optymalny poziom).

Ograniczenia parametrów

Ścisła wypukłość gwarantuje unikalne globalne optimum, pod warunkiem, że dziedzina parametrów jest wypukła. Ograniczenia parametrów mogą tworzyć domeny niewypukłe, prowadząc do wielu globalnych rozwiązań.

Bardzo prosty przykład stanowi problem oszacowania „średniej” dla danych - 1 , 1 z zastrzeżeniem ograniczenia | μ | 1 / 2 . Modeluje to sytuację, która jest swego rodzaju przeciwieństwem metod regularyzacji, takich jak Regresja Ridge'a, Lasso lub Elastyczna Sieć: nalega, aby parametr modelu nie stał się zbyt mały. (Na tej stronie pojawiły się różne pytania z pytaniem, jak rozwiązać problemy regresji przy takich ograniczeniach parametrów, co pokazuje, że pojawiają się one w praktyce).μ-1,1|μ|1/2)

Istnieją dwa rozwiązania najmniejszych kwadratów w tym przykładzie, oba równie dobre. Można je znaleźć, minimalizując zastrzeżeniem ograniczenia | μ | 1 / 2 . Oba roztwory μ = ± 1 / 2 . Więcej niż jedno rozwiązanie może powstać z powodu ograniczenia parametru dokonuje domeny ľ ( - , - 1 / 2 ] (1-μ)2)+(-1-μ)2)|μ|1/2)μ=±1/2) nonconvex:μ(-,-1/2)][1/2),)

Wykres sumy kwadratów w stosunku do $ \ mu $

Parabola jest wykresem (ściśle) wypukłej funkcji. Gęstą czerwona część jest częścią ograniczone do domeny : ma dwie najniższe punkty na ľ = ± 1 / 2 , gdzie suma kwadratów 5 / 2 . Reszta paraboli (pokazana jako kropkowana) jest usuwana przez ograniczenie, eliminując w ten sposób jego unikalne minimum.μμ=±1/2)5/2)

Metoda gradientu zejście, chyba że byli gotowi do podjęcia dużych skoków, najprawdopodobniej znaleźć „unikalny” rozwiązanie , gdy zaczyna o dodatniej wartości i inaczej byłoby znaleźć „unikalny” rozwiązanie μ = - 1 / 2 , gdy zaczynając od wartości ujemnej.μ=1/2)μ=-1/2)

Ta sama sytuacja może wystąpić w przypadku większych zestawów danych i większych wymiarów (to znaczy z większą liczbą parametrów regresji, aby pasowały).

Whuber
źródło
1
fa(x,y)=(x-y)2)y=x
1
@Kjetil Dziękuję, to prawda. Sztuczka polega na tym, aby pokazać, jak takie funkcje faktycznie powstają w sytuacjach regresji. Twoja funkcja jest właśnie inspiracją dla pierwszego przykładu, który zaoferowałem.
whuber
Wizualny przykład stats.stackexchange.com/a/151351/171583 .
ayorgo
2

Obawiam się, że nie ma binarnej odpowiedzi na twoje pytanie. Jeśli regresja liniowa jest ściśle wypukła (brak ograniczeń współczynników, brak regulizera itp.), Wówczas opadanie gradientu będzie miało unikalne rozwiązanie i będzie optymalne globalnie. Zejście gradientowe może i zwróci wiele rozwiązań, jeśli masz problem niewypukły.

Chociaż OP prosi o regresję liniową, poniższy przykład pokazuje minimalizację najmniejszych kwadratów, chociaż nieliniowa (w porównaniu z regresją liniową, której chce OP) może mieć wiele rozwiązań, a spadek gradientu może zwrócić inne rozwiązanie.

Mogę pokazać empirycznie, używając prostego przykładu

  1. Suma kwadratów błędów może być czasem niewypukła, dlatego ma wiele rozwiązań
  2. Metoda opadania gradientu może zapewnić wiele rozwiązań.

Rozważ przykład, w którym próbujesz zminimalizować najmniejsze kwadraty dla następującego problemu:

wprowadź opis zdjęcia tutaj

wza

za12=9,za13=1/9,za23=9,za31=1/9

mjanjamjazmi (9-w1w2))2)+(19-w1w3))2)+(19-w2)w1)2)+(9-w2)w3))2)+(9-w3)w1)2)+(19-w3)w2))2)

Powyższy problem ma 3 różne rozwiązania i są one następujące:

w=(0,670,0,242,0,080),objot=165,2

w=(0,080,0,242,0,670),objot=165,2

w=(0,242,0,670,0,080),objot=165,2

Jak pokazano powyżej, problem najmniejszych kwadratów może nie być wypukły i może mieć wiele rozwiązań. Następnie powyższy problem można rozwiązać za pomocą metody opadania gradientu, takiej jak Microsoft Excel Solver i za każdym razem, gdy uruchamiamy, otrzymujemy inne rozwiązanie. ponieważ opadanie gradientu jest lokalnym optymalizatorem i może utknąć w lokalnym rozwiązaniu, musimy użyć różnych wartości początkowych, aby uzyskać prawdziwe globalne optymalne wartości. Taki problem zależy od wartości początkowych.

Synoptyk
źródło
2
Nie sądzę, że to odpowiada na pytanie OP, ponieważ OP pyta konkretnie o regresję liniową , a nie o optymalizację w ogóle.
Sycorax mówi Przywróć Monikę
1
Nie, nie robi tego, ale po prostu próbując wskazać problem z optymalizacją, zaktualizuje się z zastrzeżeniami
prezenter
@ user777 masz rację. to jest bardzo ważne pytanie na starym egzaminie z MIT. Jestem pewien, że odpowiedź jest fałszywa dzięki prognozie.
Anjela Minoeu
więc jesteś pewien, że mam rację?
Anjela Minoeu
@AnjelaMinoeu, zaktualizowałem swoją odpowiedź.
prezenter
1

Wynika to z faktu, że funkcja celu, którą minimalizujesz, jest wypukła, istnieje tylko jedna minima / maksima. Dlatego też lokalne optimum jest również globalnym optymalnym. Zejście gradientowe w końcu znajdzie rozwiązanie.

Dlaczego ta funkcja celu jest wypukła? Na tym polega piękno używania kwadratu błędu do minimalizacji. Wyprowadzenie i równość do zera dobrze pokaże, dlaczego tak jest. Jest to dość problem z podręcznikiem i jest omawiany niemal wszędzie.

Vladislavs Dovgalecs
źródło
4
Wypukłość nie oznacza unikalnego minimum. Zazwyczaj musisz odwoływać się do ścisłej wypukłości funkcji celu zdefiniowanej w dziedzinie wypukłej. Problemem są również kryteria zakończenia opadania gradientu za pomocą arytmetyki zmiennoprzecinkowej: nawet gdy funkcja celu jest ściśle wypukła, algorytm może znaleźć różne rozwiązania (w zależności od wartości początkowych), gdy funkcja jest prawie płaska w pobliżu jej minimum.
whuber
@ Whuber, czy mógłbyś to dla mnie uprościć i wyjaśnić?
Anjela Minoeu
@ whuber Myślę, że pierwszym problemem jest użycie terminologii. Po drugie, wypukłość oznacza unikalne minimum. Nie widzę rozróżnialnej funkcji wklęsłej, która nie ma jednego minimum / maksimum. Zobacz dowód tutaj: planetmath.org/localminimumofconvexfunctionis niekoniecznieglobal
Vladislavs Dovgalecs
3
Nie zadałem sobie trudu, aby przeczytać dowód, ponieważ musi on odwoływać się do ścisłej wypukłości. Problem najmniejszych kwadratów z nieznanymi współczynnikami będzie wypukły, ale nie ściśle wypukły, a zatem będzie miał (nieskończenie) wiele rozwiązań. Ale nie jest to całkowicie istotne dla spadku gradientu, który ma swoje własne problemy - niektóre z nich są wyraźnie omówione w artykule w Wikipedii . Tak więc, zarówno w sensie teoretycznym, jak i praktycznym, prawidłowa odpowiedź na pytanie jest prawdziwa : zejście gradientowe może - i da - wiele rozwiązań.
whuber
@ whuber Tak, dowód odwołuje się do ścisłej wypukłości.
Vladislavs Dovgalecs