Ridge-Regressionsformulierung als eingeschränkt oder bestraft: Wie sind sie äquivalent?

10

Ich scheine eine Behauptung über lineare Regressionsmethoden, die ich an verschiedenen Orten gesehen habe, falsch zu verstehen. Die Parameter des Problems sind:

Eingang:

p + 1 y i p x i jN Datenproben von Größen, die jeweils aus einer "Antwort" -Größe und "Prädiktor" -Größenp+1yipxij

Das gewünschte Ergebnis ist eine "gute lineare Anpassung", die die Antwort basierend auf den Prädiktoren vorhersagt, wobei eine gute Anpassung (unter anderen Kriterien) kleine Unterschiede zwischen der Vorhersage und der beobachteten Antwort aufweist.

Ausgabe: Koeffizienten wobei eine "gute Anpassung" für die Vorhersage der Antwortgröße aus den Prädiktorgrößen ist. p+1βjβ0+j=1pxijβj

Ich bin verwirrt über den "Ridge Regression" -Ansatz für dieses Problem. In "Die Elemente des statistischen Lernens" von Hastie, Tibshirani und Friedman wird die Gratregression auf zwei Arten formuliert.

Zunächst als eingeschränktes Optimierungsproblem :

p Σ j = 1 β 2 it

argminβi=1N(yi(β0+j=1p(xijβj)))2
unterliegt der Einschränkung für einen positiven Parameter t.
j=1pβi2t

Zweitens ist das bestrafte Optimierungsproblem : für einen positiven Parameter . λ

argminβ(λj=1pβj2)+i=1N(yi(β0+j=1p(xijβj)))2
λ

Der Text sagt, dass diese Formulierungen äquivalent sind und dass es eine "Eins-zu-Eins-Entsprechung zwischen den Parametern und " gibt. Ich habe diese Behauptung (und ähnliche) zusätzlich zu diesem Buch an mehreren Stellen gesehen. Ich glaube, mir fehlt etwas, weil ich nicht sehe, wie die Formulierungen gleichwertig sind, wie ich es verstehe.tλt

Betrachten Sie den Fall, in dem und mit , und , . Wenn Sie den Parameter wählen, wird die eingeschränkte Formulierung zu:p = 1 y 1 = 0 x 1 , 1 = 0 y 2 = 1 x 1 , 2 = 1 t = 2N=2p=1y1=0x1,1=0y2=1x1,2=1t=2

argminβ0,β1(β02+(1(β0+β1))2)

erweitert auf

argminβ0,β1(2β02+2β0β12β0+β122β1+1)

Um dies zu lösen, finden Sie die Lösung, bei der die partiellen Ableitungen in Bezug auf und Null sind: mit Lösung und . Beachten Sie, dass nach Bedarf.β 1 4 β 0 + 2 β 1 - 2 = 0 2 β 0 + 2 β 1 - 2 = 0 β 0 = 0 β 1 = 1 β 2 0 + β 2 1tβ0β1

4β0+2β12=0
2β0+2β12=0
β0=0β1=1β02+β12t

In welcher Beziehung steht diese Ableitung zur anderen Formulierung? Gemäß der Erklärung gibt es einen Wert von eindeutig entspricht. Wenn wir die bestrafte Formulierung des Problems optimieren, werden wir die gleichen und ableiten . In diesem Fall wird die bestrafte Form zu erweitert auf Um dies zu lösen, finden Sie die Lösung, bei der die partiellen Ableitungen mit hinsichtlicht λ + 2 β 2λtβ0β1

argminβ0,β1(λ(β02+β12)+β02+(1(β0+β1))2)
argminβ0,β1(β02λ+2β02+2β0β12β0+β12λ+β122β1+1)
β0 und sind Null: für diese Gleichungen erhalte ich die Lösung Wenn das richtig ist der einzige Weg , um get gesetzt ist . Dies wäre jedoch das gleiche wir für benötigen würden. Was bedeuten sie also unter "Eins-zu-Eins-Korrespondenz"?β1
2β0λ+4β0+2β12=0
2β0+2β1λ+2β12=0
β0=λ/(λ2+3λ+1)
β1=(λ+1)/((λ+1)(λ+2)1)
β0=0λ=0λt=4

Zusammenfassend bin ich total verwirrt von den beiden Präsentationen und ich verstehe nicht, wie sie einander entsprechen. Ich verstehe nicht, wie Sie ein Formular optimieren und die gleiche Lösung für das andere Formular erhalten können oder wie mit . Dies ist nur ein Beispiel für diese Art von Korrespondenz - es gibt andere für andere Ansätze wie Lasso - und ich verstehe keinen von ihnen.tλt

Jemand, bitte hilf mir.

user101311
quelle
1
Siehe auch : stats.stackexchange.com/questions/190993 (siehe die akzeptierte Antwort).
Amöbe
1
Der "verwandte" Link bestätigt die in der Frage diskutierte Korrespondenz erneut, ohne diese Frage oder den gezeigten Beispielfall zu behandeln. Ich glaube nicht, dass es diese Frage beantwortet.
Aaron Watters

Antworten:

6

Die Verwirrung entsteht hier durch den Versuch, in einem Bereich von oder Werten zu arbeiten, in denen die Regression nicht eingeschränkt ist.tλ

In Ihrem Beispiel beträgt bei der perfekten Anpassung der Regressionslinie die Summe der Quadrate der Regressionskoeffizienten 1. Der Wert von (oder ein Wert von , der 1 oder größer ist) stellt also keine Einschränkung für die Regression dar. Im Raum der Werte wird die gesamte uneingeschränkte Regression durch . Es gibt keine Eins-zu-Eins-Entsprechung zwischen und in der uneingeschränkten Regression ; Alle Werte von von 1 oder höher entsprechen in diesem Fall . Das war die Region, die Sie untersucht haben.t λ λ = 0 t λ t λ = 0t=2tλλ=0tλ tλ=0

Nur ein Wert von kleiner als 1 wird die Regression einschränken, was positiven Werten von . Wie die akzeptierte Antwort auf diese Seite zeigt, gilt die Eins-zu-Eins-Entsprechung zwischen und in Ihrem Beispiel für " wenn die Einschränkung bindend ist" für Werte von kleiner als 1.λ t λ ttλtλt

EdM
quelle
In diesem Fall sollten sie behaupten, dass die Einschränkung verbindlich sein muss. Meinen Sie damit, dass wir damit die Äquivalenz gültig ist? βj2=t
Aaron Watters
1
Fairerweise denke ich nicht, dass sich die Leute zu viele Sorgen um Details der eingeschränkten Optimierung machen, wenn die Einschränkung nicht bindend ist. Dann erhalten Sie einfach die gewöhnliche Lösung der kleinsten Quadrate. Wenn die Einschränkung bindend ist, sollte die Optimierung ein eindeutiges Ergebnis an der Grenze der Einschränkungsmenge liefern, so dass , wodurch unter diesen Umständen eine Eins-zu-Eins-Äquivalenz von mit bereitgestellt wird . t λβj2=ttλ
EdM
+1. Wenn die Einschränkung nicht bindend ist, besteht immer noch eine Entsprechung zwischen und aber es ist keine Eins-zu-Eins: Jedes nicht bindende wird wie von @Aaron korrekt berechnet. λ t λ = 0tλtλ=0
Amöbe
Zu Ihrer Information, ich bin ein Programmierer. Es ist wichtig zu wissen, wann eine Methode geeignet ist, wenn Sie Computerprogramme schreiben. "Die Einschränkung muss verbindlich sein" scheint in vielen Präsentationen der Methode weggelassen zu werden.
Aaron Watters
4

Die klassische Ridge Regression ( Tikhonov Regularization ) ist gegeben durch:

argminx12xy22+λx22

Die obige Behauptung ist, dass das folgende Problem äquivalent ist:

argminx12xy22subject tox22t

Definieren wir als die optimale Lösung des ersten Problems und als die optimale Lösung des zweiten Problems.x^x~

Der Äquivalenzanspruch bedeutet, dass . Sie können nämlich immer ein Paar von und so dass die Lösung des Problems dieselbe ist.t,λ0:x^=x~
tλ0

Wie könnten wir ein Paar finden?
Nun, indem Sie die Probleme lösen und die Eigenschaften der Lösung betrachten.
Beide Probleme sind konvex und glatt, so dass die Dinge einfacher werden sollten.

Die Lösung für das erste Problem wird an dem Punkt gegeben, an dem der Gradient verschwindet, was bedeutet:

x^y+2λx^=0

Die KKT-Bedingungen des zweiten Problems besagen:

x~y+2μx~=0

und

μ(x~22t)=0

Die letzte Gleichung legt nahe, dass entweder oder .μ=0x~22=t

Achten Sie darauf, dass die beiden Basisgleichungen äquivalent sind.
Nämlich wenn und beide Gleichungen gelten. x^=x~μ=λ

Das bedeutet also, dass im Fall man muss was bedeutet, dass für groß genug, damit beide gleichwertig sind, man .y22tμ=0tλ=0

Im anderen Fall sollte man wo:μ

yt(I+2μI)1(I+2μI)1y=t

Dies ist im Grunde genommen, wennx~22=t

Sobald Sie feststellen, dass die Lösungen kollidieren.μ

In Bezug auf den Fall funktioniert dies mit derselben Idee. Der einzige Unterschied besteht darin, dass wir keine Lösung gefunden haben. Daher ist es schwieriger, die Verbindung abzuleiten.L1

Schauen Sie sich meine Antwort unter StackExchange Cross Validated Q291962 und StackExchange Signal Processing Q21730 an - Bedeutung von in Basis Pursuitλ .

Royi
quelle
Woher kam der Mu?
Tatami
Das Obige löst 2 verschiedene Probleme. Da der erste ich als Lagrange-Multiplikator für die Ungleichheitsbeschränkungen des zweiten verwendet. λμ
Royi