Pourquoi la norme L1 pour les modèles épars

97

Je lis les livres sur la régression linéaire. Il y a quelques phrases sur les normes L1 et L2. Je les connais, mais je ne comprends pas pourquoi la norme L1 pour les modèles clairsemés. Quelqu'un peut utiliser donner une explication simple?

Yongwei Xing
la source
4
Fondamentalement, la rareté est induite par des arêtes vives situées sur l'axe d'une isosurface. La meilleure explication graphique que j'ai trouvée jusqu'ici se trouve dans cette vidéo: youtube.com/watch?v=sO4ZirJh9ds
felipeduque
1
Il y a un article de blog sur le même chioka.in/…
prashanth
Vérifiez le post suivant de moyen. Cela pourrait aider medium.com/@vamsi149/…
solver149

Réponses:

111

Considérons le vecteur où est petit. Les normes et de , respectivement, sont données parε>0l1l2xx=(1,ε)R2ε>0l1l2x

||x||1=1+ε,  ||x||22=1+ε2

Supposons maintenant que, dans le cadre d'une procédure de régularisation, nous allons réduire la magnitude d'un des éléments de de . Si nous changeons en , les normes résultantes sont δεx11-δxδεx11δ

||x(δ,0)||1=1δ+ε,  ||x(δ,0)||22=12δ+δ2+ε2

D’autre part, réduire de donne des normes δx2δ

||x(0,δ)||1=1δ+ε,  ||x(0,δ)||22=12εδ+δ2+ε2

Il convient de noter ici que, pour une pénalité , régulariser le terme plus long entraîne une réduction de la norme beaucoup plus importante que celle au terme plus petit . Pour la pénalité , toutefois, la réduction est la même. Ainsi, lors de la pénalisation d'un modèle utilisant la norme , il est hautement improbable que rien soit jamais mis à zéro, car la réduction de la norme passant de à est presque inexistante lorsque est faible. Par contre, la réduction de la norme est toujours égale àx 1 x 20 l 1 l 2 l 2 ε 0 ε L 1 δl2x1x20l1l2l2ε0εl1δ, quelle que soit la quantité pénalisée.

Une autre façon de penser: ce n'est pas tant que peines encouragent sparsity, mais que pénalités en quelque sorte dissuadent sparsity en cédant des rendements décroissants que les éléments sont déplacés plus près de zéro.l 2l1l2

Bnaul
la source
3
Merci pour votre réponse! Je ne suis pas convaincu par le dernier point, cependant. Si vous exécutez une régression linéaire non pénalisée, vous obtiendrez rarement des solutions éparses (alors que l’ajout d’une pénalité de N1 donnera souvent lieu à une épargne partielle). Ainsi, les pénalités de N1 encouragent effectivement la réduction de la pauvreté en envoyant des coefficients de départ proches de zéro à zéro.
Stefan Wager
2
@StefanWager c'est peut-être un peu exagéré, mais je pense qu'il est vrai que la pénalité n'a rien de spécial ici: une pénalité pour tout induira également la rareté, mais vous les voyez moins souvent dans la pratique (probablement parce qu'ils ne sont pas convexes). Si vous voulez vraiment gagner de l'argent, une pénalité de (proportionnelle au nombre d'entrées non nulles) est la solution, il se trouve que c'est un peu un cauchemar. l α α 1 l 0l1lαα1l0
bnaul
1
Oui c'est correct. Il existe de nombreuses normes qui conduisent à la rareté (par exemple, comme vous l'avez mentionné, toute norme Lp avec p <= 1). En général, toute norme avec un angle pointu à zéro induit la rareté. Donc, pour en revenir à la question initiale - la norme L1 induit la fragmentation en ayant un gradient discontinu à zéro (et toute autre pénalité avec cette propriété le fera aussi).
Stefan Wager
3
Au cas où quelqu'un voudrait en savoir plus, il existe une littérature active sur les fonctions de pénalité non convexes qui sont des alternatives à la norme L1 (par exemple, récemment, papers.nips.cc/paper/… ).
Stefan Wager
1
excellente réponse que je me demandais depuis un moment jusqu'à ce que je trouve cela.
Hady Elsahar
73

Avec un modèle clairsemé, nous pensons à un modèle dont la plupart des pondérations sont égales à 0. Voyons donc pourquoi la régularisation de L1 est plus susceptible de créer des pondérations nulles.

Considérons un modèle composé des poids .(w1,w2,,wm)

Avec la régularisation L1, vous pénalisez le modèle par une fonction de perte =.Σ i | w i |L1(w)Σi|wi|

Avec la régularisation L2, vous pénalisez le modèle par une fonction de perte =1L2(w)12Σiwi2

Si vous utilisez une descente de gradient, vous ferez de manière itérative que les poids changent dans la direction opposée du gradient avec une taille de pas multipliée par le gradient. Cela signifie qu'une pente plus raide nous oblige à faire un pas plus grand, tandis qu'un gradient plus plat nous fait faire un pas plus petit. Regardons les gradients (subgradient en cas de L1):η

dL1(w)dw=sign(w) , oùsign(w)=(w1|w1|,w2|w2|,,wm|wm|)

dL2(w)dw=w

Si nous traçons la fonction de perte et sa dérivée pour un modèle composé d'un seul paramètre, cela ressemble à ceci pour L1:

entrez la description de l'image ici

Et comme ça pour L2:

entrez la description de l'image ici

Notez que pour , le gradient est 1 ou -1, sauf lorsque . Cela signifie que la régularisation L1 déplacera n'importe quel poids vers 0 avec la même taille de pas, quelle que soit la valeur du poids. En revanche, vous pouvez voir que le gradient décroît linéairement vers 0 lorsque le poids se rapproche de 0. Par conséquent, la régularisation de L2 déplace également le poids vers 0, mais il prendra des étapes de plus en plus petites à mesure qu'un poids s'approche de 0.L1w1=0L2

Essayez d'imaginer que vous commenciez avec un modèle avec et en utilisant . Dans l'image suivante, vous pouvez voir comment la descente de gradient avec la régularisation L1 fait 10 des mises à jour , jusqu'à atteindre un modèle avec :w1=5η=12w1:=w1ηdL1(w)dw=w1121w1=0

entrez la description de l'image ici

En revanche, avec la régularisation L2 où , le dégradé est , ce qui fait que chaque étape n’est que la moitié de 0. C’est-à-dire que nous effectuons la mise à jour Par conséquent, le modèle n'atteint jamais un poids 0, quel que soit le nombre d'étapes effectuées:η=12w1w1:=w1ηdL2(w)dw=w112w1

entrez la description de l'image ici

Notez que la régularisation L2 peut faire en sorte qu'un poids atteigne zéro si la taille de pas est si élevée qu'elle atteint zéro en une seule étape. Même si la régularisation L2 seule dépasse ou dépasse 0, elle peut toujours atteindre un poids de 0 lorsqu'elle est utilisée avec une fonction objectif qui tente de minimiser l'erreur du modèle par rapport aux poids. Dans ce cas, trouver les meilleurs poids du modèle est un compromis entre régulariser (avoir des poids faibles) et minimiser les pertes (ajuster les données de formation), et le résultat de ce compromis peut être que le meilleur rapport qualité-prix pour certains poids sont 0.η

Kent Munthe Caspersen
la source
3
Quelqu'un pourrait-il m'expliquer pourquoi nous n'allons pas dans une boucle infinie lorsque nous prenons le poids de départ w1 = 5.1 au lieu de 5. Soit w = 0.1, w> 0, notre dérivée partielle est égale à 1 puis prend la deuxième étape, maintenant w <0 => dérivé = -1:Nous allons donc sans fin osciller près de 0.
η=0.5
wfirst step=0.10.5(+1)=>w=0.4
wsecondstep=0.40.5(1)=0.1.
Alex Yashin
5
@AlexYashin c'est exact - si nous ne mettions à jour que les poids basés sur la régularisation de L1, nous pourrions finir par avoir des poids qui oscillent près de 0. Mais nous n'utilisons jamais la régularisation seule pour les ajuster. Nous utilisons la régularisation en combinaison avec l'optimisation d'une fonction de perte. De cette manière, la régularisation pousse les poids vers zéro tout en essayant de les pousser à une valeur qui optimise les prévisions. Un deuxième aspect est le taux d'apprentissage. Avec un taux d'apprentissage plus faible, nous pouvons nous approcher de la valeur telle que la régularisation peut osciller autour de telle sorte que nous pouvons la négliger
Kent Munthe Caspersen
1
Pourquoi le dL2(w)/dw'module' et pas seulement linéaire?
mrgloom
1
@mrgloom dL2(w)/dwpeut être lu comme le changement de L2(w)poids. Depuis que la régularisation L2 place les poids, L2(w)changera beaucoup plus pour le même changement de poids lorsque nous avons des poids plus élevés. C'est pourquoi la fonction est convexe lorsque vous la tracez. Cependant, pour L1, le changement de L1(w)changement de poids est le même quel que soit votre poids - cela conduit à une fonction linéaire.
Kent Munthe Caspersen le
1
@KentMuntheCaspersen Incroyable explication! Merci pour les graphiques et les efforts que vous avez investis pour rendre cela intuitif!
Layser
15

La figure 3.11 tirée de Eléments d'apprentissage statistique de Hastie, Tibshirani et Friedman est très illustrative:entrez la description de l'image ici

Explications: est l'estimation des moindres carrés sans contrainte. Les ellipses rouges sont (comme expliqué dans la légende de cette figure) les contours de la fonction d'erreur des moindres carrés, en termes de paramètres et . Sans contrainte, la fonction d'erreur est minimisée au niveau de MLE et sa valeur augmente à mesure que les ellipses rouges se développent. Les régions de losange et de disque sont des régions possibles pour la régression par lasso ( ) et la régression par arête ( ), respectivement. Heuristiquement, pour chaque méthode, nous recherchons l'intersection des ellipses rouges et de la région bleue, l'objectif étant de minimiser la fonction d'erreur tout en maintenant la faisabilité.β^β1β2β^L1L2

Cela dit, il est clair que la contrainte , qui correspond à la région diamantable, est plus susceptible de produire une intersection dont l'un des composants de la solution est zéro (c'est-à-dire le modèle clairsemé) en raison des propriétés géométriques. des ellipses, des disques et des diamants. C'est simplement parce que les diamants ont des coins (dont une composante est zéro) qui sont plus faciles à intersecter avec les ellipses qui s'étendent en diagonale.L1

Zhanxiong
la source
16
L'illustration n'est pas très convaincante sans informations supplémentaires. Par exemple, pourquoi les contours de l'erreur devraient-ils être situés là où ils se trouvent sur la figure?
Wabbit
@HrishikeshGanu Finalement, j'ai eu le temps de modifier le message.
Zhanxiong
Tous les contours auront la même forme ...
kjetil b halvorsen
1
Notez que les bords avec L1 ne sont préférés que lorsque a des variances différentes sur les et . En d’autres termes, lorsque la distribution de la ligne rouge n’est pas symétrique sur l’ axe diagonal . S'il est symétrique, alors tout le bord a la même distance / valeur / coût. β^β1β2β1=β2
Tautvydas
13

Jetez un coup d’œil à la figure 3.11 (page 71) du document Les éléments de l’apprentissage statistique . Il montre la position d'une contrainte qui minimise la fonction d'erreur au carré, les ellipses montrant les niveaux de la fonction d'erreur quadratique, et où sont le soumis à des contraintes et .β^β^1(β^)<t2(β^)<t

Cela vous permettra de comprendre très géométriquement que sous la contrainte , vous obtenez des composants nuls. Ceci est essentiellement dû au fait que la balle a des "arêtes" sur les axes.11{x:1(x)1}

Plus généralement, ce livre est une bonne référence sur ce sujet: à la fois rigoureux et bien illustré, de bonnes explications.

Elvis
la source
3
Je pense que votre deuxième paragraphe est une clé ... du moins pour mon intuition: une "boule" l1 ressemble plus à un diamant spikey le long des axes, ce qui signifie qu'un hyperplan contraint de la frapper a plus de chances de donner un zéro les axes.
Wayne
2
Oui, j’imaginais le processus d’optimisation comme le mouvement d’un point soumis à deux forces: attraction vers le non contraint grâce à la fonction d’erreur quadratique, attraction vers 0 due à la ou . Ici, la "géométrie" de cette force d'attraction modifie le comportement du point. Si vous une petite ou dans laquelle elle peut se déplacer librement, elle glissera sur le bord de la balle pour se rapprocher de . Le résultat est indiqué sur l'illustration dans le livre mentionné précédemment ...β^1212β^
Elvis
3
Le livre est bon, mais il n’explique jamais d’où il vient ni les calculs derrière ce calcul.
user13985
2

Une réponse simple, non mathématique, serait:

Pour L2: le terme de pénalité est carré , donc une petite valeur la réduira. Nous n'avons pas besoin de le rendre nul pour atteindre notre objectif d'obtenir une erreur carrée minimale, nous l'obtiendrons avant.

Pour L1: le terme de pénalité est absolu , il peut être nécessaire d’ aller à zéro car il n’existe pas de catalyseur pour réduire le plus petit .

C'est mon point de vue.

Arnab Mukherjee
la source
Pas très convaincant pour moi.
Tyler vendredi
2

L1 Norm vs L2 Norm

L'image montre les formes de l'aire occupée par la norme L1 et L2. La seconde image consiste en divers contours de gradient de descente pour divers problèmes de régression. Dans tous les graphiques de contour, observez le cercle rouge qui coupe la crête ou la norme L2. l'intersection n'est pas sur les axes. Le cercle noir dans tous les contours représente celui qui intersecte la norme L1 ou le lasso. Il se croise relativement près des axes. Cela se traduit par la création de coefficients à 0 et donc par la sélection des caractéristiques. Par conséquent, la norme L1 rend le modèle clairsemé.

Explication plus détaillée en cliquant sur le lien suivant: Cliquez sur Poster sur Towards Data Science

résolveur149
la source
C'est une bonne explication, mais des commentaires supplémentaires sur l'expression des exemples de fonctions de coût seraient également utiles. C'est-à-dire que la forme circulaire de -norm erreurs semble intuitive, cependant, la forme étroite-allongée (utilisée dans la plupart des autres exemples) ne semble pas triviale et ne va pas de soi. (Ici, je parle de la fonction de coût en haut à gauche sur la figure 8 (b): pourquoi sa direction principale est-elle orientée vers le point, et non, par exemple, ? Les contours seraient différent, et le point de minimisation ne serait pas à 0!)β 1 = 1 β 1 = 0 L 12β1=1β1=0L1
Nutle