Diferencia entre "información" e "información útil" en la teoría de la información algorítmica

De acuerdo con Wikipedia :

Informalmente, desde el punto de vista de la teoría de la información algorítmica, el contenido de información de una cadena es equivalente a la longitud de la representación autónoma más corta posible de esa cadena.

¿Cuál es la definición rigurosa informal análoga de "información útil"? ¿Por qué la "información útil" no se toma como el concepto más natural o más fundamental? ingenuamente parece que una cadena puramente aleatoria, por definición, debe contener información cero, por lo que estoy tratando de entender el hecho de que la definición estándar considera que tiene información máxima.

El concepto central aquí es la complejidad de Kolmogorov , y más específicamente la compresibilidad . Para tener una sensación intuitiva de compresibilidad, considere dos cadenas y B ∈ B ∗ , donde B = { 0 , 1 } . Dejar$A \in \mathbb{B}^*$$B \in \mathbb{B}^*$$\mathbb{B} = \{ 0,1 \}$

1010 1010 1010 , y$A = 1010$ $1010$ $1010$ $1010$

0110 0111 1001 .$B = 1011$ $0110$ $0111$ $1001$

Tenga en cuenta que . ¿Cómo podríamos cuantificar cuánta información tiene A o B ? Si pensamos en la teoría de la información clásica, en general, transmitir una cadena de longitud n toma n bits en promedio. Sin embargo, no podemos decir cuántos bits necesitamos para transmitir una cadena específica de longitud n .$|A| = |B| = 16$$A$$B$$n$$n$$n$

¿Por qué el contenido de información de una cadena aleatoria no es cero?

En una mirada más cercana, podemos ver que, de hecho, . Sin embargo, es mucho más difícil decir si B tiene ningún patrón obvio en su estructura, por lo menos, parece y se siente más al azar que A . Como podemos encontrar un patrón en A , podemos comprimir fácilmente A y representarlo con menos de 16 bits. Del mismo modo, dado que no es fácil detectar ningún patrón en B , no podemos comprimirlo tanto. Por lo tanto, podemos decir que B tiene más información que una . Además, una cadena aleatoria de longitud $A = 10^8$$B$$A$$A$$A$$16$$B$$B$$A$$n$tiene información máxima ya que no hay forma de que podamos comprimirla y, por lo tanto, representarla con menos de bits.$n$

¿Qué es información útil, entonces?

Para información útil , sí, hay una definición usando una máquina de Turing . La información útil en x ∈ B ∗ es$T$$x \in \mathbb{B}^*$

$$\min_T \space \{\space l(T) + C(x|T) : T \in \{ T_0, T_1, ... \} \},$$

donde indica la longitud de una codificación de auto-limitante para una máquina de Turing T . La notación es normalmente tal que C ( x ) indica la complejidad de Kolmogorov de x y C ( x | y ) la complejidad Kolmogorov condicional de x dado y .$l(T)$$T$$C(x)$$x$$C(x|y)$$x$$y$

Aquí la cantidad de información útil contenida en x . Lo que podríamos preguntar es qué T seleccionará entre aquellos que satisfagan el requisito. El problema es separar un programa más corto x ∗ en partes x ∗ = p q st p representa una T apropiada . Esta es realmente la idea que generó la longitud mínima de descripción (MDL) .$T$$x$$T$$x^*$$x^* = pq$$p$$T$

Podría ser porque "útil" es difícil de definir. Supongamos que tenemos un mensaje estructurado y rico en información que puede comprimirse como máximo por un factor de α en el mensaje y . Intuitivamente, x e y contienen la misma cantidad de información útil; de hecho, contienen la misma cantidad de información según la definición habitual. Ahora imagine un prefijo z de x de la misma longitud que y ; no debe contener más información útil que x , por lo tanto, no más que y . Sin embargo, y es más "aleatorio" que z , ya que $x$$\alpha$$y$$x$$y$$z$$x$$y$$x$$y$$y$$z$$z$puede ser comprimido y no pueden. Entonces, si tratamos de asociar información "útil" con compresibilidad, podríamos encontrar la siguiente paradoja: un prefijo de un mensaje podría tener mayor información "útil" que el mensaje completo, aparentemente una contradicción.$y$

Desde un punto de vista menos formal, creo que puede ayudar si se separa de la palabra "aleatorio", ya que tiene razón en que un conjunto de bits verdaderamente aleatorios no almacenan ninguna información en un sentido práctico. (Si cifro un conjunto de nombres y le envío los valores cifrados, es posible que tengan una complejidad de Kolmogorov muy alta, pero no le ayudará a descubrir los nombres).

Pero piénsalo de esta manera. Si ve un sitio web en un idioma extranjero (por ejemplo, sueco, suponiendo que no lo hable), se verá más o menos aleatorio. Habrá algún orden en las palabras, pero no mucho. Sin embargo, si mira una página web con un texto similar al siguiente: 123456123456123456123456 ... y así sucesivamente, podrá comprenderlo más rápidamente. Si no habla sueco, probablemente podrá sacarle mucho más provecho, incluso si la página web sueca dice el equivalente de "los primeros seis números repetidos secuencialmente". Los sitios web contienen la misma información, pero uno te parece aleatorio. Y por la cantidad de espacio, el que entiendes es mucho menos eficiente que la página web sueca, a pesar de que almacena la misma información. Es posible que no encuentre esta información "útil" porque '

La noción de "información" está destinada a ser universal, por lo que lo que parece algo aleatorio, y por lo tanto inútil, para usted puede almacenar una gran cantidad de información para otra persona. La medida de la información está destinada a ser una propiedad intrínseca de la cadena, y no puede depender de lo que tiene y no tiene sentido para usted, y de lo que puede y no puede interpretar.

Otro punto (más técnico) que puede ayudar es que estoy siendo poco sincero aquí. Como señala Juho, la información esdefinido en relación con quién lo está interpretando. Es posible que la página web sueca sea completamente inútil como vehículo para obtener información, pero alguien que hable sueco puede encontrar mucha información. La definición refleja esto. Sin embargo, de las matemáticas podemos aprender que la diferencia entre la página web más corta (más informativa para el espacio) para comunicarle este sitio web y la página web más corta que puede comunicarlo a alguien que habla sueco puede diferir solo por una constante aditiva. ¿Por qué? Porque para usted, como hablante no sueco, la forma más corta de almacenar la página que puede entender es "los primeros seis enteros repetidos secuencialmente". Esto puede ser bastante más largo que el sueco.

$$(\mbox{Most efficient representation of information in English}) \leq (\mbox{Most efficient representation in Swedish}) + (\mbox{Length of Swedish-English dictionary})$$ . Esto está un poco fuera de tema de su pregunta original, pero el punto que estoy tratando de hacer es que no importa demasiado quién está leyendo la información. La página web sueca de aspecto aleatorio no fue "útil" para usted, pero es "útil" para otra persona, y usted está a solo una cantidad constante de información lejos de poder usarla usted mismo.