Strict Dominance for the Modified Demski Prior

[abramdemski]

I previously noted that difficulties with the modified Demski prior were less than previously thought: I was failing to distinguish between the two different kinds of update. Here, I analyze more fully what it succeeds at.

---

In order to apply the logical prior to sequence induction, we will add an empirical predicate to it. We define the modified Demski prior $P\left(\varphi \right)$ as in this post, but with $\varphi$ in the language of PA plus one additional predicate, $B\left(n\right)$, which is true or false according to the bits in the bit-sequence we’re trying to predict. We wish to compare this to the universal semimeasure, $M$. For $b$ a finite or infinite binary sequence, $M\left(b\right)$ is defined as: $${\Sigma }_{p:U\left(p\right)=b^{\ast }}{2}^{-|p|}$$ where $U$ is a universal machine, and $p$ is a minimal program such that the output of $U$ is equal to or an extension of $b$. Let $P$ be the probability distribution on binary sequences which results from $P$ via encoding such sequences into logic as conjunctions of $B\left(n\right)$ and $\neg B\left(n\right)$.

Definition 1. Consider two probability distributions $f$ and $g$ defined on the same $\sigma$-algebra $\Sigma$. $f$ dominates $g$ iff $\exists \alpha \in R$ such that $\forall x\in \Sigma$ we have $\alpha f\left(x\right)\ge g\left(x\right)$. The dominance is strict if $g$ does not also dominate $f$.

This is similar to the definition of (multiplicative) dominance in Li & Vitanyi’s An Introduction to Kolmogorov Complexity and Its Applications; however, here we consider $x$ from the entire $\sigma$-algebra where they did not. This matters especially for Theorem 2.

Theorem 1.$P$ is dominant over $M$.

Proof. For a constant complexity penalty $l$, we can encode a sentence-enumerator which simulates feeding random bits to the universal machine used by the universal semimeasure and asserts the sentences $B\left(n\right)$ or $\neg B\left(n\right)$ encoding the bit-sequence output by it. All of these hypotheses will be consistent with $PA$. Therefore, P(b) will be at least $2^{-l}M\left(b\right)$. $\square$

Theorem 2. The dominance from Theorem 1 is strict.

Proof. A hypothesis with positive probability in $P$ is to encode a truth predicate for $PA$ in $B\left(n\right)$, as follows. Let $┌\varphi ┐$ be the Goedel-number of sentences $\varphi$ in the language of $PA$. We assert the T-schema, $\varphi \leftrightarrow B(┌\varphi ┐)$, for each $\varphi$ in the language of $PA$. (We do not assert this for the sentences including the predicate $B\left(\right)$.) This hypothesis forces the binary sequence to encode a complete and consistent extension of $PA$. As a result, $P$ will assign positive probability to this. (Each such extension will have zero measure, but the set of such extensions will have nonzero measure.) $M$ assigns probability zero. No finite-length program can provide a complete and consistent extension of $PA$, by the first incompleteness theorem. Therefore, any positive contribution to the probability must come from infinite-length programs. This is the same as saying that there exists a stochastic Turing machine with a nonzero probability of outputting a complete and consistent extension of $PA$. This is impossible by a result of Antonin Kucera; see here. $\square$

Discussion

The purpose of strict dominance is to show that the hypothesis space of the modified Demski prior is in some sense larger than that of Solomonoff induction, as a result of its ability to employ logic. This comes close to issues like what an agent does if it encounters a halting oracle in the wild. (Not very close, though.)

Defining dominance over the entire $\sigma$-algebra allows us to talk about how $P$ assigns positive measure to a class of sentences no one of which gets nonzero measure individually. An analogy would be the comparison between a distribution $Q$ which assigns a positive probability to all rational numbers between 0 and 1, and the mixture of $Q$ and the uniform distribution between 0 and 1. The 2nd does not assign nonzero probability to any new individual numbers, but assigns nonzero probability to the real numbers as a set while $Q$ does not.

I think this is a very legitimate move, but only found definitions for dominance which quantified over binary strings. It might be possible to prove strict dominance for that type of dominance, but I doubt it; it would require finding a single sequence which has nonzero weight in $P$ and zero weight in $M$.

Compared to my definition, the more standard definition is closer to a notion of bounded regret. For $P$ to dominate $Q$ in the old sense means that its Bayes score can only be some constant worse than $Q$, no worse, regardless of environment. My definition here implies that, but I think it’s a stricter requirement.

This framework applies the modified Demski prior to empirical uncertainty, by adding a new predicate $B\left(\right)$ to $PA$. What’s more interesting for logical uncertainty is predicting a sentence $\varphi \left(n\right)$ which is already definable in $PA$. Two informal conjectures:

Informal conjecture 1. “Natural” approximations of the modified Demski prior on $PA$ fail to approximate $\varphi$ at level 1 logical uncertainty (where $\varphi \left(n\right)$ is computable, and the time bound is enough to compute all previous values before guessing at the current). Allowing programs to guess on only the sentences they’re interested in overly incentivises them to remain silent; this is the problem which is solved by the subsequence induction algorithm (which consequently solves Level 1). Paul Christiano pointed out that this setting is called “sleeping experts” and subsequence induction looks a lot like the standard solution.

Informal conjecture 2. The modified Demski prior can succeed at Level 1 by performing a Bayesian update on things $PA$ can prove, rather than accepting the axioms of $PA$ as axioms. This is because a Bayesian update implements a correct solution to the sleeping experts problem, while the Demski procedure of kicking out inconsistent hypotheses does not. Doing a Bayesian update on our set of hypotheses when we prove a new $\varphi \left(n\right)$ implements something closer to subsequence induction, and so will be able to learn properly (at Level 1 difficulty, that is). This is similar to Christiano’s paradox of ignorance.

[SamEisenstat]

[EDIT: This all deals with measures, not semimeasures; see below.]

For $P$ to dominate $Q$ in the old sense means that its Bayes score can only be some constant worse than $Q$, no worse, regardless of environment. My definition here implies that, but I think it’s a stricter requirement.

Your definition is equivalent to the standard definition. Li and Vitányi say that $P$ dominates $Q$ iff there is some $\alpha \in R$ such that for any binary string $x$, we have $\alpha P\left(x\right)\ge Q\left(x\right)$. Li and Vitányi’s “probability distributions” take a binary string as input while the probability distributions we are using ask for an element of a $\sigma$-algebra, but we can abuse notation by allowing a binary string to represent the event of that the random sequence starts with this string as a prefix.

Theorem. For any probability distributions $P,Q$ on Cantor space and any $\alpha$, the condition $\alpha P\left(x\right)\ge Q\left(x\right)$ holds for all binary strings $x$ iff it holds for all $x\in \Sigma$.

Proof. The direction $⟸$ is immediate. For $⟹$, suppose that $\alpha P\left(x\right)\ge Q\left(x\right)$ for all binary string events $x$. We first show that this property holds for every event in the algebra $A$ generated by the binary string events. We can write any $x\in A$ as a disjoint union of binary string events $x={\bigcup }_{i=1}^n{y}_i$. Then, $$\alpha P\left(x\right)=\alpha \sum _{i=1}^{n}P\left(y_i\right)\ge \sum _{i=1}^{n}Q\left(y_i\right)=Q\left(x\right),$$ as desired.

We can extend this to the $\sigma$-algebra generated by $A$, which is just the Borel $\sigma$-algebra $\Sigma$ on Cantor space, by the monotone class theorem. I’m not sure how much measure theory you know, but you can think of this as a form of induction on measurable sets; if a property holds on an algebra of sets $A$ and it is preserved by countable monotone unions and intersections, then it holds on every set in the $\sigma$-algebra generated by $A$. For countable monotone unions, if we have $x_1\subseteq x_2\subseteq \dots$, then $$\alpha P\left(\bigcup _{i=1}^{\infty }{x}_i\right)=\underset{i}{sup}\alpha P\left(x_i\right)\ge \underset{i}{sup}Q\left(x_i\right)=Q\left(\bigcup _i{x}_i\right).$$ We can do the same thing for countable monotone intersections $x_1\supseteq x_2\supseteq \dots$; $$\alpha P\left(\bigcap _{i=1}^{\infty }{x}_i\right)=\underset{i}{inf}\alpha P\left(x_i\right)\ge \underset{i}{inf}Q\left(x_i\right)=Q\left(\bigcap _i{x}_i\right).$$ $\square$

EDIT: I’m talking about probability distributions $P$ rather than semimeasures. I don’t know how your definition of dominance is helpful for semimeasures though. The universal semimeasure $M$ is defined on binary sequences, and I think that question of whether $P$ dominates $M$ depends on how you extend it to the whole $\sigma$-algebra. I expect that many reasonable extensions of $M$ would satisfy your Theorem 1, but this post (in particular the proof of Theorem 1) doesn’t seem to choose a specific such extension.