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

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

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

इतिहास

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

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

एक्सटेंशन

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

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

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

स्यूडोकोड

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

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

• प्रत्येक तत्व $T_{1}[i,j]$ का $T_{1}$ अब तक के सबसे संभावित पथ की संभावना को संग्रहीत करता है ${\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}[i,j]$ का $T_{2}$ भंडार ${\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$ और इस प्रकार यह argmax को प्रभावित नहीं करता है।

इनपुट

• अवलोकन स्थान $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}$,
• स्टोकेस्टिक मैट्रिक्स $A$ आकार का $K\times K$ ऐसा है कि $A_{ij}$ राज्य से पारगमन की संक्रमण संभावना को संग्रहीत करता है $s_{i}$ कहना $s_{j}$,
• हिडन मार्कोव मॉडल $B$ आकार का $K\times N$ ऐसा है कि $B_{ij}$ अवलोकन की संभावना को संग्रहीत करता है $o_{j}$ राज्य से $s_{i}$.

आउटपुट

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

फ़ंक्शन VITERBI$(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$, प्रारंभिक संभावनाएँ $\pi _{i}$ राज्य में होने का $i$ और संक्रमण की संभावनाएँ $a_{i,j}$ राज्य से परिवर्तन का $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}}$

यहां हम arg max की मानक परिभाषा का उपयोग कर रहे हैं।

इस कार्यान्वयन की जटिलता है $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},
}

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

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

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

<सिंटैक्सहाइलाइट लैंग=पायथन लाइन=1 > डीईएफ़ विटरबी(अवलोकन, स्थिति, प्रारंभ_पी, ट्रांस_पी, एमिट_पी):

   वी = [{}]
   राज्यों में अनुसूचित जनजाति के लिए:
       वी[0] [एसटी] = {संभावना: प्रारंभ_पी[एसटी] * एमिट_पी[एसटी] [अवलोकन[0, पिछला: कोई नहीं}
   # जब t > 0 हो तो Viterbi चलाएँ
   रेंज में टी के लिए (1, लेन (ओब्स)):
       वी.संलग्न करें({})
       राज्यों में अनुसूचित जनजाति के लिए:
           max_tr_prob = V[t - 1] [राज्य[0 [prob] * trans_p[राज्य[0 [st] * emotional_p[st] [obs[t]
           prev_st_selected = स्थितियाँ[0]
           राज्यों में prev_st के लिए[1:]:
               tr_prob = V[t - 1] [prev_st] [prob ] * trans_p[prev_st] [st] * edit_p[st] [obs[t
               यदि tr_prob > max_tr_prob:
                   max_tr_prob = tr_prob
                   prev_st_selected = prev_st

           max_prob = max_tr_prob
           V[t] [st] = {संभावना: max_prob, पिछला: prev_st_selected}

   dptable(V) में लाइन के लिए:
       प्रिंट(लाइन)

   ऑप्ट = []
   अधिकतम_प्रोब = 0.0
   best_st = कोई नहीं
   # सबसे संभावित स्थिति और उसका बैकट्रैक प्राप्त करें
   सेंट के लिए, V[-1].आइटम() में डेटा:
       यदि डेटा[ समस्या ] > max_prob:
           max_prob = डेटा[संभावना]
           best_st = st
   ऑप्ट.एपेंड(best_st)
   पिछला = best_st

   # पहले अवलोकन तक बैकट्रैक का पालन करें
   रेंज में टी के लिए (लेन (वी) - 2, -1, -1):
       opt.insert(0, V[t + 1] [पिछला] [पिछला])
       पिछला = वी[टी + 1] [पिछला] [पिछला]

   प्रिंट करें (राज्यों के चरण + .join(opt) + %s % max_prob की उच्चतम संभावना के साथ हैं)

डीईएफ़ डीपीटेबल(वी):

   # शब्दकोश से चरणों की एक तालिका प्रिंट करें
   उपज * 5 + .join(( %3d % i) i के लिए रेंज में(len(V)))
   V[0] में राज्य के लिए:
       उपज %.7s: % स्थिति + .join( .7s % ( %lf % v[state] [prob ]) for v in V)

</सिंटैक्सहाइलाइट> कार्यक्रम viterbi निम्नलिखित तर्क लेता है: obs अवलोकनों का क्रम है, उदा. ['normal', 'cold', 'dizzy']; states छिपी हुई अवस्थाओं का समूह है; start_p प्रारंभ संभावना है; trans_p संक्रमण संभावनाएँ हैं; और emit_p उत्सर्जन संभावनाएँ हैं। कोड की सरलता के लिए, हम मानते हैं कि अवलोकन अनुक्रम obs गैर-रिक्त है और वह trans_p[i] [j] और emit_p[i] [j] सभी राज्यों i,j के लिए परिभाषित किया गया है।

चल रहे उदाहरण में, फ़ॉरवर्ड/विटर्बी एल्गोरिदम का उपयोग निम्नानुसार किया जाता है:

viterbi(obs,
        states,
        start_p,
        trans_p,
        emit_p)

स्क्रिप्ट का आउटपुट है

$ python viterbi_example.py
         0          1          2
Healthy: 0.30000 0.08400 0.00588
Fever: 0.04000 0.02700 0.01512
The steps of states are Healthy Healthy Fever with highest probability of 0.01512

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

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

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

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

SOVA शास्त्रीय विटरबी एल्गोरिदम से इस मायने में भिन्न है कि यह एक संशोधित पथ मीट्रिक का उपयोग करता है जो इनपुट प्रतीकों की प्राथमिक संभाव्यता| फैसले का.

SOVA में पहला कदम उत्तरजीवी पथ का चयन करना है, जो प्रत्येक समय तत्काल एक अद्वितीय नोड, 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 में विटरबी डिकोडिंग के लिए कोड शामिल है।

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