Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

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.

share|improve this answer
    
Thanks but I'd like to read more of an explanation. What does it mean when applied in a language model. Also, the i.i.d assumption doesn't hold very well in languages, right? –  Robert Smith Jul 12 '12 at 5:48
    
Also, the i.i.d assumption doesn't hold very well in languages, right? Nowhere in the answer do they say it does, right? What they say is that the limit formula for HH(L,m) is a generalization of the formula HH(X,q) you recall. –  Did Jul 12 '12 at 5:51
    
But that wasn't my question at all. –  Robert Smith Jul 12 '12 at 6:03
    
Too bad. $ $ $ $ –  Did Jul 12 '12 at 6:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.