dtwrb

Dynamic Time Warping (DTW), DTW Barycenter Averaging (DBA), and robust dispersion estimation for numeric sequences. Pure Ruby, no runtime dependencies.

Extracted from taiwancards, where it drives acoustic pronunciation scoring.

The problem

Point-to-point comparison — Euclidean distance between samples at equal indices — assumes that two sequences have the same length and the same phase. Repeated observations of one process violate both assumptions: two utterances of the same syllable, two executions of the same gesture, and two runs of the same machine cycle differ in duration and in local timing.

DTW drops the assumption. It computes the minimum-cost monotone, continuous alignment between two sequences, letting either one stretch or compress locally. DBA lifts the idea from comparison to estimation: given many variable-length observations of one process, it returns a single prototype sequence in the DTW sense.

Install

gem "dtwrb"

Alignment

Accumulated cost follows the standard recurrence with the symmetric step pattern {(1,1), (1,0), (0,1)}:

D(i, j) = d(a_i, b_j) + min{ D(i-1, j), D(i, j-1), D(i-1, j-1) }

d is the local distance between two frames. Alignment#cost is D(n, m). Alignment#distance divides it by the number of path cells, which removes the bias that longer warping paths accumulate more terms.

require "dtwrb"

a = [0.0, 1.0, 2.0, 3.0, 4.0]
b = [0.0, 0.0, 1.0, 2.0, 3.0, 4.0, 4.0]

DTW.distance(a, b)
# => 0.0

DTW.align(a, b).path
# => [[0, 0], [0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [4, 6]]

b is a with its first and last frame repeated. Euclidean comparison cannot even be formed here, since the lengths differ; DTW reports exact identity and returns the path that proves it.

A sequence is either scalar ([0.0, 1.0, ...]) or multivariate ([[0.0, 9.0], [1.0, 8.0], ...]). Scalar input is read as one-dimensional frames and yields scalar output.

Barycenter averaging

DTW::BarycenterAveraging implements DBA (Petitjean, Ketterlin & Gançarski, 2011):

  1. initialize the prototype from the medoid of the sample, resampled to the requested length;
  2. align every observation to the prototype;
  3. for each prototype frame and coordinate, aggregate the observation frames that the warping paths associated with it;
  4. repeat until the mean absolute update falls below tolerance.

The default aggregator is the median, not the arithmetic mean of the original formulation. Its breakdown point is 50%, so a minority of corrupt observations cannot displace the prototype. Dispersion is reported per frame and coordinate as the median absolute deviation scaled by 1.4826, a consistent estimator of σ under normality.

observations = [
  [0.0, 1.0, 2.1, 3.0, 4.0],
  [0.0, 0.0, 1.2, 2.0, 3.1, 4.0],
  [0.0, 0.9, 2.0, 2.0, 2.9, 4.2],
  [0.1, 1.1, 2.0, 3.2, 4.0]
]

prototype = DTW.barycenter(observations, length: 5)

prototype.center      # => [0.0, 1.05, 2.0, 3.05, 4.0]
prototype.dispersion  # => [0.0, 0.148, 0.0, 0.148, 0.0]
prototype.count       # => 4
prototype.length      # => 5

Length defaults to the rounded mean length of the sample. The classic mean-based formulation is one argument away:

DTW.barycenter(observations, length: 5, aggregator: :mean).center
# => [0.02, 1.05, 2.02, 3.05, 4.05]

Medoid

The medoid is the observation with the smallest total DTW distance to all others — the most central real sequence, as opposed to a synthetic one. Exact selection costs O(k²) alignments, so candidates are drawn as a uniform subsample of size sample_size (12 by default). Selection is deterministic; no pseudo-random number generator is used anywhere in this library.

DTW.medoid(observations)
# => [0.0, 0.0, 1.2, 2.0, 3.1, 4.0]

Local distances

Any object that responds to #call(frame_a, frame_b) -> Float is accepted.

Name Definition Notes
:euclidean L² default
:manhattan L¹ less sensitive to one deviant coordinate
:chebyshev L∞ worst-coordinate deviation
:cosine 1 − cos θ, range [0, 2] scale-invariant; compares direction only 
DTW.distance(a, b, metric: :manhattan)
DTW.distance(a, b, metric: ->(x, y) { (x.first - y.first).abs })

Global constraint

The Sakoe–Chiba band (Sakoe & Chiba, 1978) restricts the alignment to cells with |i − j| ≤ r, which bounds the admissible warping and reduces the cost matrix to a diagonal strip:

r = max( ⌈ratio · max(n, m)⌉, |n − m| + 1 )

The second term guarantees that at least one path stays feasible, including for sequences of very unequal length.

Value Meaning
0.25 default ratio
any Numeric Sakoe–Chiba band with that ratio
:unconstrained full cost matrix
custom any object that responds to #radius(n, m) -> Integer

Narrowing the band can only raise the accumulated cost, never lower it.

Statistics and resampling

DTW::Statistics.median([5.0, 1.0, 3.0])                                      # => 3.0
DTW::Statistics.median_absolute_deviation([10.0, 11.0, 12.0, 13.0, 1000.0])  # => 1.4826
DTW::Statistics.standard_deviation([2.0, 4.0, 4.0, 4.0, 5.0])                # => 1.0954451150103321

DTW::Resampler.call([[0.0], [10.0]], 3)                                      # => [[0.0], [5.0], [10.0]]

In practice

taiwancards teaches Taiwanese Mandarin and scores learner recordings against native templates. The library is used at two stages.

Template construction, offline. For every syllable-and-tone key the corpus pipeline gathers recordings from many speakers. Speaking rate differs, so the MFCC matrices (13 coefficients per frame) and the F0 tone contours arrive at different lengths. DTW.barycenter reduces each set to one prototype — 12 frames for MFCC, 16 for the tone contour — plus the per-frame dispersion that becomes the tolerance band.

Scoring, online. A learner utterance is framed into its own MFCC matrix. DTW.distance to the prototype center gives a rate-invariant timbre score, so a slow speaker is not penalized for being slow. The stored dispersion turns that raw distance into a z-score, so syllables whose realization is naturally variable do not raise false alarms.

Field recordings contain clipped, truncated, and mislabeled tokens. Median aggregation keeps such a minority from dragging the prototype away from the actual articulation target — the property that motivated the robust default.

Speech is one instance of the general case. Anything sampled as a variable-rate numeric sequence — gesture traces, biosignals, machine cycles, pen trajectories — poses the same alignment and prototyping problem.

Complexity

Operation Time Memory
Unconstrained alignment O(n·m·D) O(n·m)
Banded alignment O(r·max(n, m)·D) O(n·m)
Medoid over k sequences O(min(k, s)²) alignments O(min(k, s))
Barycenter, I iterations O((I + 1)·k·n·m·D) O(n·m + L·D·k)

n and m are sequence lengths, D the frame dimension, r the band radius, s the medoid sample size, L the prototype length.

Design

Strategies are injected, never hard-coded: the local distance (DTW::Metrics), the global constraint (DTW::Bands), the central-tendency aggregator, and the dispersion estimator (DTW::Statistics). DTW::Aligner, DTW::Medoid, and DTW::BarycenterAveraging are immutable and reusable; build them once when aligning many pairs.

aligner = DTW::Aligner.new(metric: :cosine, band: 0.1)
averaging = DTW::BarycenterAveraging.new(aligner: aligner, aggregator: :mean, iterations: 10)

averaging.call(observations, length: 32)

DTW::Alignment, DTW::Barycenter, and DTW::Sample are Data value objects: frozen, compared by value, copied with #with.

License

WTFPL — see LICENSE.