Modelisation probabiliste de l’information

MODELISATION PROBABILISTE DE L’INFORMATION

La théorie de l’information traite des phénomènes imprévisibles (ou aléatoires) et repose essentiellement sur le calcul des probabilités. Ce chapitre fournit les bases dans le domaine du calcul des probabilités nécessaires dans le cadre de la théorie de l’information. La plus grande partie se limite au traitement de modèles probabilistes discrets (variables aléatoires en nombre fini et ayant un nombre fini de valeurs possibles). Le calcul des probabilités est un outil mathématique qui permet de représenter et de manipuler des situations/expériences dont l’issue est aléatoire et/ou au sujet desquelles dispose de connaissances incomplètes/incertaines.

Espace probabilisé

Définition
La définition formelle d’un espace probabilisé est la suivante : Un espace probabilisé est défini par un triplet (Ω ,ε , P(.)) où :
• Ω représente l’ensemble de résultats possibles d’une expérience aléatoire,
• ε un σ -algèbre d’assertions logiques relatives aux résultats de l’expérience, et
• P(.) une loi de probabilité qui associe à chaque assertion logique A de ε un nombre P(A) ∈ [ 0;1]

Eléments de base du calcul de probabilités

Loi de probabilité conditionnelle
Partons d’un espace probabilisé (Ω ,ε , P(.)), et supposons qu’un événement B soit réalisé, par exemple parce qu’une observation le confirme ou simplement à titre hypothétique. Cherchons à savoir ce que devient alors la probabilité qu’un événement A quelconque soit également réalisé sous cette hypothèse. Nous allons noter cette quantité par P(A| B) . Si A et B sont incompatibles, il est clair que A devient impossible et P(A| B) = 0 . Par contre, si AIB ≠ ∅ , alors la réalisation de A est incompatible avec notre hypothèse, mais seulement les éléments de A qui sont également dans B nous intéressent. Si AIB ≠ B alors, nous sommes certains que A se réalisera : P(A| B) = 1. Tout se passe donc comme si nous avions restreint notre univers à l’événement B et que nous nous intéressions uniquement aux probabilités relatives des parties des événements situés dans B.

Variables aléatoires

Définition générale

Une variable aléatoire est une grandeur réelle dont la valeur dépend du hasard. Cette dépendance est exprimée par une loi de probabilité, communément appelée distribution. La distribution d’une variable aléatoire X peut être définie soit par sa fonction de répartition F(x), soit par sa densité de probabilité p(x) ou, encore, par sa fonction caractéristique H(a).

Fonction d’une variable aléatoire.
Soit une variable aléatoire X à valeur dans Ω ‘ défini par une fonction f (.), et une certaine fonction φ (.) définie sur Ω ‘ et à valeurs dans Ω  » . Alors, si φ (.) a le statut de variable aléatoire sur Ω ‘(Compatibilité de ε ‘ et ε  »), la fonction composée φ o f (.) = φ ( f (.)) définit également une variable aléatoire sur Ω . Nous verrons ci-dessous le cas particulièrement intéressant en pratique où les deux fonctions sont des variables aléatoires réelles.

Variable aléatoire discrète
Une variable aléatoire est discrète si l’ensemble de ses valeurs possibles est fini. Une telle variable aléatoire définit un système complet d’événements mutuellement exclusifs ; en fait elle est équivalente à la donnée d’un système complet d’événements discrets. Aussi, nous ne distinguerons plus dans la suite ces deux notions. Notons que si l’espace Ω est fini, alors toute variable aléatoire est nécessairement discrète.

Modèles probabilistes

Bien souvent, dans le cadre de nos raisonnements théoriques, plutôt que de passer par la définition d’une expérience aléatoire, d’un univers de résultats possibles, d’une loi de probabilités et de variables aléatoires telles que nous venons de le décrire, on postulera qu’une ou un certain nombre de variables aléatoires relatives à un problème sont distribuées selon une loi de probabilité donnée (Par exemple : une loi uniforme, gaussienne, binomiale,…). Parfois, on postule seulement la structure de cette loi de probabilités et laisse indéfinis les paramètres (Par exemple la moyenne et l’écart type dans le cas d’une loi gaussienne), sans même décrire explicitement la nature de l’expérience.

Par exemple, dans le cadre du paradigme de Shannon lorsque nous étudierons les sources d’information, nous serons dans certains cas amenés à postuler que les lettres successives de message de source sont distribuées de façon uniforme et indépendante. Ensuite, lorsque nous nous intéressons à l’étude des erreurs de communication, nous introduisons une hypothèse supplémentaire en ce qui concerne la relation entrée-sortie du canal, par exemple en supposant que celui-ci transmet les caractères successifs en choisissant pour chacun un caractère de sortie selon une loi de probabilité conditionnelle constante, qui ne fait intervenir que le caractère présenté à l’entrée. En fait, lorsqu’on étudie les relations entre un certain nombre de v.a. définies à partir d’une expérience aléatoire, il n’est pas nécessaire de connaître tous les détails relatifs à cette expérience. Il suffit en effet de connaître la loi de probabilité conjointe des v.a. en considération.

Table des matières

INTRODUCTION
CHAPITRE 1 : MODELISATION PROBABILISTE DE L’INFORMATION
1.1. Introduction
1.2. Espace probabilisé
1.2.1. Définition
1.2.2. -Algèbre des évènements
1.2.3. Evénements
1.2.4. Exemple
1.3. Système complet d’événements
1.3.1. Définition
1.3.2. Probabilités
1.3.3. Propriétés remarquables
1.3.4. Théorème des probabilités totales
1.4. Eléments de base du calcul de probabilités
1.4.1. Loi de probabilité conditionnelle
1.4.2. Définition
1.5. Notion d’indépendance d’événements
1.5.1. Définition
1.5.2. Indépendance conditionnelle
1.5.3. Propriétés positives
1.5.4. Définition alternative de l’indépendance
1.5.5. Propriétés négatives
1.5.6. Indépendance mutuelle
1.6. Formules de Bayes
1.6.1. Première formule de Bayes
1.6.2. Théorème des probabilités totales
1.6.3. Théorème sur la probabilité des causes (Deuxième formule de Bayes)
1.7. Variables aléatoires
1.7.1. Définition générale
1.7.2. Fonction d’une variable aléatoire
1.7.3. Variable aléatoire discrète
1.7.4. Variables aléatoires réelles
1.8. Fonction de répartition
1.9. Densité de probabilité
1.9.1. Densité de probabilité d’une variable aléatoire discrète
1.9.2. Densité de probabilité d’une variable aléatoire (réelle) continue
1.9.3. Variable aléatoire bidimensionnelle
1.10. Indépendance de variables aléatoires
1.11. Espérance mathématique
1.12. Variance et écart type
1.13. Inégalité de Jensen
1.14. Couples de v.a. et conditionnement
1.14.1. Cas discret
1.14.2. Lois associées
1.14.3. Lois marginales
1.14.4. Lois conditionnelles
1.15. Moments conditionnels
1.15.1. Espérance conditionnelle
1.15.2. Variance conditionnelle
1.16. Variables continues
1.16.1. Cas où une des deux variables est continue
1.16.2. Cas le plus général
1.17. Modèles probabilistes
CHAPITRE 2 : OUTILS DE LA THEORIE DE L’INFORMATION
2.1. Quantité d’information
2.2. Définition de la quantité d’information
2.3. Définition de l’entropie
2.4. Lemme 1 (Fondamentale)
2.5. Inégalité de Jensen
2.5.1. Théorème 1
2.5.2. Propriété 1
2.6. Relations entre entropie et codage de source
2.6.1. Source discrète sans mémoire
2.6.2. Extension d’ordre n d’une source
2.6.2.1. Propriété 2
2.7. Code déchiffrable
2.7.1. Condition du préfixe
2.7.2. Inégalité de Kraft
2.7.3. Codage de source
2.8. Information mutuelle
2.8.1. Entropie conjointe
2.8.2. Information mutuelle
2.9. Théorème du traitement de l’information
2.9.1. Cascade markovienne
2.10. Traitement de l’information
2.10.1. Théorème 2
2.10.2. Cas des variables aléatoires « continues »
2.11.2.1. Entropie différentielle
2.11.2.2. Lemme fondamental
2.11. Information mutuelle (continue)
2.12. Capacité d’un canal
2.12.1. Notion de canal de communication
2.12.2. Exemples de canaux en communication numériques
2.12.3. Canal binaire symétrique
2.12.4. Canal binaire à décision douce
2.12.5. Canal à effacement
2.12.6. Canal M- aire à sortie réelle
2.12.7. Canal additif gaussien blanc
2.13. Définition d’un canal discret et d’un code sur ce canal
2.13.1. Canal discret
2.13.2. Extension d’ordre n sans mémoire et sans voie de retour
2.13.3. (n,M),-code
2.14. Probabilité d’erreur maximale
2.15. Capacité
2.15.1. Formule de la capacité
2.15.2. Réciprocité
2.16. La recherche des bons codes
2.17. Exemple de calcul de capacité
2.17.1. Canal CBS
2.17.2. Canal binaire à décision douce
2.17.3. Canal AGB
CHAPITRE 3 : APPLICATION DE LA THEORIE DE L’INFORMATION AU CODAGE
3.1. Les applications des transmissions numériques
3.2. Les avantages des systèmes numériques
3.2.1. Lutte contre le bruit
3.2.2. Les aspects économiques
3.3. Le codage
3.4. Codage de source
3.4.1. Description d’un système de codage de source
3.4.2. Longueur et efficacité d’un code
3.4.3. Théorème de codage de source
3.5. Les théorèmes de Shannon
3.5.1. Premier théorème de Shannon
3.5.2. Deuxième théorème de Shannon
3.6. Exemples de codes utilisant la probabilité
3.6.1. Codage de Shannon-Fano
3.6.2. Algorithme de Huffman pour un alphabet de code binaire
3.6.2.1. Description de l’algorithme
3.6.2.2. Proposition de Huffman
Construction du code
3.7. Codage et compression de l’image numérique
3.7.1. Qu’est ce qu’une image ?
3.7.2. Coordonnées spatiales
3.7.3. Modèle probabiliste
3.7.4. Codage selon la méthode de Shannon Fano
3.7.5. Codage selon la méthode de Huffman
3.8. Compression de l’information
3.9. Méthodes de compression
CHAPITRE 4 : SIMULATION DE LA THEORIE DE L’INFORMATION SOUS MATLAB
CONCLUSION

Lire le rapport complet