Дивергенция Йенсена — Шеннона

Дивергенция Йенсена — Шеннона^[1] — это метод измерения похожести двух распределений вероятностей. Она известна также как информационный радиус^[2] или полное отклонение от среднего^[3]. Дивергенция базируется на дивергенции Кульбака — Лейблера с некоторыми существенными (и полезными) отличиями, среди которых, что она симметрична и всегда имеет конечное значение. Квадратный корень из дивергенции Йенсена — Шеннона является метрикой, которая часто упоминается как расстояние Йенсена — Шеннона^[4]^[5]^[6].

Определение

Рассмотрим множество $M_{+}^{1}(A)$ распределений вероятности, где A — это множество, снабжённое некоторой сигма-алгеброй измеримых подмножеств. В частности, мы можем взять в качестве A конечное или счётное множество, в котором все подмножества измеримы.

Дивергенция Йенсена — Шеннона (англ. Jensen–Shannon divergence, JSD) $M_{+}^{1}(A)\times M_{+}^{1}(A)\rightarrow [0,\infty {})$ — это симметризованная и сглаженная версия дивергенции Кульбака — Лейблера $D(P\parallel Q)$ . Она определяется как

{\rm {JSD}}(P\parallel Q)={\frac {1}{2}}D(P\parallel M)+{\frac {1}{2}}D(Q\parallel M)

,

где $M={\frac {1}{2}}(P+Q)$

Недавно было предложено обобщение дивергенции Йенсена — Шеннона, в котором вместо арифметического среднего используется абстрактное среднее (наподобие геометрического или гармонического среднего)^[7]. Геометрическая дивергенция Йенсена — Шеннона (англ. G-Jensen–Shannon divergence) даёт явную a формулу дивергенции между двумя гауссовыми распределениями путём применения геометрического среднего.

Более общее определение, позволяющее сравнить более двух распределений вероятности (См):

{\rm {JSD}}_{\pi _{1},\ldots ,\pi _{n}}(P_{1},P_{2},\ldots ,P_{n})=H\left(\sum _{i=1}^{n}\pi _{i}P_{i}\right)-\sum _{i=1}^{n}\pi _{i}H(P_{i})

,

где $\pi _{1},\ldots ,\pi _{n}$ являются весами, выбранными для распределений вероятности $P_{1},P_{2},\ldots ,P_{n}$ , а $H(P)$ является энтропией Шеннона для распределения $P$ . Для случая двух распределений

P_{1}=P,P_{2}=Q,\pi _{1}=\pi _{2}={\frac {1}{2}}.\

Границы

Дивергенция Йенсена — Шеннона ограничена 1 для двух распределений вероятности, если (в дивергенции Кульбака — Лейблера) используется логарифм по основанию 2^[8]

0\leqslant {\rm {JSD}}(P\parallel Q)\leqslant 1

С такой нормализацией дивергенция Йенсена — Шеннона является нижней границей полного расстояния вариации^[англ.] между P и Q:

{\rm {JSD}}(P\parallel Q)\leqslant {\frac {1}{2}}\|P-Q\|_{1}={\frac {1}{2}}\sum _{\omega \in \Omega }|P(\omega )-Q(\omega )|.

Для натурального логарифма, который обычно используется в статистической термодинамике, верхняя граница равна ln(2):

0\leqslant {\rm {JSD}}(P\parallel Q)\leqslant \ln(2)

Дивергенция Йенсена — Шеннона ограничена величиной $\log _{2}(n)$ для более двух распределений вероятности, если используется логарифм по основанию 2^[8]

0\leqslant {\rm {JSD}}_{\pi _{1},\ldots ,\pi _{n}}(P_{1},P_{2},\ldots ,P_{n})\leqslant \log _{2}(n)

Связь со взаимной информацией

Дивергенция Йенсена — Шеннона является взаимной информацией между случайной переменной $X$ , ассоциированной со смесью распределений^[англ.] между $P$ и $Q$ и двоичной индикаторной переменной $Z$ , которая используется для переключения между $P$ и $Q$ для получения смеси. Пусть $X$ будет некоторой функцией на множестве событий, которая хорошо различает события, и выберем значение $X$ согласно $P$ , если $Z=0$ , и согласно $Q$ , если $Z=1$ , где $Z$ равновероятно. То есть мы выбираем $X$ согласно мере $M=(P+Q)/2$ , и его распределение является смесью распределений. Мы вычисляем

{\begin{aligned}I(X;Z)&=H(X)-H(X|Z)\\&=-\sum M\log M+{\frac {1}{2}}\left[\sum P\log P+\sum Q\log Q\right]\\&=-\sum {\frac {P}{2}}\log M-\sum {\frac {Q}{2}}\log M+{\frac {1}{2}}\left[\sum P\log P+\sum Q\log Q\right]\\&={\frac {1}{2}}\sum P\left(\log P-\log M\right)+{\frac {1}{2}}\sum Q\left(\log Q-\log M\right)\\&={\rm {JSD}}(P\parallel Q)\end{aligned}}

Из результатов выше следует, что дивергенция Йенсена — Шеннона ограничена 0 и 1, поскольку взаимная информация неотрицательна и ограничена величиной $H(Z)=1$ . Дивергенция Йенсена — Шеннона не всегда ограничена 0 и 1 — здесь верхняя граница 1 возникает из-за того, что мы рассматриваем конкретный случай двоичной переменной $Z$ .

Можно применить тот же принцип для совместного распределения и произведения этих двух крайних распределений (по аналогии с дивергенцией Кульбака — Лейблера и взаимной информацией) и измерить, насколько достоверно можно решить, что результат получен от совместного распределения или от произведения распределений при предположении, что имеются только эти две возможности^[9].

Квантовая дивергенция Йенсена — Шеннона

Обобщение распределений вероятности на матрицы плотности позволяет определить квантовую дивергенцию Йенсена — Шеннона (англ. quantum Jensen–Shannon divergence, QJSD)^[10]^[11]. Она определяется для множества матриц плотности $(\rho _{1},\ldots ,\rho _{n})$ и распределений вероятности $\pi =(\pi _{1},\ldots ,\pi _{n})$ как

{\rm {QJSD}}(\rho _{1},\ldots ,\rho _{n})=S\left(\sum _{i=1}^{n}\pi _{i}\rho _{i}\right)-\sum _{i=1}^{n}\pi _{i}S(\rho _{i})

где $S(\rho )$ является энтропией фон Неймана^[англ.] плотности $\rho$ . Эта величина вводится в теории квантовой информации, где называется информацией Холево — она даёт верхнюю границу для количества классической информации, закодированной квантовыми состояниями $(\rho _{1},\ldots ,\rho _{n})$ при априорных распределениях $\pi$ (см. статью «Теорема Холево»)^[12]. Квантовая Дивергенция Йенсена — Шеннона для $\pi =\left({\frac {1}{2}},{\frac {1}{2}}\right)$ и двух матриц плотности является ограниченной всюду заданной симметричной функцией и равна нулю, только если две матрицы плотности совпадают. Она равна квадрату метрики чистых состояний^[13] и недавно было показано, что это метрическое свойство выполняется и для смешанных состояний^[14]^[15]. Метрика Бюреса^[англ.] тесно связана с квантовой дивергенцией Йенсена — Шеннона и является квантовым аналогом информационной метрики Фишера.

Обобщение

Нильсен ввёл косую K-дивергенцию^[16]: $K_{\alpha }(p||q)=\mathrm {KL} (p||(1-\alpha )p+\alpha q)=\int p(x)\log {\frac {p(x)}{(1-\alpha )p(x)+\alpha q(x)}}\mathrm {d} x.$ Отсюда получаем однопараметрическое семейство дивергенций Йенсена — Шеннона, называемое $\alpha$ -дивергенциями Йенсена — Шеннона:

$\mathrm {JS} _{\alpha }(p,q)={\frac {1}{2}}\left(K_{\alpha }(p||q)+K_{\alpha }(q||p)\right)=\mathrm {JS} _{\alpha }(q,p),$

которое включает дивергенцию Йенсена — Шеннона (для $\alpha ={\frac {1}{2}}$ ) и половину дивергенции Джеффриса (для $\alpha =1$ ).

Приложения

Дивергенция Йенсена — Шеннона применяется в биоинформатике и сравнении геномов^[англ.]^[17]^[18], при сравнении поверхностей белков^[19], в общественных науках^[20], при количественных исследованиях в истории^[21], экспериментах с огнём^[22] и машинном обучении ^[23].

Примечания

↑ В русскоязычной литературе чаще встречается неверное название «Дивергенция Дженсена — Шеннона»
↑ Schütze, Manning, 1999, с. 304.
↑ Dagan, Lee, Pereira, 1997, с. 56–63.
↑ Endres, Schindelin, 2003, с. 1858–1860.
↑ Ôsterreicher, Vajda, 2003, с. 639–653.
↑ Fuglede, Topsoe, 2004, с. 30.
↑ Nielsen, Frank (2019). "On a generalization of the Jensen-Shannon divergence and the JS-symmetrization of distances relying on abstract means". arXiv:1904.04017 [cs.IT].
↑ ¹ ² Lin, 1991, с. 145–151.
↑ Schneidman, Bialek, Berry, 2003.
↑ Majtey, Lamberti, Prato, 2005, с. 052310.
↑ Briët, Harremoës, 2009, с. 052311.
↑ Холево, 1973, с. 3–11.
↑ Braunstein, Caves, 1994, с. 3439–3443.
↑ Virosztek, Dániel (2019). "The metric property of the quantum Jensen-Shannon divergence". arXiv:1910.10447.
↑ Sra, Suvrit (2019). "Metrics Induced by Quantum Jensen-Shannon-Renyí and Related Divergences". arXiv:1911.02643.
↑ Nielsen, Frank (2010). "A family of statistical symmetric divergences based on Jensen's inequality". arXiv:1009.4004 [cs.CV].
↑ Sims, Jun, Wu, Kim, 2009, с. 2677–82.
↑ Itzkovitz, Hodis, Segal, 2010, с. 1582–9.
↑ Ofran, Rost, 2003, с. 377–87.
↑ DeDeo, Hawkins, Klingenstein, Hitchcock, 2013, с. 2246–2276.
↑ Klingenstein, Hitchcock, DeDeo, 2014, с. 9419–9424.
↑ Mitroi-Symeonidis, Anghel, Minculete, 2020, с. 22.
↑ Goodfellow, Pouget-Abadie и др., 2014.

Литература

Hinrich Schütze, Christopher D. Manning. Foundations of Statistical Natural Language Processing. — Cambridge, Mass: MIT Press, 1999. — ISBN 978-0-262-13360-9.
Ido Dagan, Lillian Lee, Fernando Pereira. Similarity-Based Methods For Word Sense Disambiguation // Proceedings of the Thirty-Fifth Annual Meeting of the Association for Computational Linguistics and Eighth Conference of the European Chapter of the Association for Computational Linguistics. — 1997. — doi:10.3115/979617.979625. — Bibcode: 1997cmp.lg....8010D. — arXiv:cmp-lg/9708010.
D. M. Endres, J. E. Schindelin. A new metric for probability distributions // IEEE Trans. Inf. Theory. — 2003. — Т. 49, вып. 7. — С. 1858–1860. — doi:10.1109/TIT.2003.813506.
F. Ôsterreicher, I. Vajda. A new class of metric divergences on probability spaces and its statistical applications // Ann. Inst. Statist. Math.. — 2003. — Т. 55, вып. 3. — С. 639–653. — doi:10.1007/BF02517812.
Fuglede B., Topsoe F. Jensen-Shannon divergence and Hilbert space embedding // Proceedings of the International Symposium on Information Theory, 2004. — IEEE, 2004. — С. 30. — ISBN 978-0-7803-8280-0. — doi:10.1109/ISIT.2004.1365067.
Elad Schneidman, Bialek W., Berry M.J. 2nd. Synergy, Redundancy, and Independence in Population Codes // Journal of Neuroscience. — 2003. — Т. 23, вып. 37. — С. 11539–11553. — doi:10.1523/JNEUROSCI.23-37-11539.2003. — PMID 14684857.
Majtey A., Lamberti P., Prato D. Jensen-Shannon divergence as a measure of distinguishability between mixed quantum states // Physical Review A. — 2005. — Т. 72, вып. 5. — С. 052310. — doi:10.1103/PhysRevA.72.052310. — Bibcode: 2005PhRvA..72e2310M. — arXiv:quant-ph/0508138.
Jop Briët, Peter Harremoës. Properties of classical and quantum Jensen-Shannon divergence // Physical Review A. — 2009. — Т. 79, вып. 5. — С. 052311. — doi:10.1103/PhysRevA.79.052311. — Bibcode: 2009PhRvA..79e2311B. — arXiv:0806.4472.
Холево А.С. Границы количества информации, передаваемой по квантовому каналу связи // Проблемы передачи информации. — 1973. — Т. 9.
Samuel Braunstein, Carlton Caves. Statistical distance and the geometry of quantum states // Physical Review Letters. — 1994. — Т. 72, вып. 22. — С. 3439–3443. — doi:10.1103/PhysRevLett.72.3439. — Bibcode: 1994PhRvL..72.3439B. — PMID 10056200.
Flavia-Corina Mitroi-Symeonidis, Ion Anghel, Nicuşor Minculete. Parametric Jensen-Shannon statistical complexity and its applications on full-scale compartment fire data // Symmetry (Special Issue: Symmetry in Applied Mathematics). — 2020. — Вып. 12(1). — doi:10.3390/sym12010022.
Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, Yoshua Bengio. Generative Adversarial Networks // NIPS. — 2014.
J. Lin. Divergence measures based on the shannon entropy // IEEE Transactions on Information Theory. — 1991. — Т. 37, вып. 1. — С. 145–151. — doi:10.1109/18.61115.
Sims G.E., Jun S.R., Wu G.A., Kim S.H. Alignment-free genome comparison with feature frequency profiles (FFP) and optimal resolutions // Proceedings of the National Academy of Sciences of the United States of America. — 2009. — Т. 106, вып. 8. — С. 2677–82. — doi:10.1073/pnas.0813249106. — Bibcode: 2009PNAS..106.2677S. — PMID 19188606. — PMC 2634796.
Itzkovitz S., Hodis E., Segal E. Overlapping codes within protein-coding sequences // Genome Research. — 2010. — Т. 20, вып. 11. — С. 1582–9. — doi:10.1101/gr.105072.110. — PMID 20841429. — PMC 2963821.
Ofran Y., Rost B. Analysing six types of protein-protein interfaces // Journal of Molecular Biology. — 2003. — Т. 325, вып. 2. — С. 377–87. — doi:10.1016/s0022-2836(02)01223-8. — PMID 12488102.
Sara Klingenstein, Tim Hitchcock, Simon DeDeo. The civilizing process in London's Old Bailey // Proceedings of the National Academy of Sciences. — 2014. — Т. 111, вып. 26. — С. 9419–9424. — doi:10.1073/pnas.1405984111. — Bibcode: 2014PNAS..111.9419K. — PMID 24979792. — PMC 4084475.
Simon DeDeo, Robert X. D. Hawkins, Sara Klingenstein, Tim Hitchcock. Bootstrap Methods for the Empirical Study of Decision-Making and Information Flows in Social Systems // Entropy. — 2013. — Т. 15, вып. 6. — С. 2246–2276. — doi:10.3390/e15062246. — Bibcode: 2013Entrp..15.2246D. — arXiv:1302.0907.

Литература для дальнейшего чтения

Frank Nielsen (2010). "A family of statistical symmetric divergences based on Jensen's inequality". arXiv:1009.4004 [cs.CV].

Ссылки

[1] В русскоязычной литературе чаще встречается неверное название «Дивергенция Дженсена — Шеннона»

[_a49a131213737e36-2] Schütze, Manning, 1999, с. 304.

[_8bae28e12b343f4b-3] Dagan, Lee, Pereira, 1997, с. 56–63.

[_372d25b4a81285b0-4] Endres, Schindelin, 2003, с. 1858–1860.

[_d9eb523b08274058-5] Ôsterreicher, Vajda, 2003, с. 639–653.

[_8eaa0105920135ee-6] Fuglede, Topsoe, 2004, с. 30.

[N04017-7] Nielsen, Frank (2019). "On a generalization of the Jensen-Shannon divergence and the JS-symmetrization of distances relying on abstract means". arXiv:1904.04017 [cs.IT].

[_8abd8d347d57c62c-8] ¹ ² Lin, 1991, с. 145–151.

[_af8f004e15c29070-9] Schneidman, Bialek, Berry, 2003.

[_a56e2f115a3af3f1-10] Majtey, Lamberti, Prato, 2005, с. 052310.

[_f60a1a947a440342-11] Briët, Harremoës, 2009, с. 052311.

[_04dd1858341d0014-12] Холево, 1973, с. 3–11.

[_4378861b3a7c2eb1-13] Braunstein, Caves, 1994, с. 3439–3443.

[Virosztek-14] Virosztek, Dániel (2019). "The metric property of the quantum Jensen-Shannon divergence". arXiv:1910.10447.

[Sra-15] Sra, Suvrit (2019). "Metrics Induced by Quantum Jensen-Shannon-Renyí and Related Divergences". arXiv:1911.02643.

[N10447-16] Nielsen, Frank (2010). "A family of statistical symmetric divergences based on Jensen's inequality". arXiv:1009.4004 [cs.CV].

[_bd2648b645ad976f-17] Sims, Jun, Wu, Kim, 2009, с. 2677–82.

[_42af9caf824dcaa9-18] Itzkovitz, Hodis, Segal, 2010, с. 1582–9.

[_4bf1a41c27911dc9-19] Ofran, Rost, 2003, с. 377–87.

[_bb568386a1d5a24e-20] DeDeo, Hawkins, Klingenstein, Hitchcock, 2013, с. 2246–2276.

[_7dedcb824c860b7f-21] Klingenstein, Hitchcock, DeDeo, 2014, с. 9419–9424.

[_54494812381cabbd-22] Mitroi-Symeonidis, Anghel, Minculete, 2020, с. 22.

[_b5c452fb2b775c22-23] Goodfellow, Pouget-Abadie и др., 2014.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]