Generalised models as a category

post by Stuart_Armstrong · 2021-02-16T16:08:27.774Z · LW · GW · 9 comments

Contents

  Naming the "generalised" models
  The generalised models
  Morphisms: relations
    Morphisms properties
    r-stable sets
    Morphism example: probability update
    Morphism example: surjective partial function
    Feature-split relations
None
9 comments

Naming the "generalised" models

In this post, I'll apply some mathematical rigour to my ideas of model splintering [LW · GW], and see what they are as a category^[1].

And the first question is... what to call them? I can't refer to them as 'the models I use in model splintering'. After a bit of reflection, I decided to call them 'generalised models'. Though that's a bit vague, it does describe well what they are, and what I hope to use them for: a formalism to cover all sorts of models.

The generalised models

A generalised model $M$ is given by three objects:

$$M=(F,E,Q).$$

Here $F$ is a set of features. Each feature $f$ consists of a name or label, and a set in which the feature takes values. For example, we might have the feature "room empty?" with values "true" and "false", or the feature "room temperature?" with values in $R^{+}$, the positive reals.

We allow these features to sometimes take no values at all (such as the above two features if the room doesn't exist) or multiple values (such as "potential running speed of person $X$" which includes the maximal speed and any speed below it).

Define $\overline{f}$ as the set component of the feature, and $\overline{F}$ as disjoint union of all the sets of the different features - ie $\overline{F}={\bigsqcup }_{f\in F}\overline{f}$.

A world, in the most general sense, is defined by all the values that the different features could take (including situations where features take multiple values and none at all). So the set of worlds, $W$, is the set of functions from $\overline{F}$ to $\{0,1\}$, with $1$ representing the fact that that feature takes that value, and $0$ the opposite. Hence $W=2^{\overline{F}}$, the power set of $\overline{F}$.

The set of environments is a specific subset of these worlds: $E\subset W$. The choice of $E$ is actually more important than that of $W$, as that establishes which values of the features we are modelling.

The $Q$ is a partial probability distribution [LW · GW]. In general, we won't worry as to whether $Q$ is normalised (ie whether $Q\left(E\right)=1$) or not; we'll even allow $Q$s with $Q\left(E\right)>1$. So $Q$ could be more properly be defined as a partial weight distribution. As long as we consider terms like $Q(A\mid B)$, then the normalisation doesn't matter.

Morphisms: relations

For simplicity, assume there are finitely many features taking values in finite sets, making all sets in the generalised model finite.

If $M_0=(F_0,E_0,Q_0)$ and $M^1(F_1,E_1,Q_1)$ are generalised models, then we want to use binary relations between $E_0$ and $E_1$ as morphisms between the generalised models.

Let $r$ be a relation between $E_0$ and $E_1$, written as $e_0{\sim }_r{e}_1$. Then it defines a map $r:2^{E_0}\to 2^{E_1}$ between subsets of $E_0$ and $E_1$. This map is defined by $e_1\in r\left(E_0\right)$ iff there exists an $e_0\in E_0$ with $e_0{\sim }_r{e}_1$. The map $r^{-1}:2^{E_1}\to 2^{E_0}$ is defined similarly^[2], seeing $r^{-1}$ as the inverse relation, $e_0{\sim }_r{e}_1$ iff $e_1{\sim }_{r^{-1}}{e}_0$.

We say that the relation $r$ is a morphism between the generalised models if, for any $E_0\subset E_0$ and $E_1\subset E_1$:

• $Q_0\left(E_0\right)\le Q_1\left(r\right(E_0\left)\right)$, or both measures are undefined.
• $Q_1\left(E_1\right)\le Q_0\left(r^{-1}\right(E_1\left)\right)$, or both measures are undefined.

The intuition here is that probability flows along the connections: if $e_0{\sim }_r{e}_1$ then probability can flow from $e_0$ to $e_1$ (and vice-versa). Thus $r\left(E_0\right)$ must have picked up all the probability that flowed out of $E_0$ - but it might have picked up more probability, since there may be connections coming into it from outside $E_0$. Same goes for $r^{-1}\left(E_1\right)$ and the probability of $E_1$.

Morphisms properties

We now check that these relations obey the requirements of morphisms in category theory.

Let $r$ be a morphism $M_0\to M_1$ (ie a relation between $E_0$ and $E_1$), and let $q$ be a morphism $M_1\to M_2$ (ie a relation between $E_1$ and $E_2$).

We compose relations by the composition of relations: $e_0{\sim }_{pr}{e}_2$ iff there exists an $e_1$ with $e_0{\sim }_r{e}_1$ and $e_1{\sim }_p{e}_2$. Composition of relations is associative.

We now need to show that $qr$ is a morphism. But this is easy to show:

• $Q_0\left(E_0\right)\le Q_1\left(r\right(E_0\left)\right)\le Q_2\left(pr\right(E_0\left)\right)$, or all three measures are undefined.
• $Q_2\left(E_2\right)\le Q_1\left(p^{-1}\right(E_2\left)\right)\le Q_0\left(r^{-1}{p}^{-1}\right(E_2\left)\right)$, or all three measures are undefined.

Finally, the identity relation $I{d}_{E_0}$ is the one that relates a given $e_0\in E_0$ only to itself; then $r$ and $r^{-1}$ are the identity maps on $2^{E_0}$, and the morphism properties for $Q_0=Q_1$ are trivially true.

So define the category of generalised models as $GM$.

$r$-stable sets

Say that a set $E_0\subset E_0$ is $r$-stable if $r^{-1}r\left(E_0\right)=E_0$.

For such an $r$-stable set, $Q_0\left(E_0\right)\le Q_1\left(r\right(E_0\left)\right)$ and $Q_1\left(r\right(E_0\left)\right)\le Q_0\left(r^{-1}r\right(E_0\left)\right)=Q_0\left(E_0\right)$, thus $Q_0\left(E_0\right)=Q_1\left(r\right(E_0\left)\right)$.

Hence if $r$ is a morphism, it preserves the probability measure on the $r$-stable sets.

In the particular case where $r$ is a bijective function, all points of $E_0$ are $r$-stable (and all points of $E_1$ are $r^{-1}$-stable), so it's an isomorphism between $E_0$ and $E_1$ that forces $Q_0=Q_1$.

Morphism example: probability update

Suppose we wanted to update our probability measure $Q_0$, maybe by updating that a particular feature $f$ takes a certain value $x$.

Then let $E_{f=x}\subset E_0$ be the set of environments where $f$ takes that value $x$. Then updating on $f=x$ is the same as restricting to $E_{f=x}$ and then rescaling.

Since we don't care about the scaling, we can consider updating on $f=x$ as just restricting to $E_{f=x}$. This morphism is given by:

1. $M_1=(F_0,E_{f=x},Q_1)$,
2. $Q_1=Q_0$ on $E_{f=x}\subset E_0$,
3. the morphism $r:M_0\to M_1$ is given by the relation that $e_0{\sim }_r{e}_0$ for all $e_0\in E_{f=x}$.

Morphism example: surjective partial function

In my previous [LW · GW] posts [LW · GW] I defined how $M_1=(F_1,E_1,Q_1)$ could be a refinement of $M_0=(F_0,E_0,Q_0)$.

In the language of the present post, $M_1$ is a refinement of $M_0$ if there exists a generalised model $M_1^{\prime }=(F_1,E_1,Q_1^{\prime })$ and a surjective partial function $r:E_1\to E_0$ (functions and partial functions are specific examples of binary relations) that is a morphism from $M_1^{\prime }$ to $M_0$. The $Q_1$ is required to be potentially 'better' than $Q_1^{\prime }$ on $E_1$, in some relevant sense.

This means that $M_1$ is 'better' than $M_0$ in three ways. The $r$ is surjective, so $E_1$ covers all of $E_0$, so its set of environments is at least as detailed. The $r$ is a partial function, so $E_1$ might have even more environments that don't correspond to anything in $E_0$ (it considers more situations). And, finally, $Q_1$ is better than $Q_1^{\prime }$, by whatever definition of better that we're using.

Feature-split relations

The morphisms/relations defined so far use $E$ and $Q$ - but they don't make any use of $F$. Here is one definition that does make use of the feature structure.

Say that the generalised model $M=(F,E,Q)$ is feature-split if $F={\bigsqcup }_{i=1}^n{F}^i$ and $E={\times }_{i=1}^n{E}^i$ such that

$$E^i\subset 2^{\overline{F^i}}.$$

Note that $F={\bigsqcup }_{i=1}^n{F}^i$ implies $W=2^{\overline{F}}={\times }_{i=1}^n{2}^{\overline{F^i}}$, so ${\times }_{i=1}^n{E}^i$ lies naturally within $W$.

Designate such a generalised model by $M=\left(\right\{F^i\},E,Q)$.

Then a feature-split relation between $M_0=\left(\right\{F_0^i\},E_0,Q_0)$ and $M_1=\left(\right\{F_1^i\},E_1,Q_1)$ is a morphism $r$ that is defined as $r=(r^1,r^2,\dots ,r^n)$ with $r^i$ a relation between $E_0^i$ and $E_1^i$.

---

1. I'm not fully sold on category theory as a mathematical tool, but it's certainly worthwhile to formalise your mathematical structures so that they can fit within the formalism of a category; it makes you think carefully about what you're doing. ↩︎

2. There is a slight abuse of notation here: $r:2^{E_0}\to 2^{E_1}$ and $r^{-1}:2^{E_1}\to 2^{E_0}$ are not generally inverses. They are inverses precisely for the "r-stable" sets that are discussed further down in the post. ↩︎

9 comments

Comments sorted by top scores.