EU: Information

INFORMATION THÉORIE DE L'INFORMATION

Écrit par

• Henri ATLAN : professeur émérite de biophysique aux universités de Paris-VI-Pierre-et-Marie-Curie et de Jérusalem, directeur d'études à l'École des hautes études en sciences sociales, Paris, directeur du Centre de recherches en biologie humaine, hôpital Hadassah, Jérusalem (Israël)
• Jean-Paul DELAHAYE : professeur à l'université des sciences et technologies de Lille
• Étienne KLEIN : physicien au Commissariat à l'énergie atomique

Quand on parle d'information, on pense souvent « information ayant une certaine valeur », ou « information pouvant servir à... ». Existe-t-il une théorie générale de l'information ? La théorie de l'information de Shannon (1949) a souvent été présentée comme cette théorie attendue. On admet aujourd'hui que les résultats qui en ont été tirés en biologie ou en informatique ne sont pas à la mesure des ambitions annoncées. Une seconde théorie de l'information, dite théorie algorithmique de l'information et due indépendamment à Andreï Kolmogorov et Gregory Chaitin (1965), se fonde sur la théorie du calcul d'Alan Turing (1936). Nous allons voir que ces deux théories sont liées l'une à l'autre.

Les exemples suivants de suites de caractères contenant de l'information doivent faire réfléchir : (a) la suite des caractères du texte du roman Les Misérables de Victor Hugo ; (b) la liste des emplacements des lance-missiles américains ; (c) une table de logarithmes ; (d) le génome complet d'un virus ; (e) un disque compact avec les concertos pour piano de Chopin ; (f) le programme du traitement de texte utilisé par l'auteur pour écrire cet article, tel qu'il est dans la mémoire de son ordinateur ; (g) le programme de ce même traitement de texte avant qu'il n'ait été compilé, qu'on appelle « programme source ».

Dans chaque cas, il s'agit d'objets possédant un contenu en information et ayant une certaine valeur : ils ont pu être vendus et achetés, on a dépensé de l'argent pour les produire, on continue d'en dépenser pour les conserver. Le contenu brut d'information pour chacun de ces objets est donné par le nombre de bits (éléments de mémoire binaire, 0 ou 1) nécessaires pour enregistrer la chaîne de caractères dans la mémoire d'un ordinateur quand on ne lui fait subir aucun traitement particulier. Le contenu brut d'information d'une chaîne de caractères s de longueur n est n si s ne comporte que des 0 et des 1 et c'est n log m /log 2 si la chaîne comporte des caractères pris parmi m. Dans nos exemples, l'objet ayant le contenu brut d'information le plus grand est le disque compact. Celui ayant le plus de valeur marchande est le programme non compilé de traitement de texte. Celui ayant le moins de valeur aujourd'hui est sans doute la table de logarithmes.

Bien sûr, le contenu brut d'information ne détermine pas la valeur de l'information. La valeur de l'information d'une chaîne de caractères est relative à un certain but et à une certaine situation. Nous noterons Val(s, B) la valeur de l'information contenue dans s relativement au but B. Nous allons découvrir qu'en précisant le but B on obtient différentes théories, dont la théorie de l'information de Shannon et la théorie algorithmique de l'information.

Théorie algorithmique de l'information

Si l'on se fixe pour but de compresser la chaîne de caractères s et si l'on suppose qu'on dispose pour cela d'une machine M, alors la valeur de l'information de s est la longueur du plus petit programme (écrit en binaire) qui, lorsqu'il fonctionne dans M, reconstitue la chaîne s.

La puissance des machines n'est pas sans limite. Dès qu'on a affaire à des machines d'une certaine puissance, leur puissance théorique est la même. C'est là la découverte fondamentale de Turing en 1936 : il y a des mécanismes universels de calcul et n'importe quel ordinateur contemporain est un tel mécanisme universel. Si l'on se donne un mécanisme universel de calcul, la notion de plus petit programme engendrant s ne dépend pas de la machine utilisée, ou plus précisément, ne dépend de cette machine que par une constante additive qu'on peut négliger en première approximation si on traite des suites assez longues. La découverte de ce résultat d'indépendance fonde la théorie algorithmique de l'information.

La notion de valeur de l'information qu'on obtient est particulièrement séduisante. C'est la notion de complexité de Kolmogorov ou de contenu en information de Kolmogorov. Elle correspond à notre définition générale lorsqu'on prend comme but B : [compresser pour la machine universelle M]. Cette notion d'information est sans doute la moins arbitraire de toutes et c'est à elle de préférence que toute théorie générale doit se référer.

Théorie de Shannon

Lorsque le but poursuivi est de transmettre une chaîne de caractère s à un récepteur disposant de la connaissance des fréquences p(i) des lettres de l'alphabet {a1, a2, ..., an}, on définira la valeur en information de s relativement à p(i) et ai, valeur appelée entropie et notée E(s, {p(i)}), par :

But = [transmettre s à un récepteur qui connait les probabilités p(i) des ai]

Val(s,[but]= E(s{p(i)}) = longueur(s)(-Sigma(selon i) log (p(i)

Dans cette conception de l'information, on suppose implicitement que le récepteur est capable de faire certains calculs pour reconstituer s à partir de ce qu'on lui transmet. En définitive, la machine M qui fait le décodage peut être prise comme référence et l'on découvre alors que la théorie de Shannon doit être vue comme une version probabiliste de la théorie algorithmique de l'information. On démontre d'ailleurs que le contenu moyen d'information de Kolmogorov des chaînes de caractères s de longueur n, pondérées par les probabilités résultant des fréquences supposées p(i) pour les ai, K(s, {p(i)}) vérifie la relation : |E(s, {p(i)}) – K(s, {p(i)})| < constante.

La théorie de l'information de Shannon est donc aussi une théorie de l'information par compression, qui, au lieu de considérer des suites quelconques, suppose que les suites qu'on transmet vérifient certaines propriétés statistiques. Finalement, la théorie de Shannon est une théorie du contenu en information relativement à un but de compression et à une certaine distribution statistique des suites. Ce n'est donc pas une théorie de l'information limitée au problème de la transmission, comme on le dit parfois.

La théorie de l'information de Shannon est compatible avec celle de Kolmogorov. Chacune a un rôle à jouer et, par exemple, dans la théorie de la mesure et de l'entropie physique de Wojciech Zurek (1989), c'est le jeu complémentaire des deux théories qui est considéré. Pour Zurek, une situation pour laquelle on dispose de peu d'éléments est assimilée à la situation typique dans l'ensemble des situations compatibles avec ce que l'on sait (utilisation de la théorie de Shannon), puis, au fur et à mesure des précisions qu'on acquiert par des mesures, la théorie de Kolmogorov prend le relais et finit par devenir prépondérante. Valeur de l'information

Dans nos exemples, nous avons envisagé un programme de traitement de texte. Il est clair que la compilation d'un programme source en un programme exécutable crée de l'information de valeur. Le but recherché est double : avoir une forme compacte d'un algorithme rapide réalisant une famille de calculs. Notons que :

• plus le code est rapide plus la compilation possède de valeur ;

• plus le code compilé est compact plus il a de la valeur (aujourd'hui, contrairement à ce qui se passait dans les années 1970, on favorise la rapidité aux dépens de l'espace) ;

• plus nombreux sont les problèmes traités par le programme compilé, plus sa valeur est grande.

La valeur de l'information contenue dans un programme compilé est un mélange de ces trois qualités (rapidité, compacité, variété des problèmes traités), et d'autres encore comme l'originalité, la portabilité, etc. La valeur de l'information d'un programme compilé ne se laisse donc pas réduire à un seul aspect : le contenu en information d'un programme compilé n'est ni l'information algorithmique de Kolmogorov, ni l'information donnée par la théorie de Shannon. De même, si l'on considère que le but poursuivi est de nature pratique, par exemple survivre dans un milieu donné, ou gagner le plus possible d'argent tel jour à la Bourse de Paris, alors la valeur de l'information d'une chaîne de caractères s se mesurera en fonction du but. Une information de grande valeur, ce sera l'endroit où aller chercher tel aliment, ou ce sera le nom de l'action boursière qui va monter. Aucune théorie générale de l'information ne prend en compte tous les aspects pragmatiques déterminant la valeur des chaînes de caractères. Que les théories générales (comme celles de Kolmogorov ou Shannon) puissent jouer des rôles particuliers en physique, en biologie ou ailleurs ne fait pas de doute, mais il faut garder à l'esprit qu'aucune ne constituera jamais la théorie générale de l'information.

— Jean-Paul DELAHAYE

Application à la thermodynamique

La notion de quantité d'information est l'un des concepts de base de la théorie de l'information. Remarquant que son expression mathématique ressemblait à celle que Ludwig Boltzmann avait donnée à la fin du xixe siècle pour l'entropie, Shannon a pressenti que l'on pouvait établir un pont entre la théorie de l'information et la thermodynamique. Afin de comprendre ce lien, souvenons-nous d'abord qu'un morceau de matière, même petit, comprend un si grand nombre de particules qu'on ne peut le décrire à l'échelle microscopique que de façon statistique. Prenons l'exemple d'une épingle d'acier. Elle contient quelque 1019 atomes. La plupart d'entre eux sont des atomes de fer, situés aux nœuds d'un réseau cristallin. Les autres (environ 1 p. 100 du total) sont des atomes de carbone, plus petits, qui s'intercalent en se plaçant dans certains des interstices. L'empilement des atomes de fer n'est pas parfaitement régulier, de sorte que la configuration de l'édifice est caractérisée par la nature et la position des défauts, ainsi que par les emplacements des atomes de carbone. Le nombre de ces configurations défie l'entendement. Déjà, le nombre d'états distincts obtenus en disposant les atomes de carbone de toutes les façons possibles dans un réseau régulier d'atomes de fer nécessiterait, si on voulait l'écrire, pas moins de 1017 chiffres. La connaissance de la configuration précise de notre tête d'épingle est donc hors de portée. En revanche, nous pouvons espérer rendre compte des propriétés, non pas d'un objet spécifique, mais d'échantillons génériques. Ce ne sont plus les particularités d'une certaine tête d'épingle qu'il s'agit alors de décrire, mais les propriétés communes à toutes les têtes d'épingle fabriquées dans les mêmes conditions.

Tous les objets ont alors les mêmes caractéristiques macroscopiques (volume, composition, masse, température), mais la configuration microscopique de chacun d'entre eux reste inconnue. On peut toutefois attribuer une probabilité pn à chacune des très nombreuses configurations compatibles avec les données. En particulier, si rien dans ces données ne nous permet de préférer une configuration à une autre, nous pouvons attribuer à toutes les configurations la même probabilité p. Une fois choisie cette loi de probabilité, il devient possible de répondre à des questions de nature statistique comme celle-ci : comment les distances entre atomes de carbone dans l'acier sont-elles distribuées ? Il arrive même que la loi des grands nombres fournisse des réponses quasi certaines. Ainsi, la petitesse des fluctuations statistiques de la densité d'un matériau comportant un grand nombre de particules explique l'apparence continue de la matière.

Cela n'empêche pas que notre description microscopique des objets demeure fondamentalement incomplète et probabiliste. Toutefois, le caractère partiel de cette connaissance peut être quantifié en prenant appui justement sur la théorie de l'information. Considérons les diverses configurations possibles de notre matériau comme des « messages ». Si toutes ces configurations, en nombre W, sont équiprobables, la probabilité p de chacune d'elles vaut p=1/W. Recevoir un message reviendrait à déterminer complètement la configuration d'un échantillon particulier. La quantité d'information ainsi gagnée serait alors égale, en vertu de la formule de Shannon, à k logW.

Mais nous avons déjà souligné que, en raison de la valeur gigantesque de W, l'observation d'une configuration particulière était hors de portée. Renversons donc notre point de vue : au lieu de considérer des gains d'information impossibles à obtenir, examinons la situation avant toute observation. La quantité I=k logW, qui serait acquise si la détermination complète de l'état microscopique d'un échantillon nous était accessible, peut s'interpréter comme l'information qui nous manque du fait que nous ne savons pas dans quelle configuration précise se trouve l'échantillon. Elle mesure donc l'incertitude qui découle du caractère probabiliste de notre description à l'échelle microscopique. L'expression mathématique qui donne I en fonction de W ressemble – ce n'est pas un hasard – à celle de l'entropie.

— Étienne KLEIN

Information et biologie

Informer consiste à délivrer des indications qui seront utilisables opérationnellement par le destinataire du message. L'étymologie du mot information connote donc ce terme avec des notions telles que « mise en forme », « constitution de contenu », « production de sens », qui ont, depuis Aristote, servi à expliquer les effets génésiques de la reproduction sexuée. De nos jours, l'idée d'information, appliquée à la biologie cellulaire et, ensuite, largement utilisée en génétique moléculaire, n'est-elle encore qu'une simple métaphore ?

De la théorie (Watson et Crick : la double hélice) à la pratique (H. Boyer : les manipulations génétiques), il ressort que l'ADN du noyau cellulaire – et des chromosomes qu'il recèle – a bel et bien les propriétés d'un vecteur d'information au sens de la théorie de Shannon. C'est en effet une molécule séquentiellement définie, autoréplicative et porteuse d'un code permettant la synthèse spécifique des molécules-outils que sont les protéines cellulaires. On a donc l'habitude, en biologie, de parler de molécule porteuse d'information quand on se réfère aux caractéristiques fonctionnelles de l'ADN (acide désoxyribonucléique) et, par extension, à celles de l'ARN (acide ribonucléique). D'après la théorie de l'information de Shannon (1948), les protéines sont également des molécules porteuses d'information puisqu'elles possèdent une structure séquentielle, d'ailleurs codée par celle des ADN. Mais elles sont aussi porteuses d'information au sens de signaux, de par leur structure tridimensionnelle. Or le repliement dans l'espace qui conditionne cette structure n'est pas réductible à la séquence d'acides aminés, donc ne se limite pas au code génétique qui détermine cette séquence, alors que c'est la structure tridimensionnelle qui conditionne l'activité enzymatique des protéines.

Au sens shannonien de la notion d'information, la qualification de porteuses d'information convient parfaitement pour préciser la fonction biologique des molécules d'ADN. Elles ont en effet un rôle fondamental dans la transmission des caractéristiques d'un être vivant. Elles garantissent la pérennité d'une espèce, car elles constituent le génome qui la caractérise. Elles portent, en outre, la marque de l'individu : comme les empreintes digitales, mais au niveau moléculaire, les empreintes génétiques révèlent son identité. Néanmoins, cette fonction déterminante (au sens où les généticiens de la première moitié du xxe siècle l'entendaient) ne peut s'exercer hors de son contexte, à savoir le milieu cellulaire (noyau et cytoplasme) qui renferme l'ensemble des molécules porteuses d'information. C'est lui, et lui seul qui leur donne du sens. En effet, si la théorie de l'information établie par Shannon parvient bien à vérifier qu'une structure linéaire d'ADN – ou de protéine – représente une certaine quantité d'information, parce que la séquence de nucléotides – ou d'acides aminés – dont elle est constituée en permet la mesure (en moyenne chaque nucléotide dans un ADN représente 2 bits d'information), en revanche, l'exploitation de cette information nécessite un équipement moléculaire d'une haute complexité. Il n'est donc pas étonnant que l'information inscrite dans les acides nucléiques ne revête, à elle seule, aucune signification. Elle est une mémoire et non un signal. Mais une extension de la théorie de Shannon (Von Foerster, Atlan) permet de comprendre la possibilité, sous certaines conditions, de création d'information à partir de perturbations aléatoires, telles que mutation et autres (complexité par le bruit), dans les phénomènes d'auto-organisation.

Puisque les molécules d'ADN sont nécessaires mais non suffisantes pour déterminer les structures et les fonctions biologiques, elles ne peuvent, a fortiori, pas davantage constituer un programme, ce qui rend virtuelle la notion de gène. Car une programmation, comme activité dynamique, ne peut être confondue avec un codage statique. C'est dire toute l'importance des phénomènes épigénétiques dans le déroulement du développement biologique de l'individu (ontogenèse) qui construira les formes et les structures de l'organisme vivant, donc son phénotype, à partir des informations contenues dans son génotype, variation individuelle sur le thème collectif du génome de l'espèce que lui ont transmis ses parents.

— Henri ATLAN

Pour citer l’article

Henri ATLAN, Jean-Paul DELAHAYE, Étienne KLEIN, « INFORMATION THÉORIE DE L' », Encyclopædia Universalis [en ligne], consulté le 20 janvier 2022. URL : https://www.universalis.fr/encyclopedie/theorie-de-l-information/

Bibliographie

R. B. Ash, Information Theory, Dover, New York, 1990

H. Atlan, L'Organisation biologique et la théorie de l'information, Hermann, Paris, 1972, 1992, Seuil, Paris, 2006 ; La Fin du tout génétique : vers de nouveaux paradigme en biologie, I.N.R.A. Éditions, Paris, 1999

Le Concept d’information dans la science contemporaine, Actes du 6e Colloque philosophique de Royaumont, 1962, Gauthier-Villars et éd. de Minuit, Paris, 1965

J.-P. Delahaye, Complexités : aux limites des mathématiques et de l’informatique, Bibliothèque Pour la science, Belin, Paris, 2006 ; Information, complexité et hasard, Hermès, Paris, 2e éd. 1999

P. Lyman, H. Varian, J. Dunn, A. Strygin & K. Swearingen, How Much Information ?, School of Information Management and Systems, University of California, Berkeley, 2000 et 2003 (http ://www2.sims.berkeley.edu/research/projects/how-much-info-2003)