आगे–पीछे एल्गोरिदम

फॉरवर्ड-बैकवर्ड एल्गोरिदम एक मौलिक डायनेमिक प्रोग्रामिंग तकनीक है जिसका उपयोग हिडन मार्कोव मॉडल (HMM) और संबंधित प्रोबेबिलिस्टिक अनुक्रम मॉडल के संदर्भ में किया जाता है। यह अवलोकनों के अनुक्रम को देखते हुए प्रत्येक छिपी हुई अवस्था के पोस्टीरियर मार्जिनल वितरण की गणना करता है, जिससे कुशल अनुमान और पैरामीटर अनुमान संभव होता है। यह एल्गोरिदम शास्त्रीय मशीन लर्निंग की आधारशिला है और आधुनिक अनुप्रयोगों जैसे वाक् पहचान, बायोइन्फॉर्मेटिक्स और प्राकृतिक भाषा प्रसंस्करण में प्रासंगिक बना हुआ है।

1960 के दशक के अंत और 1970 के दशक की शुरुआत में विकसित, इस एल्गोरिदम को लियोनार्ड बॉम और उनके सहयोगियों द्वारा मार्कोव श्रृंखलाओं के प्रोबेबिलिस्टिक फलनों के लिए सांख्यिकीय अनुमान पर लेखों की एक श्रृंखला में औपचारिक रूप दिया गया था। इसे अक्सर विटरबी एल्गोरिदम के साथ प्रस्तुत किया जाता है, जो छिपी हुई अवस्थाओं का सबसे संभावित अनुक्रम खोजता है, जबकि फॉरवर्ड-बैकवर्ड एल्गोरिदम प्रत्येक समय चरण पर प्रत्येक व्यक्तिगत अवस्था के लिए संभावनाओं की गणना करता है। एल्गोरिदम दो चरणों में कार्य करता है: एक फॉरवर्ड पास जो किसी दिए गए समय बिंदु तक अनुक्रम को देखने और एक विशेष अवस्था में समाप्त होने की संभावना की गणना करता है, और एक बैकवर्ड पास जो प्रारंभिक अवस्था दिए जाने पर अनुक्रम के शेष भाग को देखने की संभावना की गणना करता है। इन दो संभावनाओं के समुच्चयों को संयोजित करने से वांछित पोस्टीरियर मार्जिनल प्राप्त होते हैं।

गणितीय सूत्रीकरण

एक HMM पर विचार करें जिसमें छिपी हुई अवस्थाएँ \( S = \{s_1, s_2, \ldots, s_N\} \), संक्रमण संभावनाएँ \( a_{ij} = P(s_j | s_i) \), उत्सर्जन संभावनाएँ \( b_j(o_t) = P(o_t | s_j) \), और प्रारंभिक अवस्था वितरण \( \pi_i = P(s_i) \) हों। अवलोकन अनुक्रम \( O = (o_1, o_2, \ldots, o_T) \) के लिए, फॉरवर्ड चर \( \alpha_t(i) \) को समय \( t \) तक आंशिक अवलोकन अनुक्रम की संभावना और समय \( t \) पर अवस्था \( s_i \) में होने की संभावना के रूप में परिभाषित किया गया है: \( \alpha_t(i) = P(o_1, o_2, \ldots, o_t, q_t = s_i | \lambda) \), जहाँ \( \lambda \) मॉडल पैरामीटरों को दर्शाता है। फॉरवर्ड पास \( \alpha_1(i) = \pi_i b_i(o_1) \) को प्रारंभ करता है और पुनरावर्ती रूप से \( \alpha_{t+1}(j) = b_j(o_{t+1}) \sum_{i=1}^N \alpha_t(i) a_{ij} \) की गणना करता है।

बैकवर्ड चर \( \beta_t(i) \) को समय \( t+1 \) से \( T \) तक अवलोकन अनुक्रम की संभावना के रूप में परिभाषित किया गया है, बशर्ते कि समय \( t \) पर अवस्था \( s_i \) हो: \( \beta_t(i) = P(o_{t+1}, o_{t+2}, \ldots, o_T | q_t = s_i, \lambda) \)। बैकवर्ड पास सभी \( i \) के लिए \( \beta_T(i) = 1 \) को प्रारंभ करता है और पुनरावर्ती रूप से \( \beta_t(i) = \sum_{j=1}^N a_{ij} b_j(o_{t+1}) \beta_{t+1}(j) \) की गणना करता है। समय \( t \) पर अवस्था \( s_i \) में होने की पोस्टीरियर संभावना तब \( \gamma_t(i) = \frac{\alpha_t(i) \beta_t(i)}{\sum_{j=1}^N \alpha_t(j) \beta_t(j)} \) द्वारा दी जाती है।

अनुक्रम मॉडलिंग में अनुप्रयोग

एल्गोरिदम का व्यापक रूप से बॉम-वेल्च एल्गोरिदम के माध्यम से HMM को प्रशिक्षित करने के लिए उपयोग किया जाता है, जो अपेक्षा-अधिकतमीकरण का एक उदाहरण है। E-चरण में, फॉरवर्ड-बैकवर्ड एल्गोरिदम अपेक्षित पर्याप्त आँकड़ों की गणना करता है, जैसे कि अवस्थाओं के बीच संक्रमणों की अपेक्षित संख्या और प्रत्येक अवलोकन प्रतीक के उत्सर्जनों की अपेक्षित संख्या। इन आँकड़ों का उपयोग तब M-चरण में मॉडल पैरामीटरों को अद्यतन करने के लिए किया जाता है। यह पुनरावृत्त प्रक्रिया संभावना फलन के स्थानीय अधिकतम में अभिसरित होती है।

वाक् पहचान में, फॉरवर्ड-बैकवर्ड प्रशिक्षण वाले HMM 1970 के दशक से 2000 के दशक की शुरुआत तक ध्वनिक मॉडलिंग के लिए प्रमुख दृष्टिकोण थे, इससे पहले कि वे बड़े पैमाने पर डीप लर्निंग विधियों द्वारा प्रतिस्थापित किए गए। बायोइन्फॉर्मेटिक्स में, एल्गोरिदम का उपयोग जीन भविष्यवाणी और प्रोटीन अनुक्रमों के विश्लेषण के लिए किया जाता है, जहाँ HMM संरक्षित मोटिफों का मॉडल बनाते हैं। प्राकृतिक भाषा प्रसंस्करण में, यह पार्ट-ऑफ-स्पीच टैगिंग और अनुक्रम-से-अनुक्रम मॉडल के प्रशिक्षण में दिखाई देता है जब संरचित आउटपुट परतों के साथ उपयोग किया जाता है।

आधुनिक मशीन लर्निंग से संबंध

हालाँकि फॉरवर्ड-बैकवर्ड एल्गोरिदम एक शास्त्रीय तकनीक है, इसके सिद्धांत आधुनिक मशीन लर्निंग में बने रहते हैं। फॉरवर्ड पास आवर्ती तंत्रिका नेटवर्क में सूचना के प्रसार के अनुरूप है, और बैकवर्ड पास त्रुटि संकेतों के बैकप्रोपेगेशन से मिलता जुलता है, हालाँकि गणितीय उद्देश्य भिन्न हैं। अनुक्रम लेबलिंग के लिए उपयोग किए जाने वाले तंत्रिका नेटवर्क में, जैसे कि द्विदिशात्मक LSTM, फॉरवर्ड और बैकवर्ड छिपी हुई अवस्थाओं को दोनों दिशाओं से संदर्भ को पकड़ने के लिए संयोजित किया जाता है, जो एल्गोरिदम के फॉरवर्ड और बैकवर्ड चरों को प्रतिबिंबित करता है। इसके अलावा, एल्गोरिदम का डायनेमिक प्रोग्रामिंग का कुशल उपयोग ट्रांसफॉर्मर-आधारित मॉडलों में समान तकनीकों को प्रेरित करता है, जैसे कि संरचित भविष्यवाणी के कुछ रूपों में उपयोग किया जाने वाला फॉरवर्ड-बैकवर्ड एल्गोरिदम और नामित इकाई पहचान जैसे कार्यों के लिए बड़े भाषा मॉडल के प्रशिक्षण में।

एल्गोरिदम बीम खोज की अवधारणा से भी संबंधित है, क्योंकि दोनों अनुक्रम समस्याओं में कम्प्यूटेशनल जटिलता का प्रबंधन करते हैं, लेकिन वे अलग-अलग उद्देश्यों की पूर्ति करते हैं: बीम खोज सबसे संभावित अनुक्रम का अनुमान लगाती है, जबकि फॉरवर्ड-बैकवर्ड सटीक मार्जिनल संभावनाओं की गणना करता है। प्रोबेबिलिस्टिक ग्राफिकल मॉडल में, फॉरवर्ड-बैकवर्ड एल्गोरिदम एक श्रृंखला ग्राफ पर सम-उत्पाद एल्गोरिदम का एक विशेष मामला है, और यह विश्वास प्रसार के माध्यम से वृक्ष-संरचित मॉडलों के लिए सामान्यीकृत होता है।

कम्प्यूटेशनल जटिलता और प्रकार

फॉरवर्ड-बैकवर्ड एल्गोरिदम \( O(T N^2) \) समय और \( O(T N) \) स्थान में चलता है, जहाँ \( T \) अनुक्रम की लंबाई है और \( N \) छिपी हुई अवस्थाओं की संख्या है। यह दक्षता इसे सैकड़ों अवस्थाओं के साथ हजारों समय चरणों के अनुक्रमों के लिए व्यवहार्य बनाती है। बड़े अवस्था स्थानों के लिए, फॉरवर्ड-फिल्टरिंग बैकवर्ड-सैंपलिंग एल्गोरिदम जैसे सन्निकटन का उपयोग कण फ़िल्टरिंग और मोंटे कार्लो विधियों में किया जाता है। ऑनलाइन सेटिंग्स में, अकेले फॉरवर्ड एल्गोरिदम का उपयोग फ़िल्टरिंग के लिए किया जा सकता है, जबकि बैकवर्ड पास के लिए पूरे अनुक्रम की आवश्यकता होती है, जिससे यह ऑफ़लाइन हो जाता है। प्रकारों में संख्यात्मक अंडरफ्लो से बचने के लिए स्केल्ड फॉरवर्ड-बैकवर्ड एल्गोरिदम शामिल है, जो लंबे अनुक्रमों और छोटी संभावनाओं से निपटने के दौरान सामान्य है।

यह भी देखें

• हिडन मार्कोव मॉडल
• विटरबी एल्गोरिदम
• बॉम-वेल्च एल्गोरिदम
• डायनेमिक प्रोग्रामिंग
• अनुक्रम मॉडलिंग