- Dans ce rapport, nous présentons nos études sur l’entropie conditionnelle et ses applications en apprentissage.. - CHAPITRE 3 : COMPARAISON DES ENTROPIES CONDITIONNELLES. - En informatique, elle intervient dans la théorie de l'information, sous la forme célèbre de l’entropie de Shannon entre autres. - Parmi les premières études sur l’entropie en informatique, on peut citer celles de H. - Depuis, la notion d’entropie est devenue très importante en informatique théorique et appliquée : transmission d'information (codage de source, codage de chaîne, détecteur d’erreur), inférence statistique, cryptographie, algorithmique,…[29].. - Associée à la notion d'entropie, la notion d'entropie conditionnelle représente l’entropie d’un événement sous certaines conditions. - Pour aller plus loin, nous avons l’intention d’étudier des formes généralisées d’entropies conditionnelles : l’entropie conditionnelle est directement définie sur l’ensemble des événements conditionnels.. - Sur le plan théorique, nous avons étudié la particularité de l’entropie conditionnelle de Rényi, de Daroczy par rapport à l’entropie de Coletti et les relations entre l’entropie de Kampé de Fériet, celle de Benvenutti et celle de Coletti.. - Pour cela, plusieurs techniques ont été développées : utiliser l’entropie conditionnelle de Shannon, utiliser une mesure de discrimination [18], utiliser la mesure d’ambiguïté [33. - Pour choisir l’attribut à décomposer, il utilise l’entropie de Shannon. - L’entropie dans ce cas est utilisée comme une mesure du degré de prédictibilité : quelle est la difficulté que l’on a à prédire la classe de l’un des ses éléments ? L’attribut choisi est celui dont la connaissance diminue le plus l’entropie globale.. - Si on partitionne ce sous-ensemble selon l’attribut A j , alors l’entropie du sous-. - est : Et l’entropie globale conditionnellement à A j. - La quantité d’entropie diminuée ou le gain d’information apporté par la connaissance de A j est : I. - L’attribut choisi est celui qui permet le gain d’information le plus important, c'est-à-dire celui qui minimise l’entropie conditionnelle I ( B A j. - I(B|h i ) est calculé selon une formule d’entropie choisie, par exemple l’entropie de Shannon, Rényi ou Daroczy. - On évalue ensuite l’entropie conditionnelle de la base sachant une discrétisation H : I(B|H). - Cela pourrait être réalisé par un choix convenable du nombre d’intervalles et par l’algorithme de discrétisation (l’entropie conditionnelle utilisée par exemple).. - L’entropie de Shannon sert aussi dans la condition d’arrêt : on peut fixer un seuil d’entropie pour arrêter l’algorithme. - Dans le cas où ce seuil est strictement positif, l’algorithme s’arrête si l’entropie de tous les éléments de l’ensemble est inférieure au seuil donné, ainsi l’algorithme est capable de tolérer des données bruitées. - On rappelle que cet algorithme n’entraîne pas obligatoirement un arbre optimal au niveau de la taille, l’utilisation de l’entropie de Shannon ou d’autres entropies n’est qu’une heuristique.. - Il existe dans la littérature certaines entropies et entropies conditionnelles associées comme l’entropie et l’entropie conditionnelle de Rényi, l’entropie et l’entropie conditionnelle de Daroczy. - Elles peuvent servir comme une mesure de discrimination dans la construction d’arbre de décision selon le même principe que l’entropie conditionnelle de Shannon que nous avons décrite. - X = log2 n (comme il ne cause pas d’ambiguïté, dans ce cas, on utilise la même notation I pour l’entropie d’un événement ainsi que l’entropie d’un ensemble).. - a) Définition de l’entropie. - (correspondant à l’entropie de Rényi) et f D β x β β. - (correspondant à l’entropie de Daroczy) où x. - Fig.2 : Entropie de Rényi (normalisée par ln(2)-à gauche) et celle de Daroczy (à droite) dans le cas n=2 avec les différents coefficients β :0.1, 0.3 , 0.5, 0.8, 1, 2, 3, 10, 50, 100. - • β , c’est-à-dire, l’entropie de Rényi après. - la normalisation par ln 2 s’approche de l’entropie de Shannon lorsque β tend vers 1.. - c’est-à-dire que l’entropie de Daroczy. - tend vers l’entropie de Shannon lorsque β tend vers 1. - b) Définition de l’entropie conditionnelle. - À partir des entropies définies ci-dessus, on peut définir l’entropie conditionnelle selon l’une des trois formules suivantes. - En fait, dans la littérature, il existe des formes de type 1[31], de type 2[13], de type 3[1] pour l’entropie conditionnelle de Daroczy et seulement de type 1 pour l’entropie conditionnelle de Rényi [3, 23]. - En principe, on peut aussi combiner l’entropie de Shannon avec les trois types d’entropie conditionnelle ci-dessus.. - c) Définition de l’entropie d’événements flous. - On retourne à l’entropie de Shannon si la partition est ordinaire ou les sous-ensembles X i sont ordinaires. - Traditionnellement, on explique l’entropie comme une mesure de l’incertitude qui sert à mesurer la quantité d’information d’un événement. - Mais pour l’entropie de Shannon, celle de Rényi et celle de Daroczy.. - Donc, on n’a plus besoin de la connaissance de l’entropie inconditionnelle pour définir l’entropie conditionnelle comme d’habitude. - où le côté gauche est l’entropie d’un événement conditionnel [ B A ] et le côté droit est l’entropie conditionnelle de B sachant A selon le sens normal.. - Nous nous intéressons bien à cette approche en espérant qu’elle conduit à une définition d’entropie conditionnelle généralisée. - Comme Coletti a proposé un système d’axiomes, dans le cadre du stage, nous continuons les recherches sur cette idée en vérifiant la compatibilité entre l’entropie conditionnelle de Coletti et les différentes entropies conditionnelles existantes dans la littérature. - lorsque l’on parle de l’entropie conditionnelle de Coletti.. - Chapitre 3 : COMPARAISON DES ENTROPIES CONDITIONNELLES. - Les résultats montrent que pour satisfaire le système d’axiomes de Coletti, l’entropie d’un événement doit avoir la même forme que celle de Shannon si l’on exprime l’entropie d’un événement sous la forme d’une fonction de sa probabilité. - Nous allons démontrer que parmi les formes d’entropies conditionnelles de Rényi et Daroczy, il n’y a que l’entropie conditionnelle de Daroczy de type 2 qui vérifie le troisième axiome.. - La notion d’entropie conditionnelle de Coletti se définit sur un ensemble d’événements conditionnels tandis que Rényi et Daroczy définissent l'entropie et l'entropie conditionnelle d’une distribution probabiliste. - C’est la forme de l’entropie de Shannon. - Donc c’est la forme unique pour l’entropie d’un événement si elle vérifie le système d’axiomes proposé par Coletti. - La deuxième approche est d’essayer de mettre l’entropie conditionnelle de Coletti sous la forme d'une entropie de distribution probabiliste. - La propriété 1 est vérifiée par l’entropie conditionnelle de Rényi et Daroczy : I(E | H). - Entropie conditionnelle de Rényi de type1. - Entropie conditionnelle de Rényi de type2. - Entropie conditionnelle de Rényi de type3. - Entropie conditionnelle de Daroczy de type 1. - Entropie conditionnelle de Daroczy de type 2. - Entropie conditionnelle de Daroczy de type 3. - Entropie et entropie conditionnelle de Shannon. - Comme nous l’avons montré, il y a des études qui conduisent à des définitions d’entropie et d’entropie conditionnelle d’après l’approche axiomatique. - Seules l’entropie et l’entropie conditionnelle de Shannon vérifient totalement le système d’axiomes proposé par Coletti.. - En effet, l’entropie conditionnelle peut être utilisée dans la discrétisation des attributs numériques, le choix du meilleur attribut, le partitionnement de la base d’apprentissage, le critère d’arrêt. - Dans le cadre du stage, nous ne considérons que l’utilisation d’entropie conditionnelle pour le choix du meilleur attribut et pour la discrétisation des attributs numériques.. - Dans l’étape de choix du meilleur attribut, on utilise l’entropie conditionnelle de Shannon. - Nous faisons varier le coefficient β en fixant le type d’entropie conditionnelle utilisé. - 3 : Entropie conditionnelle de Rényi de type2. - 4 : Entropie conditionnelle de Daroczy de type 1. - Remarquons que dans le cas de l’entropie conditionnelle de Rényi de type2, si β est petit (inférieur à un seuil, approximativement égal à 0.95) alors la « couleur » est le meilleur attribut car il donne une entropie conditionnelle plus petite que la « forme. - Dans le cas de l’entropie conditionnelle de Daroczy de type 1, selon la variation de β de 0 à 9, dans le premier intervalle la « forme » est le meilleur attribut, dans l’intervalle suivant, c’est la « couleur » et enfin c’est la « forme ».. - On trouve que l’entropie conditionnelle de Rényi de type2 donne le meilleur taux de bonnes classifications. - En général, l’entropie conditionnelle de Rényi donne de meilleurs taux de bonnes classifications que celle de Daroczy. - La profondeur minimale correspond à l’entropie conditionnelle de Daroczy de type 2.. - Entropie conditionnelle. - taux de bonnes classifications est meilleur lorsqu’on utilise l’entropie conditionnelle de Rényi de type 2.. - Dans les figures suivantes, la ligne horizontale droite correspond à l’entropie conditionnelle de Shannon (l’entropie conditionnelle ne dépend pas de β).. - >10, les courbes, selon l’ordre de haut en bas, correspondent à l’entropie conditionnelle de Daroczy , de Shannon et de Rényi.. - Les courbes correspondant à l’entropie de Rényi et Daroczy sont presque similaires.. - • Pour le degré d’équilibre, il n’y a pas de différence significative entre l’entropie conditionnelle de Rényi de type 2 et celle de Daroczy de type 2 ainsi qu’entre l’entropie conditionnelle de Rényi de type 3 et celle de Daroczy de type 3.. - • Parmi les entropies conditionnelles de type 1, l’entropie conditionnelle de Daroczy conduit à des partitions non équilibrées dans plusieurs cas . - Remarquons que, en apprentissage, il faut choisir l’entropie conditionnelle à appliquer à chaque problème concret. - Les résultats montrent que l’entropie conditionnelle de Shannon vérifie le système d’axiomes de Coletti et l’entropie conditionnelle de Daroczy de type 2 vérifie le premier et le troisième axiome. - Comme nous l’avons annoncé, l’entropie conditionnelle pourrait intervenir dans d’autres étapes du processus de construction d’arbre de décision. - Cette recherche permettra de développer des outils qui donnent aux utilisateurs des recommandations sur le choix de l’entropie à employer en présence de leurs problèmes concrets.. - On utilise l’entropie conditionnelle de Shannon pour le choix du meilleur attribut. - Comme les attributs sont précis, le partitionnement est fait selon les valeurs d’attribut sans intervenir de l’entropie conditionnelle. - Il faut insister sur le fait que, avant mes travaux, le système ne permet de générer des arbres qu'en utilisant l’algorithme ID3 avec l’entropie conditionnelle de Shannon. - y a en fait 3 définitions d’entropie conditionnelle différenciées par les poids. - Par exemple, dans l’algorithme utilisant l’entropie de Rényi, il faut en plus un paramètre réel (β). - Nous trouvons qu’il est préférable de séparer la partie statistique dans DiscriminationID3.java car cette partie est commune à tous les algorithmes lors du calcul d’entropie conditionnelle et qu'elle est relativement indépendante des autres.. - Les entropies conditionnelles utilisées sont l’entropie conditionnelle de Shannon, celle de Rényi et celle de Daroczy.. - Le système permet ainsi de considérer une entropie conditionnelle selon ses paramètres (pour l’entropie de Rényi et celle de Daroczy).. - Le système est divisé suivant les packages suivants : comparaison.data, comparaison.entropie et comparaison.gui. - 15 : Diagramme de classe du package : comparaison.data b) Package comparaison.entropie:. - 16 : Diagramme de classe du package : comparaison.entropie. - Lorsque l’on lance le système, un menu permet à l'utilisateur de choisir le fichier de données, l’entropie conditionnelle, ainsi que les paramètres nécessaires.. - • Entropie conditionnelle de Shannon. - • Entropie conditionnelle de Rényi avec différents coefficients β. - • Entropie conditionnelle de Daroczy avec différents coefficients β. - • Toutes les entropies conditionnelles existantes. - 20 : Résultat de calculs correspondants à toutes les entropies conditionnelles Pour l’étude de la variation de l’entropie conditionnelle selon le coefficient β, il faut cliquer sur le bouton «Variation selon β