Der Nutzen von Renyi-Entropien?

14

Die meisten von uns kennen die Shannon-Entropie einer Zufallsvariablen, , und alle damit zusammenhängenden informationstheoretische Maßnahmen wie relative Entropie, gegenseitige Information und so weiter. Es gibt einige andere Entropiemaßnahmen, die üblicherweise in der theoretischen Informatik und der Informationstheorie verwendet werden, beispielsweise die Min-Entropie einer Zufallsvariablen. $H(X) = -\mathbb{E} \bigl[ \log p(X)\bigr]$

Ich habe angefangen, diese sogenannten Renyi-Entropien häufiger zu sehen, wenn ich in der Literatur stöbere. Sie verallgemeinern die Shannon-Entropie und die Min-Entropie und liefern tatsächlich ein ganzes Spektrum von entropischen Maßen einer Zufallsvariablen. Ich arbeite hauptsächlich im Bereich der Quanteninformation, wo auch die Quantenversion der Renyi-Entropie häufig berücksichtigt wird.

Was ich nicht wirklich verstehe, ist, warum sie nützlich sind. Ich habe gehört, dass es oft einfacher ist, mit ihnen analytisch zu arbeiten, als Shannon / von Neumann-Entropie oder Minientropie zu sagen. Sie können aber auch auf die Shannon-Entropie / Min-Entropie zurückgeführt werden.

Kann jemand (klassische oder quantitative) Beispiele dafür nennen, dass die Verwendung von Renyi-Entropien "das Richtige ist"? Was ich suche, ist ein "mentaler Haken" oder eine "Vorlage", um zu wissen, wann ich Renyi-Entropien verwenden möchte.

Vielen Dank!

it.information-theory quantum-information Henry Yuen
quelle

Nachtrag zu meiner Antwort: Es scheint eine probabilistische Definition der q-Renyi-Entropie zu geben ( ) i, e . Dann ist und diese RHS wird "Shannon-Entropie" genannt. Eine definiert auch die andere Grenze, dh . Diese Ideen scheinen in der Expander-Konstruktion Verwendung gefunden zu haben, wie hier zu sehen ist: math.rutgers.edu/~sk1233/courses/topics-S13, math.ias. edu / ~ avi / PUBLICATIONS / MYPAPERS / CRVW01 / crvw01.pdf, arxiv.org/pdf/math/0406038.pdf

q \in Z^{+}

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

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)$

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

Überlegen Sie, ob Sie atomare Vermutungen für eine unbekannte Zufallsvariable anstellen möchten, die über eine endliche Menge In der Shannon-Entropie wird davon ausgegangen, dass Sie Bit für Bit abfragen können, dh, wenn Sie kann Fragen: $X$ $A.$ $A=\{1,\ldots,N\}$

Befindet sich ? $X\in \{1,\ldots,N/2\}$ (Nehmen Sie gerade an oder verwenden Sie Boden- / Deckenfunktionen) $N$

In Krypto- und einigen Dekodierungsszenarien ist dies nicht realistisch. Wenn Sie versuchen, ein unbekanntes Kennwort zu erraten, müssen Sie atomare Abfragen durchführen, dh abfragen, ob ein bestimmter Wert ist. $X$

Es stellt sich heraus, dass die erwartete Anzahl von Abfragen, um eine Zufallsvariable zu erraten, stark von der Renyi-Entropie der Ordnung abhängtAlso mach ein paar höhere Momente. Beispielsweise $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}$

und der Zähler ist im wesentlichen der Logarithmus der Renyi-Entropie der OrdnungMan kann die Shannon-Entropie auch sehr groß machen, während die Renyi-Entropie und die Erwartung der Anzahl von Vermutungen sehr klein ist. Wenn Sie sich aus Sicherheitsgründen auf Shannon-Entropie verlassen würden, wären Sie in diesem Fall in Schwierigkeiten. $1/2.$

Bitte beachten Sie auch die entsprechende Frage Ermitteln eines niedrigen Entropiewerts bei mehreren Versuchen

Einige Referenzen:

JO Pliam, Über die Unvergleichbarkeit von Entropie und marginale Vermutungen bei Brute-Force-Angriffen. INDOCRYPT 2000: 67 & ndash; 79
E. Arikan, Eine Ungleichung beim Erraten und seiner Anwendung auf die sequentielle Decodierung. IEEE-Transaktionen zur Informationstheorie 42 (1): 99-105,1996.
S. Boztas, Über Renyi-Entropien und ihre Anwendungen zur Vermutung von Angriffen in der Kryptographie, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 97 (12): 2542-2548, 2014.

kodlu
quelle

Ich kann nicht auf dieses S.Boztas-Dokument zugreifen. Sie haben einen öffentlich zugänglichen Link?

Anirbit

@Anirbit siehe RMIT Research Repository, researchbank.rmit.edu.au

kodlu

Ich habe diesen Link durchsucht. Es hat mich nur im Kreis geführt. Ich habe nie eine öffentlich zugängliche PDF-Datei gefunden!

Anirbit

@Anirbit, sorry, ich dachte es wäre wirklich dort hinterlegt!

Kodlu

18

Die Renyi-Entropie ist in gewissem Sinne analog zu -norms. Erinnern wir uns also zunächst, warum diese Normen nützlich sind. $\ell_p$

Angenommen, wir haben einen Vektor von Zahlen . Wir wollen eine einzige Zahl haben , die in einem gewissen Sinne darstellt, wie funktioniert das typische Element aussehen. $a \in \mathbb{R}^n$ $a$

Eine Möglichkeit besteht darin, den Durchschnitt der Zahlen in , der ungefähr der Norm entspricht: . Dies ist oft nützlich, hat aber für einige Anwendungen die folgenden Probleme: Erstens gibt uns die Norm keine gute Obergrenze für das größte Element von , denn wenn es ein einzelnes großes Element und viele Nullen gibt, das Norm ist deutlich kleiner als das größte Element. Auf der anderen Seite ist die $a$ $\ell_1$ $\mathbb{E}_{1 \le i \le n}[|a_i|]$ $\ell_1$ $a$ $\ell_1$ $\ell_1$ Norm gibt uns auch keine gute Grenze dafür, wie klein die Elemente von sind, zum Beispiel wie viele Nullen hat - dieses Problem tritt in genau demselben Szenario wie zuvor auf. $a$ $a$

Wenn die Elemente von sehr unterschiedlich sind, wie im obigen Extremszenario, kann natürlich keine einzelne Zahl beide oben genannten Probleme lösen. Wir haben einen Kompromiss. Zum Beispiel, wenn wir das größte Element nur wissen wollen, können wir die Verwendung Norm, aber dann werden wir alle Informationen über die kleineren Elemente verlieren. Wenn wir die Anzahl der Nullen wollen, können wir uns die Norm ansehen , die genau die Größe der Unterstützung von . $a$ $\ell_\infty$ $\ell_0$ $a$

Der Grund für die Betrachtung von Normen ist, dass sie uns den gesamten ständigen Kompromiss zwischen den beiden Extremen ermöglichen. Wenn wir mehr Informationen über die großen Elemente wünschen, nehmen wir an, dass größer ist und umgekehrt. $\ell_p$ $p$

Gleiches gilt für Renyi-Entropien: Shanons Entropie entspricht der Norm - sie sagt etwas über die "typische" Wahrscheinlichkeit eines Elements aus, aber nichts über die Varianz oder die Extreme. Die Minentropie gibt uns Informationen über das Element mit der größten Wahrscheinlichkeit, verliert jedoch alle Informationen über den Rest. Die Stützgröße gibt das andere Extrem an. Die Renyi-Entropien bieten uns einen ständigen Kompromiss zwischen den beiden Extremen. $\ell_1$

Zum Beispiel ist die Renyi-2-Entropie oft nützlich, weil sie einerseits nahe an der Entropie von Shanon liegt und somit Informationen zu allen Elementen der Verteilung enthält und andererseits mehr Informationen zu den Elementen mit den größten Elementen liefert Wahrscheinlichkeit. Insbesondere ist bekannt, dass Grenzen für die Renyi-2-Entropie Grenzen für die Min-Entropie ergeben, siehe z. B. Anhang A hier: http://people.seas.harvard.edu/~salil/research/conductors-prelim .ps

Oder Meir
quelle

11

Die Renyi-Entropie (der Ordnung 2) ist in der Kryptographie zur Analyse der Kollisionswahrscheinlichkeit nützlich.

Man erinnere sich, dass die Renyi-Entropie der Ordnung 2 einer Zufallsvariablen durch gegeben ist $X$

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

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

$H_2(X)$ $X$ $2^{-H_2(X)}$ $n$ $n$ $C(n,2) 2^{-H_2(X)}$

Diese Fakten sind nützlich in der Kryptographie, wo Kollisionen manchmal problematisch sein können und Angriffe ermöglichen.

Für einige Analysen anderer Anwendungen in der Kryptographie empfehle ich folgende Dissertation:

Christian Cachin. Entropiemaßnahmen und bedingungslose Sicherheit in der Kryptographie . Dissertation, ETH Zürich, Mai 1997.

DW
quelle

Gibt es eine so direkte probabilistische Definition einer q-Renyi-Entropie? (Wie Sie meiner Antwort entnehmen können, kann ich dies nur durch Definieren von Partitionsfunktionen definieren, die einem physikalischen System entsprechen, das über seinen Lagrange- oder Hamilton-Operator oder seine Aktion spezifiziert wurde.)

Anirbit

@Anirbit, ich weiß nicht. Keine, an die ich mich erinnere (obwohl es möglich ist, dass die q-Renyi-Entropie zu Grenzen für andere Grenzen führt, die uns wichtig sind ...)

DW

Auch scheint "Informationsentropie" im Grunde genommen die "thermodynamische Entropie" zu sein. Also gibt es auch bei (q = 1) -Renyi-Entropie, dh Verschränkungsentropie, eine konzeptionelle Lücke bezüglich der Komplexitätsinterpretation?

Anirbit

@DW: Gute Antwort, ich habe diesen Fall vernachlässigt: In der Tat scheint es, dass Renyi-Entropien verschiedener Ordnung mit verschiedenen kryptografischen Szenarien verbunden sind, einschließlich zum Beispiel der Min-Entropie (die dem Renyi-Parameter Annäherung entspricht

), die eine spielt Teil der Zufälligkeitsextraktion.

- \infty

$-\infty$

Kodlu

@ DW Es scheint eine probabilistische Interpretation zu geben. Siehe meinen Kommentar zur ursprünglichen Frage.

Anirbit,

3

Diese andere Antwort von stackexchange und dieser Blog-Beitrag könnten sehr hilfreich sein, um ein schnelles Gefühl für ein grundlegendes Beispiel zu bekommen.

Grob gesagt kennen Renyi-Entropien die angeregten Zustände eines Quantensystems, aber die Verschränkungsentropie kennt die Grundzustände. WARNUNG: Diese Intuition könnte furchtbar grob sein, könnte aber auch nur ein guter "mentaler Haken" sein: DI würde sich SEHR freuen, eine bessere und präzise Möglichkeit zu finden, dies zu sagen!

$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$

$q>1$ $q-$ $q$

Wenn man versucht, diese anayltischen Fortsetzungen zu machen, gibt es immer eine Menge Probleme mit der Existenz und dem Wohlbefinden - aber für jemanden wie mich, der auf einer täglichen Diät mit Feynman-Pfad-Integralen aufgezogen wird, ist es ein sehr häufiges Problem, mit dem man sich befasst und wir Ich habe eine Menge Werkzeuge, um diese Probleme anzugehen. Drei nützliche Artikel, in denen Sie nach diesen Themen suchen können, sind http://arxiv.org/pdf/1306.5242.pdf , http://arxiv.org/pdf/1402.5396.pdf , http://arxiv.org/pdf/1303.7221 .pdf (der letzte dieser Artikel ist möglicherweise ein einfacher Ausgangspunkt) Diese Präsentation kann auch hilfreich sein: https://www.icts.res.in/media/uploads/Talk/Document/Tadashi_Takayanagi.pdf

Was die Renyi-Entropie in Bezug auf die Quantenkomplexitätstheorie sagt, könnte eine spannende Frage sein! Kann man sich den Renyi-Index als eine Art Parametrisierung einer Hierarchie von Komplexitätsklassen vorstellen? Das sollte Spaß machen, wenn es stimmt! Lass es mich wissen :)

Anirbit
quelle

0

Die Renyi-Entropie hat ihren Weg in Definitionen des quantitativen Informationsflusses , eines Gebiets oder der Sicherheitsforschung gefunden. Siehe das Umfragepapier von G. Smith .

Kai
quelle

Der Nutzen von Renyi-Entropien?

Antworten: