Espacio de eventos al azar
En 1946, el estadístico estadounidense John Tukey propuso el nombre de BIT
Imagina un espacio de eventos aleatorios.que consiste en lanzar una moneda falsa, a ambos lados de la cual es un águila. ¿Cuándo cae un águila? Está claro que siempre. Sabemos esto de antemano, porque nuestro espacio está dispuesto así. La caída de un águila es un evento confiable, es decir, su probabilidad es igual a 1. ¿Daremos mucha información si decimos sobre un águila caída? No La cantidad de información en dicho mensaje, nos considerará igual a 0.
Ahora lancemos la moneda correcta: tiene cara en un lado y cruz en el otro, como debe ser.A cara o cruz vendrán los dos eventos diferentes que componenSi informamos del resultado de un solo lanzamiento, seráNueva información: La cara reportará 0 y la cruz 1.Para proporcionar esta información, solo necesitamos 1 bit.
La incertidumbre ha surgido en nuestro espacio de eventos, y tenemos algo que contar al respecto a aquellos que no lanzan una moneda ellos mismosPero para entender nuestro mensaje correctamente, debe saber exactamente lo que estamos haciendo, lo que queremos decir0 y 1.Nuestros espacios de eventos deben coincidir, y el proceso de decodificación es exclusivo para restaurar el resultado del lanzamiento.Si el espacio de eventos del transmisor y del receptor no coincide o noPosibilidad de decodificación inequívoca del mensaje, la información quedará solo ruido en el canal de comunicación.
Si se lanzan dos monedas de forma independiente y al mismo tiempo, habrá diferentes resultados igualmente probablesPara transmitir la información, necesitaremos 2 bits, y nuestros mensajes serán00, 01, 10 y 11.Hay el doble de información.Si intentamos adivinar el resultado de un lanzamiento de dobles de este tipo, tenemos el doble de probabilidades de cometer un error.
Cuanto mayor sea la incertidumbre de un espacio de eventos, más información contendrá el mensaje de estado del evento.
Vamos a complicar un poco nuestro espacio de eventos, hasta ahora todos los eventos que han sucedido han sido igualmente probables.Pero en los espacios reales, no todos los eventos tienen una probabilidad traumática.Digamos que la probabilidad de que el cuervo que vemos sea negro es cercana a 1.La probabilidad de que el primer transeúnte que encuentres en la calle sea un hombre es de aproximadamente 0,5.Pero es casi increíble encontrarse con un cocodrilo en las calles de Moscú.Intuitivamente, entendemos que el mensaje de un encuentro con un cocodrilo hamucho más valor informativo que sobre el cuervo negro.Cuanto menor es la probabilidad de un evento, más información hay en el mensaje sobre dicho evento.
Que el espacio del evento no sea tan exótico. Nos paramos en la ventana y miramos los carros que pasan. Pasan autos de cuatro colores, lo que debemos informar. Para hacer esto, codificamos los colores: negro - 00, blanco - 01, rojo - 10, azul - 11. Para informar exactamente qué automóvil condujo, solo necesitamos transferir 2 bits de información.
Pero desde hace bastante tiempo mirando los coches,notamos que el color de los autos está distribuido de manera desigual: negro - 50% (cada segundo), blanco - 25% (cada cuarto), rojo y azul - 12.5% (cada octavo) A continuación, puede optimizar la información transmitida.
La mayoría de ellos son coches negros, así que denotemos negro: 0 es el código más corto, y dejemos que el código de todos los demás comience con 1.Del resto, la mitad son blancos a los 10 y los colores restantes comienzan a los 11.Finalmente, denotemos el rojo como 110 y el azul como 111.
Ahora, al pasar información sobre el color del auto, podemos codificarlo más de cerca.
Shannon Entropy
Supongamos que nuestro espacio de eventos consta de n eventos diferentes. Cuando se lanza una moneda con dos caras, hay exactamente un evento de este tipo, cuando se lanza una moneda correcta, 2 cuando se lanzan dos monedaso la observación del automóvil – 4. Cada evento corresponde a la probabilidad de su ocurrencia.Cuando se lanza una moneda con dos caras, solo hay un evento (que salga cara) y su probabilidad es p1 = 1.Cuando lanzas la moneda correcta, hay dos eventos, son igualmente probables, y la probabilidad de cada uno es 0.5: p1 = 0.5, p2 = 0.5.Si lanzas dos monedas correctas, hay cuatro eventos, todos ellos son igualmente probables, y la probabilidad de cada uno es 0,25: p1 = 0,25, p2 = 0,25, p3 = 0,25, p4 = 0,25.Al observar los coches, hay cuatro eventos, y tienen diferentes probabilidades: el negro es 0,5, el blanco es 0,25, el rojo es 0,125, el azul es 0,125: p1 = 0,5, p2 = 0,25, p3 = 0,125, p4 = 0,125.
Esto no es una coincidencia.Shannon eligió la entropía (una medida de incertidumbre en el espacio del evento) para que se cumplieran tres condiciones:
- 1La entropía de un suceso válido con una probabilidad de 1 es 0.
- La entropía de dos eventos independientes es igual a la suma de las entropías de estos eventos.
- La entropía es máxima si todos los eventos son igualmente probables.
Todos estos requisitos son bastante coherentes con nuestras ideas sobre la indeterminación del espacio del evento.Si los eventos son independientes, la incertidumbre de la suma es igual a la suma de las incertidumbres, simplemente se suman (ejemploY, finalmente, si todos los eventos son igualmente probables, entonces el grado de incertidumbre del sistema es máximo.Al igual que en el caso de lanzar dos monedas, los cuatro eventos son igualmente probables y la entropía es 2, que es mayor que en el caso de los coches, donde también hay cuatro eventos, pero tienenEn este caso, la entropía es 1,75.
La cantidad H juega un papel central en la teoría de la información como medida de información, elección e incertidumbre.
Claude Shannon
Claude Elwood Shannon- ingeniero, criptoanalista y estadounidensematemático. Considerado el "padre de la era de la información". Fundador de la teoría de la información, que ha encontrado aplicación en los modernos sistemas de comunicación de alta tecnología. Proporcionó conceptos e ideas fundamentales y sus formulaciones matemáticas que actualmente forman la base de las tecnologías de comunicación modernas.
En 1948, propuso utilizar la palabra "bit".Para indicar la unidad de información más pequeña. También demostró que la entropía introducida por él es equivalente a la incertidumbre de la información en el mensaje transmitido. Los artículos de Shannon "Teoría matemática de la comunicación" y "Teoría de la comunicación en sistemas secretos" se consideran fundamentales para la teoría de la información y la criptografía.
Durante la Segunda Guerra Mundial, Shannon trabajó en los Laboratorios Bell para desarrollar sistemas criptográficos, lo que más tarde le ayudó a descubrir métodos de codificación para corregir errores.
Shannon hizo una contribución clave a la teoría de esquemas probabilísticos, teoría de juegos, teoría de autómatas y teoría de sistemas de control, áreas de la ciencia que forman parte del concepto de la cibernética.
Codificación
Y las monedas arrojadas, y los coches que pasan no son.son similares a los números 0 y 1. Para informar eventos que ocurren en espacios, debe pensar en una manera de describir estos eventos. Esta descripción se llama codificación.
Los mensajes se pueden codificar de infinitas formas diferentes. Pero Shannon demostró que el código más corto no puede ser más pequeño en bits que la entropía.
Por eso la entropía de un mensaje es una medida.información en el mensaje. Dado que en todos los casos considerados el número de bits durante la codificación es igual a la entropía, esto significa que la codificación fue óptima. En definitiva, ya no es posible codificar mensajes sobre acontecimientos en nuestros espacios.
Con una codificación óptima, no se puede perder odistorsionar un solo bit transmitido en el mensaje. Si se pierde aunque sea un bit, la información se distorsionará. Pero no todos los canales de comunicación reales ofrecen una confianza absoluta en que todos los fragmentos del mensaje lleguen al destinatario sin distorsiones.
Para solucionar este problema es necesario hacerel código no es óptimo, pero sí redundante. Por ejemplo, transmita junto con el mensaje su suma de verificación, un valor especialmente calculado que se obtiene al convertir el código del mensaje y que se puede verificar recalculando al recibir el mensaje. Si la suma de comprobación transmitida coincide con la calculada, la probabilidad de que la transmisión se haya realizado sin errores será bastante alta. Y si la suma de verificación no coincide, entonces se debe solicitar una retransmisión. Así es como funcionan hoy en día la mayoría de los canales de comunicación, por ejemplo, cuando se transmiten paquetes de información a través de Internet.
Mensajes en lenguaje natural
Considere el espacio del evento que consisteDe publicaciones en lenguaje natural. Este es un caso especial, pero uno de los más importantes. Los eventos aquí serán transmitidos caracteres (letras de un alfabeto fijo). Estos personajes se encuentran en el lenguaje con diferentes probabilidades.
El símbolo de mayor frecuencia (es decir, uno quese encuentra con más frecuencia en todos los textos escritos en ruso) es un espacio: de mil caracteres, un espacio promedio se encuentra 175 veces. El segundo en frecuencia es el símbolo "o" - 90, seguido de otras vocales: "e" (o "e" - no las distinguiremos) - 72, "a" - 62 e i - 62, y solo más la primera consonante "t" - 53. Y la más rara "f" - este símbolo se encuentra solo dos veces por cada mil caracteres.
Utilizaremos el alfabeto de 31 letras del ruso.idioma (no difiere "e" y "e", así como "ъ" y "ь"). Si todas las letras se encontraran en el idioma con la misma probabilidad, entonces la entropía por símbolo sería H = 5 bits, pero si tenemos en cuenta las frecuencias reales de los símbolos, la entropía será menor: H = 4.35 bits. (Esto es casi dos veces menos que con la codificación tradicional, cuando un carácter se transmite como un byte - 8 bits).
Pero la entropía del personaje en el lenguaje es aún menor. La probabilidad de ocurrencia del siguiente carácter no está completamente predeterminada por la frecuencia promedio del carácter en todos los textos. Qué personaje seguirá depende de los personajes ya transferidos. Por ejemplo, en ruso moderno después del símbolo "ъ" no puede seguir el sonido del símbolo de la consonante. Después de dos vocales consecutivas "e", la tercera vocal "e" sigue extremadamente rara vez, a menos que en la palabra "cuello largo". Es decir, el siguiente personaje está en cierta medida predeterminado. Si tomamos en cuenta la predeterminación del siguiente símbolo, la incertidumbre (es decir, la información) del siguiente símbolo será incluso menor que 4.35. Según algunas estimaciones, el siguiente símbolo en ruso está predeterminado por la estructura del idioma en más del 50%, es decir, con una codificación óptima, toda la información se puede transmitir al eliminar la mitad de las letras del mensaje.
Otra cosa es que no todas las letras se pueden eliminar de forma segura. La "o" de alta frecuencia (y generalmente las vocales), por ejemplo, es fácil de tachar, pero la "f" o "e" rara es bastante problemática.
El lenguaje natural en el que nos comunicamos entre nosotros es altamente redundante y, por lo tanto, confiable; si escuchamos mal algo, está bien, la información aún se transmitirá.
Pero hasta que Shannon introdujo la medida de la información, no pudimos entender que el lenguaje es redundante y en qué medida podemos comprimir los mensajes (y por qué los archivos de texto están tan bien comprimidos por el archivador).
Redundancia del lenguaje natural
En el artículo "Acerca de cómo vorpsimanie tektkt"(¡el nombre suena exactamente así!) se tomó un fragmento de la novela Noble Nest de Ivan Turgenev y se lo sometió a alguna transformación: el 34% de las letras, pero no las aleatorias, se eliminaron del fragmento. Se dejaron la primera y la última letras de las palabras, solo se eliminaron las vocales y no todas. El objetivo no era solo tener la oportunidad de recuperar toda la información sobre el texto convertido, sino también garantizar que la persona que lee este texto no experimentara ninguna dificultad en particular debido a las letras faltantes.
¿Por qué es relativamente fácil leer esto corrupto?¿texto? De hecho, contiene la información necesaria para reconstruir palabras enteras. Un hablante nativo de ruso tiene un determinado conjunto de eventos (palabras y oraciones completas) que utiliza en el reconocimiento. Además, el hablante también tiene a su disposición estructuras lingüísticas estándar que le ayudan a recuperar información. Por ejemplo,"Ella es Blae Blee"- con una alta probabilidad se puede leer como"Ella era más sensible".. Pero tomado por separado"Ella es más bla", más bien, será restaurado como"Ella era más blanca". Dado que en la comunicación diaria tratamoscon canales en los que hay ruido e interferencias somos bastante buenos recuperando información, pero sólo la que ya conocemos de antemano. Por ejemplo, la frase"Sus rasgos no son nada agradables, htya nmngo rspkhli y splash"se lee bien excepto por la última palabra"Splash" - "rallied". Esta palabra no está en el léxico moderno. Al leer una palabra rápidamente"Splash"se lee más como “pegados”; cuando es lento, simplemente desconcierta.
Digitalización de señales
El sonido, o las oscilaciones acústicas, es una sinusoide. Esto se puede ver, por ejemplo, en la pantalla del editor de sonido. Para transmitir con precisión el sonido, necesitará un número infinito de valores: la onda sinusoidal completa. Esto es posible con una conexión analógica. Él canta: tú escuchas, el contacto no se interrumpe mientras dura la canción.
En la comunicación digital a través de un canal, solo podemos transmitir un número finito de valores. ¿Significa esto que el sonido no se puede reproducir con precisión? Resulta que no.
Los diferentes sonidos son una onda sinusoidal modulada de manera diferente.Solo transmitimos valores discretos (frecuencias y amplitudes), y la propia onda sinusoidal no necesita ser transmitida, el dispositivo receptor puede generarla.Genera una sinusoide y se superpone a ella.Modulación creada a partir de valores transmitidos a través de un canal de comunicación. Existen principios exactos según los cuales se deben transmitir valores discretos para que el sonido en la entrada al canal de comunicación coincida con el sonido en la salida, donde estos valores se superponen a alguna sinusoide estándar (esto es lo que es el teorema de Kotelnikov acerca de).
Teorema de Kotelnikov (en la literatura en inglés - el Nyquist - Teorema de Shannon, el teorema de la lectura)- una declaración fundamental en el campo de lo digitalprocesamiento de señales, conectando señales continuas y discretas y afirmando que “cualquier función F(t), que consta de frecuencias de 0 a f1, puede transmitirse continuamente con cualquier precisión utilizando números consecutivos durante 1/(2*f1) segundos
Codificación antiinterferente. Códigos de Hamming
Si está en un canal poco fiable para transmitirEl texto codificado de Ivan Turgenev, aunque con algunos errores, dará como resultado un texto bastante significativo. Pero si necesitamos transferir todo a un poco, la tarea no se resolverá: no sabemos qué bits son incorrectos, porque el error es aleatorio. Incluso la suma de comprobación no siempre se guarda.
Es por eso que hoy a la hora de transmitir datos enLas redes no tienden tanto a la codificación óptima, en la que se puede ingresar la cantidad máxima de información al canal, sino a dicha codificación (obviamente redundante) en la que se pueden recuperar los errores, como cuando leemos las palabras en el fragmento de Ivan Turgenev.
Hay códigos especiales de corrección de errores que le permiten recuperar información después de una falla. Uno de ellos es el código de Hamming.Digamos que todo nuestro idioma consta de tres palabras:111000, 001110, 100011. Tanto la fuente del mensaje como el receptor conocen estas palabras. Y sabemos que en un canal de comunicación se producen errores, pero al transmitir una palabra no se distorsiona más que un bit de información.
Supongamos que primero pasamos la palabra 111000. Como resultado, no más de un error (hemos identificado el error) se puede convertir en una de las palabras:
1) 111000,011,000, 101000, 110000, 111100, 111010, 111001.
Al transmitir la palabra 001110, se puede obtener cualquiera de las palabras:
2) 001110,101110, 011110, 000110, 001010, 001100, 001111.
Finalmente, para 100011 podemos llegar a la recepción:
3) 100011,000011, 110011, 101011, 100111, 100001, 100010.
Tenga en cuenta que las tres listas no son pares.intersectarse En otras palabras, si en el otro extremo del canal de comunicación aparece alguna palabra de la lista 1, el destinatario sabe con seguridad que se le transmitió la palabra 111000, y si aparece alguna palabra de la lista 2, aparece la palabra 001110, y de la lista 3, la palabra 100011. Dicen que nuestro código solucionó un error.
La corrección se produjo debido a dos factores.Primero, el destinatario conoce todo el "diccionario"., es decir, el espacio de eventos del destinatario del mensaje coincide con el espacio de la persona que transmitió el mensaje. Cuando el código se transmitió con un solo error, salió una palabra que no estaba en el diccionario.
En segundo lugar, las palabras en el diccionario fueron elegidas de una manera especial.Incluso si ocurriera un error, el destinatario no podríaconfundir una palabra con otra. Por ejemplo, si el diccionario consta de las palabras "hija", "punto", "golpe" y durante la transmisión el resultado fue "vochka", entonces el destinatario, sabiendo que esa palabra no existe, no podría corrija el error: cualquiera de las tres palabras puede resultar correcta. Si el diccionario incluye "punto", "daw", "branch" y sabemos que no se permite más de un error, entonces "vochka" es definitivamente un "punto" y no una "daw". En los códigos de corrección de errores, las palabras se eligen precisamente para que sean “reconocibles” incluso después de un error. La única diferencia es que el código "alfabeto" tiene sólo dos letras: cero y uno.
La redundancia de dicha codificación es muy grande, y el número de palabras que podemos transmitir es relativamente pequeño.Necesitamos excluir cualquier palabra del diccionario,que, en caso de error, puede coincidir con toda la lista correspondiente a las palabras transmitidas (por ejemplo, las palabras “hija” y “punto” no pueden estar en el diccionario). Pero la transmisión precisa de mensajes es tan importante que se dedican grandes esfuerzos a la investigación de códigos resistentes a errores.
Sensación
Conceptos de entropía (o incertidumbre yLa imprevisibilidad del mensaje y la redundancia (o la predeterminación y la previsibilidad) se corresponden muy naturalmente con nuestras ideas intuitivas acerca de la medida de la información. Cuanto más impredecible sea el mensaje (cuanto mayor sea su entropía, porque hay menos probabilidad), más información llevará. Una sensación (por ejemplo, una reunión con un cocodrilo en Tverskaya) es un evento raro, su previsibilidad es muy baja y, por lo tanto, el valor de la información es alto. A menudo, la información se denomina noticias: informes de eventos que acaban de ocurrir, sobre los cuales todavía no sabemos nada. Pero si nos dicen la segunda y la tercera vez sobre las mismas palabras, la redundancia del mensaje será excelente, su imprevisibilidad se reducirá a cero y simplemente no lo escucharemos, alejándonos del orador con las palabras "Lo sé, lo sé". Por lo tanto, los medios de comunicación están tratando de ser los primeros. Esta correspondencia con el sentido intuitivo de la novedad, que da lugar a noticias realmente inesperadas, jugó un papel importante en el hecho de que el artículo de Shannon, que no estaba destinado al lector general, se convirtió en una sensación, que la prensa percibió como una clave universal para el conocimiento de la naturaleza. - Desde lingüistas y críticos literarios hasta biólogos.
PeroConcepto de información de Shannon - teoría matemática rigurosay su aplicación fuera de la teoría de la comunicación es muy poco confiable. Pero en la teoría de la comunicación en sí, desempeña un papel central.
Informacion semantica
Shannon, introduciendo el concepto de entropía como medida.información, tuvo la oportunidad de trabajar con información, en primer lugar, medirla y evaluar características como la capacidad del canal o la codificación óptima. Pero el principal supuesto que permitió a Shannon operar exitosamente con información fue el supuesto de que la generación de información es un proceso aleatorio que puede describirse exitosamente en términos de teoría de probabilidad.Si el proceso no es aleatorio, es decir, obedece las leyes (además, no siempre es claro, como ocurre en el lenguaje natural), entonces el razonamiento de Shannon no es aplicable a él.Nada de lo que dice Shannon tiene que ver con que la información sea significativa.
Mientras hablamos de personajes (o letras del abecedario),bien podemos argumentar en términos de eventos aleatorios, pero tan pronto como lleguemos a las palabras del idioma, la situación cambiará dramáticamente. El habla es un proceso que está especialmente organizado, y aquí la estructura del mensaje no es menos importante que los caracteres por los que se transmite.
Recientemente parecía que no podíamos hacer nada.Se ha hecho mucho para acercarse al menos de alguna manera a medir el significado del texto, pero en los últimos años la situación ha comenzado a cambiar. Y esto se debe principalmente a la aplicación de redes neuronales artificiales a las tareas de traducción automática, resumen automático de textos, extracción de información de textos y generación de informes en lenguaje natural. Todas estas tareas implican transformar, codificar y decodificar información significativa contenida en el lenguaje natural. Y poco a poco se va formando una idea de la pérdida de información durante tales transformaciones y, por tanto, de la magnitud de la información significativa. Pero hoy en día, la claridad y precisión que tiene la teoría de la información de Shannon aún no están disponibles en estos difíciles problemas.