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

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 $l_1$$l_2$

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.$l_1$signum(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 Dimensions$l_1$

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 $x$$f(x)$$g(x) \le 0$$x$$\nabla f(x) = \lambda \nabla g(x)$$\lambda$$\nabla f(x) - \lambda \nabla g(x) = 0$$x$minimiza o problema de otimização irrestrita "minimize ".$f(x) - \lambda 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) < 0$$x$$f$$x$$g(x) < 0$$f(x)$ . Em seguida, definimos e estamos feito.$\lambda = 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 ∇ $g(x) = 0$$x$$\nabla g(x)$$g(x) = 0$$\nabla f$$\nabla g$ --se que tinha qualquer componente que era ortogonal para , que pode mover $\nabla g$$x$um pouco nessa direção, permaneça no hiperplano ortogonal e aumente f ( x ) .$g(x) = 0$$f(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| - c$$c$$g(x) \le 0$$x$$c$$\lambda g(x)$ (e a constante$\lambda |x| + \lambda c$ não importa para otimização).$\lambda 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:$x \in X$

• Pegue qualquer algoritmo iterativo para maximizar sem restrições a $f(x)$
• Comece com um palpite $x_0$
• Dê um passo do algoritmo: $x_0^\prime \leftarrow step(x_0)$
• Em seguida, projete de volta no conjunto : x 1 ← P X ( x ′ 0 ) .$X$$x_1 \leftarrow P_X(x_0^\prime)$
• 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.$P_X$

Juntando tudo

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$||\beta||_1 \le c$$c$$\ell_1$$c$

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.$P_X$

* 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.