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

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?

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 ( λ , μ , ν ) $z$$x$$y$$(x,y,z)$$(1,-1,0),(2,-2,-1),(3,-3,-2)$$\hat z = 1 + y$$\hat z = 1-x$$(\lambda,\mu,\nu)$$\varepsilon$

Suma kwadratów reszt upraszcza się

(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$$56$$3\times 56 - (24/2)^2 = 24$$(\mu,\nu,\lambda)$$\mu=\nu=0$$\lambda$$\operatorname{SSR}$$\lambda$$\lambda$

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 . $\hat z = 1 - x$$\hat z = 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).$\mu$$-1, 1$$|\mu| \ge 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-\mu)^2 + (-1-\mu)^2$$|\mu| \ge 1/2$$\mu=\pm 1/2$ nonconvex:$\mu \in (-\infty, -1/2]\cup [1/2, \infty)$

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.$\mu$$\mu=\pm 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.$\mu=1/2$$\mu=-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).

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:

$w$$a$

$a_{12} =9,a_{13} = 1/9,a_{23}=9,a_{31}=1/9$

$minimize$ ${(9-\frac{w_1}{w_2})^2+(\frac{1}{9}-\frac{w_1}{w_3})^2+(\frac{1}{9}-\frac{w_2}{w_1})^2+(9-\frac{w_2}{w_3})^2+(9-\frac{w_3}{w_1})^2+(\frac{1}{9}-\frac{w_3}{w_2})^2}$

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

$w = (0.670,0.242,0.080),obj = 165.2$

$w = (0.080,0.242,0.670),obj = 165.2$

$w = (0.242,0.670,0.080),obj = 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.

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.