Dynamic Time Warping
- 又称: DTW
- 类别: Learning & autonomy › Learning from demonstration
- 标签: time-series, sequence-alignment, dynamic-programming, learning-from-demonstration, trajectory-analysis
一种动态规划算法，通过找出两个时间序列样本之间总距离最小、且保持顺序的配对，来对齐速度或长度不同的两个时间序列。
定义
动态时间规整（dynamic time warping，DTW）用于比较两个遵循相似模式但速度不同的序列，例如同一动作的两次演示，其中一位操作者停顿了，另一位则动作很快。DTW 不是拿第 i 个样本与第 i 个样本比较，而是搜索一条规整路径：它把两个序列的样本配对，从两者的开头开始，在两者的结尾结束，并且在时间上从不后退。每个样本都可以与另一个序列中的一个或多个样本匹配，因此时间上的拉伸和压缩都被对齐所吸收。DTW 距离是沿最佳路径的总代价，而路径本身则说明了哪些时刻相互对应。
标准算法用动态规划填充一个代价矩阵。设一个序列的第 i 个样本与另一个序列的第 j 个样本之间的局部距离为 d(i, j)，累计代价为 D(i, j) = d(i, j) + min(D(i−1, j), D(i, j−1), D(i−1, j−1))，从最后一个单元格回溯即可恢复路径。这所需的时间和内存与两个长度的乘积成正比。Sakoe 和 Chiba（1978）把该方法推广用于口语单词识别，并引入了一条沿对角线的带，限制对齐可以偏离多远；Itakura 平行四边形是一种相关的约束。这类窗口可以加快计算，并防止出现病态规整，即一个样本被匹配到另一个序列的一长段上。
有几种变体在机器人领域很重要。子序列 DTW（subsequence DTW）放宽了起点和终点条件，使一个短查询可以与一条长轨迹中最匹配的片段对齐，这支持从大型日志中进行检索。导数 DTW（derivative DTW）根据局部斜率而不是原始值进行对齐。Soft-DTW 由 Cuturi 和 Blondel 于 2017 年提出，它用一个平滑版本替代最小值运算，使对齐代价可微，从而可以用作训练损失。DTW 只在时间上进行对齐：特征必须可比较，并且通常需要归一化；所得距离也不是真正的度量，因为它不满足三角不等式。
为何重要
机器人数据很少以统一的速度到来。演示、已执行的轨迹和传感器记录在时间上各不相同，而 DTW 是在对它们进行平均、比较、检索或评分之前，把它们放到同一时间线上的标准工具。
主要应用
- 在平均或拟合运动基元之前对齐多次演示
- 将已执行的机器人轨迹与参考轨迹进行比较
- 从大型轨迹或传感器日志中检索匹配片段
- 基于运动或惯性数据的手势与活动识别
- 用归一化 DTW 指标将导航路径与参考路径进行比较评分
- 同步以不同速率记录的传感器数据流
实际应用
一个团队收集了十次倒水动作的动觉示教演示，每次时长不同，停顿的位置也不同。为了给运动基元建立一个单一的参考，他们选取一次演示作为模板，在归一化的关节位置和末端执行器速度上用 DTW 把其他每次演示与之对齐，并利用规整路径把它们全部重采样到模板的时间线上。对对齐后的轨迹取平均，得到一条干净的平均运动和逐时间步的方差，方差显示了各次演示在哪里一致。Sakoe-Chiba 带防止对齐把停顿压缩成单个样本。之后，同一套子序列 DTW 代码会在机队存储的轨迹中搜索与一个短查询动作最匹配的片段。
常见误解
- DTW 距离是一种度量 — 它不满足三角不等式，这对假定满足三角不等式的索引和聚类方法很重要
- DTW 能处理序列之间的任何差异 — 它吸收的是时间上的差异，而不是数值上的偏移或缩放，因此特征通常需要先归一化
- 无约束的 DTW 给出最好的对齐 — 没有窗口时，它可能把单个样本匹配到另一个序列的一长段上，产生没有物理意义的规整
- DTW 太慢，不适合实际使用 — 带约束、下界和近似方法使它足够快，可用于许多实时和大规模应用
谁需要了解
- 从演示中学习的研究人员
- 分析机器人轨迹和日志的工程师
- 手势与活动识别开发者
- 评估导航和操作策略的研究人员
相关技术
- Soft-DTW
- Sakoe-Chiba 带
- 子序列 DTW（subsequence DTW）
- FastDTW
- tslearn
相关术语
- Dynamic Movement Primitive
- Imitation Learning
- Kinesthetic Teaching
- Behavior Cloning
- Success Weighted by Path Length
相关项目
- PlotJuggler: Fast time-series visualization tool for ROS topics, rosbags, and robot debugging
视频
- How DTW (Dynamic Time Warping) algorithm works: Thales Sehn Körting