【DWT】计算两不等序列相似度：DWT

noteDTWDP-matching用于计算两个不等长、但变化趋势相关的序列的相似度。论文给出了最优的对齐规则对称权重 斜率约束P1让对齐更准识别错误率降到了原来的2/3针对两个时长不同、采样点数量不一致的语音特征序列用动态时间规整DTW找最优非线性对齐路径消除语速波动带来的时间轴偏差。创新引入斜率约束P1禁止路径过陡/过缓避免短语音段错误匹配长语音段同时采用对称权重设计确保两个序列的所有特征都被纳入计算对齐更合理。实验验证该优化后的DTW算法在孤立词识别任务上错误率仅为传统算法的2/3成为后续DTW应用的经典标准方案。文章目录note一、研究动机二、论文核心1. 时间归一化距离的一般定义2. 规整函数的约束条件3. 对称形式与非对称形式的权重设计4. DP 递推算法与斜率约束的具体化三、实验结果实验一对称/非对称与斜率约束对比日语数字实验二对称形式在地名集上的斜率约束日语地名实验三与同期其他DP算法对比四、分析与结论五、Python代码示例Reference一、研究动机论文Dynamic Programming Algorithm Optimization for Spoken Word Recognition作者Hiroaki Sakoe, Seibi Chiba会议/期刊IEEE Transactions on Acoustics, Speech and Signal Processing年份1978是语音识别领域中关于动态时间规整DTW/DP‑matching的经典文献系统提出了带斜率约束的对称型DP算法并验证其优越性说话速率变化导致时间轴非线性波动早期线性时间归一化无法处理复杂的非线性波动影响孤立词识别准确率。已有DP‑matching缺乏系统性优化虽然DP可用于非线性时间对齐但在对称/非对称形式选择、权重设计、斜率约束等方面缺乏理论分析与实验验证不同研究组算法差异大、性能不明确。目标在通用等间隔采样、无先验语言学知识的前提下给出一种最优的DP时间归一化算法提升类别间判别能力并降低识别错误率。二、论文核心1. 时间归一化距离的一般定义将两段语音表示为特征向量序列A a 1 , … , a I A a_1,\dots,a_IAa1​,…,aI​B b 1 , … , b J B b_1,\dots,b_JBb1​,…,bJ​。通过规整函数warping functionF { c ( k ) ( i ( k ) , j ( k ) ) } F \{c(k)(i(k),j(k))\}F{c(k)(i(k),j(k))}建立时间点对应关系。定义时间归一化距离为沿规整路径的加权距离之和再除以权重总和D ( A , B ) min ⁡ F ∑ k 1 K d ( i ( k ) , j ( k ) ) w ( k ) ∑ k 1 K w ( k ) D(A,B)\min_F \frac{\sum_{k1}^K d(i(k),j(k))\,w(k)}{\sum_{k1}^K w(k)}D(A,B)Fmin​∑k1K​w(k)∑k1K​d(i(k),j(k))w(k)​其中d ( i , j ) ∥ a i − b j ∥ d(i,j)\|a_i-b_j\|d(i,j)∥ai​−bj​∥w ( k ) w(k)w(k)为非负权重。2. 规整函数的约束条件为保证时间对齐符合语音实际特性对 ( F ) 施加多重约束单调性i ( k − 1 ) ≤ i ( k ) , j ( k − 1 ) ≤ j ( k ) i(k-1)\le i(k),\,j(k-1)\le j(k)i(k−1)≤i(k),j(k−1)≤j(k)连续性相邻步长不超过1( i,j ) 每步最多1边界条件( 1 , 1 ) (1,1)(1,1)到( I , J ) (I,J)(I,J)调整窗口∣ i ( k ) − j ( k ) ∣ ≤ r |i(k)-j(k)|\le r∣i(k)−j(k)∣≤r限制最大时间偏差斜率约束核心创新限制规整函数斜率避免在对角方向前进步数不足时过度偏向 i 或 j 轴用P n / m Pn/mPn/m度量约束强度P PP越大越刚性线性对齐对应P → ∞ P\to\inftyP→∞。3. 对称形式与非对称形式的权重设计对称形式w ( k ) ( i ( k ) − i ( k − 1 ) ) ( j ( k ) − j ( k − 1 ) ) w(k) (i(k)-i(k-1)) (j(k)-j(k-1))w(k)(i(k)−i(k−1))(j(k)−j(k−1))归一化系数N I J NIJNIJ→ 满足D ( A , B ) D ( B , A ) D(A,B)D(B,A)D(A,B)D(B,A)且最小权重为1不会遗漏特征向量。非对称形式w ( k ) ( i ( k ) − i ( k − 1 ) ) w(k) (i(k)-i(k-1))w(k)(i(k)−i(k−1))或仅对 jN I NINI或J JJ→ 可能出现w ( k ) 0 w(k)0w(k)0导致部分特征被排除理论上不利于均衡比较。论文从理论与实验两方面论证对称形式更优尤其在无/弱斜率约束时。4. DP 递推算法与斜率约束的具体化给出初始条件与DP方程g 1 ( c ( 1 ) ) d ( c ( 1 ) ) w ( 1 ) g_1(c(1)) d(c(1)) w(1)g1​(c(1))d(c(1))w(1)g k ( c ( k ) ) min ⁡ c ( k − 1 ) [ g k − 1 ( c ( k − 1 ) ) d ( c ( k ) ) w ( k ) ] g_k(c(k)) \min_{c(k-1)}[g_{k-1}(c(k-1)) d(c(k)) w(k)]gk​(c(k))minc(k−1)​[gk−1​(c(k−1))d(c(k))w(k)]。针对P 0, 1/2, 1, 2等斜率约束分别给出对称/非对称形式的具体DP方程与可达前驱点集合见表Ⅰ并对非对称形式做加权改进以避免零权重问题。三、实验结果实验基于日语数字10词与日语地名50词孤立词数据10名说话人、多重复采用带通滤波器组18ms采样自动增益控制Chebyshev距离强制决策最近邻分类。实验一对称/非对称与斜率约束对比日语数字对称形式明显优于非对称形式随斜率约束增强P PP增大两者差距缩小对称形式在 ( P\le1 ) 性能几乎不受影响非对称形式在 ( P1 ) 达到最优( P1 ) 后性能下降过度约束退化为近似线性对齐线性时间归一化错误率约0.8%而最优DP算法更低。实验二对称形式在地名集上的斜率约束日语地名地名集存在易混淆词对如 Chiba–Shiga 等对称形式在P ≈ 1 P\approx1P≈1达到最优证明斜率约束对提升判别有效说明即使在对称形式下适当斜率约束仍有益尤其在词汇量大、混淆度高时。实验三与同期其他DP算法对比对比算法包括Sakoe–Chiba(1973)、Velichko–Zagoruyko、White–Neely、Itakura 及线性方法结果错误率 %如下算法日语数字日语地名本文对称 P10.20.8本文非对称 P10.31.3Sakoe–Chiba(1973)0.31.5White–Neely0.331.3Itakura0.41.3Velichko–Zagoruyko2.02.7线性方法0.875.9→本文提出的“对称形式 斜率约束 P1”在两项任务上均取得最低错误率相比次优算法错误数减少约至2/3。四、分析与结论对称形式优势理论上有对称性、无特征排除实验上在各约束条件下均优于或等价于非对称形式尤其弱约束时差距明显。斜率约束的作用防止过度扭曲导致异类词误配如短辅音段对齐长元音( P1 ) 在性能与计算复杂度间取得最佳平衡DP方程较简单对对称形式在困难任务地名中同样有效。综合结论在等间隔采样、无额外语言学先验条件下对称型DP‑matching 斜率约束 ( P1 )是最优的时间归一化算法较同期多种DP方法识别错误显著更低且利于硬件实时实现文末已构建300ms处理60地名的DP处理器。五、Python代码示例importnumpyasnp# 视频A每帧特征Anp.array([1,2,3,4,5])# 视频B每帧特征播放慢一点Bnp.array([1,2,2,3,4,5])mlen(A)nlen(B)# DP矩阵dpnp.full((m1,n1),np.inf)dp[0,0]0foriinrange(1,m1):forjinrange(1,n1):# 当前两帧距离costabs(A[i-1]-B[j-1])dp[i,j]costmin(dp[i-1,j],# 删除dp[i,j-1],# 插入dp[i-1,j-1]# 匹配)print(dp)print(DTW distance ,dp[m,n])结果[[0.inf inf inf inf inf inf][inf0.1.2.4.7.11.][inf1.0.0.1.3.6.][inf3.1.1.0.1.3.][inf6.3.3.1.0.1.][inf10.6.6.3.1.0.]]DTW distance0.0如果使用fastdwtimportnumpyasnpfromfastdtwimportfastdtwfromscipy.spatial.distanceimporteuclidean Anp.array([[1],[2],[3],[4],[5]])Bnp.array([[1],[2],[2],[3],[4],[5]])distance,pathfastdtw(A,B,disteuclidean)print(distance)print(path)Reference[1] https://www.music-ir.org/mirex/wiki/MIREX_HOME[2] librosa.sequence.dtw官方文档https://librosa.org/doc/0.10.2/generated/librosa.sequence.dtw.html