Dynamic Time Warping

From MSc Voice Technology
Jump to navigation Jump to search

Group Members

Zhang Ziyun

Wang Yinqiu

Cantao Su

Introduction

Dynamic time warping (DTW) is a well-known technique to find an optimal alignment between two given (time-dependent) sequences under certain restrictions. Intuitively, the sequences are warped in a nonlinear fashion to match each other. Originally, DTW has been used to compare different speech patterns in automatic speech recognition.[1]

While first introduced in 60s and extensively explored in 70s by application to the speech recognition, its applications have since expanded considerably. Today, DTW is employed in various domains, including but not limited to handwriting and online signature matching, sign language recognition, gesture recognition, and time series clustering. [2]

Historical Context

The roots of Dynamic Time Warping (DTW) can be traced back to the 1960s when it was first introduced as an algorithm for solving time series alignment problems. In the 1970s, DTW began to gain prominence through its application to speech recognition tasks.[3]

During this early period of research, scientists were grappling with fundamental challenges in recognizing spoken words and phrases. Even when the same word was spoken by the same person multiple times, factors like speech rate, emphasis, and coarticulation effects resulted in nonlinear time distortions when comparing utterances. These variations made it difficult to precisely match spoken words against templates or reference patterns, as the alignment of speech signals was non-linear and complex. This misalignment of timing poses a significant problem for accurate distance measurement in speech recognition systems. Even small shifts can lead to incorrect identification of words. Researchers explored linear normalization techniques to account for timing differences, but these proved insufficient for complex speech patterns.[4]

The groundbreaking contribution of DTW was its ability to address these challenges effectively. DTW allowed for "elastic" transformation of time series, which means it could align and compare speech signals with different time scales and phases. This flexibility in time-series alignment was crucial in mitigating the effects of shifting and distortion in speech signals.[3]

One of the primary motivations for developing DTW was to improve the accuracy of speech recognition systems. Traditional methods that relied on fixed templates for word recognition struggled to handle the variations in pronunciation time. DTW emerged as a method to measure the similarity of spoken patterns with different time zones, effectively solving the time alignment problem that had previously plagued speech recognition.

T. K. Vintsyuk's seminal paper titled "Speech Discrimination by Dynamic Programming" in 1972 played a significant role in introducing DTW as a powerful tool for speech recognition. This work emphasized the importance of time normalization, where the duration of unknown words is equated to that of standard words, to enhance recognition accuracy.[5]

In 1978, Sakoe and Chiba proposed using DTW for automatic word recognition. DTW allowed for an "elastic" time alignment through non-linear warping of the time axis between two time series. This dynamic programming approach was shown to outperform previous linear methods by more accurately modeling intrinsic fluctuations in speech. Around the same time, other pioneering studies also employed DTW for "time normalization" prior to classification.[6]

Key Innovations

The speech recognition algorithm based on DTW is a classic algorithm to solve the template matching problem, and its essence is the idea of dynamic programming (DP).

"Template matching" refers to the training phase, the feature vector sequence of speech corresponding to each word in vocabulary table was extracted as the template, and then was stored to the characteristics template library; Then, in the recognition phase, to compare the feature vector sequences of the speech to be recognized with each template of template library by dynamic time warping algorithm, and the result with the highest similarity would be taken as the recognition output.

The traditional template matching commonly uses the Euclidean distance metric to measure the degree of distortion, as follows:


Impact

In Speech recognition, as the speech is a time-dependent process, the utterances of the same word will have different durations, and utterances of the same word with the same duration will differ in the middle, due to different parts of the words being spoken at different rates.[7]In other words, the voice signal exhibits a high degree of variability, even for the same person pronounces the same word in the same way but in different time, they can’t be exactly the same because the variation arises from the unpredictable duration of each pronunciation. So it is not ideal to compare each word’s feature vector sequence’s effect directly.

Dynamic Time Warping algorithm is a prevailing approach which is practical and theoretical. Dynamic Time Warping algorithm is based on dynamic programming, problem solving approach and used for measuring similarity between two sequences, which may vary in time or space. Similarity is measured by computing a distance between two times series. [8]It is an early and classical algorithm for speech recognition especially for isolated word recognition.

The impact of Dynamic Time Warping on speech recognition is significant. One of the problems of speech recognition is different timing of speech alignment, and two words from the same word by the same user can have different times, which means small changes may result in incorrect recognition. Dynamic Time Warping is an efficient method for solving time alignment problem. Dynamic Time Warping solves this problem by aligning words correctly and calculating the minimum distance between two words. [7] It achieves more powerful recognition by adapting to changes in speech speed and pronunciation, which improves the accuracy of speech recognition.

Also, Dynamic Time Warping could be used to reduce the impact of background noise on speech recognition. Most of these DTW-related studies have either developed improved template-matching algorithms, or provided modified schemes for a DTW operation optimization framework for increasing the robustness of the recognition system.[9] Dynamic Time Warping could help distinguish between the speech signal and noise, improving recognition accuracy in noisy environment.

Traditional Dynamic Time Warping was one of the pioneering algorithms in speech recognition which offers important lessons for later developments and new recognition algorithms, like the Hidden Markov Models. The Hidden Markov Model and Dynamic Time Warping are actually sharing the same idea of DP(dynamic programming). [10] And HMMs and DTW are often used together to achieve better performance in speech recognition.

Future Research

The field of Dynamic Time Warping (DTW) in speech recognition continues to offer exciting opportunities for exploration and innovation.

Adaptability to Diverse Speaking Styles and Accents:

  • Researchers can investigate methods to make DTW-based systems more adaptable to variations in regional accents, speaking styles, and individual vocal characteristics. This research could draw inspiration from recent advances in accent adaptation and speaker recognition techniques.

Optimizing DTW for Real-Time Applications:

  • Future research can focus on optimizing DTW algorithms for parallel processing and efficient computation. Techniques such as parallelization and hardware acceleration may be explored to meet the demands of real-time applications.

Hybrid Approaches with Deep Learning:

  • Investigating hybrid systems that combine DTW with deep learning techniques, such as convolutional neural networks (CNNs) or recurrent neural networks (RNNs), could lead to more powerful and accurate speech recognition systems. This research direction can explore how to leverage the complementary strengths of both approaches.

Niche Applications:

  • Exploring DTW's application in niche areas like emotional speech recognition is another promising direction. Researchers can delve into the development of DTW-based models that can capture emotional cues and improve the recognition of emotional speech.

Scalability and Efficiency:

  • Scalability and efficiency are critical as speech recognition systems handle larger datasets and real-time tasks. Investigating how DTW can scale efficiently to handle big data while maintaining high recognition accuracy is an area ripe for exploration.

References

Together

  1. ↑ (2007). Dynamic Time Warping. In: Information Retrieval for Music and Motion. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74048-3_4
  2. ↑ Senin P. Dynamic time warping algorithm review[J]. Information and Computer Science Department University of Hawaii at Manoa Honolulu, USA, 2008, 855(1-23): 40.
  3. ↑ 3.0 3.1 Senin, Pavel. ‘Dynamic Time Warping Algorithm Review’, n.d.
  4. ↑ Sakoe, H., and S. Chiba. ‘Dynamic Programming Algorithm Optimization for Spoken Word Recognition’. IEEE Transactions on Acoustics, Speech, and Signal Processing 26, no. 1 (February 1978): 43–49. https://doi.org/10.1109/TASSP.1978.1163055.
  5. ↑ Vintsyuk, T. K. ‘Speech Discrimination by Dynamic Programming’. Cybernetics 4, no. 1 (1972): 52–57. https://doi.org/10.1007/BF01074755.
  6. ↑ Sakoe, H., and S. Chiba. ‘Dynamic Programming Algorithm Optimization for Spoken Word Recognition’. IEEE Transactions on Acoustics, Speech, and Signal Processing 26, no. 1 (February 1978): 43–49. https://doi.org/10.1109/TASSP.1978.1163055.
  7. ↑ 7.0 7.1 T. B. Amin and I. Mahmood, "Speech Recognition using Dynamic Time Warping," 2008 2nd International Conference on Advances in Space Technologies, Islamabad, Pakistan, 2008, pp. 74-79, doi: 10.1109/ICAST.2008.4747690.
  8. ↑ Yadav M, Alam M A. Dynamic time warping (dtw) algorithm in speech: a review[J]. International Journal of Research in Electronics and Computer Engineering, 2018, 6(1): 524-528.
  9. ↑ Ding Jr I, Yen C T, Hsu Y M. Developments of machine learning schemes for dynamic time-wrapping-based speech recognition[J]. Mathematical Problems in Engineering, 2013, 2013.
  10. ↑ Fang C. From dynamic time warping (DTW) to hidden markov model (HMM)[J]. University of Cincinnati, 2009, 3: 19.
Retrieved from "http://wiki.voice-technology.nl/index.php?title=Dynamic_Time_Warping&oldid=487"