Editing Dynamic Time Warping (section)

== Key Innovations ==
The speech recognition algorithm based on DTW is a classic algorithm for solving the template matching problem, and its essence lies in the concept of [https://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92 dynamic programming (DP)].

"Template matching" refers to the training phase, where the feature vector sequence of speech corresponding to each word in the vocabulary table is extracted as a template and then stored in the characteristics template library. In the recognition phase, the feature vector sequences of the speech to be recognized are compared with each template in the template library using the dynamic time warping algorithm. The result with the highest similarity is taken as the recognition output.<ref>Zhang, Jing, and Benzhuo Qin. "DTW Speech Recognition Algorithm of Optimization Template Matching".</ref>

Traditional template matching commonly uses the [https://zh.wikipedia.org/wiki/%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E8%B7%9D%E7%A6%BB Euclidean distance] metric to measure the degree of distortion,Calculated as follows:

<math>d[T(n),R(m)]=\sum_{n=1}^p(t_n-r_m)^2</math>

Where n and m are frame indices, T is the length of the feature vector, p is the metric exponent, typically 2, representing the Euclidean distance. This formula is used to calculate the distortion between a test model frame T(m) and a reference model frame R(m). The smaller the distortion, the higher the similarity between the two feature vectors.<ref>Juang, B.-H. 《On the Hidden Markov Model and Dynamic Time Warping for Speech Recognition-A Unified View》. ''AT&T Bell Laboratories Technical Journal'' 63, No.7, September 1984): 1213–43. <nowiki>https://doi.org/10.1002/j.1538-7305.1984.tb00034.x</nowiki>.</ref>

However, in practical speech recognition, random variations occurring during pronunciation (such as differences in the duration of syllables and other subtle pronunciation variations) can result in two syllables not having a linear temporal correspondence. The Euclidean distance measurement only considers numerical differences at the same time points, and therefore, it cannot capture temporal distortions and nonlinear relationships.

The core innovation of DTW lies in introducing a novel sequence similarity measurement method, which involves point-wise matching and utilizes dynamic programming to obtain the optimal path. This approach measures the similarity between sequences by calculating distances at different time points, enabling the alignment of time series with different lengths. It possesses the capability to adapt to various data patterns and provides a more accurate assessment of the similarity between speech samples.

'''Specific Method:''' 

First, in a two-dimensional Cartesian coordinate system, construct an n × m matrix grid, with the horizontal axis representing the test model (n) and the vertical axis representing the reference model (m). Each intersection point (n, m) in the grid corresponds to a frame in the test model and the training model. The DP (Dynamic Programming) algorithm can find a path passing through multiple grid points in the grid. The points passed through by the path represent the alignment points for the calculation of the two sequences. Therefore, the sum of frame distortions at all intersection points in this path is minimized, and this path is the optimal warping path, which is the shortest distance measure between these two sequences. The smaller the path warping value, the more similar the two patterns become.

'''Path Selection：'''The path selection is not arbitrary; let's define the path as W, and it must adhere to the following conditions:

* Boundary Conditions: w<sub>1</sub>= (1, 1) and w<sub>k</sub> = (m, n). Because pronunciation in speech may vary, but the order of variations in different parts cannot be reversed, the only path possible is from the bottom left corner to the top right corner of the grid.
* Continuity: If w<sub>k-1</sub> = (a', b'), then the next point in the path, w<sub>k</sub>= (a, b), must satisfy (a-a') <= 1 and (b-b') <= 1. This means it's not possible to jump over any point; the alignment can only happen with adjacent points.
* Monotonicity: If w<sub>k-1</sub> = (a', b'), then the next point in the path, w<sub>k</sub> = (a, b), must satisfy 0 <= (a-a') and 0 <= (b-b'). This constraint ensures that points on the path must monotonically progress over time.

If these constraints are followed, each grid point on the path can only have three possible directions. For example, if the path has already passed through grid point (i, j), the next grid point to be passed can only be one of the following three: (i+1, j), (i, j+1), or (i+1, j+1).

The dynamic programming (DP) method searches for a suitable path within the grid to find the optimal match between the test model and the reference model, thus accomplishing the task of speech recognition.