Teoria da informação visual

– http://colah.github.io/posts/2015-09-Visual-Information/
Postado em 14 de outubro de 2015

Adoro a sensação de ter uma nova maneira de pensar sobre o mundo. Eu particularmente amo quando há alguma idéia vaga que se formaliza em um conceito concreto. A teoria da informação é um excelente exemplo disso.
A teoria da informação nos proporciona uma linguagem precisa para descrever muitas coisas. Quão incerto estou? Quanto me diz saber a resposta para a pregunta A sobre a resposta da pregunta B? Quão semelhante é um conjunto de crenças a outras? Eu tive versões informais dessas idéias desde que eu era uma criança, mas a teoria da informação cristaliza em idéias precisas e poderosas. Essas idéias têm uma enorme variedade de aplicações, desde a compressão de dados, a física quântica, a aprendizagem de máquinas e vastos campos intermediários.
Infelizmente, a teoria da informação pode parecer meio intimidante. Eu não acho que haja algum motivo pelo que deveria ser. Na verdade, muitas idéias básicas podem ser explicadas de forma visual!

Visualizando Distribuições de Probabilidade
Antes de mergulhar na teoria da informação, pensemos em como podemos visualizar as distribuições de probabilidade simples. Nós precisaremos disso mais tarde, e é conveniente abordar agora. Como um bônus, esses truques para visualizar a probabilidade são bastante úteis em si mesmos!
Estou na Califórnia. Às vezes chove, mas principalmente está sol! Digamos que está sol o 75% do tempo. É fácil fazer uma imagem disso:

Na maioria dos dias, eu uso camisola de manga curta, mas alguns dias eu uso casaco. Digamos que eu uso casaco o 38% do tempo. Também é fácil fazer uma imagem disso!

E se eu quiser visualizar ambos ao mesmo tempo? Bem, é fácil se eles não interagem – se eles são o que chamamos independente. Por exemplo, se eu uso uma camisola de manga curta ou uma capa de chuva hoje não realmente interage com o que o tempo vai ser na semana que vem. Podemos desenhar isso usando um eixo para uma variável e um para a outra:

Observe as linhas verticais e horizontais diretas que vão até o final. Isso é o que é a independência! 1 A probabilidade de usar um casaco não muda em resposta ao fato de que estará a chover em uma semana. Em outras palavras, a probabilidade de eu usar um casaco e que vai chover na próxima semana é apenas a probabilidade de eu usar um casaco, vezes a probabilidade de chover. Eles não interagem.
Quando as variáveis interagem, há uma probabilidade extra para pares particulares de variáveis e a probabilidade faltante para outras pessoas. Há uma probabilidade extra de que eu use um casaco e está a chover porque as variáveis estão correlacionadas, elas se tornam mais prováveis. É mais provável que eu use um casaco em um dia que chove do que a probabilidade de usar um casaco em um dia e chove em algum outro dia aleatório.
Visualmente, isto parece que alguns dos quadrados aumentam com a probabilidade extra, e outros quadrados se diminuem porque o par de eventos é improvável juntos:

Mas, embora isso pareça legal, não é muito útil para entender o que está a acontecer.
Em vez disso, vamos nos concentrar em uma variável como o tempo. Sabemos o quão provável é que esteja sol ou a chover. Para ambos os casos, podemos observar as probabilidades condicionais. Qual é a probabilidade de que va usar uma t-shirt, se está sol? Qual é a probabilidade de usar um casaco se estiver a chover?

Há 25% de chance de chover. Se está a chover, há 75% de chances de vestir um casaco. Então, a probabilidade de chover e usar um casaco é de 25% vezes 75%, o que é de aproximadamente 19%. A probabilidade de chover e eu estiver a vestir um casaco é a probabilidade de estar a chover, vezes a probabilidade de eu usar um casaco se estiver a chover. Nós escrevemos isso:
p(chuva, casaco)=p(chuva) ⋅ p(casaco/chuva)
Este é um único caso de uma das identidades mais fundamentais da teoria da probabilidade:
p(x, y)=p(x) ⋅ p(y|x)
Nós estamos avaliando a distribuição, dividindo-a no produto de duas peças. Primeiro, olhamos para a probabilidade de uma variável, como o clima, assumir um certo valor. Então, olhamos para a probabilidade de que outra variável, como a minha roupa, tenha um certo valor condicionado pela primeira variável.
A escolha de com qual variável começar é arbitrária. Podemos começar tão facilmente com a atenção à minha roupa e, em seguida, olhar para o clima condicionado a ela. Isso pode parecer um pouco menos intuitivo, porque entendemos que há uma relação causal do clima que influencia o que eu uso e não o contrário… mas ainda funciona!
Passemos por um exemplo. Se escolhermos um dia aleatório, há uma chance de 38% de usar um casaco. Se sabemos que estou a usar um casaco, é provável que esteja a chover? Bem, é mais provável que use um casaco em dia de chuva do que em dia de sol, mas a chuva é um pouco rara na Califórnia, e assim que acontece que há uma chance de 50% que esteja a chover. E assim, a probabilidade de chover e eu estar a vestir um casaco é a probabilidade de eu estar a usar um casaco (38%), vezes a probabilidade de chover se eu estivesse a usar um casaco (50%) que é aproximadamente 19%.
p(chuva, casaco) = p(casaco) ⋅ p(chuva|casaco)
Isso nos dá uma segunda maneira de visualizar exatamente a mesma distribuição de probabilidade.

Note-se que os rótulos têm significados ligeiramente diferentes do que no diagrama anterior: t-shirt e casaco são agora probabilidades marginais, a probabilidade de eu usar essa roupa sem considerar o clima. Por outro lado, há agora duas etiquetas de chuva e sol, pois as probabilidades de elas são condicionais para eu vestir uma t-shirt e um casaco, respectivamente.
(Você pode ter ouvido falar do Teorema de Bayes. Se você quiser, você pode pensar nisso como a maneira de traduzir entre essas duas formas diferentes de exibir a distribuição de probabilidade!)

Aparte: O paradoxo de Simpson
Esses truques para visualizar as distribuições de probabilidade realmente são úteis? Eu acho que eles são! Vai demorar um pouco em usá-los para visualizar a teoria da informação, então eu gostaria de seguir uma pequena tangente e usá-los para explorar o paradoxo de Simpson. O paradoxo de Simpson é uma situação estatística extremamente não-intuitiva. É realmente difícil de entender num nível intuitivo. Michael Nielsen escreveu um ensaio encantador, “Reinventing Explication”, que explorou diferentes maneiras de explicá-lo. Gostaria de tentar tomar a minha própria oportunidade, usando os truques que desenvolvemos na seção anterior.
São testados dois tratamentos para cálculos renais. Metade dos pacientes recebe tratamento A enquanto a outra metade recebe tratamento B. Os pacientes que receberam o tratamento B tiveram maior probabilidade de sobreviver do que aqueles que receberam o tratamento A.

No entanto, os pacientes com pequenas pedras renais eram mais propensos a sobreviver se tomassem o tratamento. Os pacientes com grandes pedras renais também eram mais propensos a sobreviver se tomassem o tratamento A! Como isso pode ser?
O núcleo da questão é que o estudo não foi devidamente randomizado. Os pacientes que receberam o tratamento A provavelmente apresentaram pedras renais grandes, enquanto os pacientes que receberam tratamento B tiveram maior probabilidade de ter pedras renais pequenas.

Acontece que os pacientes com pequenas pedras nos rins são muito mais propensos a sobreviver em geral.
Para entender isso melhor, podemos combinar os dois diagramas anteriores. O resultado é um diagrama tridimensional com a taxa de sobrevivência separada para pedras pequenas e grandes nos rins.

Agora podemos ver que, tanto no caso pequeno quanto no grande caso, o Tratamento A supera o Tratamento B. O tratamento B pareceu melhor porque os pacientes que se aplicaram eram mais propensos a sobreviver em primeiro lugar!

Códigos
Agora que temos maneiras de visualizar a probabilidade, podemos mergulhar na teoria da informação.
Deixe-me falar sobre meu amigo imaginário, Bob. Bob gosta muito de animais. Ele fala constantemente sobre animais. Na verdade, ele apenas diz quatro palavras: “cão”, “gato”, “peixe” e “pássaro”.
Algumas semanas atrás, apesar de ser uma invenção da minha imaginação, Bob mudou-se para a Austrália. Além disso, ele decidiu que ele só queria comunicar-se em binário. Todas as minhas mensagens (imaginárias) de Bob são assim:

Para comunicar-se, Bob e eu devemos estabelecer um código, uma maneira de mapear as palavras em seqüências de bits.

Para enviar uma mensagem, Bob substitui cada símbolo (palavra) pela palavra-chave correspondente e, em seguida, os concatena para formar a cadeia codificada.

Códigos de comprimento variável
Infelizmente, os serviços de comunicação na imaginária-Austrália são caros. Eu tenho que pagar US $5 por cada mensagem que recebo de Bob. Já mencionei que Bob gosta de falar muito? Para evitar ir a falência, Bob e eu decidimos que deveríamos investigar se havia alguma maneira de reduzir o nosso tempo médio de mensagem.
Como se vê, Bob não diz todas as palavras igualmente frequentemente. Bob gosta muito de cães. Ele fala sobre cachorros o tempo todo. Na ocasião, ele falará sobre outros animais – especialmente o gato que o seu cão gosta de perseguir -, mas principalmente ele fala sobre cães. Aqui está um gráfico da sua freqüência de palavras:

Isso parece promissor. Nosso código antigo usa palavras-chave de 2 bits de comprimento, independentemente do comum que elas são.
Há uma ótima maneira de visualizar isso. No diagrama a seguir, usamos o eixo vertical para visualizar a probabilidade de cada palavra, p(x) e o eixo horizontal para visualizar o comprimento da palavra-chave correspondente, L(x). Observe que a área é o comprimento médio de uma palavra de código que enviamos – neste caso, 2 bits.

Talvez possamos ser muito inteligentes e criar um código de comprimento variável onde as palavras-chave para palavras comuns sejam especialmente curtas. O desafio é que existe uma concorrência entre palavras-chave – tornando-as mais curtos nos obriga a fazer os outros mais longos. Para minimizar o comprimento da mensagem, gostaríamos que todas as palavras-chave fossem curtas, mas especialmente queremos que as comumente usadas o sejam. Portanto, o código resultante tem palavras-chave mais curtas para palavras comuns (como “cão”) e palavras-chave mais longas para palavras menos comuns (como “pássaro”).

Vamos visualizar isso de novo. Observe que a palavra-chave mais comum tornou-se mais curta, mesmo que as palavras incomuns se tornassem mais longas. O resultado foi, na rede, uma menor quantidade de área. Isto corresponde a um menor comprimento de palavra de código esperado. Em média, o comprimento de uma palavra de código é agora de 1,75 bits!

(Você pode perguntar-se: por que não usar 1 por si só como uma palavra de código? Infelizmente, isso causaria ambigüidade quando decodificarmos as cadeias codificadas. Falaremos sobre isso mais brevemente.)
Acontece que este código é o melhor código possível. Não há nenhum código que, para esta distribuição, nos dê um comprimento médio de palavras-chave inferior a 1,75 bits.
Existe simplesmente um limite fundamental. Comunicando o que a palavra foi dita, que evento dessa distribuição ocorreu, exige que nos comuniquemos pelo menos 1,75 bits em média. Por mais inteligente que seja o nosso código, é impossível que o comprimento médio da mensagem seja menor. Chamamos entropia da distribuição a esse limite fundamental – vamos discutir isso muito mais detalhadamente em breve.

Se queremos entender esse limite, o cerne da questão é entender o trade off entre fazer algumas palavras-chave curtas e outras longas. Uma vez que entendamos isso, poderemos entender quais são os melhores códigos possíveis.

O espaço das palavras-chave
Existem dois códigos com um comprimento de 1 bit: 0 e 1. Existem quatro códigos com um comprimento de 2 bits: 00, 01, 10 e 11. Cada bit que você adiciona duplica o número de códigos possíveis.

Estamos interessados em códigos de comprimento variável, onde algumas palavras-chave são mais longas do que outras. Podemos ter situações simples em que temos oito palavras de código com 3 bits de duração. Podemos também ter misturas mais complicadas, como duas palavras-chave de comprimento 2 e quatro palavras-chave de comprimento 3. O que decide quantos códigos podemos ter de diferentes comprimentos?
Lembre-se de que Bob transforma as suas mensagens em cordas codificadas, substituindo cada palavra pela sua palavra-chave e concatenando-as.

Há uma questão ligeiramente sutil a que se deve ter cuidado ao elaborar um código de comprimento variável. Como dividimos a cadeia codificada de volta nas palavras-chave? Quando todas as palavras-chave são do mesmo comprimento, é fácil – basta com dividir a corda cada dois passos. Mas, como existem palavras-chave de diferentes comprimentos, precisamos realmente prestar atenção ao conteúdo.
Nós realmente queremos que o nosso código seja facilmente decodificável, com apenas uma maneira de decodificar uma cadeia codificada. Nós nunca queremos que seja ambíguo quais palavras-chave compõem a cadeia codificada. Se tivéssemos algum símbolo especial de “fim de palavra-chave”, isso seria fácil.2 Mas nós não temos – estamos a enviar apenas 0s e 1s. Precisamos poder visualizar uma seqüência de palavras-chave concatenadas e dizer onde cada uma delas pára.
É muito possível fazer códigos que não sejam decodificáveis. Por exemplo, imagine que 0 e 01 eram palavras-chave. Então, não ficará claro qual é a primeira palavra de código da seqüência de caracteres codificada 0100111 – pode ser qualquer um! A propriedade que queremos é que, se vemos uma palavra-chave particular, não deveria haver uma versão mais longa que também seja uma palavra-chave. Outra maneira de colocar isso é que nenhuma palavra de código deve ser o prefixo de outra palavra-chave. Isso chama-se propriedade do prefixo, e os códigos que obedecem chamam-se códigos de prefixo.
Uma maneira útil de pensar sobre isso é que cada palavra de código requer um sacrifício a partir do espaço de possíveis palavras-chave. Se tomarmos a palavra de código 01, perdemos a habilidade de usar qualquer palavra de código, é um prefixo. Não podemos usar 010 ou 011010110 por ambiguidade – eles estão perdidos para nós.

Uma vez que um quarto de todas as palavras-chave começam com 01, sacrificamos um quarto de todas as palavras-chave possíveis. Esse é o preço que pagamos em troca de uma palavra-chave de apenas 2 bits! Por sua vez, esse sacrifício significa que todas as outras palavras-chave precisam ser um pouco mais longas. Há sempre esse tipo de troca entre os comprimentos das diferentes palavras-chave. Uma breve palavra de código exige que você sacrifique mais espaço das possíveis palavras-chave, impedindo que outras palavras-chave sejam curtas. O que precisamos descobrir é qual é a melhor troca que podemos fazer!

Codificações Ótimas
Você pode pensar nisso como ter um orçamento limitado para gastar em obter palavras-chave curtas. Pagamos por uma palavra-chave sacrificando uma fração de possíveis palavras-chave.
O custo de comprar uma palavra de código de comprimento 0 é 1, todas as palavras-chave possíveis – se você quiser ter uma palavra-chave de comprimento 0, você não pode ter nenhuma outra palavra de código. O custo de uma palavra de código do comprimento 1, como “0”, é 1/2 porque metade das possíveis palavras-chave começa com “0”. O custo de uma palavra de código do comprimento 2, como “01”, é 1/4 porque um quarto de todas as palavras-chave possíveis começam com “01”. Em geral, o custo das palavras-chave diminui exponencialmente com o comprimento da palavra-chave.

Note-se que se o custo decai como exponencial (natural), é tanto a altura como a área! 3
Queremos palavras-chave curtas porque queremos comprimentos de mensagens médias curtas. Cada palavra de código torna o comprimento médio da mensagem mais longo pela sua probabilidade, vezes o comprimento da palavra-chave. Por exemplo, se precisarmos enviar uma palavra de código com 4 bits de comprimento, 50% do tempo, o nosso comprimento médio da mensagem é 2 bits maior do que seria se não enviássemos essa palavra-chave. Podemos imaginar isso como um retângulo.

Estes dois valores estão relacionados pelo comprimento da palavra-chave. O valor que pagamos determina o comprimento da palavra-chave. O comprimento da palavra-chave controla quanto adiciona ao comprimento médio da mensagem. Podemos visualizar os dois juntos, assim.

As palavras-chave curtas reduzem o comprimento médio da mensagem, mas são caras, enquanto as palavras-chave longas aumentam o comprimento médio da mensagem, mas são baratas.

Qual é a melhor maneira de usar o nosso orçamento limitado? Quanto devemos gastar na palavra-chave para cada evento?
Assim como alguém quer investir mais em ferramentas que usamos regularmente, queremos gastar mais em palavras-chave usadas com freqüência. Existe uma maneira particularmente natural de fazer isso: distribua o nosso orçamento na proporção de quão comum é um evento. Então, se um evento acontecer 50% do tempo, nós gastamos 50% do nosso orçamento ao comprar uma palavra-chave curta para isso. Mas se um evento acontecer apenas 1% do tempo, gastamos apenas 1% do nosso orçamento, porque não nos importa muito se a palavra-chave é longa.
Isso é uma coisa muito natural a fazer, mas é a melhor coisa a fazer? É, e eu vou provar isso!
A seguinte prova é visual e deve ser acessível, mas terá trabalho para passar e definitivamente é a parte mais difícil deste ensaio. Os leitores devem sentir-se livres de ignorar para aceitar isso como dado e pular para a próxima seção.
Vamos representar um exemplo concreto onde precisamos comunicar qual dos dois eventos possíveis aconteceu. O evento a acontece p(a) do tempo e evento b acontece p(b) do tempo. Distribuímos o nosso orçamento da maneira natural descrita acima, gastando p(a) do nosso orçamento em obter a, uma palavra-chave curta, e p(b) ao obter b uma palavra-chave curta.

Os limites de contribuição de custos e longitude encaixam-se bem. Isso significa alguma coisa?
Bem, considere o que acontece com o custo e a contribuição da duração se mudarmos ligeiramente o comprimento da palavra-chave. Se aumentar ligeiramente o comprimento da palavra-chave, a contribuição da duração da mensagem aumentará em proporção à sua altura no limite, enquanto o custo diminuirá em proporção à sua altura no limite.

Então, o custo para tornar a palavra-chave para “a” mais curta é p(a). Ao mesmo tempo, não nos importamos com o comprimento de cada palavra de código, nós nos preocupamos com eles em proporção ao quanto temos que usá-las. No caso de a, isso é p(a). O benefício para nós de tornar a palavra-chave para “a” um pouco mais curto é p(a).
É interessante que ambos os derivados sejam os mesmos. Isso significa que o nosso orçamento inicial tem a propriedade interessante que, se você tivesse um pouco mais para gastar, seria igualmente bom investir em tornar qualquer palavra de código mais curta. O que realmente nos interessa, no final, é a relação benefício/custo – é o que decide o que devemos investir mais. Neste caso, a proporção é p(a)/p(a), que é igual a um. Isso é independente do valor de p(a) – é sempre um. E podemos aplicar o mesmo argumento a outros eventos. O benefício/custo é sempre um, então faz sentido igual para investir um pouco mais em qualquer um deles.

Infinitamente, não faz sentido mudar o orçamento. Mas isso não é uma prova de que é o melhor orçamento. Para provar isso, consideraremos um orçamento diferente, onde gastaremos um pouco mais em uma palavra-chave à custa de outra. Investimos menos € em b e investimos em “a” em vez disso. Isso torna a palavra-chave para a um pouco mais curta, e a palavra-chave para b um pouco mais.
Agora, o custo de comprar uma palavra-chave mais curta para a é p(a)+€, e o custo de comprar uma palavra-chave mais curta para b é p(b)-€. Mas os benefícios ainda são os mesmos. Isso leva a relação de custo de benefício para comprar “a” para ser p(a)/p(a)+€ que é inferior a um. Por outro lado, a relação custo-benefício da compra b é p(b)/p(b)-€ que é superior a um.

Os preços não são mais equilibrados. b é um acordo melhor do que a. Os investidores gritam: “Compre b! Venda a!” Fazemos isso e terminamos no nosso plano de orçamento original. Todos os orçamentos podem ser melhorados, mudando para o nosso plano original.
O orçamento original – investindo em cada palavra de código em proporção com a frequência com que usamos – não era apenas a coisa natural a fazer, era a melhor coisa a fazer. (Embora esta prova apenas funcione para duas palavras-chave, generaliza facilmente para mais.)
(Um leitor cuidadoso pode ter percebido que é possível que o nosso ótimo orçamento sugira códigos onde as palavras-chave têm comprimentos fracionários. Isso parece bastante preocupante! O que significa isso? Bem, é claro, na prática, se você quer comunicar-se enviando uma palavra-chave única, você deve arredondar. Mas, como veremos mais adiante, há um sentido muito real em que é possível enviar palavras-chave fracionárias quando enviamos muitas por vez. Vou pedir-lhe que seja paciente comigo por agora!)
Calculando a Entropia
Lembre-se de que o custo de uma mensagem de comprimento L é 1/2L. Podemos inverter isso para obter o comprimento de uma mensagem que custa uma determinada quantidade: log2/(1 custo). Uma vez que gastamos p(x) em uma palavra de código para x, o comprimento é log2/(1p (x)). Essas são as melhores escolhas de comprimentos.

Anteriormente, discutimos como há um limite fundamental para o quão curto pode-se obter a mensagem média para comunicar eventos de uma distribuição de probabilidade específica, p. Este limite, o comprimento médio da mensagem usando o melhor código possível, chama-se entropia de p, H(p). Agora que conhecemos os comprimentos ideais das palavras-chave, podemos realmente calculá-lo!

(As pessoas geralmente escrevem entropia como H(p)=- Σp(x)log2(p(x)) usando o log de identidade (1/a) = -log(a). Acho que a primeira versão é mais intuitiva e continuará a usá-lo nesta ensaio.)
Não importa o que eu faça, em média, eu preciso enviar pelo menos esse número de bits se eu quiser comunicar que evento ocorreu.
A quantidade média de informações necessárias para comunicar algo tem implicações claras para a compressão. Mas existem outras razões pelas quais devemos nos preocupar com isso? Sim! Ele descreve o quão incerto eu estou e dá uma maneira de quantificar a informação.
Se eu soubesse com certeza o que aconteceria, não teria que enviar uma mensagem! Se houver duas coisas que poderiam acontecer com 50% de probabilidade, eu só preciso enviar 1 bit. Mas se houver 64 coisas diferentes que poderiam acontecer com a mesma probabilidade, eu teria que enviar 6 bits. Quanto mais concentrada a probabilidade, mais eu posso criar um código inteligente com mensagens de médias baixas. Quanto mais difusa a probabilidade, mais longas as minhas mensagens devem ser.
Quanto mais incerto o resultado, mais aprendo, em média, quando descubro o que aconteceu.

Cross-Entropy
Pouco antes de sua mudança para a Austrália, Bob casou com a Alice, outra invenção da minha imaginação. Para minha surpresa, e também os outros personagens na minha cabeça, Alice não era amante dos cães. Ela era amante dos gatos. Apesar disso, os dois conseguiram encontrar um terreno comum na sua obsessão compartilhada com animais e tamanho de vocabulário muito limitado.

Os dois dizem as mesmas palavras, apenas em diferentes freqüências. Bob fala sobre cachorros o tempo todo, Alice fala sobre gatos o tempo todo.
Inicialmente, Alice me enviou mensagens usando o código de Bob. Infelizmente, as suas mensagens eram mais longas do que precisavam ser. O código de Bob foi otimizado para a sua distribuição de probabilidade. Alice tem uma distribuição de probabilidade diferente, e o código é subóptimo para isso. Enquanto o comprimento médio de uma palavra de código quando Bob usa o seu próprio código é de 1,75 bits, quando Alice usa o seu código é 2,25. Seria pior se os dois não fossem tão parecidos!
Esse comprimento – o comprimento médio de comunicação de um evento de uma distribuição com o código ótimo para outra distribuição – chama-se entropia cruzada. Formalmente, podemos definir entropia cruzada como: 4

Neste caso, é a entropia cruzada de Alice a freqüência de palavras dos amantes dos gatos em relação à freqüência de palavras de Bob dos amantes dos cães.

Para reduzir o custo de nossas comunicações, pedi a Alice que use o seu próprio código. Para meu alívio, isso reduziu o comprimento da mensagem média. Mas introduziu um novo problema: às vezes, Bob usaria acidentalmente o código de Alice. Surpreendentemente, é pior para Bob usar acidentalmente o código de Alice do que para Alice usar o dele!
Então, agora temos quatro possibilidades:
– Bob usando o seu próprio código (H(p) = 1,75 bits)
– Alice usando o código de Bob (Hp(q) = 2,25 bits)
– Alice usando o seu próprio código (H(q) = 1.75 bits)
– Bob usando o código de Alice (Hq(p) = 2.375 bits)
Isso não é tão intuitivo como se poderia pensar. Por exemplo, podemos ver que Hp(q) ≠ Hq(p). Existe alguma maneira de ver como esses quatro valores se relacionam?
No diagrama a seguir, cada subtrama representa uma dessas 4 possibilidades. Cada subtrama visualiza o comprimento médio da mensagem da mesma forma que os nossos diagramas anteriores. Eles estão organizados em um quadrado, de modo que, se as mensagens vierem da mesma distribuição, as parcelas estão lado a lado, e se eles usam os mesmos códigos, eles estão um em cima do outro. Isso permite que você visualize as distribuições e os códigos juntos.

Você pode ver por que Hp(q) ≠ Hq(p)? Hq(p) é longo porque há um evento (azul) que é muito comum em p, mas obtém um código longo porque é muito incomum em q. Por outro lado, eventos comuns em q são menos comuns em p, mas a diferença é menos drástica, então Hp(q) não é tão alto.

A entropia cruzada não é simétrica.
Então, por que você deveria se preocupar com a entropia cruzada? Bem, a entropia cruzada nos dá uma maneira de expressar o quanto são diferentes as duas distribuições de probabilidade. Quanto mais diferentes são as distribuições p e q, quanto maior a entropia cruzada de p em relação a q será maior do que a entropia de p.

Da mesma forma, quanto mais diferente é p de q, quanto mais a entropia cruzada de q em relação a p será maior do que a entropia de q.

A coisa realmente interessante é a diferença entre a entropia e a entropia cruzada. Essa diferença é o quão longas são as nossas mensagens porque usamos um código otimizado para uma distribuição diferente. Se as distribuições forem iguais, essa diferença será zero. À medida que a diferença cresce, ela aumentará.
Chamamos a essa diferença da divergência Kullback-Leibler, ou apenas a divergência de KL. A divergência de KL de p em relação a q, Dq(p), 5 é definida: 6
Dq(p) = Hq(p)-H(p)
A coisa realmente agradável sobre a divergência de KL é que é como uma distância entre duas distribuições. Ele mede como são diferentes! (Se você levar essa idéia a sério, você chega a geometria da informação.)
Cross-Entropy e KL divergência são incrivelmente úteis na aprendizagem de máquinas. Muitas vezes, queremos que uma distribuição esteja próxima de outra. Por exemplo, podemos querer que uma distribuição prevista esteja próxima da verdade. A divergência de KL nos dá uma maneira natural de fazer isso, e isso aparece em todos os lugares.

Entropia e variáveis múltiplas
Voltemos ao nosso exemplo anterior de tempo e roupas:

Minha mãe, como muitos pais, às vezes se preocupa por não me vestir adequadamente para o tempo. (Ela tem uma causa razoável de suspeita – muitas vezes não usei casacos no inverno.) Então, ela muitas vezes quer saber o tempo e as roupas que eu uso. Quantos bits eu tenho que mandar-lhe para comunicar-lhe isso?
Bem, a maneira fácil de pensar sobre isso é aplanar a distribuição de probabilidade:

Agora, podemos descobrir as palavras-chave ideais para eventos dessas probabilidades e calcular o comprimento médio da mensagem:

Nós chamamos a isso entropia conjunta de X e Y, definida

Isso é exatamente o mesmo que a nossa definição normal, exceto com duas variáveis ao invés de uma.
Uma maneira um pouco melhor de pensar sobre isso é evitar aplanar a distribuição, e apenas pensar nos comprimentos do código como uma terceira dimensão. Agora, a entropia é o volume!

Mas suponha que minha mãe já conhece o clima. Ela pode verificar isso nas notícias. Agora, quanta informação eu preciso de fornecer?
Parece que eu preciso enviar, no entanto, muita informação porque preciso para comunicar as roupas que eu uso. Mas eu realmente preciso enviar menos, porque o tempo implica fortemente o que vestirei! Vamos considerar o caso onde está a chover e onde está sol separadamente.

Em ambos os casos, não preciso enviar muita informação em média, porque o tempo me dá um bom palpite sobre qual será a resposta correta. Quando está sol, posso usar um código especial otimizado para o sol, e quando está a chover, posso usar um código otimizado. Em ambos os casos, envio menos informações do que se eu usei um código genérico para ambos. Para obter a quantidade média de informações que preciso enviar a minha mãe, eu apenas coloco esses dois casos juntos…

Nós chamamos isso entropia condicional. Se você o formalizar numa equação, você obtém:

Informação mútua
Na seção anterior, observamos que conhecer uma variável pode significar que a comunicação de outra variável requer menos informações.
Uma boa maneira de pensar sobre isso é imaginar quantidades de informações como barras. Essas barras se sobrepõem se houver informações compartilhadas entre elas. Por exemplo, algumas das informações em X e Y são compartilhadas entre elas, então H(X) e H(Y) são barras sobrepostas. E como H(X, Y) é a informação em ambos, é a união das barras H(X) e H(Y).7

Uma vez que pensamos sobre as coisas dessa maneira, muitas coisas se tornam mais fáceis de ver.
Por exemplo, anteriormente observamos que é preciso mais informações para comunicar X e Y (a “entropia conjunta”, H(X, Y)) do que é necessário para comunicar apenas X (a “entropia marginal”, H(X)). Mas se você já conhece Y, então é preciso menos informações para comunicar X (a “entropia condicional”, H(X|Y)) do que seria se você não fizesse!

Isso parece um pouco complicado, mas é muito simples quando pensamos sobre isso na perspectiva da barra. H(X|Y) é a informação que precisamos enviar para comunicar X a alguém que já conhece Y, a informação em X que também não está em Y. Visualmente, isso significa que H(X|Y) é a parte de H (X) que não se sobrepõe com H(Y).
Agora você pode ler a desigualdade H(X,Y) ≥ H(X) ≥ H(X|Y) logo após o seguinte diagrama.

Outra identidade é que H(X,Y) = H(Y) + H(X|Y). Ou seja, as informações em X e Y são as informações em Y mais a informação em X que não está em Y.

Novamente, é difícil de ver nas equações, mas é fácil ver se você está a pensar em termos dessas barras de informações sobrepostas.
Neste ponto, partimos as informações em X e Y de várias maneiras. Nós temos a informação em cada variável, H(X) e H(Y). Temos a união da informação em ambos, H(X, Y). Nós temos a informação que está em um, mas não no outro, H(X|Y) e H(Y|X). Muito disso parece girar em torno da informação compartilhada entre as variáveis, a interseção de suas informações. Chamamos essa “informação mútua”, I(X,Y), definida como: 8
I(X,Y) = H(X) + H(Y) – H(X,Y)
Esta definição funciona porque H(X) + H(Y) possui duas cópias da informação mútua, uma vez que está em X e Y, enquanto H(X, Y) tem apenas uma. (Considere o diagrama de barras anterior).
Estreitamente relacionado à informação mútua é a variação de informação. A variação de informação é a informação que não é compartilhada entre as variáveis. Podemos defini-la assim:
V(X,Y) = H(X,Y) – I(X,Y)
A variação da informação é interessante porque nos dá uma métrica, uma noção de distância, entre diferentes variáveis. A variação de informação entre duas variáveis é zero se conhecer o valor de um, diz-lhe o valor do outro e aumenta à medida que se tornam mais independentes.
Como isso se relaciona com a divergência de KL, que também nos deu uma noção de distância? Bem, a divergência de KL nos dá uma distância entre duas distribuições sobre a mesma variável ou conjunto de variáveis. Em contrapartida, a variação de informação nos dá distância entre duas variáveis distribuídas conjuntamente. A divergência de KL está entre distribuições, variação de informação dentro de uma distribuição.
Podemos juntar tudo isso em um único diagrama que relaciona esses diferentes tipos de informações:

Bits Fracionados
Uma coisa muito pouco intuitiva sobre a teoria da informação é que podemos ter números fracionários de bits. Isso é muito estranho. O que significa ter meio bit?
Aqui está a resposta fácil: muitas vezes, estamos interessados no comprimento médio de uma mensagem e não em qualquer comprimento específico da mensagem. Se metade do tempo se envia um único bit, e metade do tempo se envia dois bits, em média um envia um e meio pedaços. Não há nada estranho sobre as médias serem fracionárias.
Mas essa resposta é realmente esquivando o problema. Muitas vezes, os comprimentos ideais das palavras-chave são fracionários. O que isso significa?
Para ser concreto, consideremos uma distribuição de probabilidade onde um evento, a, ocorre 71% do tempo e outro evento, b, ocorre 29% do tempo.

O código ideal usaria 0,5 bits para representar a e 1,7 bits para representar b. Bem, se queremos enviar uma única dessas palavras-chave, simplesmente não é possível. Nós somos forçados a arredondar para um número inteiro de bits, e enviar em média 1 bit.
… Mas se estamos a enviar várias mensagens ao mesmo tempo, verifica-se que podemos fazer melhor. Consideremos a comunicação de dois eventos desta distribuição. Se os enviássemos de forma independente, precisamos enviar dois bits. Podemos fazer melhor?

Metade do tempo, precisamos comunicar aa, 21% do tempo que precisamos enviar ab ou ba, e 8% do tempo que precisamos comunicar bb. Novamente, o código ideal envolve números fracionários de bits.

Se usarmos os comprimentos das palavras-chave, obteremos algo como isto:

Estes códigos nos dão um comprimento médio de mensagem de 1,8 bits. Isso é inferior aos 2 bits quando os enviamos de forma independente. Outra maneira de pensar nisso é que estamos a enviar 0,9 bits em média para cada evento. Se enviássemos mais eventos de uma só vez, ficaria ainda mais pequeno. Como n tende a infinito, a sobrecarga devido ao arredondamento do nosso código desapareceria, e o número de bits por palavra-chave se aproximaria da entropia.
Além disso, note que o comprimento ideal da palavra-código para a foi de 0,5 bits e o comprimento ideal da palavra-código para aa foi de 1 bit. Os comprimentos de palavras-chave ideais são adicionados, mesmo quando são fracionários! Então, se nós comunicarmos muitos eventos ao mesmo tempo, os comprimentos serão adicionados.
Existe um sentido muito real em que se pode ter números fracionários de informações, mesmo que os códigos reais só possam usar números inteiros.
(Na prática, as pessoas usam esquemas de codificação específicos que são eficientes em diferentes extensões. A codificação de Huffman, que é basicamente o tipo de código que esboçamos aqui, não manipula bits de fração muito graciosamente – você tem que agrupar símbolos, como nós fizemos acima ou usa truques mais complicados para aproximar o limite de entropia. A codificação aritmética é um pouco diferente, mas eleva elegantemente os bits fracionários para serem otimizados assintoticamente.)
Conclusão
Se nos preocupamos em comunicar-nos com um número mínimo de bits, essas ideias são claramente fundamentais. Se nos preocupamos com a compressão de dados, a teoria da informação aborda as principais questões e nos dá as abstrações fundamentalmente corretas. Mas e se não nos importar – eles são algo além de curiosidades?
As idéias da teoria da informação se apresentam em muitos contextos: aprendizagem de máquinas, física quântica, genética, termodinâmica e até jogos de azar. Os praticantes nestes campos geralmente não se preocupam com a teoria da informação porque querem comprimir informações. Eles se importam porque tem uma conexão convincente com seu campo. O emaranhamento quântico pode ser descrito com entropia.9 Muitos resultados em mecânica estatística e termodinâmica podem ser obtidos assumindo a entropia máxima sobre as coisas que você não conhece.10 As vitórias ou perdas de um jogador estão diretamente conectadas à divergência de KL, em particular as configurações de iteração. 11
A teoria da informação aparece em todos esses lugares, porque oferece formalizações concretas e de princípios para muitas coisas que precisamos expressar. Ela nos dá formas de medir e expressar a incerteza, como são diferentes dois conjuntos de crenças e quanto uma resposta a uma pergunta nos diz sobre as outras: como é a probabilidade difusa, a distância entre distribuições de probabilidade e quão dependentes são as duas variáveis. Existem idéias alternativas, semelhantes? Certo. Mas as idéias da teoria da informação são limpas, elas têm propriedades realmente bonitas e uma origem baseada em princípios. Em alguns casos, eles são exatamente o que você gosta e, em outros casos, eles são uma proxy conveniente em um mundo bagunçado.
Aprendizagem de máquina é o que eu conheço melhor, então vamos falar sobre isso por um minuto. Um tipo muito comum de tarefas na aprendizagem de máquinas é a classificação. Digamos que queremos olhar uma imagem e prever se é uma foto de cachorro ou gato. O nosso modelo pode dizer algo como “há uma chance de 80%, de que essa imagem é um cachorro e uma chance de 20% de ser um gato”. Digamos que a resposta correta é um cachorro – quão bom ou ruim é que só dissemos que havia 80 % de chance de ser um cachorro? Quanto melhor teria sido dizer 85%?
Esta é uma questão importante porque precisamos de alguma noção de quão bom ou ruim é o nosso modelo, a fim de o otimizar para funcionar bem. O que devemos otimizar? A resposta correta realmente depende do que estamos a usar o modelo para: Nós nos preocupamos apenas se o argumento principal estava certo, ou nós nos preocupamos com a confiança que estamos na resposta correta? Quão ruim é estar confiantemente errado? Não há uma resposta certa para isso. E, muitas vezes, não é possível conhecer a resposta correta, porque não sabemos como o modelo será usado de maneira suficientemente precisa para formalizar o que nos interessa. O resultado é que existem situações em que a entropia cruzada realmente é precisamente sobre o que nos interessa, mas isso nem sempre é o caso. Muito mais frequentemente, não sabemos exatamente o que nos interessa e a entropia cruzada é um excelente proxy.
A informação nos dá uma nova e poderosa estrutura para pensar sobre o mundo. Às vezes, ele se encaixa perfeitamente no problema; outras vezes não é um encaixe exato, mas ainda é extremamente útil. Este ensaio apenas arranhou a superfície da teoria da informação – há tópicos importantes, como os códigos de correção de erros, que não tocamos em tudo – mas espero ter mostrado que a teoria da informação é um assunto bonito que não precisa ser intimidante.
Para me ajudar a tornar-me um escritor melhor, considere preencher este formulário.

Leitura adicional
O artigo original de Claude Shannon sobre a teoria da informação, uma teoria matemática da comunicação, é extremamente acessível. (Isso parece ser um padrão recorrente em papéis da teoria da informação precoce. Era a era? Falta de limites de página? Uma cultura que emana da Bell Labs?)
Cover & Thomas Elementos da teoría da informação parece ser a referência padrão. Eu achei-o útil.

Reconhecimentos
Estou muito grato a Dan Mané, David Andersen, Emma Pierson e Dario Amodei por terem tido tempo para dar comentários incrivelmente detalhados e extensivos sobre este ensaio. Também agradeço os comentários de Michael Nielsen, Greg Corrado, Yoshua Bengio, Aaron Courville, Nick Beckstead, Jon Shlens, Andrew Dai, Christian Howard e Martin Wattenberg.
Obrigado também às minhas duas primeiras séries de seminários de rede neural para atuar como cobaias para essas idéias.
Finalmente, obrigado aos leitores que detectaram erros e omissões. Em particular, obrigado a Connor Zwick, Kai Arulkumaran, Jonathan Heusser, Otavio Good e um comentarista anônimo.

1. É divertido usar isso para visualizar classificadores bayesianos ingênuos, que assumem a independência…
2. Mas horrivelmente ineficiente! Se tivermos um símbolo adicional para usar nos nossos códigos, apenas usando-o no final de palavras-chave como esta seria um desperdício terrível.
3. Estou a enganar um pouco aqui. Eu tenho usado uma exponencial da base 2, onde isso não é verdade, e vou mudar para uma exponencial natural. Isso nos poupa ter um monte de log(2)s na nossa prova, e torna-o visualmente muito mais agradável.
4. Observe que esta notação para entropia cruzada não é padrão. A notação normal é H(p,q). Esta notação é horrível por duas razões. Em primeiro lugar, a mesma notação também se usa para a entropia conjunta. Em segundo lugar, parece que a entropia cruzada é simétrica. Isso é ridículo, e então vou escrever Hq(p).
5. Também notação não padrão.
6. Se você expandir a definição de divergência de KL, você obtém:

Isso pode parecer um pouco estranho. Como devemos interpretá-lo? Bem, log2(p(x)/q(x)) é apenas a diferença entre quantos bits usaria um código otimizado para q e um código otimizado para p para representar x. A expressão como um todo é a diferença esperada em quantos bits os dois códigos usariam.
7. Isso desencadeia a interpretação definida da teoria da informação apresentada no artigo de Raymond W. Yeung, “A New Outlook on Shannon’s Information Measures”.
8. Se você expandir a definição de informação mútua, você obtém:

Isso parece suspeito como a divergência de KL!
O que está a acontecer? Bem, é a divergência de KL. É a divergência de KL de P(X,Y) e a sua aproximação ingênua P(X) P(Y). Ou seja, é o número de bits que você guarda representando X e Y se você entender a relação entre eles em vez de assumir que eles são independentes.
Uma maneira simples de visualizar isso é descrever literalmente a relação entre uma distribuição e a sua aproximação ingênua:

9. Existe um campo inteiro de teoria da informação quântica. Eu não sei exatamente nada sobre o assunto, mas eu aposto com uma confiança extremamente alta, com base no outro trabalho de Michael, que a Computação Quântica de Michael Nielsen e Issac Chuang e as Informações Quânticas são uma excelente introdução.
10. Como alguém que não sabe nada de física estatística, tentarei esboçar a sua conexão com a teoria da informação conforme eu entendo.
Depois que Shannon descobriu a teoria da informação, muitas se observaram muitas semelhanças suspeitas entre as equações na termodinâmica e as equações na teoria da informação. E.T. Jaynes encontrou uma conexão muito profunda e baseada em princípios. Suponha que você tenha algum sistema e tome algumas medidas como a pressão e a temperatura. Quão provável você deve pensar que é um determinado estado do sistema? Jaynes sugeriu que devemos assumir a distribuição de probabilidade que, sujeita às restrições da nossa medição, maximiza a entropia. (Note-se que este “princípio da entropia máxima” é muito mais geral do que a física!) Ou seja, devemos assumir a possibilidade com a informação mais desconhecida. Muitos resultados podem ser derivados dessa perspectiva.
(Lendo as primeiras seções dos papéis de Jaynes (parte 1, parte 2) fiquei impressionado com o quão acessível que eles são.)
Se você está interessado nesta conexão, mas não quer trabalhar nos documentos originais, há uma seção na Cover & Thomas que deriva uma versão estatística da Segunda Lei da Termodinâmica das Cadeias de Markov!
11. A conexão entre a teoria da informação e o jogo foi originalmente estabelecida por John Kelly no seu artigo “Uma Nova Interpretação da Taxa de Informação”. É um documento extremamente acessível, embora exija algumas idéias que não desenvolvemos neste ensaio.
Kelly teve uma motivação interessante para o seu trabalho. Ele notou que a entropia estava a ser usada em muitas funções de custo que não tinham conexão com a codificação de informações e queria algum motivo de princípio para isso. Ao escrever este ensaio, fiquei preocupado com o mesmo, e apreciei muito o trabalho de Kelly como uma perspectiva adicional. Dito isto, não o acho completamente convincente: Kelly só encerra a entropia porque ele considera apostas iteradas onde um reinveste todo o seu capital em cada aposta. As configurações diferentes não levam à entropia.
Uma boa discussão sobre a conexão de Kelly entre as apostas e a teoria da informação pode encontrar-se na referência padrão sobre a teoria da informação, Cover & Thomas ”Elements of Information Theory”.
12. Não resolve o problema, mas não posso resistir a oferecer uma pequena defesa adicional da divergência de KL.
Há um resultado que a Cover & Thomas chama o Lemma de Stein, embora pareça que não tem relação com o resultado geralmente chamado de Lemma de Stein. Em um nível alto, é assim:
Suponha que você tenha alguns dados que você conhece provêm de uma das duas distribuições de probabilidade. Com que confiança você consegue determinar de quais distribuições eles vieram? Em geral, à medida que você obtém mais pontos de dados, a sua confiança deve aumentar exponencialmente. Por exemplo, em média, você pode tornar-se 1,5 vezes mais confiante sobre que distribuição é a verdadeira para cada ponto de dados que você vê.
O quanto sua confiança é multiplicada depende de quão diferentes sejam as distribuições. Se eles são muito diferentes, você pode rapidamente tornar-se confiante. Mas se eles são apenas um pouco diferentes, talvez seja necessário que veja muitos dados antes de ter uma resposta levemente confiante.
O lema de Stein diz, grosso modo, que a quantidade que você multiplica é controlada pela divergência de KL. (Existe alguma sutileza sobre o trade off entre falsos positivos e falsos negativos.) Isso parece ser uma boa razão para preocupar-se com a divergência de KL!

Sobre o autor

Sara Filipa

Comentar

por: Sara Filipa

Posts recentes

Comentários

Arquivos

Categorias

Meta