做网站怎么申请域名,石家庄工程造价信息网,平台网站建设方案标书,装修设计网站有哪些前言
动态时间规整算法#xff0c;Dynamic Time Wraping#xff0c;缩写为DTW#xff0c;是语音识别领域的一个基础算法。
算法的提出
DTW 的提出是为了解决或尽量解决在语音识别当中的孤立词识别不正确的问题。该问题简单描述为#xff1a;在识别阶段#xff0c;将输入…前言
动态时间规整算法Dynamic Time Wraping缩写为DTW是语音识别领域的一个基础算法。
算法的提出
DTW 的提出是为了解决或尽量解决在语音识别当中的孤立词识别不正确的问题。该问题简单描述为在识别阶段将输入语音的特征矢量时间序列依次与模板库中的每个模板进行相似度比较最后将相似度最高者作为识别结果输出。但是由于语音信号具有相当大的随机性即使是同一个人在不同时刻所讲的同一句话、发的同一个音也不可能具有完全相同的时间长度。而在进行模板匹配时这些时间长度的变化会影响测度的估计从而降低识别率。对此日本学者 板仓Itakura将动态规划DP算法的概念用于解决孤立词识别时的说话速度不均匀的难题提出了著名的动态时间规整算法或称动态时间伸缩算法DTW。
算法的内容
DTW 的目标是从不同时间跨度的两个数据求出它们之间的最小总累计距离所以首先我们要找出输入矢量和参考矢量之间的对应关系从而根据对应的矢量来求出模板之间的最小累计距离。在求累计距离的每一步中需要满足以下条件的规整函数 边界条件 w(1) 1w(N) M 3-1 即规整函数起点为1,1终点为NM 连续条件 w(n 1) w(n) 0/1/2如果 w(n) w(n - 1) 成立 3-2
w(n 1) w(n) 1/2如果 w(n) w(n - 1) 成立 3-3 Tip 式3-2意思是 w() 的当前值和前一个 w() 值不相等说明已经加过 1 或 2 则 w(n 1) 的加上的值可为 0式3-3则刚刚相反w(n 1) 的加上的值不能为 0因为 w(n) 已经使用过 0本质上规整函数限制了最小累加距离的路径走向。0/1/2代表了路径走的步数要么是当前矢量本身要么是当前矢量的前一列的步数为 1和 2 的矢量或点。n 的值与 N 相对应 使用规整函数的最小累计距离递推公式
DTW(n,m) d((n,m)) min { DTW(n - 1, m) * g(n - 1, m)DTW(n - 1, m - 1), DTW(n - 1, m - 2)} 3-4 其中
g(n - 1,m) 1如果 w(n - 1) w(n - 2) 3-5
g(n - 1,m) ∞如果w(n - 1) w(n - 2) 3-6 Tip这里的只能取前一列的矢量点的数据 根据式3-2和式3-3文字解释为当 DTW(n - 1, m) 不是来自 DTW(n - 2, m) 时则去判断 DTW(n - 1, m) [本身步数为 0 ]DTW(n - 1, m - 1) [步数为 1 ]DTW(n - 1, m - 2) [步数为 2 ] 优点和注意点
时间复杂度
DTW算法的优势在于它解决了数据长度不同的两数据序列的差异度表示方式。从计算的角度来说式3-4可看出横轴每向前增加一步仅参考前一列的累计距离所以在计算时只保留前一列的累计距离即可不必保留所有数据。这样可以降低算法的时间复杂度其原理在于一个参考数据只与其距离相近的数据会比较相似距离过远的数据关系不大所以就没必要计算参考数据与对比数据的所有距离而DTW算法本身就是在矩阵中运算的其一般的计算点关系如图 距离指标选择
相邻矢量间距离指标的好坏绝对影响DTW算法的效果。在孤立词识别当中先用矢量量化技术然后再对各分量使用欧拉 距离来度量和计算由于DTW算法可应用不同的领域所以不同的领域距离指标是不一样的甚至一般的统计距离欧拉距离、Minkowski距离、Mahalanobis距离以及兰氏距离等用在所碰到的问题上达不到想要的效果。所以此时就需要根据实际数据的特征来构造距离这里的距离已经不是一般意义上的长度等指标去衡量两个数据的相似程度
数据点约束
虽说根据规整函数可以使计算复杂度降低但是从递推公式可知要想知道终点的累计最短距离还是要不断计算前面的累计距离那么如何才能更进一步的降低计算时间复杂度呢答案就是对计算数据的范围进行约束下图是平行四边形约束 也就是说计算的数据点坐标必须落在平行四边形内部否则就不用计算至于平行四边形的形状可以根据实际数据来调试一般不会相差很大主要取决于平行四边形邻边的角度即斜率
计算例子
最后给出一个简单的例子讲下DTW的计算过程。 时间序列为 d1 {1,3,3,5,2}d2 {0,2,3,6,4,1} 第一列 DTW(1,1) 1 0 1; DTW(1,2) 1 min {DTW(0,2), DTW(0,1), DTW(0,0)} 1 0 1; DTW(1,3) 2 min {DTW(0,3), DTW(0,2), DTW(0,1)} 2 0 2; DTW(1,4) 5 min {DTW(0,4), DTW(0,3), DTW(0,2)} 5 0 5; DTW(1,5) 3 min {DTW(0,5), DTW(0,4), DTW(0,3)} 3 0 3; DTW(1,6) 0 min {DTW(0,6), DTW(0,5), DTW(0,4)} 0 0 0; 第二列 DTW(2,1) 3 min {DTW(1,1), DTW(1,0), DTW(1,-1)} 3 1 4; DTW(2,2) 1 min {DTW(1,2), DTW(1,1), DTW(1,0)} 1 1 2; DTW(2,3) 0 min {DTW(1,3), DTW(1,2), DTW(1,1)} 0 1 1; DTW(2,4) 3 min {DTW(1,4), DTW(1,3), DTW(1,2)} 3 1 4; DTW(2,5) 1 min {DTW(1,5), DTW(1,4), DTW(1,3)} 1 2 3; DTW(2,6) 2 min {DTW(1,6), DTW(1,5), DTW(1,4)} 2 0 2;这列符合w(n-1) w(n-2) 第三列 DTW(3,1) 3 min {DTW(2,1), DTW(2,0), DTW(2,-1)} 3 4 7; DTW(3,2) 1 min {DTW(2,2), DTW(2,1), DTW(2,0)} 1 2 3; DTW(3,3) 0 min {DTW(2,3), DTW(2,2), DTW(2,1)} 0 1 1;这列符合w(n-1) w(n-2) DTW(3,4) 3 min {DTW(2,4), DTW(2,3), DTW(2,2)} 3 1 4; DTW(3,5) 1 min {DTW(2,5), DTW(2,4), DTW(2,3)} 1 1 2; DTW(3,6) 2 min {DTW(2,6)_∞, DTW(2,5), DTW(2,4)} 2 3 5; 第四列 DTW(4,1) 5 min {DTW(3,1), DTW(3,0), DTW(3,-1)} 5 7 12;这列符合w(n-1) w(n-2) DTW(4,2) 3 min {DTW(3,2), DTW(3,1), DTW(3,0)} 3 3 6;这列符合w(n-1) w(n-2) DTW(4,3) 2 min {DTW(3,3)_∞, DTW(3,2), DTW(3,1)} 2 3 5; DTW(4,4) 1 min {DTW(3,4), DTW(3,3), DTW(3,2)} 1 1 2; DTW(4,5) 1 min {DTW(3,5), DTW(3,4), DTW(3,3)} 1 1 2; DTW(4,6) 4 min {DTW(3,6), DTW(3,5), DTW(3,4)} 4 2 6; 第五列 DTW(5,1) 2 min {DTW(4,1), DTW(4,0), DTW(4,-1)} 2 ∞ ∞ ; DTW(5,2) 0 min {DTW(4,2), DTW(4,1), DTW(4,0)} 0 12 12; DTW(5,3) 1 min {DTW(4,3), DTW(4,2), DTW(4,1)} 1 5 6; DTW(5,4) 4 min {DTW(4,4), DTW(4,3), DTW(4,2)} 4 2 6;这列符合w(n-1) w(n-2) DTW(5,5) 2 min {DTW(4,5), DTW(4,4), DTW(4,3)} 2 2 4;这列符合w(n-1) w(n-2) DTW(5,6) 1 min {DTW(4,6), DTW(4,5), DTW(4,4)} 1 2 3; 最终以表格形式给出计算结果 DTW(5,6) 就是最终的累计最短距离也就是两个数据的差异度表示
