Conseguimos!
“O objetivo deste curso é prepará-lo para o seu futuro técnico.”
Olá, Habr. Lembre-se do artigo incrível (+219, 2588 marcadores, 429 mil leituras)?
Então Hamming (sim, sim, automonitoramento e autocorreção ) há um todo , escrito com base em suas palestras. Nós traduzimos, porque o homem fala o que pensa.
Este livro não é apenas sobre TI, é um livro sobre o estilo de pensamento de pessoas incrivelmente legais. “Não é apenas um impulso ao pensamento positivo; descreve as condições que aumentam as chances de realizar um ótimo trabalho.”
Obrigado a Andrey Pakhomov pela tradução.
A Teoria da Informação foi desenvolvida por C. E. Shannon no final da década de 1940. A administração do Bell Labs insistiu que ele chamasse isso de "Teoria da Comunicação" porque... este é um nome muito mais preciso. Por razões óbvias, o nome “Teoria da Informação” tem um impacto muito maior no público, razão pela qual Shannon o escolheu, e é o nome que conhecemos até hoje. O próprio nome sugere que a teoria lida com informação, o que a torna importante à medida que avançamos na era da informação. Neste capítulo, abordarei várias conclusões principais desta teoria, fornecerei evidências não estritas, mas bastante intuitivas de algumas disposições individuais desta teoria, para que você entenda o que realmente é a “Teoria da Informação”, onde você pode aplicá-la e onde não.
Em primeiro lugar, o que é “informação”? Shannon equipara informação à incerteza. Ele escolheu o logaritmo negativo da probabilidade de um evento como uma medida quantitativa da informação que você recebe quando ocorre um evento com probabilidade p. Por exemplo, se eu lhe disser que o tempo em Los Angeles está com neblina, então p está próximo de 1, o que realmente não nos dá muita informação. Mas se eu disser que chove em Monterey em junho, haverá incerteza na mensagem e ela conterá mais informações. Um evento confiável não contém nenhuma informação, pois log 1 = 0.
Vejamos isso com mais detalhes. Shannon acreditava que a medida quantitativa da informação deveria ser uma função contínua da probabilidade de um evento p, e para eventos independentes deveria ser aditiva - a quantidade de informação obtida como resultado da ocorrência de dois eventos independentes deveria ser igual ao quantidade de informações obtidas em decorrência da ocorrência de um evento conjunto. Por exemplo, o resultado de um lançamento de dados e de uma moeda são geralmente tratados como eventos independentes. Vamos traduzir o que foi dito acima para a linguagem da matemática. Se I(p) é a quantidade de informação contida em um evento com probabilidade p, então para um evento conjunto que consiste em dois eventos independentes x com probabilidade p1 e y com probabilidade p2 obtemos
(x e y são eventos independentes)
Esta é a equação funcional de Cauchy, verdadeira para todos p1 e p2. Para resolver esta equação funcional, suponha que
p1 = p2 = p,
isto dá
Se p1 = p2 e p2 = p então
etc. Estendendo este processo usando o método padrão para exponenciais, para todos os números racionais m/n o seguinte é verdadeiro
Da suposta continuidade da medida de informação, segue-se que a função logarítmica é a única solução contínua para a equação funcional de Cauchy.
Na teoria da informação, é comum considerar a base do logaritmo como 2, portanto, uma escolha binária contém exatamente 1 bit de informação. Portanto, a informação é medida pela fórmula
Vamos fazer uma pausa e entender o que aconteceu acima. Em primeiro lugar, não definimos o conceito de “informação”; simplesmente definimos a fórmula para a sua medida quantitativa.
Em segundo lugar, esta medida está sujeita a incerteza e, embora seja razoavelmente adequada para máquinas – por exemplo, sistemas telefónicos, rádio, televisão, computadores, etc. – não reflecte atitudes humanas normais em relação à informação.
Em terceiro lugar, esta é uma medida relativa, depende do estado atual do seu conhecimento. Se você observar um fluxo de “números aleatórios” de um gerador de números aleatórios, você assumirá que cada próximo número é incerto, mas se você souber a fórmula para calcular “números aleatórios”, o próximo número será conhecido e, portanto, não será. contém informações.
Portanto, a definição de informação de Shannon é apropriada para máquinas em muitos casos, mas não parece se adequar à compreensão humana da palavra. É por esta razão que a “Teoria da Informação” deveria ter sido chamada de “Teoria da Comunicação”. No entanto, é tarde demais para mudar as definições (que deram à teoria a sua popularidade inicial, e que ainda fazem as pessoas pensarem que esta teoria trata de “informação”), por isso temos que conviver com elas, mas ao mesmo tempo é preciso compreender claramente até que ponto a definição de informação de Shannon está do seu significado comumente usado. As informações de Shannon tratam de algo completamente diferente, nomeadamente a incerteza.
Aqui está algo em que pensar ao propor qualquer terminologia. Como uma definição proposta, como a definição de informação de Shannon, concorda com sua ideia original e quão diferente ela é? Quase não existe um termo que reflita exatamente a sua visão anterior de um conceito, mas, em última análise, é a terminologia utilizada que reflete o significado do conceito, portanto, formalizar algo através de definições claras sempre introduz algum ruído.
Considere um sistema cujo alfabeto consiste em símbolos q com probabilidades pi. Nesse caso quantidade média de informações no sistema (seu valor esperado) é igual a:
Isso é chamado de entropia do sistema com distribuição de probabilidade {pi}. Usamos o termo “entropia” porque a mesma forma matemática aparece na termodinâmica e na mecânica estatística. É por isso que o termo “entropia” cria uma certa aura de importância em torno de si, que em última análise não se justifica. A mesma forma matemática de notação não implica a mesma interpretação dos símbolos!
A entropia da distribuição de probabilidade desempenha um papel importante na teoria da codificação. A desigualdade de Gibbs para duas distribuições de probabilidade diferentes pi e qi é uma das consequências importantes desta teoria. Então devemos provar que
A prova é baseada em um gráfico óbvio, Fig. 13.I, o que mostra que
e a igualdade é alcançada somente quando x = 1. Apliquemos a desigualdade a cada termo da soma do lado esquerdo:
Se o alfabeto de um sistema de comunicação consiste em q símbolos, então tomando a probabilidade de transmissão de cada símbolo qi = 1/q e substituindo q, obtemos da desigualdade de Gibbs
Figura 13.I
Isso significa que se a probabilidade de transmissão de todos os símbolos q for igual e igual a - 1 / q, então a entropia máxima é igual a ln q, caso contrário a desigualdade é válida.
No caso de um código unicamente decodificável, temos a desigualdade de Kraft
Agora, se definirmos pseudo-probabilidades
onde é claro = 1, que segue da desigualdade de Gibbs,
e aplicando um pouco de álgebra (lembre-se que K ≤ 1, para que possamos abandonar o termo logarítmico e talvez fortalecer a desigualdade mais tarde), obtemos
onde L é o comprimento médio do código.
Assim, a entropia é o limite mínimo para qualquer código caractere por símbolo com um comprimento médio de palavra-código L. Este é o teorema de Shannon para um canal livre de interferências.
Agora consideremos o teorema principal sobre as limitações dos sistemas de comunicação nos quais a informação é transmitida como um fluxo de bits independentes e o ruído está presente. Entende-se que a probabilidade de transmissão correta de um bit é P > 1/2, e a probabilidade de o valor do bit ser invertido durante a transmissão (ocorrerá um erro) é igual a Q = 1 - P. Por conveniência, nós suponha que os erros sejam independentes e que a probabilidade de erro seja a mesma para cada bit enviado - ou seja, há “ruído branco” no canal de comunicação.
A maneira como temos um longo fluxo de n bits codificados em uma mensagem é a extensão n dimensional do código de um bit. Determinaremos o valor de n posteriormente. Considere uma mensagem que consiste em n bits como um ponto no espaço n-dimensional. Como temos um espaço n-dimensional - e para simplificar vamos assumir que cada mensagem tem a mesma probabilidade de ocorrência - existem M mensagens possíveis (M também será definida posteriormente), portanto a probabilidade de qualquer mensagem enviada é
(remetente)
Anexo 13.II
A seguir, considere a ideia de capacidade do canal. Sem entrar em detalhes, a capacidade do canal é definida como a quantidade máxima de informação que pode ser transmitida de forma confiável através de um canal de comunicação, levando em consideração a utilização da codificação mais eficiente. Não há argumento de que mais informações possam ser transmitidas através de um canal de comunicação do que a sua capacidade. Isto pode ser provado para um canal binário simétrico (que usamos no nosso caso). A capacidade do canal, ao enviar bits, é especificada como
onde, como antes, P é a probabilidade de nenhum erro em qualquer bit enviado. Ao enviar n bits independentes, a capacidade do canal é dada por
Se estivermos próximos da capacidade do canal, então devemos enviar quase esta quantidade de informação para cada um dos símbolos ai, i = 1, ..., M. Considerando que a probabilidade de ocorrência de cada símbolo ai é 1/M, Nós temos
quando enviamos qualquer uma das M mensagens igualmente prováveis ai, temos
Quando n bits são enviados, esperamos que ocorram erros nQ. Na prática, para uma mensagem composta por n bits, teremos aproximadamente nQ erros na mensagem recebida. Para n grande, variação relativa (variação = largura de distribuição,)
a distribuição do número de erros tornar-se-á cada vez mais estreita à medida que n aumenta.
Então, do lado do transmissor, pego a mensagem ai para enviar e desenho uma esfera ao redor dela com um raio
que é ligeiramente maior em um valor igual a e2 do que o número esperado de erros Q, (Figura 13.II). Se n for grande o suficiente, então há uma probabilidade arbitrariamente pequena de um ponto de mensagem bj aparecer no lado do receptor que se estende além desta esfera. Vamos esboçar a situação como a vejo do ponto de vista do transmissor: temos quaisquer raios da mensagem transmitida ai até a mensagem recebida bj com probabilidade de erro igual (ou quase igual) à distribuição normal, atingindo um máximo de nQ. Para qualquer e2 dado, existe um n tão grande que a probabilidade do ponto resultante bj estar fora da minha esfera é tão pequena quanto você desejar.
Agora vamos examinar a mesma situação do seu lado (Fig. 13.III). No lado do receptor existe uma esfera S(r) de mesmo raio r em torno do ponto recebido bj no espaço n-dimensional, tal que se a mensagem recebida bj está dentro da minha esfera, então a mensagem ai enviada por mim está dentro da sua esfera.
Como pode ocorrer um erro? O erro pode ocorrer nos casos descritos na tabela abaixo:
Figura 13.III
Aqui vemos que se na esfera construída em torno do ponto recebido houver pelo menos mais um ponto correspondente a uma possível mensagem não codificada enviada, então ocorreu um erro durante a transmissão, pois não é possível determinar qual dessas mensagens foi transmitida. A mensagem enviada está livre de erros somente se o ponto correspondente a ela estiver na esfera, e não houver outros pontos possíveis no código fornecido que estejam na mesma esfera.
Temos uma equação matemática para a probabilidade de erro Pe se a mensagem ai for enviada
Podemos descartar o primeiro fator no segundo termo, tomando-o como 1. Assim obtemos a desigualdade
Obviamente, o
portanto
reaplicar ao último termo à direita
Tomando n grande o suficiente, o primeiro termo pode ser considerado tão pequeno quanto desejado, digamos, menor que algum número d. Portanto temos
Agora vamos ver como podemos construir um código de substituição simples para codificar M mensagens que consistem em n bits. Não tendo ideia de como exatamente construir um código (os códigos de correção de erros ainda não haviam sido inventados), Shannon escolheu a codificação aleatória. Jogue uma moeda para cada um dos n bits da mensagem e repita o processo para M mensagens. No total, nM lançamentos de moeda precisam ser feitos, então é possível
dicionários de código com a mesma probabilidade ½nM. É claro que o processo aleatório de criação de um livro de códigos significa que existe a possibilidade de duplicatas, bem como de pontos de código que estarão próximos uns dos outros e, portanto, serão uma fonte de prováveis erros. Deve-se provar que se isso não acontecer com uma probabilidade maior do que qualquer pequeno nível de erro escolhido, então o n dado é grande o suficiente.
O ponto crucial é que Shannon calculou a média de todos os livros de códigos possíveis para encontrar o erro médio! Usaremos o símbolo Av[.] para denotar o valor médio do conjunto de todos os livros de códigos aleatórios possíveis. Calcular a média de uma constante d, é claro, fornece uma constante, uma vez que, para calcular a média, cada termo é igual a todos os outros termos da soma,
que pode ser aumentado (M–1 vai para M)
Para qualquer mensagem, ao calcular a média de todos os livros de códigos, a codificação percorre todos os valores possíveis, portanto, a probabilidade média de um ponto estar em uma esfera é a razão entre o volume da esfera e o volume total do espaço. O volume da esfera é
onde s=Q+e2 <1/2 e ns deve ser um número inteiro.
O último termo à direita é o maior nesta soma. Primeiro, vamos estimar seu valor usando a fórmula de Stirling para fatoriais. Observaremos então o coeficiente decrescente do termo à sua frente, notamos que este coeficiente aumenta à medida que nos movemos para a esquerda, e assim podemos: (1) restringir o valor da soma à soma da progressão geométrica com este coeficiente inicial, (2) expandir a progressão geométrica de ns termos para um número infinito de termos, (3) calcular a soma de uma progressão geométrica infinita (álgebra padrão, nada significativo) e finalmente obter o valor limite (para um suficientemente grande n):
Observe como a entropia H(s) apareceu na identidade binomial. Observe que a expansão da série de Taylor H(s)=H(Q+e2) fornece uma estimativa obtida levando em consideração apenas a primeira derivada e ignorando todas as outras. Agora vamos montar a expressão final:
onde
Tudo o que temos que fazer é escolher e2 tal que e3 < e1, e então o último termo será arbitrariamente pequeno, desde que n seja suficientemente grande. Consequentemente, o erro médio de PE pode ser obtido tão pequeno quanto desejado com a capacidade do canal arbitrariamente próxima de C.
Se a média de todos os códigos tiver um erro suficientemente pequeno, então pelo menos um código deve ser adequado, portanto existe pelo menos um sistema de codificação adequado. Este é um resultado importante obtido por Shannon - "Teorema de Shannon para um canal ruidoso", embora deva ser notado que ele provou isso para um caso muito mais geral do que para o canal simétrico binário simples que usei. Para o caso geral, os cálculos matemáticos são muito mais complicados, mas as ideias não são tão diferentes, muitas vezes, usando o exemplo de um caso particular, é possível revelar o verdadeiro significado do teorema.
Vamos criticar o resultado. Repetimos repetidamente: “Para n suficientemente grande.” Mas quão grande é n? Muito, muito grande se você realmente deseja estar próximo da capacidade do canal e ter certeza da transferência de dados correta! Tão grande, na verdade, que você terá que esperar muito tempo para acumular uma mensagem com bits suficientes para codificá-la mais tarde. Nesse caso, o tamanho do dicionário de código aleatório será simplesmente enorme (afinal, tal dicionário não pode ser representado de uma forma mais curta do que uma lista completa de todos os Mn bits, apesar do fato de n e M serem muito grandes)!
Os códigos de correção de erros evitam esperar por uma mensagem muito longa e depois codificá-la e decodificá-la por meio de livros de códigos muito grandes, porque eles evitam os próprios livros de códigos e, em vez disso, usam computação comum. Na teoria simples, tais códigos tendem a perder a capacidade de se aproximar da capacidade do canal e ainda manter uma baixa taxa de erros, mas quando o código corrige um grande número de erros, eles apresentam um bom desempenho. Em outras palavras, se você alocar alguma capacidade de canal para correção de erros, então você deverá utilizar a capacidade de correção de erros na maior parte do tempo, ou seja, um grande número de erros deve ser corrigido em cada mensagem enviada, caso contrário você desperdiçará essa capacidade.
Ao mesmo tempo, o teorema provado acima ainda não é sem sentido! Mostra que sistemas de transmissão eficientes devem usar esquemas de codificação inteligentes para cadeias de bits muito longas. Um exemplo são os satélites que voaram além dos planetas exteriores; À medida que se afastam da Terra e do Sol, são obrigados a corrigir cada vez mais erros no bloco de dados: alguns satélites utilizam painéis solares, que fornecem cerca de 5 W, outros utilizam fontes de energia nuclear, que fornecem aproximadamente a mesma potência. A baixa potência da fonte de alimentação, o pequeno tamanho das antenas transmissoras e o tamanho limitado das antenas receptoras na Terra, a enorme distância que o sinal deve percorrer - tudo isso requer o uso de códigos com alto nível de correção de erros para construir um sistema de comunicação eficaz.
Voltemos ao espaço n-dimensional que usamos na prova acima. Ao discuti-lo, mostramos que quase todo o volume da esfera está concentrado próximo à superfície externa - assim, é quase certo que o sinal enviado estará localizado próximo à superfície da esfera construída em torno do sinal recebido, mesmo com uma distância relativamente pequeno raio de tal esfera. Portanto, não é surpreendente que o sinal recebido, após corrigir um número arbitrariamente grande de erros, nQ, acabe sendo arbitrariamente próximo de um sinal sem erros. A capacidade de ligação que discutimos anteriormente é fundamental para a compreensão deste fenômeno. Observe que esferas semelhantes construídas para códigos de Hamming de correção de erros não se sobrepõem. O grande número de dimensões quase ortogonais no espaço n-dimensional mostra porque podemos ajustar M esferas no espaço com pouca sobreposição. Se permitirmos uma sobreposição pequena, arbitrariamente pequena, que pode levar a apenas um pequeno número de erros durante a decodificação, podemos obter uma colocação densa de esferas no espaço. Hamming garantiu um certo nível de correção de erros, Shannon - uma baixa probabilidade de erro, mas ao mesmo tempo mantendo o rendimento real arbitrariamente próximo da capacidade do canal de comunicação, o que os códigos de Hamming não podem fazer.
A teoria da informação não nos diz como conceber um sistema eficiente, mas aponta o caminho para sistemas de comunicação eficientes. É uma ferramenta valiosa para a construção de sistemas de comunicação máquina-máquina, mas, como observado anteriormente, tem pouca relevância para a forma como os humanos comunicam entre si. Até que ponto a herança biológica se assemelha a sistemas técnicos de comunicação é simplesmente desconhecida, pelo que não está actualmente claro como a teoria da informação se aplica aos genes. Não temos outra escolha senão tentar, e se o sucesso nos mostrar a natureza maquinal deste fenómeno, então o fracasso apontará para outros aspectos significativos da natureza da informação.
Não vamos divagar muito. Vimos que todas as definições originais, em maior ou menor grau, devem expressar a essência das nossas crenças originais, mas são caracterizadas por algum grau de distorção e, portanto, não são aplicáveis. É tradicionalmente aceite que, em última análise, a definição que utilizamos define realmente a essência; mas isso apenas nos diz como processar as coisas e de forma alguma nos transmite qualquer significado. A abordagem postulacional, tão fortemente favorecida nos círculos matemáticos, deixa muito a desejar na prática.
Agora veremos um exemplo de testes de QI em que a definição é tão circular quanto você gostaria que fosse e, como resultado, enganosa. É criado um teste que supostamente mede a inteligência. Em seguida, é revisado para torná-lo o mais consistente possível, e então é publicado e, num método simples, calibrado para que a “inteligência” medida acabe sendo normalmente distribuída (numa curva de calibração, é claro). Todas as definições devem ser verificadas novamente, não apenas quando são propostas pela primeira vez, mas também muito mais tarde, quando são utilizadas nas conclusões tiradas. Até que ponto os limites de definição são apropriados para o problema que está sendo resolvido? Com que frequência as definições dadas num ambiente são aplicadas em ambientes bastante diferentes? Isso acontece com bastante frequência! Nas humanidades, que você inevitavelmente encontrará em sua vida, isso acontece com mais frequência.
Assim, um dos propósitos desta apresentação da teoria da informação, além de demonstrar sua utilidade, foi alertar sobre esse perigo, ou mostrar exatamente como utilizá-la para obter o resultado desejado. Há muito se observa que as definições iniciais determinam o que você encontra no final, em uma extensão muito maior do que parece. As definições iniciais exigem muita atenção de sua parte, não apenas em qualquer situação nova, mas também em áreas com as quais você já trabalha há muito tempo. Isso permitirá compreender até que ponto os resultados obtidos são uma tautologia e não algo útil.
A famosa história de Eddington conta a história de pessoas que pescavam no mar com rede. Depois de estudarem o tamanho dos peixes que pescaram, determinaram o tamanho mínimo dos peixes que se encontram no mar! A sua conclusão foi motivada pelo instrumento utilizado e não pela realidade.
Para ser continuado ...
Quem quiser ajudar na tradução, diagramação e publicação do livro - escreva em mensagem pessoal ou email [email protegido]
Aliás, também lançamos a tradução de outro livro bacana - )
Procuramos especialmente aqueles que ajudarão a traduzir . (transferência por 10 minutos, os primeiros 20 já foram realizados)
Conteúdo do livro e capítulos traduzidos
- Introdução à Arte de Fazer Ciência e Engenharia: Aprendendo a Aprender (28 de março de 1995)
- "Fundamentos da Revolução Digital (Discreta)" (30 de março de 1995)
- "História dos Computadores - Hardware" (31 de março de 1995)
- "História dos Computadores - Software" (4 de abril de 1995)
- "História dos Computadores - Aplicações" (6 de abril de 1995)
- "Inteligência Artificial - Parte I" (7 de abril de 1995)
- "Inteligência Artificial - Parte II" (11 de abril de 1995)
- "Inteligência Artificial III" (13 de abril de 1995)
- "Espaço n-Dimensional" (14 de abril de 1995)
- "Teoria da Codificação - A Representação da Informação, Parte I" (18 de abril de 1995)
- "Teoria da Codificação - A Representação da Informação, Parte II" (20 de abril de 1995)
- "Códigos de correção de erros" (21 de abril de 1995)
- "Teoria da Informação" (25 de abril de 1995)
- "Filtros Digitais, Parte I" (27 de abril de 1995)
- "Filtros Digitais, Parte II" (28 de abril de 1995)
- "Filtros Digitais, Parte III" (2 de maio de 1995)
- "Filtros Digitais, Parte IV" (4 de maio de 1995)
- "Simulação, Parte I" (5 de maio de 1995)
- "Simulação, Parte II" (9 de maio de 1995)
- "Simulação, Parte III" (11 de maio de 1995)
- "Fibra Óptica" (12 de maio de 1995)
- "Instrução Auxiliada por Computador" (16 de maio de 1995)
- "Matemática" (18 de maio de 1995)
- "Mecânica Quântica" (19 de maio de 1995)
- "Criatividade" (23 de maio de 1995). Tradução:
- "Especialistas" (25 de maio de 1995)
- "Dados não confiáveis" (26 de maio de 1995)
- "Engenharia de Sistemas" (30 de maio de 1995)
- "Você obtém o que mede" (1º de junho de 1995)
- (Junho de 2, 1995) traduzir em pedaços de 10 minutos
- Hamming, “Você e sua pesquisa” (6 de junho de 1995).
Quem quiser ajudar na tradução, diagramação e publicação do livro - escreva em mensagem pessoal ou email [email protegido]
Fonte: habr.com