fórmula entropia de Shannon. Ajuda a minha confusão

Question

minha compreensão da fórmula entropia é que ele é usado para calcular o número mínimo de bits necessários para representar alguns dados. Geralmente é redigida de forma diferente quando definido, mas o entendimento anterior é o que eu confiei em até agora.

Aqui está o meu problema. Suponhamos que tem uma sequência de 100 '1', seguida por 100 '0' = 200 pedaços. O alfabeto é {0,1}, base de entropia é 2. A probabilidade do símbolo "0" é de 0,5 e "1" é 0,5. Assim, a entropia é 1 ou 1 bit para representar 1 bit.

run-length No entanto, você pode codificá-lo com algo como 100/1/100/0, onde é o número de bits para a saída seguido pelo bit. Parece que eu tenho uma representação menor do que o de dados. Especialmente se você aumentar o 100 para o número muito maior.

Eu estou usando: http://en.wikipedia.org/wiki/Information_entropy como referência no momento. Onde foi que eu errei? É a probabilidade atribuída a símbolos? Eu não acho que é errado. Ou será que eu obtenho a conexão entre a compressão e errado entropia? Mais alguma coisa?

Graças.

Editar

A seguir algumas das respostas meu acompanhamento são: se você aplicar a fórmula entropia a uma instância específica de uma mensagem para tentar descobrir o seu conteúdo de informação? Seria válido para levar a mensagem "aaab" e dizem que a entropia é ~ 0,811. Se sim, então o que é a entropia de 1 ... 10 .... 0 onde 1s e 0s são repetidas n vezes usando a fórmula entropia. É a resposta 1?

Sim, eu entendo que você está criando uma variável aleatória de símbolos de entrada e adivinhando a função massa de probabilidade com base em sua mensagem. O que eu estou tentando confirmar é a fórmula entropia não leva em conta a posição dos símbolos na mensagem.

Answer 1

Ou será que eu obtenho a conexão entre a compressão e errado entropia?

Você é muito perto, mas esta última questão é onde o erro foi. Se você é capaz de algo compressa em uma forma que era menor do que a sua representação original, isso significa que a representação original tinha, pelo menos, alguma redundância. Cada bit na mensagem realmente não estava transmitindo um bit de informação.

Como os dados redundantes não contribui para o conteúdo de informação de uma mensagem, ele também não aumenta a sua entropia. Imagine, por exemplo, um "gerador de bits aleatórios" que só retorna o valor "0". Este transmite nenhuma informação a todos! (Na verdade, ele transmite um indefinido quantidade de informação, porque qualquer mensagem binária consistindo de apenas um tipo de símbolo requer uma divisão por zero na fórmula entropia.)

Por outro lado, tinha-lhe simulado um grande número de coin flips aleatório, seria muito difícil para reduzir o tamanho desta mensagem por muito. Cada bit estariam contribuindo perto de 1 bit de entropia.

Quando você compactar os dados, você extrai que a redundância. Em troca, você paga um preço entropia one-time por ter que elaborar um esquema que sabe como comprimir e descomprimir esses dados; que em si leva algumas informações.

run-length No entanto, você pode codificá-lo com algo como 100/1/100/0, onde é o número de bits para a saída seguido pelo bit. Parece que eu tenho uma representação menor do que o de dados. Especialmente se você aumentar o 100 para o número muito maior.

Para resumir, o fato de que você poderia conceber um esquema para fazer o codificação dos dados menor do que os dados originais diz-lhe algo importante. Ou seja, ele diz que seus dados originais continha muito pouca informação .

---

Leitura

Para um tratamento mais completo deste, incluindo exatamente como você calcular a entropia para qualquer seqüência arbitrária de dígitos com alguns exemplos, veja este pequeno whitepaper .

Answer 2

Tenha um olhar em Kolmogorov complexidade

O número mínimo de bits em que uma corda pode ser comprimido sem perda de informação. Esta é definida em relação a um fixo, mas esquema de descompressão universal, dado por uma máquina de Turing universal.

E no seu caso particular, não restringir-se a alfabeto {0,1}. Para o seu exemplo de uso {0 ... 0, 1 ... 1} (cem por 0 e centenas de 1 de)

Answer 3

As suas obras de codificação neste exemplo, mas é possível conceber um caso igualmente válidas: 010101010101 ... que seria codificado como 1/0/1/1 / ...

A entropia é medido em todas as mensagens possíveis que podem ser construídos no alfabeto dado, e não apenas patológica exemplos!

Answer 4

John Feminella deu certo, mas acho que há mais para dizer.

Shannon entropia é baseada na probabilidade e probabilidade é sempre no olho do observador.

Você disse que 1 e 0 foram igualmente provável (0,5). Se é assim, então a cadeia de 100 1s seguido por 100 0s tem uma probabilidade de 0,5 ^ 200, dos quais -log (base 2) é de 200 bits, conforme o esperado. No entanto, a entropia de que string (em termos de Shannon) é seus tempos de conteúdo informativo a sua probabilidade, ou 200 * 0,5 ^ 200, ainda realmente um pequeno número.

Isto é importante porque se você codificação para comprimir a corda, run-length, no caso de esta cadeia que irá receber um pequeno comprimento, mas calculados para o conjunto 2 ^ 200 cordas, ele não vai fazer bem. Com sorte, ele vai média a cerca de 200, mas não menos.

Por outro lado, se você olhar para a sua seqüência original e dizer que é tão marcante que quem o gerou é susceptível de gerar mais parecido com ele, então você está realmente dizendo a sua probabilidade é maior do que 0,5 ^ 200, assim que você é fazendo uma pressupostos diferentes sobre a estrutura original da probabilidade do gerador da cadeia, ou seja, que tem a entropia mais baixo do que o de 200 bits.

Pessoalmente, acho que este assunto muito interessante, especialmente quando você olha para Kolmogorov (Algorithmic) informações. Nesse caso, você define o conteúdo de informação de uma corda como o comprimento do menor programa que pode gerá-lo. Isto leva a todos os tipos de insights sobre engenharia de software e design de linguagem.

Espero que ajude, e obrigado por sua pergunta.