{{Short description|Statistical distance measure}} In probability theory and statistics, the '''Jensen–Shannon divergence''', named after Johan Jensen and Claude Shannon, is a method of measuring the similarity between two probability distributions. It is also known as '''information radius''' ('''IRad''')<ref>{{cite journal | author1=Frank Nielsen | title=On a variational definition for the Jensen-Shannon symmetrization of distances based on the information radius | journal = Entropy | publisher= MDPI | year=2021 | doi=10.3390/e21050485 | volume=23 | number =4 | page=464| pmid=33267199 | pmc=7514974 | bibcode=2019Entrp..21..485N | doi-access=free }}</ref><ref>{{cite book |author=Hinrich Schütze |author2=Christopher D. Manning|title=Foundations of Statistical Natural Language Processing |publisher=MIT Press |location=Cambridge, Mass |year=1999 |isbn=978-0-262-13360-9 |url=https://nlp.stanford.edu/fsnlp/ |page=304}}</ref> or '''total divergence to the average'''.<ref>{{cite conference | last1 = Dagan | first1 = Ido | last2 = Lee | first2 = Lillian |author2-link = Lillian Lee (computer scientist) | last3 = Pereira | first3 = Fernando C. N. | editor1-last = Cohen | editor1-first = Philip R. | editor2-last = Wahlster | editor2-first = Wolfgang | arxiv = cmp-lg/9708010 | contribution = Similarity-based methods for word sense disambiguation | contribution-url = https://aclanthology.org/P97-1008/ | doi = 10.3115/976909.979625 | pages = 56–63 | publisher = Morgan Kaufmann Publishers / ACL | title = 35th Annual Meeting of the Association for Computational Linguistics and 8th Conference of the European Chapter of the Association for Computational Linguistics, Proceedings of the Conference, 7–12 July 1997, Universidad Nacional de Educación a Distancia (UNED), Madrid, Spain | year = 1997}}</ref> It is based on the Kullback–Leibler divergence, with some notable (and useful) differences, including that it is symmetric and it always has a finite value. The square root of the Jensen–Shannon divergence is a metric often referred to as Jensen–Shannon distance. The similarity between the distributions is greater when the Jensen-Shannon distance is closer to zero.<ref>{{cite journal|title=A new metric for probability distributions|journal=IEEE Trans. Inf. Theory|year=2003|first=D. M.|last=Endres|author2=J. E. Schindelin|volume=49|issue=7|pages=1858–1860|url=https://research-repository.st-andrews.ac.uk/bitstream/10023/1591/1/Endres2003-IEEETransInfTheory49-NewMetric.pdf|doi=10.1109/TIT.2003.813506|bibcode=2003ITIT...49.1858E |hdl=10023/1591|s2cid=14437777|hdl-access=free}}</ref><ref>{{cite journal|title=A new class of metric divergences on probability spaces and its statistical applications|journal=Ann. Inst. Statist. Math.|year=2003|first=F.|last=Ôsterreicher|author2=I. Vajda|volume=55|issue=3|pages=639–653|doi=10.1007/BF02517812|s2cid=13085920}}</ref><ref>{{cite book |doi=10.1109/ISIT.2004.1365067 |isbn=978-0-7803-8280-0 |chapter=Jensen-Shannon divergence and Hilbert space embedding |title=Proceedings of the International Symposium on Information Theory, 2004 |page=30 |year=2004 |last1=Fuglede |first1=B. |last2=Topsoe |first2=F. |publisher=IEEE |s2cid=7891037 |chapter-url=https://www.math.ku.dk/~topsoe/ISIT2004JSD.pdf }}</ref>
==Definition== Consider the set <math>M_+^1(A)</math> of probability distributions where <math>A</math> is a set provided with some σ-algebra of measurable subsets. In particular we can take <math>A</math> to be a finite or countable set with all subsets being measurable.
The Jensen–Shannon divergence (JSD) is a symmetrized and smoothed version of the Kullback–Leibler divergence <math>D(P \parallel Q)</math>. It is defined by
:<math>{\rm JSD}(P \parallel Q)= \frac{1}{2}D(P \parallel M)+\frac{1}{2}D(Q \parallel M),</math>
where <math>M=\frac{1}{2}(P+Q)</math> is a mixture distribution of <math>P</math> and <math>Q</math>.
The geometric Jensen–Shannon divergence<ref>{{cite journal | author1=Frank Nielsen | title=On the Jensen-Shannon symmetrization of distances relying on abstract means | journal = Entropy | publisher= MDPI | year=2019 | doi=10.3390/e21050485 | volume=21 | number =5 | page=485| pmid=33267199 | pmc=7514974 | arxiv=1904.04017 | bibcode=2019Entrp..21..485N | doi-access=free }}</ref> (or G-Jensen–Shannon divergence) yields a closed-form formula for divergence between two Gaussian distributions by taking the geometric mean.
A more general definition, allowing for the comparison of more than two probability distributions, is:
:<math> \begin{align} {\rm JSD}_{\pi_1, \ldots, \pi_n}(P_1, P_2, \ldots, P_n) &= \sum_i \pi_i D( P_i \parallel M ) \\ &= H\left(M\right) - \sum_{i=1}^n \pi_i H(P_i) \end{align} </math>
where
<math>\begin{align} M &:= \sum_{i=1}^n \pi_i P_i \end{align}</math>
and <math>\pi_1, \ldots, \pi_n</math> are weights that are selected for the probability distributions <math>P_1, P_2, \ldots, P_n</math>, and <math>H(P)</math> is the Shannon entropy for distribution <math>P</math>. For the two-distribution case described above,
<math>P_1=P, P_2=Q, \pi_1 = \pi_2 = \frac{1}{2}.\ </math>
Hence, for those distributions <math>P, Q</math>
<math>JSD = H(M) - \frac{1}{2}\bigg(H(P) + H(Q)\bigg)</math>
==Bounds== The Jensen–Shannon divergence is bounded by 1 for two discrete probability distributions, given that one uses the base 2 logarithm:<ref name=Lin/>
:<math>0 \leq {\rm JSD}( P \parallel Q ) \leq 1</math>.
With this normalization, it is a lower bound on the total variation distance between P and Q:
:<math> {\rm JSD}(P\parallel Q) \le \frac12\|P-Q\|_1=\frac12\sum_{\omega\in\Omega}|P(\omega)-Q(\omega)|</math>.
With base-e logarithm, which is commonly used in statistical thermodynamics, the upper bound is <math>\ln(2)</math>. In general, the bound in base b is <math>\log_{b}(2)</math>:
:<math>0 \leq {\rm JSD}( P \parallel Q ) \leq \log_b(2)</math>.
A more general bound, the Jensen–Shannon divergence is bounded by <math>\log_{b}(n)</math> for more than two probability distributions:<ref name="Lin" /> :<math>0 \leq {\rm JSD}_{\pi_1, \ldots, \pi_n}(P_1, P_2, \ldots, P_n) \leq \log_{b}(n)</math>.
== Relation to mutual information == The Jensen–Shannon divergence is the mutual information between a random variable <math>X</math> associated to a mixture distribution between <math>P</math> and <math>Q</math> and the binary indicator variable <math>Z</math> that is used to switch between <math>P</math> and <math>Q</math> to produce the mixture. Let <math>X</math> be some abstract function on the underlying set of events that discriminates well between events, and choose the value of <math>X</math> according to <math>P</math> if <math>Z = 0</math> and according to <math>Q</math> if <math>Z = 1</math>, where <math>Z</math> is equiprobable. That is, we are choosing <math>X</math> according to the probability measure <math>M=(P+Q)/2</math>, and its distribution is the mixture distribution. We compute :<math>\begin{align} 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{align} </math> It follows from the above result that the Jensen–Shannon divergence is bounded by 0 and 1 because mutual information is non-negative and bounded by <math>H(Z) = 1</math> in base 2 logarithm.
One can apply the same principle to a joint distribution and the product of its two marginal distribution (in analogy to Kullback–Leibler divergence and mutual information) and to measure how reliably one can decide if a given response comes from the joint distribution or the product distribution—subject to the assumption that these are the only two possibilities.<ref>{{cite journal|title=Synergy, Redundancy, and Independence in Population Codes|journal=Journal of Neuroscience|year=2003|first1=Elad|last1=Schneidman|pages=11539–11553|volume=23|issue=37|pmid=14684857|last2=Bialek|first2=W|last3=Berry|first3=M.J. II|doi=10.1523/JNEUROSCI.23-37-11539.2003|pmc=6740962|doi-access=free}}</ref>
==Quantum Jensen–Shannon divergence== The generalization of probability distributions on density matrices allows to define quantum Jensen–Shannon divergence (QJSD).<ref>{{cite journal|doi=10.1103/PhysRevA.72.052310|title=Jensen-Shannon divergence as a measure of distinguishability between mixed quantum states|year=2005|last1=Majtey|first1=A.|last2=Lamberti|first2=P.|last3=Prato|first3=D.|journal=Physical Review A|volume=72|issue=5|article-number=052310|arxiv=quant-ph/0508138|bibcode=2005PhRvA..72e2310M|s2cid=32062112}}</ref><ref name="briet">{{Cite journal|doi=10.1103/PhysRevA.79.052311|title=Properties of classical and quantum Jensen-Shannon divergence|year=2009|last1=Briët|first1=Jop|last2=Harremoës|first2=Peter|journal=Physical Review A|volume=79|issue=5|article-number=052311|arxiv=0806.4472|bibcode=2009PhRvA..79e2311B}}</ref> It is defined for a set of density matrices <math>(\rho_1,\ldots,\rho_n)</math> and a probability distribution <math>\pi=(\pi_1,\ldots,\pi_n)</math> as
:<math>{\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)</math>
where <math>S(\rho)</math> is the von Neumann entropy of <math>\rho</math>. This quantity was introduced in quantum information theory, where it is called the Holevo information: it gives the upper bound for amount of classical information encoded by the quantum states <math>(\rho_1,\ldots,\rho_n)</math> under the prior distribution <math>\pi</math> (see Holevo's theorem).<ref>{{citation|first=A. S.|last=Holevo|author-link=Alexander Holevo|title=Bounds for the quantity of information transmitted by a quantum communication channel|journal=Problemy Peredachi Informatsii|volume=9|pages=3–11|year=1973|language=ru}}. English translation: ''Probl. Inf. Transm''., '''9''': 177–183 (1975) {{mr|456936}}</ref> Quantum Jensen–Shannon divergence for <math>\pi=\left(\frac{1}{2},\frac{1}{2}\right)</math> and two density matrices is a symmetric function, everywhere defined, bounded and equal to zero only if two density matrices are the same. It is a square of a metric for pure states,<ref>{{cite journal|doi=10.1103/PhysRevLett.72.3439|title=Statistical distance and the geometry of quantum states|year=1994|last1=Braunstein|first1=Samuel|last2=Caves|first2=Carlton|journal=Physical Review Letters|volume=72|issue=22|pages=3439–3443|pmid=10056200|bibcode=1994PhRvL..72.3439B}}</ref> and it was recently shown that this metric property holds for mixed states as well.<ref>{{cite journal|title=The metric property of the quantum Jensen-Shannon divergence|year=2021|first=Dániel|last=Virosztek|journal=Advances in Mathematics|volume=380|article-number=107595|doi=10.1016/j.aim.2021.107595|arxiv=1910.10447|s2cid=204837864}}</ref><ref>{{cite arXiv|title=Metrics Induced by Quantum Jensen-Shannon-Renyí and Related Divergences|year=2019|first=Suvrit|last=Sra|class=cs.IT|eprint=1911.02643}}</ref> The Bures metric is closely related to the quantum JS divergence; it is the quantum analog of the Fisher information metric.
==Jensen–Shannon centroid==
The centroid C* of a finite set of probability distributions can be defined as the minimizer of the average sum of the Jensen-Shannon divergences between a probability distribution and the prescribed set of distributions: <math display="block"> C^*=\arg\min_{Q} \sum_{i=1}^n {\rm JSD}(P_i \parallel Q) </math> An efficient algorithm<ref>{{cite journal |author1=Frank Nielsen |year=2021 |title=On a generalization of the Jensen-Shannon divergence and the Jensen--Shannon centroid |journal=Entropy |publisher=MDPI |volume=22 |page=221 |doi=10.3390/e22020221 |pmc=7516653 |pmid=33285995 |doi-access=free |number=2}}</ref> (CCCP) based on difference of convex functions is reported to calculate the Jensen-Shannon centroid of a set of discrete distributions (histograms).
==Applications== The Jensen–Shannon divergence has been applied in bioinformatics and genome comparison,{{r|Sims}}{{r|It}} in protein surface comparison,{{r|Ofran}} in the social sciences,{{r|DeDeo}} in the quantitative study of history,{{r|Klingenstein}} in fire experiments,<ref>{{cite journal |author=Flavia-Corina Mitroi-Symeonidis |author2=Ion Anghel |author3=Nicuşor Minculete |title=Parametric Jensen-Shannon statistical complexity and its applications on full-scale compartment fire data |journal=Symmetry |date=2020 |volume=12 |issue=1 |page=22 |doi=10.3390/sym12010022|doi-access=free }}</ref> and in machine learning.<ref>{{cite conference |first1=Ian J. |last1=Goodfellow |first2=Jean |last2=Pouget-Abadie |first3=Mehdi |last3=Mirza |first4=Bing |last4=Xu |first5=David |last5=Warde-Farley |first6=Sherjil |last6=Ozair |first7=Aaron |last7=Courville |first8=Yoshua |last8=Bengio |author-link8=Yoshua Bengio |title=Generative Adversarial Networks |conference=NIPS |year=2014 |arxiv=1406.2661|bibcode=2014arXiv1406.2661G }}</ref>
== Notes == {{Reflist|refs=
<ref name=Lin>{{cite journal |first=J. |last=Lin |url=https://www.cise.ufl.edu/~anand/sp06/jensen-shannon.pdf |title=Divergence measures based on the shannon entropy |journal=IEEE Transactions on Information Theory |volume=37 |issue=1 |pages=145–151 |year=1991 |doi=10.1109/18.61115|citeseerx=10.1.1.127.9167 |s2cid=12121632 }}</ref>
<ref name=Sims>{{Cite journal|pmid=19188606|year=2009|last1=Sims|first1=GE|last2=Jun|first2=SR|last3=Wu|first3=GA|last4=Kim|first4=SH|title=Alignment-free genome comparison with feature frequency profiles (FFP) and optimal resolutions|volume=106|issue=8|pages=2677–82|doi=10.1073/pnas.0813249106|pmc=2634796|journal=Proceedings of the National Academy of Sciences of the United States of America |bibcode=2009PNAS..106.2677S|doi-access=free}}</ref>
<ref name=It>{{Cite journal|pmid=20841429|year=2010|last1=Itzkovitz|first1=S|last2=Hodis|first2=E|last3=Segal|first3=E|title=Overlapping codes within protein-coding sequences|volume=20|issue=11|pages=1582–9|doi=10.1101/gr.105072.110|pmc=2963821|journal=Genome Research}}</ref>
<ref name=Ofran>{{Cite journal|pmid=12488102|year=2003|last1=Ofran|first1=Y|last2=Rost|first2=B|title=Analysing six types of protein-protein interfaces|volume=325|issue=2|pages=377–87|journal=Journal of Molecular Biology|doi=10.1016/s0022-2836(02)01223-8|citeseerx=10.1.1.6.9207}}</ref>
<ref name= Klingenstein >{{cite journal| last1=Klingenstein|first1=Sara|last2=Hitchcock|first2=Tim|last3=DeDeo|first3=Simon|title=The civilizing process in London's Old Bailey|journal=Proceedings of the National Academy of Sciences of the United States of America|volume=111|issue=26|year=2014|doi=10.1073/pnas.1405984111|pmid=24979792|pmc=4084475|pages=9419–9424|bibcode=2014PNAS..111.9419K|doi-access=free}}</ref>
<ref name=DeDeo>{{cite journal| last1=DeDeo|first1=Simon|last2=Hawkins|first2=Robert X. D.|last3=Klingenstein|first3=Sara|last4=Hitchcock|first4=Tim|title=Bootstrap Methods for the Empirical Study of Decision-Making and Information Flows in Social Systems|journal=Entropy|volume=15|issue=6|year=2013|pages=2246–2276|doi=10.3390/e15062246|arxiv=1302.0907|bibcode=2013Entrp..15.2246D|doi-access=free}}</ref>
}}
==External links== * [https://github.com/evansenter/diverge Ruby gem for calculating JS divergence] *[https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.jensenshannon.html#scipy.spatial.distance.jensenshannon Python function for calculating JS distance], (SciPy) * [https://sites.santafe.edu/~simon/page7/page7.html THOTH: a python package for the efficient estimation of information-theoretic quantities from empirical data] * [https://cran.r-project.org/web/packages/statcomp/ statcomp R library for calculating complexity measures including Jensen-Shannon Divergence]
{{DEFAULTSORT:Jensen-Shannon Divergence}} Category:Statistical distance