विटर्बी एल्गोरिदम

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

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

इतिहास

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

संभावनाओं से जुड़ी समस्याओं को अधिकतम बढ़ाने के लिए इसमें गतिशील प्रोग्रामिंग एल्गोरिदम के अनुप्रयोग के लिए विटर्बी पथ और विटरबी एल्गोरिदम मानक शब्द बन गए हैं। इस प्रकार उदाहरण के लिए, सांख्यिकीय पार्सिंग में शृंखला के एकल सबसे संभावित संदर्भ-मुक्त व्युत्पत्ति (पार्स) की खोज के लिए गतिशील प्रोग्रामिंग एल्गोरिदम का उपयोग किया जा सकता है, जिसे सामान्यतः विटर्बी पार्स भी कहा जाता है। इस प्रकार अन्य अनुप्रयोग ऑप्टिकल मोशन ट्रैकिंग में होते है, जहां ट्रैक की गणना की जाती है और जिन्हें अवलोकनों के अनुक्रम को अधिकतम संभावना प्रदान करता है।

एक्सटेंशन

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

पुनरावृत्त विटरबी डिकोडिंग नामक एल्गोरिदम के साथ कोई भी अवलोकन के परिणाम को प्राप्त सकता है| इस प्रकार किसी दिए गए छिपे हुए मार्कोव मॉडल से सबसे अच्छा (औसतन) मेल खाता है। और यह एल्गोरिदम Qi वांग एट अल द्वारा प्रस्तावित होता है। टर्बो कोड से निपटने के लिए. पुनरावृत्तीय विटरबी डिकोडिंग संशोधित विटरबी एल्गोरिदम को पुनरावृत्त रूप से प्रयुक्त करके कार्य करता रहता है, और यह अभिसरण तक भराव के लिए स्कोर का पुनर्मूल्यांकन करता रहता है।

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

स्यूडोकोड

यह एल्गोरिथम पथ $X=(x_{1},x_{2},\ldots ,x_{T})$ उत्पन्न करता है जो समिष्ट $x_{n}\in S=\{s_{1},s_{2},\dots ,s_{K}\}$ का अनुक्रम होता है | जो $y_{n}\in O=\{o_{1},o_{2},\dots ,o_{N}\}$ के साथ अवलोकन $Y=(y_{1},y_{2},\ldots ,y_{T})$ उत्पन्न करते रहते हैं| और इस प्रकार जहाँ $N$ अवलोकन समिष्ट $O$ में संभावित अवलोकनों की संख्या होती है |

इसमें $K\times T$ आकार की दो 2-आयामी तालिकाएँ निर्मित होता हैं|

• $T_{1}$ प्रत्येक अवयव $T_{1}[i,j]$ का अब तक के सबसे संभावित पथ ${\hat {X}}=({\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j})$ की संभावना को ${\hat {x}}_{j}=s_{i}$ के साथ संग्रहीत करता है जो $Y=(y_{1},y_{2},\ldots ,y_{j})$ उत्पन्न करता है|
• $T_{2}$ में से प्रत्येक अवयव $T_{2}[i,j]$ अब तक के सबसे संभावित पथ के ${\hat {x}}_{j-1}$ को संगृहीत करता रहता हैं| और जिन्हें ${\hat {X}}=({\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j-1},{\hat {x}}_{j}=s_{i})$ $\forall j,2\leq j\leq T$ तालिका प्रविष्टियाँ $T_{1}[i,j],T_{2}[i,j]$ $K\cdot j+i$ के बढ़ते क्रम से भरे जाते हैं |

$T_{1}[i,j]=\max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$,

$T_{2}[i,j]=\operatorname {argmax} _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$,

इसके साथ जैसा कि नीचे परिभाषित हुआ हैं कि $A_{ki}$ और $B_{iy_{j}}$ के साथ किया गया है। और ध्यान दें कि $B_{iy_{j}}$ इसके पश्चात् की अभिव्यक्ति में प्रकट होने की आवश्यकता नहीं होती है, क्योंकि यह गैर-ऋणात्मक होता हैं| और इस प्रकार यह $k$ स्वतंत्र होता है और इस प्रकार यह आर्ग मैक्स को प्रभावित नहीं करता है।

इनपुट

• अवलोकन समिष्ट $O=\{o_{1},o_{2},\dots ,o_{N}\}$,
• अवस्था समिष्ट $S=\{s_{1},s_{2},\dots ,s_{K}\}$,
• प्रारंभिक संभावनाओं की श्रृंखला $\Pi =(\pi _{1},\pi _{2},\dots ,\pi _{K})$ ऐसा है कि $\pi _{i}$ इसकी संभावना को संग्रहीत करता है कि यह $x_{1}=s_{i}$ होता हैं|
• अवलोकनों का क्रम $Y=(y_{1},y_{2},\ldots ,y_{T})$इस प्रकार हैं कि $y_{t}=o_{i}$ यदि समय $t$ पर अवलोकन $o_{i}$ होता है|
• स्टोकेस्टिक आव्यूह आकार $K\times K$ का संक्रमण संभावना $A$ ऐसा है कि $A_{ij}$ समिष्ट $s_{i}$ से समिष्ट $s_{j}$ तक पारगमन की को संग्रहीत करता है|
• हिडन मार्कोव मॉडल आकार $K\times N$ का उत्सर्जन आव्यूह $B$ ऐसा है कि $B_{ij}$ समिष्ट $s_{i}$से $o_{j}$ देखने की संभावना संग्रहीत करता है।

आउटपुट

• सबसे संभावित छिपा हुआ अवस्था क्रम $X=(x_{1},x_{2},\ldots ,x_{T})$ होता हैं|

और यह फलन विटर्बी $(O,S,\Pi ,Y,A,B):X$ होता हैं|

इस प्रकार यह प्रत्येक समिष्ट के लिए $i=1,2,\ldots ,K$ करना होता हैं|

और यह $T_{1}[i,1]\leftarrow \pi _{i}\cdot B_{iy_{1}}$ होता हैं|

 $T_{2}[i,1]\leftarrow 0$

इसके लिए समाप्त होता हैं|

 प्रत्येक अवलोकन के लिए $j=2,3,\ldots ,T$ करना
 प्रत्येक समिष्ट के लिए $i=1,2,\ldots ,K$ करना 

$T_{1}[i,j]\gets \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$

$T_{2}[i,j]\gets \arg \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$

 के लिए समाप्त
 के लिए समाप्त 

$z_{T}\gets \arg \max _{k}{(T_{1}[k,T])}$ $x_{T}\leftarrow s_{z_{T}}$

के लिए $j=T,T-1,\ldots ,2$ करना

$z_{j-1}\leftarrow T_{2}[z_{j},j]$

 $x_{j-1}\leftarrow s_{z_{j-1}}$

के लिए समाप्त

 वापस करना $X$

अंत फलन

पाइथॉन (प्रोग्रामिंग भाषा) के निकट संक्षिप्त रूप में पुन: प्रस्तुत:

फलन विटरबी$(O,S,\Pi ,Tm,Em):best\_path$ टीएम: संक्रमण आव्यूह एम: उत्सर्जन आव्यूह 

$trellis\leftarrow matrix(length(S),length(O))$ प्रत्येक अवलोकन को देखते हुए प्रत्येक स्थिति की संभाव्यता बनाए रखना $pointers\leftarrow matrix(length(S),length(O))$ बैकपॉइंटर को सर्वोत्तम पूर्व स्थिति में रखने के लिए

 एस इन के लिए $range(length(S))$: समय 0 पर प्रत्येक छिपी हुई स्थिति की संभावना निर्धारित करें… 

$trellis[s,0]\leftarrow \Pi [s]\cdot Em[s,O[0]]$ ओ इन के लिए $range(1,length(O))$: ...और उसके पश्चात्, प्रत्येक समिष्ट की सबसे संभावित पूर्व स्थिति पर नज़र रखते हुए, k

 एस इन के लिए $range(length(S))$: 

$k\leftarrow \arg \max(trellis[k,o-1]\cdot Tm[k,s]\cdot Em[s,o]\ {\mathsf {for}}\ k\ {\mathsf {in}}\ range(length(S)))$

 $trellis[s,o]\leftarrow trellis[k,o-1]\cdot Tm[k,s]\cdot Em[s,o]$
 $pointers[s,o]\leftarrow k$
 $best\_path\leftarrow list()$
 $k\leftarrow \arg \max(trellis[k,length(O)-1]\ {\mathsf {for}}\ k\ {\mathsf {in}}\ range(length(S)))$ सर्वोत्तम अंतिम स्थिति का k ज्ञात करें
 ओ इन के लिए $range(length(O)-1,-1,-1)$: पिछले अवलोकन से पीछे हटें 

$best\_path.insert(0,S[k])$ सबसे संभावित पथ पर पिछली स्थिति डालें $k\leftarrow pointers[k,o]$ सर्वोत्तम पिछली स्थिति खोजने के लिए बैकपॉइंटर का उपयोग करें

 वापस करना $best\_path$

व्याख्या

मान लीजिए हमें अवस्था समिष्ट $S$ के साथ छिपा हुआ मार्कोव मॉडल (एचएमएम) दिया गया है ,समिष्ट $i$ में होने का प्रारंभिक संभावनाएँ $\pi _{i}$और समिष्ट $i$ से समिष्ट $j$ में संक्रमण की संभावनाएँ $a_{i,j}$ हैं मान लीजिए हम आउटपुट $y_{1},\dots ,y_{T}$,$x_{1},\dots ,x_{T}$ देखते हैं सबसे संभावित स्थिति अनुक्रम जो अवलोकन उत्पन्न करता है, पुनरावृत्ति संबंधों द्वारा दिया गया है

${\begin{aligned}V_{1,k}&=\mathrm {P} {\big (}y_{1}\ |\ k{\big )}\cdot \pi _{k},\\V_{t,k}&=\max _{x\in S}\left(\mathrm {P} {\big (}y_{t}\ |\ k{\big )}\cdot a_{x,k}\cdot V_{t-1,x}\right).\end{aligned}}$

यहाँ $V_{t,k}$ सबसे संभावित स्थिति अनुक्रम की संभावना है| और $\mathrm {P} {\big (}x_{1},\dots ,x_{t},y_{1},\dots ,y_{t}{\big )}$ जो पहले $t$ अवलोकन के लिए जिम्मेदार हैं जिसकी अंतिम अवस्था $k$ हैं विटर्बी पथ को बैक पॉइंटर्स को संभाल कर पुनः प्राप्त किया जा सकता है जो याद रखता है कि दूसरे समीकरण में किसी स्थिति $x$ का उपयोग किया गया था। मान लीजिए $\mathrm {Ptr} (k,t)$ वह फलन होता है जो $x$ का मान परिवर्तित करता है| जिसका उपयोग $V_{t,k}$ की गणना करने के लिए किया जाता है और यदि $t>1$ या $k$ यदि $t=1$ हैं तब

${\begin{aligned}x_{T}&=\arg \max _{x\in S}(V_{T,x}),\\x_{t-1}&=\mathrm {Ptr} (x_{t},t).\end{aligned}}$

यहां हम आर्ग मैक्स की मानक परिभाषा का उपयोग कर रहे हैं।

इस कार्यान्वयन की जटिलता $O(T\times \left|{S}\right|^{2})$ होती है | जिसका उत्तम अनुमान तब उपस्थित होता है जब आंतरिक लूप में अधिकतम केवल उन समिष्ट पर पुनरावृत्ति करके पाया जाता है और जो सीधे वर्तमान स्थिति से जुड़े होते हैं अर्थात $k$ से $j$ तक बढ़त होती है और फिर अमूर्त विश्लेषण का उपयोग करके कोई यह दिखा सकता है कि जटिलता $O(T\times (\left|{S}\right|+\left|{E}\right|))$ है| जहाँ $E$ ग्राफ़ में किनारों की संख्या होती है|

उदाहरण

ऐसे गांव पर विचार करें जहां सभी ग्रामीण या मध्य स्वस्थ हैं या उन्हें ज्वर है, और वह केवल गांव का डॉक्टर ही यह निर्धारित कर सकता है कि प्रत्येक को ज्वर है या नहीं हैं। डॉक्टर रोगी से यह पूछकर ज्वर का निदान करते हैं कि उन्हें कैसी अनुभूति हो रही है। और ग्रामीण केवल यही उत्तर दे सकते हैं कि उन्हें सामान्य, चक्कर या ठंड लग रही है।

डॉक्टर का मानना ​​है कि रोगी की स्वास्थ्य स्थिति अलग मार्कोव श्रृंखला के रूप में संचालित होती है। दो अवस्थाएँ हैं, "स्वस्थ" और ज्वर,", किन्तु डॉक्टर उनका सीधे निरीक्षण नहीं कर सकते हैं| वे डॉक्टर से छिपे हुए हैं। और प्रत्येक दिन, इस बात की निश्चित संभावना होती है कि रोगी डॉक्टर को बताएगा कि "मुझे सामान्य अनुभूति हो रही है", या "मुझे ठंड लग रही है", और या "मुझे चक्कर आ रहा है", यह रोगी की स्वास्थ्य स्थिति पर निर्भर करता है।

छिपी हुई स्थिति (स्वस्थ, ज्वर) के साथ अवलोकन (सामान्य, सर्दी, चक्कर आना) छिपे हुए मार्कोव मॉडल (एचएमएम) का निर्माण करते हैं, और इसे पायथन (प्रोग्रामिंग भाषा) में निम्नानुसार दर्शाया जा सकता है|

obs = ("normal", "cold", "dizzy")
states = ("Healthy", "Fever")
start_p = {"Healthy": 0.6, "Fever": 0.4}
trans_p = {
    "Healthy": {"Healthy": 0.7, "Fever": 0.3},
    "Fever": {"Healthy": 0.4, "Fever": 0.6},
}
emit_p = {
    "Healthy": {"normal": 0.5, "cold": 0.4, "dizzy": 0.1},
    "Fever": {"normal": 0.1, "cold": 0.3, "dizzy": 0.6},
}

इस प्रकार कोड के इस टुकड़े में, स्टार्ट_पी डॉक्टर के इस विश्वास का प्रतिनिधित्व करता है कि जब रोगी पहली बार आता है तब मध्य एचएमएम किस स्थिति में होता है| और (डॉक्टर केवल इतना जानता है कि रोगी स्वस्थ है)। यहां प्रयुक्त विशेष संभाव्यता वितरण संतुलन वितरण नहीं होता है| इससे (संक्रमण संभावनाओं को देखते हुए) लगभग {'Healthy': 0.57, 'Fever': 0.43}. हैं| और transition_p e> अंतर्निहित मार्कोव श्रृंखला में स्वास्थ्य स्थिति में परिवर्तन का प्रतिनिधित्व करता है। इस प्रकार उदाहरण में, रोगी जो आज स्वस्थ है, उसे कल ज्वर होने की केवल 30% संभावना होती है। और यह emit_p ई> दर्शाता है कि अंतर्निहित स्थिति (स्वस्थ या ज्वर) को देखते हुए, प्रत्येक संभावित अवलोकन (सामान्य, सर्दी, या चक्कर आना) की कितनी संभावना रहती है।इस प्रकार रोगी जो स्वस्थ होता है| उसके सामान्य अनुभूति करने की 50% संभावना रहती है| और जिस व्यक्ति को ज्वर होता है उसे चक्कर आने की संभावना 60% होती है।

दिए गए एचएमएम का चित्रमय प्रतिनिधित्व करता हैं|

रोगी लगातार तीन दिन दौरा करता है, और डॉक्टर को पता चलता है कि रोगी को पहले दिन सामान्य अनुभूति होती है| और दूसरे दिन ठंड लगती है, और तीसरे दिन चक्कर आता है। तब डॉक्टर का प्रश्न होता है कि रोगी की स्वास्थ्य स्थितियों का सबसे संभावित क्रम क्या है जो इन टिप्पणियों की व्याख्या करेगा? और इसका उत्तर विटर्बी एल्गोरिथम द्वारा दिया गया है।

def viterbi(obs, states, start_p, trans_p, emit_p):
    V = [{}]
    for st in states:
        V[0] [st] = {"prob": start_p[st] * emit_p[st] [obs[0]], "prev": None}
    # Run Viterbi when t > 0
    for t in range(1, len(obs)):
        V.append({})
        for st in states:
            max_tr_prob = V[t - 1] [states[0]] ["prob"] * trans_p[states[0]] [st] * emit_p[st] [obs[t]]
            prev_st_selected = states[0]
            for prev_st in states[1:]:
                tr_prob = V[t - 1] [prev_st] ["prob"] * trans_p[prev_st] [st] * emit_p[st] [obs[t]]
                if tr_prob > max_tr_prob:
                    max_tr_prob = tr_prob
                    prev_st_selected = prev_st

            max_prob = max_tr_prob
            V[t] [st] = {"prob": max_prob, "prev": prev_st_selected}

    for line in dptable(V):
        print(line)

    opt = []
    max_prob = 0.0
    best_st = None
    # Get most probable state and its backtrack
    for st, data in V[-1].items():
        if data["prob"] > max_prob:
            max_prob = data["prob"]
            best_st = st
    opt.append(best_st)
    previous = best_st

    # Follow the backtrack till the first observation
    for t in range(len(V) - 2, -1, -1):
        opt.insert(0, V[t + 1] [previous] ["prev"])
        previous = V[t + 1] [previous] ["prev"]

    print ("The steps of states are " + " ".join(opt) + " with highest probability of %s" % max_prob)

def dptable(V):
    # Print a table of steps from dictionary
    yield " " * 5 + "     ".join(("%3d" % i) for i in range(len(V)))
    for state in V[0]:
        yield "%.7s: " % state + " ".join("%.7s" % ("%lf" % v[state] ["prob"]) for v in V)

इससे पता चलता है कि अवलोकन ['normal', 'cold', 'dizzy'] संभवतः समिष्ट ['Healthy', 'Healthy', 'Fever']. के द्वारा उत्पन्न किए गए थे जिन्हें दूसरे शब्दों में, देखी गई गतिविधियों को देखते हुए, रोगी के पहले दिन और दूसरे दिन भी स्वस्थ रहने की संभावना रहती थी| और (उस दिन ठंड की अनुभूति होने के अतिरिक्त), और केवल तीसरे दिन ज्वर होने की संभावना थी।

विटर्बी के एल्गोरिदम के संचालन को इसके लिस आरेख के माध्यम से देखा जा सकता है। इस प्रकार विटर्बी पथ अनिवार्य रूप से इस जाली के माध्यम से सबसे छोटा रास्ता होता है।

सॉफ्ट आउटपुट विटर्बी एल्गोरिदम

सॉफ्ट आउटपुट विटर्बी एल्गोरिदम (सोवा) क्लासिकल विटर्बी एल्गोरिदम का प्रकार होता है।

सोवा मौलिक विटरबी एल्गोरिदम से इस प्रकार से भिन्न होता है कि यह संशोधित पथ मीट्रिक का उपयोग करता है जो इनपुट प्रतीकों की प्राथमिक संभावनाओं को ध्यान में रखता है, और निर्णय की विश्वसनीयता को संकेत करने वाला नरम आउटपुट उत्पन्न करता है।

सोवा में पहला कदम उत्तरजीवी पथ का चयन करना होता है, जो प्रत्येक समय तत्काल अद्वितीय नोड, t से होकर गुजरता है। चूँकि प्रत्येक नोड में 2 शाखाएँ एकत्रित होती हैं (एक शाखा को सर्वाइवर पाथ बनाने के लिए चुना जाता है, और दूसरी को छोड़ दिया जाता है), चुनी गई और छोड़ी गई शाखाओं के मध्य शाखा आव्युह (या निवेश) में अंतर त्रुटि की मात्रा को दर्शाता है।

विटर्बी एल्गोरिदम के हार्ड बिट निर्णय की विश्वसनीयता के नरम आउटपुट माप को इंगित करने के लिए, यह निवेश पूरी स्लाइडिंग विंडो (सामान्यतः कम से कम पांच बाधा लंबाई के बराबर) पर एकत्रित होती है।

यह भी देखें

• अपेक्षा-अधिकतमीकरण एल्गोरिथ्म
• बॉम-वेल्च एल्गोरिथम
• फॉरवर्ड-बैकवर्ड एल्गोरिथम
• अग्रेषित एल्गोरिथ्म
• त्रुटि-सुधार कोड
• विटर्बी डिकोडर
• हिडन मार्कोव मॉडल
• पार्टऑफ़ स्पीच टैगिंग
• ए* खोज एल्गोरिदम

सामान्य संदर्भ

• Viterbi AJ (April 1967). "कनवल्शनल कोड के लिए त्रुटि सीमाएं और एक एसिम्प्टोटिक रूप से इष्टतम डिकोडिंग एल्गोरिदम". IEEE Transactions on Information Theory. 13 (2): 260–269. doi:10.1109/TIT.1967.1054010. (नोट: विटर्बी डिकोडिंग एल्गोरिदम अनुभाग IV में वर्णित है।) सदस्यता आवश्यक है।
• Feldman J, Abou-Faycal I, Frigo M (2002). "A Fast Maximum-Likelihood Decoder for Convolutional Codes". कार्यवाही आईईईई 56वें ​​वाहन प्रौद्योगिकी सम्मेलन. pp. 371–375. CiteSeerX 10.1.1.114.1314. doi:10.1109/VETECF.2002.1040367. ISBN 978-0-7803-7467-6. S2CID 9783963. {{cite book}}: |journal= ignored (help); zero width space character in |title= at position 23 (help)
• Forney GD (March 1973). "विटरबी एल्गोरिदम". Proceedings of the IEEE. 61 (3): 268–278. doi:10.1109/PROC.1973.9030. सदस्यता आवश्यक है.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 16.2. Viterbi Decoding". संख्यात्मक व्यंजन विधि: वैज्ञानिक कंप्यूटिंग की कला (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
• Rabiner LR (February 1989). "छिपे हुए मार्कोव मॉडल और वाक् पहचान में चयनित अनुप्रयोगों पर एक ट्यूटोरियल". Proceedings of the IEEE. 77 (2): 257–286. CiteSeerX 10.1.1.381.3454. doi:10.1109/5.18626. S2CID 13618539. (एचएमएम के लिए फॉरवर्ड एल्गोरिदम और विटर्बी एल्गोरिदम का वर्णन करता है)।
• शिंगल, आर. और गॉडफ्राइड टूसेंट|गॉडफ्राइड टी. टूसेंट, संशोधित विटरबी एल्गोरिदम के साथ पाठ पहचान में प्रयोग, पैटर्न विश्लेषण और मशीन इंटेलिजेंस पर आईईईई लेनदेन, वॉल्यूम। पीएएमआई-एल, अप्रैल 1979, पृ. 184-193।
• शिंगल, आर. और गॉडफ्राइड टूसेंट|गॉडफ्राइड टी. टूसेंट, स्रोत सांख्यिकी के लिए संशोधित विटर्बी एल्गोरिदम की संवेदनशीलता, पैटर्न विश्लेषण और मशीन इंटेलिजेंस पर आईईईई लेनदेन, वॉल्यूम। पीएएमआई-2, मार्च 1980, पृ. 181-185।

बाहरी संबंध

• Implementations in Java, F#, Clojure, C# on Wikibooks
• Tutorial on convolutional coding with viterbi decoding, by Chip Fleming
• A tutorial for a Hidden Markov Model toolkit (implemented in C) that contains a description of the Viterbi algorithm
• Viterbi algorithm by Dr. Andrew J. Viterbi (scholarpedia.org).

कार्यान्वयन

• Mathematica में स्टोकेस्टिक प्रक्रियाओं के समर्थन के हिस्से के रूप में कार्यान्वयन है
• Susa सिग्नल प्रोसेसिंग फ्रेमवर्क आगे त्रुटि सुधार कोड और चैनल इक्वलाइजेशन के लिए C++ कार्यान्वयन प्रदान करता है ज यहाँ.
• C++
• C#
• जावा
• जावा 8
• जूलिया (HMMBase.jl)
• पर्ल
• प्रोलॉग
• हास्केल
• जाओ
• SFIHMM में विटरबी डिकोडिंग के लिए कोड सम्मिलित है।

श्रेणी:त्रुटि का पता लगाना और सुधार करना श्रेणी:गतिशील प्रोग्रामिंग श्रेणी:मार्कोव मॉडल श्रेणी: पायथन (प्रोग्रामिंग भाषा) कोड के उदाहरण वाले लेख