Entropie de Rényi - Rényi entropy

En théorie de l'information , l' entropie de Rényi généralise l' entropie de Hartley , l' entropie de Shannon , l' entropie de collision et la min-entropie . Les entropies quantifient la diversité, l'incertitude ou le caractère aléatoire d'un système. L'entropie porte le nom d' Alfréd Rényi . Dans le cadre de l' estimation de dimension fractale , l'entropie de Rényi est à la base du concept de dimensions généralisées .

L'entropie Rényi est importante en écologie et en statistique comme indice de diversité . L'entropie de Rényi est également importante dans l'information quantique , où elle peut être utilisée comme mesure d' intrication . Dans le modèle de chaîne de spin Heisenberg XY, le Rényi entropie en fonction de α peut être calculé explicitement en vertu du fait qu'il est une fonction automorphic par rapport à un sous - groupe particulier du groupe modulaire . En informatique théorique , la min-entropie est utilisée dans le cadre des extracteurs d'aléatoire .

Définition

L'entropie d'ordre Rényi , où et , est définie comme ${\style d'affichage \alpha }$${\displaystyle \alpha \geq 0}$${\displaystyle \alpha \neq 1}$

${\displaystyle \mathrm {H} _{\alpha }(X)={\frac {1}{1-\alpha }}\log {\Bigg (}\sum _{i=1}^{n}p_ {i}^{\alpha }{\Bigg )}}$ .

Ici, est une variable aléatoire discrète avec des résultats possibles dans l'ensemble et des probabilités correspondantes pour . Le logarithme est classiquement pris en base 2, notamment dans le contexte de la théorie de l' information où l' on utilise des bits . Si les probabilités sont pour tout , alors toutes les entropies de Rényi de la distribution sont égales : . En général, pour toutes les variables aléatoires discrètes , est une fonction non croissante dans . ${\style d'affichage X}$${\displaystyle {\mathcal {A}}=\{x_{1},x_{2},...,x_{n}\}}$${\displaystyle p_{i}\doteq \Pr(X=x_{i})}$${\displaystyle i=1,\dots ,n}$${\style d'affichage p_{i}=1/n}$${\displaystyle i=1,\dots ,n}$${\displaystyle \mathrm {H} _{\alpha }(X)=\log n}$${\style d'affichage X}$${\displaystyle \mathrm {H} _{\alpha }(X)}$${\style d'affichage \alpha }$

Les applications exploitent souvent la relation suivante entre l'entropie de Rényi et la p -norme du vecteur de probabilités :

${\displaystyle \mathrm {H} _{\alpha }(X)={\frac {\alpha {1-\alpha }}\log \left(\|P\|_{\alpha }\right)}$ .

Ici, la distribution de probabilité discrète est interprétée comme un vecteur dans avec et . ${\displaystyle P=(p_{1},\dots ,p_{n})}$${\displaystyle \mathbb {R} ^{n}}$${\displaystyle p_{i}\geq 0}$${\displaystyle \sum _{i=1}^{n}p_{i}=1}$

L'entropie de Rényi pour tout est Schur concave . ${\displaystyle \alpha \geq 0}$

Cas spéciaux

Entropie de Rényi d'une variable aléatoire avec deux issues possibles contre p ₁ , où P = ( p ₁ , 1 − p ₁ ) . Sont représentés H ₀ , H ₁ , H ₂ et H _∞ , en unités de Shannons .

À mesure que α se rapproche de zéro, l'entropie de Rényi pèse de plus en plus tous les événements avec une probabilité non nulle de manière plus égale, quelles que soient leurs probabilités. A la limite pour α → 0, l'entropie de Rényi est juste le logarithme de la taille du support de X . La limite pour α → 1 est l' entropie de Shannon . À mesure que α tend vers l'infini, l'entropie de Rényi est de plus en plus déterminée par les événements de probabilité la plus élevée.

Hartley ou max-entropie

A condition que les probabilités soient différentes de zéro, est le logarithme de la cardinalité de l'alphabet ( ) de , parfois appelée l' entropie de Hartley de , ${\displaystyle \mathrm {H} _{0}}$${\displaystyle {\mathcal {A}}}$${\style d'affichage X}$${\style d'affichage X}$

${\displaystyle \mathrm {H} _{0}(X)=\log n=\log |{\mathcal {A}}|\,}$

Entropie de Shannon

La valeur limite de as α → 1 est l' entropie de Shannon : ${\displaystyle \mathrm {H} _{\alpha }}$

${\displaystyle \mathrm {H} _{1}(X)\equiv \lim _{\alpha \to 1}\mathrm {H} _{\alpha }(X)=-\sum _{i=1} ^{n}p_{i}\log p_{i}}$

Entropie de collision

L'entropie de collision , parfois simplement appelée « entropie de Rényi », fait référence au cas α = 2,

${\displaystyle \mathrm {H} _{2}(X)=-\log \sum _{i=1}^{n}p_{i}^{2}=-\log P(X=Y), }$

où X et Y sont indépendants et identiquement distribués . L'entropie de collision est liée à l' indice de coïncidence .

Min-entropie

A la limite as , l'entropie de Rényi converge vers la min-entropie : ${\displaystyle \alpha \rightarrow \infty }$${\displaystyle \mathrm {H} _{\alpha }}$ ${\displaystyle \mathrm {H} _{\infty }}$

${\displaystyle \mathrm {H} _{\infty }(X)\doteq \min _{i}(-\log p_{i})=-(\max _{i}\log p_{i})= -\log \max _{i}p_{i}\,.}$

De manière équivalente, la min-entropie est le plus grand nombre réel b tel que tous les événements se produisent avec une probabilité d'au plus . ${\displaystyle \mathrm {H} _{\infty }(X)}$${\style d'affichage 2^{-b}}$

Le nom min-entropie vient du fait qu'il s'agit de la plus petite mesure d'entropie de la famille des entropies de Rényi. En ce sens, c'est le moyen le plus efficace de mesurer le contenu informationnel d'une variable aléatoire discrète. En particulier, la min-entropie n'est jamais plus grande que l' entropie de Shannon .

La min-entropie a des applications importantes pour les extracteurs d'aléatoire en informatique théorique : les extracteurs sont capables d'extraire l'aléatoire à partir de sources aléatoires qui ont une grande min-entropie ; le simple fait d'avoir une grande entropie de Shannon ne suffit pas pour cette tâche.

Les inégalités entre les différentes valeurs de α

C'est non croissant pour une distribution donnée de probabilités , qui peut être prouvée par différentiation, comme ${\displaystyle \mathrm {H} _{\alpha }}$${\style d'affichage \alpha }$${\style d'affichage p_{i}}$

${\displaystyle -{\frac {d\mathrm {H} _{\alpha }}{d\alpha }}={\frac {1}{(1-\alpha )^{2}}}\sum _{ i=1}^{n}z_{i}\log(z_{i}/p_{i}),}$

qui est proportionnel à la divergence de Kullback-Leibler (qui est toujours non négative), où . ${\displaystyle z_{i}=p_{i}^{\alpha }/\sum _{j=1}^{n}p_{j}^{\alpha }}$

Dans des cas particuliers, les inégalités peuvent aussi être prouvées par l'inégalité de Jensen :

${\displaystyle \log n=\mathrm {H} _{0}\geq \mathrm {H} _{1}\geq \mathrm {H} _{2}\geq \mathrm {H} _{\infty } .}$

Pour les valeurs de , les inégalités dans l'autre sens sont également valables. En particulier, nous avons ${\displaystyle \alpha >1}$

${\displaystyle \mathrm {H} _{2}\leq 2\mathrm {H} _{\infty }.}$

D'autre part, l'entropie de Shannon peut être arbitrairement élevée pour une variable aléatoire qui a une min-entropie donnée. ${\displaystyle \mathrm {H} _{1}}$${\style d'affichage X}$

Divergence de Rényi

En plus des entropies absolues de Rényi, Rényi a également défini un spectre de mesures de divergence généralisant la divergence de Kullback-Leibler .

La divergence de Rényi d'ordre α ou alpha-divergence d'une distribution P à partir d'une distribution Q est définie comme étant

${\displaystyle D_{\alpha }(P\|Q)={\frac {1}{\alpha -1}}\log {\Bigg (}\sum _{i=1}^{n}{\frac {p_{i}^{\alpha }}{q_{i}^{\alpha -1}}}{\Bigg )}\,}$

lorsque 0 < α < ∞ et α ≠ 1 . On peut définir la divergence de Rényi pour les valeurs spéciales α = 0, 1, ∞ en prenant une limite, et en particulier la limite α → 1 donne la divergence de Kullback–Leibler.

Quelques cas particuliers :

${\displaystyle D_{0}(P\|Q)=-\log Q(\{i:p_{i}>0\})}$ : moins le log de probabilité sous Q que p _i > 0 ;

${\displaystyle D_{1/2}(P\|Q)=-2\log \sum _{i=1}^{n}{\sqrt {p_{i}q_{i}}}}$ : moins deux fois le logarithme du coefficient de Bhattacharyya ; ( Nielsen et Boltz (2010) )

${\displaystyle D_{1}(P\|Q)=\sum _{i=1}^{n}p_{i}\log {\frac {p_{i}}{q_{i}}}}$ : la divergence Kullback–Leibler ;

${\displaystyle D_{2}(P\|Q)=\log {\Big \langle }{\frac {p_{i}}{q_{i}}}{\Big \rangle }}$ : le log du rapport attendu des probabilités ;

${\displaystyle D_{\infty }(P\|Q)=\log \sup _{i}{\frac {p_{i}}{q_{i}}}}$ : le log du rapport maximum des probabilités.

La divergence de Rényi est bien une divergence , c'est-à-dire simplement supérieure ou égale à zéro, et nulle uniquement lorsque P = Q . Pour toutes distributions fixes P et Q , la divergence de Rényi est non décroissante en fonction de son ordre α , et elle est continue sur l'ensemble de α pour lequel elle est finie. ${\displaystyle D_{\alpha }(P\|Q)}$

Interprétation financière

Une paire de distributions de probabilités peut être considérée comme un jeu de hasard dans lequel l'une des distributions définit les cotes officielles et l'autre contient les probabilités réelles. La connaissance des probabilités réelles permet à un joueur de tirer profit du jeu. Le taux de profit attendu est lié à la divergence de Rényi comme suit

${\displaystyle {\rm {ExpectedRate}}={\frac {1}{R}}\,D_{1}(b\|m)+{\frac {R-1}{R}}\,D_{ 1/R}(b\|m)\,,}$

où est la distribution définissant les cotes officielles (c'est-à-dire le "marché") pour le jeu, est la distribution que l'investisseur croit et est l'aversion au risque de l'investisseur (l'aversion au risque relative d'Arrow-Pratt). ${\style d'affichage m}$${\style d'affichage b}$${\style d'affichage R}$

Si la vraie distribution est (pas nécessairement coïncidant avec la croyance de l'investisseur ), le taux réalisé à long terme converge vers la vraie attente qui a une structure mathématique similaire ${\style d'affichage p}$${\style d'affichage b}$

${\displaystyle {\rm {RealizedRate}}={\frac {1}{R}}\,{\Big (}D_{1}(p\|m)-D_{1}(p\|b){ \Gros )}+{\frac {R-1}{R}}\,D_{1/R}(b\|m)\,.}$

Pourquoi α = 1 est spécial

La valeur α = 1 , qui donne l' entropie de Shannon et la divergence de Kullback-Leibler , est particulière car ce n'est qu'à α = 1 que la règle de la chaîne de probabilité conditionnelle tient exactement :

${\displaystyle \mathrm {H} (A,X)=\mathrm {H} (A)+\mathbb {E} _{a\sim A}{\big [}\mathrm {H} (X|A= un gros ]}}$

pour les entropies absolues, et

${\displaystyle D_{\mathrm {KL} }(p(x|a)p(a)\|m(x,a))=D_{\mathrm {KL} }(p(a)\|m(a ))+\mathbb {E} _{p(a)}\{D_{\mathrm {KL} }(p(x|a)\|m(x|a))\},}$

pour les entropies relatives.

Ce dernier en particulier signifie que si nous recherchons une distribution p ( x , a ) qui minimise la divergence par rapport à une mesure a priori sous - jacente m ( x , a ) , et que nous acquérons de nouvelles informations qui n'affectent que la distribution de a , alors la distribution de p ( x | a ) reste m ( x | a ) , inchangé.

Les autres divergences Rényi satisfont aux critères d'être positifs et continus ; être invariant sous des transformations de coordonnées 1 à 1 ; et de combiner additivement lorsque A et X sont indépendants, de sorte que si p ( A , X ) = p ( A ) p ( X ) , alors

${\displaystyle \mathrm {H} _{\alpha }(A,X)=\mathrm {H} _{\alpha }(A)+\mathrm {H} _{\alpha }(X)\;}$

et

${\style d'affichage D_{\alpha }(P(A)P(X)\|Q(A)Q(X))=D_{\alpha }(P(A)\|Q(A))+D_{\ alpha }(P(X)\|Q(X)).}$

Les propriétés des plus fortes alpha = 1 quantités qui permettent la définition de l' information conditionnelle et information mutuelle de la théorie de la communication, peut être très important dans d' autres applications, ou tout à fait sans importance, selon les exigences de ces applications.

Familles exponentielles

Les entropies et divergences de Rényi pour une famille exponentielle admettent des expressions simples

${\displaystyle \mathrm {H} _{\alpha }(p_{F}(x;\theta ))={\frac {1}{1-\alpha }}\left(F(\alpha \theta )- \alpha F(\theta )+\log E_{p}[e^{(\alpha -1)k(x)}]\right)}$

et

${\displaystyle D_{\alpha }(p:q)={\frac {J_{F,\alpha }(\theta :\theta ')}{1-\alpha }}}$

où

${\displaystyle J_{F,\alpha }(\theta :\theta ')=\alpha F(\theta )+(1-\alpha )F(\theta ')-F(\alpha \theta +(1- \alpha )\theta ')}$

est une divergence par différence de Jensen.

Signification physique

L'entropie de Rényi en physique quantique n'est pas considérée comme observable , en raison de sa dépendance non linéaire à la matrice densité. (Cette dépendance non linéaire s'applique même dans le cas particulier de l'entropie de Shannon.) On peut cependant lui donner un sens opérationnel grâce aux mesures en deux temps (également appelées statistiques de comptage complet) des transferts d'énergie.

La limite de l'entropie de Rényi est l' entropie de von Neumann . ${\displaystyle \alpha \to 1}$

Voir également

• Indices de diversité
• Entropie des tsallis
• Indice d'entropie généralisée

Remarques

Les références