Maximize Worst Case Bayes Score

[Scott Garrabrant]

This post has mostly been copied from something I posted on Less Wrong over a year ago. I am reposting it here, because I want to reference it in a future post related to the two-update problem. Here, I propose an logical prior. I do not think this prior is nearly as good as the modified Demski prior, or even the original Demski prior, but I am posting it has some interesting properties.

Given a consistent but incomplete theory, how should one choose a random model of that theory?

My proposal is rather simple. Just assign probabilities to sentences in such that if an adversary were to choose a model, your Worst Case Bayes Score is maximized. This assignment of probabilities represents a probability distribution on models, and choose randomly from this distribution. However, it will take some work to show that what I just described even makes sense. We need to show that Worst Case Bayes Score can be maximized, that such a maximum is unique, and that this assignment of probabilities to sentences represents an actual probability distribution. This post gives the necessary definitions, and proves these three facts.

Finally, I will show that any given probability assignment is coherent if and only if it is impossible to change the probability assignment in a way that simultaneously improves the Bayes Score by an amount bounded away from 0 in all models. This is nice because it gives us a measure of how far a probability assignment is from being coherent. Namely, we can define the “incoherence” of a probability assignment to be the supremum amount by which you can simultaneously improve the Bayes Score in all models. This could be a useful notion since we usually cannot compute a coherent probability assignment so in practice we need to work with incoherent probability assignments which approach a coherent one.

Now, let’s move on to the formal definitions and proofs.

Fix some language $L$, for example the language of first order set theory. Fix a consistent theory $T$ of $L$, for example ZFC. Fix a nowhere zero probability measure $\mu$ on $L$, for example $\mu \left(\varphi \right)=2^{-\ell \left(\varphi \right)}$, where $\ell \left(\varphi \right)$ is the number of bits necessary to encode $\varphi$.

A probability assignment of $L$ is any function from $L$ to the interval $[0,1]$. Note that this can be any function, and does not have to represent a probability distribution. Given a probability assignment $P$ of $L$, and a model $M$ of $T$, we can define the Bayes Score of $P$ with respect to $M$ by

$$\text{Bayes}(M,P)=\sum _{M\models \varphi }{\log }_2\left(P\right(\varphi \left)\right)\mu \left(\varphi \right)+\sum _{M\models \neg \varphi }{\log }_2(1-P(\varphi \left)\right)\mu \left(\varphi \right).$$

We define the Worst Case Bayes Score $\text{WCB}\left(P\right)$ to be the infimum of $\text{Bayes}(M,P)$ over all models $M$ of $T$. Let $P$ denote the probability assignment that maximizes the function $\text{WCB}$. We will show that this maximum exists and is unique, so $P$ is well defined.

In fact, $P$ is also coherent, meaning that there exists a probability distribution on the set of all models of $T$ such that $P\left(\varphi \right)$ is exactly the probability that a randomly chosen model satisfies $\varphi$. Since the natural definition of a measurable subset of models comes from unions and intersections of the sets of all models satisfying a given sentence, we can think of $P$ as an actual probability distribution on the set of all models of $T$.

First, we must show that there exists a probability assignment $P$ which maximizes $\text{WCB}$.

Note that $\text{Bayes}(M,P)$ either diverges to $-\infty$, or converges to a non-positive real number. If $P$ is the identically $1/2$ function, then $\text{WCB}\left(P\right)=-1$, so there is at least one $P$ for which $\text{WCB}\left(P\right)$ is finite. This means that when maximizing $\text{WCB}\left(P\right)$, we need only consider $P$ for which $\text{Bayes}(M,P)$ converges to a number between $-1$ and $0$ for all $M$.

Assume by way of contradiction that there is no $P$ which maximizes $\text{WCB}$. Then there must be some supremum value $m$ such that $\text{WCB}$ can get arbitrarily close to $m$, but never equals or surpasses $m$. Consider an infinite sequence probability assignments $\left\{P_i\right\}$ such that $\text{WCB}\left(P_i\right)\to m$. We may take a subsequence of $\left\{P_i\right\}$ in order to assume that $\left\{P_i\right(\varphi \left)\right\}$ converges for every sentence $\varphi$. Let $P$ be such that $P_i\left(\varphi \right)\to P\left(\varphi \right)$ for all $\varphi$.

By assumption, $\text{WCB}\left(P\right)$ must be less than $m$. Take any model $M$ for which $\text{Bayes}(M,P)<m$. Then there exists a finite subset $S$ of $L$ such that ${\text{Bayes}}_S(M,P)<m$, where

$${\text{Bayes}}_S(M,P)=\sum _{\varphi \in S,M\models \varphi }{\log }_2\left(P\right(\varphi \left)\right)\mu \left(\varphi \right)+\sum _{\varphi \in S,M\models \neg \varphi }{\log }_2(1-P(\varphi \left)\right)\mu \left(\varphi \right).$$

Note that in order to keep the Bayes score at least $-1$, any $P_i$ must satisfy $2^{-1/\mu \left(\varphi \right)}\le P_i\left(\varphi \right)\le 1$ if $M\models \varphi$, and $0\le P_i\left(\varphi \right)\le 1-2^{-1/\mu \left(\varphi \right)}$ if $M\models \neg \varphi$. Consider the space of all functions $f$ from $S$ to $[0,1]$ satisfying these inequalities. Since there are only finitely many values restricted to closed and bounded intervals, this space is compact. Further, ${\text{Bayes}}_S(M,f)$ is a continuous function of $f$, defined everywhere on this compact set. Therefore,

$$\underset{i\to \infty }{lim}{\text{Bayes}}_S(M,P_i)={\text{Bayes}}_S(M,P)<m.$$

However, clearly $\text{WCB}\left(P_i\right)\le \text{Bayes}(M,P_i)\le {\text{Bayes}}_S(M,P_i)$, so

$$\underset{i\to \infty }{lim}\text{WCB}\left(P_i\right)<m,$$

contradicting our assumption that $\text{WCB}\left(P_i\right)$ converges to $m$.

Next, we will show that there is a unique probability assignment which maximizes $\text{WCB}$. Assume by way of contradiction that there were two probability assignments, $P_1$ and $P_2$ which maximize $\text{WCB}$. Consider the probability assignment $P_3$, given by

$$P_3\left(\varphi \right)=\frac{\sqrt{P_1\left(\varphi \right)P_2\left(\varphi \right)}}{\sqrt{P_1\left(\varphi \right)P_2\left(\varphi \right)}+\sqrt{(1-P_1(\varphi \left)\right)(1-P_2(\varphi \left)\right)}}.$$

It is quick to check that this definition satisfies both

$${\log }_2\left(P_3\right(\varphi \left)\right)\ge \frac{{\log }_2\left(P_1\right(\varphi \left)\right)+{\log }_2\left(P_2\right(\varphi \left)\right)}{2}$$

and

$${\log }_2(1-P_3(\varphi \left)\right)\ge \frac{{\log }_2(1-P_1(\varphi \left)\right)+{\log }_2(1-P_2(\varphi \left)\right)}{2},$$

and in both cases equality holds only when $P_1\left(\varphi \right)=P_2\left(\varphi \right).$

Therefore, we get that for any fixed model, $M$,

$$\text{Bayes}(M,P_3(\varphi \left)\right)\ge \frac{\text{Bayes}(M,P_1(\varphi \left)\right)+\text{Bayes}(M,P_2(\varphi \left)\right)}{2}.$$

By looking at the improvement coming from a single sentence $\varphi$ with $P_1\left(\varphi \right)\ne P_2\left(\varphi \right),$ we see that

$$\text{Bayes}(M,P_3(\varphi \left)\right)-\frac{\text{Bayes}(M,P_1(\varphi \left)\right)+\text{Bayes}(M,P_2(\varphi \left)\right)}{2},$$

is actually bounded away from $0$, which means that

$$\text{WCB}\left(P_3\right(\varphi \left)\right)\ge \frac{\text{WCB}\left(P_1\right(\varphi \left)\right)+\text{WCB}\left(P_2\right(\varphi \left)\right)}{2},$$

which contradicts the fact that $P_1$ and $P_2$ maximize $\text{WCB}$.

This means that there is a unique probability assignment, $P$, which maximizes $\text{WCB}$, but we still need to show that $P$ is coherent. For this, we will use the fact that $P$ is coherent if and only if $P$ assigns probability 0 to every contradiction, probability 1 to every tautology, and satisfies $P\left(\varphi \right)=P(\varphi \wedge \psi )+P(\varphi \wedge \neg \psi )$ for all $\varphi$ and $\psi$.

Clearly $P$ assigns probability 0 to every contradiction, since otherwise we could increase the Bayes Score in all models by the same amount by updating that probability to 0. Similarly $P$ clearly assigns probability 1 to all tautologies.

If $P\left(\varphi \right)\ne P(\varphi \wedge \psi )+P(\varphi \wedge \neg \psi )$, then we update all three probabilities as follows:

$$P\left(\varphi \right)\mapsto \frac{1}{1+\frac{1-P\left(\varphi \right)}{P\left(\varphi \right)}\left(2^{-x/\mu \left(\varphi \right)}\right)},$$

$$P(\varphi \wedge \psi )\mapsto \frac{1}{1+\frac{1-P(\varphi \wedge \psi )}{P(\varphi \wedge \psi )}\left(2^{x/\mu (\varphi \wedge \psi )}\right)},$$

and

$$P(\varphi \wedge \neg \psi )\mapsto \frac{1}{1+\frac{1-P(\varphi \wedge \neg \psi )}{P(\varphi \wedge \neg \psi )}\left(2^{x/\mu (\varphi \wedge \neg \psi )}\right)},$$

where $x$ is the unique real number such that the three new probabilities satisfy $P\left(\varphi \right)=P(\varphi \wedge \psi )+P(\varphi \wedge \neg \psi )$. This correction increases Bayes Score by the same amount in all models, and therefore increase $\text{WCB}$, contradicting the maximality of $\text{WCB}\left(P\right)$. Therefore $P$ is coherent as desired.

Finally, we show that any given probability assignment $P$ is coherent if and only if it is impossible to simultaneously improve the Bayes Score by an amount bounded away from 0 in all models. The above proof that $P$ is coherent actually shows one direction of this proof, since the only fact it used about $P$ is that you could not simultaneously improve the Bayes Score by an amount bounded away from 0 in all models. For the other direction, assume by way of contradiction that $P$ is coherent, and that there exists a $Q$ and an $ϵ>0$ such that $\text{Bayes}(M,Q)-\text{Bayes}(M,P)>ϵ$ for all $M$.

In particular, since $P$. is coherent, it represents a probability distribution on models, so we can choose a random model $M$ from the distribution $P$. If we do so, we must have that

$$E\left(\text{Bayes}\right(M,Q\left)\right)-E\left(\text{Bayes}\right(M,P\left)\right)>0.$$

However, this contradicts the well known fact that the expectation of Bayes Score is maximized by choosing honest probabilities corresponding the actual distribution $M$ is chosen from.

Coming up, I will present a list of open problems related to this prior.