Algorithm 1004
Jeremy Reizenstein, Benjamin Graham · ACM Transactions on Mathematical Software · 2020
Iterated-integral signatures and log signatures are sequences calculated from a path that characterizes its shape. They originate from the work of K. T. Chen and have become important through Terry Lyons’s theory of differential equations driven by rough paths, which is an important developing area of stochastic analysis. They have applications in statistics and machine learning, where there can be a need to calculate finite parts of them quickly for many paths. We introduce the signature and the most basic information (displacement and signed areas) that it contains. We present algorithms for efficiently calculating these signatures. For log signatures this requires consideration of the structure of free Lie algebras. We benchmark the performance of the algorithms. The methods are implemented in C++ and released as a Python extension package, which also supports differentiation. In combination with a machine learning library (Tensorflow, PyTorch, or Theano), this allows end-to-end learning of neural networks involving signatures.
Cited by 28 works. doi:10.1145/3371237 Open-access PDF
Authors
References
- The NumPy Array: A Structure for Efficient Numerical Computation
- Treue Darstellung Liescher Ringe.
- A Basis for Free Lie Rings and Higher Commutators in Free Groups
- Differential equations driven by rough signals
- Sparse arrays of signatures for online character recognition
- Integration of paths—a faithful representation of paths by non-commutative formal power series
- Algebraic relations between harmonic sums and associated quantities
- A Primer on the Signature Method in Machine Learning
- "Building Workload Characterization Tools with Valgrind"
- An efficient algorithm for computing the Baker–Campbell–Hausdorff series and some of its applications