2103/2103.01189.md

Title: Learners’ Languages

URL Source: https://arxiv.org/html/2103.01189

Markdown Content: Back to arXiv

This is experimental HTML to improve accessibility. We invite you to report rendering errors. Use Alt+Y to toggle on accessible reporting links and Alt+Shift+Y to toggle off. Learn more about this project and help improve conversions.

Why HTML? Report Issue Back to Abstract Download PDF Abstract 1Introduction 2Constructions in 𝐏𝐨𝐥𝐲 3Toposes of learners

HTML conversions sometimes display errors due to content that did not convert correctly from the source. This paper uses the following packages that are not yet supported by the HTML conversion tool. Feedback on these issues are not necessary; they are known and are being worked on.

failed: dutchcal failed: biblatex

Authors: achieve the best HTML results from your LaTeX submissions by following these best practices.

License: arXiv.org perpetual non-exclusive license arXiv:2103.01189v3 [math.CT] null \addbibresource

LibrarySmall.bib

Learners’ Languages David I. Spivak Topos Institute Berkeley USA david@topos.institute Abstract

In “Backprop as functor”, the authors show that the fundamental elements of deep learning—gradient descent and backpropagation—can be conceptualized as a strong monoidal functor 𝐏𝐚𝐫𝐚 ⁢ ( 𝐄𝐮𝐜 ) → 𝐋𝐞𝐚𝐫𝐧 from the category of parameterized Euclidean spaces to that of learners, a category developed explicitly to capture parameter update and backpropagation. It was soon realized that there is an isomorphism 𝐋𝐞𝐚𝐫𝐧 ≅ 𝐏𝐚𝐫𝐚 ⁢ ( 𝐒𝐋𝐞𝐧𝐬 ) , where 𝐒𝐋𝐞𝐧𝐬 is the symmetric monoidal category of simple lenses as used in functional programming.

In this note, we observe that 𝐒𝐋𝐞𝐧𝐬 is a full subcategory of 𝐏𝐨𝐥𝐲 , the category of polynomial functors in one variable, via the functor 𝐴 ↦ 𝐴 ⁢ 𝓎 𝐴 . Using the fact that ( 𝐏𝐨𝐥𝐲 , ⊗ ) is monoidal closed, we show that a map 𝐴 → 𝐵 in 𝐏𝐚𝐫𝐚 ⁢ ( 𝐒𝐋𝐞𝐧𝐬 ) has a natural interpretation in terms of dynamical systems (more precisely, generalized Moore machines) whose interface is the internal-hom type [ 𝐴 ⁢ 𝓎 𝐴 , 𝐵 ⁢ 𝓎 𝐵 ] .

Finally, we review the fact that the category 𝑝 ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 of dynamical systems on any 𝑝 ∈ 𝐏𝐨𝐥𝐲 forms a topos, and consider the logical propositions that can be stated in its internal language. We give gradient descent as an example, and we conclude by discussing some directions for future work.

1Introduction

In the paper “Backprop as functor” [fong2019backprop], the authors show that gradient descent and backpropagation—as used in deep learning—can be conceptualized as a strong monoidal functor 𝐿 : 𝐏𝐚𝐫𝐚 ⁢ ( 𝐄𝐮𝐜 ) → 𝐋𝐞𝐚𝐫𝐧 from the category of parameterized euclidean spaces to that of learners, a category developed explicitly to capture parameter update and backpropagation. Here, 𝐏𝐚𝐫𝐚 is a monad on the category of symmetric monoidal categories. It sends ( 𝒞 , 𝐼 , ⊗ ) to a category with the same objects Ob ⁡ 𝐏𝐚𝐫𝐚 ⁢ ( 𝒞 ) ≔ Ob ⁡ 𝒞 , but with hom-sets that include a parameterizing object

𝐏𝐚𝐫𝐚 ( 𝒞 ) ( 𝑐 1 , 𝑐 2 ) ≔ { ( 𝑝 , 𝑓 ) ∣ 𝑝 ∈ 𝒞 , 𝑓 : 𝑐 1 ⊗ 𝑝 → 𝑐 2 } / ∼

where the parameterizing object 𝑝 is considered up to an equivalence relation ∼ .1 The composite of 𝑐 1 ⊗ 𝑝 1 → 𝑐 2 and 𝑐 2 ⊗ 𝑝 2 → 𝑐 3 in 𝐏𝐚𝐫𝐚 ⁢ ( 𝒞 ) has parameterizing object 𝑝 1 ⊗ 𝑝 2 and is given by the ordinary composite

𝑐 1 ⊗ ( 𝑝 1 ⊗ 𝑝 2 ) → 𝑐 2 ⊗ 𝑝 2 → 𝑐 3 .

The domain of the backpropagation functor, 𝐏𝐚𝐫𝐚 ⁢ ( 𝐄𝐮𝐜 ) , is thus the Para construction applied to the Cartesian monoidal category of Euclidean spaces ℝ 𝑛 and smooth maps.

But it was soon realized that 𝐋𝐞𝐚𝐫𝐧 is in fact also given by a Para construction, namely there is an isomorphism 𝐋𝐞𝐚𝐫𝐧 ≅ 𝐏𝐚𝐫𝐚 ⁢ ( 𝐒𝐋𝐞𝐧𝐬 ) , where 𝐒𝐋𝐞𝐧𝐬 is the symmetric monoidal category of simple lenses as used in functional programming. The objects of 𝐒𝐋𝐞𝐧𝐬 are sets Ob ⁡ ( 𝐒𝐋𝐞𝐧𝐬 )

Ob ⁡ ( 𝐒𝐞𝐭 ) , but a morphism consists of a pair of functions

𝐒𝐋𝐞𝐧𝐬 ⁢ ( 𝐴 , 𝐵 ) :- { ( 𝑓 1 , 𝑓 ♯ ) ∣ 𝑓 1 : 𝐴 → 𝐵 , 𝑓 ♯ : 𝐴 × 𝐵 → 𝐴 } .

(1)

Thus a map 𝐴 → 𝐵 in 𝐏𝐚𝐫𝐚 ⁢ ( 𝐒𝐋𝐞𝐧𝐬 ) consists of a set 𝑃 and functions 𝑓 1 : 𝐴 × 𝑃 → 𝐵 and 𝑓 ♯ : 𝐴 × 𝐵 × 𝑃 → 𝐴 × 𝑃 . The authors of [fong2019backprop] developed this structure in order to conceptualize the compositional nature of deep learning as comprising a parameterizing set 𝑃 (often called “the space of weights and biases”) and three functions:

𝐼

: 𝐴 × 𝑃 → 𝐵 implement

𝑈

: 𝐴 × 𝐵 × 𝑃 → 𝑃 update

𝑅

: 𝐴 × 𝐵 × 𝑃 → 𝐴 request (2)

The implement function is a 𝑃 -parameterized function 𝐴 → 𝐵 , and the update and request functions take a pair ( 𝑎 , 𝑏 ) of “training data” and both updates the parameter—e.g. by gradient descent—and returns an element of the input space 𝐴 , which is used to train another such function in the network. This last step—the request—is not just found in deep learning as practiced, but is in fact crucial for defining composition.2

But by this point, the notation ( 𝑃 , 𝐼 , 𝑈 , 𝑅 ) of 𝐋𝐞𝐚𝐫𝐧 has become heavy and the structure seems to be getting lost. Even knowing 𝐋𝐞𝐚𝐫𝐧 ≅ 𝐏𝐚𝐫𝐚 ⁢ ( 𝐒𝐋𝐞𝐧𝐬 ) seems ad-hoc since the morphisms (1) of 𝐒𝐋𝐞𝐧𝐬 are—to this point—mathematically unmotivated. This is where 𝐏𝐨𝐥𝐲 comes in.

In this note, we observe that 𝐒𝐋𝐞𝐧𝐬 is a full subcategory of 𝐏𝐨𝐥𝐲 , the category of polynomial functors in one variable, via the functor 𝐴 ↦ 𝐴 ⁢ 𝓎 𝐴 . Using the fact that ( 𝐏𝐨𝐥𝐲 , ⊗ ) is monoidal closed, we will reconceptualize 𝐏𝐚𝐫𝐚 ⁢ ( 𝐒𝐋𝐞𝐧𝐬 ) in terms of polynomial coalgebras, which can be understood as dynamical systems: machines with states that can be observed as “output” and updated based on “input” [jacobs2017introduction]. In particular, a morphism 𝐴 → 𝐵 in 𝐋𝐞𝐚𝐫𝐧 will be recast as a coalgebra on the internal hom polynomial [ 𝐴 ⁢ 𝓎 𝐴 , 𝐵 ⁢ 𝓎 𝐵 ] , and we will explain this in terms of dynamics.

This viewpoint allows us to substantially generalize the construction in 𝐋𝐞𝐚𝐫𝐧 , a construction which also appears prominently in the theory of open games [ghani2016compositional]. Perhaps more interestingly, it allows us to use the fact that the category 𝑝 ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 of dynamical systems on any interface 𝑝 ∈ 𝐏𝐨𝐥𝐲 forms a topos. A topos is a setting in which one can do dependent type theory and higher-order logic. In fact, the topos of 𝑝 -coalgebras is in some ways as simple as possible: it is not only a copresheaf topos 𝑝 ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 ≅ 𝐒𝐞𝐭 𝒞 for a certain category 𝒞 , but in fact the site 𝒞 is the free category on a directed graph that we’ll call 𝖳𝗋𝖾𝖾 𝑝 . This makes the logic of 𝑝 -coalgebras—and hence of dynamical systems, learners, and game-players—quite simple. However, the particular graph 𝖳𝗋𝖾𝖾 𝑝 associated to 𝑝 is highly-structured, and we should find that this structure is inherited by the internal language of 𝑝 ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 .

The point is to consider logical propositions that can be stated in the internal language of 𝑝 ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 and to use these propositions in order to constrain the behavior of learners and game-players (categorified as discussed above), and of interaction patterns between dynamical systems more generally. For example, “gradient descent and backpropagation” is a property we can express in the internal language. Note that the term language in the title refers to the internal language of the topos 𝑝 ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 , which can be thought of as a language for specifying or constraining learning algorithms or dynamic organizational patterns more generally.

Plan for the paper

In Section 2 we will discuss various relevant constructions in the category 𝐏𝐨𝐥𝐲 of polynomial functors in one variable. In particular, we will review its symmetric monoidal closed structure ( 𝐏𝐨𝐥𝐲 , 𝓎 , ⊗ , [ − , − ] ) , its composition monoidal structure ( 𝓎 , ◁ ) , and the notion of coalgebras. We explain how morphisms in 𝐋𝐞𝐚𝐫𝐧 can be phrased in terms of coalgebras on internal hom objects, and we reconstruct 𝐏𝐚𝐫𝐚 ⁢ ( 𝐒𝐋𝐞𝐧𝐬 ) in these terms.

In Section 3, we first show that the category 𝑝 ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 of 𝑝 -coalgebras for the endofunctor 𝑝 : 𝐒𝐞𝐭 → 𝐒𝐞𝐭 is a presheaf topos. We then discuss the internal logic of 𝑝 ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 , and we conclude by giving several directions for future work.

Notation

We denote the category of sets by 𝐒𝐞𝐭 ; we generally denote sets with upper-case letters 𝐴 , 𝐵 , etc. Given a natural number 𝑁 ∈ ℕ , we write 𝖭 ≔ { 1 , … , 𝑁 } , so 0

∅ , 1

{ 1 } , 2

{ 1 , 2 } , etc. Given sets 𝐴 , 𝐵 , we often write 𝐴 ⁢ 𝐵 ≔ 𝐴 × 𝐵 to denote their Cartesian product. We will denote polynomials with lower-case letters, 𝑝 , 𝑞 , etc.

Acknowledgments

We thank David A. Dalrymple, Dai Girardo, Paul Kreiner, David Jaz Myers, and Alex Zhu for useful conversations. We also acknowledge support from AFOSR grant FA9550-20-10348.

2Constructions in 𝐏𝐨𝐥𝐲

In this section we review the category 𝐏𝐨𝐥𝐲 , for which [kock2012polynomial] is an excellent reference; we also discuss its symmetric monoidal closed structure. Then we discuss polynomial coalgebras and reconceptualize the category 𝐋𝐞𝐚𝐫𝐧 and Gavranović’s bicategorical variant, in that language.

2.1Background on 𝐏𝐨𝐥𝐲 as a monoidal closed category

For any set 𝐴 , let 𝓎 𝐴 : 𝐒𝐞𝐭 → 𝐒𝐞𝐭 be the functor represented by 𝐴 ; that is, 𝓎 𝐴 applied to a set 𝑆 is 𝐒𝐞𝐭 ⁢ ( 𝐴 , 𝑆 ) ≅ 𝑆 𝐴 . In particular, 𝓎 ≔ 𝓎 1 is (isomorphic to) the identity functor 𝑆 ↦ 𝑆 and 1 ≔ 𝓎 0 is the constant functor 𝑆 ↦ 1 . Note that 𝓎 𝐴 ⁢ ( 1 ) ≅ 1 𝐴 ≅ 1 for any 𝐴 .

The coproduct of functors 𝐹 and 𝐺 , denoted 𝐹 + 𝐺 , is taken pointwise; this means there is a natural isomorphism

( 𝐹 + 𝐺 ) ⁢ ( 𝑆 ) ≅ 𝐹 ⁢ ( 𝑆 ) + 𝐺 ⁢ ( 𝑆 )

where the coproduct 𝐹 ⁢ ( 𝑆 ) + 𝐺 ⁢ ( 𝑆 ) is taken in 𝐒𝐞𝐭 . Similarly, for any set 𝐼 and functors 𝐹 𝑖 , one for each 𝑖 ∈ 𝐼 , their coproduct is computed pointwise

( ∑ 𝑖 ∈ 𝐼 𝐹 𝑖 ) ⁢ ( 𝑆 ) ≅ ∑ 𝑖 ∈ 𝐼 𝐹 𝑖 ⁢ ( 𝑆 ) .

Definition 2.1.

A polynomial functor 𝑝 is any coproduct

𝑝 ≔ ∑ 𝑖 ∈ 𝐼 𝓎 𝑝 ⁢ [ 𝑖 ]

of representable functors, where 𝐼 ∈ 𝐒𝐞𝐭 and each 𝑝 ⁢ [ 𝑖 ] ∈ 𝐒𝐞𝐭 are sets. We denote the category of polynomial functors and natural transformations between them by 𝐏𝐨𝐥𝐲 .

We note that if 𝑝

∑ 𝑖 ∈ 𝐼 𝓎 𝑝 ⁢ [ 𝑖 ] then 𝑝 ⁢ ( 1 ) ≅ 𝐼 ; hence we can write any 𝑝 ∈ 𝐏𝐨𝐥𝐲 in canonical form

𝑝 ≅ ∑ 𝑖 ∈ 𝑝 ⁢ ( 1 ) 𝓎 𝑝 ⁢ [ 𝑖 ] .

(3)

We refer to each 𝑖 ∈ 𝑝 ⁢ ( 1 ) as a position in 𝑝 and to each 𝑑 ∈ 𝑝 ⁢ [ 𝑖 ] as a direction at 𝑖 .

Example 2.2.

We can consider any set 𝑆 as a constant polynomial ∑ 𝑠 ∈ 𝑆 𝓎 0 .

We can consider a polynomial 𝑝 ∈ 𝐏𝐨𝐥𝐲 as a set (or discrete category) 𝑝 ⁢ ( 1 ) equipped with a functor 𝑝 ⁢ [ − ] : 𝑝 ⁢ ( 1 ) → 𝐒𝐞𝐭 . Then a map of polynomials 𝜑 : 𝑝 → 𝑞 can be identified with a diagram as follows

𝑝 ⁢ ( 1 ) 𝑞 ⁢ ( 1 ) 𝐒𝐞𝐭 𝜑 1 𝑝 ⁢ [ − ] ⇐ 𝜑 ♯ 𝑞 ⁢ [ − ]

(4)

That is, 𝜑 can be decomposed into a function 𝜑 1 : 𝑝 ⁢ ( 1 ) → 𝑞 ⁢ ( 1 ) on positions, and for every 𝑖 ∈ 𝑝 ⁢ ( 1 ) with 𝑗 ≔ 𝜑 1 ⁢ ( 𝑖 ) , a component function 𝜑 𝑖 ♯ : 𝑞 ⁢ [ 𝑗 ] → 𝑝 ⁢ [ 𝑖 ] on directions. This follows from the Yoneda lemma and the universal property of coproducts. We will sometimes use this ( 𝜑 1 , 𝜑 ♯ ) : 𝑝 → 𝑞 notation below.

Example 2.3.

A morphism 𝐴 1 ⁢ 𝓎 𝐴 2 → 𝐵 1 ⁢ 𝓎 𝐵 2 can be identified with a function 𝜑 1 : 𝐴 1 → 𝐵 1 and a function 𝜑 ♯ : 𝐴 1 × 𝐵 2 → 𝐴 2 . That is,

𝐏𝐨𝐥𝐲 ⁢ ( 𝐴 1 ⁢ 𝓎 𝐴 2 , 𝐵 1 ⁢ 𝓎 𝐵 2 ) ≅ 𝐵 1 𝐴 1 ⁢ 𝐴 2 𝐴 1 ⁢ 𝐵 2 .

(5) Proposition 2.4.

The composite of polynomial functors 𝑝 , 𝑞 ∈ 𝐏𝐨𝐥𝐲 , which we denote 𝑝 ◁ 𝑞 , is again polynomial with formula

𝑝 ◁ 𝑞 ≅ ∑ 𝑖 ∈ 𝑝 ⁢ ( 1 ) ∑ 𝑗 : 𝑝 ⁢ [ 𝑖 ] → 𝑞 ⁢ ( 1 ) 𝓎 ∑ 𝑑 ∈ 𝑝 ⁢ [ 𝑖 ] 𝑞 ⁢ [ 𝑗 ⁢ 𝑑 ]

(6)

The composition operation ◁ is a (nonsymmetric) monoidal structure on 𝐏𝐨𝐥𝐲 , with unit 𝓎 .

Proof.

See page A. ∎

Example 2.5.

If 𝑝

𝓎 2 and 𝑞

𝓎 + 1 , then 𝑝 ◁ 𝑞 ≅ 𝓎 2 + 2 ⁢ 𝓎 + 1 whereas 𝑞 ◁ 𝑝 ≅ 𝓎 2 + 1 .

Example 2.6.

Applying a polynomial 𝑝 to a set 𝑆 is given by composition: 𝑝 ⁢ ( 𝑆 ) ≅ 𝑝 ◁ 𝑆 .

Proposition 2.7 (The symmetric monoidal category ( 𝐏𝐨𝐥𝐲 , 𝓎 , ⊗ ) ).

The category 𝐏𝐨𝐥𝐲 has a symmetric monoidal structure with unit 𝓎 and monoidal product ⊗ on objects given by the following formula

𝑝 ⊗ 𝑞 ≔ ∑ 𝑖 ∈ 𝑝 ⁢ ( 1 ) ∑ 𝑗 ∈ 𝑞 ⁢ ( 1 ) 𝓎 𝑝 ⁢ [ 𝑖 ] × 𝑞 ⁢ [ 𝑗 ]

Proof.

See page A. ∎

Proposition 2.8 (Internal hom [ − , − ] ).

The ⊗ monoidal structure on 𝐏𝐨𝐥𝐲 is closed; that is, for every 𝑝 , 𝑞 ∈ 𝐏𝐨𝐥𝐲 there is a polynomial

[ 𝑝 , 𝑞 ] ≔ ∑ 𝜑 : 𝑝 → 𝑞 𝓎 ∑ 𝑖 ∈ 𝑝 ⁢ ( 1 ) 𝑞 ⁢ [ 𝜑 1 ⁢ ( 𝑖 ) ]

(7)

for which we have a natural isomorphism

𝐏𝐨𝐥𝐲 ⁢ ( 𝑟 ⊗ 𝑝 , 𝑞 ) ≅ 𝐏𝐨𝐥𝐲 ⁢ ( 𝑟 , [ 𝑝 , 𝑞 ] ) .

(8) Proof.

See page A. ∎

Example 2.9.

Given sets 𝐴 and 𝐵 , we use Eqs. 5 and 7 to compute that the internal hom between 𝐴 ⁢ 𝓎 𝐴 and 𝐵 ⁢ 𝓎 𝐵 is

[ 𝐴 ⁢ 𝓎 𝐴 , 𝐵 ⁢ 𝓎 𝐵 ] ≅ 𝐵 𝐴 ⁢ 𝐴 𝐴 ⁢ 𝐵 ⁢ 𝓎 𝐴 ⁢ 𝐵 .

The counit of the adjunction (8) is a natural map eval : 𝑝 ⊗ [ 𝑝 , 𝑞 ] → 𝑞 called evaluation. In very much the same way, it induces two sorts of morphisms we will use later:

[ 𝑝 1 , 𝑞 1 ] ⊗ [ 𝑝 2 , 𝑞 2 ] → [ 𝑝 1 ⊗ 𝑝 2 , 𝑞 1 ⊗ 𝑞 2 ] and [ 𝑝 , 𝑞 ] ⊗ [ 𝑞 , 𝑟 ] → [ 𝑝 , 𝑟 ] .

(9) 2.2Coalgebras, generalized Moore machines, and learners

Coalgebras for endofunctors 𝐹 : 𝐒𝐞𝐭 → 𝐒𝐞𝐭 form a major topic of study [arbib1982parametrized, adamek2005introduction, jacobs2017introduction]. In this section we recall the definition and explain the relevance to dynamical systems (generalized Moore machines) and learners.

Definition 2.10 (Coalgebra).

Given a polynomial 𝑝 , a 𝑝 -coalgebra is a pair ( 𝑆 , 𝛽 ) where 𝑆 ∈ 𝐒𝐞𝐭 and 𝛽 : 𝑆 → 𝑝 ◁ 𝑆 . A 𝑝 -coalgebra morphism from ( 𝑆 , 𝛽 ) to ( 𝑆 ′ , 𝛽 ′ ) consists of a function 𝑓 : 𝑆 → 𝑆 ′ such that the following diagram commutes:

𝑆 𝑝 ◁ 𝑆 𝑆 ′ 𝑝 ◁ 𝑆 ′ 𝛽 𝑓 𝑝 ◁ 𝑓 𝛽 ′

(10)

We denote the category of 𝑝 -coalgebras and their morphisms by 𝑝 ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 .

Proposition 2.11.

A 𝑝 -coalgebra ( 𝑆 , 𝛽 ) can be identified with a map of polynomials

𝑆 ⁢ 𝓎 𝑆 → 𝑝 .

(11) Proof.

One finds an isomorphism 𝐏𝐨𝐥𝐲 ⁢ ( 𝑆 , 𝑝 ◁ 𝑆 ) ≅ 𝐏𝐨𝐥𝐲 ⁢ ( 𝑆 ⁢ 𝓎 𝑆 , 𝑝 ) by direct calculation. ∎

Warning 2.12.

Looking at Proposition 2.11, one might be tempted to think that a map of 𝑝 -coalgebras as in (10) can be identified with a commuting triangle

𝑆 ⁢ 𝓎 𝑆 𝑆 ′ ⁢ 𝓎 𝑆 ′ 𝑝 ?

but this is not the case; for one thing, the marked arrow does not arise from a function 𝑓 : 𝑆 → 𝑆 ′ . The point is, (11) can be misleading when it comes to maps, and hence we will depart from the so-called 𝐏𝐚𝐫𝐚 construction for 2-cells. For us, the correct sort of map between 𝑝 -coalgebras is the usual one, as shown in (10).

Proposition 2.13.

For any 𝑝 , 𝑞 ∈ 𝐏𝐨𝐥𝐲 there is a functor

𝑝 ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 × 𝑞 ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 → ( 𝑝 ⊗ 𝑞 ) ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠

making ∙

⁢ 𝐂𝐨𝐚𝐥𝐠 a lax monoidal functor 𝐏𝐨𝐥𝐲 → 𝐂𝐚𝐭 .

Proof.

See page A. ∎

The relevance of coalgebras to dynamics was of interest in the earliest of references we know of, namely [arbib1982parametrized], where they are referred to as codynamics. We will proceed with our own terminology.

Definition 2.14 (Moore machine).

For sets 𝐴 , 𝐵 , an ( 𝐴 , 𝐵 ) -Moore machine consists of

•

a set 𝑆 , elements of which are called states,

•

a function 𝑟 : 𝑆 → 𝐵 , called readout, and

•

a function 𝑢 : 𝑆 × 𝐴 → 𝑆 , called update.

It is further called initialized if it is equipped with an element 𝑠 0 ∈ 𝑆 .

With an initialized ( 𝐴 , 𝐵 ) -Moore machine ( 𝑆 , 𝑟 , 𝑢 , 𝑠 0 ) , we can take any 𝐴 -stream 𝑎 : ℕ → 𝐴 and produce a 𝐵 -stream 𝑏 : ℕ → 𝐵 inductively using the formula

𝑠 𝑛 + 1 ≔ 𝑢 ⁢ ( 𝑠 𝑛 , 𝑎 𝑛 ) and 𝑏 𝑛 ≔ 𝑟 ⁢ ( 𝑠 𝑛 ) .

Proposition 2.15.

An ( 𝐴 , 𝐵 ) -Moore machine with states 𝑆 can be identified with a map of polynomials 𝑆 ⁢ 𝓎 𝑆 → 𝐵 ⁢ 𝓎 𝐴 , and hence with a 𝐵 ⁢ 𝓎 𝐴 -coalgebra 𝑆 → 𝐵 ⁢ 𝓎 𝐴 ◁ 𝑆 by Proposition 2.11.

Proof.

The identification uses 𝜑 1 ≔ 𝑟 and 𝜑 ♯ ≔ 𝑢 . ∎

Replacing 𝐵 ⁢ 𝓎 𝐴 with an arbitrary polynomial 𝑝 ∈ 𝐏𝐨𝐥𝐲 , we think of 𝑝 -coalgebras as generalized Moore machines. We will refer to them as 𝑝 -dynamical systems and call 𝑝 the interface. Mathematically, given 𝛽 : 𝑆 → 𝑝 ◁ 𝑆 , we also get the two-fold composite

𝑆 → 𝛽 𝑝 ◁ 𝑆 → 𝑝 ◁ 𝛽 𝑝 ◁ 𝑝 ◁ 𝑆

and indeed the 𝑛 -fold composite 𝑆 → 𝑝 ⊲ 𝑛 ◁ 𝑆 for any 𝑛 ∈ ℕ . The idea is that for every state 𝑠 ∈ 𝑆 , we get a position 𝑟 ⁢ ( 𝑠 ) ∈ 𝑝 ⁢ ( 1 ) , and for every direction 𝑑 ∈ 𝑝 ⁢ [ 𝑟 ⁢ ( 𝑠 ) ] there, we get a new state 𝑢 ⁢ ( 𝑠 , 𝑑 ) . We thus think of 𝑝 as an interface for the dynamical system: 𝑝 ⁢ ( 1 ) says what the world can see about the current state—i.e. its outward position 𝑖 ≔ 𝑟 ⁢ ( 𝑠 ) —and 𝑝 ⁢ [ 𝑖 ] says what sort of forces or inputs the state can be subjected to.

A map of polynomials 𝜑 : 𝑝 → 𝑝 ′ is a change of interface. We can transform a 𝑝 -dynamical system into a 𝑝 ′ -dynamical system that has the same set of states. Indeed, simply compose any 𝑆 → 𝑝 ◁ 𝑆 with 𝜑 ◁ 𝑆 : 𝑝 ◁ 𝑆 → 𝑝 ′ ◁ 𝑆 .

More generally, a map 𝜑 : 𝑝 1 ⊗ ⋯ ⊗ 𝑝 𝑘 → 𝑝 ′ allows us to take 𝑘 -many dynamical systems 𝑆 1 → 𝑝 1 ◁ 𝑆 1 through 𝑆 𝑘 → 𝑝 𝑘 ◁ 𝑆 𝑘 and use Proposition 2.13 to combine them into a single dynamical system

𝑆 → ( 𝑝 1 ⊗ ⋯ ⊗ 𝑝 𝑘 ) ◁ 𝑆 → 𝜑 𝑝 ′ ◁ 𝑆

with interface 𝑝 ′ and states 𝑆 ≔ 𝑆 1 × ⋯ × 𝑆 𝑘 .

Example 2.16.

Wiring diagrams are one way of combining dynamical systems as above.

𝜑

Plant Controller 𝐴 𝐵 𝐶 Controlled_Plant

(12)

In the wiring diagram (12) three boxes are shown: the controller, the plant, and the system; we can consider each as having a monomial interface:

Plant

𝐶 ⁢ 𝓎 𝐴 ⁢ 𝐵 Controller

𝐵 ⁢ 𝓎 𝐶 Controlled_Plant

𝐶 ⁢ 𝓎 𝐴 .

(13)

The wiring diagram itself represents a morphism

𝜑 : 𝐶 ⁢ 𝓎 𝐴 ⁢ 𝐵 ⊗ 𝐵 ⁢ 𝓎 𝐶 → 𝐶 ⁢ 𝓎 𝐴

in 𝐏𝐨𝐥𝐲 . Defining 𝜑 requires a function 𝜑 1 : 𝐶 × 𝐵 → 𝐶 and a function 𝜑 ♯ : 𝐶 × 𝐵 × 𝐴 → 𝐴 × 𝐵 × 𝐶 ; the first is projection and the second is an isomorphism. Together these simply say how the wiring diagram shuttles information within the controlled plant. Indeed, the wiring diagram lets us put together dynamics of the controller and the plant to give dynamics for the controlled plant. That is, given Moore machines 𝑆 ⁢ 𝓎 𝑆 → Plant and 𝑇 ⁢ 𝓎 𝑇 → Controller , we get a Moore machine 𝑆 ⁢ 𝑇 ⁢ 𝓎 𝑆 ⁢ 𝑇 → Controlled_Plant .

More generally, we can think of transistors in a computer as dynamical systems, and the logic gates, adder circuits, memory circuits, a connected keyboard or monitor, etc. each as a wiring diagram comprising these simpler systems.

Example 2.17.

In Example 2.16 the wiring pattern is fixed, but as we show in [spivak2020poly], 𝐏𝐨𝐥𝐲 also supports wiring diagrams for dynamical systems that can change their interaction pattern based on their internal states.

We now come to learners. As mentioned in the introduction, the category 𝐋𝐞𝐚𝐫𝐧 from [fong2019backprop] is better understood as a bicategory which we’ll denote 𝕃 ⁢ 𝐞𝐚𝐫𝐧 . Its objects are sets, Ob ⁡ ( 𝕃 ⁢ 𝐞𝐚𝐫𝐧 )

Ob ⁡ ( 𝐒𝐞𝐭 ) , a 1-morphism (learner) from 𝐴 to 𝐵 consists of a set 𝑃 and maps 𝐼 : 𝐴 × 𝑃 → 𝐵 and ( 𝑅 , 𝑈 ) : 𝐴 × 𝐵 × 𝑃 → 𝐴 × 𝑃 , and a 2-morphism—a morphism between learners—is a function 𝑓 : 𝑃 → 𝑃 ′ making the following squares commute:

𝐴 × 𝑃 𝐵 𝐴 × 𝑃 ′ 𝐵 𝐼 𝐴 × 𝑓 𝐼 ′             𝐴 × 𝐵 × 𝑃 𝐴 × 𝑃 𝐴 × 𝐵 × 𝑃 ′ 𝐴 × 𝑃 ′ ( 𝑅 , 𝑈 ) 𝐴 × 𝐵 × 𝑓 𝐴 × 𝑓 ( 𝑅 ′ , 𝑈 ′ )

(14)

We denote the category of learners from 𝐴 to 𝐵 as 𝕃 ⁢ 𝐞𝐚𝐫𝐧 ⁢ ( 𝐴 , 𝐵 ) ∈ 𝐂𝐚𝐭 .

Proposition 2.18.

For sets 𝐴 , 𝐵 , there is an equivalence of categories

𝕃 ⁢ 𝐞𝐚𝐫𝐧 ⁢ ( 𝐴 , 𝐵 ) ≅ [ 𝐴 ⁢ 𝓎 𝐴 , 𝐵 ⁢ 𝓎 𝐵 ] ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 .

Proof.

See page A. ∎

We will now give a definition that generalizes the bicategory 𝕃 ⁢ 𝐞𝐚𝐫𝐧 , give examples, and discuss intuition. In particular, we define a category-enriched operad 𝕆 ⁢ 𝐫𝐠 , which includes 𝕃 ⁢ 𝐞𝐚𝐫𝐧 as a full subcategory.

Definition 2.19 (The operad 𝕆 ⁢ 𝐫𝐠 ).

We define 𝕆 ⁢ 𝐫𝐠 to be the category-enriched operad defined as follows. The objects of 𝕆 ⁢ 𝐫𝐠 are polynomials: Ob ⁡ ( 𝕆 ⁢ 𝐫𝐠 ) ≔ Ob ⁡ ( 𝐏𝐨𝐥𝐲 ) . For objects 𝑝 1 , … , 𝑝 𝑘 , 𝑝 ′ , the category of maps between them is defined by

𝕆 ⁢ 𝐫𝐠 ⁢ ( 𝑝 1 , … , 𝑝 𝑘 ; 𝑝 ′ ) ≔ [ 𝑝 1 ⊗ ⋯ ⊗ 𝑝 𝑘 , 𝑝 ′ ] ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 .

For any object 𝑝 , the identity on 𝑝 is given by the [ 𝑝 , 𝑝 ] -coalgebra 1 → [ 𝑝 , 𝑝 ] ⁢ ( 1 ) ≅ 𝐏𝐨𝐥𝐲 ⁢ ( 𝑝 , 𝑝 ) that sends 1 ↦ id 𝑝 .

Given objects 𝑝 1 , 1 , … , 𝑝 1 , 𝑗 1 , … , 𝑝 𝑘 , 1 , … , 𝑝 𝑘 , 𝑗 𝑘 , the composition functor

[ 𝑝 1 , 1 ⊗ ⋯ ⊗ 𝑝 1 , 𝑗 1 , 𝑝 1 ] ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 × ⋯ × [ 𝑝 𝑘 , 1 ⊗ ⋯ ⊗ 𝑝 𝑘 , 𝑗 𝑘 , 𝑝 𝑘 ] ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠

× [ 𝑝 1 ⊗ ⋯ ⊗ 𝑝 𝑘 , 𝑝 ′ ]

𝐂𝐨𝐚𝐥𝐠 → [ 𝑝 1 , 1 ⊗ ⋯ ⊗ 𝑝 𝑘 , 𝑗 𝑘 , 𝑝 ′ ]

𝐂𝐨𝐚𝐥𝐠

is given by repeated application of the maps in (9) and Proposition 2.13.

How do we think of a morphism ( 𝑆 , 𝛽 ) : ( 𝑝 1 , … , 𝑝 𝑘 ) → 𝑝 ′ in 𝕆 ⁢ 𝐫𝐠 ? It is a dynamical system which has a set 𝑆 of states. For every state 𝑠 ∈ 𝑆 , we can read out an associated element 𝛽 1 ⁢ ( 𝑠 ) : 𝑝 1 ⊗ ⋯ ⊗ 𝑝 𝑘 → 𝑝 ′ ; we can think of this as a wiring diagram as in Example 2.16 or a generalization thereof. That is, the current state 𝑠 dictates an organization pattern 𝛽 1 ⁢ ( 𝑠 ) : how outputs of the internal systems are aggregated and output from the outer interface, and how feedback from outside is distributed internally.

But so far, this is only the readout of 𝛽 . What’s an input? An input to this system consists of a tuple of outputs 𝑖 ≔ ( 𝑖 1 , … , 𝑖 𝑘 ) ∈ 𝑝 1 ⁢ ( 1 ) × ⋯ × 𝑝 𝑘 ⁢ ( 1 ) , one output for each of the internal systems, together with an input 𝑑 ∈ 𝑝 ′ ⁢ [ 𝛽 1 ⁢ ( 𝑖 ) ] to the outer system.

Imagine you’re the officer in charge of an organization: you’re in charge of the system by which your employees and other resources are arranged, how they send information to each other and the outside world, and how the feedback from the outside world is disbursed to the employees and resources. You see what they do, you see how the world responds, and you update your internal state and hence the system itself, however you see fit. In this image, you as the officer are playing the role of ( 𝑆 , 𝛽 ) , i.e. a morphism in 𝕆 ⁢ 𝐫𝐠 . But even a simple logic gate or adder circuit in a computer—something that doesn’t have a changing internal state or update how resources are connected—counts as a morphism in 𝕆 ⁢ 𝐫𝐠 . Again, the only difference in that case is that the state set 𝑆 ≅ 1 , the way the internal resources are connected—is unchanged by inputs.

Example 2.20.

For any operad, there is an algebra of 0 -ary morphisms. In the case of 𝕆 ⁢ 𝐫𝐠 , this algebra sends 𝑝 ↦ 𝑝 ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 , the category of dynamical systems on 𝑝 , since the unit of ⊗ is 𝓎 and [ 𝓎 , 𝑝 ] ≅ 𝑝 .

Next we’ll give a mathematical language for describing dynamical systems as in Example 2.20 as well as the generalized learners (or officers) described above.

3Toposes of learners

We ended the previous section by defining the (category-enriched) operad 𝕆 ⁢ 𝐫𝐠 and explaining how it generalizes the bicategory 𝕃 ⁢ 𝐞𝐚𝐫𝐧 . In this section we mainly discuss the internal language for each learner. That is, given 𝑝 , 𝑝 ′ ∈ Ob ⁡ ( 𝐏𝐨𝐥𝐲 )

Ob ⁡ ( 𝕆 ⁢ 𝐫𝐠 ) , where perhaps 𝑝

𝑝 1 ⊗ ⋯ ⊗ 𝑝 𝑘 , we discuss the category 𝕆 ⁢ 𝐫𝐠 ⁢ ( 𝑝 ; 𝑝 ′ ) of such learners.

Our first job is to show that every such category is a topos; this will give us access to the Mitchell-Benabou language and Kripke-Joyal semantics—the so-called internal language of the topos and its interpretation [macLane1992sheaves]. We then explain the sorts of things—propositions—that one can express in this language, e.g. the proposition “I will follow the gradient descent algorithm” is a particular case.

3.1The topos of 𝑝 -coalgebras

In this section, we show that for any polynomial 𝑝 , there is a category 𝒞 𝑝 , called the cofree category on 𝑝 , for which we can find an equivalence

𝑝 ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 ≅ 𝒞 𝑝 ⁢

⁢ 𝐒𝐞𝐭

between 𝑝 -coalgebras and functors 𝒞 𝑝 → 𝐒𝐞𝐭 . In fact, the category 𝒞 𝑝 is free on a graph, making it quite easy to understand in certain respects.3

Following [nlab:tree], we define a rooted tree to be a graph 𝑇 whose free category has an initial object, called the root; the idea is that for any node 𝑛 , there is exactly one path from the root to 𝑛 . We denote the nodes of 𝑇 by 𝑇 0 , the root by root 𝑇 ∈ 𝑇 0 , and for any node 𝑛 ∈ 𝑇 0 we denote the set of arrows emanating from 𝑛 by 𝑇 ⁢ [ 𝑛 ] . Note that at the target 𝑛 ′ of any arrow 𝑎 ∈ 𝑇 ⁢ [ 𝑛 ] , there sits another rooted tree with root 𝑛 ′ ; we denote this tree by cod 𝑇 ⁡ ( 𝑎 ) .

Definition 3.1 (The graph 𝖳𝗋𝖾𝖾 𝑝 of 𝑝 -trees).

For a polynomial 𝑝 ∈ 𝐏𝐨𝐥𝐲 , define a 𝑝 -tree to be a tuple ( 𝑇 , 𝜙 1 , 𝜙 ♯ ) , where 𝑇 is a rooted tree, 𝜙 1 : 𝑇 0 → 𝑝 ⁢ ( 1 ) is a function called the position function, and 𝜙 𝑛 ♯ is a bijection

𝜙 𝑛 ♯ : 𝑝 ⁢ [ 𝜙 1 ⁢ ( 𝑛 ) ] → ≅ 𝑇 ⁢ [ 𝑛 ]

for each node 𝑛 ∈ 𝑇 0 , identifying the set of branches in the tree 𝑇 at node 𝑛 with the set of directions in the polynomial 𝑝 at the position 𝜙 1 ⁢ ( 𝑛 ) .

We denote by 𝖳𝗋𝖾𝖾 𝑝 the graph whose vertex set is the set of 𝑝 -trees, and for which an arrow 𝑎 : 𝑇 → 𝑇 ′ is a branch 𝑎 ∈ 𝑇 ⁢ [ root 𝑇 ] with 𝑇 ′

cod 𝑇 ⁡ ( 𝑎 ) .

Example 3.2.

If 𝑝

𝓎 𝐴 for a nonempty set 𝐴 then there is only one 𝑝 -tree: each node has the unique label 𝑝 ⁢ ( 1 ) ≅ 1 and 𝐴 -many branches.

If 𝑝

{ go } ⁢ 𝓎 1 + { stop } ⁢ 𝓎 0 ≅ 𝓎 + 1 then counting the number of nodes gives a bijection between set of 𝑝 -trees and the set ℕ ∪ { ∞ }

∙ stop , ∙ go → ∙ stop , ∙ go → ∙ go → ∙ stop , … , ∙ go → ∙ go → ∙ go → ⋯

Theorem 3.3.

For any polynomial 𝑝 there is an equivalence of categories

𝑝 ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 ≅ 𝐓𝐫𝐞𝐞 𝑝 ⁢

⁢ 𝐒𝐞𝐭

where 𝐓𝐫𝐞𝐞 𝑝 is the free category on the graph 𝖳𝗋𝖾𝖾 𝑝 of 𝑝 -trees.

Proof.

See page A. ∎

∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙
Figure 1:Left: a dynamical system, i.e. coalgebra, for the polynomial 𝑝 ≔ { ∙ , ∙ } 𝓎 2 + ∙ ≅ 2 𝓎 2 + 1 . Right: the 𝑝 -tree corresponding to the node ∙ . 3.2The internal language of 𝑝 ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠

For any category 𝒞 , the category 𝒞 ⁢

⁢ 𝐒𝐞𝐭 of functors 𝒞 → 𝐒𝐞𝐭 forms a topos. In particular, this means that mathematicians have already developed a language and logic that faithfully represents the structures of 𝒞 ⁢

⁢ 𝐒𝐞𝐭 , and we can import it wholesale; see [fong2019seven, Chapter 7] or [macLane1992sheaves, Chapter VI]. Now that we know from Theorem 3.3 that 𝑝 ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 is a topos for any 𝑝 ∈ 𝐏𝐨𝐥𝐲 , we are interested in corresponding language for the topos 𝕃 ⁢ 𝐞𝐚𝐫𝐧 ⁢ ( 𝐴 , 𝐵 )

[ 𝐴 ⁢ 𝓎 𝐴 , 𝐵 ⁢ 𝓎 𝐵 ] ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 of learners, for any sets 𝐴 , 𝐵 ; hence the title “learners’ languages.” However since most of the relevant abstractions work more generally for 𝑝 ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 , we’ll mainly work there.

Not assuming the reader knows topos theory, we will proceed as though we are defining the few relevant concepts from scratch, when in actuality we are merely “reading them off” from the established literature. For example Definition 3.4 simply unpacks the topos-theoretic definition of a logical proposition as a subobject of the terminal object in the topos 𝑝 ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 .

Definition 3.4.

A logical proposition (about 𝑝 -coalgebras) is defined to be a set 𝑃 ⊆ 𝖳𝗋𝖾𝖾 𝑝 of 𝑝 -trees satisfying the condition that if 𝑇 ∈ 𝑃 is a tree in 𝑃 , then for any direction 𝑑 ∈ 𝑇 ⁢ [ root 𝑇 ] , the tree cod 𝑇 ⁡ ( 𝑑 ) ∈ 𝑃 is also a tree in 𝑃 .

Proposition 3.5 gives us an easy way to construct logical propositions about 𝑝 -coalgebras, and hence learners. Namely, it says if we put a condition on the 𝑝 -positions that can show up as labels, and if we put a condition on the codomain map (how directions in the tree lead to new positions), we get a logical proposition. Of course, these aren’t the only ones, but they form a nice special case.

Recall from Definition 3.1 that a 𝑝 -tree is a rooted tree 𝑇 equipped with a position function 𝜙 1 : 𝑇 0 → 𝑝 ⁢ ( 1 ) ; we elide the bijections (earlier denoted 𝜙 𝑛 ♯ : 𝑇 ⁢ [ 𝑛 ] ≅ 𝑝 ⁢ [ 𝜙 1 ⁢ ( 𝑛 ) ] ) in what follows.

Proposition 3.5.

Given 𝑝 ∈ 𝐏𝐨𝐥𝐲 , suppose given subsets

𝑄 ⊆ 𝑝 ⁢ ( 1 ) and 𝑅 ⊆ ∏ 𝑖 ∈ 𝑄 ∏ 𝑑 ∈ 𝑝 ⁢ [ 𝑖 ] 𝑄 .

Then the following set of trees is a logical proposition:

𝑃 𝑄 𝑅 ≔ { 𝑇 ∈ 𝖳𝗋𝖾𝖾 𝑝 ∣ ∀ ( 𝑖 : 𝑇 0 ) . 𝜙 1 ( 𝑖 ) ∈ 𝑄 ∧ ∀ ( 𝑑 : 𝑇 [ 𝑖 ] ) . cod 𝑇 ( 𝑑 ) ∈ ( 𝑅 𝑖 𝑑 ) } .

Proof.

The result is immediate from Definition 3.4. ∎

Example 3.6 (Gradient descent).

The gradient descent, backpropagation algorithm used by each “neuron” in a deep learning architecture can be phrased as a logical proposition about learners. The whole learning architecture is then put together as in [fong2019backprop], or as we’ve explained things above, using the operad 𝕆 ⁢ 𝐫𝐠 from Definition 2.19.

So suppose a neuron is tasked with learning a function ℝ 𝑚 → ℝ 𝑛 , and it has a parameter space ℝ 𝑘 , i.e. we are given a smooth function 𝑓 : ℝ 𝑘 × ℝ 𝑚 → ℝ 𝑛 . We will define a corresponding logical proposition using Proposition 3.5. Define 𝑝 ∈ 𝐏𝐨𝐥𝐲 by

𝑝 ≔ [ ℝ 𝑚 ⁢ 𝓎 ℝ 𝑚 , ℝ 𝑛 ⁢ 𝓎 ℝ 𝑛 ] ≅ ∑ 𝑔 : ℝ 𝑚 ⁢ 𝓎 ℝ 𝑚 → ℝ 𝑛 ⁢ 𝓎 ℝ 𝑛 𝓎 ℝ 𝑚 × ℝ 𝑛 .

Define 𝑄 ⊆ { ( 𝑔 1 , 𝑔 ♯ ) ∣ 𝑔 1 : ℝ 𝑚 → ℝ 𝑛 , 𝑔 ♯ : ℝ 𝑚 × ℝ 𝑛 → ℝ 𝑚 } by saying that 𝑔 1 ⁢ ( 𝑥 ) must be of the form 𝑓 ⁢ ( 𝑎 , 𝑥 ) for some 𝑎 ∈ ℝ 𝑘 in the parameter set and that 𝑔 𝑥 ♯ is given by “pulling back gradient vectors” using the map on cotangent spaces defined by composing with the derivative of 𝑔 1 at 𝑥 , in the usual way.

Now given ( 𝑔 1 , 𝑔 ♯ ) ∈ 𝑄 , we continue with the setup of Proposition 3.5 by defining 𝑅 ⁢ ( 𝑔 1 , 𝑔 ♯ ) : ℝ 𝑚 × ℝ 𝑛 → 𝑄 to say how the learner updates its current parameter value 𝑎 ∈ ℝ 𝑘 given an input-output pair; this again is specified by the deep learning algorithm. Typically, it uses a loss function to calculate a cotangent vector at 𝑓 ⁢ ( 𝑎 , 𝑥 ) which is passed back to a cotangent vector at 𝑎 , and a dual vector of some “learning rate” 𝜖 is traversed.

The details are important for implementation, but not for understanding the idea. The idea is that as long as we say what sorts of maps are allowed (smooth maps with reverse derivatives) and how they update, we have defined a logical proposition.

The logical propositions that come from Proposition 3.5 are very special. More generally, one could have a logical proposition like “whenever I receive two red tokens within three seconds, I will wait five seconds and then send either three blue tokens or two blues and six reds.” As long as this behavior has the “whenever” flavor—more precisely as long as it satisfies the condition in Definition 3.4—it will be a logical proposition in the topos.

3.3Future work

There are many avenues for future work. One is to give more syntactic language—beyond the logical symbols true , false , ∧ , ∨ , ⇒ , ¬ , ∀ , ∃ that exist in any topos—for building logical propositions in the 𝑝 ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 toposes specifically. Another is to understand various modalities in these toposes.

The sort of morphisms between toposes that seem to arise most naturally in this context are not the usual kind—adjoint functors ℰ ⇆ ℰ ′ for which the left adjoint preserves all finite limits, called geometric morphisms—but instead adjoint functors ℰ ⇆ ℰ ′ for which the left adjoint preserves all connected limits. Thus another avenue for future research is to consider how logical and type-theoretic statements move between toposes that are connected in this way.

Appendix AProofs Proof of Proposition 2.4.

It is well-known that composition of functors is a monoidal operation, so it suffices to see that the polynomial (6) is the composite of functors 𝑝 , 𝑞 . To show this, we use the fact that for any set 𝐴 we have a bijection 𝓎 𝐴 ≅ ∏ 𝑎 ∈ 𝐴 𝓎 to calculate the composite

𝑝 ◁ 𝑞

≅ ∑ 𝑖 ∈ 𝑝 ⁢ ( 1 ) ∏ 𝑑 ∈ 𝑝 ⁢ [ 𝑖 ] 𝓎 ◁ ∑ 𝑗 ∈ 𝑞 ⁢ ( 1 ) ∏ 𝑒 ∈ 𝑞 ⁢ [ 𝑗 ] 𝓎

≅ ∑ 𝑖 ∈ 𝑝 ⁢ ( 1 ) ∏ 𝑑 ∈ 𝑝 ⁢ [ 𝑖 ] ∑ 𝑗 ∈ 𝑞 ⁢ ( 1 ) ∏ 𝑒 ∈ 𝑞 ⁢ [ 𝑗 ] 𝓎

≅ ∑ 𝑖 ∈ 𝑝 ⁢ ( 1 ) ∑ 𝑗 : 𝑝 ⁢ [ 𝑖 ] → 𝑞 ⁢ ( 1 ) ∏ 𝑑 ∈ 𝑝 ⁢ [ 𝑖 ] ∏ 𝑒 ∈ 𝑞 ⁢ [ 𝑗 ⁢ ( 𝑑 ) ] 𝓎 ≅ ∑ 𝑖 ∈ 𝑝 ⁢ ( 1 ) ∑ 𝑗 : 𝑝 ⁢ [ 𝑖 ] → 𝑞 ⁢ ( 1 ) 𝓎 ∑ 𝑑 ∈ 𝑝 ⁢ [ 𝑖 ] 𝑞 ⁢ [ 𝑗 ⁢ 𝑑 ]

where the first isomorphism is (3), the second is substitution, the third is the distributive law, and the fourth is properties of exponents. ∎

Proof of Proposition 2.7.

With the formula given, it is clear that the ⊗ -operation is associative (up to isomorphism), and that 𝓎 , which has 𝓎 ⁢ ( 1 ) ≅ 1 and 𝓎 ⁢ [ 1 ] ≅ 𝓎 , is a unit. One can also check that the formula is functorial in 𝑝 and 𝑞 , completing the proof. ∎

Proof of Proposition 2.8.

The natural isomorphism is given by rearranging terms:

𝐏𝐨𝐥𝐲 ⁢ ( 𝑟 ⊗ 𝑝 , 𝑞 )

≅ ∏ 𝑘 ∈ 𝑟 ⁢ ( 1 ) ∏ 𝑖 ∈ 𝑝 ⁢ ( 1 ) ∑ 𝑗 ∈ 𝑞 ⁢ ( 1 ) ∏ 𝑒 ∈ 𝑞 ⁢ [ 𝑗 ] 𝑟 ⁢ [ 𝑘 ] × 𝑝 ⁢ [ 𝑖 ]

≅ ∏ 𝑘 ∈ 𝑟 ⁢ ( 1 ) ∑ 𝜑 1 : 𝑝 ⁢ ( 1 ) → 𝑞 ⁢ ( 1 ) ∏ 𝑖 ∈ 𝑝 ⁢ ( 1 ) ∏ 𝑒 ∈ 𝑞 ⁢ [ 𝜑 1 ⁢ ( 𝑖 ) ] 𝑟 ⁢ [ 𝑘 ] × 𝑝 ⁢ [ 𝑖 ]

≅ ∏ 𝑘 ∈ 𝑟 ⁢ ( 1 ) ∑ 𝜑 1 : 𝑝 ⁢ ( 1 ) → 𝑞 ⁢ ( 1 ) ( ∏ 𝑖 ∈ 𝑝 ⁢ ( 1 ) ∏ 𝑒 ∈ 𝑞 ⁢ [ 𝜑 1 ⁢ ( 𝑖 ) ] 𝑝 ⁢ [ 𝑖 ] ) × ( ∏ 𝑖 ∈ 𝑝 ⁢ ( 1 ) ∏ 𝑒 ∈ 𝑞 ⁢ [ 𝜑 1 ⁢ ( 𝑖 ) ] 𝑟 ⁢ [ 𝑘 ] )

≅ ∏ 𝑘 ∈ 𝑟 ⁢ ( 1 ) ∑ 𝜑 : 𝑝 → 𝑞 ∏ 𝑖 ∈ 𝑝 ⁢ ( 1 ) ∏ 𝑒 ∈ 𝑞 ⁢ [ 𝜑 1 ⁢ ( 𝑖 ) ] 𝑟 ⁢ [ 𝑘 ]

≅ 𝐏𝐨𝐥𝐲 ⁢ ( 𝑟 , ∑ 𝜑 : 𝑝 → 𝑞 𝓎 ∑ 𝑖 ∈ 𝑝 ⁢ ( 1 ) 𝑞 ⁢ [ 𝜑 1 ⁢ ( 𝑖 ) ] ) ≅ 𝐏𝐨𝐥𝐲 ⁢ ( 𝑟 , [ 𝑝 , 𝑞 ] ) .

In order, these isomorphisms are given by: unfolding the definition of morphisms in 𝐏𝐨𝐥𝐲 , distributivity, products commuting with products, definition of morphisms in 𝐏𝐨𝐥𝐲 , rules of exponents, and Eq. 7’s definition of [ 𝑝 , 𝑞 ] , respectively. ∎

Proof of Proposition 2.13.

We need to give not only the functor 𝜆 : 𝑝 ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 × 𝑞 ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 → ( 𝑝 ⊗ 𝑞 ) ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 , for any 𝑝 , 𝑞 ∈ 𝐏𝐨𝐥𝐲 but also a functor { 1 } → 𝓎 ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 , which we can identify with a 𝓎 -coalgebra; we take the latter to be the unique function 1 → 𝓎 ◁ 1 . For the former, one could proceed abstractly using the fact that there is a duoidal structure on 𝐏𝐨𝐥𝐲

( 𝑝 ◁ 𝑠 ) ⊗ ( 𝑞 ◁ 𝑡 ) → ( 𝑝 ⊗ 𝑞 ) ◁ ( 𝑠 ⊗ 𝑡 ) .

Indeed, since for sets 𝑆 , 𝑇 we have 𝑆 ⊗ 𝑇 ≅ 𝑆 × 𝑇 , the result will follow from the properties of duoidal structures (applied in the case where 𝑠 ≔ 𝑆 and 𝑡 ≔ 𝑇 are constant polynomials). However, for the reader’s convenience, we will give the map 𝜆 : 𝑝 ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 × 𝑞 ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 → ( 𝑝 ⊗ 𝑞 ) ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 more explicitly.

Given 𝛽 : 𝑆 → 𝑝 ◁ 𝑆 and 𝛾 : 𝑇 → 𝑞 ◁ 𝑇 , we define a function

𝑆 ⁢ 𝑇

→ ( 𝑝 ⊗ 𝑞 ) ◁ ( 𝑆 ⁢ 𝑇 ) ≅ ∑ 𝑖 ∈ 𝑝 ⁢ ( 1 ) ∑ 𝑗 ∈ 𝑞 ⁢ ( 1 ) ( 𝑆 ⁢ 𝑇 ) 𝑝 ⁢ [ 𝑖 ] × 𝑞 ⁢ [ 𝑗 ]

( 𝑠 , 𝑡 )

↦ ( 𝑖 ≔ 𝛽 1 ( 𝑠 ) , 𝑗 ≔ 𝛾 1 ( 𝑡 ) , ( 𝑑 , 𝑒 ) ↦ ( 𝛽 𝑖 ♯ ( 𝑑 ) , 𝛾 𝑗 ♯ ( 𝑒 ) ) .

This is natural in 𝑆 , 𝑇 , which makes 𝜆 a functor for any 𝑝 , 𝑞 . One can check that all the axioms of a lax monoidal functor are verified, in the sense that the required diagrams commute up to natural isomorphism. ∎

Proof of Proposition 2.18.

On one hand, an object in 𝕃 ⁢ 𝐞𝐚𝐫𝐧 ⁢ ( 𝐴 , 𝐵 ) as described in (2) consists of a set 𝑃 and functions 𝐴 × 𝑃 → 𝐵 and 𝐴 × 𝐵 × 𝑃 → 𝐴 and 𝐴 × 𝐵 × 𝑃 → 𝑃 . On the other hand, we have [ 𝐴 ⁢ 𝓎 𝐴 , 𝐵 ⁢ 𝓎 𝐵 ] ≅ 𝐵 𝐴 ⁢ 𝐴 𝐴 ⁢ 𝐵 ⁢ 𝓎 𝐴 ⁢ 𝐵 by Example 2.9, so a coalgebra 𝑃 → [ 𝐴 ⁢ 𝓎 𝐴 , 𝐵 ⁢ 𝓎 𝐵 ] ◁ 𝑃 consists of a function 𝑃 → 𝐵 𝐴 , a function 𝑃 → 𝐴 𝐴 ⁢ 𝐵 , and a function 𝑃 → 𝑃 𝐴 ⁢ 𝐵 . The two descriptions can be identified by currying. The [ 𝐴 ⁢ 𝓎 𝐴 , 𝐵 ⁢ 𝓎 𝐵 ] ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 morphisms

𝑃 𝐵 𝐴 ⁢ 𝐴 𝐴 ⁢ 𝐵 ⁢ 𝑃 𝐴 ⁢ 𝐵 𝑃 ′ 𝐵 𝐴 ⁢ 𝐴 𝐴 ⁢ 𝐵 ⁢ ( 𝑃 ′ ) 𝐴 ⁢ 𝐵

are easily seen to coincide with those shown in (14). ∎

Proof of Theorem 3.3.

It is well-known that 𝒞 ⁢

⁢ 𝐒𝐞𝐭 is equivalent to the category of discrete opfibrations over 𝒞 via the category-of-elements construction. When 𝒞 is free on a graph 𝐺 , the category of elements for any functor ℎ : 𝒞 → 𝐒𝐞𝐭 is also free on a graph, say 𝐻 . In this case the opfibration can be identified with a graph homomorphism 𝜋 : 𝐻 → 𝐺 with the property (“opfib”) that for any vertex ℎ ∈ 𝐻 , the function on arrows 𝐻 ⁢ [ ℎ ] → ≅ 𝐺 ⁢ [ 𝜋 ⁢ ( ℎ ) ] induced by 𝜋 is a bijection. Under this correspondence, a morphism ℎ → ℎ ′ of copresheaves is identified with a graph homomorphism 𝑓 : 𝐻 → 𝐻 ′ for which 𝜋

𝜋 ′ ∘ 𝑓 .

Thus we have reduced to showing that there is an equivalence between 𝑝 ⁢

⁢ 𝐂𝐨𝐚𝐥𝐠 and the category of those graph homomorphisms 𝜋 : 𝐻 → 𝖳𝗋𝖾𝖾 𝑝 that have the opfib property. Suppose given a 𝑝 -coalgebra 𝛽 : 𝑆 → 𝑝 ◁ 𝑆 ; it includes a function 𝛽 1 : 𝑆 → 𝑝 ⁢ ( 1 ) and for each 𝑠 ∈ 𝑆 a function 𝛽 𝑠 ♯ : 𝑝 ⁢ [ 𝛽 1 ⁢ ( 𝑠 ) ] → 𝑆 . We define the corresponding graph 𝐺 𝑆 , 𝛽 to have vertex set 𝑆 , and each 𝑠 ∈ 𝑆 to have 𝑝 ⁢ [ 𝛽 1 ⁢ ( 𝑠 ) ] -many outgoing arrows; the target of each outgoing arrow 𝑑 ∈ 𝑝 ⁢ [ 𝛽 1 ⁢ ( 𝑠 ) ] is defined to be 𝛽 𝑠 ♯ ⁢ ( 𝑑 ) . The graph homomorphism 𝜋 : 𝐺 𝑆 , 𝛽 → 𝖳𝗋𝖾𝖾 𝑝 is defined inductively: for any 𝑠 ∈ 𝑆 , the 𝑝 -tree 𝜋 ⁢ ( 𝑠 ) has root labeled 𝛽 1 ⁢ ( 𝑠 ) , and for each outgoing branch 𝑑 ∈ 𝑝 ⁢ [ 𝛽 1 ⁢ ( 𝑠 ) ] the target vertex is assigned the label 𝛽 1 ⁢ ( 𝑠 ′ ) , where 𝑠 ′ ≔ 𝛽 𝑠 ♯ ⁢ ( 𝑑 ) , and for each outgoing branch 𝑑 ′ ∈ 𝑝 ⁢ [ 𝛽 1 ⁢ ( 𝑠 ′ ) ] the target vertex is assigned the label 𝛽 1 ⁢ ( 𝑠 ′′ ) where 𝑠 ′′ ≔ 𝛽 𝑠 ′ ♯ ⁢ ( 𝑑 ′ ) , and so on. It is clear that 𝜋 satisfies the opfib property, since it assigns to each vertex 𝑠 in the graph 𝐺 𝑆 , 𝛽 a vertex in 𝖳𝗋𝖾𝖾 𝑝 (the 𝑝 -tree 𝜋 ⁢ ( 𝑠 ) ) with the same set 𝑝 ⁢ [ 𝛽 1 ⁢ ( 𝑠 ) ] of outgoing arrows.

Conversely, given a graph homomorphism 𝜋 : 𝐺 → 𝖳𝗋𝖾𝖾 𝑝 with the opfib property, let 𝑆 𝐺 be the set of vertices in 𝐺 . The required coalgebra map 𝛽 : 𝑆 𝐺 → 𝑝 ◁ 𝑆 𝐺 consists of a function 𝛽 1 : 𝑆 𝐺 → 𝑝 ⁢ ( 1 ) and a function 𝛽 𝑠 ♯ : 𝑝 ⁢ [ 𝛽 1 ⁢ ( 𝑠 ) ] → 𝑆 𝐺 for every 𝑠 ∈ 𝑆 𝐺 . We take the function 𝛽 1 to send vertex 𝑠 to the root label 𝜙 ⁢ ( root 𝜋 ⁢ ( 𝑠 ) ) for tree 𝜋 ⁢ ( 𝑠 ) . Since we have a bijection 𝑝 ⁢ [ 𝛽 1 ⁢ ( 𝑠 ) ] ≅ 𝐺 ⁢ [ 𝑠 ] , we can take 𝛽 𝑠 ♯ to simply be the target function 𝐺 ⁢ [ 𝑠 ] → 𝑆 𝐺 for the graph 𝐺 .

It is a straightforward calculation to check that these two constructions are mutually inverse, and to check that graph homomorphisms over 𝖳𝗋𝖾𝖾 𝑝 correspond bijectively to morphisms of 𝑝 -coalgebras. ∎

\printbibliography Report Issue Report Issue for Selection Generated by L A T E xml Instructions for reporting errors

We are continuing to improve HTML versions of papers, and your feedback helps enhance accessibility and mobile support. To report errors in the HTML that will help us improve conversion and rendering, choose any of the methods listed below:

Click the "Report Issue" button. Open a report feedback form via keyboard, use "Ctrl + ?". Make a text selection and click the "Report Issue for Selection" button near your cursor. You can use Alt+Y to toggle on and Alt+Shift+Y to toggle off accessible reporting links at each section.

Our team has already identified the following issues. We appreciate your time reviewing and reporting rendering errors we may not have found yet. Your efforts will help us improve the HTML versions for all readers, because disability should not be a barrier to accessing research. Thank you for your continued support in championing open access for all.

Have a free development cycle? Help support accessibility at arXiv! Our collaborators at LaTeXML maintain a list of packages that need conversion, and welcome developer contributions.