18
$\begingroup$

When we quantify information, we use $I(x)=-\log{P(x)}$, where $P(x)$ is the probability of some event $x$. The explanation I always got, and was satisfied with up until now, is that for two independent events, to find the probability of them both we multiply, and we would intuitively want the information of each event to add together for the total information. So we have $I(x \cdot y) = I(x) + I(y)$. The class of logarithms $k \log(x)$ for some constant $k$ satisfy this identity, and we choose $k=-1$ to make information a positive measure.

But I'm wondering if logarithms are more than just a sensible choice. Are they the only choice? I can't immediately think of another class of functions that satisfy that basic identity. Even in Shannon's original paper on information theory, he doesn't say it's the only choice, he justifies his choice by saying logs fit what we expect and they're easy to work with. Is there more to it?

$\endgroup$
  • 5
    $\begingroup$ That functional equation characterizes the logarithm (as long as you have any reasonable continuity condition). $\endgroup$ – Ethan Bolker Jun 11 '17 at 15:26
  • $\begingroup$ The logarithm I think is the only class of continuous functions that turn multiplication into addition, but as you said the explanation is only intuitive. I don't know of an alternative, but I am certain the logarithm is not the only possible choice. $\endgroup$ – Matt Samuel Jun 11 '17 at 15:27
  • $\begingroup$ Sketch of proof: Let $I = f\circ\log$, then the identity becomes $f(a+b)=f(a)+f(b)$, which is Cauchy's functional equation. $\endgroup$ – Rahul Jun 11 '17 at 15:30
  • 5
    $\begingroup$ I don't think that $I(xy) = I(x) + I(y)$ etc are the only properties that make $\log$ the sensible choice for computing information. Such a "function hunt" ignores the fact that information and exponentials are actually fundamentally related. Check out this explanation, starting from the section titled "Codes". A simple binary information example is used to demonstrate the exponential hiding in the process of finding the smallest code-length we can use to transfer a certain message, which brings us to a core notion of information. $\endgroup$ – jnez71 Jun 11 '17 at 20:35
  • 1
    $\begingroup$ There is a generalization -- Renyi entropy and renyi divergences and what not. You might want to look into this, but they lose some of the properties Shannon entropy has (see problem 2.46 in Cover and Thomas Elements of Information Theory 2e for an axiomatic def. of Shannon entropy). $\endgroup$ – Batman Jun 12 '17 at 3:24
18
$\begingroup$

We want to classify all continuous(!) functions $I\colon(0,1]\to\Bbb R$ with $I(xy)=I(x)+I(y)$. If $I$ is such a function, we can define the (also continouus) function $f\colon[0,\infty)\to \Bbb R$ given by $f(x)=I(e^{-x})$ (using that $x\ge 0$ implies $e^{-x}\in(0,1]$). Then for $f$ we have the functional equation $$f(x+y)=I(e^{-(x+y)})=I(e^{-x}e^{-y})=I(e^{-x})+I(e^{-y})=f(x)+f(y).$$ Let $$ S:=\{\,a\in[0,\infty)\mid \forall x\in[0,\infty)\colon f(ax)=af(x)\,\}.$$ Then trivially $1\in S$. Also, $f(0+0)=f(0)+f(0)$ implies $f(0)=0$ and so $0\in S$. By the functional equation, $S$ is closed under addition: If $a,a'\in S$ then for all $x\ge 0$, we have $$f((a+a')x)=f(ax+a'x)=f(ax)+f(a'x)=af(x)+a'f(x)=(a+a')f(x)$$ and so als $a+a'\in S$.

Using this we show by induction that $\Bbb N\subseteq S$: We have $1\in S$; and if $n\in S$ then also $n+1\in S$ (because $1\in S$).

Next note that if $a,b\in S$ with $b>0$ then for all $x\ge0$ we have $f(a\frac xb)=af(\frac xb)$ and $f(x)=f(b\frac xb)=bf(\frac xb)$, i.e., $f(\frac ab x)=\frac abf(x)$ and so $\frac ab\in S$. As $\Bbb N\subseteq S$, this implies that $S$ contains all positive rationals, $\Bbb Q_{>0}\subseteq S$.

In particular, if we let $c:=f(1)$, then $f(x)=cx$ for all $x\in \Bbb Q_{>0}$. As we wanted continuous functions, it follows that $f(x)=cx$ for all $x\in[0,\infty)$. Then $$ I(x)=f(-\ln x)=-c\ln x.$$

Remark: The request for continuity of $I$ (and hence $f$) is of course reasonable in the given context. But it turns out that much milder restrictons on $f$ suffice to enforce the result as found. It is only without any such restrictions that the Axiom of Choice supplies us with highly non-continuous additional solutions to the functional equation. The original remark that the logs fits what we expect and are easy to work with is quite an understatement if one even thinks of considering these non-continuous solutions.

$\endgroup$
  • 9
    $\begingroup$ Man, how I wish all of mathematics was taught like this. It's infinitely more satisfying to say "hmm, what properties should X have?" and then deduce that down to "aha, X must be Y" instead of going "what if X happens to be Y? oh hey, it also has properties that make sense!" $\endgroup$ – Mehrdad Jun 12 '17 at 1:36
  • 2
    $\begingroup$ @Mehrdad I wonder if there is a list of books on MSE where mathematics is taught like that :) Because even if you are dealing with math for quite long time, when you want to study something outside of your area of expertise the purely axiomatic and theorems-driven approach to material isn't very helpful. $\endgroup$ – Evgeny Jun 12 '17 at 9:55
  • $\begingroup$ The middle of the proof is just showing that $f(kx)=kf(x)$ for all $k$ in the reals, and I found this link that goes step by step at a slow pace. Someone may find it useful someday: westmont.edu/~howell/courses/ma-108/illustrations/… $\endgroup$ – Cordello Jun 12 '17 at 15:46
9
$\begingroup$

I just wanted to point something out, but honestly, I think the other answers are far better given that this is a mathematics site. I'm just pointing it out to add another argument for why logarithm makes sense as the only choice.

You have to ask yourself what information even is. What is information?

Information is the ability to distinguish possibilities.1

1 Compare with energy in physics: the ability to do work or produce heat.

Okay, let's start reasoning.

Every bit (= binary digit) of information can (by definition) distinguish 2 possibilities, because it can have 2 different values. Similarly, every n bits of information can distinguish $2^n$ possibilities.

Therefore: the amount of information required to distinguish $2^n$ possibilities is $n$ bits.
And the same exact reasoning works regardless of whether you're talking about base 2 or 3 or e.
So clearly you have to take a logarithm if the number of possibilities is an integer power of the base.

Now, what if the number of possibilities is not a power of $b = 2$ (or whatever your base is)?
In this case you're looking for a function that coincides with the logarithm at the integer powers.

At this point, I would be convinced to use the logarithm itself (anything else would seem bizarre), but this is where a mathematician would invoke the reasonings mentioned in the other arguments (continuity or additivity for independent events or whatever) to show that no other function could satisfy reasonable criteria on information content.

$\endgroup$
0
$\begingroup$

My understanding is that $-\log$ provides a mapping $({\mathbb R}_{\geq 0},+,\cdot)\rightarrow({\mathbb R}\cup\{\infty\},\min,+)$ between semirings (multiplicatively a monoid homomorphism). It is monotonically decreasing and maps large probabilities to low weights and vice versa. This is used in certain statistical models such as sequence alignment and hidden Markov model. The mapping is sometimes referred to tropicalization. Have a look into the work of Bernd Sturmfels et al.

$\endgroup$
  • $\begingroup$ Are you saying that $\log(a+b)=\min\{-\log a,-\log b\}$?? $\endgroup$ – Hagen von Eitzen Jun 11 '17 at 15:35
  • $\begingroup$ No multiplicatively: $-log(xy) = -(log(x)+log(y)) = (-log(x))+ (-log(y))$. $\endgroup$ – Wuestenfux Jun 11 '17 at 15:39
  • $\begingroup$ What's going on with $+$ and $\min$ in there? $\endgroup$ – G Tony Jacobs Jun 11 '17 at 15:41
  • $\begingroup$ Have a look into the Viterbi algorithm which is derived from an ansatz in sum-product decomposition the HMM model. Its tropicalization, which means replacing sums by tropical sums and products by tropical products, yields the Viterbi algorithm in the min-plus semiring $((\mathbb{R}\cup\{\infty\},min,+)$. $\endgroup$ – Wuestenfux Jun 11 '17 at 15:45
  • $\begingroup$ Ok, but is it the only choice that meets all those lovely requirements, or is it just a convenient choice? $\endgroup$ – Cordello Jun 11 '17 at 15:48

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.