Definition and origin of “cross entropy”

Question

Without citing sources, Wikipedia defines the cross-entropy of discrete distributions $P$ and $Q$ to be

\begin{align} \mathrm{H}^{\times}(P; Q) &= -\sum_x p(x)\, \log q(x). \end{align}

Who was first to start using this quantity? And who invented this term? I looked in:

J. E. Shore and R. W. Johnson, "Axiomatic derivation of the principle of maximum entropy and the principle of minimum cross-entropy," Information Theory, IEEE Transactions on, vol. 26, no. 1, pp. 26-37, Jan. 1980.

I followed their introduction to

A. Wehrl, "General properties of entropy," Reviews of Modern Physics, vol. 50, no. 2, pp. 221-260, Apr. 1978.

who never uses the term.

Neither does

S. Kullback and R. Leibler, "On information and sufficiency," The Annals of Mathematical Statistics, vol. 22, no. 1, pp. 79-86, 1951.

I looked in

T. M. Cover and J. A. Thomas, Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing). Wiley-Interscience, 2006.

and

I. Good, "Maximum Entropy for Hypothesis Formulation, Especially for Multidimensional Contingency Tables," The Annals of Mathematical Statistics, vol. 34, no. 3, pp. 911-934, 1963.

but both papers define cross-entropy to be synonymous with KL-divergence.

The original paper

C. E. Shannon, "A Mathematical Theory of Communication," Bell system technical journal, vol. 27, 1948.

Doesn't mention cross entropy (and has a strange definition of "relative entropy": "The ratio of the entropy of a source to the maximum value it could have while still restricted to the same symbols").

Finally, I looked in some old books and papers by Tribus.

Does anyone know what the equation above is called, and who invented it or has a nice presentation of it?

Answer 1

It seems to be closely related to the concept of Kullback–Leibler divergence (see Kullback and Leibler, 1951). In their article Kullback and Leibler discuss the mean information for discriminating between two hypotheses (defined as $I_{1:2}(E)$ in eqs. $2.2-2.4$) and cite pp. 18-19 of Shannon and Weaver's The Mathematical Theory of Communication (1949) and p. 76 of Wiener's Cybernetics (1948).

EDIT:

Additional aliases include the Kullback-Leibler information measure, the relative information measure, cross-entropy, I-divergence and Kerridge inaccuracy.

Answer 2

Thanks to @Itamar's suggestion, I found a mention in:

I. J. Good, "Some Terminology and Notation in Information Theory," Proceedings of the IEE - Part C: Monographs, vol. 103, no. 3, pp. 200-204, Mar. 1956.

It would still be really useful for me to find a nice presentation of cross-entropy.

Answer 3

Thanx for this - good summary of background literature. The 1980 Shore and Johnson article in IEEE is a good start, but @itamar's pointer to the Good monograph from 1956 is even better. The concept seems to come from Shannon's work, with Kullback & Leibler's 1951 AMS note being the origin of the current use of the term. As far as the origin of the term "cross entropy" relates to artificial neural networks, there is a term used in a paper in Science, submitted 1994, published 1995, by G. E. Hinton, P. Dayan, B. J. Frey & R. M. Neal, in which there is an early use of the term "Hemholtz Machine" - possibly the first. Url for copy In that paper, "The Wake-sleep algorithm for unsupervised neural networks", the note before equation #5 says:

When there are many alternative ways of describing an input vector it is possible to design a stochastic coding scheme that takes advantage of the entropy across alternative descriptions[1]. The cost is then:" (see paper for eqn#5)

The second term is then the entropy of the distribution that the recognition weights assign to the various alternative representations.

Later in the paper, eqn#5 is rewritten as eqn#8, with the last term described as the Kullback-Leibler divergence between the initial probability distribution, and the posterior probability distribution. The paper states:

So for two generative models which assign equal probability to d, minimizing equation #8 with respect to the generative weights will tend to favour the model whose posterior distribution is most similar to Q(.|d) (Where Q(.|d) is the initial distribution you are training your net towards.)

This paper still describes the minimization process for this specific algorithm as minimizing the Kullback-Leibler divergence, but it looks like it could be where the term "entropy across alternative descriptions" was shortened to just "cross entropy". For an numerical example of cross entropy, using TensorFlow, see the posting here, it is helpful: What is cross-entropy?

Note that the solution of CE = 0.47965 is derived simply by taking the natural log of the .619 probability. In the above example, the use of "one hot" encoding means that the other two initial and posterior probabilities are ignored due to multiplication by zero-valued initial probability, in the summation for cross entropy.