# Notation of cross entropy

I have a question regarding a notation that seems to be very usual.

For starters, cross entropy is defined by:

\begin{align}H(X, q) &= H(X) + D(p||q) \\ & =-\sum_x p(x)\log_2 q(x)\end{align}

However, when applied to a language model $m$, with a language $L=X_{i}\approx p(x)$, it's defined as:

$$H(L, m) = -\lim_{n \to \infty}\frac{1}{n}\sum_{X_{ \,\scriptstyle 1n}}p(x_{1n})\log \;m(x_{1n})\tag{1}$$

Apologies if it's too small to see. The sum is over $X_{1n}$ and the notation $x_{1n}$ means the sequence $(x_1, x_2,\ldots, x_n)$. Well, my question is: What does it mean $(1)$? My assumption is that if I have a language that consists of, say, 5 words {hi, this, is, a, test} and I want to know how good a model of that language is, then $\sum_{X_{\,\scriptstyle 1n}}$ is summing over sequences of $n$ elements from my words. If I were to say that $n=4$, in this case, $m(x_{1n})$ should be something like the probability according to my model $m$ of having a sentence {hi, this, is, a} plus the probability of {this, is, a, test}, plus the probability of ... etc, although I'm not sure if they should be consecutive, which is a good restriction to have in linguistics but I don't see that reflected in $(1)$. Is this interpretation correct?

Other question: $x_{1n}$ contains elements that a random variable $X$ can have? Then what does it mean $X_{1n}$, that is, $(X_{1}, X_{2},\ldots,X_{n})$ ? I suppose that every $X_{i}$ refers to the same event space but that seems to suggest that I could have {hi, hi, hi, hi}. Is that true?

Last question: What happens to $(1)$ when $n\to \infty$? Supposedly, this limit is appropriate when dealing with a whole language or a very large sentece. In this case, we are considering infinitely large sequences of letters or words, but how do you calculate something like that? Actually, in general, how do you calculate $(1)$?

UPDATE

I think I understand a little bit better what is meant to be $(1)$. It's clearer if I use this alternative notation:

$$H(L, m) = -\lim_{n \to \infty}\frac{1}{n}\sum_{x_{1}, x_{2},..., x_{n}\in L }p(x_{1}, x_{2},..., x_{n})\log m(x_{1}, x_{2},..., x_{n})\tag{2}$$

where $L$ is the set of every sequence of $n$ elements (they can be letters, words, bigrams, etc). Using bigrams as an example, $n = 2$. Then if I had a sentence (any sentence), $(2)$ refers to sum like this:

$$H(L, m) = -\lim_{n \to \infty}\frac{1}{2}\sum_{x_{1}, x_{2}\in L }p(x_{1}, x_{2})\log m(x_{1}, x_{2})\tag{3}$$

So, the limit is saying simply that we can calculate the cross entropy of a language $L$ and a model $m$ (that is, how good is our model $m$ given that the true distribution for $L$ is given by $p(x)$) when dealing with a very large sequence. Cross entropy seems to be a modification of entropy rate which is defined by:

$$H(L) = -\lim_{n \to \infty}\frac{1}{n}\sum_{x_{1}, x_{2},..., x_{n}\in L }p(x_{1}, x_{2},..., x_{n})\log p(x_{1}, x_{2},..., x_{n})\tag{*}$$

In (*), we are calculating the average entropy per symbol. $\displaystyle \frac{1}{n}$ is there to ensure we are getting that average.

Is this interpretation correct?

Thanks!

-

When the letters in the language model $(L,m)$ are i.i.d. for some $(p_0,m_0)$, $p(x_{1:n})=\prod\limits_{k=1}^np_0(x_k)$ and $m(x_{1:n})=\prod\limits_{k=1}^nm_0(x_k)$ hence the summation in the RHS of (1) is $$\sum_{x_{1:n}}\prod\limits_{i=1}^np_0(x_i)\sum\limits_{k=1}^n\log m_0(x_k)=\sum_{k=1}^n\sum_{x_k}p_0(x_k)\log m_0(x_k)\sum_{x_{i},i\ne k}p(x_{1:k-1}x_{k+1:n}).$$ Each last sum over $x_i$, $i\ne k$, on the RHS is $1$ because $p_0$ is a probability distribution, hence, for every $n\geqslant1$, $$\frac1n\sum_{x_{1:n}}p(x_{1n})\log m(x_{1:n})=\sum_{x_0}p_0(x_0)\log m_0(x_0)=-HH(p_0,m_0).$$ In particular, $HH(L,m)=HH(p_0,m_0)$, that is, the limit formula (1) for cross entropy extends to non i.i.d. models the classical definition.
Too bad.   –  Did Jul 12 '12 at 6:09