Mi hai fatto questo!
“Lo scopo di questo corso è prepararti per il tuo futuro tecnico.”
Ciao, Habr. Ricorda il fantastico articolo (+219, 2588 segnalibri, 429 letture)?
Quindi Hamming (sì, sì, automonitoraggio e autocorrezione ) c'è un tutto , scritto sulla base delle sue lezioni. Lo traduciamo, perché l'uomo dice quello che pensa.
Questo è un libro non solo sull'IT, ma sullo stile di pensiero di persone incredibilmente interessanti. “Non è solo una spinta al pensiero positivo; descrive le condizioni che aumentano le possibilità di fare un ottimo lavoro”.
Grazie ad Andrey Pakhomov per la traduzione.
La teoria dell'informazione è stata sviluppata da C. E. Shannon alla fine degli anni '1940. La direzione dei Bell Labs ha insistito perché la chiamasse "Teoria della comunicazione" perché... questo è un nome molto più accurato. Per ovvi motivi, il nome "Teoria dell'informazione" ha un impatto molto maggiore sul pubblico, motivo per cui Shannon lo ha scelto, ed è il nome che conosciamo ancora oggi. Il nome stesso suggerisce che la teoria ha a che fare con l’informazione, il che la rende importante man mano che ci addentriamo nell’era dell’informazione. In questo capitolo, toccherò alcune conclusioni principali di questa teoria, fornirò prove non rigorose, ma piuttosto intuitive di alcune singole disposizioni di questa teoria, in modo che tu possa capire cos'è effettivamente la "teoria dell'informazione" e dove puoi applicarla e dove no.
Innanzitutto, cos’è l’“informazione”? Shannon identifica l'informazione con l'incertezza. Ha scelto il logaritmo negativo della probabilità di un evento come misura quantitativa dell'informazione che si riceve quando si verifica un evento con probabilità p. Ad esempio, se ti dico che il tempo a Los Angeles è nebbioso, allora p è vicino a 1, il che in realtà non ci fornisce molte informazioni. Ma se dico che a Monterey piove a giugno, il messaggio sarà incerto e conterrà più informazioni. Un evento affidabile non contiene alcuna informazione, poiché log 1 = 0.
Diamo un'occhiata a questo in modo più dettagliato. Shannon credeva che la misura quantitativa dell'informazione dovesse essere una funzione continua della probabilità di un evento p, e per eventi indipendenti dovrebbe essere additiva: la quantità di informazioni ottenute come risultato del verificarsi di due eventi indipendenti dovrebbe essere uguale alla quantità di informazioni ottenute a seguito del verificarsi di un evento congiunto. Ad esempio, il risultato di un lancio di dadi e di un lancio di monete vengono solitamente trattati come eventi indipendenti. Traduciamo quanto sopra nel linguaggio della matematica. Se I (p) è la quantità di informazione contenuta in un evento con probabilità p, allora per un evento congiunto costituito da due eventi indipendenti x con probabilità p1 ey con probabilità p2 otteniamo
(xey sono eventi indipendenti)
Questa è l'equazione funzionale di Cauchy, vera per tutti i p1 e p2. Per risolvere questa equazione funzionale, supponiamo che
p1 = p2 = p,
questo da
Se p1 = p2 e p2 = p allora
eccetera. Estendendo questo processo utilizzando il metodo standard per gli esponenziali, per tutti i numeri razionali m/n vale quanto segue
Dalla presunta continuità della misura dell'informazione consegue che la funzione logaritmica è l'unica soluzione continua dell'equazione funzionale di Cauchy.
Nella teoria dell'informazione, è comune considerare la base del logaritmo pari a 2, quindi una scelta binaria contiene esattamente 1 bit di informazione. Pertanto, le informazioni vengono misurate dalla formula
Fermiamoci e capiamo cosa è successo sopra. Innanzitutto non abbiamo definito il concetto di “informazione”; abbiamo semplicemente definito la formula per la sua misura quantitativa.
In secondo luogo, questa misura è soggetta a incertezza e, sebbene sia ragionevolmente adatta alle macchine – ad esempio sistemi telefonici, radio, televisione, computer, ecc. – non riflette il normale atteggiamento umano nei confronti dell’informazione.
In terzo luogo, questa è una misura relativa, dipende dallo stato attuale delle tue conoscenze. Se guardi un flusso di “numeri casuali” da un generatore di numeri casuali, presumi che ogni numero successivo sia incerto, ma se conosci la formula per calcolare i “numeri casuali”, il numero successivo sarà noto e quindi non lo sarà. contenere informazioni.
Quindi la definizione di informazione di Shannon è appropriata per le macchine in molti casi, ma non sembra adattarsi alla comprensione umana della parola. È per questo motivo che la “Teoria dell’informazione” avrebbe dovuto essere chiamata “Teoria della comunicazione”. Tuttavia, è troppo tardi per cambiare le definizioni (che hanno dato alla teoria la sua popolarità iniziale, e che ancora fanno pensare che questa teoria abbia a che fare con l’”informazione”), quindi dobbiamo conviverci, ma allo stesso tempo dobbiamo comprendere chiaramente quanto la definizione di informazione di Shannon sia lontana dal suo significato comunemente usato. Le informazioni di Shannon riguardano qualcosa di completamente diverso, vale a dire l'incertezza.
Ecco qualcosa a cui pensare quando proponi una terminologia. In che modo una definizione proposta, come la definizione di informazione di Shannon, concorda con la tua idea originale e quanto è diversa? Non esiste quasi nessun termine che rifletta esattamente la tua precedente visione di un concetto, ma alla fine è la terminologia utilizzata che riflette il significato del concetto, quindi formalizzare qualcosa attraverso definizioni chiare introduce sempre del rumore.
Consideriamo un sistema il cui alfabeto è costituito da simboli q con probabilità pi. In questo caso quantità media di informazioni nel sistema (il suo valore atteso) è pari a:
Questa è chiamata entropia del sistema con distribuzione di probabilità {pi}. Usiamo il termine "entropia" perché la stessa forma matematica appare nella termodinamica e nella meccanica statistica. Ecco perché il termine “entropia” crea attorno a sé una certa aura di importanza, che in definitiva non è giustificata. La stessa forma matematica di notazione non implica la stessa interpretazione dei simboli!
L'entropia della distribuzione di probabilità gioca un ruolo importante nella teoria dei codici. La disuguaglianza di Gibbs per due diverse distribuzioni di probabilità pi e qi è una delle conseguenze importanti di questa teoria. Quindi dobbiamo dimostrarlo
La dimostrazione si basa su un grafico evidente, Fig. 13.I, il che lo dimostra
e l'uguaglianza si ottiene solo quando x = 1. Applichiamo la disuguaglianza a ciascun termine della somma dal lato sinistro:
Se l'alfabeto di un sistema di comunicazione è costituito da q simboli, allora prendendo la probabilità di trasmissione di ciascun simbolo qi = 1/q e sostituendo q, otteniamo dalla disuguaglianza di Gibbs
Figura 13.I
Ciò significa che se la probabilità di trasmettere tutti i simboli q è la stessa e pari a - 1 / q, allora l'entropia massima è uguale a ln q, altrimenti vale la disuguaglianza.
Nel caso di un codice univocamente decodificabile si ha la disuguaglianza di Kraft
Ora se definiamo le pseudo-probabilità
dove ovviamente = 1, che segue dalla disuguaglianza di Gibbs,
e applichiamo un po' di algebra (ricordiamo che K ≤ 1, così possiamo eliminare il termine logaritmico e forse rafforzare la disuguaglianza in seguito), otteniamo
dove L è la lunghezza media del codice.
Pertanto, l'entropia è il limite minimo per qualsiasi codice carattere per simbolo con una lunghezza media della parola in codice L. Questo è il teorema di Shannon per un canale privo di interferenze.
Consideriamo ora il teorema principale sui limiti dei sistemi di comunicazione in cui l'informazione viene trasmessa come un flusso di bit indipendenti ed è presente rumore. Resta inteso che la probabilità di trasmissione corretta di un bit è P > 1/2, e la probabilità che il valore del bit venga invertito durante la trasmissione (si verifichi un errore) è pari a Q = 1 - P. Per comodità, presupponiamo che gli errori siano indipendenti e che la probabilità di un errore sia la stessa per ciascun bit inviato, ovvero che sia presente un "rumore bianco" nel canale di comunicazione.
Il modo in cui abbiamo un lungo flusso di n bit codificati in un messaggio è l'estensione n-dimensionale del codice a un bit. Determineremo il valore di n più tardi. Considera un messaggio composto da n bit come un punto nello spazio n dimensionale. Poiché abbiamo uno spazio n-dimensionale - e per semplicità assumeremo che ogni messaggio abbia la stessa probabilità di accadimento - ci sono M messaggi possibili (anche M verrà definito in seguito), quindi la probabilità di ogni messaggio inviato è
(mittente)
Allegato 13.II
Successivamente, considera l'idea della capacità del canale. Senza entrare nei dettagli, la capacità del canale è definita come la quantità massima di informazioni che possono essere trasmesse in modo affidabile su un canale di comunicazione, tenendo conto dell'uso della codifica più efficiente. Non vi è alcun argomento che possa trasmettere più informazioni attraverso un canale di comunicazione rispetto alla sua capacità. Ciò può essere dimostrato per un canale simmetrico binario (che utilizziamo nel nostro caso). La capacità del canale, quando si inviano bit, è specificata come
dove, come prima, P è la probabilità che non vi siano errori in alcun bit inviato. Quando si inviano n bit indipendenti, la capacità del canale è data da
Se siamo vicini alla capacità del canale, allora dobbiamo inviare quasi questa quantità di informazioni per ciascuno dei simboli ai, i = 1, ..., M. Considerando che la probabilità di occorrenza di ciascun simbolo ai è 1 / M, noi abbiamo
quando inviamo uno qualsiasi dei M messaggi ugualmente probabili ai, abbiamo
Quando vengono inviati n bit, ci aspettiamo che si verifichino nQ errori. In pratica, per un messaggio composto da n bit, avremo circa nQ errori nel messaggio ricevuto. Per n grande, variazione relativa (variazione = larghezza di distribuzione, )
la distribuzione del numero di errori diventerà sempre più ristretta all'aumentare di n.
Quindi, dal lato del trasmettitore, prendo il messaggio ai da inviare e gli disegno attorno una sfera con un raggio
che è leggermente maggiore di un importo pari a e2 rispetto al numero di errori attesi Q, (Figura 13.II). Se n è sufficientemente grande, allora esiste una probabilità arbitrariamente piccola che sul lato ricevente appaia un punto del messaggio bj che si estende oltre questa sfera. Descriviamo la situazione come la vedo io dal punto di vista del trasmettitore: abbiamo qualsiasi raggio dal messaggio trasmesso ai al messaggio ricevuto bj con una probabilità di errore uguale (o quasi uguale) alla distribuzione normale, raggiungendo un massimo di nQ. Per ogni dato e2, c'è un n così grande che la probabilità che il punto risultante bj sia fuori dalla mia sfera è piccola quanto vuoi.
Ora diamo un'occhiata alla stessa situazione dalla tua parte (Fig. 13.III). Dal lato del ricevente c'è una sfera S(r) dello stesso raggio r attorno al punto ricevuto bj nello spazio n-dimensionale, tale che se il messaggio ricevuto bj è all'interno della mia sfera, allora il messaggio ai da me inviato è all'interno della tua sfera.
Come può verificarsi un errore? L'errore può verificarsi nei casi descritti nella tabella seguente:
Figura 13.III
Qui vediamo che se nella sfera costruita attorno al punto ricevuto c'è almeno un altro punto corrispondente ad un eventuale messaggio inviato non codificato, allora si è verificato un errore durante la trasmissione, poiché non è possibile determinare quale di questi messaggi sia stato trasmesso. Il messaggio inviato è esente da errori solo se il punto ad esso corrispondente si trova nella sfera e non esistono altri punti possibili nel codice dato che si trovino nella stessa sfera.
Abbiamo un'equazione matematica per la probabilità di errore Pe se è stato inviato il messaggio ai
Possiamo eliminare il primo fattore nel secondo termine, prendendolo come 1. In questo modo otteniamo la disuguaglianza
Ovviamente, l'
следовательно
riapplicare all'ultimo termine a destra
Prendendo n sufficientemente grande, il primo termine può essere preso piccolo quanto si desidera, diciamo inferiore a un certo numero d. Pertanto abbiamo
Ora vediamo come possiamo costruire un semplice codice di sostituzione per codificare M messaggi costituiti da n bit. Non avendo idea di come costruire esattamente un codice (i codici di correzione degli errori non erano ancora stati inventati), Shannon scelse la codifica casuale. Lancia una moneta per ciascuno degli n bit nel messaggio e ripeti la procedura per M messaggi. In totale, è necessario effettuare lanci di monete nM, quindi è possibile
dizionari di codici aventi la stessa probabilità ½nM. Naturalmente, il processo casuale di creazione di un codebook significa che esiste la possibilità di duplicati, così come di punti di codice che saranno vicini tra loro e quindi costituiranno fonte di probabili errori. Bisogna dimostrare che se ciò non accade con una probabilità maggiore di qualsiasi piccolo livello di errore scelto, allora il dato n è sufficientemente grande.
Il punto cruciale è che Shannon ha calcolato la media di tutti i codici possibili per trovare l'errore medio! Useremo il simbolo Av[.] per denotare il valore medio sull'insieme di tutti i possibili codici casuali. La media su una costante d, ovviamente, dà una costante, poiché per la media ogni termine è uguale a ogni altro termine nella somma,
che può essere aumentato (M–1 va a M)
Per ogni dato messaggio, quando si calcola la media tra tutti i codici, la codifica passa attraverso tutti i valori possibili, quindi la probabilità media che un punto si trovi in una sfera è il rapporto tra il volume della sfera e il volume totale dello spazio. Il volume della sfera è
dove s=Q+e2 <1/2 e ns deve essere un numero intero.
L'ultimo termine a destra è il più grande in questa somma. Innanzitutto, stimiamo il suo valore utilizzando la formula di Stirling per i fattoriali. Guarderemo quindi il coefficiente decrescente del termine davanti ad esso, noteremo che questo coefficiente aumenta man mano che ci spostiamo verso sinistra, e quindi possiamo: (1) restringere il valore della somma alla somma della progressione geometrica con questo coefficiente iniziale, (2) espandere la progressione geometrica da ns termini a un numero infinito di termini, (3) calcolare la somma di una progressione geometrica infinita (algebra standard, nulla di significativo) e infine ottenere il valore limite (per un valore sufficientemente grande N):
Notate come appare l'entropia H(s) nell'identità binomiale. Si noti che lo sviluppo in serie di Taylor H(s)=H(Q+e2) fornisce una stima ottenuta tenendo conto solo della derivata prima e ignorando tutte le altre. Ora mettiamo insieme l'espressione finale:
dove
Tutto quello che dobbiamo fare è scegliere e2 tale che e3 < e1, e quindi l'ultimo termine sarà arbitrariamente piccolo, purché n sia sufficientemente grande. Di conseguenza, l’errore PE medio può essere ottenuto piccolo quanto desiderato con la capacità del canale arbitrariamente vicina a C.
Se la media di tutti i codici ha un errore sufficientemente piccolo, allora almeno un codice deve essere adatto, quindi esiste almeno un sistema di codifica adatto. Questo è un risultato importante ottenuto da Shannon - "il teorema di Shannon per un canale rumoroso", anche se va notato che lo ha dimostrato per un caso molto più generale che per il semplice canale binario simmetrico che ho usato. Nel caso generale, i calcoli matematici sono molto più complicati, ma le idee non sono così diverse, quindi molto spesso, utilizzando l'esempio di un caso particolare, è possibile rivelare il vero significato del teorema.
Critichiamo il risultato. Abbiamo ripetuto più volte: “Per n sufficientemente grande”. Ma quanto è grande n? Molto, molto grande se vuoi davvero essere vicino alla capacità del canale ed essere sicuro del corretto trasferimento dei dati! Così grande, infatti, che dovrai aspettare molto tempo per accumulare un messaggio con abbastanza bit per codificarlo successivamente. In questo caso, la dimensione del dizionario dei codici casuali sarà semplicemente enorme (dopotutto, un tale dizionario non può essere rappresentato in una forma più breve di un elenco completo di tutti i Mn bit, nonostante n e M siano molto grandi)!
I codici di correzione degli errori evitano di attendere un messaggio molto lungo e quindi di codificarlo e decodificarlo attraverso codici molto grandi perché evitano i codici stessi e utilizzano invece il calcolo ordinario. In teoria, tali codici tendono a perdere la capacità di avvicinarsi alla capacità del canale e mantengono comunque un basso tasso di errore, ma quando il codice corregge un gran numero di errori, funzionano bene. In altre parole, se si assegna una certa capacità del canale alla correzione degli errori, è necessario utilizzare la capacità di correzione degli errori per la maggior parte del tempo, ovvero è necessario correggere un gran numero di errori in ciascun messaggio inviato, altrimenti si spreca questa capacità.
Allo stesso tempo, il teorema dimostrato sopra non è ancora privo di significato! Mostra che sistemi di trasmissione efficienti devono utilizzare schemi di codifica intelligenti per stringhe di bit molto lunghe. Un esempio sono i satelliti che hanno volato oltre i pianeti esterni; Man mano che si allontanano dalla Terra e dal Sole, sono costretti a correggere sempre più errori nel blocco dati: alcuni satelliti utilizzano pannelli solari, che forniscono circa 5 W, altri utilizzano fonti di energia nucleare, che forniscono circa la stessa potenza. La bassa potenza dell'alimentatore, le piccole dimensioni delle parabole trasmittenti e le dimensioni limitate delle parabole riceventi sulla Terra, l'enorme distanza che il segnale deve percorrere: tutto ciò richiede l'uso di codici con un alto livello di correzione degli errori per costruire un sistema di comunicazione efficace.
Torniamo allo spazio n-dimensionale che abbiamo usato nella dimostrazione precedente. Discutendone, abbiamo dimostrato che quasi l'intero volume della sfera è concentrato vicino alla superficie esterna - quindi è quasi certo che il segnale inviato si troverà vicino alla superficie della sfera costruita attorno al segnale ricevuto, anche con una distanza relativamente elevata. piccolo raggio di tale sfera. Pertanto non sorprende che il segnale ricevuto, dopo aver corretto un numero arbitrariamente grande di errori, nQ, risulti arbitrariamente vicino a un segnale privo di errori. La capacità di collegamento di cui abbiamo discusso in precedenza è la chiave per comprendere questo fenomeno. Si noti che sfere simili costruite per la correzione degli errori dei codici Hamming non si sovrappongono tra loro. Il gran numero di dimensioni quasi ortogonali nello spazio n-dimensionale mostra perché possiamo inserire M sfere nello spazio con poca sovrapposizione. Se permettiamo una piccola, arbitrariamente piccola sovrapposizione, che può portare solo a un piccolo numero di errori durante la decodifica, possiamo ottenere una densa disposizione delle sfere nello spazio. Hamming garantiva un certo livello di correzione degli errori, Shannon - una bassa probabilità di errore, ma allo stesso tempo mantenendo il throughput effettivo arbitrariamente vicino alla capacità del canale di comunicazione, cosa che i codici Hamming non possono fare.
La teoria dell’informazione non ci dice come progettare un sistema efficiente, ma indica la strada verso sistemi di comunicazione efficienti. È uno strumento prezioso per costruire sistemi di comunicazione da macchina a macchina, ma, come notato in precedenza, ha poca rilevanza per il modo in cui gli esseri umani comunicano tra loro. La misura in cui l’eredità biologica è simile ai sistemi tecnici di comunicazione è semplicemente sconosciuta, quindi al momento non è chiaro come la teoria dell’informazione si applichi ai geni. Non abbiamo altra scelta che provarci, e se il successo ci mostra la natura meccanica di questo fenomeno, allora il fallimento indicherà altri aspetti significativi della natura dell’informazione.
Non divaghiamo troppo. Abbiamo visto che tutte le definizioni originali, in misura maggiore o minore, devono esprimere l'essenza delle nostre convinzioni originali, ma sono caratterizzate da un certo grado di distorsione e quindi non sono applicabili. È tradizionalmente accettato che, in definitiva, la definizione che usiamo definisce effettivamente l'essenza; ma questo ci dice solo come elaborare le cose e non ci trasmette in alcun modo alcun significato. L’approccio postulazionale, così fortemente favorito negli ambienti matematici, lascia molto a desiderare nella pratica.
Ora esamineremo un esempio di test del QI in cui la definizione è circolare quanto vuoi e, di conseguenza, fuorviante. Viene creato un test che dovrebbe misurare l'intelligenza. Viene poi rivisto per renderlo il più coerente possibile, quindi pubblicato e, con un metodo semplice, calibrato in modo che l’“intelligenza” misurata risulti essere distribuita normalmente (su una curva di calibrazione, ovviamente). Tutte le definizioni devono essere ricontrollate, non solo quando vengono proposte per la prima volta, ma anche molto più tardi, quando vengono utilizzate nelle conclusioni tratte. In che misura i confini della definizione sono adeguati al problema da risolvere? Quanto spesso le definizioni fornite in un contesto vengono applicate in contesti molto diversi? Questo accade abbastanza spesso! Nelle discipline umanistiche, che inevitabilmente incontrerai nella tua vita, questo accade più spesso.
Pertanto, uno degli scopi di questa presentazione della teoria dell'informazione, oltre a dimostrarne l'utilità, era quello di avvisarvi di questo pericolo, o di mostrarvi esattamente come usarlo per ottenere il risultato desiderato. È stato notato da tempo che le definizioni iniziali determinano ciò che si trova alla fine, in misura molto maggiore di quanto sembri. Le definizioni iniziali richiedono molta attenzione da parte tua, non solo in ogni nuova situazione, ma anche nelle aree con cui lavori da molto tempo. Questo permetterà di capire fino a che punto i risultati ottenuti siano una tautologia e non qualcosa di utile.
La famosa storia di Eddington racconta di persone che pescavano in mare con una rete. Dopo aver studiato la dimensione del pesce catturato, hanno determinato la dimensione minima del pesce che si trova nel mare! La loro conclusione è stata guidata dallo strumento utilizzato, non dalla realtà.
To be continued ...
Chi vuole aiutare con la traduzione, l'impaginazione e la pubblicazione del libro - scrivi in un messaggio personale o e-mail [email protected]
A proposito, abbiamo anche lanciato la traduzione di un altro bel libro: )
Cerchiamo soprattutto coloro che aiuteranno a tradurre . (trasferimento per 10 minuti, i primi 20 sono già stati occupati)
Contenuto del libro e capitoli tradotti
- Introduzione all'arte di fare scienza e ingegneria: imparare a imparare (28 marzo 1995)
- "Fondamenti della rivoluzione digitale (discreta)" (30 marzo 1995)
- "Storia dei computer - Hardware" (31 marzo 1995)
- "Storia dei computer - Software" (4 aprile 1995)
- "Storia dei computer - Applicazioni" (6 aprile 1995)
- "Intelligenza Artificiale - Parte I" (7 aprile 1995)
- "Intelligenza Artificiale - Parte II" (11 aprile 1995)
- "Intelligenza Artificiale III" (13 aprile 1995)
- "Spazio n-dimensionale" (14 aprile 1995)
- "Teoria dei codici - La rappresentazione delle informazioni, parte I" (18 aprile 1995)
- "Teoria dei codici - La rappresentazione delle informazioni, parte II" (20 aprile 1995)
- "Codici di correzione degli errori" (21 aprile 1995)
- "Teoria dell'informazione" (25 aprile 1995)
- "Filtri digitali, parte I" (27 aprile 1995)
- "Filtri digitali, parte II" (28 aprile 1995)
- "Filtri digitali, parte III" (2 maggio 1995)
- "Filtri digitali, parte IV" (4 maggio 1995)
- "Simulazione, parte I" (5 maggio 1995)
- "Simulazione, parte II" (9 maggio 1995)
- "Simulazione, parte III" (11 maggio 1995)
- "Fibra Ottica" (12 maggio 1995)
- "Istruzione assistita dal computer" (16 maggio 1995)
- "Matematica" (18 maggio 1995)
- "Meccanica quantistica" (19 maggio 1995)
- "Creatività" (23 maggio 1995). Traduzione:
- "Esperti" (25 maggio 1995)
- "Dati inaffidabili" (26 maggio 1995)
- "Ingegneria dei sistemi" (30 maggio 1995)
- "Ottieni ciò che misuri" (1 giugno 1995)
- (Giugno 2, 1995) tradurre in pezzi di 10 minuti
- Hamming, "Tu e la tua ricerca" (6 giugno 1995).
Chi vuole aiutare con la traduzione, l'impaginazione e la pubblicazione del libro - scrivi in un messaggio personale o e-mail [email protected]
Fonte: habr.com