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 key property of $\mathbb {V} ^{\text{fix}}$ that we use in the proof:

• If $T_{n}$ buys a share of $\phi$ on day $n$, then the price of $\phi$ on day $n$ is 1 (the maximum possible).
• If $T_{n}$ sells a share of $\phi$ on day $n$, then the price of $\phi$ on day $n$ is 0 (the minimum possible).

One question to ask is, couldn't we just avoid using Brouwer's fixed point theorem by just setting the prices to obey the above property? There are two problems with this. One is that the definition of the $n$th day prices would depend on $T_{n}$'s behavior, which depends on the $n$th day prices! So the definition would be circular. The other problem is that we can't guarantee that the map would be continuous if we just magically set it to obey some property.

Something else I got confused about: I was thinking that the above key property only talks about day $n$. Couldn't the trader make a lot of money on previous days, and then just make no money on day $n$, so that it would still be making lots of money? The answer is that we are only dealing with a trading strategy in this lemma, not a full trader. Later, in lemma 5.1.3, we recursively use this idea to deal with a full trader.

How do we come up with the definition of fix? Here's one way to think about it. Let $x$ be the market price (of some sentence on day $n$) and $\delta$ be the trading volume of that sentence on the same day. We want to return some quantity $f(x,\delta )$ that fixes up the price, after the fact, so that the trader would have earned less money. Ideally we would like to say something like:

$f(x,\delta )={\begin{cases}1&{\text{if }}\delta >0\\x&{\text{if }}\delta =0\\0&{\text{if }}\delta <0\end{cases}}$

This will work, but it's after the fact. We eventually would like to fix the prices in real time. So one way to think about this is to adjust the prices a little at a time, querying the trading strategy each time to see if we should nudge the prices up or down. Here is one idea:

$f(x,\delta )={\begin{cases}x-\epsilon &{\text{if }}\delta >0\\x&{\text{if }}\delta =0\\x+\epsilon &{\text{if }}\delta <0\end{cases}}$

where $\epsilon >0$ is some small adjustment. In other words, if a trader buys at the current price, then nudge it up a little to make it a slightly worse deal for the trader. And if the trader sells at the current price, then nudge it down. Now, there are two problems with this map. As a function of $\delta$, it's still discontinuous (ugly). But more importantly, if we only adjust the prices a little, that means the trader can still make money from us. So what can we do? Well, we can apply the map many times: $f(f(f(f(f(x,\delta ),\delta ),\delta ),\delta ),\delta )$ (actually, maybe we should allow the $\delta$s to change as well, to react in response).

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