Logical inductors [1] are very complex objects, and even their limits are hard to get a handle on. In this post, I investigate the topological properties of the set of all limits of logical inductors.
I’ll use the language of universal inductors [2], but everything I say will also hold for general logical inductors by conditioning. Also, the proofs can be made to apply directly to general logical inductors with relatively few changes.
Universal inductors are measures on Cantor space (i.e. the space 2ω of infinite bit-strings) at every finite time, as well as in the limit (this is a bit nicer than the analogous situation for general logical inductors, which are measures on the space of completions of a theory only in the limit). There are many topologies on spaces of measures, and we can ask about topological properties under any of these. Interestingly, the set of universal inductor limits is dense in the topology of weak convergence, but not in the topology of strong convergence (or, a fortiori, the total variation metric topology).
It’s not immediately clear how to interpret this - should we think of the space of measures as being full of universal inductor limits, or should we think of universal inductor limits as being relatively few, with big holes where none exist? A relatively close analogy is the relationship between computable sets (or limit computable sets for a closer analogy) and arbitrary subsets of N; any subset of N can be approximated pointwise by limit computable sets (indeed, even by finite sets), but may be impossible to approximate under the ℓ1 norm, i.e. the number of differing bits. Now, on with the proofs!
Theorem 1: The set of limits of universal inductors is dense in the topology of weak convergence on the space of measures Δ(2ω).
Proof outline: We need to find a limit of universal inductors in any neighborhood of any measure μ. That is, for any finite collection of continuous functions, we need a universal inductor that, in the limit, assigns expectations to each such function that is close to the expectation under μ.
We do this with a modification of the standard universal inductor construction (section 5 of [1]), adding one additional trader to TradingFirm. This trader can buy and sell shares in events in order to keep these expectations within certain bounds, in a way similar to the Occam traders in the proof of theorem 4.6.4 in [1]. However, we give this trader a much larger budget than the others, allowing its control to be sufficiently tight.
Proof: It suffices to show that for any measure μ on 2ω, any finite set of bounded continuous functions fi:2ω→R for i∈{1,…,n} and any ε>0, there is a universal inductor limit ν such that ∣∣Eμf−Eνf∣∣<ε for all 1≤i≤n.
It's easier to work with prefixes of bit-strings than continuous functions, so we'll pass to such a description. Consider some fi. For each world W∈2ω, there is some clopen set A⊆2ω such that ∣∣fi(W)−fi(˜W)∣∣<ε3 for all ˜W∈A. By compactness, we can pick a finite cover (Ai,j)mij=1. Letting Bi,j=Ai,j∖⋃j−1k=1Ai,k, we get a disjoint open cover. By construction, for each 1≤j≤mi, there is some Wi,j such that for all ˜W∈Bi,j, we have ∣∣fi(Wi,j)−fi(˜W)∣∣<ε3, and we can define a simple function gi that takes the locally constant value fi(Wi,j) on each set Bi,j. Then,
∣∣Eμ(fi)−Eν(fi)∣∣≤∣∣Eμ(fi−gi)∣∣+∣∣Eμ(gi)−Eν(gi)∣∣+|Eν(gi−fi)|≤∣∣Eμ(gi)−Eν(gi)∣∣+23ε,
so we need only control what our universal inductor limit ν thinks of the clopen sets Bi,j.
Pass to a single disjoint cover (Ck)pk=1 of 2ω by clopen sets such that for each 1≤i≤n and 1≤j≤mi, the set Bi,j is a union of sets Ck. Further, take M∈R+ such that |gi|≤M for all i, and pick rational numbers (ak)pk=1 in (0,1)∩Q such that ∑pk=1ak=1 and |μ(Ck)−ak|<ε3pM; note we can do this since ∑pk=1μ(Ck)=1. If we can arrange ν so that ν(Ck)=ak for all k, we can conclude
∣∣Eμ(gi)−Eν(gi)∣∣≤p∑k=1∣∣∣∫Ckgidμ−∫Ckgidν∣∣∣=p∑k=1|gi(Ck)⋅(μ(Ck)−ν(Ck))|≤p∑k=1M|μ(Ck)−ak|<ε/3
as desired.
We now need only find a universal inductor limit ν such that ν(Ck)=ak for all 1≤k≤p. As mentioned above, we modify TradingFirm by adding a trader. For each Ck, take a sentence ϕk that holds exactly on Ck, and define the trader
Vicen=p∑k=1[Ind1(ϕ∗nk<ak)−Ind1(ϕ∗nk>ak)]⋅(ϕk−ϕ∗nk).
Then, with Skn and Budgeter as in section 5 of [1], we can define
TradingFirmn(P≤n−1)=Vicen+∑ℓ∈N+∑b∈N+2−ℓ−bBudgetern(b,Sk≤n,P≤n−1),
analogous to (5.3.2) in [1]. This is an n-strategy by an extension of the argument in [1] so, like in the construction of LIA there, we can define a belief sequence
νn=MarketMakern(TradingFirmn(ν≤n−1),ν≤n−1),
and this will not be exploitable by TradingFirm.
Next, we will use the fact that TradingFirm does not exploit ¯¯¯ν to investigate how $\mathrm{Vice} $'s holdings behave over time when trading on the market ¯¯¯ν. As in lemma 5.3.3 in [1], letting Fn=TradingFirmn(ν≤n−1), Vn=Vicen(ν≤n−1) and Bb,ℓn=Budgetern(b,Sℓ≤n,ν≤n−1), we have that in any world W∈2ω and at any step n∈N+,
W(∑i≤nFn)=W(∑i≤nVn)+W⎛⎝∑i≤n∑ℓ∈N+∑b∈N+2−ℓ−bBb,ℓn⎞⎠≥W(∑i≤nVn)−2,
so since TradingFirm cannot exploit ¯¯¯ν by construction, Vice cannot as well.
Now, notice that, for fixed n∈N+, the value W(Vn) is constant by construction as W varies within any one set Ck, so, regarding (ak)pk=1 as a measure on the finite σ-algebra generated by (Ck)pk=1, it makes sense to integrate W(Vn) with respect to that measure. For each n, we have that this integral is
p∑k=1Ck(Vn)ak=p∑k=1p∑k′=1Ck[(Ind1(νn(ϕk′)<ak′)−Ind1(νn(ϕk′)>ak′))⋅(ϕk′−νn(ϕk′))]⋅ak=p∑k′=1(Ind1(νn(ϕk′)<ak′)−Ind1(νn(ϕk′)>ak′))p∑k=1[Ck(ϕk′)⋅ak−νn(ϕk′)⋅ak]=p∑k′=1(Ind1(νn(ϕk′)<ak′)−Ind1(νn(ϕk′)>ak′))⋅(ak′−νn(ϕk′))≥0,
since for each k′ the two factors are either both positive, both negative, or both zero. This is to say, the value of Vice's holdings according to the measure given by the numbers ak is nondecreasing over time. Since ak>0 for all k, we can use our upper bound on W(Vn) to derive a lower bound; if L∈R is such that ˜W(∑ni=1Vi)≤L for all ˜W∈2ω and n∈N+, then for any W, say, in Ck,
W(n∑i=1Vi)=n∑i=1W(Vi)≥n∑i=1−1ak∑k′≠kCk′(Vi)ak′≥−1ak∑k′≠kL⋅ak′.
We can conclude two things from this, which will finish the argument. First, we get an analogue of lemma 5.3.3 from [1], from which it follows that ¯¯¯ν is a universal inductor (ignoring minor differences between the definitions of universal and logical inductors; see [2]). This is since for any of the budgeters Bb,ℓ defined above,
W(n∑i=1Fi)=2−b−ℓW(n∑i=1Bb,ℓi)+W(n∑i=1Vi)+W⎛⎝n∑i=1∑(b′,ℓ′)≠(b,ℓ)2−b′−ℓ′Bb′,ℓ′i⎞⎠≥2−b−ℓW(n∑i=1Bb,ℓi)+W(n∑i=1Vi)−2,
so Bb,ℓ has its holdings bounded uniformly in W and n.
Second, defining ν=limn→∞νn, we get the desired property that ν(Ck)=ak for all k. Suppose for contradiction that ν(Ck)<ak. Taking δ>0 with ν(Ck)+δ<ak, there is some N∈N+ such that if n≥N, then |νn(Ck)−ν(Ck)|<δ2. Then, for all such n, it follows that
νn(Ind1(ϕ∗nk<ak))>δ2,
and
νn(Ind1(ϕ∗nk>ak))=0,
so in any world W∈Ck,
W(Vn)≥δ2(1−νn(ϕk))≥δ2(1−ak),
and so Vice's holdings go to infinity in this world, giving the desired contradiction. By a symmetrical argument, we can't have ν(Ck)>ak, so ν(Ck)=ak as desired. □
One thing I want to note about the above proof is that, to my knowledge, it is the first construction of a logical inductor for which the limiting probability of a particular independent sentence is known.
Theorem 2: The set of universal inductor limits is not dense in the topology of strong convergence of measures or the total variation distance topology on Δ(2ω).
Proof: The total variation distance induces a finer topology than the topology of strong convergence, so it suffices to show that this set is not dense under strong convergence. Take any world W∈2ω that is not Δ2, and let μ∈Δ(2ω) be a point mass on W. The singleton {W} is a measurable set, so it suffices to show that for any universal inductor limit ν, we have μ({W})=1 but ν({W})=0.
Suppose for contradiction that there was some universal inductor limit ν for which this failed. By the Lebesgue density theorem, there is some clopen set A such that W∈A and
ν({W})ν(A)>12.
Then, it is possible to compute W from ν as follows. Each k∈N corresponds to some clopen subbase element Uk for the topology on 2ω. In order to determin whether k∈W, we can improve our estimates of ν(Uk∩A) and ν(A) until we've determined either ν(Uk∩A)/ν(A)>1/2 or ν(Uk∩A)/ν(A)<1/2. One of these must be the case, and we will eventually determine it since these are both open conditions. Thus, since ν is Δ2, the set W is as well, contradicting the hypothesis. □
[1] Scott Garrabrant, Tsvi Benson-Tilsen, Andrew Critch, Nate Soares, and Jessica Taylor. 2016. “Logical induction.” arXiv: 1609.03543 [cs.AI].
[2] Scott Garrabrant. 2016. “Universal inductors.” https://agentfoundations.org/item?id=941.
Logical inductors [1] are very complex objects, and even their limits are hard to get a handle on. In this post, I investigate the topological properties of the set of all limits of logical inductors.
I’ll use the language of universal inductors [2], but everything I say will also hold for general logical inductors by conditioning. Also, the proofs can be made to apply directly to general logical inductors with relatively few changes.
Universal inductors are measures on Cantor space (i.e. the space 2ω of infinite bit-strings) at every finite time, as well as in the limit (this is a bit nicer than the analogous situation for general logical inductors, which are measures on the space of completions of a theory only in the limit). There are many topologies on spaces of measures, and we can ask about topological properties under any of these. Interestingly, the set of universal inductor limits is dense in the topology of weak convergence, but not in the topology of strong convergence (or, a fortiori, the total variation metric topology).
It’s not immediately clear how to interpret this - should we think of the space of measures as being full of universal inductor limits, or should we think of universal inductor limits as being relatively few, with big holes where none exist? A relatively close analogy is the relationship between computable sets (or limit computable sets for a closer analogy) and arbitrary subsets of N; any subset of N can be approximated pointwise by limit computable sets (indeed, even by finite sets), but may be impossible to approximate under the ℓ1 norm, i.e. the number of differing bits. Now, on with the proofs!
Theorem 1: The set of limits of universal inductors is dense in the topology of weak convergence on the space of measures Δ(2ω).
Proof outline: We need to find a limit of universal inductors in any neighborhood of any measure μ. That is, for any finite collection of continuous functions, we need a universal inductor that, in the limit, assigns expectations to each such function that is close to the expectation under μ.
We do this with a modification of the standard universal inductor construction (section 5 of [1]), adding one additional trader to TradingFirm. This trader can buy and sell shares in events in order to keep these expectations within certain bounds, in a way similar to the Occam traders in the proof of theorem 4.6.4 in [1]. However, we give this trader a much larger budget than the others, allowing its control to be sufficiently tight.
Proof: It suffices to show that for any measure μ on 2ω, any finite set of bounded continuous functions fi:2ω→R for i∈{1,…,n} and any ε>0, there is a universal inductor limit ν such that ∣∣Eμf−Eνf∣∣<ε for all 1≤i≤n.
It's easier to work with prefixes of bit-strings than continuous functions, so we'll pass to such a description. Consider some fi. For each world W∈2ω, there is some clopen set A⊆2ω such that ∣∣fi(W)−fi(˜W)∣∣<ε3 for all ˜W∈A. By compactness, we can pick a finite cover (Ai,j)mij=1. Letting Bi,j=Ai,j∖⋃j−1k=1Ai,k, we get a disjoint open cover. By construction, for each 1≤j≤mi, there is some Wi,j such that for all ˜W∈Bi,j, we have ∣∣fi(Wi,j)−fi(˜W)∣∣<ε3, and we can define a simple function gi that takes the locally constant value fi(Wi,j) on each set Bi,j. Then, ∣∣Eμ(fi)−Eν(fi)∣∣≤∣∣Eμ(fi−gi)∣∣+∣∣Eμ(gi)−Eν(gi)∣∣+|Eν(gi−fi)|≤∣∣Eμ(gi)−Eν(gi)∣∣+23ε, so we need only control what our universal inductor limit ν thinks of the clopen sets Bi,j.
Pass to a single disjoint cover (Ck)pk=1 of 2ω by clopen sets such that for each 1≤i≤n and 1≤j≤mi, the set Bi,j is a union of sets Ck. Further, take M∈R+ such that |gi|≤M for all i, and pick rational numbers (ak)pk=1 in (0,1)∩Q such that ∑pk=1ak=1 and |μ(Ck)−ak|<ε3pM; note we can do this since ∑pk=1μ(Ck)=1. If we can arrange ν so that ν(Ck)=ak for all k, we can conclude ∣∣Eμ(gi)−Eν(gi)∣∣≤p∑k=1∣∣∣∫Ckgidμ−∫Ckgidν∣∣∣=p∑k=1|gi(Ck)⋅(μ(Ck)−ν(Ck))|≤p∑k=1M|μ(Ck)−ak|<ε/3 as desired.
We now need only find a universal inductor limit ν such that ν(Ck)=ak for all 1≤k≤p. As mentioned above, we modify TradingFirm by adding a trader. For each Ck, take a sentence ϕk that holds exactly on Ck, and define the trader Vicen=p∑k=1[Ind1(ϕ∗nk<ak)−Ind1(ϕ∗nk>ak)]⋅(ϕk−ϕ∗nk). Then, with Skn and Budgeter as in section 5 of [1], we can define TradingFirmn(P≤n−1)=Vicen+∑ℓ∈N+∑b∈N+2−ℓ−bBudgetern(b,Sk≤n,P≤n−1), analogous to (5.3.2) in [1]. This is an n-strategy by an extension of the argument in [1] so, like in the construction of LIA there, we can define a belief sequence νn=MarketMakern(TradingFirmn(ν≤n−1),ν≤n−1), and this will not be exploitable by TradingFirm.
Next, we will use the fact that TradingFirm does not exploit ¯¯¯ν to investigate how $\mathrm{Vice} $'s holdings behave over time when trading on the market ¯¯¯ν. As in lemma 5.3.3 in [1], letting Fn=TradingFirmn(ν≤n−1), Vn=Vicen(ν≤n−1) and Bb,ℓn=Budgetern(b,Sℓ≤n,ν≤n−1), we have that in any world W∈2ω and at any step n∈N+, W(∑i≤nFn)=W(∑i≤nVn)+W⎛⎝∑i≤n∑ℓ∈N+∑b∈N+2−ℓ−bBb,ℓn⎞⎠≥W(∑i≤nVn)−2, so since TradingFirm cannot exploit ¯¯¯ν by construction, Vice cannot as well.
Now, notice that, for fixed n∈N+, the value W(Vn) is constant by construction as W varies within any one set Ck, so, regarding (ak)pk=1 as a measure on the finite σ-algebra generated by (Ck)pk=1, it makes sense to integrate W(Vn) with respect to that measure. For each n, we have that this integral is p∑k=1Ck(Vn)ak=p∑k=1p∑k′=1Ck[(Ind1(νn(ϕk′)<ak′)−Ind1(νn(ϕk′)>ak′))⋅(ϕk′−νn(ϕk′))]⋅ak=p∑k′=1(Ind1(νn(ϕk′)<ak′)−Ind1(νn(ϕk′)>ak′))p∑k=1[Ck(ϕk′)⋅ak−νn(ϕk′)⋅ak]=p∑k′=1(Ind1(νn(ϕk′)<ak′)−Ind1(νn(ϕk′)>ak′))⋅(ak′−νn(ϕk′))≥0, since for each k′ the two factors are either both positive, both negative, or both zero. This is to say, the value of Vice's holdings according to the measure given by the numbers ak is nondecreasing over time. Since ak>0 for all k, we can use our upper bound on W(Vn) to derive a lower bound; if L∈R is such that ˜W(∑ni=1Vi)≤L for all ˜W∈2ω and n∈N+, then for any W, say, in Ck, W(n∑i=1Vi)=n∑i=1W(Vi)≥n∑i=1−1ak∑k′≠kCk′(Vi)ak′≥−1ak∑k′≠kL⋅ak′.
We can conclude two things from this, which will finish the argument. First, we get an analogue of lemma 5.3.3 from [1], from which it follows that ¯¯¯ν is a universal inductor (ignoring minor differences between the definitions of universal and logical inductors; see [2]). This is since for any of the budgeters Bb,ℓ defined above, W(n∑i=1Fi)=2−b−ℓW(n∑i=1Bb,ℓi)+W(n∑i=1Vi)+W⎛⎝n∑i=1∑(b′,ℓ′)≠(b,ℓ)2−b′−ℓ′Bb′,ℓ′i⎞⎠≥2−b−ℓW(n∑i=1Bb,ℓi)+W(n∑i=1Vi)−2, so Bb,ℓ has its holdings bounded uniformly in W and n.
Second, defining ν=limn→∞νn, we get the desired property that ν(Ck)=ak for all k. Suppose for contradiction that ν(Ck)<ak. Taking δ>0 with ν(Ck)+δ<ak, there is some N∈N+ such that if n≥N, then |νn(Ck)−ν(Ck)|<δ2. Then, for all such n, it follows that νn(Ind1(ϕ∗nk<ak))>δ2, and νn(Ind1(ϕ∗nk>ak))=0, so in any world W∈Ck, W(Vn)≥δ2(1−νn(ϕk))≥δ2(1−ak), and so Vice's holdings go to infinity in this world, giving the desired contradiction. By a symmetrical argument, we can't have ν(Ck)>ak, so ν(Ck)=ak as desired. □
One thing I want to note about the above proof is that, to my knowledge, it is the first construction of a logical inductor for which the limiting probability of a particular independent sentence is known.
Theorem 2: The set of universal inductor limits is not dense in the topology of strong convergence of measures or the total variation distance topology on Δ(2ω).
Proof: The total variation distance induces a finer topology than the topology of strong convergence, so it suffices to show that this set is not dense under strong convergence. Take any world W∈2ω that is not Δ2, and let μ∈Δ(2ω) be a point mass on W. The singleton {W} is a measurable set, so it suffices to show that for any universal inductor limit ν, we have μ({W})=1 but ν({W})=0.
Suppose for contradiction that there was some universal inductor limit ν for which this failed. By the Lebesgue density theorem, there is some clopen set A such that W∈A and ν({W})ν(A)>12. Then, it is possible to compute W from ν as follows. Each k∈N corresponds to some clopen subbase element Uk for the topology on 2ω. In order to determin whether k∈W, we can improve our estimates of ν(Uk∩A) and ν(A) until we've determined either ν(Uk∩A)/ν(A)>1/2 or ν(Uk∩A)/ν(A)<1/2. One of these must be the case, and we will eventually determine it since these are both open conditions. Thus, since ν is Δ2, the set W is as well, contradicting the hypothesis. □
[1] Scott Garrabrant, Tsvi Benson-Tilsen, Andrew Critch, Nate Soares, and Jessica Taylor. 2016. “Logical induction.” arXiv:
1609.03543 [cs.AI]
.[2] Scott Garrabrant. 2016. “Universal inductors.”
https://agentfoundations.org/item?id=941
.