Полезность энтропий Реньи?

14

Большинство из нас знакомы или, по крайней мере, слышали о энтропии Шеннона случайной величины, H(X)=E[logp(X)] , и обо всех связанных с этим теоретико-информационных мерах, таких как относительная энтропия, взаимная информация и так далее. Есть несколько других мер энтропии, которые обычно используются в теоретической информатике и теории информации, такие как мин-энтропия случайной величины.

Я начал видеть эти так называемые энтропии Реньи чаще, когда просматриваю литературу. Они обобщают энтропию Шеннона и мин-энтропию и фактически предоставляют целый спектр энтропийных мер случайной величины. Я работаю в основном в области квантовой информации, где также часто рассматривается квантовая версия энтропии Реньи.

То, что я не понимаю, почему они полезны. Я слышал, что часто с ними аналитически легче работать, чем, скажем, с энтропией Шеннона / фон Неймана или мин-энтропией. Но они также могут быть связаны с энтропией / мин-энтропией Шеннона.

Может ли кто-нибудь привести примеры (классические или квантовые) того, когда использование энтропий Реньи является «правильным решением»? То, что я ищу, - это какой-то «умственный крючок» или «шаблон», позволяющий узнать, когда я захочу использовать энтропии Рени.

Благодарность!

Генри Юн
источник
Приложение к моему ответу: Кажется, что существует вероятностное определение энтропии q-реньи ( ) i, e H q ( { p i } n i = 1 ) = 1qZ+. Тогдаlimq1Hq=-pkln(pk),и эта RHS называется «энтропией Шеннона». Один также определяет другой предел, т.е.H(X)=ln[1Hq({pi}i=1n)=11-QLN[ΣКзнак равно1NпКQ]LямQ1ЧАСQзнак равно-ΣпКLN(пК). Эти идеи, похоже, нашли применение в конструкции экспандеров, как показано здесь, math.rutgers.edu/~sk1233/courses/topics-S13, math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/CRVW01/crvw01.pdf, arxiv. org / pdf / math / 0406038.pdfЧАС(Икс)знак равноLN[1мaИксaпр[Иксзнак равноa]]
Anirbit

Ответы:

15

Рассмотрим пытается сделать атомные догадки по неизвестной случайной величины , распределенной по некоторому конечному множеству A . В энтропии Шеннона предполагается, что вы можете выполнять запрос побитно, т. Е. Если A = { 1 , , N }, вы можете спросить:XA.A={1,,N}

Является ли ? X{1,,N/2}(предположим, что четное или использовать функции пола / потолка)N

В криптографии и некоторых сценариях декодирования это нереально. Пытаясь угадать неизвестный пароль, вам нужно сделать атомарные запросы, т.е. запросить, если является конкретным значением.X

Оказывается , что ожидаемое число запросов угадать случайную величину , то плотно зависит от энтропии Реньи порядка 1 / 2. Так что некоторые высшие моменты. НапримерX1/2.

E[G](xAPX(x)1/2)22

а числитель является по существу логарифмом Рения энтропии порядка Можно также сделать Шеннон энтропия очень велик , а энтропия Реньи и ожидание числа догадок очень мало. Если вы полагаетесь на энтропию Шеннона для обеспечения безопасности, в этом случае у вас будут проблемы.1/2.

Также см. Соответствующий вопрос « Угадайте низкое значение энтропии при нескольких попытках».

Некоторые ссылки:

  1. Ю.О. Плиам. О несопоставимости энтропии и предельной догадки в атаках грубой силы. INDOCRYPT 2000: 67-79
  2. Э. Арикан, Неравенство по угадыванию и его применение к последовательному декодированию. IEEE Труды по теории информации 42 (1): 99-105, 1996.
  3. Бозтас С. Об энтропиях Реньи и их приложениях к угадыванию атак в криптографии. Операции IEICE с основами электроники, связи и компьютерных наук 97 (12): 2542-2548, 2014.
kodlu
источник
Я не могу получить доступ к этой статье С.Бозтаса. У вас есть общедоступная ссылка?
Anirbit
@Anirbit см. Исследовательский репозиторий RMIT, researchbank.rmit.edu.au
кодлу
Я искал по этой ссылке. Это только взял меня в кругах. Я никогда не находил общедоступный файл PDF!
Anirbit
@ Anirbit, извини, я думал, что он там действительно хранится!
Кодлу
18

Энтропия Реньи в некотором смысле аналогична -нормам, поэтому давайте сначала вспомним, почему эти нормы полезны.p

Предположим, у нас есть вектор чисел . Мы хотим иметь одно число , которое представляет, в каком - то смысле, как делает типичный элемент в выглядеть.aRna

Один из способов сделать это - взять среднее число чисел в , что примерно соответствует норме 1 : E 1 i a1. Это часто бывает полезно, но для некоторых применений имеют следующие проблемы:первых,1 норма не дает нам хорошую верхнюю границу на наибольшем элементе, потому что если есть один большой элемент и много нулей, то1 норма будет значительно меньше, чем самый большой элемент. С другой стороны,1E1in[|ai|]1a11норма также не дает нам хорошей оценки того, насколько малы элементы , например, сколько нулей имеет a - эта проблема возникает точно в том же сценарии, что и раньше.aa

Конечно, когда элементы много дисперсии, например, в крайнем случае , как указано выше, ни один номер не может дать решить обе проблемы выше. У нас есть компромисс. Например, если мы хотим знать , самый большой элемент, мы можем использовать л норму, но тогда мы потеряем всю информацию о более мелких элементах. Если нам нужно количество нулей, мы можем посмотреть на норму 0 , которая является просто размером поддержки a .a0a

Теперь, причина для рассмотрения норм состоит в том, что они дают нам весь непрерывный компромисс между двумя крайностями. Если мы хотим получить больше информации о больших элементах, мы берем p, чтобы быть больше, и наоборот.pp

То же самое относится и к Рению энтропии: энтропия Shanon является как норма - это говорит нам кой - что о «типичной» вероятность элемента, но ничего о дисперсии или крайностях. Мин-энтропия дает нам информацию об элементе с наибольшей вероятностью, но теряет всю информацию об остальном. Размер поддержки дает другую крайность. Энтропии Реньи дают нам непрерывный компромисс между двумя крайностями.1

Например, много раз энтропия Реньи-2 полезна, потому что она, с одной стороны, близка к энтропии Шенона и, таким образом, содержит информацию обо всех элементах распределения, а с другой стороны дает больше информации об элементах с наибольшим вероятность. В частности, известно, что границы энтропии Реньи-2 дают границы минимальной энтропии, см., Например, Приложение A здесь: http://people.seas.harvard.edu/~salil/research/conductors-prelim. .ps

Или меир
источник
11

Энтропия Реньи (порядка 2) полезна в криптографии для анализа вероятности столкновений.

X

H2(X)=log2xPr[X=x]2.

H2(X)X2H2(X)nnC(n,2)2H2(X)

Эти факты полезны в криптографии, где коллизии могут иногда вызывать проблемы и включать атаки.

Для некоторого анализа других применений в криптографии я рекомендую следующую кандидатскую диссертацию:

Кристиан Качин. Меры энтропии и безусловная безопасность в криптографии . Докторская диссертация, ETH Zurich, май 1997.

DW
источник
Существует ли такое прямое вероятностное определение энтропии q-реньи? (как вы можете видеть из моего ответа, единственный способ определить это при произвольном q - это определить функции разбиения, соответствующие физической системе, которая была задана с помощью ее лагранжиана или гамильтониана или ее действия)
Anirbit
@ Анбит, я не знаю. Ничего из того, что я помню, не видел (хотя вполне возможно, что энтропия q-реньи может привести к границам для других границ, которые нас интересуют ...)
DW
Также кажется, что «информационная энтропия» в основном является «термодинамической энтропией». Таким образом, даже при (q = 1) -энтропии Реньи, т. Е. Энтропии запутанности, существует концептуальный пробел в интерпретации ее сложности?
Anirbit
@DW Кажется, есть вероятностная интерпретация. Смотрите мой комментарий на оригинальный вопрос.
Anirbit
3

Этот другой ответ об обмене стеками и этот пост в блоге могут быть очень полезны, чтобы быстро понять основной пример,

Грубо говоря, энтропии Реньи знают о возбужденных состояниях квантовой системы, но энтропия запутанности знает об основных состояниях. ПРЕДУПРЕЖДЕНИЕ: эта интуиция может быть ужасно грубой, но может быть хорошим «умственным крючком»: я был бы ОЧЕНЬ рад узнать о лучшем и точном способе сказать это!

S1SqqZ+S1=limitq1SqSqqRq1qRSq

q>1qq

Всегда есть много вопросов о существовании и правильности, когда кто-то пытается сделать эти аналитические продолжения - но для кого-то вроде меня, воспитанного на ежедневной диете интегралов по путям Фейнмана, это очень распространенная проблема, и мы есть много инструментов для решения этих проблем. Три хороших документа для изучения этих вопросов: http://arxiv.org/pdf/1306.5242.pdf , http://arxiv.org/pdf/1402.5396.pdf , http://arxiv.org/pdf/1303.7221. .pdf (последняя из этих статей может быть более легкой отправной точкой). Эта презентация также может помочь, https://www.icts.res.in/media/uploads/Talk/Document/Tadashi_Takayanagi.pdf.

То, что энтропия Реньи говорит в терминах квантовой теории сложности, может быть волнующим вопросом! Можно ли считать индекс Реньи параметризацией иерархии классов сложности? Это должно быть весело, если правда! Дай мне знать :)

Anirbit
источник