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

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

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

Приложение к сжатию данных

Предположим, что нам даны две условные вероятности: $P(X|A)$ и $P(X|B)$ , и мы хотим оценить $P(X|A,B)$ , вероятность события X при обоих условиях $A$ и $B$ . недостаточно информации, Для теории вероятностей чтобы дать результат. На самом деле можно сконструировать сценарии, в которых результатом может быть что угодно. Но интуитивно мы ожидаем, что результат будет своего рода средним из двух.

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

Например, предположим, что мы сжимаем текстовый файл. Мы хотим предсказать, будет ли следующий символ переводом строки, учитывая, что предыдущий символ был точкой (контекст $A$ ) и что последний перевод строки произошел 72 символа назад (контекст $B$ ). Предположим, что ранее произошел перевод строки после 1 из последних 5 периодов ( $P(X|A=0.2$ ) и в 5 из последних 10 строк в столбце 72 ( $P(X|B)=0.5$ ). Как следует объединить эти прогнозы?

Использовались два общих подхода: линейное и логистическое смешивание. Линейное смешивание использует средневзвешенное значение прогнозов, взвешенных по доказательствам. В этом примере $P(X|B)$ получает больший вес, чем $P(X|A)$ потому что $P(X|B)$ основан на большем количестве тестов. Более старые версии PAQ используют этот подход. ^[1] В более новых версиях используется логистическое (или нейронное ) смешивание, сначала преобразующее прогнозы в логистическую область, log(p/(1-p)) перед усреднением. ^[2] Это фактически придает больший вес прогнозам около 0 или 1, в данном случае $P(X|A)$ . В обоих случаях каждой из входных моделей могут быть присвоены дополнительные веса и адаптированы в пользу моделей, которые давали наиболее точные прогнозы в прошлом. Все версии PAQ, кроме самых старых, используют адаптивное взвешивание.

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

Линейное смешивание

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

S ₀ знак равно Σ _я ш _я п _0i
S ₁ знак равно Σ _я ш _я п _1i
С = С ₀ + С ₁
Р(0) = С0 _/ С
Р(1) = С1 _/ С

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

п _я = п _0i + п _1i
ошибка = y – P(1)
w _i w _i + [(Sn1i _- S1ni ₎ S0S1 _← / ₍ ) _ошибка ]

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

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

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

х _я = растяжение (П _я (1))
P (1) = сквош (Σ _ш я _Икс я ₎ я

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

растяжение(х) = ln(х/(1 - х))
сквош(х) = 1/(1 + е ^-х) (обратное растяжению).

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

w _i ← w _i + η x _i (y - P(1))

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

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

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

Все PAQ версии (Мэтт Махони, Серж Оснах, Александр Ратушняк, Пшемыслав Скибиньский, Ян Ондрус и другие) [1] . PAQAR и версии до PAQ7 использовали линейное смешивание. В более поздних версиях использовалось логистическое смешивание.
All LPAQ versions (Matt Mahoney, Alexander Ratushnyak) [2] .
ZPAQ (Мэтт Махони) [3] .
WinRK 3.0.3 (Malcolm Taylor) в режиме PWCM максимального сжатия [4] . Версия 3.0.2 была основана на линейном смешивании.
NanoZip (Sami Runsas) в режиме максимального сжатия (опция -cc) [5] .
xwrt 3.2 (Пшемыслав Скибинский) в режиме максимального сжатия (параметры от -i10 до -i14) [6] в качестве серверной части словарного кодировщика.
cmm1–cmm4, M1 и M1X2 (Кристофер Маттерн) используют небольшое количество контекстов для обеспечения высокой скорости. M1 и M1X2 используют генетический алгоритм для выбора контекстов с двумя битовыми масками в отдельном проходе оптимизации.
ccm (Кристиан Мартелок).
бит (Осман Туран) [7] .
pimple, pimple2, tc и px (Илья Муравьев) [8] .
enc (Серж Оснак) пробует несколько методов, основанных на PPM и (линейном) смешивании контекстов, и выбирает лучший из них. [9]
fpaq2 (Нания Франческо Антонио) использует фиксированное усреднение веса для высокой скорости.
cmix (Байрон Нолл) сочетает в себе множество моделей и в настоящее время занимает первое место в тесте сжатия большого текста, ^[3] а также Силезский корпус ^[4] и превзошел работу, выигравшую премию Хаттера, хотя она не имеет права участвовать в конкурсе из-за использования слишком большого количества памяти.

Ссылки

^ Махони, М. (2005), «Адаптивное взвешивание контекстных моделей для сжатия данных без потерь», Технологический институт Флориды. Технический отчет CS-2005-16
^ Махони, М. «Программа сжатия данных PAQ8» .
^ Мэтт Махони (25 сентября 2015 г.). «Бенчмарк сжатия большого текста» . Проверено 4 ноября 2015 г.
^ Мэтт Махони (23 сентября 2015 г.). «Силезский тест сжатия с открытым исходным кодом» . Проверено 4 ноября 2015 г.

[1] Махони, М. (2005), «Адаптивное взвешивание контекстных моделей для сжатия данных без потерь», Технологический институт Флориды. Технический отчет CS-2005-16

[2] Махони, М. «Программа сжатия данных PAQ8» .

[largetext-3] Мэтт Махони (25 сентября 2015 г.). «Бенчмарк сжатия большого текста» . Проверено 4 ноября 2015 г.

[silesia-4] Мэтт Махони (23 сентября 2015 г.). «Силезский тест сжатия с открытым исходным кодом» . Проверено 4 ноября 2015 г.

[1]

[2]

[3]

[4]