Premio Hutter
# Premio Hutter

El premio de Hutter (Hutter Prize for Compression of Human Knowledge, en inglés) se le es otorgado a quien o a quienes contribuyan con mejoras en la compresión de datos en un archivo de texto en inglés de 100 MB llamado enwik8. Al valor del premio se le agregan 500 euros extra por cada porcentaje que la compresión en cuestión logre sin exceder los 50.000 euros que es la cantidad total disponible en la competición.

El archivo enwik8 consiste de los primeros 100.000.000 caracteres de una versión de la Wikipedia en inglés. El concurso es organizado por Marcus Hutter, Matt Mahoney y Jim Bowery.

## Objetivos

El objetivo del Premio Hutter es fomentar la investigación en inteligencia artificial (IA). Los organizadores creen que la compresión de texto y la IA son problemas equivalentes. Hutter demostró que el comportamiento óptimo de un agente de búsqueda en un entorno desconocido, pero computable, es suponer en cada paso que el entorno está probablemente controlado por uno de los programas más cortas compatibles con toda la interacción hasta ahora. Desafortunadamente, no existe una solución general, debido a que la complejidad de Kolmogorov no es computable. Hutter demostró que en el caso restringido (llamado AIXItl) donde el entorno se limita a tiempo t y el espacio l, que una solución se puede calcular en tiempo O(lt2), que todavía es intratable.

Los organizadores creen además que la compresión de texto en lenguaje natural es un problema difícil de IA, equivalente a pasar el test de Turing. Por lo tanto, el progreso hacia una meta representa un progreso hacia el otro. Sostienen que la predicción de qué caracteres son más probable que ocurra el siguiente en una secuencia de texto requiere un amplio conocimiento del mundo real. Un compresor de texto debe resolver el mismo problema con el fin de asignar los códigos más cortos a las secuencias de texto más probables.

## Reglas

El concurso está abierto a todo el mundo. El participante deberá presentar un programa de compresión y un descompresor que descomprime el archivo enwik8. También es posible enviar un archivo comprimido en lugar del programa de compresión. El tamaño total del archivo comprimido y descompresor (como un ejecutable Win32 o Linux) no debe ser mayor que el 99% del archivo del ganador anterior del premio. Por cada mejora del uno por ciento, el participante gana 500 euros. El programa de descompresión también debe cumplir con el tiempo de ejecución y las limitaciones de memoria, en la actualidad 10 horas en un Pentium 4 a 2 GHz con 1 GB de memoria. Estas limitaciones pueden ser rebajadas en el futuro.

Las presentaciones deben ser publicadas para permitir la verificación independiente. Hay un período de espera de 30 días para comentarios del público antes de otorgar un premio. Las normas no exigen la liberación de código fuente, a menos que dicha información sea solicitada bajo la licencia de código (como en el caso de PAQ, que está licenciado bajo GPL).

## Historia

El premio fue anunciado el 6 de agosto de 2006. La base inicial para el premio fue de 18.324.887 bytes, obtenidos por PAQ8F.

El 16 de agosto, Rudi Cilibrasi presentó una versión modificada del llamado PAQ8F RAQ8G que añade el modelado de paréntesis. Sin embargo, no cumplió con el umbral del 1%.

El mismo día, pero unas horas más tarde, Dmitry Shkarin presentó una versión modificada de su compresor DURILCA llamada DURILCA 0.5h, lo que mejoró la compresión en un 1,5%. Sin embargo, fue descalificado por usar 1,75 GB de memoria. La decisión de descalificar fue controvertida debido a que los límites de la memoria no se especificaron con claridad en las reglas en el momento.

El 20 de agosto, Alexander Ratushnyak presentó PAQ8HKCC, una versión modificada de PAQ8H, lo que mejoró la compresión de un 2,6% con respecto de PAQ8F. Continuó mejorando la compresión a 3,0% con PAQ8HP1 el 21 de agosto, 4% con PAQ8HP2 el 28 de agosto, un 4,9% con PAQ8HP3 el 3 de septiembre, un 5,9% con PAQ8HP4 el 10 de septiembre, y el 5,9% con PAQ8HP5 el 25 de septiembre. En ese punto fue galardonado con 3.416 euros y la nueva línea de base fue ajustada a 17.245.509 bytes. Desde entonces, ha mejorado éste en un 1% con PAQ8HP6 el 6 de noviembre, 2% con PAQ8HP7 el 10 de diciembre, y el 2,3% con PAQ8HP8 el 18 de enero de 2007. El tamaño comprimido es 16.681.045 bytes. El 10 de julio de 2007, una vez más rompió su marca con PAQ8HP12, logrando un tamaño de 16.481.655 bytes, y fue galardonado con 1.732 euros. El 23 de mayo de 2009, consiguió una nueva marca con decomp8, logrando un tamaño de 15.949.688 bytes y un premio de 1.614 euros.

