Przydatność entropii Renyi?

14

Większość z nas zna - lub przynajmniej słyszała - entropię Shannona zmiennej losowej, $H(X) = -\mathbb{E} \bigl[ \log p(X)\bigr]$ oraz wszystkie powiązane miary teoretyczne, takie jak entropia względna, wzajemna informacja i tak dalej. Istnieje kilka innych miar entropii, które są powszechnie stosowane w informatyce teoretycznej i teorii informacji, takich jak min-entropia zmiennej losowej.

Zacząłem częściej oglądać tak zwane entropie Renyi, gdy przeglądam literaturę. Uogólniają one entropię Shannona i entropię minową i faktycznie zapewniają całe spektrum miar entropicznych zmiennej losowej. Pracuję głównie w obszarze informacji kwantowej, w której kwantowa wersja entropii Renyi jest również rozważana dość często.

Nie do końca rozumiem, dlaczego są przydatne. Słyszałem, że często łatwiej jest pracować analitycznie, niż powiedzmy entropię Shannon / von Neumann lub min-entropię. Ale można je również powiązać z entropią Shannona / entropią min.

Czy ktoś może podać przykłady (klasyczne lub kwantowe), gdy stosowanie entropii Renyi jest „właściwą rzeczą”? To, czego szukam, to jakiś „mentalny haczyk” lub „szablon” pozwalający dowiedzieć się, kiedy mogę użyć entropii Renyi.

Dzięki!

it.information-theory quantum-information

— Henry Yuen
źródło

Dodatek do mojej odpowiedzi: Wydaje się, że istnieje probabilistyczna definicja entropii q-Renyi (

) i, e

q \in Z^{+}

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

. Następnie

i ten RHS nazywa się `` Shannon Entropy ". Jeden określa również drugi limit, tj.

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

. Wydaje się, że pomysły te znalazły zastosowanie w konstrukcji ekspanderów, jak pokazano tutaj, 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

Rozważmy próbując zgadnąć atomowych do nieznanej zmiennej losowej rozpostartej na jakiś skończony zbiór W entropii Shannona zakłada się, że możesz przesyłać zapytania krok po kroku, tzn. Jeśli możesz zapytać: $X$ $A.$ $A=\{1,\ldots,N\}$

Czy ? $X\in \{1,\ldots,N/2\}$ (zakładaj parzysty lub użyj funkcji podłogi / sufitu) $N$

W przypadku szyfrowania i niektórych scenariuszy dekodowania nie jest to realistyczne. Próbując odgadnąć nieznane hasło, musisz wykonać zapytania atomowe, tzn. Zapytać, czy jest określoną wartością. $X$

Okazuje się, że oczekiwana liczba zapytań do odgadnięcia zmienną losową potem zależy ściśle od entropii Renyi zamówienia Tak samo niektóre wyższe momenty. Na przykład $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}$

a licznik jest zasadniczo logarytm Renyi entropii rzędu $1/2.$ Można także dokonać Shannon entropii bardzo duży podczas Renyi entropia i oczekiwanie na liczbę prób jest bardzo mała. Jeśli polegałeś na entropii Shannona dla bezpieczeństwa, miałbyś wtedy kłopoty.

Zobacz także powiązane pytanie Zgadywanie niskiej wartości entropii przy wielu próbach

Niektóre referencje:

JO Pliam, O nieporównywalności Entropii i marginalnych domysłów w atakach brutalnej siły. INDOCRYPT 2000: 67-79
E. Arikan, Nierówność zgadywania i jego zastosowanie do sekwencyjnego dekodowania. Transakcje IEEE dotyczące teorii informacji 42 (1): 99–105,1996.
S. Boztas, O entropiach Renyi i ich zastosowaniach do zgadywania ataków w kryptografii, Transakcje IEICE na podstawach elektroniki, komunikacji i informatyki 97 (12): 2542-2548, 2014.

— kodlu
źródło

Nie mogę uzyskać dostępu do tego artykułu S.Boztas. Masz publicznie dostępny link?

— Anirbit

@Anirbit zobacz repozytorium badań RMIT, researchbank.rmit.edu.au

— kodlu

Przeszukałem ten link. Zajęło mi to tylko kręgi. Nigdy nie znalazłem publicznie dostępnego pliku pdf!

— Anirbit

@Airirbit, przepraszam, myślałem, że to tam naprawdę zdeponowano!

— kodlu

18

Renyi entropia jest analogiczna, w pewnym sensie, do -norms, więc najpierw przypomnieć Załóżmy, dlaczego te normy są użyteczne. $\ell_p$

Załóżmy, że mamy wektor liczb . Chcemy mieć jeden numer, który reprezentuje w pewnym sensie, w jaki sposób typowy element wyglądać. $a \in \mathbb{R}^n$ $a$

Jednym ze sposobów jest pobranie średniej liczb w , która z grubsza odpowiada normie : . Jest to często przydatne, ale w przypadku niektórych aplikacji ma następujące problemy: Po pierwsze, norma nie daje nam dobrej górnej granicy największego elementu , ponieważ jeśli jest jeden duży element i wiele zer, norma będzie znacznie mniejsza niż największy element. Z drugiej strony $a$ $\ell_1$ $\mathbb{E}_{1 \le i \le n}[|a_i|]$ $\ell_1$ $a$ $\ell_1$ $\ell_1$ norma również nie daje nam dobre związanie na jak małe elementy są, na przykład, ile zer ma - ten problem występuje w dokładnie taki sam scenariusz jak poprzednio. $a$ $a$

Oczywiście, gdy elementy dużo sprzeczności, tak jak w scenariuszu skrajnym jak powyżej, żadna ilość może dać rozwiązać oba problemy powyżej. Mamy kompromis. Na przykład, jeśli chcemy poznać tylko największy element, możemy zastosować normę , ale wtedy utracimy wszystkie informacje o mniejszych elementach. Jeśli chcemy liczby zer, możemy spojrzeć na normę , która jest tylko rozmiarem wsparcia . $a$ $\ell_\infty$ $\ell_0$ $a$

Powodem do rozważenia norm jest to, że dają nam one ciągły kompromis między dwiema skrajnościami. Jeśli chcemy uzyskać więcej informacji na temat dużych elementów, przyjmujemy, że jest większe i odwrotnie. $\ell_p$ $p$

To samo dotyczy entropii Renyi: entropia Shanon jest jak normą - mówi nam coś o „typowej” prawdopodobieństwa elementu, ale nic o wariancji lub skrajnościami. Minimalna entropia daje nam informacje o elemencie z największym prawdopodobieństwem, ale traci wszystkie informacje o reszcie. Rozmiar podpory daje drugą skrajność. Entropie Renyi dają nam ciągły kompromis między dwiema skrajnościami. $\ell_1$

Na przykład, wielokrotnie entropia Renyi-2 jest przydatna, ponieważ z jednej strony jest bliska entropii Shanona, a zatem zawiera informacje o wszystkich elementach w rozkładzie, a z drugiej strony daje więcej informacji o elementach o największej prawdopodobieństwo. W szczególności wiadomo, że granice entropii Renyi-2 dają granice min-entropii, patrz np. Załącznik A tutaj: http://people.seas.harvard.edu/~salil/research/conductors-prelim .ps

— Lub Meir
źródło

11

Entropia Renyi (rzędu 2) jest przydatna w kryptografii do analizy prawdopodobieństwa kolizji.

Przypomnijmy, że entropia Renyi rzędu 2 losowej zmiennej jest podana przez $X$

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

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

Okazuje się, że pozwala zmierzyć prawdopodobieństwo, że dwie wartości narysowane zgodnie z rozkładem będą takie same („zderzają się”): prawdopodobieństwo to wynosi dokładnie . Po losowaniu razy z tego rozkładu oczekiwana liczba kolizji między tymi losowaniami wynosi . $H_2(X)$ $X$ $2^{-H_2(X)}$ $n$ $n$ $C(n,2) 2^{-H_2(X)}$

Fakty te są przydatne w kryptografii, w której kolizje mogą czasem stanowić problem i umożliwiają ataki.

W celu analizy innych zastosowań w kryptografii polecam następującą rozprawę doktorską:

Christian Cachin. Miary Entropii i bezwarunkowe bezpieczeństwo w kryptografii . Rozprawa doktorska, ETH Zurich, maj 1997.

— DW
źródło

Czy istnieje taka bezpośrednia probabilistyczna definicja jakiejkolwiek entropii q-Renyi? (jak widać z mojej odpowiedzi, jedyny sposób, w jaki znam to definiowanie przy dowolnym q, to definiowanie funkcji podziału odpowiadających układowi fizycznemu określonemu przez jego Lagrangian lub Hamiltonian lub jego działanie)

— Anirbit

@Airirbit, nie wiem. Żadne, które pamiętam, widząc (chociaż jest to możliwe, że entropia q-Renyi może prowadzić do granic innych granic, na których nam zależy ...)

— DW

Wydaje się również, że „entropia informacji” wydaje się zasadniczo „entropią termodynamiczną”. Więc nawet przy (q = 1) entropii Renyi, tj. Entropii splątania, istnieje konceptualna luka co do złożoności jej interpretacji?

— Anirbit

@DW: Dobra odpowiedź, zaniedbałem uwzględnienia tego przypadku: rzeczywiście wydaje się, że entropie Renyi różnych rzędów są powiązane z różnymi scenariuszami kryptograficznymi, w tym na przykład z min-entropią (która odpowiada zbliżającemu się parametrowi Renyi

- \infty

$-\infty$ ), który odgrywa rolę w ekstrakcji losowości.

— kodlu

@DW Wygląda na to, że istnieje interpretacja probabilistyczna. Zobacz mój komentarz do pierwotnego pytania.

— Anirbit

3

Ta inna odpowiedź stackexchange i ten post na blogu mogą być bardzo pomocne, aby szybko zapoznać się z podstawowym przykładem,

Roughly speaking Renyi entropies know about the excited states of a quantum system but the entanglement entropy knows about the ground states. WARNING: This intuition could be terribly crude but might just be a good "mental hook" :D I would be VERY happy to know of a better and precise way to say this!

One can think of calculating the entanglement entropy $S_1$ (which is a more physical quantity) as the singular limit of calculating the Renyi entropies ( $S_q$ for each $q \in \mathbb{Z}^+$ ). But this limit $S_1 = limit_{q \rightarrow 1} S_q$ is terribly badly defined. So often the idea is that one can calculate $S_q$ at an arbitrary integer value and then do an analytic continuation of that to $q \in \mathbb{R}$ and then try to define taking of the $q \rightarrow 1$ limit. (though always $q \in \mathbb{R}$ , this I call "analytic" continuation because often enough one needs to do the interpolation via contours in the complex plane - and the continuation can depend on what contours one chooses through the poles and branch-cuts of the $S_q$ that one started with)

At integral values of $q>1$ typically there is a always a very well-defined construction in terms of some integration of some function on some $q-$ branched manifold. After one has done such an integration one happily forgets about the manifold used and just tries to do the analytic continuation parametrically in the variable $q$ .

There are always a lot of issues about existence and well-posedness when one tries to do these anayltic continuations - but for someone like me who is brought up on a daily diet of Feynman path-integrals its a very common issue to deal with and we have a lot of tools to address these. Three nice papers to look into for these issues are, http://arxiv.org/pdf/1306.5242.pdf, http://arxiv.org/pdf/1402.5396.pdf, http://arxiv.org/pdf/1303.7221.pdf (the last of these papers might be an easier starting point) This presentation might also help, https://www.icts.res.in/media/uploads/Talk/Document/Tadashi_Takayanagi.pdf

What Renyi entropy says in terms of quantum complexity theory might be an exciting question! Can one think of the Renyi index as somehow parameterizing a hierarchy of complexity classes? That should be fun if true! Do let me know :)

— Anirbit
źródło

0

Renyi entropy has found its way into definitions of quantitative information flow, an area or security research. See G. Smith's survey paper.

— Kai
źródło