Fixémolo!
"O propósito deste curso é prepararte para o teu futuro técnico".
Ola, Habr. Lembra o artigo incrible (+219, 2588 marcadores, 429k lecturas)?
Entón Hamming (si, si, autocontrol e autocorrección ) hai un todo , escrito a partir das súas conferencias. Nós traducímolo, porque o home di o que pensa.
Este é un libro non só sobre TI, é un libro sobre o estilo de pensamento de persoas incriblemente xeniais. “Non é só un impulso ao pensamento positivo; describe as condicións que aumentan as posibilidades de facer un gran traballo”.
Grazas a Andrey Pakhomov pola tradución.
A teoría da información foi desenvolvida por C. E. Shannon a finais da década de 1940. A dirección de Bell Labs insistiu en que lle chamaba "Teoría da comunicación" porque... este é un nome moito máis preciso. Por razóns obvias, o nome "Teoría da información" ten un impacto moito maior no público, polo que Shannon o escolleu, e é o nome que coñecemos ata hoxe. O propio nome suxire que a teoría trata sobre a información, o que a fai importante a medida que avanzamos máis na era da información. Neste capítulo, tocarei varias conclusións principais desta teoría, proporcionarei evidencias non estritas, senón máis ben intuitivas dalgunhas disposicións individuais desta teoría, para que comprenda o que é realmente a "Teoría da información", onde pode aplicala. e onde non.
En primeiro lugar, que é "información"? Shannon equipara a información coa incerteza. Escolleu o logaritmo negativo da probabilidade dun evento como medida cuantitativa da información que recibe cando se produce un evento con probabilidade p. Por exemplo, se che digo que o tempo en Los Ángeles é nébooso, entón p está preto de 1, o que realmente non nos dá moita información. Pero se digo que chove en Monterrei en xuño, haberá incerteza na mensaxe e conterá máis información. Un evento fiable non contén ningunha información, xa que o rexistro 1 = 0.
Vexamos isto con máis detalle. Shannon cría que a medida cuantitativa da información debería ser unha función continua da probabilidade dun evento p, e para eventos independentes debería ser aditiva: a cantidade de información obtida como resultado da ocorrencia de dous eventos independentes debería ser igual á cantidade de información obtida como resultado da ocorrencia dun suceso conxunto. Por exemplo, o resultado dunha tirada de dados e dunha moeda adoitan tratarse como eventos independentes. Imos traducir o anterior á linguaxe das matemáticas. Se I (p) é a cantidade de información contida nun suceso con probabilidade p, entón para un suceso conxunto que consiste en dous sucesos independentes x con probabilidade p1 e y con probabilidade p2 obtemos
(x e y son eventos independentes)
Esta é a ecuación funcional de Cauchy, verdadeira para todos os p1 e p2. Para resolver esta ecuación funcional, supoña que
p1 = p2 = p,
isto dá
Se p1 = p2 e p2 = p entón
etc. Ampliando este proceso usando o método estándar para exponenciais, para todos os números racionais m/n é verdade o seguinte
Da continuidade asumida da medida de información, despréndese que a función logarítmica é a única solución continua da ecuación funcional de Cauchy.
En teoría da información, é común tomar a base do logaritmo como 2, polo que unha opción binaria contén exactamente 1 bit de información. Polo tanto, a información mídese mediante a fórmula
Fagamos unha pausa e entendamos o que pasou arriba. En primeiro lugar, non definimos o concepto de "información", simplemente definimos a fórmula para a súa medida cuantitativa.
En segundo lugar, esta medida está suxeita a incerteza, e aínda que é razoablemente adecuada para máquinas —por exemplo, sistemas de telefonía, radio, televisión, ordenadores, etc.— non reflicte as actitudes humanas normais cara á información.
En terceiro lugar, esta é unha medida relativa, depende do estado actual dos teus coñecementos. Se observas un fluxo de "números aleatorios" dun xerador de números aleatorios, asume que cada número seguinte é incerto, pero se coñeces a fórmula para calcular "números aleatorios", coñecerase o seguinte número e, polo tanto, non contén información.
Entón, a definición de información de Shannon é apropiada para máquinas en moitos casos, pero non parece encaixar na comprensión humana da palabra. É por iso que a "teoría da información" debería chamarse "teoría da comunicación". Porén, é demasiado tarde para cambiar as definicións (que deron á teoría a súa popularidade inicial, e que aínda fan pensar que esta teoría trata sobre a “información”), polo que hai que convivir con elas, pero ao mesmo tempo hai que convivir con elas. comprender claramente ata que punto está a definición de información de Shannon do seu significado habitual. A información de Shannon trata sobre algo completamente diferente, é dicir, a incerteza.
Aquí tes algo no que pensar cando propoñas algunha terminoloxía. Como concorda unha definición proposta, como a definición de información de Shannon, coa túa idea orixinal e en que medida é diferente? Case non hai termo que reflicta exactamente a túa visión previa dun concepto, pero, en definitiva, é a terminoloxía empregada a que reflicte o significado do concepto, polo que formalizar algo mediante definicións claras sempre introduce un pouco de ruído.
Considere un sistema cuxo alfabeto consta de símbolos q con probabilidades pi. Neste caso cantidade media de información no sistema (o seu valor esperado) é igual a:
Isto chámase entropía do sistema con distribución de probabilidade {pi}. Usamos o termo "entropía" porque a mesma forma matemática aparece na termodinámica e na mecánica estatística. É por iso que o termo "entropía" crea unha certa aura de importancia ao seu redor, que finalmente non se xustifica. A mesma forma matemática de notación non implica a mesma interpretación dos símbolos!
A entropía da distribución de probabilidade xoga un papel importante na teoría de codificación. A desigualdade de Gibbs para dúas distribucións de probabilidade diferentes pi e qi é unha das consecuencias importantes desta teoría. Así que debemos demostralo
A demostración baséase nunha gráfica obvia, Fig. 13.Eu, que demostra que
e a igualdade só se consegue cando x = 1. Apliquemos a desigualdade a cada termo da suma do lado esquerdo:
Se o alfabeto dun sistema de comunicación consta de q símbolos, tomando a probabilidade de transmisión de cada símbolo qi = 1/q e substituíndo q, obtemos a partir da desigualdade de Gibbs
Figura 13.I
Isto significa que se a probabilidade de transmitir todos os símbolos q é a mesma e igual a - 1 / q, entón a entropía máxima é igual a ln q, se non, a desigualdade vale.
No caso dun código decodificable unicamente, temos a desigualdade de Kraft
Agora se definimos pseudoprobabilidades
onde por suposto = 1, que se segue da desigualdade de Gibbs,
e aplicamos un pouco de álxebra (lembremos que K ≤ 1, polo que podemos deixar o termo logarítmico, e quizais reforzar a desigualdade máis tarde), obtemos
onde L é a lonxitude media do código.
Así, a entropía é o límite mínimo para calquera código carácter por símbolo cunha lonxitude media de palabras de código L. Este é o teorema de Shannon para unha canle sen interferencias.
Considere agora o teorema principal sobre as limitacións dos sistemas de comunicación nos que a información se transmite como un fluxo de bits independentes e está presente ruído. Enténdese que a probabilidade de transmisión correcta dun bit é P > 1/2, e a probabilidade de que o valor do bit se inverta durante a transmisión (se produza un erro) é igual a Q = 1 - P. Por comodidade, supoña que os erros son independentes e que a probabilidade dun erro é a mesma para cada bit enviado, é dicir, hai "ruído branco" na canle de comunicación.
A forma en que temos un longo fluxo de n bits codificados nunha mensaxe é a extensión n-dimensional do código dun bit. Determinaremos o valor de n máis adiante. Considere unha mensaxe formada por n bits como un punto no espazo ndimensional. Dado que temos un espazo n-dimensional -e por simplicidade asumiremos que cada mensaxe ten a mesma probabilidade de ocorrer- hai M mensaxes posibles (M tamén se definirá máis adiante), polo tanto, a probabilidade de calquera mensaxe enviada é
(remitente)
Anexo 13.II
A continuación, considere a idea da capacidade da canle. Sen entrar en detalles, a capacidade da canle defínese como a cantidade máxima de información que se pode transmitir de forma fiable por unha canle de comunicación, tendo en conta o uso da codificación máis eficiente. Non hai argumento de que a través dunha canle de comunicación se poida transmitir máis información que a súa capacidade. Isto pódese probar para unha canle simétrica binaria (que usamos no noso caso). A capacidade da canle, ao enviar bits, especifícase como
onde, como antes, P é a probabilidade de non erro en ningún bit enviado. Cando se envían n bits independentes, a capacidade da canle vén dada por
Se estamos preto da capacidade da canle, entón debemos enviar case esta cantidade de información para cada un dos símbolos ai, i = 1, ..., M. Considerando que a probabilidade de aparición de cada símbolo ai é 1 / M, obtemos
cando enviamos algunha das M mensaxes igualmente probables ai, temos
Cando se envían n bits, esperamos que se produzan nQ erros. Na práctica, para unha mensaxe formada por n bits, teremos aproximadamente nQ erros na mensaxe recibida. Para n grande, variación relativa (variación = ancho de distribución, )
a distribución do número de erros será cada vez máis estreita a medida que aumente n.
Entón, dende o lado do transmisor, tomo a mensaxe ai para enviar e debuxo unha esfera ao seu redor cun radio
que é lixeiramente maior nunha cantidade igual a e2 que o número esperado de erros Q, (Figura 13.II). Se n é o suficientemente grande, entón hai unha probabilidade arbitrariamente pequena de que apareza un punto de mensaxe bj no lado do receptor que se estenda máis aló desta esfera. Esbocemos a situación tal e como eu a vexo dende o punto de vista do transmisor: temos calquera radio desde a mensaxe transmitida ai ata a mensaxe recibida bj cunha probabilidade de erro igual (ou case igual) á distribución normal, chegando a un máximo. en nQ. Para calquera e2 dado, hai un n tan grande que a probabilidade de que o punto resultante bj estea fóra da miña esfera é tan pequena como queiras.
Agora vexamos a mesma situación dende o teu lado (Fig. 13.III). No lado do receptor hai unha esfera S(r) do mesmo raio r arredor do punto recibido bj no espazo n-dimensional, de tal xeito que se a mensaxe recibida bj está dentro da miña esfera, entón a mensaxe ai enviada por min está dentro da túa esfera. esfera.
Como pode ocorrer un erro? O erro pode ocorrer nos casos descritos na seguinte táboa:
Figura 13.III
Aquí vemos que se na esfera construída arredor do punto recibido hai polo menos un punto máis correspondente a unha posible mensaxe enviada sen codificar, entón produciuse un erro durante a transmisión, xa que non se pode determinar cal destas mensaxes foi transmitida. A mensaxe enviada está libre de erros só se o punto que lle corresponde está na esfera e non hai outros puntos posibles no código dado que estean na mesma esfera.
Temos unha ecuación matemática para a probabilidade de erro Pe se se enviou a mensaxe ai
Podemos descartar o primeiro factor no segundo termo, tomándoo como 1. Así obtemos a desigualdade
Obviamente,
polo tanto
volve aplicar ao último termo da dereita
Tomando n o suficientemente grande, o primeiro termo pódese tomar tan pequeno como se desexe, digamos menos que algún número d. Polo tanto temos
Agora vexamos como podemos construír un código de substitución sinxelo para codificar mensaxes M formadas por n bits. Non tendo idea de como construír exactamente un código (os códigos de corrección de erros aínda non foran inventados), Shannon escolleu a codificación aleatoria. Lanza unha moeda por cada un dos n bits da mensaxe e repite o proceso para as mensaxes M. En total, hai que facer lanzamentos de moedas nM, polo que é posible
dicionarios de código que teñen a mesma probabilidade ½ nM. Por suposto, o proceso aleatorio de creación dun libro de códigos significa que hai unha posibilidade de duplicados, así como puntos de código que estarán preto uns dos outros e, polo tanto, serán unha fonte de erros probables. Hai que demostrar que se isto non ocorre cunha probabilidade maior que calquera pequeno nivel de erro elixido, entón o n dado é o suficientemente grande.
O punto crucial é que Shannon fixo unha media de todos os libros de códigos posibles para atopar o erro medio. Usaremos o símbolo Av[.] para indicar o valor medio sobre o conxunto de todos os posibles libros de códigos aleatorios. A media sobre unha constante d, por suposto, dá unha constante, xa que para promediar cada termo é o mesmo que todos os outros termos da suma,
que se pode aumentar (M–1 vai a M)
Para calquera mensaxe dada, ao facer a media en todos os libros de códigos, a codificación percorre todos os valores posibles, polo que a probabilidade media de que un punto estea nunha esfera é a relación entre o volume da esfera e o volume total do espazo. O volume da esfera é
onde s=Q+e2 <1/2 e ns debe ser un número enteiro.
O último termo da dereita é o maior desta suma. Primeiro, imos estimar o seu valor usando a fórmula de Stirling para factoriais. Despois observaremos o coeficiente decrecente do termo que ten diante, observamos que este coeficiente aumenta a medida que nos movemos cara á esquerda, e así podemos: (1) restrinxir o valor da suma á suma da progresión xeométrica con este coeficiente inicial, (2) expandir a progresión xeométrica de ns termos a un número infinito de termos, (3) calcular a suma dunha progresión xeométrica infinita (álxebra estándar, nada significativo) e finalmente obter o valor límite (para un número suficientemente grande). n):
Observe como apareceu a entropía H(s) na identidade binomial. Nótese que a expansión da serie de Taylor H(s)=H(Q+e2) dá unha estimación obtida tendo en conta só a primeira derivada e ignorando todas as demais. Agora imos xuntar a expresión final:
onde
Todo o que temos que facer é escoller e2 tal que e3 < e1, e entón o último termo será arbitrariamente pequeno, sempre que n sexa o suficientemente grande. En consecuencia, o erro PE medio pódese obter tan pequeno como se desexe coa capacidade da canle arbitrariamente próxima a C.
Se a media de todos os códigos ten un erro suficientemente pequeno, entón polo menos un código debe ser adecuado, polo que hai polo menos un sistema de codificación adecuado. Este é un resultado importante obtido por Shannon: "Teorema de Shannon para unha canle ruidosa", aínda que hai que ter en conta que o demostrou para un caso moito máis xeral que para a canle binaria simétrica simple que usei. Para o caso xeral, os cálculos matemáticos son moito máis complicados, pero as ideas non son tan diferentes, polo que moitas veces, usando o exemplo dun caso particular, pode revelar o verdadeiro significado do teorema.
Critiquemos o resultado. Repetimos varias veces: "Para n suficientemente grande". Pero canto é de grande n? Moi, moi grande se realmente queres estar preto da capacidade da canle e estar seguro da transferencia de datos correcta. Tan grande, de feito, que terás que esperar moito tempo para acumular unha mensaxe de bits suficientes para codificala máis tarde. Neste caso, o tamaño do dicionario de código aleatorio será simplemente enorme (a fin de contas, un dicionario deste tipo non se pode representar nunha forma máis curta que unha lista completa de todos os bits Mn, a pesar de que n e M son moi grandes)!
Os códigos de corrección de erros evitan agardar por unha mensaxe moi longa e despois codificala e decodificala a través de libros de códigos moi grandes porque evitan os propios libros de códigos e usan o cálculo ordinario. En teoría simple, estes códigos tenden a perder a capacidade de achegarse á capacidade da canle e aínda manteñen unha baixa taxa de erros, pero cando o código corrixe un gran número de erros, funcionan ben. Noutras palabras, se asigna algunha capacidade de canle á corrección de erros, entón debes usar a capacidade de corrección de erros a maior parte do tempo, é dicir, hai que corrixir un gran número de erros en cada mensaxe enviada, se non, desperdiciarás esta capacidade.
Ao mesmo tempo, o teorema demostrado anteriormente aínda non carece de sentido! Mostra que os sistemas de transmisión eficientes deben usar esquemas de codificación intelixentes para cadeas de bits moi longas. Un exemplo son os satélites que voaron máis aló dos planetas exteriores; A medida que se afastan da Terra e do Sol, vense obrigados a corrixir cada vez máis erros no bloque de datos: algúns satélites utilizan paneis solares, que proporcionan uns 5 W, outros utilizan fontes de enerxía nuclear, que proporcionan aproximadamente a mesma potencia. A baixa potencia da fonte de alimentación, o pequeno tamaño das antenas transmisoras e o tamaño limitado das antenas receptoras na Terra, a enorme distancia que debe percorrer o sinal - todo isto require o uso de códigos cun alto nivel de corrección de erros para construír un sistema de comunicación eficaz.
Volvamos ao espazo n-dimensional que usamos na demostración anterior. Ao discutilo, demostramos que case todo o volume da esfera está concentrado preto da superficie exterior; polo tanto, é case seguro que o sinal enviado estará situado preto da superficie da esfera construída arredor do sinal recibido, mesmo cun pequeno radio de tal esfera. Polo tanto, non é de estrañar que o sinal recibido, despois de corrixir un número arbitrariamente grande de erros, nQ, resulte estar arbitrariamente próximo a un sinal sen erros. A capacidade de enlace que comentamos anteriormente é a clave para comprender este fenómeno. Teña en conta que as esferas similares construídas para corrixir erros códigos Hamming non se solapan entre si. O gran número de dimensións case ortogonais no espazo n-dimensional mostra por que podemos encaixar M esferas no espazo con pouca superposición. Se permitimos unha superposición pequena e arbitrariamente pequena, que só pode provocar un pequeno número de erros durante a decodificación, podemos obter unha colocación densa de esferas no espazo. Hamming garantiu un certo nivel de corrección de erros, Shannon - unha baixa probabilidade de erro, pero ao mesmo tempo mantendo o rendemento real de forma arbitraria preto da capacidade da canle de comunicación, o que os códigos Hamming non poden facer.
A teoría da información non nos indica como deseñar un sistema eficiente, pero si indica o camiño cara a sistemas de comunicación eficientes. É unha ferramenta valiosa para construír sistemas de comunicación de máquina a máquina, pero, como se indicou anteriormente, ten pouca relevancia para a forma en que os humanos se comunican entre si. Simplemente descoñécese ata que punto a herdanza biolóxica é como os sistemas técnicos de comunicación, polo que actualmente non está claro como se aplica a teoría da información aos xenes. Non nos queda máis remedio que tentalo, e se o éxito nos mostra a natureza de máquina deste fenómeno, entón o fracaso apuntará a outros aspectos significativos da natureza da información.
Non nos divaguemos demasiado. Vimos que todas as definicións orixinais, en maior ou menor medida, deben expresar a esencia das nosas crenzas orixinais, pero caracterízanse por certo grao de distorsión e, polo tanto, non son aplicables. Tradicionalmente acéptase que, en definitiva, a definición que utilizamos define realmente a esencia; pero, isto só nos indica como procesar as cousas e de ningún xeito nos transmite ningún significado. O enfoque postulacional, tan favorecido nos círculos matemáticos, deixa moito que desexar na práctica.
Agora veremos un exemplo de probas de coeficiente intelectual onde a definición é tan circular como che guste e, como resultado, enganosa. Créase unha proba que se supón que mide a intelixencia. Despois revísase para facelo o máis coherente posible, e despois publícase e, nun método sinxelo, calibrase para que a “intelixencia” medida resulte estar distribuída normalmente (nunha curva de calibración, claro). Todas as definicións deben ser revisadas de novo, non só cando se propoñen por primeira vez, senón tamén moito máis tarde, cando se utilicen nas conclusións extraídas. En que medida os límites definicionais son axeitados para o problema que se está a resolver? Con que frecuencia se aplican definicións que se dan nun mesmo escenario en contextos moi diferentes? Isto ocorre con bastante frecuencia! Nas humanidades, que inevitablemente atoparás na túa vida, isto ocorre con máis frecuencia.
Así, unha das finalidades desta presentación da teoría da información, ademais de demostrar a súa utilidade, era advertirche deste perigo, ou mostrarche exactamente como utilizala para obter o resultado desexado. Hai tempo que se observa que as definicións iniciais determinan o que se atopa ao final, en moita maior medida do que parece. As definicións iniciais requírenche moita atención, non só ante calquera situación nova, senón tamén en áreas coas que levas traballando dende hai tempo. Isto permitirá comprender ata que punto os resultados obtidos son unha tautoloxía e non algo útil.
A famosa historia de Eddington conta sobre persoas que pescaban no mar cunha rede. Despois de estudar o tamaño dos peixes que capturaron, determinaron o tamaño mínimo de peixe que se atopa no mar! A súa conclusión foi impulsada polo instrumento empregado, non pola realidade.
Continuar ...
Quen queira axudar coa tradución, maquetación e publicación do libro: escriba nunha mensaxe persoal ou correo electrónico [protexido por correo electrónico]
Por certo, tamén lanzamos a tradución doutro libro xenial: )
Buscamos especialmente aqueles que axudarán a traducir . (transferencia durante 10 minutos, xa se tomaron os 20 primeiros)
Contidos do libro e capítulos traducidos
- Intro to The Art of Doing Science and Engineering: Learning to Learn (28 de marzo de 1995)
- "Fundamentos da revolución dixital (discreta)" (30 de marzo de 1995)
- "History of Computers - Hardware" (31 de marzo de 1995)
- "History of Computers - Software" (4 de abril de 1995)
- "History of Computers - Applications" (6 de abril de 1995)
- "Intelixencia artificial - Parte I" (7 de abril de 1995)
- "Intelixencia artificial - Parte II" (11 de abril de 1995)
- "Intelixencia Artificial III" (13 de abril de 1995)
- "Espazo n-Dimensional" (14 de abril de 1995)
- "Teoría da codificación - A representación da información, parte I" (18 de abril de 1995)
- "Teoría da codificación - A representación da información, parte II" (20 de abril de 1995)
- "Códigos de corrección de erros" (21 de abril de 1995)
- "Teoría da información" (25 de abril de 1995)
- "Filtros dixitais, parte I" (27 de abril de 1995)
- "Filtros dixitais, parte II" (28 de abril de 1995)
- "Filtros dixitais, parte III" (2 de maio de 1995)
- "Filtros dixitais, parte IV" (4 de maio de 1995)
- "Simulation, Part I" (5 de maio de 1995)
- "Simulation, Part II" (9 de maio de 1995)
- "Simulation, Part III" (11 de maio de 1995)
- "Fibra Óptica" (12 de maio de 1995)
- "Ensino asistido por ordenador" (16 de maio de 1995)
- "Matemáticas" (18 de maio de 1995)
- "Mecánica cuántica" (19 de maio de 1995)
- "Creatividade" (23 de maio de 1995). Tradución:
- "Expertos" (25 de maio de 1995)
- "Datos pouco fiables" (26 de maio de 1995)
- "Enxeñaría de sistemas" (30 de maio de 1995)
- "You Get What You Measure" (1 de xuño de 1995)
- (Xuño 2, 1995) traducir en anacos de 10 minutos
- Hamming, "You and Your Research" (6 de xuño de 1995).
Quen queira axudar coa tradución, maquetación e publicación do libro: escriba nunha mensaxe persoal ou correo electrónico [protexido por correo electrónico]
Fonte: www.habr.com