動態時間規整

在大部分的學科中，時間序列是數據的一種常見表示形式。對於時間序列處理來説，一個普遍的任務就是比較兩個序列的相似性。在時間序列中，需要比較相似性的兩段時間序列的長度可能並不相等，在語音識別領域表現為不同人的語速不同。

語音信號具有很強的隨機性，不同的發音習慣，發音時所處的環境不同，心情不同都會導致發音持續時間長短不一的現象。如單詞最後的聲音帶上一些拖音，或者帶上一點呼吸音，此時，由於拖音或呼吸音會被誤認為一個音素，造成單詞的端點檢測不準，造成特徵參數的變化，從而影響測度估計，降低識別率。

在孤立詞語音識別中，最為簡單有效的方法是採用動態時間歸整（Dynamic Time Warping）算法。該算法基於動態規劃（DP）的思想，解決了發音長短不一的模板匹配問題，是語音識別中出現較早、較為經典的一種算法，用於孤立詞識別。 ^[2] 

動態時間規整在60年代由日本學者Itakura提出，把未知量伸長或縮短(壓擴)，直到與參考模板的長度一致，在這一過程中，未知單詞的時間軸會產生扭曲或彎折，以便其特徵量與標準模式對應 ^[2]  。

是一個典型的優化問題，它用滿足一定條件的的時間規整函數

描述測試模板和參考模板的時間對應關係，求解兩模板匹配時累計距離最小所對應的規整函數。

測試語音參數共有

幀矢量，而參考模板共有

幀矢量，

和

不等，尋找一個時間規整函數

，它將測試矢量的時間軸

非線性地映射到模板的時間軸

上，並使該函數

滿足：

第

幀測試矢量

和第

幀模板矢量

之間的距離測度

最優時間規整情況下，所有矢量幀間的距離和

最小 ^[2]  。

給定兩個時間序列

和

，他們的長度分別是

和

：

若

，可直接計算兩個序列的距離；

若

，則需要線性縮放，即把短的序列線性放大到和長序列一樣的長度，或者把長的線性縮短到和短序列一樣的長度，再進行比較。但是，語音中各個段在不同情況下的持續時間會產生或長或短的變化，因此，這樣的計算導致識別效果不佳。實踐中，更多的是採用動態規劃（dynamic programming）的方法，具體如下：

為對齊這兩個序列，構造一個

的矩陣網格，矩陣

處的元素為

和

兩個點的距離

(即序列

的每一個點和

的每一個點之間的相似度，距離越小則相似度越高)，一般採用歐式距離，即

。該DP方法可以歸結為尋找一條通過此網格中若干格點的路徑，路徑通過的格點即為兩個序列進行計算的對齊的點。

那麼如何找到這條路徑？

我們把這條路徑定義為warping path 規整路徑，並用

來表示，

的第

個元素定義為

，

這條路徑不是隨意選擇的，需要滿足以下幾個約束：

任何一種語音的發音快慢都有可能變化，但是其各部分的先後次序不可能改變，因此所選的路徑必定是從左下角出發，在右上角結束。

若

，則路徑的下一個點

需要滿足

即，不可能跨過某個點去匹配，只能和自己相鄰的點對齊。這樣可以保證

和

中的每個座標都在

中出現。

如果

，那麼對於路徑的下一個點

需要滿足

這限制

上面的點必須是隨着時間單調進行的。

綜合連續性和單調性約束，每一個格點的路徑就只有三個方向。如：如果路徑已經通過了格點

，那麼下一個通過的格點只可能是下列三種情況之一：

滿足上面這些約束條件的路徑可以有指數個，然後我們感興趣的是使得下面的規整代價最小的路徑：

該路徑可通過動態規劃算法得到。 ^[2] 

假設標準模板R為字母ABCDEF(6個)，測試模板T為1234(4個)。R和T中各元素之間的距離已經給出。如下：

現假設題目滿足如下的約束：當從一個方格

或

或

中到下一個方格

，如果是橫着或者豎着的話其距離為

，如果是斜着對角線過來的則是

。其約束條件如下：

其中，

表示

個模板都從起始分量逐次匹配，已經到了

中的

分量和

中的

分量，並且匹配到該步是兩個個模板之間的距離。

所以我們將所有的匹配步驟標註後如下：

路徑如下圖： ^[2] 

假定一個孤立字（詞）語音識別系統，利用模板匹配法進行識別。這時一般是把整個單詞作為識別單元。在訓練階段，用户將詞彙表中的每一個單詞説一遍，提取特徵後作為一個模板，存入模板庫。在識別階段，對一個新來的需要識別的詞，也同樣提取特徵，然後採用DTW算法和模板庫中的每一個模板進行匹配，計算距離。求出最短距離也就是最相似的那個就是識別出來的字了 ^[2]  。