User:IssaRice/Logical inductor construction

Notes from the Logical Induction paper as I walk through the construction of LIA in section 5.

Lemma 5.1.1 (Fixed Point Lemma)

"Observe that ${\mathcal {V}}'$ is equal to the natural inclusion of the finite-dimensional cube $[0,1]^{{\mathcal {S}}'}$ in the space of all valuations ${\mathcal {V}}=[0,1]^{\mathcal {S}}$." -- I think what this is saying is that since ${\mathcal {S}}'\subset {\mathcal {S}}$, we can think of $[0,1]^{{\mathcal {S}}'}$ as being sort of a subset of $[0,1]^{\mathcal {S}}$. Except it's not strictly speaking a subset, since the functions in $[0,1]^{{\mathcal {S}}'}$ and $[0,1]^{\mathcal {S}}$ have different domains. How can we make it a subset? The "natural" way to do this is to set everything outside of ${\mathcal {S}}'$ to zero. But that's exactly what ${\mathcal {V}}'=\{\mathbb {V} \in [0,1]^{\mathcal {S}}:\mathbb {V} (\phi )=0{\text{ whenever }}\phi \notin {\mathcal {S}}'\}$ is. One thing I'm still not sure about is the "finite-dimensional" part; doesn't having $[0,1]$ make the cube infinite-dimensional?

Definition of fix: I found it helpful to look at the graph of $f(x)=\max(0,\min(1,x))$; this looks like the identity function in the interval $[0,1]$, but then becomes constant once it hits either of the endpoints. If you've already thought about the definition of continuous threshold indicator (definition 4.3.2), then you will recognize that $f(x)=\mathrm {Ind} _{1}(x>0)$.

"the compact, convex space ${\mathcal {V}}'$" -- this intuitively makes sense, since ${\mathcal {V}}'$ basically "looks like" a cube. But I'm not sure how to verify this.

For the fixed point reasoning: we don't actually have a fixed point of $f$; instead, it's a fixed point of $g$, where $g(x)=f(x+\delta )$ and $\delta =T_{n}(\mathbb {P} _{\leq n-1},\mathbb {V} ^{\text{fix}})[\phi ]$. If $\delta >0$, then the graph of $g$ is just the graph of $f$ but shifted to the left. You will see that this intersects the graph of the identity function at $x=1$; this is the fixed point. On the other hand, if $\delta <0$, then we shift the graph of $f$ to the right, and now the fixed point is at $x=0$.

The following is used in the Fixed Point Lemma (5.1.1):

Writing the $n$-strategy as

$T_{n}=\sum _{j=1}^{k}\xi _{j}\phi _{j}-\sum _{j=1}^{k}\xi _{j}\phi _{j}^{*n}$

we have

$\mathbb {V} (T_{n}(\mathbb {P} _{\leq n-1},\mathbb {V} ))=\sum _{j=1}^{k}\xi _{j}(\mathbb {P} _{\leq n-1},\mathbb {V} )\cdot \mathbb {V} (\phi _{j})-\sum _{j=1}^{k}\xi _{j}(\mathbb {P} _{\leq n-1},\mathbb {V} )\cdot \phi _{j}^{*n}(\mathbb {P} _{\leq n-1},\mathbb {V} )$

But $\phi _{j}^{*n}(\mathbb {P} _{\leq n-1},\mathbb {V} )=\mathbb {V} (\phi _{j})$ so the two sums cancel to obtain $0$.

See also

• https://machinelearning.subwiki.org/wiki/User:IssaRice/Logical_induction_notation