La mezcla de contexto es un tipo de algoritmo de compresión de datos en el que las predicciones del siguiente símbolo de dos o más modelos estadísticos se combinan para producir una predicción que a menudo es más precisa que cualquiera de las predicciones individuales. Por ejemplo, un método simple (no necesariamente el mejor) es promediar las probabilidades asignadas por cada modelo . El bosque aleatorio es otro método: genera la predicción que es el modo de las predicciones generadas por modelos individuales. La combinación de modelos es un área activa de investigación en el aprendizaje automático . [ cita requerida]
La serie PAQ de programas de compresión de datos utiliza la mezcla de contexto para asignar probabilidades a bits individuales de la entrada.
Aplicación a la compresión de datos
Supongamos que se nos dan dos probabilidades condicionales, y , y deseamos estimar , la probabilidad del evento X dadas ambas condiciones y . No hay información suficiente para que la teoría de la probabilidad dé un resultado. De hecho, es posible construir escenarios en los que el resultado podría ser cualquier cosa. Pero intuitivamente, esperaríamos que el resultado fuera una especie de promedio de los dos.
El problema es importante para la compresión de datos. En esta aplicación, y son contextos, es el caso de que el siguiente bit o símbolo de los datos a comprimir tenga un valor particular, y y son las estimaciones de probabilidad de dos modelos independientes. La relación de compresión depende de qué tan cerca se acerque la probabilidad estimada a la probabilidad verdadera pero desconocida del evento.. A menudo ocurre que los contextos y han ocurrido con suficiente frecuencia para estimar con precisión y contando apariciones de en cada contexto, pero los dos contextos no han ocurrido juntos con frecuencia, o hay recursos informáticos insuficientes (tiempo y memoria) para recopilar estadísticas para el caso combinado.
Por ejemplo, suponga que estamos comprimiendo un archivo de texto. Deseamos predecir si el siguiente carácter será un salto de línea, dado que el carácter anterior era un punto (contexto) y que el último salto de línea ocurrió hace 72 caracteres (contexto ). Suponga que un salto de línea ocurrió previamente después de 1 de los últimos 5 períodos () y en 5 de las últimas 10 líneas en la columna 72 (). ¿Cómo deben combinarse estas predicciones?
Se han utilizado dos enfoques generales, mezcla lineal y logística. La mezcla lineal utiliza un promedio ponderado de las predicciones ponderadas por evidencia. En este ejemplo, obtiene más peso que porque se basa en un mayor número de pruebas. Las versiones anteriores de PAQ utilizan este enfoque. [1] Las versiones más recientes utilizan la mezcla logística (o red neuronal ) transformando primero las predicciones en el dominio logístico , log (p / (1-p)) antes de promediar. [2] Esto da mayor peso a las predicciones cercanas a 0 o 1, en este caso. En ambos casos, se pueden asignar pesos adicionales a cada uno de los modelos de entrada y adaptarlos para favorecer los modelos que han dado las predicciones más precisas en el pasado. Todas las versiones de PAQ, excepto las más antiguas, utilizan ponderación adaptativa.
La mayoría de los compresores de mezcla de contexto predicen un bit de entrada a la vez. La probabilidad de salida es simplemente la probabilidad de que el siguiente bit sea un 1.
Mezcla lineal
Se nos da un conjunto de predicciones P i (1) = n 1i / n i , donde n i = n 0i + n 1i , y n 0i y n 1i son los recuentos de 0 y 1 bits respectivamente para el i-ésimo modelo . Las probabilidades se calculan mediante la suma ponderada de los recuentos de 0 y 1:
- S 0 = sigma i w i n 0i
- S 1 = Σ yo w yo n 1i
- S = S 0 + S 1
- P (0) = S 0 / S
- P (1) = S 1 / S
Las ponderaciones w i son inicialmente iguales y siempre suman 1. En las condiciones iniciales, cada modelo se pondera en proporción a la evidencia. Luego, los pesos se ajustan para favorecer los modelos más precisos. Supongamos que se nos da que el bit real que se predice es y (0 o 1). Entonces el ajuste de peso es:
- n i = n 0i + n 1i
- error = y - P (1)
- w i ← w i + [(S n 1i - S 1 n i ) / (S 0 S 1 )] error
La compresión se puede mejorar limitando n i para que la ponderación del modelo esté mejor equilibrada. En PAQ6, siempre que se incrementa uno de los recuentos de bits, la parte del otro recuento que excede 2 se reduce a la mitad. Por ejemplo, después de la secuencia 000000001, los recuentos irían de (n 0 , n 1 ) = (8, 0) a (5, 1).
Mezcla logística
Sea P i (1) la predicción del i-ésimo modelo de que el siguiente bit será un 1. Luego, se calcula la predicción final P (1):
- x i = estirar (P i (1))
- P (1) = calabaza (Σ yo w yo x yo )
donde P (1) es la probabilidad de que el siguiente bit sea un 1, P i (1) es la probabilidad estimada por el i-ésimo modelo, y
- estirar (x) = ln (x / (1 - x))
- squash (x) = 1 / (1 + e −x ) (inverso de estiramiento).
Después de cada predicción, el modelo se actualiza ajustando los pesos para minimizar el costo de codificación.
- w yo ← w yo + η x yo (y - P (1))
donde η es la tasa de aprendizaje (normalmente 0,002 a 0,01), y es el bit predicho y (y - P (1)) es el error de predicción.
Lista de compresores de mezcla de contexto
Todas las versiones siguientes utilizan mezcla logística a menos que se indique lo contrario.
- Todas las versiones de PAQ (Matt Mahoney, Serge Osnach, Alexander Ratushnyak, Przemysław Skibiński, Jan Ondrus y otros) [1] . PAQAR y las versiones anteriores a PAQ7 usaban mezcla lineal. Las versiones posteriores utilizaron la mezcla logística.
- Todas las versiones de LPAQ (Matt Mahoney, Alexander Ratushnyak) [2] .
- ZPAQ (Matt Mahoney) [3] .
- WinRK 3.0.3 (Malcolm Taylor) en modo PWCM de máxima compresión [4] . La versión 3.0.2 se basó en la mezcla lineal.
- NanoZip (Sami Runsas) en modo de máxima compresión (opción -cc) [5] .
- xwrt 3.2 (Przemysław Skibiński) en modo de compresión máxima (opciones -i10 a -i14) [6] como back-end para un codificador de diccionario.
- cmm1 a cmm4, M1 y M1X2 (Christopher Mattern) utilizan una pequeña cantidad de contextos para alta velocidad. M1 y M1X2 usan un algoritmo genético para seleccionar contextos enmascarados de dos bits en una pasada de optimización separada.
- ccm (Christian Martelock).
- bit (Osman Turan) [7] .
- espinilla, espinilla2, tc y px (Ilia Muraviev) [8] .
- enc (Serge Osnach) prueba varios métodos basados en PPM y mezcla de contexto (lineal) y elige el mejor. [9]
- fpaq2 (Nania Francesco Antonio) usando un promedio de peso fijo para alta velocidad.
- cmix (Byron Knoll) mezcla muchos modelos, y actualmente ocupa el primer lugar en el índice de referencia de compresión de texto grande, [3] así como en el corpus de Silesia [4] y ha superado la entrada ganadora del Premio Hutter, aunque no es elegible debido a usando demasiada memoria.
Referencias
- ^ Mahoney, M. (2005), "Pesaje adaptativo de modelos de contexto para la compresión de datos sin pérdida", Florida Tech. Informe técnico CS-2005-16
- ^ Mahoney, M. "Programa de compresión de datos PAQ8" .
- ^ Matt Mahoney (25 de septiembre de 2015). "Benchmark de compresión de texto grande" . Consultado el 4 de noviembre de 2015 .
- ^ Matt Mahoney (23 de septiembre de 2015). "Benchmark de compresión de código abierto de Silesia" . Consultado el 4 de noviembre de 2015 .