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

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

использует 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 использовали линейное смешивание. В более поздних версиях использовалось логистическое смешивание.
Все версии 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 (Нания Франческо Антонио) использует фиксированное усреднение веса для высокой скорости.
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]

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

Линейное микширование ​ ​

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

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

Ссылки [ править ]

Линейное микширование

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