Back to search

University of Southampton

Category-theoretic data structures and algorithms for learning polynomial circuits

Abstract

dc:description.abstract

The purpose of this thesis is to provide practical, high-performance tools for working with string diagrams for the specific application of machine learning. The thesis consists of two main lines of research towards this aim. In Part I, we define a family of categories of differentiable circuits suitable for machine learning. This construction is made in a modular way: we first give an alternative axiomatisation of Reverse Derivative categories which is then used to prove a functional completeness result showing that these circuits are sufficiently expressive. We then show how ‘gradient-like’ learning can be understood in terms of morphisms of these categories and discuss how to generalise gradient-based methods as applied to neural networks to new settings by varying the ‘underlying arithmetic’ of models. Part II of the thesis is concerned with how to represent and manipulate large string diagrams, specifically with an eye to those defined in Part I. We develop data structures and define efficient algorithms for tensor and composition of string diagrams in terms of simple linear-algebraic operations. We show that complexity of operations is linear in the size of the resulting diagram and validate our claims with empirical evidence that our approach can handle diagrams constructed from millions of generators. Finally, we give a graphical calculus allowing terms of non-strict monoidal categories to be represented by our data structure, which in turn yields novel proofs of Mac Lane’s strictness and coherence theorems.

Degree

thesis:*
Name dc:type.qualificationname
Ph.D.
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Southampton
Year dc:date.issued
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Wilson, Paul William
Advisor dc:contributor.advisor
  • Rathke, Julian

Rights

Language dc:language
English, eng

Chain of custody

source
Harvested from
University of Southampton
Base URL
eprints.soton.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Wilson, Paul William. Category-theoretic data structures and algorithms for learning polynomial circuits. doctoral thesis, University of Southampton, 2023.