View source for Cross-entropy

{{Short description|Information-theoretic measure}}
{{Information theory}}
In [[information theory]], the '''cross-entropy''' between two [[probability distribution]]s <math>p</math> and <math>q</math>, over the same underlying set of events, measures the average number of [[bit]]s needed to identify an event drawn from the set when the coding scheme used for the set is optimized for an estimated probability distribution <math>q</math>, rather than the true distribution <math>p</math>.

== Definition ==
The cross-entropy of the distribution <math>q</math>  relative to a distribution <math>p</math> over a given set is defined as follows:

<math display="block">H(p, q) = -\operatorname{E}_p[\log q],</math>

where <math>E_p[\cdot]</math> is the [[expected value]] operator with respect to the distribution <math>p</math>.

The definition may be formulated using the [[Kullback–Leibler divergence]] <math>D_{\mathrm{KL}}(p \parallel q)</math>, divergence of <math>p</math> from <math>q</math> (also known as the ''relative entropy'' of <math>p</math> with respect to <math>q</math>).

<math display="block">H(p, q) = H(p) + D_{\mathrm{KL}}(p \parallel q),</math>

where <math>H(p)</math> is the [[information entropy|entropy]] of <math>p</math>.

For [[discrete random variable|discrete]] probability distributions <math>p</math> and <math>q</math> with the same [[Support (mathematics)|support]] <math>\mathcal{X}</math>, this means

{{Equation box 1
|indent = :
|title =
|equation = <math>H(p,q) = -\sum_{x\in\mathcal{X}} p(x)\, \log q(x).</math>
|ref = Eq.1
|cellpadding= 6
|border
|border colour = #0073CF
|background colour=var(--background-color-success-subtle,#d5fdf4)}}

The situation for [[continuous random variable|continuous]] distributions is analogous. We have to assume that <math>p</math> and <math>q</math> are [[absolutely continuous]] with respect to some reference [[measure (mathematics)|measure]] <math>r</math> (usually <math>r</math> is a [[Lebesgue measure]] on a [[Borel set|Borel]] [[Sigma-algebra|σ-algebra]]). Let <math>P</math> and <math>Q</math> be probability density functions of <math>p</math> and <math>q</math> with respect to <math>r</math>. Then

<math display="block">-\int_\mathcal{X} P(x)\, \log Q(x)\, \mathrm{d}x = \operatorname{E}_p[-\log Q],</math>

and therefore

{{Equation box 1
|indent = :
|title=
|equation = <math>H(p,q) = -\int_\mathcal{X} P(x)\, \log Q(x)\, \mathrm{d}x.</math>
|ref = Eq.2
|cellpadding= 6
|border
|border colour = #0073CF
|background colour=var(--background-color-success-subtle,#d5fdf4)}}

NB: The notation <math>H(p,q)</math> is also used for a different concept, the [[joint entropy]] of <math>p</math> and <math>q</math>.

== Motivation ==
In [[information theory]], the [[Kraft's inequality|Kraft&ndash;McMillan theorem]] establishes that any directly decodable coding scheme for coding a message to identify one value <math>x_i</math> out of a set of possibilities <math>\{x_1,\ldots,x_n\}</math> can be seen as representing an implicit probability distribution <math>q(x_i) = \left(\frac{1}{2}\right)^{\ell_i}</math> over <math>\{x_1, \ldots, x_n\}</math>, where <math>\ell_i</math> is the length of the code for <math>x_i</math> in bits. Therefore, cross-entropy can be interpreted as the expected message-length per datum when a wrong distribution <math>q</math> is assumed while the data actually follows a distribution <math>p</math>. That is why the expectation is taken over the true probability distribution <math>p</math> and not <math>q.</math> Indeed the expected message-length under the true distribution <math>p</math> is

<math display="block"> \operatorname{E}_p[\ell] = - \operatorname{E}_p\left[\frac{\ln{q(x)}}{\ln(2)}\right]</math>
<math display="block"> = - \operatorname{E}_p\left[\log_2 {q(x)}\right] = - \sum_{x_i} p(x_i)\, \log_2 q(x_i) </math> 
<math display="block"> = -\sum_x p(x)\, \log_2 q(x) = H(p, q). </math>

== Estimation ==
There are many situations where cross-entropy needs to be measured but the distribution of <math>p</math> is unknown. An example is [[language model]]ing, where a model is created based on a training set <math>T</math>, and then its cross-entropy is measured on a test set to assess how accurate the model is in predicting the test data. In this example, <math>p</math> is the true distribution of words in any corpus, and <math>q</math> is the distribution of words as predicted by the model. Since the true distribution is unknown, cross-entropy cannot be directly calculated. In these cases, an estimate of cross-entropy is calculated using the following formula:

<math display="block">H(T,q) = -\sum_{i=1}^N \frac{1}{N} \log_2 q(x_i)</math>

where <math>N</math> is the size of the test set, and <math>q(x)</math> is the probability of event <math>x</math> estimated from the training set. In other words, <math>q(x_i)</math> is the probability estimate of the model that the i-th word of the text is <math>x_i</math>. The sum is averaged over the <math>N</math> words of the test. This is a [[Monte Carlo method|Monte Carlo estimate]] of the true cross-entropy, where the test set is treated as samples from <math>p(x)</math>.{{Citation needed|reason=Needs to be proved|date=May 2019}}<!-- This entire section about how perplexity of a language model on the test set is calculated is wrong. For language modeling, p is the one hot vector p(xi=wi | x<i), q is the distribution output by LM. Since p is a one-hot vector, only the term corresponding to the correct word is preserved, i.e. why only q(xi). The wording in this section is very misleading. -->

== Relation to maximum likelihood ==
The cross entropy arises in classification problems when introducing a logarithm in the guise of the [[Likelihood function#Log-likelihood|log-likelihood]] function.

The section is concerned with the subject of estimation of the probability of different possible discrete outcomes. To this end, denote a parametrized family of distributions by <math>q_{\theta}</math>, with <math>\theta</math> subject to the optimization effort. Consider a given finite sequence of <math>N</math> values <math>x_i</math> from a training set, obtained from [[conditionally independent]] sampling. The likelihood assigned to any considered parameter <math>\theta</math> of the model is then given by the product over all probabilities <math>q_{\theta}(X=x_i)</math>.
Repeated occurrences are possible, leading to equal factors in the product. If the count of occurrences of the value equal to <math>x_i</math> (for some index <math>i</math>) is denoted by <math>\#x_i</math>, then the frequency of that value equals <math>\#x_i/N</math>. Denote the latter by <math>p(X=x_i)</math>, as it may be understood as empirical approximation to the probability distribution underlying the scenario. Further denote by <math>PP := {\mathrm e}^{ H(p, q_\theta) }</math> the [[Perplexity#Perplexity of a probability model|perplexity]], which can be seen to equal <math display="inline">\prod_{x_i} q_{\theta}(X=x_i)^{-p(X=x_i)}</math> by the [[List of logarithmic identities|calculation rules for the logarithm]], and where the product is over the values without double counting. So
<math display="block">\mathcal{L}(\theta; {\mathbf x}) = \prod_{i} q_{\theta}(X=x_i) = \prod_{x_i} q_{\theta}(X=x_i)^{\#x_i} = PP^{-N} = {\mathrm e}^{ - N\cdot H(p, q_\theta) }</math>
or
<math display="block">\log \mathcal{L}(\theta; {\mathbf x}) = -N\cdot H(p, q_\theta).</math>
Since the logarithm is a [[Monotonic function|monotonically increasing function]], it does not affect extremization. So observe that the [[Maximum likelihood estimation#Relation to minimizing Kullback–Leibler divergence and cross entropy|likelihood maximization]] amounts to minimization of the cross-entropy.

== Cross-entropy minimization ==
{{Main|Cross-entropy method}}

Cross-entropy minimization is frequently used in optimization and rare-event probability estimation. When comparing a distribution <math>q</math> against a fixed reference distribution <math>p</math>, cross-entropy and [[Kullback–Leibler divergence|KL divergence]] are identical up to an additive constant (since <math>p</math> is fixed): According to the [[Gibbs' inequality]],  both take on their minimal values when <math>p = q</math>, which is <math>0</math> for KL divergence, and <math>\mathrm{H}(p)</math> for cross-entropy. In the engineering literature, the principle of minimizing KL divergence (Kullback's "[[Kullback–Leibler divergence#Principle of minimum discrimination information|Principle of Minimum Discrimination Information]]") is often called the '''Principle of Minimum Cross-Entropy''' (MCE), or '''Minxent'''.

However, as discussed in the article ''[[Kullback–Leibler divergence]]'', sometimes the distribution <math>q</math> is the fixed prior reference distribution, and the distribution <math>p</math> is optimized to be as close to <math>q</math> as possible, subject to some constraint. In this case the two minimizations are ''not'' equivalent. This has led to some ambiguity in the literature, with some authors attempting to resolve the inconsistency by restating cross-entropy to be <math>D_{\mathrm{KL}}(p \parallel q)</math>, rather than <math>H(p, q)</math>. In fact, cross-entropy is another name for [[relative entropy]]; see Cover and Thomas<ref>Thomas M. Cover, Joy A. Thomas, Elements of Information Theory, 2nd Edition, Wiley, p. 80</ref>  and Good.<ref>I. J. Good, Maximum entropy for hypothesis formulation, especially for multidimensional contingency tables, Ann. of Math. Statistics, 1963</ref> On the other hand, <math>H(p, q)</math> does not agree with the literature and can be misleading.

== Cross-entropy loss function and logistic regression ==
Cross-entropy can be used to define a loss function in [[machine learning]] and [[optimization]]. Mao, Mohri, and Zhong (2023) give an extensive analysis of the properties of the family of cross-entropy loss functions in machine learning, including theoretical learning guarantees and extensions to [[Adversarial machine learning|adversarial learning]].<ref>Anqi Mao, Mehryar Mohri, Yutao Zhong. Cross-entropy loss functions: Theoretical analysis and applications. ICML 2023. https://arxiv.org/pdf/2304.07288.pdf</ref> The true probability <math>p_i</math> is the true label, and the given distribution <math>q_i</math> is the predicted value of the current model. This is also known as the '''log loss''' (or '''logarithmic loss'''<ref>''The Mathematics of Information Coding, Extraction and Distribution'', by George Cybenko, Dianne P. O'Leary, Jorma Rissanen, 1999, [https://books.google.com/books?id=jDrp4QEGioMC&dq=%22logarithmic+loss%22+%22log+loss%22&pg=PA82 p. 82]</ref> or '''[[logistic loss]]''');<ref>''Probability for Machine Learning: Discover How To Harness Uncertainty With Python'', Jason Brownlee, 2019, p. 220: "Logistic loss refers to the loss function commonly used to optimize a logistic regression model. It may also be referred to as logarithmic loss (which is confusing) or simply log loss."</ref> the terms "log loss" and "cross-entropy loss" are used interchangeably.<ref>[https://scikit-learn.org/stable/modules/generated/sklearn.metrics.log_loss.html sklearn.metrics.log_loss]</ref>

More specifically, consider a [[binary regression]] model which can be used to classify observations into two possible classes (often simply labelled <math>0</math> and <math>1</math>). The output of the model for a given observation, given a vector of input features <math> x </math>, can be interpreted as a probability, which serves as the basis for classifying the observation. In [[logistic regression]], the probability is modeled using the [[logistic function]] <math>g(z) = 1/(1+e^{-z})</math> where <math> z </math> is some function of the input vector <math>x</math>, commonly just a linear function. The probability of the output <math>y=1</math> is given by
<math display="block">q_{y=1} = \hat{y} \equiv g(\mathbf{w}\cdot\mathbf{x}) = \frac 1 {1+e^{-\mathbf{w}\cdot\mathbf{x}}},</math>
where the vector of weights <math>\mathbf{w}</math> is optimized through some appropriate algorithm such as [[gradient descent]]. Similarly, the complementary probability of finding the output <math>y=0</math> is simply given by
<math display="block">q_{y=0} = 1-\hat{y}.</math>

Having set up our notation, <math>p\in\{y,1-y\}</math> and <math>q\in\{\hat{y},1-\hat{y}\}</math>, we can use cross-entropy to get a measure of dissimilarity between <math>p</math> and <math>q</math>:
<math display="block">H(p,q)\ =\ -\sum_i p_i\log q_i\ =\ -y\log\hat{y} - (1-y)\log(1-\hat{y}).</math>
:[[File:Comparison of Loss functions for binary classification.png|thumb|948x948px|Plot shows different loss functions that can be used to train a binary classifier.  Only the case where the target output is 1 is shown. It is observed that the loss is zero when the target is equal to the output and increases as the output becomes increasingly incorrect.]]

Logistic regression typically optimizes the log loss for all the observations on which it is trained, which is the same as optimizing the average cross-entropy in the sample. Other loss functions that penalize errors differently can be also used for training, resulting in models with different final test accuracy.<ref>{{Cite arXiv |last1=Noel |first1=Mathew |last2=Banerjee |first2=Arindam |last3=D |first3=Geraldine Bessie Amali |last4=Muthiah-Nakarajan |first4=Venkataraman |date=March 17, 2023 |title=Alternate loss functions for classification and robust regression can improve the accuracy of artificial neural networks |class=cs.NE |eprint=2303.09935 }}</ref> For example, suppose we have <math>N</math> samples with each sample indexed by <math>n=1,\dots,N</math>. The ''average'' of the loss function is then given by:

<math display="block">
    J(\mathbf{w})\ =\ \frac{1}{N}\sum_{n=1}^N H(p_n,q_n)\ =\ -\frac1N\sum_{n=1}^N\ \bigg[y_n  \log \hat y_n + (1 - y_n)  \log (1 - \hat y_n)\bigg]\,,
</math>

where <math>\hat{y}_n\equiv g(\mathbf{w}\cdot\mathbf{x}_n) = 1/(1+e^{-\mathbf{w}\cdot\mathbf{x}_n}) </math>, with <math>g(z)</math> the logistic function as before.

{{duplication span|text=The logistic loss is sometimes called cross-entropy loss. It is also known as log loss.|date=November 2023|reason=duplication of end of first paragraph in this section}} (In this case, the binary label is often denoted by {−1,+1}.<ref>{{cite book |last1=Murphy |first1=Kevin|date=2012 |title=Machine Learning: A Probabilistic Perspective |publisher=MIT |isbn=978-0262018029 }}</ref>)

'''Remark:''' The gradient of the cross-entropy loss for logistic regression is the same as the gradient of the squared-error loss for [[linear regression]]. That is, define

<math display="block">X^\mathsf{T} = \begin{pmatrix}
1        & x_{11} &  \dots & x_{1p} \\ 
1        & x_{21} & \cdots & x_{2p} \\ 
\vdots   & \vdots &        & \vdots \\
1        & x_{n1} & \cdots & x_{np} \\ 
\end{pmatrix}\in \mathbb{R}^{n\times(p+1)},</math>
<math display="block">\hat{y_i} = \hat{f}(x_{i1},\dots,x_{ip}) = \frac{1}{1+\exp(-\beta_0-\beta_1x_{i1}-\dots-\beta_px_{ip})},</math>
<math display="block">L(\boldsymbol{\beta}) = -\sum_{i=1}^N \left[y_i\log \hat{y}_i+(1-y_i)\log(1-\hat{y}_i)\right].</math>

Then we have the result

<math display="block">\frac{\partial}{\partial\boldsymbol{\beta}}L(\boldsymbol{\beta})=X^T(\hat{Y}-Y).</math>

The proof is as follows. For any <math>\hat{y}_i</math>, we have

<math display="block">\frac{\partial}{\partial\beta_0}\ln\frac{1}{1+e^{-\beta_0+k_0}} = \frac{e^{-\beta_0+k_0}}{1+e^{-\beta_0+k_0}},</math>
<math display="block">\frac{\partial}{\partial \beta_0}\ln \left(1-\frac{1}{1+e^{-\beta_0+k_0}}\right)=\frac{-1}{1+e^{-\beta_0+k_0}},</math>
<math display="block">\begin{align}
\frac{\partial}{\partial\beta_0}L(\boldsymbol{\beta}) &= -\sum_{i=1}^{N}\left[\frac{y_i \cdot e^{-\beta_0+k_0}}{1+e^{-\beta_0+k_0}}-(1-y_i)\frac{1}{1+e^{-\beta_0+k_0}}\right] \\
    &= - \sum_{i=1}^{N} \left[y_i-\hat{y}_i\right]
     = \sum_{i=1}^{N}(\hat{y}_i-y_i),
\end{align}</math>
<math display="block">\frac{\partial}{\partial \beta_1}\ln \frac{1}{1+e^{-\beta_1x_{i1}+k_1}} = \frac{x_{i1}e^{k_1}}{e^{\beta_1x_{i1}}+e^{k_1}},</math>
<math display="block">\frac{\partial}{\partial \beta_1}\ln\left[1-\frac{1}{1+e^{-\beta_1x_{i1}+k_1}}\right] = \frac{-x_{i1}e^{\beta_1x_{i1}}}{e^{\beta_1x_{i1}}+e^{k_1}},</math>
<math display="block">\frac{\partial}{\partial\beta_1}L(\boldsymbol{\beta}) = -\sum_{i=1}^N x_{i1}(y_i-\hat{y}_i) = \sum_{i=1}^N x_{i1}(\hat{y}_i-y_i).</math>

In a similar way, we eventually obtain the desired result.

==Amended cross-entropy==
It may be beneficial to train an ensemble of models that have diversity, such that when they are combined, their predictive accuracy is augmented.<ref>{{cite conference
 | last1 = Shoham | first1 = Ron
 | last2 = Permuter | first2 = Haim H.
 | editor1-last = Dolev | editor1-first = Shlomi
 | editor2-last = Hendler | editor2-first = Danny
 | editor3-last = Lodha | editor3-first = Sachin
 | editor4-last = Yung | editor4-first = Moti
 | contribution = Amended Cross-Entropy Cost: An Approach for Encouraging Diversity in Classification Ensemble (Brief Announcement)
 | doi = 10.1007/978-3-030-20951-3_18
 | pages = 202–207
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Cyber Security Cryptography and Machine Learning – Third International Symposium, CSCML 2019, Beer-Sheva, Israel, June 27–28, 2019, Proceedings
 | volume = 11527
 | year = 2019| isbn = 978-3-030-20950-6
 }}</ref><ref>{{cite arXiv |last1=Shoham |first1=Ron |last2=Permuter |first2=Haim |title=Amended Cross Entropy Cost: Framework For Explicit Diversity Encouragement |date=2020 |class=cs.LG |eprint=2007.08140 }}</ref>
Assuming a simple ensemble of <math> K </math> classifiers is assembled via averaging the outputs, then the amended cross-entropy is given by
<math display="block">
    e^k = H(p,q^k)-\frac{\lambda}{K}\sum_{j\neq k}H(q^j,q^k)
</math>
where <math> e^k </math> is the cost function of the <math> k^{th} </math> classifier, <math> q^k </math> is the output probability of the <math> k^{ th} </math> classifier, <math> p </math> is the true probability to be estimated, and <math> \lambda </math> is a parameter between 0 and 1 that defines the 'diversity' that we would like to establish among the ensemble. When <math> \lambda=0 </math> we want each classifier to do its best regardless of the ensemble and when <math> \lambda=1 </math> we would like the classifier to be as diverse as possible.

== See also ==
* [[Cross-entropy method]]
* [[Logistic regression]]
* [[Conditional entropy]]
* [[Kullback–Leibler distance]]
* [[Maximum-likelihood estimation]]
* [[Mutual information]]
* [[Perplexity]]

== References ==
{{reflist}}

== Further reading ==
* de Boer, Kroese, D.P., Mannor, S. and Rubinstein, R.Y. (2005). [https://link.springer.com/article/10.1007/s10479-005-5724-z A tutorial on the cross-entropy method]. ''Annals of Operations Research'' 134 (1), 19–67.

{{DEFAULTSORT:Cross Entropy}}
[[Category:Entropy and information]]
[[Category:Loss functions]]