PaperlayerView exact revision on arXiv

Source-linked AI summary

A Primer on the Signature Method in Machine Learning

Ilya Chevyrev, Andrey Kormilitzin

arXiv:1603.03788v2stat.MLcs.LGstat.ME

TL;DR

Time-ordered data may contain differences too small for pointwise testing, motivating effective representations of paths. The paper introduces signatures through iterated integrals and examines their theoretical properties and use as machine-learning features.

  • Problem

    Differences between time-ordered paths can be difficult to detect when pointwise discrepancies remain below an instrument’s precision.

  • Method

    The paper studies signatures as sequences of iterated integrals and uses embedded continuous paths to extract features for machine-learning applications.

  • Results

    The signature is highly descriptive of a path, while extracted features support supervised and unsupervised learning applications.

  • Takeaways & Limitations

    Signature features provide a compact path description that is sensitive to geometric shape and applicable to sequential data embedded as continuous paths.

  • Takeaways & Limitations

    A path is not completely determined by its signature because traversal speed and certain path reversals cannot be recovered.

Abstract

from arXiv · show

We provide an introduction to the signature method, focusing on its theoretical properties and machine learning applications. Our presentation is divided into two parts. In the first part, we present the definition and fundamental properties of the signature of a path. The signature is a sequence of numbers associated with a path that captures many of its important analytic and geometric properties. As a sequence of numbers, the signature serves as a compact description (dimension reduction) of a path. In presenting its theoretical properties, we assume only familiarity with classical real analysis and integration, and supplement theory with straightforward examples. We also mention several advanced topics, including the role of the signature in rough path theory. In the second part, we present practical applications of the signature to the area of machine learning. The signature method is a non-parametric way of transforming data into a set of features that can be used in machine learning tasks. In this method, data are converted into multi-dimensional paths, by means of embedding algorithms, of which the signature is then computed. We describe this pipeline in detail, making a link with the properties of the signature presented in the first part. We furthermore review some of the developments of the signature method in machine learning and, as an illustrative example, present a detailed application of the method to handwritten digit classification.

Introduction

The introduction presents signatures as compact, descriptive features for time-ordered data and outlines an elementary treatment of their theory and applications. It also notes that the chapter intentionally omits many newer developments.

  • Motivation: Time-ordered data arise in financial series, text, and evolving networks, and can be represented as paths from an index set into a state space.The chapter then restricts attention to paths taking values in R^d, often after composing with an embedding function.
  • Motivation: Signatures encode paths as sequences of iterated-integral numbers that are both highly descriptive and compact.The introduction characterizes signatures as a natural generalization of polynomials to parametrized or unparametrized paths.
  • Scope and approach: The chapter develops theoretical and practical aspects of signatures while requiring only classical integration theory for its basic properties.It aims to remain self-contained and elementary, while connecting the subject to rough path theory and Chen’s earlier work.
  • Scope and approach: The selected applications are intended as conceptual introductions for readers who wish to study advanced topics or apply signatures in practice.The chapter does not attempt to review the full expansion of signature applications since the notes’ first version appeared in 2016.

1 Theoretical Foundations

This section introduces the signature’s definition and fundamental properties, including reparametrization invariance, algebraic identities, time reversal, and the log-signature. It provides complete proofs except for the log-signature result and points readers to further treatments.

  • Theoretical foundations: The theoretical foundations define the signature and develop its core structural properties, including reparametrization invariance, the shuffle product, Chen’s identities, time reversal, and the log-signature.These topics organize the first part’s mathematical treatment.
  • Proof strategy: Complete proofs are provided for the theoretical statements except for the log-signature result.The authors direct readers to existing references for alternative proofs of that result.
  • Theoretical foundations: The section also frames the signature as an object whose properties support later questions about paths and random paths.The cited overview identifies the fundamental theory as the basis for subsequent discussion.

1.1 Preliminaries

The preliminaries define paths as continuous maps into Euclidean space and assume piecewise continuous differentiability or bounded variation. They introduce smooth and piecewise linear examples before reviewing path integrals.

  • Paths in Euclidean space: A path in R^d is a continuous mapping X: [a, b] → R^d, with X_t denoting its value at parameter t.This establishes the basic mathematical object used throughout the chapter.
  • Paths in Euclidean space: The standing assumption is that paths are piecewise continuously differentiable, with bounded-variation paths providing a broader setting for the same classical theory.Smooth paths are defined as paths having derivatives of all orders.
  • Examples: The section illustrates smooth two-dimensional paths and a piecewise linear path, with the latter representing sequential measurements such as stock prices.The figures provide examples of smooth and non-smooth path behavior.
  • Path integrals: The path integral of Y against X is introduced through differentiation of X and the usual Riemann integral.The following examples identify constant integrands with increments and the time path with ordinary integration.

1.2 The signature of a path

The signature of a path is an infinite sequence of iterated integrals indexed by words, beginning with the constant zeroth term 1. Its levels encode path increments and higher-order time-ordered interactions, and its values determine solutions of certain controlled differential equations.

  • Iterated integrals: Higher signature levels are recursively defined iterated path integrals over ordered integration domains, such as triangles or higher-dimensional simplices.Double and triple integrals provide the first examples of this recursive construction.
  • Definition: The signature collects all iterated integrals of a path into an infinite sequence indexed by multi-indexes, with zeroth term 1.The indexes are finite words over the coordinate alphabet.
  • Signature levels: The first signature level records the increments of the path’s individual coordinates.Each first-level term is itself defined through a path integral.
  • Examples: For one-dimensional paths, the signature depends only on the path increment, so it encodes the powers of that increment.This is illustrated by the path X_t = t and stated for any one-dimensional path.
  • Examples: For multidimensional paths, the signature captures more than coordinate increments through the ordering of iterated integrals.The two-dimensional example uses words formed from the coordinate indexes and computes corresponding signature terms for a parabolic path.
  • ODE motivation: The signature completely determines solutions of controlled differential equations driven by a path, including agreement for linear vector fields when signatures coincide.The chapter presents this as a motivation for the signature’s role in differential equations and machine learning.
  • ODE motivation: The signature is motivated as a feature for distinguishing time-ordered paths when pointwise differences remain below an instrument’s precision.The associated ODE solutions can differ substantially even when the driving paths are uniformly close.

1.3 Important properties of signature

The signature has fundamental invariance and algebraic properties that support its interpretation as a polynomial-like description of paths. These include invariance under time reparametrization, the shuffle product, and Chen’s identity for concatenated paths.

  • Invariance under time reparametrizations: The signature is invariant under smooth time reparametrizations of a path.This follows from the corresponding invariance of iterated path integrals.
  • Shuffle product: For one-dimensional linear paths, signature terms encode powers of the path increment, illustrating the polynomial analogy.In the multidimensional linear case, a signature term depends on the entries of its multi-index and encodes a multivariate monomial of the increment vector.
  • Shuffle product: The shuffle product expresses products of signature terms as linear combinations of higher-order signature terms.The shuffled multi-indexes preserve the internal order of the two original multi-indexes, generalizing polynomial multiplication.
  • Chen’s identity: Chen’s identity provides an algebraic relationship between a path and the signatures of its subintervals.It also supports computation of signatures when values are known on subintervals and is effective for piecewise linear paths.
  • Log-signature: The log-signature theorem discussed in this subsection is not proved because its proofs require a non-trivial detour into Lie algebras.The authors direct readers to external references for two proofs.

1.4 Expected signatures as moments of path-valued random variables

The expected signature interprets signature coordinates as moments of path-valued random variables, linking path statistics to approximation and measure identification. Because signatures do not separate arbitrary paths, the paper restricts the path space to recover approximation results.

  • Expected signatures as moments: Signature coordinates generalize multivariate monomials, so expected signature terms act as moments of path-valued random variables.This connects signature features with the role of classical moments in statistics.
  • Approximation: The Weierstrass theorem motivates using polynomial-like signature functions to approximate continuous functions through linear combinations of signature coordinates.Classical polynomials approximate continuous functions on bounded intervals, and signature functions inherit an analogous algebraic structure.
  • Path-space limitation: The signature function class fails to separate arbitrary paths because signatures are invariant to translations, time reparametrizations, and tree-like path cancellations.These invariances identify distinct paths under the signature representation.
  • Recovering separation: Restricting paths to those with a fixed initial point and a strictly monotone time component yields a space on which the signature separates points.The paper denotes this restricted space by Y and uses it to restore the point-separating condition.
  • Approximation: For a compact K within the restricted path space, every continuous function can be uniformly approximated by a linear function of signature coordinates.For every continuous g and ε>0, the proposition provides a signature-based approximation whose error is below ε throughout K.
  • Measure identification: Equal expected signatures identify probability measures on compact subsets of the restricted path space.This follows by transferring the moment-determination argument from polynomials to signature functions.

1.5 Further topics and extensions

The section surveys extensions and deeper consequences of signatures, including rough paths, path uniqueness, jump processes, and moment problems for random paths. It also identifies important scope boundaries and unresolved questions.

  • Rough paths: Rough paths extend signatures beyond bounded-variation paths when iterated integrals are not uniquely defined for highly irregular paths.For finite p-variation paths, specifying the first floor(p) iterated integrals consistently determines the remaining iterated integrals.
  • Rough paths: The universal limit theorem gives meaning to controlled differential equations driven by geometric rough paths, with solutions depending continuously on the driver.Continuity is formulated using a suitable p-variation metric on rough-path space.
  • Path uniqueness: Signatures do not determine exact traversal speed or distinguish a constant path from a path followed by its time reversal.More generally, two paths have the same signature exactly when they are tree-like equivalent.
  • Path uniqueness: For non-self-intersecting paths, the signature completely describes the image and traversal direction modulo the starting point.Effective recovery of path properties from signatures remains challenging despite these uniqueness results.
  • Jump processes: Discontinuous paths can receive meaningful signatures by connecting jumps with straight lines after adding infinitesimal extra time, under suitable regularity assumptions.For finitely many jumps, this agrees with the piecewise linear path joining jumps in order; another Itô-based construction leads to branched rough paths and lacks the shuffle identity.
  • Moment problem and random paths: Expected signatures uniquely determine probability measures on compact path sets where the signature map is injective, while moment-decay conditions extend this result beyond compact support.For some processes the necessary decay condition fails, and whether their signature laws are determined by expected signatures remains open.

2 Practical Applications

The signature method converts sequential data into continuous paths and computes signature terms as features for statistical learning. Practical choices include interpolation schemes and auxiliary transformations that shape the resulting path representation.

  • Overview: Signature terms of sequential data streams provide candidate features, while the shuffle product expresses nonlinear signature functions linearly.The section presents the method as a practical computation pipeline for machine learning.
  • Path construction: Discrete d-dimensional observations are converted into continuous paths using interpolation before signature computation.The data stream consists of N points observed at ordered times in R^d.
  • Piecewise linear interpolation: Piecewise linear interpolation connects consecutive observations with linear segments to form a continuous path.The path is obtained by concatenating the locally interpolated segments.
  • Rectilinear interpolation: Rectilinear interpolation updates coordinates consecutively along the d axes, adding d−1 auxiliary points between consecutive observations.For d=3, each interval uses four points connected by piecewise linear interpolation.
  • Interpolation choices: The interpolation schemes are illustrated as piecewise linear and rectilinear paths, with auxiliary points added for the rectilinear construction.The signature is unaffected by the precise parametrization of the rectilinear path because of parametrization invariance.
  • Auxiliary transformations: Auxiliary data transformations can change stream dimension and improve representations for learning, generalization, and prediction.The section introduces transformations such as cumulative sums as additional preprocessing choices.

Base-point augmentation

Base-point and time-related augmentations modify the stream representation to retain absolute location or encode sampling-time information. These additions can provide features related to levels, elapsed time, and time differences.

  • Base-point augmentation: Adding an anchor point, typically the origin, removes translation invariance and allows absolute stream values to be represented.Without augmentation, paths at different locations in R^d produce the same signature.
  • Auxiliary time: A monotonically varying auxiliary component can act as time, making integrals against it describe path areas related to statistics such as the mean.This may provide informative features for downstream analytical tasks.
  • Time-related augmentation: Timestamp-related streams can encode both time since the beginning and differences between consecutive timestamps for unevenly sampled data.The combined representation is a 5-dimensional stream; the first missing time difference may be filled heuristically, such as with zero.

Lead-lag transformation

Lead-lag transformations duplicate and shift sequential data to form multidimensional paths, enabling signatures to capture relationships such as quadratic variation. Their signatures are equivalent under reparametrization invariance.

  • Lead-lag transformation: Lead-lag transformations shift a time series forward and backward to analyze relationships between signals and can map one-dimensional paths into two dimensions.They can capture statistics such as quadratic variation.
  • Construction: Lead and lag streams are repeated, time-shifted versions of the original stream, with first and last data points deleted.The construction derives both transformed streams by repeating and shifting observations.
  • Construction: Each original index corresponds to three transformed indices in the lead-lag construction.The transformation increases the number of points from N to 2N+1, requiring other streams to be length-adjusted.
  • Examples: The lead-lag mappings of X1 and X2 are illustrated in Figures 11 and 12, respectively.The figures show the corresponding lead and lag paths for each stream.
  • Multidimensional embedding: Multivariate streams can be embedded in R^d, with piecewise linear and rectilinear versions extending the representation to three dimensions.Figure 13 displays the resulting three-dimensional paths for both interpolation choices.
  • Signature property: The signatures of lead and lag transformations are equivalent because the signature is invariant under reparametrization.This equivalence concerns the signature values, not necessarily the visual parametrizations of the two paths.

Further path transformations

Path transformations can alter the dimension or representation of sequential data before signature computation, while orientation determines the sign of enclosed areas.

  • Further path transformations: Auxiliary transformations can increase or decrease the data stream dimension to improve representations for downstream learning.Examples include invisibility-reset augmentation, coordinate projections, rescaling, and random projections.
  • Signed-area orientation: A path’s orientation determines whether its enclosed signed area is positive or negative.Clockwise paths are negatively oriented, whereas counterclockwise paths are positively oriented.
  • Signed-area orientation: Signed areas reflect the direction in which a path encloses a region.The sign is also related to the sign of the path’s winding number.

The relative movement as a signed area

Low-order signature terms have geometric interpretations as increments and signed areas, with higher-order terms becoming less intuitive; the log-signature removes repeated information while preserving the signature’s information.

  • Relative movement and signed area: Aligned relative movements of two path components produce a positive area, while opposite movements produce a negative area.These cases are illustrated by positive and negative Lévy areas.
  • Example computation: For the example path, the level-2 truncated signature is (1, 5, −5, 12.5, −10.5, −14.5, 12.5).The vector contains the constant, first-order, and second-order terms.
  • Low-order signature terms: The first-order signature terms equal the total increments along each data stream.For the example path, the truncated signature begins with S1 = 5 and S2 = −5.
  • Low-order signature terms: Second-order signature terms S1,2 and S2,1 have geometric interpretations as areas, and their sum corresponds to a rectangle area through the shuffle relation.The terms can be partitioned into individual signed contributions relative to dashed lines.
  • Example computation: The example’s signed-area computation decomposes into positive and negative contributions whose sum equals the Lévy area.The contributions are A+ = 6.8 and A− = −4.8.
  • Log-signature: The log-signature contains the same information as the signature with fewer terms, removing repeated information caused by shuffle identities.Its higher-order terms are represented using iterated Lie brackets, and it can serve as a machine-learning feature set.

2.2 Machine learning with signature features

The signature method converts sequential data into geometric paths and signature features for supervised or unsupervised learning. In handwritten-digit examples, higher-order terms capture orientation-dependent differences and UMAP reveals class clusters.

  • Signature features: The signature is a collection of iterated integrals that encodes geometric path information for sequential-data learning.The general workflow embeds sequential data into continuous paths and computes signature features.
  • Machine-learning workflow: Signature features can support supervised classification and unsupervised tasks such as clustering and dimensionality reduction.The feature matrix can be supplied to hypothesis tests or algorithms predicting class labels.
  • Handwritten-digit example: The handwritten-digit dataset contains 250 digit samples from 44 writers, represented as consecutive tablet-stylus x,y coordinates.The data cover handwritten integers from 0 to 9.
  • Handwritten-digit example: Each coordinate sequence is treated as a path in R2, transformed into a signature feature matrix, and paired with its digit label.The example applies the signature transformation without composite augmentations.
  • Handwritten-digit example: Second-order signature terms improve zero–eight separability by capturing differences in the orientations of similarly closed shapes.The distributions of S1, S2 and S1,2, S2,1 differ between the two digit classes.
  • Handwritten-digit example: UMAP applied to the signature feature space produces clusters of points belonging to the same class label.The projection maps the feature space from R7 onto R2.

2.3 Overview of signature-based machine learning applications

Signature-based learning has been applied across finance, healthcare, sound compression, computer vision, and other machine-learning settings. These applications use signatures to represent complex sequential data and support tasks including regression, prediction, classification, and hypothesis testing.

  • Application areas: The signature method has been applied across finance, healthcare, natural language processing, wearable devices, and computer vision.The paper presents this breadth as evidence of the method’s versatility across scientific domains.
  • Signal and financial applications: In sound compression, signatures provide an alternative to Fourier and wavelet transforms by accounting for non-linear dependencies.The cited work applies rough path theory and signatures to sound compression.
  • Signal and financial applications: Financial applications use signatures to identify atypical market behavior, recognize trading-algorithm patterns, and construct non-parametric regression methods.Truncation provides an efficient local description with a stated provable efficiency gain over linear methods.
  • Healthcare applications: Healthcare applications use signatures for longitudinal pattern detection, clinical-trial analysis, mood prediction, diagnosis classification, and medical-text chronology.These examples involve wearable and self-reported data as well as clinical and textual records.
  • Computer-vision and related applications: Computer-vision and related applications include human-pose estimation, handwriting recognition, deep learning, neural controlled differential equations, topological data analysis, and kernel methods.Kernel combinations are described for classification and hypothesis testing.
Loading 1603.03788v2…