энтропия
В четырёх лицах теоремы Байеса последнее лицо — про вес новости: скучное событие ничего не сообщает, сенсация разворачивает мнение. Там же сказано, что вес меряют в битах, и обещан мост к энтропии. Пройдём по нему. Оказывается, что «сколько информации в сообщении» — не оборот речи, а величина с единицей, и что единица эта не выбрана из удобства, а выведена из трёх требований, которые трудно оспорить.
откуда берётся логарифм
Начнём с одного события. Хочется величины, которая скажет, насколько оно неожиданно. Три требования, каждое очевидно.
Событие вероятности единица не удивляет вовсе — неожиданность нулевая. Чем событие реже, тем неожиданность больше. И третье, решающее: если случились два независимых события, общая неожиданность равна сумме двух — узнать две новости значит узнать первую и вторую, ни больше ни меньше.
Третье требование почти всё и решает. Вероятности независимых событий перемножаются, а неожиданности должны складываться. Функция, превращающая произведение в сумму, ровно одна — логарифм. Остаётся только знак, чтобы редкое давало много, а не мало.
P = 1/2 → один бит · P = 1/1024 → десять бит · P = 1 → ноль
Бит — это ответ на один вопрос «да или нет», заданный так, чтобы оба ответа были равновероятны. Не метафора: если нужно угадать число от одного до тысячи двадцати четырёх, при удачных вопросах хватит ровно десяти, и −log₂(1/1024) равно десяти. Основание логарифма — это просто выбор единицы; возьмёшь натуральный — получишь наты, десятичный — децибелы, и суть не изменится.
энтропия — средняя неожиданность
Одно событие — неожиданность. Источник, выдающий события по какому-то распределению, характеризуют средним: сколько удивления он производит в среднем на одно сообщение. Это и есть энтропия.
математическое ожидание неожиданности
Считать её удобно на монетах. Честная монета: два исхода по половине, каждый на один бит, среднее — один бит. Монета с перекосом девять к одному: орёл почти не удивляет, решка удивляет сильно, но случается редко, и в среднем выходит около половины бита. Монета, всегда падающая орлом, не сообщает ничего — ноль.
| источник | энтропия | смысл |
|---|---|---|
| честная монета | 1.00 бита | один вопрос на исход |
| монета 9 : 1 | 0.47 | меньше половины вопроса |
| монета 99 : 1 | 0.08 | почти ничего |
| кубик | 2.58 | между двумя и тремя вопросами |
| буква русского текста | ≈ 1.5 | язык избыточен на две трети |
Последняя строка стоит того, чтобы задержаться. В алфавите тридцать три буквы, и будь они равновероятны и независимы, каждая несла бы больше пяти бит. На деле — около полутора: буквы разной частоты и, как показал счёт по «Золотому телёнку», ещё и сцеплены между собой. Избыточность языка — не изъян, а защита: пропущенную букву восстанавливаешь, не заметив.
биты — это буквально длина сообщения
Тут теория перестаёт быть метафорой. Шеннон в 1948 году доказал: энтропия источника — это нижняя граница средней длины сообщения, которым его можно закодировать[1]. Не «примерно столько», а точно: короче нельзя, и сколь угодно близко подойти можно.
Отсюда практическое правило, которое работает в обе стороны. Частому событию нужен короткий код, редкому — длинный, и это единственный способ уложиться в границу. Так устроена азбука Морзе, где «е» — одна точка, а «щ» — четыре знака. Так устроены все архиваторы. И так же объясняется, почему уже сжатый файл не сжимается второй раз: избыточность вынута, энтропия достигнута, резерва нет.
чем это не сложность по Колмогорову
Две величины постоянно путают, а меряют они разное, и разница принципиальная.
Сложность по Колмогорову — свойство отдельного объекта: длина кратчайшей программы, которая его печатает. Она ничего не знает о вероятностях и о том, откуда объект взялся.
Энтропия — свойство источника: сколько в среднем он выдаёт на сообщение. Об отдельном сообщении она молчит.
Практическая разница такая. Строка из миллиона нулей имеет крошечную колмогоровскую сложность — программа в одну строку. Но если она пришла от честной монеты, источник имел энтропию в бит на знак, и эта конкретная строка — просто крайне маловероятный его выход. Одна величина говорит «этот объект прост», другая — «этот источник богат». Оба утверждения верны одновременно.
кросс-энтропия: плата за неверную модель
Дальше начинается место, ради которого всё это стоит знать не только из любопытства.
Допустим, ты кодируешь сообщения источника p, но веришь, что источник — q. Коды назначены по вере, а события приходят по правде. Средняя длина получится больше минимальной, и превышение считается точно.
заплатил = минимум + штраф за ошибку модели
Первое слагаемое — неустранимое: столько неопределённости в самом источнике. Второе — расстояние Кульбака—Лейблера, цена твоего заблуждения[2]. Оно всегда неотрицательно и равно нулю ровно тогда, когда ты угадал распределение.
Вот почему языковые модели учат на кросс-энтропии: это буквально средняя неожиданность модели при виде настоящего текста. Модель, назначившая правильному слову вероятность 0.5, удивляется на один бит; назначившая 0.001 — на десять. Обучение сводится к «удивляйся меньше», а перплексия, о которой говорят как об отдельной метрике, — это та же величина в другой шкале: два в степени кросс-энтропии, то есть «между сколькими вариантами модель фактически колеблется».
Заметь, что разложение объясняет и потолок. Часть кросс-энтропии — энтропия самого языка, и её не убрать никаким обучением: текст не предопределён. Модель может свести к нулю только второе слагаемое. Метрика, у которой есть неустранимая часть, ведёт себя как пол разметки в оценке — ниже него улучшать нечего, и путать приближение к полу с исчерпанием задачи легко.
назад к Байесу
Круг замыкается там, откуда начали. В четвёртом лице теоремы улики копились сложением логарифмов шансов, и в Блетчли-Парке эти лог-единицы называли банами и децибанами.
Теперь видно, что это была за величина. Логарифм отношения правдоподобий — информация, которую улика несёт в пользу одной гипотезы против другой, и складывается она именно потому, что логарифм превращает умножение в сложение. Байесовское обновление и есть накопление информации, а сила улики измеряется в тех же битах, что и вес новости.
И вопрос «сколько мне даст этот эксперимент» получает точный смысл: насколько ожидаемо уменьшится моя энтропия. Вопрос, на который все отвечают одинаково, не даёт ни бита — распределение ответов вырождено, удивления нет. Тот же довод, что запрещает тест, любой исход которого тебя укрепляет, и тот же, по которому в наборе для оценки работают лишь примеры, где модели расходятся.
что с этим делать
Три вещи стоит унести.
Мера информации не выбрана, а выведена: сложение неожиданностей для независимых событий не оставляет вариантов, кроме логарифма. Когда величина возникает из требований, а не из удобства, ей можно доверять за пределами примеров, на которых её показывали.
Энтропия — свойство источника, а не сообщения. Спрашивать, сколько бит в конкретной строке, бессмысленно, пока не сказано, из какого распределения она пришла.
И всякая разность между «что я думал» и «что оказалось» имеет цену в битах — одну и ту же для модели языка, для эксперимента и для собственного мнения. Заблуждаться, оказывается, дорого в точном смысле слова.