L'utilité des entropies Renyi?

14

La plupart d'entre nous connaissent - ou du moins ont entendu parler - l'entropie de Shannon d'une variable aléatoire, $H(X) = -\mathbb{E} \bigl[ \log p(X)\bigr]$ , et toutes les mesures théoriques de l'information connexes telles que l'entropie relative, informations mutuelles, etc. Il existe quelques autres mesures de l'entropie couramment utilisées en informatique théorique et en théorie de l'information, comme l'entropie minimale d'une variable aléatoire.

J'ai commencé à voir ces soi-disant entropies Renyi plus souvent en parcourant la littérature. Ils généralisent l'entropie de Shannon et l'entropie min, et fournissent en fait tout un spectre de mesures entropiques d'une variable aléatoire. Je travaille principalement dans le domaine de l'information quantique, où la version quantique de l'entropie Renyi est également considérée assez souvent.

Ce que je ne comprends pas vraiment, c'est pourquoi ils sont utiles. J'ai entendu dire qu'il est souvent plus facile de travailler avec des analyses que de dire l'entropie de Shannon / von Neumann ou l'entropie min. Mais ils peuvent également être liés à l'entropie / min-entropie de Shannon.

Quelqu'un peut-il fournir des exemples (classiques ou quantiques) de l'utilisation de l'entropie Renyi comme «la bonne chose à faire»? Ce que je recherche, c'est un «crochet mental» ou un «modèle» pour savoir quand je pourrais utiliser des entropies Renyi.

Merci!

it.information-theory quantum-information Henry Yuen
la source

Addendum à ma réponse: Il semble qu'il existe une définition probabiliste de l'entropie q-Renyi (

) i, e

q \in Z^{+}

$q \in \mathbb{Z}^+$

. Alors

et cette RHS est appelée "Entropie de Shannon". On définit également l'autre limite soit

H_{q} ({p_{i}}_{i = 1}^{n}) = \frac{1}{1 - q} l n [\sum_{k = 1}^{n} p_{k}^{q}]

$H_q (\{ p_i \}_{i=1}^n )= \frac{1}{1-q} ln [ \sum_{k=1}^n p_k^q ]$

l i m_{q \to 1} H_{q} = - \sum p_{k} l n (p_{k})

$lim_{q \rightarrow 1} H_q = - \sum p_k ln (p_k)$

. Ces idées semblent avoir trouvé des utilisations dans la construction d'extensions comme on le voit ici, math.rutgers.edu/~sk1233/courses/topics-S13, math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/CRVW01/crvw01.pdf, arxiv. org / pdf / math / 0406038.pdf

H_{\infty} (X) = l n [\frac{1}{m a x_{a} P r [X = a]}]

$H_{\infty} (X) = ln [\frac{1}{ max_{a} Pr[X=a]} ]$

Anirbit

15

Pensez à essayer de faire des suppositions atomiques pour une variable aléatoire inconnue répartie sur un certain ensemble fini Dans l'entropie de Shannon, on suppose que vous pouvez interroger petit à petit, c'est-à-dire que si vous pouvez demander: $X$ $A.$ $A=\{1,\ldots,N\}$

Est-ce que ? $X\in \{1,\ldots,N/2\}$ (supposez pair ou utilisez les fonctions plancher / plafond) $N$

En crypto et certains scénarios de décodage, ce n'est pas réaliste. Essayer de deviner un mot de passe inconnu dont vous avez besoin pour faire des requêtes atomiques, c'est-à-dire demander si est une valeur spécifique. $X$

Il s'avère que le nombre attendu de requêtes pour deviner une variable aléatoire dépend alors étroitement de l'entropie Renyi d'ordre Il en va de même pour les moments supérieurs. Par exemple $X$ $1/2.$

E [G] \leq \frac{(\sum_{x \in A} P_{X} (x)^{1 / 2})^{2}}{2}

$E[G]\leq \frac{(\sum_{x \in A} P_X(x)^{1/2})^2}{2}$

et le numérateur est essentiellement le logarithme de l'entropie de Renyi d'ordre On peut aussi rendre l'entropie de Shannon très grande tandis que l'entropie de Renyi et l'attente du nombre de suppositions sont très petites. Si vous comptiez sur l'entropie de Shannon pour la sécurité, vous auriez des ennuis dans ce cas. $1/2.$

Veuillez également consulter la question connexe Deviner une faible valeur d'entropie lors de plusieurs tentatives

Quelques références:

JO Pliam, Sur l'incomparabilité de l'entropie et des devinettes marginales dans les attaques par force brute. INDOCRYPT 2000: 67-79
E. Arikan, Une inégalité sur les devinettes et son application au décodage séquentiel. Transactions IEEE sur la théorie de l'information 42 (1): 99-105,1996.
Boztas, On Renyi entropies and their applications to guessing attack in cryptography, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 97 (12): 2542-2548, 2014.

kodlu
la source

Je ne parviens pas à accéder à ce document S.Boztas. Vous avez un lien accessible au public?

Anirbit

@Anirbit voir le référentiel de recherche RMIT, researchbank.rmit.edu.au

kodlu

J'ai cherché via ce lien. Cela ne m'a pris que dans les cercles. Je n'ai jamais trouvé de fichier pdf accessible au public!

Anirbit

@Anirbit, désolé, je pensais qu'il y était vraiment déposé!

kodlu

18

L'entropie de Renyi est analogue, dans un certain sens, à $\ell_p$ normales, alors rappelons d'abord pourquoi ces normes sont utiles.

Supposons que nous ayons un vecteur de nombres . Nous voulons avoir un numéro unique qui représente, dans un certain sens, comment l'élément typique d' $a \in \mathbb{R}^n$ $a$ .

Une façon de le faire est de prendre la moyenne des nombres dans , ce qui correspond à peu près à la norme : . Ceci est souvent utile, mais pour certaines applications, il présente les problèmes suivants: Premièrement, la norme ne nous donne pas une bonne borne supérieure sur le plus grand élément de , car s'il y a un seul grand élément et plusieurs zéros, le norme sera significativement plus petite que l'élément le plus grand. En revanche, le $a$ $\ell_1$ $\mathbb{E}_{1 \le i \le n}[|a_i|]$ $\ell_1$ $a$ $\ell_1$ $\ell_1$ La norme ne nous donne pas non plus une bonne limite sur la taille des éléments d' , par exemple, le nombre de zéros d' $a$ $a$ a - ce problème se produit exactement le même scénario que précédemment.

Bien sûr, lorsque les éléments d' ont beaucoup de variance, comme dans le scénario extrême ci-dessus, aucun nombre unique ne peut résoudre les deux problèmes ci-dessus. Nous avons un compromis. Par exemple, si nous voulons seulement connaître l'élément le plus grand, nous pouvons utiliser la norme , mais nous perdrons alors toutes les informations sur les éléments les plus petits. Si nous voulons le nombre de zéros, nous pouvons regarder la norme , qui est juste la taille du support d' $a$ $\ell_\infty$ $\ell_0$ $a$ .

Maintenant, la raison pour laquelle nous considérons les normes est qu'elles nous donnent tout le compromis continu entre les deux extrêmes. Si nous voulons plus d'informations sur les grands éléments, nous considérons que est plus grand, et vice versa. $\ell_p$ $p$

Il en va de même pour les entropies de Renyi: l'entropie de Shanon est comme la norme - elle nous dit quelque chose sur la probabilité "typique" d'un élément, mais rien sur la variance ou les extrêmes. La min-entropie nous donne des informations sur l'élément avec la plus grande probabilité, mais perd toutes les informations sur le reste. La taille du support donne l'autre extrême. Les entropies Renyi nous donnent un compromis continu entre les deux extrêmes. $\ell_1$

Par exemple, plusieurs fois l'entropie Renyi-2 est utile car elle est d'une part proche de l'entropie de Shanon, et contient donc des informations sur tous les éléments de la distribution, et d'autre part donne plus d'informations sur les éléments avec la plus grande probabilité. En particulier, il est connu que les limites de l'entropie Renyi-2 donnent des limites sur l'entropie min, voir, par exemple, l'annexe A ici: http://people.seas.harvard.edu/~salil/research/conductors-prelim .ps

Ou Meir
la source

11

L'entropie Renyi (d'ordre 2) est utile en cryptographie pour analyser la probabilité de collisions.

Rappelons que l'entropie Renyi d'ordre 2 d'une variable aléatoire est donnée par $X$

H_{2} (X) = - \log_{2} \sum_{x} Pr [X = x]^{2} .

$H_2(X) = - \log_2 \sum_x \Pr[X=x]^2.$

Il s'avère que nous permet de mesurer la probabilité que deux valeurs tirées iid en fonction de la distribution de soient identiques ("collision"): cette probabilité est exactement . Après avoir tiré fois de cette distribution, le nombre attendu de collisions entre ces tirages est . $H_2(X)$ $X$ $2^{-H_2(X)}$ $n$ $n$ $C(n,2) 2^{-H_2(X)}$

Ces faits sont utiles en cryptographie, où les collisions peuvent parfois être problématiques et permettre des attaques.

Pour une analyse d'autres utilisations en cryptographie, je recommande la thèse de doctorat suivante:

Christian Cachin. Mesures d'entropie et sécurité inconditionnelle en cryptographie . Thèse de doctorat, ETH Zurich, mai 1997.

DW
la source

Existe-t-il une définition probabiliste directe d'une entropie q-Renyi? (comme vous pouvez le voir dans ma réponse, la seule façon que je sache de définir cela à q arbitraire est de définir des fonctions de partition correspondant à un système physique qui a été spécifié via son lagrangien ou hamiltonien ou son action)

Anirbit

@Anirbit, je ne sais pas. Aucune dont je me souviens avoir vu (bien qu'il soit possible que l'entropie q-Renyi puisse conduire à des limites sur d'autres limites qui nous intéressent ...)

DW

Il semble également que «l'entropie de l'information» semble être fondamentalement «l'entropie thermodynamique». Donc, même à (q = 1) -entropie de Renyi, c'est-à-dire entropie d'enchevêtrement, il y a un vide conceptuel sur l'interprétation de la complexité de celui-ci?

Anirbit

- \infty

$-\infty$

@DW Il semble y avoir une interprétation probabiliste. Voyez mon commentaire sur la question d'origine.

Anirbit

3

Cette autre réponse stackexchange et cet article de blog pourraient être très utiles pour avoir un aperçu rapide d'un exemple de base,

En gros, les entropies de Renyi connaissent les états excités d'un système quantique, mais l'entropie d'enchevêtrement connaît les états fondamentaux. AVERTISSEMENT: Cette intuition pourrait être terriblement grossière mais pourrait simplement être un bon "crochet mental": DI serait TRÈS heureux de connaître une façon meilleure et précise de le dire!

$S_1$ $S_q$ $q \in \mathbb{Z}^+$ $S_1 = limit_{q \rightarrow 1} S_q$ $S_q$ $q \in \mathbb{R}$ $q \rightarrow 1$ $q \in \mathbb{R}$ $S_q$ que l'on a commencé avec)

Aux valeurs intégrales de $q>1$ il y a généralement une construction toujours très bien définie en termes d'intégration de certaines fonctions sur certaines $q-$ manifold ramifié. Après avoir fait une telle intégration, on oublie joyeusement la variété utilisée et essaie simplement de faire la continuation analytique paramétrique dans la variable $q$ .

Il y a toujours beaucoup de problèmes à propos de l'existence et de la bonne posture quand on essaie de faire ces continuations anayltic - mais pour quelqu'un comme moi qui est élevé quotidiennement au régime de Feynman-intégrales c'est un problème très commun à traiter et nous ont beaucoup d'outils pour y faire face. Trois beaux articles pour étudier ces problèmes sont: http://arxiv.org/pdf/1306.5242.pdf , http://arxiv.org/pdf/1402.5396.pdf , http://arxiv.org/pdf/1303.7221 .pdf (le dernier de ces articles pourrait être un point de départ plus facile) Cette présentation pourrait également aider, https://www.icts.res.in/media/uploads/Talk/Document/Tadashi_Takayanagi.pdf

Ce que dit l'entropie de Renyi en termes de théorie de la complexité quantique pourrait être une question passionnante! Peut-on penser à l'indice Renyi comme paramétrant en quelque sorte une hiérarchie de classes de complexité? Cela devrait être amusant si c'est vrai! Faites le moi savoir :)

Anirbit
la source

0

L'entropie Renyi a trouvé sa place dans les définitions du flux d'informations quantitatives , d'un domaine ou de la recherche sur la sécurité. Voir le document d'enquête de G. Smith .

Kai
la source

L'utilité des entropies Renyi?

Réponses: