"Начиная"

Интуитивный взгляд на основы теории информации

Нетехнический тур по сжатию данных, энтропии, шифрованию, сложности Колмогорова и их значению

Вступление

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

Можно ли сжать любой файл?

Ответ на этот вопрос глубокий. Вместо того, чтобы просто формулировать ответ, давайте посмотрим, сможем ли мы обосновать свой путь к решению.

  1. Предположим, любой файл можно сжать, что приведет к уменьшению размера файла.
  2. Следовательно, вывод сжатого файла всегда может быть сжат.
  3. Если это правда, то любой файл можно сжимать бесконечно много раз.
  4. Из этого следует, что любое количество информации можно сжать до одного бита.
  5. Это явно абсурд, поэтому мы должны отвергнуть эту предпосылку.

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

Вы легко можете убедиться в этом сами, создав файл со случайно сгенерированным текстом (без шаблонов или избыточности) и попытавшись сжать его в ZIP-файл. Проверьте размер файла до и после, и вы увидите, что они не сильно отличаются. Тем временем возьмите абзац из Википедии, скопируйте и вставьте его несколько десятков раз в файл и сожмите. Вы увидите, что он сильно сжимается. Вы также можете попробовать функцииcompress и decompress библиотеки zlib Python, чтобы программно поиграться со сжатием.

Изучение сжатия данных раскрывает некоторые из наиболее важных идей теории информации:

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

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

Шифрование и информация

Шифрование означает, что сообщение принимает и делает его нечитаемым для всех, у кого нет секретного ключа. Ранние шифры подстановки (например, шифр Цезаря) просто заменяли друг друга буквами, сохраняя статистические закономерности языка. Если сообщение было сжимаемым до шифрования, оно все равно будет сжимаемым после шифрования. Я опробовал это с помощью zlib и получил степень сжатия 70% согласно Биллю о правах США, независимо от применения шифра Цезаря. См. Код, который я использовал здесь. Эти подстановочные шифры довольно легко взломать, если использовать статистические данные о частоте символов.

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

Чтобы использовать OTP, две стороны должны совместно использовать строку секретных случайных битов («блокнот»). Чтобы отправить секретное сообщение, одна из сторон преобразует сообщение в двоичное, выравнивает его с блокнотом и выполняет побитовую операцию исключающего ИЛИ (XOR). XOR, представленный кружком с плюсом внутри, возвращает 0, если два бита одинаковы, и возвращает 1, если два бита различны. В результате получается строка случайных битов, которую невозможно расшифровать без секретной панели. Поскольку зашифрованное сообщение выглядит случайным, оно будет в значительной степени несжимаемым. Никакая статистическая информация о базовом сообщении не просачивается, и оно даже невосприимчиво к атакам методом грубой силы, поскольку, пробуя каждый возможный блокнот длиной N, вы просто обнаруживаете все возможные сообщения длины N, без возможности отличить правильное от правильного. неверно.

Чтобы расшифровать сообщение, принимающая сторона выравнивает полученное сообщение со своим блокнотом и снова выполняет побитовое исключающее ИЛИ. Это меняет шифрование на противоположное и открывает исходное сообщение. Это работает из-за некоторых свойств функции XOR: (a XOR b) XOR b = a XOR (b XOR b) = a XOR 0 = a. На практике обмен действительно случайными одноразовыми блокнотами невозможен. Но идея, описанная выше, также может использоваться с псевдослучайными контактными площадками, что означает, что обе стороны должны только обмениваться относительно короткими секретными ключами, используемыми для генерации псевдослучайных контактных площадок.

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

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

С другой стороны, если вы получили массив случайных пикселей, как на изображении выше, он неотличим от значимого изображения, которое было зашифровано. Применив какое-то преобразование, кажущиеся случайными 0 и 1 на изображении могут стать значимыми. Возможно, пиксели действительно представляют собой просто случайные биты, которые не так важны для нас, как людей. Без дополнительных знаний мы не сможем увидеть разницу, но в любом случае информация присутствует. Значение - это не то же самое, что информация. Значение относится к нашему субъективному пониманию сообщения, а информация - это объективный показатель.

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

Макросостояния и микросостояния

Мы только что обсудили, как неправильно объединять случайность с недостатком информации и упорядоченность с информацией. Мы можем использовать макросостояния и микросостояния, чтобы понять взаимосвязь между порядком и информацией. Макросостояние - это общее описание системы, например «Изображение полностью черное» или «изображение имеет пиксели со случайным значением». Микросостояние - это точное расположение системы на меньшем уровне детализации, например фактические значения RGB для каждого пикселя изображения.

Концепция энтропии, часто переводимая как «беспорядок», встречается как в термодинамике, так и в теории информации. Высокая энтропия возникает, когда существует много микросостояний для данного макросостояния. Низкая энтропия - это когда для данного макросостояния мало микросостояний. Меньшая энтропия означает больший порядок и большую предсказуемость. Больше энтропии означает меньше порядка, больше случайности и больше неопределенности.

Давайте рассмотрим другой повседневный пример: бросание пары игральных костей. Любой игрок в монополию знает, что не все результаты одинаковы. Только 1 из каждых 36 бросков в среднем дает сумму 12. Но 6 из 36 дают сумму 7. Таким образом, макросостояние «Я выбросил 12» имеет только одно соответствующее микросостояние, а «Я выбросил 7». »Имеет 6 микросостояний.

В ранее полученном полностью черном изображении есть только одно микросостояние, которое соответствует макросостоянию «изображение полностью черное»: каждый пиксель должен иметь RGB = (0, 0, 0). Это означает, что энтропия очень низкая, а значит, мало информации и, следовательно, высокая сжимаемость. Каждый пиксель соответствует шаблону предыдущих, поэтому он не вносит ничего удивительного или информативного.

В изображении со случайными пикселями существует невообразимо большое количество микросостояний, которые соответствуют макросостоянию «изображение имеет пиксели со случайным значением». Существует около 2³⁰⁰⁰⁰⁰⁰ возможных уникальных изображений RGB с разрешением 1200x800, многие из которых могут привести к появлению случайного изображения. Это означает, что существует очень высокая энтропия, следовательно, высокая информация и, следовательно, низкая сжимаемость. Цвет каждого пикселя полностью не зависит от цвета предыдущих, поэтому каждый пиксель максимально удивителен и информативен.

Энтропия также применима ко многим физическим системам. Представьте, что вы открываете воздушный шар, наполненный неприятно пахнущим газом, в углу комнаты. Есть много микросостояний, которые соответствуют «газу равномерно распределен по комнате», в то время как гораздо меньшее количество состояний соответствует «газу сконцентрирована в углу комнаты». Или представьте себе кубик льда, лежащий при комнатной температуре. Для молекул воды, прыгающих в жидкой форме, гораздо больше макросостояний, чем для молекул воды, заключенных в высокоупорядоченный кубик льда. Согласно второму закону термодинамики, общая энтропия системы неизбежно увеличивается со временем, причем более вероятные события преобладают над менее вероятными. В результате газы неизменно диффундируют, происходят химические реакции и тают кубики льда. Совершенно разные области - теория информации, химия и физика - используют идею энтропии.

Колмогоровская сложность

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

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

Предположим, у вас есть файл, подобный следующему, в котором хранятся данные о погоде на каждый день года:

01/01/2021: sunny, high of 8 C, low of 4 C
01/02/2021: partly cloudy, high of 3 C, low of -1 C
01/03/2021: rainy, high of 6 C, low of 2 C
...
12/31/2021: snow, high of -1 C, low of -5 C

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

Колмогоров Сложность также была расширена до идеи о том, что законы физики представляют собой тип алгоритма сжатия для состояния Вселенной. Знание взаимосвязи между силой, массой и ускорением означает, что одну и ту же систему можно описать меньшим количеством переменных. Объект, следующий по параболической траектории при баллистическом движении, можно описать всего двумя точками, а не бесконечным числом, через которое он фактически проходит. Идея науки как способа сжатия Вселенной глубока и была исследована Маркусом Хаттером в подкасте Лекса Фридмана [5].

Лингвистика, музыка и многое другое

Как лингвист, я очарован тем, как эти концепции применимы к человеческому языку. Существуют статистические шаблоны в языках и встроенная избыточность, которые делают все человеческие языки сжимаемыми. Клод Шеннон, который в значительной степени создал область теории информации, оценил, что письменный английский имеет коэффициент избыточности ~ 50% .

То, что эта информация является правильной, написанной на английском языке.

В языке необходимо уравновешивать эффективность и избыточность. Языки не должны без надобности тратить драгоценные биты и слоги. Однако слишком большая плотность информации, и сообщение становится более чувствительным к шуму и искажениям. Если каждый бит в сообщении выполняет больше работы, то случайное переключение битов приведет к более катастрофическим последствиям. Избыточность языка позволяет слушателям восстанавливать смысл даже из поврежденных сообщений (например, в шумной комнате, с плохим соединением FaceTime или при чтении грязного почерка), точно так же, как биты исправления ошибок, добавленные в цифровое сообщение, позволяют восстанавливать искаженные сигналы . Интересно отметить, что приведенный выше пример «плотного английского» не работает на таком языке, как иврит, который уже является орфографически плотным (гласные не записываются). Некоторые особенности языка, такие как маркеры согласия (я ем или она ест s), поначалу кажутся излишними, поскольку они не говорят вам ничего, чего вы не могли бы понять из другого. слова в предложении. Но встроенное резервирование действительно имеет большой смысл, учитывая, что связь подвержена шумам и помехам [6].

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

О теории информации можно сказать гораздо больше, поэтому ознакомьтесь с приведенными ниже источниками и спасибо за чтение!

использованная литература

[1] Информация, Джеймс Глейк.

[2] https://en.wikipedia.org/wiki/Entropy

[3] Николас Хадсон. 2008. Музыкальная красота и сжатие информации. Https://www.researchgate.net/publication/49770962_Musical_beauty_and_information_compression_Complex_to_the_ear_but_simple_to_the_mind

[4] https://ru.wikipedia.org/wiki/Kolmogorov_complexity

[5] Маркус Хаттер о подкасте Лекса Фридмана. Https://www.youtube.com/watch?v=E1AxVXt2Gv4

[6] Роджер Леви. 2008. Модель с зашумленным каналом рационального понимания человеческих предложений при неопределенных входных данных. Http://www.mit.edu/~rplevy/papers/levy-2008-emnlp.pdf