Kernels for sequentially ordered data

Franz J Király; Harald Oberhauser

Source-linked AI summary

Kernels for sequentially ordered data

Franz J Király, Harald Oberhauser

arXiv:1601.08169v1Jan 29, 2016stat.MLcs.DMcs.LGmath.STstat.ME

TL;DR

Learning from sequential data is hindered by diverse features, structured objects, and costly manual preprocessing. The paper introduces signature-based kernel sequentialization, which extends static kernels to sequences, is discretely computable with convergence guarantees, and performs competitively in experiments.

Problem
Sequential learning lacks a broadly transferable representation because applications use diverse handcrafted features and ad-hoc methods for structured objects.
Method
Signature features treat sequences as ordered variants of sample moments, and kernel sequentialization applies the kernel trick to turn any static kernel into a sequence kernel.
Results
The discrete sequential kernel approximates its continuous counterpart and supports efficient computation for finite sequences.
Takeaways & Limitations
Experiments indicate that the proposed sequential kernel can beat state-of-the-art sequence classification while avoiding extensive preprocessing.
Takeaways & Limitations
The paper identifies limitations for large cross-kernel computations and for the definiteness treatment of global alignment kernels.

Abstract

from arXiv · show

We present a novel framework for kernel learning with sequential data of any kind, such as time series, sequences of graphs, or strings. Our approach is based on signature features which can be seen as an ordered variant of sample (cross-)moments; it allows to obtain a "sequentialized" version of any static kernel. The sequential kernels are efficiently computable for discrete sequences and are shown to approximate a continuous moment form in a sampling sense. A number of known kernels for sequences arise as "sequentializations" of suitable static kernels: string kernels may be obtained as a special case, and alignment kernels are closely related up to a modification that resolves their open non-definiteness issue. Our experiments indicate that our signature-based sequential kernel framework may be a promising approach to learning with sequential data, such as time series, that allows to avoid extensive manual pre-processing.

1. Introduction

Sequential data are diverse, structured, and computationally large, making manual feature extraction and ad-hoc representations difficult to transfer. The paper uses signature features and kernel sequentialization to build universal, efficiently computable kernels for such data.

Motivation: Sequential data vary widely, often require application-specific handcrafted features, and may consist of structured objects such as letters, images, or graphs.Existing approaches use manual feature extraction or ad-hoc structure-specific methods that do not transfer easily.
Signature features: Signature features are ordered analogues of sample moments that can characterize sequences and compare sequences of different sizes and lengths.They provide a way to avoid extensive manual feature extraction.
Kernel sequentialization: Combining the signature map with the kernel trick produces sequence kernels and extends static kernels to sequences of structured objects through kernel sequentialization.The construction applies a kernel on objects to sequences, yielding a canonical sequentialized kernel.
Experiments: Experiments report that sequentialization of nonlinear kernels may be beneficial and that the proposed kernel can beat state-of-the-art sequence classification without extensive preprocessing.This is the paper’s reported empirical outcome rather than a universal claim about all sequence tasks.
Signature features: Signature features preserve chronological order, unlike ordinary moment matrices, so higher-order features capture dependencies between changes at ordered time points.The resulting tensors are generally non-symmetric because reversing chronological order changes the feature value.
Computation: The framework addresses computational growth through a second kernelization and discretization, enabling dynamic-programming evaluation for discrete sequences.The two kernelization steps avoid the combinatorial explosion of explicit signature features and permit arbitrary-object inputs.

22 Es1<s2,t1<t2

The paper discretizes the continuous sequential kernel by replacing expectations and derivatives with finite sums and difference approximations. This yields convergence to the continuous kernel, efficient dynamic-programming computation, and connections to established sequence-comparison methods.

Discretization: Discrete sequential kernels replace continuous expectations with sums over sampled support points and derivatives with adjacent finite differences.The finite-difference construction uses neighboring support values in each discretized sequence.
Connections to prior kernels: The sequential kernel is related to string kernels as an infinitesimal limit, while the paper presents string kernels as a special case.This places the construction within prior sequence-kernel methodology.
Approximation: The discretized kernel converges to the continuous kernel with convergence order linear in the sampling density.This convergence is stated as a theoretical result for the discretization scheme.
Computation: Dynamic programming evaluates the iterated sum-product on three-dimensional arrays, with quadratic complexity in sequence length and linear complexity in approximation degree.Low-rank techniques can reduce complexity to linear in both quantities.
Prior art: The paper situates its contribution across dynamic programming, kernel learning, and rough-path research communities, where it identifies previously underdeveloped connections.The authors frame the work as a unifying view of sequence kernels and their relation to classical sequence methods.

2. Notation for ordered data

This section establishes notation for finite ordered tuples, arbitrary finite sequences, ordered subsequences, and monotone order simplices used in later sequence calculations.

Basic notation: [L] denotes the integers from 1 through L, and N includes zero.These conventions support indexing and degree-based constructions.
Sequences: A^L denotes ordered L-tuples from a set A, while A+ denotes tuples of arbitrary finite length.The notation supports sequences whose lengths may vary.
Tuple statistics: The count notation #a records the multiplicity of the most frequent item in a tuple, while a! multiplies factorials of distinct-item multiplicities.These quantities are introduced as sequence-combinatorial notation.
Ordered tuples: For real-valued domains, increasing tuples form subsets of A+ and are used in calculations involving signature features.The relevant tuples are organized through order simplices.
Order simplices: The order simplex ΔM(A) contains monotonously ordered M-tuples, with strict tuples satisfying u[i] < u[i+1].The paper allows repeated entries for general ordered tuples and excludes them for strict tuples.
Subsequence notation: The relations a ⊑ b and a ⊏ b denote, respectively, ordered and strictly ordered subsequences of b.The bounded relation a ⊑D b additionally limits the subsequence length by D.

3. Signature features: ordered moments for sequential data

Signatures represent sequential data through iterated, order-sensitive integrals in a tensor algebra. They are essentially faithful features and are rich enough to approximate continuous functions on suitable path classes.

Definition and interpretation: Signature features are iterated integrals over ordered time points, forming an ordered and non-commutative analogue of sample moments.The degree-M features integrate along the M-simplex of chronologically ordered points.
Path setting: The construction is formulated for bounded-variation paths in a Hilbert space, with Riemann–Stieltjes integrals defining the iterated features.The paper restricts paths to bounded variation for regularity, while noting that this excludes some stochastic-process samples.
Tensor representation: The M-th iterated integral lies in H⊗M, and all degrees together form the tensor power algebra over H.In finite dimensions, degrees one, two, and three correspond respectively to vectors, matrices, and third-order tensors.
Universality: Linear combinations of signature features can approximate continuous functions arbitrarily well on compact sets of paths that are not tree-like equivalent.The signature features therefore provide a universal linear feature class for the supported sequential setting.
Canonical representation: Signature features are essentially faithful: equal signatures characterize bounded-variation paths up to tree-like equivalence.Adding time as an extra coordinate guarantees the relevant non-tree-like condition for the paper’s experimental data.

4. Kernelized signatures and sequentialized kernels

The paper constructs signature-based kernels for sequential data by first using signature inner products in Hilbert spaces and then sequentializing arbitrary static kernels. It also establishes well-definedness, positive definiteness, efficient recursive computation, and robustness under discretization and noise-related settings.

Kernel construction: Signature features yield kernels for sequences in a Hilbert space by taking scalar products of their signature representations.The construction is motivated by the signature’s ordered-moment representation and is first developed for sequences in H.
Computation: The kernels admit Horner-type recursions expressed through scalar products, avoiding the infeasible naive evaluation caused by combinatorial expansion.The recursion is preserved under discretization and supports practical evaluation.
Kernel construction: The framework sequentializes any static kernel k on X into a kernel k⊕ on suitably regular sequences or paths in X.A primary feature map φ embeds static objects into an RKHS, after which the sequential kernel is defined through the signature construction.
Theoretical properties: The resulting kernels are positive definite and finite for bounded-variation paths, so they are well-defined under the stated conditions.Positive definiteness follows from their explicit feature-space scalar-product form.
Assumptions and robustness: The construction assumes observations can be represented by sufficiently regular paths whose primary-feature images have bounded variation and, in the general setting, are absolutely continuous.The paper also discusses robustness under noise and extends beyond bounded variation in a later section.

5. Discrete signatures and kernels for sequences

The paper replaces continuous signature integrals with discrete sequence constructions that approximate the continuous signature and its kernel as sampling becomes dense. These discretized kernels retain positive definiteness and can be evaluated efficiently using dynamic programming.

Discretization: Because continuous paths are observed only at finitely many samples, the paper develops discrete signatures and kernels for sampled sequences.The discretization uses finite sums to approximate the relevant integrals.
Discretization: The discrete construction proceeds in two kernelization steps: a signature kernel on H-valued sequences, followed by replacement of inner products with evaluations of a primary kernel on X.This yields sequentialized kernels for arbitrary static object spaces.
Approximation: The discrete kernels converge to their continuous counterparts as the sampling meshes vanish, with convergence supported by the discrete-signature approximation theorem.The same approximation establishes convergence of the sequential kernel k+ to k⊕.
Approximation: The discrete approximation is algebraic rather than generally geometric: it need not correspond to a bounded-variation path whose signature equals the discrete signature.The paper contrasts this with path-level approximations, which are not known to yield an equally efficient kernel.
Kernel properties: The discrete signature kernels are positive semidefinite because they are defined as scalar products of discretized features.This preserves the kernel property for finite sequences, including sequences of differing lengths.

6. The string, alignment and ANOVA kernel seen via sequentializations

The section shows that string, alignment, ANOVA, and relation-convolution kernels can be understood through sequentialization, while a modification makes alignment kernels positive definite.

String kernels: String kernels arise as sequentializations of suitable primary and weighting kernels, including the original kernel and variants with parameter λ.The construction uses symbol agreement as the primary kernel and κ(i,j)=λ^(d(i)+d(j)) as the weighting kernel.
String kernels: The string kernel is not exactly a continuous signature kernel because sequentialization acts on the tensor algebra rather than directly on paths.The section attributes this difference to the discretization level used by the construction.
Global alignment kernel: The native global alignment kernel need not be positive definite, so it cannot generally be represented as a sequential kernel.Its direct weighting function is not positive definite, unlike the weights required by the sequential-kernel construction.
Global alignment kernel: A simple modification of the global alignment construction produces a sequential kernel and therefore a positive definite kernel.The modified construction is obtained by changing the admissible alignment representation rather than retaining the native form.
Global alignment kernel: The authors argue that restoring terms omitted from the original alignment kernel is more natural because those terms correspond to non-transitivity and lack a first-principles exclusion.They leave open the possibility of empirically retaining the omissions but reject an intrinsic justification for doing so.
Related kernel frameworks: The sequential kernel is related to Haussler’s relation-convolution framework through the ordered sub-sequence relation, with a discrepancy in whether evaluation occurs before or after summation.The ANOVA kernel uses the same sub-sequence relation but restricts the primary kernel to unequal-element zeros.

7. Higher order sequentialization and noisy observations

The paper extends sequentialization to higher-order approximations for irregular or noisy paths, connecting discrete sequential kernels with signature constructions and convergence results.

Signature convergence: Sequentialization converges to an inner product of signature features when the feature-mapped sequences have bounded variation.The signature is defined through Riemann–Stieltjes integration under this assumption.
Noisy observations: Noisy observations can violate bounded variation, motivating rough-path or stochastic-analysis constructions that replace the classical signature map.For rougher paths, the paper uses higher-order approximations whose required order increases with path irregularity.
Noisy observations: For Brownian motion, piecewise-linear dyadic approximations connect signature terms with Ito–Stratonovich integrals, although second-order diagonal terms do not converge to the corresponding classical expression.The non-convergence is linked to Brownian motion’s non-vanishing quadratic variation.
Scope: The general rough-path treatment is beyond the paper’s scope, which instead gives the definitions needed for the higher-order sequentialized kernels.The required approximation order depends on the regularity of the underlying path.
Higher-order approximations: Higher-order sequentialization introduces an approximation order D and tensor truncation degree M for paths of unbounded variation.The framework includes Brownian motion, continuous semimartingales, fractional Brownian motion, Gaussian processes, and continuous-time Markov processes as motivating examples.
Higher-order approximations: The higher-order formulas retain recursive evaluation, but their multi-way structure is better expressed through dynamic programming.The paper states that an efficient algorithm for general D and M is given later.

8. Efficient computation of sequentialized kernels

The paper develops dynamic-programming and low-rank algorithms for efficiently computing sequentialized kernels, replacing naive exponential or costly evaluations with polynomial-time procedures. The resulting strategies reduce computation or storage across sequence length, kernel degree, and dataset size.

Algorithmic motivation: Dynamic-programming algorithms make signature and sequential kernel computation polynomial in sequence length rather than exponential in input length or degree.The basic algorithms target efficient computation of signature and sequential kernels for discrete sequences.
Dynamic programming: Algorithm 3 evaluates a sequential kernel in O(Mℓ(σ)ℓ(τ)) arithmetic operations and O(Mℓ(σ)ℓ(τ)) storage.Storage can be reduced to O(ℓ(σ)ℓ(τ)) by discarding previously used array entries.
Higher-order approximation: Higher-order approximation increases Algorithm 4's cost to O(D2Mℓ(σ)ℓ(τ)) operations and O(D2ℓ(σ)ℓ(τ)) storage.The additional factor D applies to the modified dynamic-programming algorithms.
Large-scale strategies: Low-rank strategies reduce learning costs for N sequences to O((r + N)·r·L2·M) operations and O((r + N)·r·L2) storage.The learning algorithm then usually costs O((r + N)·r2) rather than O(N3) operations and storage.
Large-scale strategies: Low-rank factorization does not remove dependence on sequence length, while modified operations are needed because the cross-kernel matrix is generally non-symmetric.Naive summations and multiplications otherwise require access to the full cross-kernel matrix.

9. Experimental validation

The experiments validate the sequential kernel as a practically meaningful concept on hand-movement and handwritten-digit classification, while explicitly stopping short of a systematic benchmark comparison. Results support the usefulness of order information and, on pendigits, the advantage of sequentializing a non-linear rather than linear kernel.

Pendigits: On pendigits, sequentializing the Euclidean kernel achieves sub-baseline performance, whereas the sequentialized Gaussian kernel improves accuracy to the baseline region.The linear sequentialized kernel roughly matches previously reported results, while the Gaussian version is similar to the documented k-nearest-neighbors baseline.
Scope and limitations: The experiments are intended as concept validation rather than systematic benchmarking against prior methods and additional baselines.A broader benchmark would require multiple string, alignment, dynamic-time-warping, aggregation, distributional, and naive methods, many lacking compatible code.
Validation and prediction set-up: Two supervised classification experiments evaluate sequential kernels on multivariate time series, using SVC and nested 5-fold cross-validation.The datasets contain equal-length series, and performance is reported with precision, recall, and F1-score.
Validation and prediction set-up: Sequential kernels use ordering only for truncation M ≥2; at M = 1 they reduce to aggregate-style Euclidean or Gaussian features.The experimental design compares truncation level 1 with levels 2 and higher to assess whether order information is beneficial.
Classifying hand movements: For hand-movement classification, level-2-or-higher sequential kernels outperform non-sequential kernels for all five subjects.The dataset contains 180 two-channel recordings per subject, each with 3,000 time points; the uninformed baseline is 1/6 ≈0.17.
Classifying hand movements: The sequential kernel appears to outperform methods reported in the original hand-movement study, although missing code and unclear figure subject indexing limit the comparison.The paper flags additional uncertainty because the reported figures may concern different classification settings.

A. Second kernelization of the signature kernel

The second kernelization extends the signature-kernel construction from vector-valued paths to sequences of arbitrary objects. It defines the required kernel through a signed-measure representation and establishes convergence of the discrete construction to the continuous signature form.

Definition and extension: The kernel k(dσ,dτ) is defined for arbitrary values in X by replacing differentials with a signed Borel measure.This measure-valued formulation makes the kernel meaningful when the sequence space has no differential structure.
Definition and extension: A feature map φ embeds arbitrary sequence elements so that the resulting paths can be treated as piecewise linear bounded-variation paths.The construction assumes x := φ(σ) and y := φ(τ) are piecewise linear between their time points.
Theorem: Under the stated assumptions, the measure-based expression is valid for paths whose feature-mapped versions lie in BV(H).The theorem applies to arbitrary paths satisfying the bounded-variation condition after feature mapping.
Theorem: For discretized paths formed by piecewise linear interpolation, the discrete construction converges to the continuous signature inner product as the sampling mesh tends to zero.The interpolation uses sampled points at times t_n, with the limit taken as n→∞.

B. Integral approximation bounds and proof of Theorem 5

This appendix develops algebraic and integral estimates for comparing the relevant homogeneous expansions and their discretized approximations. The bounds are organized through generating functions and converge uniformly under mesh refinement.

Integral decomposition: The proof splits integrals over partition cells and separates differential operators to control the approximation terms.The partition uses intervals U_i=[t_i,t_{i+1}] and products of these cells.
Integral decomposition: Index sequences are separated according to whether indices repeat, distinguishing strictly increasing contributions from repeated-index contributions.The decomposition introduces C1 for non-repeating sequences and C2 for sequences with repeats.
Approximation bounds: Norm bounds control the difference between the homogeneous parts C_m and D_m, with the generating function G collecting the resulting approximation bounds.G is defined through Taylor coefficients g_m and serves as a generating function for the bounds.
Approximation bounds: The resulting approximation estimates include uniform convergence of order O(max_i x_i) on compact subsets of [0,∞).The convergence rate is stated for the relevant expansion estimates.
Approximation bounds: The bound from Proposition B.6 can be worse than Euler’s bound for equal x_i by a factor of x because it also covers heavily imbalanced partitions.This identifies a conservatism in the general bound rather than a failure of convergence.