基于PaddlePaddle2.0-构建动态时间归整模型(DTW)

本文介绍基于PaddlePaddle2.0构建动态时间规整（DTW）模型的方法。DTW用于计算两时间序列相似度，适用于语音识别等场景，能解决序列长度不一致问题，但不适用于交叉对应关系的序列。文中举例说明DTW建模流程，包括初始化距离矩阵、用动态规划找最短路径，并给出了基于PaddlePaddle2.0的实现代码及示例计算结果。

基于PaddlePaddle2.0-构建动态时间规整模型

作者：陆平

1. 动态时间规整模型原理

动态时间归整模型(Dynamic Time Warping, DTW)可以用于计算两个时间序列的相似程度。它适用于语音识别中的孤立词识别、姿势识别等场景。

例如，我们通常需要用唤醒词来启动智能音响，小米的小爱音响的唤醒词为“小爱同学”。但是不同的人对“小爱同学”这四个字的发音、语速等都是不同的，即便是相同的人也不可能每次说“小爱同学”这四个字的发音、语速完全相同，也就是说，实际发音与标准序列在长度上是不一致的。为解决这个问题，可以对序列进行缩放，使得两个时间序列长度一致，但这里没有考虑到序列中的某个元素一对多问题、一对零的问题。还有一种解决方式是利用动态规划方法，找到两个时间序列的最短匹配路径，即DTW模型。

然而，DTW模型不适用于具有交叉对应关系的时间序列。例如，中英文语言翻译场景中，词语序列之间普遍存在交叉对应关系，这种情形DTW模型不太适用。“今天我吃了水果”这句话翻译成英文是“I had fruit today”，“今天”这个词在中文语境中通常在第一个词的位置，而在英文语境下“today”处于最后一个词位置，这表明这两个时间序列存在交叉对应关系。

以下用个例子来看DTW建模流程。

步骤1：设有两个时间序列$s_1=[1,2,3,4,5,5,5,4]$s1=[1,2,3,4,5,5,5,4]和$s_2=[3,4,5,6,5,4]$s2=[3,4,5,6,5,4]，这两个时间序列的长度分别为8和6.

步骤2：初始化一个距离矩阵dtw，该矩阵用于衡量两时间序列的距离。

初始化第一列，采用以下公式: $dtw[i,0]=dtw[i-1,0]+distance(s_1[i],s_2[0]),i=1,\mathrm{.}\mathrm{.}\mathrm{.},7$dtw[i,0]=dtw[i−1,0]+distance(s1[i],s2[0]),i=1,...,7.

具体来看，$dtw[0,0]$dtw[0,0]这个位置取值为2，是因为$\mathrm{\mid }1-3\mathrm{\mid }=2$∣1−3∣=2.

$dtw[1,0]$dtw[1,0]这个位置取值为3，是因为$dtw[0,0]+distance(s_1[1],s_2[0])=2+\mathrm{\mid }2-3\mathrm{\mid }=2+1=3$dtw[0,0]+distance(s1[1],s2[0])=2+∣2−3∣=2+1=3.

$dtw[2,0]$dtw[2,0]这个位置取值为3，是因为$dtw[1,0]+distance(s_1[2],s_2[0])=3+\mathrm{\mid }3-3\mathrm{\mid }=3+0=3$dtw[1,0]+distance(s1[2],s2[0])=3+∣3−3∣=3+0=3.

$dtw[3,0]$dtw[3,0]这个位置取值为4，是因为$dtw[2,0]+distance(s_1[3],s_2[0])=3+\mathrm{\mid }4-3\mathrm{\mid }=3+1=4$dtw[2,0]+distance(s1[3],s2[0])=3+∣4−3∣=3+1=4.

以此类推。

初始化第一行，采用以下公式: $dtw[0,i]=dtw[0,i-1]+distance(s_1[0],s_2[i]),i=1,\mathrm{.}\mathrm{.}\mathrm{.},5$dtw[0,i]=dtw[0,i−1]+distance(s1[0],s2[i]),i=1,...,5.

$dtw[0,1]$dtw[0,1]这个位置取值为5，是因为$dtw[0,0]+distance(s_1[0],s_2[1])=2+\mathrm{\mid }1-4\mathrm{\mid }=2+3=5$dtw[0,0]+distance(s1[0],s2[1])=2+∣1−4∣=2+3=5.

$dtw[0,2]$dtw[0,2]这个位置取值为9，是因为$dtw[0,1]+distance(s_1[0],s_2[2])=5+\mathrm{\mid }1-5\mathrm{\mid }=5+4=9$dtw[0,1]+distance(s1[0],s2[2])=5+∣1−5∣=5+4=9.

$dtw[0,3]$dtw[0,3]这个位置取值为14，是因为$dtw[0,2]+distance(s_1[0],s_2[3])=9+\mathrm{\mid }1-6\mathrm{\mid }=9+5=14$dtw[0,2]+distance(s1[0],s2[3])=9+∣1−6∣=9+5=14.

以此类推。

Tensor(shape=[8, 6], dtype=float32, place=CPUPlace, stop_gradient=True,
       [[ 2.,  5.,  9., 14., 18., 21.],
        [  3., inf., inf., inf., inf., inf.],
        [  3., inf., inf., inf., inf., inf.],
        [  4., inf., inf., inf., inf., inf.],
        [  6., inf., inf., inf., inf., inf.],
        [  8., inf., inf., inf., inf., inf.],
        [ 10., inf., inf., inf., inf., inf.],
        [ 11., inf., inf., inf., inf., inf.]])

步骤3: 利用动态规划算法找出最短的对应路径。 这里假设了一个单调性条件，即通往$dtw[i,j]$dtw[i,j]的路径，上一步只能是$dtw[i-1,j]$dtw[i−1,j]、$dtw[i,j-1]$dtw[i,j−1]、$dtw[i-1,j-1]$dtw[i−1,j−1]三者之一。相应的代码为：

    for i in range(1,len(src)):        for j in range(1,len(tar)):            cost=dist_func(src[i],tar[j])            temp=[]            temp.append(cost+dtw[i-1,j])            temp.append(cost+dtw[i,j-1])            temp.append(cost+dtw[i-1,j-1])
            dtw[i,j]=min(temp)

这里的假设是可以放松的，如果想要涵盖跳跃一步的对应关系。即通往$dtw[i,j]$dtw[i,j]的路径，上一步可以是$dtw[i-1,j]$dtw[i−1,j]、$dtw[i,j-1]$dtw[i,j−1]、$dtw[i-1,j-1]$dtw[i−1,j−1]、$dtw[i-2,j-1]$dtw[i−2,j−1]、$dtw[i-1,j-2]$dtw[i−1,j−2]之一。可以在循环中增加如下代码：

            temp.append(cost+dtw[i-2,j-1])            temp.append(cost+dtw[i-1,j-2])

进一步，如果我们想避免某种跳跃关系，可以在cost前乘以某个正数，从而放大该步的即时成本。

正因为DTW模型含有单调性假设，它不适合于计算具有交叉对应关系的序列相似性。

2. 应用PaddlePaddle2.0构建DTW模型

In [7]

import paddleimport numpy as np#距离函数def dist_func(v1,v2):
    return paddle.abs(v1-v2)#DTW模型def dtw_func(src,tar):
    dtw=paddle.zeros([len(src),len(tar)])
    dtw[:] = np.inf    #初始化
    dtw[0,0]=dist_func(src[0],tar[0])    for i in range(1,len(src)):
        dtw[i,0] = dtw[i-1,0]+dist_func(src[i],tar[0]) 
    for i in range(1,len(tar)):
        dtw[0,i] = dtw[0,i-1]+dist_func(src[0],tar[i]) 
    
    #动态规划
    for i in range(1,len(src)):        for j in range(1,len(tar)):
            cost=dist_func(src[i],tar[j])
            temp=[]
            temp.append(cost+dtw[i-1,j])
            temp.append(cost+dtw[i,j-1])
            temp.append(cost+dtw[i-1,j-1])
            dtw[i,j]=min(temp)    return dtw[-1,-1].numpy().item()


s1=paddle.to_tensor([1, 2, 3, 4, 5, 5, 5, 4])
s2=paddle.to_tensor([3, 4, 5, 6, 5, 4])
ds=dtw_func(s1,s2)print("s1, s2两序列之间的距离为：{}".format(ds))

s1, s2两序列之间的距离为：4.0