Optimal predictors and propositional calculus

[Vanessa Kosoy]

This is a writeup of the stuff Benja and I thought up during the logical uncertainty workshop in May.

An optimal predictor for $(D,\mu )$ allows assigning probabilities to logical sentences of the form $x\in D$ but in general it doesn’t allow assigning probabilities to propositional formulae constructed from sentences of that form. Here we outline two approaches to defining such probabilities.

Consider $D$ a language. Define $B_D\subseteq \{0,1{\}}^{\ast }$ to be the set of words encoding propositional formulae whose variables are labeled by elements of $\{0,1{\}}^{\ast }$ such that the formula evaluates to truth if a variable labeled by $x$ is substituted for the truth value of $x\in D$. We can think of $B_D$ as consisting of expressions like $\lceil 0110\in D\rceil \wedge \neg \lceil 101\in D\rceil$ which represent true sentences.

Consider $\mu$ a word ensemble and suppose $P$ is an optimal predictor for $(D,\mu )$. It would be nice to show $P$ satisfies something like the “coherence condition”

$$P^k\left(\varphi \right)=P^k(\varphi \wedge \psi )+P(\varphi \wedge \neg \psi )$$

Obviously we cannot expect the exact equality since $P$ is only defined up to similarity relative to $\mu$. Instead, we were able to show that under certain assumptions on $\mu$, we have that $\left(P^k\right(\varphi )-P^k(\varphi \wedge \psi )-P(\varphi \wedge \neg \psi ){)}^2$ is “negligible on average” in some sense.

To see this define the languages

$$D_{+}=\left\{\right(\varphi ,\psi )\mid \varphi \wedge \psi \in B_D\}$$ $$D_{-}=\left\{\right(\varphi ,\psi )\mid \varphi \wedge \neg \psi \in B_D\}$$ $$D_0=\left\{\right(\varphi ,\psi )\mid \varphi \in B_D\}$$

All three languages have reductions to $B_D$:

$$f_{+}(\varphi ,\psi ):=\varphi \wedge \psi$$ $$f_{-}(\varphi ,\psi ):=\varphi \wedge \neg \psi$$ $$f_0(\varphi ,\psi ):=\varphi$$

Assume a word ensemble $\nu$ exists s.t. $f_{+}$, $f_{-}$ and $f_0$ are pseudo-invertible reductions of $(D_{+},\nu )$, $(D_{-},\nu )$ and $(D_0,\nu )$ to $(B_D,\mu )$. Then by Theorem 6.1 of [1], $f_{+}^{-1}\left(P\right)$ is an optimal predictor for $(D_{+},\nu )$, $f_{-}^{-1}\left(P\right)$ is an optimal predictor for $(D_{-},\nu )$ and $f_0^{-1}\left(P\right)$ is an optimal predictor for $(D_0,\nu )$. Since $D_0=D_{+}\bigsqcup D_{-}$, Theorems 5.1 and 4.2 imply that $f_0^{-1}\left(P\right)\stackrel{\nu }{\sim }{f}_{+}^{-1}\left(P\right)+f_{-}^{-1}\left(P\right)$. That is, $E_{{\nu }^k}\left[\right(P^k\left(\varphi \right)-P^k(\varphi \wedge \psi )-P(\varphi \wedge \neg \psi ){)}^2]$ is negligible.

Another approach is considering a language $D$ equipped with a binary operation $m:\{0,1{\}}^{\ast }\times \{0,1{\}}^{\ast }\to \{0,1{\}}^{\ast }$ such that ${\chi }_D\left(m\right(x,y\left)\right)={\chi }_D\left(x\right){\chi }_D\left(y\right)$. If $\mu$ is a word ensemble and $P$ is an optimal predictor for $(D,\mu )$ then $P^k\left(m\right(x,y\left)\right)$ can be interpreted as the probability of $\lceil x\in D\rceil \wedge \lceil y\in D\rceil$. The probability of $\lceil x\in D\rceil \wedge \neg \lceil y\in D\rceil$ can be taken to be $\eta \left(P^k\right(m(x,y))-P^k(y\left)\right)$. Continuing in this manner, it is possible to assign probabilities to all propositional formulae of the sort.

In this case, the coherence condition would hold automatically except for the presence of $\eta$. Define

$$D_{+}=\left\{\right(x,y)\mid m(x,y)\in D\}$$ $$D_0=\left\{\right(x,y)\mid x\in D\}$$

We can now apply the same method as above combined with Lemma 4.3 ($D_{+}\subseteq D_0$) to show approximate coherence.

It would be interesting to construct concrete examples in which these results are applicable.

[1] “A complexity theoretic approach to logical uncertainty (Draft)”