Société des enseignants BULLETIN No 20 / Théorie de l'information |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Quelques aspects élémentaires de la théorie de l'informationL.-O. Pochon, IRDP |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Dans le cadre d'un enseignement par situation-problèmes, on
trouve fréquemment utilisés les problèmes de minimum
de pesées ou le jeu des questions (trouver un élément
inconnu en posant un minimum de questions). Cas par cas, il est souvent
possible de se convaincre de l'aspect optimal des solutions trouvées
par bon sens, intuition et raisonnement ad hoc. Toutefois, il peut apparaître
des doutes sur la solution proposée. La théorie de l'information
fournit un cadre général à ce genre de problèmes
qui permet de lever certaines ambiguïtés.
Ce fait se démontre en utilisant la convexité
de f(x) ou, en deux coups de cuillère à pot, à
l'aide des multiplicateurs de Lagrange.
Cette relation est parfois utilisée pour définir
de H.
Dans cette expression pAi(Bj) représente
la probabilité conditionnelle p(Bj /Ai).
HAi()
est l'entropie de la source sachant que a
produit Ai
H()
= 0 est équivalent à pAi(Bj) = 0 ou
1 i, j, ce qui justifie
dans ce cas de nullité de H(),
l'interprétation suivante: détermine
complètement .
(4)
avec le résultat intuitif que l'égalité
étant d'autant mieux réalisée que les i
sont indépendantes.
L'exemple précédent montre l'intérêt de définir l'apport de concernant l'incertitude de par l'information contenue dans relative à :
L'information apportée par à la détermination de ne peut ni excéder l'information totale (l'incertitude) de ni sa propre information totale. Le jeu des questions Le problème suivant est bien connu:
Une première étape consiste à d'adapter le modèle théorique à cette situation réelle en faisant confiance à un principe d'adéquation. La façon de procéder indiquée, par exemple par Yaglom, est la suivante: on considère l'expérience qui consiste à tirer un nombre parmi 1000. Chaque nombre a autant de chance d'être choisi et donc H() = log 1000 = 9.97. On note (k) = 1 2 ... k une suite de k questions (expériences) à deux issues (réponse oui ou non). En principe on s'arrange pour que H() = 0 mais ce n'est pas obligatoire pour la suite. Pour ces expériences on a: H(i) log 2 et par 7) H((k)) k log 2 = k Pour que (k) détermine entièrement , il faut que H(k) () = 0 (on rappelle que cela signifie de fait une famille de probabilités conditionnelles égales soit à 1 soit à 0). De (8) on tire l'inégalité: log 1000 = H() H((k)) k donc k >= 9.96 et donc k >= 10. Et on voit que cela est possible en 10 questions, en posant la question qui à chaque fois départage en deux les solutions et en rendant les questions indépendantes les unes des autres possibles ("est-ce ce que le nombre pensé est inférieur à 500?", etc.). Dans ce cas un raisonnement direct (ou le bon sens) en dit tout autant et l'apport de la théorie est, dans ce cas, limité. On peut utiliser des interprétations plus parlantes en utilisant la définition de I((k), ) = H() et en passant par elle pour l'inégalité: H() = I((k), ) H((k)) k . Ce qui se lit: l'information apportée à la détermination de par (k), doit être égale à l'incertitude de . Cette information est inférieure à l'entropie de (k). Il faut toutefois noter qu'il n'est pas possible d'utiliser la théorie qu'à moitié et d'imposer directement que H((k)) doit être au moins égal à H() arguant que l'information apportée par (k) doit être supérieur à l'incertitude présentée par . En effet, nul ne nous assure que tous les raisonnements menés à l'aide des signification attribuées vont forcément correspondre aux propriétés formelles liées à la définition de H. Un autre problème est déjà plus intéressant et la solution directe moins évidente:
Il y a 9 (= 3x3) issues à l'expérience de détermination de la ville et de l'origine de l'interlocuteur. Par conséquent le nombre k de questions doit satisfaire l'inégalité: log 9 <= k log 2 = k donc k est au moins égal à 4. On trouve que 4 questions suffisent par exhibition des questions, par exemple: 1) Suis-je dans l'une des villes A ou B? 2) Suis-je dans C? 3) Habitez-vous la ville C? 4) Suis-je dans la ville A? A partir de la réponse à la question 2) on peut savoir si l'interlocuteur provient de C ou non. La question 3) permet dans le premier cas de déterminer l'ordre de l'alternance entre vérité et mensonge et donc la ville où l'on se trouve. Dans le deuxième cas, elle permet de déceler la provenance de l'interlocuteur et si l'on se trouve dans C ou non. Dans ce dernier cas la question 4) permet de trancher entre les villes A et B. (6) Le problème des pesées Une autre famille d'énigmes est donnée par les problèmes des pesées sur une balance à deux plateaux sans l'utilisation de poids auxiliaires.
Dans ce cas l'expérience a 26 (= 2 x 13) issues et donc H() = log 26 = 4.700. Une pesée donne une information au plus égale à log 3. Donc log 26 <= H((k)) <= k log 3 = k et donc k >= (log 26)/log 3 = log3 26 et donc à nouveau k >= 3. Mais dans ce cas on va démontrer que k ne peut pas être égal à 3 en montrant que la deuxième pesée apporte une information trop faible. A nouveau, il est assez facile de voir (2 stratégies) que la première pesée la plus efficace est de mettre 4 pièces sur chaque plateau de la balance. La distribution des probabilités des issues est donnée par [4, 4, 5] et H(1) = 1.577 est très proche de log 3 (1.584). Pour la deuxième pesée on s'intéresse au cas le plus défavorable, c'est-à-dire celui où la pièce différente est parmi les 5 qui n'ont pas fait partie de la première pesée (cas d'équilibre) (7) . On peut passer en revue le nombre de ces pièces que l'on va mettre sur la balance (plateau de gauche, par exmple). Ce nombre peut varier de 1 à 5. Les différentes répartitions des probabilités (penche à gauche, à droite, équilibre) sont les suivantes: [1, 1, 8] [3, 3, 6] [2, 2, 6] [1, 1, 8] [1, 1, 0] auxquelles correspondent les valeurs de l'entropie suivantes: 0.922, 1.414, 1.252, 0.922, 1. La plus forte est 1.414. Ajoutée à celle de la première expérience on a donc au maximum pour information après deux pesées: 2.991 bits. Reste donc au moins une incertitude de 1.71 bits, valeur supérieure à log 3. Une troisième pesée ne pourra donc pas toujours suffire (8). Cet examen nous indique également quelle est la deuxième pesée à effectuer. La solution effective en 4 pesées est laissée au lecteur, de même que la solution en 3 pesées dans le cas où le nombre total de pièces est de 12 seulement (11 "normales" et 1 défectueuse). Cette théorie ne donne qu'une borne inférieure au nombre d'expériences à effectuer. Par contre, le calcul de H peut fournir des heurisitques locales et ne saurait donner une marche à suivre globale. A noter que dans les exemples 3, 4 et 5, le simple dénombrement des réponses suffisait à calculer une borne inférieure raisonnable (équiprobabilité des réponses). L'exemple 6 montre déjà une plus grande complexité. Le cas du "Master mind" offre un autre exemple où la première approximation est trop grossière et où le calcul de la probabilité des réponses (qui peut dépendre de l'issue de ) peut s'avérer délicat. Le cas du "Master mind"
L'expérience a 64 issues, donc H() = log 64 = 6. Par ailleurs, il y a 9 réponses possibles à une question (9). On peut donc estimer H() <= log 9 = 3.16, d'où k >= 6/log 9 >= 1.89 et donc k >= 2. Mais les probabilités des réponses sont très disparates. On peut en tenir compte pour une meilleure estimation de k (et aussi pour imaginer la suite des questions à poser). Dans le tableau ci-dessous on présente la distribution des 9 réponses aux trois types de questions possibles. On voit que la meilleure question est la question 1.3 et que l'information apportée dans ce cas est nettement plus faible que la valeur 3.16 obtenue en supposant les réponses équiprobables. La nouvelle minoration de k est donc 3.
On se contente ici d'étudier la question suivante dans le cas le plus "défavorable" (la question 012 a provoqué la réponse (0,2)): Dans ce cas 15 codes sont encore possibles: 100 101 103 121 123 130 200 203 220 221 230 231 301 320 321. La distribution des réponses est la suivante pour des questions de trois types différents:
Messulan. J. (1978). Jouons au "Master mind" avec un ordinateur. Pentamino, 5, 57-63. Shannon, C. E. & Weawer, W. (1963). The mathematical theory of communication. Urbana: University of Illinois Press. Yaglom, A. M. & Yaglom, I.M. (1969). Probabilité et information. Paris: Dunod. Watanabe, S. (1969) Knowing & Guessing. New York:
John Wiley & Sons. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
(c) L.-O. Pochon & SENS, 1999 |