энтропия Реньи

Понятие в теории информации

В теории информации энтропия Реньи — это величина, обобщающая различные понятия энтропии , включая энтропию Хартли , энтропию Шеннона , энтропию столкновений и минимальную энтропию . Энтропия Реньи названа в честь Альфреда Реньи , который искал наиболее общий способ количественной оценки информации, сохраняя при этом аддитивность для независимых событий. ^{[1] [2]} В контексте оценки фрактальной размерности энтропия Реньи составляет основу концепции обобщенных размерностей . ^[3]

Энтропия Реньи важна в экологии и статистике как индекс разнообразия . Энтропия Реньи также важна в квантовой информации , где она может использоваться как мера запутанности . В модели спиновой цепи Гейзенберга XY энтропия Реньи как функция α может быть вычислена явно, поскольку она является автоморфной функцией по отношению к конкретной подгруппе модулярной группы . ^{[4] [5]} В теоретической информатике минимальная энтропия используется в контексте экстракторов случайности .

Определение

Энтропия Реньи порядка ⁠ ⁠ ${\displaystyle \alpha }$ , где и ⁠ ⁠ , определяется как ^[1] ${\displaystyle 0<\alpha <\infty }$ ${\displaystyle \alpha \neq 1}$

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

Далее он определяется как ${\displaystyle \alpha =0,1,\infty }$

${\displaystyle \mathrm {H} _{\alpha }(X)=\lim _{\gamma \to \alpha }\mathrm {H} _{\gamma }(X).}$

Здесь, — дискретная случайная величина с возможными результатами в наборе и соответствующими вероятностями для ⁠ ⁠ . Результирующая единица информации определяется основанием логарифма , например, Шеннон для основания 2 или nat для основания e . Если вероятности равны для всех ⁠ ⁠ , то все энтропии Реньи распределения равны: ⁠ ⁠ . В общем случае для всех дискретных случайных величин ⁠ ⁠ , — невозрастающая функция по ⁠ ⁠ . ${\displaystyle X}$ ${\displaystyle {\mathcal {A}}=\{x_{1},x_{2},...,x_{n}\}}$ ${\displaystyle p_{i}\doteq \Pr(X=x_{i})}$ ${\displaystyle i=1,\dots ,n}$ ${\displaystyle p_{i}=1/n}$ ${\displaystyle i=1,\dots ,n}$ ${\displaystyle \mathrm {H} _{\alpha }(X)=\log n}$ ${\displaystyle X}$ ${\displaystyle \mathrm {H} _{\alpha }(X)}$ ${\displaystyle \alpha }$

Приложения часто используют следующее соотношение между энтропией Реньи и α - нормой вектора вероятностей:

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

Здесь дискретное распределение вероятностей интерпретируется как вектор с и ⁠ ⁠ . ${\displaystyle P=(p_{1},\dots ,p_{n})}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle p_{i}\geq 0}$ ${\displaystyle \textstyle \sum _{i=1}^{n}p_{i}=1}$

Энтропия Реньи для любого является вогнутой по Шуру . Доказано критерием Шура–Островского. ${\displaystyle \alpha \geq 0}$

Особые случаи

Энтропия Реньи случайной величины с двумя возможными исходами относительно p ₁ , где P = ( p ₁ , 1 − p ₁ ) . Показаны Η ₀ , Η ₁ , Η ₂ и Η _∞ , причем единицей на вертикальной оси является шеннон .

По мере приближения к нулю энтропия Реньи все более равномерно взвешивает все события с ненулевой вероятностью, независимо от их вероятностей. В пределе для ⁠ ⁠ энтропия Реньи — это просто логарифм размера носителя X . Пределом для является энтропия Шеннона . По мере приближения к бесконечности энтропия Реньи все больше определяется событиями с наибольшей вероятностью. ${\displaystyle \alpha }$ ${\displaystyle \alpha \to 0}$ ${\displaystyle \alpha \to 1}$ ${\displaystyle \alpha }$

Хартли или максимальная энтропия

${\displaystyle \mathrm {H} _{0}(X)}$где — число ненулевых вероятностей. ^[6] Если все вероятности не равны нулю, то это просто логарифм мощности алфавита ( ⁠ ⁠ ) ⁠ ⁠ , иногда называемый энтропией Хартли ⁠ ⁠ , ${\displaystyle \log n}$ ${\displaystyle n}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle X}$ ${\displaystyle X}$

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

энтропия Шеннона

Предельное значение as — энтропия Шеннона : ^[7] ${\displaystyle \mathrm {H} _{\alpha }}$ ${\displaystyle \alpha \to 1}$

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

Энтропия столкновения

Энтропия столкновений , иногда называемая просто «энтропией Реньи», относится к случаю ⁠ ⁠ ${\displaystyle \alpha =2}$ ,

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

где и независимы и одинаково распределены . Энтропия столкновений связана с индексом совпадения . Это отрицательный логарифм индекса разнообразия Симпсона . ${\displaystyle X}$ ${\displaystyle Y}$

Мин-энтропия

В пределе ⁠ ⁠ ${\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}\,.}$

Эквивалентно, минимальная энтропия — это наибольшее действительное число b, такое, что все события происходят с вероятностью не более ⁠ ⁠ . ${\displaystyle \mathrm {H} _{\infty }(X)}$ ${\displaystyle 2^{-b}}$

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

Минимальная энтропия имеет важное применение для экстракторов случайности в теоретической информатике : экстракторы способны извлекать случайность из случайных источников, имеющих большую минимальную энтропию; для этой задачи недостаточно иметь только большую энтропию Шеннона .

Неравенства для разных порядковα

Это не возрастает для любого заданного распределения вероятностей ⁠ ⁠ , что может быть доказано дифференцированием, ^[8] как ${\displaystyle \mathrm {H} _{\alpha }}$ ${\displaystyle \alpha }$ ${\displaystyle 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})={\frac {1}{(1-\alpha )^{2}}}D_{KL}(z\|p)}$

которая пропорциональна расхождению Кульбака–Лейблера (которое всегда неотрицательно), где ⁠ ⁠ ${\displaystyle \textstyle z_{i}=p_{i}^{\alpha }/\sum _{j=1}^{n}p_{j}^{\alpha }}$ . В частности, она строго положительна, за исключением случаев, когда распределение равномерно.

В пределе мы имеем ⁠ ⁠ . ${\displaystyle \alpha \to 1}$ ${\displaystyle -{\frac {d\mathrm {H} _{\alpha }}{d\alpha }}\to {\frac {1}{2}}\sum _{i}p_{i}(\ln p_{i}+H(p))^{2}}$

В частных случаях неравенства можно доказать также с помощью неравенства Йенсена : ^{[9] [10]}

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

Для значений ⁠ ⁠ ${\displaystyle \alpha >1}$ неравенства в другую сторону также имеют место. В частности, имеем ^{[11] [12]}

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

С другой стороны, энтропия Шеннона может быть произвольно высокой для случайной величины , которая имеет заданную минимальную энтропию. Примером этого является последовательность случайных величин для таких, что и так как но ⁠ ⁠ . ${\displaystyle \mathrm {H} _{1}}$ ${\displaystyle X}$ ${\displaystyle X_{n}\sim \{0,\ldots ,n\}}$ ${\displaystyle n\geq 1}$ ${\displaystyle P(X_{n}=0)=1/2}$ ${\displaystyle P(X_{n}=x)=1/(2n)}$ ${\displaystyle \mathrm {H} _{\infty }(X_{n})=\log 2}$ ${\displaystyle \mathrm {H} _{1}(X_{n})=(\log 2+\log 2n)/2}$

расхождение Реньи

Наряду с абсолютными энтропиями Реньи, Реньи также определил спектр мер расхождения, обобщающих расхождение Кульбака–Лейблера . ^[13]

Расхождение Реньи порядка ⁠ ⁠ ${\displaystyle \alpha }$ или альфа-расхождение распределения P от распределения Q определяется как

${\displaystyle D_{\alpha }(P\Vert Q)={\frac {1}{\alpha -1}}\log {\Bigg (}\sum _{i=1}^{n}{\frac {p_{i}^{\alpha }}{q_{i}^{\alpha -1}}}{\Bigg )}={\frac {1}{\alpha -1}}\log \mathbb {E} _{i\sim p}[(p_{i}/q_{i})^{\alpha -1}]\,}$

когда ⁠ ⁠ ${\displaystyle 0<\alpha <\infty }$ и ⁠ ⁠ ${\displaystyle \alpha \neq 1}$ . Мы можем определить расхождение Реньи для специальных значений α = 0, 1, ∞, взяв предел, и, в частности, предел α → 1 дает расхождение Кульбака–Лейблера.

Некоторые особые случаи:

⁠ ⁠ ${\displaystyle D_{0}(P\Vert Q)=-\log Q(\{i:p_{i}>0\})}$ : минус логарифм вероятности под Q того, что p _i > 0 ;

⁠ ⁠ ${\displaystyle D_{1/2}(P\Vert Q)=-2\log \sum _{i=1}^{n}{\sqrt {p_{i}q_{i}}}}$ : минус удвоенный логарифм коэффициента Бхаттачарьи ; (Nielsen & Boltz (2010))

⁠ ⁠ ${\displaystyle D_{1}(P\Vert Q)=\sum _{i=1}^{n}p_{i}\log {\frac {p_{i}}{q_{i}}}}$ : расхождение Кульбака–Лейблера ;

⁠ ⁠ ${\displaystyle D_{2}(P\Vert Q)=\log {\Big \langle }{\frac {p_{i}}{q_{i}}}{\Big \rangle }}$ : логарифм ожидаемого отношения вероятностей;

⁠ ⁠ ${\displaystyle D_{\infty }(P\Vert Q)=\log \sup _{i}{\frac {p_{i}}{q_{i}}}}$ : логарифм максимального отношения вероятностей.

Расхождение Реньи действительно является расхождением , что означает, что оно больше или равно нулю, и равно нулю только при P = Q. Для любых фиксированных распределений P и Q расхождение Реньи не убывает как функция своего порядка α и является непрерывным на множестве α , для которых оно конечно, ^[13] или, для краткости, информации порядка α, полученной, если распределение P заменить распределением Q. ^[1 ] ${\displaystyle D_{\alpha }(P\|Q)}$

Финансовая интерпретация

Пару распределений вероятностей можно рассматривать как азартную игру, в которой одно из распределений определяет официальные шансы, а другое содержит фактические вероятности. Знание фактических вероятностей позволяет игроку получать прибыль от игры. Ожидаемая норма прибыли связана с дивергенцией Реньи следующим образом ^[14]

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

где — распределение, определяющее официальные шансы (т.е. «рынок») для игры, — распределение, предполагаемое инвестором, а — неприятие риска инвестором ( относительное неприятие риска Эрроу–Пратта ). ${\displaystyle m}$ ${\displaystyle b}$ ${\displaystyle R}$

Если истинное распределение (не обязательно совпадает с убеждением инвестора ) , то долгосрочная реализованная ставка сходится к истинному ожиданию, которое имеет схожую математическую структуру ^[14] ${\displaystyle p}$ ${\displaystyle b}$

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

Свойства, характерные дляα= 1

Значение ⁠ ⁠ ${\displaystyle \alpha =1}$ , которое дает энтропию Шеннона и расхождение Кульбака–Лейблера , является единственным значением, при котором цепное правило условной вероятности выполняется точно:

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

для абсолютных энтропий и

${\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))\},}$

для относительных энтропий.

Последнее, в частности, означает, что если мы ищем распределение p ( x , a ) , которое минимизирует отклонение от некоторой базовой априорной меры m ( x , a ) , и получаем новую информацию, которая влияет только на распределение a , то распределение p ( x | a ) остается m ( x | a ) неизменным.

Другие расхождения Реньи удовлетворяют критериям положительности и непрерывности, инвариантности относительно преобразований координат один к одному и аддитивности, когда A и X независимы, так что если p ( A , X ) = p ( A ) p ( X ) , то

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

и

${\displaystyle D_{\alpha }(P(A)P(X)\|Q(A)Q(X))=D_{\alpha }(P(A)\|Q(A))+D_{\alpha }(P(X)\|Q(X)).}$

Более сильные свойства величин позволяют определить условную информацию и взаимную информацию из теории связи. ${\displaystyle \alpha =1}$

Экспоненциальные семьи

Энтропии и расхождения Реньи для экспоненциального семейства допускают простые выражения ^[15]

${\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)}$

и

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

где

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

является разностным расхождением Йенсена.

Физическое значение

Энтропия Реньи в квантовой физике не считается наблюдаемой величиной из -за ее нелинейной зависимости от матрицы плотности. (Эта нелинейная зависимость применима даже в частном случае энтропии Шеннона.) Однако ей можно придать операциональное значение посредством двукратных измерений (также известных как статистика полного счета) переносов энергии ^{[ требуется ссылка ]} .

Предел квантово-механической энтропии Реньи равен энтропии фон Неймана . ${\displaystyle \alpha \to 1}$

Смотрите также

• Индексы разнообразия
• Энтропия Цаллиса
• Обобщенный индекс энтропии

Примечания

1. Реньи (1961)
2. Риуль (2021)
3. Баррос, Ванесса; Руссо, Жером (2021-06-01). «Кратчайшее расстояние между несколькими орбитами и обобщенные фрактальные измерения». Annales Henri Poincaré . 22 (6): 1853–1885. arXiv : 1912.07516 . Bibcode : 2021AnHP...22.1853B. doi : 10.1007/s00023-021-01039-y. ISSN  1424-0661. S2CID  209376774.
4. Франчини, Its и Корепин (2008)
5. Итс и Корепин (2010)
6. RFC 4086, стр. 6
7. Бромили, Такер и Боухова-Такер (2004)
8. Бек и Шлегль (1993)
9. выполняется, потому что ⁠ ⁠ . ${\displaystyle \textstyle \mathrm {H} _{1}\geq \mathrm {H} _{2}}$ ${\displaystyle \textstyle \sum \limits _{i=1}^{M}{p_{i}\log p_{i}}\leq \log \sum \limits _{i=1}^{M}{p_{i}^{2}}}$
10. выполняется, потому что ⁠ ⁠ . ${\displaystyle \mathrm {H} _{\infty }\leq \mathrm {H} _{2}}$ ${\displaystyle \textstyle \log \sum \limits _{i=1}^{n}{p_{i}^{2}}\leq \log \sup _{i}p_{i}\left({\sum \limits _{i=1}^{n}{p_{i}}}\right)=\log \sup _{i}p_{i}}$
11. имеет место, потому что ${\displaystyle \mathrm {H} _{2}\leq 2\mathrm {H} _{\infty }}$ ${\displaystyle \textstyle \log \sum \limits _{i=1}^{n}{p_{i}^{2}}\geq \log \sup _{i}p_{i}^{2}=2\log \sup _{i}p_{i}}$
12. Девройе, Люк; Дьёрфи, Ласло; Лугоши, Габор (1996-04-04). Вероятностная теория распознавания образов (исправленное издание). Нью-Йорк, Нью-Йорк: Springer. ISBN 978-0-387-94618-4.
13. Ван Эрвен, Тим; Харремоэс, Питер (2014). «Дивергенция Реньи и дивергенция Кульбака – Лейблера». Транзакции IEEE по теории информации . 60 (7): 3797–3820. arXiv : 1206.2459 . дои :10.1109/TIT.2014.2320500. S2CID  17522805.
14. Соклаков (2018)
15. Нильсен и Нок (2011)

Ссылки

• Бек, Кристиан; Шлегль, Фридрих (1993). Термодинамика хаотических систем: введение . Cambridge University Press. ISBN 0521433673.
• Jizba, P.; Arimitsu, T. (2004). «Мир по Реньи: Термодинамика мультифрактальных систем». Annals of Physics . 312 (1): 17–59. arXiv : cond-mat/0207707 . Bibcode : 2004AnPhy.312...17J. doi : 10.1016/j.aop.2004.01.002. S2CID  119704502.
• Jizba, P.; Arimitsu, T. (2004). "О наблюдаемости энтропии Реньи". Physical Review E. 69 ( 2): 026128. arXiv : cond-mat/0307698 . Bibcode : 2004PhRvE..69b6128J. doi : 10.1103/PhysRevE.69.026128. PMID  14995541. S2CID  39231939.
• Бромили, Пенсильвания; Такер, Северная Каролина; Бухова-Такер, Э. (2004), Энтропия Шеннона, энтропия Реньи и информация , CiteSeerX  10.1.1.330.9856
• Franchini, F.; Its, AR; Korepin, VE (2008). "Энтропия Реньи как мера запутанности в квантовой спиновой цепочке". Journal of Physics A: Mathematical and Theoretical . 41 (25302): 025302. arXiv : 0707.2534 . Bibcode :2008JPhA...41b5302F. doi :10.1088/1751-8113/41/2/025302. S2CID  119672750.
• «Тест Реньи», Энциклопедия математики , EMS Press , 2001 [1994]
• Hero, AO; Michael, O.; Gorman, J. (2002). Альфа-дивергенция для классификации, индексирования и поиска (PDF) (технический отчет CSPL-328). Лаборатория связи и обработки сигналов, Мичиганский университет. CiteSeerX  10.1.1.373.2763 .
• Итс, АР; Корепин, В.Е. (2010). «Обобщенная энтропия спиновой цепочки Гейзенберга». Теоретическая и математическая физика . 164 (3): 1136–1139. Bibcode :2010TMP...164.1136I. doi :10.1007/s11232-010-0091-6. S2CID  119525704.
• Нильсен, Ф.; Больц, С. (2010). «Центроиды Бурбеа-Рао и Бхаттачарьи». Труды IEEE по теории информации . 57 (8): 5455–5466. arXiv : 1004.5049 . doi : 10.1109/TIT.2011.2159046. S2CID  14238708.
• Nielsen, Frank; Nock, Richard (2012). "Выражение в замкнутой форме для энтропии Шармы–Миттала экспоненциальных семейств". Journal of Physics A . 45 (3): 032003. arXiv : 1112.4221 . Bibcode :2012JPhA...45c2003N. doi :10.1088/1751-8113/45/3/032003. S2CID  8653096.
• Нильсен, Франк; Нок, Ричард (2011). «Об энтропиях и расхождениях Реньи и Цаллиса для экспоненциальных семейств». Journal of Physics A . 45 (3): 032003. arXiv : 1105.3259 . Bibcode :2012JPhA...45c2003N. doi :10.1088/1751-8113/45/3/032003. S2CID  8653096.
• Реньи, Альфред (1961). «О мерах информации и энтропии» (PDF) . Труды четвертого симпозиума в Беркли по математике, статистике и теории вероятностей 1960 г. стр. 547–561.
• Россо, О.А. (2006). «Анализ ЭЭГ с использованием информационных инструментов на основе вейвлетов». Журнал методов нейронауки . 153 (2): 163–182. doi :10.1016/j.jneumeth.2005.10.009. PMID  16675027. S2CID  7134638.
• Zachos, CK (2007). «Классическая граница квантовой энтропии». Journal of Physics A. 40 ( 21): F407–F412. arXiv : hep-th/0609148 . Bibcode : 2007JPhA...40..407Z. doi : 10.1088/1751-8113/40/21/F02. S2CID  1619604.
• Назаров, Ю. (2011). "Потоки энтропий Реньи". Physical Review B. 84 ( 10): 205437. arXiv : 1108.3537 . Bibcode : 2015PhRvB..91j4303A. doi : 10.1103/PhysRevB.91.104303. S2CID  40312624.
• Ансари, Мохаммад Х.; Назаров, Юлий В. (2015). «Потоки энтропии Реньи из квантовых тепловых двигателей». Physical Review B. 91 ( 10): 104303. arXiv : 1408.3910 . Bibcode : 2015PhRvB..91j4303A. doi : 10.1103/PhysRevB.91.104303. S2CID  40312624.
• Ansari, Mohammad H.; Nazarov, Yuli V. (2015). "Точное соответствие между потоками энтропии Реньи и физическими потоками". Physical Review B. 91 ( 17): 174307. arXiv : 1502.08020 . Bibcode : 2015PhRvB..91q4307A. doi : 10.1103/PhysRevB.91.174307. S2CID  36847902.
• Соклаков, АН (2020). «Экономика разногласий — финансовая интуиция для расхождения Реньи». Энтропия . 22 (8): 860. arXiv : 1811.08308 . Bibcode : 2020Entrp..22..860S. doi : 10.3390/e22080860 . PMC  7517462. PMID  33286632 .
• Ансари, Мохаммед Х.; ван Стинсел, Элвин; Назаров, Юлий В. (2019). «Производство энтропии в квантовой системе разное». Энтропия . 21 (9): 854. arXiv : 1907.09241 . дои : 10.3390/e21090854 . S2CID  198148019.
• Риуль, Оливье (2021). «Это ИТ: Учебник по энтропии и информации Шеннона» (PDF) . Теория информации . Прогресс в математической физике. Том 78. Биркхойзер. С. 49–86. doi :10.1007/978-3-030-81480-9_2. ISBN 978-3-030-81479-3. S2CID  204783328.