thedeemon | Часть 5. Context Mixing

В предыдущих частях мы без особенных усилий построили компрессор, который жмет сильнее, чем zip, rar, bz2 и 7z в их режимах по-умолчанию. Однако примененным технологиям хоть и не 30 лет, как LZ, но не меньше 15. Куда продвинулся прогресс за это время?

В классическом PPM мы исходим из того, что более длинные контексты лучше предсказывают очередной символ. Вообще говоря, это не всегда правда. Например, на границе двух слов длинный контекст будет содержать конец предыдущего слова, которое не особенно помогает в предсказании и рассеивает статистику. Вместо выбора самого длинного имеющегося контекста можно выбрать, например, тот, в котором распределение символов имеет наименьшую энтропию. Если символ будет угадан с первой попытки (без эскейпов), то в этом контексте он в среднем будет закодирован меньшим числом бит. А если в том контексте его нет, то поскольку это потенциально более короткий контекст, максимальное число уходов будет меньше. Но считать для всех контекстов символа их энтропию слишком накладно. Есть более простой метод, дающий практически тот же результат: выбирать контекст, у которого вероятность самого вероятного символа больше, чем у всех других контекстов. Поскольку скорее всего символ окажется именно тем, который имеет наибольшую вероятность (тавтология), на него потратится меньше всего бит там, где эта вероятность больше. Прием с таким осознанным выбором контекста носит название LOE - Local Order Estimation. Я попробовал реализовать его в демонстрационном компрессоре, но то ли он действительно несовместим с некоторыми другими приемами, то ли я просто не умею его готовить (самый большой вопрос - как обновлять статистику в дереве контекстов), но у меня LOE не дал улучшения сжатия, а только ухудшил.

Давайте теперь посмотрим, чему равна оценка вероятности произвольного символа в PPM. Пусть P_(k,i) - оценка вероятности i-го символа в контексте длины k, а E_k - оценка вероятности ухода из контекста длины k. Тогда если мы кодируем i-й символ в PPM 4-го порядка, и самый длинный из нашедшихся контекстов имеет длину 3, и нужный символ в нем найден, то его вероятность будет оценена как P_(3,i). Если нужного символа нет в контексте длины 3, то делается уход к более короткому. Если символ найден в контексте 2-го порядка, то его оценка там P_(2,i) будет умножена на вероятность ухода из предыдущего контекста E_4, т.к. подинтервал для P_(2,i) будет высекаться внутри подинтервала для Е_4. Если же символ нашелся лишь в контексте 1-го порядка, то произойдет два ухода, и его оценка получится равной E_4 * E_3 * P_(2,i). В общем случае если мы начали оценивать символ в самом длинном из имеющихся контекстов длины start_k, а нашли символ в контексте found_k, то его оценка его вероятности получится

Если еще больше обобщить это выражение, то можно записать так:

Т.е. оценка вероятности символа получается из ее оценок в разных контекстах с разными весами. В классическом PPM веса всех кроме одного контекстов равны нулю. Но никто же не мешает сделать их ненулевыми: брать разные оценки и смешивать их с некоторыми весами. Причем в такой схеме уже не нужны никакие уходы, мы работает только с вероятностями символов. В определенном смысле, схема с уходами - это частный случай смешивания контекстов. Вычислять такие взвешенные суммы для всех символов довольно накладно. Но все становится много проще и удобнее, если от посимвольного сжатия перейти к побитному. Будем рассматривать входные данные как последовательность бит, оценивать для каждого бита вероятность 0 и 1 разными контекстами с разными весами и кодировать бинарным арифметиком, который тоже сильно проще (в частности, там можно обойтись без делений и с минимумом умножений или даже вовсе без них). В PPM нашими контекстами были k предыдущих символов. Но опять же никто не мешает ввести дополнительные модели, например разреженные контексты (включающие некоторые не подряд идущие символы из истории), контексты, учитывающие текущую позицию (полезно для сжатия нетекстовых структурированных данных) и т.д. Можно придумать очень много разных моделей, использующих разные данные, и все они будут давать свои оценки вероятности единицы и нуля, а эти оценки мы можем как-нибудь хитро смешивать. Такой подход носит название CM - Context Mixing. Именно на нем сейчас построены самые мощные компрессоры, побеждающие в соревнованиях. В частности, семейство компрессоров PAQ работает именно по этому принципу.

На первый план в этой схеме выходит вопрос о том, как именно смешивать оценки и как обновлять веса. Самый простой способ: если каждая модель j со своим контекстом содержит счетчики нулей и единиц n0_j и n1_j (соответственно, предсказывая вероятность нуля как n0_j/(n0_j+n1_j)), то можно просто просуммировать соответствующие счетчики всех моделей
N0 = n0_1 + n0_2 + n0_3 + ...
N1 = n1_1 + n1_2 + n1_3 + ...
и получить оценку N0/(N0+N1). Это эквивалентно суммированию оценок с весами, пропорциональными количеству символов, встреченных в использованных контекстах (w_j ~ n0_j + n1_j).

Другой способ - присвоить моделям разные вещественные веса w_j, суммировать счетчики с этими весами, а потом после кодирования каждого символа (бита) увеличивать вес тем моделям, которые успешно предсказали бит, и уменьшать веса менее успешным моделям. Тут
N0 = w1 * n0_1 + w2 * n0_2 + w3 * n0_3 + ...
N1 = w1 * n1_1 + w2 * n1_2 + w3 * n1_3 + ...
P(0) = N0 / (N0 + N1)
средняя длина сжатого бита получается равна энтропии
H = -P(0) * log2 P(0) - (1-P(0)) * log2 (1-P(0))
Если поставить определение P(0) через счетчики, то получим выражение, зависящее от w1, w2, w3... от которого можно найти производную по каждому из весов w_j и будет ясно, в какую сторону вес нужно изменить, чтобы уменьшить H. Что-то вроде
w_j := w_j + (bit - P)((N0+N1)* n1_j - N1 * (n0_j + n1_j)) / (N0*N1)

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

Еще можно заметить, что если у нас есть предсказания двух моделей, и одна предсказывает 0 с вероятностью 0.52, а другая - с вероятностью 0.95, то это как бы первая говорит "а фиг его знает, что это будет за бит", а вторая - "зуб даю, будет ноль". Т.е. вторая более уверена в предсказании, а значит совместную оценку вероятности стоит сделать не посередине (0.73), а ближе к более уверенной, скажем, 0.9. Это получается естественным образом, если перейти в "logistic domain", растянуть вероятности, сложить с весами и стянуть обратно:

где

При таком подходе обновление весов гораздо проще:
w_j := w_j + C * (bit - p) * stretch(P_j)
где C - параметр агрессивности обучения.

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

На этом обзор энтропийных методов сжатия можно закончить. Теперь вы знаете почти все, что знаю я, и при желании сможете тоже написать лучший в мире кодек и переехать на тропический остров. :) Главное, что я хотел донести, это:
* Задача сжатия сводится к задаче предсказания, оценки вероятностей.
* Чем больше компрессор знает о данных и чем лучше он "умеет знать" (т.е. чем лучше его модель), тем лучше его предсказание очередного символа, тем меньше неопределенность символа, меньше локальная энтропия и меньше число бит на символ.
* В частности, если символ полностью предсказуем, т.е. его вероятность равна 1, неопределенность равна 0, и на него тратится 0 бит.
* Оценка вероятностей символа и ее энтропия определяются моделью и имеющимися данными, это чисто субъективная величина, которая для каждого символа характеризует не столько сам символ, сколько объем и качество знаний компрессора о характере данных. Чем лучше у кодера модель, тем меньше получается энтропия сжимаемых данных (если они вообще сжимаемы).
* Каждый новый символ добавляет сведений в модель, увеличивает накопленный объем знаний кодера и тем самым уменьшает неопределенность относительно характера данных.
* Везде выше вместо "символ" можно подставить "событие" или "сообщение". Можно рассматривать потоки сообщений или последовательности событий, предсказывать их, оценивать вероятности. Энтропия сообщения (одного из потока) также определяется качеством априорного знания о сообщении, а не самим сообщением.

Кстати, о сжимаемости. Что будет, если входные данные абсолютно случайны и равномерно распределены? Тогда во всех контекстах вероятности всех символов будут 1/A, где А - размер алфавита, тогда на каждый символ будет в среднем потрачено log2(A) бит, а значит размер сжатых данных будет равен размеру входных, никакого сжатия не будет. Это верно, если статистику посчитать заранее. Если ее составлять динамически, то кодер будет увеличивать вероятности то одному символу, то другому, они будут иметь приблизительно одинаковые вероятности, но в каждый момент времени распределение будет немного отличаться от равномерного, поэтому в среднем может на символ уйти чуть больше log2(A) и вместо сжатия получится распухание. Нетрудно заметить, что универсальных компрессоров быть не может: нельзя все последовательности длины N бит сжать до размера меньшего N, т.к. количество всех возможных файлов длины N-1 меньше, чем количество всех возможных входных данных длины N. Любой компрессор сжимает какой-то класс данных, а какой-то наоборот раздувает. И в общем-то доля более-менее сносно сжимаемых данных из всех последовательностей длины N очень невелика, просто мы обычно имеем дело с сильно избыточными форматами.

Еще можно заметить такое свойство арифметического сжатия: в первой части мы увидели, что это функция, которая из одного длинного вещественного числа между 0 и 1 делает другое вещественное число между 0 и 1, если повезет, то менее длинное (по числу значащих цифр). Исходный интервал [0,1) делится на подинтервалы S0, S1, S2... каждый из которых тоже делится на подинтервалы и так далее, но размер каждого из подинтервалов соответствует вероятности появления символа, а значит плотность этой вероятности для каждого интервала равна Pi/Si = Pi/Pi = 1. Если у 0 вероятность вдвое выше, чем у 1, его интервал будет вдвое больше, но и попадать мы в него будем вдвое чаще, т.е. итоговое число, результат сжатия, будучи рассмотрено как случайная величина, имеет равномерное распределение: сжимая множество различных файлов с одинаковой статистикой мы получим множество длинных "чисел", и они будут распределены равномерно. Равномерно распределенная на [0,1) случайная величина так же равномерна распределена на любом интервале [a,b) внути [0,1). А это значит, что результат энтропийного кодера (если он хороший и модель его правильно оценивает вероятности) есть последовательность битов с равномерным распределением. Именно поэтому хорошо сжатые данные не подлежат дальнейшему сжатию.

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

Продолжение...