9
$\begingroup$

I know of Shannon's work with entropy, but lately I have worked on succinct data structures in which empirical entropy is often used as part of the storage analysis.

Shannon defined the entropy of the information produced by a discrete information source as $-\sum_{i=1}^k p_i \log{p_i}$, where $p_i$ is the probability of event $i$ occurring, e.g. a specific character generated, and there are $k$ possible events.

As pointed out by MCH in the comments, the empirical entropy is the entropy of the empirical distribution of these events, and is thus given by $-\sum_{i=1}^k \frac{n_{i}}{n} \log{\frac{n_{i}}{n}}$ where $n_{i}$ is the number of observed occurrences of event $i$ and $n$ is the total number of events observed. This is called zero-th order empirical entropy. Shannon's notion of conditional entropy has a similar higher order empirical version.

Shannon did not use the term empirical entropy, though he surely deserves some of the credit for this concept. Who did first used this idea and who first used the (very logical) name empirical entropy to describe it?

$\endgroup$
  • $\begingroup$ "pointwise defined for every string" sounds like Kolmogorov complexity: is that what you're referring to ? If not, can you point to a link that defines it, or better still provide a defn in the question itself ? $\endgroup$ – Suresh Venkat Jun 4 '13 at 22:07
  • 1
    $\begingroup$ It is called so because empirical entropy is the entropy of the empirical distribution of a sequence. $\endgroup$ – MCH Jun 4 '13 at 22:40
  • $\begingroup$ @SureshVenkat I've tried to elaborate the question. $\endgroup$ – deleted user 42 Jun 5 '13 at 10:50
  • 1
    $\begingroup$ Take a look to Kosaraju S. Rao, Manzini G., "Compression of low entropy strings with Lempel-Ziv algorithms" (1998), too. They analyze the performance of the Lempel-Ziv algorithms using the "so-called empirical entropy". $\endgroup$ – Marzio De Biasi Jun 5 '13 at 14:24
  • 2
    $\begingroup$ Note that the "empirical distribution" is really the ML distribution for a given set of frequency counts. So I wonder if this dates back to Bayes. Even Laplace had pondered the problem of defining a distribution from empirical counts. $\endgroup$ – Suresh Venkat Jun 5 '13 at 19:51
3
$\begingroup$

I am interested in "empirical entropy" like you and the earliest paper I find was that from Kosaraju like the user "Marzio De Biasi" told in his comment.

But in my opinion the real definitions of "empirical entropy" are made later by generalizing the former concepts:

  1. "Large Alphabets and Incompressibility" by Travis Gagie (2008)
  2. "Emprical entropy" by Paul M. B. Vitányi (2011)

Gagie rephrase the definition of $k$th order empirical entropy to:

  • $H_{k}(w)=\frac{1}{|w|}\min\limits_{Q}\left\{\log\large\frac{1}{P(Q=w)}\right\}$

where $Q$ is a $k$th order Markov process. He also showed that this definition is equivalent to the previous one.
The next step from Vitányi was a generalization to arbitrary classes of processes (not only Markov-processes):

  • $H(w|\mathcal{X})=\min\limits_{X}\left\{K(X)+H(X):\;\left|H(X)-\log\large\frac{1}{P(X=w)}\right|\normalsize\;is\;minimal!\right\}$

where $\mathcal{X}$ is the class of allowed processes and $K(X)$ is the Kolmogorov complexity.
If we choose $\mathcal{X}$ to be the class of $k$th order Markov processes producing a sequence of $|w|$ random variables and ignoring the Kolmogorov complexity, than this also leads to the definition of Gagie (multiplied with $|w|$).

$\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.