एचएमएम

Question

में शीर्ष - के viterbi पथ ढूंढना मुझे एक एल्गोरिदम लिखना होगा जो एचएमएम में शीर्ष-के विटरबी पथ पाता है (सर्वोत्तम पथ खोजने के लिए नियमित विटरबी एल्गोरिदम का उपयोग करके)।

मुझे लगता है कि मुझे शायद प्रत्येक राज्य एन के लिए आकार के आकार के V_t, एन को सहेजने की आवश्यकता है जिसमें राज्य एन में समाप्त होने वाले शीर्ष-के पथ शामिल हैं, लेकिन मुझे यह सुनिश्चित नहीं है कि उस सूची का ट्रैक कैसे रखें। कोई विचार? धन्यवाद

Answer 1

हम इसे कुछ देखभाल के साथ हल कर सकते हैं। यह सबसे आसान है हम्म की ट्रेल्लिस संरचना को देखकर देखने के लिए:,

इस उदाहरण छिपा राज्यों 00 कर रहे हैं, 01, 10, 11 में इन चार एस के रूप में टिप्पणियों का सेट निरूपित दिखाया नहीं गया, लेकिन मान लें कि वे 0,1 हैं।

मान लीजिए कि हम सही संक्रमण मैट्रिक्स है:

transition[4][4] 

उत्सर्जन संभावनाओं:

emissions[4][2] 

और प्रारंभिक संभावनाओं:

p[2] 

इसलिए हर स्तंभ छिपा राज्यों का प्रतिनिधित्व करता है, और विटरबी का लक्ष्य टी को दिए गए सबसे संभावित छिपे हुए राज्य अनुक्रम की गणना करना है वह अवलोकन अब अल्फा (i, t) = सबसे बड़ी संभावना है कि छुपा राज्य अनुक्रम राज्य में है I (मैं 00, 01, 10, 11 में से एक है), समय टी पर जहां समय टी पर अवलोकन o_t है (o_t एक है 0, 1)। पहले अवलोकन को ओ_1 को इंगित करने दें। यह रूप में कुशलता से गणना की जा सकती:

alpha(i, 1) = p[i] * emissions[i][o_1] 
alpha(i, t) = emissions[i][o_t] * max_{k in states} (alpha(k, t-1) * transition[k][i]) 

क्रम में सबसे अच्छा रास्ता खोजने के लिए, हम संकेत पीछे की ओर अल्फा (मैं, टी) चरण में, राज्य में जो ऊपर में अधिकतम समारोह को बड़ा करने के लिए रहते हैं। आखिरकार हम सभी अल्फा (i, टी) और राज्यों में राज्यों की जांच करते हैं, और पाते हैं कि कौन सा सबसे बड़ा है, फिर सबसे अधिक संभावना राज्य अनुक्रम प्राप्त करने के लिए इसका पालन करें।

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

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

ऐसा लगता है कि हमारे पास निम्नलिखित समस्या है, एक मैट्रिक्स, एम, आकार 4 के के द्वारा, जहां एक पंक्ति पिछले राज्य का प्रतिनिधित्व करती है और एम [राज्य] वहां समाप्त होने वाले पथों के लिए शीर्ष के संभावनाओं का प्रतिनिधित्व करता है। इस प्रकार मीटर की प्रत्येक पंक्ति छोटी से छोटी करने के लिए सबसे बड़ा के अनुसार क्रमबद्ध किया जाता है, समस्या अब लगता है हो जाता है:

Best_K_Values(t, i) = Top K over all i,preceding_state,k (emissions[i][o_t] * m[preceding_state][k] * transition[preceding_state][i]) 

अब इस चुनौतीपूर्ण लग रहा है, लेकिन यह समझने के लिए कुछ समय लगेगा, हम एक ढेर का उपयोग कर क्रमबद्ध मैट्रिक्स समस्या से शीर्ष कश्मीर हल कर सकते हैं ओ (4 लॉग के) या ओ (numStates लॉग के) में सामान्य रूप से।

इस मामूली बदलाव Kth smallest element in sorted matrix देखें, बस ध्यान दें कि हमारे मामले में कॉलम क्रमबद्ध नहीं हैं, लेकिन विचार अभी भी लागू होता है।

यदि आप अभी भी पढ़ रहे हैं, तो ध्यान दें कि इस विधि की समग्र जटिलता ओ है ((numStates लॉग k) * numStates * t) = O (numStates^2 * t * log k) (मुझे विश्वास है कि यह सही जटिलता है)।

यह पालन करना मुश्किल हो सकता है, लेकिन अगर आपके कोई प्रश्न हैं, तो कृपया मुझे बताएं, या मैंने कुछ गलत तरीके से किया है।

Answer 2

इस पर वास्तव में व्यापक साहित्य है। यह कुछ खुदाई ले लिया, लेकिन मुझे यह मिला।

सूची Viterbi डिकोडिंग एल्गोरिदम आवेदन

http://www.ensc.sfu.ca/people/faculty/cavers/ENSC805/readings/42comm02-seshadri.pdf