Théories et théorie de l’information

Dans la suite de ce document, nous nous focaliserons sur le sens précis que prend ce terme dans le contexte de l’informatique fondamentale, et tenterons de répondre à la question : « Peut-on établir une théorie générale de l’information ? »

Claude Shannon.
Photo © Alcatel-Lucent/Bell Labs.

Il existe une première théorie de l’information, due à Claude Shannon et Warren Weaver dès 1949, présentée en français par Léon Brillouin en 1959. C’est une théorie mathématique qui formalise l’information et sa transmission de manière probabiliste. Cependant, lorsqu’on a voulu parler précisément de l’information génétique, dans les années 1970, on a essayé d’établir des liens avec cette théorie mathématique ; les résultats n’ont pas été à la mesure des espoirs et des ambitions annoncées. De même, alors qu’à un moment on a pu penser que la théorie de l’information de Shannon allait être « la théorie de l’informatique », on a vite découvert qu’il n’en était rien. En effet, la théorie de Shannon est une théorie du contenu en information relativement à des objectifs comme celui de compresser ou transmettre une information à travers un canal. Elle est relative à des distributions de probabilité ; elle est finalement indépendante des données elles-mêmes. Elle ne dit rien sur une donnée particulière, mais sur la moyenne d’un ensemble de données, comme nous le préciserons plus loin.

Une autre théorie de l’information, dite « théorie algorithmique de l’information » ou « théorie de l’information de Kolmogorov », est alors apparue, proposée par Andreï Kolmogorov en 1965. Nous allons voir de quelle façon ces deux théories sont liées l’une à l’autre, et quelles sont les limitations tant de l’une que de l’autre.

Problème général des théories de l’information

Supposons que nous disposions d’une suite de symboles s, qui forme une chaîne de caractères.

Nous pouvons porter peu ou beaucoup d’intérêt à ces symboles, trouver du sens ou non à leur enchaînement. Indépendamment de ces éléments externes, qu’entendons-nous lorsque nous parlons de son contenu en information ou de sa valeur en information ?

Voici quelques exemples très concrets de suites de symboles auxquelles nous reconnaissons un contenu et une valeur en information :

• la suite des caractères composant l’Introduction à la Psychanalyse de Freud ;
• la liste dactylographiée des emplacements des lance-missiles américains dans le monde ;
• une table de logarithmes ;
• le génome complet d’un virus HIV du Sida ;
• un disque compact avec les concertos pour piano de Chopin interprétés par Samson François ;
• le programme du traitement de texte utilisé pour taper ce texte tel qu’il est inscrit dans la mémoire de mon ordinateur ;
• le programme de ce même traitement de texte avant qu’il n’ait été compilé, qu’on appelle « programme source » (en règle générale, l’éditeur du logiciel ne le diffuse pas).

Ces exemples correspondent à des objets ayant, ou ayant eu à un moment donné, un contenu en information d’une certaine valeur pour celui qui les a produits et très certainement pour d’autres personnes. À titre d’exemple, nous pouvons attribuer à ces objets un prix, une valeur marchande.

Accordons qu’il y a un contenu brut d’information pour chacun de ces objets. Ce contenu brut est donné en digits (ou bits) et on peut le définir comme le nombre de mémoires élémentaires que la chaîne s occupe dans la mémoire d’un ordinateur quand on ne lui fait subir aucun traitement particulier autre que la mise sous un format compatible avec le système de l’ordinateur.

Le contenu brut d’information d’une chaîne de caractères s de longueur n est donné par 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, au lieu de pris parmi 2.

Parmi nos exemples, l’objet ayant le contenu brut d’information le plus grand est le disque compact, celui ayant le plus petit contenu brut d’information est la liste des emplacements des lance-missiles. 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 la table de logarithmes.

Il est clair à partir de ces exemples que le contenu brut en information ne détermine pas la valeur de l’information : la valeur d’une information est quelque chose de plus compliqué et surtout qui prend un sens différent selon le contexte. Cela explique d’ailleurs pourquoi il y a plusieurs théories de l’information. Selon le sens que nous donnons au mot information, il faut formaliser le concept différemment.

Nous adopterons donc la procédure suivante : nous nous fixerons tout d’abord un but, puis nous déterminerons la valeur de l’information de la chaîne de caractères s relativement à ce but. Nous allons ainsi découvrir qu’en précisant le but, on obtient différentes théories, dont la théorie de l’information de Shannon et la théorie algorithmique de l’information, citées précédemment.

La théorie algorithmique de l’information

Si on se fixe le but de pouvoir fabriquer la chaîne de caractères s, et si 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’on le donne à M, lui permet de reconstituer la chaîne s. La valeur en information, c’est ce contenu incompressible de s. On parle de compression, puisque nous remplaçons la chaîne de caractères s par quelque chose de plus court, le plus petit programme qui la génère. (Par exemple la chaîne « papapapapapapapapapapapapapapapapapapapa … papapapapapapapapapa » sera compressée en « recopie N fois ‘pa’ »).

L’idée ici est simple : un message s est pauvre en information s’il est généré par un programme informatique rudimentaire, et riche en information si seuls des programmes sophistiqués, donc de grande taille, peuvent produire ce message.

Andreï Kolmogorov.
Source : Wikipédia.

Il se trouve que la puissance de calcul des machines n’est pas sans limites. Elles peuvent aller plus ou moins vite, mais dès qu’on a affaire à des machines d’une certaine puissance, ce qu’elles peuvent calculer est le maximum de ce que n’importe quelle machine puissante peut calculer. C’est là la découverte fondamentale de Turing en 1936 : il y a des mécanismes universels de calcul et n’importe quel micro-ordinateur constitue un tel mécanisme universel. Pourvu donc qu’on se donne un mécanisme de calcul universel, la notion de plus petit programme pouvant engendrer s ne dépend pas de la machine universelle qu’on utilise. Ou plus précisément, elle 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 suffisamment longues. C’est la découverte de ce résultat d’indépendance, ou théorème d’invariance, qui fonde la théorie algorithmique de l’information.

La notion de valeur en information qu’on obtient est particulièrement séduisante. C’est la notion de complexité de Kolmogorov ou de contenu en information de Kolmogorov.

Les complexités descriptionnelles

On peut considérer des mécanismes de calcul plus limités, par exemple ne servant pas à coder toutes les suites finies possibles mais seulement une certaine famille d’entre elles, ou ne disposant que d’une quantité limitée de mémoire, ou devant travailler en temps proportionnel à la taille de s, etc.

Détaillons un exemple. Si je ne souhaite que compresser le contenu en information des 500 chaînes de caractères que constituent les 500 livres de ma bibliothèque, je peux imaginer une machine spécialement adaptée à ce travail, qui pour chaque nombre entier n entre 0 et 499 produise le livre numéro n de ma bibliothèque. Le contenu en information d’un livre de ma bibliothèque est alors simplement le nombre n (plus précisément log₂(n)), et c’est effectivement le contenu brut de la chaîne de caractères que je dois transmettre à un ami présent dans ma bibliothèque, et à qui je parle au téléphone, pour qu’il accède à un certain livre que je veux lui conseiller.

Bien sûr, dans cet exemple, la machine de compression est tout sauf universelle, et c’est bien pour cela que cette notion limitée de valeur d’une information est moins intéressante que la notion de valeur d’une information que donne la théorie de l’information de Kolmogorov.

Nous parlerons de complexité descriptionnelle ou de contenu descriptionnel en information d’une chaîne de caractères s, lorsque nous ne supposerons pas que M est une machine universelle, et nous réserverons le terme de complexité de Kolmogorov ou de contenu en information de Kolmogorov lorsque M sera supposée universelle.

La notion d’information de Kolmogorov est sans doute la moins arbitraire de toutes les définitions générales de contenu en information (grâce au théorème d’invariance évoqué plus haut), et c’est à elle sans doute que toute théorie générale doit se référer de préférence. Il faut cependant garder à l’esprit qu’elle ne peut s’appliquer qu’à des situations où un grand nombre de chaînes de caractères (et si possible assez longues) sont présentes.

Une difficulté supplémentaire de la théorie de l’information de Kolmogorov est son lien avec les théorèmes d’indécidabilité de Gödel. Décompresser une suite de caractères s se fait sans problème : il suffit de faire fonctionner M. En revanche, compresser une suite de caractères s, c’est-à-dire trouver le plus court programme pour M qui redonne s, ne peut se faire qu’à la limite, c’est-à-dire comme résultat d’un calcul infini de M. On ne peut pas espérer mieux, puisque la fonction qui donne la complexité de Kolmogorov d’une chaîne s en fonction de s n’est pas une fonction récursive, et que déterminer la complexité d’une chaîne de caractères s constitue, dans tout système formel donné S, un problème indécidable, sauf pour des chaînes s d’une complexité inférieure à une constante c(S) dépendant de S.

Le rôle théorique particulier joué par la théorie de Kolmogorov, en tant que théorie optimale du contenu descriptionnel de l’information, commence à être reconnu par les biologistes et les physiciens. En physique, le concept d’information est difficile à identifier, malgré des liens souvent évoqués avec la thermodynamique, liens qui semblent avoir subi une refonte de première importance très récemment grâce aux travaux de Bennett et Zurek. Quant à la biologie, elle cumule toutes les difficultés, car de toute évidence un sens pragmatique doit être attribué au concept d’information biologique, qui rend inadéquates ou incomplètes les théories mathématiques de l’information et peu probable l’utilité des théories thermodynamiques de l’information. Face à ces problèmes difficiles, la notion de complexité ou de contenu en information de Kolmogorov offre un nouvel outil théorique.

La théorie de l’information de Shannon

Si le but poursuivi est de transmettre une chaîne de caractère s à un récepteur disposant de certaines connaissances sur la fréquence des lettres (prises dans l’alphabet {a₁, a₂, …, a_n}) de la chaîne de caractères s que l’on souhaite transmettre, alors on utilisera une autre définition de l’information, celle découlant théorie de l’information de Shannon.

Cette formulation donne le contenu moyen d’information de l’ensemble des chaînes de caractères s quand on tient compte des probabilités p(i) des lettres utilisées. Le « théorème de la voie sans bruit » indique que l’on ne peut pas en moyenne compresser plus les chaînes de caractères s.

Implicitement, dans cette conception de l’information, on suppose que le récepteur est susceptible de faire certains calculs pour reconstituer s à partir de ce qu’on lui transmet. Implicitement donc, on suppose un certain pouvoir de calcul du récepteur. En définitive, la machine M qui fait le décodage peut être prise comme référence, et 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 et compatible avec elle dans le sens suivant :
le contenu algorithmique moyen d’information de Kolmogorov des chaînes de caractères de longueur n (pondérées par les probabilités résultant des fréquences supposées p(i) pour les lettres a_i) est du même ordre de grandeur que le contenu en information au sens de Shannon.

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 à cause du fait qu’elle ne s’occupe que du problème de la transmission, comme on le dit parfois, c’est une théorie de l’information probabiliste compatible avec la théorie algorithmique de l’information et limitée simplement parce qu’elle est relative à des distributions probabilistes particulières.

De ce fait, parler de l’information de Shannon du génome de tel être vivant précis n’a pas de sens, car ce génome est une chaîne unique : l’approcher par le contenu incompressible moyen de l’ensemble des chaînes auxquelles elle appartient peut conduire à une erreur grossière. Autre exemple, si une chaîne de dix millions de 0 est vue comme un élément particulier de l’ensemble de toutes les chaînes de dix millions de 0 et de 1 (0 et 1 munis de poids égaux), on lui attribuera un contenu d’information de dix millions de bits, ce qui est absurde, car une telle suite peut être décrite avec quelques bits (c’est d’ailleurs ce que je viens de faire). Une telle suite n’est pas un élément « typique » de l’ensemble de toutes les suites de dix millions de 0 et de 1.

La théorie de l’information de Shannon est compatible avec celle de Kolmogorov. Chacune a son rôle à jouer, par exemple dans une théorie de la mesure ou de la prise d’information. C’est le jeu complémentaire des deux théories qui doit être considéré. Une situation sur laquelle on dispose de peu d’éléments ne peut être qu’assimilée à la situation typique de l’ensemble des situations compatibles avec ce que l’on sait, on utilise donc la théorie de Shannon. Puis, au fur et à mesure des précisions qu’on acquiert, c’est la théorie de Kolmogorov qui doit devenir prépondérante.

Toutes les théories que nous venons de présenter sont des théories « compressionnelles » (ou « descriptionnelles ») de l’information. Compresser des données est certes important pour les stocker à moindre coût, ou les transmettre au plus vite, mais il est bien clair que ce n’est pas cela uniquement qui constitue la valeur d’une information. On sait par exemple qu’une suite tirée au hasard de 0 et de 1 est le plus souvent incompressible, mais cela ne signifie pas bien sûr que chaque suite de 0 et de 1 a de la valeur, ni que chaque suite de 0 ou de 1 est incompressible.

La notion de profondeur logique de Bennett

Une autre insuffisance frappante des théories descriptionnelles de l’information apparaît quand on considère la suite des cent premiers millions de chiffres binaires de Pi, qui a une complexité de Kolmogorov assez petite (car il y a des algorithmes courts qui la génèrent). Ce qui fait la valeur de cette suite — et on a dépensé beaucoup d’argent pour la calculer — comme ce qui faisait la valeur des tables de logarithmes d’autrefois, c’est qu’une telle suite représente une quantité importante de calculs. La notion de profondeur logique proposée par Charles Bennett en 1988 prend en compte cet aspect du contenu en information.

Si on poursuit l’objectif de limiter au maximum le nombre de pas de calculs qu’on doit faire pour retrouver s, alors la « valeur en information de la suite s » sera le nombre minimum de pas de calculs qu’il faut pour produire s.

La théorie de Bennett définit la profondeur logique d’une suite s par le temps de calcul qu’il faut à une machine universelle M pour produire s à partir de sa description minimale. Bennett montre que cette notion est robuste, c’est-à-dire qu’elle dépend relativement peu de la machine universelle qu’on se donne. Là encore, on a une définition très séduisante de la valeur en information d’une chaîne de caractères. Cette théorie est appelée à jouer un rôle important en physique, en biologie et dans d’autres disciplines, puisqu’elle donne une autre mesure de la complexité (ici en temps de calcul) d’une information.

Théories pragmatiques de l’information

Parmi nos exemples, nous avons considéré 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.

Là le but est mixte : avoir une forme compacte d’un algorithme assez rapide réalisant une famille de calculs. Notons que :

• plus le code est rapide, plus la compilation a de la valeur ;
• plus le code compilé est compact, plus il a de la valeur (aujourd’hui, contrairement à ce qui se passait il y a 30 ans, on préfère favoriser la rapidité aux dépens de l’espace, car le prix des mémoires a baissé) ;
• 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é, champ des problèmes traités), et d’autres encore comme l’originalité, la portabilité, etc. La valeur de l’information d’un programme compilé (et de bien des chaînes de caractères) ne se laisse pas réduire à un seul aspect : le contenu en information d’un programme compilé, ce n’est ni l’information algorithmique de Kolmogorov, ni l’information donnée par la théorie de Shannon, ni l’information-profondeur de Bennett.

Si 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 de ce 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. Là encore, les théories descriptionnelles de l’information seront de peu d’utilité.

Ces théories mathématiques concernant l’information, qu’elles soient disponibles ou qu’elles s’élaborent encore, ont des prétentions à l’universalité et à l’applicabilité. Mais il convient de se méfier. Elles sont parfois mal assimilées : celle de Shannon a engendré beaucoup de discours dont aujourd’hui on comprend qu’ils étaient insuffisamment prudents ; celle de Kolmogorov semble parfois aussi induire en erreur. Mais l’attitude de prudence à préconiser vis-à-vis de ces théories n’implique pas la stérilité : souvenons-nous en effet de Jacques Monod qui, ressentant sans doute que tout n’était pas clair du côté des théories physiques de l’information, parlait à propos de ce qu’on leur faisait dire « de généralisations et d’assimilations imprudentes ». Monod, ce grand scientifique qui découvrit l’ARN messager et révolutionna la biologie moléculaire, était prudent. Avec instinct, il se méfiait des spéculations trop hâtives, et pourtant son travail ne fut pas stérile ! En ces domaines risqués, à vouloir aller trop vite on risque de ne pas tout voir ; comme de plus, ainsi que nous l’avons montré ici, beaucoup d’idées très intéressantes ont été avancées ces dernières années, il serait dommage de passer à côté d’elles parce qu’on fonce la tête baissée.

Ce texte est une version condensée et adaptée par l’auteur du premier chapitre de son livre Information, complexité et hasard, Éditions Hermès, Paris, seconde édition, 1999.