Entropia da informação

RKA4JL - Imagine duas máquinas. Ambas emitem mensagens de saída a partir do alfabeto de A, B, C ou D. A máquina 1 gera cada símbolo aleatoriamente e todos ocorrem em 25% das vezes. Enquanto isso, a máquina 2 gera símbolos de acordo com as probabilidades a seguir. Qual das máquinas está produzindo mais informação? Claude Shannon sabiamente refez a questão. Se você tivesse que prever o próximo símbolo de cada máquina, qual seria o número mínimo de perguntas "sim ou não" que você espera responder? Olhamos a máquina 1. O meio mais eficiente é fazer uma pergunta a qual divida as possibilidades na metade. Por exemplo, na nossa primeira questão poderíamos perguntar se pode ser quaisquer dois símbolos, tal como: "é A ou B?", já que existe 50% de chance de ser A ou B e 50% de chance de ser C ou D. Depois de ter a resposta, podemos eliminar metade das possibilidades e ficaremos com apenas dois símbolos, ambos igualmente prováveis. Então apenas perguntamos: "é A?". E depois da segunda resposta, teremos identificado corretamente o símbolo. Podemos dizer que a incerteza da máquina 1 é de duas questões por símbolo. E a máquina 2? Assim como a máquina 1, podemos fazer duas perguntas para determinar o próximo símbolo. No entanto, dessa vez a probabilidade de cada símbolo é diferente, então faremos diferentes perguntas. Aqui, A tem 50% de chance de ocorrer e todas as outras juntas têm os outros 50%. Podemos iniciar perguntando se é A. Se for A, muito bom. Apenas uma questão, nesse caso. No entanto, ficamos com dois resultados igualmente prováveis: D ou B e C. Então perguntamos se é D. Se sim, terminamos com duas perguntas. Se não, teremos que fazer a terceira pergunta para identificar qual dos dois últimos símbolos será. Em média, quantas perguntas você espera fazer para determinar o símbolo da máquina 2? Isso pode ser explicado com uma analogia. Ao invés de assumir que queremos construir a máquina 1 e a máquina 2, podemos gerar símbolos saltando discos de uma quilha, em uma de duas direções igualmente prováveis. E, baseados em qual caminho ele cairá, podemos gerar o símbolo. Não precisamos adicionar um segundo nível ou um segundo salto para que tenhamos dois saltos que levam a quatro saídas igualmente prováveis. Baseado onde o disco cair, teremos as saídas A, B, C ou D. Agora, a máquina 2. Neste caso, o primeiro salto leva tanto a A, que ocorre em 50% das vezes, ou ao segundo salto, que pode ter a saída tanto em D, que ocorre em 25% das vezes, ou levar a um terceiro salto que segue para B ou C, 12,5% das vezes. Agora, façamos uma média ponderada como se segue. O número esperado de saltos é a probabilidade do símbolo A vezes 1 salto, mais a probabilidade de B vezes 3 saltos, mais a probabilidade de C vezes 3 saltos, mais a probabilidade de D vezes 2 saltos. Isso nos dá 1,75 salto. Agora, note a conexão entre as perguntas de "sim ou não" e os saltos justos. O número esperado de questões é igual ao número esperado de saltos. Então, a máquina 1 requer dois saltos para gerar um símbolo, enquanto adivinhar um símbolo desconhecido requer duas perguntas. Já a máquina 2 requer 1,75 salto. Precisamos perguntar 1,75 questão em média, o que significa que se precisamos adivinhar 100 símbolos de ambas as máquinas, esperamos perguntar 200 questões para a máquina 1 e 175 questões para a máquina 2. Isso significa que a máquina 2 está produzindo menos informação, pois existe menos incerteza ou surpresa a respeito de sua saída. E é isso. Claude Shannon chama esta medição da média da incerteza de "entropia". Ele usa a letra "H" para representar isso. A unidade entropia que Shannon escolheu é baseada na incerteza de uma virada de moeda justa e ele chama isso de "bit", o qual é equivalente a um salto justo. Podemos chegar ao mesmo resultado usando a analogia do nosso salto. Entropia, ou H, é a soma de cada símbolo da probabilidade daquele símbolo vezes o número de saltos. E como expressamos o número de saltos de uma maneira mais geral? Como já vimos, um número de saltos depende de quão baixo na árvore estamos. Podemos simplificar dizendo que o número de saltos é igual o logaritmo de base 2 de número de saída daquele nível. E o número de saída daquele nível também é baseado na probabilidade, onde o número de saídas daquele nível é igual a 1 dividido pela probabilidade daquela saída. O número de saltos, na verdade, é igual ao logaritmo de base 2 de 1 sobre a probabilidade daquele símbolo que nos dá a nossa última equação. Entropia, ou H, é a somatória da probabilidade daquele símbolo vezes o logaritmo de base 2 de 1 sobre a probabilidade daquele símbolo. E Shannon escreve isso um pouco diferente, o que nos dá a expressão invertida dentro do logaritmo, que nos leva a adicionar um negativo. Apesar disso, ambas as formas levam ao mesmo resultado. Então, vamos resumir: entropia é o máximo quando todas as saídas são igualmente prováveis. Qualquer hora que você se afasta de saídas igualmente prováveis ou introduza previsibilidade, a entropia precisa diminuir. A ideia fundamental é que se a entropia de uma fonte de informação diminui, isso significa que podemos fazer menos perguntas para adivinhar a saída. Graças a Shannon, o bit, que é uma unidade de entropia, é adotado como nossa medida de informação quantitativa ou medida de surpresa.