Aller au contenu

1NSI : TD Entropie de Shannon⚓︎

Introduction⚓︎

En Physique, L'Entropie (de Boltzmann), est un paramètre (un nombre) qui mesure le degré de désordre/ d'imprédictibilité du contenu au niveau microscopique d'un Système Physique (par ex. en Thermodynamique Statistique). Plus l'entropie du système est élevée, moins ses éléments sont ordonnés, liés entre eux, capables de produire des effets mécaniques.

En Informatique, plus spécifiquement en Théorie de l'Information, l'Entropie (de Shannon) correspond à la quantité d'information contenue ou délivrée par une source d'information (un texte écrit dans une langue donnée, un signal électrique, un fichier informatique)

Entropie⚓︎

Notations⚓︎

On se donne une phrase/séquence (sans prendre en considération les espaces, ni les tirets, ni les apostrophes) :

phrase ="DIDON DINA DIT-ON DU DOS D'UN DODU DINDON"

On se donne également :

  • un Alphabet \(A=\{a_1;a_2;..;a_n\}\) des lettres utilisées dans la phrase
  • Une langue parlée (Français 🇫🇷, Anglais 🇬🇧, Ukrainien 🇺🇦, etc..)
  • Des probabilités \(0\leq p_i \leq 1\) de chaque lettre \(a_i\) de l'Alphabet, de sorte que \(\displaystyle \sum_{i=1}^{n} p_i=1\).

Remarque

On peut considérer qu'une lettre appartenant à alphabet \(A\), mais qui n'existe pas dans la phrase étudiée admet une probabilité nulle (\(p_i=0\)) d'apparition : Au niveau des calculs de probablités (on ajoute une probabilité \(p_i=0\)), cela revient à considérer que cette lettre n'appartient pas à l'Alphabet \(A\) (donc la négliger pour l'étude de la phrase donnée).

Définition⚓︎

On dit que l'Entropie (Binaire) de la phrase \(X\) est calculée par la Formule:

\(\displaystyle H(X)= \sum_{i=1}^{n} p_i log_2 \left( \frac 1{p_i} \right)\)

avec :

  • Si \(p_i=0\), alors on convient que : \(\displaystyle p_i log_2 \left( \frac 1{p_i} \right)=0\)

  • \(n\) est (donc) le nombre de caractères distincts existant réellement dans la phrase

Remarque

Encore une fois, on peut considérer qu'une lettre appartenant à l'Alphabet \(A\), mais qui n'existe pas dans la phrase étudiée admet une entropie nulle (\(p_i log_2 (\frac {1}{p_i})\) ) : Au niveau des calculs d'entropie (on ajoute une entropie \(p_i log_2( \frac {1}{p_i})=0\)), cela revient à considérer que cette lettre n'appartient pas à l'Alphabet \(A\) (donc la négliger pour l'étude de la phrase donnée).

Un Exemple⚓︎

Calcul de l'Entropie d'une phrase

  • On commence par calculer les probabilités d'apparition de chaque lettre existant réellement dans cette phrase :
Lettre
\(a_i\)		 \(D\) \(N\) \(O\) \(I\) \(U\) \(A\) \(T\) \(S\)
\(p_i\) \(\dfrac {11}{32}\) \(\dfrac {6}{32}\) \(\dfrac {5}{32}\) \(\dfrac {4}{32}\) \(\dfrac {3}{32}\) \(\dfrac {1}{32}\) \(\dfrac {1}{32}\) \(\dfrac {1}{32}\)
  • Puis, on applique la formule pour \(H(X)\) (ici \(n=8\)) :

\(\displaystyle \begin{align} H(X) &= \sum_{i=1}^{n} p_i log_2 \left( \frac 1{p_i} \right) \\ &= \frac{11}{32} log_2 \left(\frac {32}{11} \right)+\frac{6}{32} log_2 \left(\frac {32}{6} \right)+\frac{5}{32} log_2 \left(\frac {32}{5} \right)+\frac{4}{32} log_2 \left(\frac {32}{4} \right)+3\times \frac{1}{32} log_2 \left(\frac {32}{1} \right) \\ &\approx 2,56475 \end{align} \)

Propriétés⚓︎

  • L'entropie n'est pas forcément un nombre entier

  • On peut montrer que \(0\leq H(X) \leq log_2 (n)\)

    Demo
    • \(0 \lt p_i \leq 1 \Rightarrow \dfrac {1}p_i{} \geq 1 \Rightarrow log_2\left( \dfrac {1}p_i{}\right)\geq log_2 (1)=0 \Rightarrow p_i log_2\left( \dfrac {1}p_i{}\right)\geq 0\)
      donc \(H(X)\) est une somme de nombres positifs, donc \(H(X) \geq 0\)
    • la fonction \(log_2\) est concave ce qui veut dire que :
      \(\dfrac {log_2(x)+log_2(y)}{2} \leq log_2 \left( \dfrac {x+y}{2} \right )\)
      \(\Leftrightarrow \dfrac 12.log_2(x)+\dfrac 12.log_2(y) \leq log_2 \left( \dfrac 12 .x + \dfrac 12. y \right )\)
      Cette formule est généralisable, lorsqu'il y a plusieurs termes positifs \(p_i\) et des \(x_i\) : \(p_1log_2(x_1)+p_2 log_2(x_2)+\cdots+p_n log_2(x_n) \leq log_2 \left( p_1 x_1 + p_2 x_2+\cdots +p_n x_n \right)\)
      Autrement dit, pour des \(0 \leq p_i \leq 1\) tels que \(\displaystyle \sum_{i=1}^{n} p_i=1\) et \(x_i \gt 0\) :
      \(\displaystyle \sum_{i=1}^{n} p_i log_2(x_i) \leq log_2 \left( \sum_{i=1}^{n} p_i x_i \right)\)

      donc, en appliquant cette formule à \(x_i = \dfrac 1{p_i}\gt 0\) : \(\displaystyle \begin{align} H(X) = \sum_{i=1}^{n} p_i log_2 \left( \frac{1}{p_i} \right) &\leq log_2\left( \sum_{i=1}^{n} (p_i\times \frac{1}{p_i}) \right) \\ &\leq log_2\left( \sum_{i=1}^{n} (1) \right) \\ &\leq log_2\left( n \right) \end{align} \)

Interprétations de l'Entropie⚓︎

  • \(\begin{align} H(X) =0 &\Leftrightarrow \text{L'Entropie est minimale} \\ &\Leftrightarrow \text{Toutes les lettres de la phrase sont les mêmes } \\ &\Leftrightarrow \text{Pas de désordre dans la phrase} \\ &\Leftrightarrow \text{Le nombre de phrases (une seule) écrivables avec une unique lettre est minimal } \\ \end{align} \)
  • \(\begin{align} H(X) =log_2(n) &\Leftrightarrow \text{L'Entropie est maximale} \\ &\Leftrightarrow \text{Toutes les lettres de la phrase sont différentes } \\ &\Leftrightarrow \text{Le désordre dans la phrase est maximal} \\ &\Leftrightarrow \text{Le nombre de phrase que l'on peut écrire avec ces lettres est maximal} \\ \end{align} \)
  • Dire que \(p_i=2^{-m_i} (\text{avec }m_i \in \mathbb{N}) \Leftrightarrow m_i = log_2 \left( \dfrac{1}{p_i} \right)\)
    • Comment interpréter ce nombre \(m_i\) ?
      Supposons que l'on choisisse au hasard une lettre (parmi celles de la phrase), dont la fréquence dans la phrase soit \(p_i\), et que vous devez deviner cette lettre en ne posant que des questions binaires (pour lesquelles on ne peut répondre que par OUI ou NON) Alors \(m_i\) est le nombre (minimal) de questions binaires à poser pour trouver cette lettre dans la phrase.
    • En outre, on a :
      \(\displaystyle \begin{align} H(X) &= \sum_{i=1}^{n} p_i log_2 \left( \frac{1}{p_i} \right) \\ &= \sum_{i=1}^{n} p_i log_2 \left( \frac{1}{2^{-m_i}} \right) \\ &= \sum_{i=1}^{n} p_i log_2 \left( 2^{m_i} \right) \\ &= \sum_{i=1}^{n} p_i m_i \end{align} \)

Pte

L'Entropie modélise donc le nombre moyen de questions nécessaires à poser pour deviner une lettre tirée au hasard dans la phrase

Le TD : Travail à Faire⚓︎

On supposera dans cette partie que l'Alphabet \(A=\{A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z\}\) et que la langue choisie est le Français.

On se donne plusieurs phrases :

X1 = "Pour qui sont ces serpents qui sifflent sur vos têtes" (Andromaque de Racine)
X2 = "Un chasseur sachant chasser doit savoir chasser sans son chien"
X3 = "Les chaussettes de l'archiduchesse sont sèches, archisèches"

Pour chacune de ces phrases, on pourra :

  • négliger les virgules,
  • négliger les espaces et
  • négliger les apostrophes, et
  • considérer les lettres accentuées comme la lettre non accentuée correspondante ( é=e et è=e, etc..)

Pour chacune des phrases données, dont on pourra supposer qu'elles ont été préalablement formattées convenablement (virgules, espaces, lettres accentuées), répondre aux questions suivantes :

  1. Calculer manuellement l'Entropie \(H(X)\) de la phrase \(X\)
  2. Quel est le nombre minimal de questions binaires pour devenir une lettre piochée au hasard dans cette phrase ?

  3. Écrire une fonction lettres_phrase(X:str)->list python qui :

    • reçoit en entrée une phrase \(X\) sous forme de str
    • renvoie en sortie une chaîne de caractères constituée uniquement de chacune des lettres existant dans la phrase \(X\) (sans répétition, et dans un ordre quelconque)

    Par exemple: la phrase "A BAS ALIBABA" doit renvoyer la chaîne "ABILS"

  4. Écrire une fonction occurences(X:str)->dict python qui :

    • reçoit en entrée une phrase \(X\) sous forme de str
    • renvoie en sortie un dictionnaire d tel que :
      • les clés sont les lettres existant dans la phrase
      • les valeurs correspondant aux clés sont le nombre d'occurences de chacune des lettres existant dans la phrase \(X\)

  5. Écrire une fonction probas(X:str)->dict python qui :

    • reçoit en entrée une phrase \(X\) sous forme de str
    • renvoie en sortie un dictionnaire d tel que :
      • les clés sont les lettres existant dans la phrase
      • les valeurs correspondant aux clés sont la probabilité de chacune des lettres existant dans la phrase \(X\)

  6. Écrire une fonction entropie(X:str)->dict python qui :

    • reçoit en entrée une phrase \(X\) sous forme de str
    • renvoie en sortie l'entropie de la phrase

Références⚓︎

  • https://www.youtube.com/watch?v=kD5DHGbkYz0