Skip to main content
Join the official 2019 Python Developers SurveyStart the survey!

Python implementation of soft-DTW

Project description

Python implementation of soft-DTW.

What is it?

The celebrated dynamic time warping (DTW) [1] defines the discrepancy between two time series, of possibly variable length, as their minimal alignment cost. Although the number of possible alignments is exponential in the length of the two time series, [1] showed that DTW can be computed in only quadractic time using dynamic programming.

Soft-DTW [2] proposes to replace this minimum by a soft minimum. Like the original DTW, soft-DTW can be computed in quadratic time using dynamic programming. However, the main advantage of soft-DTW stems from the fact that it is differentiable everywhere and that its gradient can also be computed in quadratic time. This enables to use soft-DTW for time series averaging or as a loss function, between a ground-truth time series and a time series predicted by a neural network, trained end-to-end using backpropagation.

Supported features

  • soft-DTW (forward pass) and gradient (backward pass) computations, implemented in Cython for speed
  • barycenters (time series averaging)
  • dataset loader for the UCR archive
  • Chainer function

Planned features

  • PyTorch function

Example

from sdtw import SoftDTW
from sdtw.distance import SquaredEuclidean

# Time series 1: numpy array, shape = [m, d] where m = length and d = dim
X = ...
# Time series 2: numpy array, shape = [n, d] where n = length and d = dim
Y = ...

# D can also be an arbitrary distance matrix: numpy array, shape [m, n]
D = SquaredEuclidean(X, Y)
sdtw = SoftDTW(D, gamma=1.0)
# soft-DTW discrepancy, approaches DTW as gamma -> 0
value = sdtw.compute()
# gradient w.r.t. D, shape = [m, n], which is also the expected alignment matrix
E = sdtw.grad()
# gradient w.r.t. X, shape = [m, d]
G = D.jacobian_product(E)

Installation

Binary packages are not available.

This project can be installed from its git repository. It is assumed that you have a working C compiler.

  1. Obtain the sources by:

    git clone https://github.com/mblondel/soft-dtw.git
    

or, if git is unavailable, download as a ZIP from GitHub.

  1. Install the dependencies:

    # via pip
    
    pip install numpy scipy scikit-learn cython nose
    
    
    # via conda
    
    conda install numpy scipy scikit-learn cython nose
    
  2. Build and install soft-dtw:

    cd soft-dtw
    python setup.py install
    

References

[1]Hiroaki Sakoe, Seibi Chiba. Dynamic programming algorithm optimization for spoken word recognition. In: IEEE Trans. on Acoustics, Speech, and Sig. Proc, 1978.
[2]Marco Cuturi, Mathieu Blondel. Soft-DTW: a Differentiable Loss Function for Time-Series. In: Proc. of ICML 2017. [PDF]

Author

  • Mathieu Blondel, 2017

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for soft-dtw, version 0.1.6
Filename, size File type Python version Upload date Hashes
Filename, size soft_dtw-0.1.6-cp36-cp36m-macosx_10_13_x86_64.whl (29.3 kB) File type Wheel Python version 3.6 Upload date Hashes View hashes
Filename, size soft-dtw-0.1.6.tar.gz (58.1 kB) File type Source Python version None Upload date Hashes View hashes

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN SignalFx SignalFx Supporter DigiCert DigiCert EV certificate StatusPage StatusPage Status page