Regularização indutora de escassez para matrizes estocásticas

10

É bem sabido (por exemplo, no campo do sensoriamento compressivo) que a norma é "indutora de dispersão", no sentido de que se minimizarmos o funcional (para matriz fixa A e vetor b ) f A , b ( x ) = A x - b ² 2 2 + λ x1 para um tamanho suficientemente grande λ > 0 , é provável que haja muitas opções de A , bL1Ab

fA,b(x)=Axb22+λx1
λ>0AbE ter muitas exatamente de zero entradas na resultante x .λx

Mas se minimizarmos sob a condição de que as entradas de x sejam positivas e somadas a 1 , o termo L 1 não terá nenhum efeito (porque " x " 1 = 1 por decreto). Existe uma análoga L 1 do tipo regularizer que as obras neste caso para incentivar que a resultante x é escassa?fA,bx1L1x1=1L1x

Justin Solomon
fonte
Você poderia elaborar "então o termo L 1 não tem nenhum efeito (porque | | x | | 1 = 1 por decreto)"? L1||x||1=1
usar o seguinte comando
2
@ Cam.Davidson.Pilon: e xi0 implicax 1 = 1 . :)ixi=1x1=1
cardeal
11
Justin: Mais alguns detalhes podem dar uma chance melhor de uma resposta útil. Aqui estão algumas perguntas que surgem imediatamente ao ler sua descrição: ( 1 ) Onde está a "matriz estocástica" em tudo isso? Você parece descrever apenas uma situação envolvendo um vetor estocástico . Podem ser apenas linhas individuais da sua matriz estocástica, ou outra estrutura pode se tornar evidente quando mais detalhes estiverem presentes. ( 2 ) Você deseja que as probabilidades sejam esparsas, ou talvez esparsas, de alguma maneira apropriada? Se o primeiro, por quê? (Isso é algum passeio aleatório em uma escassa) Gráfico ponderados (?)
cardeal
Por que você está exigindo que as entradas de sejampositivas? Em vez disso, você deveria exigir que elesnãofossemnegativos? Além disso, você considerou a parametrização para eliminar a restrição (assumindo que você quer dizer não negativo)? Em outras palavras, tentexi=exp(wi)xxi=exp(wi)jexp(wj)
jrennie
11
@jrennie: Dado o contexto, por positivo, Justin certamente significava não-negativo .
cardeal

Respostas:

2

Um método geral para criar soluções esparsas é via estimativa MAP com uma média normal zero antes de uma variação desconhecida.

p(xi|σi2)N(0,σi2)

Se você atribuir um antes de que tem um modo em zero, o modo posterior geralmente é escasso. O L 1 surge com esta abordagem, tendo uma distribuição de mistura exponencial.σi2L1

p(σi2|λ)Expo(λ22)

Então você recebe

log[p(xi|λ)]=λ|xi|+log[λ2]

Algumas alternativas são o duplo pareto generalizado, meio cauchy e beta invertido. Em certo sentido, estes são melhores que o laço, porque não encolhem valores grandes. Na verdade, tenho certeza de que o duplo pareto generalizado pode ser escrito como uma mistura de exponenciais. Ou seja, escrevemos λ=λip(λi|αβ)

p(xi|αβ)=α2β(1+|xi|β)(α+1)

Observe que incluí constantes de normalização, pois elas ajudam a escolher bons parâmetros globais. Agora, se aplicarmos a restrição de intervalo, teremos um problema mais complicado, pois precisamos renormalizar sobre o simplex.

Outra característica genérica das penalidades de indução de escarsidade é que elas não são diferenciáveis ​​em zero. Normalmente, isso ocorre porque os limites esquerdo e direito são de sinal oposto.

Isso se baseia no brilhante trabalho de Nicolas Polson e James Scott sobre representações médias de variância que eles usam para desenvolver o TIRLS - uma extensão massiva de mínimos quadrados para uma classe muito grande de combinações de penalidade por perda.

Como alternativa, você pode usar um prior que é definido no simplex, mas tem modos nas distribuições marginais em zero. Um exemplo é a distribuição de dirichlet com todos os parâmetros entre 0 e 1. A penalidade implícita seria semelhante a:

i=1n1(ai1)log(xi)(an1)log(1i=1n1xi)

0<ai<1

probabilityislogic
fonte
L1
log[xixn]
xn
1

Duas opções:

  1. L0x . A desvantagem óbvia é que isso não é convexo e, portanto, difícil de otimizar.
  2. xi=exp(wi)jexp(wj)w
jrennie
fonte
Você pode explicar como sua reparametrização incentiva a esparsidade? Parece antes garantir o contrário.
cardeal
wx
Sim eu entendo isso. Mas esses valores não serão zero. Se considerarmos o OP literalmente, isso não ajudará e realmente "machucará" (em certo sentido). Porém, é possível que o OP esteja interessado na escarsidade em relação a alguma outra base, caso em que essa seria uma delas. :)
cardeal
x
wi
1

L1 -norm é apenas uma constante sob a restrição, o problema de otimização restrição poderia muito bem ter uma solução escassa.

λ ; portanto, existe uma solução esparsa ou não. Outra questão é como encontrar a solução. Um otimizador quadrático padrão sob restrições lineares pode, é claro, ser usado, mas os algoritmos populares de descida de coordenadas não podem ser usados ​​imediatamente.

λL1

NRH
fonte
0

Eu posso pensar em três métodos.

  • Método bayesiano: introdução de uma distribuição prévia com média zero e uso da probabilidade do tipo II para estimar os parâmetros e hiper parâmetros.

  • i=1logxi

De fato, o primeiro e o terceiro métodos são os mesmos.

Han Zhang
fonte