Смешивание контекста - Context mixing

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

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

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

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

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

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

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

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

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

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

• S₀ = Σ_я ш_я п_0i
• S₁ = Σ_я ш_я п_1i
• S = S₀ + S₁
• P (0) = S₀ / S
• P (1) = S₁ / S

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

• п_я = п_0i + п_1i
• ошибка = y - P (1)
• ш_я ← w_я + [(S n_1i - S₁ п_я) / (S₀ S₁)] ошибка

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

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

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

• Икс_я = растянуть (P_я(1))
• P (1) = кабачок (Σ_я ш_я Икс_я)

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

• растянуть (х) = ln (х / (1 - х))
• сквош (x) = 1 / (1 + e^−x) (инверсия растяжения).

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

• ш_я ← w_я + η x_я (у - P (1))

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

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

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

• Все PAQ версии (Мэтт Махони, Серж Оснач, Александр Ратушняк, Пшемыслав Скибинский, Ян Ондрус и др.) [1]. PAQAR и версии до PAQ7 использовали линейное смешение. Более поздние версии использовали логистическое смешивание.
• Все версии 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 (Кристиан Мартелок).
• бит (Осман Туран) [7].
• pimple, pimple2, tc и px (Илья Муравьев) [8].
• enc (Serge Osnach) пробует несколько методов, основанных на PPM и (линейное) смешивание контекста и выбирает лучший. [9]
• fpaq2 (Nania Francesco Antonio) с фиксированным усреднением веса для высокой скорости.
• cmix (Байрон Нолл) смешивает множество моделей и в настоящее время занимает первое место в тесте сжатия большого текста,^[3] а также корпус Силезии ^[4] и превзошла победную запись Приз Хаттера хотя он не подходит из-за использования слишком большого объема памяти.

Рекомендации

1. Махони, М. (2005), «Адаптивное взвешивание контекстных моделей для сжатия данных без потерь», Florida Tech. Технический отчет CS-2005-16
2. Махони, М. «Программа сжатия данных PAQ8».
3. Мэтт Махони (2015-09-25). «Тест сжатия большого текста». Получено 2015-11-04.
4. Мэтт Махони (2015-09-23). «Тест Silesia Open Source Compression Benchmark». Получено 2015-11-04.