Typowa koncepcja zestawu

15

Pomyślałem, że koncepcja typowego zestawu jest dość intuicyjna: sekwencja długości należałaby do typowego zestawu jeśli prawdopodobieństwo wystąpienia sekwencji byłoby wysokie. Tak więc każda sekwencja, która prawdopodobnie byłaby w . (Unikam formalnej definicji związanej z entropią, ponieważ staram się ją zrozumieć jakościowo.) $n$ $A_\epsilon ^{(n)}$ $A_\epsilon ^{(n)}$

Jednak przeczytałem, że generalnie najbardziej prawdopodobna sekwencja nie należy do typowego zestawu. To mnie bardzo zamieszało.

Czy istnieje intuicyjna definicja typowego zestawu? A może to tylko matematyczne narzędzie, które nie ma wiele wspólnego ze zdrowym rozsądkiem?

entropy intuition information-theory

— Tendero
źródło

13

Wiem, że wyraźnie poprosiłeś o intuicyjne wyjaśnienie i pominięcie formalnej definicji, ale myślę, że są one raczej powiązane, więc pozwól mi przypomnieć definicję typowego zestawu:

$X_1, X_2 ,...$ są to zmienne losowe a następnie typowy zestaw w odniesieniu do jest zbiorem sekwencji z właściwością oznacza to, że dla stałego , typowy zestaw składa się ze wszystkich sekwencji w którym prawdopodobieństwa Close do . Aby sekwencja należała do typowego zestawu, jej prawdopodobieństwo musi być zbliżone do $\sim$ $p(x)$ $A_\epsilon^{(n)}$ $p(x)$ $(x_1,x_2,...,x_n) \in \chi^n$

\begin{matrix} (1) & 2^{- n (H (X) + ϵ)} \leq p (x_{1}, x_{2}, . . ., x_{n}) \leq 2^{- n (H (X) - ϵ)} \end{matrix}

$2^{-n(H(X)+\epsilon)}\le p(x_1,x_2,...,x_n) \le 2^{-n(H(X)-\epsilon)} \tag{1}$

ϵ

$\epsilon$

2^{- n H (X)}

$2^{-nH(X)}$

2^{- n H (X)}

$2^{-nH(X)}$ , zwykle tak nie jest. Aby zrozumieć dlaczego, pozwól mi przepisać równanie 1, stosując na nim .

l o g_{2}

$log_2$

\begin{matrix} (2) & H (X) - ϵ \leq \frac{1}{n} \log_{2} (\frac{1}{p (x_{1}, x_{2}, . . ., x_{n})}) \leq H (X) + ϵ \end{matrix}

$H(X)-\epsilon\le \frac{1}{n}\log_2\left(\frac{1}{p(x_1,x_2,...,x_n)}\right) \le H(X)+\epsilon \tag{2}$

Teraz typowa definicja zbioru jest bardziej bezpośrednio związana z pojęciem entropii lub inaczej mówiąc, średnią informacją zmiennej losowej. Bliski termin może być traktowane jako próbki entropii sekwencji, więc typowy zestaw jest wykonany przez wszystkich sekwencji, które dają nam pewną ilość informacji zbliżona do średniej informacji o zmiennej losowej . Najbardziej prawdopodobna sekwencja zwykle daje nam mniej informacji niż średnia. Pamiętaj, że im niższe jest prawdopodobieństwo wyniku, tym wyższa będzie informacja, jaką nam przedstawi. Aby zrozumieć, dlaczego podam przykład: $X$

Załóżmy, że mieszkasz w mieście, którego pogoda jest prawdopodobnie słoneczna i ciepła, między 24 ° C a 26 ° C. Możesz oglądać prognozę pogody każdego ranka, ale nie przejmowałbyś się tym, to znaczy, zawsze jest słonecznie i ciepło. Ale co, jeśli któregoś dnia pogoda / mężczyzna / kobieta powie ci, że dziś będzie deszczowo i zimno, to zmieniarka gier. Będziesz musiał użyć różnych ubrań, wziąć parasol i robić inne rzeczy, których zwykle nie robisz, więc człowiek od pogody udzielił ci naprawdę ważnych informacji.

Podsumowując, intuicyjna definicja typowego zestawu polega na tym, że składa się on z sekwencji, które dają nam informacje zbliżone do oczekiwanego źródła (zmienna losowa).

— diegobatt
źródło

1

... a raczej $$H(X)-\epsilon\le \frac{1}{n}log_2(\frac{1}{p(x_1,x_2,...,x_n)}) \le H(X)+\epsilon \tag{2}$$...

— Cbhihe,

OK, ale jaki jest zatem cel typowego zestawu zdefiniowanego w ten sposób? Wcześniej myślałem, że stworzyliśmy pojęcie typowego zestawu, aby mieć intuicję, którą NAJMNIEJSZY podzbiór sekwencji musimy podjąć, aby upewnić się, że „pokrywamy” (1 - \ eps)% przypadków. W ten sposób wybór najbardziej prawdopodobnej sekwencji jest oczywistym wyborem. czego mi brakuje?

— tomwesolowski

12

Odpowiedź Diegobatta dobrze wyjaśnia intuicyjnie, jaki jest typowy zestaw. Ta odpowiedź odniesie się do drugiego pytania OP, powtórzonego przez @tomwesolowski: dlaczego zdefiniowałbyś typowy zestaw w sposób, który mógłby wykluczyć najbardziej prawdopodobne elementy?

Krótka odpowiedź jest taka, że typowy zestaw jest przede wszystkim narzędziem matematycznym. Został zdefiniowany, aby pomóc coś udowodnić, a ta definicja jest najwygodniejsza dla dowodu. Jest to dobry przykład tego, jak potrzeby teoretyczne mogą czasem przebijać intuicyjne preferencje matematyczne.

Typowy zestaw został zdefiniowany przez ojca teorii informacji , Claude'a Shannona . Chciał, aby ustalić, jak skutecznie można by ewentualnie kodować strumień symboli z ustalonym alfabetem, przy założeniu każdy symbol jest iid losowa próbka z jakiejś dystrybucji. Jego kluczowe spostrzeżenia były następujące:

Istnieje łatwy do zidentyfikowania, stosunkowo niewielki zestaw „typowych” sekwencji, które pojawiają się nieproporcjonalnie często w strumieniu.
Przypisanie tego „typowego zestawu” sekwencji najkrótszych kodowań daje optymalnie wydajne kodowanie (asymptotycznie, ponieważ wyjście strumienia rośnie dowolnie długo).

Typowy zestaw, który odkryła Shannon, składa się właśnie z sekwencji, których samoinformacja , czyli „zaskakująca”, jest mniej więcej taka sama, jak oczekiwana średnio informacja o dystrybucji źródła w strumieniu. Takie sekwencje są „typowe” w tym sensie, że ich informacje dotyczą średniej, ale ta definicja domyślnie wyklucza te sekwencje, które mają znacznie mniej informacji niż średnia. Te mniej pouczające sekwencje są również najbardziej prawdopodobne.

Jak zauważa OP, nie jest to intuicyjnie atrakcyjne! Na jego twarzy typowy zestaw brzmi, jakby zawierał wszystkie najbardziej prawdopodobne sekwencje do pewnego progu. To lepiej reprezentuje to, co zwykle widać w strumieniu.

Ale Shannon nie chciał najbardziej „typowego” możliwego zestawu; chciał takiego, który ułatwi udowodnienie wyniku, który chciał udowodnić. Typowy zestaw zdefiniowany przez Shannona gwarantuje, że istnieje, gwarantuje, że jest mały i gwarantuje, że będzie mniej więcej tak mały, jak każdy inny zestaw, który możesz zaproponować, jak wskazuje ta odpowiedź . Dodanie najbardziej prawdopodobnych elementów sprawia, że zestaw jest bardziej prawdopodobny, co jest dobre, ale także zwiększa zestaw, co jest złe. Jeśli zależy Ci tylko na wykonaniu dowodu, po co naprawiać to, co nie jest zepsute?

Jeśli masz inne cele niż Shannon, twoja preferowana koncepcja typowości może być również inna. Na przykład w kodowaniu Huffmana najbardziej prawdopodobne symbole (lub sekwencje symboli) otrzymują najkrótsze kody. W pewnym sensie technicznym kodowanie Huffmana jest optymalnym rozwiązaniem pierwotnego problemu Shannona i lepiej oddaje naszą intuicję dotyczącą typowości. Z drugiej strony definicja typowości Shannona jest wygodniejsza do udowodnienia.

— Paweł
źródło

1

Doskonałe rozumowanie i uznanie za dobrze wykonaną pracę, wypełniając lukę między intuicją a definicją. Powiedziałbym, że ta rozbieżność występuje z powodu niedociągnięcia językowego w codziennym życiu, w którym typowe i średnie zwykle oznaczają to samo, ale pod względem statystycznym typowe (w sensie prawdopodobieństwa, tj. Tryb) niekoniecznie jest takie samo jak średnia , tj. wartość oczekiwana.

— Emil

Jedno pytanie, gdy mówisz, że definicja wyklucza te sekwencje, które mają „znacznie mniej informacji niż średnia”, nie powinno być „znacznie mniej lub więcej”, ponieważ dolna i górna granica to odpowiednio i ?

H (x) - ε

$H(x)-\varepsilon$

H (x) + ε

$H(x)+\varepsilon$

— Emil

@Emil, zakładam, że autor powiedział to w ten sposób, ponieważ wszyscy zgodziliśmy się, że sekwencje zawierające więcej informacji (mniej prawdopodobne) nie powinny być zawarte w typowym zestawie.

— tomwesolowski

1

Idea typowego zestawu domyślnie traktuje sekwencje wynikowe jako multisets, tzn. Zakłada, że zależy ci na histogramie każdej sekwencji, np. Bierzesz pod uwagę wszystkie 10 sekwencji rzutu monetą z 7 główkami i 3 ogonami jako równoważne.

$p(H) = .9$

Ważnym rezultatem jest to, że w przypadku wystarczająco długich sekwencji prawie wszystkie próbkowane sekwencje będą arbitralnie zbliżone do oczekiwanych częstotliwości, tj. Rozkład staje się wyjątkowo szczytowy wraz ze wzrostem długości rozważanych sekwencji.

$10^5$ $P(H)=.9$ $10^4{+/-}300$

Typowy zestaw to bardziej ogólna, teoretycznie zdefiniowana wersja tego pomysłu.

— Daniel Mahler
źródło

0

$2^{-nH(X)}$ $2^{nH}$

— tomwesolowski
źródło

1

Czy mógłbyś wyjaśnić, w jaki sposób rozwiązuje to żądanie „intuicyjnej definicji typowego zestawu”?

— whuber

Nie jestem pewien, ale miało to na celu odniesienie się do „Jednak przeczytałem, że generalnie najbardziej prawdopodobna sekwencja nie należy do typowego zestawu. To mnie bardzo pomieszało”. część pytania :)

— tomwesolowski