Por que a gente só vê e regularização, mas não outras normas?

36

Estou curioso para por que geralmente há apenas regularização de normas e . Existem provas de por que estas são melhores?L 2L1L2

user10024395
fonte
13
(+1) Não investiguei essa questão especificamente, mas a experiência com situações semelhantes sugere que pode haver uma boa resposta qualitativa: todas as normas que são segundo diferenciáveis ​​na origem serão localmente equivalentes entre si, das quais as norma é o padrão. Todas as outras normas não serão diferenciáveis ​​na origem e reproduz qualitativamente seu comportamento. Isso abrange toda a gama. De fato, uma combinação linear de uma norma e aproxima de qualquer norma de segunda ordem na origem - e é isso que mais importa na regressão sem resíduos externos. L 1 L 1 L 2L2L1L1L2
whuber
3
Sim: este é essencialmente o teorema de Taylor.
whuber
4
A premissa da pergunta é falsa: outras -norms são usadas, embora muito menos comuns. p
Firebug 25/03
3
A combinação linear mencionada pelo @whuber é freqüentemente chamada de rede elástica .
Luca Citi
4
Além disso, entre as normas Lp, também recebe muita quilometragem. L
user795305

Respostas:

28

Além dos comentários do @ whuber (*).

O livro de Hastie et al. Aprendizado estatístico com Sparsity discute isso. Eles também usam o que é chamado de "norma" (aspas porque essa não é uma norma no sentido matemático estrito (**)), que simplesmente conta o número de componentes diferentes de zero de um vetor.L0

Nesse sentido, a norma é usada para seleção de variáveis, mas, juntamente com as normas com não é convexa, sendo difícil de otimizar. Eles argumentam (um argumento que acho que vem de Donohoe no sensor comprimido) que a norma , ou seja, o laço, é a melhor convexificação da "norma" ("o relaxamento convexo mais próximo da melhor seleção de subconjunto"). Esse livro também faz referência a alguns usos de outras normas . A bola unitária na -norm com parece com issol q q < 1 L 1 L 0 L q l q q q < 1L0lqq<1L1L0Lqlqq<1

insira a descrição da imagem aqui

(imagem da wikipedia), enquanto uma explicação pictórica de por que o laço pode fornecer seleção de variáveis ​​é

insira a descrição da imagem aqui

Esta imagem é do livro mencionado acima. Você pode ver que, no caso do laço (a bola unitária desenhada como um diamante), é muito mais provável que os contornos elipsoidais (soma dos quadrados) tocem primeiro o diamante em um dos cantos. No caso não convexo (figura da primeira bola unitária), é ainda mais provável que o primeiro toque entre o elipsóide e a bola unitária esteja em um dos cantos, de modo que o caso enfatize a seleção de variáveis ​​ainda mais que o laço.

Se você tentar esse "laço com penalidade não convexa" no google, você receberá muitos trabalhos com problemas semelhantes ao laço com penalidade não convexa, como com . q < 1lqq<1

(*) Para completar, copio aqui os comentários da whuber:

Não investiguei essa questão especificamente, mas a experiência com situações semelhantes sugere que pode haver uma boa resposta qualitativa: todas as normas que são segundo diferenciáveis ​​na origem serão localmente equivalentes entre si, das quais a norma é o padrão. Todas as outras normas não serão diferenciáveis ​​na origem e reproduz qualitativamente seu comportamento. Isso abrange toda a gama. Com efeito, uma combinação linear de um e norma aproxima qualquer norma de segunda ordem na origem - e isso é o que mais importa na regressão sem resíduos periféricas.L 1 L 1 L 2L2L1L1L2

(**) O - "norma" não possui homogeneidade, que é um dos axiomas para as normas. Homogeneidade significa para que. α 0 " α x " = α " x "l0α0αx=αx

kjetil b halvorsen
fonte
1
@kjetilbhalvorsen Obrigado por sua resposta profunda. Eu escolhi o sobrescrito incomum para ser consistente com a pergunta e o título. Claro que você pode escrever da maneira que preferir.
Ferdi 25/03
@kjetilbhalvorsen Você pode expandir um pouco o comentário de Whuber? É sabido que a norma não é diferenciável na origem (considere , por exemplo). Também não está claro o que se entende por 'equivalência local' de normas. Referências são necessárias, para dizer o mínimo. x | x |L2x|x|
26717 Olivier
@ Olivier O -norm é diferenciável na origem, você está pensando sobre o -norm. 121
Firebug 27/03
@ Firebug No. Estou pensando na norma em 1 dimensão, que é igual à norma . Estou esquecendo de algo? L 1L2L1
Olivier
2
@ Olivier Oh, você está realmente certo. Eu errado , porque o quadrado -norm é realmente usado e é diferenciável em todos os lugares. 2
Firebug 27/03
12

Eu acho que a resposta para a pergunta depende muito de como você define "melhor". Se estou interpretando bem, você quer saber por que essas normas aparecem com tanta frequência em comparação com outras opções. Nesse caso, a resposta é simplicidade. A intuição por trás da regularização é que eu tenho algum vetor e gostaria que esse vetor fosse "pequeno" em algum sentido. Como você descreve o tamanho de um vetor? Bem, você tem opções:

  • Você conta quantos elementos ele possui ?(L0)
  • Você soma todos os elementos ?(L1)
  • Você mede quanto tempo "a" flecha é ?(L2)
  • Você usa o tamanho do elemento maior ?(L)

Você pode empregar normas alternativas como , mas elas não têm interpretações físicas amigáveis ​​como as acima.L3

Dentro dessa lista, a norma apresenta soluções analíticas agradáveis ​​de forma fechada para problemas como mínimos quadrados. Antes que você tivesse poder computacional ilimitado, não seria possível avançar muito de outra maneira. Eu especularia que o visual do "comprimento da flecha" também é mais atraente para as pessoas do que outras medidas de tamanho. Embora a norma escolhida para a regularização tenha impacto nos tipos de resíduos obtidos com uma solução ideal, não acho que a maioria das pessoas a) esteja ciente disso ou b) considere isso profundamente ao formular seu problema. Neste ponto, espero que a maioria das pessoas continue usando porque é "o que todos fazem".L 2L2L2

Uma analogia seria a função exponencial, - isso aparece literalmente em toda parte na física, economia, estatísticas, aprendizado de máquina ou qualquer outro campo matematicamente orientado. Sempre me perguntei por que tudo na vida parecia ser descrito por exponenciais, até que percebi que nós, humanos, simplesmente não temos muitos truques na manga. Os exponenciais têm propriedades muito úteis para fazer álgebra e cálculo e, portanto, acabam sendo a principal função na caixa de ferramentas de qualquer matemático ao tentar modelar algo no mundo real. Pode ser que coisas como tempo de descoerência sejam "melhores" descritas por um polinômio de alta ordem, mas essas são relativamente mais difíceis de fazer álgebra e, no final do dia, o que importa é que sua empresa está lucrando - o exponencial é mais simples e bom o suficiente.ex

Caso contrário, a escolha da norma terá efeitos muito subjetivos, e cabe a você, como pessoa que indica o problema, definir o que você prefere em uma solução ideal. Você se importa mais com o fato de todos os componentes em seu vetor de solução serem similares em magnitude ou com o tamanho do maior componente o menor possível? Essa escolha dependerá do problema específico que você está resolvendo.

Panda vermelho
fonte
10

A principal razão para ver principalmente e normas é que eles cobrem a maioria das aplicações atuais. Por exemplo, a norma também chamada de norma de táxi , uma norma de conexão reticulada em rede, inclui a norma de valor absoluto . L 2 L 1L1L2L1

nUm x - b 2 + Γ x 2 L 2L2 normas são, além dos mínimos quadrados, as distâncias euclidianas no espaçon , bem como a norma variável complexa . Além disso, a regularização de Tikhonov e a regressão de cume , ou seja, aplicativos que minimizam , são frequentemente consideradas normas .Axb2+Γx2L2

A Wikipedia fornece informações sobre essas e outras normas . Vale mencionar . A norma generalizada , a norma também denominada norma uniforme .L0L LpL

Carl
fonte