Oblicz w praktyce rozbieżność Kullbacka-Leiblera?

15

Używam KL Divergence jako miary odmienności między 2 p.m.f. P i Q .

DKL(P||Q)=i=1Nln(PiQi)Pi
=P(Xi)ln(Q(Xi))+P(Xi)ln(P(Xi))

Jeśli to możemy łatwo obliczyć, że P ( X i ) l n ( Q ( X i ) ) = 0 P ( X i ) l n ( P ( X i ) ) = 0

P(Xi)=0
P(Xi)ln(Q(Xi))=0
P(Xi)ln(P(Xi))=0

Ale jeśli i Q ( X i ) = 0, jak obliczyć P ( X i ) l n ( Q ( X i ) )

P(Xi)0
Q(Xi)=0
P(Xi)ln(Q(Xi))
smwikipedia
źródło
Aby zaoszczędzić wszystkim innym czas na wpatrywanie się w to, co miałeś na myśli, możesz zmienić do P ( X i ) 0 z tokenem „\ ne”P(Xi)!=0P(Xi)0
Q(Xi)=0XiQ
@Matthew Dzięki, poprawione. Przypadkowo zastosowałem swój zwyczaj kodowania.
smwikipedia
Q(Xi)=0XiPQ wyników i dodaję małą liczbę pseudo , powiedzmy 0,001, dla wyników nie pokazujących się. Pozwala to uniknąć prawdopodobieństw o ​​wartości zerowej. Ale nie jestem pewien, czy są jakieś skutki uboczne.
smwikipedia

Odpowiedzi:

15

Nie możesz i nie robisz. Wyobraź sobie, że masz losową zmienną rozkładu prawdopodobieństwa Q. Ale twój przyjaciel Bob uważa, że ​​wynik pochodzi z rozkładu prawdopodobieństwa P. Stworzył optymalne kodowanie, które minimalizuje liczbę oczekiwanych bitów, których będzie musiał użyć, aby powiedzieć ci wynik. Ale ponieważ skonstruował kodowanie z P, a nie z Q, jego kody będą dłuższe niż to konieczne. Rozbieżność KL mierzy, jak długo będą kody.

Teraz powiedzmy, że ma monetę i chce opowiedzieć o sekwencji wyników, jakie otrzymuje. Ponieważ głowa i ogon są równie prawdopodobne, daje im oba kody 1-bitowe. 0 za głowę, 1 za ogon. Jeśli dostanie ogon, ogon, może wysłać 1 1 0 1. Teraz, jeśli jego moneta wyląduje na krawędzi, nie jest w stanie ci powiedzieć! Żaden kod, który ci wyśle, nie zadziała. W tym momencie dywergencja KL ulega załamaniu.

Ponieważ dywergencja KL ulega awarii, będziesz musiał albo użyć innej miary, albo innych rozkładów prawdopodobieństwa. To, co powinieneś zrobić, naprawdę zależy od tego, czego chcesz. Dlaczego porównujesz rozkłady prawdopodobieństwa? Skąd pochodzą twoje rozkłady prawdopodobieństwa, czy są one szacowane na podstawie danych?

Mówisz, że twoje rozkłady prawdopodobieństwa pochodzą w jakiś sposób z dokumentów w języku naturalnym i chcesz porównać pary kategorii.

Po pierwsze, poleciłbym symetryczną miarę pokrewieństwa. W przypadku tej aplikacji brzmi to tak, jakby A było tak samo podobne do B, jak B jest podobne do A.

Czy próbowałeś miary podobieństwa cosinus? Jest to dość powszechne w NLP.

Jeśli chcesz trzymać się KL, jedną rzeczą, którą możesz zrobić, to oszacować funkcję prawdopodobieństwa z obu dokumentów, a następnie zobaczyć, ile dodatkowych bitów potrzebujesz średnio dla każdego dokumentu. To jest (P || (P + Q) / 2 + Q || (P + Q) / 2) / 2

użytkownik1417648
źródło
Świetne wyjaśnienie, ale nieco mylące: sposób, w jaki opisujesz pierwszy akapit, nie jest KL (Q || P)?
Jurgen
8

W praktyce również natrafiłem na ten problem. W tym przypadku stwierdziłem, że podstawienie wartości 0 przez bardzo małą liczbę może powodować problemy. W zależności od użytej wartości wprowadzisz „odchylenie” w wartości KL. Jeśli używasz wartości KL do testowania hipotez lub innego zastosowania, które obejmuje próg, wówczas ta niewielka wartość może wpływać na wyniki. Odkryłem, że najskuteczniejszym sposobem radzenia sobie z tym jest rozważenie obliczenia KL tylko w oparciu o spójną przestrzeń hipotezy X_i, gdzie OBA P i Q są niezerowe. Zasadniczo ogranicza to domenę KL do domeny, w której obie są zdefiniowane, i pozwala uniknąć kłopotów przy użyciu KL do przeprowadzania testów hipotez.

concipiotech
źródło
Dzięki. To ciekawa propozycja. Zasadniczo próbuje również oprzeć P i Q na tym samym zestawie wyników. Spróbuję tego.
smwikipedia
Jeśli obliczę KL dla podzbioru danych, w którym zarówno P, jak i Q są niezerowe, czy muszę ponownie normalizować P i Q w tym podzbiorze? Lub po prostu użyj oryginalnej wartości prawdopodobieństwa? Myślę, że powinienem. W przeciwnym razie P i Q nadal nie są na tej samej podstawie.
smwikipedia
Właśnie próbowałem z twoją sugestią. P rozprowadza ponad 10 000 wyników, a Q także rozsyła ponad 10 000 wyników. Ale P i Q mają tylko wspólne wyniki 3K. Jeśli wykorzystam tylko typowe wyniki 3K do oszacowania różnicy między P i Q, nie sądzę, aby było to uzasadnione. Ponieważ ignorujemy wiele rzeczy. I tak przy okazji, wynik z tym podejściem jest zupełnie inny niż to, co otrzymuję, dodając małą liczbę (lub pseudo liczbę).
smwikipedia
Dodaj kontekst, pracuję nad eksperymentem NLP. Mam kilka kategorii dokumentów i chcę powiedzieć, jak blisko każda para kategorii jest ze sobą powiązana.
smwikipedia
5

Qi=0iQiQiQP . Jeśli przybliżenie przewiduje prawdopodobieństwo 0 dla zdarzenia, które ma prawdopodobieństwo dodatnie w rzeczywistości, wówczas doświadczysz nieskończonej niespodzianki przez pewien czas, a tym samym średnio nieskończonej niespodzianki.

Rozwiązaniem jest nigdy nie dopuszczać 0 lub 1 prawdopodobieństw w szacunkowych rozkładach. Zwykle osiąga się to przez jakąś formę wygładzania, taką jak wygładzanie Good-Turinga, wygładzanie Dirichleta lub wygładzanie Laplace'a.

Daniel Mahler
źródło