Teoria da Informação

Até a década de 1930, engenheiros eletricistas podiam construir circuitos eletrônicos para resolver problemas lógicos e matemáticos, mas a maioria o fazia sem qualquer processo, de forma particular, sem rigor teórico para tal. Isso mudou com a tese de mestrado de Claude E. Shannon de 1937, A Symbolic Analysis of Relay and Switching Circuits. Enquanto tomava aulas de Filosofia, Shannon foi exposto ao trabalho de George Boole, e percebeu que tal conceito poderia ser aplicado em conjuntos eletro-mecânicos para resolver problemas de lógica. Tal ideia, que utiliza propriedades de circuitos eletrônicos para a lógica, é o conceito básico de todos os computadores digitais. Shannon desenvolveu a teoria da informação no artigo de 1948 A Mathematical Theory of Communication, cujo conteúdo serve como fundamento para áreas de estudo como compressão de dados e criptografia.

Modernamente, a Teoria da informação ou Teoria matemática da comunicação é um ramo da teoria da probabilidade e da matemática estatística que lida com sistemas de comunicação, transmissão de dados, criptografia, codificação, teoria do ruído, correção de erros, compressão de dados, etc. Ela não deve ser confundida com tecnologia da informação e biblioteconomia.

Claude E. Shannon (1916-2001) é conhecido como “o pai da teoria da informação”. Sua teoria foi a primeira a considerar comunicação como um problema matemático rigorosamente embasado na estatística e deu aos engenheiros da comunicação um modo de determinar a capacidade de um canal de comunicação em termos de ocorrência de bits. A teoria não se preocupa com a semântica dos dados, mas pode envolver aspectos relacionados com a perda de informação na compressão e na transmissão de mensagens com ruído no canal.

No processo de desenvolvimento de uma teoria da comunicação que pudesse ser aplicada por engenheiros eletricistas para projetar sistemas de telecomunicação melhores, Shannon definiu uma medida chamada de entropia, definida como:

H(X) = -\sum_{x \in \mathbb{X}} p(x) \log p(x)

onde log é o logaritmo na base 2, que determina o grau de caoticidade da distribuição de probabilidade pi e pode ser usada para determinar a capacidade do canal necessária para transmitir a informação.

A medida de entropia de Shannon passou a ser considerada como uma medida da informação contida numa mensagem, em oposição à parte da mensagem que é estritamente determinada (portanto prevísivel) por estruturas inerentes, como por exemplo a redundância da estrutura das linguagens ou das propriedades estatísticas de uma linguagem, relacionadas às frequências de ocorrência de diferentes letras (monemas) ou de pares, trios, (fonemas) etc., de palavras. Veja cadeia de Markov.

A entropia como definida por Shannon está intimamente relacionada à entropia definida por físicos. Boltzmann e Gibbs fizeram um trabalho considerável sobre termodinâmica estatística. Este trabalho foi a inspiração para se adotar o termo entropia em teoria da informação. Há uma profunda relação entre entropia nos sentidos termodinâmico e informacional. Por exemplo, o demônio de Maxwell necessita de informações para reverter a entropia termodinâmica e a obtenção dessas informações equilibra exatamente o ganho termodinâmico que o demônio alcançaria de outro modo.

Outras medidas de informação úteis incluem informação mútua, que é uma medida da correlação entre dois conjuntos de eventos. Informação mútua é definida por dois eventos X e Y como:

\ M(X,Y)=H(X,Y)-H(X)-H(Y)

onde H(X,Y) é a entropia conjunta (join entropy) ou

\ H(X,Y)=-\sum_{x,y} p(x,y)\log p(x,y)

Informação mútua está relacionada de forma muito próxima com testes estatísticos como o teste de razão logarítmica e o teste Chi-square.

A teoria da informação de Shannon é apropriada para medir incerteza sobre um espaço desordenado. Uma medida alternativa de informação foi criada por Fisher para medir incerteza sobre um espaço ordenado. Por exemplo, a informação de Shannon é usada sobre um espaço de letras do alfabeto, já que letras não tem ‘distâncias’ entre elas. Para informação sobre valores de parâmetros contínuos, como as alturas de pessoas, a informação de Fisher é usada, já que tamanhos estimados tem uma distância bem definida.

Diferenças na informação de Shannon correspondem a um caso especial da distância de Kullback-Leibler da estatística Bayesiana, uma medida de distância entre distribuições de probabilidade a priori e a posteriori.

Andrei Nikolaevich Kolmogorov introduziu uma medida de informação que é baseada no menor algoritmo que pode computá-la (veja complexidade de Kolmogorov).

A complexidade de Kolmogorov é uma teoria da informação e da aleatoriedade, profunda e sofisticada, que trata da quantidade de informação de objetos individuais, medida através do tamanho de sua menor descrição algorítmica. Ela é uma noção moderna de aleatoriedade, e refere-se a um conceito pontual de aleatoriedade, ao invés de uma aleatoriedade média como o faz a teoria das probabilidades. Ela é um ramo derivado da teoria da informação de Claude E. Shannon, embora hoje possa ser considerada uma área de pesquisa madura e autônoma.

Complexidade de Kolmogorov define uma nova teoria da informação, chamada teoria algorítmica da informação (por tratar com algoritmos).

A complexidade de Kolmogorov tem sua origem nos anos 1960, quando Andrei Kolmogorov, Ray Solomonoff e Gregory Chaitin desenvolveram, de forma independente, uma teoria da informação baseada no tamanho dos programas para a Máquina de Turing. Convencionou-se chamar a área genericamente de “complexidade de Kolmogorov” em homenagem ao famoso matemático russo, e fundador da área, Andrei Nikolaevich Kolmogorov (1903-1987).

A complexidade de Kolmogorov está definida sobre o conjunto de strings binárias (seqüências de zeros e uns). Ela associa a cada string binária um valor numérico que é sua “complexidade”.

A complexidade de Kolmogorov pode ser definida simplificadamente como o tamanho do menor programa (ou descrição algoritmica) que computa na Máquina de Turing uma determinada string binária.

Exige-se que o conjunto de descrições (programas) forme um conjunto livre de prefixo, e se chama esta complexidade de “complexidade de prefixo”, representada por K(x). Para enfatizar a Máquina que está sendo usada para definir a complexidade podemos escrever KM(x) ao invés de K(x), onde M é uma Máquina de Turing em particular.

Também podemos definir uma complexidade condicional, K(x | y), definida como o tamanho do programa que computa x a partir de y, que é dado como entrada do programa. Intuitivamente, K(x | y) representa a quantidade de informação que devemos adicionar à informação em y para computar x.

Importante que o conceito de descrição seja bem fundamentado (ou seja, formalmente definido como um programa para a máquina de Turing) para evitar paradoxos. Paradoxos (ou antinômias) são bastante freqüentes na história da matemática. Podemos citar o famoso “paradoxo do barbeiro”, de autoria de Bertrand Russel, que diz que “o barbeiro é aquele que barbeia os homens que não barbeiam a si próprios”. O paradoxo é obtido ao perguntar se o barbeiro barbeia a si próprio.

Da forma como foi definido, pode parecer que a complexidade de Kolmogorov permanece dependente da máquina escolhida como máquina de referência. No entanto, existe um teorema (chamado Teorema da Invariância) que prova que todas as máquinas universais (ou seja, que tem a capacidade de simular todas as outras máquinas de Turing concebíveis) resultam no mesmo valor de complexidade, a não ser por uma constante que é assintoticamente desprezável: K_{U1}(x)\leq K_{U2}(x)+c, para alguma constante c, e U1 e U2 são duas máquinas universais quaisquer.

Isto significa que a complexidade passa a ser um atributo intrínseco do objeto, independente da máquina universal escolhida como máquina de referência.

O objetivo original do trabalho de Kolmogorov era obter uma definição formal de seqüência aleatória. Kolmogorov observou que algumas seqüências binárias podiam ser comprimidas algoritmicamente. Nos dias de hoje, a maioria das pessoas está acostumada a usar programas de compressão de dados, tais como winzip, gzip, arj, etc. Assim, a idéia que dados possam ser comprimidos não é de todo estranha.

Fica fácil perceber que um número como 1.000.000.000 na base 10 pode ser facilmente expresso como 109, enquanto que o número 5.321.478.927, escolhido arbitrariamente, não poderia ser expresso desta forma compacta.

Se tomarmos as strings binárias 11111111111111111111 e 10110011010111011010, aceitaríamos facilmente a segunda como sendo resultante do lançamento sucessivo de uma moeda honesta (1=cara e 0=coroa). No entanto, dificilmente a primeira seqüência poderia ser resultado de um experimento realmente aleatório. Notamos que a primeira string poderia ser computada pelo programa:

FOR I=1 TO 20 PRINT 1

Que é um programa pequeno em relação ao tamanho da string. Já a segunda string não pode ser computada por um programa tão curto, pois ele deverá conter a própria string literalmente armazenada dentro do programa:

PRINT 10110011010111011010

Kolmogorov postulou que seqüências que não podem ser comprimidas algoritmicamente em uma descrição de tamanho muito menor que a seqüência original são seqüências aleatórias (no sentido estocástico do termo). Esta definição só funciona se forem admitidas apenas descrições dentro de uma classe de descrições livres de prefixo (ou seja que nenhuma descrição seja prefixo de outra da classe).

Solomonoff propôs o uso da regra de Bayes para obter previsão indutiva, ou seja, para prever a seqüência de uma string binária. Para isto ele usou como probabilidade prévia a probabilidade universal, que pode ser definida como 2 – K(x), porque ela domina toda probabilidade prévia semi-computável concebível. Isto constitui-se no núcleo dos métodos de inteligência artificial MDL (minimum description length) e MML (minimum message length).

A complexidade K(x | y) induz um conceito de distância (ou similaridade), chamada distância de informação, que é uma medida a priori e absoluta sobre o conjunto das strings binárias. Esta distância pode ser aplicada em diversos e diferentes contextos de forma muito similar a outras medidas de distância definidas na matemática. O interessante é que podemos aproximar esta medida usando um programa compressor de dados e efetuar medições empíricas. Destacam-se como aplicações desta distância o reconhecimento de genoma, a classificação automática de música, e o estabelecimento de uma hierarquia de linguagens humanas.

Chaitin construiu um paradoxo envolvendo o tamanho dos programas que constitui-se em uma prova alternativa ao que ficou conhecido como prova de Gödel (ou Teorema da incompletude de Gödel). Chaitin baseou-se no paradoxo de Berry que supõe considerar o menor número inteiro positivo que não pode ser definido por uma frase em português com menos que 1.000.000.000 de caracteres. No entanto, a própria definição do problema define o número e tem menos de 1.000.000.000 de caracteres, o que é uma contradição. Isto resulta que strings não podem ser produzidas por programas que tenham menos complexidade que a própria string, sendo isto um limite dos sistemas formais.

Uma outra interessante aplicação de complexidade de Kolmogorov é o número mágico e místico Ω, proposto por Chaitin, definido como:

Ω = ∑ 2 – | p | .
p

Nesta fórmula, p representa um programa que pára (finaliza) e | p | é o tamanho deste programa. É interessante observar que 0\leq \Omega\leq 1, representando Ω a probabilidade de um programa qualquer parar (finalizar). Ω é um número real aleatório (cujos dígitos formam uma seqüência aleatória) e não computável (ou seja, não pode ser computado por um programa na máquina de Turing). Além disto, Ω contém em si, da forma mais compacta possível, todas as verdades matemáticas possíveis de serem expressas.

Diversas outras aplicações da teoria foram desenvolvidas desde então: inteligência artificial, linguagens formais, complexidade computacional, teoria dos grafos, biotecnologia, etc.