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 \ lambda> 0 , prawdopodobnie istnieje wiele opcji A , \ vec {b} , a \ lambda ma wiele dokładnie zerowych pozycji w wynikowym \ vec {x} . A b f A , b ( x ) = A x - b2 2 + λ x1 λ > 0 A b λ xL1Ab

fA,b(x)=Axb22+λx1
λ>0Abλx

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

Justin Solomon
źródło
Czy mógłbyś rozwinąć „wtedy termin nie ma żadnego wpływu (ponieważ według fiat)”? | | x | | 1 = 1L1||x||1=1
Cam.Davidson.Pilon
2
@ Cam.Davidson.Pilon: i oznacza . :)xi0ixi=1x1=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óbujxxi=exp(wi)jexp(wj)
jrennie
1
@jrennie: Biorąc pod uwagę kontekst, pozytywny Justin z pewnością oznaczał nieujemne .
kardynał

Odpowiedzi:

2

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

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

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.σi2L1

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

To dostajesz

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

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 p ( λ i | α β ) . Otrzymujemy:λ=λip(λja|αβ)

p(xi|αβ)=α2β(1+|xi|β)(α+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:

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

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. P0<ai<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! L1
Justin Solomon
log[xixn]
xn
1

Dwie opcje:

  1. L0x
  2. xi=exp(wi)jexp(wj)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ł
wx
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ł
x
wi
1

L1

λ

λL1

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.

  • i=1logxi

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

Han Zhang
źródło