Regularização e de projecção para o

8

Eu estou tentando entender como funciona regularização em termos de projeções em um l bola, e projeção euclidiana para o simplex.

Não sei ao certo o que queremos dizer quando projetamos o vetor de peso nas bolas ou .l 2l1l2

Eu posso entender o conceito de programa de regularização de programática, como em, passamos por cada elemento no vetor de peso e aplicamos onde , levando assim pequenos pesos a 0.l1signum(w) * max(0.0, abs(w) - shrinkageValue)shrinkageValue = regularizationParameter * eta

Acho que estou perdendo um pouco de matemática aqui, então minha pergunta é como traduzimos a projeção do vetor no programa que acabei de descrever? Como a regularização e as projeções vetoriais estão conectadas?

Edit: Estou tentando passar por este artigo Projeções eficientes no - for Learning in High Dimensionsl1

Barra
fonte

Respostas:

11

A regularização e as projeções vetoriais são conectadas através da idéia de otimização restrita e das condições de Karush-Kuhn (sem relação) -Tucker .

Quais são as condições da KKT?

Resumidamente, afirmam que, se é uma solução para o problema "minimize f ( x ) sujeito a g ( x ) 0 ", então x também é uma solução para o problema f ( x ) = λ g ( x ) para alguns escalares λ . Mas isso é equivalente a dizer f ( x ) - λ g ( x ) = 0 , o que significa que xxf(x)g(x)0xf(x)=λg(x)λf(x)λg(x)=0xminimiza o problema de otimização irrestrita "minimize ".f(x)λg(x)

A intuição é que:

  • . Nesse caso, x é uma "solução interior", portanto o gradiente de f deve ser zero nesse ponto. (Se não fosse zero, poderíamos nos mover um pouco nessa direção de x , mantendo g ( x ) < 0 e ter um valor mais alto para f ( x )g(x)<0xfxg(x)<0f(x) . Em seguida, definimos e estamos feito.λ=0

  • Ou . Nesse caso, x está no limite do possível espaço da solução. Localmente, essa aresta se parece com um hiperplano ortogonal ao gradiente g ( x ) , porque a maneira como você mantém a restrição g ( x ) = 0 é não subir nem descer o gradiente. Mas isso significa que a única direção em que o gradiente f poderia apontar é exatamente a mesma direção que gg(x)=0xg(x)g(x)=0fg --se que tinha qualquer componente que era ortogonal para , que pode mover xgxum pouco nessa direção, permaneça no hiperplano ortogonal e aumente f ( x ) .g(x)=0f(x)

Como as condições da KKT explicam a relação entre minimização restrita e regularização

Se para alguma norma e alguma constante c , então a restrição g ( x ) 0 significa que x está em uma esfera de raio c sob essa norma. E na formulação irrestrita, subtrair λ g ( x ) da função que você deseja maximizar é o que acaba aplicando a penalidade de regularização: você está realmente subtraindo λ | x |g(x)=|x|ccg(x)0xcλg(x) (e a constante λλ|x|+λc não importa para otimização).λc

As pessoas geralmente aproveitam essa "dualidade" entre otimização irrestrita e restrita. Para um exemplo que eu pude encontrar rapidamente pesquisando no Google, consulte On the LASSO e seu dual .

Por que as projeções são importantes aqui?

OK, então por que alguém está escrevendo um artigo sobre projeções rápidas?

Basicamente, uma maneira de fazer otimização restrita geral - "maximize sujeito a x f(x) " - é fazer o seguinte:xX

  • Pegue qualquer algoritmo iterativo para maximizar sem restrições a f(x)
  • Comece com um palpite x0
  • Dê um passo do algoritmo: x0step(x0)
  • Em seguida, projete de volta no conjunto : x 1P X ( x 0 ) .Xx1PX(x0)
  • E repita até a convergência.

Por exemplo, é assim que a descida de gradiente projetada é derivada da descida de gradiente comum. Obviamente, otimizar sua função de projeção é de vital importância aqui.PX

Juntando tudo

argminβ(yβX)2+λ||β||1

Essa é a versão irrestrita. Pelas condições do KKT, adicionar o termo de regularização é equivalente a restringir a solução a para alguma constante . Mas isso é apenas a com raio !c 1 c||β||1cc1c

Então você pode imaginar resolver isso com a descida projetada (sub) gradiente. * Se o fizesse, sua função seria uma projeção na bola unitária e você quer fazer isso rápido.PX

* Eu não acho que as pessoas realmente fazem isso, porque existem maneiras mais eficientes. Mas esses podem usar projeções também. EDIT: como aponta @Dougal, uma variante mais sofisticada da descida projetada do subgradiente foi boa o suficiente para escrever um artigo em 2008.

Ben Kuhn
fonte
1
O algoritmo ISTA / FISTA é basicamente a descida projetada (acelerada) do subgradiente, que talvez não seja o algoritmo LASSO mais favorecido, mas é muito bom (e eu acho que era o estado da arte por volta de 2008, quando esse artigo foi publicado).
Dougal
@ Dougal: obrigado pela referência! Eu o editei.
Ben Kuhn