本系列介绍几种序列对齐方法,包括Dynamic time warping (DTW),Smith–Waterman algorithm,Cross-recurrence plot

Dynamic time warping (DTW) is a well-known technique to find an optimal alignment between two given (time-dependent) sequences under certain restrictions.       

——Meinard Muller的《Information Retrieval for Music and Motion》

DTW路径的定义:用p = (p1, p2, ..., pL),来表示,需要满足以下三个条件:

  (i) 边界条件:p1 = (1,1) 和 pL = (N,M)

  (ii) 单调条件:n1 ≤ n2 ≤ ... ≤ nL 以及 m1 ≤ m2 ≤ ... ≤ mL

  (iii) 跨步大小:p(l+1) - pl属于{(1,0),(0,1),(1,1)} for l属于[1:L-1]

DTW的目标函数:将c(x,y)定义为对齐x, y两点的损失函数,总的损失函数则是从p1到pL每个点对的损失函数之和,DTW路径的目标就是使总的损失函数最小的路径。

DTW的动态规划:D(n,m) = min{D(n-1,m-1), D(n-1,m), D(n,m-1)} + c(xn,yn),对于传统DTW,可以看到时间复杂度为O(MN)

DTW的变种:

  跨步变种1:原跨步大小导致每一步的斜率范围为0到正无穷,可能会引起路径退化,故修改为{(2,1),(1,2),(1,1)},这样斜率范围就变成0.5到2了。此时状态转移方程变为D(n,m) = min{D(n-1,m-1), D(n-2,m-1), D(n-1,m-2)} + c(xn,yn)

  跨步变种2:变种1会引入新的问题,即会直接忽略两个序列的某些点,故可采用状态转移方程D(n,m) = min{D(n-1,m-1), D(n-2,m-1) + c(xn-1, ym), D(n-1,m-2) + c(xn,  ym-1)} + c(xn,yn)

  损失函数权值变种:(1,0),(0,1),(1,1)三个跨步对应不同的权值,如在状态转移时,损失函数分别乘以权值(1,1,2)

  Global Constraints:全局限制,目的是使得最优路径在某个限制的区间内。两个著名的全局限制区域为Sakoe-Chiba band和Itakura parallelogram。这种方法使得时间复杂度也大幅度减小。问题在于会丢掉稍微超出限制的区间的最优路径。

  近似估计:只是为了降低计算复杂度。通过降采样,低通滤波,分段平滑函数等,降低O(MN)中M和N的大小

  Multiscale DTW:综合Global Constraints和近似估计的方法,先通过低分辨率下的最优路径;在得到的靠近最优路径范围内增大分辨率,找到较高分别率在的最优路径;循环迭代操作

DTW的问题:在于它是将整个序列进行warping,并不符合很多实际需求

Subsequence DTW:(a*, b*) = argmin(DTW(X, Y(a: b))), (a, b): 1 ≤ a ≤ b ≤ M.找到损失值最小的匹配对

结论:在实际大规模检索中,大多数方法采取的策略是首先提取粗粒度的数据表征时间序列,检索出候选文档,然后进行细粒度的rank

05-03 23:56