Смешение контекста

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

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

• 1 Приложение к сжатию данных
  • 1.1 Линейное смешивание
  • 1.2 Логистическое смешивание
  • 1.3 Список компрессоров смешивания контекста
• 2 Ссылки

Предположим, что нам даны две условные вероятности: $P\; (X\; |\; A)\; \{\backslash \; displaystyle\; P\; (X\; |\; A)\}$и $P\; (X\; |\; B)\; \{\backslash \; displaystyle\; P\; (\; X\; |\; B)\}$, и мы хотим оценить $P\; (X\; |\; A,\; B)\; \{\backslash \; displaystyle\; P\; (X\; |\; A,\; B)\}$, вероятность событие X при обоих условиях $A\; \{\backslash \; displaystyle\; A\}$и $B\; \{\backslash \; displaystyle\; B\}$. Для теории вероятности недостаточно информации, чтобы дать результат. Фактически, можно построить сценарии, в которых результат может быть любым. Но интуитивно мы ожидаем, что результат будет средним из двух.

Проблема важна для сжатия данных. В этом приложении $A\; \{\backslash \; displaystyle\; A\}$и $B\; \{\backslash \; displaystyle\; B\}$- это контексты, $X\; \{\backslash \; displaystyle\; X\}$- это событие, когда следующий бит или символ данных, подлежащих сжатию, имеет конкретное значение, и $P\; (X\; |\; A)\; \{\backslash \; displaystyle\; P\; (X\; |\; A)\}$и $P\; (X\; |\; B)\; \{\backslash \; displaystyle\; P\; (X\; |\; B)\}$- оценки вероятности по двум независимым моделям. Степень сжатия зависит от того, насколько приблизительная вероятность приближается к истинной, но неизвестной вероятности события $X\; \{\backslash \; displaystyle\; X\}$. Часто контексты $A\; \{\backslash \; displaystyle\; A\}$и $B\; \{\backslash \; displaystyle\; B\}$встречаются достаточно часто, чтобы точно оценить $P\; (\; X\; |\; A)\; \{\backslash \; displaystyle\; P\; (X\; |\; A)\}$и $P\; (X\; |\; B)\; \{\backslash \; displaystyle\; P\; (X\; |\; B)\}$путем подсчета вхождений $X\; \{\backslash \; displaystyle\; X\}$в каждом контексте, но два контекста либо не встречались вместе часто, либо недостаточно вычислительных ресурсов (времени и памяти) для сбора статистики для объединенного случая.

Например, предположим, что мы сжимаем текстовый файл. Мы хотим предсказать, будет ли следующий символ переводом на строку, учитывая, что предыдущий символ был точкой (context $A\; \{\backslash \; displaystyle\; A\}$) и что последний символ перевода строки имел место 72 символа назад (контекст $В\; \{\backslash \; displaystyle\; B\}$). Предположим, что перевод строки ранее происходил после 1 из последних 5 периодов ($P\; (X\; |\; A\; =\; 0,2\; \{\backslash \; displaystyle\; P\; (X\; |\; A\; =\; 0,2\}$)) и в 5 из последних 10 строки в столбце 72 ($P\; (X\; |\; B)\; =\; 0,5\; \{\backslash \; displaystyle\; P\; (X\; |\; B)\; =\; 0,5\}$). Как следует объединить эти прогнозы?

Два были использованы общие подходы, линейное и логистическое смешивание. При линейном смешивании используется средневзвешенное значение прогнозов, взвешенных по свидетельствам. В этом примере $P\; (X\; |\; B)\; \{\backslash \; displaystyle\; P\; (X\; |\; B)\}$получает больший вес, чем $P\; (X\; |\; A)\; \{\backslash \; displaystyle\; P\; (X\; |\; A)\}$, потому что $P\; (X\; |\; B)\; \{\backslash \; displaystyle\; P\; (X\; |\; B)\}$основан на большем количестве тестов. В старых версиях PAQ используется этот подход. В более новых версиях используется логистическое (или нейронная сеть ) смешивание путем первого преобразования прогнозы в логистической области, log (p / (1-p)) перед усреднением. Это эффективно дает больший вес прогнозам около 0 или 1, в данном случае $P\; (X\; |\; A)\; \{\backslash \; Displaystyle\; P\; (X\; |\; A)\}$. В обоих случаях каждой из входных моделей могут быть присвоены дополнительные веса и адаптированы для того, чтобы отдавать предпочтение моделям, которые давали наиболее точные прогнозы в прошлом. Все версии PAQ, кроме самых старых, используют адаптивное взвешивание.

Большинство компрессоров микширования контекста прогнозируют ввод одного бита за раз. Выходная вероятность - это просто вероятность того, что следующим битом будет 1.

Linear Mixing

Нам дан набор прогнозов P i (1) = n 1i/ni, где n i = n 0i + n 1i, а n 0i и n 1i являются отсчетами 0 и 1 бит соответственно для i-й модели. Вероятности вычисляются путем взвешенного сложения значений 0 и 1:

• S0= Σ iwin0i
• S1= Σ iwin1i
• S = S 0 + S 1
• P (0) = S 0 / S
• P (1) = S 1 / S

Веса w i изначально равны и всегда суммируются с 1. В начальных условиях каждая модель взвешивается пропорционально доказательствам. Затем веса корректируются в пользу более точных моделей. Предположим, нам дано, что фактический прогнозируемый бит равен y (0 или 1). Тогда корректировка веса:

• ni= n 0i + n 1i
• error = y - P (1)
• wi← w i + [(S n 1i - S 1ni) / (S 0S1)] error

Сжатие можно улучшить, ограничив n i так, чтобы взвешивание модели было лучше сбалансировано. В PAQ6 всякий раз, когда один из счетчиков битов увеличивается, часть другого счетчика, превышающая 2, уменьшается вдвое. Например, после последовательности 000000001 счетчики будут идти от (n 0, n 1) = (8, 0) до (5, 1).

Логистическое смешивание

Пусть P i (1) будет предсказанием i-й модели, что следующим битом будет 1. Тогда окончательное предсказание P ( 1) вычисляется:

• xi= растяжение (P i (1))
• P (1) = squash (Σ iwixi)

, где P (1) - вероятность того, что следующим битом будет 1, P i (1) - это вероятность, оцененная i-й моделью, и

• stretch (x) = ln (x / (1 - x))
• squash (x) = 1 / (1 + e) ​​(инверсия растяжения).

После каждого прогноза модель обновляется путем корректировки весов для минимизации затрат на кодирование.

• wi← w i + η x i (y - P (1))

где η - скорость обучения (обычно от 0,002 до 0,01), y - прогнозируемый бит, а (y - P ( 1)) является ошибкой прогнозирования.

Список компрессоров смешивания контекста

Все версии ниже используют логистическое смешивание, если не указано иное.

• Все версии PAQ (Мэтт Махони, Серж Оснач, Александр Ратушняк, Пшемыслав Скибинский, Ян Ондрус и другие) [1]. PAQAR и версии до PAQ7 использовали linear m ixing. В более поздних версиях использовалось логистическое смешивание.
• Все версии LPAQ (Мэтт Махони, Александр Ратушняк) [2].
• ZPAQ (Мэтт Махони) [3].
• WinRK 3.0.3 (Малкольм Тейлор) в режиме PWCM максимального сжатия [4]. Версия 3.0.2 была основана на линейном смешивании.
• NanoZip (Sami Runsas) в режиме максимального сжатия (опция -cc) [5].
• xwrt 3.2 (Przemysław Skibiński) в режиме максимального сжатия ( параметры -i10 - -i14) [6] в качестве серверной части для кодировщика словаря.
• cmm1 - cmm4, M1 и M1X2 (Christopher Mattern) используют небольшое количество контекстов для высокоскоростной. M1 и M1X2 используют генетический алгоритм для выбора двух контекстов с битовой маской в отдельном проходе оптимизации.
• ccm (Christian Martelock).
• бит (Осман Туран) [7].
• pimple, pimple2, tc и px (Илья Муравьев) [8].
• enc (Серж Оснач) пробует несколько методов, основанных на PPM и (линейное) смешение контекста и выбирает лучший. [9]
• fpaq2 (Nania Francesco Antonio) с фиксированным усреднением веса для высокой скорости.
• cmix (Byron Knoll) смешивает многие модели и в настоящее время занимает первое место в тесте сжатия большого текста, а также корпус Silesia и превзошел выигравшую запись Hutter Prize, хотя он не соответствует требованиям из-за использования слишком большого объема памяти.