Intuicja na temat dywergencji Kullbacka-Leiblera (KL)

47

Dowiedziałem się o intuicji stojącej za dywergencją KL, jak bardzo funkcja rozkładu modelu różni się od teoretycznego / prawdziwego rozkładu danych. Źródłem Czytam mówi dalej, że intuicyjne rozumienie „odległość” między tymi dwoma dystrybucjami jest pomocny, ale nie powinny być brane dosłownie, bo dla dwóch rozkładów i , KL Rozbieżność nie jest symetryczny w i .PQPQ

Nie jestem pewien, jak rozumieć ostatnie stwierdzenie, czy może właśnie tam załamuje się intuicja „odległości”?

Byłbym wdzięczny za prosty, ale wnikliwy przykład.

cgo
źródło
3
Myślę, że musisz się wycofać i zrozumieć, że zazwyczaj masz asymetrię statystyczną między prawdziwym rozkładem populacji a próbką (lub prawdą i modelem) itd., I właśnie to odzwierciedla dywergencja KL ... W ogólnej teorii prawdopodobieństwa nie ma To rozróżnienie zwykle ma charakter symetryczny
seanv507
1
Jakie „źródło” czytałeś?
nbro

Odpowiedzi:

34

Odległość A (metryczna) musi być symetryczna, tj. . Ale z definicji nie jest.DD(P,Q)=D(Q,P)KL

Przykład: , , .Ω={A,B}P(A)=0.2,P(B)=0.8Q(A)=Q(B)=0.5

Mamy:

KL(P,Q)=P(A)logP(A)Q(A)+P(B)logP(B)Q(B)0.19

i

KL(Q,P)=Q(A)logQ(A)P(A)+Q(B)logQ(B)P(B)0.22

zatem i dlatego nie jest odległością (metryczną).K LKL(P,Q)KL(Q,P)KL

mikrofon
źródło
50

Dodając do innych doskonałych odpowiedzi, odpowiedź z innego punktu widzenia, która może dodać nieco więcej intuicji, o którą poproszono.

Rozbieżność Kullbacka-Leiblera to Jeśli dwie hipotezy dotyczące dystrybucji, która jest do generowania danych , i , a jest współczynnikiem prawdopodobieństwo testowania na . Widzimy, że powyższa rozbieżność Kullbacka-Leiblera jest wówczas oczekiwaną wartością współczynnika logikeli w ramach alternatywnej hipotezy. Tak więc jest miarą trudności tego problemu testowego, gdy jest hipotezą zerową. A więc asymetriaX P Q p ( x )

KL(P||Q)=p(x)logp(x)q(x)dx
XPQp(x)q(x)H0:QH1:PKL(P||Q)QKL(P||Q)KL(Q||P) po prostu odzwierciedla asymetrię między hipotezą zerową a alternatywną.

Spójrzmy na to w konkretnym przykładzie. Niech będzie rozkładem a standardowym rozkładem normalnym (w przykładzie liczbowym poniżej ). Całka definiująca rozbieżność wygląda na skomplikowaną, więc zastosujmy po prostu całkowanie numeryczne w R:PtνQν=1

> lLR_1  <-  function(x) {dt(x, 1, log=TRUE)-dnorm(x, log=TRUE)}  
> integrate(function(x) dt(x, 1)*lLR_1(x), lower=-Inf, upper=Inf)
Error in integrate(function(x) dt(x, 1) * lLR_1(x), lower = -Inf, upper = Inf) : 
  the integral is probably divergent

> lLR_2  <-  function(x) {-dt(x, 1, log=TRUE)+dnorm(x, log=TRUE)}  
> integrate(function(x) dnorm(x)*lLR_2(x), lower=-Inf, upper=Inf)
0.2592445 with absolute error < 1e-07

W pierwszym przypadku całka wydaje się rozbieżna numerycznie, wskazując, że rozbieżność jest bardzo duża lub nieskończona, w drugim przypadku jest niewielka, podsumowując: Pierwszy przypadek jest weryfikowany przez analityczną integrację symboliczną w odpowiedzi @ Xi'an tutaj: Jaka jest maksymalna wartość dywergencji Kullbacka-Leiblera (KL) .

KL(P||Q)KL(Q||P)0.26

Co nam to mówi w praktyce? Jeśli model zerowy jest standardowym rozkładem normalnym, ale dane są generowane z rozkładu , to całkiem łatwo jest odrzucić wartość zerową! Dane z dystrybucji nie wyglądają jak normalne dane rozproszone. W innym przypadku role są zmieniane. Wartość null to ale dane są normalne. Ale normalne dane rozproszone mogą wyglądać jak dane , więc ten problem jest znacznie trudniejszy! Tutaj mamy wielkość próbki , a wszystkie dane, które mogą pochodzić z rozkładu normalnego, mogą również pochodzić z ! Zmieniając role, nie, różnica wynika głównie z roli wartości odstających.t1t1t1t1n=1t1

W alternatywnym rozkładzie istnieje dość duże prawdopodobieństwo uzyskania próbki, która ma bardzo małe prawdopodobieństwo w modelu zerowym (normalnym), co daje ogromną rozbieżność. Ale gdy rozkład alternatywny jest normalny, praktycznie wszystkie dane, które możemy uzyskać, będą miały umiarkowane prawdopodobieństwo (naprawdę gęstość ...) w modelu zerowym , więc rozbieżność jest niewielka.t1t1

Jest to związane z moją odpowiedzią tutaj: dlaczego powinniśmy używać t błędów zamiast zwykłych błędów?

kjetil b halvorsen
źródło
22

Po pierwsze, naruszenie warunku symetrii jest najmniejszym problemem z rozbieżnością Kullbacka-Leiblera. również narusza nierówność trójkąta. Możesz po prostu wprowadzić wersję symetryczną jako , ale nadal nie jest to metryczna, ponieważ zarówno i narusza nierówność trójkąta. Aby udowodnić, że wystarczy wziąć trzy tendencyjne monety A, B i C, które produkują znacznie mniej głów niż reszki, np. Monety o prawdopodobieństwie głów: A = 0,1, B = 0,2 i C = 0,3. W obu przypadkach regularna dywergencja KL D lub jej symetryczna wersja SKL, sprawdź, czy nie wypełniają nierówności trójkąta S K L ( P D ( A | | C )D(P||Q)

SKL(P,Q)=D(P||Q)+D(Q||P)
D(P||Q)SKL(P,Q)
D(A||B)+D(B||C)D(A||C)
SKL(A,B)+SKL(B,C)SKL(A,C)
Wystarczy użyć tych wzorów:
D(P||Q)=ipilog(piqi)
SKL(P,Q)=i(piqi)log(piqi)

D(A||B)=0.1log(0.10.2)+0.9log(0.90.8)0.0159
D(B||C)0.0112
D(A||C)0.0505
0.0159+0.01120.0505
SKL(A,B)0.0352
SKL(B,C)0.0234
SKL(A,C)0.1173
0.0352+0.02340.1173

Przedstawiłem ten przykład celowo. Wyobraźmy sobie, że rzucasz monetami, np. 100 razy. Tak długo, jak monety są obiektywne, po prostu kodujesz wyniki losowania w sekwencji 0-1 bitów (1-główka, 0-ogon). W takiej sytuacji, gdy prawdopodobieństwo głowy jest takie samo jak prawdopodobieństwo ogona i wynosi 0,5, jest to dość skuteczne kodowanie. Teraz mamy pewne tendencyjne monety, więc wolelibyśmy zakodować bardziej prawdopodobne wyniki za pomocą krótszego kodu, np. Scalić grupy głów i ogonów i reprezentować sekwencje k głów o dłuższym kodzie niż sekwencja k ogonów (są bardziej prawdopodobne). I tu pojawia się dywergencja Kullbacka-Leiblera . Jeśli P reprezentuje prawdziwy rozkład wyników, a Q jest jedynie przybliżeniem P, toD(P||Q)D(P||Q) oznacza karę, którą płacisz, gdy kodujesz wyniki, które faktycznie pochodzą z dystrybucji P z kodowaniem przeznaczonym dla Q (kara w znaczeniu dodatkowych bitów, których musisz użyć).

Jeśli potrzebujesz tylko metryki, skorzystaj z odległości Bhattacharyya (oczywiście zmodyfikowana wersja )1[xp(x)q(x)]

Adam Przedniczek
źródło
7
Jeśli ktoś martwi się faktem posiadania metryki o bliższym związku z dywergencją KL, może rozważyć pierwiastek kwadratowy dywergencji Jensen-Shannon zamiast Bhattacharyya.
kardynał
5

Kusi mnie tutaj, aby udzielić czystej intuicyjnej odpowiedzi na twoje pytanie. Zmieniając to, co mówisz, rozbieżność KL jest sposobem pomiaru odległości między dwoma rozkładami, tak jak przy obliczaniu odległości między dwoma zestawami danych w przestrzeni Hilberta, ale należy zachować ostrożność.

Dlaczego? Rozbieżność KL nie jest odległością, której zwykle można użyć, na przykład normą . Rzeczywiście, jest dodatni i równy zero, tylko wtedy, gdy oba rozkłady są równe (jak w aksjomatach określających odległość). Ale jak wspomniano, nie jest symetryczny. Istnieją sposoby na obejście tego, ale ma sens, aby nie było symetryczne.L2

Rzeczywiście, rozbieżność KL definiuje odległość między rozkładem modelu (który faktycznie znasz) a teoretycznym tak że sensowne jest obsługiwanie w inny sposób („teoretyczna” odległość do przy założeniu, że model ) i („empiryczna” odległość do przy założeniu danych ), ponieważ oznaczają one całkiem różne miary.QPKL(P,Q)PQPKL(Q,P)PQQ

meduz
źródło
4

Podręcznik Elementy teorii informacji daje nam przykład:

Na przykład, jeśli znamy prawdziwy rozkład p zmiennej losowej, moglibyśmy zbudować kod o średniej długości opisu H (p). Jeśli zamiast tego użyjemy kodu dla rozkładu q, potrzebowalibyśmy średnio H (p) + D (p || q) bitów, aby opisać zmienną losową.

Aby sparafrazować powyższe stwierdzenie, możemy powiedzieć, że jeśli zmienimy rozkład informacji (z q na p), potrzebujemy średnio dodatkowych bitów D (p || q), aby zakodować nowy rozkład.

Ilustracja

Pozwól mi to zilustrować za pomocą jednej aplikacji w przetwarzaniu języka naturalnego.

Pod uwagę, że duża grupa ludzi, oznaczony B, są mediatorami, a każdy z nich jest przypisany zadania do wyboru z rzeczownika turkey, animala booki przekazuje go do C. Jest to nazwa facet, który może wysłać każdy z nich e-maila, aby dać im kilka wskazówek. Jeśli nikt w grupie nie otrzyma wiadomości e-mail, może unieść brwi i wahać się przez chwilę, zastanawiając się, czego potrzebuje C. Prawdopodobieństwo wyboru każdej opcji wynosi 1/3. Zbyt jednolity rozkład (jeśli nie, może odnosić się do ich własnych preferencji i po prostu ignorujemy takie przypadki).

Ale jeśli otrzymają czasownik, np. baste3/4 z nich może wybrać, turkeya 3/16 wybrać animali 1/16 book. Więc ile informacji w bitach uzyskał średnio każdy z mediatorów, gdy zna czasownik? To jest:

D(p(nouns|baste)||p(nouns))=x{turkey,animal,book}p(x|baste)log2p(x|baste)p(x)=34log23413+316log231613+116log211613=0.5709  bits

Ale co jeśli podany czasownik jest read? Możemy sobie wyobrazić, że wszyscy bookwybraliby bez wahania, wówczas średni przyrost informacji dla każdego mediatora z czasownika readwynosi:

D(p(nouns|read)||p(nouns))=x{book}p(x|read)log2p(x|read)p(x)=1log2113=1.5849  bits
Widzimy, że czasownik readmoże dostarczyć mediatorom więcej informacji. I to może mierzyć względna entropia.

Kontynuujmy naszą historię. Jeśli C podejrzewa, że ​​rzeczownik może się mylić, ponieważ A powiedział mu, że mógł popełnić błąd, wysyłając niewłaściwy czasownik do mediatorów. Ile informacji w bitach może dać C zła wiadomość?

1) jeśli czasownik podany przez A brzmiał baste:

D(p(nouns)||p(nouns|baste))=x{turkey,animal,book}p(x)log2p(x)p(x|baste)=13log21334+13log213316+13log213116=0.69172  bits

2) ale co jeśli czasownik był read?

D(p(nouns)||p(nouns|baste))=x{book,,}p(x)log2p(x)p(x|baste)=13log2131+13log2130+13log2130=  bits

Ponieważ C nigdy nie wie, jakie byłyby pozostałe dwa rzeczowniki i każde słowo w słownictwie byłoby możliwe.

Widzimy, że dywergencja KL jest asymetryczna.

Mam nadzieję, że mam rację, a jeśli nie, proszę o komentarz i pomoc w poprawieniu mnie. Z góry dziękuję.

Lerner Zhang
źródło