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 e vetor ) para um tamanho suficientemente grande , é provável que haja muitas opções de , $L_1$ $A$ $\vec{b}$

f_{A, \vec{b}} (\vec{x}) = ‖ A \vec{x} - \vec{b} ‖_{2}^{2} + λ ‖ \vec{x} ‖_{1}

$f_{A,\vec{b}}(\vec{x})=\|A\vec{x}-\vec{b}\|_2^2+\lambda\|\vec{x}\|_1$

λ > 0

$\lambda>0$

A

$A$

\vec{b}

$\vec{b}$ E

ter muitas exatamente de zero entradas na resultante

.

λ

$\lambda$

\vec{x}

$\vec{x}$

Mas se minimizarmos sob a condição de que as entradas de sejam positivas e somadas a , o termo não terá nenhum efeito (porque por decreto). Existe uma análoga do tipo regularizer que as obras neste caso para incentivar que a resultante é escassa? $f_{A,\vec{b}}$ $\vec{x}$ $1$ $L_1$ $\|\vec{x}\|_1=1$ $L_1$ $\vec{x}$

regression matrix normalization regularization sparse Justin Solomon
fonte

Você poderia elaborar "então o

termo

não tem nenhum efeito (porque

por decreto)"?

L_{1}

$L_1$

| | x | |_{1} = 1

$||x||_1 = 1$

usar o seguinte comando

2

@ Cam.Davidson.Pilon:

e

x_{i} \geq 0

$x_i \geq 0$

implica

. :)

\sum_{i} x_{i} = 1

$\sum_i x_i = 1$

‖ x ‖_{1} = 1

$\|x\|_1 = 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, tente

\vec{x}

$\vec x$

x_{i} = \frac{\exp (w_{i})}{\sum_{j} \exp (w_{j})}

$x_i = \frac{\exp(w_i)}{\sum_j \exp(w_j)}$

jrennie

11

@jrennie: Dado o contexto, por positivo, Justin certamente significava não-negativo .

cardeal

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 (x_{i} | σ_{i}^{2}) \sim N (0, σ_{i}^{2})

$p(x_i|\sigma_i^2)\sim N(0,\sigma_i^2)$

Se você atribuir um antes de que tem um modo em zero, o modo posterior geralmente é escasso. O surge com esta abordagem, tendo uma distribuição de mistura exponencial. $\sigma_i^2$ $L_1$

p (σ_{i}^{2} | λ) \sim E x p o (\frac{λ^{2}}{2})

$p(\sigma_i^2|\lambda)\sim Expo\left(\frac{\lambda^2}{2}\right)$

Então você recebe

\log [p (x_{i} | λ)] = - λ | x_{i} | + \log [\frac{λ}{2}]

$\log[p(x_i|\lambda)]=-\lambda | x_i|+\log\left[\frac{\lambda}{2}\right]$

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 $\lambda=\lambda_i$ $p(\lambda_i|\alpha\beta)$

p (x_{i} | α β) = \frac{α}{2 β} {(1 + \frac{| x_{i} |}{β})}^{- (α + 1)}

$p(x_i|\alpha\beta)=\frac{\alpha}{2\beta}\left(1+\frac{|x_i|}{\beta}\right)^{-(\alpha+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:

- \sum_{i = 1}^{n - 1} (a_{i} - 1) \log (x_{i}) - (a_{n} - 1) \log (1 - \sum_{i = 1}^{n - 1} x_{i})

$-\sum_{i=1}^{n-1}(a_i-1)\log(x_i) - (a_n-1)\log(1-\sum_{i=1}^{n-1}x_i)$

$0<a_i<1$

probabilityislogic
fonte

L_{1}

$L_1$

\log [\frac{x_{i}}{x_{n}}]

$\log\left[\frac{x_i}{x_n}\right]$

x_{n}

$x_n$

1

Duas opções:

$L_0$ $\vec x$ . A desvantagem óbvia é que isso não é convexo e, portanto, difícil de otimizar.
$x_i = \frac{\exp(w_i)}{\sum_j \exp(w_j)}$ $\|\vec w\|$

jrennie
fonte

Você pode explicar como sua reparametrização incentiva a esparsidade? Parece antes garantir o contrário.

cardeal

\vec{w}

$\vec w$

\vec{x}

$\vec x$

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

\vec{x}

$\vec x$

w_{i}

$w_i$

- \infty

$-\infty$

1

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

$\lambda$ ; 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.

$\lambda$ $L_1$

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.
$\Vert\cdot\Vert_{\infty}$
$-\sum_{i=1}\log x_i$

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

Han Zhang
fonte

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

Respostas: