2
$\begingroup$

I recently read this paper Mahoney, 1999. And encountered this line,

optimal compression of a probabilistic language L with unknown distribution (such as English) using an estimated distribution M (an encoding of length −log2 M(x) bits for each string x) is M = L, by the discrete channel capacity theorem.

Can you please explain what this means and what is the relation between data compression and estimation of distribution?

$\endgroup$
2
$\begingroup$

Suppose that we have a random source $X$, and we wish to encode many independent samples $x_1,\ldots,x_n$ taken from $X$. An compression scheme is an algorithm that converts $n$ samples of $X$ to a binary string in a reversible way. Shannon showed that the optimal compression scheme produces binary strings of length roughly $nH(X)$, where $H(X)$ is the entropy of $X$.

In practice, we may have access to $X$ but might not know its distribution exactly. What we can do is to estimate its distribution as $Y$, and then use an optimal compression for $Y$. This will produce binary strings of length roughly $n(H(X) + D(X\|Y))$, where $D(X\|Y)$ is the Kullback–Leibler divergence (called cross-entropy by Mahoney). We have $D(X\|Y) \geq 0$, with equality only when $Y = X$. Thus optimal compression requires knowing the distribution of the source exactly.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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