Deep Signature Transforms

Introduction

Given a path, we may define its signature, which is a collection of statistics of the path. The map from a path to its signature is called the signature transform.

We shall often use the term signature to refer to both a path’s signature and the signature transform. Other texts sometimes use the term path signature in a similar manner.

We refer the reader to for a primer on the use of the signature in machine learning. A brief overview of its key properties may be found in Appendix A, along with associated references.

In short, the signature of a path determines the path essentially uniquely, and does so in an efficient, computable way. Furthermore, the signature is rich enough that every continuous function of the path may be approximated arbitrarily well by a linear function of its signature; it may be thought of as a ‘universal nonlinearity’. Taken together these properties make the signature an attractive tool for machine learning. The most simple way to use the signature is as feature transformation, as it may often be simpler to learn a function of the signature than of the original path.

Originally introduced and studied by Chen in , the signature has seen use in finance , rough path theory and machine learning .

2 Comparison to the Fourier transform

The signature transform is most closely analogous to the Fourier transform.

The fundamental difference between the signature transform and classical signal transforms such as Fourier transforms and wavelets is that the latter are used to model a curve as a linear combination in a functional basis. The signature does not try to model or parameterise the curve itself, but instead provides a basis for functions on the space of curves.

For example, regularly seeing the sequence: phone call, trade, price movement in the stream of office data monitoring a trader might be an indication of insider trading. Such occurrences are straightforward to detect by via a linear regression composed with the signature transform. Modelling this signal using Fourier series or wavelets would be much more expensive: linearity of these transforms imply that each channel must be resolved accurately enough to see the order of events.

From a signal processing perspective, the signature can be thought of as a filter which is invariant to resampling of the input signal. (See Proposition A.7 in Appendix A).

3 Use of the signature transform in machine learning

4 Our work

In this way the signature transform has been elevated from a one-time feature transformation to a first-class layer within a neural network. Thus we may reap the benefits of both the signature transform, with its strong corpus of mathematical theory, and the benefits of neural networks, with their great empirical success.

Naturally all of this implies the need for an efficient implementation of the signature transform. Such concerns have motivated the creation of the spin-off Signatory project .

The remainder of the paper is laid out as follows. In Section 2 we briefly discuss some related work, in Section 3 we detail the specifics of embedding the signature as a layer within a neural network. Sections 4 covers experiments; we demonstrate positive results for generative, supervised, and reinforcement learning problems. Section 5 is the conclusion. Appendix A provides an exposition of the theoretical properties of the signature, and Appendix B specifies implementation details.

Related Work

The signature transform is roughly analogous to the use of wavelets or Fourier transforms, and there are also related models based around these, for example . We do not know of a detailed comparison between the use of these various transformations in the context of machine learning.

Some related work using signatures has already been discussed in the previous section. We expand on their proposed models here.

Given a set $V$, the space of streams of data in $V$ is defined as

Given $\mathbf{x}=(x_{1},\ldots,x_{n})\in\mathcal{S}(V)$, the integer $n$ is called the length of $\mathbf{x}$.

Two simple models utilising the signature layer are shown in Figure 1.

In principle the universal nonlinearity property of signatures (see Proposition A.6 in Appendix A) guarantees that the model shown in Figure 1(a), is rich enough to learn any continuous function. (With the neural network taken to be a single linear layer and the input stream assumed to already be time-augmented.) In practice, of course, the signature must be truncated. Furthermore, it is not clear how to appropriately choose the truncation hyperparameter $N$. Thus a more practical approach is to remove the restriction that the neural network must be linear, and learn a nonlinear function instead. This approach has been applied successfully in various tasks .

The signature transform as a layer in a neural network

However, there is not always a clear candidate for the feature map $\Phi$ and a good choice is likely to be data-dependent. Thus we propose to make $\Phi$ learnable by taking $\Phi=\Phi^{\theta}$ to be a neural network with trainable parameters $\theta$. In this case, we again obtain the neural network shown in Figure 1(b), except that $\Phi$ is now also learnable.

Despite being formed of integrals, the signature is in fact straightforward and efficient to compute exactly, see Section A.3 in Appendix A. More than that, the computation may in fact be described in terms of standard tensor operations. As such it may be backpropagated through without difficulty.

2 Stream-like data

The data is treated as a discretisation or set of observations of some underlying path. Note that there is nothing wrong with the path itself having a discrete structure to it; for example a sentence.

In principle one could reshape a tensor of shape $(b,nd)$ with no stream-like nature into one of shape $(b,d,n)$, and then take the signature. However it is not clear what this means mathematically. There is no underlying path. The signature is at this point an essentially arbitrary transformation, without the mathematical guarantees normally associated with it.

3 Stream-preserving signatures, using lifts

In this way the stream-like nature of the data is preserved through the signature transform.

4 Multiple signature layers

This defines the deep signature model, summarised in Figure 2.

Note that in principle it is acceptable to take the trivial lift to a sequence of a single element,

Taking the signature of this will then essentially remove the stream-like nature, however, so it is suitable only for the final lift of a deep signature model. We observe in particular that this is what is done in the models described in Figure 1, which we identify as special cases of the deep signature model, lacking also any learned transformation before the signature.

It is easy to see that the deep signature model exhibits the universal approximation property. This fact follows from the universal approximation theorem for neural networks and from the universal nonlinearity property of signatures (see Proposition A.6 in Appendix A).

5 Implementation

When using the signature transform as a feature transformation, then it suffices to just pre-process and save the entire dataset before training. However when the signature transform is placed within a neural network then the signature transform must be evaluated and backpropagated through for each step of training; this is much more computationally intensive. This has motivated the creation of the separate spin-off Signatory project , to efficiently perform and backpropagate through the signature transform.

6 Inverting the truncated signature

How well does a truncated signature encode the original stream of data? A simple experiment is to attempt to recover the original stream of data given its truncated signature. We remark that finding a mathematical description of this inversion is a challenging task .

Figure 3 shows four handwritten digits from the PenDigits dataset . The solid blue path is the original path $\mathbf{x}$, whilst the dashed orange path is the reconstructed path $\mathbf{y}$ minimising $L(\mathbf{y};\mathbf{x})$. Truncated signatures of order $N=12$ were used for this task. We see that the truncated signatures have managed to encode the input paths $\mathbf{x}$ almost perfectly.

Numerical experiments

Generative models are typically trained to learn to transform random noise to a target distribution. One common approach are Generative Adversarial Networks . An alternative approach is to define a distance on the space of distributions by embedding them into a Reproducing Kernel Hilbert Space. The discriminator is then a fixed two-sample test based on a kernel maximum mean discrepancy. This is known as a Generative Moment Matching Network .

With this framework we propose a deep signature model to generate sequential data. The discriminator is as in . The natural choice for random noise is Brownian motion $B_{t}$.

Let the input to the network be time-augmented Brownian motion

The overall model is shown in Figure 4. In a nice twist, both the generator and the discriminator involve the signature.

Observe how the generative part is a particular case of the deep signature model, and that furthermore the whole generator-discriminator pair is also a particular case of the deep signature model, with the trivial lift of equation (9) before the second signature layer.

We applied the proposed model to a dataset of $1024$ realisations of an Ornstein–Uhlenbeck process . The loss was minimised at $6.6\times 10^{-4}$, which implies that the generated paths are statistically almost indistinguishable from the real Ornstein–Uhlenbeck process. Figure 5 shows the generated paths alongside the original ones. Further implementation details are in Appendix B.

2 Supervised learning with fractional Brownian motion

Estimating the Hurst parameter of a fractional Brownian motion path is considered a nontrivial task because of the paths’ non-stationarity and long range dependencies . We train a variety of models to perform this estimation. That is, to learn the map $\mathbf{x}^{H}\mapsto H$, where

The results are shown in Figure 6 and Table 1. Also shown in Table 1 are the results of the rescaled range method , which is a mathematically derived method rather than a learned method.

RNN, GRU and LSTM models provide baselines in the context of recurrent neural networks. The simple Neural-Sig model outlined previously in Figure 1(a) provides a baseline from the context of signatures.

DeepSigNet and DeeperSigNet are both deep signature models of the form given by Figure 2. DeepSigNet has a single large Neural-Lift-Signature block, whilst DeeperSigNet has three smaller ones.

We observe that traditional signature based models perform slightly worse than traditional recurrent models, but that deep signature models outperform all other models by at least an order of magnitude. Further implementation details are found in Appendix B.

3 Non-Markovian deep reinforcement learning

Finally we show how these ideas may be extended, by demonstrating a model that adds a residual connection to the deep signature model; it may also be interpreted as using signatures as the memory of a recurrent neural network.

As an example, we apply this architecture to tackle a non-Markovian reinforcement learning problem. This means that the optimal action depends not just on the current state of the environment, but upon the history of past states, so that the agent must maintain a memory.

where $a_{i}$ is the action proposed by the network at time $i$, and $y_{i}$ and $\sigma_{i}$ are the memory at time $i$, and $\otimes$ denotes the tensor product as in A.13 in Appendix A.

The model is summarised in Figure 7 as a recurrent neural network with signature-based memory. Note that $y_{i}$ is preserved in memory only to compute the signature at the next time step, as the shortest path it is meaningful to compute the signature of is of length two.

However, note that by Proposition A.15 in Appendix A,

Furthermore the $x_{i}$, $y_{i}$, $\sigma_{i}$ and $a_{i}$ may be collected into streams

In this way we may interpret this model as a generalisation of deep signature model: it has a single Neural-Lift-Signature block, with a skip connection across the whole block. The neural component is given by the neural network $\Phi^{\theta_{1}}$, which is stream-preserving as it operates pointwise, in the manner of equation (1). The lift is the ‘expanding window’ lift given by equation (6). Finally $f^{\theta_{2}}$ is another neural network, which is again pointwise and thus stream-preserving.

This interpretation of the model is demonstrated in Figure 8.

We test this model on a non-Markovian modification to the classical Mountain Car problem , in which the agent receives only partial information: it is only given the car’s position, and not its velocity.We find that it is capable of learning how to solve the problem within a set number of episodes, whilst a comparable RNN architecture fails to do so. The reinforcement learning technique used was Deep Q Learning with the specified models performing function approximation on $Q$. Both models were chosen to have comparable numbers of parameters. Further implementation details can be found in Appendix B.

Conclusion

There is a strong corpus of theory motivating the use of the signature transform as a tool to understand streams of data. Meanwhile neural networks have enjoyed great empirical success. It is thus desirable to bring them together; in this paper we have described how this may be done in a general fashion, and have provided examples of how this principle may be used in a variety of domains.

There are two key contributions. First, we discuss stream-preserving neural networks, which are what allow for using signature transforms deeper within a network, rather than as just a feature transformation. Second, we discuss lifts, which is what allows for the use of multiple signature transforms. In this way we have significantly extended the use of the signature transform in machine learning: rather than limiting its usage to data preprocessing, we demonstrate how the signature transform, as a univeral nonlinearity, may be used as a pooling layer within a neural network.

PB was supported by the EPSRC grant EP/R513295/1. PK was supported by the EPSRC grant EP/L015811/1. PK, IPA, CS, TL were supported by the Alan Turing Institute under the EPSRC grant EP/N510129/1.

References

Appendix A A brief overview of signatures

This appendix is split into three subsections. The first subsection discusses the definition and properties of the signature transform on path space, which is the mathematically natural way to approach things. The second subsection goes on to adapt the signature transform to the space of streams of data.

In the third subsection we discuss how to compute the signature transform. In particular we will see that whilst the signature transform of a path may look somewhat unfriendly to compute, it will (fortunately!) turn out that the signature transform may be efficiently computed in the special case that its input is piecewise linear, which is how a stream of data is interpreted.

We begin with the definition of the signature. Note that this definition is written in a slightly different format to that of Definition 1.1, as the more traditional (if somewhat unfriendly-looking) notation of stochastic calculus is used; however the mathematical meaning is the same.

The truncated signature of depth $N$ of $X$ is defined as

The signature exhibits four key properties that makes its use attractive when dealing with path-like data. First, a path is essentially defined by its signature. This means that essentially no information is lost when applying the signature transform.

Next, the terms of the signature decay in size factorially.

Third, functions of the path are approximately linear on the signature. In some sense the signature may be thought of as a ‘universal nonlinearity’ on paths.

Finally, the signature is invariant to time reparameterisations.

Thus the signature encodes the order in which data arrives without caring precisely when it arrives; it is essentially factoring out the infinite-dimensional group of time reparameterisations. For example, consider the scenario of recording the movement of a pen as it draws a character on a piece of paper. Then the signature of the stream of data is invariant to the speed at which the character was drawn.

There is an interesting interplay between Proposition A.6 and Proposition A.7. If one desires invariance to time reparameterisations, as in the example of a pen drawing a character, then computing the signature of just $X$ rather than $\widehat{X}$ will ensure by Proposition A.7 that this invariance is present. If one does not desire invariance to time reparameterisations, then using the time-augmented path $\widehat{X}$ is what ensures that parameterisation-dependent functions may still be learned. This essentially corresponds to the difference between $\widehat{X\circ\psi}$ and $\widehat{X}\circ\psi$.

A.2 Signatures of streams of data

We interpret a stream of data as a discretisation of a path.

The space of streams of data is defined as

and the (truncated) signature of order $N$ of $\mathbf{x}$ is defined as

A priori this definition of the signature of a stream of data depends on the choice of linear interpolation. (That is, the speed at which one traverses the gap between the $x_{i}$.) However, it turns out that Definition A.10 is well-defined and independent of this choice, by Proposition A.7. See [10, Lemma 2.12].

A.3 Computing the signature

The tensor product $\otimes$ is typically defined between two tensors, taking a tensor of shape $(a_{1},\ldots,a_{n})$ and a tensor of shape $(b_{1},\ldots,b_{m})$ to a tensor of shape $(a_{1},\ldots,a_{n},b_{1},\ldots,b_{m})$. For example, in the special case that these two tensors are of shapes $(a_{1})$, $(b_{1})$, so that they are vectors, then the tensor product is what is referred to as the outer product.

A fundamental insight of Chen is that concatenation of paths corresponds to tensor multiplication of their signatures. The following relation is known as Chen’s identity.

Equipped with Chen’s identity, the signature of a stream is straightforward to compute explicitly.

Computing signatures in the manner described here involves only normal tensor operations, so it may be backpropagated through in the usual way. Recall that signatures are fundamentally defined on path space; backpropagating corresponds to determining the perturbation of the signature when perturbing its input with white noise. However one of the insights of rough path theory is that a path needs more than just its pointwise values to be fully determined. The most common example of this arises in stochastic calculus, where one has to make a choice between Itô and Stratonovich integration. Until such a choice is made, one cannot define a notion of integrals of the path. In general, for sufficiently rough paths, one has to define what the integrals of a path are: essentially the path is defined by its signature, rather than the other way around. In such a framework it is not clear what the correct notion of perturbations of path space are, and this remains a direction for future work.

Appendix B Implementation Details

All experimental models were trained using the Adam optimiser as implemented by PyTorch , which was the framework used to implement the models. Signature calculations were performed with the iisignature package (as the Signatory project mentioned elsewhere in this paper had not yet been developed). All activation functions were taken to be the ReLU. Computations were performed on two computers. One was equipped with two Tesla K40m GPUs. The second was equipped with two GeForce RTX 2080 Ti GPUs and two Quadro GP100 GPUs.

In each of the following sections, the notation is the same as the notation used in the corresponding section of the main document.

The training dataset was given by 1024 realisations of an Ornstein–Uhlenbeck process, and the test set was of the same size, each sampled at 100 points of $$. No minibatching was used. The model was trained for 500 epochs.

for some learned $\phi^{\theta_{1}}_{1},\phi^{\theta_{1}}_{2}$. The lift was the ‘expanding window’ described in equation (6). The signature in the generator was truncated at $N=3$ (giving 84 scalar nonconstant terms) The layer $f^{\theta_{2}}$ operated pointwise on the stream of signatures, and was a simple linear map down to a scalar value (the value of the generated process at that time step). The signature in the discriminator was truncated at $M=4$.

Some hyperparameter searching was necessary to obtain good results. The search was not done according to any formal scheme. It seemed that if $\Phi^{\theta_{1}}$ was sufficiently simple and not did not keep the original stream then the training would easily get trapped in a bad local minima, and the generated process would be visually distinct from the Ornstein–Uhlenbeck process.

B.2 Supervised learning with fractional Brownian motion

The training set featured 600 samples whilst the test set featured 100 samples, each of an instance of fractional Brownian motion sampled at 300 time steps of $$, with Hurst parameters in the range$[0.2,0.8]$. These were split up into batches of 128 samples, so the last batch is slightly smaller than the others, and every model trained for 100 epochs. The loss function was taken to be mean squared error (MSE).

There was no hyperparameter searching except to require that all models should have approximately the same number of parameters; in all cases the results represent a model whose hyperparameters have not been fine-tuned to the task at hand.

All models used a sigmoid as a final nonlinearity, so as to map in to $(0,1)$.

The differing sizes of layers between models (whilst keeping roughly the same overall parameter count) is usually because of the varying size of the input to the model. Some models take all of the raw data, some models use signatures, and some models take expanding or sliding windows of the data in a manner akin to equations (6) and (8).

The Feedforward model was a simple neural network with 3 hidden layers of 16 neurons each.

The Neural-Sig model – which is essentially the same model as the Feedforward model, except that the data has the signature applied as feature transformation first – featured hidden layers of sizes 64, 64, 32, 32, 16, 16 respectively.

The RNN model is two recurrent neural networks, the first comprised of dense layers of sizes 64, 64, 32 and output size 6, and the second comprised of dense layers of size 32, 32, 32, and output size 5. The first network sweeps across the input data relatively slowly, with a stride of 2, whilst the second network sweeps across the result of the first network more quickly, with a stride of 4. In this way it may capture information from the input data at multiple timescales; part of the challenge of fractional Brownian motion is the existence of long-range dependencies .

The LSTM and GRU models both featured two recurrent layers each of size 32, and swept across the raw data with a stride of 1.

DeepSigNet featured a single Neural-Lift-Signature block, where the neural component was given by a single convolutional layer with 3 channels and kernel size 3, the lift was the trivial lift of equation (9), and the signature was truncated as $N=3$. The neural component also preserved the original time-augmented stream of data, so that in some sense the neural component has 3 extra channels corresponding to time and value. On top of this a feedforward neural network with 5 hidden layers of size 32 was placed. Thus this model is very similar to the Neural-Sig model, except that a small learnable transformation was allowed before the signature. The difference in their performance highlights the value of learning a transformation before using the signature. (Without which the Neural-Sig model is merely outperformed by some non-signature based models.)

DeeperSigNet featured three Neural-Lift-Signature blocks. The neural component of the first block was a small feedforward network with 2 hidden layers of size 16 and an output layer of size 3, swept across the length of the stream; its kernel size (how many time-value pairs of the stream it saw at once) was 4. The original time-augmented stream of data was also preserved by the neural component. The neural components of the other two blocks were recurrent neural networks, featuring 2 hidden layers of 16 neurons each. The lifts were in every case expanding windows as in equation (6). On top of this another recurrent neural network was placed, and the value of its final hidden state used as the output. This final network used 2 hidden layers of 16 neurons each.

B.3 Non-Markovian deep reinforcement learning

We used the implementation of the Mountain Car problem implemented by the OpenAI Gym , modified to return only the car’s position. Each episode was run for 300 steps, and each model was given 2000 episodes in which to learn. The reward function was given by the car’s position, in the range $(-1.2,0.6)$, with a bonus $+1$ on reaching the goal. At each step the car could drive its engine left, right, or not use it at all. This problem was chosen for its ease of implementation.

The sizes of the models were chosen to ensure that they both had roughly the same number of scalar parameters. Within this specification, there was a small amount of hyperparameter searching. This was done in an ad hoc manner, for both models, varying the number of layers and the numbers of neurons in each layer, around the values that were eventually used. The eventual values chosen for the deep signature model were selected as the ones giving the best results for the deep signature model. The eventual values for the RNN were selected to give roughly the same parameter count as the deep signature model, as no RNN model achieved any appreciable success.

The deep signature model was as described in Section 4.3, with the first network $\Phi^{\theta_{1}}$ applying a learned linear transformation with output dimension 2. Furthermore it kept the original time-augmented stream, so that

where $\phi_{1}^{\theta_{1}}$ and $\phi_{2}^{\theta_{2}}$ are learned linear functions. The signature was truncated at $N=3$. The second network $f^{\theta_{2}}$ was comprised of a single hidden layer of 64 neurons, followed by an output layer of 3 neurons, corresponding to the three possible actions. The action with the greatest value was the action selected. This model had a total of 5769 scalar parameters.

The RNN model featured 3 recurrent layers each of size 32, followed by an output layer of 3 neurons, corresponding to the three possible actions. The action with the greatest value was the action selected. This model had a total of 5475 scalar parameters.

The reinforcement learning technique used was Deep Q Learning , to effectively transform the task into a supervised learning problem, with each of the specified models performing function approximation on $Q$. Actions were chosen in an $\varepsilon$-greedy manner, with $\varepsilon=0.2$. The discount factor was given by $\gamma=0.99$.

The deep signature model achieved success, and would learn to consistently solve the problem at around 1500 episodes. The RNN failed to achieved success within 2000 episodes on any test run. 3 test runs were performed.