Po co optymalizować maksymalne prawdopodobieństwo dziennika zamiast prawdopodobieństwa

66

W większości zadań uczenia maszynowego, w których można sformułować pewne prawdopodobieństwo które należy zmaksymalizować, faktycznie zoptymalizowalibyśmy prawdopodobieństwo zamiast prawdopodobieństwa dla niektórych parametrów . Np. W treningu z maksymalnym prawdopodobieństwem jest to zwykle logarytm prawdopodobieństwa. W przypadku tej metody gradientowej wiąże się to z czynnikiem:plogpθ

logpθ=1ppθ

Zobacz tutaj lub tutaj kilka przykładów.

Oczywiście optymalizacja jest równoważna, ale gradient będzie inny, więc każda metoda oparta na gradientach będzie zachowywać się inaczej (zwłaszcza metody gradientów stochastycznych). Czy jest jakieś uzasadnienie, że gradient działa lepiej niż gradient ?logpp

Albert
źródło
3
musisz zauważyć, że zwykle maksymalizujemy prawdopodobieństwo korzystania z instrumentów pochodnych. Z drugiej strony w wielu przypadkach stosowany jest warunek niezależności, co oznacza, że ​​prawdopodobieństwo jest iloczynem niektórych funkcji gęstości prawdopodobieństwa iid. Ponadto iloczyn wielu małych wartości (w przedziale [0,1]) daje bardzo małą wartość. Powoduje to trudność obliczeniową.
TPArrow
@AlejandroRodriguez sprawdź moją odpowiedź tutaj, aby uzyskać więcej szczegółów.
Paul

Odpowiedzi:

65

Metody gradientowe zwykle działają lepiej, optymalizując niż ponieważ gradient jest ogólnie lepiej skalowany . Oznacza to, że ma rozmiar, który konsekwentnie i pomocnie odzwierciedla geometrię funkcji celu, co ułatwia wybranie odpowiedniego rozmiaru kroku i osiągnięcie optymalnej w mniejszej liczbie kroków.p ( x ) log p ( x )logp(x)p(x)logp(x)

Aby sprawdzić, co znaczy, porównaj proces optymalizacji Gradient i . W dowolnym punkcie gradient wynosiJeśli pomnożymy to przez , otrzymamy dokładny rozmiar kroku potrzebny do osiągnięcia globalnego optimum przy początku, bez względu naf ( x ) = log p ( x ) = - x 2 xp(x)=exp(x2)f(x)=logp(x)=x2xf(x)

f(x)=2x.
1/2xjest. Oznacza to, że nie musimy zbyt ciężko pracować, aby uzyskać dobry rozmiar kroku (lub „szybkość uczenia się” w żargonie ML). Bez względu na to, gdzie jest nasz punkt początkowy, po prostu ustawiliśmy nasz krok na połowę gradientu i będziemy w jednym punkcie na początku. A jeśli nie znamy dokładnego wymaganego współczynnika, możemy po prostu wybrać rozmiar kroku wokół 1, przeprowadzić trochę wyszukiwania linii i szybko znajdziemy duży rozmiar kroku, taki, który działa dobrze bez względu na to, gdzie jest. Ta właściwość jest odporna na translację i skalowanie . Podczas gdy skalowanie spowoduje, że optymalne skalowanie kroków będzie różnić się od 1/2, przynajmniej skalowanie kroków będzie takie samo bez względu na , więc musimy tylko znaleźć jeden parametr, aby uzyskać skuteczną optymalizację opartą na gradiencie schemat.xf(x)f(x)x

Natomiast gradient ma bardzo słabe globalne właściwości do optymalizacji. MamyMnoży to idealnie ładny, dobrze zachowujący się gradient przez współczynnik który zanika (szybciej niż) wykładniczo wraz ze wzrostem . Przy mamy już , więc krok wzdłuż wektora gradientu jest około razy za mały. Aby uzyskać rozsądny rozmiar kroku w kierunku optymalnego, musielibyśmy przeskalować gradient przez odwrotność tego, ogromną stałąp(x)

p(x)=f(x)p(x)=2xexp(x2).
2xexp(x2)xx=5exp(x2)=1.4101110111011. Taki źle wyskalowany gradient jest gorszy niż bezużyteczny dla celów optymalizacji - lepiej byłoby po prostu spróbować wykonać krok jednostkowy w górę, niż ustawić nasz krok skalując względem ! (W wielu zmiennych staje się nieco bardziej użyteczny, ponieważ przynajmniej otrzymujemy informacje kierunkowe z gradientu, ale problem skalowania pozostaje.)p(x)p(x)

Zasadniczo nie ma gwarancji, że będzie miał tak świetne właściwości skalowania gradientu, jak ten przykład zabawki, szczególnie gdy mamy więcej niż jedną zmienną. Jednak w przypadku niemal nietrywialnych problemów będzie znacznie lepszy niż . Wynika to z faktu, że prawdopodobieństwo jest dużym produktem z wieloma warunkami, a dziennik zamienia ten produkt w sumę, jak zauważono w kilku innych odpowiedziach. Pod warunkiem, że terminy z prawdopodobieństwem są dobrze zachowane z punktu widzenia optymalizacji, ich log jest ogólnie dobrze zachowany, a suma dobrze zachowanych funkcji jest dobrze zachowana. Przez dobrze wychowany mam na myślilogp(x)logp(x)p(x)f(x)nie zmienia się zbyt szybko ani zbyt szybko, co prowadzi do niemal kwadratowej funkcji, którą można łatwo zoptymalizować metodami gradientowymi. Suma pochodnego jest pochodną sumy, bez względu na kolejność pochodnych, co pomaga zapewnić, że ten duży stos sum sum ma bardzo rozsądną drugą pochodną!

Paweł
źródło
4
+1 Ta odpowiedź przywołuje i podkreśla punkty, które docierają do sedna sprawy.
whuber
47

Niedomiar

Komputer używa ograniczonej cyfrowej reprezentacji zmiennoprzecinkowej ułamków, dlatego pomnożenie tak wielu prawdopodobieństw jest gwarantowane bardzo blisko zera.

W przypadku nie mamy tego problemu.log

Uri Goren
źródło
3
+1 za stabilność liczbową - to i odpowiedź Yurila powinna być jedna!
Alec Teal
1
Możesz obliczyć produkt w przestrzeni dziennika, dzięki czemu staje się sumą, a następnie przenieść go z powrotem. Lub obliczasz który jest równy . Zatem stabilność numeryczna nie jest pytaniem. logpθppθ
Albert
1
Pamiętaj, że , o którym wspomniałeś, jest zwielokrotnieniem prawdopodobieństwa wszystkich zdarzeń w próbce, a jest elementem podlegającym niedopełnieniu. pp
Uri Goren
5
@Filip Terminologia w tym wątku jest nieco odradzana. Omawiamy gęstości prawdopodobieństwa , a nie prawdopodobieństwa. Gęstości są dowolne: zależą od jednostek miary. Co więcej, dla wystarczającej wielkości próbek gęstość prawdopodobieństwa dowolnej prostej próbki z modelu parametrycznego będzie ostatecznie mniejsza niż . W dużych problemach (z milionami danych) gęstość prawdopodobieństwa rutynowo wynosi lub mniej. Nawet próbka wielkości ze standardowego rozkładu normalnego prawie na pewno ma gęstość prawdopodobieństwa mniejszą niż . 212721000000802127
whuber
4
@FilipHaglund: whuber ma rację, jednak fakt, że jego gęstość nie jest tutaj kluczową obserwacją. Równie dobrze moglibyśmy dyskutować o dyskretnym procesie i mówić o rzeczywistych prawdopodobieństwach (i faktycznie PO nie powiedział niczego, co wykluczałoby ten przypadek). Ale mówimy o prawdopodobieństwach dla bardzo konkretnych wyników (np. Milion obserwacji podążających w określony sposób). Pojedynczy konkretny wynik jest mało prawdopodobny, ale w bayesowskim wnioskowaniu współczynniki prawdopodobieństwa są ważne, dlatego musimy wiedzieć, o ile większe jest jedno małe prawdopodobieństwo od drugiego.
Meni Rosenfeld,
34
  1. Logarytm prawdopodobieństwa wielu wspólnych prawdopodobieństw upraszcza sumę logarytmów poszczególnych prawdopodobieństw (a reguła sumy jest łatwiejsza niż reguła iloczynu dla różnicowania)

    log(iP(xi))=ilog(P(xi))

  2. Logarytm członka rodziny rozkładów prawdopodobieństwa wykładniczego (który obejmuje wszechobecną normalną) jest wielomianem parametrów (tzn. Maksymalne prawdopodobieństwo zmniejsza się do najmniejszych kwadratów dla rozkładów normalnych)

    log(exp(12x2))=12x2

  3. Ta druga forma jest zarówno bardziej stabilna numerycznie, jak i symbolicznie łatwiejsza do odróżnienia od pierwszej.

  4. Wreszcie, logarytm jest transformacją monotoniczną, która zachowuje lokalizację ekstremów (w szczególności szacowane parametry o maksymalnym prawdopodobieństwie są identyczne dla formuły oryginalnej i transformowanej logarytmicznie)

TemplateRex
źródło
5
Powodu 2 nie można wystarczająco zestresować. Aby zmaksymalizować prawdopodobieństwo logarytmiczne dla modelu liniowego z szumem Gaussa, wystarczy rozwiązać problem najmniejszych kwadratów, co sprowadza się do rozwiązania liniowego układu równań.
Paweł
Powody 1 i 3 opisują po prostu, jak to obliczyć. Możesz to obliczyć w ten sposób, a następnie przekonwertować z powrotem (pomnożyć przez ), aby uzyskać . W rzeczywistości dość często oblicza się w przestrzeni logów stabilność liczbową. Ale to nie wyjaśnia, dlaczego używasz tego gradientu. Powód 4 również nie jest powodem, dla którego gradient jest lepszy. Możesz to zrobić również z wieloma innymi transformacjami. Powód 2 jest interesujący, ale nadal nie jestem do końca pewien, dlaczego gradient wielomianu jest lepszy niż gradient innej funkcji. ppθlogp
Albert
@Albert pochodna wielomianu jest wielomianem o jeden stopień niższym (w szczególności kwadratowy staje się liniowy), podczas gdy wykładnicze nie są po prostu różnicowane
TemplateRex,
@TemplateRex: Tak, to jasne. Ale pytam o właściwości zbieżności w metodzie gradientu stochastycznego.
Albert
25

O wiele łatwiej jest pobrać pochodną sumy logarytmów niż pochodną produktu, która zawiera, powiedzmy, 100 mnożników.

Jurij
źródło
10
Dodatkowo zmniejszasz potencjalne problemy numeryczne, gdy terminy stają się bardzo małe lub duże.
Björn
8
Przeciwnie, PO zapewnia domyślnie doskonały sposób na obliczenie pochodnej dowolnego produktu funkcji nieujemnych: pomnożenie sumy pochodnych dzienników przez sam produkt. (To zwielokrotnienie najlepiej jest przeprowadzić w kategoriach logarytmów, co eliminuje również problemy numeryczne, o których mowa w komentarzu @ Björna.) Zatem „łatwość” nie oferuje żadnej prawdziwej mocy wyjaśniającej, ani nie odnosi się do bardziej znaczącego pytania o porównywanie gradientów .
whuber
10

Zasadniczo najbardziej podstawowym i łatwym problemem optymalizacji jest optymalizacja funkcji kwadratowej. Możesz łatwo znaleźć optymalną funkcję, bez względu na to, od czego zaczynasz. To, jak to się manifestuje, zależy od konkretnej metody, ale im bliżej funkcji kwadratowej, tym lepiej.

Jak zauważono w TemplateRex, przy wielu różnych problemach prawdopodobieństwa, które biorą udział w obliczaniu funkcji prawdopodobieństwa, pochodzą z rozkładu normalnego lub są przez niego przybliżone. Więc jeśli pracujesz na logu, otrzymujesz ładną funkcję kwadratową. Natomiast jeśli pracujesz nad prawdopodobieństwami, masz funkcję, która

  1. Nie jest wypukły (zmora algorytmów optymalizacji wszędzie)
  2. Szybko przecina wiele skal, a zatem ma bardzo wąski zakres, w którym wartości funkcji wskazują, gdzie należy kierować wyszukiwanie.

Którą funkcję wolisz zoptymalizować, czy inną ?

(To było w rzeczywistości łatwe; w praktycznych zastosowaniach wyszukiwanie może rozpocząć się tak daleko od optymalnego, że wartości funkcji i gradienty, nawet jeśli byłyby w stanie je obliczyć numerycznie, będą nie do odróżnienia od 0 i bezużyteczne dla celów optymalizacji algorytm. Ale przekształcenie w funkcję kwadratową sprawia, że ​​jest to bułka z masłem.)

Zauważ, że jest to całkowicie zgodne z już wspomnianymi problemami ze stabilnością liczbową. Powodem, dla którego skala dziennika jest wymagana do pracy z tą funkcją, jest dokładnie ten sam powód, dla którego prawdopodobieństwo dziennika jest znacznie lepiej zachowane (dla optymalizacji i innych celów) niż oryginał.

Możesz również podejść do tego w inny sposób. Nawet jeśli nie ma przewagi w logu (który jest) - i tak użyjemy skali logu do pochodnych i obliczeń, więc jaki jest powód, aby zastosować transformację exp tylko do obliczenia gradientu? Równie dobrze możemy pozostać spójni z logem.

Meni Rosenfeld
źródło
@TemplateRex: Dziennik funkcji wypukłej (skierowanej w dół) jest wypukły, ale odwrotność nie jest prawdą. Prawdopodobieństwa nie są wypukłe, więc nie mają nic do zachowania, ale log jest wypukły. Spójrz na wykresy, które połączyłem - exp (-10x ^ 2) jest oczywiście niewypukły, ale -10x ^ 2 jest.
Meni Rosenfeld
4

Używając , zwiększamy zakres dynamiczny algorytmu optymalizacji. w zastosowaniach jest zwykle produktem funkcji. Na przykład w oszacowaniu maksymalnego prawdopodobieństwa jest to iloczyn postaci , gdzie Jest funkcją gęstości, którą można większa lub mniejsza niż 1, btw.lnppL(x|θ)=Πi=1nf(xi|θ)f(.)

Tak więc, gdy jest bardzo duża, tj dużą próbkę, czynność prawdopodobieństwo jest zazwyczaj daleko od 1: to albo bardzo małe lub bardzo duże, ponieważ jest to funkcja zasilania .nL(.)Lf(.)n

Rejestrując dziennik, po prostu poprawiamy zakres dynamiczny dowolnego algorytmu optymalizacyjnego, umożliwiając mu pracę z bardzo dużymi lub małymi wartościami w ten sam sposób.

Aksakal
źródło
0

Podano już kilka fajnych odpowiedzi. Ale ostatnio spotkałem nowy:

Często otrzymujesz olbrzymi zestaw danych treningowych i definiujesz jakiś model probabilistyczny i chcesz zmaksymalizować prawdopodobieństwo . Zakłada się, że są niezależne, tzn. Masz Teraz często ćwiczysz stochastyczne (mini-wsadowe) szkolenie gradientowe, tj. Na każdym etapie, dla swojej straty , optymalizujesz dla , tj. Xp(x|θ)xX

p(X|θ)=xXp(x|θ).
LL(X|θ)XX
θ:=θxXL(x|θ)θ.
Teraz te stochastyczne kroki są kumulowane addytywnie. Z tego powodu chcesz właściwości, która ogólnie Tak jest w przypadku
L(X|θ)=xXL(x|θ).
L(x|θ)=logp(x|θ).

Albert
źródło