डायनामिक टाइम वार्पिंग (DTW) एक एल्गोरिदम है जो दो समय श्रृंखला अनुक्रमों के बीच एक इष्टतम संरेखण की गणना करता है, जो गति, अवधि, या चरण में भिन्न हो सकते हैं। यूक्लिडियन दूरी जैसे सरल दूरी मापों के विपरीत, जो समान समय सूचकांकों पर बिंदुओं की तुलना करते हैं, DTW समय अक्ष के गैर-रेखीय वार्पिंग की अनुमति देता है ताकि अनुक्रमों के बीच सर्वोत्तम संभव मिलान पाया जा सके। यह गुण DTW को उन संकेतों की तुलना करने के लिए विशेष रूप से प्रभावी बनाता है जो अस्थायी परिवर्तनशीलता प्रदर्शित करते हैं, जैसे कि अलग-अलग दरों पर बोले गए शब्द, हस्तलिखित वर्ण, या विभिन्न उपकरणों से सेंसर रीडिंग।
एल्गोरिदम को 1970 के दशक में भाषण पहचान के संदर्भ में पेश किया गया था, जहां यह Machine learning मॉडल के व्यापक रूप से अपनाए जाने से पहले एक आधारभूत तकनीक बन गया। इसका मूल सिद्धांत गतिशील प्रोग्रामिंग है: यह एक लागत मैट्रिक्स का निर्माण करता है जो दो अनुक्रमों से बिंदुओं के हर जोड़े के बीच की दूरी को संचित करता है, फिर इस मैट्रिक्स के माध्यम से पथ ढूंढता है जो कुल संचयी दूरी को कम करता है। परिणामी वार्पिंग पथ इंगित करता है कि एक अनुक्रम में कौन से बिंदु दूसरे में कौन से बिंदुओं के अनुरूप हैं, और अंतिम DTW दूरी इस इष्टतम पथ के साथ दूरियों का योग है।
ऐतिहासिक विकास
DTW पर सबसे प्रारंभिक प्रकाशित कार्य अक्सर हिरोआकी साको और सेइबी चिबा को श्रेय दिया जाता है, जिन्होंने 1978 में दक्षता और मजबूती में सुधार के लिए बाधाओं के साथ एल्गोरिदम को औपचारिक रूप दिया। उनके पेपर, "डायनामिक प्रोग्रामिंग एल्गोरिदम ऑप्टिमाइज़ेशन फॉर स्पोकन वर्ड रिकग्निशन," ने साको-चिबा बैंड पेश किया, जो एक सामान्य बाधा है जो कम्प्यूटेशनल लागत को कम करने और पैथोलॉजिकल संरेखण को रोकने के लिए अनुमत वार्पिंग विंडो को सीमित करती है। उसी समय के आसपास, Xerox PARC और अन्य संस्थानों के शोधकर्ताओं ने पैटर्न मिलान के लिए समान गतिशील प्रोग्रामिंग दृष्टिकोणों की खोज की, लेकिन साको और चिबा का सूत्रीकरण मानक संदर्भ बन गया।
1980 के दशक के दौरान, DTW भाषण प्रणालियों में पृथक शब्द पहचान के लिए प्रमुख विधि थी, जिसे अक्सर समर्पित हार्डवेयर पर लागू किया जाता था। इसे बाद में छिपे हुए मार्कोव मॉडल (HMM) और हाल ही में Deep learning दृष्टिकोणों जैसे Neural network आधारित ध्वनिक मॉडल द्वारा प्रतिस्थापित किया गया। हालांकि, DTW एक बेंचमार्क के रूप में और प्रशिक्षण डेटा को संरेखित करने के लिए एक उपकरण के रूप में प्रभावशाली बना रहा।
एल्गोरिदमिक विवरण
DTW एल्गोरिदम दो अनुक्रमों पर काम करता है, X = (x1, x2, ..., xn) और Y = (y1, y2, ..., ym), जहां प्रत्येक xi और yj फीचर वेक्टर हैं (अक्सर स्केलर मान या बहुआयामी बिंदु)। एल्गोरिदम एक n-बाय-m मैट्रिक्स D बनाता है, जहां प्रत्येक सेल D(i, j) में उस सेल पर समाप्त होने वाले सर्वोत्तम संरेखण की संचयी दूरी होती है। पुनरावृत्ति संबंध है:
D(i, j) = d(xi, yj) + min(D(i-1, j), D(i, j-1), D(i-1, j-1))
जहां d(xi, yj) एक स्थानीय दूरी माप है, आमतौर पर निरंतर डेटा के लिए यूक्लिडियन दूरी या स्केलर मानों के लिए पूर्ण अंतर। अंतिम DTW दूरी D(n, m) है, और इष्टतम वार्पिंग पथ उस सेल से बैकट्रैकिंग द्वारा पुनर्प्राप्त किया जा सकता है।
दक्षता में सुधार और अपक्षयी संरेखण से बचने के लिए, कई बाधाएं आमतौर पर लागू की जाती हैं। साको-चिबा बैंड वार्पिंग पथ को एक निश्चित-चौड़ाई वाले विकर्ण बैंड तक सीमित करता है, खोज स्थान को O(nm) से O(nबैंडविड्थ) तक कम करता है। इटाकुरा समांतर चतुर्भुज, जिसका नाम फुमितादा इटाकुरा के नाम पर रखा गया है, एक ढलान बाधा का उपयोग करता है जो पथ की तीव्रता को सीमित करता है। इसके अतिरिक्त, सीमा शर्तों के लिए पथ को (1,1) पर शुरू करना और (n,m) पर समाप्त करना आवश्यक है, और एकरसता सुनिश्चित करती है कि सूचकांक कभी घटते नहीं हैं।
अनुप्रयोग
DTW ने कई डोमेन में अनुप्रयोग पाए हैं। भाषण पहचान में, इसका उपयोग बोले गए शब्दों की टेम्पलेट्स के साथ तुलना करने के लिए किया गया था, विशेष रूप से छोटे-शब्दावली कार्यों के लिए। समय-श्रृंखला विश्लेषण में (एक संबंधित क्षेत्र, हालांकि प्रदान की गई स्लग सूची में नहीं), DTW क्लस्टरिंग और वर्गीकरण के लिए एक मानक उपकरण है, जो अक्सर अस्थायी गलत संरेखण वाले डेटासेट पर यूक्लिडियन दूरी से बेहतर प्रदर्शन करता है। उदाहरण के लिए, एक्सेलेरोमीटर डेटा से इशारा पहचान में, DTW अलग-अलग गति से किए गए इशारों का मिलान कर सकता है।
जैव सूचना विज्ञान में, DTW को जीन अभिव्यक्ति प्रोफाइल या प्रोटीन अनुक्रमों को संरेखित करने के लिए लागू किया गया है, हालांकि यह नीडलमैन-वुंश जैसे अनुक्रम संरेखण एल्गोरिदम की तुलना में कम सामान्य है। वित्त में, DTW का उपयोग समय के साथ स्टॉक मूल्य आंदोलनों या आर्थिक संकेतकों की तुलना करने के लिए किया जाता है। रोबोटिक्स में, DTW प्रदर्शन से सीखने के लिए विभिन्न परीक्षणों से सेंसर रीडिंग को संरेखित करने में मदद करता है। एल्गोरिदम का उपयोग Data Augmentation में मौजूदा समय श्रृंखला को वार्प करके सिंथेटिक प्रशिक्षण उदाहरण उत्पन्न करने के लिए भी किया जाता है।
विविधताएं और विस्तार
DTW के कई विविधताएं विशिष्ट सीमाओं को संबोधित करने के लिए विकसित की गई हैं। डेरिवेटिव DTW (DDTW) कच्चे मानों के बजाय अनुक्रमों के पहले व्युत्पन्न का उपयोग करता है, जिससे यह ऑफसेट और स्केलिंग अंतरों के प्रति अधिक मजबूत होता है। भारित DTW फीचर वेक्टरों के विभिन्न आयामों को अलग-अलग भार निर्दिष्ट करता है। सॉफ्ट-DTW, जिसे 2017 में मार्को कुटुरी और मैथ्यू ब्लोंडेल द्वारा पेश किया गया था, न्यूनतम ऑपरेशन को एक सॉफ्ट न्यूनतम के साथ बदल देता है, जिससे दूरी अवकलनीय हो जाती है और इस प्रकार Deep learning पाइपलाइनों में हानि फ़ंक्शन के रूप में उपयोग योग्य हो जाती है।
बहुविविध DTW कई चैनलों वाले अनुक्रमों को संभालता है, और उपअनुक्रम DTW एक लंबे अनुक्रम के भीतर सर्वोत्तम मिलान उपअनुक्रम ढूंढता है। बड़े डेटासेट के लिए, फास्टDTW जैसे अनुमानित तरीके कम्प्यूटेशनल जटिलता को कम करने के लिए बहु-पैमाने दृष्टिकोण का उपयोग करते हैं। इन विस्तारों ने DTW को आधुनिक शोध में प्रासंगिक बनाए रखा है, विशेष रूप से Machine learning के संदर्भ में जहां अवकलनीय संस्करण अंत-से-अंत प्रशिक्षण को सक्षम करते हैं।
आधुनिक AI से संबंध
जबकि DTW एक Deep learning विधि नहीं है, यह Artificial intelligence के युग में प्रासंगिक बना हुआ है। इसका उपयोग अक्सर Neural network मॉडल, जैसे Residual Network (ResNet) या U-Net आर्किटेक्चर, में अनुक्रम भविष्यवाणी के लिए फीड करने से पहले समय श्रृंखला को संरेखित करने के लिए एक प्रीप्रोसेसिंग चरण के रूप में किया जाता है। Speech recognition में (एक अवधारणा जो स्लग सूची में नहीं है), DTW अभी भी कम-संसाधन सेटिंग्स में कीवर्ड स्पॉटिंग के लिए उपयोग किया जाता है। एल्गोरिदम के गतिशील प्रोग्रामिंग सिद्धांत Sequence-to-Sequence (Seq2Seq) मॉडल में भी दिखाई देते हैं, जहां संरेखण ध्यान तंत्र के माध्यम से स्पष्ट रूप से सीखने के बजाय निहित रूप से सीखा जाता है।
MIT CSAIL और Stanford AI Lab जैसे संस्थानों के शोधकर्ताओं ने समय श्रृंखला वर्गीकरण और विसंगति का पता लगाने जैसे कार्यों के लिए DTW को Deep learning के साथ जोड़ने वाले हाइब्रिड दृष्टिकोणों की खोज की है। सॉफ्ट-DTW की अवकलनीयता ने अस्थायी संरेखण की आवश्यकता वाले मॉडलों के प्रशिक्षण के लिए Loss Functions में इसके एकीकरण को सक्षम किया है। 2020 के दशक की शुरुआत तक, DTW समय श्रृंखला बेंचमार्क में एक मानक आधार रेखा बना हुआ है, और इसकी कम्प्यूटेशनल दक्षता अध्ययन का विषय बनी हुई है, जिसमें GPU और AWS Trainium हार्डवेयर के लिए अनुकूलन की खोज की जा रही है।