Indywidualna regularyzacja dla matryc stochastycznych

10

Dobrze wiadomo (np. W dziedzinie wykrywania kompresji), że norma „indukuje ” w tym sensie, że jeśli zminimalizujemy funkcjonalność (dla stałej macierzy i wektora ) dla wystarczająco dużych , prawdopodobnie istnieje wiele opcji , , a ma wiele dokładnie zerowych pozycji w wynikowym . $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}$

λ

$\lambda$

\vec{x}

$\vec{x}$

Ale jeśli zminimalizujemy $f_{A,\vec{b}}$ pod warunkiem, że wpisy w $\vec{x}$ są dodatnie i sumują się do $1$ , to termin $L_1$ nie ma żadnego wpływu (ponieważ $\|\vec{x}\|_1=1$ przez fiat). Czy istnieje analogiczny $L_1$ typu który działa w tym przypadku, aby zachęcić, że wynikowy $\vec{x}$ jest rzadki?

regression matrix normalization regularization sparse Justin Solomon
źródło

Czy mógłbyś rozwinąć „wtedy termin nie ma żadnego wpływu (ponieważ według fiat)”?

L_{1}

$L_1$

| | x | |_{1} = 1

$||x||_1 = 1$

Cam.Davidson.Pilon

2

@ Cam.Davidson.Pilon: i oznacza . :)

x_{i} \geq 0

$x_i \geq 0$

\sum_{i} x_{i} = 1

$\sum_i x_i = 1$

‖ x ‖_{1} = 1

$\|x\|_1 = 1$

kardynał

1

Justin: Więcej szczegółów może dać lepszą szansę na użyteczną odpowiedź. Oto kilka pytań, które pojawiają się natychmiast po przeczytaniu opisu: ( 1 ) Gdzie w tym wszystkim znajduje się „matryca stochastyczna”? Wygląda na to, że opisujesz sytuację dotyczącą wektora stochastycznego . Mogą to być po prostu pojedyncze rzędy macierzy stochastycznej lub inna struktura może stać się widoczna, gdy pojawią się kolejne szczegóły. ( 2 ) Chcesz, aby same prawdopodobieństwa były rzadkie, a może rzadkie na jakiejś odpowiedniej podstawie? Jeśli pierwszy, dlaczego? (Czy to jakiś losowy spacer na ważonym (rzadkim) wykresie?)

kardynał

Dlaczego wymagasz, aby wpisy były pozytywne ? Czy zamiast tego powinieneś wymagać, aby były one nieujemne ? Czy zastanawiałeś się też nad ponowną parametryzacją w celu wyeliminowania ograniczenia (zakładając, że masz na myśli wartość nieujemną)? Innymi słowy, spróbuj

\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

1

@jrennie: Biorąc pod uwagę kontekst, pozytywny Justin z pewnością oznaczał nieujemne .

kardynał

2

Ogólna metoda tworzenia rzadkich rozwiązań polega na oszacowaniu MAP przy zerowej średniej normalnej przed nieznaną wariancją.

p (x_{i} | σ_{i}^{2}) \sim N (0, σ_{i}^{2})

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

Jeśli następnie przypiszesz przed który ma tryb zerowy, wtedy tryb tylny jest zwykle rzadki. wynika z tego podejścia, biorąc wykładniczy rozkład mieszania. $\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)$

To dostajesz

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

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

Niektóre alternatywy to uogólnione podwójne pareto, pół cauchy, odwrócona beta. W pewnym sensie są one lepsze niż lasso, ponieważ nie zmniejszają dużych wartości. W rzeczywistości jestem prawie pewien, że uogólnione podwójne pareto można zapisać jako mieszaninę wykładników. Oznacza to, że piszemy a następnie umieszczamy wartość gamma przed . Otrzymujemy: $\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)}$

Zauważ, że uwzględniłem stałe normalizujące, ponieważ pomagają one wybrać dobre parametry globalne. Teraz, jeśli zastosujemy ograniczenie zakresu, będziemy mieli bardziej skomplikowany problem, ponieważ musimy renormalizować na simpleksie.

Inną ogólną cechą kar wywołujących rzadkość jest to, że nie można ich odróżnić od zera. Zwykle dzieje się tak, ponieważ lewy i prawy limit mają przeciwny znak.

Jest to oparte na genialnej pracy Nicolasa Polsona i Jamesa Scotta na temat reprezentacji wariancji średnich mieszanin, których używają do opracowania TIRLS - masywne rozszerzenie najmniejszych kwadratów do bardzo dużej klasy kombinacji strat i kar.

Alternatywnie można użyć wcześniejszego, który jest zdefiniowany na simpleksie, ale ma tryby w rozkładach krańcowych na zero. Jednym z przykładów jest rozkład dirichleta ze wszystkimi parametrami między 0 a 1. Implikowana kara wyglądałaby następująco:

- \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)$

Gdzie . Jednak trzeba zachować ostrożność przy optymalizacji numerycznej, ponieważ kara ma osobliwości. Bardziej solidnym procesem szacowania jest użycie średniej tylnej. Chociaż stracisz dokładną rzadkość, otrzymasz wiele tylnych środków, które są bliskie zeru. P $0<a_i<1$

prawdopodobieństwo prawdopodobieństwa
źródło

To wydaje się bardzo interesującym pomysłem, chociaż nie jesteśmy w pełni przygotowani do zrozumienia szczegółów! Jeśli dobrze rozumiem, chodzi o to, że poprzednik

wywodzi się z założenia, że zmienne mają rozkład wykładniczy około 0. Zatem potrzebujemy rozkładu wyśrodkowanego na 0, który działa lepiej dla naszych zmiennych. Ale nie ma wyraźnego zwycięzcy, prawda? Czy istnieją rozkłady na „zmienne dodatnie, które sumują się do 1”? Dzięki za pomoc!

L_{1}

$L_1$

Justin Solomon

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

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

x_{n}

$x_n$

1

Dwie opcje:

$L_0$ $\vec x$
$x_i = \frac{\exp(w_i)}{\sum_j \exp(w_j)}$ $\|\vec w\|$

jrennie
źródło

Czy możesz wyjaśnić, w jaki sposób twoja reparametryzacja zachęca do rzadkości? Wydaje się raczej gwarantować coś wręcz przeciwnego.

kardynał

\vec{w}

$\vec w$

\vec{x}

$\vec x$

Tak rozumiem to. Ale te wartości nie będą równe zero. Jeśli weźmiemy PO dosłownie, to nie pomoże i faktycznie „skrzywdzi” (w pewnym sensie). Możliwe jednak, że OP jest zainteresowany rzadkością w odniesieniu do innych podstaw, w którym to przypadku byłby to jeden z nich. :)

kardynał

\vec{x}

$\vec x$

w_{i}

$w_i$

- \infty

$-\infty$

1

$L_1$

$\lambda$

$\lambda$ $L_1$

NRH
źródło

0

Potrafię wymyślić trzy metody.

Metoda bayesowska: wprowadzenie zerowej średniej wcześniejszej dystrybucji i wykorzystanie prawdopodobieństwa typu II do oszacowania parametrów i parametrów hiperparametrów.
$\Vert\cdot\Vert_{\infty}$
$-\sum_{i=1}\log x_i$

W rzeczywistości pierwsza i trzecia metoda są takie same.

Han Zhang
źródło

Indywidualna regularyzacja dla matryc stochastycznych

Odpowiedzi: