Exemple d'entropie conditionnelle. Entropie d'une source de messages continus

Considérant la formule de Shannon (3.3) pour calculer l'entropie variable aléatoire et la quantité d'informations, nous avons supposé que les informations sur la variable aléatoire (X) parviennent directement à l'observateur. Cependant, en règle générale, nous recevons des informations non pas sur la variable aléatoire (X) qui nous intéresse, mais sur une autre variable (Y), qui est liée à X de manière stochastique. Une telle connexion de variables aléatoires diffère d'une connexion fonctionnelle, dans laquelle chaque valeur d'une valeur correspond à une valeur unique et bien définie d'une autre valeur. La connexion stochastique (probabiliste) entre deux variables aléatoires X et Y signifie qu'un changement dans l'une d'elles affecte la valeur de l'autre, mais de telle manière que connaissant la valeur de X, il est impossible d'indiquer avec précision la valeur que la valeur Y prendra. Vous ne pouvez indiquer que la tendance du changement de la valeur Y.

Soit B un événement aléatoire ; p(B) – probabilité de son apparition ; notons X une variable aléatoire qui prend N différentes significations(x 1 , x 2 , … x N ), et par A k l'événement où la variable aléatoire X prendra la valeur x k :

A k = ( X = x k ), k=1,2, …N ;

Nous notons la probabilité de l'événement A k par p(A k). La probabilité que certains événements se produisent peut changer selon qu'un autre événement se produit ou non. La probabilité p B (A k) de l'événement A k, calculée dans l'hypothèse où l'événement B s'est produit, est appelée probabilité conditionnelle de l'événement A k, dans ce cas :

Les événements A k et B sont dits indépendants si la probabilité d'occurrence de l'événement A k ne dépend pas du fait que l'événement B se soit produit ou non. Cela signifie que la probabilité conditionnelle de l'événement p B (A k) est égale à « l'ordinaire ». probabilité p(UNE k).

Définition. L'entropie conditionnelle d'une variable aléatoire X sous la condition B est la quantité

(4.2)

La différence avec la formule de Shannon (3.3) est qu’au lieu des probabilités p(A k), des probabilités conditionnelles p B (A k) sont utilisées.

Soit maintenant Y une autre variable aléatoire prenant des valeurs (y 1 , y 2 , ... y M ). Notons B j l'événement où la variable aléatoire Y prend la valeur y j :

B j = ( Y = y j ), j=1, 2,… M.

Nous notons la probabilité de l'événement B j par p(B j).

Définition. L'entropie conditionnelle de la variable aléatoire X à valeur définie la variable aléatoire Y est la quantité H Y (X)

(4.3)

Transformons la formule (4.3) :

La formule (4.3) prend la forme :

(4.4)

Calculons la quantité d'informations sur la variable aléatoire X obtenue en observant la variable aléatoire Y. Cette quantité d'informations I(X,Y) est égale à la diminution de l'entropie de la variable aléatoire X lors de l'observation de la variable aléatoire Y :

Remplaçons les expressions pour H(X) et H Y (X) dans (15) :

Dans la première somme, nous remplaçons p(A k)=p(A k B 1)+ p(A k B 2)+ p(A k B 3)…+ p(A k B M). Cette égalité a réellement lieu, car les événements A k B 1 , A k B 2 , … A k B M sont incompatibles par paires, et l'un d'eux se produira si A k se produit. Inversement, si l'un des B j apparaît, alors A k apparaît également. En continuant les transformations, on obtient :

Nous avons donc une formule pour calculer la quantité d'informations sur une variable aléatoire X lors de l'observation d'une autre variable aléatoire Y :

(4.6)

Si les variables aléatoires (ou événements) sont indépendantes, alors la relation p(A k B j) = p(A k)p(B j) est valable pour elles - la probabilité d'occurrence conjointe de deux événements est égale au produit de les probabilités de ces événements.

Concernant la valeur I(X,Y), les affirmations suivantes sont vraies.

Pour les variables aléatoires indépendantes, nous obtenons

Cela signifie que l'observation de la variable aléatoire Y n'apportera aucun avantage pour obtenir des informations sur la variable aléatoire X.

Dans d’autres cas, I(X,Y) >0, et l’inégalité suivante est vraie :

L'égalité est atteinte s'il existe une connexion fonctionnelle Y=F(X). Dans ce cas, observer Y donne informations complètesà propos de X. Si Y=X, alors I(X,X) = H(X).

La quantité I(X,Y) est symétrique : I(X,Y) = I(Y,X). Cela signifie que l'observation d'une variable aléatoire Y fournit la même quantité d'informations sur la variable aléatoire X que l'observation d'une variable aléatoire X fournit sur la variable aléatoire Y. Si nous considérons deux variables aléatoires qui sont dans une dépendance stochastique, alors au moyen de la théorie de l’information, il est impossible d’établir laquelle est la cause et laquelle est l’effet.

Pour une présentation plus approfondie, nous aurons besoin de certaines informations connues issues de la théorie des probabilités.

1) Propriétés des probabilités pour un ensemble événements aléatoires UN Et DANS:

P(UNE,B)=P(UNE)*P(B/UNE); -> P(B/A)=P(A,B)/P(B);

P(UNE,B)=P(B)*P(B/UNE); -> P(A/B)=P(A,B)/P(A);

P(A/B)=P(A)*P(B/A)/P(B);

P(B/A)=P(B)*P(A/B)/P(A); UN Et DANS Si

sont indépendants, alors

P(A/B) = P(A); P(B/A)=P(B) :

P(UNE,B)=P(UNE)*P(B);

Encore une fois, la définition de l'entropie de Shannon pour une source de messages discrets :

Ses propriétés : ;

H > 0Nm;

hache = log N Avec des sources indépendantes;

H(UNE,B)=H(UNE)+H(B)

Si les états des éléments du système ne dépendent pas les uns des autres ou si l'état d'un système ne dépend pas de l'état d'un autre système, alors l'incertitude selon laquelle un élément du système (ou un système) sera dans l'un des les états possibles seraient entièrement déterminés par les caractéristiques probabilistes des éléments individuels du système. Dans ce cas montant spécifique les informations par état d'un élément du système ou par symbole de message sont appelées entropie moyenne, et lors de son calcul, l'expression est utilisée

Lors du calcul de la quantité moyenne d'informations par symbole de message, l'interdépendance est prise en compte à travers probabilités conditionnelles d'occurrence de certains événements par rapport à d'autres, et l'entropie résultante est appelée entropie conditionnelle.

Considérons la transmission de messages à partir d'une source de symboles aléatoires A via un canal de transmission d'informations. Dans ce cas, on suppose qu'avec une transmission fiable lors de la transmission du symbole a 1, nous obtenons b 1 , un 2 - b 2 etc. Dans ce cas, pour un canal avec interférence, la transmission est déformée, et lorsqu'un symbole est reçu b 1 on ne peut parler que de la probabilité de retransmission du symbole un 1 . Il se pourrait bien que les caractères aient été transmis un 2 , un 3 etc.

Les distorsions sont décrites par la matrice des probabilités conditionnelles des canaux P.(UN/ B)={ p(un je / b je }.

Considérons le processus de transmission de signaux sur un canal de communication avec du bruit et utilisons-le pour comprendre le mécanisme de calcul de l'entropie conditionnelle.

Si la source du message produit les caractères

un je , UN 2 , ..., un je ..., UN n

avec des probabilités en conséquence

Pennsylvanie 1 ), p (un 2 ) ... ..., p (une je ), ..., p (une n ),

et en sortie du canal de transmission on reçoit des symboles

b 1 ,b 2 , ..., b je ..., b n

avec des probabilités en conséquence

p(b 1 ), p (b 2 ), ..., p (b je , ..., p (b n ),

puis le concept d'entropie conditionnelle H (B/un je ) exprime l'incertitude de quoi, en envoyant un je , nous aurons b je., concept H(A/b je ) l'incertitude qui subsiste après la réception b je dans ce qui a été envoyé exactement un je. Ceci est représenté graphiquement dans la figure ci-dessus. S'il y a des interférences dans le canal de communication, n'importe lequel des signaux peut être reçu avec différents degrés de probabilité. b j et, inversement, le signal reçu b j peut apparaître à la suite de l’envoi de l’un des signaux un je . S'il n'y a aucune interférence dans le canal de communication, le symbole envoyé est toujours UN 1 correspond au caractère accepté b 1 , UN 2 -b 2 , ..., UN n -b n .

Dans ce cas, l'entropie de la source du message H(A) est égale à l'entropie du récepteur du message H(B). S'il y a des interférences dans le canal de communication, cela détruit ou déforme une partie des informations transmises.

Les pertes d'informations sont complètement décrites par l'entropie conditionnelle privée et générale. Il est pratique de calculer l’entropie conditionnelle partielle et générale à l’aide de matrices de canaux. Le terme « matrice de canaux » désigne : une matrice qui décrit statistiquement cette chaîne connexion, utilisée par souci de brièveté. Si le canal de communication est décrit du côté de la source du message (c'est-à-dire que le signal envoyé est connu), alors la probabilité que lors de la transmission du signal un je via un canal de communication avec interférence, nous recevrons un signal b j noté probabilité conditionnelle p(b j /ai). et la matrice de canal a la forme

Les probabilités situées le long de la diagonale (en gras) déterminent les probabilités d'une réception correcte, le reste - une fausse. Les valeurs des chiffres remplissant les colonnes de la matrice de canal diminuent généralement avec la distance par rapport à la diagonale principale, et en l'absence totale d'interférence, tous sauf les chiffres situés sur la diagonale principale sont égaux à zéro.

Passer le symbole un je du côté de la source du message dans un canal de communication donné est décrit par la distribution de probabilités conditionnelles de la forme p(b j /un je ), la somme des probabilités doit toujours être égale à un. Par exemple, pour un signal UN 1

Pertes d'informations par partage de signal un je sont décrits en utilisant une entropie conditionnelle partielle. Par exemple, pour un signal un 1

La sommation est effectuée selon j, parce que je-ème état (dans dans ce cas premier) reste constant.

Perte de transmission tous les signaux sur un canal de communication donné sont décrits en utilisant l'entropie conditionnelle générale. Pour le calculer, vous devez additionner toutes les entropies conditionnelles partielles, c'est-à-dire effectuer une double sommation sur je et par j.

En cas de probabilité inégale d'apparition des symboles sources du message, la probabilité d'apparition de chaque symbole doit être prise en compte en multipliant l'entropie conditionnelle partielle correspondante par celle-ci. Dans ce cas, l'entropie conditionnelle totale

Si l'on examine la situation de l'extérieur destinataire du message(c'est lorsque le signal reçu est connu) , puis à la réception du symbole b j on suppose que l'un des symboles a été envoyé un 1 , un 2 , …, un je ,…, un N. Dans ce cas, la matrice de canaux a la forme :

Dans ce cas, les sommes des probabilités conditionnelles doivent être égales à un non pas dans les lignes, mais dans les colonnes de la matrice de canaux

Entropie conditionnelle partielle

Et l'entropie conditionnelle totale

Entropie conditionnelle totale du système B par rapport au système A caractérise la quantité d'informations contenues dans tout symbole de la source du message à travers laquelle nous représentons les états des éléments des systèmes étudiés.

L'entropie conditionnelle générale est déterminée en faisant la moyenne de tous les symboles, c'est-à-dire de tous les états. UN je en tenant compte de la probabilité d'occurrence de chacun d'eux. Elle est égale à la somme des produits des probabilités d'apparition des symboles sources et de l'incertitude qui subsiste après que le destinataire a reçu les symboles :

S'il n'y a pas d'interférence dans le canal de communication, alors tous les éléments de la matrice de canal, à l'exception de ceux situés sur la diagonale principale, sont égaux à zéro. Cela suggère que lors de la transmission d'un signal UN 1 nous aurons certainement b 1 lors de la transmission UN 2 - b 2 , ..., UN N - b N. La probabilité de recevoir le signal correct deviendra inconditionnel, et conditionnel l'entropie sera nulle.

L'entropie conditionnelle atteint son maximum dans le cas où, lors de la transmission d'un symbole UN je peut-être avec probabilité égale l'un des signaux reçus b 1 , b 2 , ..., b N .

Entropie conditionnelle

Entropie (informative)- une mesure du chaos informationnel, l'incertitude de l'apparition de tout symbole de l'alphabet primaire. En l'absence de pertes d'informations, elle est numériquement égale à la quantité d'informations par symbole du message transmis.

Par exemple, dans la séquence de lettres qui composent une phrase en russe, différentes lettres apparaissent avec des fréquences différentes, de sorte que l'incertitude d'occurrence est moindre pour certaines lettres que pour d'autres. Si l'on tient compte du fait que certaines combinaisons de lettres (dans ce cas on parle d'entropie n-ème ordre, voir) sont très rares, alors l'incertitude est encore réduite.

Pour illustrer le concept d'entropie informationnelle, on peut également recourir à un exemple issu du domaine de l'entropie thermodynamique, appelé le démon de Maxwell. Les concepts d'information et d'entropie ont des liens profonds les uns avec les autres, mais malgré cela, le développement des théories dans mécanique statistique et la théorie de l'information a mis de nombreuses années à les rendre cohérentes les unes avec les autres.

Définitions formelles

Entropie de l'information pour des événements aléatoires indépendants x Avec n conditions possibles(de 1 à n) est calculé à l'aide de la formule :

Cette quantité est aussi appelée entropie moyenne des messages. La quantité s'appelle entropie privée, caractérisant uniquement je-domaine.

Ainsi, l'entropie de l'événement x est la somme avec signe opposé tous les travaux fréquences relatives survenance d'un événement je, multipliés par leurs propres logarithmes binaires (la base 2 a été choisie uniquement pour la commodité de travailler avec des informations présentées sous forme binaire). Cette définition des événements aléatoires discrets peut être étendue à une fonction de distribution de probabilité.

En général b entropie -aire(Où b est égal à 2, 3, ...) source avec l'alphabet original et distribution discrète probabilités où p je est la probabilité un je (p je = p(un je) ) est déterminé par la formule :

La définition de l'entropie de Shannon est liée au concept d'entropie thermodynamique. Boltzmann et Gibbs l'ont fait super travail Par thermodynamique statistique, ce qui a contribué à l'adoption du mot « entropie » dans théorie de l'information. Il existe un lien entre la thermodynamique et l’entropie de l’information. Par exemple, le démon de Maxwell contraste également entropie thermodynamique informations, et gagner n’importe quelle quantité d’informations équivaut à une perte d’entropie.

Définition alternative

Une autre façon de définir la fonction d'entropie est H est la preuve que H est déterminé de manière unique (comme indiqué précédemment) si et seulement si H remplit les conditions :

Propriétés

Il est important de rappeler que l'entropie est une quantité définie en contexte modèle probabiliste pour la source de données. Par exemple, lancer une pièce a une entropie − 2 (0,5 log 2 0,5) = 1 bit par lancer (en supposant qu'elle soit indépendante). Une source qui génère une chaîne composée uniquement des lettres « A » a une entropie nulle : . Ainsi, par exemple, on peut établir expérimentalement que l'entropie texte anglais est égal à 1,5 bits par caractère, ce qui varie bien entendu selon les textes. Le degré d'entropie d'une source de données désigne le nombre moyen de bits par élément de données nécessaire pour le chiffrer sans perte d'information, avec un codage optimal.

1. Certains bits de données peuvent ne pas contenir d'informations. Par exemple, les structures de données stockent souvent des informations redondantes ou comportent des sections identiques quelles que soient les informations contenues dans la structure de données.
2. La quantité d'entropie n'est pas toujours exprimée sous forme d'un nombre entier de bits.

Propriétés mathématiques

Efficacité

L’alphabet original rencontré en pratique présente une distribution de probabilité loin d’être optimale. Si l'alphabet original avait n caractères, il peut alors être comparé à un « alphabet optimisé » dont la distribution de probabilité est uniforme. Le rapport d'entropie de l'alphabet original et optimisé est l'efficacité de l'alphabet original, qui peut être exprimée en pourcentage.

Il s'ensuit que l'efficacité de l'alphabet original avec n les symboles peuvent être définis simplement comme égaux à leur n-entropie aire.

L'entropie limite la compression maximale possible sans perte (ou presque sans perte) qui peut être réalisée en utilisant un ensemble théoriquement typique ou, en pratique, le codage de Huffman, le codage de Lempel-Ziv-Welch ou le codage arithmétique.

Variations et généralisations

Entropie conditionnelle

Si la séquence de caractères alphabétiques n'est pas indépendante (par exemple, dans Français la lettre « q » est presque toujours suivie d'un « u », et le mot « avancé » dans Journaux soviétiques généralement suivi du mot « production » ou « travail »), la quantité d'informations véhiculée par une séquence de tels symboles (et donc l'entropie) est évidemment moindre. Pour prendre en compte ces faits, l’entropie conditionnelle est utilisée.

L'entropie conditionnelle du premier ordre (similaire au modèle de Markov du premier ordre) est l'entropie d'un alphabet où les probabilités d'apparition d'une lettre après l'autre sont connues (c'est-à-dire les probabilités de combinaisons de deux lettres) :

Où je est un état dépendant du caractère précédent, et p je (j) - c'est la probabilité j, à condition que jeétait le personnage précédent.

Donc, pour la langue russe sans la lettre "".

Les pertes d'informations lors de la transmission de données dans un canal bruyant sont entièrement décrites à travers des entropies conditionnelles partielles et générales. A cet effet, ce qu'on appelle matrices de canaux. Ainsi, pour décrire les pertes de la part de la source (c'est-à-dire que le signal envoyé est connu), la probabilité conditionnelle de recevoir le symbole par le récepteur est considérée b jà condition que le personnage ait été envoyé un je. Dans ce cas, la matrice de canaux a la forme suivante :

Évidemment, les probabilités situées le long de la diagonale décrivent la probabilité d'une réception correcte, et la somme de tous les éléments de la colonne donnera la probabilité que le symbole correspondant apparaisse du côté du récepteur - p(b j) . Pertes par signal transmis un je, sont décrits par entropie conditionnelle partielle :

Pour calculer les pertes de transmission de tous les signaux, l'entropie conditionnelle générale est utilisée :

Cela signifie l'entropie côté source ; l'entropie côté récepteur est considérée de la même manière : au lieu d'être indiquée partout (en additionnant les éléments de la ligne, vous pouvez obtenir p(un je) , et les éléments diagonaux signifient la probabilité que le caractère exact reçu ait été envoyé, c'est-à-dire la probabilité de transmission correcte).

Entropie mutuelle

Entropie mutuelle, ou entropie syndicale, est destiné au calcul de l'entropie des systèmes interconnectés (l'entropie de l'occurrence conjointe de messages statistiquement dépendants) et est noté H(UNB) , Où UN, comme toujours, caractérise l'émetteur, et B- récepteur.

La relation entre les signaux transmis et reçus est décrite par des probabilités événements communs p(un je b j) , et pour description complète caractéristiques du canal, une seule matrice est requise :

Pour plus cas général, lorsqu'il ne s'agit pas d'un canal qui est décrit, mais simplement de systèmes en interaction, la matrice n'a pas besoin d'être carrée. Évidemment, la somme de tous les éléments de la colonne avec le numéro j donnera p(b j) , la somme du numéro de ligne je Il y a p(un je) , et la somme de tous les éléments de la matrice est égale à 1. Probabilité conjointe p(un je b j) événements un je Et b j est calculé comme le produit de la probabilité originale et conditionnelle,

Probabilités conditionnelles sont produits selon la formule de Bayes. Ainsi, on dispose de toutes les données permettant de calculer les entropies de la source et du récepteur :

L'entropie mutuelle est calculée en additionnant séquentiellement sur des lignes (ou des colonnes) toutes les probabilités de la matrice, multipliées par leur logarithme :

L'unité de mesure est le bit/deux symboles, cela s'explique par le fait que l'entropie mutuelle décrit l'incertitude par paire de symboles - envoyés et reçus. Par de simples transformations on obtient aussi

L'entropie mutuelle a la propriété exhaustivité des informations- à partir de là, vous pouvez obtenir toutes les quantités considérées.