Энтропия и WinRAR

    image
    Понятие энтропии используется практически во всех областях науки и техники,
    от проектирования котельных до моделей человеческого сознания.
    Основные определения как для термодинамики, так и для динамических систем и способы вычисления понять не сложно. Но чем дальше в лес — тем больше дров. Например, недавно выяснил (благодаря Р. Пенроуз, «Путь к реальности», стр 592-593), что для жизни на Земле важна не просто солнечная энергия, а её низкая энтропия.

    Если ограничится простыми динамическими системами или одномерными массивами данных (которые могут быть получены как «след» движения системы), то и тогда можно насчитать минимум три определения энтропии как меры хаотичности.
    Самое глубокое и полное из них (Колмогорова-Синая) можно наглядно изучить,
    используя программы — архиваторы файлов.

    Введение

    Упоминая информационную энтропию, нередко просто приводят «волшебную» формулу Шеннона:
    image
    где N — количество возможных реализаций, b — единицы измерения (2 — биты, 3 — триты,..), pi — вероятности реализаций.
    Разумеется, всё не так просто (зато интересно!). Для первого (а также второго, и даже третьего) знакомства, рекомендую ничуть не устаревшую книгу А.Яглом, И.Яглом «Вероятность и информация», 1973.
    В качестве ответа на «детский» вопрос: "Что же означает число, полученное по формуле?"
    подойдёт такая наглядная иллюстрация.

    Пусть имеется N = 16 клеток, одна из которых помечена крестиком:

    [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [x] [ ] [ ] [ ] [ ]

    Выбор случаен; вероятность того, что помечена i-тая клетка равна pi = 1/16
    Энтропия Шеннона равна

    А теперь представим себе игру; один игрок рисует клетки, ставит крестик и сообщает второму только
    количество клеток. Второй должен узнать, какая из них помечена и задаёт вопросы;
    но первый будет отвечать только «Да» или «Нет».
    Сколько (минимум!) вопросов надо задать, чтобы узнать, где крестик?
    Ответ — "4". Во всех подобных играх минимальное число вопросов будет равно информационной энтропии.
    При этом не имеет значения, какие вопросы задавать. Пример правильной стратегии —
    разделить клетки пополам (если N — нечётное, то с избытком/недостатком в 1 клетку) и спросить:
    «Крестик в первой половине?» Узнав, что в такой-то, делим и её пополам и т.д.

    Другой вроде «наивный», но глубокий вопрос: почему в формуле Шеннона присутствует логарифм?
    А что такое, собственно, логарифмическая функция? Обратная показательной… А что такое показательная?
    На самом деле, строгие определения даются в курсе матанализа, но они совсем не сложные.
    Часто бывает, что увеличивая «вход» в разы, мы получаем «выход» лишь на сколько-то единиц больше.
    Огюстен Коши доказал, что уравнение

    f(x · y) = f(x) + f(y) x,y>0

    имеет только одно непрерывное решение; это и есть логарифмическая функция.
    Представим теперь, что мы проводим два независимых испытания; количество исходов у них n и m, все они равновероятны (например, бросаем одновременно игральную кость и монету; n = 6, m=2)
    Очевидно, число исходов двойного опыта равно произведению n · m.
    Неопределённости же опытов складываются; и энтропия, как мера этой неопределённости, должна
    удовлетворять условию h(m · n) = h(m) + h(n), т.е. быть логарифмической.

    Энтропия Колмогорова-Синая

    Строгое определение этого фундаментального понятия довольно сложно для понимания.
    Подойдём к нему постепенно;
    нашим «фазовым пространством» будут одномерные массивы натуральных чисел.
    Например, десятичные цифры числа «Пи»: {3, 1, 4, 1, 5, 9, 2, 6,...}
    На самом деле, к такому виду можно привести любые данные (с потерями, конечно).
    Достаточно весь диапазон значений разбить на N интервалов и при попадании в k-тый интервал записывать число k (как при семплинге звука).
    Насколько случайна, стохастична та или иная последовательность?
    Информационная энтропия, конечно, является хорошим кандитатом на «измеритель хаоса».
    Нетрудно доказать, что она максимальна, когда все вероятности появления различных чисел равны.

    Но дальше начинаются трудности, о которых я упоминал в предыдущем посте.
    Например, массив ...010101010101010101… имеет максимальную энтропию, будучи наименее случайной последовательностью из 0 и 1.
    Если данные изначально не цифровые (звук, картинки), то конвертировать их в числа от 0 до N можно разными способами. А вероятности в числовом массиве можно мерить не только для отдельных элементов, но и для пар, троек, нечётных по порядку и т.д.
    Что ж, раз вариантов много, используем их все!
    Будем отображать «подопытный» массив всевозможными способами — в различных системах счисления, разбивая на пары и тройки и т.д. Очевидно, его размер L и энтропия Шеннона H будут зависеть от способа отображения.
    Например, считая его цельным, неделимым объектом, получим L = 1, H = 0.
    Учитывая, что H растёт с увеличением L, введём величину



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

    Архивация и энтропия

    О методах и алгоритмах сжатия информации на Хабре рассказывалось не раз,
    habrahabr.ru/post/142242
    habrahabr.ru/post/132683
    не говоря уже об оригинальных источниках.
    В своё время возможность сжатия до 50% с полным восстановлением произвела на меня шокирующее впечатление.
    Не менее удивлён был и недавно, когда узнал, что строго доказана связь степени сжатия данных с их энтропией Колмогорова-Синая. Интуитивно это понятно — чем более упорядочены данные, тем больше возможностей для сжимающей кодировки.
    Однако строгое математическое рассмотрение не всегда подтверждает «здравый смысл»;
    и хотя статьи на эту тему довольно заковыристые основная — ещё и платная), поверим теоретикам, что всё законно и приступим к опытам.

    Создадим данные 4-х видов:
    • десятичные цифры числа Пи (π)
    • ГПСЧ Wolfram Mathematica (Random)
    • самый яркий и простой образец детерминированного хаоса — логистическое отображение (Logistic)
    • массив из одних «1» (Const)
    • некая глюковатая формула, генерирующая на первый взгляд случайные числа (Map)

    Разумеется, мы можем вычислить энтропии по формуле Шеннона (встроена в Mathematica как Entropy[]).
    Однако, как и говорилось выше, результат будет сильно зависеть от системы счисления, формы представления данных и т.п.
    Вот, например, график энтропий логистического для всё увеличивающегося объёма данных:



    Не очень понятно, стремится ли энтропия к определённому значению при увеличении размера массива.
    А теперь попробуем мерить энтропию с помощью сжатия. Для каждого примера наделаем массивы разных размеров и построим графики отношений «размер после сжатия/размер до сжатия» в зависимости от длины массива (честно говоря, использовал не вынесенный в заголовок WinRAR, а встроенный zip-архиватор Mathematica)



    Вот это уже правильные, «винрарные» картинки! Хорошо видно, как коэффицент сжатия выходит на предельное значение, которое и характеризует меру хаотичности исходных данных.
    Напомню, что чем менее упорядоченны данные — тем труднее их кодировать.
    Наибольший остаточный объём — у цифр числа Пи и случайных чисел (почти слившиеся синий и красный
    графики).

    Пример развития идеи.

    Вместо «скучных» чисел возьмём осмысленные литературные тексты. Степень их стохастичности и способы сжатия — весьма обширная тема (см. например )
    Здесь мы просто убедимся, что измерения с помощью архиваторов также имеют смысл.
    В качестве примеров взяты примерно равные отрывки русских сказок, духовных бесед Джидду Кришнамурти и речей Л.И. Брежнева.



    Интересно получилось — для малых отрывков степень сжатия (т.е. упорядоченность) текстов заметно отличается, при этом лидирует Брежнев(!) Но для больших массивов энтропия текстов примерно одинакова.Что сие означает и всегда ли так — неизвестно.
    Поделиться публикацией

    Комментарии 28

      0
      Интересно, а сравнение энтропии исходников программ о чём-нибудь скажет?
        +1
        Хе-хе… думаю, да. Только анализировать надо не по буквам, а по семантическим единицам — операторам,
        переменным.
        Очевидно, прога, в которой все операторы и объявленные переменные встречаются равновероятно — это реальный хаос!
          +4
          Смотря какой хаос. Если распределение будет близко к гауссу, то это уже не детерминированный хаос, а вероятностная модель, для нее Энтропия Колмогорова — Синая по теории должна к бесконечности стремиться. Для систем с детерминированным хаосом она положительна. Вообще в нелинейной динамике, если система описывается большим числом степеней свободы и на определенном этапе нельзя получить ее описание в конечном числе степеней свободы, говорят, что это Джокер, в противном случае — Русло.
            +4
            Не всё понял из того что вы сказали, но глядя на ваш ник, в вопросах хаоса судя по всему спорить с вами бессмысленно :)
            0
            Тогда порядок — это прога, в которой половина кода — это if-else :)
              0
              Как раз хороший код не должен сильно жаться. А код с кучей дубликатов и повторов — должен.
          +1
          Для динамических систем несколько проще подсчитать показатели Ляпунова (которые связаны с КС энтропией)
          А, если не секрет, как Вы КС энтропию считали и для каких систем?
            0
            Конечно, связь показателей Ляпунова с КС — гораздо более прямая.
            По крайней мере, я реально с выводом разобрался
            (а вот доказательства связи сжатия и КС не очень понял, скорее, поверил).

            Но то, что ляпуновские показатели проще считать — совсем не факт.
            (С алгоритмом Бенеттина долго возился, но сделал на Mathematica).
            Для детального анализа, они, конечно, нужны. А для общего сравнения разных данных
            метод архивации очень симпатичен.

            Системы самые любимые — это биллиарды
              +1
              Алгоритм Бенеттина, это если у вас система в аналитическом виде известна
              Если у вас временной ряд или вектор, то используется алгоритм Вольфа.
                0
                А можно на Вольфа ссылку? Честно говоря, «готовые» временные ряды по Ляпунову еще не анализировал.
                  0
                  Конечно — метод
                  Там отличие от Бенеттина незначительное, если есть реализация бенеттина, то допилить можно мгновенно
                  Но вам еще нужно будет восстановить сам аттрактор методом задержек, найти размерность пространства и т.д., а это уже искусство и шаманство )
                    0
                    Спасибо, действительно, хорошо написано!
            0
            Последние значения наверняка зависят от количества авторов.
            • НЛО прилетело и опубликовало эту надпись здесь
                0
                Конечно, анализ текста по буквам — это детский сад. Но серьёзных работ по сжатию текстов на уровне семантики не нашёл.
                  0
                  Понятие энтропии используется практически во всех областях науки и техники,
                  от проектирования котельных до моделей человеческого сознания.

                  О! А можете дать ссылки на несколько моделей человеческого сознания?
                    0
                    Вот, пожалуйста.
                    А энтропия и информация мощно используется в модели Джулио Тонони «Information integration».
                    Мечтаю о ней пост на Хабре написать.
                      +1
                      Мечтаю о ней пост на Хабре написать.

                      Плюсанул карму. Пишите :-) С удовольствием почитаю…
                    +2
                    Подпишите оси координат, если не трудно.
                      0
                      ОК
                        0
                        С единицами измерения, если не затруднит.
                          0
                          Сегодня уже не успею… Абсциссы — это количество «кусков» данных, ~ 20 кБ кусок
                          (а для текстов точно сейчас уже не смогу сказать). Энтропия в бит/символ, степень сжатия — безразмерна.
                      +4
                      Сколько (минимум!) вопросов надо задать, чтобы узнать, где крестик?
                      Ответ — «4». Во всех подобных играх минимальное число вопросов будет равно информационной энтропии.
                      При этом не имеет значения, какие вопросы задавать.


                      Правильно будет:

                      Сколько (минимум!) вопросов надо задать, чтобы гарантированно узнать, где крестик?
                      Ответ — «4». Во всех подобных играх минимальное число вопросов будет равно информационной энтропии.
                      При этом не имеет значения, какие вопросы задавать.


                      Очень даже имеет значение, какие вопросы задавать. Просто представьте, если задавать
                      вопросы типа: «а в первой клетке есть? а во второй есть?.. а в 16-й есть?»

                        0
                        Да, неточно выразился. Под «любыми» имелись в виду оптимальные стратегии,
                        а они могут быть разными, например вопросы о делимости.
                          0
                          Да все поняли.
                          +1
                          Спасибо за интересную статью.
                          Возможно дополнением к теме, будет этот пост: habrahabr.ru/post/171759/ где я рассказывал о применении энтропии в машинном обучении. А также, ещё один вариант вывода формулы энтропии Шеннона :-)
                            +1
                            Это поиск по Хабру подвёл. Обязательно дал бы ссылку, но почему-то поиск по слову «энтропия» не выдал её.
                            +1
                            Интересная статья, но попробуйте померить степень стахостичности не от осмысленных произведений, а от случайного набора слов (перемешайте случайно слова в имеющихся источниках). Также можно попробовать перемешать имеющиеся в источниках буквы. Есть подозрение, что результат будет аналогичный :), и зависит он не от смысла произведений, а от количества букв в алфавите(можно перемешать буквы и мерить степерь сжатия, как функцию от используемых букв в тексте) и от количества каждой конкретной буквы в тексте. Но это лишь предположение, конечно :)

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

                            Самое читаемое