A measure-theoretic generalization of logical induction

by Vanessa Kosoy6 min read18th Jan 2017No comments

4

Logical InductionLogical Uncertainty
Personal Blog
Crossposted from the AI Alignment Forum. May contain more technical jargon than usual.

% operators that are separated from the operand by a space

% operators that require brackets

% operators that require parentheses

% Paper specific

Logical induction is defined in terms of logical sentences and theories, but its principles are applicable in much greater generality and abstraction. Indeed, one such generalization was studied under the name "universal induction." We proposed a slightly different generalization in order to model reasoning with incomplete models. Here, we describe a formalism that includes all these cases and many more, using the language of measure theory. This provides the following advantages:

  • The formalism is applicable to event spaces substantially different from truth assignments or bit sequences, e.g. we can consider sequences of real numbers.

  • The formalism treats probabilities and expectations on the same footing, rather than constructing expectations as in section 4.8 of original paper. We consider this more convenient.

  • In our opinion, this language is more mathematically natural than the original formalism, at least for applications unrelated to formal logic.

On the other hand, we ignore all computational considerations. Obviously these are often important, but in the study of purely information-theoretic questions the use of numerical approximations only serves to obscure.

All proofs are in the Appendix.

##Results

Fix a compact Polish space. For example, might be or the space of propositionally consistent truth assignments in some language or . The role of "pricings" is served by : the space of probability measures on . A market is thus a sequence . The "deductive process" is replaced by a sequence of closed sets A trading strategy is a continuous function , were is equipped with the weak* topology (as before) and is the space of continuous functions from to equipped with the uniform convergence topology. Here, we should think of as the share portfolio acquired by the strategy given pricing , where the cost of the acquisition is understood to be while the ultimate value of the portfolio is (in the following we will use the less clumsy notation ; in fact, we can equivalently define as the set of continuous functions from to ) for some . We denote the set of trading strategies by . A trader is a sequence , where the functions can be arbitrary (don't have to be continuous in any sense). The argument of these functions refers to the market pricings on previous days.

Analogously to Lemma 5.1.1 in "Logical Induction" (existence of "market maker"), we have:

#Proposition 1

For any , there is s.t.


Analogous to Definition 5.2.1 ("budgeter"), we have:

#Proposition 2

Given , define by

Fix a trader . Define by

Define by

(For , the above definition is understood to mean 0)

Fix . Assume and are s.t.

Then, we can define by

Finally, define by

Then:

  • is also a trader (i.e. it is continuous in the last argument).

  • If is s.t. , then .


The analogue of Definition 5.3.2 ("trading firm") is as follows:

#Proposition 3

Consider a family of traders and s.t.

Define as follows:

Then, the above sum is convergent and defines a trader. Moreover:


The analogue of Definition 5.4.1 (logical inductor construction):

#Proposition 4

Consider the setting of Proposition 3. Then, there are s.t.


Analogously to Definition 3.5.1 ("exploitation") we have:

#Definition

A market is said to dominate a trader relatively to when

  • Denoting the inclusion mapping, is in the image of .

  • The following set of real numbers is either unbounded from below or bounded from above:


Finally, the analogue of Theorem 5.4.2:

#Theorem

Consider the setting of Proposition 4, and assume that . Then, dominates for every .

##Appendix

#Proposition A.1

Given , define by

Then, is continuous.

#Proof of Proposition A.1

Consider and . We have

By continuity of , and therefore, . We get

Since and is continuous, we have and therefore

#Proof of Proposition 1

Define as follows:

For any , denote . is convex due to linearity of expected value. is non-empty because given , .

Consider and s.t. . We have

By Proposition A.1, the left hand side converges to . Since , the right hand side converges to . We get:

Therefore, and is a closed set. Applying the Kakutani-Glicksberg-Fan theorem, we get the desired result.

#Proof of Proposition 2

is continuous by Proposition A.1. Therefore, is continuous in the last argument and is also continuous in the last argument.

Assume is s.t.

Then, for any we are in the second case in the definition of . Moreover, we have

Using the assumption again, the left hand side is positive. It follows that

Now, fix any . Let be the largest number s.t. and

For any , we have

(Note that the sum in the definition of only involves for )

For , we have

The first term only involves for , and we are still in the first case in the definition of the second term, therefore

If is s.t. , then

If is s.t. , then

We got that for all , and therefore

Finally, consider .

Now we are in the first case in the definition of , therefore the second term vanishes.

By induction on , we conclude:

#Proposition A.2

If are compact Polish spaces and is continuous, then defined by is continuous.

#Proof of Proposition A.2

We already proved an equivalent proposition: see "Proposition A.1" here.

#Proof of Proposition 3

The definition of implies that

Observe that

As a result, the definition of is pointwise absolutely convergent:

Moreover, this series converges uniformly absolutely in and :

By the uniform limit theorem, the series defines a continuous function of and . By Proposition A.2, it follows that is a trader.

Now, let's examine :

Since convergence is uniform absolute, the sum commutes with .

By Proposition 2:

#Proof of Proposition 4

We construct recursively in . Define by

(pushforward is obviously continuous in the weak* topology)

Now construct by applying Proposition 1 to .

#Proof of Theorem

We have

By definition of

Fix and assume for some (otherwise is dominated). Define by

We get and therefore

By Proposition 2 and the definition of , we can remove in the second term.

By Proposition 3, the right hand side is bounded from above by , therefore

4

New Comment