Le problème du vilain petit canard (ugly duckling problem)

 

Le problème

Ce problème est lié au fait qu'il n'est pas possible de distinguer deux objets lorsque la totalité des caractéristiques disponibles sont prises en compte avec la même importance. Le terme du "vilain petit canard" est repris du conte de Andersen où un bébé cygne est élevé dans une famille de canards, d'abord vilain (du point de vue des canards), le même oiseau devient un cygne "splendide" !

La situation

On imagine un ensemble de n objets distincts caractérisés par m propriétés ou concepts. Chaque objet (document) est donné par un vecteur à m composantes chacune d'elle valant 0 ou 1. Il est possible de considérer jusqu'à n = 2m objets différents. Les m propriétés sont des prédicats qui caractérisent les objets.

Par exemple, si on a m = 2 propriétés, il y a 4 objets différents.

  P1 P2
O1 0 0
O2 0 1
O3 1 0
O4 1 1

Le pas suivant est de considérer l'ensemble des propriétés-prédicats que l'on peut construire avec les m prédicats primitifs (algèbre de Boole "libre" générée par les prédicats). L'ensemble des prédicats compte 2n éléments.

Dans notre exemple, le deuxième prédicat est P1 * P2, le troisième P1 * P2', etc.

  1 2 3 P1 5 P2 7 8 9 10 11 12 13 14 15 16
O1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
O2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
O3 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
O4 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

Etant donné deux objets, le nombre de prédicats qui les différencie est toujours le même (8 dans l'exemple).

Conséquences

Des objets ne peuvent être classés selon l'ensemble de leurs caractéristiques. Il faut introduire des poids ou limiter le nombre de concepts à utiliser pour chaque objets.

Référence

Watanabe, S. (1969). Knowing and Guessing. A quantitative study of inference information. New-York: John Wiley and Sons.

 

(c) A. Favre, A2I & L.-O. Pochon, IRDP, 2000