Der Beweis äquivalenter Formeln der Gratregression

15

Ich habe die beliebtesten Bücher zum statistischen Lernen gelesen

1- Die Elemente des statistischen Lernens.

2- Eine Einführung in das statistische Lernen .

Beide erwähnen, dass die Gratregression zwei äquivalente Formeln hat. Gibt es einen nachvollziehbaren mathematischen Beweis für dieses Ergebnis?

Ich habe auch Cross Validated durchlaufen , kann dort aber keinen eindeutigen Beweis finden.

Wird LASSO darüber hinaus die gleiche Art von Beweis erhalten?

Bildbeschreibung hier eingeben

jeza
quelle
1
Lasso ist keine Form der Gratregression.
Xi'an
@jeza, könntest du erklären, was in meiner Antwort fehlt? Es lässt sich wirklich alles über die Verbindung ableiten.
Royi
@jeza, könntest du konkret sein? Wenn Sie das Lagrange-Konzept für ein eingeschränktes Problem nicht kennen, ist es schwierig, eine prägnante Antwort zu geben.
Royi
1
@jeza, ein eingeschränktes Optimierungsproblem kann in eine Optimierung der Lagrange-Funktion / KKT-Bedingungen umgewandelt werden (wie in den aktuellen Antworten erläutert). Dieses Prinzip hat bereits viele verschiedene einfache Erklärungen im Internet. In welche Richtung ist eine nähere Erläuterung des Beweises notwendig? Erklärung / Beweis des Lagrange-Multiplikators / der Lagrange-Funktion, Erklärung / Beweis, wie es sich bei diesem Problem um einen Optimierungsfall handelt, der sich auf die Methode von Lagrange, die Differenz KKT / Lagrange, die Erklärung des Regularisierungsprinzips usw. bezieht.
Sextus Empiricus

Antworten:

19

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

arg min x 12x-y 2 2 +λx 2 2

argminx12xy22+λx22

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

arg min x12x-y 2 2 vorbehaltlichX 2 2t

argminxsubject to12xy22x22t

Lassen Sie uns definieren x als die optimale Lösung des ersten Problems und ~x^ xx~ als die optimale Lösung des zweiten Problems.

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

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 es die Dinge einfacher machen sollte.

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

X -y+2λ x =0

x^y+2λx^=0

Die KKT-Bedingungen des zweiten Problems besagen:

x -y+2μx =0

x~y+2μx~=0

und

μ ( ~ x2 2 - t ) = 0

μ(x~22t)=0

Die letzte Gleichung legt nahe, dass entweder μ = 0μ=0 oder ˜ x2 2 = t istx~22=t .

Achten Sie darauf, dass die 2 Basisgleichungen äquivalent sind.
Das heißt , wenn x = ~ x und μ =x^=x~ λμ=λ beide Gleichungen gelten.

Das bedeutet, dass für den Fall y 2 2t y22tμ = 0μ=0 gesetzt werden muss, was bedeutet, dass für t, dast groß genug ist, damit beide äquivalent sind, λ = gesetzt werden muss 0λ=0 .

Im anderen Fall sollte man μ findenμ wo:

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

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

Dies ist im Grunde , wenn ~ x2 2 = tx~22=t

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

In Bezug auf den Fall L 1L1 (LASSO) funktioniert es mit der gleichen Idee.
Der einzige Unterschied ist, dass wir keine Lösung gefunden haben, weshalb es schwieriger ist, die Verbindung herzustellen.

Werfen Sie einen Blick auf meine Antwort unter StackExchange Cross Validated Q291962 und StackExchange Signal Processing Q21730 - Bedeutung von λλ in Basis Pursuit .

Bemerkung
Was ist eigentlich los?
Bei beiden Problemen versucht xx so nah wie möglich an y zu seiny .
Im ersten Fall verschwindet x = yx=y im ersten Term ( L 2L2 -Distanz) und im zweiten Fall verschwindet die Zielfunktion.
Der Unterschied besteht darin, dass man im ersten Fall die L 2L2 -Norm von xx ausgleichen muss . Wenn λλ höher wird, bedeutet das Gleichgewicht, dass Sie xx kleiner machen sollten .
Im zweiten Fall gibt es eine Mauer, die Sie xx immer näher bringen yybis Sie an die Wand stoßen, die der Norm unterliegt (By tt ).
Wenn die Wand weit genug ist (hoher Wert von tt ) und genug von der Norm von yy abhängt, dann hat i keine Bedeutung, genau wie λλ relevant ist, ist nur der Wert multipliziert mit der Norm von yy sinnvoll.
Der genaue Zusammenhang ergibt sich aus dem oben angegebenen Lagrange.

Ressourcen

Ich habe diesen Artikel heute (03/04/2019) gefunden:

Royi
quelle
Bedeutet das Äquivalent, dass \ lambda und \ t gleich sein sollten. Weil ich das im Beweis nicht sehen kann. danke
jeza
@jeza, wie ich schrieb oben, für jede T ist & lgr; 0 (nicht notwendigerweise gleich t als eine Funktion von t und den Daten ytλ0tty ) derart , dass die Lösungen der beiden Formen sind die gleichen.
Royi
3
@jeza, beide λ & t sind hier im Wesentlichen freie Parameter. Wenn Sie beispielsweise λ einmal angegeben haben, erhalten Sie eine bestimmte optimale Lösung. Aber t bleibt ein freier Parameter. An diesem Punkt lautet die Behauptung, dass es einen Wert von t geben kann , der dieselbe optimale Lösung ergibt. Im Wesentlichen gibt es keine Einschränkungen auf , was die t sein muss; Es ist nicht so, dass es eine feste Funktion von λ sein muss , wie t = λ / 2 oder so. λtλtttλt=λ/2
gung - Wiedereinsetzung von Monica
@ Royi, ich möchte 1- wissen, warum deine Formel (1/2) hat, während die fraglichen Formeln nicht? 2- Verwenden Sie KKT, um die Äquivalenz der beiden Formeln zu zeigen? 3- Wenn ja, kann ich diese Entsprechung immer noch nicht erkennen. Ich bin nicht sicher, aber ich erwarte, dass dieser Beweis zeigt, dass Formel eins = Formel zwei.
Jeza
1. Einfacher, wenn Sie den LS-Begriff unterscheiden. Sie können von my λ zum OP λ um den Faktor zwei verschieben. 2. Ich habe KKT für den 2. Fall verwendet. Der erste Fall hat keine Einschränkungen, daher können Sie ihn einfach lösen. 3. Es gibt keine geschlossene Formgleichung zwischen ihnen. Ich habe die Logik gezeigt und gezeigt, wie Sie ein Diagramm erstellen können, das sie verbindet. Aber wie ich geschrieben habe, ändert es sich für jedes y (es ist datenabhängig).λλy
Royi
9

Ein weniger mathematisch strenger, aber möglicherweise intuitiverer Ansatz zum Verstehen der Vorgänge besteht darin, mit der Einschränkungsversion (Gleichung 3.42 in der Frage) zu beginnen und sie mit den Methoden des "Lagrange-Multiplikators" ( https: //en.wikipedia ) zu lösen .org / wiki / Lagrange_multiplier oder Ihren bevorzugten multivariablen Kalkültext). Denken Sie daran, dass x im Kalkül der Vektor von Variablen ist, aber in unserem Fall ist x konstant und β ist der variable Vektor. Sobald Sie die Lagrange - Multiplikator - Technik anwenden Sie mit der ersten Gleichung am Ende (3,41) (nach dem zusätzlichen Wegwerfen - λ t , die zur Minimierung konstant ist relativ und kann ignoriert werden).xxβλt

Dies zeigt auch, dass dies für Lasso und andere Einschränkungen funktioniert.

Greg Snow
quelle
8

It's perhaps worth reading about Lagrangian duality and a broader relation (at times equivalence) between:

  • optimization subject to hard (i.e. inviolable) constraints
  • optimization with penalties for violating constraints.

Quick intro to weak duality and strong duality

Assume we have some function f(x,y)f(x,y) of two variables. For any ˆxx^ and ˆyy^, we have:

minxf(x,ˆy)f(ˆx,ˆy)maxyf(ˆx,y)

minxf(x,y^)f(x^,y^)maxyf(x^,y)

Since that holds for any ˆxx^ and ˆyy^ it also holds that:

maxyminxf(x,y)minxmaxyf(x,y)

maxyminxf(x,y)minxmaxyf(x,y)

This is known as weak duality. In certain circumstances, you have also have strong duality (also known as the saddle point property):

maxyminxf(x,y)=minxmaxyf(x,y)

maxyminxf(x,y)=minxmaxyf(x,y)

When strong duality holds, solving the dual problem also solves the primal problem. They're in a sense the same problem!

Lagrangian for constrained Ridge Regression

Let me define the function LL as:

L(b,λ)=ni=1(yxib)2+λ(pj=1b2jt)

L(b,λ)=i=1n(yxib)2+λ(j=1pb2jt)

The min-max interpretation of the Lagrangian

The Ridge regression problem subject to hard constraints is:

minbmaxλ0L(b,λ)

minbmaxλ0L(b,λ)

You pick bb to minimize the objective, cognizant that after bb is picked, your opponent will set λλ to infinity if you chose bb such that pj=1b2j>tpj=1b2j>t.

If strong duality holds (which it does here because Slater's condition is satisfied for t>0t>0), you then achieve the same result by reversing the order:

maxλ0minbL(b,λ)

maxλ0minbL(b,λ)

Here, your opponent chooses λλ first! You then choose bb to minimize the objective, already knowing their choice of λλ. The minbL(b,λ)minbL(b,λ) part (taken λλ as given) is equivalent to the 2nd form of your Ridge Regression problem.

As you can see, this isn't a result particular to Ridge regression. It is a broader concept.

References

(I started this post following an exposition I read from Rockafellar.)

Rockafellar, R.T., Convex Analysis

You might also examine lectures 7 and lecture 8 from Prof. Stephen Boyd's course on convex optimization.

Matthew Gunn
quelle
note that your answer can be extended to any convex function.
81235
6

They are not equivalent.

For a constrained minimization problem

minbni=1(yxib)2s.t.pj=1b2jt,b=(b1,...,bp)

minbi=1n(yxib)2s.t.j=1pb2jt,b=(b1,...,bp)(1)

we solve by minimize over bb the corresponding Lagrangean

Λ=ni=1(yxib)2+λ(pj=1b2jt)

Λ=i=1n(yxib)2+λ(j=1pb2jt)(2)

Here, tt is a bound given exogenously, λ0λ0 is a Karush-Kuhn-Tucker non-negative multiplier, and both the beta vector and λλ are to be determined optimally through the minimization procedure given tt.

Comparing (2)(2) and eq (3.41)(3.41) in the OP's post, it appears that the Ridge estimator can be obtained as the solution to

minb{Λ+λt}

minb{Λ+λt}(3)

Since in (3)(3) the function to be minimized appears to be the Lagrangean of the constrained minimization problem plus a term that does not involve bb, it would appear that indeed the two approaches are equivalent...

But this is not correct because in the Ridge regression we minimize over bb given λ>0λ>0. But, in the lens of the constrained minimization problem, assuming λ>0λ>0 imposes the condition that the constraint is binding, i.e that

pj=1(bj,ridge)2=t

j=1p(bj,ridge)2=t

The general constrained minimization problem allows for λ=0λ=0 also, and essentially it is a formulation that includes as special cases the basic least-squares estimator (λ=0λ=0) and the Ridge estimator (λ>0λ>0).

So the two formulation are not equivalent. Nevertheless, Matthew Gunn's post shows in another and very intuitive way how the two are very closely connected. But duality is not equivalence.

Alecos Papadopoulos
quelle
@MartijnWeterings Thanks for the comment, I have reworked my answer.
Alecos Papadopoulos
@MartijnWeterings I do not see what is confusing since the expression written in your comment is exactly the expression I wrote in my reworked post.
Alecos Papadopoulos
1
This was the duplicate question I had in mind were the equivalence is explained very intuitively to me math.stackexchange.com/a/336618/466748 the argument that you give for the two not being equivalent seems only secondary to me, and a matter of definition (the OP uses λ0λ0 instead of λ>0λ>0 and we could just as well add the constrain t<βOLS22t<βOLS22 to exclude the cases where λ=0λ=0) .
Sextus Empiricus
@MartijnWeterings When A is a special case of B, A cannot be equivalent to B. And ridge regression is a special case of the general constrained minimization problem, Namely a situation to which we arrive if we constrain further the general problem (like you do in your last comment).
Alecos Papadopoulos
Certainly you could define some constrained minimization problem that is more general then ridge regression (like you can also define some regularization problem that is more general than ridge regression, e.g. negative ridge regression), but then the non-equivalence is due to the way that you define the problem and not due to the transformation from the constrained representation to the Lagrangian representation. The two forms can be seen as equivalent within the constrained formulation/definition (non-general) that are useful for ridge regression.
Sextus Empiricus