Pourquoi ne voit-on que les régularisations

36

Je suis juste curieux de savoir pourquoi il n’ya habituellement que des régularisations des normes L1 et L2 . Y a-t-il des preuves de la raison pour laquelle elles sont meilleures?

utilisateur10024395
la source
13
(+1) Je n'ai pas enquêté spécifiquement sur cette question, mais l'expérience de situations similaires suggère qu'il peut exister une bonne réponse qualitative: toutes les normes qui sont différenciées en second à l'origine seront localement équivalentes les unes aux autres, dont la norme L2 est la norme. Toutes les autres normes ne seront pas différenciables à l'origine et L1 reproduira qualitativement leur comportement. Cela couvre toute la gamme. En effet, une combinaison linéaire d'une norme L1 et L2 rapproche chaque norme du second ordre à l'origine - et c'est ce qui importe le plus dans la régression sans résidus éloignés.
whuber
3
Oui: c'est essentiellement le théorème de Taylor.
whuber
4
La prémisse de la question est fausse: d'autres normales sont utilisées, bien que beaucoup moins courantes. p
Firebug
3
La combinaison linéaire mentionnée par @whuber est souvent appelée le filet élastique .
Luca Citi
4
En outre, parmi les normes Lp, obtient aussi beaucoup de kilométrage. L
user795305

Réponses:

28

En plus des commentaires de @ whuber (*).

Le livre de Hastie et al ., Apprentissage statistique avec Sparsity, aborde ce sujet. Ils utilisent également ce qu'on appelle le L0 "norme" (guillemets car ce n'est pas une norme au sens mathématique strict (**)), qui compte simplement le nombre de composantes non nulles d'un vecteur.

En ce sens, la norme est utilisée pour la sélection de variables, mais, avec les normes l q avec q < 1, elle n’est pas convexe et est donc difficile à optimiser. Ils affirment (un argument que je pense proviennent de Donohoe dans la détection comprimée) que la norme L 1 , c’est-à-dire le lasso, est la meilleure convexification de la "norme" de L 0 ("le relâchement convexe le plus proche de la meilleure sélection de sous-ensembles"). Ce livre fait également référence à certaines utilisations d’autres normes L q . L'unité balle dans le l q -norm avec q < 1 ressemble à ceciL0lqq<1L1L0Lqlqq<1

enter image description here

(image de wikipedia) alors qu'une explication imagée de la raison pour laquelle le lasso peut fournir une sélection variable est

enter image description here

Cette image provient du livre référencé ci-dessus. Vous pouvez voir que dans le cas du lasso (la boule unitaire dessinée comme un diamant), il est beaucoup plus probable que les contours ellipsoïdaux (somme des carrés) touchent d’abord le diamant à l’un des coins. Dans le cas non convexe (première boule), il est encore plus probable que le premier contact entre l'ellipsoïde et la boule unitaire se fera à l'un des coins, de sorte que la casse mettra davantage l'accent sur la sélection variable que sur le lasso.

Si vous essayez ce "lasso avec pénalité non convexe" dans google, vous obtiendrez un grand nombre de documents faisant des problèmes de type lasso avec pénalité non convexe comme avec q < 1 .lqq<1

(*) Pour être complet, je copie ici les commentaires de whuber:

Je n’ai pas étudié cette question spécifiquement, mais l’expérience de situations similaires suggère une bonne réponse qualitative: toutes les normes qui sont ensuite différenciables à l’origine seront localement équivalentes les unes aux autres, la norme étant la norme. Toutes les autres normes ne seront pas différenciables à l'origine et L 1 reproduira qualitativement leur comportement. Cela couvre toute la gamme. En effet, une combinaison linéaire d'une norme L 1 et L 2 rapproche chaque norme du second ordre à l'origine - et c'est ce qui importe le plus dans la régression sans résidus éloignés.L2L1L1L2

(**) La - "norme" manque d'homogénéité, ce qui est l'un des axiomes de la norme. Des moyens d'homogénéité pour α 0 qui α x = α x .l0α0αx=αx

kjetil b halvorsen
la source
1
@kjetilbhalvorsen Merci pour votre réponse profonde. J'ai choisi l'incroyable indice en exposant afin d'être cohérent avec la question et le titre. Bien sûr, vous pouvez l'écrire comme vous préférez.
Ferdi
@kjetilbhalvorsen Pouvez-vous développer un peu le commentaire de Whuber? Il est bien connu que la norme n’est pas différentiable à l’origine (considérons x | x | , par exemple). On ne voit pas non plus ce que l’on entend par «équivalence locale» des normes. Des références sont nécessaires pour le moins. L2x|x|
Olivier
@Olivier Le -norme est différentiables à l'origine, vous pensez à la 1 -norme. 21
Firebug
@Firebug No. Je pense à la norme en 1 dimension, qui est la même que la norme L 1 . Est-ce que je manque quelque chose? L2L1
Olivier
2
@ Olivier Oh, vous avez raison. J'ai mal compris, parce que le carré -norme est effectivement utilisé, et il est partout différentiables. 2
Firebug
12

Je pense que la réponse à la question dépend beaucoup de la définition que vous donnez à "meilleur". Si je comprends bien, vous voulez savoir pourquoi ces normes apparaissent si souvent par rapport à d’autres options. Dans ce cas, la réponse est la simplicité. L'intuition derrière la régularisation est que j'ai un vecteur, et j'aimerais que ce vecteur soit "petit" dans un sens. Comment décrivez-vous la taille d'un vecteur? Eh bien, vous avez le choix:

  • Comptez-vous le nombre d’éléments qu’elle contient ?(L0)
  • Ajoutez-vous tous les éléments ?(L1)
  • Mesurez-vous la longueur de la "flèche" ?(L2)
  • Utilisez-vous la taille du plus grand élément (L) ?

Vous pouvez employer des normes alternatives comme L3 , mais elles n’ont pas d’interprétation physique et conviviale comme celles décrites ci-dessus.

Dans cette liste, la norme offre des solutions analytiques intéressantes, telles que les problèmes des moindres carrés. Avant, vous disposiez d'une puissance de calcul illimitée, vous ne pourriez pas faire beaucoup mieux autrement. Je supposerais que le visuel "longueur de la flèche" est également plus attrayant pour les gens que d'autres mesures de taille. Même si la norme que vous choisissez pour la régularisation a une incidence sur les types de résidus que vous obtenez avec une solution optimale, je ne pense pas que la plupart des gens sont a) conscients de cela, ou b) y réfléchissent profondément lors de la formulation de leur problème. À ce stade, la plupart des gens continuent à utiliser la L 2L2L2 parce que c'est "ce que tout le monde fait".

Une analogie serait la fonction exponentielle, ex - elle apparaît littéralement partout dans la physique, l’économie, les statistiques, l’apprentissage automatique ou tout autre domaine axé sur les mathématiques. Je me demandais depuis toujours pourquoi toutes les choses dans la vie semblaient être décrites par des exponentielles, jusqu'à ce que je réalise que nous, les humains, n'avons pas beaucoup de trucs dans notre manche. Les exponentielles ont des propriétés très utiles pour faire de l’algèbre et du calcul. Elles finissent donc par être la fonction n ° 1 de la boîte à outils de tout mathématicien lorsqu’on essaie de modéliser quelque chose dans le monde réel. Il se peut que des choses comme le temps de décohérence soient "mieux" décrites par un polynôme d’ordre élevé, mais celles-ci sont relativement plus difficiles à faire en algèbre,

Sinon, le choix de la norme a des effets très subjectifs et il vous appartient, en tant que personne qui énonce le problème, de définir ce que vous préférez dans une solution optimale. Souhaitez-vous plus que tous les composants de votre vecteur de solution soient de magnitude similaire ou que la taille du composant le plus grand soit aussi petite que possible? Ce choix dépendra du problème spécifique que vous résolvez.

Panda rouge
la source
10

L1L2L1

L2nUNEX-b2+ΓX2L2

L0Lp norme, la Lnorme a également appelé la norme uniforme .

Carl
la source