Logical counterfactuals using optimal predictor schemes

post by Vanessa Kosoy (vanessa-kosoy) · 2015-10-04T19:48:23.000Z · LW · GW · 0 comments

Contents

  Definition
  Theorem
  Note
  Proof of Theorem
None
No comments

We give a sufficient condition for a logical conditional expectation value defined using an optimal predictor scheme to be stable on counterfactual conditions.

Definition

Given $\Delta$ an error space of rank $r$, the stabilizer of $\Delta$, denoted $\mathrm{stab}\Delta$ is the set of functions $\gamma :N^r\to R^{>0}$ s.t. for any $\delta \in \Delta$ we have $\gamma \delta \in \Delta$.

Theorem

Consider $\Delta$ an error space of rank 2, $D\subseteq \{0,1{\}}^{\ast }$, $\mu$ a word ensemble and ${\hat{P}}_D$ a $\Delta (poly,log)$-optimal predictor scheme for $({\chi }_D,\mu )$. Assume $ϵ:N^2\to R^{>0}$ is s.t.

(i) ${ϵ}^{-1}\in \mathrm{stab}\Delta$

(ii) ${\hat{P}}_D^{kj}\ge ϵ(k,j)$

Consider $f:D\cap \mathrm{supp}\mu \to [0,1]$ and ${\hat{P}}_1$, ${\hat{P}}_2$ $\Delta (poly,log)$-optimal predictor schemes for $(f,\mu \mid D)$. Then, ${\hat{P}}_1\underset{\Delta }{\stackrel{\mu }{\simeq }}{\hat{P}}_2$.

Note

This result can be interpreted as stability on counterfactual conditions since the similarity is relative to $\mu$ rather than only relative to $\mu \mid D$. That is, ${\hat{P}}_1$ and ${\hat{P}}_2$ are similar outside of $D$ as well.

Proof of Theorem

We will refer to the previously established results about $\Delta (poly,log)$-optimal predictor schemes by L.N where N is the number in the linked post. Thus Theorem 1 there becomes Theorem L.1 here and so on.

By Theorem L.A.7

$$E_{({\mu }^k\mid D)\times U^{r_1(k,j)+r_2(k,j)}}\left[\right({\hat{P}}_1^{kj}\left(x\right)-{\hat{P}}_2^{kj}\left(x\right){)}^2]\in \Delta$$

$$\frac{E_{{\mu }^k\times U^{r_1(k,j)+r_2(k,j)}}\left[{\chi }_D\right(x\left)\right({\hat{P}}_1^{kj}\left(x\right)-{\hat{P}}_2^{kj}\left(x\right){)}^2]}{{\mu }^k\left(D\right)}\in \Delta$$

$$E_{{\mu }^k\times U^{r_1(k,j)+r_2(k,j)}}\left[{\chi }_D\right(x\left)\right({\hat{P}}_1^{kj}\left(x\right)-{\hat{P}}_2^{kj}\left(x\right){)}^2]\in \Delta$$

On the other hand, by Lemma L.B.3

$$E_{{\mu }^k\times U^{r(k,j)+r_1(k,j)+r_2(k,j)}}\left[\right({\hat{P}}_D^{kj}\left(x\right)-{\chi }_D\left(x\right)\left)\right({\hat{P}}_1^{kj}\left(x\right)-{\hat{P}}_2^{kj}\left(x\right){)}^2]\in \Delta$$

Combining the last two statements we conclude that

$$E_{{\mu }^k\times U^{r(k,j)+r_1(k,j)+r_2(k,j)}}\left[{\hat{P}}_D^{kj}\right(x\left)\right({\hat{P}}_1^{kj}\left(x\right)-{\hat{P}}_2^{kj}\left(x\right){)}^2]\in \Delta$$

It follows that

$$E_{{\mu }^k\times U^{r_1(k,j)+r_2(k,j)}}\left[\right({\hat{P}}_1^{kj}\left(x\right)-{\hat{P}}_2^{kj}\left(x\right){)}^2]=ϵ(k,j{)}^{-1}{E}_{{\mu }^k\times U^{r_1(k,j)+r_2(k,j)}}\left[ϵ\right(k,j\left)\right({\hat{P}}_1^{kj}\left(x\right)-{\hat{P}}_2^{kj}\left(x\right){)}^2]$$

$$E_{{\mu }^k\times U^{r_1(k,j)+r_2(k,j)}}\left[\right({\hat{P}}_1^{kj}\left(x\right)-{\hat{P}}_2^{kj}\left(x\right){)}^2]\le ϵ(k,j{)}^{-1}{E}_{{\mu }^k\times U^{r(k,j)+r_1(k,j)+r_2(k,j)}}\left[{\hat{P}}_D^{kj}\right(x\left)\right({\hat{P}}_1^{kj}\left(x\right)-{\hat{P}}_2^{kj}\left(x\right){)}^2]$$

$$E_{{\mu }^k\times U^{r_1(k,j)+r_2(k,j)}}\left[\right({\hat{P}}_1^{kj}\left(x\right)-{\hat{P}}_2^{kj}\left(x\right){)}^2]\in \Delta$$

0 comments

Comments sorted by top scores.