Kann es mehrere lokale optimale Lösungen geben, wenn wir eine lineare Regression lösen?

19

Ich habe diese Aussage auf einer alten True / False-Prüfung gelesen:

Wir können mehrere lokale optimale Lösungen erhalten, wenn wir ein lineares Regressionsproblem lösen, indem wir die Summe der Fehlerquadrate mithilfe des Gradientenabfalls minimieren.

Lösung: Falsch

Meine Frage ist, welcher Teil dieser Frage ist falsch? Warum ist diese Aussage falsch?

Anjela Minoeu
quelle

Antworten:

8

Diese Frage ist insofern interessant, als sie Zusammenhänge zwischen Optimierungstheorie, Optimierungsmethoden und statistischen Methoden aufdeckt, die jeder fähige Benutzer von Statistiken verstehen muss. Obwohl diese Zusammenhänge einfach und leicht zu erlernen sind, sind sie subtil und werden oft übersehen.

Um einige Ideen aus den Kommentaren zu anderen Antworten zusammenzufassen, möchte ich darauf hinweisen, dass "lineare Regression" nicht nur theoretisch, sondern in der Praxis zu nicht eindeutigen Lösungen führen kann.

Fehlende Erkennbarkeit

Das erste ist, wenn das Modell nicht identifizierbar ist. Dies schafft eine konvexe, aber nicht streng konvexe Zielfunktion, die mehrere Lösungen hat.

Betrachten wir zum Beispiel Regression gegen und (mit einem Achsenabschnitt) für die Daten . Eine Lösung ist . Ein anderes ist . Um zu sehen, dass es mehrere Lösungen geben muss, parametrisieren Sie das Modell mit drei Realparametern und einem Fehlerterm im Formularzx( x , y , z ) ( 1 , - 1 , 0 ) , ( 2 , - 2 , - 1 ) , ( 3 , - 3 , - 2 ) , z = 1 + y z = 1 - x ( λ , μ , ν ) εy(x,y,z)(1,-1,0),(2,-2,-1),(3,-3,-2)z^=1+yz^=1-x(λ,μ,ν)ε

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

Die Summe der Quadrate der Residuen vereinfacht sich zu

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

(Dies ist ein Grenzfall für objektive Funktionen, die in der Praxis auftreten, wie der unter Kann der empirische Hessian eines M-Schätzers unbestimmt sein? Beschriebene , in dem Sie detaillierte Analysen lesen und Diagramme der Funktion anzeigen können.)

Da die Koeffizienten der Quadrate ( und ) positiv sind und die Determinante positiv ist, ist dies eine positiv-semidefinite quadratische Form in . Es wird minimiert, wenn , aber kann einen beliebigen Wert haben. Da die Zielfunktion nicht von abhängt , gilt dies auch für den Gradienten (oder andere Ableitungen). Daher setzt jeder Algorithmus für den Gradientenabstieg - wenn er keine willkürlichen Richtungsänderungen vornimmt - den Wert der Lösung von auf einen beliebigen Startwert.56 3 × 56 - ( 24 / 2 ) 2 = 24 ( μ , ν , λ ) μ = ν = 0 λ SSR λ λ3563×56(24/2)2=24(μ,ν,λ)μ=ν=0λSSRλλ

Auch wenn kein Gefälle verwendet wird, kann die Lösung variieren. In Rzum Beispiel gibt es zwei einfache, gleichwertige Möglichkeiten , dieses Modell zu spezifizieren: wie z ~ x + yoder z ~ y + x. Die erste ergibt , die zweite ergibt . z =1+yz^=1xz^=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 

(Die NAWerte sollten als Nullen interpretiert werden, jedoch mit der Warnung, dass mehrere Lösungen vorhanden sind. Die Warnung war möglich, da vorläufige Analysen Runabhängig von der Lösungsmethode durchgeführt wurden. Eine Gradientenabstiegsmethode würde wahrscheinlich nicht die Möglichkeit mehrerer Lösungen erkennen.) obwohl ein guter Sie vor einer gewissen Ungewissheit warnen würde, dass das Optimum erreicht wurde.)

Parameterbeschränkungen

Strikte Konvexität garantiert ein einzigartiges globales Optimum, vorausgesetzt, der Bereich der Parameter ist konvex. Parametereinschränkungen können nicht konvexe Domänen erstellen und zu mehreren globalen Lösungen führen.

Ein sehr einfaches Beispiel liefert das Problem der Schätzung eines "Mittelwerts" für die Daten , die der Einschränkung unterliegen . Dies modelliert eine Situation, die im Gegensatz zu Regularisierungsmethoden wie Ridge Regression, Lasso oder Elastic Net steht: Es besteht darauf, dass ein Modellparameter nicht zu klein wird. (Auf dieser Website wurden verschiedene Fragen zur Lösung von Regressionsproblemen mit solchen Parameterbeschränkungen gestellt, die zeigen, dass sie in der Praxis auftreten.)- 1 , 1 | μ | 1 / 2μ1,1|μ|1/2

Für dieses Beispiel gibt es zwei Lösungen mit den kleinsten Quadraten, die beide gleich gut sind. Sie werden durch Minimieren von unter der Bedingung . Die beiden Lösungen sind . Es kann mehr als eine Lösung geben, da die Parameterbeschränkung die Domäne nicht konvex macht:| μ | 1 / 2 μ = ± 1 / 2 μ ( - , - 1 / 2 ] [ 1 / 2 , )(1μ)2+(1μ)2|μ|1/2μ=±1/2μ(,1/2][1/2,)

Plot der Quadratsumme gegen $ \ mu $

Die Parabel ist der Graph einer (streng) konvexen Funktion. Der dicke rote Teil ist der Teil, der auf die Domäne von : Er hat zwei niedrigste Punkte bei , wobei die Summe der Quadrate beträgt . Der Rest der Parabel (gepunktet dargestellt) wird durch die Beschränkung entfernt, wodurch sein eindeutiges Minimum von der Betrachtung ausgeschlossen wird.& mgr; = ± 1 / 2 5 / 2μμ=±1/25/2

Eine Gradientenabstiegsmethode würde, wenn sie nicht bereit wäre, große Sprünge zu machen, wahrscheinlich die "eindeutige" Lösung finden wenn sie mit einem positiven Wert beginnt, und andernfalls würde sie die "eindeutige" Lösung finden wenn mit einem negativen Wert begonnen wird.μ = - 1 / 2μ=1/2μ=1/2

Dieselbe Situation kann bei größeren Datensätzen und in höheren Dimensionen auftreten (dh, es müssen mehr Regressionsparameter angepasst werden).

whuber
quelle
1
Ein sehr einfaches Beispiel für eine konvexe Funktion, die nicht streng konvex ist und unendlich viele Minima hat, ist . Jeder Punkt auf der Linie ist ein Mindestpunkt. f(x,y)=(xy)2y=x
kjetil b halvorsen
1
@Kjetil Danke, das stimmt. Der Trick dabei ist zu zeigen, wie solche Funktionen in Regressionssituationen tatsächlich entstehen. Ihre Funktion ist genau die Inspiration für das erste Beispiel, das ich angeboten habe.
Whuber
Ein visuelles Beispiel: stats.stackexchange.com/a/151351/171583 .
Ayorgo
2

Ich fürchte, es gibt keine binäre Antwort auf Ihre Frage. Wenn die lineare Regression streng konvex ist (keine Einschränkungen für Koeffizienten, kein Regularisierer usw.), hat die Gradientenabnahme eine eindeutige Lösung und ist ein globales Optimum. Gradientenabstieg kann und wird mehrere Lösungen zurückgeben, wenn Sie ein nicht konvexes Problem haben.

Obwohl OP nach einer linearen Regression fragt, zeigt das folgende Beispiel eine Minimierung der kleinsten Quadrate, obwohl nichtlineare (gegenüber der linearen Regression, die OP will) mehrere Lösungen haben können und ein Gradientenabfall unterschiedliche Lösungen zurückgeben kann.

Ich kann das anhand eines einfachen Beispiels empirisch zeigen

  1. Die Summe der Fehlerquadrate kann einige Zeit nicht konvex sein, daher gibt es mehrere Lösungen
  2. Gradient-Descent-Methode kann mehrere Lösungen bieten.

Betrachten Sie das Beispiel, in dem Sie versuchen, die kleinsten Quadrate für das folgende Problem zu minimieren:

Bildbeschreibung hier eingeben

wo Sie versuchen, für durch Minimierung der Zielfunktion zu lösen . Die obige Funktion ist zwar differenzierbar, aber nicht konvex und kann mehrere Lösungen haben. Setzt man die tatsächlichen Werte für siehe unten.wein

ein12=9,ein13=1/9,ein23=9,ein31=1/9

michnichmichze (9-w1w2)2+(19-w1w3)2+(19-w2w1)2+(9-w2w3)2+(9-w3w1)2+(19-w3w2)2

Das obige Problem hat 3 verschiedene Lösungen und sie sind wie folgt:

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

Wie oben gezeigt, kann das Problem der kleinsten Quadrate nicht konvex sein und mehrere Lösungen haben. Das obige Problem kann dann mithilfe einer Gradientenabstiegsmethode wie Microsoft Excel Solver gelöst werden, und jedes Mal, wenn wir ausgeführt werden, erhalten wir eine andere Lösung. Da der Gradientenabstieg ein lokaler Optimierer ist und in der lokalen Lösung stecken bleiben kann, müssen unterschiedliche Startwerte verwendet werden, um echte globale Optima zu erhalten. Ein solches Problem hängt von den Startwerten ab.

Prognostiker
quelle
2
Ich glaube nicht, dass dies die Frage von OP beantwortet, da OP speziell nach linearer Regression fragt , nicht nach Optimierung im Allgemeinen.
Sycorax sagt Reinstate Monica
1
Nein, tut es nicht, aber nur zu versuchen, Probleme mit Optimierungen herauszustellen, wird mit Vorbehalten aktualisiert
Prognostiker
@ user777 du hast recht. Dies ist eine sehr gültige Frage zur alten Prüfung des MIT. Ich bin sicher, dass die Antwort dank Forecastet falsch ist.
Anjela Minoeu
Bist du sicher, dass ich Recht habe?
Anjela Minoeu
@AnjelaMinoeu, ich habe meine Antwort aktualisiert.
Prognose
1

Dies liegt daran, dass die Zielfunktion, die Sie minimieren, konvex ist und es nur ein Minimum / Maximum gibt. Daher ist das lokale Optimum auch ein globales Optimum. Steigungsabstieg wird schließlich die Lösung finden.

Warum ist diese Zielfunktion konvex? Dies ist das Schöne daran, den quadratischen Fehler zur Minimierung zu verwenden. Die Herleitung und die Gleichheit mit Null werden gut zeigen, warum dies der Fall ist. Es ist ein ziemliches Lehrbuchproblem und wird fast überall behandelt.

Vladislavs Dovgalecs
quelle
4
Konvexität bedeutet kein eindeutiges Minimum. In der Regel müssen Sie sich auf die strikte Konvexität einer objektiven Funktion berufen, die in einer konvexen Domäne definiert ist. Ein weiteres Problem sind hier die Abbruchkriterien für den Gradientenabstieg mit Gleitkomma-Arithmetik: Selbst wenn die Zielfunktion streng konvex ist, wird der Algorithmus wahrscheinlich unterschiedliche Lösungen finden (abhängig von den Startwerten), wenn die Funktion in der Nähe ihres Minimums nahezu flach ist.
whuber
@whuber würdest du es mir bitte einfacher und klarer machen?
Anjela Minoeu
@whuber Ich denke, das erste Problem ist die Verwendung von Terminologie. Zweitens impliziert Konvexität ein eindeutiges Minimum. Ich kann keine differenzierbare konkave Funktion sehen, die kein einzelnes Minimum / Maximum hat. Siehe Beweis hier: planetmath.org/localminimumofconvexfunctionisnecessarilyglobal
Vladislavs Dovgalecs
3
Ich habe mir nicht die Mühe gemacht, den Beweis zu lesen, da er eine strikte Konvexität erfordern muss , um korrekt zu sein. Ein Problem der kleinsten Quadrate mit nicht identifizierbaren Koeffizienten wird konvex, aber nicht streng konvex sein und dadurch (unendlich) viele Lösungen haben. Dies ist jedoch für den Gradientenabstieg, der seine eigenen Probleme hat - von denen einige im Wikipedia-Artikel klar diskutiert werden, nicht ganz relevant . Sowohl in theoretischer als auch in praktischer Hinsicht ist die richtige Antwort auf die Frage richtig : Gradientenabstieg kann - und wird - mehrere Lösungen geben.
whuber
@whuber Ja, der Beweis spricht die strenge Konvexität an.
Vladislavs Dovgalecs