Asymptotic Logical Uncertainty: Uniform Coherence

Scott Garrabrant

6 Asymptotic Logical Uncertainty: Uniform Coherence

by Scott Garrabrant

14th Aug 2015

AI Alignment Forum

2 min read

4

6 Ω 4

EDIT: This post is out of date, the new, better definition is here.

This post is part of the Asymptotic Logical Uncertainty series. Here, I give a concrete proposal for a definition of Uniform Coherence, as mentioned here.

This is only a proposal for a definition. It may be that this definition is bad, and we would rather replace it with something else

Let $M$ be a Turing machine which on input $N$ runs for some amount of time $R (N)$ then outputs a probability, representing the probability assigned to $ϕ_{N}$ .

In the following definition, we fix a function $T (N)$ (e.g. $2^{N}$ ). We say that a sequence ${s_{n}}$ is quickly computable if it is an increasing sequence and there exists a Turing machine which determines whether or not an input $N$ is of the form $s_{n}$ in time $T (N)$ .

We say that $M$ is Uniformly Coherent if

${lim}_{n \to \infty} M (┌ (\neg \neg)^{n} ⊥ ┐) = 0$
If ${s_{n}}$ is quickly computable and $P A ⊢ ϕ_{s_{n}} \to ϕ_{s_{n + 1}}$ for all $n$ , then ${lim}_{n \to \infty} M (s_{n})$ exists.
If ${q_{n}}$ , ${r_{n}}$ , and ${s_{n}}$ are quickly computable and $P A ⊢ (ϕ_{q_{i}} \lor ϕ_{r_{n}} \lor ϕ_{r_{n}}) \land \neg (ϕ_{q_{n}} \land ϕ_{r_{n}}) \land \neg (ϕ_{q_{n}} \land ϕ_{s_{n}}) \land \neg (ϕ_{r_{n}} \land ϕ_{s_{n}})$ for all $n$ , then ${lim}_{n \to \infty} M (q_{n}) + M (r_{n}) + M (s_{n}) = 1$

Open Question 1: Does there exist a uniformly coherent logical predictor $M$ ?

Open Question 2: Does there exist a uniformly coherent logical predictor $M$ which also passes the Generalized Benford Test? (Here, we mean the generalization of the Benford Test to all irreducible patterns)

Theroem: If $M$ is uniformly coherent, then if we define $P (ϕ) = {lim}_{n \to \infty} M (┌ (\neg \neg)^{n} ϕ ┐)$ , then $P (ϕ)$ is defined for all $ϕ$ and is a computably approximable coherent probability assignment. (see here for definitions.)

Proof: Computable approximability is clear. For coherence, it suffices to show that $P (ϕ)$ is well defined, $P (ϕ) = 1$ for provable $ϕ$ , $P (ϕ) = 0$ for disprovable $ϕ$ , and $P (ϕ \land ψ) + P (ϕ \land \neg ψ) = P (ϕ)$ .

The fact that $P (ϕ)$ is well defined comes from applying 2 to the sequence $s_{n} = ┌ (\neg \neg)^{n} ϕ ┐$ .

The fact that $P (ϕ) = 1$ for provable $ϕ$ , comes from applying 3 to $q_{n} = ┌ (\neg \neg)^{n} ⊥ ┐$ , $r_{n} = ┌ (\neg \neg)^{n} ⊥ ┐$ , and $s_{n} = ┌ (\neg \neg)^{n} ϕ ┐$ . The fact that $P (ϕ) = 0$ for disprovable $ϕ$ , comes from applying 3 to $q_{n} = ┌ (\neg \neg)^{n} ⊥ ┐$ , $r_{n} = ┌ (\neg \neg)^{n} ⊤ ┐$ , and $s_{n} = ┌ (\neg \neg)^{n} ϕ ┐$ , since we already know that $P (⊤) = 1$ .

The fact that $P (ϕ \land ψ) + P (ϕ \land \neg ψ) = P (ϕ)$ comes from applying 3 to $q_{n} = ┌ (\neg \neg)^{n} ϕ \land ψ ┐$ , $r_{n} = ┌ (\neg \neg)^{n} ϕ \land \neg ψ ┐$ , and $s_{n} = ┌ (\neg \neg)^{n} \neg ϕ ┐,$ then applying 3 again to $q_{n} = ┌ (\neg \neg)^{n} ⊥ ┐$ , $r_{n} = ┌ (\neg \neg)^{n} ϕ ┐$ , and $s_{n} = ┌ (\neg \neg)^{n} \neg ϕ ┐,$ to get that $P (ϕ \land ψ) + P (ϕ \land \neg ψ) + P (ϕ) = 1 = P (ϕ) + P (ϕ)$ . $□$

Uniform Coherence is however much stronger than coherence. To see an example, consider an infinite sequence of sentences $ϕ_{s_{n}} =$ "PA is consistent on proofs of length up to $n$ ." Uniform coherence can be shown to imply that ${lim}_{n \to \infty} M (s_{n}) = 1$ . (Each of the sentences is provable, so you can apply 3 to this sequence and a pair of $┌ (\neg \neg)^{n} ⊥ ┐$ sequences.)

Theorem: If we take a quickly computable sequence of mutually exclusive sentences, ${ϕ_{s_{n}}}$ , then if $M$ is uniformly coherent, we have ${lim}_{n \to \infty} M (s_{n}) = 0$ .

Proof: Let $ϕ_{r_{n}}$ be the disjunction of all the $ϕ_{s_{i}}$ for $i < n$ . Let $ϕ_{q_{n}} = \neg ϕ_{r_{n + 1}}$ . By 2, ${lim}_{n \to \infty} M (q_{n})$ converges to some $p$ . Applying 3 to ${q_{n}}$ , ${r_{n + 1}}$ and ${┌ (\neg \neg)^{n} ⊥ ┐}$ shows that ${lim}_{n \to \infty} M (r_{n})$ converges to $1 - p$ . Therefore, applying 3 to ${q_{n}}$ , ${r_{n}}$ , and ${s_{n}}$ shows that ${lim}_{n \to \infty} M (s_{n})$ converges to 0.(Note that I assumed here that $T$ was reasonable enough that $q_{n}$ and $r_{n}$ ane also quickly computable) $□$

Personal Blog

6 Ω 4

New Comment

4 comments, sorted by

top scoring

Click to highlight new comments since: Today at 5:18 AM

[-]abramdemski11yΩ110

This notion, by the argument you give before the final theorem, implies belief (with probability 1) in all true $Π_{1}$ sentences -- therefore it must disbelieve true $Π_{2}$ sentences. This is quite intriguing, but likely means it's not quite what we want.

If uniformly coherent predictors exist, their self-referential knowledge would obey Paul Christiano's reflection principle (which follows directly from believing true $Π_{1}$ sentences).

Reply

[-]Scott Garrabrant11yΩ230

It does not imply belief in all true $Π_{1}$ sentences. If $f (x)$ is true for all $x$ , the probability of $f (x)$ will go to 1 as $x$ goes to infinity, but the probability of $(\neg \neg)^{n} \forall x f (x)$ may stay bounded away from 1.

Reply

[-]abramdemski11yΩ110

Ahh, right. Silly mistake.

So the difference in this example is that a coherent prior with approximation $P_{t} (n)$ can have $l i m_{t} P_{t} (ϕ_{s_{n}}) \to 1$ for all $n$ , but not have $l i m_{t} P_{t} (ϕ_{s_{t}}) \to 1$ ; uniformly coherent must have this. To be precise, if we set $P_{t} (ϕ) := M (┌ (\neg \neg)^{t} ϕ ┐)$ with $M$ uniformly coherent, we must have this.