动态时间规整（DTW）是一种算法，用于计算两条时间序列之间的最优对齐，这些序列可能在速度、持续时间或相位上有所不同。与欧几里得距离等更简单的距离度量不同，后者比较相同时间索引处的点，DTW允许对时间轴进行非线性规整，以找到序列之间的最佳匹配。这一特性使DTW在比较表现出时间变异性的信号时特别有效，例如以不同语速说出的单词、手写字符或来自不同设备的传感器读数。
该算法于1970年代在语音识别领域被引入，在机器学习模型广泛采用之前，它成为了一项基础技术。其核心原理是动态规划：它构建一个成本矩阵，累积两条序列中每对点之间的距离，然后找到通过该矩阵的路径，使总累积距离最小化。由此产生的规整路径指示一条序列中的哪些点对应于另一条序列中的哪些点，最终的DTW距离是沿此最优路径的距离之和。
历史发展
关于DTW的最早发表工作通常归功于Hiroaki Sakoe和Seibi Chiba，他们在1978年通过约束条件形式化了该算法，以提高效率和鲁棒性。他们的论文《动态规划算法优化用于口语单词识别》引入了Sakoe-Chiba带，这是一种常见约束，限制了允许的规整窗口，以减少计算成本并防止病态对齐。大约在同一时期，施乐帕克研究中心及其他机构的研究人员探索了类似的动态规划方法用于模式匹配，但Sakoe和Chiba的表述成为了标准参考。
在1980年代，DTW是语音系统中孤立词识别的主导方法，通常实现于专用硬件上。后来，它被隐马尔可夫模型（HMM）以及更近期的深度学习方法（如基于神经网络的声学模型）所取代。然而，DTW作为基准和训练数据对齐工具仍然具有影响力。
算法细节
DTW算法作用于两条序列，X = (x1, x2, ..., xn)和Y = (y1, y2, ..., ym)，其中每个xi和yj是特征向量（通常是标量值或多维点）。该算法构建一个n乘m的矩阵D，其中每个单元格D(i, j)包含以该单元格结束的最佳对齐的累积距离。递推关系为：
D(i, j) = d(xi, yj) + min(D(i-1, j), D(i, j-1), D(i-1, j-1))
其中d(xi, yj)是局部距离度量，对于连续数据通常为欧几里得距离，对于标量值为绝对差。最终的DTW距离是D(n, m)，通过从该单元格回溯可以恢复最优规整路径。
为了提高效率并避免退化对齐，通常应用几种约束。Sakoe-Chiba带将规整路径限制在固定宽度的对角带内，将搜索空间从O(nm)减少到O(n带宽)。Itakura平行四边形，以Fumitada Itakura命名，使用斜率约束来限制路径的陡峭程度。此外，边界条件要求路径从(1,1)开始并在(n,m)结束，单调性确保索引永远不会减小。
应用
DTW在许多领域都有应用。在语音识别中，它被用于将口语单词与模板进行比较，特别适用于小词汇量任务。在时间序列分析（一个相关领域，尽管不在提供的slug列表中）中，DTW是聚类和分类的标准工具，在时间错位的数据集上通常优于欧几里得距离。例如，在基于加速度计数据的手势识别中，DTW可以匹配以不同速度执行的手势。
在生物信息学中，DTW已被应用于对齐基因表达谱或蛋白质序列，尽管它不如Needleman-Wunsch等序列比对算法常见。在金融领域，DTW用于比较股票价格走势或经济指标随时间的变化。在机器人技术中，DTW有助于对齐不同试验中的传感器读数，用于从示范中学习。该算法还用于数据增强，通过规整现有时间序列生成合成训练示例。
变体与扩展
已经开发了几种DTW变体来解决特定局限性。导数DTW（DDTW）使用序列的一阶导数而不是原始值，使其对偏移和缩放差异更加鲁棒。加权DTW为特征向量的不同维度分配不同权重。Soft-DTW，由Marco Cuturi和Mathieu Blondel于2017年引入，用软最小值替代了最小值操作，使距离可微，从而可用作深度学习流程中的损失函数。
多变量DTW处理具有多个通道的序列，子序列DTW在较长序列中找到最佳匹配的子序列。对于大型数据集，FastDTW等近似方法使用多尺度方法来降低计算复杂度。这些扩展使DTW在现代研究中保持相关性，特别是在机器学习背景下，可微版本支持端到端训练。
与现代AI的关系
虽然DTW不是一种深度学习方法，但在人工智能时代它仍然具有相关性。它通常用作预处理步骤，在将时间序列输入神经网络模型（如用于序列预测的残差网络或U-Net架构）之前进行对齐。在语音识别（一个不在slug列表中的概念）中，DTW仍用于低资源环境下的关键词检测。该算法的动态规划原理也出现在序列到序列模型中，其中对齐通过注意力机制隐式学习，而不是显式学习。
麻省理工学院计算机科学与人工智能实验室和斯坦福人工智能实验室等机构的研究人员探索了将DTW与深度学习相结合的混合方法，用于时间序列分类和异常检测等任务。Soft-DTW的可微性使其能够集成到损失函数中，用于训练需要时间对齐的模型。截至2020年代初，DTW仍然是时间序列基准测试中的标准基线，其计算效率仍是一个研究课题，正在探索针对GPU和AWS Trainium硬件的优化。