软动态时间规整（soft-DTW）

Python 实现的软动态时间规整。

这是什么？

著名的动态时间规整（DTW）[1] 定义了两个可能长度不一的时间序列间的差异，通过它们最小对齐成本来衡量。虽然存在的时间序列对齐方式数量随两个序列的长度呈指数增长，但[1]展示了如何使用动态规划以二次时间复杂度计算DTW。

软-DTW[2] 提议用一个软性最小值替代这个绝对最小值。与原始DTW一样，软-DTW能以二次时间复杂度利用动态规划进行计算。然而，软-DTW的主要优势在于它在各处都是可微分的，并且其梯度也能在二次时间内计算出来。这使得能够将软-DTW应用于时间序列的平均处理或作为损失函数，用于比较神经网络预测的时间序列和实际基准时间序列之间的差异，整个过程可通过反向传播实现端到端训练。

支持的功能

• 使用Cython优化速度的软-DTW（前向传递）和梯度（后向传递）计算。
• 时间序列聚心（即时间序列平均）。
• 加载UCR存档 数据集的工具。
• Chainer 函数支持。

示例

from sdtw import SoftDTW
from sdtw.distance import SquaredEuclidean

# 时间序列1：numpy数组，形状=[m, d]，其中m=长度，d=维度
X = ...
# 时间序列2：numpy数组，形状=[n, d]，其中n=长度，d=维度
Y = ...

# D也可以是任意距离矩阵：numpy数组，形状=[m, n]
D = SquaredEuclidean(X, Y)
sdtw = SoftDTW(D, gamma=1.0)
# 软-DTW差异，当gamma->0时接近于DTW
value = sdtw.compute()
# 关于D的梯度，形状=[m, n]，也即期望的对齐矩阵
E = sdtw.grad()
# 关于X的梯度，形状=[m, d]
G = D.jacobian_product(E)

安装

没有提供二进制包。

可以从其Git仓库安装此项目，假定您有一个可用的C编译器。

1. 获取源代码：

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

   如果无法使用git，则从GitHub上下载ZIP文件：https://github.com/mblondel/soft-dtw/archive/master.zip。

2. 安装依赖项：

   • 使用pip安装：

     pip install numpy scipy scikit-learn cython nose
     

   • 或者使用conda安装：

     conda install numpy scipy scikit-learn cython nose
     

3. 构建并安装soft-dtw：

   cd soft-dtw
   make cython
   python setup.py build
   sudo python setup.py install
   

参考文献

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

作者

• Mathieu Blondel, 2017