Signatory: differentiable computations of the signature and logsignature transforms, on both CPU and GPU
Authors: Patrick Kidger
Terry Lyons
Venue: ICLR 2021 Poster (2021)
Keywords: signature
logsignature
gpu
library
open source

Abstract: Signatory is a library for calculating and performing functionality related to the signature and logsignature transforms. The focus is on machine learning, and as such includes features such as CPU parallelism, GPU support, and backpropagation. To our knowledge it is the first GPU-capable library for these operations. Signatory implements new features not available in previous libraries, such as efficient precomputation strategies. Furthermore, several novel algorithmic improvements are introduced, producing substantial real-world speedups even on the CPU without parallelism. The library operates as a Python wrapper around C++, and is compatible with the PyTorch ecosystem. It may be installed directly via \texttt{pip}. Source code, documentation, examples, benchmarks and tests may be found at \texttt{\url{https://github.com/patrick-kidger/signatory}}. The license is Apache-2.0.

Published as a conference paper at ICLR 2021
SIGNATORY: DIFFERENTIABLE COMPUTATIONS OF THE SIGNATURE AND LOGSIGNATURE TRANSFORMS, ON BOTH CPU AND GPU
Patrick Kidger
Terry Lyons
Mathematical Institute, University of Oxford The Alan Turing Institute, British Library (kidger, tlyons| maths ox. ac.
ABSTRACT
Signatory is library for calculating and performing functionality related to the signature and logsignature transforms. The focus is on machine learning, and as such includes features such as CPU parallelism, GPU support, and backpropa- gation. To our knowledge it is the first GPU-capable library for these operations. Signatory implements features not available in previous librarics, such effi- cient precomputation strategies. Furthermore, several novel algorithmic improve- ments introduced, producing substantial real-world speedups without parallelism. The library operates as a Python wrapper around C++, and is compatible with the PyTorch ecosystem. It may be installed directly via pip. Source code, documentation, examples, benchmarks and tests may be found at httpss: /ttpa////gthhb...e//e http://ww....oooaaaaaae///oo//// Apoche-2.0.
the CPU
The license
INTRODUCTION
The signature transform, sometimes referred as the path signature or simply signature, is central object in rough path theory (Lyons 1998 2014). It is transformation on differentiable path and may be thought of as loosely analogous to Fourier transform. However whilst the Fourier transform extracts information about frequency, treats each channel separately, and is linear, the signature transform exacts information about order and area, explicitly considers combinations of channels, and is in precise sense 'universally nonlinear' (Bonnier et al. 2019 Proposition A.6).
The logsignature transform (Liao et al. 2019) is a related transform, that we will also consider. In both cases, by treating sequences of data continuous paths, then the (log)signature transform may be applied for use in problems with sequential structure, such as time series. Indeed there is significant body of work using the (log)signature transform in machine learning. with examples ranging from handwriting identification to sepsis prediction, see for example Morrill et al. (201);;
Fermanian 2 Király& & Oberhauser (2019); Toth & Oberhauser (2020); Morrill al. (2020b).
Earlier work often used the signature and logsignature transforms as a feature transformation. See Levin et al. (2013); Chevyrev & Kormilitzin (2016); Yang al. (2016a b): Kormilitzin et al. (2016);
Li et al. (217) (017);; Perez Arribas et al. (2018) for range of examples. In this context, when training model on top, sufficent to simply preprocess the entire dataset with the signature logsignature transform, and then save the result.
However, recent work has focused on embedding the signature and logsignature transforms within neural networks. Recent work includes Bonnier et al. (2019): Liao et al. (2019); Moor et al. (2020); Morrill al. (2020a): Kidger et al. (2020) among others. In this context, the signature and logsigna- ture transforms are evaluated many times throughout a training procedure, and as such efficient and differentiable implementations are crucial. Previous libraries (Lyons) 2017 Reizenstein & Graham 2018) have been CPU-only and single-threaded, and quickly become the major source of slowdown when training and evaluating these networks.
And may extended paths of bounded variation, or merely finite p-variation ( Lyons al. 2004

---

Published as a conference paper at ICLR 2021
1.1 CONTRIBUTIONS
We introduce Signatory, a CPU- and GPU-capable library for calculating and performing functional- ity related to the signature and logsignature transforms. To our knowledge is the first GPU-capable library for these operations. The focus is on machine learning applications.
Signatory is significantly faster than previous libraries (whether run on the CPU or the GPU), due to combination of parallelism and novel algorithmic improvements. In particular the latter includes both uniform and asymptotic rate improvements over previous algorithms. Additionally, Signatory provides functionality not available in previous libraries, such precomputation strategies for effi- cient querying of the (log)signature transform over arbitrary overlapping intervals.
The library integrates with the open souree PyTorch ecosystem and runs on Linux or Windows. Documentation, examples, benchmarks and tests form a part of the project.
Much of the code is written in C++ primitives and the CPU implementation utilises OpenMP. The backward operations are handwritten for both speed and memory efficiency, and do not rely on the autodifferentiation provided by PyTorch.
The source code is located umentation and examples available at
doc-
rew.torrr.r.aathedoooos .1 and the
project may be installed directly via pip.
This paper is not guide using Signatory for that refer to the documentation. This is meant as a technical exposition of its innovations.
1.2 APPLICATIONS
Signatory has already seen rapid uptake amongst the signature community. Recent work using Signatory include Morrill et al. (2020b); Perez Arribas et al. (2020) who involve signatures neural differential equations, or Moor et al. (2020); Min & Ichiba (2020) who study deep signature models (Bonnier et al.] 2019). Mcanwhile Ni et al. (2020) apply Signatory to hybridise signatures with GANs, and Morrill et al. (2020a) create generalised framework for the "signature method". As final example, Signatory is now itself a dependency for other libraries (Kidger 2020).
2 BACKGROUND
We begin with some exposition on theory of the signature and logsignature transforms. We begin with definitions and offer intuition afterwards. Also see Reizenstein & Graham (2018) for an intro- duction focusing on computational concerns, and [Lyon et (2004) and Hodgkinson et (2020) for pedagogical introductions to the motivating theory of rough paths.
and
2.1 THE SIGNATURE TRANSFORM
Definition 1. Let Rd4 & & ..d denote the space of all real tensors with shape dj d2 x d,, There is a corresponding binary operation & called the tensor product, which maps tensor of shape (d,, ... dn) and tensor of shape (EI, ................................ em) to tensor of shape (di,..., day et,... em) via (Ai Bi...... + Ai B im For example when applied to two vectors, it reduces the outer product.
Let (IRd 0k
Rd 2...2RR Rdd and 8k o x- for E Rd in each case with k many 8.
Definition 2. Let N E N. The signature transform depth N is defined
N
SigN: C([O, R): |s differentiable)
+ II
(Rd)
OK
k=1
df di (ti) 8
df di
Sig
(tx) dt ... dd
(I)
ISKgN
2

---

Published as a conference paper at ICLR 2021
Most texts define the signature transform using the notation of stochastic calculus. Here, sacrifice some generality (that not needed this context) favour of more widely-used notation
The signature transform may naturally be extended to sequences of data.
Definition 3. The space of sequences of data over a set V is
S (V) = {x (Z1,...., .L. L E N, 2; E V for all i}
interval (ri,..., 21) E (V) (I.....,3)) 13) (V) for some 1 S < L.
Definition 4. Let x (x) ( vT.) S (RR)) with 2 2. Let f: [0, 1] + Rd be the unique continuous piecewise affine function such that 1(1-) = x; for all i, and is affine on the pieces in between. Let E N. Then define Sig"(x) Sig
N (f). In this way we interpret Sig as map
N
Sig N S (R*)
+ II (R.)
8K
Note that the choice of i-1 is unimportant; any L points [0. 1] would suffice, and in fact the L-1 definition is invariant this choice (Bonnier et al. 2019 Definition A.10).
2.2
THE GROUPLIKE STRUCTURE
With Ao Bu = 1 E R on the right hand side, define X by
x
II R
II
RR4) @K
II IR @k
(A AN) X (BI...., Br)
Σ Ag Bk-j
ISASN
Chen's identity (Lyons et al. 2004 Theorem 2.9) states that the image of the signature transform forms noncommutative group with respect X. That is, given sequence of data (z1,..., S ( and some {2..... L }}. then
Sig Sign(((... (( xL) Sig (0gg(((1,.... B Sig ((zz, ((z)...,,II).
Furthermore the signature of a sequence of length two may be computed explicitly from the defini- tion. Letting
N II
82
exp: RRd
(R2
@k
exp: U -
0, 2!
31
N!
k=1
then
Sig NN ((11, x2)) = exp(x2 x1).
With Chen's identity, this implies that the signature transform may be computed by evaluating
Sig (())) exp(x2 x1 8 exp(#3 x22) X X exp(@1 xL-1).
(3)
2.3
THE LOGSIGNATURE, INVERTED SIGNATURE, AND INVERTED LOGSIGNATURE
The group inverse we denote -1 Additionally a notion of logarithm may be defined [Lao et al. 2019). where
log: image (Sig N) + II (R))4 84
(4)
k=1
Additionally, many also include 0 term, which is defined equal one. We omit this does not carry any information, and therefore irrelevant to the task of machine learning.
Moost texts use rather than & to denote this operation, as it may be regarded as generalisation of the tensor product. That will not be important us, however, we differing notation aid interpretation.

---

Published as a conference paper at ICLR 2021
This then defines the notions of inverted signature transform, logsignature transform and inverted logsignature transform as
InvertSig' N (x) = Sig (x) (x)_
LogSig"
N (x) log (Sig" (x))
InvertLogSig" (x) log (Sig") (x)=1)
respectively. We emphasise that the inverted signature or logsignature transforms are not the inverse maps of the signature or the logsignature transforms.
The logsignature transform extracts the same information as the signature transform, but repre- sents the information in a much more compact way, as image (log) is proper subspace of I mula Lothaire 1997). ş is the Möbius function.
[R4)
@k
Its dimension is w(d, N) = E Eije l (+) d', which is known as Witt's for-
2.4 SIGNATURES IN MACHINE LEARNING
In terms of the tensors used by most machine learning frameworks, then the (inverted) signature and logsignature transforms of depth N may both be thought of as consuming tensor of shape (b, L, d), corresponding to batch different sequences data, each of the form (I1,..... ................................ &t) for 24 E IRd. The (inverted) signature transform then produces a tensor of shape (b, >> k=1 d²). whilst the (inverted) logsignature transform produces tensor of shape (b, w(d, N)). We note that these can be easily be large, and much research has focused on ameliorating this Bonnier et al. (2199; Morrill et al. (2020a): Cuchiero al. (2020).
All of these transforms are in fact differentiable with respect to and so may be backpropagated through. These transforms may thus be thought of differentiable operations between tensors, in the way usually performed by machine learning frameworks.
2.5 INTUITION
The (inverted) signature and logsignature transforms all have roughly the same intuition as one another. (They all represent the same information, just in slightly different ways.) Given a sequence of data (Z1..... ,L,, then these transforms may be used as binning functions, feature extractors, or nonlinearities, to give summary statisties over the data.
These summary statistics describe the way in which the data interacts with dynamical systems (Mor- rill al., 20206). Indeed, we have already linked the signature the exponential map, which defined as solution to a differential equation: dexp (I) = exp(l). The signature may fact be defined as the solution of controlled exponential map: dSig (f)(t) Sig (f) & df(t), so that Sig" N (f) is response of a particular dynamical system driven by f. The theory here is somewhat involved, and not an interpretation we shall pursue further here.
An equivalent more straightforward interpretation is arrived at by observing that the terms of the ex- ponential of scalar exp: x E ~ (1, _==2 ....) produce (up to scaling factors) every monomial of its input. Classical machine learning takes advantage of this as feature extractor in polynomial regression. The signature transform is the equivalent operation when the input is sequence.
3 CODE EXAMPI.E
Signatory is designed to be Pythonic, and offer operations working just like any other Py PyTocch operation, outputting PyTorch tensors. A brief example is:
import signatory
import torch batch. stream channels. depth = 1, 10. 2.
'log is actually bijection. image (Sig.) ) is some curved manifold in I[ (Rd)** 0* and log is the map that straightens out into linear subspace.
4

---

Published as a conference paper at ICLR 2021
path torch rand (batch. stream channels, requires grad=True) signature signatory signature (path, depth) signature sum (). backward ()
ALGORITHMIC IMPROVEMENTS
We present several noveral algorithmic improvements for computing signatures and logsignatures.
4.1 FUSED MULTIPLY-EXPOENTTNE
Recall from equation (3) that the signature may be computed by evaluating several exponentials and several X. We begin by finding that it is beneficial compute
N
N
II
R
x IR
II k=1
[R
Ok
A, 4,2+3 A X exp(2)
as a fused operation. Doing so has uniformly (over d, N) fewer scalar multiplications than the composition of the individual exponential and 8, and in fact reduces the asymptotic complexity of this operation from (NNd) to Odd"). Furthermore this rate is now optimal, as the size of result
(an element of I (R.) @k ), is itself of size (dd))
The bulk of signature computation may then be sped up by writing it in terms of this fused op- cration. See equation (3): a single exponential is required at the start, followed by a reduction with respect to this fused multiply--xponentiall This gives substantial real-world speedups; the benchmarks of Section(6
The fusing is done by expanding
2((--))
A M exp(22)
Σ A @
(A:
ii!
1=0
ISKSN
at which point the k-th term may be computed by a scheme in the style of Horner's method:
k
2
@(k-i)
A X
(k: i)!
i=0
+ A1
k-1 +
Ak-1 2 Ag.
(5)
k
See Appendix A.I for the the mathematics, including proofs of both the asymptotic complexity and the uniformly fewer multiplications.
4.2 IMPROVED PRECOMPUTATION STRATEGIES
Given a sequence of data ( Fr),, may be desirable query Sig ((x,, (..,,..., .ry)) for many different pairs j. We show that this query may be computed in just (L)) (in L) time and memory by using (L) precomputation and storage. Previous theoretical work has achieved only Ollog I.) inference with OL L.) precomputation (Chafai & Lyons 2005).
Doing so is surprisingly simple. Precompute Sig" ((11,.... .z)) and InvertSig N ((I1,..., 2z)) for all j. This may be done in only (T.) work, by iteratively computing each signature via
Sig ((11. ... 22,)) Sig ((#1...., 2,....,,--11 z)-1))
X ((z)-1,
(6)
with similar relation for the inverted signature. Then, inference time the group-like structure Sig ((x,,..., xr)) = InvertSig (aatiiig((((())...... ((z,,..., .x.)) X S ((1),.( x,)), followed by log if is logsignature that is desired. As single operation this is (() in L.
We do remark that this should used with caution, and may suffer from numerical stability issues when used for large j.
5

---

Published as a conference paper at ICLR 2021
4.3 MORE EFFICIENT LOGSIGNATURE BASIS
The logsignature transform of a path has multiple possible representations, corresponding to dif- ferent possible bases of the ambient space, which is typically interpreted free Lie algebra [Reutenauer] 1993). The Lyndon basis is typical choice (Reizenstein & Graham 2018).
We show that there exists more computationally efficient basis. It is mathematically unusual, as it is not constructed as a Hall basis. But if doing deep learning, then the choice of basis is (mostly) unimportant if the next operation is learnt linear transformation.
The Lyndon basis uses Lyndon brackets as its basis elements. Meanwhile our new basis uses basis elements that, when written as sum of Lyndon brackets and expanded precisely one word as Lyndon word. This means that the coefficient of this basis element can be found cheaply, by extracting the coeffient of that Lyndon word from the tensor algebra representation of the logsignature. See Appendix A.2 for the full exposition.
sum of words, have
5
NEW FEATURES
Signatory provides several features not available in previous libraries.
5.1 PARALLELISM
There two main levels of parallelism. First is naive parallelism over the batch dimension. Sec- ond, we observe that equation (3) takes the form of a noncommutative reduction with respect to the fused multiply expinetttte..oeniiattt.... The operation & is associative, and so this may be parallelised in the usual way for reductions, by splitting the computation up into chunks.
Parallelism on the CPU is implemented with OpenMP. For speed the necessary operations written in terms of C++ primitives, and then bound into PyTorch.
5.2 GPU SUPPORT
An important feature is GPU support, which is done via the functionality available through LibTTorch. It was a deliberate choice not to write CUDA code; this is due to technical reasons for distributing the library in widely-compatible manner. See Appendix B
There are again two levels of parallelism, as described in the previous section.
When the (log)signature transform is part of deep learning model trained on the GPU, then GPU support offers speedups not just from the use of a GPU over the CPU, but also obviates the need for copying the data to and from the GPU.
5.3 BACKPROPAGATION
Crucial for any library used in deep learning is to be able to backpropagate through the provided operations. Signatory provides full support for backpropagation through every provided operation. There has previously only been limited support for backpropagation through handful of simple operations, via the i iisi gnature library (Reizenstein Graham 2018).
The backpropagation computations are handwritten, rather than being generated autodifferentiably. This improves the speed of the computation by using C++ primitives rather than high-level tensors, and furthermore allows for improved memory efficiency, by exploiting reversibility property of signature (Reizenstein, 2019) Section 4.9.3). We discuss backpropagation in more detail in Appendix C
5.4 INVERTED SIGNATURES AND LOGSIGNATURES
Signatory provides the capability to compute inverted signatures and logsignatures, via the optional inverse argument to the signature and logsignature functions. This is primarily a venience as
Sig ((x) "o01,...,.7.
((.1,...,,I1) xI1) Sig ((F1,..,,x1))

---

Published as a conference paper at ICLR 2021
5.5 EXPLOITING THE GROUPLIKE STRUCTURE
It is often desirable to compute (inverted) (log)signatures over multiple intervals of the same se- quence of data. These calculations may jointly be accomplished more efficiently than by evaluating the signature transform over every interval separately. In some cases, if the original data has been discarded and only its signature now known, exploiting this structure is the only way to perform the computation.
Here we detail several notable cases, and how Signatory supports them. In all cases the aim is to provide flexible set of tools that may be used together, so that wherever possible unecessary recomputation may be elided. Their use is also discussed in the documentation, including examples.
If the two signatures on the right hand side of the equation are already known, then the signature of the overall sequence of data may be computed using only single & operation, without re-iterating over the data.
Combining adjacent intervals Recall equation 2
This operation
provided for by the multi s seaggnatre_combilie functions.
and
Expanding intervals Given a sequence of data (fi,..., .L) E (R.). a scenario that is partic-
ularly important for its use in Section 4.2 is to compute the signature of expanding intervals of the data
(Sig ((11, x2)), Sigg (1))), Sig
This may be interpreted as a sequence of signatures, that is to say an element of (IIM (R*) ox) )o))
By equation (6). this may be done efficiently in only O(L) work, and with all the earlier signatures available as byproducts, for free, of computing the final element Sig"((
This is handled by the optional stream argument to the signature function and to the logs dogsignature function.
Arbitrary intervals Given a sequence of data x (I1,..., LL). it may be desirable to query Sig ((I.,.... ..)) for many j.j such that 1 < i < < L, in Section 4.2 Using the efficient precomputation strategy described there, Signatory provides this capability via the Path class.
Keeping the signature up-to-date Suppose we have sequence of data (z1...., xL) S (IR)) whose signature Sig" N ((I1,...,xL)) has already been computed. New data subsequently arrives, some (#L+1>...- .., FLLM E S (R.), and now wish update our computed signature, for exam- ple to compute the sequence of signatures
((TI..,,
Sig
This could done by computing the signatures over (#I+I,..., TL+M). and combining them together as above. However, if these signatures (over (IL+1...... FL+M) are not themselves of interest, then this approach may be improved upon, as this only exploits the grouplike structure, but not the fused caltiply-exponenttian described in Section 4.1
Computing them in this more efficient way may be handled via the basepo nt and initial arguments to the sig gnature function, and via the update method of the Path class.
BENCHMARK PERFORMANCE
We are aware of two existing software libraries providing similar functionality, esig (Lyons 2017) and i iisignattun ure (Reizenstein & Graham 2018). We ran a series of benchmarks against the lat- est versions of both of these libraries, namely esig 0.6.31 and i lisis iisignattt gnature 0.24. The computer used was equipped with a Xeon E5-2960 v4 and a Quadro GP100, and was running Ubuntu 18.04 and Python 3.7.
Note that we start with Sig ((#1, two is the shortest sequence of data can be to define a path; Definition 4

---

Published as a conference paper at ICLR 2021
eog
mi Sinntorr CPU tno paralltii
ssenatum
Signebory CPU Ind parslel ginotory erU
Signetory CRU (paralte)
Signetory CPU iparaltti
Signttory BrU
100
"the second
Numbar Charnds
Dopth
Signature forward, varying channels
(b) Signature forward, varying depths
Figure I: Time taken on benchmark computations to compute the signature transform. esig is only shown for small operations is incapable of larger operations. Note the logarithmic scale.
15 1sarooure
Signatory CNI the paraitell Sign atory GPU
escnsture
Benstory CPU tne psratell Signatory DPU
5 vetoryy CPU (peralle
Signetory CPU (parall))
327
101
10a
Tiee seconds
307
30:1
10:3
10"
Charnass
Dupch
(a) Signature backward, varying channels
(b) Signature backward, varying depths
Figure 2: Time taken on benchmark computations to backpropagate through the signature transform. esig is not shown as it is incapable of computing backward operations. Note the logarithmic scale.
6.1 DIRECT COMPARISON
For esig and iis gigntuure we report time the CPU, whilst for Signatory we report run time on the GPU, CPU with parallelism, and CPU without parallelism. As it is in principle possible to parallelise these alternative libraries using Python's multiprocess important comparisons are to Signatory on the CPU without parallelism (representing like-for-like computational resources), and on the GPU (representing the best possible performance).
module") the most
We begin with benchmark for the forward operation through the signature transform. We consider a batch of 32 sequences, of length 128. We then investigate the scaling as we vary either the number of channels (over 2-7) in the input sequences, the depth (over 2-9) of the signature transform. For varying channels, the depth was fixed at 7. For varying depths, the channels was fixed at 4.
Every test case is repeated 50 times and the fastest time taken. See Figure 1 Note the logarithmic scale.
We observe that i iisignature is Signatory's strongest competitor in all cases. Signatory and iis disignature ure are comparable for the very smallest computations. As the computation in- creases in size, then the CPU implementations of Signatory immediately overtake iisignature, followed by the GPU implementation.
For larger computations, Signatory be orders of magnitude faster. For example, to compute the signature transform with depth and number of channels both equal to 7, then iist Lisignate ture takes 20.9 seconds to perform the computation. In contrast, running the CPU without parallelism,
"Subject nontrivial overhead.
8

---

Published as a conference paper at ICLR 2021
Signatory takes only 3.8 seconds, which represents 5.5% speedup. We emphasise that the same computational resources (including lack of parallelism) were used for both. To see the benefits of GPU implementation over a CPU implementation the primary motivation for Signatory s existence-then we observe that Signatory takes only 0.16 seconds to compute this same operation. Compared to the best previous alternative in i iisiigg iisignaturr this represents 132x speedup.
Next, we consider the backward operation through the signature transform. We vary over multiple inputs as before. See F We again observe the same behaviour. i iisignature is Signatory's strongest competitor, but is still orders of magnitude slower on anything but the very smallest of problems. For example, to backpropagate through the signature transform, with depth and number of channels both equal to 7, then Signatory on the CPU without parallelism takes 13.7 seconds. Meanwhile, i gnaturs takes over minutes 128 seconds to perform this computation on like-for-like computational resources. Running Signatory on the GPU takes fraction of a second, specifically 0.772 seconds. These represent speedups of 9.4 and 166x respectively.
For further speed benchmarks, discussion on memory usage benchmarks, the precise numerical values of the graphs presented here, and code to reproduce these benchmarks, see Appendix We observe the same consistent improvements on these additional benchmarks.
6.2 DEEP LEARNING EXAMPLE
To emphasise the benefit of Signatory to deep learning applications, we consider training deep signature model (Bonnier et al.) 2019) a toy dataset of geometric Brownian motion samples. The samples have one of two different volatilities, and the task is to perform binary classification.
The model sweeps small feedforward network hidden states), applies the signature transform, and then maps to a binary prediction via a final learnt linear map. This model has leartt parameters prior to the signature transform, and in particular backpropagation through the signature transform is necessary.
the input sequence (to produce sequence of
The signature transform is computed either using Signatory, or using iisignature. We train the model on the GPU and plot training loss against wall-clock time.
ioly nture
asggeature
5 gnaborry
gnatory
10000
20020
30000
43200
Wall clock me
Figure 3: Loss against wall-clock time for deep signature model. Both plots are identical; the second plot uses a log-scaled x-axis.
Both models train successfully, but the model using Signatory trains 210 times faster than the one using iisignature. This makes clear how signatures have previously represented the largest computational bottleneck. The improvement of 210x is even larger than the improvements ob- tained the previous section. We attribute this to the fact that i iisignature necessarily has the additional overhead copying data from the GPU to the CPU and back again.
7 CONCLUSION
We have introduced Signatory, a library for performing functionality related to the signature and logsignature transforms, with particular focus applications to machine learning. Notable contri- butions are the speed its operation, its GPU support, differentiability every provided operation, and its novel algorithmic innovations.

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGEMENTS
This work was supported by the Engineering and Physical Sciences Research Council [EP/L015811//].
REFERENCES
Patric Bonnier, Patrick Kidger, Imanol Pérez Arribas, Cristopher Salvi, and Terry Lyons. Deep signature transforms. In Neural Information Processing Systems, 2019.
Djalil Chafai and Terry Lyons. Coropa project, 2005, http::::/ccrop..suucceeeeee rde/]
Ricky T. Q. Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural Ordinary Differential Equations. In Advances in Neural Information Processing Systems 31, pp. 6571 6583. Curran Associates, Inc.. 2018.
I. Chevyrev and A. Kormilitzin. A primer on the signature method in machine learning arXiv preprint arXiv:1603.0377 033888, 2016.
Christa Cuchiero, Lukas Gonon, Lyudmila Grigoryeva, luan-Pablo Ortega, and Josef Teichmann. Discrete-ting time signatures and randommess in reservoir computing. (tt1:20000.46155, 2020.
Adeline Fermanian. Embedding and learning with signatures. arXiv: 1.12111,,,,,,, 2019.
Amir Gholami, Kurt Keutzer, and George Biros. Anode: Unconditionally accurate memory-efficien gradients for neural odes. Proceedings of the Twenty-Eighuh International Joint Conference on Artificial Intelligence, 2019.
Liam Hodgkinson, Chris van der Heide, Fred Roosta, and Michael Mahoney, Stochastic Normaliz- ing Flows. arXiv:2002.09547, 2020.
https///gaatuub.cmmpaaaaiii- hiipr///cckkkkierrrrrrcccece Patrick Kidger. torchode, 2020.
Patrick Kidger, James Morrill, and Terry Lyons. Generalised Interpretable Shapelets for Irregular Time Series. arXiv:2005.13348 2020.
Franz J Király and Harald Oberhauser. Kernels for sequentially ordered data. Journal of Machine Learning Research, 2019.
A. B. Kormilitzin, E. A. Saunders, J. Harrison, J. R. Geddes, and T. Lyons. Application of the signature method to pattern recognition in the cequel clinical trial. arXiv: (600::666.0000 020744 2016.
Pierre Lalonde and Arun Ram. Standard lyndon bases of lie algebras and enveloping algebras. Transactions of the American Mathematical Society, (47 1995.
D. Levin, Lyons, and H. Ni. Learning from the past, predicting the statistics for the future, learning evolving system. arXiv:1309.022 2013.
Chenyang Li, Xin Zhang, and Lianwen Jin. LPSNet: novel log path signature feature based hand gesture recognition framework. In Proceedings of the IEEE International Conference on Computer Vision, pp. 63 631-639, 2017.
Shujian Liao, Temry Lyons, Weixin Yang, and Hao Ni. Learning stochastic differential equations using rnn with log signature features. 2019.
M. Lothaire. Combinatorics on words. 1997.
Terry Lyons. Rough paths, signatures and the modelling of functions on streams. 4rXiv:1405.4537, 2014.
Temry Lyons. esig, 2017. URL
Terry Lyons, Michael Caruana, and Thierry Levy. Differential equations driven by rough paths. Springer, 2004. Éeole d' Été de Probabilités de Saint-Flour XXXIV 2004.
10

---

Published as a conference paper at ICLR 2021
Terry Lyons, Hao Ni, and Harald Oberhauser. A feature set for streams and application to high- frequency financial tick data, In Proceedings of the 2014 International Conference on Big Data Science and Computing, pp. 1-8, 2014.
Terry J Lyons. Differential equations driven by rough signals. Revista Matemática Iberoamericana, 14(2):21-310,, 1998.
Ming Min and Tomoyuki Ichiba. Convolutional Signatures for Sequential Data. arXiv:2009.06719, 2020.
Michael Moor, Max Horn Christian Bock, Karsten Borgwardt, and Bastian Rieck. Path Imputation Stratgies for Signature Models. arXiv:2005 /2359, 2020.
James Morrill, Adeline Fermanian, Patrick Kidger, and Terry Lyons. A Generalised Signature
Method for Time Series. arXiv:2006.00873, 2020a.
James Morrill, Patrick Kidger, Cristopher Salvi, James Foster, and Terry Lyons. Neural CDEs for Long Time-Series via the Log-ODE Method. Machine Learning and the Physical Sciences, NeurlPS Workshop. 2020b.
James Lewis Morrill, Andrey Kormilitzin, Alejo Nevado-Holgade Sumanth Swaminathan, Sam Howison, and Terry Lyons. The signature- based model for early detection of sepsis from elec- tronic health records in the intensive care unit. In International Conference in Computing in Cardiology 2019 (CINC 2019), 2019.
Hao Ni, Lukasz Szpruch, Magnus Wiese, Shujian Liao, and Baoren Xiao. Conditional Sig- Wasserstein GANs for Time Series Generation. (Tt1:20000.54221,, 2020.
Imanol Perez Arribas, Guy M. Goodwin, John R. Geddes, Terry Lyons, and Kate E. A. Saunders. A signature-based machine learning model for distinguishing bipolar disorder and borderline per- sonality disorder. Translational Psychiatry, 8(1):274, 2018.
Imanol Perez Arribas, Cristopher Salvi, and Lukasz Szpruch. Sig-SDEs model for quantitative finance. arXiv:2006.002/8, 2020.
Jeremy Reizenstein. Iterated-integral signatures in machine learning. 2019, URL http::/wrrar
warwick.ac.uk//333.
Jeremy Reizenstein and Benjamin Graham. The iisignature library: efficient calculation of iterated- integral signatures and log signatures. arXiv: /00v./802.0555 082522 2018.
Christophe Reutenauer. Free Lie Algebras. Clarendon Press, 1993.
Csaba Toth and Harald Oberhauser. Bayesian Learning from Sequential Data using Gaussian Pro- cesses with Signature Covariances. International Conference on Machine Learning, 2020.
Weixin Yang, Lianwen Jin, and Manfei Liu. Deepwriterid: An end-to-end online text-indeppndent writer identification system. IEEE Intelligent Systems, 3 31(2):45-53 2016a.
Weixin Yang, Lianwen Jin, Hao Ni, and Terry Lyons. Rotation-fret online handwritten character recognition using dyadic path signature features, hanging normalization, and deep neural network. In 2016 23rd International Conference Pattern Recognition (ICPR), pp. 4083-4088. IEEE, 2016b.
11

---

Published as a conference paper at ICLR 2021
A FURTHER DETAILS OF ALGORITHMIC IMPROVEMENTS
A.1 FUSED CELLTIPLY-EXPNEETTIEE
The conventional way compute signature is iterate through the computation described by equation (3) for each new increment, take its exponential, and X on to what has already been computed: repeat.
Our proposed alternate way is to fuse the exponential and X into a single operation, and then itera- tively perform this fused operation.
We now count the number multiplications required to compute
N
N
II ==
R
8k
x
RR
II
[
Ok
A=1
A, + A exp(22
for each approach.
We will establish that the fused operation uses fewer multiplications for all possible 2 1 and N 1. We will then demonstrate that is in fact of a lower asymptotic complexity.
A.1.1 THE CONVENTIONAL WAY
The exponential is defined
exp: IR
II
[R.)
8k
km
2:2
20
exp: x H+
[r
31
N!
Bonnier al. (2019 Proposition 15).
Note that every tensor in the exponential is symmetric, and so in principle requires less work to compute than its number of elements would suggest. For the purposes of this analysis, to give the benefit of the doubt to competing method, we shall assume that this is done (although taking advantage of this in practice is actually quite hard (Reizenstein & Graham 2018 Section 2)). This takes
Σ (a+((++h)1) k
k=2
scalar multiplications, using the formula for unordered sampling with replacement (Reizenstein & Graham 2018, Section 2), under the assumption that each division by scalar costs the same as multiplication (which can be accomplished by precomputing their reciprocals and then multiplying by them).
Next, we need to count the number of multiplications to perform a single Н.
Let
A, B
R
OK
Let A = (AI...,,Ay AN). with
A; (AP iSh...iis
and every Alindd
R. Additionally let Ag = 1. Similarly for B. Then E is defined by
N
x:
II R )
x
II R
II
R
k=1
R=1
8: A, B +
Σ
A, BR-s
ISKEN
12

---

Published as a conference paper at ICLR 2021
where each
A 2 Bk-; = (Aqt Bk= Bl
the usual tensor product, the result is thought of as tensor in (RR)),, and the summation is taken in this space. See Bonnier et al. (2019) Definition A.13).
To the authors' knowledge there has been no formal analysis of a lower bound on the computational complexity of X and there is no better way to compute than naively following this definition.
This, then, requires
k-
R-
ΣΣ
Σ
Σ
d
Σ
(k: - 1)dt
k=1
scalar multiplications.
Thus the overall cost of the conventional way involves
N
d + (++--1)
1)
N
C)d,
=
d
Σ
(k 1)d
(9)
k
k=2
k=1
scalar multiplications.
A.1.2 THE FUSED OPERATION
Let A E II (Rd) @K
and
Rd Then
20(
A exp(2)
Σ 1
A ②
(lc
i)!
ISKSN
where the k-th term may be computed by a scheme in the style of Horner's method:
(kk-1
A 3
(k ii!
1=0
+ A1)
2 + A2
2
+
+ Ak-1) + Ak.
(10)
k
2
As before, we assume that the reciprocals costs the same multiplication.
1 ..... have been precomputed, so that each division
Then we begin by computing x/2...., z/N. which takes d(N 1) multiplications.
Computing the k-th term in equation 10 then involves d² + dd +... + dt multiplications. This because, working from innermost bracket to outermost, the first @ produces a a d matrix as the outer product of two size d vectors, and may thus be computed with d2 multiplications; the second & produces a x d x tensor from a x d matrix and a size vector, and may thus be computed with d multiplications; and so on.
Thus the overall cost a fused multiply-exponentian is
F(d, d(N +
(II)
k=
scalar multiplications.
13

---

Published as a conference paper at ICLR 2021
A.1.3 COMPARISON
We begin by establishing the uniform bound F(d, N) C(d, for all 2 and N 1. First suppose d = 1. Then
F(L,N) -N Σ
(k:
kml
2N 1)+ + Σ 1)
k=1
C(1
Now suppose N 1. Then
F(d, = 0 C(d,1)
Now suppose N =2 Then
F(d,2) d+ &
(d+11 1)
S d+
d8
C(d,2)
Now suppose d 2 2 and N 3. Then
N &
F(d, = d(N 1)+ ΣΣ d'
k= i=2
N42 d (N - 1) + (N - 1)d
(12)
(d - 1)2
And
d+ dd (d+k-1))
1)
N
C(d,N) = Σ
Σ
(k 1 1)
k
k=2
> (k - 1)ct
k=1
(N 1)d N4 d
(13)
(d-1)²
Thus we see that it suffices to show that
N22 L (N 1)de + (N 1)d < (N 12d Nd d3
for d 2 and N 2 3. That is,
N+1 (d(N - N) + dade + N(P - 1)-
(14)
At this point 2, N must be handled as a special case, and may be verified by direct evaluation of equation (14 So now assume d > 2, N 2 3, and that d = 2, N = 3 does not occur jointly. Then we see that equation (4p is implied by
0 d(N 2) - and 0 df
of + N( 1.
The second condition trivially true. The first condition rearranges to N/(N - 2) < d, which is not not jointly true.
now true for d 2 2, N 2 with d 2, N
This establishes the uniform bound F(d < C(d,
Checking the asymptotic complexity is much more straightforward. Consulting equations
12 and
shows that F(d, n) O(d²) whilst C(d, N) 9(Nd ), And in fact as (d+k-1) equation (9) demonstrates that C(d, N) ONN
dx then
14

---

Published as a conference paper at ICLR 2021
A.2 LOGSIGNATURE BASES
We move on to describing our new more efficient basis for the logsignature.
A.2.1 WORDS, LYNDON WORDS, AND LYNDON BRACKETS
A {a1....,,a, )d) be set of d letters. Let A+N between 1 and N inclusive. For example abab E A
HN be the set of all words in these letters, of length + is word of length two.
Impose the order ai < 42 < ... A-N of the same length as each other, so that for example 0142 < 0144 < d2ar. Then a Lyndon word (Lalonde & Ram 1995) is word which comes earlier in lexicographic order than any of its rotations, where rotation corresponds to moving some number of letters from the start of the word to the end of the word. For example azdgdza4 is a Lyndon word, it is lexicographically earlier than 020z4402, 03040202 and 04020203- Meanwhile 02a2 is not Lyndon word, as it is not lexicographically earlier than d202 (which is rotation). Denote by (A+*) the set of all Lyndon words of length between 1 and N.
A, and extend it to the lexicographic order words in
Given any Lyndon word w1 W,, with 2 and w; A, we may consider its longest Lyndon suffix; that is, the smallest j > for which w..... is a Lyndon word. (It is guaranteed to exist as W4, alone is Lyndon word.) It is fact (Lalonde & Ram 1995) that w1 .-- wy-1 then also Lyndon word. Given Lyndon word w, we denote by w" longest Lyndon suffix, and by w the corresponding prefix.
... Wn
Considering spans with respect R, let
[., I: span(A+N) x span(A+N) - span(A+N)
be the commutator given by
[w, 2| = wz -w0
where wz denotes concatenation of words, distributed over the addition, as w and æ belong to a span and thus may be linear combinations of words. For example 2a, 02 + aj and ai + 0g gives wz = 20y020 + 20; 0243 + a101 + a103.
Then define
6: C (A-*)= + span(A+N))
by x(w) = w if w is word of only a single letter, and by
<(w) [o(w"), v(w0)
otherwise. For example,
ø ((a102a))
= ((1,,a2) a2]
= |a|a2 - 02a1, [2]
0102a2 20raia2 a20201
Now extend ó by linearity from L (A+N) to span([ span(C(At (A+*))) so that
Φ: span(C (C (A+N)) span
linear map between finite dimensional real vector spaces, from a lower dimensional space to higher dimensional space.
Next, let
1b A span(C (A**))
be such that (w) if w E L (A*N)) and vww) = 0 otherwise. Extend & by linearity to span([A+N), that
# span(AA - (p (A+N))
a linear map between finite dimensional real vector spaces, from a higher dimensional space to a lower dimensional space.
15

---

Published as a conference paper at ICLR 2021
A.2.2 A BASIS FOR SIGNATURES
Recall that the signature transform maps between spaces follows.
Sig 8 (R.*
II k=1
(R.))R
R ok
Let {er 11sis i d} the usual basis for R Then
fes, Cit |1 ix S d}
is a basis for (1Z))8K. An arbitrary element of I (R*) @k
may be written as
Oipond Cjj 2 ... Cig
(15)
f2=1
ISKEN
for some "i.....
Then A may be used to represent basis for II -== (Rd) @k Identify C, @ ... @ ev with
a, Oi. Extend linearly, so to identify expression (15) with the formal sum of words
Oi Oi die-
k=1 f1pedgml
With this identification,
span (A NN
(R))a
(16)
A.2.3 BASES FOR LOGSIGNATURES
Suppose we have some E S (R.). Using the identification in equation (16). then may attempt seek some x E {p (A+N)) such that
((x) log (Sigg(())
(17)
This is an overdetermined linear system. As matrix ø tall and thin. However it turns out that image (log) image (ő) and moreover there exists unique solution (Reizenstein & Graham 2018). (That is an overdetermined system is typically the point of the logsignature transform over the signature transform, it then represents the same information in less space.)
If x ELEC(AtN) arl, with ag E R, then by linearity
aro(E) = log (Sig" (xx),
(EC(ALN)
so that &C (At+)) is basis, called the Lyndon basis, of image (log). When calculating the logsignature transform a computer, then the collection of a are sensible choice for representing the result, and indeed, this is what is done by iisignature. See Reizenstein & Graham (2018) for details this procedure.
However, it turns out that this is unnecessarily expensive. In deep learning, it is typical to apply leartt linear transformation after a nonlinearity in which case we largely do not care in what basis represent the logsignature, and it turns out that
find more efficient one.
The Lyndon basis cxhibits a particular triangularity property (Reutenauer 1993. Theorem 5.1), (Reizenstein, 2019 Theorem 32), meaning that for all & E L (A+*), then ((E) has coefficient zero for any Lyndon word lexicographically earlier than f. This property has already been exploited by iisignature solve (17) efficiently, but we do better: means that
s/ tb span (f. (A+N)) span (L (A++))
16

---

Published as a conference paper at ICLR 2021
is triangular linear map, and so in particular it is invertible, and defines change of basis; it is this alternate basis that we shall use instead. Instead of seeking r as in equation (17), we may now instead seek span (- (AA ((+N) such that
( (+ (z) = log (Sig (x))
But by simply applying u both sides:
(log (Sig (x)))
This is now incredibly easy to compute. Once log (Sig (x)) has been computed, and interpreted in equation (T6), then the operation of is simply extract the coefficients of all the Lyndon words, and we are done.
B LIBTORCH VS CUDA
LibTorch is the C++ equivalent to the PyTorch library. GPU support in Signatory was provided by using the operations provided by LibTorch.
was a deliberate choice not to write custom CUDA kernels. The reason for this is as follows. We have to make choice between distributing source code and distributing precompiled binaries. If we distribute source code, then we rely on users being able to compile CUDA, which is far from a guarantee.
Meanwhile, distributing precompiled binaries is unfortunately not feasible on Linux. C/C++ exten- sions for Python are typically compiled for Linux using the 'manylinux' specification, and indeed PyPI will only host binaries claiming to be compiled according to this specification. Unfortunately, based on our inspection of its build scripts, PyTorcc appears not conform this specification, instead compiles against later version of Centos than is supported by manylinux, and then subse- quently modifies things so as to seem compatible with the manylinux specification.
Unpicking precisely how PyTorch does this so that we might duplicate the necessary functionality (as we must necessarily remain compatible with PyTorch as well) was judged finickity task full of hard-to-test edge cases, that is an implementation detail of Py PyTocc that should not be relied upon, and that may not remain stable across future versions.
C BACKPROPAGATION
Backpropagation calculated the usual way, mathematically speaking, by treating the signature and logsignature transforms composition of differentiable primitives, discussed in Section
The backpropagation computations are handwritten, and are not generated autodifferentiably. This improves the speed of the computation by using C++ primitives, rather than high-level tensors.
C.I REVERSIBILITY
Moreover, it allows to exploit reversibility property of the signature (Reizenstein, 2019). When backpropagating through any forward operation, then typically the the forward results are stored in memory, as these are used in the backward pass.
However, recall the grouplike structure of the signature; in particular this means that
Sig
= Sig (( (())) X Sig ((LL-1)Z1))-1
Sig ((I1...,, & Sig ((IL
(18)
Consider the case of Sig ((2) ((F)....,T,)) by iterating through equation (3) from left to right. Re- versibility means we not need to store the intermediate computations Sig ((x),..., 2T))): given
the final Sig N ((I),..., 2r))), we can recover Sig N ((z)...., ..), in the order that they are needed in the backward pass by repeatedly applying equation (18)
17

---

Published as a conference paper at ICLR 2021
We remark in Section 2.5 that the signature may be interpreted as the solution to differential equa- tion. This recomputation procedure actually corresponds to the adjoint method for backpropagating through a differential equation, popularised in machine learning via Chen et al. (2018).
Importantly however, this does not face reconstruction errors in the same way as neural differential equations (Gholami al. 2019). Because the driving path f is taken to be piecewise affine in Definition then the differential equation defining the signature may be solved exactly, without numerical approximations.
Equation 18) uses the same basic operations as the forward operation, and can be computed using the subroutines, including the fused multiply-epponentate.
C.2 SPEED VERSUS MEMORY TRADE-OFFS
The reversibility procedure just described introduces the additional cost of recomputing the path (rather than just holding it in memory). principle this need not be performed by holding partial results in memory.
For simplicity we not offer this an alternative with Signatory. Signature-based techniques are often applied to long or high-frequency data (Lyons et al.) 2014 Morrill et al. (2020b), for which the large size of multiple partially computed signatures can easily become memory issue. Nonetheless this represents opportunity for further work.
C.3 PARALLELISM
The use parallelism in the gradient computation depends upon whether to use reversibility as discussed.
Consider first the case in which reversibility not used, and all intermediate results are held in memory. As discussed in Section 5.T] the forward operation may be computed in parallel reduction. The computation graph (within the signature computation) then looks like a balanced tree, and the backward operation through this computation graph may be performed in parallel as well.
However if reversibility is used then only the final Sig" ((11, ))) is held in memory, then the necessary intermediate computations to backpropagate in parallel are not available.
As Signatory uses reversibility then backpropagation is not performed in parallel.
This represents an opportunity for further work, but practically speaking we expect that its impact is only moderate. Backpropagation typically performed as part training procedure over batches of data; thus the available parallelism may already saturated by parallelism over the batch, and by the intrinsic parallelism available within each primitive operation.
D FURTHER BENCHMARKS
D. CODE FOR REPRODUCIBILITY
The benchmarks may be reproduced with the following code on Linux system. First we install the necessary packages.
pip install numpy==1, .180 matplot1ib==3, .0.3 torch==1.5.0
pip install Lisignature==0.22 esig==0, 6.31 signatory==1..2 2..11.11...111111 git clone hetps://githhne cd signatory
Note that numpy must be installed before iisignature, and PyTorch must be installed before Signatory. The unusually long version number for Signatory is necessary to specify both the ver- sion of Signatory, and the version of PyTorch that it is for. The git clone is necessary as the benchmarking code is not distributed via pip.
18

---

Published as a conference paper at ICLR 2021
Now
python command. py benchmark -help
for further details how any partieular benchmark. For example,
python. command. benchmark -m time -f sigf channels -o graph
will reproduce Figure
D.2 MEMORY BENCHMARKS
Our benchmark scripts offer some limited ability to benchmark memory consumption, via the -m memory flag to the benchmark scripts.
The usual approach such benchmarking, using valgrind' massif, necessarily includes mea- suring the set-up code. As this includes loading both the Python interpreter and PyTorch, measuring memory usage of our code becomes tricky.
As such we use an alternate method, in which the memory usage is sampled at intervals, using the Python package memory_pros filrr which may be installed via pip install memory_pree www.proiiiii profilers ler. This in turn has the limitation that may miss peak in memory usage; for small calculations may miss the entire calculation. Furthermore, the values reported are incon- sistent with those reported in Reizenstein & Graham 2018).
Nonetheless, when compared against i i disignature using pamoooyyprofierr,. on larger com- putations where peaks are less likely to go unobserved, then Signatory typically uses at order of magnitude less memory. However due to the limitations above, we have chosen not report quantita- tive memory benchmarks here.
D.3 SIGNATURE TRANSFORM BENCHMARKS
The precise values of the points of Figures D and are shown in Tables 4
For convenience, the ratio between the speed of Signatory and the speed of iisignature is also shown.
D.4 LOGSIGNATURE TRANSFORM BENCIIMARKS
See Figure 4 for the graphs of the benchmarks for the logsignature transform.
The computer and runtime environment used was as described in Section
We observe similar behaviour to the benchmarks for the signature transform. uisignature is slightly faster for some very small computations, but that as problem size increases, Signatory swiftly overtakes 1is Lisignature, and orders of magnitude faster for larger computations.
The precise values of the points on these graphs are shown in Tables 5
Times are given in seconds. Also shown is the ratio between the speed of Signatory and the speed of ii sisiinatuee. dash indicates that es ig does not support that operation.
D.5 SINGL--HLEMENTTBBTICH BENCHMARKS
The benchmarks so far considered were for batch of samples (of size 32). Whilst this is of particu- lar relevance for training, is sometimes less relevant for inference. We now repeat all the previous benchmarks (forward and backward through both signature and logsignature, varying both depth and channels), except that the batch dimension is reduced to size See Figures Flad Numerical values presented in Tables 16
19

---

Published as a conference paper at ICLR 2021
Here very small problems that iisignature outperforms Signatory by about millisecond, but that once again Signatory overtakes i iisignaurre on reasonably problems, and is still orders of magnitude faster larger problems.
We do not regard the performance on very small single-clement problems as a drawback of Signa- tory. If performing very few very small calculations, then the difference of millisecond is irrelevant. performing very many very small calculations, then these can typically be batched together.
Table I: Signature forward, varying channels. Times are given in seconds. A dash indicates that esig does not support that operation.
Channels
5
esig
0.531
9.34
lisignature
0,00775
0.0632
0.375
1,97
7.19
20.9
Signstory CPU
0.00327
0.0198
0.101
0.402
1.45
(no parallel)
Signatory CPU
0.00286
0.00504
0.00975
0.0577
0.21
1.22
(purallel)
Signatory
0.0129
0.0135
Ratio CPU
2.37
3.19
3.71
4.89
4.95
5.49
(no parallel)
2.71
12.5
38.5
34.1
34.2
17.0
(parallel)
Ratio GPU
0.602
4.68
20.6
88.7
120
132
Table Signature backward, varying channels. Times are given in seconds. dash indicates that esig does not support that operation.
Channels
2
5
6
esig
1 gnature
0.026
0.248
1.59
7.78
27.6
128
Signatory CPU
0.0222
0.106
0.428
1.54
4.97
13.7
(no parallel)
Signatory CPU
0.0623
(paralle))
Signatory GPU
0.0472
0.0413
0.0534
0.119
0.314
0.772
Ratio CPU
2.34
9.38
(no parallel)
Ratio CPU
2.82
3.97
7.69
7.92
14.2
(purallel)
Ratio GPU
0.551
29.7
65.2
Table 3: Signature forward, varying depths. Times are given in seconds. A dash indicates that esig does not support that operation.
Depth
esig
0.019
0.0954
0.527
2.73
15.5
iisignature
0.00145
0.376
8.16
Signatory
0.000708
0.00129
0.0022
0.00765
0.027
0.104
0.402
1.68
(no parallel)
Signatory CPU (parallel)
0.000722
0.00242
0.00279
0.00321
0.00546
0.0161
0.0408
0.381
Signatory GPU
0.00172
0.00326
0.00484
0.00735
0.0104
0.0132
0.0232
0.0773
Ratio CPU
0.661
1.12
2.2
2.61
3.18
3.6
4.55
4.86
(no parallel)
Ratio CPU
0.649
0.597
6.21
15.7
23.3
44.8
21.4
(parallel)
Ratio GPL:
0.273
0.443
1.0
2.71
8.34
28.3
79.0
106
20

---

Published as a conference paper at ICLR 2021
Table 4: Signature backward, varying depths. Times are given seconds. A dash indicates that esig does not support that operation.
Depth
2
esig
1..5 gigguuure
0.00149
0.00438
0.0179
0.0954
0.366
1.59
7.72
34.7
Signatory CPU
0.00322
0.00518
0.0123
0.0347
0.109
0.437
6.31
parallel)
Signatory CPU
0.00354
0.00409
0.0089
0.0152
0.0563
0.175
0.839
4.06
(parallel)
Signatory
0.00525
0.495
Ratio CPU
0.464
0.845
1.45
2.75
3.37
3.63
4.28
5.49
parallel)
CPU
0.422
1,07
2.02
6.28
6.51
9.07
9.21
8.54
(parallel)
Ratio GPU
0.284
0.478
1.19
4.42
11.3
31.7
53.8
70.1
Signetory
307
307
304
10"
Namber channate
Number charmetc
(a) Logsignature forward, varying channels
(b) Logsignature backward, varying channels
55g
lognosure
ldignauure
signotery L/U tne porolteii
5 ggawtory CPU toe paral Sigwhory CPU
Signatoryy CPU (panailel)
Signatory CPU (paralie))
Sipnatory tPU
30
Time 5000 dd
307
30-3
10*1
18.4
Deptth
Depih
(c) Logsignature forward, varying depths
(d) Logsignature hackward, varying depths
Figure 4: Time taken on benchmark computations to compute the specified operation. In all cases the input
batch of 32 sequences of data, each of length 128. For varying channels, the depth was fixed at 7. For varying depths, the channels was fixed 4. Every test case was repeated 50 times and the fastest time taken. Note that esig only shown for certain operations it incapable of computing large operations or of computing backward operations. Note the logarithmic scale.
21

---

Published as a conference paper at ICLR 2021
Table Logsignature forward, varying channels. Times are given seconds. dash indicates that esig does not support that operation.
Channels
2
5
6
coig
0.539
8.61
1. gnature
0.0037
0.0591
0.412
2.0
7.26
27.9
Signatory CPU
0,0258
0.125
(no panallel)
Signatory CPU
0.108
1.87
(purallel)
Signatory GPU
0.0176
0.0164
0.0149
0.0243
0.0638
0.165
Ratio CPU
6.36
(no parallel)
Ratio CPU
0.952
8.89
16.1
18.4
20.1
14.9
(parallel)
Ratio GPU
Table 6: Logsignature backward, varying channels. Times are given in seconds. A dash indicates that esig does not support that operation.
5
esig
uirignature
0.0346
Signatory
0.0243
0.114
0.421
1.87
5.34
17.9
(no parallel)
Signatory CPU
0.0152
0,0503
0.302
1.03
3,47
9.34
(parallel)
Signatory GPU
0.0478
0.05
0.058
0.127
0.323
0.79
Ratio CPU
1.42
2.83
4.81
5.17
6.4
6.24
(no purallel)
Ratio CPU
6.69
11.9
(parallel)
Ratin GPU
0.723
6.44
34.9
76.2
106
141
Table 7: Logsignature forward, varying depths. Times are given in seconds. A dash indicates that esig does not support that operation.
Depth
estig
0.0185
0.0815
0.517
2.67
14.6
ilaignature
0.0001
0.000502
0.00188
0.0197
0.107
0.423
2.07
9.98
Signatory CPU
0.000888
0.00152
0.00272
0.00849
0.0315
0.124
0.534
2.28
(no parallet)
Signatory CPU
0.000886
0.00285
0.00355
0.00466
0.00891
0.0251
0.0801
0.536
(parallel)
Signatory GPL
0.00196
0.00453
0.00558
0.0161
Ratio CPI:
0. 124
0.33
0.693
2.33
3.41
3.42
3.88
4.37
parallel)
Ratio CPL
0.124
0.176
0.531
4.23
12.0
16.9
25.9
18.6
(parallel)
Ratio GPU
0.0561
0.111
0.337
2.42
6.67
28.4
79.0
120
22

---

Published as a conference paper at ICLR 2021
Table 8: Logsignature backward, varying depths. Times are given in seconds. dash indicates that esig g does not support that operation.
Depth
7
esag
11.. grature
0.000189
0.00572
0.0225
0.0968
0.432
1.98
9.36
42.3
Signatory CPU
0.0033
0.00555
0.0127
0.0351
0.133
0.408
6.84
(nD parailel)
Signatory CPU
0.00363
0.0051
0.0103
0.0197
0.0562
0.287
1.02
4.13
(parallel)
Signatory
0.00559
0.00979
0.0253
Ratio CPU
0.0573
1.03
1.78
2,76
3.25
4.86
5.54
6.19
(no parallel)
Ratio CPU
0.0521
1.12
2.18
4.91
7.69
6.89
9.13
10.2
(parallel) Ratio GPL
0.0338
0.584
1.17
3.83
11.6
31.9
82.8
Signabture forword: time
bagnabure Ggnattry ERI (pansle)
Signatory CPU (ne panalet) Signatnry
CRU zwralle)
Signarar (paralle)
Sigrotory GFU
307
22-4
10
Number chencele
Mumber churnal
(a) Signature forward, varying channels
(b) Signature backward, varying channels
Signabure
Signature backward tire
<hig Signelory CPU swralle))
Bignaturc
Sig whory per allo Sggnaoory
Signatory CPU (paralle)
Signatury (paralle))
Signotory GFU
10-4
10-1
Time in secodd
30-4
10a1
Depth
(c) Signature forward, varying depths
(d) Signature backward, varying depths
Figure 5: Time taken on benchmark computations to compute the specified operation. In all cases the input was "batch" of sequence, of length 128. For varying channels, the depth fixed at 7. For varying depths, the channels was fixed at 4. Every test case was repeated 50 times and the fastest time taken. Note that esig g only shown for certain operations as it incapable of computing large operations or of computing backward operations. Note the logarithmic scale.
23

---

Published as a conference paper at ICLR 2021
Logsignature farward: time
Logs ghature beckward: time
e5g
tngnature
Hignature
Signatory CPU (ne panaleti sigratory
Sigronrry CHU tno zaralles
signatory cru (paralle)
Sgnatory cnU (parake0
Suraiorr GFU
10
307
10"1
00
10
Number channats
Mumber channabs
(a) Logsignature forward, varying channels
(b) Logsignature backward, varying channels
Legnignature
Logsignanura backward:
eiig
Bogeware
Rignature
wory pe alle)
sigrotory CPU peralle)
signabary cnu (paralke)
signstory cru (paralie)
story
Sigratory GPU
10a
Time sesconis
00-3
10*2
10
Death
(c) Logsignature forward, varying depths
(d) Logsignature backward, varying depths
Figure 6: Time taken on benchmark computations to compute the specified operation. In all cases the input was "batch" of sequence, of length 128. For varying channels, the depth fixed at 7. For varying depths, the channels was fixed 4. Every test case was repeated 50 times and the fastest time taken. Note that esig only shown for certain operations as it is incapable of computing large operations or computing backward operations. Note the logarithmic scale.
Table Signature forward, varying channels, single-element-batch Times are given in seconds. A dash indicates that esig does not support that operation.
Channels
2
3
5
6
7
esig
0.0142
0.228
Lisignature
0.000246
0.00244
0.0132
0.0642
0.228
0.647
Signatory CPU
0.00394
(no parallel)
Signstory CPU
0.000657
0.00262
0.00474
0.0123
0.0180
0.0317
(parallet)
Signatory GPC
0.0109
0.0104
0.0107
0.0104
0.0104
0.0110
Rario CPU
0.389
3.33
4.60
parallet)
Ratio CPL
0.374
0.929
2.77
5.24
12.6
20.4
(parallet)
Ratio GPU
0.235
1.23
6.17
24

---

Published as a conference paper at ICLR 2021
Table Signature backward, varying channels, single-element-bttch Times are given in seconds. A dash indicates that esig g does not support that operation.
Channels
2
5
coig
1. gnature
0.00085
0.00809
0.0526
0.244
0.854
2,63
Signatory CPU
0.00235
0.00454
(no parallel)
Signatory CPU
0.0109
0.0607
0.312
(purallel)
Signatory GPU
0.0356
0.0352
0.0365
0.0374
0.0369
0.0518
Ratio CPU
(no parallel)
Ratio CPU
0.129
0.745
0.867
2.47
2.73
6.06
(parallel)
Ratio GPU
0.0239
Table 11: Signature forward, varying depths, single- teleemmeettbaccee Times given in seconds. A dash indicates that esig does not support that operation.
Depth
esig
0.00085
0.0033
0.0151
0.0668
0.311
Lisignature
0.00295
0.0614
Signatory
0.000470
0.000479
0.000650
0.000753
0.00148
0.00393
0.0139
0.0526
(no parallel)
Signatory CPU
0.000597
0.000512
0.000541
0.00126
0.00228
0.00528
0.0136
0.0294
(parallel)
Signatory GPU
0.00153
0.00264
0.00416
0.00599
0.0114
0.0149
0.0135
0.0166
Ratio CPU
0.0342
0.102
0.269
0.896
1.99
3.28
4.43
5.24
(no parallel)
Ratio CPU
0.0269
0.0957
0.323
1.30
9.37
(parallel)
Ratio GPU
0.0105
0.0186
0.0419
0.133
0.259
0.861
4.60
16.6
Table 12: Signature backward, varying depths, single-element-hee blacheeetttttthhhh...e. Times are given in seconds. A dash indicates that isig does support that operation.
Depth
4
8
esig
.ssignauure
0.0000480
0.000148
0.000588
0.00251
0.01
0.0525
0.245
1.11
Signatory CPU
0.00153
0.00157
0.00184
0.00259
0.00517
0.0146
0.0513
0.195
(no parallel)
Signatory CPU (paraliel)
0.00154
0.00226
0.00419
0.00495
0.0105
0.053
0.164
0.317
Signatory GPU
0.00492
0.0202
0.0598
Ratio CPU
0.0314
0.0947
0.320
0.969
2.22
3.58
4.79
5.70
(no paraliel)
Ratio CPU
0.0311
0.0656
0.140
0.508
1.09
0.99
1.50
3.51
(parallel)
Ratio GPU
0.00975
0.0183
0.0465
0.124
0.436
1.49
5.29
25

---

Published as a conference paper at ICLR 2021
Logsignature forward, varying channels, single-element-hatch Times are given in sec- onds. A dash indicates that es i g does not support that operation.
Table 13:
Channels
2
3
6
7
csig
0.014
0.210
1..1 groture
0.000121
0.00201
0.0134
0.0653
0.231
0.658
Signatory CPU
0.00123
0.00479
0.125
(no parallell
Signatory CPU
0.00144
0.0352
(parallet)
Signatory GPL
0.0123
0.0117
0.0116
0.0120
0.0126
0,0125
Ratio CPC
(no parallel)
Ratio CPU
0.0846
0.606
2.38
4.32
10.1
18.7
(parallell
Ratio GPL
0.00391
1.15
Table 14: Logsignature backward, varying channels, single-element-bale Times are given in sec- onds. dash indicates that esig does not support that operation.
esig
uisignature
0.0103
3.29
Signatory
0.00390
0.00698
D.0163
0.0523
0.160
0.422
(no parallel)
Signatory CPU
0,00902
0.0124
0.0631
0.122
0.32
0.448
(parallel)
Signatory GPU
0.0383
0.0408
0.0384
0.0385
0.0M05
0.0542
Ratio CPU
0.286
1.48
4.02
5.95
6.82
7.81
(no purallel)
Ratio CPU
0.124
0.834
1.04
7.35
(parallel)
Ratin GPU
0.0291
0.253
1.71
8.08
26.9
60.8
Table 15: Logsignature forward, varying depths, single-element-bann Times are given in seconds. dash indicates that esig does support that operation.
Depth
8
esf
0.000837
0.00325
0.0148
0.065
0.285
1. iigature
0.00000505
0.0000137
0.0000666
0.000682
0.00300
0.0134
0.0618
0.282
Signatory CPU
0.000762
0.000666
0.000794
0.00112
0.00228
0.00519
0.0160
0.0596
(no parallel)
Signatory CPU (parallel)
0.000590
0.000674
0.00108
0.00178
0.00296
0.00612
0.0170
0.0347
Signatory GPU
0.0089
0.0189
Ratio CPU
0.00663
0.0207
0.0838
0.608
1.32
2.58
3.87
4.73
(mo parallel)
Ratio CPU
0.00843
0.0204
0.0614
0.382
1.01
2.18
3.63
8.13
(parallel)
Ratio GPU
0.00206
0.00481
0.0154
0.0766
0.239
0.767
2.72
14.9
26

---

Published as a conference paper at ICLR 2021
Table 16: Logsignature backward, varying depths, single-clement-brie Times given in sec- onds. dash indicates that esig does not support that operation.
Depth
esig
disignature
0.00000651
Signatory
0.00145
0.00182
0.00218
D.0032
0.00622
0.0164
0.0557
0.203
(no paraliel)
Signatory CPU
0.00182
0.00250
0.00363
0,00575
0.00968
0.0626
0.193
0.349
(parallel)
Signatory GPU
0.00509
0.00866
D.0143
0.0206
0.0301
0.0374
0.0509
0.0635
Ratio CPU
0.00448
0.115
0.35
1.02
2.32
4.08
5.58
6.87
(no parallel)
Ratio CPU
0.00359
0.0839
0.211
0.566
1.61
3.99
(paralle))
Ratin GPU
0.00128
0.0242
0.0534
0.158
0.48
1.79
6.11
21.9
27


Reviews:
[{"review_id": "nk8-HuJI95t", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Signatory is a library for calculating path 'signatures'. Unlike previous implementations, it engineered with machine learning uses cases in mind, supporting minibatches and GPU computation. The performance seems to be a significant improvement on previous work. This seems to be stem from a mix of algorithmic modifications and engineering work.\n\n#### Questions/Comments:\n\nIn it unclear how much of the the performance improvement is due to (i) technical optimizations like using AVX to speed up batch processing, and (ii) due to fundamental algorithmic improvements, e.g. the choice of basis. \n* How does performance compare with esig/iisignature in the batch size == 1 case, where using AVX is harder? Although batching is common during training, the 'batch size = 1' case is important in applications.\n*  Figures 5 and 6 in [A] show the FLOPs needed for each step of the path for specific dimensions and depths.\nCan you compare the number of FLOPs per piecewise-linear-segment needed by Signatory and iisignature to calculate the  log signature path-increment update?\n\np4:Section 3.1: Is the fusion a contribution of the paper, or is it similar to previous work, i.e. Section 4 in [A]? Is the difference that Signatory does kernel fusion for the signature and log-signature, but iisignature only does it for the signature?\n\np5: 'numerical stability' The experiments in article look at the run time, but not the numerical accuracy.\nThis raises a theoretical concern that Signatory might be less numerically stable than previous libraries.\n(C.f. In the case of matrix multiplication, Strassen's algorithm uses fewer FLOPs than the naive method, but is less numerically stable.) Is Signatory 'fit for purpose' for machine learning in the sense that either\n(i) the calculated signatures elements are within 5% of the true values, or\n(ii) when used in a machine learning context, test accuracy is equivalent to previous libraries?\n\n\n#### References:\n[A] Reizenstein and Graham, https://arxiv.org/pdf/1802.08252.pdf\n\n----updating in light of author's response-----\nI am upgrading to 7 as my concerns have been addressed.\nOther reviewers have questioned if ICLR is the right venue for a paper about a library.\nThe paper does describe novel algorithms that lower the big-O cost of computation, similar to how Strassen's algorithm is a non-trivial modification of the naive matrix multiplication algorithm.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Pe-QZjQXuqT", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "After reading the rebuttal from the authors, as well as the updated draft, I agree that this style of presentation and framing is much more approachable to people not familiar with sig/logsig transforms. Thus I vote to accept this as a *library* paper.\n\n\n\nLibrary papers are difficult to review, and in general reviewing them is a highly subjective process (far more subjective than reviewing in general). Although I think this library paper could be a good contribution, I'd like a subsequent edit pass by the authors with a strong focus on presentation and framing before I am fully convinced.\n\nAbove all, I'd really appreciate a library paper being an *advertisement* for the library. In the current form the paper doesn't do a good job advertising the signature and logsignature transforms as a must have in a researchers toolkit. As this is the first time many readers will learn about the existence of the signature/logsignature transform, I'd like a more significant portion of the paper's content to motivation for why these transforms are important in machine learning, as well as useful applications. What problems become significantly easier due to this transform? What useful properties does it have? I think that this deserves more real estate than say comparisons to competing libraries, as well as the precise mathematical details, which could be moved to the appendix.\n\nIt's unclear to me how to best apply this transform just by reading the paper. Interestingly, I found other application papers did a better job of describing the signature/logsignature transform. This is a definite shortcoming of this paper as I would deeply appreciate a 'text' explanation of how these transforms work. Indeed it seems that the strongest motivation for sig/logsig is their apparent purpose as a 'summarizer' of arbitrary time series. To this extent sig/logsig behave as a universal 'sketching'/compressed sensing tool for time series. Yet, I had to read other papers to figure this out.\n\nOutside of a few nitpicks, I found the mathematical presentation and definitions of the paper high quality and illuminating. In particular, after understanding what sig/logsig transform actually do, I could easily match notation to concept. I urge the authors to both present sig/logsig transforms conceptually as well as mathematically and help the reader match concept to notation.\n\nIs the purpose of backprop through sig/logsig transform to allow for usage in larger models? Could the authors give a usecase of this? Using this in practice inside a larger deep learning model would give significant weight to this contribution. Indeed, usage in a wider deep learning application of these transforms with good results would make this library a bit of a 'must-have'.\n\nIn Eq. 1 is using \\prod to define an iterated cartesian product standard? A footnote here would be useful to make this notation explicit.\n\nShould Sec 2.3 be ahead of 2.2 as it is more conceptually tied to the def'n provided in 2.1.\n\nAs the mathematical definition of tensor product is used here, could the authors clarify in the appendix/give pointers in the main paper?\n\nIn experiments how come the fastest speed is presented. Why not mean/stderror as usual?\n\nPlenty of space is wasted in Sec. 4 highlighting the contributions of the library. Can this be improved with the use of \\paragraphs instead of \\subsubsections?\n\nApplications/usecases/toy examples solved by this library would be so useful to present along with benchmarks. How difficult is this library to code with? Does it remain 'pythonic'? Does it blend well with existing pytorch code?", "extra_scores": {}, "extra_text": {}}, {"review_id": "9GCQLuv6Bz4", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n-------\nThe paper presents the first GPU-capable library implementing the _\"signature\"_ and _\"log-signature\"_ functions as well as their gradients. It introduces these transformations to a machine learning audience, as well as their recent uses in ML, then proposes algorithmic improvements that reduce the necessary computation. The resulting library is benchmarked against existing implementations, and the code, benchmarks, and proofs are included in supplementary materials.\n\nPros\n-----\n* The library makes the signature transform much more accessible to ML researchers, opening up a promising research space\n* The paper is overall really clear, especially the introduction to the signature function and the explanations about the implementation strategy\n* Benchmarks are sound and show impressive speed-ups; they seem particularly easy to reproduce thanks to the detailed instructions\n* The work goes beyond implementation of an existing algorithm in a new framework, but uses novel techniques to reduce algorithmic complexity\n\nCons\n------\n* Very few details about the implementation of back-propagation through these transforms, and of the inverse transforms, although they are an important part of the implementation\n\nRecommendation\n----------------------------\nI recommend to **accept** this paper, as the proposed library could be extremely helpful to researchers wanting to explore the signature function, especially as an intermediate transformation. The impact could be high in sequence modelling for instance.\n\nArguments\n------------------\n* A fast, differentiable implementation of an operation of interest, especially integrated in a major framework, is *highly significant* for the community, as it enables quick exploration of research ideas to incorporate it.\n* The paper is *clearly written*, and does a good job exposing the concepts of interest to an unfamiliar audience. Relevant literature is clearly cited with context.\n* The *quality* of the benchmarks is god, and care has been put in making them easily reproducible. The algorithmic improvements (reformulation of complex formulas to re-use common computations, pre-computation and re-use of inverses) are clever and especially adapted to the current ML/DL context, in particular getting rid of a costly linear transformation in the log-signature computation.\n* The work is *original* in that it is the first library to include both GPU compatibility and implementation of the gradients of such transformations, as well as the speed ups mentioned above.\n\nClarifications\n------------------\nThe main missing part is the derivation and implementation of the gradients of these transformations for reverse-mode automatic differentiation. The text glosses over it in section 4.4, but I would have appreciated if its implementation had been explained, similarly to the original transforms. For instance:\n- Is the implementation of the gradients similar or dissimilar to the forward computation?\n- Are there common parts that are re-used in both?\n- Are there different trade-offs?\n- Do the implementations benefit from the same algorithmic improvements, or other ones?\n- What are the opportunities for parallelism?\n\nFrom what I understand, the \"inverse\" transformations are really close to the original ones, but it could have been expanded upon as well.\n\nMinor points:\n- In section 4.5.4, the text mentions computing Eq. 7 not by combining intervals (as in 4.5.1), but exploiting the fused multiply-exponentiate. I assumed that section 4.5.2 was already using the fused multiply-exp for expanding intervals, is that not the case? Or is there another difference I missed between the techniques of sections 4.5.2 and 4.5.4?\n- In section A.2.1, do I understand correctly that $a_2 a_2$ would _not_ be a Lyndon word? There is no other rotation that comes before it, but it does not come *strictly* before itself either. \n\nAdditional feedback\n--------------------------------\nIt would have been particularly nice to have an empirical evaluation of the removal of the new basis of the log-signature function. As the authors state, it is unlikely to have a major impact if a linear transformation is learned afterwards, but there are cases where linear transformations can impact the dynamics of training, by improving or worsening conditioning for instance. I understand it is not the focus of this work, though.\n\nTypos:\n- A.1.1: \"naiïvely\" -> \"naïvely\"\n- A.2.1: In the definition of the longest Lyndon suffix, should it be \"the smallest $j > 1$?\n- A.2.2: In the unnamed equation before (15), should it be $1 \\leq i_1, ...$ ?\n- C.1 : \"reproducability\" -> \"reproducibility\"", "extra_scores": {}, "extra_text": {}}, {"review_id": "8czUy-QQTt", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Update:\nThe authors have revised the paper, which helps the presentation somewhat (though headings like \"The Grouplike Structure\" still come at the reader without much context).\n\nThe authors added a more application-oriented benchmark, which makes the more convincing case for practical speedup of 210x.\n\nCertainly the new \"Intuition\" section is helpful in explaining the transform.\n\nThe NT library is an interesting counterpoint on the library front. It feels a little bit apples and oranges to me because of the broad scope of that library (give me DNN, I give you NTK) as opposed to the narrower scope of this one (give me sequence, I give you [log][invert]signature). NT is munging your entire DNN into a GP kernel; signature is an implementation of O(a dozen) ops.\n\nI remain somewhat skeptical that the signature transform can enjoy wide applicability given the exponential scaling behavior, unless first and perhaps second order terms suffice for practical use-cases.\n\n---\n\nThe main contribution is a software library for computing the signature and logsignature transforms taking advantage of CPU parallelism and GPU acceleration, and providing a reverse mode derivative. Some algorithmic improvements which yield substantial speedups to the computation are described. Features of the library are described, offering more functionality than predecessor software packages.\n\nThe paper provides a background of the signature and related transforms, motivating these with selected applications including continuous differential equations (relevant to continuous normalizing flows), sepsis prediction, handwriting ID, GANs, etc.\n\nThe authors demonstrate in several benchmarks that the new library is substantially more performant (10-100x) than predecessors, which suggests it could unlock further usage by making it more practical / reducing time-per-step.\n\n\n\n+ve:\nInsofar as \"signature\" is a representation and this software lets us do backprop, this might be a fit to ICLR.\nOr perhaps it fits into the \"implementation issues, parallelization, software platforms, hardware\" CFP.\n\nAs machines become more powerful, we gain the capability of using such representations, and having software to enable this is important. \n\nThe transform can be useful in neural differential equations, an area of some interest to the community, though exploring how is beyond the scope of the paper. Stepping back, the transform seems to be used in several areas-of-interest to ICLR.\n\n-ve:\nWhile some math background is given, it feels like 8 pages may be too tight to present it thoroughly. I was not able to understand from this background what the invert/log/invertlog signature transforms are, other than \"log is a compressed representation\".\n\nThis is \"just\" about the software. It would be feel more compelling to me if the software were offered as the artifact of an application paper, or at least if the benchmarking portion were on an application instead of the pure forward/backward passes of the signature transform. As it stands, we can only speculate that there must be cases where signature was the sole bottleneck and such training setups are now ~10-100x faster. To frame it another way, it would be more interesting to see a plot of wall clock on the x axis and loss on the y axis, for some real world problem where this transform is useful, and note speedups as \"reaches loss y 50x faster\".\n\nThe paper does not discuss what appears to be a substantial downside of the approach, namely exponential scaling of memory in the truncation term N. Memory scaling may be in the appendix. What is the tradeoff between \"universally nonlinear\" and truncating N to practical values? The $d^N$ term seems quite limiting for multidimensional timeseries even as d goes to 5 or 10.\n\nThe actual algorithmic changes are around rearranging multiply-exp, and around recasting a sequential reduction as an associative reduction for parallelism.\n\n\nAccept/reject\nUndecided / weak reject\n\nMy main reservations are mainly around the goodness of fit of a solely-software paper to ICLR. At a glance, I would think the paper might better appear in a forum like SysML. Certainly the CFP includes bullets the software is relevant-to; but the way I read the CFP is that we are looking for research innovations in those spaces. Implementing accelerator friendly kernels, rearranging the math, and implementing backprop, while all very valuable contributions in a purely applied sense, do not in themselves seem to match the CFP. My opinion is pretty weak, though, because the huge speedups very well may unlock novel usages; and the \"software platforms\" part of the CFP could maybe be interpreted to match this work.\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces Signatory, a library for computing functionality related to the signature and logsignature transforms. Although a large body of the initial literature on the signature in ML focuses on using it as a feature extractor, more recent works have incorporated within modern deep learning architectures and therefore, the importance of having GPU-capable libraries (with automatic differentiation) that implement these transforms. Several algorithmic improvements are incorporated into the library. Some of the computational benefits of this library wrt to previous ones are demonstrated empirically. 

There were some concerns from the reviewers about accepting library papers at ICLR. Library papers clearly fall into the ICLR CFP and, therefore, library, frameworks and platform papers that can be relevant and impactful are welcome contributions to the community. Additionally, more signature-related papers are appearing are mainstream ML venues, hence, despite the poor scalability wrt input dimensions, this paper is definitely relevant. 

Perhaps one the drawbacks of this paper is the lack of a more rigorous empirical evaluation. The authors have added a deep learning benchmark, which is welcome but only on a toy dataset. There are still some concerns about the wide applicability of the signature (and its relatives) given its exponential scaling. That’s why applications on more realistic problems will be welcome. At the very least, It will be good if the authors incorporate a separate section discussing the limitations of the signature transform (and the library), especially in terms of computations and scalability. 

Decision: Accept (Poster)