Cartesian frames as generalised models

by Stuart_Armstrong7 min read16th Feb 2021No comments

20

Ω 11

Category TheoryAI
Frontpage
Crossposted from the AI Alignment Forum. May contain more technical jargon than usual.

Scott presented Cartesian frames/Chu spaces as follows:

  • Let be a set of possible worlds. A Cartesian frame over is a triple , where represents a set of possible ways the agent can be, represents a set of possible ways the environment can be, and is an evaluation function that returns a possible world given an element of and an element of .

In a previous post, I defined , the category of generalised models.

In this post, I'll try and see how these two formalisms relate to each other.

Equivalence with Cartesian frames

We'll now demonstrate the equivalence of Cartesian frames morphisms with the morphisms of generalised models. To do so, and avoid a collision of symbols, I've slightly tweaked the notation for Cartesian frames.

Equivalence of morphisms

Let and be Cartesian frames over : thus there are relations (written as ) and (written as ).

A morphism between them is a pair of maps , such that, for all and , .

How can we express this in the generalised model formalism?

First, let . In terms of features, this can be defined by setting , and . Then , and is the feature-split generalised model with , , and .

As we'll see in the bears example, there can be more interesting ways of defining the feature split .

Then the map pair is equivalent to the (feature-split) relation , defined such that iff:

  1. ,
  2. ,
  3. and .

Without loss of clarity, we can thus write as the feature-split relation .

Composing and generates . Take as the relation defined by and as the relation defined by . Then if , there must exist an with . Then:

  1. ,
  2. ,
  3. .

So composition of morphisms for Cartesian frames is the same as the composition of corresponding relations .

The extra structure

We have two structures to add: Cartesian frames have the map, while generalised models have the probability measures ; we need to relate them.

One natural way to relate them is to consider that if , then we should get and have for . This reflects the fact that action and environment lead inevitably to world .

Now , where denotes on the set ; this is .

Hence the desired condition on is equivalent with iff . There are, of course, multiple possible s with that property for any given .

The categorical equivalence

Now let's tie these together, and define , a subcategory of the , the category of generalised models. This will map surjectively to the category of Cartesian frames.

The objects of are those (feature-split) generalised models which have for some sets and , and have iff for some evaluation function .

The morphisms of are those morphisms of that map to itself, and that are of the form for a morphism of Cartesian frames.

Thus morphisms of are derived from morphisms of , and are also compatible with the structures (since they are also morphisms of ). Also included are the identity morphisms , which trivially preserve the structures.

To demonstrate that is a category, we need to show that is a morphism of it whenever and are. We know that must respect the structures (since and are morphisms of ), while , which derives from , a morphism of .

Thus is a category. Let be the map that sends to , and sends to .

This is clearly a functor of categories, and it is surjective on the objects of (the Cartesian frames). Now we need to show that it's also surjective on the morphisms, which comes from the following result:

  • Let be a morphism between and . Then there exists and a morphism between them such that .

To show that, we need to choose and that are compatible with and , and are compatible with .

In fact, we'll show a slightly stronger result: that for any with , we can pick an (ie pick a ) with the required properties.

To show this, note that will relate every element of with every element of . In fact, is defined by such relations, for any , and . No other elements are related by .

For compatibility of with the s, it suffices that be equal to .

For any , define as the size of ; since , .

Then define as . This will give the compatibility that we want.

Hence is a surjective functor of categories, from a subcategory of , the category of generalised models.

More functors

Given two sets and , and a function , there is an induced functor , sending to and sending the morphism to the morphism with the same underlying functions, .

Then by the above, we have and as distinct subcategories of , with functors and sending these subcategories to and .

Then also induces a functor , by sending to . The induced is given by .

Note that is not only a functor , it also acts as a morphism between any to , when both are seen as elements of . We'll designate these various morphisms by as well. As a functor, maps the relation to ; seeing as a morphism, is precisely , where is the opposite morphism to : iff .

We can see that the morphism commutes with the s:

  • .

This is probably enough exploration of the functorial properties of these spaces for one post.

An example: colours and bears

To illustrate, let's use the Cartesian frame from this post; this construction will also show how features can figure non-trivially in this construction.

Here the agent has two unrelated choices: which colour to think about (green, or red ) and whether to go for a walk or stay home ( or ). So . The environment is either safe or has bears: .

This gives the following frame :

Of course, and only differ in the colour that the agent is thinking about (similarly for and , etc...). We could choose a frame that doesn't distinguish between these thoughts:

Let . Then we can define the various sets through features; specifically, in this example, . Similarly .

Adding a definition of and , we can construct the feature split generalised models:

  1. .
  2. .

The are defined by the matrix above; if we want them to make sense as traditional probability distributions, we might require that whenever it is non-zero, with the size of the matrix. In that case, , as required.

Notes on non-synonyms

Some of the terminology is repeated between the two formalisms, but doesn't mean the same things. Specifically:

  • Environments: for Cartesian frames, this is , the different columns of the matrix. For generalised models, this is the larger set .
  • Worlds: for Cartesian frames, this is , the possible values of the elements of the matrix. For generalised models, this is , the set of all possible values all the features could take. At the very least, contains , but it could be much larger.

20

Ω 11

New Comment