 Strict Dominance for the Modified Demski Prior
post by Abram Demski 1329 days ago | Sam Eisenstat, Jessica Taylor, Patrick LaVictoire and Scott Garrabrant like this | 1 comment

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 $$\mathbb{P} (\phi)$$ as in this post, but with $$\phi$$ in the language of PA plus one additional predicate, $$B(n)$$, 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(b)$$ is defined as: $\Sigma_{p: U(p)=b^*} 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 $$\mathbb{P}$$ via encoding such sequences into logic as conjunctions of $$B(n)$$ and $$\neg B(n)$$.

Definition 1. Consider two probability distributions $$f$$ and $$g$$ defined on the same $$\sigma$$-algebra $$\Sigma$$. $$f$$ dominates $$g$$ iff $$\exists \alpha \in \mathbb{R}$$ such that $$\forall x \in \Sigma$$ we have $$\alpha f(x) \geq g(x)$$. 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(n)$$ or $$\neg B(n)$$ 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(b)$$. $$\Box$$

Theorem 2. The dominance from Theorem 1 is strict.

Proof. A hypothesis with positive probability in $$\mathbb{P}$$ is to encode a truth predicate for $$PA$$ in $$B(n)$$, as follows. Let $$\ulcorner \phi \urcorner$$ be the Goedel-number of sentences $$\phi$$ in the language of $$PA$$. We assert the T-schema, $$\phi \leftrightarrow B(\ulcorner \phi \urcorner)$$, for each $$\phi$$ in the language of $$PA$$. (We do not assert this for the sentences including the predicate $$B()$$.) 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. $$\Box$$

# 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()$$ to $$PA$$. What’s more interesting for logical uncertainty is predicting a sentence $$\phi(n)$$ which is already definable in $$PA$$. Two informal conjectures:

Informal conjecture 1. “Natural” approximations of the modified Demski prior on $$PA$$ fail to approximate $$\phi$$ at level 1 logical uncertainty (where $$\phi(n)$$ 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 $$\phi(n)$$ 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.  by Sam Eisenstat 1327 days ago | Abram Demski and Patrick LaVictoire like this | link [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 \mathbb{R}$$ such that for any binary string $$x$$, we have $$\alpha P(x) \ge Q(x)$$. 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(x) \ge Q(x)$$ holds for all binary strings $$x$$ iff it holds for all $$x \in \Sigma$$. Proof. The direction $$\Longleftarrow$$ is immediate. For $$\Longrightarrow$$, suppose that $$\alpha P(x) \ge Q(x)$$ for all binary string events $$x$$. We first show that this property holds for every event in the algebra $$\mathcal{A}$$ generated by the binary string events. We can write any $$x \in \mathcal{A}$$ as a disjoint union of binary string events $$x = \bigcup_{i=1}^n y_i$$. Then, $\alpha P(x) = \alpha \sum_{i=1}^n P(y_i) \ge \sum_{i=1}^n Q(y_i) = Q(x),$ as desired. We can extend this to the $$\sigma$$-algebra generated by $$\mathcal{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 $$\mathcal{A}$$ and it is preserved by countable monotone unions and intersections, then it holds on every set in the $$\sigma$$-algebra generated by $$\mathcal{A}$$. For countable monotone unions, if we have $$x_1 \subseteq x_2 \subseteq \dots$$, then $\alpha P(\bigcup_{i=1}^\infty x_i) = \sup_i \alpha P(x_i) \ge \sup_i Q(x_i) = Q(\bigcup_i x_i).$ We can do the same thing for countable monotone intersections $$x_1 \supseteq x_2 \supseteq \dots$$; $\alpha P(\bigcap_{i=1}^\infty x_i) = \inf_i \alpha P(x_i) \ge \inf_i Q(x_i) = Q(\bigcap_i x_i).$ $$\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. reply

### NEW DISCUSSION POSTS

[Note: This comment is three
 by Ryan Carey on A brief note on factoring out certain variables | 0 likes

There should be a chat icon
 by Alex Mennen on Meta: IAFF vs LessWrong | 0 likes

Apparently "You must be
 by Jessica Taylor on Meta: IAFF vs LessWrong | 1 like

There is a replacement for
 by Alex Mennen on Meta: IAFF vs LessWrong | 1 like

Regarding the physical
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

I think that we should expect
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

I think I understand your
 by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

This seems like a hack. The
 by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

After thinking some more,
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Yes, I think that we're
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

My intuition is that it must
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

To first approximation, a
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Actually, I *am* including
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Yeah, when I went back and
 by Alex Appel on Optimal and Causal Counterfactual Worlds | 0 likes

> Well, we could give up on
 by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes