Los datos aleatorios son incompresibles.
Hay dos resultados relevantes:
- Independientemente del código que utilice, Shannon demostró que el número esperado de bits que necesita para representar algunos datos no puede ser menor que la entropía de la fuente de datos. Si la fuente es una distribución uniforme en, digamos, secuencias de dígitos binarios [math] n [/ math], entonces la entropía es igual a [math] n [/ math], por lo que en espera de su código, sea lo que sea, no comprimir
- Pero ese resultado está en expectativa; en la práctica, ¿no podemos tener suerte? Por ejemplo, si lanzo una moneda un millón de veces y por pura suerte todos ellos lanzan cara, entonces los datos serían comprimibles, ¿no? Bueno, sí, pero eso es extremadamente improbable: puede demostrar que la probabilidad de que pueda comprimir una cadena binaria aleatoria de cualquier longitud por [math] k [/ math] bits o más es menor que [math] 2 ^ {- k }[/mates]. Por lo tanto, la probabilidad de que pueda comprimir más de unos pocos bits es astronómicamente baja. Y para poder hacerlo, necesitaría usar un código que realmente expanda la mayoría de las entradas.
Los datos aleatorios son incompresibles.
- ¿Puede un modelo de aprendizaje automático reemplazar completamente un sistema basado en reglas?
- Andrew Ng: ¿La ira del aprendizaje automático está causando una fuga de cerebros de otros campos igualmente importantes y atractivos, pero menos glamorosos?
- ¿Qué es el código del cambio?
- ¿Cuál es el principio de funcionamiento del subespacio aleatorio en el aprendizaje automático?
- ¿Qué es la informática estocástica?
Con eso fuera del camino, voy a tomar esta pregunta un poco más literalmente: ¿cuál es la relación de compresión máxima posible? Bueno, voy a lanzar una moneda [matemáticas] n [/ matemáticas] veces. Acordemos con el siguiente código: si todos los flips resultan en caras, entonces representaré este resultado con la secuencia binaria “0”. De lo contrario, representaré el resultado con la secuencia binaria “1”, seguida de todos los resultados de los lanzamientos de monedas. Ahora lanzo las monedas y ¿qué sabes? ¡Todos son cabezas! Eso significa que he comprimido los datos por un factor de [math] n [/ math]. Mejor que eso es imposible: mi palabra clave debe tener al menos un bit de largo, de lo contrario no puedo representar todos los demás resultados posibles. Así que todavía puedes tener una compresión extremadamente buena, pero como indican los resultados anteriores, tienes que ser muy afortunado por eso.