Visualizando Entropia da Informação

Maurice Flanagan Blocked Unblock Seguir Seguindo 2 de janeiro

A entropia da informação é um belo conceito que é fundamental para o aprendizado de máquina. Eu gostaria de compartilhar uma maneira simples e visual de pensar sobre a entropia da informação que me ajudou a obter uma compreensão mais intuitiva da matemática.

A matemática

Nosso objetivo é obter um melhor entendimento da entropia da informação, aqui está a matemática (em Python):

 def information_entropy (P): 
soma de retorno ([p * log2 (1 / p) para p em P.values ()])

Dada uma distribuição de probabilidade P1 = {'a': .5, 'b': .25, 'c': .25} podemos usar este método para calcular o número de bits em média produzidos por esta distribuição, neste caso:

 # .5 * log (1 / 0,5) + 0,25 * log (1 / 0,25) + 0,25 * log (1 / 0,25) 
information_entropy (P1) == 1,5

O que significa para uma distribuição produzir bits? Como essa fórmula calcula o número de bits? Vamos dividi-lo sem ficar muito mathy.

Um bit (moeda)

Vamos começar com uma distribuição muito simples, um lance de moeda justo P0 = {'h': .5, 't':.5} . Podemos escrever um método python simples para provar esta distribuição:

 def flip (): 
return random.randint (0, 1)
 def sample_P0 (): 
se flip ():
return "t"
outro:
return "h"

Podemos visualizar esse método como uma árvore de decisão:

generate_P0

De acordo com a nossa fórmula, a entropia de informação de P0 é de 1 bit :

 # .5 * log2 (1 / .5) + .5 * log2 (1 / .5) 
h (P0) == 1

Isso faz sentido? O que significa quando dizemos que P1 produz 1 bit de informação? Vamos pensar nisso em termos de codificação. Se nós sample_P1 quatro vezes e geramos hthh qual é a codificação mais compacta que funcionará para uma string arbitrariamente longa de samples? Bem, olhando para a árvore de decisão, por que não apenas registrar os resultados do flip que geraram a saída:

 t -> 0 
h -> 1
hthh -> 1011

Portanto, com este esquema de codificação, cada sample_P0 pode ser codificado em um bit e, portanto, a entropia da informação é um bit.

Agora entendemos o que significa dizer que uma distribuição produz bits, mas não abordamos a fórmula information_entropy , para fazer isso precisamos de uma distribuição mais complexa.

Uma distribuição mais complexa

Podemos construir nossa distribuição original P1 = {'a': .5, 'b': .25, 'c': .25} usando uma árvore de decisão? Sobre o quê:

generate_P1

Que se traduz em:

 def sample_P1 (): 
se flip ():
retornar "a"
outro:
se flip ():
retorno "b"
outro:
return "c"

Isso gera a distribuição correta? Bem, se olharmos para o caminho percorrido para chegar a cada resultado, podemos calcular a probabilidade desse caminho ser tomado:

 a -> 0 
b -> 10
c -> 11
p (a) == p (0) == .5
p (b) == p (1) * p (0) == 0,25
p (c) == p (1) * p (1) == 0,25

Puro, a distribuição se alinha. Agora, e a entropia da informação? Bem, vamos usar a mesma abordagem de P0 e codificar nossos símbolos usando os bits de caminho acima. Por exemplo, digamos que sample_P1 quatro vezes e obtenha abcb :

 a -> 0 
b -> 10
c -> 11
 abcb 
0 10 11 10
 abcb -> 0101110 

Portanto, nossos quatro símbolos são codificados como sete bits, significando uma média de 4/7 bits por símbolo. Isso não é exatamente 1.5, e é claro por que, nós pegamos uma amostra muito pequena e poderiamos ter aaaa ou cccc variando de 4/4 bits a 8/4 bits.

Precisamos de uma fórmula que possa calcular o tamanho de codificação esperado, de acordo com nossa árvore de decisão.

Entropia de informação é o conteúdo de informação esperado

Vamos colocar todas as peças na mesa e ver se podemos descrever a entropia da informação em termos da nossa árvore de decisão:

generate_P1

Seguimos o caminho para cada nó da folha para gerar sua codificação binária com um bit gerado por cada flip mas não nos importamos realmente com a string de codificação específica , apenas com o seu comprimento. Vamos chamar esse comprimento o conteúdo da informação

 a -> 0 -> 1 bit de conteúdo informativo 
b -> 10 -> 2 bit de conteúdo de informação
c -> 11 -> 2 bits de conteúdo de informação

Esse conteúdo de informação sempre será igual ao comprimento do caminho em nossa árvore de decisão.

Nós geramos nossas probabilidades com base nas seqüências de codificação, podemos usar o conteúdo da informação para gerar a probabilidade de cada resultado? Podemos porque p(0) == p(1) == .5 a probabilidade é de .5 ** information content ou em outras palavras:

 def probabilidade_de_informacao_conteúdo (bits): 
retorno 1 / (2 ** bits)

Estamos nos aproximando da fórmula information_entropy . Lembre-se, a árvore de decisão é apenas uma ferramenta visual, o que realmente precisamos é uma maneira de ir de probabilidades para information_content, e se simplesmente invertermos o método anterior?

 def information_content (p): 
return log2 (1 / p)

Então, agora podemos calcular uma probabilidade e calcular a duração da codificação para esse resultado específico. Nossa etapa final é calcular o tamanho de codificação esperado para a distribuição de probabilidade. Fazemos isso simplesmente tomando a média do information_content para cada resultado, ponderada pela probabilidade de cada resultado (este é apenas o valor esperado da probabilidade):

 def information_entropy (P): 
soma de retorno ([p * information_content (p) para p em P.values ()])

Conclusão

Nós explicamos a fórmula para a entropia da informação em termos de uma árvore de decisão que gera uma distribuição de probabilidade. A entropia de informação é, na verdade, o número médio de bits que devem ser gerados para produzir uma amostra, dada uma determinada árvore / distribuição de decisão.

Isso está longe de ser um tratamento rigoroso desse tópico extremamente importante, mas achei útil pensar em muitos conceitos da teoria da informação e aprendizado de máquina em termos de gráficos simples.