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?
Réponses:
La régression de crête classique ( régularisation de Tikhonov ) est donnée par:
L'affirmation ci-dessus est que le problème suivant est équivalent:
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~ . t etλ ≥ 0 , la solution du problème est la même.
À savoir, vous pouvez toujours avoir une paire de
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:
Les conditions KKT du deuxième problème stipulent:
et
La dernière équation suggère queμ=0 ou ∥x~∥22=t .
Faites attention à ce que les 2 équations de base soient équivalentes.x^=x~ μ=λ
A savoir si x = ~ x et μ = λ les deux équations tiennent.
Cela signifie donc que dans le cas où∥y∥22≤t 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ù:
C'est essentiellement lorsque∥x~∥22=t
Une fois que vous avez trouvé queμ les solutions entreront en collision.
Concernant le casL1 (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 .
Remarquex essaie d'être aussi proche que possible de y . x=y disparaîtra le premier terme (la distance L2 ) et dans le second cas il fera disparaître la fonction objectif. L2 de x . Lorsque λ augmente, l'équilibre signifie que vous devez réduire x . x plus en plus de y jusqu'à ce que vous frappiez le mur qui est la contrainte sur sa norme (By t ). 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.
Que se passe-t-il réellement?
Dans les deux problèmes,
Dans le premier cas,
La différence est que dans le premier cas, il faut équilibrer la norme
Dans le second cas il y a un mur, vous rapprochez
Si le mur est suffisamment éloigné (valeur élevée de
La connexion exacte est par le Lagrangien indiqué ci-dessus.
Ressources
J'ai trouvé cet article aujourd'hui (03/04/2019):
la source
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é).x x β −λt
Cela montre également que cela fonctionne pour le lasso et d'autres contraintes.
la source
Cela vaut peut-être la peine d'être lu sur la dualité lagrangienne et une relation plus large (parfois équivalente) entre:
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^
Depuis détient pour tout x et y détient également que:x^ y^
This is known as weak duality. In certain circumstances, you have also have strong duality (also known as the saddle point property):
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 functionL as:
The min-max interpretation of the Lagrangian
The Ridge regression problem subject to hard constraints is:
You pickb to minimize the objective, cognizant that after b is picked, your opponent will set λ to infinity if you chose b such that ∑pj=1b2j>t .
If strong duality holds (which it does here because Slater's condition is satisfied fort>0 ), you then achieve the same result by reversing the order:
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.
la source
They are not equivalent.
For a constrained minimization problem
we solve by minimize overb the corresponding Lagrangean
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
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 overb given λ>0 . But, in the lens of the constrained minimization problem, assuming λ>0 imposes the condition that the constraint is binding, i.e that
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.
la source