La preuve de formules équivalentes de régression de crête

15

J'ai lu les livres les plus populaires en apprentissage statistique

1- Les éléments de l'apprentissage statistique.

2- Une introduction à l'apprentissage statistique .

Les deux mentionnent que la régression de crête a deux formules qui sont équivalentes. Existe-t-il une preuve mathématique compréhensible de ce résultat?

Je suis également passé par Cross Validated , mais je n'y trouve pas de preuve définitive.

De plus, LASSO bénéficiera-t-il du même type de preuve?

entrez la description de l'image ici

jeza
la source
1
Le lasso n'est pas une forme de régression de crête.
Xi'an
@jeza, pourriez-vous expliquer ce qui manque dans ma réponse? Il dérive vraiment tout ce qui peut être dérivé sur la connexion.
Royi
@jeza, pourriez-vous être précis? À moins que vous ne connaissiez le concept lagrangien de problème contraint, il est difficile de donner une réponse concise.
Royi
1
@jeza, un problème d'optimisation contraint peut être converti en optimisation de la fonction lagrangienne / conditions KKT (comme expliqué dans les réponses actuelles). Ce principe a déjà de nombreuses explications simples différentes sur Internet. Dans quelle direction une explication supplémentaire de la preuve est-elle nécessaire? Explication / preuve du multiplicateur / fonction lagrangien, explication / preuve comment ce problème est un cas d'optimisation qui concerne la méthode de Lagrange, différence KKT / Lagrange, explication du principe de régularisation, etc?
Sextus Empiricus

Réponses:

19

La régression de crête classique ( régularisation de Tikhonov ) est donnée par:

argminx12xy22+λx22

L'affirmation ci-dessus est que le problème suivant est équivalent:

argminx12xy22subject tox22t

Définissons x comme la solution optimale du premier problème et ~ x comme la solution optimale du second problème.x^x~

La revendication d'équivalence signifie que t,λ0:x^=x~ .
À savoir, vous pouvez toujours avoir une paire det etλ0 , la solution du problème est la même.

Comment pourrions-nous trouver une paire?
Eh bien, en résolvant les problèmes et en examinant les propriétés de la solution.
Les deux problèmes sont convexes et lisses, ce qui devrait simplifier les choses.

La solution du premier problème est donnée au point où le gradient disparaît, ce qui signifie:

x^y+2λx^=0

Les conditions KKT du deuxième problème stipulent:

x~y+2μx~=0

et

μ(x~22t)=0

La dernière équation suggère que μ=0 ou x~22=t .

Faites attention à ce que les 2 équations de base soient équivalentes.
A savoir si x = ~ x et μ = λ les deux équations tiennent. x^=x~μ=λ

Cela signifie donc que dans le cas où y22t il faut définir μ=0 ce qui signifie que pour t suffisamment grand pour que les deux soient équivalents, il faut définir λ=0 .

Dans l'autre cas, on devrait trouver μ où:

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

C'est essentiellement lorsque x~22=t

Une fois que vous avez trouvé que μ les solutions entreront en collision.

Concernant le cas L1 (LASSO), eh bien, ça marche avec la même idée.
La seule différence est que nous n'avons pas fermé pour la solution, d'où la dérivation de la connexion est plus difficile.

Jetez un œil à ma réponse à StackExchange Cross Validated Q291962 et StackExchange Signal Processing Q21730 - Signification de λ dans Basis Pursuit .

Remarque
Que se passe-t-il réellement?
Dans les deux problèmes, x essaie d'être aussi proche que possible de y .
Dans le premier cas, x=y disparaîtra le premier terme (la distance L2 ) et dans le second cas il fera disparaître la fonction objectif.
La différence est que dans le premier cas, il faut équilibrer la norme L2 de x . Lorsque λ augmente, l'équilibre signifie que vous devez réduire x .
Dans le second cas il y a un mur, vous rapprochez x plus en plus de yjusqu'à ce que vous frappiez le mur qui est la contrainte sur sa norme (By t ).
Si le mur est suffisamment éloigné (valeur élevée de t ) et assez dépend de la norme de y alors i n'a pas de sens, tout comme λ n'est pertinent que de sa valeur multipliée par la norme de y commence à avoir un sens.
La connexion exacte est par le Lagrangien indiqué ci-dessus.

Ressources

J'ai trouvé cet article aujourd'hui (03/04/2019):

Royi
la source
fait l'équivalent signifie que les \ lambda et \ t devraient être les mêmes. Parce que je ne vois pas ça dans la preuve. merci
jeza
@jeza, Comme je l'ai écrit ci-dessus, pour tout il y a λ 0 (pas nécessairement égal à t mais une fonction de t et des données y ) de sorte que les solutions des deux formes sont les mêmes. tλ0tty
Royi
3
@jeza, les deux et t sont essentiellement des paramètres libres ici. Une fois que vous avez spécifié, disons, λ , cela donne une solution optimale spécifique. Mais t reste un paramètre libre. Donc, à ce stade, l'affirmation est qu'il peut y avoir une certaine valeur de t qui donnerait la même solution optimale. Il n'y a pratiquement pas de contraintes sur ce que t doit être; ce n'est pas comme si cela devait être une fonction fixe de λ , comme t = λ / 2 ou quelque chose. λtλtttλt=λ/2
gung - Rétablir Monica
@Royi, je voudrais savoir 1- pourquoi votre formule a (1/2), alors que les formules en question ne le sont pas? 2- utilisez KKT pour montrer l'équivalence des deux formules? 3- Si oui, je ne vois toujours pas cette équivalence. Je ne suis pas sûr mais ce que je m'attends à voir, c'est cette preuve pour montrer que la formule un = formule deux.
jeza
1. Simplement plus facile lorsque vous différenciez le terme LS. Vous pouvez déplacer la forme my vers l'OP λ par un facteur de deux. 2. J'ai utilisé KKT pour le 2ème cas. Le premier cas n'a pas de contraintes, vous pouvez donc simplement le résoudre. 3. Il n'y a pas d'équation de forme fermée entre eux. J'ai montré la logique et comment vous pouvez créer un graphique les reliant. Mais comme je l'ai écrit, cela changera pour chaque y (cela dépend des données). λλy
Royi
9

Une approche moins rigoureuse mathématiquement, mais peut-être plus intuitive, pour comprendre ce qui se passe consiste à commencer par la version de contrainte (équation 3.42 dans la question) et à la résoudre en utilisant les méthodes du "Lagrange Multiplier" ( https: //en.wikipedia .org / wiki / Lagrange_multiplier ou votre texte de calcul multivariable préféré). N'oubliez pas que dans le calcul, est le vecteur des variables, mais dans notre cas, x est constant et β est le vecteur variable. Une fois que vous avez appliqué la technique du multiplicateur de Lagrange, vous vous retrouvez avec la première équation (3,41) (après avoir jeté l'extra - λ t qui est constant par rapport à la minimisation et peut être ignoré).xxβλt

Cela montre également que cela fonctionne pour le lasso et d'autres contraintes.

Greg Snow
la source
8

Cela vaut peut-être la peine d'être lu sur la dualité lagrangienne et une relation plus large (parfois équivalente) entre:

  • optimisation soumise à des contraintes dures (c'est-à-dire inviolables)
  • optimisation avec pénalités pour violation des contraintes.

Introduction rapide à la dualité faible et à la dualité forte

Supposons que nous ayons une fonction de deux variables. Pour tout x et y , nous avons:f(x,y)x^y^

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

Depuis détient pour tout x et y détient également que: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)

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 L as:

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

The min-max interpretation of the Lagrangian

The Ridge regression problem subject to hard constraints is:

minbmaxλ0L(b,λ)

You pick b to minimize the objective, cognizant that after b is picked, your opponent will set λ to infinity if you chose b such that j=1pbj2>t.

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

maxλ0minbL(b,λ)

Here, your opponent chooses λ first! You then choose b to minimize the objective, already knowing their choice of λ. The 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
la source
note that your answer can be extended to any convex function.
81235
6

They are not equivalent.

For a constrained minimization problem

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

we solve by minimize over b the corresponding Lagrangean

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

Here, t is a bound given exogenously, λ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 t.

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

(3)minb{Λ+λt}

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

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

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

The general constrained minimization problem allows for λ=0 also, and essentially it is a formulation that includes as special cases the basic least-squares estimator (λ=0) and the Ridge estimator (λ>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
la source
@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 instead of λ>0 and we could just as well add the constrain t<βOLS22 to exclude the cases where λ=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