Typisches Set-Konzept

14

Ich dachte, dass das Konzept einer typischen Menge ziemlich intuitiv ist: Eine Folge der Länge n würde zu der typischen Menge wenn die Wahrscheinlichkeit, dass die Folge herauskommt, hoch wäre. Jede mögliche Sequenz, die wahrscheinlich war, würde sich in . (Ich vermeide die formale Definition im Zusammenhang mit Entropie, weil ich versuche, sie qualitativ zu verstehen.) A ( n ) ϵAϵ(n)Aϵ(n)

Ich habe jedoch gelesen, dass im Allgemeinen die wahrscheinlichste Sequenz nicht zum typischen Satz gehört. Das hat mich sehr verwirrt.

Gibt es eine intuitive Definition einer typischen Menge? Oder ist es nur ein mathematisches Werkzeug, das nicht viel mit gesundem Menschenverstand zu tun hat?

Tendero
quelle

Antworten:

11

Ich weiß, dass Sie ausdrücklich um eine intuitive Erklärung gebeten haben und die formale Definition weggelassen haben, aber ich denke, dass sie ziemlich verwandt sind, also lassen Sie mich an die Definition der typischen Menge erinnern:

X1,X2,...istiidZufallsvariablen p(x) , danndie typische SatzAϵ(n) bezüglichp(x) ist der Satz von Sequenzen(x1,x2,...,xn)χn mit der Eigenschaft

(1)2n(H(X)+ϵ)p(x1,x2,...,xn)2n(H(X)ϵ)
Das bedeutetdass für eine festeϵ, ist die typische Menge aller Sequenzen zusammengesetzt deren Wahrscheinlichkeiten in derNähevon2nH(X). Damit eine Sequenz zur typischen Menge gehört, muss sie nur eine Wahrscheinlichkeit nahe bei haben2nH(X) ist dies normalerweise nicht der Fall. Um zu verstehen, warum, lassen Sie mich die Gleichung 1 umschreiben, indem Sielog2 daraufanwenden.

(2)H(X)ϵ1nlog2(1p(x1,x2,...,xn))H(X)+ϵ

Nun ist die typische Mengen-Definition direkter mit dem Konzept der Entropie verbunden, oder anders ausgedrückt, der Durchschnittsinformation der Zufallsvariablen. Der mittlere Term kann als Stichprobenentropie der Sequenz betrachtet werden, daher wird die typische Menge aus allen Sequenzen gebildet, die eine Informationsmenge ergeben, die der durchschnittlichen Information der Zufallsvariablen X . Die wahrscheinlichste Sequenz gibt uns normalerweise weniger Informationen als der Durchschnitt. Denken Sie daran, dass die Informationen, die wir erhalten, umso höher sind, je geringer die Wahrscheinlichkeit eines Ergebnisses ist. Um zu verstehen, warum ich ein Beispiel gebe:

Angenommen, Sie leben in einer Stadt, deren Wetter mit hoher Wahrscheinlichkeit sonnig und warm ist (zwischen 24 ° C und 26 ° C). Sie können den Wetterbericht jeden Morgen ansehen, aber es interessiert Sie nicht viel, ich meine, es ist immer sonnig und warm. Aber was ist, wenn dir eines Tages der Wettermann / die Wetterfrau sagt, dass es heute regnerisch und kalt sein wird, das ist ein Game Changer. Sie müssen andere Kleidung tragen, einen Regenschirm mitnehmen und andere Dinge tun, die Sie normalerweise nicht tun. Deshalb hat der Wettermann Ihnen wirklich wichtige Informationen gegeben.

Zusammenfassend lässt sich sagen, dass die intuitive Definition der typischen Menge aus Sequenzen besteht, die eine Informationsmenge liefern, die der erwarteten Menge der Quelle (Zufallsvariable) nahe kommt.

diegobatt
quelle
1
... oder vielmehr $$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, aber was ist der Zweck einer auf diese Weise definierten typischen Menge? Früher dachte ich, wir hätten eine Vorstellung von einer typischen Menge mit einer Intuition erstellt, die DIE KLEINSTE Teilmenge von Sequenzen ist, die wir verwenden müssen, um sicherzustellen, dass wir (1 - \ eps)% Fälle "abdecken". Auf diese Weise ist es naheliegend, die wahrscheinlichste Reihenfolge zu wählen. Was vermisse ich?
Tomwesolowski
10

Die Antwort von Diegobatt ist gut darin, intuitiv zu erklären, was das typische Set ist. Diese Antwort wird sich mit der anderen Frage des OP befassen, die von @tomwesolowski wiederholt wurde: Warum würden Sie die typische Menge so definieren, dass die wahrscheinlichsten Elemente ausgeschlossen werden?

Die kurze Antwort lautet, dass die typische Menge in erster Linie ein mathematisches Werkzeug ist. Es wurde definiert, um etwas zu beweisen, und diese Definition ist die bequemste für den Beweis. Es ist ein gutes Beispiel dafür, wie theoretische Bedürfnisse manchmal die intuitiven Vorlieben in der Mathematik übertreffen können.

Die typische Menge wurde vom Vater der Informationstheorie , Claude Shannon, definiert . Er wollte , um zu bestimmen , wie effizient man möglicherweise einen Strom von Symbolen aus einem festen Alphabet kodieren könnte, jedes Symbol unter der Annahme ist eine iid Stichprobe von einer Verteilung. Seine wichtigsten Erkenntnisse waren:

  1. Es gibt eine leicht zu identifizierende, relativ kleine Menge "typischer" Sequenzen, die im Stream überproportional häufig vorkommen.
  2. Wenn Sie diesen "typischen Satz" von Sequenzen mit den kürzesten Codierungen versehen, erhalten Sie eine optimal effiziente Codierung (asymptotisch, da die Ausgabe des Streams beliebig lang wird).

Die typische Menge, die Shannon entdeckt hat, setzt sich genau aus den Sequenzen zusammen, deren Selbstinformation oder "Überraschung" ungefähr der Selbstinformation entspricht , die im Durchschnitt für die Quellverteilung des Streams erwartet wird. Solche Sequenzen sind "typisch" in dem Sinne, dass ihre Informationen ungefähr durchschnittlich sind, aber diese Definition schließt implizit diejenigen Sequenzen aus, die signifikant weniger Informationen als durchschnittlich haben. Diese weniger informativen Sequenzen sind auch die wahrscheinlichsten.

Wie das OP feststellt, ist dies nicht intuitiv ansprechend! Das typische Set klingt so, als ob es die wahrscheinlichsten Sequenzen bis zu einem gewissen Schwellenwert enthalten sollte. Das würde besser repräsentieren, was normalerweise im Stream zu sehen ist.

Aber Shannon wollte nicht das "typischste" typische Set. er wollte einen, der es einfach machte, das Ergebnis zu beweisen, das er beweisen wollte. Es ist garantiert, dass die von Shannon definierte typische Menge existiert, dass sie klein ist und dass sie ungefähr so ​​klein ist wie jede andere Menge, die Sie vorschlagen, wie diese Antwort zeigt. Durch das Hinzufügen der wahrscheinlichsten Elemente wird die Menge wahrscheinlicher, was gut ist, aber es wird auch die Menge größer, was schlecht ist. Wenn Sie sich nur darum kümmern, Ihren Beweis zu erbringen, warum beheben Sie dann, was nicht kaputt ist?

Wenn Sie andere Ziele als Shannon verfolgen, ist möglicherweise auch Ihr bevorzugtes Konzept der Typizität anders. Beispielsweise erhalten bei der Huffman-Codierung die wahrscheinlichsten Symbole (oder Symbolsequenzen) die kürzesten Codes. In gewisser technischer Hinsicht ist die Huffman-Codierung die optimale Lösung für Shannons ursprüngliches Problem und fängt unsere Intuition über die Typizität besser ein. Andererseits eignet sich Shannons Definition von Typizität besser, um Dinge zu beweisen.

Paul
quelle
1
Hervorragende Argumentation und ein großes Lob bei der Bewältigung der Kluft zwischen Intuition und Definition. Ich würde sagen, dass diese Diskrepanz aufgrund eines alltäglichen Sprachmangels auftritt, bei dem typisch und durchschnittlich in der Regel dasselbe bedeuten, statistisch jedoch das Typische (im Sinne der Wahrscheinlichkeit, dh des Modus) nicht unbedingt das Gleiche wie der Durchschnitt ist , dh erwarteter Wert.
Emil
Eine Frage jedoch, wenn Sie sagen, dass die Definition diejenigen Sequenzen ausschließt, die "signifikant weniger Informationen als der Durchschnitt" aufweisen, sollte dies nicht "signifikant weniger oder mehr" sein, da die untere bzw. obere Schranke ist H(x)-ε und H(x)+ε?
Emil
@Emil, ich gehe davon aus, dass der Autor dies so ausgedrückt hat, weil wir uns alle einig waren, dass Sequenzen mit mehr Informationen (weniger wahrscheinlich) nicht in einer typischen Menge enthalten sein sollten.
Tomwesolowski
1

Bei der Vorstellung eines typischen Sets werden die Ergebnissequenzen implizit als Multisets behandelt, dh es wird davon ausgegangen, dass Sie sich nur um das Histogramm jeder Sequenz kümmern, dh, Sie betrachten alle 10 Münzwurfsequenzen mit 7 Köpfen und 3 Schwänzen als gleichwertig.

Stellen Sie sich vor, Sie haben eine sehr voreingenommene Münze p(H)=.9. Dies ist nur die Binomialverteilung. Die wahrscheinlichste Folge von 100 Würfen sind 100 Köpfe, aber es gibt nur eine Folge von 1 100 Köpfen. Es gibt exponentiell viel mehr Sequenzen, die 10 Schwänze enthalten, aber diese sind einzeln viel weniger wahrscheinlich. Die größte Anzahl von Sequenzen ist mit halben Köpfen und halben Schwänzen, aber diese sind noch weniger wahrscheinlich. Es besteht also eine Spannung zwischen der Wahrscheinlichkeit einzelner Sequenzen und der Anzahl äquivalenter Sequenzen in einer Klasse. Die maximale Wahrscheinlichkeit ist erreicht, wenn die Frequenzen in den Sequenzen mit den Wahrscheinlichkeiten übereinstimmen.

Das wichtige Ergebnis ist, dass für ausreichend lange Sequenzen fast alle abgetasteten Sequenzen in beliebiger Nähe zu den erwarteten Frequenzen liegen, dh die Verteilung wird mit zunehmender Länge der betrachteten Sequenzen extrem hoch.

Zum Beispiel beobachtet 105 werfen Sequenzen der P(H)=.9 coin will get sequences with 104+/300 tails 99% of the time since the standard deviation on the number of tails in a sequnce is approximately 100. The probability of all heads is negligible despite that being the most probable specific sequence.

Typical set is a more general, information theoretically defined version of this idea.

Daniel Mahler
quelle
0

Gemäß Satz 6.3 in diesen Vorlesungsskripten spielt es keine Rolle, ob wir eine Teilmenge von Sequenzen mit höchster Wahrscheinlichkeit oder solche mit einer Wahrscheinlichkeit in der Nähe von nehmen2-nH(X) (vom typischen Satz) müssen wir ungefähr nehmen 2nHum sicherzustellen, dass die ausgewählte Teilmenge eine zufällige Sequenz mit hoher Wahrscheinlichkeit enthält. Normalerweise nehmen wir typische Mengenelemente, weil wir die Größe davon leichter binden können.

Tomwesolowski
quelle
1
Could you explain how this addresses the request for "intuitive definition of typical set"?
whuber
I'm not sure, but it meant to address "However, I've read that, in general, the most likely sequence doesn't belong to the typical set. This confused me big time." part of question :)
tomwesolowski