Jaynes’ Widget Problem^[1]: How Do We Update On An Expected Value?

Mr A manages a widget factory. The factory produces widgets of three colors - red, yellow, green - and part of Mr A’s job is to decide how many widgets to paint each color. He wants to match today’s color mix to the mix of orders the factory will receive today, so he needs to make predictions about how many of today’s orders will be for red vs yellow vs green widgets.

The factory will receive some unknown number of orders for each color throughout the day - $N_r$ red, $N_y$ yellow, and $N_g$ green orders. For simplicity, we will assume that Mr A starts out with a prior distribution $P[N_r,N_y,N_g]$ under which:

• Number of orders for each color is independent of the other colors, i.e. $P[N_r,N_y,N_g]=P\left[N_r\right]P\left[N_y\right]P\left[N_g\right]$
• Number of orders for each color is uniform between 0 and 100: $P[N_i=n_i]=\frac{1}{100}I[0\le n_i<100]$^[2]

… and then Mr A starts to update that prior on evidence.

You’re familiar with Bayes’ Rule, so you already know how to update on some kinds of evidence. For instance, if Mr A gets a call from the sales department saying “We have at least 40 orders for green widgets today!”, you know how to plug that into Bayes’ Rule:

$P[N_r,N_y,N_g|N_g\ge 40]=\frac{1}{P[N_g\ge 40]}P[N_g\ge 40|N_r,N_y,N_g]P[N_r,N_y,N_g]$

$=\frac{1}{0.6}I[N_g\ge 40]P\left[N_r\right]P\left[N_y\right]P\left[N_g\right]$

… i.e. the posterior is still uniform, but with probability mass only on $N_g\ge 40$, and the normalization is different to reflect the narrower distribution.

But consider a different kind of evidence: Mr A goes through some past data, and concludes that the average number of red sales each day is 25, the average number of yellow sales is 50, and the average number of green sales is 5. So, Mr A would like to update on the information $E\left[N_r\right]=25,E\left[N_y\right]=50,E\left[N_g\right]=5$.

Chew on that for a moment.

That’s… not a standard Bayes’ Rule-style update situation. The information doesn’t even have the right type for Bayes’ Rule. It’s not a logical sentence about the variables $(N_r,N_y,N_g)$, it’s a logical statement about the distribution itself. It’s a claim about the expected values which will live in Mr A’s mind, not the widget orders which will live out in the world. It’s evidence which didn’t come from observing $(N_r,N_y,N_g)$, but rather from observing some other stuff and then propagating information through Mr A’s head.

… but at the same time, it seems like a kind of intuitively reasonable type of update to want to make. And we’re Bayesians, we don’t want to update in some ad-hoc way which won’t robustly generalize, so… is there some principled, robustly generalizable way to handle this type of update? If the information doesn’t have the right type signature for Bayes’ Rule, how do we update on it?

Enter Maxent

Here’s a handwavy argument: we started with a uniform prior because we wanted to assume as little as possible about the order counts, in some sense. Likewise, when we update on those expected values, we should assume as little as possible about the order counts while still satisfying those expected values.

Now for the big claim: in order to “assume as little as possible” about a random variable, we should use the distribution with highest entropy.

Conceptually: the entropy $H\left(\right(N_r,N_y,N_g\left)\right)$ tells us how many bits of information we expect to gain by observing the order counts. The less information we expect to gain by observing those counts, the more we must think we already know. A 50/50 coinflip has one bit of entropy; we learn one bit by observing it. A coinflip which we expect will come up heads with 100% chance has zero bits of entropy; we learn zero bits by observing it, because (we think) we already know the one bit which the coin flip nominally tells us. One less bit of expected information gain is one more bit which we implicitly think we already know. Conversely, one less bit which we think we already know means one more bit of entropy.

So, to assume as little as possible about what we already know… we should maximize our distribution’s entropy. We’ll maximize that entropy subject to constraints encoding the things we do want to assume we know - in this case, the expected values.

Spelled out in glorious mathematical detail, our update looks like this:

$P[N_r,N_y,N_g|E[N_r]=25,E[N_y]=50,E[N_g]=5]=$

${\text{argmax}}_Q-{\sum }_{N_r,N_y,N_g}Q[N_r,N_y,N_g]logQ[N_r,N_y,N_g]$

$\text{subject to}{\sum }_{N_r}Q\left[N_r\right]N_r=25,{\sum }_{N_y}Q\left[N_y\right]N_y=50,{\sum }_{N_g}Q\left[N_g\right]N_g=5$

(... as well as the implicit constraints $Q[N_r,N_y,N_g]\ge 0$ and ${\sum }_{N_r,N_y,N_g}Q[N_r,N_y,N_g]=1$, which make sure that $Q$ is a probability distribution. We usually won’t write those out, but one does need to include them when actually calculating $Q$.)

Then we use the Standard Magic Formula for maxent distributions which we’re not going to derive here because this is a concepts post, which says

$P[N_r,N_y,N_g|E[N_r]=25,E[N_y]=50,E[N_g]=5]=\frac{1}{Z}{e}^{{\lambda }_r{N}_r+{\lambda }_y{N}_y+{\lambda }_g{N}_g}$

… where the parameters ${\lambda }_r,{\lambda }_y,{\lambda }_g$ and $Z$ are chosen to match the expected value constraints and make the distribution sum to 1. (In this case, David's numerical check finds Z $\approx$ 17465.2, ${\lambda }_r\approx -0.0349,{\lambda }_y\approx 0.0006,{\lambda }_g\approx -0.1823$)

Some Special Cases To Check Our Intuition

We have a somewhat-handwavy story for why it makes sense to use this maxent machinery: the more information we expect to gain by observing a variable, the less we implicitly assume we already know about it. So, maximize expected information gain (i.e. minimize implicitly-assumed knowledge) subject to the constraints of whatever information we do think we know.

But to build confidence in that intuitive story, we should check that it does sane things in cases we already understand.

“No Information”

First, what does the maxent construction do when we don’t pass in any constraints? I.e. we don’t think we know anything relevant?

Well, it just gives the distribution with largest entropy over the outcomes, which turns out to be a uniform distribution. So in the case of our widgets problem, the maximum entropy construction with no constraints gives the same prior we specified up front, uniform over all outcomes.

Furthermore: what if the expected number of yellow orders, $N_y$, were 49.5 - the same as under the prior - and we only use that constraint? Conceptually, that constraint by itself would not add any information not already implied by the prior. And indeed, the maxent distribution would be the same as the trivial case: uniform.

Bayes Updates

Now for a more interesting class of special cases. Suppose, as earlier, that Mr A gets a call from the sales department saying “We have at least 40 orders for green widgets today!” - i.e. $N_g\ge 40$. This is a case where Mr A can use Bayes’ Rule, as we all know and love. But he could use a maxent update instead… and if he does so, he’ll get the same answer as Bayes’ Rule.

Here’s how.

Let’s think about the variable $I[N_g\ge 40]$ - i.e. it’s 1 if there are 40 or more green orders, 0 otherwise. What does it mean if I claim $E\left[I\right[N_g\ge 40\left]\right]=1$? Well, that expectation is 1 if and only if all of the probability mass is on $N_g\ge 4$. In other words, $E\left[I\right[N_g\ge 40\left]\right]=1$ is synonymous with $N_g\ge 4$ (under the distribution).

So what happens when we find the maxent distribution subject to $E\left[I\right[N_g\ge 40\left]\right]=1$? Well, the Standard Magic Formula says

$P[N_r,N_y,N_g|E[I[N_g\ge 40]]=1]=\frac{1}{Z}{e}^{\lambda I[N_g\ge 40]]}$

… where $Z$ and $\lambda$ are chosen to satisfy the constraints. In this case, we’ll need to take $\lambda$ to be (positive) infinitely large, and $Z$ to normalize it. In that limit, the probability will be 0 on $N_g<40$, and uniform on $N_g\ge 40$ - exactly the same as the Bayes update.

This generalizes: the same construction, with the expectation of an indicator function, can always be used in the maxent framework to get the same answer as a Bayes update on a uniform distribution.

… but uniform distributions aren’t always the right starting point, which brings us to the next key piece.

Relative Entropy and Priors

Our trick above to replicate a Bayes update using maximum entropy machinery only works insofar as the prior is uniform. And that points to a more general problem with this whole maxent approach: intuitively, it doesn’t seem like a uniform prior should always be my “assume as little as possible” starting point.

A toy example of the sort of problem which comes up: suppose two people are studying rolls of the same standard six-sided die. One of them studies extreme outcomes, and only cares whether the die rolls 6 or not, so as a preprocessing step they bin all the rolls into 6 or not-6. The other keeps the raw data on the rolls. Now, if they both use a uniform distribution, they get different distributions: one of them assigns probability ½ to a  roll of 6 (because 6 is one of the two preprocessed outcomes), the other assigns probability ⅙ to a roll of 6. Seems wrong! This maxent machine should have some kind of slot in it where we put in a distribution representing (in this case) how many things we binned together already. Or, more generally, a slot where we put in prior information which we want to take as already known/given, aside from the expectation constraints.

Enter relative entropy, the negative of KL divergence.

Relative entropy can be thought of as entropy relative to a reference distribution, which works like a prior. Intuitively:

• Entropy $-{\sum }_{X}P\left[X\right]logP\left[X\right]$ answers “Under distribution $P$, how many bits of information do I expect to gain by observing $X$?”
• KL divergence ${\sum }_{X}P\left[X\right]log\frac{P\left[X\right]}{Q\left[X\right]}$ answers “Under distribution $P$, how many fewer bits of information will I gain by observing $X$, compared to the number of bits gained by someone who believed distribution $Q$?”. Someone who believed $Q$ would start out believing wrong things (according to distribution $P$), so $P$ generally expects such a person to gain more information (or at least no less) from observation - i.e. KL divergence is nonnegative.
• Relative entropy is the negative of KL divergence, so it answers “Under distribution $P$, how many more bits of information will I gain by observing $X$, compared to the number of bits gained by someone who believed distribution $Q$?”. By maximizing this, we assume as little information as possible beyond the information already built into $Q$.

In most cases, rather than maximizing entropy, it makes more sense to maximize relative entropy - i.e. minimize KL divergence - relative to some prior $Q$. (In the case of continuous variables, using relative entropy rather than entropy is an absolute necessity, for reasons we won’t get into here.)

The upshot: if we try to mimic a Bayes update in the maxent framework just like we did earlier, but we maximize entropy relative to a prior, we get the same result as a Bayes update - without needing to assume a uniform prior. Mathematically: let

$P^{\ast }[N_r,N_y,N_g|E[I[N_g\ge 40]]=1]=$

${\text{argmin}}_R{D}_{KL}\left(R\right[N_r,N_y,N_g\left]||P\right[N_r,N_y,N_g\left]\right)$

$\text{subject to}{E}_R\left[I\right[N_g\ge 40\left]\right]=1.$

That optimization problem will spit out the standard Bayes-updated distribution

$P^{\ast }[N_r,N_y,N_g|E[I[N_g\ge 40]]=1]=P[N_r,N_y,N_g|N_g\ge 40]$.

… and that is the last big piece in how we think of maxent machinery as a generalization of Bayes updates.

Recap

The key pieces to remember are:

• When updating via maxent, we maximize entropy relative to a prior (i.e. minimize KL divergence from the prior) subject to some constraints which encode our information.
• We do this because, intuitively, we want a distribution which assumes as little as possible beyond the prior and the information encoded in the constraints.
• The maxent update procedure can handle kinds of information which aren’t even the right type for Bayes’ Rule.

… but in the cases which can be handled by Bayes’ Rule, updating via maxent yields the same answer.

1. ^{^}

   You can find Jaynes’ original problem starting on page 440 of Probability Theory: The Logic Of Science. The version I present here is similar but not identical; I have modified it to remove conceptual distractions about unnormalizable priors and to get the point of this post faster.

2. ^{^}

   $I[\cdot ]$ is the indicator function; it’s 1 if its inputs are true and 0 if its inputs are false.