Computer Science › Inteligência + Teoria
Antes de qualquer matemática de entropia, um simples argumento de contagem pelo princípio da casa dos pombos prova que nenhum algoritmo consegue comprimir sem perdas toda entrada possível e que, na verdade, a esmagadora maioria das entradas de um dado comprimento não pode ser comprimida de jeito nenhum; o teto que esta disciplina inteira explora é um limite matemático rígido, e não questão de encontrar um algoritmo mais esperto.
Define a autoinformação de Shannon I(x) = −log₂p(x), a medida baseada em logaritmo de quão surpreendente é um único resultado, e deriva por que o logaritmo (aditivo entre eventos independentes e coerente com a intuição de que resultados mais raros carregam mais informação) é a única medida com as propriedades que Shannon exigiu, e não uma escolha arbitrária.
A entropia H(X) = ∑ₓ p(x)·I(x) é exatamente a autoinformação esperada de uma variável aleatória (calculada aqui à mão para vários alfabetos pequenos), e prova-se que ela é maximizada pela distribuição uniforme e limitada entre 0 e log₂(n), o que a torna o único número que captura quão incerta, e portanto quão compressível, uma fonte realmente é.
A divergência KL D(p‖q) é derivada como o número esperado de bits extras pagos por codificar dados de p com um código feito para q (resolvido concretamente com duas moedas de vieses diferentes), e sua não negatividade (desigualdade de Gibbs) é provada pela desigualdade de Jensen; a entropia cruzada H(p,q) = H(p) + D(p‖q) é então identificada como exatamente a perda que `softmax-and-cross-entropy-loss` de `deep-learning` derivou de forma independente e autocontida, fechando o ciclo que aquele conceito deixou aberto de propósito.
Estende a entropia a pares de variáveis aleatórias: a entropia conjunta H(X,Y) mede a incerteza do par como um todo, a entropia condicional H(Y|X) mede o que sobra depois que X é conhecido, e a regra da cadeia H(X,Y) = H(X) + H(Y|X) liga as duas, provada em geral e conferida à mão numa distribuição conjunta real.
A informação mútua I(X;Y) = D(p(x,y) ‖ p(x)p(y)) é definida como a divergência KL entre a distribuição conjunta verdadeira e o produto das marginais (equivalentemente, H(X) − H(X|Y)), quantificando exatamente quantos bits saber Y economiza ao descrever X, e prova-se que ela é igual a zero precisamente quando X e Y são independentes.
O teorema da codificação de fonte de Shannon (nenhum código sem perdas consegue vencer um comprimento médio de H(X) bits por símbolo, e a entropia é assintoticamente alcançável por algum código) é enunciado e motivado com um esboço de prova real, no mesmo espírito de argumento de contagem já usado no limite inferior da ordenação por comparação de `algorithms`.
A desigualdade de Kraft ∑ᵢ 2^(−lᵢ) ≤ 1 caracteriza exatamente quais conjuntos de comprimentos de palavras-código admitem um código livre de prefixo, provada diretamente a partir da correspondência um para um entre um código livre de prefixo e uma árvore binária com os símbolos nas folhas, a mesma estrutura de árvore já vista em `trees` e `binary-trees-terminology-and-representation`, agora com um uso genuinamente novo.
O algoritmo de codificação de Huffman (fundir repetidamente os dois símbolos menos prováveis num novo nó combinado) é construído e rastreado à mão até formar uma árvore binária completa para um pequeno alfabeto real com frequências reais, produzindo um código livre de prefixo concreto e seu comprimento médio exato de palavra-código.
Prova-se que a codificação de Huffman é ótima entre todos os códigos livres de prefixo por meio de um argumento de troca construído sobre o mesmo molde que `algorithms` já estabeleceu para a seleção de atividades, mostrando que os dois símbolos menos prováveis sempre podem ser colocados como irmãos na profundidade máxima de alguma árvore de código ótima sem nenhuma perda no comprimento esperado.
Um panorama do que os sistemas reais usam depois de Huffman. A codificação aritmética remove a restrição de Huffman de bits inteiros por símbolo para chegar arbitrariamente perto do limite da entropia, e a compressão por dicionário no estilo LZ77 (combinada com a própria codificação de Huffman dentro do DEFLATE, o algoritmo por trás do gzip e do PNG) explora substrings repetidas que uma única tabela fixa de frequências de símbolos nunca consegue capturar.
O canal binário simétrico (cada bit transmitido é invertido de forma independente com probabilidade p, uma genuína tentativa de Bernoulli aplicada por bit) é apresentado como o canal ruidoso de brinquedo canônico que torna concretos e calculáveis à mão todos os argumentos de capacidade e do teorema da codificação deste bloco.
A capacidade do canal C = maxₚ₍ₓ₎ I(X;Y), a maior informação mútua alcançável entre todas as distribuições de entrada possíveis, é definida e calculada à mão para o canal binário simétrico, chegando à forma fechada exata C = 1 − H(p) e confirmando que um canal mais ruidoso (maior probabilidade de cruzamento) tem capacidade estritamente menor.
O teorema da codificação de canal ruidoso de Shannon (a comunicação confiável é possível a qualquer taxa abaixo da capacidade e impossível acima dela) é enunciado com sua implicação no mundo real tornada concreta, com a direção de alcançabilidade motivada no nível de intuição de sequências típicas e codificação aleatória adequado a um público de computação, em vez de toda a maquinaria de prova de nível de pós-graduação.
Liga a maquinaria abstrata de capacidade e do teorema da codificação a códigos corretores de erros reais (bits de paridade e códigos de Hamming resolvidos à mão), desenvolvendo a técnica de correção antecipada de erros que o conceito de camada de enlace de `computer-networks` nomeou explicitamente mas optou por não desenvolver, fechando a pendência deixada por aquela disciplina.
Um capstone que rastreia de ponta a ponta uma mensagem real e pequena. Calcula-se à mão a entropia da fonte, constrói-se o código de Huffman e mede-se a taxa de compressão real alcançada contra o limite teórico da entropia, e depois os bits comprimidos passam por um canal binário simétrico, checando a taxa de transmissão da mensagem contra a capacidade real do canal.
Part of the Computer Science curriculum.
Antes de qualquer matemática de entropia, um simples argumento de contagem pelo princípio da casa dos pombos prova que nenhum algoritmo consegue comprimir sem perdas toda entrada possível e que, na verdade, a esmagadora maioria das entradas de um dado comprimento não pode ser comprimida de jeito nenhum; o teto que esta disciplina inteira explora é um limite matemático rígido, e não questão de encontrar um algoritmo mais esperto.
Define a autoinformação de Shannon I(x) = −log₂p(x), a medida baseada em logaritmo de quão surpreendente é um único resultado, e deriva por que o logaritmo (aditivo entre eventos independentes e coerente com a intuição de que resultados mais raros carregam mais informação) é a única medida com as propriedades que Shannon exigiu, e não uma escolha arbitrária.
A entropia H(X) = ∑ₓ p(x)·I(x) é exatamente a autoinformação esperada de uma variável aleatória (calculada aqui à mão para vários alfabetos pequenos), e prova-se que ela é maximizada pela distribuição uniforme e limitada entre 0 e log₂(n), o que a torna o único número que captura quão incerta, e portanto quão compressível, uma fonte realmente é.
A divergência KL D(p‖q) é derivada como o número esperado de bits extras pagos por codificar dados de p com um código feito para q (resolvido concretamente com duas moedas de vieses diferentes), e sua não negatividade (desigualdade de Gibbs) é provada pela desigualdade de Jensen; a entropia cruzada H(p,q) = H(p) + D(p‖q) é então identificada como exatamente a perda que `softmax-and-cross-entropy-loss` de `deep-learning` derivou de forma independente e autocontida, fechando o ciclo que aquele conceito deixou aberto de propósito.
Estende a entropia a pares de variáveis aleatórias: a entropia conjunta H(X,Y) mede a incerteza do par como um todo, a entropia condicional H(Y|X) mede o que sobra depois que X é conhecido, e a regra da cadeia H(X,Y) = H(X) + H(Y|X) liga as duas, provada em geral e conferida à mão numa distribuição conjunta real.
A informação mútua I(X;Y) = D(p(x,y) ‖ p(x)p(y)) é definida como a divergência KL entre a distribuição conjunta verdadeira e o produto das marginais (equivalentemente, H(X) − H(X|Y)), quantificando exatamente quantos bits saber Y economiza ao descrever X, e prova-se que ela é igual a zero precisamente quando X e Y são independentes.
O teorema da codificação de fonte de Shannon (nenhum código sem perdas consegue vencer um comprimento médio de H(X) bits por símbolo, e a entropia é assintoticamente alcançável por algum código) é enunciado e motivado com um esboço de prova real, no mesmo espírito de argumento de contagem já usado no limite inferior da ordenação por comparação de `algorithms`.
A desigualdade de Kraft ∑ᵢ 2^(−lᵢ) ≤ 1 caracteriza exatamente quais conjuntos de comprimentos de palavras-código admitem um código livre de prefixo, provada diretamente a partir da correspondência um para um entre um código livre de prefixo e uma árvore binária com os símbolos nas folhas, a mesma estrutura de árvore já vista em `trees` e `binary-trees-terminology-and-representation`, agora com um uso genuinamente novo.
O algoritmo de codificação de Huffman (fundir repetidamente os dois símbolos menos prováveis num novo nó combinado) é construído e rastreado à mão até formar uma árvore binária completa para um pequeno alfabeto real com frequências reais, produzindo um código livre de prefixo concreto e seu comprimento médio exato de palavra-código.
Prova-se que a codificação de Huffman é ótima entre todos os códigos livres de prefixo por meio de um argumento de troca construído sobre o mesmo molde que `algorithms` já estabeleceu para a seleção de atividades, mostrando que os dois símbolos menos prováveis sempre podem ser colocados como irmãos na profundidade máxima de alguma árvore de código ótima sem nenhuma perda no comprimento esperado.
Um panorama do que os sistemas reais usam depois de Huffman. A codificação aritmética remove a restrição de Huffman de bits inteiros por símbolo para chegar arbitrariamente perto do limite da entropia, e a compressão por dicionário no estilo LZ77 (combinada com a própria codificação de Huffman dentro do DEFLATE, o algoritmo por trás do gzip e do PNG) explora substrings repetidas que uma única tabela fixa de frequências de símbolos nunca consegue capturar.
O canal binário simétrico (cada bit transmitido é invertido de forma independente com probabilidade p, uma genuína tentativa de Bernoulli aplicada por bit) é apresentado como o canal ruidoso de brinquedo canônico que torna concretos e calculáveis à mão todos os argumentos de capacidade e do teorema da codificação deste bloco.
A capacidade do canal C = maxₚ₍ₓ₎ I(X;Y), a maior informação mútua alcançável entre todas as distribuições de entrada possíveis, é definida e calculada à mão para o canal binário simétrico, chegando à forma fechada exata C = 1 − H(p) e confirmando que um canal mais ruidoso (maior probabilidade de cruzamento) tem capacidade estritamente menor.
O teorema da codificação de canal ruidoso de Shannon (a comunicação confiável é possível a qualquer taxa abaixo da capacidade e impossível acima dela) é enunciado com sua implicação no mundo real tornada concreta, com a direção de alcançabilidade motivada no nível de intuição de sequências típicas e codificação aleatória adequado a um público de computação, em vez de toda a maquinaria de prova de nível de pós-graduação.
Liga a maquinaria abstrata de capacidade e do teorema da codificação a códigos corretores de erros reais (bits de paridade e códigos de Hamming resolvidos à mão), desenvolvendo a técnica de correção antecipada de erros que o conceito de camada de enlace de `computer-networks` nomeou explicitamente mas optou por não desenvolver, fechando a pendência deixada por aquela disciplina.
Um capstone que rastreia de ponta a ponta uma mensagem real e pequena. Calcula-se à mão a entropia da fonte, constrói-se o código de Huffman e mede-se a taxa de compressão real alcançada contra o limite teórico da entropia, e depois os bits comprimidos passam por um canal binário simétrico, checando a taxa de transmissão da mensagem contra a capacidade real do canal.