Gain d’information et information mutuelle pour l’apprentissage automatique

Dernière mise à jour le 10 décembre 2020

Le gain d’information calcule la réduction de l’entropie ou de la surprise de la transformation d’un ensemble de données d’une certaine manière.

Il est couramment utilisé dans la construction d’arbres de décision à partir d’un ensemble de données d’entraînement, en évaluant le gain d’information pour chaque variable, et en sélectionnant la variable qui maximise le gain d’information, qui à son tour minimise l’entropie et divise au mieux l’ensemble de données en groupes pour une classification efficace.

Le gain d’information peut également être utilisé pour la sélection de caractéristiques, en évaluant le gain de chaque variable dans le contexte de la variable cible. Dans cette utilisation légèrement différente, le calcul est appelé information mutuelle entre les deux variables aléatoires.

Dans ce post, vous découvrirez le gain d’information et l’information mutuelle en apprentissage automatique.

Après avoir lu ce post, vous saurez :

• Le gain d’information est la réduction de l’entropie ou de la surprise en transformant un ensemble de données et est souvent utilisé dans la formation des arbres de décision.
• Le gain d’information est calculé en comparant l’entropie de l’ensemble de données avant et après une transformation.
• L’information mutuelle calcule la dépendance statistique entre deux variables et est le nom donné au gain d’information lorsqu’il est appliqué à la sélection de variables.

Démarrez votre projet avec mon nouveau livre Probabilité pour l’apprentissage automatique, comprenant des tutoriels étape par étape et les fichiers de code source Python pour tous les exemples.

Démarrons.

• Mise à jour Nov/2019 : Amélioration de la description des bases de l’info/entropie (merci HR).
• Mise à jour Août/2020 : Ajout des parenthèses manquantes à l’équation (merci David)

Aperçu

Ce tutoriel est divisé en cinq parties ; ce sont :

1. Qu’est-ce que le gain d’information ?
2. Exemple travaillé de calcul du gain d’information
3. Exemples de gain d’information en apprentissage automatique
4. Qu’est-ce que l’information mutuelle ?
5. Comment le gain d’information et l’information mutuelle sont-ils liés ?

Qu’est-ce que le gain d’information ?

Le gain d’information, ou IG pour faire court, mesure la réduction de l’entropie ou de la surprise en divisant un ensemble de données selon une valeur donnée d’une variable aléatoire.

Un gain d’information plus important suggère un groupe ou des groupes d’échantillons à plus faible entropie, et donc moins de surprise.

Vous vous souvenez peut-être que l’information quantifie le degré de surprise d’un événement en bits. Les événements à faible probabilité ont plus d’information, les événements à forte probabilité ont moins d’information. L’entropie quantifie la quantité d’information contenue dans une variable aléatoire, ou plus précisément dans sa distribution de probabilité. Une distribution asymétrique a une faible entropie, tandis qu’une distribution où les événements ont une probabilité égale a une plus grande entropie.

En théorie de l’information, nous aimons décrire la « surprise » d’un événement. Les événements à faible probabilité sont plus surprenants donc ont une plus grande quantité d’information. Alors que les distributions de probabilité où les événements sont de probabilité égale sont plus surprenantes et ont une plus grande entropie.

• Distribution de probabilité oblique (peu surprenante) : Faible entropie.
• Distribution de probabilité équilibrée (surprenante) : entropie élevée.

Pour en savoir plus sur les bases de l’information et de l’entropie, consultez le tutoriel :

• Une douce introduction à l’entropie de l’information

Maintenant, considérons l’entropie d’un ensemble de données.

Nous pouvons penser à l’entropie d’un ensemble de données en termes de distribution de probabilité des observations dans l’ensemble de données appartenant à une classe ou à une autre, par exemple deux classes dans le cas d’un ensemble de données de classification binaire.

Une interprétation de l’entropie à partir de la théorie de l’information est qu’elle spécifie le nombre minimum de bits d’information nécessaires pour coder la classification d’un membre arbitraire de S (c’est-à-dire, un membre de S tiré au hasard avec une probabilité uniforme).

– Page 58, Machine Learning, 1997.

Par exemple, dans un problème de classification binaire (deux classes), nous pouvons calculer l’entropie de l’échantillon de données comme suit:

• Entropie = -(p(0) * log(P(0)) + p(1) * log(P(1)))

Un ensemble de données avec une répartition 50/50 des échantillons pour les deux classes aurait une entropie maximale (surprise maximale) de 1 bit, tandis qu’un ensemble de données déséquilibré avec une répartition de 10/90 aurait une entropie plus petite car il y aurait moins de surprise pour un exemple tiré au hasard dans l’ensemble de données.

Nous pouvons démontrer cela avec un exemple de calcul de l’entropie pour cet ensemble de données déséquilibré en Python. L’exemple complet est repris ci-dessous.

En exécutant l’exemple, nous pouvons voir que l’entropie du jeu de données pour la classification binaire est inférieure à 1 bit. C’est-à-dire que moins d’un bit d’information est nécessaire pour coder l’étiquette de classe pour un exemple arbitraire de l’ensemble de données.

De cette façon, l’entropie peut être utilisée comme un calcul de la pureté d’un ensemble de données, par ex.p. ex. à quel point la distribution des classes se trouve être équilibrée.

Une entropie de 0 bit indique un ensemble de données contenant une seule classe ; une entropie de 1 ou plus suggère une entropie maximale pour un ensemble de données équilibré (selon le nombre de classes), les valeurs intermédiaires indiquant des niveaux entre ces extrêmes.

Le gain d’information fournit un moyen d’utiliser l’entropie pour calculer comment une modification de l’ensemble de données a un impact sur la pureté de l’ensemble de données, p. ex. la distribution des classes. Une entropie plus petite suggère plus de pureté ou moins de surprise.

… le gain d’information, est simplement la réduction attendue de l’entropie causée par le partitionnement des exemples selon cet attribut.

– Page 57, Machine Learning, 1997.

Par exemple, nous pouvons souhaiter évaluer l’impact sur la pureté en divisant un ensemble de données S par une variable aléatoire avec une gamme de valeurs.

Cela peut être calculé comme suit :

• IG(S, a) = H(S) – H(S | a)

Où IG(S, a) est l’information pour l’ensemble de données S pour la variable a pour une variable aléatoire, H(S) est l’entropie pour l’ensemble de données avant tout changement (décrit ci-dessus) et H(S | a) est l’entropie conditionnelle pour l’ensemble de données étant donné la variable a.

Ce calcul décrit le gain dans l’ensemble de données S pour la variable a. C’est le nombre de bits économisés lors de la transformation de l’ensemble de données.

L’entropie conditionnelle peut être calculée en divisant l’ensemble de données en groupes pour chaque valeur observée de a et en calculant la somme du rapport des exemples dans chaque groupe sur l’ensemble de données entier multiplié par l’entropie de chaque groupe.

• H(S | a) = somme v dans un Sa(v)/S * H(Sa(v))

Où Sa(v)/S est le rapport du nombre d’exemples dans l’ensemble de données avec la variable a a la valeur v, et H(Sa(v)) est l’entropie du groupe d’échantillons où la variable a a la valeur v.

Cela peut sembler un peu confus.

Nous pouvons rendre le calcul du gain d’information concret avec un exemple travaillé.

Vous voulez apprendre les probabilités pour l’apprentissage automatique

Prenez mon cours intensif gratuit de 7 jours par courriel maintenant (avec un exemple de code).

Cliquez pour vous inscrire et obtenir également une version Ebook PDF gratuite du cours.

Téléchargez votre mini-cours GRATUIT

Exemple travaillé de calcul du gain d’information

Dans cette section, nous allons concrétiser le calcul du gain d’information avec un exemple travaillé.

Nous pouvons définir une fonction pour calculer l’entropie d’un groupe d’échantillons en fonction du rapport entre les échantillons qui appartiennent à la classe 0 et à la classe 1.

Maintenant, considérons un ensemble de données avec 20 exemples, 13 pour la classe 0 et 7 pour la classe 1. Nous pouvons calculer l’entropie pour cet ensemble de données, qui aura moins de 1 bit.

Envisageons maintenant qu’une des variables de l’ensemble de données a deux valeurs uniques, disons « valeur1 » et « valeur2 ». Nous sommes intéressés par le calcul du gain d’information de cette variable.

Supposons que si nous divisons l’ensemble de données par valeur1, nous avons un groupe de huit échantillons, sept pour la classe 0 et un pour la classe 1. Nous pouvons alors calculer l’entropie de ce groupe d’échantillons.

Maintenant, supposons que nous divisons l’ensemble de données par la valeur2 ; nous avons un groupe de 12 échantillons avec six dans chaque groupe. Nous nous attendrions à ce que ce groupe ait une entropie de 1.

Enfin, nous pouvons calculer le gain d’information pour cette variable en fonction des groupes créés pour chaque valeur de la variable et de l’entropie calculée.

La première variable a donné lieu à un groupe de huit exemples de l’ensemble de données, et le deuxième groupe avait les 12 échantillons restants dans l’ensemble de données. Par conséquent, nous avons tout ce dont nous avons besoin pour calculer le gain d’information.

Dans ce cas, le gain d’information peut être calculé comme:

• Entropie(Ensemble de données) – (Compte(Groupe1) / Compte(Ensemble de données) * Entropie(Groupe1) + Compte(Groupe2) / Compte(Ensemble de données) * Entropie(Groupe2))

Ou :

• Entropie(13/20, 7/20) – (8/20 * Entropie(7/8, 1/8) + 12/20 * Entropie(6/12, 6/12))

Or en code :

En reliant tout cela, l’exemple complet est listé ci-dessous.

D’abord, l’entropie de l’ensemble de données est calculée à un peu moins de 1 bit. Ensuite, l’entropie du premier et du deuxième groupe est calculée à environ 0,5 et 1 bit respectivement.

Enfin, le gain d’information pour la variable est calculé à 0,117 bit. C’est-à-dire que le gain pour l’ensemble de données en le divisant via la variable choisie est de 0,117 bits.

Exemples de gain d’information dans l’apprentissage automatique

Peut-être que l’utilisation la plus populaire du gain d’information dans l’apprentissage automatique est dans les arbres de décision.

Un exemple est l’algorithme Iterative Dichotomiser 3, ou ID3 pour faire court, utilisé pour construire un arbre de décision.

Le gain d’information est précisément la mesure utilisée par ID3 pour sélectionner le meilleur attribut à chaque étape de la croissance de l’arbre.

– Page 58, Machine Learning, 1997.

Le gain d’information est calculé pour chaque variable de l’ensemble de données. La variable qui a le plus grand gain d’information est sélectionnée pour diviser l’ensemble de données. Généralement, un gain plus grand indique une plus petite entropie ou moins de surprise.

Notez que minimiser l’entropie est équivalent à maximiser le gain d’information…

– Page 547, Machine Learning : A Probabilistic Perspective, 2012.

Le processus est ensuite répété sur chaque groupe créé, en excluant la variable qui a déjà été choisie. Cela s’arrête une fois qu’une profondeur souhaitée de l’arbre de décision est atteinte ou qu’aucune autre division n’est possible.

Le processus de sélection d’un nouvel attribut et de partition des exemples d’entraînement est maintenant répété pour chaque nœud descendant non terminal, cette fois en utilisant uniquement les exemples d’entraînement associés à ce nœud. Les attributs qui ont été incorporés plus haut dans l’arbre sont exclus, de sorte qu’un attribut donné peut apparaître au plus une fois le long de n’importe quel chemin dans l’arbre.

– Page 60, Machine Learning, 1997.

Le gain d’information peut être utilisé comme critère de partition dans la plupart des implémentations modernes des arbres de décision, comme l’implémentation de l’algorithme CART (Classification and Regression Tree) dans la bibliothèque d’apprentissage automatique scikit-learn Python dans la classe DecisionTreeClassifier pour la classification.

Cela peut être réalisé en définissant l’argument de critère à « entropie » lors de la configuration du modèle ; par exemple :

Le gain d’information peut également être utilisé pour la sélection des caractéristiques avant la modélisation.

Il s’agit de calculer le gain d’information entre la variable cible et chaque variable d’entrée dans le jeu de données d’apprentissage. L’atelier d’apprentissage automatique Weka fournit une mise en œuvre du gain d’information pour la sélection de caractéristiques via la classe InfoGainAttributeEval.

Dans ce contexte de sélection de caractéristiques, le gain d’information peut être appelé « information mutuelle » et calculer la dépendance statistique entre deux variables. Un exemple d’utilisation du gain d’information (information mutuelle) pour la sélection de caractéristiques est la fonction scikit-learn mutual_info_classif().

Qu’est-ce que l’information mutuelle ?

L’information mutuelle est calculée entre deux variables et mesure la réduction de l’incertitude pour une variable étant donné une valeur connue de l’autre variable.

Une quantité appelée information mutuelle mesure la quantité d’information que l’on peut obtenir d’une variable aléatoire étant donné une autre.

– Page 310, Data Mining : Outils et techniques pratiques d’apprentissage automatique, 4e édition, 2016.

L’information mutuelle entre deux variables aléatoires X et Y peut être énoncée formellement comme suit :

• I(X ; Y) = H(X) – H(X | Y)

Où I(X ; Y) est l’information mutuelle pour X et Y, H(X) est l’entropie pour X et H(X | Y) est l’entropie conditionnelle pour X étant donné Y. Le résultat a pour unité les bits.

L’information mutuelle est une mesure de dépendance ou « dépendance mutuelle » entre deux variables aléatoires. En tant que telle, la mesure est symétrique, ce qui signifie que I(X ; Y) = I(Y ; X).

Elle mesure la réduction moyenne de l’incertitude sur x qui résulte de l’apprentissage de la valeur de y ; ou vice versa, la quantité moyenne d’information que x transmet sur y.

– Page 139, Théorie de l’information, inférence et algorithmes d’apprentissage, 2003.

La divergence de Kullback-Leibler, ou KL, est une mesure qui calcule la différence entre deux distributions de probabilité.

L’information mutuelle peut également être calculée comme la divergence de KL entre la distribution de probabilité conjointe et le produit des probabilités marginales de chaque variable.

Si les variables ne sont pas indépendantes, on peut avoir une idée de si elles sont « proches » d’être indépendantes en considérant la divergence de Kullback-Leibler entre la distribution conjointe et le produit des marginales qui est appelé l’information mutuelle entre les variables

– Page 57, Pattern Recognition and Machine Learning, 2006.

Cela peut être énoncé formellement comme suit :

• I(X ; Y) = KL(p(X, Y) || p(X) * p(Y))

L’information mutuelle est toujours supérieure ou égale à zéro, où plus la valeur est grande, plus la relation entre les deux variables est importante. Si le résultat calculé est égal à zéro, alors les variables sont indépendantes.

L’information mutuelle est souvent utilisée comme une forme générale d’un coefficient de corrélation, par exemple une mesure de la dépendance entre des variables aléatoires.

Elle est également utilisée comme un aspect dans certains algorithmes d’apprentissage automatique. Un exemple courant est l’analyse en composantes indépendantes, ou ICA pour faire court, qui fournit une projection des composantes statistiquement indépendantes d’un ensemble de données.

Comment le gain d’information et l’information mutuelle sont-ils liés ?

L’information mutuelle et le gain d’information sont la même chose, bien que le contexte ou l’utilisation de la mesure donne souvent lieu à des noms différents.

Par exemple :

• Effet des transformations sur un ensemble de données (arbres de décision) : Gain d’information.
• Dépendance entre les variables (sélection de caractéristiques) : Information mutuelle.

Notez la similitude entre la façon de calculer l’information mutuelle et la façon de calculer le gain d’information ; elles sont équivalentes :

• I(X ; Y) = H(X) – H(X | Y)

et

• IG(S, a) = H(S) – H(S | a)

Ainsi, l’information mutuelle est parfois utilisée comme synonyme de gain d’information. Techniquement, ils calculent la même quantité s’ils sont appliqués aux mêmes données.

On peut comprendre la relation entre les deux comme suit : plus la différence entre les distributions de probabilité conjointe et marginale (information mutuelle) est grande, plus le gain d’information est important (gain d’information).

Lectures complémentaires

Cette section fournit plus de ressources sur le sujet si vous cherchez à approfondir.

Livres

• Théorie de l’information, inférence et algorithmes d’apprentissage, 2003.
• Apprentissage automatique : A Probabilistic Perspective, 2012.
• Reconnaissance des formes et apprentissage automatique, 2006.
• Apprentissage automatique, 1997.
• Data Mining : Practical Machine Learning Tools and Techniques, 4e édition, 2016.

API

• scipy.stats.entropy API

Articles

• Entropie (théorie de l’information), Wikipédia.
• Gain d’information dans les arbres de décision, Wikipédia.
• Algorithme ID3, Wikipédia.
• Ratio de gain d’information, Wikipédia.
• Information mutuelle, Wikipédia.

Résumé

Dans ce billet, vous avez découvert le gain d’information et l’information mutuelle dans l’apprentissage automatique.

Spécifiquement, vous avez appris :

• Le gain d’information est la réduction de l’entropie ou de la surprise par la transformation d’un ensemble de données et est souvent utilisé dans l’entraînement des arbres de décision.
• Le gain d’information est calculé en comparant l’entropie de l’ensemble de données avant et après une transformation.
• L’information mutuelle calcule la dépendance statistique entre deux variables et est le nom donné au gain d’information lorsqu’il est appliqué à la sélection de variables.

Avez-vous des questions ?
Posez vos questions dans les commentaires ci-dessous et je ferai de mon mieux pour y répondre.