Kullback and Leibler: "On Information and Sufficiency" (1951)

This paper is mostly known for introducing the concept of divergence into statistics. It's quite notation-heavy but actually quite straightforward if you've already solved exercise 3.9 in Cover and Thomas' textbook. Everything is about log-likelihood ratios that fly off into infinity.

The paper is concerned quite a lot with the question of sufficient statistics. An interesting illustration in the last paragraph (§6) concerns the problem of how to choose the best non-sufficient statistic when we must (for some extrinsic reason).

More specifically, the set up is the following: You are observing samples from a categorical distribution with four different categories, and you want to distinguish the two following hypotheses:

x	1	2	3	4
Pr(x | A)	.25	.25	.25	.25
Pr(x | B)	.50	.30	.10	.10

However, you are not actually allowed to see the original data set; instead, you have to lump the categories into two groups, and you will then be told which group the observation fell. (This corresponds to using an indicator function as your statistic.)

In order to solve this exercise, they quantify the informativeness of the statistic in terms of the symmetrized divergence between the two hypotheses:

J(A, B)  ==  D(A || B) + D(B || A).

I guess a more cautious measure would have been the minimum of the two, since this would provide a lower bound on the growth rate of the likelihood ratio whichever of the two hypotheses were true.

Using base 10 logarithms, the divergence from the uniform to the skewed distribution (A to B) is .1039, and the divergence from the skewed to the uniform (B to A) is .0947. The symmetrized divergence J(A, B) is thus about .1986, and the minimum is .0947.

Grouping the categories in various ways, we can also find the following divergences:

Grouping	D(A || B)	D(A || B)	J(A, B)	min
{}, {1, 2, 3, 4}	0	0	0	0
{1}, {2, 3, 4}	.5068	.0635	.1193	.0635
{2}, {1, 3, 4}	.0027	.0028	.0055	.0027
{3}, {2, 3, 4}	.0401	.0315	.0716	.0315
{4}, {2, 3, 4}	.0401	.0315	.0716	.0315
{1, 2}, {3, 4}	.0969	.0837	.1806	.0837
{1, 3}, {2, 4}	.0089	.0087	.0176	.0087
{1, 4}, {2, 3}	.0089	.0087	.0176	.0087

In the paper, Kullback and Leibler report that the best grouping is {{1}, {2, 3, 4}}, which indicates that they might have used D(A || B) as their objective function. This is a bit strange, since everything they say in the text indicates that they are thinking exclusively in terms of the symemtrized divergence J. I don't know what to conclude from that.

Topsøe: "Game Theoretical optimization inspired by information theory" (2009)

I finally got around to reading Flemming's recent paper on information theory. It's a short introduction to his and Peter Harremoës' approach to the topic, which involves a game-theoretical interpretation of coding.

The Nature-Observer Game

The basic theoretical framework is the following: Nature and Observer play a zero-sum game. Nature picks a world from the set X, and Observer picks an action from the set Y. For each strategy profile (x,y), three quantities are then defined:

• H(x), the entropy of x
• D(x,y), the (Kullback-Leibler) divergence of x from y
• Φ(x,y), the complexity of the pair (x,y)

The three quantities are related through the equality

Complexity = Entropy + Divergence

which also implies that the smallest complexity that Observer can achieve in a world x is the entropy H(x).

The point of the game is for nature to produce maximal complexity, and for Observer to produce minimal complexity. By Von Neumann and Morgenstern's minimax theorem, this means that a strategy profile (x*,y*) is an equilibrium for the game if the following three quantities coincide (p. 559):

sup_x inf_y Φ(x,y) = Φ(x*,y*) = inf_y sup_x Φ(x,y)

The leftmost term here designates the optimal outcome for Nature (highest complexity given averse reponses), while the rightmost term designates the optimal outcome for Observer (lowest complexity given averse responses).

Notice that inf_y Φ(x,y) = H(x), since D(x,y) is assumed to be positive. This means that Nature in effect can be seen as an entropy-maximizer when playing optimally. Further, Topsøe defines R(y) = sup_x Φ(x,y) to be the risk associated with a given action y, so Observer can then be described as a risk-minimizer.

Information Transmission

The paper also defines a notion of information transmission rate (p. 556), but I am not quite sure about its applications. But this is the idea behind the concept, in bullet-point form:

• Assume that α is a (prior) probability distribution on the set of worlds.
• Construct an expected case scenario by summing all worlds with the probabilities of α as weights.
• Let y be a best response to this expected case.
• For each world x, let the surprisal of x be the divergence between x and y. This can be seen as a motivated quantitative measure of how different x is from the expected case.
• Find the weighted average of the surprisals, using the probabilities of α as weights.

This average surprise level is the information transmission rate.

Notice that if there is a single action which is an optimal response to all worlds, then the information transmission rate is 0. This reflects the fact that the state of the world would not inform the actions of Observer at all in such a situation. He would simply use the same strategy whatever happened.

Reversely, if the information transmission rate is very high, this means that an insensitive, on-average response pattern will be costly for the Observer (in terms of complexity). If we reinterpret the action of choosing a best response to a certain world as an act of inferring the state of the world (describing it correctly), then the surprisal can further be seen as Observer's ability to distinguish states of the world. On such an interpretation, the best-response function can be seen as a signaling function in a Bayesian game.