3
$\begingroup$

I'd like to measure how much information a document $D$ contains.

Clearly, the New York Times published yesterday contains more information than my diary wrote on the same day. But, I do not know how to quantify those differences.

I think there are at least two alternatives. Those are the information entropy, and tf-idf.

In general, the information entropy $H$ is employed to measure the information. Basically the information entropy seems OK to measure document information.

For instance, let's compare two documents: $D_1 = \text{"Tom loves Mary. Tom loves Mary"}$; $D_2 = \text{"Tom loves Mary. Jack loves Jane."}$. In this case, clearly the information of $D_1$ is less than $D_2$ and $H(D_1) < H(D_2)$ holds.

The tf-idf is the second option. With tf-idf, more rare words are regarded as more informative words. This also sounds valid. In fact, tf-idf is used to measure the importance of documents in automatic document summarization.

Then, my questions are

  • Are there standard way to measure the information of a document?
  • Are The information entropy and tf-idf used for this purpose? Why or why not?

Update on Aug 17

Thanks to several kind comments, I came to clarify what my question really was. I'd like to know formal (mathematical) definition of what is information or informative in the "NYT-and-diary comparison".

Intuitively, the New York Times is more helpful than my diary in order to get valuable information. In fact, many people pay $3 for NYT, and most people do not for my diary.

However, formally (mathematically), I can not explain why NYT is more informative.

Hence, my question is equivalent to how to formally define information or informative in the NYT-diary case. Then, the questions in the comments like "what do you mean by information" is totally what I'd like to know :)

$\endgroup$
  • 2
    $\begingroup$ I think you need to define "information" more precisely if you want to be able to distinguish between the NYT and your diary. $\endgroup$ – adrianN Aug 16 '16 at 10:16
  • $\begingroup$ @adrianN Thank you very much. Yes. I think this problem is almost equivalent to "how to define the information in a document". If it is precisely (mathematically) defined, the amount of the information can be defined. $\endgroup$ – rkjt50r983 Aug 16 '16 at 10:24
  • 3
    $\begingroup$ I'm not an expert, but I think this is too broad. It may be impossible to capture "information content" in a both general and meaningful way. You may want to restrict yourself to documents of a certain kind. $\endgroup$ – Raphael Aug 16 '16 at 10:58
  • 2
    $\begingroup$ What do you mean by information? In the general vernacular, "information" is a spectacularly vague and poorly-defined word. Alternatively, Shannon entropy is precisely-defined but apparently not what you want. So what do you want? Until you can tell us what you mean by information, I doubt we can answer your question. $\endgroup$ – D.W. Aug 16 '16 at 17:57
  • $\begingroup$ Frequencies or entropy will give the wealth of document, how sophisticated vocabulary was used, but will not tell apart the fresh news from common knowledge or past events. There is an emotional correlation of words, style measure (special dictionaries to anoint words), but this is not about information definition. NLP can boil down text, but to really answer the "informative" part - unfortunately no way to do that. Something is informative to someone, assuming common and prior knowledge - subjective task. To compare NYT and YD you can use the mutual information scheme on processed text. $\endgroup$ – Evil Sep 16 '16 at 1:15
2
$\begingroup$

Assuming that your data comes from a Markovian source, you can estimate the entropy of the source using an optimal compression algorithm such as Lempel–Ziv, whose theoretical version (without limiting the table size) is known to asymptotically converge to the entropy. That is, if the entropy of the source (suitable defined) is $H$, then the expected compressed size of $n$ samples is roughly $nH$. Definitions and proofs appear in Cover and Thomas' Elements of Information Theory, Chapter 13 of the 2nd edition.

The entropy of the source differs from your example. It doesn't make sense to calculate the entropy of a single output – entropy is a function of a random variable (or a distribution), and the entropy of a constant random variable is zero. Instead, we consider your source text as a random variable, and our goal is to estimate the entropy of that random variable from a single sample.

If the source has no memory – that is, the individual symbols of the text are independent – then a good estimate of the entropy of the source is the empirical single-character entropy, which is the function that appears in your question. But general sources – such as a random text – do have memory: if you just sample a random list of characters according to their distribution in the English language, you will get gibberish (a nice example of this appears in Shannon's 1948 paper, p. 7). This is why we need to use a more sophisticated estimator, such as the Lempel–Ziv algorithm.

In practice, you can approximate the information content by just compressing the text using an off-the-shelf program.

$\endgroup$
0
$\begingroup$

You can compute Shannon entropy or tf-idf for a quantifiable measure but it is not possible to compute Kolmogorov complexity in general.

$\endgroup$
  • 3
    $\begingroup$ I don't see how this answers the question. $\endgroup$ – Raphael Aug 16 '16 at 22:40

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.