avsmal Jan 13 2022 at 19:49

Как измерить количество информации?

16 min

31K

Образовательные проекты JetBrains corporate blogAlgorithms*Mathematics*Popular science

+36

Comments 20

kt97679 Jan 14 2022 at 00:30

Верещагин и Щепин нашлись здесь.

-1

Arvardan Jan 14 2022 at 13:42

Так сколько же информации в «Война и мир»?

avsmal Jan 14 2022 at 14:02

С математической точки зрения это просто константа, зависящая от выбора универсального способа описания.

На практике её можно попытаться оценить сверху при помощи сжатия. Если сжали до 2Мб, то можно считать, что информации там не более 2Мб. Для текстов это неплохо работает, а вот для числа $\pi$ будет работать плохо.

Arvardan Jan 14 2022 at 15:54

А есть модели описывающие информативность отдельно взятых слов или фраз?
Например, слово «стена» несет ведь информацию, как узнать сколько этой информации?

avsmal Jan 14 2022 at 18:39

Информативность относительно языка? Слово "стена" не несёт информацию само по себе, а количество передаваемой им информации зависит от контекста. Сомневаюсь, что такие (математические) модели существуют.

Sergey_Kovalenko Jan 14 2022 at 17:44

Спасибо за статью. Позвольте сделать несколько замечаний.

Указание префиксного кодирования в объяснении понятия энтропии - без сомнения методологически правильный ход, но... . Спросите у своего читателя, появилось ли у него интуитивное понимание откуда все-таки берется сумма "пэ-логарифм-пэ". Это важно, это то что останется в голове читателя через неделю или месяц спустя. Мне кажется этот момент должен быть центральным в подобной статье.

Второе.

К сожалению понятие "колмогоровской сложности" является относительным по отношению к языку описания и поэтому не несет никакой смысловой нагрузки для оценки "случайности" или "алгоритмичности" (конечных) символьных последовательностей. Для любой сколь угодно случайно выглядещей последовательности сколь угодно большой длины есть язык, в котором ее "колмогоровская сложность" равна нулю. Поэтому у Вас нет никаких логических оснований для вот этого места в тексте.

"Теперь предположим, что вам показали текст, который вас устроил (он с вашей точки зрения будет похож на "случайный"). Но ведь вероятность его появления тоже будет порядка $1/80^{2000}$ . Как же вы определяете, что один текст выглядит "случайным", а другой — не выглядит?

Колмогоровская сложность позволяет дать формальный ответ на этот вопрос. Если у текста отстутствует короткое описание (т.е. в нём нет каких-то закономерностей, которые можно было бы использовать для сжатия), то такую строку можно назвать случайной. И как мы увидели выше почти все строки имеют большую колмогоровскую сложность. Поэтому, когда вы видите строку с закономерностями, т.е. маленькой колмогоровской сложности, то это соответствует очень редкому событию. В противоположность наблюдению строки без закономерностей. Вероятность увидеть строку без закономерностей близка к 1."

Колмогоровскоая сложность - сырое, не проработанное понятие, которое имеет мало пользы и чаще всего (Ваша статья еще один пример в подтверждение) применяется не коректно. Ее вред еще и втом, что своим сущесвование она ложно закрывает еще не решенный современной наукой вопрос об объективной сложности конечных последовательностей и языков описания. Да, как я уже упоминал, для любой сколь угодно с виду сложной запутанной и длинной последовательности можно конструктивно предъявить язык, в котором длинна ее описания равна нулю. Но во в чем тонкость: любое естественное текстовое описание подобного языка скорее всего будет больше длины той последовательности, по которой он построен. Кажется что существования не относительного, а абсолютного пянятие сложности отсюда на лицо, но вот строго логически оформить эти идеи так никому и не удалось.

avsmal Jan 14 2022 at 18:29

Спасибо за содержательный комментарий.

Я не ставил перед собой задачу объяснить, откуда там в теоремах Шеннона для кодов возникает энтропия. Это почти нереально сделать в рамках такого обзора. При этом я постарался в меру своих возможностей объяснить, почему формула для энтропии именно такая. Не уверен, что это хорошо получилось, но это действильно важный момент, вы совершенно правы.
Про объяснение случайности для конечных объектов вы правы, что нет возможности определить случайность для конечных объектов без фиксации способа описания. Но я здесь и не пытаюсь определить случайность для конечных объектов, а только объясняю человеческую интуцию, которая неплохо позволяет отличать "случайные" и "неслучайные" тексты. Всё, что я хотел сказать, это то, что текст, который для конкретного человека кажется "неслучайным", это обычно текст имеющий какие-то завимости и закономерности с точки зрения конкретного человека, т.е. не текст не максимальной сложности относительно способа описания конкретного человека. В этом случае мы по сути зафиксировали способ описания тем, зафиксировали человека. Так что никакой проблемы тут нет. При этом определение случайной последовательности я даю только для бесконечных последовательностей.
На замечание про сырость и вредность позволю себе не отвечать. Отмечу только, что вопрос о существовании абсолютного понятия сложности не кажется мне таким очевидным.

Sergey_Kovalenko Jan 14 2022 at 19:40

Про формулу "пэ-логарифм-пэ" можно попробовать так.

Пусть есть длинная случайная последовательность из нулей и единиц, в которой частота единиц мала (n раз поставлен опыт, который дает "1" с малой вероятностью p и "0" с вероятностью 1-p, близкой к 1). При стандартном написании такая последовательность займет n бит. С другой стороны вы можете ее однозначно задать указав расстояния между началом и первой единицей а затем меду остальными единицами. Всего единиц будет примерно np, а характерное расстояние между ними 1/p. Чтобы записать число величиной потребуется -log(p) бит, таким образо все сообщение закодируется шишровкой примерно в -(np)log(p) бит.

Пусть теперь последовательность состоит из (очень) большого числа числа символов и каждый из них встречается редко. Будем кодирывать ее следующим образом: перечислим расстояния между пермым символом в алфавите, затем без каких либо разделительных знаков расстояние меду вторым ит так далее для всех символов. Поскольку длина исходной последовательности считается известной, мы ее легко можем восстановить по написанной последовательности чисел (когда сумма интервалов очередной раз превышает n, значит мы перешли к ледующему символу). Суммируя числа, выражающие интервальные расстояния между символами как раз и получаем сумму -(np)log(p) бит.

И так, величиной энтропии сообщение (асимптотически!) закодировать можно. Можно ли короче?
Нет! Доказательство не сложное - оно заключается в подсчете числа всех вохможных расстановок из примерно np_1 символов первого сорта, np_2 второго ... и взятие от этого всего логарифма. Таким образом смысл энтропии вероятностных сообщений - это (усредненная) длинна их эффективного закодированного аналога.

Тонким местом "доказательства" является подмена среднего логарифма логарифмом среднего, но для групп (асимпотически) больших чисел так делать можно, потому что "нелинейность" логарифмической функции на больших аргументах сходит почти на нет. Как доказать формуму, если частоты появления символов не являются бесконечно малыми? - Для любой последовательности вы можете перейти от исходного асфавита к "многобуквенным" сочетаниям символов, и если это сделать правильно, то вероятность наиболее частовстречаемого сочетания окажется меньше любого напередзаданного числа.

avsmal Jan 15 2022 at 19:56

Эти рассуждения в другом сеттинге. Речь в разделе про кодирование шла про коды, которые кодируют отдельно каждый символ. То, что вы доказываете в первом абзаце — это оценка колмогоровскую сложность строки длины n с np единицами (вы приводите некоторый способ кодирования, который к посимвольным кодам не имеют никакого отношения). То же самое можно получить, просто указав номер этой последовательности среди всех последовательностей длины n с np единицами. Таких последовательностей: $\binom{n}{np}$ . Для записи такого числа потребуется

$\log_2 \binom{n}{np} = \log_2 \frac{n!}{(np)!(n(1-p))!}\approx \log_2 \frac{\mathrm{poly}(n)\cdot (n/e)^n}{(np/e)^{np}(n(1-p)/e)^{n(1-p)}}$

Сокращает на (n/e)^n и получаем

$\log_2 \frac{\mathrm{poly}(n)}{p^{np}\cdot(1-p)^{n(1-p)}} = n\left(p\log_2\frac{1}{p} + (1-p)\log_2\frac{1}{1-p}\right) + O(\log n)$

В этом случае не нужно ничего предполагать про "характерное расстояние". В вашем рассуждении с этим есть проблема. Если для записи расстояния не хватило $-\log_2p$ символов, то не понятно, что с этим делать. Добавлять разделители?

Идею про отсутствие то, как определять, что начались числа для следующего числа я тоже не понял (когда сумма перевалила за ). Ведь при таком кодировании могут быть неоднозначности: пр n=5 последовательность 2, 1, 1... может разбиваться как (2,1) (1,..., так и как (2) (1,1,.... Либо нужно как-то кодировать количество чисел в самом начале.

Для символов это тоже обоющается (картинка из моего конспекта, переписывать лень)

Ваша нижняя оценка предлагает именно такое рассуждение выше с подсчётом числа последовательностей такого вида. Но она тоже по сути про колмогоровскую сложность, т.к. вы никак не пользуетесь тем, что это именно код определенного вида. Её с соответствующими оговорками и пояснениями можно применить к любому кодированию, но мы потеряем ту точность, что есть в соответствующей теореме Шеннона.

Sergey_Kovalenko Jan 16 2022 at 01:47

"Речь в разделе про кодирование шла про коды, которые кодируют отдельно каждый символ. То, что вы доказываете в первом абзаце — это оценка колмогоровскую сложность строки длины n с np единицами (вы приводите некоторый способ кодирования, который к посимвольным кодам не имеют никакого отношения)"

-Ваша статья вроде бы про количество информации, я привел рассуждения как кодировать длинное случайнонабранное сообщение целиком, причем асимптотически оптимально. Да, и нет тут никакой колмогоровской сложности, не вводите себя в заблуждение - у меня конечная, хоть и очень длинная последовательность сиволов. На конечном множестве конечных последовательностей средняя колмогоровская сложность может быть сколь угодно большой - для этого достаточно выбрать язык описания "нужной громодкости". Вы снова пытаетесь применять теоремы о колмогоровской сложности к конечным конструктивным объектам - она в них безсильна.

По поводу неодинаковости длин чисел, выражающих расстояния между символами - да молчаливо предполагался разделитель. Это не портит рассуждений, поскольку

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

2) для достаточно длинных (случайных) последовательностей с не слишком редкими частотами указан способ, как перейти к сочетаниям символов (кстати словарь сочетаний тоже должен быть "беспрефиксным") так, чтобы сочетания уже имели чрезвычайно малую частоту.

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

Применять понятие энтропии к неслучайным последовательностям нужно с большой осторожностью. Одно дело, когда я кладу орех в правый и левый кулак с вероятностью 1/2, другое - у меня в одном из кулаков орех, но вы не знаете в каком именно. Комбинаторная энтропия приписывает всем исходам равные вероятности, но ведь это по сути худший сценарий для сжатия длины сообщения о появившейся последовательности и только поэтому комбинаторная энтропия имеет право быть.

avsmal Jan 16 2022 at 11:26

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

Любой алгоритм кодирования битовых последовательностей задаёт верхнюю оценку на колмогороскую сложность с точностью до константы. В тексте поста есть такая теорема о связи энтропии и колмогоровской сложности.

Вы снова пытаетесь применять теоремы о колмогоровской сложности к конечным конструктивным объектам

И какую теорему я применил? )

она в них безсильна.

Не понял этого утверждения. Мы тут рассматриваем не конкретную длину, а асимптотическую оценку. Какая бы не была константа вылезающая из "нужной громодкости" при асимптотических рассуждениях (а тут речь именно про них и вы сами об это пишете) её вкад будет ничтожен.

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

У вас не получится сделать разделитель однобитным: для кодировки пары чисел суммарной длины нужно порядка $\log m + O(\log\log m)$ битов. Соответственно, на каждый разделитель потребуется порядка $O(\log\log(1/p))$ .

но для неслучайных последовательностей нужно делать оговорки. (...)
Применять понятие энтропии к неслучайным последовательностям

Не очень понимаю, что вы имеете в виду. Как вы сами правильно заметили для конечных последовательностей не получается формально определить понятие случайности. Это, кстати, и к вашему способу кодирования относится. Вы там пишете про "случайнонабранное сообщение", а по сути просто хотите сделать оценку в среднем.

Применять понятие энтропии к неслучайным последовательностям

Я его нигде и не применяю, т.к. энтропия определена не для последовательностей, а для случайных величин.

Sergey_Kovalenko Jan 16 2022 at 13:08

Докатились до разбирательства по пунктам, ну что ж, если надо.

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

Однако если как-то задана последовательнсть конструктивных объектов, такая что их колмогоровская сложность относительно хотя бы одного алгоритмически полного языка стремится к бесконечности, то их колмогоровская сложность и относительно любого другого алгоритмически полного языка тоже будет стремится к бесконечности, а отношение обоих сложностей будет стремится к 1. Мне кажется это единственный способ корретно приписать смысл вашего утвержения об "колмогоровской сложности (случайных?) последовательностей из np единиц и mp нулей". То есть, мне кажется, что вы должны были предполагать некоторую последовательность сообщений, длинна n которых стремится к бесконечности.

Теперь о чем говорю я.

Если вы мне назовете алфавит и зададите вероятности появления его символов в сообщении, а потом укажите любое "эпсилон" большее нуля, то я смогу назвать вам такое натуральное "эн" и такой способ записи натуральных чисел с разделителителем, что для сообщения любой длинны "эм" большей "эн" описанный мной способ кодирования даст математическое ожидание длины шифровки не более чем в (1+"эпсилон") раз превышающюю энтропию этого сообщения.

Да "эн" в действительности будет непрактично большим, однако я задам способ равномерно по всем длинным сообщениям, а не для какой-то конкретной их последовательности. Например, вы можете генерировать только сообщения какой-то определенной большой длинны "эм" - мое утверждение останется верным, а вот о колмогоровской сложности (ее математическом ожидании) на сообщениях этой конкретной длинны говорить не приходится - все зависит от языка описания. Оно, хоть и не может быть (всреднем) меньше энтропии (это все-таки больше теорема об энтропии: никакое описание в среднем не может быть меньше энтропии), однако подходящим выбором достаточно грамоздкого языка может быть сделано сколь угодно большим.

Да, насчет разделителя я был не точен, но ведь это не меняет сути дела: двойной логарифм (1/p) для достаточно малых p будет пренебрежимо мал по сравнению с "просто" логарифмом (1/p).

avsmal Jan 16 2022 at 14:01

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

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

Однако если как-то задана последовательнсть конструктивных объектов

Что значит "конструктивных" объектов? Все конечные строки конструктивны. Но для конечных строк это утверждение

отношение обоих сложностей будет стремится к 1.

просто не верно. Возьмём произвольную последовательность строк сложности и последовательность нулей (сложность будет $\log n$ ). Отношение сложностей будет в пределе будет бесконечным.

Мне кажется это единственный способ корретно приписать смысл вашего утвержения об "колмогоровской сложности (случайных?) последовательностей из np единиц и mp нулей". То есть, мне кажется, что вы должны были предполагать некоторую последовательность сообщений, длинна n которых стремится к бесконечности.

Про какое утверждение идёт речь? Про теорему в секции "Связь с энтропией Шеннона"? Это теорема. Ничего про случайность там нет. Теорема говорит о том, что колмогоровская сложность любой строки такого вида длины ограничена $nh(p) + O(\log n)$ (константа в O общая для всех строк и не зависит ). Докательство я привёл двумя комментариями выше.

Если вы мне назовете алфавит ... (1+"эпсилон") раз превышающюю энтропию этого сообщения.

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

Да "эн" в действительности будет непрактично большим, однако я задам способ равномерно по всем длинным сообщениям, а не для какой-то конкретной их последовательности. Например, вы можете генерировать только сообщения какой-то определенной большой длинны "эм" - мое утверждение останется верным, а вот о колмогоровской сложности (ее математическом ожидании) на сообщениях этой конкретной длинны говорить не приходится - все зависит от языка описания.

Вы как-то смешиваете ваш способ кодирования и колмогоровскую сложность, что я не могу понять, что вы мне хотите доказать. Вы говорите, что начиная с некоторого средняя длина кода будет $nH(1+\epsilon).$ Но ровно такое же утверждение верно и для колмогоровской сложности. Единственная разница, что , начиная с которого это будет выполняться, сложно задать контретно. Для вычисления придётся запрограммировать генератор такой последовательности на машине Тьюринга.

это все-таки больше теорема об энтропии: никакое описание в среднем не может быть меньше энтропии

В вашей формулировке два понятия: описание и энтропия. Как вы решили, что это формулировка больше об энтропии, чем об описаниях?)

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

Ещё раз повторюсь, что способ описания не является параметром.

avsmal Jan 16 2022 at 14:44

Да, насчет разделителя я был не точен, но ведь это не меняет сути дела: двойной логарифм (1/p) для достаточно малых p будет пренебрежимо мал по сравнению с "просто" логарифмом (1/p).

И всё же тут нужно быть аккуратным. Если в вашем способе кодирования вы добавляете разделитель на каждый символ, то в сумме получится $O(n\log\log n)$ (то, что "характерная" длина промежутка равна 1/p, не исключает возможности, что будет много промежутков порядка ). А добавка такого размера уже может быть сравнима nH(...) . Энтропия может быть очень маленькой и поэтому добавлять что-то на каждый символ — не самая хорошая идея. Вполне возможно, что если аккуратно всё посчитать и применить неравенство Йенсена, то всё сойдётся, но мне не кажется это совсем уж очевидным.

Sergey_Kovalenko Jan 16 2022 at 21:49

Я вроде бы точно описал про стреление к 1: вы берете любую последовательность строк, такую, что хотябы относительно одного алгоритмически полного языка ее сложность сремится к бесконечности (не одну строку, а последовательность строк), тогда относительно другого алгоритмически полного языка ее сложность растет асимптотически так же быстро (оношение сложностей строк последовательности, вычисленных для двух языков стремится к 1).

Касатеьно второго пункта я имел ввиду ваше утверждение в ответе на мой комментарий о (средней) сложности строки из np и nq нулей. Да, если вы фиксировали (достаточно выразительный) язык, то для достаточно больших n это утверждение верно, но не для всех n.

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

Наш спор больше идейный - так за слова цепляемся. Но если по существу то он об идее, почему один конечный текст выглядит случайно, а другой нет. Мой тезис заключается в том, что колмогоровская сложность в своем рафинированном виде никак не может помочь на него ответить. Всегда есть машина Тьюринга, которая напечатает данный конкретный текст "на пустом" входе.

avsmal Jan 16 2022 at 22:42

Я вроде бы точно описал про стреление к 1 ....

Да, тут я неправильно понял ваше утверждение.

то для достаточно больших n это утверждение верно, но не для всех n.

Верно для всех начиная с некоторого момента (момент зависит от $\epsilon$ ). Точно так же ваше утверждение про среднюю длину вашего кодирования верно не для любого , а начиная с некоторого момента:

... я смогу назвать вам такое натуральное "эн" и такой способ записи натуральных чисел с разделителителем, что для сообщения любой длинны "эм" большей "эн" описанный мной способ кодирования даст математическое ожидание длины шифровки не более чем в (1+"эпсилон") раз превышающюю энтропию этого сообщения.

Мой тезис заключается в том, что колмогоровская сложность в своем рафинированном виде никак не может помочь на него ответить.

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

Всегда есть машина Тьюринга, которая напечатает данный конкретный текст "на пустом" входе.

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

Рассмотрим следующий эксперимент. Возьмём двух человек, Алису и Боба. Сгенерируем "настоящий" случайный текст, покажем его Алисе и просим её запомнить. После этого возьмём новый листок со "случайным" текстом, покажем его обоим игрокам и попросим каждого сказать, верит ли он/она, что этот текст получен в результате случайного набора на клавиатуре. Если второй текст совпадает с первым, то Боб скорее всего скажет, что текст похож на случайный (т.к. первый был случайным), а Алиса скажет, что она только что видела точно такой же текст, поэтому не верит, что именно он получился в результате случайного набора. Это и соответствует тому, что в её способе описания этот текст имеет очень короткое описание "такой же, как мне показали до этого".

avsmal Jan 16 2022 at 23:00

Отвечаю на вопрос, который не понял сразу.

То есть, мне кажется, что вы должны были предполагать некоторую последовательность сообщений, длинна n которых стремится к бесконечности.

Нет, последовательность здесь не нужна. В том виде, в котором эта теорема записана, она верна для произвольной строки такого вида. Давайте сформулирую со всеми кванторами.

Теорема. Существует константа такая, что для любогo $p\in [0,1]$ , любого натурального и битовой строки с $\lceil np\rceil$ единицами выполняется: $K(x) \le n\cdot h(p) + C\cdot(1+\log n)$ , где $h(p) = - p\log p - (1-p)\log(1-p)$ .