vendredi 1 novembre 2013

L'entropie en théorie de l'information

Dans les années 1950, Claude Shannon travaille sur l'information perdue dans une ligne téléphonique à cause des perturbations (celles qui déclenchent les grésillements parasites sur une ligne téléphonique ou les gros pixels sur les télévisions numériques)
Ses travaux, de nature statistique, le mènent à une formulation mathématique de la perte d'information liée au bruit dans les lignes téléphoniques.
Cette formulation, similaire à la formule de Boltzmann en physique statistique, fonde le concept d'entropie d'information, les 2 formules étant quasiment identiques (au signe près).
Il est à noter que le parallèle entre les 2 formules fut découvert plus tard par le mathématicien John Von Neumann (l'inventeur de l'architecture de quasiment tous les ordinateurs modernes) qui lui donna sa dénomination d'entropie d'information.

Voici concrètement la théorie de Shannon:
  • Si une source A d'information envoie toujours le même signal (par exemple un A) alors son entropie est nulle (car le récepteur pourra dire avec une grande fiabilité que le prochain signal émis sera un A). 
  • Si tous les symboles de l'alphabet sont envoyés par la source A de manière statistiquement équiprobable alors son entropie est maximale (Le récepteur ne peut pas prévoir quel est le prochain signal qui va être envoyé)
  • Si l'entropie est non nulle alors elle représente la quantité d'information qui doit être transmise pour que le récepteur la reçoive sans ambiguïté. Plus les symboles sont redondants (C'est à dire plus ils se répètent), plus l'entropie baisse. Exemple: si la source répète tous les mots 3 fois, par exemple "bonjour-bonjour-bonjour" alors le message est redondant (et donc pas très optimal du point de vue de la vitesse de transmission) mais la transmission est fiabilisée car le fait de perdre un "bonjour" à cause du bruit n'empêche pas le récepteur d'interpréter correctement le message. Autrement dit, plus il y a de "bruit" sur la ligne, et plus l'entropie augmente, donc plus le message doit être redondant pour être fiable.
Par exemple, l'apparition d'une lettre dans une phrase d'un énoncé en français n'est pas totalement prévisible (entropie nulle) mais elle n'est pas totalement aléatoire non plus (entropie max) sinon aucune phrase n'aurait de sens.

Par exemple, si je dis:

C'est l'été, il fait un temps m...

La probabilité d'un "x" après ce "m" est d'environ zéro, par contre un "a" ou un "e" ont une bonne probabilité d'apparition, ce qui permet à un programme informatique de deviner en quelle langue est écrit un texte donné. (par exemple, l'apparition des trigrammes "the", "and" et "ing" sont extrêmement fréquents en anglais mais pas en français)

Cette théorie a permis la fiabilisation des transmissions sur les lignes téléphoniques et également donné lieu à plusieurs algorithmes de compression des messages en informatique.

Dans cette théorie, l'entropie représente donc la probabilité de perte d'information mais elle représente également la prévisibilité de la source d'information.
Autrement dit, l'entropie d'un joueur de poker doit être maximale. (on ne doit pas pouvoir prévoir ses actions).
Pour qu'un récepteur puisse comprendre de manière fiable un message malgré le bruit, il faut que ce message soit redondant. Il y a donc un lien entre entropie et redondance et aussi entre entropie et prévisibilité.

L'entropie d'information représente donc le niveau de bruitage et de parasitage de la communication de la source mais également notre incertitude concernant la source d'information.

Le parallèle (pas forcément évident) avec l'entropie physique statistique de Boltzmann qui donne une mesure d'homogénéité est le suivant: 
Si je dépose une goutte d'encre dans un bain, je peux dire au départ avec une bonne probabilité où se trouve l'encre et où se trouve l'eau. 
J'ai donc une assez bonne information sur l'état du système.
Mais après quelque temps, l'entropie augmente et j'ai de plus en plus de mal à percevoir et à prévoir où se trouve l'encre car l'agitation moléculaire diffuse spontanément l'encre dans le bain.
De sorte qu'après un moment, je ne sais plus dire où se trouve l'encre (le liquide est devenu homogène). 
Le liquide mélangé contient donc une information diffuse "noyée" dans le système "eau + encre" que je ne suis plus capable de percevoir... la source n'émet plus cette information... (Il est à noter toutefois que cette information n'a pas disparu: elle n'est simplement plus perceptible par un observateur mais elle continue d'exister au sein du système...)

C'est pour cette raison qu'on dit généralement que l'entropie est une mesure de désordre d'un système: A cause du phénomène de diffusion, l'ordre moléculaire entre l'encre et l'eau ne peut plus être perçu par l'observateur quand toutes les molécules sont mélangées (comme un jeu de carte qu'on aurait mélangé)

Mais en théorie de l'information, l'entropie est plutôt une mesure de notre manque d'information concernant un système, et pas une mesure de désordre.

4 commentaires:

  1. Si j'ai bien tout compris, c'est l'entropie qui s'amuse avec les ragots transmis déformés amplifiés par le téléphone arabe ?
    (Désolée si mes commentaires ne culminent pas au plus haut niveau scientifique...)

    RépondreSupprimer
    Réponses
    1. Tu as bien compris. Mais ça marche en anglais et en français aussi bien qu'en arabe...

      Supprimer
  2. J'ai une question sur le début du post. Tu dis que Shannon a travaillé sur les perturbations sur une ligne A CAUSE DES PERTURBATIONS (qui donne donc les grésillements et autres pixelisation sur écran noir de la TV). On pense notamment aux perturbations électro-magnétiques. Mais Mandelbrot a déterminé dans les années 60 que, même en l'absence de la moindre perturbation, il y avait un "bruit blanc", bref des anomalies de transmission, de nature chaotique.
    Je sais qu'ensuite Mandelbrot a repris les travaux de Shannon et fait une loi avec Zipf (le Z de LZW), un algo de cryptage encore utilisé dans les GIF de nos jours ...
    Bref, bref, je manque de connaissances pour vraiment raconter l'histoire de bout en bout mais si tu te sens ;)

    RépondreSupprimer
    Réponses
    1. En effet, les anomalies de transmissions ne sont pas forcément liées à ces perturbations externes mais simplement à la non-linéarité des phénomènes de transmission. Par contre, pour l'algo Zipf, j'avoue mon ignorance. Mais je vois qu'il y a des très bon articles, je vais m'y pencher de ce pas... :-)

      Supprimer