The underlying model of a morphism

Stuart_Armstrong

I've already talked about generalised models. The aim is not only to have a universal system for modelling any agent's mental model - universality is pretty easy to get - but a system where it's easy to recreate these mental models. And then analyse the transition between models.

This post will show that if there is a morphism $r$ between two models (say, between ideal gas laws and models of atoms bouncing around), then there is an underlying model for that morphism.

Specifically, if $r$ is a morphism between $M_{0} = (F_{0}, Q_{0})$ and $M_{1} = (F_{1}, Q_{1})$ , then there is a generalised model $M_{r}$ defined from $r$ . The features of this model are the combination of the features of the two models: $F_{0} ⊔ F_{1}$ , and there are natural morphisms $r_{0}$ and $r_{1}$ from this underlying model to $M_{0}$ and $M_{1}$ :

Now, if $W_{0}$ and $W_{1}$ are the sets of possible worlds for $M_{0}$ and $M_{1}$ , then $W_{0} \times W_{1}$ is the set of possible worlds for $M_{r}$ . Then since $r$ is a relation between $W_{0}$ and $W_{1}$ , it can be seen as subset of $W_{0} \times W_{1}$ . And the $Q_{r}$ is a probability distribution over this subset $r$ .

What this means is that $Q_{r}$ measures how probability 'flows' from worlds in $M_{0}$ to worlds in $M_{1}$ . If $(w_{0}, w_{1})$ is an element of $r$ , then $Q_{r} (w_{0}, w_{1})$ measures how much probability is flowing from $w_{0}$ to $w_{1}$ . The actual probability of $w_{0}$ is the sum of all probability flowing out of it; that of $w_{1}$ , the sum of the probability flowing into it.

See for example this diagram, where the $Q_{0}$ probabilities are indicated in blue, those of $Q_{r}$ in black, and those of $Q_{1}$ in red. The probabilities $Q_{0}$ and $Q_{1}$ are the sum of the relevant probabilities $Q_{r}$ on the "edges" connecting to those points:

The distribution $Q_{r}$ is non-unique, though. The following two examples show situations with the same $Q_{0}$ and $Q_{1}$ , but different $Q_{r}$ :

The rest of this post will be dedicated to prove the existence of the underlying model for the morphism $r$ ; it can be skipped if you aren't interested.

Proof of underlying model

Definitions

Previous posts on generalised models defined them as triplets $M = (F, E, Q)$ , with $F$ a set of features, $W = 2^{¯ ¯¯ ¯ F}$ the set of possible worlds for those features, $E \subset W$ a subset of environments, and $Q$ a probability distribution on $E$ .

But $E$ was mainly superfluous, as $Q$ can be extended to a probability distribution on all of $W$ just by setting it to be zero on $W - E$ . Thus $E$ was dropped from the definition.

The original definition allowed $Q$ to be a partial probability distribution, but here we'll assume it's a total probability distribution (though not necessarily normalised; $Q (W)$ need not be $1$ ). The sets of features are assumed to be finite.

Then a morphism $r$ between generalised models $M_{0} = (F_{0}, Q_{0})$ and $M_{1} = (F_{1}, Q_{1})$ is a binary relation between $W_{0}$ and $W_{1}$ , such that:

$Q_{0} (E_{0}) \leq Q_{1} (r (E_{0}))$ ,
$Q_{1} (E_{1}) \leq Q_{0} (r^{- 1} (E_{1}))$ .

We might extend the class of morphisms by defining relations that only obey the first inequality as "left-morphisms", and relations that only obey the second one as a "right-morphisms". Left-morphisms ensure probability isn't lost ( $Q_{1} (W_{1}) \geq Q_{0} (W_{0})$ ), right morphisms ensure probability isn't gained ( $Q_{0} (W_{0}) \geq Q_{1} (W_{1})$ ). Full morphisms, of course, ensure that probability isn't gained or lost ( $Q_{0} (W_{0}) = Q_{1} (W_{1})$ ).

Binary relations are not necessarily functions; functions are relations $r$ such that each $w_{0}$ in $W_{0}$ is related to exactly one $w_{1}$ in $W_{1}$ .

Statement of the theorem

Let $r$ be a morphism between $M_{0} = (F_{0}, Q_{0})$ and $M_{1} = (F_{1}, Q_{1})$ . Then there exists a generalised model $M_{r} = (F_{0} ⊔ F_{1}, Q_{r})$ , with natural function morphisms $r_{0} : M_{r} \to M_{0}$ and $r_{1} : M_{r} \to M_{1}$ .

The $Q_{r}$ is non-zero on a set contained in $r \subset W_{0} \times W_{1} = 2^{F_{0}} \times 2^{F_{1}} = 2^{F_{0} ⊔ F_{1}}$ . The $Q_{r}$ need not be uniquely defined, but the total measure of $Q_{r}$ is the same as $Q_{0}$ and $Q_{1}$ :

$Q_{r} (r) = Q_{r} (W_{0} \times W_{1}) = Q_{0} (W_{0}) = Q_{1} (W_{1}) .$

Main proof

The function $r_{0}$ is just projection onto the first component: it sends $(w_{0}, w_{1})$ to $w_{0}$ . The functions $r_{1}$ conversely send $(w_{0}, w_{1})$ to $w_{1}$ .

Because $r_{0}$ and $r_{1}$ are functions, they can 'push-forward' any probability distribution $Q_{r}^{'}$ on $W_{0} \times W_{1}$ to $W_{0}$ and $W_{1}$ , respectively. This is given by: $r_{0} (Q_{r}^{'}) (w_{0}) = \sum_{w_{1}} Q_{r} (w_{0}, w_{1})$ , and similarly for $r_{1} (Q_{r}^{'})$ .

We aim to construct a $Q_{r}^{'}$ such that $r_{0} (Q_{r}^{'}) = Q_{0}$ and $r_{1} (Q_{r}^{'}) = Q_{1}$ ; this will be our $Q_{r}$ , and will make $r_{0}$ and $r_{1}$ into morphisms.

Define $Q_{r}^{'} (w_{0}, w_{1})$ to be zero if $(w_{0}, w_{1}) \notin r$ , or $Q_{0} (w_{0}) = 0$ or $Q_{1} (w_{1}) = 0$ . Thus we will ignore any elements of $W_{0}$ and $W_{1}$ of measure zero, and any element of $W_{0} \times W_{1}$ that is not in $r$ .

Let $w_{0} \in W_{0}$ be such that it is not related to any elements of $w_{1}$ by $r$ . Then $Q_{0} (w_{0}) \leq Q_{1} (r (w_{0})) = Q_{1} (\emptyset) = 0$ . Thus any element of $W_{0}$ with non-zero measure is related to some $w_{1}$ via $r$ .

Then define a choice function $c$ that maps every element $w_{0}$ with $Q_{0} (w_{0}) > 0$ , to an element $w_{1}$ that it is related to by $r$ . And define $Q_{r}^{'} (w_{0}, c (w_{0})) = Q_{0} (w_{0})$ , and $Q_{r}^{'}$ is zero on all other elements of $W_{0} \times W_{1}$ .

Then $r_{0} (Q_{r}^{'}) (w_{0}) = \sum_{(w_{0}, w_{1})} Q_{r}^{'} (w_{0}, w_{1}) = Q_{r}^{'} (w_{0}, c (w_{0})) = Q_{0} (w_{0})$ . Hence $r_{0} (Q_{r}^{'}) = Q_{0}$ . Consequently, $Q_{r}^{'} (W_{0} \times W_{1}) = Q_{0} (W_{0})$ .

Define $Q_{0}$ as the set of $Q_{r}^{'}$ , probability distributions on $r$ with $r_{0} (Q_{r}^{'}) = Q_{0}$ . We've shown that $Q_{0}$ is non-empty; moreover, any $Q_{r}^{'} \in Q_{0}$ has a total measure equal to $Q_{0} (W_{0}) = q$ . Since $Q_{r}^{'}$ is defined on $r$ , then it is contained in the set $[0, q]^{r}$ .

The set $[0, q]^{r}$ is compact, and $r_{0} (Q_{r}^{'}) = Q_{0}$ is a closed condition, so $Q_{0}$ is compact. The next section will prove that there is an element $Q_{r}^{'} \in Q_{0}$ with $r_{1} (Q_{r}^{'}) = Q_{1}$ ; that will complete the proof.

Key lemmas

Define $L (Q_{r}^{'}) = | r_{1} (Q_{r}^{'}) - Q_{1} |_{1} = \sum_{w_{1} \in W_{1}} | r_{1} (Q_{r}^{'}) (w_{1}) - Q_{1} (w_{1}) |$ . Now $L (Q_{r}^{'}) \geq 0$ , and note that $L (Q_{r}^{'}) = 0$ is equivalent with $r_{1} (Q_{r}^{'}) = Q_{1}$ .

Thus if $L$ takes the value $0$ on $Q_{0}$ , we've found the desired $Q_{r}$ . We will show that this happens thanks to the following key lemma:

Lemma 1: If there is a $Q_{r}^{'} \in Q_{0}$ with $L (Q_{r}^{'}) > 0$ , then there exists a $Q_{r}^{''} \in Q_{0}$ with $L (Q_{r}^{''}) < L (Q_{r}^{'})$ .

Now, since $Q_{0}$ is compact and $L$ is continuous, it will attain its minimum $μ$ on $Q_{0}$ . Then lemma 1 shows that $μ = 0$ (otherwise it wouldn't be a minimum).

Proof of Lemma 1:

Fix a $Q_{r}^{'}$ with $L (Q_{r}^{'}) > 0$ . Now $r_{1} (Q_{r}^{'}) (W_{1}) = \sum_{(w_{0}, w_{1})} Q_{r}^{'} (w_{0}, w_{1}) = r_{0} (Q_{r}^{'}) (W_{0}) = Q_{0} (W_{0}) = Q_{1} (W_{1})$ . So, since $L (Q_{r}^{'}) > 0$ , there must exist a $w_{1}$ with $r_{1} (Q_{r}^{'}) (w_{1}) > Q_{0} (w_{1})$ .

By lemma 2 (see below), we'll show that there exists a path $ρ_{n} = w_{1}^{0} w_{0}^{1} w_{1}^{1} w_{0}^{2} \dots w_{0}^{n} w_{1}^{n}$ with the following properties:

$w_{1}^{0} = w_{1}$ ,
$(w_{0}^{i} w_{1}^{i})$ and $(w_{0}^{i + 1} w_{1}^{i})$ are both elements of $r$ ,
the $Q_{r}^{'} (w_{0}^{i + 1} w_{1}^{i})$ are all greater than $0$ ,
$w_{1}^{n}$ is such that $r_{1} (Q_{r}^{'} (w_{1}^{n})) < Q_{1} (w_{1}^{n})$ .

Then define $ϵ > 0$ to be the minimum of ${r_{1} (Q_{r}^{'}) (w_{1}) - Q_{1} (w_{1}),$ $Q_{r}^{'} (w_{0}^{i} w_{1}^{i}),$ $Q_{1} (w_{1}) - r_{1} (Q_{r}^{'}) (w_{1}^{n})}$ .

We'll then define $Q_{r}^{''}$ as $Q_{r}^{''} (w_{0}^{i} w_{1}^{i}) = Q_{r}^{'} (w_{0}^{i + 1} w_{1}^{i}) - ϵ$ (which is greater than $0$ by the definition of $ϵ$ ), $Q_{r}^{''} (w_{0}^{i} w_{1}^{i}) = Q_{r}^{'} (w_{0}^{i} w_{1}^{i}) + ϵ$ , and $Q_{r}^{''} = Q_{r}$ otherwise.

Then notice that, apart from $w_{1} = w_{1}^{0}$ and $w_{1}^{n}$ , $r_{1} (Q_{r}^{''}) (w_{0}^{i}) =$ $\sum_{(w_{0}^{i}, w_{1}) \in r} Q_{r}^{''} (w_{0}^{i}, w_{1}) =$ $r_{1} (Q_{r}^{''}) (w_{0}^{i}) + ϵ - ϵ = r_{1} (Q_{r}^{''}) (w_{0}^{i})$ . So $r (Q_{r}^{'})$ and $r (Q_{r}^{''})$ differ only on $w_{1}$ and $w_{1}^{n}$ ; specifically

$r (Q_{r}^{''}) (w_{1}) = r (Q_{r}^{'}) (w_{1}) - ϵ$ ,
$r (Q_{r}^{''}) (w_{1}^{n}) = r (Q_{r}^{'}) (w_{1}^{n}) + ϵ$ .

Since $r (Q_{r}^{''}) (w_{1}) \geq Q_{1} (w_{1}) + ϵ$ and $r (Q_{r}^{''}) \leq Q_{1} (w_{1}^{n}) - ϵ$ , we have $L (Q_{r}^{''}) = L (Q_{r}^{'}) - 2 ϵ$ . This proves Lemma 1.

Lemma 2: There exists a path $ρ_{n} = w_{1}^{0} w_{0}^{1} w_{1}^{1} w_{0}^{2} \dots w_{0}^{n} w_{1}^{n}$ with the following properties:

$w_{1}^{0} = w_{1}$ ,
$(w_{0}^{i} w_{1}^{i})$ and $(w_{0}^{i + 1} w_{1}^{i})$ are both elements of $r$ ,
the $Q_{r}^{'} (w_{0}^{i + 1} w_{1}^{i})$ are all greater than $0$ ,
$w_{1}^{n}$ is such that $r_{1} (Q_{r}^{'} (w_{1}^{n})) < Q_{1} (w_{1}^{n})$ .

Proof of Lemma 2:

Let $W_{1} \subset W_{1}$ be the set of all elements of $W_{1}$ that can be reached by paths $ρ_{n}$ (ie are $w_{1}^{n}$ ) that obey the first three properties above. Let $W_{0} \subset W_{0}$ be the set of all elements of $W_{1}$ that are $w_{0}^{n}$ for some path $ρ_{n}$ that obey the first three properties above. Then clearly $W_{1} = r (W_{0})$ , by the second condition above (note that the third condition doesn't affect $(w_{0}^{n} w_{1}^{n})$ , which is only required to be in $r$ ).

Since $r$ is a morphism, $Q_{0} (W_{0}) \leq Q_{1} (W_{1})$ .

Note that if $Q_{r}^{'} (w_{0}, w_{1}^{'}) > 0$ with $w_{1}^{'} \in W_{1}$ , then $w_{0}$ must be in $W_{0}$ ; this is because we could add $w_{0} w_{1}^{'}$ as $w_{0}^{n + 1} w_{1}^{n + 1}$ to any path $ρ_{n}$ that reaches $w_{1}^{'}$ , getting a slightly longer path that goes via $w_{0}$ and thus puts it in $W_{0}$ .

Consequently, $r_{1} (Q_{r}^{'}) (W_{1}) =$ $\sum_{(w_{0}^{'}, w_{1}^{'}) \in r, w_{1}^{'} \in W_{1}} Q_{r}^{'} (w_{1}^{'}) =$ $\sum_{(w_{0}^{'}, w_{1}^{'}) \in r, w_{0}^{'} \in W_{0}} Q_{r}^{'} (w_{0}^{'}) =$ $Q_{0} (W_{0})$ .

So $r_{1} (Q_{r}^{'}) (W_{1}) = Q_{0} (W_{0}) \leq Q_{1} (W_{1})$ . Since $W_{1}$ includes $w_{1}$ with $r_{1} (Q_{r}^{'}) (w_{1}) > Q_{1} (w_{1})$ , it also much include at least one $w_{1}^{''}$ with $r_{1} (Q_{r}^{'}) (w_{1}^{''}) < Q_{1} (w_{1}^{''})$ .

The path $ρ_{n}$ that reaches this $w_{1}^{''}$ will then satisfy the fourth condition of the lemma, proving it.

AI ALIGNMENT FORUM
AF

6