Trois entropies

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 26 — Apprentissage automatique

Énoncé

Calculer $H (S)$ pour ces trois ensembles d'étiquettes, et dire ce que chaque valeur signifie.

$S_{1}$	quatre exemples, tous « oui »
$S_{2}$	deux « oui » et deux « non »
$S_{3}$	trois « oui » et un « non »

Que se passe-t-il si l'on double la taille de $S_{3}$ en recopiant chaque exemple ?

Corrigé

$H (S_{1}) = - 1 \cdot lo g_{2} 1 = 0$ . Aucun désordre : l'ensemble est homogène, et ID3 en fait une feuille sans poser de question.
$H (S_{2}) = - \frac{1}{2} lo g_{2} \frac{1}{2} - \frac{1}{2} lo g_{2} \frac{1}{2} = 1$ . C'est le maximum en deux classes : une étiquette tirée au hasard demande exactement un bit pour être décrite.
$H (S_{3}) = - \frac{3}{4} lo g_{2} \frac{3}{4} - \frac{1}{4} lo g_{2} \frac{1}{4} = 0, 8113$ .

Recopier chaque exemple ne change rien : $H$ ne dépend que des proportions $p_{c}$ , pas des effectifs. Six « oui » et deux « non » donnent encore $0, 8113$ — vérifié par le calcul. C'est voulu : l'entropie mesure un désordre, non une quantité.

Le piège de la convention. Pour une classe absente, $p_{c} = 0$ et $lo g_{2} 0$ n'existe pas. On pose $0 lo g_{2} 0 = 0$ , ce qui est la limite $lim_{t \to 0^{+}} t lo g_{2} t = 0$ . Un programme qui ne traite pas ce cas rend nan sur le premier ensemble homogène venu, c'est-à-dire sur toutes les feuilles.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.