Cross-entropy

The cross-entropy of the distribution q relative to a distribution p over a given set is defined as follows: H(p, q) = -\operatorname{E}_p[\log q], where \operatorname{E}_p[\cdot] is the expected value operator with respect to the distribution p. The definition may be formulated using the Kullback–Leibler divergence D_{\mathrm{KL}}(p \parallel q), divergence of p from q (also known as the relative entropy of p with respect to q). H(p, q) = H(p) + D_{\mathrm{KL}}(p \parallel q), where H(p) is the entropy of p. For discrete probability distributions p and q with the same support \mathcal{X}, this means {{Equation box 1 The situation for continuous distributions is analogous. We have to assume that p and q are absolutely continuous with respect to some reference measure r (usually r is a Lebesgue measure on a Borel σ-algebra). Let P and Q be probability density functions of p and q with respect to r. Then -\int_\mathcal{X} P(x)\, \log Q(x)\, \mathrm{d}x = \operatorname{E}_p[-\log Q], and therefore {{Equation box 1 NB: The notation H(p,q) is also used for a different concept, the joint entropy of p and q. == Motivation ==

In information theory, the Kraft–McMillan theorem establishes that any directly decodable coding scheme for coding a message to identify one value x_i out of a set of possibilities \{x_1,\ldots,x_n\} can be seen as representing an implicit probability distribution q(x_i) = \left(\frac{1}{2}\right)^{\ell_i} over \{x_1, \ldots, x_n\}, where \ell_i is the length of the code for x_i in bits. Therefore, cross-entropy can be interpreted as the expected message-length per datum when a wrong distribution q is assumed while the data actually follows a distribution p. That is why the expectation is taken over the true probability distribution p and not q. Indeed the expected message-length under the true distribution p is \begin{align} \operatorname{E}_p[\ell] &= - \operatorname{E}_p\left[\frac{\ln{q(x)}}{\ln(2)}\right] \\[1ex] &= - \operatorname{E}_p\left[\log_2 {q(x)}\right] \\[1ex] &= - \sum_{x_i} p(x_i)\, \log_2 q(x_i) \\[1ex] &= -\sum_x p(x)\, \log_2 q(x) = H(p, q). \end{align} == Estimation ==

There are many situations where cross-entropy needs to be measured but the distribution of p is unknown. An example is language modeling, where a model is created based on a training set T, 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, p is the true distribution of words in any corpus, and q 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: H(T,q) = -\sum_{i=1}^N \frac{1}{N} \log_2 q(x_i) where N is the size of the test set, and q(x) is the probability of event x estimated from the training set. In other words, q(x_i) is the probability estimate of the model that the i-th word of the text is x_i. The sum is averaged over the N words of the test. This is a Monte Carlo estimate of the true cross-entropy, where the test set is treated as samples from p(x). == Relation to maximum likelihood ==

The cross entropy arises in classification problems when introducing a logarithm in the guise of the log-likelihood function. This section concerns the estimation of the probabilities of different discrete outcomes. To this end, denote a parametrized family of distributions by q_{\theta}, with \theta subject to the optimization effort. Consider a given finite sequence of N values x_i from a training set, obtained from conditionally independent sampling. The likelihood assigned to any considered parameter \theta of the model is then given by the product over all probabilities q_{\theta}(X=x_i). Repeated occurrences are possible, leading to equal factors in the product. If the count of occurrences of the value equal to x is denoted by \#x, then the frequency of that value equals \#x/N. If p(X=x) is the underlying probability distribution, for large N we expect p(X=x)\approx \#x/N, by the law of large numbers. Writing our likelihood function as the product of observations from the distribution q_\theta : \begin{align}\mathcal{L}(\theta; {\mathbf x}) &= \prod_{i} q_{\theta}(X=x_i) = \prod_{x} q_{\theta}(X=x)^{\#x} \\ &\approx \prod_{x} q_{\theta}(X=x)^{N \cdot p(X=x)} = \exp\log\left[\prod_{x} q_{\theta}(X=x)^{N \cdot p(X=x)} \right]\\ &= \exp\left(\sum_{x} N \cdot p(X=x)\log q_{\theta}(X=x)^{} \right), \end{align} where we have used the calculation rules for the logarithm in the final line. Notice how the exponent contains a -H(p,q_\theta) term. Taking the logarithm of both sides gives: \log \mathcal{L}(\theta; {\mathbf x}) = -N\cdot H(p, q_\theta). Since the logarithm is a monotonically increasing function, the maximizing value of \theta is unaffected by this final step. Similarly, the maximizing value of \theta is unaffected by the factor of N. So we observe that the likelihood maximization amounts to minimization of the cross-entropy. == Cross-entropy minimization ==

Cross-entropy minimization is frequently used in optimization and rare-event probability estimation. When comparing a distribution q against a fixed reference distribution p, cross-entropy and KL divergence are identical up to an additive constant (since p is fixed): According to the Gibbs' inequality, both take on their minimal values when p = q, which is 0 for KL divergence, and \mathrm{H}(p) for cross-entropy. In the engineering literature, the principle of minimizing KL divergence (Kullback's "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 q is the fixed prior reference distribution, and the distribution p is optimized to be as close to q 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 D_{\mathrm{KL}}(p \parallel q), rather than H(p, q). In fact, cross-entropy is another name for relative entropy; see Cover and Thomas and Good. On the other hand, H(p, q) 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 learning. The true probability p_i is the true label, and the given distribution q_i is the predicted value of the current model. This is also known as the log loss (or logarithmic loss or logistic loss); the terms "log loss" and "cross-entropy loss" are used interchangeably. More specifically, consider a binary regression model which can be used to classify observations into two possible classes (often simply labelled 0 and 1). The output of the model for a given observation, given a vector of input features x , 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 g(z) = 1/(1+e^{-z}) where z is some function of the input vector x, commonly just a linear function. The probability of the output y=1 is given by q_{y=1} = \hat{y} \equiv g(\mathbf{w}\cdot\mathbf{x}) = \frac 1 {1+e^{-\mathbf{w}\cdot\mathbf{x}}}, where the vector of weights \mathbf{w} is optimized through some appropriate algorithm such as gradient descent. Similarly, the complementary probability of finding the output y=0 is simply given by q_{y=0} = 1-\hat{y}. Having set up our notation, p\in\{y,1-y\} and q\in\{\hat{y},1-\hat{y}\}, we can use cross-entropy to get a measure of dissimilarity between p and q: \begin{align} H(p,q) &= -\sum_m p_m \log q_m = -y\log\hat{y} - (1-y) \log(1-\hat{y}). \end{align} 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. For example, suppose we have N samples with each sample indexed by n=1,\dots,N. The average of the loss function is then given by \begin{align} J(\mathbf{w}) &= \frac{1}{N} \sum_{i=1}^N H(p_i,q_i) \\ &= -\frac{1}{N} \sum_{i=1}^N\ \left[y_i \log \hat y_i + (1 - y_i) \log (1 - \hat y_i)\right], \end{align} where \hat{y}_i\equiv g(\mathbf{w}\cdot\mathbf{x}_i) = 1/(1+e^{-\mathbf{w}\cdot\mathbf{x}_i}) , with g(z) as the logistic function as before. == Relation to linear regression ==

The gradient of the cross-entropy loss for logistic regression is equal to the gradient of the squared-error loss for linear regression (up to a constant factor). To see this, define X \equiv \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)}, \hat{y_i} = g(\mathbf{w}\cdot X^i) = \frac{1}{1+\exp(-w_0-w_1x_{i1}-\dots-w_px_{ip})}, L(\mathbf{w}) \equiv -\sum_{i=1}^N \left[y_i\ln \hat{y}_i+(1-y_i)\ln(1-\hat{y}_i)\right]. Then we have the result \nabla_{\mathbf{w}} L(\mathbf{w})=X^\mathsf{T}(\hat{\mathbf{y}}-\mathbf{y}). Proof: For any \hat{y}_i we have \frac{\partial}{\partial w_0}\ln \hat{y}_i = \frac{\partial}{\partial w_0}\ln\frac{1}{1+e^{-w_0+k_0}} = \frac{e^{-w_0+k_0}}{1+e^{-w_0+k_0}} = 1-\hat{y}_i, \frac{\partial}{\partial w_0}\ln (1-\hat{y}_i) = \frac{\partial}{\partial w_0}\ln \left(1-\frac{1}{1+e^{-w_0+k_0}}\right)=\frac{-1}{1+e^{-w_0+k_0}} = -\hat{y}_i and thus \begin{align} \frac{\partial L}{\partial w_0} &= -\sum_{i=1}^{N} [y_i (1-\hat{y}_i) - (1-y_i) \hat{y}_i] = -\sum_{i=1}^{N} [y_i-\hat{y}_i] = \sum_{i=1}^{N}X_{i0}(\hat{y}_i-y_i). \end{align} Similarly, for any \hat{y}_i and j = 1,\dots,p we have \frac{\partial}{\partial w_j}\ln \hat{y}_i = \frac{\partial}{\partial w_j}\ln \frac{1}{1+e^{-w_jx_{ij}+k_j}} = \frac{x_{ij}e^{-w_jx_{ij}+k_j}}{1+e^{-w_jx_{ij}+k_j}} = x_{ij}(1-\hat{y}_i), \frac{\partial}{\partial w_j}\ln (1-\hat{y}_i) = \frac{\partial}{\partial w_j}\ln\left[1-\frac{1}{1+e^{-w_jx_{ij}+k_j}}\right] = \frac{-x_{ij}}{1+e^{-w_jx_{ij}+k_j}} = -x_{ij}\hat{y}_i and thus \begin{align} \frac{\partial L}{\partial w_j} &= -\sum_{i=1}^N x_{ij}[y_i (1-\hat{y}_i) - (1-y_i) \hat{y}_i] = \sum_{i=1}^N X_{ij}(\hat{y}_i-y_i). \end{align} Put together, we obtain the desired result. Note that here we used the natural logarithm ln instead of log (canonically log_2) in the loss function L. This merely changes the result by a factor of log(e) though. Moreover, for all i we reused k_0 := -\sum_{l=1}^p w_l x_{il} and k_j := -w_0-\sum_{l \neq j} w_l x_{il} as constants w.r.t. each w_j. ==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. Assuming a simple ensemble of K classifiers is assembled via averaging the outputs, then the amended cross-entropy is given by e^k = H(p,q^k)-\frac{\lambda}{K}\sum_{j\neq k}H(q^j,q^k) where e^k is the cost function of the k^{th} classifier, q^k is the output probability of the k^{ th} classifier, p is the true probability to be estimated, and \lambda is a parameter between 0 and 1 that defines the 'diversity' that we would like to establish among the ensemble. When \lambda=0 we want each classifier to do its best regardless of the ensemble and when \lambda=1 we would like the classifier to be as diverse as possible. == See also ==