Théorie de l'information et créationnisme : Théorie de l'information classique (Shannon)

Dans cet article

• Claude Shannon et la théorie classique de l'information
• Sources d'information
• Information, entropie et incertitude
• Entropie conditionnelle et jointe
• Implications pour la communication
• Information et bruit
• Entropie de Shannon vs. entropie thermodynamique
• Liens

Claude Shannon et la théorie classique de l'information[Sommaire]

La communication numérique moderne dépend de la théorie de l'information, qui a été inventée dans les années 1940 par Claude E. Shannon. Shannon a d'abord publié A Mathematical Theory of Communication en 1947-1948, et a publié conjointement The Mathematical Theory of Communciation avec Warren Weaver en 1949. Ce texte est toujours en publication chez l'University of Illinois Press. La théorie de l'information, parfois appelée Théorie classique de l'information par opposition à la Théorie algorithmique de l'information, fournit un modèle mathématique pour la communication. Bien que Shannon ait été principalement préoccupé par le problème des communications électroniques, la théorie a une applicabilité beaucoup plus large. La communication se produit chaque fois que des choses sont copiées ou déplacées d'un endroit et/ou d'un moment à un autre.

Cet article décrit brièvement les concepts principaux de la théorie de Shannon. Les démonstrations mathématiques sont facilement disponibles dans de nombreuses sources, y compris les liens Internet de cette page. Bien que la théorie de Shannon couvre à la fois la communication numérique et analogique, la communication analogique sera ignorée pour simplifier. D'un autre côté, la théorie de l'information est un sujet assez technique, généralement introduit aux étudiants en ingénierie de troisième année d'université. Pour vraiment la comprendre, il faut des connaissances en statistiques et en calcul.

Pour ceux qui se demandent comment une théorie sur la communication peut éventuellement se rapporter à l'évolution biologique, une visite du site web de Tom Schneider, Théorie de l'information moléculaire et la théorie des machines moléculaires, peut aider. Dans tous les cas, les créationnistes sont maintenant friands de débattre de l'information, et cet article fournit des matériaux de fond utiles sur le sujet.

Informations Sources[Haut]

Une source d'information est un système qui émet à partir d'un ensemble fixe de M symboles {a_1..a_M} dans une séquence à un certain taux (voir Fig.1). Dans le cas le plus simple, chaque symbole qui pourrait être émis par le système est également probable. La lettre i représentera un symbole de sortie donné de l'ensemble {a_1..a_M}. Si tous les symboles sont également probables, alors la probabilité que le symbole i soit celui qui est produit est p_i=P=¹/_M quelle que soit la symbolique que nous avons en tête. Par exemple, si la source d'information peut produire quatre symboles également probables (A, B, C et D), alors chaque symbole a une probabilité de .25 (c'est-à-dire 25 % ou 1/4).

Fig. 1. Source d'information et observateur

Un observateur est incertain quant à quel symbole parmi les M sera émis. Une fois qu'un symbole donné a_i est observé, l'observateur a obtenu de l'information de la source. L'incertitude de l'observateur est réduite. La quantité d'information obtenue peut être mesurée car le nombre de symboles possibles est connu. Par définition, la mesure de l'information I observée à partir du système est donnée par :

I = log₂ M=-log₂P,

et l'unité de mesure est les chiffres binaires, ou bits. L'unité de mesure dépend de la base du logarithme. La plupart du temps, la théorie de l'information utilise le logarithme en base 2 (log₂). Toute autre base de logarithme fonctionnerait. Si nous utilisions la base 10, alors l'unité de mesure serait les chiffres décimaux.

Si un système peut produire l'un des 16 symboles possibles, pour chaque symbole observé, l'observateur reçoit 4 bits d'information. C'est-à-dire qu'il réduit l'incertitude de l'observateur de 4 bits (voir Fig.2). L'utilisation d'un logarithme pour mesurer l'information est due à Ralph V.L. Hartley, dont le papier de 1928 est cité par Shannon.

Fig. 2. L'un des 16 Symboles Possibles est Observé

Il est facile de voir l'utilité de cette définition. Lorsqu'une source d'information capable de produire l'un des 128 symboles ASCII de base, tous également probables, génère un symbole, l'observateur obtient 7 bits d'information, exactement le nombre de bits utilisés pour encoder l'ensemble des symboles ASCII de base. (ASCII signifie American Standard Code for Information Interchange, utilisé depuis de nombreuses années dans les machines à écrire et les ordinateurs. Bien sûr, une source d'information ASCII réelle ne produit pas 128 symboles également probables, mais pour simplifier, nous allons supposer qu'elle le fait pour l'instant.)

Fig. 3. Système de communication

Shannon décrit un système de communication comme une source d'information, émetteur, canal, récepteur et destination (voir Fig. 3). La destination est notre observateur. Une exigence fondamentale pour un système de communication est que, avec une grande fiabilité, le symbole à la source d'information et le symbole à la destination coïncident. Shannon a eu une percée clé à ce sujet : ce n'est pas important que le symbole ait un sens. Ce qui compte, c'est uniquement que le symbole à la source d'information et à la destination soient identiques. C'est cette percée, le sens doit être ignoré, qui a permis à Shannon de créer un modèle mathématique fonctionnel pour l'information.

Ensuite, considérez que les symboles émis par une source d'information ne sont pas nécessairement équiprobables. Supposons que les symboles {a_1..a_M} apparaissent avec des probabilités p₁..p_M. Puisque {a_1..a_M} sont tous les symboles possibles, la somme des probabilités p_i pour tous les i est égale à 1. Étant donné que l'observateur ne sait pas quel sera le prochain symbole de la séquence de sortie, la source d'information est traitée comme un processus stochastique. Autrement dit, nous supposons que les symboles émis sont aléatoires, apparaissant avec les probabilités données.

Un exemple simple d'un processus stochastique est une personne lançant une pièce à répétition (voir Fig.4). Les résultats sont parfois pile et parfois face, mais nous ne pouvons pas prédire les résultats pour un lancer donné de la pièce. Nous supposons, bien sûr, que la pièce est une pièce équitable, qui a une probabilité de 50 % d'être pile et une probabilité de 50 % d'être face lorsqu'elle est lancée. Si nous enregistrions la séquence de lancers de pièces, elle pourrait ressembler à HHTHTHHTHTTTTHTHHT...

Fig. 4. Un processus stochastique simple

Le concept suivant nécessaire est une machine à états finis. Il s'agit d'une sorte de machine qui possède un nombre fini de conditions ou d'états dans lesquels elle peut se trouver à un instant donné. Un interrupteur, par exemple, possède deux états : ON et OFF. Une machine à états finis n'a pas besoin d'exister physiquement. Elle peut simplement être un modèle mathématique sur papier ou dans un ordinateur. L'état de la machine peut être enregistré au fil du temps, produisant une séquence tout à fait analogue à celle du lancer de pièce. Si nous enregistrions la position d'un interrupteur dans la chambre d'un enfant hyperactif toutes les 15 minutes, cela pourrait même sembler plutôt aléatoire, comme ON - ON - OFF - ON - OFF - ON - ON - OFF - ON - OFF - OFF - OFF - OFF - ON - OFF - ON - ON - OFF..., tout comme le lancer d'une pièce.

Nous pouvons maintenant modéliser une source d'information comme une sorte de machine à états aléatoire, sautant d'un état à l'autre, chaque état correspondant au symbole de sortie suivant. Nous pouvons toujours exprimer l'information reçue en observant le symbole i en fonction de sa probabilité :

I_i=-log₂p_i

Penser à la source d'information de cette manière, il est raisonnable de supposer que la probabilité de son état suivant dépend de son état actuel. Par exemple, un interrupteur de lumière dans la chambre d'un octogénaire sédentaire ne changerait probablement pas beaucoup toutes les 15 minutes : ON - ON - ON - ON - ON - ON - OFF - OFF - OFF - OFF...

Considérons une seule transition d'état. Notre machine à états peut passer de l'état i à l'état j. Cette transition d'état a une certaine probabilité. Nous pouvons décrire la probabilité que j suive i comme p(j|i). La notation p(j|i) se lit à voix haute comme « la probabilité de j sachant i ». Si vous lisez l'article de Shannon, notez qu'il utilise une notation moins conventionnelle p_i(j) plutôt que p(j|i).

Pour simplifier les choses, nous ne laisserons pas notre machine à états se souvenir de l'état qu'elle occupait précédemment. Elle ne connaît que l'état dans lequel elle se trouve actuellement. Cela signifie que la probabilité de son prochain état ne peut dépendre que de l'état actuel. Elle ne peut pas dépendre de la manière dont la machine est arrivée dans l'état actuel. Si nous examinons ensuite toutes les transitions d'états possibles pour la machine, nous pouvons écrire l'ensemble des probabilités de transition d'état. Pour chaque symbole i, la somme de tous les p(j|i) sur j est égale à 1. L'ensemble des probabilités de transition d'état pour notre interrupteur est :

{ p(ON|ON), p(ON |OFF), p(OFF|ON), p(OFF|OFF) }

Il est facile de voir que p(ON|ON) + p(OFF|ON) = 1, et également que p(ON|OFF) + p(OFF|OFF) = 1.

Un processus stochastique de ce type, où la distribution de probabilité de l'état suivant dépend de l'état actuel mais de rien d'autre, est appelé un processus de Markov discret. Shannon représente les sources d'information comme des processus de Markov discrets. Autrement dit, la source d'information est supposée être un processus aléatoire, produisant une séquence de symboles à partir d'un ensemble de symboles fixe, où la probabilité de chaque nouveau symbole dépend uniquement du symbole précédent. La machine à états ne peut rien se souvenir d'avant cela.

Un processus ergodique est une classe particulière de processus de Markov. Pour un processus ergodique, chaque séquence qu'il peut produire possède les mêmes propriétés statistiques. Si la source d'information est ergodique, alors la probabilité que le symbole j apparaisse après N symboles, P_j(N), converge vers une valeur d'équilibre lorsque N devient de plus en plus grand. Shannon fait une hypothèse générale selon laquelle les sources d'information sont des processus ergodiques.

Information, Entropie et Incertitude[Haut]

Rappelez-vous que l'observateur commence par être complètement incertain quant à la séquence de symboles qui sera produite par la source d'information. À mesure que chaque symbole est observé, l'incertitude diminue. Nous pouvons représenter la source d'information comme une variable aléatoire, car son état peut correspondre à n'importe quelle valeur de l'ensemble des symboles, et nous l'appellerons X, tout comme Shannon. La variable aléatoire X peut produire l'un des M symboles {a_1..a_M}. Chaque l'un de ces symboles a une probabilité p₁ .. p_M, et ces probabilités doivent toutes additionner à 1.

Les informations reçues de X lorsqu'il produit un symbole i sont

I_X=-log₂p_i

L'entropie de X est définie par son information moyenne:

H(X) = E{I_X}=-∑ _i(p_ilog₂p _i)

La notation E{I_X} désigne la valeur attendue de I_X, qui est un terme plus spécifique en statistiques que « moyenne ». L'entropie peut également être appelée incertitude moyenne (strictement parlant, la réduction moyenne de l'incertitude pour un récepteur).

Pourquoi l'entropie de l'information est-elle définie comme cette somme pondérée de probabilités ? Principalement parce que les probabilités associées aux symboles ne sont pas, en général, égales. Considérez les 26 lettres de l'alphabet anglais. Comme l'a noté Shannon, la lettre « E » se produit plus fréquemment que « Q », la séquence « TH » plus que « XP », etc. En définissant l'entropie comme l'information moyenne, elle nous dira quelque chose sur la manière dont un canal de communication est utilisé.

La fonction d'entropie H(X) est maximale lorsque p_i=¹/_M pour tous i. Cela a du sens intuitif, car l'incertitude est la plus grande lorsque tous les résultats sont également probables. D'un autre côté, si une source d'information produit le symbole a₁ avec une probabilité de 0,999 et dix autres symboles a₂..a₁₁ chacun avec une probabilité de 0,0001, nous sommes presque certains que le prochain symbole sera a₁.

Fig. 5. Entropie d'une source binaire

Considérez une source d'information binaire capable de produire des symboles 0 et 1. Son entropie en fonction de la probabilité p₁ du symbole 1 est illustrée sur Fig.5. (Rappelez-vous que p₀₌1-p₁ car il n'y a que deux symboles autorisés et que leurs probabilités doivent somme à 1). Notez que l'entropie atteint un maximum de 1 lorsque p₁=p₀=1/2. Lorsque les deux symboles sont également probables, l'observateur est le plus incertain. La séquence de piles ou de faces issues de plusieurs lancers d'une pièce équitable, par exemple, possède une entropie maximale. D'un autre côté, si la source d'information produisait toujours le symbole 1 avec une probabilité p₁=1, l'entropie et l'incertitude de l'observateur seraient nulles. Si la source d'information ne produisait jamais le symbole 1 mais produisait toujours le symbole 0, l'entropie et l'incertitude de l'observateur seraient également nulles. Aucune information n'est gagnée en observant un événement connu pour ne jamais changer.

Entropie conditionnelle et conjointe[Haut]

Si X et Y sont des variables aléatoires représentant respectivement l'entrée et la sortie d'un canal, alors l' entropie conditionnelle (c'est-à-dire l'incertitude moyenne du symbole reçu sachant que X a été transmis) est :

H(Y|X)=-∑_i,j p(x_i,y_j)log₂ p(y_j|x_i),

l'entropie conjointe (signifiant l'incertitude moyenne du système d'information total) est :

H(X,Y)=-∑_i,j p(x_i,y_j)log₂ p(x_i,y_j),

et l'entropie d'équivoque (c'est-à-dire l'incertitude moyenne du symbole transmis après réception d'un symbole) est :

H(X|Y)=-∑_i,j p(x_i,y_j)log₂ p(x_i|y_j).

La notation p(A,B) signifie la probabilité que A et B se produisent tous les deux, tandis que p(A|B) signifie la probabilité que A se produise sachant que B s'est produit.

Une relation importante est :

H(X,Y)=H(X|Y)+ H(Y)=H(Y|X)+H( X).

Implications pour la communication[Haut]

Shannon a démontré que, pour un canal de capacité C et une source d'information d'entropie H, il est possible de transmettre la sortie codée de la source d'information à travers le canal à un débit moyen allant jusqu'à (^C/_H) -e, où e est un nombre arbitrairement petit. Il n'est pas possible de transmettre à un débit moyen supérieur à ^C/_H.

Shannon et R.M. Fano ont développé indépendamment une méthode d'encodage efficace, connue sous le nom de technique de Shannon-Fano, dans laquelle la longueur du mot de code augmente avec la diminution de la probabilité du symbole de source ou du mot de source. L'idée de base est que les symboles fréquemment utilisés (comme la lettre E) doivent être codés plus court que les symboles peu fréquemment utilisés (comme la lettre Z) pour utiliser au mieux le canal, contrairement au codage ASCII où E et Z nécessitent tous les deux sept bits.

Si une communication se produit avec une entrée X et une sortie Y, la capacité d'un canal est :

C = Max ( H(X) - H(X | Y) )

La fonction Max(H) signifie la valeur maximale de H. Pour un canal sans bruit, H(X|Y)=0. Puisque H(X) est maximale lorsque les M symboles possibles pour X sont également probables, C=log₂M, ou C=I(X).

Shannon a également fourni les fondements mathématiques pour la transmission sur un canal bruité (voir Fig.6). Un canal bruité peut être considéré comme connecté à deux processus stochastiques : la source d'information et la source de bruit.

Fig. 6. Système de communication avec bruit

Si X est la source d'information et Y l'information reçue, alors en utilisant un nouveau canal (un canal de correction) dont la capacité est égale à l'entropie conditionnelle H(Y|X), il est possible de coder les données de correction de manière à ce que toutes les erreurs sauf une fraction arbitrairement petite e puissent être corrigées (voir Fig.7). Si l'entropie de la source d'information H ≤C, alors la source d'information peut être transmise avec un taux d'erreur arbitrairement faible. Si H>C, alors aucune méthode de codage n'est possible de telle sorte que l'équivocation soit inférieure à H-C.

Fig. 7. Encodage pour réduire les erreurs dues au bruit

Il existe de nombreux exemples dans la littérature de codes de correction d'erreurs. Parmi les plus connus figurent les codes de Hamming, Reed-Solomon, Viterbi et Fire.

Information et Bruit [Sommaire]

Un point important à garder à l'esprit est que la source d'information et la source de bruit sur Fig. 6 et Fig. 7 sont des processus stochastiques. Elles pourraient toutes deux être traitées comme des sources d'information. La principale différence entre elles est que le récepteur s'intéresse à la source d'information et souhaite ignorer la source de bruit.

Dans certaines situations, une source de bruit est observée intentionnellement, dans ce cas elle devient une source d'information. D'un autre côté, parfois, l'information est copiée involontairement d'un canal vers un autre. Cela s'appelle le bruit croisé, et son résultat est qu'une source d'information peu intéressante d'autrui est considérée comme du bruit.

Lorsque les scientifiques mesurent le rayonnement cosmique de fond pour l'étudier, il s'agit d'information. Les interférences dans un système de communication dues au rayonnement cosmique de fond constituent du bruit. Les données d'altitude du terrain peuvent être considérées comme aléatoires. Si vous les enregistrez pour créer une carte topographique, il s'agit d'information. Si vous souhaitez mesurer le diamètre d'une planète, il s'agit de bruit. Ce concept, selon lequel l'information d'une personne est le bruit d'une autre personne et vice-versa, est couramment mal compris dans les discussions laïques sur la théorie de l'information. Pour réitérer, c'est l'intérêt de l'observateur qui transforme un processus stochastique en source d'information.

Certains créationnistes soutiendront que le bruit dégrade l'information tout comme la deuxième loi de la thermodynamique dégrade l'ordre, et suggéreront que la deuxième loi s'applique à l'information. Mais pour la définition de l'information de Shannon, puisque nous ne nous soucions pas du sens, et que la différence entre l'information et le bruit dépend uniquement de notre intérêt, cet argument ne tient pas debout. Nous transformons le bruit en information simplement en décidant de nous en soucier, et l'information en bruit en choisissant de l'ignorer. De plus, l'ordre thermodynamique porte sur l'arrangement des molécules et d'objets similaires, et non sur des symboles mathématiques, donc leur argument est doublement faux. Les symboles d'information sont des abstractions mathématiques et n'ont pas besoin de se comporter comme un système physique particulier (tel qu'une collection de molécules), comme on le verra dans la section suivante.

Certains créationnistes soutiennent également l'existence d'une Loi de conservation de l'information, similaire à la première loi de la thermodynamique. Nous devons nous rappeler que la conservation de l'énergie est un principe établi par plus de 150 ans de collecte scrupuleuse de données, et qu'il n'y a aucune rigueur derrière la notion de conservation de l'information. Dans tous les cas, selon la définition de l'information de Shannon, cette loi proposée est du non-sens. Tout ce dont vous avez besoin pour créer de l'information est un processus ergodique et un observateur pour le regarder. La désintégration atomique fournit un exemple physique simple. Un observateur de la désintégration atomique obtient de nouvelles informations (quel atome, quel moment, quels produits) à chaque désintégration d'un atome.

Entropie de Shannon vs. Entropie thermodynamique[Haut]

La fonction d'entropie informationnelle de Shannon a exactement la même forme que l'équation du théorème H de Boltzmann :

H(t) = ∫f ln f dc

où ∫ est le symbole d'intégration du calcul, ln signifie logarithme naturel (base e), f est la fonction de distribution pour les molécules dans un gaz idéal, et c est l'espace des vitesses. Le symbole H est utilisé en théorie de l'information en raison de cette similitude.

Intéressamment, le mouvement brownien (le mouvement thermique aléatoire des molécules) est également un processus de Markov. C'est à partir de la formule H(t) que nous pouvons déduire :

S = k ln w

où S est l'entropie thermodynamique d'un système, k est la constante de Boltzmann, et w est le désordre du système ; c'est-à-dire la probabilité qu'un système existe dans l'état où il se trouve par rapport à tous les états possibles dans lesquels il pourrait se trouver. Le théorème H de Boltzmann nous dit qu'après un long temps, f atteindra l'équilibre. Cela est similaire à ce que Shannon nous dit sur les sources d'information modélisées comme des processus ergodiques. Malgré les similitudes, l'entropie de Shannon et l'entropie thermodynamique ne sont pas les mêmes. L'entropie thermodynamique caractérise un ensemble statistique d'états moléculaires, tandis que l'entropie de Shannon caractérise un ensemble statistique de messages.

En thermodynamique, l'entropie concerne toutes les façons dont les molécules ou les particules peuvent être arrangées, et une entropie plus élevée signifie que moins de travail physique peut être extrait du système. Dans l'usage de Shannon, l'entropie concerne toutes les façons dont les messages peuvent être transmis par une source d'information, et une entropie plus élevée signifie que les messages sont plus également probables. L'entropie en théorie de l'information ne signifie pas que l'information devient plus inutile ou dégradée ; et parce qu'il s'agit d'une abstraction mathématique, elle ne se rapporte pas directement au travail physique sauf si vous traitez les molécules de manière informatique.

L'entropie de Shannon a été liée par le physicien Léon Brillouin à un concept parfois appelé négentropie. Ce terme a été introduit par le physicien et lauréat du prix Nobel Erwin Schrödinger dans son texte de 1944 Qu'est-ce que la vie pour expliquer comment les systèmes vivants exportent l'entropie vers leur environnement tout en maintenant leur propre entropie basse ; en d'autres termes, il s'agit de l'opposé de l'entropie. Dans son livre de 1962 Science et théorie de l'information, Brillouin a décrit le principe de la négentropie de l'information ou NPI, dont l'essentiel est que l'acquisition d'informations sur les micro-états d'un système est associée à une diminution de l'entropie (il faut du travail pour extraire de l'information, l'effacement entraîne une augmentation de l'entropie thermodynamique). Il n'y a aucune violation de la deuxième loi de la thermodynamique impliquée, car une réduction de l'entropie thermodynamique d'un système local entraîne une augmentation de l'entropie thermodynamique ailleurs.

La relation entre l'entropie informationnelle de Shannon H et l'entropie S de la mécanique statistique a été établie de manière plus rigoureuse par Edwin Jaynes en 1957. Le résultat est que l'entropie informationnelle et l'entropie thermodynamique sont des mesures étroitement liées, mais ne sont pas la même mesure. Pour la plupart des praticiens de la théorie de l'information jusqu'à présent, cela ne pose aucun problème, car leur domaine est la communication et le calcul utilisant des circuits électroniques conventionnels où la signification thermodynamique de l'entropie n'est pas discutée. Cependant, la terminologie conflictuelle entraîne beaucoup de confusion dans des domaines comme les machines moléculaires et la physique du calcul, où l'entropie informationnelle et l'entropie thermodynamique sont traitées côte à côte. Certains auteurs, comme Tom Schneider, plaident pour l'abandon du mot entropie pour la fonction H de la théorie de l'information et l'utilisation de l'autre terme de Shannon, incertitude (surprise moyenne), à la place. Pour en savoir plus, consultez L'information n'est pas l'entropie, l'information n'est pas l'incertitude !

Contrairement à l'entropie moléculaire, l'entropie de Shannon peut être localement réduite sans fournir d'énergie au système d'information. Le simple fait de passer un canal à travers un filtre passif peut réduire l'entropie de l'information transmise (sans que l'émetteur s'en rende compte, la capacité du canal est réduite, et donc l'entropie de l'information sur le canal également). La quantité de puissance nécessaire à la transmission est la même, que le filtre soit présent ou non, et que l'entropie de l'information soit réduite ou non. Une autre façon de concevoir cela est de couper un fil d'un canal comportant plusieurs fils parallèles. L'information moyenne traversant le canal, l'entropie, diminue, sans rapport avec la quantité d'énergie nécessaire pour couper le fil. Ou bien, coupez l'alimentation électrique d'une source d'information et observez sa sortie se figer sur un seul symbole « hors tension » avec une probabilité de 1 et une entropie d'information de 0.

Un mot de prudence concernant la notation : pour ceux qui sont familiers avec la thermodynamique chimique, H dans la théorie classique de l'information n'est pas l'enthalpie, et les deux sujets ne doivent pas être confondus. De même, le H dans la théorie classique de l'information mesure une propriété différente de celle du H dans la théorie algorithmique de l'information. Bien que ces conflits de notation puissent être regrettables, toute la littérature est rédigée ainsi et toute personne souhaitant comprendre la théorie de l'information devra simplement s'y habituer.

[Haut]