C'est moi qui l'ai dit !
« Le but de cette formation est de vous préparer à votre avenir technique. »
Bonjour Habr. Rappelez-vous l'article génial (+219, 2588 signets, 429 XNUMX lectures) ?
Alors Hamming (oui, oui, auto-surveillance et auto-correction ) il y a un tout , écrit sur la base de ses conférences. Nous le traduisons, parce que l’homme dit ce qu’il pense.
Ce n'est pas seulement un livre sur l'informatique, c'est un livre sur le style de pensée de gens incroyablement cool. « Ce n’est pas seulement un élan de pensée positive ; il décrit les conditions qui augmentent les chances de réaliser un excellent travail.
Merci à Andrey Pakhomov pour la traduction.
La théorie de l’information a été développée par C. E. Shannon à la fin des années 1940. La direction des Bell Labs a insisté pour qu'il l'appelle « Théorie de la communication » parce que... c'est un nom beaucoup plus précis. Pour des raisons évidentes, le nom « Théorie de l’information » a un impact bien plus grand sur le public, c’est pourquoi Shannon l’a choisi, et c’est le nom que nous connaissons encore aujourd’hui. Le nom lui-même suggère que la théorie traite de l’information, ce qui la rend importante à mesure que nous avançons plus profondément dans l’ère de l’information. Dans ce chapitre, j'aborderai plusieurs conclusions principales de cette théorie, je fournirai des preuves non strictes, mais plutôt intuitives de certaines dispositions individuelles de cette théorie, afin que vous compreniez ce qu'est réellement la « théorie de l'information », où vous pouvez l'appliquer. et où pas.
Tout d’abord, qu’est-ce qu’une « information » ? Shannon assimile l'information à l'incertitude. Il a choisi le logarithme négatif de la probabilité d'un événement comme mesure quantitative de l'information que vous recevez lorsqu'un événement de probabilité p se produit. Par exemple, si je vous dis que le temps à Los Angeles est brumeux, alors p est proche de 1, ce qui ne nous donne pas vraiment beaucoup d'informations. Mais si je dis qu'il pleut à Monterey en juin, il y aura de l'incertitude dans le message et il contiendra plus d'informations. Un événement fiable ne contient aucune information, puisque log 1 = 0.
Regardons cela plus en détail. Shannon pensait que la mesure quantitative de l'information devrait être une fonction continue de la probabilité d'un événement p, et pour les événements indépendants, elle devrait être additive - la quantité d'informations obtenues à la suite de l'apparition de deux événements indépendants devrait être égale à la quantité d'informations obtenues à la suite de la survenance d'un événement commun. Par exemple, le résultat d’un lancer de dés et d’un lancer de pièces sont généralement traités comme des événements indépendants. Traduisons ce qui précède dans le langage des mathématiques. Si I (p) est la quantité d'informations contenues dans un événement avec probabilité p, alors pour un événement conjoint constitué de deux événements indépendants x avec probabilité p1 et y avec probabilité p2 on obtient
(x et y sont des événements indépendants)
C'est l'équation fonctionnelle de Cauchy, vraie pour tous p1 et p2. Pour résoudre cette équation fonctionnelle, supposons que
p1 = p2 = p,
cela donne
Si p1 = p2 et p2 = p alors
etc. En étendant ce processus en utilisant la méthode standard pour les exponentielles, pour tous les nombres rationnels m/n, ce qui suit est vrai
De la continuité supposée de la mesure de l'information, il s'ensuit que la fonction logarithmique est la seule solution continue de l'équation fonctionnelle de Cauchy.
En théorie de l’information, il est courant de prendre la base du logarithme égale à 2, donc un choix binaire contient exactement 1 bit d’information. Par conséquent, l'information est mesurée par la formule
Faisons une pause et comprenons ce qui s'est passé ci-dessus. Tout d’abord, nous n’avons pas défini le concept d’« information », nous avons simplement défini la formule de sa mesure quantitative.
Deuxièmement, cette mesure est sujette à l’incertitude et, bien qu’elle soit raisonnablement adaptée aux machines – par exemple les systèmes téléphoniques, la radio, la télévision, les ordinateurs, etc. – elle ne reflète pas les attitudes humaines normales à l’égard de l’information.
Troisièmement, il s'agit d'une mesure relative, elle dépend de l'état actuel de vos connaissances. Si vous regardez un flux de « nombres aléatoires » provenant d'un générateur de nombres aléatoires, vous supposez que chaque nombre suivant est incertain, mais si vous connaissez la formule de calcul des « nombres aléatoires », le nombre suivant sera connu et ne le sera donc pas. contenir des informations.
Ainsi, la définition de Shannon de l'information est appropriée pour les machines dans de nombreux cas, mais ne semble pas correspondre à la compréhension humaine du mot. C’est pour cette raison que la « théorie de l’information » aurait dû être appelée « théorie de la communication ». Cependant, il est trop tard pour changer les définitions (qui ont donné à la théorie sa popularité initiale et qui font encore penser que cette théorie traite de « l’information »), il faut donc vivre avec, mais en même temps il faut comprendre clairement à quel point la définition de l'information donnée par Shannon est éloignée de sa signification couramment utilisée. Les informations de Shannon portent sur quelque chose de complètement différent, à savoir l'incertitude.
Voici quelque chose à penser lorsque vous proposez une terminologie. Dans quelle mesure une définition proposée, telle que celle de Shannon, s'accorde-t-elle avec votre idée originale et dans quelle mesure est-elle différente ? Il n’existe quasiment aucun terme qui reflète exactement votre vision antérieure d’un concept, mais en fin de compte, c’est la terminologie utilisée qui reflète le sens du concept, donc formaliser quelque chose à travers des définitions claires introduit toujours du bruit.
Considérons un système dont l'alphabet est constitué de symboles q avec des probabilités pi. Dans ce cas quantité moyenne d'informations dans le système (sa valeur attendue) est égale à :
C'est ce qu'on appelle l'entropie du système avec distribution de probabilité {pi}. Nous utilisons le terme « entropie » car la même forme mathématique apparaît en thermodynamique et en mécanique statistique. C’est pourquoi le terme « entropie » crée autour de lui une certaine aura d’importance, qui n’est finalement pas justifiée. La même forme mathématique de notation n’implique pas la même interprétation des symboles !
L'entropie de la distribution de probabilité joue un rôle majeur dans la théorie du codage. L'inégalité de Gibbs pour deux distributions de probabilité différentes pi et qi est l'une des conséquences importantes de cette théorie. Il faut donc prouver que
La preuve est basée sur un graphique évident, Fig. 13.I, ce qui montre que
et l'égalité n'est atteinte que lorsque x = 1. Appliquons l'inégalité à chaque terme de la somme du côté gauche :
Si l'alphabet d'un système de communication est constitué de q symboles, alors en prenant la probabilité de transmission de chaque symbole qi = 1/q et en substituant q, nous obtenons de l'inégalité de Gibbs
Figure 13.I
Cela signifie que si la probabilité de transmettre tous les symboles q est la même et égale à - 1 / q, alors l'entropie maximale est égale à ln q, sinon l'inégalité est vraie.
Dans le cas d'un code uniquement décodable, nous avons l'inégalité de Kraft
Maintenant si on définit des pseudo-probabilités
où bien sûr = 1, qui découle de l’inégalité de Gibbs,
et appliquez un peu d'algèbre (rappelez-vous que K ≤ 1, donc nous pouvons laisser tomber le terme logarithmique, et peut-être renforcer l'inégalité plus tard), nous obtenons
où L est la longueur moyenne du code.
Ainsi, l'entropie est la limite minimale pour tout code caractère par symbole avec une longueur moyenne de mot de code L. Il s'agit du théorème de Shannon pour un canal sans interférence.
Considérons maintenant le théorème principal sur les limites des systèmes de communication dans lesquels les informations sont transmises sous la forme d'un flux de bits indépendants et de bruit. Il est entendu que la probabilité de transmission correcte d'un bit est P > 1/2, et la probabilité que la valeur du bit soit inversée pendant la transmission (une erreur se produira) est égale à Q = 1 - P. Pour plus de commodité, nous supposons que les erreurs sont indépendantes et que la probabilité d'une erreur est la même pour chaque bit envoyé - c'est-à-dire qu'il y a un « bruit blanc » dans le canal de communication.
La façon dont nous avons un long flux de n bits codés dans un seul message est l'extension à n dimensions du code à un bit. Nous déterminerons la valeur de n plus tard. Considérons un message composé de n bits comme un point dans un espace à n dimensions. Puisque nous avons un espace à n dimensions - et pour simplifier nous supposerons que chaque message a la même probabilité d'apparition - il y a M messages possibles (M sera également défini plus tard), donc la probabilité d'envoi d'un message est
(expéditeur)
Annexe 13.II
Ensuite, considérons l'idée de capacité de canal. Sans entrer dans les détails, la capacité du canal est définie comme la quantité maximale d'informations pouvant être transmises de manière fiable sur un canal de communication, en tenant compte de l'utilisation du codage le plus efficace. Il ne fait aucun doute que plus d’informations peuvent être transmises via un canal de communication que sa capacité. Cela peut être prouvé pour un canal symétrique binaire (que nous utilisons dans notre cas). La capacité du canal, lors de l'envoi de bits, est spécifiée comme
où, comme précédemment, P est la probabilité qu’il n’y ait aucune erreur dans un bit envoyé. Lors de l'envoi de n bits indépendants, la capacité du canal est donnée par
Si on est proche de la capacité du canal, alors on doit envoyer quasiment cette quantité d'informations pour chacun des symboles ai, i = 1, ..., M. Considérant que la probabilité d'apparition de chaque symbole ai est de 1/M, on a
lorsque nous envoyons l’un des M messages équiprobables ai, nous avons
Lorsque n bits sont envoyés, nous nous attendons à ce que nQ erreurs se produisent. En pratique, pour un message constitué de n bits, on aura environ nQ erreurs dans le message reçu. Pour n grand, variation relative (variation = largeur de distribution, )
la répartition du nombre d’erreurs deviendra de plus en plus étroite à mesure que n augmente.
Donc, du côté émetteur, je prends le message ai à envoyer et je dessine une sphère autour de lui avec un rayon
qui est légèrement supérieur d’un montant égal à e2 au nombre attendu d’erreurs Q (Figure 13.II). Si n est suffisamment grand, alors il existe une probabilité arbitrairement faible qu’un point de message bj apparaisse du côté du récepteur et s’étende au-delà de cette sphère. Esquissons la situation telle que je la vois du point de vue de l'émetteur : nous avons des rayons quelconques depuis le message transmis ai jusqu'au message reçu bj avec une probabilité d'erreur égale (ou presque égale) à la distribution normale, atteignant un maximum de nQ. Pour tout e2 donné, il existe un n si grand que la probabilité que le point résultant bj soit en dehors de ma sphère est aussi petite que vous le souhaitez.
Regardons maintenant la même situation de votre côté (Fig. 13.III). Du côté du récepteur, il y a une sphère S(r) du même rayon r autour du point reçu bj dans un espace à n dimensions, de sorte que si le message reçu bj est à l'intérieur de ma sphère, alors le message ai que j'ai envoyé est à l'intérieur de votre sphère.
Comment une erreur peut-elle se produire ? L'erreur peut survenir dans les cas décrits dans le tableau ci-dessous :
Figure 13.III
On voit ici que si dans la sphère construite autour du point reçu il y a au moins un point supplémentaire correspondant à un éventuel message non codé envoyé, alors une erreur s'est produite lors de la transmission, puisqu'il est impossible de déterminer lequel de ces messages a été transmis. Le message envoyé est sans erreur uniquement si le point qui lui correspond est dans la sphère, et qu'il n'y a pas d'autres points possibles dans le code donné qui se trouvent dans la même sphère.
Nous avons une équation mathématique pour la probabilité d'erreur Pe si le message ai était envoyé
Nous pouvons éliminer le premier facteur du deuxième terme, en le prenant pour 1. Nous obtenons ainsi l'inégalité
De toute évidence, l'
donc
réappliquer au dernier terme à droite
En prenant n suffisamment grand, le premier terme peut être pris aussi petit que souhaité, disons inférieur à un certain nombre d. Nous avons donc
Voyons maintenant comment construire un code de substitution simple pour coder M messages composés de n bits. N'ayant aucune idée de la manière exacte de construire un code (les codes correcteurs d'erreurs n'ayant pas encore été inventés), Shannon a choisi le codage aléatoire. Lancez une pièce de monnaie pour chacun des n bits du message et répétez le processus pour M messages. Au total, nM lancers de pièces doivent être effectués, il est donc possible
dictionnaires de codes ayant la même probabilité ½nM. Bien entendu, le processus aléatoire de création d'un livre de codes signifie qu'il existe une possibilité de doublons, ainsi que des points de code qui seront proches les uns des autres et seront donc source d'erreurs probables. Il faut prouver que si cela ne se produit pas avec une probabilité supérieure à tout petit niveau d’erreur choisi, alors le n donné est suffisamment grand.
Le point crucial est que Shannon a fait la moyenne de tous les livres de codes possibles pour trouver l'erreur moyenne ! Nous utiliserons le symbole Av[.] pour désigner la valeur moyenne sur l’ensemble de tous les livres de codes aléatoires possibles. La moyenne sur une constante d donne bien sûr une constante, puisque pour faire la moyenne, chaque terme est le même que tous les autres termes de la somme,
qui peut être augmenté (M–1 va à M)
Pour un message donné, lors de la moyenne de tous les livres de codes, le codage passe par toutes les valeurs possibles, de sorte que la probabilité moyenne qu'un point se trouve dans une sphère est le rapport entre le volume de la sphère et le volume total de l'espace. Le volume de la sphère est
où s=Q+e2 <1/2 et ns doit être un nombre entier.
Le dernier terme à droite est le plus grand de cette somme. Tout d’abord, estimons sa valeur à l’aide de la formule de Stirling pour les factorielles. On regardera ensuite le coefficient décroissant du terme qui le précède, notons que ce coefficient augmente à mesure qu'on se déplace vers la gauche, et on pourra donc : (1) restreindre la valeur de la somme à la somme de la progression géométrique avec ce coefficient initial, (2) étendre la progression géométrique de ns termes à un nombre infini de termes, (3) calculer la somme d'une progression géométrique infinie (algèbre standard, rien de significatif) et enfin obtenir la valeur limite (pour un coefficient suffisamment grand n):
Remarquez comment l'entropie H(s) est apparue dans l'identité binomiale. Notez que le développement en série de Taylor H(s)=H(Q+e2) donne une estimation obtenue en prenant en compte uniquement la dérivée première et en ignorant toutes les autres. Rassemblons maintenant l'expression finale :
où
Tout ce que nous avons à faire est de choisir e2 tel que e3 < e1, et alors le dernier terme sera arbitrairement petit, tant que n est suffisamment grand. Par conséquent, l’erreur PE moyenne peut être obtenue aussi petite que souhaité avec la capacité du canal arbitrairement proche de C.
Si la moyenne de tous les codes présente une erreur suffisamment petite, alors au moins un code doit convenir, il existe donc au moins un système de codage approprié. Il s'agit d'un résultat important obtenu par Shannon - "Théorème de Shannon pour un canal bruyant", même s'il convient de noter qu'il l'a prouvé pour un cas beaucoup plus général que pour le simple canal symétrique binaire que j'ai utilisé. Pour le cas général, les calculs mathématiques sont beaucoup plus compliqués, mais les idées ne sont pas si différentes, donc très souvent, à l'aide de l'exemple d'un cas particulier, on peut révéler le vrai sens du théorème.
Critiquons le résultat. Nous avons répété à plusieurs reprises : « Pour n suffisamment grand ». Mais quelle est la taille de n ? Très, très grand si vous voulez vraiment être à la fois proche de la capacité du canal et être sûr du bon transfert de données ! Si grand, en fait, qu'il faudra attendre très longtemps pour accumuler un message de suffisamment de bits pour l'encoder plus tard. Dans ce cas, la taille du dictionnaire de codes aléatoires sera tout simplement énorme (après tout, un tel dictionnaire ne peut pas être représenté sous une forme plus courte qu'une liste complète de tous les Mn bits, malgré le fait que n et M soient très grands) !
Les codes de correction d'erreurs évitent d'attendre un message très long, puis de le coder et de le décoder via de très grands livres de codes, car ils évitent les livres de codes eux-mêmes et utilisent à la place des calculs ordinaires. En théorie simple, ces codes ont tendance à perdre la capacité de s'approcher de la capacité du canal tout en conservant un faible taux d'erreur, mais lorsque le code corrige un grand nombre d'erreurs, ils fonctionnent bien. En d’autres termes, si vous allouez une certaine capacité de canal à la correction d’erreurs, alors vous devez utiliser la capacité de correction d’erreurs la plupart du temps, c’est-à-dire qu’un grand nombre d’erreurs doivent être corrigées dans chaque message envoyé, sinon vous gaspillez cette capacité.
En même temps, le théorème démontré ci-dessus n’est toujours pas dénué de sens ! Cela montre que les systèmes de transmission efficaces doivent utiliser des schémas de codage intelligents pour les chaînes de bits très longues. Un exemple est celui des satellites qui ont volé au-delà des planètes extérieures ; À mesure qu'ils s'éloignent de la Terre et du Soleil, ils sont obligés de corriger de plus en plus d'erreurs dans le bloc de données : certains satellites utilisent des panneaux solaires, qui fournissent environ 5 W, d'autres utilisent des sources d'énergie nucléaires, qui fournissent à peu près la même puissance. La faible puissance de l'alimentation électrique, la petite taille des paraboles émettrices et la taille limitée des paraboles réceptrices sur Terre, l'énorme distance que doit parcourir le signal - tout cela nécessite l'utilisation de codes avec un niveau élevé de correction d'erreurs pour construire un système de communication efficace.
Revenons à l'espace à n dimensions que nous avons utilisé dans la preuve ci-dessus. En en discutant, nous avons montré que presque tout le volume de la sphère est concentré près de la surface extérieure - il est donc presque certain que le signal envoyé sera situé près de la surface de la sphère construite autour du signal reçu, même avec une distance relativement grande. petit rayon d'une telle sphère. Il n’est donc pas surprenant que le signal reçu, après correction d’un nombre arbitrairement grand d’erreurs, nQ, se révèle arbitrairement proche d’un signal sans erreurs. La capacité de liaison dont nous avons parlé plus tôt est la clé pour comprendre ce phénomène. Notez que les sphères similaires construites pour les codes de Hamming de correction d'erreurs ne se chevauchent pas. Le grand nombre de dimensions presque orthogonales dans l’espace à n dimensions montre pourquoi nous pouvons placer M sphères dans l’espace avec peu de chevauchement. Si nous autorisons un petit chevauchement arbitrairement petit, qui peut conduire à seulement un petit nombre d'erreurs lors du décodage, nous pouvons obtenir un placement dense de sphères dans l'espace. Hamming a garanti un certain niveau de correction d'erreur, Shannon - une faible probabilité d'erreur, tout en maintenant le débit réel arbitrairement proche de la capacité du canal de communication, ce que les codes de Hamming ne peuvent pas faire.
La théorie de l’information ne nous dit pas comment concevoir un système efficace, mais elle montre la voie vers des systèmes de communication efficaces. Il s’agit d’un outil précieux pour construire des systèmes de communication de machine à machine, mais, comme indiqué précédemment, il n’a que peu d’impact sur la façon dont les humains communiquent entre eux. On ne sait tout simplement pas dans quelle mesure l’héritage biologique ressemble aux systèmes de communication techniques. Il n’est donc pas clair actuellement comment la théorie de l’information s’applique aux gènes. Nous n’avons pas d’autre choix que d’essayer, et si le succès nous montre la nature mécanique de ce phénomène, alors l’échec mettra en lumière d’autres aspects importants de la nature de l’information.
Ne nous éloignons pas trop. Nous avons vu que toutes les définitions originales, dans une plus ou moins grande mesure, doivent exprimer l'essence de nos croyances originelles, mais elles se caractérisent par un certain degré de distorsion et ne sont donc pas applicables. Il est traditionnellement admis qu’en fin de compte, la définition que nous utilisons définit réellement l’essence ; mais cela nous indique seulement comment traiter les choses et ne nous donne en aucun cas un sens. L’approche postulationnelle, si fortement privilégiée dans les cercles mathématiques, laisse beaucoup à désirer en pratique.
Nous allons maintenant examiner un exemple de tests de QI dont la définition est aussi circulaire que vous le souhaiteriez et, par conséquent, trompeuse. Un test est créé, censé mesurer l’intelligence. Elle est ensuite révisée pour la rendre la plus cohérente possible, puis publiée et, selon une méthode simple, calibrée pour que « l'intelligence » mesurée s'avère être distribuée normalement (sur une courbe de calibration, bien entendu). Toutes les définitions doivent être revérifiées, non seulement lorsqu’elles sont proposées pour la première fois, mais aussi bien plus tard, lorsqu’elles sont utilisées dans les conclusions tirées. Dans quelle mesure les limites définitionnelles sont-elles appropriées au problème à résoudre ? À quelle fréquence les définitions données dans un contexte donné sont-elles appliquées dans des contextes très différents ? Cela arrive assez souvent ! Dans les sciences humaines, que vous rencontrerez inévitablement dans votre vie, cela arrive plus souvent.
Ainsi, un des buts de cette présentation de la théorie de l'information, en plus de démontrer son utilité, était de vous avertir de ce danger, ou de vous montrer exactement comment l'utiliser pour obtenir le résultat souhaité. On sait depuis longtemps que les définitions initiales déterminent ce que l’on trouve finalement, dans une bien plus grande mesure qu’il n’y paraît. Les définitions initiales nécessitent beaucoup d'attention de votre part, non seulement dans toute situation nouvelle, mais également dans les domaines avec lesquels vous travaillez depuis longtemps. Cela vous permettra de comprendre dans quelle mesure les résultats obtenus sont une tautologie et non quelque chose d’utile.
La célèbre histoire d’Eddington raconte l’histoire de gens qui pêchaient en mer avec un filet. Après avoir étudié la taille des poissons qu'ils ont capturés, ils ont déterminé la taille minimale des poissons que l'on trouve dans la mer ! Leur conclusion était motivée par l’instrument utilisé et non par la réalité.
A suivre ...
Qui souhaite aider avec la traduction, la mise en page et la publication du livre - écrivez dans un message personnel ou par e-mail [email protected]
À propos, nous avons également lancé la traduction d'un autre livre sympa - )
Nous recherchons particulièrement ceux qui aideront à traduire . (transfert pendant 10 minutes, les 20 premières ont déjà été prises)
Contenu du livre et chapitres traduits
- Introduction à L'art de faire des sciences et de l'ingénierie : apprendre à apprendre (28 mars 1995)
- "Fondements de la révolution numérique (discrète)" (30 mars 1995)
- "Histoire des ordinateurs - Matériel" (31 mars 1995)
- "Histoire des ordinateurs - Logiciels" (4 avril 1995)
- "Histoire des ordinateurs - Applications" (6 avril 1995)
- "Intelligence artificielle - Partie I" (7 avril 1995)
- "Intelligence artificielle - Partie II" (11 avril 1995)
- "Intelligence artificielle III" (13 avril 1995)
- "Espace n-dimensionnel" (14 avril 1995)
- "Théorie du codage - La représentation de l'information, partie I" (18 avril 1995)
- "Théorie du codage - La représentation de l'information, partie II" (20 avril 1995)
- "Codes de correction d'erreurs" (21 avril 1995)
- "Théorie de l'information" (25 avril 1995)
- "Filtres numériques, partie I" (27 avril 1995)
- "Filtres numériques, partie II" (28 avril 1995)
- "Filtres numériques, partie III" (2 mai 1995)
- "Filtres numériques, partie IV" (4 mai 1995)
- "Simulation, partie I" (5 mai 1995)
- "Simulation, partie II" (9 mai 1995)
- "Simulation, Partie III" (11 mai 1995)
- "Fibre Optique" (12 mai 1995)
- "Instruction assistée par ordinateur" (16 mai 1995)
- "Mathématiques" (18 mai 1995)
- "Mécanique quantique" (19 mai 1995)
- "Créativité" (23 mai 1995). Traduction:
- "Experts" (25 mai 1995)
- "Données peu fiables" (26 mai 1995)
- "Ingénierie des systèmes" (30 mai 1995)
- "Vous obtenez ce que vous mesurez" (1er juin 1995)
- (Juin 2, 1995) traduire en morceaux de 10 minutes
- Hamming, « Vous et vos recherches » (6 juin 1995).
Qui souhaite aider avec la traduction, la mise en page et la publication du livre - écrivez dans un message personnel ou par e-mail [email protected]
Source: habr.com