Compressão de dados sem perda: Entropia de Shannon, Aleatoriedade, Complexidade de Kolmogorov
Pretendo dar início a alguns artigos sobre um dos temas que mais me fascinam desde a juventude: compressão de dados lossless, Teoria da Informação (envolve Probabilidade, Estatística, Ciência da Computação, entre outros). Tentarei aqui relacionar alguns conceitos sobre um tema que considero complexo, da forma mais clara que conseguir.
Um pouco sobre Probabilidade (recapitulando)
Normalmente começamos pelo cenário mais simples/trivial; o lançamento de uma moeda.
Quais possíveis resultados temos para esse experimento? Ou se preferir, pode também dizer: quais estados possíveis podem ser assumidos a cada lançamento?
Temos o conceito de espaço amostral, que é o conjunto de todas possibilidades (resultados) que um determinado experimento pode assumir, nesse exemplo, {cara, coroa}.
Se a moeda for honesta, isto é, se o resultado de cada lançamento for totalmente independente, podemos dizer que é um experimento aleatório (o resultado do próximo experimento é desconhecido). Nesse caso, cada estado tem a mesma probabilidade de ocorrer, dizemos que é um espaço amostral equiprovável.
Temos 2 situações possíveis: sair cara (evento A); sair coroa (evento B).
Evento é um subconjunto do espaço amostral (que chamaremos de K). Logo,
A = {cara}, B = {coroa}. n(A) = 1, n(B) = 1. Onde n(X) é a cardinalidade de X; portanto n(K) = 2.
Obtemos a probabilidade de cada evento P(X), dividindo n(X)/n(K) e a soma de todas probabilidades deve ser = 1; P(A) + P(B) = 1
Pois bem, temos 50% de chance de obter cara e 50% de obter coroa. => 50/100 = 1/2. P(A) = P(B) = 1/2.
Mas e se a moeda estivesse viciada? Digamos que agora a moeda tem
66.6…% de chance de dar cara e 33.3…% de dar coroa. Pense que no primeiro caso, o grau de incerteza é o máximo. Não poderemos estabelecer nenhum padrão a partir da coleta de uma quantidade mínima de resultados dos experimentos, dado que desconhecemos totalmente qual será o próximo resultado. Já no segundo caso, esperamos, diante mão, que ocorra mais cara do que coroa ao longo dos experimentos.
Demonstrando com strings
Cenário 1 (“Moeda Honesta”)
Evento A = Escrever o caractere ‘H’ na saída. (H de Heads)
Evento B = Escrever o caractere ‘T’ na saída. (T de Tails)
Definiremos arbitrariamente P(A) = P(B) = 1/2
Utilizei a ferramenta random strings generator para gerar as strings. Defini nos parâmetros que gerasse 5 strings de 32 caracteres e com alfabeto HT para amostra.
Observe o que acontece quando pegamos, por exemplo, a sequência dos 8 primeiros caracteres e buscamos por repetições desse padrão. Da mesma forma, foi feito iniciando do 2º caractere, depois iniciando do 3º caractere em grupos de 8.
Não há repetições. Significa que quanto maior o grau de incerteza, maior a quantidade de informação no conjunto dos dados.
Cenário 2 (“Moeda Viciada”)
Evento A = Escrever o caractere ‘H’ na saída.
Evento B = Escrever o caractere ‘T’ na saída.
Aqui definiremos, P(A) ≃ 66.6% (2/3) e P(B) ≃ 33.3% (1/3)
Para simular essa condição, mudei o parâmetro de alfabeto na ferramenta de geração de strings para HHT. Isso pode ser facilmente demonstrado da seguinte forma:
P(A) = 2 * P(B), tal que P(A) + P(B) = 1
Então: (2 * P(B) + P(B)) = (3 * P(B)) = 1
Logo: P(B) = 1/3 e P(A) = 2/3
Observe agora o que ocorre com as strings que são geradas, quando buscamos pelos grupos de 8 caracteres.
Isso é o que acontece com um conjunto de dados onde o grau de incerteza é menor, haverá redundância de elementos com maior probabilidade de ocorrer. Acaba havendo uma quantidade menor de informação “real”.
Mas o que é, afinal, a Entropia de Shannon?
Ela nada mais é do que uma função que mensura (quantifica) o grau de incerteza média associada a um conjunto de eventos, dadas as probabilidades de cada evento.
Se usarmos log na base 2 nessa fórmula, ela nos fornecerá a quantidade de bits necessária, na média, para representar cada símbolo emitido por uma fonte de dados.
Cenário 1
Imagine que tenhamos a mensagem “abcd” emitida pela fonte.
Pergunta: quantos bits são necessários pra representar cada símbolo?
1º: Como a frequência de cada símbolo é = 1, todos apresentam a mesma probabilidade de ocorrência, no caso 1/4 (eventos equiprováveis).
Aplicando a fórmula da entropia de Shannon, temos:
Entenda que isso é um limite inferior para a quantidade necessária de bits (na média) por símbolo para representar essa mensagem. Não há como compactar essa mensagem (ou codificá-la) com menos de 8 bits, conforme Shannon provou em seu teorema de codificação da fonte.
Parece intuitivo, já que para representar 4 valores distintos na base 2, poderíamos usar simplesmente a sequência de números binários iniciando com 00.
00 01 10 11
Cenário 2
Agora imagine a mensagem “acbc”.
Temos, de um lado o evento C = emitir “c” com P(C) = 2/4 =1/2 = 50% e do outro, o evento A = emitir “a” com P(A) = 1/4 = 25% e o evento B = emitir “b” também com P(B) = 1/4.
Pergunta: precisamos de 2 bits no mínimo para representar cada símbolo dessa mensagem?
A resposta é não. Isso porque temos 4 elementos na mensagem, mas só 3 de informação “real”. Há redundância do símbolo “c”.
De novo, aplicando a fórmula da entropia de Shannon, temos:
Uma forma de representar essa mensagem com quantidade total mínima de bits poderia ser: a ⇢ 00, b ⇢ 01, c ⇢ 1.
00 1 01 1 => Total: 6 bits, 6/4 = 1.5 (confere com o resultado da função Entropia de Shannon).
E como isso está diretamente relacionado à aleatoriedade?
Quanto maior a entropia de uma mensagem, maior a quantidade de informação real presente (não redundante) e por consequência, maior o grau de incerteza (imprevisibilidade) quanto ao próximo elemento que virá nessa mensagem.
Quando a entropia é zero, significa que a probabilidade de um estado ocorrer é de 100%. É quando há certeza sobre qual símbolo (informação) será transmitido, então não é necesśario que o transmissor envie nenhum código para o receptor, dado que ele já conhece que símbolo é.
Complexidade de Kolmogorov e onde ela se insere nesse contexto
Observe essas 2 mensagens (strings) com 18 símbolos (caracteres):
R = ovbijtlwmdqyxkzeac
S = bbbbbaabbaaaaabbbbDe cara, percebemos neste caso, que a entropia de R é maior que a de S, isto é, sendo
H(R) = H(p(r)|r ∊ Dom(R)) := -∑ p(r)* log2(p(r)) e
H(S) = H(p(s)|s ∊ Dom(S)) := -∑ p(s)* log2(p(s)),
temos que H(R) > H(S). Onde p(a) é a probabilidade do evento a sobre o espaço amostral correspondente.
A complexidade de Kolmogorov ou entropia algorítmica (como alguns autores a chamaram originalmente), é o tamanho (comprimento em bits) do menor programa (algoritmo) capaz de gerar determinada string.
Para ilustar, poderíamos escrever um algorítmo para descrever S => emita ‘b’5, ‘a’2, ‘b’2, ‘a’5, ‘b’4
Já no caso de R, o algoritmo seria significativamente mais complexo. Como os eventos nele são equiprováveis, o programa P para gerar essa string, teria que ter toda essa informação.
R => emita ‘o’,’v’,’b’,’i’,’j’,…,’c’
Temos que:
K(R) > K(S)
K(R) > L(R)
K(S) < L(S)
K(x) é o tamanho do menor programa possível que descreve x.
L(x) é o comprimento de x.
Onde x é uma string.
Aqui entra o conceito de aleatoriedade de Kolmogorov. Uma string é dita aleatória se e somente se K(s) ≥ L(s). Ou seja, a string s não pode ser gerada por um programa P menor do que seu próprio comprimento, logo, ela não pode ser comprimida (toda informação de s precisa estar descrita em P).
Nota: Não há uma fórmula que calcule o valor de K(x) para toda e qualquer string x de entrada, porque é provado que K(x) é uma função incomputável.
Novamente, relacionando à entropia de Shannon: quanto maior o grau de incerteza presente em um conjunto de dados, maior sua entropia. Quanto maior for a quantidade de redundância em uma mensagem, menor o tamanho do programa mínimo posśivel capaz de gerar essa mensagem.
Conclusão
Percebe como tudo se encaixa e se relaciona?
Quanto maior o grau de incerteza/imprevisibilidade associada à distribuição de probabilidades em um conjunto de eventos (por exemplo, a emissão de uma sequência de símbolos por uma fonte), dizemos que sua entropia é maior. Significa, em outras palavras, que tem menos redundância, portanto os bits estão distribuídos de maneira mais desordenada, logo, a quantidade de informação nela é maior.
Se uma sequência de bits não segue nenhum padrão, isto é, não pode ser descrita por nenhuma outra string menor do que ela própria, então ela não pode ser comprimida e é aleatória segundo a Complexidade de Kolmogorov, significa grau zero de previsibilidade, grau máximo de incerteza; ou entropia média máxima.
Legal, não? 😃
Por hoje é isso, pretendo dar continuidade num próximo com um exemplo de codificação do algoritmo de Huffman.
O matemático Claude E. Shannon é tido como o pai da teoria da informação (apesar de ter havido outros anteriores que também deixaram importantes contribuições nesse campo). Entrou pra história com seu célebre paper “A Mathematical Theory of Communication” em 1948.
Andrey Nikolayevich Kolmogorov foi um dos mais proeminentes matemáticos soviéticos. Deixou um legado notável com brilhantes séries de publicações sobre teoria da probabilidade.
