Espaço para eventos aleatórios
Em 1946, o estatístico americano John Tukey propôs o nome BIT
Imagine um espaço de eventos aleatóriosque consiste em jogar uma moeda falsa, de ambos os lados é uma águia. Quando uma águia cai? É claro que sempre. Nós sabemos disso com antecedência, porque o nosso espaço é tão organizado. A queda de uma águia é um evento confiável, isto é, sua probabilidade é igual a 1. Daremos muita informação se dissermos sobre uma águia derrubada? Não A quantidade de informação nesta mensagem, será considerada igual a 0.
Agora vamos jogar a moeda justa:de um lado é cara e do outro coroa, como deveria ser. Cara ou coroa serão dois eventos diferentes que compõem nosso espaço de eventos aleatórios. Se reportarmos o resultado de um lançamento, será de facto uma informação nova. Se cair cara, reportaremos 0, e se coroa, 1. Para reportar esta informação, precisamos apenas de 1 bit.
O que mudou?A incerteza apareceu em nosso espaço de eventos. Temos algo a contar sobre isso para alguém que não joga uma moeda e não vê o resultado do lançamento. Mas para compreender adequadamente a nossa mensagem, ele deve saber exatamente o que estamos fazendo e o que significam os 0 e 1.Nossos espaços de eventos devem corresponder e o processo de decodificação é exclusivo para restaurar o resultado do lançamento.Se o espaço de eventos do transmissor e do receptor não coincidir ou não houver possibilidade de decodificação inequívoca da mensagem, a informação permanecerá apenas ruído no canal de comunicação.
Se você lançar dois de forma independente e simultâneamoedas, então haverá quatro resultados diferentes igualmente prováveis: cara-cara, cara-coroa, coroa-cara e coroa-coroa. Para transmitir informações precisaremos de 2 bits, e nossas mensagens serão as seguintes: 00, 01, 10 e 11. São o dobro de informações. Isso aconteceu porque a incerteza aumentou. Se tentarmos adivinhar o resultado desse lançamento pareado, teremos duas vezes mais chances de estar errados.
Quanto maior a incerteza do espaço de eventos, mais informações contém a mensagem sobre seu estado.
Vamos complicar um pouco nosso espaço para eventos.Até agora, todos os eventos que aconteceram foram igualmente prováveis. Mas em espaços reais, nem todos os eventos têm probabilidade igual. Digamos que a probabilidade de o corvo que vemos ser preto seja próxima de 1. A probabilidade de o primeiro transeunte que encontrarmos na rua ser um homem é de aproximadamente 0,5. Mas encontrar um crocodilo nas ruas de Moscou é quase impossível. Intuitivamente, entendemos que um relato sobre um encontro com um crocodilo tem um valor informativo muito maior do que um relato sobre um corvo negro.Quanto menor a probabilidade de um evento, mais informações na mensagem sobre esse evento.
Deixe o espaço do evento não ser tão exótico. Nós apenas ficamos na janela e olhamos para os carros que passam. Carros de quatro cores estão passando, o que precisamos informar. Para fazer isso, vamos codificar as cores: preto-00, branco-01, vermelho-10, azul-11. Para informar exatamente qual carro percorreu, precisamos apenas transferir 2 bits de informação.
Mas por um bom tempo observando os carros,Observamos que a cor dos carros é desigual: preto - 50% (a cada segundo), branco - 25% (a cada quatro), vermelho e azul - 12,5% (a cada oitavo). Então você pode otimizar as informações transmitidas.
A maioria dos carros é preta, entãovamos denotar preto - 0 - o código mais curto, e deixar o código de todo o resto começar em 1. Da metade restante, branco - 10, e as cores restantes começam em 11. Finalmente, vamos denotar vermelho - 110 e azul - 111.
Agora, passando informações sobre a cor do carro, podemos codificá-lo mais de perto.
Entropia de Shannon
Deixe nosso espaço de eventos consistir em neventos diferentes. Ao jogar uma moeda com duas caras há exatamente um desses eventos, ao jogar uma moeda honesta há exatamente 2, ao jogar duas moedas ou observar carros há exatamente 4. Cada evento tem uma probabilidade de ocorrer. Ao lançar uma moeda com duas caras, há um evento (queda de cara) e sua probabilidade é p1 = 1. Ao lançar uma moeda justa, há dois eventos, eles são igualmente prováveis e a probabilidade de cada um é 0,5: p1 = 0,5, p2 = 0,5. Ao lançar duas moedas justas, existem quatro eventos, todos eles são igualmente prováveis e a probabilidade de cada um é 0,25: p1 = 0,25, p2 = 0,25, p3 = 0,25, p4 = 0,25. Ao observar carros, existem quatro eventos e eles têm probabilidades diferentes: preto - 0,5, branco - 0,25, vermelho - 0,125, azul - 0,125: p1 = 0,5, p2 = 0,25, p3 = 0,125, p4 = 0,125.
Isto não é uma coincidência.Shannon escolheu a entropia (uma medida de incerteza no espaço do evento) para que três condições fossem atendidas:
- 1A entropia de um evento confiável, cuja probabilidade é 1, é igual a 0.
- A entropia de dois eventos independentes é igual à soma das entropias desses eventos.
- A entropia é máxima se todos os eventos forem igualmente prováveis.
Todos esses requisitos são totalmente consistentes com nossosideias sobre a incerteza do espaço do evento. Se houver apenas um evento (o primeiro exemplo), não há incerteza. Se os eventos são independentes - a incerteza da soma é igual à soma das incertezas - eles simplesmente somam (o exemplo do lançamento de duas moedas). E finalmente, se todos os eventos forem igualmente prováveis, então o grau de incerteza do sistema é máximo. Como no caso do lançamento de duas moedas, todos os quatro acontecimentos são igualmente prováveis e a entropia é 2, é maior do que no caso dos carros, quando também existem quatro acontecimentos, mas têm probabilidades diferentes - neste caso a entropia é 1,75.
A quantidade H desempenha um papel central na teoria da informação como medida de informação, escolha e incerteza.
Claude Shannon
Claude Elwood Shannon- Engenheiro americano, criptoanalista ematemático. Considerado o “pai da era da informação”. Fundador da teoria da informação, que encontrou aplicação em modernos sistemas de comunicação de alta tecnologia. Forneceu conceitos fundamentais, ideias e suas formulações matemáticas que atualmente constituem a base das modernas tecnologias de comunicação.
Em 1948, propôs usar a palavra "bit"para indicar a menor unidade de informação. Ele também demonstrou que a entropia inserida por ele é equivalente à incerteza da informação na mensagem transmitida. Os artigos de Shannon "Teoria Matemática da Comunicação" e "Teoria da Comunicação em Sistemas Secretos" são considerados fundamentais para a teoria da informação e criptografia.
Durante a Segunda Guerra Mundial, Shannon trabalhou nos Laboratórios Bell para desenvolver sistemas criptográficos, que mais tarde o ajudaram a descobrir métodos de codificação para correção de erros.
Shannon fez uma contribuição fundamental para a teoria dos esquemas probabilísticos, teoria dos jogos, teoria dos autômatos e teoria dos sistemas de controle - áreas da ciência que fazem parte do conceito de cibernética.
Codificação
E joguei moedas e carros que passam não sãosão semelhantes aos números 0 e 1. Para relatar eventos que ocorrem em espaços, você precisa pensar em uma maneira de descrever esses eventos. Essa descrição é chamada de codificação.
As mensagens podem ser codificadas de inúmeras maneiras diferentes. Mas Shannon mostrou que o código mais curto não pode ser menor em bits que a entropia.
É por isso que a entropia de uma mensagem é uma medidainformações na mensagem. Como em todos os casos considerados o número de bits durante a codificação é igual à entropia, isso significa que a codificação foi ótima. Em suma, já não é possível codificar mensagens sobre acontecimentos nos nossos espaços.
Com codificação ideal, você não pode perder oudistorcer um único bit transmitido na mensagem. Se pelo menos um bit for perdido, a informação será distorcida. Mas todos os canais de comunicação reais não proporcionam 100% de confiança de que todos os bits da mensagem chegarão ao destinatário sem distorções.
Для устранения этой проблемы необходимо сделать код не оптимальным, а избыточным. Например, передавать вместе с сообщением его контрольную сумму — специальным образом вычисленное значение, получаемое при преобразовании кода сообщения, и которое можно проверить, пересчитав при получении сообщения. Если переданная контрольная сумма совпадет с вычисленной, вероятность того, что передача прошла без ошибок, будет довольно высока. А если контрольная сумма не совпадет, то необходимо запросить повторную передачу. Примерно так работает сегодня большинство каналов связи, например, при передаче пакетов информации по интернету.
Mensagens de linguagem natural
Considere o espaço para eventos que consistede posts em linguagem natural. Este é um caso especial, mas um dos mais importantes. Os eventos aqui serão os caracteres transmitidos (letras de um alfabeto fixo). Esses caracteres são encontrados na linguagem com probabilidades diferentes.
O símbolo de maior freqüência (ou seja, um queé mais frequentemente encontrado em todos os textos escritos em russo) é um espaço: de mil caracteres, um espaço médio é encontrado 175 vezes. O segundo em freqüência é o símbolo "o" - 90, seguido por outras vogais: "e" (ou "e" - nós não os distinguiremos) - 72, "a" - 62 e i - 62, e só mais adiante a primeira consoante "t" - 53. E o mais raro "f" - este símbolo é encontrado apenas duas vezes por mil caracteres.
Vamos usar o alfabeto de 31 letras do russoidioma (não difere "e" e "e", bem como "ъ" e "ь"). Se todas as letras foram encontradas na linguagem com a mesma probabilidade, então a entropia por símbolo seria H = 5 bits, mas se levarmos em conta as freqüências reais dos símbolos, a entropia será menor: H = 4,35 bits. (Isso é quase duas vezes menor que a codificação tradicional, quando um caractere é transmitido como um byte - 8 bits).
Mas a entropia do personagem na linguagem é ainda menor. A probabilidade de ocorrência do próximo caractere não é completamente predeterminada pela freqüência média do caractere em todos os textos. Qual personagem seguirá depende dos personagens já transferidos. Por exemplo, no russo moderno após o símbolo "ъ" não pode seguir o som do símbolo consoante. Após duas vogais consecutivas "e", a terceira vogal "e" segue extremamente raramente, a menos que na palavra "long-necked". Ou seja, o próximo caractere é até certo ponto predeterminado. Se levarmos em conta tal predeterminação do próximo símbolo, a incerteza (isto é, a informação) do próximo símbolo será ainda menor que 4,35. De acordo com algumas estimativas, o seguinte símbolo em russo é predeterminado pela estrutura da linguagem em mais de 50%, ou seja, com codificação ideal, todas as informações podem ser transmitidas excluindo metade das letras da mensagem.
Outra coisa é que nem toda letra pode ser deletada com segurança. O "o" de alta frequência (e geralmente as vogais), por exemplo, é fácil de eliminar, mas o "f" ou "e" raro é bastante problemático.
Естественный язык, на котором мы общаемся друг с другом, высоко избыточен, а потому надежен, если мы что-то недослышали — нестрашно, информация все равно будет передана.
Mas até Shannon introduzir a medida da informação, não poderíamos entender que a linguagem é redundante e em que medida podemos comprimir as mensagens (e por que os arquivos de texto são tão bem compactados pelo arquivador).
Redundância de linguagem natural
No artigo "Sobre como estamos inserindo textos"(o nome soa exatamente assim!) um fragmento do romance de Ivan Turgenev, "O Ninho Nobre", foi levado e sujeito a alguma transformação: 34% das letras, mas não as aleatórias, foram excluídas do fragmento. As primeiras e últimas letras das palavras foram deixadas, apenas as vogais foram excluídas e não todas. O objetivo não era apenas ser capaz de recuperar todas as informações no texto convertido, mas também garantir que a pessoa que estava lendo este texto não tivesse dificuldades especiais devido a omissões de letras.
Почему сравнительно легко читать этот испорченный текст? В нем действительно содержится необходимая информация для восстановления целых слов. Носитель русского языка располагает определенным набором событий (слов и целых предложений), которые он использует при распознавании. Кроме того, в распоряжении носителя еще и стандартные языковые конструкции, которые помогают ему восстанавливать информацию. Например, "Ela é mais branca do que é" — с высокой вероятностью можно прочесть как "Ela era mais sensível.". Но взятая отдельно фраза "Ela é mais branca", скорее, будет восстановлена как "Ela era mais branca". Поскольку мы в повседневном общении имеем дело с каналами, в которых есть шум и помехи, то довольно хорошо умеем восстанавливать информацию, но только ту, которую мы уже знаем заранее. Например, фраза "Seus demônios não são mais brilhantes que prazeres, html хорошо читается за исключением последнего слова "Divisões" - "emenda". Этого слова нет в современном лексиконе. При быстром чтении слово Spld читается скорее как «слиплись», при медленном — просто ставит в тупик.
Digitalização de sinais
O som, ou vibrações acústicas, é uma onda senoidal. Isso pode ser visto, por exemplo, na tela do editor de som. Para transmitir o som com precisão, você precisa de um número infinito de valores - todo o senoide. Isso é possível com uma conexão analógica. Ele canta - você escuta, o contato não quebra enquanto a música dura.
При цифровой связи по каналу мы можем передать только конечное количество значений. Значит ли это, что звук нельзя передать точно? Оказывается, нет.
Разные звуки — это по-разному модулированная синусоида. Nós transmitimos apenas valores discretos (frequências e amplitudes), mas o próprio senoide não precisa ser transmitido - ele pode ser gerado pelo dispositivo receptor. Он порождает синусоиду, и на нее накладывается модуляция, созданная по значениям, переданным по каналу связи. Существуют точные принципы, какие именно дискретные значения надо передавать, чтобы звук на входе в канал связи совпадал со звуком на выходе, где эти значения накладываются на некоторую стандартную синусоиду (об этом как раз теорема Котельникова).
Teorema de Kotelnikov (na literatura inglesa - teorema de Nyquist-Shannon, teorema de contagem) — фундаментальное утверждение в области цифровой обработки сигналов, связывающее непрерывные и дискретные сигналы и гласящее, что «любую функцию F(t), состоящую из частот от 0 до f1, можно непрерывно передавать с любой точностью при помощи чисел, следующих друг за другом через 1/(2*f1) секунд.
Codificação robusta. Códigos de Hamming
Se você transmitir através de um canal não confiáveltexto codificado de Ivan Turgenev, embora com uma certa quantidade de erros, será um texto completamente significativo. Porém, se precisarmos transferir tudo de forma precisa para um pouco, a tarefa não será resolvida: não sabemos quais bits estão errados, porque o erro é aleatório. Mesmo uma soma de verificação nem sempre é salva.
É por isso que hoje, ao transmitir dados através deas redes não se esforçam tanto pela codificação ideal, na qual a quantidade máxima de informações pode ser inserida em um canal, mas por uma codificação (obviamente excessiva) na qual os erros podem ser restaurados - assim como quando recuperamos palavras em um fragmento de Ivan Turgenev ao ler.
Existem códigos especiais de correção de erros que permitem recuperar informações após uma falha. Um deles é o código de Hamming. Допустим, весь наш язык состоит из трех слов: 111000, 001110, 100011. Эти слова знают и источник сообщения, и приемник. И мы знаем, что в канале связи случаются ошибки, но при передаче одного слова искажается не более одного бита информации.
Suponha que primeiro passemos a palavra 111000. Como resultado de não mais de um erro (os erros que destacamos), ele pode se transformar em uma das seguintes palavras:
1) 111000, 011000, 101000, 110000, 111100, 111010, 111001.
Ao transmitir a palavra 001110, qualquer uma das palavras pode aparecer:
2) 001110, 101110, 011110, 000110, 001010, 001100, 001111.
Finalmente, para 100011, podemos obtê-lo na recepção:
3) 100011, 000011, 110011, 101011, 100111, 100001, 100010.
Observe que todas as três listas não são emparelhadascruzar. Em outras palavras, se alguma palavra da lista 1 aparecer na outra extremidade do canal de comunicação, o destinatário sabe com certeza que a palavra 111000 foi transmitida a ele e se qualquer palavra da lista 2 aparecer a palavra 001110 e da lista 3 a palavra 100011. Nesse caso Eles dizem que nosso código corrigiu um erro.
Исправление произошло за счет двух факторов. Primeiro, o destinatário conhece todo o "dicionário", ou seja, o espaço de eventos do destinatário da mensagem corresponde ao espaço da pessoa que transmitiu a mensagem. Quando o código foi transmitido com apenas um erro, saiu uma palavra que não estava no dicionário.
Em segundo lugar, as palavras no dicionário foram selecionadas de uma maneira especial. Даже при возникновении ошибки получатель не мог перепутать одно слово с другим. Например, если словарь состоит из слов «дочка», «точка», «кочка», и при передаче получалось «вочка», то получатель, зная, что такого слова не бывает, исправить ошибку не смог бы — любое из трех слов может оказаться правильным. Если же в словарь входят «точка», «галка», «ветка» и нам известно, что допускается не больше одной ошибки, то «вочка» это заведомо «точка», а не «галка». В кодах, исправляющих ошибки, слова выбираются именно так, чтобы они были «узнаваемы» даже после ошибки. Разница лишь в том, что в кодовом «алфавите» всего две буквы — ноль и единица.
A redundância dessa codificação é muito grande e o número de palavras que podemos transmitir dessa maneira é relativamente pequeno. Нам ведь надо исключать из словаря любое слово, которое может при ошибке совпасть с целым списком, соответствующим передаваемым словам (например, в словаре не может быть слов «дочка» и «точка»). Но точная передача сообщения настолько важна, что на исследование помехоустойчивых кодов тратятся большие силы.
Sensação
Os conceitos de entropia (ou incerteza eimprevisibilidade) mensagens e redundância (ou predeterminação e previsibilidade) correspondem naturalmente às nossas idéias intuitivas sobre a medida da informação. Quanto mais imprevisível a mensagem (quanto maior a sua entropia, porque é menos provável), mais informações ela carrega. Sensação (por exemplo, uma reunião com um crocodilo em Tverskaya) é um evento raro, sua previsibilidade é muito pequena e, portanto, o custo da informação é alto. Muitas vezes, as informações são chamadas de notícias - mensagens sobre eventos que acabaram de ocorrer, sobre os quais ainda não sabemos nada. Mas se eles nos disserem sobre o incidente uma segunda e terceira vez com aproximadamente as mesmas palavras, a mensagem será redundante, sua imprevisibilidade cairá para zero e nós simplesmente não ouviremos, dispensando o orador com as palavras "eu sei, eu sei". Portanto, a mídia está se esforçando tanto para ser a primeira. Essa correspondência com o senso intuitivo de novidade, que dá origem a notícias realmente inesperadas, desempenhou um papel importante no fato de o artigo de Shannon, que não era destinado ao leitor em geral, ter se tornado uma sensação, captada pela imprensa, que foi aceita como uma chave universal para conhecer a natureza por cientistas de várias especialidades - de linguistas e críticos literários a biólogos.
Но Conceito de informação de Shannon - teoria matemática rigorosa, e sua aplicação fora da teoria da comunicação não é confiável. Mas, na própria teoria da comunicação, ela desempenha um papel central.
Informação semântica
Шеннон, введя понятие энтропии как меры информации, получил возможность работать с информацией — в первую очередь, ее измерять и оценивать такие характеристики, как пропускная способность каналов или оптимальность кодирования. Но главным допущением, которое позволило Шеннону успешно оперировать с информацией, было предположение, что порождение информации — это случайный процесс, который можно успешно описать в терминах теории вероятности. Se o processo não é aleatório, ou seja, obedece às leis (além de nem sempre ser claro, como ocorre na linguagem natural), o raciocínio de Shannon não se aplica a ele. Все, что говорит Шеннон, никак не связано с осмысленностью информации.
Enquanto falamos de caracteres (ou letras do alfabeto),podemos raciocinar em termos de eventos aleatórios, mas assim que chegarmos às palavras do idioma, a situação mudará dramaticamente. A fala é um processo especialmente organizado, e aqui a estrutura da mensagem não é menos importante que os caracteres pelos quais ela é transmitida.
Еще недавно казалось, что мы ничего не можем сделать, чтобы хоть как-то приблизиться к измерению осмысленности текста, но в последние годы ситуация начала меняться. И связано это прежде всего с применением искусственных нейронных сетей к задачам машинного перевода, автоматического реферирования текстов, извлечению информации из текстов, генерированию отчетов на естественном языке. Во всех этих задачах происходит преобразование, кодирование и декодирование осмысленной информации, заключенной в естественном языке. И постепенно складывается представление об информационных потерях при таких преобразованиях, а значит — о мере осмысленной информации. Но на сегодняшний день той четкости и точности, которую имеет шенноновская теория информации, в этих трудных задачах еще нет.