Diferença entre “informação” e “informação útil” na teoria algorítmica da informação

De acordo com a Wikipedia :

Informalmente, do ponto de vista da teoria algorítmica da informação, o conteúdo da informação de uma string é equivalente ao comprimento da menor representação possível possível dessa string.

Qual é a definição rigorosa informal análoga de "informação útil"? Por que a "informação útil" não é tomada como o conceito mais natural ou mais fundamental; ingenuamente, parece que uma sequência puramente aleatória deve, por definição, conter zero informação, então estou tentando entender o fato de que ela é considerada como tendo informações máximas pela definição padrão.

O conceito central aqui é a complexidade de Kolmogorov e, mais especificamente, a compressibilidade . Para obter uma sensação intuitiva de compressibilidade, considere duas seqüências de caracteres e B ∈ B ∗ , onde B = { 0 , 1 } . Deixei$A \in \mathbb{B}^*$$B \in \mathbb{B}^*$$\mathbb{B} = \{ 0,1 \}$

1010 1010 1010 e$A = 1010$ $1010$ $1010$ $1010$

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

Note que . Como poderíamos quantificar quanta informação A ou B possui? Se pensarmos na teoria clássica da informação, em geral, transmitir uma sequência de comprimento n leva n bits em média. No entanto, não podemos dizer quantos bits precisamos para transmitir uma sequência específica de comprimento n .$|A| = |B| = 16$$A$$B$$n$$n$$n$

Por que o conteúdo de informações de uma sequência aleatória não é zero?

Em uma análise mais detalhada, podemos ver que, de fato, . No entanto, é muito mais difícil de dizer se B tem quaisquer padrões óbvios em sua estrutura, pelo menos ele parece e se sente mais aleatória do que A . Como podemos encontrar um padrão em A , podemos compactar facilmente A e representá-lo com menos de 16 bits. Da mesma forma, como não é fácil detectar nenhum padrão em B , não podemos compactá-lo tanto. Portanto, podemos dizer que B tem mais informações do que um . Além disso, uma sequência aleatória de comprimento $A = 10^8$$B$$A$$A$$A$$16$$B$$B$$A$$n$possui informações máximas, pois não há como compactá-las e, portanto, representá-las com menos de bits.$n$

O que é informação útil, então?

Para informação útil , sim, há uma definição usando uma máquina de Turing . A informação útil em x ∈ B ∗ é$T$$x \in \mathbb{B}^*$

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

onde indica o comprimento de uma codificação de auto-limitante para uma máquina de Turing T . A notação é geralmente tal que C ( x ) indica a complexidade de Kolmogorov de X e C ( x | y ) a complexidade de Kolmogorov condicional de x dadas y .$l(T)$$T$$C(x)$$x$$C(x|y)$$x$$y$

Aqui incorpora a quantidade de informações úteis contidas em x . O que poderíamos perguntar é qual desses T selecionar entre aqueles que atendem ao requisito. O problema é separar um programa mais curto x ∗ em partes x ∗ = p q st p representa um T apropriado . Esta é realmente a própria idéia que gerou o comprimento mínimo da descrição (MDL) .$T$$x$$T$$x^*$$x^* = pq$$p$$T$

Pode ser porque "útil" é difícil de definir. Digamos que tenhamos uma mensagem altamente estruturada e rica em informações, que pode ser compactada no máximo por um fator de α para a mensagem y . Intuitivamente, x e y contêm a mesma quantidade de informações úteis; de fato, eles contêm a mesma quantidade de informações de acordo com a definição usual. Agora imagine um prefixo z de x do mesmo comprimento que y ; não deve conter informações mais úteis que x , portanto, não mais que y . No entanto, y é mais "aleatório" que z , pois $x$$\alpha$$y$$x$$y$$z$$x$$y$$x$$y$$y$$z$$z$pode ser compactado e não. Portanto, se tentarmos associar informações "úteis" à compressibilidade, poderemos encontrar o seguinte paradoxo: um prefixo de uma mensagem pode ter informações "úteis" mais altas que a mensagem inteira, aparentemente uma contradição.$y$

De um ponto de vista menos formal, acho que pode ajudar se você se distanciar da palavra "aleatório", pois está certo de que um conjunto de bits verdadeiramente aleatórios não armazena nenhuma informação no sentido prático. (Se eu criptografar um conjunto de nomes e enviar os valores criptografados para você, eles podem ter uma complexidade Kolmogorov muito alta, mas isso não ajudará a descobrir os nomes).

Mas pense dessa maneira. Se você vir um site em um idioma estrangeiro (por exemplo, sueco, supondo que você não o fale), será mais ou menos aleatório. Haverá alguma ordem para as palavras, mas não muito. No entanto, se você olhar para uma página da Web com texto parecido com este: 123456123456123456123456 ... e assim por diante, poderá entendê-la mais rapidamente. Se você não fala sueco, provavelmente conseguirá obter muito mais com isso, mesmo que a página sueca tenha o equivalente aos "seis primeiros números repetidos sequencialmente". Os sites contêm as mesmas informações, mas um parece aleatório para você. E, quanto à quantidade de espaço, o que você entende é bem menos eficiente que a página sueca, mesmo que armazene as mesmas informações. Você pode não achar essas informações "úteis" porque "

A noção de "informação" deve ser universal; portanto, o que parece bits aleatórios - e, portanto, inúteis - para você pode armazenar uma grande quantidade de informações para outra pessoa. A medida da informação pretende ser uma propriedade intrínseca da cadeia de caracteres e não pode depender do que faz ou não faz sentido para você e do que você pode ou não interpretar.

Outro ponto (mais técnico) que pode ajudar é que estou sendo um pouco falso aqui. Como Juho aponta, a informação édefinido em relação a quem o está interpretando. Você pode achar a página sueca completamente inútil como um veículo para obter informações, mas alguém que fala sueco pode achar que possui uma grande quantidade de informações. A definição reflete isso. No entanto, a partir da matemática, podemos aprender que a diferença entre a página mais curta (mais informativa para o espaço) para comunicar este site a você e a página mais curta que pode comunicá-lo a alguém que fala sueco pode diferir apenas por uma constante aditiva. Por quê? Porque para você, como um falante não-sueco, a maneira mais curta de armazenar a página que você entende é "os seis primeiros números inteiros repetidos sequencialmente". Isso pode ser um pouco mais longo que o sueco.

$$(\mbox{Most efficient representation of information in English}) \leq (\mbox{Most efficient representation in Swedish}) + (\mbox{Length of Swedish-English dictionary})$$ . Isso está ficando um pouco fora de tópico com a sua pergunta original, mas o que estou tentando dizer é que não importa muito quem está lendo as informações. A página sueca de aparência aleatória não era "útil" para você, mas é "útil" para outra pessoa, e você tem apenas uma quantidade constante de informações para poder usá-las.