La régularisation et les projections vectorielles sont liées par l'idée d' optimisation contrainte et les conditions de Karush-Kuhn (sans relation) -Tucker .
Quelles sont les conditions KKT?
En bref, ceux-ci indiquent que, si est une solution au problème "minimiser soumis à ", alors est également une solution au problème pour certains scalaires . Mais cela revient à dire , ce qui signifie que minimise le problème d'optimisation non contraint "minimise ".xf(x)g(x)≤0x∇f(x)=λ∇g(x)λ∇f(x)−λ∇g(x)=0xf(x)−λg(x)
L'intuition est que:
g(x)<0 . Dans ce cas, est une "solution intérieure", donc le gradient de doit être nul à ce point. (S'il n'était pas nul, nous pourrions nous déplacer un peu dans cette direction à partir de , tout en maintenant , et avoir une valeur plus élevée pour . Ensuite, nous définissons et nous ' re fait.xfxg(x)<0f(x)λ=0
Ou, . Dans ce cas, est au bord de l'espace de solution possible. Localement, cette arête ressemble à un hyperplan orthogonal au gradient , car la façon dont vous maintenez la contrainte est de ne pas monter ou descendre le gradient du tout. Mais cela signifie que la seule direction que le gradient pourrait éventuellement pointer est exactement la même direction que - s'il avait une composante orthogonale à , nous pourrions déplacer un peu dans cette direction, rester sur l'hyperplan orthogonal , et augmenter .g(x)=0x∇g(x)g(x)=0∇f∇g∇gxg(x)=0f(x)
Comment les conditions KKT expliquent la relation entre minimisation contrainte et régularisation
Si pour une norme et une constante , alors la contrainte signifie que se trouve sur une sphère de rayon sous cette norme. Et dans la formulation non contrainte, la soustraction de de la fonction que vous souhaitez maximiser est ce qui finit par appliquer la pénalité de régularisation: vous soustrayez vraiment (et la constante n'a pas d'importance pour l'optimisation).g(x)=|x|−ccg(x)≤0xcλg(x)λ|x|+λcλc
Les gens profitent souvent de cette «dualité» entre l'optimisation non contrainte et contrainte. Pour un exemple que j'ai pu trouver rapidement sur Google, voir On the LASSO and its dual .
Pourquoi les projections sont-elles importantes ici?
OK, alors pourquoi quelqu'un écrit-il un article sur des projections rapides?
Fondamentalement, une façon d'optimiser les contraintes générales - "maximiser sous réserve de " - est de procéder comme suit:f(x)x∈X
- Prenez n'importe quel algorithme itératif pour une maximisation sans contrainte def(x)
- Commencez avec une suppositionx0
- Faites une étape de l'algorithme:x′0←step(x0)
- ensuite sur l'ensemble : .Xx1←PX(x′0)
- Et répétez jusqu'à convergence.
Par exemple, c'est ainsi que la descente de gradient projetée est dérivée de la descente de gradient ordinaire. Bien sûr, l'optimisation de votre fonction de projection est ici d'une importance vitale.PX
Mettre tous ensemble
Supposons donc que vous vouliez résoudre le LASSO:
argminβ(y−β′X)2+λ||β||1
C'est la version sans contrainte. Par les conditions KKT, l'ajout du terme de régularisation équivaut à contraindre la solution à se trouver dans pour une constante . Mais ce n'est que la de rayon !||β||1≤ccℓ1c
Vous pouvez donc imaginer résoudre ce problème avec une descente (sub) de gradient projetée. * Si vous le , votre fonction serait une projection sur la boule unitaire, et vous voulez faire ça rapidement.PX
* Je ne pense pas que les gens fassent cela, car il existe des moyens plus efficaces. Mais ceux-ci pourraient également utiliser des projections. EDIT: comme le souligne @Dougal, une variante plus sophistiquée de la descente projetée du premier cycle était assez bonne pour écrire un article sur en 2008.