विटरबी एल्गोरिथ्म एक डायनामिक प्रोग्रामिंग एल्गोरिथ्म है जो छिपे हुए राज्यों के उस अनुक्रम की पहचान करता है जिसने दिए गए अवलोकित घटनाओं के अनुक्रम को उत्पन्न किया होगा। परिणामी अनुक्रम को अक्सर विटरबी पथ कहा जाता है। इसे सबसे अधिक सामान्यतः छिपे हुए मार्कोव मॉडल (HMMs) पर लागू किया जाता है, जहाँ अंतर्निहित राज्य सीधे अवलोकनीय नहीं होते लेकिन अवलोकनों को प्रभावित करते हैं। उदाहरण के लिए, एक डॉक्टर जो कई दिनों तक रोगी के लक्षणों का अवलोकन करता है, वह एल्गोरिथ्म का उपयोग करके अंतर्निहित स्वास्थ्य स्थितियों के सबसे संभावित अनुक्रम का अनुमान लगा सकता है जिसने उन लक्षणों को उत्पन्न किया।
एल्गोरिथ्म ने CDMA और GSM डिजिटल सेलुलर नेटवर्क, डायल-अप मोडेम, उपग्रह और गहरे अंतरिक्ष संचार, और 802.11 वायरलेस LAN में उपयोग किए जाने वाले कन्वोल्यूशनल कोड को डिकोड करने में सार्वभौमिक अनुप्रयोग पाया है। यह भाषण पहचान, भाषण संश्लेषण, वक्ता विभाजन, कीवर्ड स्पॉटिंग, कम्प्यूटेशनल भाषाविज्ञान, और जैव सूचना विज्ञान में भी व्यापक रूप से उपयोग किया जाता है। भाषण-से-पाठ प्रणालियों में, ध्वनिक संकेत अवलोकित अनुक्रम के रूप में कार्य करता है, और पाठ स्ट्रिंग छिपा हुआ कारण होता है; विटरबी एल्गोरिथ्म ध्वनिक संकेत के आधार पर सबसे संभावित पाठ ढूंढता है।
इतिहास
विटरबी एल्गोरिथ्म का नाम एंड्रयू विटरबी के नाम पर रखा गया है, जिन्होंने 1967 में इसे शोरगुल वाले डिजिटल संचार लिंक पर कन्वोल्यूशनल कोड के लिए एक डिकोडिंग एल्गोरिथ्म के रूप में प्रस्तावित किया था। इसका एकाधिक आविष्कार का इतिहास है, जिसमें कम से कम सात स्वतंत्र खोजें शामिल हैं, जिनमें विटरबी, नीडलमैन और वुन्श, और वैगनर और फिशर की खोजें शामिल हैं। इसे 1987 की शुरुआत में ही भाषा प्रसंस्करण में भाग-की-भाषण टैगिंग की विधि के रूप में पेश किया गया था।
"विटरबी पथ" और "विटरबी एल्गोरिथ्म" शब्द संभावनाओं से जुड़ी अधिकतमीकरण समस्याओं के लिए डायनामिक प्रोग्रामिंग दृष्टिकोण के मानक बन गए हैं। सांख्यिकीय पार्सिंग में, एक डायनामिक प्रोग्रामिंग एल्गोरिथ्म किसी स्ट्रिंग की सबसे संभावित संदर्भ-मुक्त व्युत्पत्ति (पार्स) खोज सकता है, जिसे आमतौर पर "विटरबी पार्स" कहा जाता है। एक और अनुप्रयोग लक्ष्य ट्रैकिंग है, जहाँ एल्गोरिथ्म उस ट्रैक की गणना करता है जो अवलोकनों के अनुक्रम को अधिकतम संभावना प्रदान करता है।
एल्गोरिथ्म अवलोकन
छिपे हुए राज्यों के समुच्चय S, संभावित उत्सर्जन (अवलोकनों) के समुच्चय M, और T अवलोकनों o0, o1, ..., oT-1 के अनुक्रम वाले एक छिपे हुए मार्कोव मॉडल को देखते हुए, विटरबी एल्गोरिथ्म उन छिपे हुए राज्यों का सबसे संभावित अनुक्रम ढूंढता है जो उन अवलोकनों को उत्पन्न कर सकते थे। प्रत्येक समय चरण t पर, एल्गोरिथ्म उस उप-समस्या को हल करता है जहाँ केवल ot तक के अवलोकनों पर विचार किया जाता है।
आकार T × |S| के दो मैट्रिक्स बनाए जाते हैं। मैट्रिक्स Pt,s में अवलोकन t पर राज्य s पर समाप्त होने की अधिकतम संभावना होती है, जो उस तक ले जाने वाले सभी संभावित राज्य अनुक्रमों में से होती है। मैट्रिक्स Qt,s उस पिछले राज्य को ट्रैक करता है जो इस अधिकतम संभावना वाले राज्य अनुक्रम में s से पहले उपयोग किया गया था।
मान लीजिए πs और ar,s क्रमशः प्रारंभिक और संक्रमण संभावनाएँ हैं, और bs,o राज्य s पर o का अवलोकन करने की संभावना है। फिर P के मान एक पुनरावृत्ति संबंध द्वारा दिए जाते हैं। समय t = 0 पर, Pt,s, πs को bs,o0 से गुणा करने के बराबर होता है। t > 0 के लिए, Pt,s सभी पिछले राज्यों r पर (Pt-1,r × ar,s × bs,ot) का अधिकतम मान होता है। मैट्रिक्स भरने के बाद, एल्गोरिथ्म अंतिम समय चरण पर उच्चतम संभावना वाले राज्य से Q मैट्रिक्स का उपयोग करके पीछे की ओर ट्रेस करता है ताकि सबसे संभावित राज्य अनुक्रम का पुनर्निर्माण किया जा सके।
संचार में अनुप्रयोग
एल्गोरिथ्म आधुनिक डिजिटल संचार की आधारशिला है। यह कन्वोल्यूशनल कोड को डिकोड करता है, जो कई वायरलेस और वायर्ड प्रणालियों में उपयोग किए जाने वाले त्रुटि-सुधार कोड हैं। CDMA और GSM सेलुलर नेटवर्क में, विटरबी एल्गोरिथ्म शोर और हस्तक्षेप के बावजूद प्रेषित डेटा को पुनर्प्राप्त करने में मदद करता है। डायल-अप मोडेम, उपग्रह लिंक, और गहरे अंतरिक्ष संचार प्रणालियाँ भी इस पर निर्भर करती हैं। 802.11 वायरलेस LAN मानक विश्वसनीय डेटा संचरण के लिए विटरबी डिकोडिंग को शामिल करता है।
एल्गोरिथ्म की दक्षता इसकी डायनामिक प्रोग्रामिंग प्रकृति से आती है: यह सभी संभावित राज्य अनुक्रमों की विस्तृत गणना से बचता है, मध्यवर्ती संभावनाओं को संग्रहीत करके और इष्टतमता के सिद्धांत का उपयोग करता है। यह लंबे अनुक्रमों को वास्तविक समय में डिकोड करना संभव बनाता है, यहाँ तक कि सीमित संसाधनों वाले उपकरणों पर भी।
भाषण और भाषा में अनुप्रयोग
भाषण पहचान में, विटरबी एल्गोरिथ्म ध्वनिक विशेषताओं को ध्वन्यात्मक या शब्द मॉडल के साथ संरेखित करता है। ध्वनिक संकेत अवलोकित अनुक्रम है, और पाठ स्ट्रिंग छिपा हुआ कारण है। एल्गोरिथ्म ध्वनिक संकेत के आधार पर पाठ की सबसे संभावित स्ट्रिंग ढूंढता है, जिससे सटीक प्रतिलेखन संभव होता है। इसका उपयोग भाषण संश्लेषण में भाषण इकाइयों के सबसे प्राकृतिक अनुक्रम का चयन करने के लिए, और वक्ता विभाजन में यह निर्धारित करने के लिए किया जाता है कि किसने कब बोला।
कम्प्यूटेशनल भाषाविज्ञान में, एल्गोरिथ्म भाग-की-भाषण टैगिंग पर लागू होता है, जहाँ छिपे हुए राज्य व्याकरणिक श्रेणियाँ हैं और अवलोकन शब्द हैं। यह सांख्यिकीय पार्सिंग का भी समर्थन करता है, जहाँ यह एक वाक्य के लिए सबसे संभावित पार्स वृक्ष ढूंढता है। जैव सूचना विज्ञान में, यह जैविक अनुक्रमों को संरेखित करने और जीन संरचनाओं की भविष्यवाणी करने में मदद करता है, DNA या प्रोटीन अनुक्रमों को अवलोकनों के रूप में और कार्यात्मक तत्वों को छिपे हुए राज्यों के रूप में मानता है।
संबंधित तकनीकें
विटरबी एल्गोरिथ्म अन्य डायनामिक प्रोग्रामिंग विधियों से निकटता से संबंधित है, जैसे कि फॉरवर्ड-बैकवर्ड एल्गोरिथ्म, जो सभी संभावित राज्य अनुक्रमों पर संभावनाओं की गणना करता है, न कि केवल सबसे संभावित एक की। यह Beam Search के साथ वैचारिक नींव भी साझा करता है, जो अनुक्रम निर्माण में उपयोग की जाने वाली एक अनुमानी खोज तकनीक है। आधुनिक Machine learning और Artificial intelligence प्रणालियों में, विशेष रूप से Sequence-to-Sequence (Seq2Seq) मॉडल और Large language model से जुड़े, बीम खोज को अक्सर सटीक विटरबी डिकोडिंग पर प्राथमिकता दी जाती है, क्योंकि इसमें बड़े राज्य स्थान शामिल होते हैं।
Neural network दृष्टिकोणों के उदय के बावजूद, विटरबी एल्गोरिथ्म हाइब्रिड प्रणालियों में प्रासंगिक बना हुआ है। उदाहरण के लिए, इसका उपयोग भाषण पहचान में Neural network ध्वनिक मॉडल से आउटपुट को डिकोड करने के लिए, या Natural language processing कार्यों में संरचनात्मक बाधाओं को लागू करने के लिए किया जा सकता है। इसकी गणितीय स्पष्टता और दक्षता शास्त्रीय और समकालीन दोनों अनुप्रयोगों में इसके निरंतर उपयोग को सुनिश्चित करती है।