Lecture notes on rough paths and applications to machine learning

Introduction

These lecture notes introduce a mathematical concept, that of describing a path through its iterated integrals, and explain how the resulting theory can be used in data science and machine learning tasks involving streamed data. The study of iterated integrals has deep-seated roots in both mathematics and physics, with the early mathematical work stretching back at least to a series of papers by K-T. Chen, see e.g. . Chen’s contribution spanned various domains, with a central emphasis being on homotopy theory and the use of path space integration to illuminate the interplay between topology and analysisAn overview of Chen’s contributions can be found in the introduction to his collected works . Without providing an exhaustive historical narrative, related contemporaneous developments also appeared in physics, in the form of the Dyson exponential , and the subsequent work of W. Magnus . Later insights revealed how similar principles can be applied in the control theory of nonlinear systems, catalysed by the work of Fliess . Consequently, what we term the “signature” often appears as the eponymous Chen-Fliess series in certain parts of the literature.

By building on these foundations, B. Hambly and T. Lyons showed in a landmark 2010 paper how, for two continuous paths of finite 1-variation, the agreement of signatures coincides with the notion that the pair of paths are tree-like equivalent. The collection of iterated integrals thus determines a path up to tree-like equivalence analogously to the way in which integrable functions on the circle are determined by their Fourier coefficients, up to Lebesgue-null sets.

A later, no less influential development was the theory of rough paths, which was developed by T. Lyons as a branch of stochastic analysis in the 1990s , . A core achievement of this theory is to show how a path-by-path and robust notion of solution can be ascribed to differential equations of the form:

This construction holds even in cases where the input path $x$ may be highly irregular as a function of time. The crux is to enhance $x$ with iterated integral type terms, up to certain order, to form a rough path. The Hambly and Lyons theorem allows an extension to the setting of (geometric) rough paths . A breakthrough in merging these ideas with modern data science tools came in 2013, when B. Graham combined the signature features of pen strokes with sparse neural network methods to win part of an international competition on Chinese handwriting recognition.

The purpose of these notes is thus to give an account of the extraordinarily rapid progress of the application of this mathematics to data science since these initial developments. By adopting simplifications, opting for a streamlined treatment over generality, we hope that this text can be used by researchers and graduate students seeking a quick introduction to the subject from a cross section of disciplines including mathematics, data science, computer science statistics and engineering.

Our presentation proceeds in the order of abstraction-first, applications-second. Accordingly, our first section treats the fundamental mathematical underpinnings of the theory, focusing on the core properties of the signature transform. We freely make compromises to maintain the tempo. One such concession is to develop the theory specifically for continuous, finite-length paths, and not the more delicate cases of (geometric) rough paths or discontinuous paths. In the same vein, we keep algebraic notions to a minimum. A pivotal theme throughout the section is how the iterated integral perspective on signatures can be enriched by treating the ensemble as the solution to a particular controlled differential equation. This observation often facilitates simpler and more direct proofs. It also highlights another key theme of the subject: the idea of controlled differential equations as paradigmatic examples of functions on path space. The coordinate iterated integrals emerge as a universal feature set, or “basis”, for functions on path space, and serve as a foundation for functional approximation. To capture this idea using mathematics, we need to introduce unparametrised path space and understand some elementary topology on this space. The section culminates in a practical demonstration illustrating how this concept can be applied to execute nonlinear regression on path space using signature features.

Signature methods offer powerful techniques for handling streamed data, although they pose challenge themselves due to the inherently high dimensionality of the feature space. In statistical learning, kernel methods have emerged as effective tools for managing such difficulties for vector-valued data in an inner product space. Kernel methods, including signature kernel methods, can be applied in tasks where it is sufficient to know only the inner products of observations and not the exact values of the features themselves. Our second section develops the core concepts behind signature kernel methods building upon the foundations established in the first section. The exposition deliberately mirrors that of classical kernel methods for vector-valued data. We establish the main theoretical properties of these kernels – universality and characteristicness – and illustrate their practical implications for concrete applications, such as distribution regression for streamed data. Computational considerations predominate when assessing the effectiveness of a kernel; a kernel only becomes useful if there is an efficient means for evaluating it at a pair of observations. For a certain class of signature kernels, this can be achieved through solving a partial differential equation known as the signature kernel PDE. This approach is particularly effective for sufficiently smooth input paths, allowing for efficient computation of inner products.

The concluding section provides an overview of the theory of rough differential equations, which naturally extends the concept of a controlled differential equation. In deep learning, neural ordinary differential equation (Neural ODE) models have recently emerged, offering a continuous-time approach for modelling the latent state of residual neural networks. Neural controlled differential equations (Neural CDEs) are continuous-time analogues of recurrent neural networks and provide a memory-efficient way to model functions of incoming data streams. When the driving signal is Brownian, the resulting neural stochastic differential equations (Neural SDEs) can be used as powerful generative models for time series. These models can be studied in a unified way by using the overarching framework of neural rough differential equation (Neural RDEs). We provide an overview of the fundamental constituents of rough path theory, placing emphasis on how they are used in practice through numerical schemes, such as the log-ODE method, for the training of Neural CDEs, SDEs and RDEs.

These notes have emerged from a series of lecture courses delivered at Imperial College London by the authors during the periods of 2020 to 2021, initially by TC and then, from 2022 to 2024, by CS. We extend our gratitude to successive cohorts of students in the MSc in Mathematics and Finance programme, as well as the students in the EPSRC CDT in the Mathematics of Random Systems, whose insightful comments and feedback have enriched these sessions and hardened up the presentation of these notes. Special acknowledgments are owed to Nicola Muca Cirone, Francesco Piatti, Will Turner, and Nikita Zozoulenko for their invaluable feedback and discussions on earlier versions of these notes. TC is grateful to the Institute of Advanced Study where he spent the academic year 2023-24, with the generous support of a Erik Ellentuck Fellowship, and where a first draft of these notes were finalised.

Thomas Cass, Princeton Cristopher Salvi, London

Chapter 1 The signature transform

We will refer to (1.1) as a controlled differential equation (CDE), usually adopting the more concise notation expressed in terms of differentials

This notation makes it apparent that the role of the function $f$ is to model how, at every point along the output trajectory, changes in $y$ are brought about by changes in $x$. Before we develop these points, we recall the definition of a vector field.

If we assume that $f$ in equation (1.2) is $C^{k}$, $f$ can be equivalently defined as a linear map $v\mapsto f_{v}$ from $V$ into the (real) vector space $\mathcal{T}^{k}\left(W\right)$ of $C^{k}$-vector fields on $W$, where $f_{v}$ and $f$ are related by

With this point of view, one can use the alternative notation for the CDE (1.2)

In particular, if the driving path $x$ is differentiable, then this CDE becomes $\dot{y}_{t}=f_{\dot{x}_{t}}\left(y_{t}\right)$ so that $y$ is the integral curve of the time-dependent vector field

The CDE terminology originates from optimal control theory, where typically some desired feature of the output $y$ is realised by appropriately selecting some control $\dot{x}$.

A vector field $h$ in $\mathcal{T}\left(W\right)$, defined below as a smooth function from $W$ to itself, can equivalently be defined as a first-order differential operator acting on functions in $C^{\infty}(W).$ From this point of view $h:C^{\infty}(W)\rightarrow C^{\infty}(W)$ is the linear map

A choice of basis $\left\{b_{i}\right\}_{i=1}^{n}$ for $W$ gives rise to a global coordinate system$\ w=\left(w^{1},...,w^{n}\right)$ on $W\,,$ which then allows us to write $h\phi$ in terms of partial derivatives

It can be convenient to write as $h\phi=h^{i}\partial_{i}\phi$, implicitly summing over repeated indices.

Viewing vector fields as differential operators allows us to consider their composition as well as the important operation of taking their Lie brackets.

Suppose that $g$ and $h$ are two vector fields in $\mathcal{T}\left(W\right),$ then the composition $gh$ is the differential operator defined by $\left(gh\right)\phi=g\left(h\phi\right)$ for all $\phi$ in $C^{\infty}\left(W\right).$ Furthermore, the Lie bracket of $f$ and $g$ is the differential operator defined by $\left[g,h\right]\phi=\left(gh-hg\right)\phi$ for all $\phi$ in $C^{\infty}\left(W\right).$

The Lie bracket $\left[g,h\right]$ is in fact another vector field in the sense that it is a first-order differential operator, as can be seen from the fact that the terms involving second-order derivatives disappear:

As a consequence $\left[\cdot,\cdot\right]:\mathcal{T}\left(W\right)\times\mathcal{T}\left(W\right)\rightarrow\mathcal{T}\left(W\right)$ is a bilinear map.

One of the achievements of rough path theory is to give a framework for interpreting solutions to controlled differential equations when the driving signal $x$ is very far from differentiable. The focus of this chapter and the next will not be on this theory, but many of the underpinning ideas are nonetheless inspired by it. A common theme is the central role will be played by the collection of iterated integrals of the path $x$, and it is with an our account of their properties that we begin.

1.1 Coordinate iterated integrals

To understand why iterated integrals emerge from studying CDEs, we recall the classical method of Picard iteration for constructing solutions to CDEs. The basic idea is to inductively define a sequence of paths $\left(y^{n}\right)_{n=0}^{\infty}$, the Picard iterates, as follows

Provided sufficient regularity of the data $f$ and $x$ is assumed, the sequence of Picard iterates can be shown to converge to a limit in a suitable sense. A final step is then to show that this limit solves (1.1), and to understand whether this solutions is unique.

We consider a simple special case of this scheme when $f:W\rightarrow L\left(V,W\right)$ is a linear function; that is, when $f$ belongs to the space $L\left(W,L\left(V,W)\right)\right)$. If we allow that $x$ is differentiable, a general Picard iterate then has the form

where $f^{\left(0\right)}=$id${}_{W},$ the identity function on $W\,$, and $f^{\otimes k}\left(y\right):V\times V\times....\times V\rightarrow W$ is the $k$-fold multilinear map defined by

Multilinear maps can be better understood through the notion of tensor product that we now recall.

Let $S$ and $T$ be two vector spaces. The tensor product of $S$ and $T$ is a vector space $S\otimes T$ together with a bilinear map from $S\times T$ to $S\otimes T\,,$ whose action is denoted by $\left(s,t\right)\mapsto s\otimes t,$ which has the universal property that for any bilinear function $\phi:S\times T\rightarrow U$ into another vector space $U$ there exists a unique linear map $\hat{\phi}:S\otimes T\rightarrow U$ such that $\phi\left(s,t\right)=\hat{\phi}\left(s\otimes t\right).$

We will most often use this in the case $V=S=T$ when we will write $V^{\otimes 2}$ as short hand for $V\otimes V.$ The definition is associative, $V_{1}\otimes(V_{2}\otimes V_{3})$ and $\left(V_{1}\otimes V_{2}\right)\otimes V_{3}$ are isomorphic, and hence we can write $V^{\otimes k}$ unambiguously to denote the $k$-fold tensor product of $V.$ Under this isomorphism we have that $v_{1}\otimes\left(v_{2}\otimes v_{3}\right)=\left(v_{1}\otimes v_{2}\right)\otimes v_{3}$ and thus $v_{1}\otimes v_{2}\otimes v_{3}$ is also well defined. As a consequence of the universal property, the multilinear map $f^{\otimes k}\left(y\right)$ in (1.5) is such that

for a unique linear map $\widehat{f^{\otimes k}\left(y\right)}:V^{\otimes k}\to W$. To ease the notational burden we abuse notation and refer to this map also as $f^{\otimes k}\left(y\right)$. It will also be unwieldy to write $\otimes$ each time a tensor product of vectors occurs and so we adopt the more concise notation $v_{1}...v_{k}$ instead of $v_{1}\otimes...\otimes v_{k}$. Using this and the linearity of the integral we write the $n^{\text{th}}$ Picard iterate (1.4) as

is the $k$-fold iterated integral of $x.$ The assumption that $x$ is differentiable is an unnecessarily strong one to define these iterated integrals. For a less restrictive notion, we will need the following way to quantify the regularity of a path.

Let $p\geq 1$ be a real number. The $p$-variation of a path $x:[a,b]\to V$ be on any subinterval $[s,t]\subset[a,b]$ is the following quantity

where $||\cdot||$ is any norm on $V$, and the supremum is taken over all partitions $\mathcal{D}$ of the interval $[s,t]$, i.e. over all increasing finite sequences such that $\mathcal{D}=\{s=k_{0}<k_{1}<...<k_{r}=t\}$. We say that $x$ has finite $p$-variation on $[s,t]$ if $\left\lVert x\right\rVert_{p,[s,t]}<\infty$. If $x$ has finite $1$-variation we will say that $x$ has bounded variation (or has finite length).

We will denote by $C_{p}([a,b],V)$, to be the space of continuous paths from the interval $[a,b]$ to $V$ which have finite $p$-variation. If the intervals can be understood from the context, then we use the abridged notation $\left\lVert x\right\rVert_{p}$ and $C_{p}(V)$ respectively in place of $\left\lVert x\right\rVert_{p,[s,t]}$ and $C_{p}([a,b],V)$.

Using the definition of integration theory due to Young (e.g. [37, Chapter 6]), the integrals in equation (1.7) will continue to exist whenever $x$ is in $C_{p}([a,b],V)$ and for any $1\leq p<2$. As these objects will appear repeatedly, we introduce the notation

to denote the $k$-fold iterated integral in (1.7). A central theme in the sequel will be the way in which the collection of all such iterated integrals determines the effect of the path $x$ on general non-linear CDEs.

For any path $x\in C_{p}([a,b],V)$ with $p\in[1,2)$ and any subinterval $[s,t]\subset[a,b]$, the signature transform (ST) $S(x)_{[s,t]}$ of $x$ on $[s,t]$ is defined as the following collection of iterated integrals

When it is clear from the context, we will suppress the dependence on the interval and instead denote the ST of $x$ by $S(x)$.

As with the ST, we omit reference to the interval $S_{n}\left(x\right)$ when the interval can be inferred from the context.

The iterated integrals characterized by the ST have been the object of numerous mathematical studies prior to rough paths. Initially presented in a geometric framework by Chen in and later by Fliess and Kawski in control theory, many researchers explored this sequence of iterated integrals of a path to derive pathwise Taylor series for solutions of differential equations. In fact, the ST is sometime referred to as the ”Chen-Fliess series”. This book delves into integrating the ST in machine learning to model functions on sequential data.

1.2 Algebras of tensors

In this book we are interested in the setting where $U$ is the set of continuous paths of bounded $p$-variation for $p\in[1,2)$. Monomials will be given by terms of the ST. This motivates the need to study the algebraic structure of the space of tensors $\prod_{i=0}^{\infty}V^{\otimes i}$. Subsequently, the algebraic and anlytic properties of the ST will yield the fundamental approximation result for the ST in Theorem 1.4.7 which will be derived as a simple consequence of the Stone-Weierstrass Theorem.

It will be important to have the structure of an algebra on the product space ${\textstyle\prod\nolimits_{i=0}^{\infty}}V^{\otimes i}$. To introduce this, we observe from the universal property of the tensor product that the space $V^{\otimes n}\otimes V^{\otimes m}$ is isomorphic to $V^{\otimes\left(n+m\right)}$ and therefore that $v_{m}v_{n}$ is a well-defined element of $V^{\otimes\left(n+m\right)}.$ This allows to define an associative product on ${\textstyle\prod\nolimits_{i=0}^{\infty}}V^{\otimes i}$ which is compatible with the tensor products on the individual levels $V^{\otimes i}$. By this we mean that if $\mathfrak{i}_{n}:V^{\otimes n}\hookrightarrow$ ${\textstyle\prod\nolimits_{i=0}^{\infty}}V^{\otimes i}$ denotes the canonical inclusion, then the tensor product on ${\textstyle\prod\nolimits_{i=0}^{\infty}}V^{\otimes i}$ satisfies

for every $n$ and $m.$ The following definition provides this.

Suppose that $v=\left(v_{0},v_{1},...\right)$ and $w=\left(w_{0},w_{1},...\right)$ are two elements of ${\textstyle\prod\nolimits_{i=0}^{\infty}}V^{\otimes i}.$ Then we define the (extended) tensor product $v\cdot w=\left(z_{0},z_{1},...\right)$ as

The product space ${\textstyle\prod\nolimits_{i=0}^{\infty}}V^{\otimes i}$ equipped with the product $\cdot$ is an algebra. Sometimes it is convenient to interpret elements of ${\textstyle\prod\nolimits_{i=0}^{\infty}}V^{\otimes i}$ as formal series of tensors; that is, to identify $v=\left(v_{0},v_{1},...\right)$ with $\sum_{i=0}^{\infty}v_{i}$. We denote by $T\left(\left(V\right)\right)$ the algebra of formal tensor series with the product (1.11).

The tensor algebra $T(V)$ has the following universal property, which in fact can be used as an alternative way to uniquely characterise it (up to isomorphism).

Let $A$ be an associative algebra and let $F:V\rightarrow A$ be a linear map. Then there exists a unique algebra homomorphism $\hat{F}:T\left(V\right)\rightarrow A$ which extends $F$ in the sense that $F=\hat{F}\circ\mathfrak{i}_{1},$where $\mathfrak{i}_{1}:V\hookrightarrow T\left(V\right)$ is the canonical inclusion.

Let End$\left(W\right)=L\left(W,W\right)$ denote the algebra of endomorphisms of $W$ with an (associative) product given by $A\ast B=B\circ A$ where $\circ$ denotes the usual composition of linear maps. In the case of our earlier discussion of a differential equation with linear vector fields we used $f$ in $L\left(W,L\left(V,W\right)\right)$. Any such $f$ is determined by the map $F$ in $L\left(V,\text{End}\left(W\right)\right)$ through $F\left(v\right)\left(w\right)=f\left(w\right)\left(v\right).$ By using the universal property of the tensor algebra, we can extend $F$ to an algebra homomorphism $\hat{F}$ on $T\left(V\right)$ into $($End$\left(W\right),\ast).$ We note that for any $k$ this map is determined by

With this formulation, we can further simplify the $n^{th}$ Picard iterate (1.6) by writing

Given inner products on $V$ and $W$, we can endow $V\otimes W$ with a canonical inner product.

Let $V,W$ be vector spaces endowed with the inner-products $\left\langle\cdot,\cdot\right\rangle_{V}$ and $\left\langle\cdot,\cdot\right\rangle_{W}$ respectively. Define the (Hilbert-Schmidt) inner product on $V\otimes W$ by

for any $v_{1},v_{2}\in V$ and $w_{1},w_{2}\in W$.

Thus, we can equip $V^{\otimes k}$ with the norm determined by

In the sequel, we will consider Banach spaces $E\subset T((V))$ defined as follows

in which the norm will typically be an $l_{q}$-norm, with $q$ in $[1,\infty)$, of the form

Two cases are of particular interest. When $q=2$ the resulting space is a Hilbert space with the inner product given by

If $q=1$ then $(E,\left\lVert\cdot\right\rVert)$ is a Banach algebra, i.e. $\left\lVert ab\right\rVert\leq\left\lVert a\right\rVert\left\lVert b\right\rVert$, as is easily verified.

1.3 Functions on the range of the signature transform

In this section we outline how the dual space $T(V)^{*}$ of the tensor algebra $T(V)$ can be constructed from the dual space $V^{*}$ of $V$. Dual elements in $T(V)^{*}$, when restricted to functionals on the range of the ST, will furnish the main building blocks (or monomials) of our Taylor expansion for functions on path space.

and by linearity. In particular, we see that $e_{i}^{\ast}\left(v\right)=v_{i}$ when $v=\sum_{i=1}^{d}v_{i}e_{i}.$ This leads naturally to a dual basis for $\left(V^{\ast}\right)^{\otimes k}$.

Given a multi-index $I=\left(i_{1},...,i_{k}\right)$ of length $\left|I\right|=k$ and a basis for $V$ as above, we denote $e_{I}=e_{i_{1}}...e_{i_{k}}$. The set $\left\{e_{I}:\left|I\right|=k\right\}$ is a basis for $V^{\otimes k}$ and so it also has a dual basis whose elements we denote by $e_{I}^{\ast}.$

Any choice of basis for $V$ induces a vector space isomorphism between $\left(V^{\otimes k}\right)^{\ast}$ and $\left(V^{\ast}\right)^{\otimes k}$ which is characterised by

This isomorphism is, in fact, independent of the original choice of basis for $V$, as can be easily shown, and as such we will often implicitly identify elements of $\left(V^{\otimes k}\right)^{\ast}$ with the corresponding element of $\left(V^{\ast}\right)^{\otimes k}$ under this canonical isomorphism. A similar observation can be made for the dual space $T\left(V\right)^{\ast}$, although more care is needed because $T(V)$ is infinite dimensional; the follow lemma describes the situation.

The vector spaces $T\left(\left(V^{\ast}\right)\right)$ and $T\left(V\right)^{\ast\ }$can be identified through the explicit isomorphism $\Phi:T\left(\left(V^{\ast}\right)\right)\rightarrow T\left(V\right)^{\ast\ }$

Note that here $f_{k}$ in $\left(V^{\ast}\right)^{\otimes k}$ is identified with $\left(V^{\otimes k}\right)^{\ast}$ in the way described above.

By considering the restriction of the linear map (1.13) to $T\left(V^{\ast}\right)$ we can identify $T\left(V^{\ast}\right)$ with a subspace of $T\left(\left(V\right)\right)^{\ast}$. This is because $\Phi_{f}$ can be extended to $T\left(\left(V\right)\right)^{\ast}$ whenever $f$ is a tensor polynomial.

By regarding $e_{I}^{\ast}\in\left(V^{\otimes k}\right)^{\ast}\cong\left(V^{\ast}\right)^{\otimes k}$ as an element of $T\left(V^{\ast}\right)$ under the usual inclusion of $\left(V^{\ast}\right)^{\otimes k}$ into $T\left(V^{\ast}\right),$ the previous remark allows us to define a collection of scalars

as $I$ ranges over all multi-indices $I$ of finite length. This offers another view on the signature which is captured by the following definition.

Let $\{e_{i}\}_{i=1,..,d}$ be a basis for $V$ with corresponding dual basis $\{e_{i}^{*}\}_{i=1,...d}$ and suppose that $1\leq p<2$. If $x$ is in $C_{p}(V)$ and $I=\left(i_{1},...,i_{k}\right)$ is a multi-index of integers from $\{1,...,d\}$, then the coordinate iterated integral $S(x)^{I}$ is the real number given by $S(x)^{I}=e_{I}^{*}(S(x))$.

2 Analytical properties

We will now apply the tools we have developed for studying tensors to understand some important analytic properties of the ST. Firstly, the ST exhibits invariance under reparameterizations; this essentially allows the ST to act as a filter that removes an infinite dimensional group of symmetries given by time reparameterizations. Secondly, the factorial decay of the terms in the ST implies that truncating the ST at a sufficiently high level retains the bulk of the critical information. This is especially pertinent for describing solutions to CDEs, as the omitted infinite number of ST coefficients diminish in importance factorially. Finally, the uniqueness of ST for a certain class of paths, ensuring a one-to-one identifiability of a path with its ST.

Suppose that $1\leq p<2$ and let $x$ be in $C_{p}([a,b],V)$ and let $[a,b]$ and assume that $\lambda:[c,d]\to[a,b]$ is a continuous non-decreasing surjection. Then $S(x)_{[a,b]}=S(x\circ\lambda)_{[c,d]}$.

We prove the result first under the assumption that $p=1$. Let $x^{\lambda}:=x\circ\lambda$ denote the reparameterisation of $x$ by $\lambda$. We prove the statement by an induction on the level of the ST. The $1^{st}$-order iterated integral is the increment, and so we have

which holds for all $t\in[c,d]$. Fixing a basis $\{v_{i}:i=1,...,d\}$ for $V$, we assume that for any $k\geq 0$ and any multi-index $(i_{1},...,i_{m})$ of integers from $\{1,...,d\}$ of length $m\leq k$, we have equality of the coordinate iterated integrals defined with respect to this basis, i.e.

We then consider an arbitrary multi-index $(i_{1},...,i_{k},i_{k+1})$ of length $k+1$. For any $t\in[c,d]$ we can use the induction hypothesis to write

see, e.g., Theorem 3.6 of . By applying this result with the choices $f(r)=S(x)_{[a,r]}^{(i_{1},...,i_{k})}$ and $i=i_{k+1}$ we obtain

whereupon the induction step is complete.

The case $1<p<2$ can be obtained using a simple approximation argument by combining the fact that the closure of $C_{1}(V)$ in $C_{q}(V)$ contains $C_{p}(V)$ for any $p<q$. The argument is then concluded by considering such $q$ with $q<2$ and then using the joint continuity, in $q$-variation, of the Young integral map (e.g. [37, Prop. 6.11])

It is left to the reader to fill in the fine details. ∎

It is useful sometimes to work with re-parameterisations which may fail to be continuous or even surjective. In these cases, it is possible for a version of the previous theorem to still hold. For example, suppose that $x$ is a path in $C_{1}\left([a,b],V\right)$ of length $L=\left|\left|x\right|\right|_{1;\left[a,b\right]}$ then we can define a right-continuous function $\tau:\left[0,L\right]\rightarrow[a,b]$

with the convention that $\inf\emptyset=b$. In spite of the lack of continuity of $\tau,$ it can be seen easily that $x\circ\tau$ is itself still continuous and indeed still has finite length. In fact more is true: under this choice of reparameterisation, the path $x\circ\tau$ is Lipschitz continuous. The reader is invited to prove this in Exercise 1.6.6. The steps in the proof of the previous theorem can be retraced in this case to show again that $S\left(x^{\tau}\right)=S\left(x\right)$.

2.2 Fast decay in the magnitude of coefficients

As an application of this property we now prove two key results which expose properties of the ST, and which we will use repeatedly. The first, the so-called factorial decay estimate, quantifies the magnitude of the terms $S\left(x\right)^{\left(k\right)}$ with respect to appropriate terms norms. We state it for paths of finite length, although generalisations to less regular paths are possible, see for instance [37, Sec. 9.1.1].

Set $L:=\left\lVert x\right\rVert_{1,[a,b]}$ to be the $1$-variation of $x$, or its length. Let $\tau$ be the reparamterisation defined by (1.14) then $x^{\tau}=x\circ\tau$ $:\left[0,L\right]\rightarrow V$ is Lipschitz continuous; see 1.6.6. Using Remark 1.2.2 we have that $S\left(x\right)=S\left(x^{\tau}\right)$ and, as the length of $x$ is also a parameterisation-invariant quantity, it suffices to work with $x^{\tau}$ in place of $x$ when proving (1.15). Any Lipschitz continuous function is absolutely continuous and hence, by the Radon-Nikodym Theorem (e.g. [35, Thm. 3.8]), there exists an integrable function $\left(x^{\tau}\right)^{\prime}$ in $L^{1}\left(\left[0,L\right],V\right)$ such that

for all $\left[u,v\right]$ in $\left[0,L\right].$ The derivative of $x_{t}^{\tau}$ exists for almost every $t$ in $\left[0,L\right]$ and it equals $\left(x_{r}^{\tau}\right)^{\prime}$; the fact that $x^{\tau}$ has Lipschitz norm bounded by one, cf. (1.42), then shows that $||\left(x^{\tau}\right)^{\prime}||\leq 1$ almost everywhere. Using these observations, together with Fubini’s Theorem (e.g. [35, Thm. 2.37]), it is easy to see that

2.3 Uniqueness

The next result we show is that for any two paths $x$ and $y$ in $C_{p}\left(V\right)$ which share an identical, strictly monotone coordinate, one has $S\left(x\right)=S\left(y\right)$ if and only if the paths $x$ and $y$ are identically equal. This is the first instance of a result, which we will revisit later in a more general form, which validates that the ST is injective.

Suppose that $x$ and $y$ are two paths in $C_{p}\left([a,b],V\right)$, with $p\in[1,2)$, for some choice of basis for $V,$ their expression in these coordinates $x=\left(x^{1},...,x^{d}\right)$ and $y=\allowbreak\left(y^{1},...,y^{d}\right)$ are such that

for some strictly monotone path $\rho.$ Suppose that $x_{a}=y_{a}$, then

It is obvious that two identical paths have the same ST. To prove the converse we first notice, by considering $-x$ and $-y$ if necessary, that it is sufficient to prove the result assuming that $\rho$ is strictly increasing. Further by reparameterising $x$ and $y$ by the (necessarily continuous and strictly increasing) function $\sigma=\rho^{-1}$ we can assume that the first coordinate of both $x$ and $y$ is the identity function $i\left(t\right)\equiv t$. By making these simplification, we can write

for every $k$ and every $j$. For simplicity we drop the index $j$ and refer only to $x^{-}$. Integration-by-part then yields that

Noting that $x_{a}=y_{a}$ together with $x_{a,b}=S\left(x\right)_{a,b}^{\left(1\right)}=S\left(y\right)_{a,b}^{\left(1\right)}=y_{a,b}$ results in

and hence that $x^{-}-y^{-}$ as an element of $L^{2}\left(\left[a,b\right]\right)$ is in the orthogonal complement $\mathcal{P}^{\perp}$ of the space $\mathcal{P}$ of finite degree polynomials. Since $\mathcal{P}$ is dense subspace of $L^{2}\left(\left[a,b\right]\right)$ it follows that $\mathcal{P}^{\perp}=\left\{0\right\}$ and hence $x^{-}=y^{-}$ almost everywhere. Using the continuity of $x^{-}$ and $y^{-}$ then gives that $x^{-}$and $y^{-}$ are identically equal. ∎

So far we have seen that the ST satisfies two important analytic properties: the factorial decay allows for fast approximation of solutions of differential equations, while the invariance to reparameterization allows to remove possibly detrimental symmetries from the data. The ST also benefits from a rich algebraic structure which allow for efficient computations as we shall see next.

3 Algebraic properties

At first sight, the ST looks like an object very difficult to compute in practice. However, it turns out that these computations can be carried out elegantly and efficiently by using simple classes of paths as building blocks for more complicated paths. To do this we will make use of an algebraic property of the ST called Chen’s relation. We will later refine our view on this point but, for the moment, we assume that $x\in C_{1}([a,b],V)$ is a linear path, i.e. a straight line, so that for any $t\in[a,b]$

Denote by $x_{a,b}:=i_{1}(x_{b}-x_{a})$, where $i_{1}:V\to T((V))$ is the canonical inclusion. Then, in this special case, we can calculate the ST of $x$ over $[a,b]$ very easily and show that

where the map $\exp:T((V))\to T_{1}((V))$ is the tensor exponential defined as

where $T_{1}\left(\left(V\right)\right)=\left\{v\in T\left(\left(V\right)\right):\pi_{0}v=1\right\}.$

The proof of this observation follows because the derivative of $x$ is the constant vector $\frac{x_{b}-x_{a}}{(b-a)}$ on $[a,b]$, and therefore

Suppose we now have two paths $x$ in $C_{p}([a,b],V)$ and $y$ in $C_{p}([b,c],V)$. Then there is a very natural binary operation on these paths which allows us to combine $x$ and $y$ into a single path. We define the concatenation of $x$ and $y$, which we denote by $x\ast y$, to be the path in $C_{p}([a,c],V)$ given by

An important property is that the ST $S(x*y)$ can be described in terms of the ST of $x$ and the ST of $y$ and, in fact, it equals the tensor product $S(x)\cdot S(y)$. This property, which is called Chen’s relation, is the content of the following lemma.

Let $1\leq p<2$. Suppose that $x$ is in $C_{p}([a,b],V)$ and $y$ is in $C_{p}([b,c],V)$. Then

We prove the result in the case $p=1$; the identity for arbitrary $1<p<2$ can be obtained by the now-familiar routine of approximating $x$ and $y$ in $C_{q}$ with $p<q<2$ by respective sequences bounded variation paths. See the final paragraph of the proof of 1.2.1. The identity (1.19) for $p=1$ then carries over to general $p$ by the continuity of Young integration in the $q$-variation topology. With this simplification being understood, we let $z:=x\ast y$. Then, for each $k\geq 1$, the level $k$ of the ST

By Fubini’s theorem, this is equivalent to

On each sub-interval $[t_{i},t_{i+1}]$ the path $x$ is linear, therefore eq. 1.16 yields

Expression (1.20) is leveraged in all the main python packages for computing signatures such as esig , iisignature and signatory .

We conclude this section by showing that at any level of truncation, the truncated tensor algebra coincides with the linear span of signatures truncated at that level. Several proofs of this statement can be found in the literature, see for example [26, Lemma 3.4]. The one we propose below, (which one of us learnt from Bruce Driver), solely requires tools introduced so far in this chapter and the well-known fact that the exponential map in (1.17) and the tensor logarithm $\log:T_{1}((V))\to T((V))$ defined as

where $(x^{a})^{*l}$ is the path $x^{a}$ concatenated with itself $l$ times and where the fifth equality follows from the Chen’s identity of Lemma 1.3.1. From this we have

where $i_{1}^{N}:V\to T_{N}(V)$ is the canonical inclusion. A variation on the same idea yields for $n\leq N$ that

for any collection $a_{1},....,a_{n}$ in $V.$

From this it follows as above that $T_{N}\left(V\right)\subset$ span$\left(\mathcal{S}_{N}\right).$ ∎

In Proposition 2.1.14 in the next chapter we will show that this statement not only holds for the TST, but also for the (untruncated) ST.

3.2 The signature as a controlled differential equation

Many of the important properties of the ST of a path $x$ can be derived most easily by observing that it is the solution of a specific CDE driven by $x$. Indeed, we will see that we could have used this as a starting point to define the ST without ever introducing iterated integrals. Formally this CDE reads

where we continue to use $\cdot$ to denote the multiplication in $T((V))$. We will shortly introduce the analysis needed to ensure that the equation is well posed and then explore some of its properties. For the moment, we comment on the structure of the equation by observing that it is a linear CDE.

If the tensor product $\cdot$ in equation (1.22) were replaced by a commutative product, then we would expect the resulting solution to be the exponential of the driving signal $x$. This allows us to view the signature, at least impressionistically, as a form of non-commutative exponential. The analysis below develops the tools needed to put this intuition on a firmer foundation. A key eventual goal will be to show, in a precise sense, the universality of the ST: under certain conditions, all continuous input-response relationships are expressible in terms of it. This class contains a wide family of CDEs, the canonical example with which we started this chapter. The reader may find is useful to look ahead at the statement of Theorem 1.4.7 at this stage.

We begin by introducing some notation for the range of the signature map, which will be heavily used throughout the rest of this chapter.

Let $1\leq p<2$. We use $\mathcal{S}_{p}\subset T((V))$ to denote the image of $C_{p}(V)$ under the ST.

The following result then makes precise the CDE-formulation of the signature which we described above.

Suppose that $x$ is in $C_{p}([a,b],V)$ for some $p$ in $[1,2)$. Let $(E,\left|\left|\cdot\right|\right|)$ be a Banach algebra which is a subalgebra of $T((V))$ with the property that $\mathcal{S}_{p}\subset E$. Then the controlled differential equation

admits a unique solution in $E$ which is given explicitly by $Y_{t}=A\cdot S(x)_{[a,t]}$. In particular, if $A=\mathbf{1}=(1,0,...)$ then the ST uniquely solves (1.23).

For instance $E$ could be taken as the Banach algebra described in Example 1.1.14.

The map $f:E\rightarrow L\left(V,E\right)$ given by $f\left(Y\right)=Y\cdot a$ is well defined; it takes values in $E$ as $E$ is a Banach algebra and, by virtue of being linear in $Y$, $f$ can easily been seen to satisfy the conditions of the classical versions of Picard theorem for Young CDEs (e.g. [67, Thm. 1.28]). A solution to (1.23) thus exists uniquely in $E$. On the other hand, any solution $Y_{t}=\left(Y_{t}^{0},Y_{t}^{1},Y_{t}^{2},...\right)$ to (1.23) must satisfy

We give an example of how this characterisation of the ST can be used to extract useful algebraic properties. To do so we first observe that, in addition to the binary operation of concatenating two paths, there is another natural unary operation consisting of running the path backwards starting from its end point. Symbolically, given $x\in C_{p}([a,b],V)$ we define the time reversal of $x$ to be $\overleftarrow{x}$ where

It is easily verified that $\overleftarrow{x}$ again belongs to $C_{p}([a,b],V)$. The following result shows that the signature of $\overleftarrow{x}$ is the mutliplicative inverse of the ST of $x$ in $T((V))$.

Let $p\in[1,2)$ and let $x\in C_{p}([a,b],V)$. Then

Let $A=S\left(x\right)_{[a.b]}$ then, by using Theorem 1.3.5, we have $U_{t}=A\cdot S\left(\overleftarrow{x}\right)_{[a,t]}$ uniquely solves the CDE

We need to prove that $U_{b}=\mathbf{1.}$ To do this we define $V_{t}:=U_{a+b-t}$ for $t$ in $\left[a,b\right]$ and observe that $V$ solves

Because $V_{b}=S\left(x\right)_{\left[a,b\right]}$ and $S\left(x\right)_{\left[a,\cdot\right]}$ solves (1.24) we have by uniqueness that $V_{a}=S\left(x\right)_{\left[a,a\right]}=\mathbf{1.}$ It follows that $S\left(x\right)_{\left[a,b\right]}$ $\cdot S\left(\overleftarrow{x}\right)_{[a,b]}=\mathbf{1}$ for any $x$. The fact that $\overleftarrow{\overleftarrow{x}}=x$ completes the proof. ∎

Readers who may be sceptical about the advantages of working with the analytical, CDE approach to the signature are invited to compare the proof of this result with the same proof attempted using algebraic methods.

3.3 The shuffle identity

The tensor product $\cdot$ is not the only product that makes sense on $T((V))$. In this section we will discuss another product, called the shuffle product $\shuffle$, which will turn out to be a fundamental tool for some more advanced manipulations of the ST, and is an important tool underpinning many version of the universal approximation theorems using signature features that arise in machine learning.

We first defined this product, and then explain through examples how it is used.

We define $\shuffle:T(V)\times T(V)\mapsto T(V)$ by

for any $f\in V^{\otimes k}$ and $g\in V^{\otimes l}$ of the form $f=f_{-}\cdot a$ and $g=g_{-}\cdot b$, where $a$ and $b$ are in $V$. Given this definition, $\shuffle$ extends uniquely to an algebra product on $T(V)\times T(V)$ by linearity in each term of the product.

For reasons that will be clear soon, it will be useful to work with the $\shuffle$ on the co-tensor algebra $T(V^{*})$. This does not affect the definition above, which holds when $V$ is an arbitrary vector space (and so, in particular can be taken to be $V^{*}$).

Why is the shuffle product relevant to the ST? One important tool which we encounter in foundational calculus is integration-by-parts. To put this familiar result in the present context, suppose that $x$ is a smooth path in $V$ and that $f$ and $g$ are linear functionals in $V^{*}$, then classical integration-by-parts is the identity

and this be rewritten in terms of shuffle products as

This observation can be generalised: products of iterated integrals can be re-expressed as a linear combination of higher order iterated integrals using integration-by-parts. The shuffle product can be used to succinctly capture the algebraic identities which result from this observation.

Suppose that $x\in C_{p}([a,b],V)$ for $p$ in $[1,2)$. For any two linear functionals $f$ and $g$ in $T((V))^{*}\cong T(V^{*})$ it holds that

It suffices to prove the result for arbitrary $f$ $\in V^{\ast\otimes k}$ and $g\in V^{\ast\otimes l}$ the general result then follows from the distributivity of the shuffle product.

We will prove, by double induction, the following statement

$H(m,n)$: $\forall 0\leq k\leq m,0\leq l\leq n$, identity (1.26) holds $\forall f\in V^{\ast\otimes k},g\in V^{\ast\otimes l}.$

We can check that $H(m,0)$ and $H(0,n)$ hold using elementary properties of scalar multiplication in $T\left(V^{\ast}\right)$. We assume therefore that $H(m-1,n)$ and $H(m,n-1)$ hold and verify $H(m,n)$. To do so, take $f\in V^{\ast\otimes m}$ and $g\in V^{\ast\otimes n}$ and use the definition of the shuffle product to see that

where $f=f_{-}\cdot p$ and $g=g_{-}\cdot q.$ We can then simplify the first term by using $H(m-1,n)$ and the second using $H(m,n-1)$ to obtain

with $F_{s}:=\left(f,S\left(x\right)_{a,s}\right)$ and $G_{s}:=\left(g,S\left(x\right)_{a,s}\right).$ Integration-by-parts then yields the desired conclusion

Given a basis $\{f_{i}\}_{i=1}^{d}$ for $V^{*}$ we could also define the shuffle product directly on $T(V^{*})$ by letting $I=(i_{1},...i_{n})$ and $J=(i_{n+1},...i_{n+m})$ be arbitrary multi-indices in $\{i,...,d\}$ and then, recalling Notation 1.1.15, by defining

The summation is over all $(n,m)$-shuffles ; that is over the subset of the permutations of the $\{1,...,n+m\}$ which satisfy $\sigma(1)<...<\sigma(n)$ and $\sigma(n+1)<...<\sigma(n+m)$. It can be verified that this defines an element of $T(V^{*})$ in a way that does not depend on the choice of basis. The resulting definition coincides with Definition 1.3.9.

If we work with a particular basis $\{e_{i}\}_{i=1}^{d}$ of $V$, then the shuffle product identity for the ST can be expressed more tersely in terms coordinate iterated integrals by

This expression holds for any pair of multi-indices $I$ and $J$; the term $S(x)^{I\shuffle J}_{[a,b]}$ is defined to be $(e_{I}^{*}\shuffle e_{J}^{*},S(x)_{[a,b]})$.

We elucidate this definition with an example.

Let $\{e_{i}\}_{i=1}^{d}$ be a basis of $V$ and let its dual basis be denoted by $\{e_{i}^{*}\}_{i=1}^{d}$. Suppose that $e_{i}^{*}e_{j}^{*}$ and $e_{k}^{*}$ are elements of $(V^{*})^{\otimes 2}$ and $V^{*}$ respectively, then

This expression can be rewritten as the sum of three third-order iterated integrals by ”shuffling” the integrands

Note that the tuples $(i,j,k),(i,k,j),(k,i,j)$ indexing the dual basis elements appearing in this expansion are obtained by shuffling $(i,j)$ and $(k)$ while retaining the order of the indices within each tuple, thus explains the nomenclature of the shuffle product.

The shuffle property can be used to prove the following useful lemma.

Let $1\leq p<2$ and suppose $h_{1},..,h_{n}$ is a finite collection of distinct elements of $\mathcal{S}_{p}\subset T\left(\left(V\right)\right).$ Then there exists a linear functional $f$ in $T\left(\left(V\right)\right)^{\ast}$ such that $f\left(h_{1}\right)=1$ and $f\left(h_{i}\right)=0$ for all $i=2,...,n.$

An important consequence of this is the following result.

Suppose $1\leq p<2$. Any finite set of distinct elements $\left\{h_{1},..,h_{n}\right\}\subset\mathcal{S}_{p}$ is a linearly independent subset of $T\left(\left(V\right)\right).$

Suppose that $h=\sum_{i=1}^{n}\lambda_{i}h_{i}=0$ in $T\left(\left(V\right)\right)$ and assume that $\lambda_{j}$ is non-zero for some $j$. By relabelling the $h_{i}\,$s if necessary we can assume that $\lambda_{1}\neq 0.$ Then, letting $f$ be the linear functional in Lemma 1.3.13, we arrive at the contradiction $0=f\left(h\right)=\lambda_{1}.$ It follows that $\lambda_{i}=0$ for every $i=1,..,n.$ ∎

As an immediate corollary we can obtain that any discrete $\mathcal{S}_{p}$-valued random variable is uniquely characterised by its expected value.

Let $G$ be another random variable with law $\nu=\sum_{j=1}^{m}q_{j}\delta_{g_{j}}$ supported on distinct $g_{1},...,g_{m}$ in $\mathcal{S}_{p}.$ By Proposition 1.3.14 we see that $\sum_{i=1}^{n}p_{i}h_{i}=\sum_{j=1}^{m}q_{j}g_{j}$ if and only if both $n=m$ and the sets

4 Unparameterised paths

We have seen in Lemma 1.2.1 that the ST of a path $x$ is invariant under reparameterisation. It is also immediate from its definition that when $x$ is translated by any constant path its signature will be unchanged. Nothing is lost therefore by only considering signatures of paths in $C_{0,p}(V)$, the subspace of $C_{p}(V)$ consisting of paths which start at the zero vector $0\in V$, and we will do this throuhgout this section. A special role will be played by $o$, the path that is constantly zero $o\equiv 0$.

The notion of ST allows us define a relation on $C_{0,p}(V)$ by declaring two paths to be related if they have the same signature. It is easily proved that this is an equivalence relation which we will denote by $\sim$. We denote the equivalence class containing a path $x$ by $[x]$. A natural question prompted by this discussion is: what elements does $[x]$ contain? We know already that distinct paths can have equal signatures; using Lemma 1.2.1 any reparameterisation of $x$ will have the same signature as $x$ but will, in general, be distinct from $x$ as an element of $C_{p}(V)$. It can happen however that two paths share the same signature while not being re-parameterisations of one another in the strict sense of Lemma 1.2.1. For example, if $x\neq o$ we have that $x*\overleftarrow{x}\neq o$, while from Lemma 1.3.7 we have

More generally, by Chen’s identity any path which contains segments that exactly retrace themselves will have the same signature as the path obtained by excising both of those segments. We note also that, again in view of Lemma 1.3.7, $\sim$ could also be defined by saying that $x\sim y$ if

which, when it holds, also means that $S(y*\overleftarrow{x})=\mathbf{1}$. Elements of the equivalence class $[o]$ are called tree-like paths.

It turns out that $\sim$-equivalence coincides with an ostensibly-unconnected equivalence relation called tree-like equivalence. This latter notion makes no direct reference to the ST and is formulated purely in term of the properties of the path. Nonetheless the two notions are the same and can be viewed as a general notion of reparameterisation which simultaneously captures both the classical concept of Lemma 1.2.1 and the idea of excising retracings expressed in the example (1.29). We will not use the notion of tree-like equivalence in what follows; the key result is the following and the interested reader can consult the references given.

Let $1\leq p<2$, then tree-like equivalence defines an equivalence relation on $C_{0,p}(V)$. It coincides with the equivalence relation $\sim$ defined by the equality of signatures. In the case $p=1$, there exists an element of each tree-like equivalence class $[x]$ which has minimal length. This element in unique up to parameterisation and is called the tree-reduced representative of $[x]$.

We now introduce the space of unparameterised paths.

Suppose $1\leq p<2$. We define the space of $p$-unparameterised paths, denoted by $\mathcal{C}_{p}$, to be the quotient space

There is a natural group structure on the space of unparameterised paths.

Suppose $1\leq p<2$. The concatenation operation $*$ on $C_{p}(V)$ induces a well defined binary operation on $\mathcal{C}_{p}$ by $[x]*[y]=[x*y]$. Moreover $(\mathcal{C}_{p},*)$ is a group in which the identity element is $[o]$ and where $[\overleftarrow{x}]$ is the well-defined inverse of $[x]$.

That $*$ is well defined on $\mathcal{C}_{p}$ amounts to showing that $[x*y]=[x^{\prime}*y^{\prime}]$ for any $x^{\prime}\in[x]$ and $y^{\prime}\in[y]$ and this is a direct consequence of Chen’s relations, Lemma 1.3.1. The group axioms can be verified similarly using properties of the tensor product, and the final assertion about the inverse is obtained from Lemma 1.3.7. ∎

We will be interested to use the ST representation of a path to learn functions on path space. An immediate obstacle to implementing this idea is that the ST cannot distinguish between different paths in the same tree-like equivalence class. This compels us to work for the moment on functions defined on unparameterised path space.

Suppose that $X$ is a set and let $1\leq p<2$. We use $X^{\mathcal{C}_{p}}$ to denote the set of functions from $\mathcal{C}_{p}$ into $X.$

One way to obtain functions in $X^{\mathcal{C}_{p}}$ is to study the subset of functions on the original space $C_{0,p}(V)$ which are invariant under tree-like equivalence. Fortunately there is an abundance of such functions; the examples covered by the results below describe an immediately-useful collection of them.

The following fundamental result underpins the conceptual framework of using the signature features to approximate continuous functions on unparameterised paths.

Let $1\leq p<2$ and suppose that $\chi$ is a collection of subsets which form a topology on $\mathcal{C}_{p}$. Assume that $K$ is a compact subspace of $\mathcal{C}_{p}$ and, for $f\in T((V))^{*}$, let $\Phi_{f}|_{K}$ denote the restriction of the function (1.31) to $K$. Let $C(K)$ denote the space of continuous functions on $K$ with the topology of uniform convergence. If the set $\mathcal{A}_{K}:=\{\Phi_{f}|_{K}:f\in T((V))^{*}\}$ is a subset of $C(K)$, then it is a dense subset.