Ateoria matemática da informação estuda a quantificação, armazenamento e comunicação dainformação. Ela foi originalmente proposta porClaude E. Shannon em 1948 para achar os limites fundamentais no processamento de sinais e operações de comunicação, como as decompressão de dados.[1] No entanto, o termo “informação”, em geral, é usado como um substantivo abstrato de massa para denotar qualquer quantidade de dados, código ou texto armazenado, enviado, recebido ou manipulado em qualquer meio. A história do termo “informação” quanto dos vários conceitos a ele associados é complexa e o significado do termo “informação” varia em diferentes contextos.
A medida chave em teoria da informação é aentropia. A entropia é o grau de aleatoriedade, de indeterminação que algo possui. Quanto maior a informação, maior a desordem, maior a entropia. Quanto menor a informação, menor a escolha, menor a entropia.[4] Dessa forma, esse processo quantifica a quantidade de incerteza envolvida no valor de uma variável aleatória ou na saída de um processo aleatório. Por exemplo, a saída de cara ou coroa de uma moeda honesta (com duas saídas igualmente prováveis) fornece menos informação (menor entropia) do que especificar a saída da rolagem de um dado de seis faces (com seis saídas igualmente prováveis). Algumas outras medidas importantes em teoria da informação sãoinformação mútua,informação condicional ecapacidade de um canal.[5]
Aplicações de tópicos fundamentais da teoria da informação incluem compressão sem perdas de dados (comoZIP), e compressão com perdas de dados (comoMP3 eJPEG).
Essa teoria é considerada uma das fundadoras das ciências da comunicação[6]. Um dos criadores da teoria da informação,Weaver, defende que comunicação é o processo de transmissão plena de uma ideia[7]. E para isso a informação deve solucionar três níveis de problemas: técnico, semântico e de influência. Enquanto a maior parte das pessoas acredita que o principal aspecto da comunicação é a interpretação (nível semântico) ou o efeito (problema de influência), a teoria matemática da comunicação traz as questões técnicas para o centro da discussão. Esse nível envolve tudo que diz respeito à precisão na transmissão de informação que parte do emissor e vai até o receptor através de um sinal, seja de rádio, telefone ou televisão.[5] Sua importância se justapõe à dos outros dois níveis de problemas, porque eles dependem inevitavelmente da eficácia na transmissão das mensagens.
O campo está na intersecção da matemática, estatística,ciência da computação, física, neurobiologia eengenharia elétrica. Seu impacto é crucial, por exemplo, no sucesso das missões da sondaVoyager no espaço, no entendimento de buracos negros e da consciência humana, como na teoria de integração da informação (do inglês,Integrated Information Theory) proposta por Giulio Tononi.[5]
O termo "informação" especifica (sob o contexto dateoria da informação) o valor-surpresa de determinado conteúdo (ou mensagem) que consegue diminuir a quantidade de incerteza que existe em algum meio físico anteriormente à chegada do conteúdo informativo.[8][9][10][11] Colocando de outro modo, informação especifica o quanto a ignorância ou incerteza previamente existente foi reduzida em um meio assim que este recebeu a mensagem informativa. Usualmente, a consequência da mensagem informativa é tornar a incerteza previamente existente em certeza.[9]
Por exemplo, suponhamos que você precise identificar um certo indivíduo em uma lista composta por 30 pessoas. Você somente pode receber respostas do tipo Sim ou Não (respostas binárias). Perguntas como "É homem ou mulher?" e "Tem cabelo loiro?" me dão informações que diminuirão minha incerteza sobre qual indivíduo preciso achar. Em outras palavras, após eu encontrar o ser que estou procurando, a incerteza previamente existente se transformará em certeza.
A informação consiste em um estado (ou configuração) particular dos elementos que compõem um determinado meio que tem a capacidade de afetar esse próprio meio ou qualquer outro. Isso é o mesmo que dizer que a informação é uma propriedade que um meio pode possuir, e designa sobretudo os estados que podem resultar em algum efeito útil para alguma finalidade.[8][10][12][13][14]
O marco que estabeleceu a teoria da informação e chamou imediatamente a atenção mundial foi o artigoA Mathematical Theory of Communication escrito porClaude Shannon de julho a outubro de 1948.
Antes deste artigo, algumas abordagens teóricas ainda que limitadas vinham sendo desenvolvidas nos laboratórios da Bell, todas implicitamente assumindo eventos de igual probabilidade. O artigoCertain Factors Affecting Telegraph Speed deHarry Nyquist escrito em 1924 contém uma seção teórica que quantificainteligência e a velocidade de transmissão pela qual ela pode ser transmitida por um sistema de comunicação, estabelecendo a relação, onde é a velocidade de transmissão da inteligência, é o número de níveis de tensão para cada intervalo de tempo, e é uma constante.[15] Em 1928,Ralph Hartley publicou o artigoTransmission of Information, onde aparece a palavrainformação como uma medida da capacidade do destinatário para distinguir diferentes sequências de símbolos, levando à expressão, onde e representam, respectivamente, o número de símbolos possíveis e o número de símbolos na transmissão. Inicialmente, a unidade natural da transmissão foi definida como sendo o dígito decimal, sendo, posteriormente, renomeada para hartley em uma clara homenagem.[16]Alan Turing em 1940, durante a 2ª Guerra Mundial, aplicou ideias similares como parte da análise estatística para decifrar a criptografia da máquina alemã Enigma.
No artigo seminal de Shannon, introduz-se pela primeira vez um modelo quantitativo e qualitativo da comunicação, apresentando-a como um processo estatístico subjacente à teoria da informação. Shannon inicia seu artigo dizendo
"O problema fundamental da comunicação é reproduzir em um dado ponto, exata ou aproximadamente, uma mensagem produzida em outro ponto."
Antes de prosseguir é importante definir a notação utilizada para as variáveis aleatórias discretas. Dado uma variável aleatória, que pode assumir valores, podemos representá-la como:
Onde é o i-ésimo valor que pode ser assumido pela variável. Cada um dos valores podem acontecer com probabilidade, não necessariamente iguais. A distribuição de probabilidades de é representada como:
Nesse caso, com, representa a probabilidade do valor acontecer. Esse tipo de distribuição pode ser representada com um gráfico de barras como na figura a seguir.
Distribuição de probabilidades de uma variável discreta.
Para uma dada distribuição de probabilidades a condição é cumprida.
*
Dado duas variáveis aleatórias e, cada uma podendo assumir quatro valores, logo e, com distribuições de probabilidade e. A distribuição conjunta das variáveis pode ser determinada medindo-se a frequência de ocorrência dos pares, com.
Medindo o número de ocorrências dos pares, em uma amostragem de tamanho suficientemente grande, é possível determinar as probabilidades de cada par dividindo o número de ocorrências de cada um deles por. Dando a distribuição de probabilidades conjunta (do inglês,joint probability distribution).
A distribuição conjunta pode ser por um histograma tridimensional, como o mostrado a seguir.
Distribuição de probabilidade conjunta das variáveis X e Y.
A partir da distribuição conjunta de, é possível obter as distribuições de ou de (chamadas de distribuições marginais), através de um processo chamadomarginalização. Por exemplo, se quisermos obter o valor da distribuição para então devemos fazê-lo somando por todos os valores de para:
Fazendo isso fixando cada um dos possíveis valores de $X$, obtemos a distribuição marginal:
Para obter a distribuição marginal basta seguir o mesmo procedimento, fixando, em cada um de seus possíveis valores:
A teoria da informação é baseada na teoria de probabilidades e estatística. Ela se preocupa com medidas de informação das distribuições de probabilidade associadas com variáveis aleatórias. Grandezas importantes da teoria da informação são aentropia, uma medida de informação de uma única variável aleatória, einformação mútua, uma medida de informação em comum entre das variáveis aleatórias.
Na formulação das grandezas da teoria da informação, escolheu-se utilizar bases logarítmicas (para manter propriedades como a aditividade da entropia), mais especificamente a entropia de Shannon é definida com logaritmos na base 2. A unidade utilizada para quantificar informação é obit (baseado no logaritmo base 2), muito embora outras existam, como onat (baseada no logaritmo natural), e ohartley (baseado no logaritmo na base 10).[16]
Tendo citado as aplicações da teoria da informação, seu contexto histórico de surgimento e mencionado as grandezas envolvidas, chegou o momento de discutir mais a fundo alguns dos conceitos bases da teoria, começando pela unidade de informação, obit.
A fim de entender de forma intuitiva o que significa dizer 1bit de informação, imagine a seguinte situação, um viajante, decide sair de sua cidade, no ponto marcado com a letra "A" na figura abaixo e chegar ao seu destino no ponto "D".
Caminho percorrido pelo viajante. Em cada bifurcação ele recebia a instrução esquerda (0) direita (1) até alcançar seu destino final.
O caminho entre "A" e "D" possui várias bifurcações (como os pontos "B" e "C"). Assumindo que o viajante desconhece o caminho, em cada cidade que passar (representada pelas bifurcações) ele pede uma informação, perguntando se deve seguir à direita ou à esquerda. Na figura anterior, dizer que ele deve seguir a esquerda é o mesmo que mostrar odígito binário 0 a ele, e um sinal de que deve seguir a direita o mesmo que mostrar o dígito 1.
Dessa forma, como é possível ver pela figura, ele terá que pedir informação nos pontos "A", "B" e "C". Note que independente do destino () o número de perguntas para alcançá-lo (nesse caso) é sempre três. Ou seja, escolher entre oito destinos requer três perguntas:
Note que o o expoente do número dois na equação anterior é igual ao número de perguntas feitas. Define-se então que para escolher entre um dos oito possíveis destinos é necessária uma quantidade de informação igual a.
Aplicando logaritmo de base dois na expressão anterior, temos:
É importante salientar que como o viajante poderia igualmente ter escolhido qualquer um dos destinos finais possíveis eles são todos equiprováveis com probabilidade.
De forma análoga, para o caso em que se tem possíveis destinos, esupondo que o viajante possa escolher qualquer um deles com igual probabilidade, a quantidade de informação, em bits, para alcançar um dos possíveis destinos é dada pela relação a seguir:
Com isso conclui-se quebits é a quantidade informação necessária para se escolher entre alternativas equiprováveis, ou é a quantidade de informação necessária para escolher entre duas alternativas equiprováveis.
Usarei de outro exemplo para explicar a medida de Informação de Shannon ou surpresa. Imagine nesse caso, uma moeda desonesta (enviesada), que tem probabilidade de dar cara e probabilidade de dar coroa.
Por você estar acostumado que a jogada dessa moeda quase sempre dêcara, esse resultado não te surpreende. Mas um resultadocoroa te surpreende por conta da "raridade" do evento. Pensando nisso, uma forma natural de se definir essa surpresa que se tem, seria como algo proporcional ao inverso da probabilidade de ocorrência do evento, de modo que quando menor essa probabilidade maior a surpresa.
Shannon definiu essa grandeza como:
Utilizando o logaritmo na base dois mantêm-se a propriedade de aditividade dessa grandeza.
Dessa maneira podemos calcular a surpresa da jogada da moeda retornar cara () ou coroa () de acordo com a definição anterior.
A fim de chegar na formulação matemática da entropia, imagine por exemplo uma variável aleatória, que pode assumir dois valores distintos e com probabilidades e, respectivamente. Seguindo a notação definida na seção: Variáveis aleatórias discretas, temos:
e,
A informação de Shannon associada a cada um dos valores é:
e,
Na prática, geralmente nós não estamos interessados em saber a surpresa de um valor em particular que uma variável aleatória pode assumir, e sim a surpresa associada com todos os possíveis valores que essa variável aleatória pode ter. De modo a obter a surpresa associada a todos possíveis valores que pode assumir, define-se a entropia como a informação de Shannon média:
Caso, possa assumir valores, a expressão anterior pode ser escrita de modo mais geral.
Uma aplicação direta para a equação da entropia definida anteriormente pode ser obtida com o exemplo um dado de seis faces. Representando o dado pela variável aleatória, temos que:
Considere a moeda honesta, representada pela variável aleatória:
e,
E a moeda enviesada, como aquela utilizada para exemplificar a informação de Shannon, representada pela variável aleatória.
e,
Note que um resultadocara é representado pelo dígito 0 e um resultadocoroa por um dígito 1. A entropia de cada uma das moedas pode ser calculada, sendo então:
e,
Nesse caso a entropia da moeda honesta é maior do que a da moeda desonesta, mas qual o significado disso? O que a medida de entropia pode me dizer? Essas questões serão abordadas na próxima seção, onde uma abordagem conceitual de entropia será tratada.
Fundamentalmente a entropia é uma medida deincerteza. Isso pode ser visto no exemplo anterior, na moeda honesta é muito difícil dizer qual será o resultado antes de jogá-la, alguém pode arriscar dizer que o resultado será cara ou coroa, mas aincerteza continua maior do que no caso da moeda enviesada (logo com entropia também maior), onde podemos prever com certa tranquilidade que o resultado da jogada será cara.
No fundo, essa incerteza está ligada à previsibilidade do valor que será assumido por uma dada variável aleatória, prever um valor sorteado entre 100 valores equiprováveis (por exemplo, adivinhar o número que saíra em um dado de 100 faces) é mais difícil do que prever esse valor, caso esse dado seja enviesado e uma das faces tenha probabilidade alta de aparecer.
Agora sabemos também que a entropia é uma medida de informação, como uma coisa se relaciona a outra?
Justamente por ter mais incerteza sobre a possível saída de uma variável aleatória, você precisa de mais informação, para "adivinhar" essa saída. Isso é análogo ao número de perguntas que o nosso viajante da seção "Escolhendo destinos e o bit de informação" teve de fazer para chegar ao seu destino. Desse modo quanto maior a entropia maior a incerteza e maior a informação que você precisa para "adivinhar" uma possível saída que a variável aleatória pode apresentar.
Para ilustrar o que foi dito, considere a seguinte situação, estacionaram seu carro em um estacionamento de 8 vagas dispostas como no desenho abaixo, para adivinhar em que vaga ele está você tem permissão de realizar perguntas sim ou não.
Esquema do estacionamento.
Você pode começar: "O carro está na direita?", caso a resposta seja sim, isso restringe as possíveis vagas pela metade, sendo elas as vagas 3, 4, 7 e 8. A próxima perguntar pode ser: "O carro está ao norte?", com uma resposta não, restam duas possibilidades, a vaga 7 ou 8. Uma ultima pergunta: "O carro está a direita?", basta para determinar em qual delas seu carro está. Nesse caso cada resposta sim/não te da 1 bit de informação. Como são necessárias três perguntamos podemos dizer que a entropia é igual a 3 bits.
Assim fica fácil entender a ideia de que a entropia está relacionada com a quantidade de informação necessária para "adivinhar" a resposta (ou uma possível saída de uma variável aleatória).
No exemplo das vagas, como a probabilidade do carro estar em qualquer uma das vagas é igual, cada bit de informação diminui o número de respostas possíveis pela metade.
O teorema de codificação da fonte é fundamental para todos os meios de comunicação, uma vez que ele estabelece limites de como mensagens podem ser transmitidas e além disso, ele mostra que existem maneiras mais e menos eficientes de se fazer isso, dependendo da mensagem enviada. Aqui apenas uma ideia do que ele se trata será dada, para entendimento maior consulte as referências.
Antes de mais nada considere um canal, sem fonte de ruído, onde uma mensagem é codificada em sua fonte (source) por umencoder, enviada pelo canal até seu destino, decodificada por umdecoder e interpretada pela pessoa alvo.
Esquema de um canal sem ruído.
Define-se a Capacidade do canal como sendo numericamente igual ao número de dígitos binários comunicados por segundo. Se tivermos 1 bit por dígito binário a capacidade é definida em unidades de bits por segundo. Essa definição pode ser mais bem explorada matematicamente, mas para os fins aqui propostos, a definição dada é suficiente.
Dada as definições, imagine que se deseja transmitir uma série de $m$ símbolos, representados pela variável, sendo a distribuição de probabilidades de e sua entropia. O teorema de codificação da fonte pode ser enunciado como segue:
"Dada a distribuição $S$ com entropia $H(S)$, medida em bits por símbolo $s$, e um canal com capacidade $C$ bits por segundo. Então é possível codificar os símbolos $s$ enviados pela fonte de tal modo que a mensagem seja transmitida na capacidade máxima $C$ do canal."
Imagine uma fonte que envia números de 1 a 8, com igual probabilidade, então temos nossa variável, podemos determinar a entropia decomo sendo.
Caso os números sejam transmitidos por um canal com capacidade, o teorema de codificação da fonte garante que existe um modo de codificar os símbolos em de modo tal que eles sejam transmitidos com capacidade máxima, no caso 3 bits/s.
Um modo de codificar os valores de 1 a 8, seria representá-los por números binários de dígitos binários, como na tabela a seguir, que indica o símbolo e sua respectivo código.
Simbolo
Código
1
001
2
010
3
011
4
100
5
101
6
110
7
111
8
1000
Sendo o número de dígitos binários utilizado por código para cada símbolo de. A eficiência é um número entre 0 e 1, calculada como a razão da entropia de por.
Nesse caso,
Para esse caso simples é muito fácil encontrar a codificação necessária para transmitir os símbolos com máxima eficiência. Mas para maioria dos casos não é assim, e são necessários algoritmos mais rebuscados, como por exemplo acodificação de Huffman, que não será discutida aqui, mas consiste em codificar os símbolos mais frequentes com códigos mais simples (que usam menos dígitos binários por exemplo). Ocódigo Morse (figura abaixo), se baseia nesse princípio, onde letras como oE mais frequentes na língua inglesa são representados por sequência mais simples, e outras letras menos frequentes como oJ por sequências mais complicadas, isso ajuda a aumentar a eficiência com a qual a mensagem é enviada.
Código Morse.
É importante salientar que o código Morse precede o artigo de Shannon, sendo portanto desconhecidos esses limites teóricos para comunicar informação.
Dado duas variáveis aleatórias e, a informação mútua entre elas é a quantidade de informação média que ganhamos sobre após observar um valor isolado de
A informação mútua entre e é definida como:
Para valores de e valores de. A expressão anterior pode ser trabalhada de forma a ser escrita como:
Onde é entropia da distribuição conjunta dada já definida anteriormente.
Um modo alternativo de enxergar o conceito de informação mútua pode ser obtido considerando-se a entropia da saída em relação ao ruído do canal. Se não conhecemos o valor da entrada então nossa incerteza sobre o valor de é dado por sua entropia. Mas se conhecemos o valor de então nossa incerteza sobre é reduzida de para um valor chamado deentropia condicional, que é a incerteza média do valor de após ser observado. Assim:
Como informação mútua e uma grandeza simétrica:
Onde é a incerteza média que temos sobre o valor de após temos observado, e portanto a incerteza média em que não pode ser atribuída a.
Se e são estatisticamente independentes, então conhecer um valor de não nos dá nenhuma informação sobre evice versa. Nesse caso cada valor de probabilidade da distribuição conjunta pode ser escrito como:
Substituindo na definição de informação mútua, e realizando algumas manipulações temos:
Diferente do que se considerou na seção onde tratamos do teorema de codificação da fonte, os canais geralmente possuem ruído (figura abaixo). Por esse motivo se considera que a saída do canal é igual a entrada mas um ruído do canal, é possível achar uma expressão do ruído do canal como a seguir.
Esquema de canal com ruído.
Da expressão nos leva a:
Se o valor de é conhecido, então a incerteza em é zero, logo ele não tem nenhuma contribuição na entropia condicional, dando:
Entretanto o valor do ruído é independente do valor de, logo, o que nos permite reescrever a equação anterior como:
Comparando as equações e a anterior podemos concluir que:
Logo, a entropia do ruído é igual a entropia condicional.
↑WEAVER, W. A teoria matemática da comunicação. COHN, Gabriel (Org.). *Comunicação e indústria cultural*. 3. ed. São Paulo: Nacional, 1977. [S.l.: s.n.]
