Qual é o papel do logaritmo na entropia de Shannon?

A entropia de Shannon é o negativo da soma das probabilidades de cada resultado multiplicado pelo logaritmo de probabilidades de cada resultado. Que finalidade o logaritmo serve nessa equação?

Uma resposta intuitiva ou visual (em oposição a uma resposta profundamente matemática) receberá pontos de bônus!

A entropia de Shannon é uma quantidade que satisfaz um conjunto de relações.

Em resumo, o logaritmo é fazê-lo crescer linearmente com o tamanho do sistema e "comportar-se como informação".

O primeiro significa que a entropia do lançamento de uma moeda vezes é vezes a entropia do lançamento de uma moeda:$n$$n$

Ou apenas para ver como ele funciona ao jogar duas moedas diferentes (talvez injustas - com cabeças com probabilidade e coroa para a primeira moeda e e para a segunda) para que as propriedades do logaritmo (logaritmo do produto sejam soma logaritmos) são cruciais.$p_1$$p_2$$q_1$$q_2$

Mas também a entropia de Rényi possui essa propriedade (ela é parametrizada por um número real , que se torna entropia de Shannon para ).$\alpha$$\alpha \to 1$

No entanto, aqui vem a segunda propriedade - a entropia de Shannon é especial, pois está relacionada à informação. Para obter uma sensação intuitiva, você pode ver como a média de .

Podemos chamar informações. Por quê? Porque se todos os eventos ocorrerem com probabilidade , isso significa que existem eventos. Para saber qual evento aconteceu, precisamos usar os bits (cada bit dobra o número de eventos que podemos distinguir).$\log(1/p)$$p$$1/p$$\log(1/p)$

Você pode se sentir ansioso "OK, se todos os eventos tiverem a mesma probabilidade, faz sentido usar como uma medida de informação. Mas, se não estiverem, por que a média da informação faz algum sentido?" - e é uma preocupação natural.$\log(1/p)$

Mas acontece que faz sentido - fonte de Shannon codificação teorema diz que uma string com letras uncorrelted com probabilidades de comprimento não podem ser compactados (em média) a cadeia binária menor do que . E, de fato, podemos usar Huffman codificação para comprimir a corda e ficar muito perto de .$\{p_i\}_i$$n$$n H$n H$n H$

Veja também:

• Uma boa introdução é a entrada da teoria da informação de Cosma Shalizi
• O que é entropia, realmente? - MathOverflow
• Dissecando o formato GZIP

É o mesmo que as outras respostas, mas acho que a melhor maneira de explicar é ver o que Shannon diz em seu artigo original.

A medida logarítmica é mais conveniente por vários motivos:

1. É praticamente mais útil. Parâmetros de importância de engenharia, como tempo, largura de banda, número de relés etc., tendem a variar linearmente com o logaritmo do número de possibilidades. Por exemplo, adicionar um relé a um grupo duplica o número de estados possíveis dos relés. Ele adiciona 1 ao logaritmo base 2 desse número. Dobrar o tempo aproxima o número de mensagens possíveis ou dobrar o logaritmo, etc.
2. Está mais próximo do nosso sentimento intuitivo quanto à medida adequada. Isso está intimamente relacionado a (1), pois medimos intuitivamente as entidades por comparação linear com padrões comuns. Considera-se, por exemplo, que dois cartões perfurados devem ter o dobro da capacidade de um para armazenamento de informações e dois canais idênticos duas vezes a capacidade de um para transmitir informações.
3. É matematicamente mais adequado. Muitas das operações limitadoras são simples em termos de logaritmo, mas exigiriam uma correção desajeitada em termos de número de possibilidades

Fonte: Shannon, Uma teoria matemática da comunicação (1948) [ pdf ].

Observe que a entropia de Shannon coincide com a entropia de Gibbs da mecânica estatística, e também há uma explicação para o motivo pelo qual o log ocorre na entropia de Gibbs. Na mecânica estatística, a entropia deve ser uma medida do número de estados possíveis nos quais um sistema pode ser encontrado. A razão pela qual é melhor que é porque geralmente é uma função de crescimento muito rápido de seus argumentos e, portanto, não pode ser útil para uma aproximação de uma expansão de Taylor, enquanto pode ser. (Não sei se essa foi a motivação original para tirar o registro, mas isso é explicado dessa maneira em muitos livros introdutórios de física.)log Ω Ω Ω log $\Omega$$\log \Omega$$\Omega$$\Omega$$\log \Omega$

outra maneira de ver isso é do ponto de vista algorítmico. Imagine que você está indo para adivinhar um número , que a única informação que tem é que esse número está no intervalo de . Nessa situação, o algoritmo ideal para adivinhar o número é um algoritmo de pesquisa binária simples , que encontra na ordem . Essa fórmula diz intuitivamente quantas perguntas você precisa fazer para descobrir o que é . Por exemplo, se , você precisa fazer no máximo 3 perguntas para encontrar o desconhecido .1 ≤ x ≤ N x O ( log 2 N ) x N = 8 $x$$1 \leq x \leq N$$x$$O(\log_2N)$$x$$N=8$$x$

Do ponto de vista probabilística, quando se declara como sendo a mesma probabilidade de ser quaisquer valores na faixa de , significa para . Claude Shannon mostrou muito bem que o conteúdo informativo de um resultado é definido como:1 ≤ x ≤ N p ( x ) = 1 / N 1 ≤ x ≤ N $x$$1 \leq x \leq N$$p(x) = 1/N$$1 \leq x \leq N$$x$

A razão para a base 2 no logaritmo é que aqui estamos medindo as informações em bits . Você também pode assumir o logaritmo natural que mede suas informações em nats . Como exemplo, o conteúdo informativo da saída é . Este valor é precisamente igual ao número de etapas no algoritmo de pesquisa binária (ou número de instruções IF no algoritmo). Portanto, o número de perguntas que você precisa descobrir é igual a , é exatamente o conteúdo informativo do resultado .$x=4$$h(4) = 3$$x$$4$$x=4$

Também podemos analisar o desempenho do algoritmo de busca binária quanto a qualquer resultado possível. Uma maneira de fazer isso é descobrir qual é o número esperado de perguntas a serem feitas para quaisquer valores de . Observe que o número de perguntas necessárias para adivinhar um valor de , como discuti acima, é . Portanto, o número esperado de perguntas para qualquer é, por definição, igual a:$x$$x$$h(x)$$x$

O número esperado de perguntas é exatamente o mesmo que a entropia de um conjunto , ou entropia em resumo. Portanto, podemos concluir que a entropia quantifica o número esperado (ou médio) de perguntas que você precisa fazer para adivinhar um resultado, que é a complexidade computacional do algoritmo de busca binária.$\langle h(x) \rangle$$H(X)$$H(X)$

Aqui está uma explicação imediata. Você poderia dizer que 2 livros do mesmo tamanho têm o dobro de informações que 1 livro, certo? (Considerando que um livro é uma sequência de bits.) Bem, se um determinado resultado tem probabilidade P, então você pode dizer que o conteúdo de suas informações é sobre o número de bits que você precisa escrever 1 / P. (por exemplo, se P = 1/256, são 8 bits.) A entropia é apenas a média do tamanho do bit de informação, em todos os resultados.

O objetivo de aparece na Entropia de Shannon é que é a única função que satisfaz o conjunto básico de propriedades que a função de entropia, , é incorporada.$\log(p_i)$$\log(p_i)$$H(p_1, \ldots ,p_N)$

Shannon forneceu uma prova matemática desse resultado que foi minuciosamente escolhida e amplamente aceita. O objetivo e o significado do logaritmo na equação da entropia são, portanto, independentes nas suposições e provas.

Isso não facilita a compreensão, mas é, em última análise, a razão pela qual o logaritmo aparece.

Encontrei as seguintes referências úteis além das listadas em outros lugares:

1. Teoria da Probabilidade: A Lógica da Ciência por ET Jaynes . Jaynes é um dos poucos autores que obtém muitos resultados do zero; veja o capítulo 11.
2. Teoria da Informação, Inferência e Algoritmos de Aprendizagem de David MacKay. Contém uma análise aprofundada do teorema da codificação de origem de Shannon; veja o capítulo 4.

Resumo:

Porque representa o número total médio de perguntas perfeitas que você precisa que sejam respondidas para resolver completamente todas as ambiguidades em dados que você ainda não tinha visto. Uma pergunta perfeita com respostas possíveis é aquela que, quando respondida, o espaço de possibilidades será reduzido em vezes.$n$$n$

Exemplo:

Suponha que eu joguei um dado justo de faces e você previsse o resultado. O espaço de possibilidades é . Você poderia me fazer perguntas como essa binária "é o resultado ?" (a resposta é sim ou não, ou seja, ) e minha resposta pode ser "nopies!". Então o espaço de possibilidades é apenas . Portanto, essa pergunta não é boa para perguntar.$6$$6$$1$$n=2$$1$

Como alternativa, você poderia fazer perguntas melhores, como esta pergunta binária superior "é maior que ?", E minha resposta seria "yeppies!" - então bum, o espaço de possibilidades é reduzido pela metade! Ou seja, restam apenas candidatos (dos 6 originalmente). Inferno, sim cara.$3.5$$6/2=3$

Agora, suponha que você continue fazendo recursivamente mais dessas boas perguntas até chegar ao caso em que o espaço de possibilidades tem apenas possibilidade, pela qual - por definição - não resta ambiguidade (você sabe a resposta).$1$

Vamos fazer isso:

• $6$ possibilidades. P: O resultado é ? A: sim$> 3.5$
• $6/2=3$ possibilidades restantes. P: o resultado é ? A: sim$\ge 5$
• $6/2/2=1.5$ possibilidades restantes. Q: resultado ? A: sim$= 6$

Você conclui que o resultado deve ser o número e só precisava fazer perguntas binárias. seja,$6$$3$$ceil(\log_2(6)) = ceil(2.58) = 3$

Agora, obviamente, o número de perguntas binárias é sempre um número natural. Então, por que a entropia de Shannon não usa a função ? Porque na verdade cospe o número médio de boas perguntas que precisam ser feitas.$ceil$

Se você repetir esse experimento (escrevendo um código Python), notará que, em média , precisará fazer perguntas binárias perfeitas.$2.58$

Obviamente, se você fizer perguntas binárias, defina a base do log para isso. Então aqui porque nossas perguntas eram binárias. Se você fizer perguntas que esperam muitas respostas possíveis, você definirá a base como vez de , ou seja, .$\log_2(...)$$n$$n$$2$$\log_n(...)$

Simulação:

import random

total_questions = 0
TOTAL_ROUNDS = 10000

for i in range(0,TOTAL_ROUNDS):
    outcome = random.randrange(1,7)
    total_questions += 1
    if outcome > 3.5:
        total_questions += 1
        if outcome >= 5:
            total_questions += 1
            if outcome == 5:
                pass
            else:
                # must be 6! no need to ask
                pass
        else:
            # must be 4! no need to ask
            pass
    else:
        total_questions += 1
        if outcome >= 2:
            total_questions += 1
            if outcome == 2:
                pass
            else:
                # must be 3! no need to ask
                pass
        else:
            # must be 1! no need to ask
            pass


print 'total questions: ' + str(total_questions)
print 'average questions per outcome: ' + str(total_questions/float(TOTAL_ROUNDS))

Resultados:

total questions: 26634
average questions per outcome: 2.6634

Santo molly cara .$2.6634 \ne \log_2(6) \ne 2.58$

O que há de errado? Está quase perto, mas não tão perto quanto eu esperava. É o PRNG do Python tentando dizer uma piada lenta? Ou Shannon está errado? Ou é - Deus não permita - meu entendimento está errado? De qualquer maneira AJUDA. SOS já é cara.

Suponha que tenhamos uma fonte de informação discreta que produz símbolos de algum alfabeto finito com probabilidades . Shannon define a entropia como a medida tal que$\Omega = \{\omega_1, \dotsc, \omega_n\}$$p_1, \dotsc, p_n$$H(p_1, \dotsc, p_n)$

• $H$ é contínuo em seus parâmetros,
• $H$ é monótono aumentando em quando (já que a incerteza está aumentando) e$n$$p_1 = \dots = p_n = \frac1n$
• $H$ é independente de como uma escolha é dividida em escolhas sucessivas. Por exemplo, considere três eventos ao rolar um dado preto e um dado branco: (1) o dado branco é ímpar, (2) o dado branco é par e o dado preto é menor que três e (3) caso contrário. Ou os dados são lançados juntos, ou então o dado branco é rolado primeiro e talvez o dado preto, se necessário. Este requisito indica que $$\begin{align} H\left(\frac12, \frac16, \frac13\right) &= H\left(\frac12, \frac12\right) + \frac12 H\left(\frac13, \frac23\right). \end{align}$$

Shannon prova que o único satisfaz os três requisitos tem a forma que corresponde a uma unidade de medida de informações arbitrária. Quando , esta unidade é o bit .$H$

Esta pergunta foi levantada há dois anos e já existem muitas respostas impressionantes, mas eu gostaria de acrescentar as minhas que me ajudaram bastante.

A questão é

Que finalidade o logaritmo serve nessa equação?

O logaritmo (geralmente baseado em 2) é devido à desigualdade de Kraft .

$\sum_{i=1}^m 2^{-l_i} <= 1$

podemos intuir da seguinte maneira: a soma da probabilidade de todo o código com comprimento é menor que 1. Da desigualdade, podemos derivar o seguinte resultado: para cada função de comprimento do código de um código decodificável exclusivamente, existe uma distribuição tal que$l_i$$L_x$$P(x)$

$P(x) = 2^{-L(x)}$ ,

E, portanto, e é a probabilidade do código com o comprimento .$L_{(x)} = -logP(x)$$P(x)$$L_{(x)}$

A entropia de Shannon é definida como o comprimento médio de todo o código. Como a probabilidade de todo código com comprimento é , o comprimento médio (ou entropia de Shannon) é .$L_{(x)}$$P(x)$$-P(x)logP(x)$

Uma ilustração intuitiva e uma resposta visual (conforme necessário, mas mais especificamente para a desigualdade da Kraft) é articulada neste documento , a Árvore de códigos e a desigualdade da Kraft .

Com base na sua não aceitação de respostas já respondidas, acho que o que você está procurando é a razão pela qual Shannon usou o logaritmo em sua fórmula em primeiro lugar. Em outras palavras, a filosofia disso.

_{Isenção de responsabilidade : estou neste campo por uma semana, vindo aqui por causa de uma pergunta como você . Se você tiver mais conhecimento sobre isso, entre em contato.}

Eu tenho essa pergunta depois de ler um dos artigos mais importantes de Ulanowicz, Aumentando a entropia: morte por calor ou harmonias perpétuas? . Este é o parágrafo explica por que a fórmula possui -log (p) em vez de (1-p):

Antes de descompactar ainda mais a definição formal de entropia, seria justificável perguntar por que não escolher simplesmente (1 - p) em vez de [–log (p)] como a medida mais apropriada de inexistência? A resposta é que o produto resultante com p (ou seja, [p – p ^ 2]) é perfeitamente simétrico em torno do valor p = 0,5. Os cálculos de acordo com essa combinação simétrica seriam capazes de descrever apenas um universo reversível. Boltzmann e Gibbs, no entanto, procuravam quantificar um universo irreversível. Ao escolher a função logarítmica convexa univariada, Boltzmann deu assim um viés ao não ser sobre o ser. Observa-se, por exemplo, que max [–xlog {x}] = {1 / e} ≈ 0,37, de modo que a medida de indeterminação é inclinada para valores mais baixos de pi.

Parece que Shannon escolheu o logaritmo sem motivo. Ele apenas "cheirou" que deveria usar o logaritmo. Por que Newton escolheu a operação de multiplicação em sua fórmula F = m * a?

Observe que, naquele momento, ele não tinha idéia sobre entropia :

Minha maior preocupação era como chamar. Pensei em chamá-lo de 'informação', mas a palavra era muito usada, então decidi chamá-la de 'incerteza'. Quando discuti com John von Neumann, ele teve uma ideia melhor. Von Neumann me disse: 'Você deveria chamar isso de entropia, por duas razões. Em primeiro lugar, sua função de incerteza foi usada na mecânica estatística sob esse nome, portanto, ela já tem um nome. Em segundo lugar, e mais importante, ninguém sabe o que realmente é entropia; portanto, em um debate, você sempre terá a vantagem.

Então, minha resposta é: não há razão para isso. Ele escolheu isso porque funcionou magicamente.

A entropia é definida como o logaritmo da média geométrica do coeficiente multinomial que expressa o número de estados em que um sistema pode estar:

Os logaritmos aparecem na fórmula após o uso da aproximação do fatorial por Stirling (veja esta explicação )

O log deriva da derivação de uma função H que satisfaz certos requisitos naturais. Veja a pág. 3 seg. 2 desta fonte:

http://www.lptl.jussieu.fr/user/lesne/MSCS-entropy.pdf

Dados os axiomas, se você realizar a otimização, obtém uma função exclusiva (até constantes) com um log nela.

Todas as respostas acima estão corretas, exceto que elas interpretam o log, mas não explicam a origem dele.

Eu acho que sua pergunta é mais sobre o "significado" desse logaritmo e por que cada componente contribui para o significado geral da fórmula, ao invés do mero formalismo que mostra a coerência da definição para certos requisitos.

A idéia na entropia de Shannon é avaliar as informações de uma mensagem observando sua FREQUÊNCIA (ou seja, ) e sua GENERALIDADE (ou seja, ):$p(x)$$-log(p(x))$

• $p(x)$ : quanto mais "frequente" uma mensagem for, menor será a informação (ou seja, mais fácil de prever).
• $-log(p(x))$ : Quanto mais "geral" for uma mensagem, mais informações serão transmitidas.

O primeiro termo é sobre a frequência, o é sobre sua generalidade.$p(x)$$-log(p(x))$

A partir de agora, discutirei como a GENERALIDADE afeta a fórmula final da entropia.

Portanto, podemos definir como geral (por exemplo, chuva / não chuva) ou específica (por exemplo, ligth / avg / heavy / veryHeavy rain) é uma mensagem com base no número de bits necessários para codificá-la:

Agora, sente-se, relaxe e veja como a Entropia de Shannon faz o truque: baseia-se na suposição (razoável) de que mensagens mais GERAIS são, conseqüentemente, MAIS FREQUENTES.

Por exemplo, direi que está chovendo se é uma chuva média, forte ou muito forte. Assim, ele propôs codificar a GERALIDADE das mensagens com base em quão FREQÜENTES elas são ... e lá vai você:

com a frequência de uma mensagem .$N$$x$

A equação pode ser interpretada como: mensagens raras terão codificação mais longa porque são menos gerais, portanto, precisam de mais bits a serem codificados e são menos informativas. Portanto, ter mensagens mais específicas e raras contribuirá mais para a entropia do que ter muitas mensagens gerais e frequentes.

Na formulação final, queremos considerar dois aspectos. A primeira, , é que as mensagens frequentes são mais fáceis de serem previstas e, dessa perspectiva, menos informativas (ou seja, codificação mais longa significa maior entropia). O segundo, , é que as mensagens frequentes também são gerais e, dessa perspectiva, mais informativas (ou seja, codificação mais curta significa menor entropia).$p(x)$$-log(p(x))$

A entropia mais alta é quando temos um sistema com muitas mensagens raras e específicas. A entropia mais baixa com mensagens frequentes e gerais. No meio, temos um espectro de sistemas equivalentes a entropia que podem ter mensagens raras e gerais ou mensagens frequentes mas específicas.

Não acho que seja possível dar uma resposta universal "intuitiva". Vou dar uma resposta intuitiva para algumas pessoas, como os físicos. O logaritmo existe para obter a energia média do sistema. Aqui estão os detalhes.

Shannon usou a palavra " entropia " porque adaptou o conceito da mecânica estatística . Na mecânica estatística, há uma distribuição seminal com o nome de Boltzmann. Curiosamente, agora é uma distribuição importante no aprendizado de máquina!

A distribuição de Boltzmann pode ser escrito como onde são constantes, e é a energia do sistema num estado do espaço estado . Na termodinâmica clássica, , onde são uma coordenada e momento da partícula. É uma função de probabilidade adequada quando as constantes são selecionadas corretamente, ou seja, . Além disso, você pode achar interessante que corresponda à temperatura do sistema.

Agora, observe como , isto é, um log de probabilidade é linear (proporcional) à energia. Agora, você pode ver que a seguinte expressão é essencialmente um valor esperado de energia do sistema: Foi o que Gibbs fez.$\ln P\sim E$

Então, Shannon pegou isso e discretizou como e chamou de "entropia", e chamamos de "entropia de Shannon". Não há mais conceito de energia aqui, mas talvez você possa anular a probabilidade de um estado e chamar isso de energia do estado?

Isso é intuitivo o suficiente para você? É para mim, mas eu era um físico teórico na vida passada. Além disso, você pode ir para um nível mais profundo de intuição vinculando-se a conceitos termodinâmicos ainda mais antigos, como temperatura e obras de Boltzmann e Clausius.