Типичная концепция набора

15

Я думал, что концепция типичного набора довольно интуитивна: последовательность длины будет принадлежать типичному набору A ( n ) ϵ, если вероятность выхода последовательности будет высокой. Таким образом, любая последовательность, которая была бы вероятна, была бы в A ( n ) ϵ . (Я избегаю формального определения, связанного с энтропией, потому что я пытаюсь понять это качественно.)nAϵ(n)Aϵ(n)

Однако я читал, что, в общем, наиболее вероятная последовательность не относится к типичному набору. Это сбило меня с толку.

Есть ли интуитивное определение типичного набора? Или это просто математический инструмент, который не имеет ничего общего со здравым смыслом?

Tendero
источник

Ответы:

13

Я знаю, что вы явно просили интуитивное объяснение и опустить формальное определение, но я думаю, что они скорее связаны, поэтому позвольте мне напомнить определение типичного набора:

X1,X2,...являютсяIIDслучайные величины p(x) , то типичный набор ( п ) ε относительно р ( х ) есть множество последовательностей ( х 1 , х 2 , . . . , х п ) х п со свойством 2 - n ( H (Aε(N)п(Икс)(Икс1,Икс2,,,,,ИксN)χN

(1)2-N(ЧАС(Икс)+ε)п(Икс1,Икс2,,,,,ИксN)2-N(ЧАС(Икс)-ε)
Это означаетчто при фиксированномε, типичный набор состоит из всех последовательностей чьи вероятностиблизкик2-NЧАС(Икс). Таким образом, чтобы последовательность принадлежала типичному набору, она должна иметь вероятность, близкую к2-NЧАС(Икс) , обычно это не так. Чтобы понять почему, позвольте мне переписать уравнение 1, применив к немуLограмм2 .

(2)ЧАС(Икс)-ε1Nжурнал2(1п(Икс1,Икс2,,,,,ИксN))ЧАС(Икс)+ε

Теперь типичное определение множества более непосредственно связано с понятием энтропии или, иначе говоря, со средней информацией о случайной переменной. Средний термин можно рассматривать в качестве образца энтропии последовательности, таким образом, типичный набор выполнен всех последовательности, которые дают нам количество информации , близкой к средней информации случайной величины Икс . Наиболее вероятная последовательность обычно дает нам меньше информации, чем в среднем. Помните, что чем ниже вероятность результата, тем выше будет информация, которую он нам дает. Чтобы понять, почему я приведу пример:

Предположим, что вы живете в городе, погода которого, скорее всего, будет солнечной и теплой, между 24 ° C и 26 ° C. Вы можете смотреть сводку погоды каждое утро, но вам будет плевать на это, я имею в виду, всегда солнечно и тепло. Но что, если однажды погода мужчина / женщина скажет вам, что сегодня будет дождливо и холодно, это изменит правила игры. Вы должны будете носить различную одежду, взять зонтик и делать другие вещи, которые вы обычно не делаете, поэтому метеоролог дал вам действительно важную информацию.

Подводя итог, интуитивное определение типичного набора состоит в том, что он состоит из последовательностей, которые дают нам объем информации, близкий к ожидаемому из источника (случайная величина).

diegobatt
источник
1
... а точнее $$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
Хорошо, но какова цель типичного набора, определенного таким образом? Ранее я думал, что мы создали понятие типичного набора, чтобы иметь интуитивное представление о САМОМ НАИБОЛЕЕМ подмножестве последовательностей, которое мы должны принять, чтобы убедиться, что мы «покрываем» (1 - \ eps)% случаев. Таким образом, выбор наиболее вероятной последовательности является очевидным выбором. Что мне не хватает?
tomwesolowski
12

Ответ Дигобатта хорошо объясняет, каков типичный набор. Этот ответ будет касаться другого вопроса ОП, повторяемого @tomwesolowski: почему вы определяете типичный набор таким образом, который может исключать наиболее вероятные элементы?

Короткий ответ: типичный набор - это прежде всего математический инструмент. Это было определено, чтобы помочь доказать что-то, и это определение является наиболее удобным для доказательства. Это хороший пример того, как теоретические потребности иногда могут превзойти интуитивные предпочтения в математике.

Типичный набор был определен отцом теории информации , Клодом Шенноном . Он хотел , чтобы определить , насколько эффективно можно было бы возможно кодировать поток символов из фиксированного алфавита, предполагая , что каждый символ является н.о.р. случайной выборкой из некоторого распределения. Его ключевые идеи заключались в следующем:

  1. Существует легко идентифицируемый, относительно небольшой набор «типичных» последовательностей, которые непропорционально часто появляются в потоке.
  2. Присваивая этот «типичный набор» последовательностей, кратчайшие кодировки дают оптимально эффективное кодирование (асимптотически, поскольку выходной поток увеличивается произвольно долго).

Типичный набор, обнаруженный Шенноном, состоит именно из последовательностей, чья самооценка , или «удивительность», примерно такая же, как и самооценка, ожидаемая в среднем для распределения источника потока. Такие последовательности являются «типичными» в том смысле, что их информация о среднем, но это определение неявно исключает те последовательности, которые имеют значительно меньше информации, чем среднее. Эти менее информативные последовательности также являются наиболее вероятными.

Как отмечает ОП, это не интуитивно привлекательно! На первый взгляд типичный набор звучит так, как будто он должен содержать все наиболее вероятные последовательности вплоть до некоторого порога. Это будет лучше представлять то, что обычно видят в потоке.

Но Шеннон не хотел наиболее «типичного» возможного типичного набора; он хотел тот, который позволил бы доказать результат, который он хотел доказать. Типичный набор, определенный Шенноном, гарантированно существует, он гарантированно будет небольшим, и он будет примерно таким же маленьким, как любой другой набор, который вы можете предложить, как указывает этот ответ . Добавление наиболее вероятных элементов делает набор более вероятным, что хорошо, но также увеличивает набор, что плохо. Если все, что вас волнует, - это сделать ваши доказательства, зачем исправлять то, что не сломано?

Если у вас другие цели, чем у Шеннона, ваша предпочтительная концепция типичности также может отличаться. Например, в кодировании Хаффмана наиболее вероятные символы (или последовательности символов) получают самые короткие коды. В определенном техническом смысле кодирование Хаффмана является оптимальным решением исходной проблемы Шеннона, и оно лучше отражает нашу интуицию о типичности. С другой стороны, определение типичности Шеннона более удобно для доказательства.

Павел
источник
1
Отличная аргументация и благодарность за хорошо выполненную работу по устранению разрыва между интуицией и определением. Я бы сказал, что это несоответствие происходит из-за недостатка языка в повседневной жизни, где типичное и среднее значение обычно означают одно и то же, но с точки зрения статистики типичное (в смысле вероятности, то есть моде) не обязательно совпадает со средним ожидаемое значение.
Эмиль
ЧАС(Икс)-εЧАС(Икс)+ε
@ Эмиль, я предполагаю, что автор сказал это так, потому что мы все согласились, что последовательности, содержащие больше информации (менее вероятные), не должны содержаться в типичном наборе.
tomwesolowski
1

Идея типичного набора неявно трактует конечные последовательности как мультимножества, то есть предполагает, что вы просто заботитесь о гистограмме каждой последовательности, например, вы рассматриваете все 10 последовательностей броска монеты с 7 головами и 3 хвостами как эквивалентные.

Представьте, что у вас очень предвзятая монета, скажем, п(ЧАС)знак равно+0,9, Это просто биномиальное распределение. Наиболее вероятная последовательность из 100 бросков - 100 голов, но есть только 1 последовательность из 100 голов. Есть экспоненциально много других последовательностей, которые содержат 10 хвостов, но они гораздо менее вероятны в отдельности. Наибольшее количество последовательностей - с половиной голов и половиной хвоста, но они еще менее вероятны. Таким образом, существует напряженность между вероятностью отдельных последовательностей и количеством эквивалентных последовательностей в классе. Максимальная вероятность достигается, когда частоты в последовательностях соответствуют вероятностям.

Важным результатом является то, что для достаточно длинных последовательностей почти все выбранные последовательности будут произвольно близки к ожидаемым частотам, то есть распределение становится чрезвычайно пиковым с увеличением длины рассматриваемых последовательностей.

Например заметил 105 бросить последовательности из п(ЧАС)знак равно+0,9 монета получит последовательности с 104+/-300 хвосты в 99% случаев, так как стандартное отклонение числа хвостов в последовательности составляет приблизительно 100. Вероятность всех голов незначительна, несмотря на то, что это наиболее вероятная специфическая последовательность.

Типичный набор представляет собой более общую, теоретически определенную версию этой идеи.

Дэниел Малер
источник
0

Согласно теореме 6.3 в этих примечаниях к лекции, независимо от того, берем ли мы подмножество последовательностей с наибольшей вероятностью или тех, которые близки к вероятности2-NЧАС(Икс) (из типового набора) мы должны взять примерно 2NЧАСчтобы убедиться, что выбранное подмножество содержит случайную последовательность с высокой вероятностью. Обычно мы берем типичные элементы набора, потому что мы можем легче связать его размер.

tomwesolowski
источник
1
Не могли бы вы объяснить, как это обращается к запросу «интуитивное определение типичного набора»?
whuber
Я не уверен, но это означало обратиться к «Тем не менее, я читал, что, в общем, наиболее вероятная последовательность не относится к типичному набору. Это сбило меня с толку». часть вопроса :)
tomwesolowski