Tag: Spivak

Learners and Poly

Published January 29, 2022 by lieven

Brendan Fong, David Spivak and Remy Tuyeras cooked up a vast generalisation of neural networks in their paper Backprop as Functor: A compositional perspective on supervised learning.

Here’s a nice introduction to neural networks for category theorists by Bruno Gavranovic. At 1.49m he tries to explain supervised learning with neural networks in one slide. Learners show up later in the talk.

$Poly$ is the category of all polynomial functors, that is, things of the form
$p = \sum_{i \in p (1)} y^{p [i]} : Sets \to Sets S \mapsto ⨆_{i \in p (1)} M a p s (p [i], S)$
with $p (1)$ and all $p [i]$ sets.

Last time I gave Spivak’s ‘corolla’ picture to think about such functors.

I prefer to view $p \in Poly$ as an horribly discrete ‘sheaf’ $P$ over the ‘space’ $p (1)$ with stalk $p [i] = P_{i}$ at point $i \in p (1)$ .

A morphism $p \to q$ in $Poly$ is a map $φ_{1} : p (1) \to q (1)$ , together with for all $i \in p (1)$ a map $φ_{i}^{#} : q [φ_{1} (i)] \to p [i]$ .

In the sheaf picture, this gives a map of sheaves over the space $p (1)$ from the inverse image sheaf $φ_{1}^{*} Q$ to $P$ .

But, unless you dream of sheaves in the night, by all means stick to Spivak’s corolla picture.

A learner $A \to B$ between two sets $A$ and $B$ is a complicated tuple of things $(P, I, U, R)$ :

$P$ is a set, a parameter space of some maps from $A$ to $B$ .
$I$ is the interpretation map $I : P \times A \to B$ describing the maps in $P$ .
$U$ is the update map $U : P \times A \times B \to P$ , the learning procedure. The idea is that $U (p, a, b)$ is a map which sends $a$ closer to $b$ than the map $p$ did.
$R$ is the request map $R : P \times A \times B \to A$ .

Here’s a nice application of $Poly$ ’s set-up:

Morphisms $P y^{P} \to Maps (A, B) \times Maps (A \times B, A) y^{A \times B}$ in $Poly$ coincide with learners $A \to B$ with parameter space $P$ .

This follows from unpacking the definition of morphism in $Poly$ and the process CT-ers prefer to call Currying.

The space-map $φ_{1} : P \to M a p s (A, B) \times M a p s (A \times B, A)$ gives us the interpretation and request-map, whereas the sheaf-map $φ^{#}$ gives us the more mysterious update-map $P \times A \times B \to P$ .

$Learn (A, B)$ is the category with objects all the learners $A \to B$ (for all paramater-sets $P$ ), and with morphisms defined naturally, that is, maps between the parameter-sets, compatible with the structural maps.

A surprising result from David Spivak’s paper Learners’ Languages is

$Learn (A, B)$ is a topos. In fact, it is the topos of all set-valued representations of a (huge) directed graph $G_{AB}$ .

This will take some time.

Let’s bring some dynamics in. Take any polynmial functor $p \in Poly$ and fix a morphism in $Poly$
$φ = (φ_{1}, φ [-]) : p (1) y^{p (1)} \to p$
with space-map $φ_{1}$ the identity map.

We form a directed graph:

the vertices are the elements of $p (1)$ ,
vertex $i \in p (1)$ is the source vertex of exactly one arrow for every $a \in p [i]$ ,
the target vertex of that arrow is the vertex $ϕ [i] (a) \in p (1)$ .

Here’s one possibility from Spivak’s paper for $p = 2 y^{2} + 1$ , with the coefficient $2$ -set ${green dot, yellow dot}$ , and with $1$ the singleton ${red dot}$ .

Start at one vertex and move after a minute along a directed edge to the next (possibly the same) vertex. The potential evolutions in time will then form a tree, with each node given a label in $p (1)$ .

If we start at the green dot, we get this tree of potential time-evolutions

There are exactly $# p [i]$ branches leaving a node labeled $i \in p (1)$ , and all subtrees emanating from equal labelled nodes are isomorphic.

If we had started at the yellow dot we had obtained a labelled tree isomorphic to the subtree emanating here from any yellow dot.

We can do the same things for any morphism in $Poly$ of the form
$φ = (φ_{1}, φ [-]) : S y^{S} \to p$
Now, we have a directed graph with vertices the elements $s \in S$ , with as many edges leaving vertex $s$ as there are elements $a \in p [φ_{1} (s)]$ , and with the target vertex of the edge labeled $a$ starting in $s$ the vertex $φ [φ_{1} (s)] (A)$ .

Once we have this directed graph on $# S$ vertices we can label vertex $s$ with the label $φ_{1} (s)$ from $p (1)$ .

In this way, the time evolutions starting at a vertex $s \in S$ will give us a $p (1)$ -labelled rooted tree.

But now, it is possibly that two distinct vertices can have the same $p (1)$ -labeled tree of evolutions. But also, trees corresponding to equal labeled vertices can be different.

Right, I guess we’re ready to define the graph $G_{A B}$ and prove that $Learn (A, B)$ is a topos.

In the case of learners, we have the target polynomial functor $p = C y^{A \times B}$ with $C = M a p s (A, B) \times M a p s (A \times B, A)$ , that is
$p (1) = C and all p [i] = A \times B$

Start with the free rooted tree $T$ having exactly $# A \times B$ branches growing from each node.

Here’s the directed graph $G_{A B}$ :

vertices $v_{χ}$ correspond to the different $C$ -labelings of $T$ , one $C$ -labeled rooted tree $T_{χ}$ for every map $χ : v t x (T) \to C$ ,
arrows $v_{χ} \to v_{ω}$ if and only if $T_{ω}$ is the rooted $C$ -labelled tree isomorphic to the subtree of $T_{χ}$ rooted at one step from the root.

A learner $A \to B$ gives a set-valued representation of $G_{AB}$ .

We saw that a learner $A \to B$ is the same thing as a morphism in $Poly$
$φ = (φ_{1}, φ [-]) : P y^{P} \to C y^{A \times B}$
with $P$ the parameter set of maps.

Here’s what we have to do:

1. Draw the directed graph on vertices $p \in P$ giving the dynamics of the morphism $φ$ . This graph describes how the learner can cycle through the parameter-set.

2. Use the map $φ_{1}$ to label the vertices with elements from $C$ .

3. For each vertex draw the rooted $C$ -labeled tree of potential time-evolutions starting in that vertex.

In this example the time-evolutions of the two green vertices are the same, but in general they can be different.

4. Find the vertices in $G_{A B}$ determined by these $C$ -labeled trees and note that they span a full subgraph of $G_{A B}$ .

5. The vertex-set $P_{v}$ consists of all elements from $p$ whose ( $C$ -labeled) vertex has evolution-tree $T_{v}$ . If $v \to w$ is a directed edge in $G_{A B}$ corresponding to an element $(a, b) \in A \times B$ , then the map on the vertex-sets corresponding to this edge is
$f_{v, (a, b)} : P_{v} \to P_{w} p \mapsto φ [φ_{1} (p)] (a, b)$

A set-valued representation of $G_{AB}$ gives a learner $A \to B$ .

1. Take a set-valued representation of $G_{A B}$ , that is, the finite or infinite collection of vertices $V$ in $G_{A B}$ where the vertex-set $P_{v}$ is non-empty. Note that these vertices span a full subgraph of $G_{A B}$ .

And, for each directed arrow $v \to w$ in this subgraph, labeled by an element $(a, b) \in A \times B$ we have a map
$f_{v, (a, b)} : P_{v} \to P_{w}$

2. The parameter set of our learner will be $P = ⊔_{v} P_{v}$ , the disjoint union of the non-empty vertex-sets.

3. The space-map $φ_{1} : P \to C$ will send an element in $P_{v}$ to the $C$ -label of the root of the tree $T_{v}$ . This gives us already the interpretation and request maps
$I : P \times A \to B and R : P \times A \times B \to A$

4. The update map $U : P \times A \times B \to P$ follows from the sheaf-map we can define stalk-wise
$φ [φ_{1} (p)] (a, b) = f_{v, (a, b)} (p)$
if $p \in P_{v}$ .

That’s all folks!

$Learn (A, B)$ is equivalent to the (covariant) functors $G_{AB} \to Sets$ .

Changing the directions of all arrows in $G_{A B}$ any covariant functor $G_{AB} \to Sets$ becomes a contravariant functor $G_{AB}^{o} \to Sets$ , making $Learn (A, B)$ an honest to Groth topos!

Every topos comes with its own logic, so we have a ‘learners’ logic’. (to be continued)

One Comment

Poly

Published January 26, 2022 by lieven

Following up on the deep learning and toposes-post, I was planning to do something on the logic of neural networks.

Prepping for this I saw David Spivak’s paper Learner’s Languages doing exactly that, but in the more general setting of ‘learners’ (see also the deep learning post).

And then … I fell under the spell of $Poly$ .

Spivak is a story-telling talent. A long time ago I copied his short story (actually his abstract for a talk) “Presheaf, the cobbler” in the Children have always loved colimits-post.

Last week, he did post Poly makes me happy and smart on the blog of the Topos Institute, which is another great read.

If this is way too ‘fluffy’ for you, perhaps you should watch his talk Poly: a category of remarkable abundance.

If you like (applied) category theory and have some days to waste, you can binge-watch all 15 episodes of the Poly-course Polynomial Functors: A General Theory of Interaction.

If you are more the reading-type, the 273 pages of the Poly-book will also kill a good number of your living hours.

Personally, I have no great appetite for category theory, I prefer to digest it in homeopathic doses. And, I’m allergic to co-terminology.

So then, how to define $Poly$ for the likes of me?

$Poly$ , you might have surmised, is a category. So, we need ‘objects’ and ‘morphisms’ between them.

Any set $A$ has a corresponding ‘representable functor’ sending a given set $S$ to the set of all maps from $A$ to $S$
$y^{A} : Sets \to Sets S \mapsto S^{A} = M a p s (A, S)$
This looks like a monomial in a variable $y$ ( $y$ for Yoneda, of course), but does it work?

What is $y^{1}$ , where $1$ stands for the one-element set ${*}$ ? $M a p s (1, S) = S$ , so $y^{1}$ is the identity functor sending $S$ to $S$ .

What is $y^{0}$ , where $0$ is the empty set $\emptyset$ ? Well, for any set $S$ there is just one map $\emptyset \to S$ , so $y^{0}$ is the constant functor sending any set $S$ to $1$ . That is, $y^{0} = 1$ .

Going from monomials to polynomials we need an addition. We add such representable functors by taking disjoint unions (finite or infinite), that is
$\sum_{i \in I} y^{A_{i}} : Sets \to Sets S \mapsto ⨆_{i \in I} M a p s (A_{i}, S)$
If all $A_{i}$ are equal (meaning, they have the same cardinality) we use the shorthand $I y^{A}$ for this sum.

The objects in $Poly$ are exactly these ‘polynomial functors’
$p = \sum_{i \in I} y^{p [i]}$
with all $p [i] \in Sets$ . Remark that $p (1) = I$ as for any set $A$ there is just one map to $1$ , that is $y^{A} (1) = M a p s (A, 1) = 1$ , and we can write
$p = \sum_{i \in p (1)} y^{p [i]}$
An object $p \in Poly$ is thus described by the couple $(p (1), p [-])$ with $p (1)$ a set, and a functor $p [-] : p (1) \to Sets$ where $p (1)$ is now a category with objects the elements of $p (1)$ and no morphisms apart from the identities.

We can depict $p$ by a trimmed down forest, Spivak calls it the corolla of $p$ , where the tree roots are the elements of $p (1)$ and the tree with root $i \in p (1)$ has one branch from the root for any element in $p [i]$ . The corolla of $p = y^{2} + 2 y + 1$ looks like

If $M$ is an $m$ -dimensional manifold, then you might view its tangent bundle $T M$ set-theoretically as the ‘corolla’ of the polynomial functor $M y^{R^{m}}$ , the tree-roots corresponding to the points of the manifold, and the branches to the different tangent vectors in these points.

Morphisms in $Poly$ are a bit strange. For two polynomial functors $p = (p (1), p [-])$ and $q = (q (1), q [-])$ a map $p \to q$ in $Poly$ consists of

a map $ϕ_{1} : p (1) \to q (1)$ on the tree-roots in the right direction, and
for any $i \in p (1)$ a map $q [ϕ_{1} (i)] \to p [i]$ on the branches in the opposite direction

In our manifold/tangentbundle example, a morphism $M y^{R^{m}} \to y^{1}$ sends every point $p \in M$ to the unique root of $y^{1}$ and the unique branch in $y^{1}$ picks out a unique tangent-vector for every point of $M$ . That is, vectorfields on $M$ are very special (smooth) morphisms $M u^{R^{m}} \to y^{1}$ in $Poly$ .

A smooth map between manifolds $M \to N$ , does not determine a morphism $M y^{R^{m}} \to N y^{R^{n}}$ in $Poly$ because tangent vectors are pushed forward, not pulled back.

If instead we view the cotangent bundle $T^{*} M$ as the corolla of the polynomial functor $M y^{R^{m}}$ , then everything works well.

But then, I promised not to use co-terminology…

Another time I hope to tell you how $Poly$ helps us to understand the logic of learners.

Comments closed

Deep learning and toposes

Published January 16, 2022 by lieven

Judging from this and that paper, deep learning is the string theory of the 2020s for geometers and representation theorists.

String theory is the 90s answer to the tears of algebraic geometers worldwide trying to write the "Applications" part of their grant proposals. https://t.co/AboZ5WkPtc

— algebraic geometer BLM (@BarbaraFantechi) December 17, 2021

If you want to know quickly what neural networks really are, I can recommend the post demystifying deep learning.

The typical layout of a deep neural network has an input layer $L_{0}$ allowing you to feed $N_{0}$ numbers to the system (a vector $\vec{v_{0}} \in R^{N_{0}}$ ), an output layer $L_{p}$ spitting $N_{p}$ numbers back (a vector $\vec{v_{p}} \in R^{N_{p}}$ ), and $p - 1$ hidden layers $L_{1}, \dots, L_{p - 1}$ where all the magic happens. The hidden layer $L_{i}$ has $N_{i}$ virtual neurons, their states giving a vector $\vec{v_{i}} \in R^{N_{i}}$ .

Picture taken from Logical informations cells I

For simplicity let’s assume all neurons in layer $L_{i}$ are wired to every neuron in layer $L_{i + 1}$ , the relevance of these connections given by a matrix of weights $W_{i} \in M_{N_{i + 1} \times N_{i}} (R)$ .

If at any given moment the ‘state’ of the neural network is described by the state-vectors $\vec{v_{1}}, \dots, \vec{v_{p - 1}}$ and the weight-matrices $W_{0}, \dots, W_{p}$ , then an input $\vec{v_{0}}$ will typically result in new states of the neurons in layer $L_{1}$ given by

${\vec{v_{1}}}^{'} = c_{0} (W_{0} . \vec{v_{0}} + \vec{v_{1}})$

which will then give new states in layer $L_{2}$

${\vec{v_{2}}}^{'} = c_{1} (W_{1} . {\vec{v_{1}}}^{'} + \vec{v_{2}})$

and so on, rippling through the network, until we get as the output

$\vec{v_{p}} = c_{p - 1} (W_{p - 1} . {\vec{v_{p - 1}}}^{'})$

where all the $c_{i}$ are fixed smooth activation functions $c_{i} : R^{N_{i + 1}} \to R^{N_{i + 1}}$ .

This is just the dynamic, or forward working of the network.

The learning happens by comparing the computed output with the expected output, and working backwards through the network to alter slightly the state-vectors in all layers, and the weight-matrices between them. This process is called back-propagation, and involves the gradient descent procedure.

Even from this (over)simplified picture it seems doubtful that set valued (!) toposes are suitable to describe deep neural networks, as the Paris-Huawei-topos-team claims in their recent paper Topos and Stacks of Deep Neural Networks.

Still, there is a vast generalisation of neural networks: learners, developed by Brendan Fong, David Spivak and Remy Tuyeras in their paper Backprop as Functor: A compositional perspective on supervised learning (which btw is an excellent introduction for mathematicians to neural networks).

For any two sets $A$ and $B$ , a learner $A \to B$ is a tuple $(P, I, U, R)$ where

$P$ is a set, a parameter space of some functions from $A$ to $B$ .
$I$ is the interpretation map $I : P \times A \to B$ describing the functions in $P$ .
$U$ is the update map $U : P \times A \times B \to P$ , part of the learning procedure. The idea is that $U (p, a, b)$ is a map which sends $a$ closer to $b$ than the map $p$ did.
$R$ is the request map $R : P \times A \times B \to A$ , the other part of the learning procedure. The idea is that the new element $R (p, a, b) = a^{'}$ in $A$ is such that $p (a^{'})$ will be closer to $b$ than $p (a)$ was.

The request map is also crucial is defining the composition of two learners $A \to B$ and $B \to C$ . $Learn$ is the (symmetric, monoidal) category with objects all sets and morphisms equivalence classes of learners (defined in the natural way).

In this way we can view a deep neural network with $p$ layers as before to be the composition of $p$ learners
$R^{N_{0}} \to R^{N_{1}} \to R^{N_{2}} \to \dots \to R^{N_{p}}$
where the learner describing the transition from the $i$ -th to the $i + 1$ -th layer is given by the equivalence class of data $(A_{i}, B_{i}, P_{i}, I_{i}, U_{i}, R_{i})$ with
$A_{i} = R^{N_{i}}, B_{i} = R^{N_{i + 1}}, P_{i} = M_{N_{i + 1} \times N_{i}} (R) \times R^{N_{i + 1}}$
and interpretation map for $p = (W_{i}, {\vec{v}}_{i + 1}) \in P_{i}$
$I_{i} (p, \vec{v_{i}}) = c_{i} (W_{i} . \vec{v_{i}} + {\vec{v}}_{i + 1})$
The update and request maps (encoding back-propagation and gradient-descent in this case) are explicitly given in theorem III.2 of the paper, and they behave functorial (whence the title of the paper).

More generally, we will now associate objects of a topos (actually just sheaves over a simple topological space) to a network op $p$ learners
$A_{0} \to A_{1} \to A_{2} \to \dots \to A_{p}$
inspired by section I.2 of Topos and Stacks of Deep Neural Networks.

The underlying category will be the poset-category (the opposite of the ordering of the layers)
$0 \leftarrow 1 \leftarrow 2 \leftarrow \dots \leftarrow p$
The presheaf on a poset is a locale and in this case even the topos of sheaves on the topological space with $p + 1$ nested open sets.
$X = U_{0} \supseteq U_{1} \supseteq U_{2} \supseteq \dots \supseteq U_{p} = \emptyset$
If the learner $A_{i} \to A_{i + 1}$ is (the equivalence class) of the tuple $(A_{i}, A_{i + 1}, P_{i}, I_{i}, U_{i}, R_{i})$ we will now describe two sheaves $W$ and $X$ on the topological space $X$ .

$W$ has as sections $Γ (W, U_{i}) = \prod_{j = i}^{p - 1} P_{i}$ and the obvious projection maps as the restriction maps.

$X$ has as sections $Γ (X, U_{i}) = A_{i} \times Γ (W, U_{i})$ and restriction map to the next smaller open
$ρ_{i + 1}^{i} : Γ (X, U_{i}) \to Γ (X, U_{i + 1}) (a_{i}, (p_{i}, p^{'})) \mapsto (p_{i} (a_{i}), p^{'})$
and other retriction maps by composition.

A major result in Topos and Stacks of Deep Neural Networks is that back-propagation is a natural transformation, that is, a sheaf-morphism $X \to X$ .

In this general setting of layered learners we can always define a map on the sections of $X$ (for every open $U_{i}$ ), $Γ (X, U_{i}) \to Γ (X, U_{i})$
$(a_{,} (p_{i}, p^{'})) \mapsto (R (p_{i}, a_{i}, p_{i} (a_{i})), (U (p_{i}, a_{i}, p_{i} (a_{i})), p^{'})$
But, in order for this to define a sheaf-morphism, compatible with the restrictions, we will have to impose restrictions on the update and restriction maps of the learners, in general.

Still, in the special case of deep neural networks, this compatibility follows from the functoriality property of Backprop as Functor: A compositional perspective on supervised learning.

To be continued.

One Comment