Контекстное смешивание

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

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

Применение для сжатия данных

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

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

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

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

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

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

• S ₀ = Σ _i w _i n _0i
• S ₁ = Σ _i w _i n _1i
• С = _С0 + _С1
• Р(0) = S0 _/ S
• П(1) = С ₁ / С

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

• н _я = н _0i + н _1i
• ошибка = у – P(1)
• w _i ← w _i + [(S n _1i - S ₁ n _i ) / (S ₀ S ₁ )] ошибка

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

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

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

• x _i = растянуть(P _i (1))
• P(1) = сквош(Σ _i w _i x _i )

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

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

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

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

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

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

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

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

Ссылки

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