Segmental Dtw: A Parallelizable Alternative to Dynamic Time Warping
Segmental Dtw: A Parallelizable Alternative to Dynamic Time Warping
复制标题
DOI：
10.1109/icassp39728.2021.9413827
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
TJ Tsai
中科院分区：
文献类型：
--
作者：
TJ Tsai
在这项工作中，我们探索并行替代DTW全局对齐两个特征序列。DTW的主要实际限制之一是其二次计算和存储器成本。以前的工作已经试图以各种方式减少计算成本，例如在成本矩阵中施加频带或使用多分辨率方法。在这项工作中，我们利用的事实，计算是一个丰富的资源，而不是专注于探索替代品，近似固有的顺序DTW算法与一个是并行的。我们描述了一种称为分段DTW的算法的两种变体，其中全局成本矩阵被分解为更小的子矩阵，对每个子矩阵执行子序列DTW，并且结果用于解决指定全局最优对齐路径的分段级动态规划问题。我们使用肖邦马祖卡数据集在音频-音频对齐任务上评估所提出的对齐算法，我们表明，他们密切配合定期DTW的性能。我们进一步证明，几乎所有的计算分段DTW是可并行的，并且其中一个变量是单方面优于其他的经验和理论的原因。
In this work we explore parallelizable alternatives to DTW for globally aligning two feature sequences. One of the main practical limitations of DTW is its quadratic computation and memory cost. Previous works have sought to reduce the computational cost in various ways, such as imposing bands in the cost matrix or using a multiresolution approach. In this work, we utilize the fact that computation is an abundant resource and focus instead on exploring alternatives that approximate the inherently sequential DTW algorithm with one that is parallelizable. We describe two variations of an algorithm called Segmental DTW, in which the global cost matrix is broken into smaller sub-matrices, subsequence DTW is performed on each sub-matrix, and the results are used to solve a segment-level dynamic programming problem that specifies a globally optimal alignment path. We evaluate the proposed alignment algorithms on an audio-audio alignment task using the Chopin Mazurka dataset, and we show that they closely match the performance of regular DTW. We further demonstrate that almost all of the computations in Segmental DTW are parallelizable, and that one of the variants is unilaterally better than the other for both empirical and theoretical reasons.