Le problème des pièces

Présentation
Méthode
Etude du cas à douze pièces
Différents arbres possibles
Analyse des résultats
Comparaison avec le codage de Huffmann
Remarques sur le code
Conclusion

Présentation

Ce projet est réalisé dans le carde du cours de Donald Geman sur le thème "Information et reconnaissance visuelle".

On souhaite résoudre de manière automatique le problème des pièces. On possède pour cela :

En plus, on connait la probabilité qu'il n'y ait aucune fausse pièce et a priori, s'il y a une fausse pièce, il y a une probabilité égale pour chaque pièce qu'elle soit la fausse pièce et une fausse pièce à autant de chances d'être trop lourde que trop légère.

On cherche une stratégie permettant en pesant des groupes de pièce :

Méthode

On procède par réduction progressive d'entropie. L'idée est qu'au départ, on ne connait que peu de choses donc l'incertitude est importante, donc on a une entropie importante. Par contre, si on arrive à résoudre le problème, il n'y aura plus d'incertitude donc l'entropie sera nulle. Et entre ces deux points, chaque pesée va apporter plus ou moins d'information donc faire baisser en conséquence l'entropie. On va donc simplement choisir à chaque étape la pesée qui fait baisser le plus possible l'entropie.

On calcule l'entropie par la formule suivante :  H = - p1 log3 p1 - p2 log3 p2 - ... où pi est la probabilté d'être dans le cas i et log3 le logarithme en base 3 (on choisit 3 car chaque pesée à 3 issues : déséquilibre à gauche ou à droite et équilibre).  A chaque étape, on calcule l'entropie conditionnelle de chaque pesée (i.e. l'espérance de l'entropie après la pesée). Puis on choisit celle qui aboutit à l'entropie la plus faible. Et pour itérer, on envisage les trois résultats de la pesée et dans chaque cas, on cherche à nouveau la pesée qui minimise l'entropie conditionnelle... On arrête de contruire l'arbe quand on aboutit à une situation d'entropie nulle. Il est à noter que par moment, on rencontre des résultats impossibles, i.e. incohérent avec les résultats précédents; dans le déroulement de l'algorithme, ces issues apparaissent comme ayant une probabilité nulle de se produire et donc elles sont simplement mis à l'écart.

On obtient ainsi un arbre ternaire qui représente la succession des pesées dans chacun des cas. Le fils de gauche correspond à l'hypothèse "la balance penche à gauche", celui du milieu à "la balance ne penche pas" et celui de droite à "la balance penche à droite".

Par exemple, l'arbre pour 6 pièces avec certitude d'en avior une fausse (en bleu, les résultats finaux avec "n-" la pièce n est légère , "n+" la pièce n est lourde, "-" aucune pièce n'est fausse; en rouge, les résultats impossibles) :

Etude du cas à douze pièces

On va observer plus particulièrement le cas du problème à douze pièces. Dans un premier temps, on va observer les différents arbres que l'on obtient en fonction de probabilité p0 qu'il n'y est aucune fausse pièce. Ensuite on analysera les caractéristiques de ces différents arbres.

Différents arbres possibles

On trouve quatre arbres différents pour les valeurs de p0 de 0, 0.04, 0.1 et 0.5 .
Sur ces arbres, on a les données suivantes : entropie de la situation initiale, profondeur moyenne de l'arbre et profondeur maximum de l'arbre.
 
p0 
entropie initiale
profondeur moyenne
profondeur maximale
0
2.893
3
3
0.04
2.930
3
3
0.1
2.899
3.075
4
0.5
2.077
2.25
4

 

Analyse des résultats

On peut coder chaque cas par un mot de {G,E,D}* où les lettres codes pour "balance penche à gauche", "équilibre" et "balance penche à droite". Par exemple dans l'arbre p0 = 0.5, le code du cas "10-" est GEG et celui de "6-" est DGEG.

A priori, on peut considérer ce code comme étant acceptable dans le sens où il vérifie bien la relation H <= L < H + 1 où L est la longueur moyenne d'un mot. On voit même que l'on est assez proche du cas d'égalité.

Néanmoins, le cas p0 = 0.1 bien que vérifiant la relation ci-dessus n'appraît pas aussi bon que l'on pourrait le souhaiter. En effet, on a L = 3.075 et on sait que dans le cas p0 = 0.04 par exemple on a une longueur maximale de 3. Quelles que soient les probabilités, on est donc sûr de pouvoir coder tous les cas avec L <= 3 ; simplement en utilisant l'arbre p0 = 0.04 . Dans ce cas, on est sûr de ne pas avoir atteint la longueur minimale du code.

Comparaison avec le codage de Huffmann

Pour les mêmes répartitions de probabilités, on peut calculer les arbres de Huffmann ternaires. Bien évidemment, ici les noeuds internes ne représentent plus des pesées.
 
On peut alors comparer les résultats des Huffmann avec les résultats précédents (en gris) :
 
p0 
entropie initiale
profondeur moyenne
profondeur maximale
profondeur moyenne
profondeur maximale
0
2.893
3
3
2.958
3
0.04
2.930
3
3
2.96
3
0.1
2.899
3.075
4
2.9
3
0.5
2.077
2.25
4
2.188
4

On voit alors que le codage réalise systématiquement mieux que la méthode par réduction d'entropie. Et notamment, on ne dépasse jamais la valeur de 3 pour la longueur moyenne.

Une des raisons qui explique cette différence de "performances" est l'existence de résultats d'impossibilité dans la méthode par réduction d'entropie. En effet ces résultats doivent être représentés dans l'arbre et occupent alors "de la place" inutilement et empêche d'atteindre l'optimum. Cela n'explique pas toutefois que la réduction d'entropie dépasse parfois la valeur 3 pour la longueur moyenne du code induit.

Remarques sur le code

Le programme a été codé en OCamL. Il comporte 3 modules : Generator qui génère toutes les pesées possibles, Entropy qui effectue tous les calculs d'entropie et Tree qui construit l'arbre et l'affiche.

Generator procède en deux étapes. Premièrement, il génère tous les ensembles de cardinal au plus n/2 pièces. Deuxièmement, il calcule toutes les intersections deux à deux des ensembles de même cardinal. Quand l'intersection est vide, il "crée" une pesée car la comparaison est possible entre les deux ensembles.

Entropy contient toutes les routines de calcul de l'entropie. Les probabilités conditionnelles sont calculées directement au cas par cas : par exemple, on sait que pour une pièce qui se trouve dans le plateau le plus lourd ne peut pas être trop légère.

Tree construit l'arbre simplement par un procédé récursif selon la méthode décrite ci-dessus. Ce module contient une implémentation pour construire l'arbre de Huffmann dans les mêmes structures que l'arbre des pesées -- cette implémentation n'est pas optimale et a simplement un objectif de comparaison.

On utilise alors deux exécutables : coins et huffmann dont la syntaxe est coins #pièces p0 et huffmann #pièces p0. A chaque exécutable correspond un makefile.

Télécharger les sources

Conclusion

On a donc ici une méthode assez simple à implémenter qui permet de construire un arbre de décision acceptable dans un certain sens. Toutefois, on sait que l'on ne construit pas nécessairement le meilleur arbre et que le code induit par l'arbre n'est pas optimal.

Sylvain Paris (s.paris@netcourrier.com)