Por que a norma L1 para modelos esparsos

97

Estou lendo os livros sobre regressão linear. Existem algumas frases sobre a norma L1 e L2. Eu os conheço, só não entendo por que a norma L1 para modelos esparsos. Alguém pode dar uma explicação simples?

Yongwei Xing
fonte
4
Basicamente, a escarsidade é induzida por arestas vivas no eixo de uma superfície isosuperficial. A melhor explicação gráfica que eu encontrei até agora é neste vídeo: youtube.com/watch?v=sO4ZirJh9ds
felipeduque
1
Existe um artigo de blog sobre o mesmo chioka.in/…
prashanth
Verifique a seguinte postagem do Medium. Pode ajudar medium.com/@vamsi149/…
solver149

Respostas:

111

Considere o vector onde ε > 0 é pequena. As normas l 1 e l 2 de x , respectivamente, são dadas porx=(1,ε)R2ε>0l1l2x

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

Agora diga que, como parte de algum procedimento de regularização, vamos reduzir a magnitude de um dos elementos de em δ ε . Se mudarmos x 1 para 1 - δ , as normas resultantes sãoxδεx11δ

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

Por outro lado, reduzir por δ fornece normasx2δ

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

O que se deve notar aqui é que, para uma penalidade de , regularizar o termo maior x 1 resulta em uma redução muito maior na norma do que fazê-lo no termo menor x 20 . Para a penalidade de l 1 , no entanto, a redução é a mesma. Assim, ao penalizar um modelo usando a norma l 2 , é altamente improvável que algo seja definido como zero, uma vez que a redução na norma l 2 que vai de ε a 0 é quase inexistente quando ε é pequeno. Por outro lado, a redução em l 1l2x1x20l1l2l2ε0εl1A norma é sempre igual a , independentemente da quantidade que está sendo penalizada.δ

Outra maneira de pensar sobre isso: não é tanto que penalidades incentivam a esparsidade, mas que l 2 penalizações desencorajam a esparsidade, produzindo retornos decrescentes à medida que os elementos são movidos para mais perto de zero.l1l2

bnaul
fonte
3
Obrigado pela sua resposta! Eu não estou convencido pelo último ponto, no entanto. Se você executar uma regressão linear não penalizada, dificilmente obterá soluções esparsas (ao passo que a adição de uma penalidade L1 geralmente gera escassez). Portanto, as penalidades de L1 realmente incentivam a esparsidade, enviando coeficientes que começam exatamente de zero a zero.
Stefan Wager
2
@StefanWager talvez seja um exagero, mas acho que é verdade que não há nada de especial na penalidade aqui: uma penalidade l α para qualquer α 1 também induz a escarsidade, mas você as vê com menos frequência na prática ( provavelmente porque não são convexos). Se você realmente quer apenas sparsity em seguida, um l 0 penalidade (proporcional ao número de entradas diferentes de zero) é o caminho a percorrer, isso só acontece que é um pouco de um pesadelo para trabalhar. l1lαα1eu0 0
bnaul
1
Sim esta correto. Existem muitas normas que levam à esparsidade (por exemplo, como você mencionou, qualquer norma Lp com p <= 1). Em geral, qualquer norma com um canto agudo em zero induz escarsidade. Então, voltando à pergunta original - a norma L1 induz a escarsidade tendo um gradiente descontínuo em zero (e qualquer outra penalidade com essa propriedade também o fará).
Stefan Wager
3
Caso alguém queira ler mais, há uma literatura ativa sobre funções de penalidade não convexa que são alternativas à norma L1 (por exemplo, recentemente, papers.nips.cc/paper/… ).
Stefan Wager,
1
ótima resposta eu estive pensando por um tempo até que eu encontrei isso.
Hady Elsahar
73

Com um modelo esparso, pensamos em um modelo em que muitos pesos são 0. Vamos, portanto, raciocinar sobre como a regularização de L1 tem maior probabilidade de criar pesos-zero.

Considere um modelo que consiste nos pesos .(W1,W2,...,Wm)

Com a regularização L1, você penaliza o modelo por uma função de perda = Σ i | w i | .eu1(W)ΣEu|WEu|

Com a regularização L2, você penaliza o modelo por uma função de perda = 1eu2(W)12ΣEuWEu2

Se você estiver usando a descida do gradiente, iterativamente, os pesos serão alterados na direção oposta do gradiente com um tamanho de passo multiplicado pelo gradiente. Isso significa que um gradiente mais acentuado nos fará dar um passo maior, enquanto um gradiente mais plano nos fará dar um passo menor. Vejamos os gradientes (subgradiente no caso de L1):η

, ondesign(w)=(w1deu1(W)dW=sEugn(W)sEugn(W)=(W1|W1|,W2|W2|,...,Wm|Wm|)

deu2(W)dW=W

Se traçarmos a função de perda e sua derivada para um modelo que consiste em apenas um único parâmetro, será assim para L1:

insira a descrição da imagem aqui

E assim para L2:

insira a descrição da imagem aqui

Observe que para , o gradiente é 1 ou -1, exceto quando w 1 = 0 . Isso significa que a regularização L1 moverá qualquer peso para 0 com o mesmo tamanho de etapa, independentemente do valor do peso. Por outro lado, você pode ver que o gradiente de L 2 está diminuindo linearmente em direção a 0 conforme o peso vai para 0. Portanto, a regularização de L2 também moverá qualquer peso em direção a 0, mas tomará etapas cada vez menores à medida que o peso se aproxima de 0.eu1W1=0 0eu2

Tente imaginar que você começa com um modelo com e usando η = 1W1=5 . Na figura a seguir, é possível ver como a descida do gradiente usando a regularização L1 faz 10 das atualizaçõesw1:=w1-ηdL1(w)η=12, até atingir um modelo comw1=0:W1: =W1-ηdeu1(W)dW=W1-121W1=0 0

insira a descrição da imagem aqui

Em contraste, com regularização L2 onde , o gradiente éw1, fazendo com que cada passo seja apenas na metade do caminho para 0. Ou seja, fazemos a atualizaçãow1:=w1-ηdL2(w)η=12W1 Portanto, o modelo nunca atinge um peso 0, independentemente de quantas etapas executar:W1: =W1-ηdeu2(W)dW=W1-12W1

insira a descrição da imagem aqui

Observe que a regularização L2 pode fazer um peso chegar a zero se o tamanho da etapa for tão alto que chega a zero em uma única etapa. Mesmo se a regularização L2 por conta própria exceder ou ultrapassar 0, ele ainda poderá atingir um peso 0 quando usado em conjunto com uma função objetivo que tenta minimizar o erro do modelo em relação aos pesos. Nesse caso, encontrar os melhores pesos do modelo é um compromisso entre regularizar (com pesos pequenos) e minimizar as perdas (ajustar os dados de treinamento), e o resultado desse compromisso pode ser o melhor valor para alguns pesos são 0.η

Kent Munthe Caspersen
fonte
3
η=0,5
WfEurst step=0,1-0,5(+1)=>W=-0,4
Wsecondstep=-0,4-0,5(-1)=0.1
5
@ Alexyashin está correto - se apenas atualizarmos os pesos com base na regularização L1, poderemos acabar tendo pesos que oscilam perto de 0. Mas nunca usamos a regularização sozinha para ajustar os pesos. Usamos a regularização em combinação com a otimização de uma função de perda. Dessa forma, a regularização empurra os pesos para zero, enquanto tentamos empurrar os pesos para um valor que otimiza as previsões. Um segundo aspecto é a taxa de aprendizado. Com uma taxa de aprendizagem menor, podemos chegar tão perto do valor que a regularização pode oscilar em torno de que podemos negligenciá-lo
Kent Munthe Caspersen
1
Por que dL2(w)/dw'módulo' e não apenas linear?
precisa saber é o seguinte
1
@mrgloom dL2(w)/dwpode ser lido como a mudança de L2(w)peso por mudança. Como a regularização L2 quadratura os pesos, L2(w)mudará muito mais para a mesma mudança de pesos quando tivermos pesos mais altos. É por isso que a função é convexa quando você a plota. Para L1, no entanto, a alteração de L1(w)cada alteração de pesos é a mesma, independentemente de quais sejam seus pesos - isso leva a uma função linear.
Kent Munthe Caspersen
1
@KentMuntheCaspersen Amazing explicação! Obrigado pelos gráficos e pelo esforço que você investiu para tornar isso intuitivo!
Layser # 10/18
15

A Figura 3.11 de Elements of Statistical Learning de Hastie, Tibshirani e Friedman é muito ilustrativa:insira a descrição da imagem aqui

β^β1β2β^eu1eu2) regressão, respectivamente. Heuristicamente, para cada método, procuramos a interseção das elipses vermelhas e da região azul, pois o objetivo é minimizar a função de erro, mantendo a viabilidade.

eu1

Zhanxiong
fonte
16
A ilustração não é muito convincente sem informações adicionais. Por exemplo, por que os contornos do erro devem estar localizados onde estão na figura?
Wabbit #
@HrishikeshGanu Eventualmente, tenho algum tempo para editar a postagem.
Zhanxiong
Todos os contornos terá a mesma forma ...
Kjetil b Halvorsen
1
β^β1β2β1=β2
13

β^β^1(β^)<t2(β^)<t

11{x:1(x)1}

De maneira mais geral, este livro é uma boa referência sobre esse assunto: tanto rigorosas quanto bem ilustradas, ótimas explicações.

Elvis
fonte
3
Eu acho que o seu segundo parágrafo é a chave ... pelo menos para a minha intuição: uma "bola" l1 é mais como um diamante que é espigado ao longo dos eixos, o que significa que um hiperplano obrigado a atingi-lo tem mais chances de ter um zero os eixos.
Wayne
2
β^1212β^
Elvis
3
O livro é bom, mas nunca explica de onde veio e a matemática por trás dele.
user13985
2

Uma resposta não matemática simples será:

Para L2: o termo de penalidade é quadrado , portanto, ao quadrado um valor pequeno o tornará menor. Não precisamos zerá-lo para atingir nosso objetivo de obter um erro quadrado mínimo, vamos obtê-lo antes disso.

Para L1: termo Penalty é absoluta , que pode necessário ir a zero, pois não há catalisador para diminuir o tamanho .

Este é o meu ponto de vista.

Arnab Mukherjee
fonte
Não é muito convincente para mim.
Tyler #
2

L2 Norm vs L2 Norm

A imagem mostra as formas da área ocupada pelas normas L1 e L2. A segunda imagem consiste em vários contornos de descida de gradiente para vários problemas de regressão. Em todas as plotagens de contorno, observe o círculo vermelho que cruza a Norma Ridge ou L2. a interseção não está nos eixos. O círculo preto em todos os contornos representa aquele que intercepta a norma L1 ou Lasso. Cruza-se relativamente próximo dos eixos. Isso resulta em fazer coeficientes para 0 e, portanto, na seleção de recursos. Portanto, a norma L1 torna o modelo escasso.

Explicação mais detalhada no seguinte link: Clique em Postar em direção à ciência de dados

solver149
fonte
2β1=1β1=0 0eu1