अदृश्य मार्कोव मॉडल

अदृश्य मार्कोव प्रारूप (एचएमएम) सांख्यिकीय मार्कोव प्रारूप है जिसमें गणितीय प्रारूप वाली प्रणाली को मार्कोव प्रक्रिया माना जाता है- इसे कॉल करें $X$ - अप्राप्य (अदृश्य) अवस्थाओं के साथ। परिभाषा के भाग के रूप में, एचएमएम की आवश्यकता है कि अवलोकन योग्य प्रक्रिया हो $Y$ जिनके परिणाम के प्रभाव से प्रभावित होते हैं $X$ ज्ञात तरीके से। तब से $X$ प्रत्यक्ष रूप से नहीं देखा जा सकता है, लक्ष्य के बारे में सीखना है $X$ अवलोकन करके $Y.$ एचएमएम की अतिरिक्त आवश्यकता है कि इसका परिणाम $Y$ समय पर $t=t_{0}$ के परिणाम से विशेष रूप से प्रभावित होना चाहिए $X$ पर $t=t_{0}$ और इसके परिणाम $X$ और $Y$ पर $t<t_{0}$ से सशर्त रूप से स्वतंत्र होना चाहिए $Y$ पर $t=t_{0}$ दिया गया $X$ समय पर $t=t_{0}.$ अदृश्य मार्कोव प्रारूप ऊष्मप्रवैगिकी, सांख्यिकीय यांत्रिकी, भौतिकी, रसायन विज्ञान, अर्थशास्त्र, वित्त, संकेत आगे बढ़ाना , सूचना सिद्धांत, पैटर्न पहचान - जैसे वाक् पहचान, के लिए अपने अनुप्रयोगों के लिए जाने जाते हैं। लिखावट पहचान, हावभाव पहचान, पार्ट-ऑफ-स्पीच टैगिंग, म्यूजिकल स्कोर फॉलोइंग, आंशिक निर्वहन और जैव सूचना विज्ञान।

परिभाषा

होने देना $X_{n}$ और $Y_{n}$ असतत-समय स्टोकेस्टिक प्रक्रियाएं और $n\geq 1$. जोड़ी $(X_{n},Y_{n})$ अदृश्य मार्कोव प्रारूप है यदि

• $X_{n}$ मार्कोव प्रक्रिया है जिसका व्यवहार प्रत्यक्ष रूप से देखने योग्य (छिपा हुआ) नहीं है;
• $\operatorname {\mathbf {P} } {\bigl (}Y_{n}\in A\ {\bigl |}\ X_{1}=x_{1},\ldots ,X_{n}=x_{n}{\bigr )}=\operatorname {\mathbf {P} } {\bigl (}Y_{n}\in A\ {\bigl |}\ X_{n}=x_{n}{\bigr )},$

हर के लिए $n\geq 1,$ $x_{1},\ldots ,x_{n},$ और हर बोरेल सेट सेट $A$.

होने देना $X_{t}$ और $Y_{t}$ निरंतर-समय की स्टोकेस्टिक प्रक्रियाएँ हों। जोड़ी $(X_{t},Y_{t})$ छिपा हुआ मार्कोव प्रारूप है यदि

• $X_{t}$ मार्कोव प्रक्रिया है जिसका व्यवहार प्रत्यक्ष रूप से देखने योग्य (छिपा हुआ) नहीं है;
• $\operatorname {\mathbf {P} } (Y_{t_{0}}\in A\mid \{X_{t}\in B_{t}\}_{t\leq t_{0}})=\operatorname {\mathbf {P} } (Y_{t_{0}}\in A\mid X_{t_{0}}\in B_{t_{0}})$,

हर के लिए $t_{0},$ हर बोरेल सेट $A,$ और बोरेल सेट का हर परिवार $\{B_{t}\}_{t\leq t_{0}}.$

शब्दावली

प्रक्रिया की अवस्थाएँ $X_{n}$ (प्रति. $X_{t})$ अदृश्य अवस्था कहलाते हैं, और $\operatorname {\mathbf {P} } {\bigl (}Y_{n}\in A\mid X_{n}=x_{n}{\bigr )}$ (प्रति. $\operatorname {\mathbf {P} } {\bigl (}Y_{t}\in A\mid X_{t}\in B_{t}{\bigr )})$ उत्सर्जन संभावना या उत्पादन संभावना कहा जाता है।

उदाहरण

अदृश्यकलश से गेंद निकालना

चित्र 1. अदृश्यमार्कोव प्रारूप के संभाव्य पैरामीटर (उदाहरण)
एक्स — स्थिति
y — संभावित प्रेक्षण
a — अवस्था परिवर्तन की संभावनाएं
बी - आउटपुट संभावनाएं

अपने असतत रूप में, छिपी हुई मार्कोव प्रक्रिया को प्रतिस्थापन के साथ कलश समस्या के सामान्यीकरण के रूप में देखा जा सकता है (जहां कलश से प्रत्येक वस्तु अगले चरण से पहले मूल कलश में वापस आ जाती है)। इस उदाहरण पर विचार करें: कमरे में जो प्रेक्षक को दिखाई नहीं देता है वहां जिन्न है। कमरे में कलश X1, X2, X3, ... हैं जिनमें से प्रत्येक में गेंदों का ज्ञात मिश्रण है, प्रत्येक गेंद पर y1, y2, y3, ... का लेबल लगा है। जिन्न उस कमरे में कलश चुनता है और बेतरतीब ढंग से उस कलश से गेंद निकालता है। इसके बाद यह गेंद को कन्वेयर बेल्ट पर रखता है, जहां पर्यवेक्षक गेंदों के अनुक्रम का निरीक्षण कर सकता है, लेकिन कलशों का क्रम नहीं, जिससे वे निकाले गए थे। जिन्न के पास कलश चुनने की कुछ प्रक्रिया होती है; n-वीं गेंद के लिए कलश का चुनाव केवल यादृच्छिक संख्या पर निर्भर करता है और (n − 1)-वीं गेंद के लिए कलश का चुनाव। कलश का चुनाव इस एकल पिछले कलश से पहले चुने गए कलशों पर सीधे निर्भर नहीं करता है; इसलिए, इसे मार्कोव प्रक्रिया कहा जाता है। इसे चित्र 1 के ऊपरी भाग द्वारा वर्णित किया जा सकता है।

मार्कोव प्रक्रिया को ही नहीं देखा जा सकता है, केवल लेबल वाली गेंदों का क्रम, इस प्रकार इस व्यवस्था को छिपी हुई मार्कोव प्रक्रिया कहा जाता है। यह चित्र 1 में दिखाए गए आरेख के निचले भाग द्वारा चित्रित किया गया है, जहां कोई देख सकता है कि गेंदों y1, y2, y3, y4 को प्रत्येक अवस्था में खींचा जा सकता है। भले ही पर्यवेक्षक कलशों की संरचना को जानता हो और उसने अभी तीन गेंदों का क्रम देखा हो, उदा। कन्वेयर बेल्ट पर y1, y2 और y3, प्रेक्षक अभी भी सुनिश्चित नहीं हो सकता है कि जिन्न ने तीसरी गेंद को किस कलश (यानी, किस अवस्था में) से निकाला है। हालाँकि, प्रेक्षक अन्य सूचनाओं पर काम कर सकता है, जैसे कि संभावना है कि तीसरी गेंद प्रत्येक कलश से आई है।

मौसम अनुमान लगाने का खेल

दो मित्रों, ऐलिस और बॉब पर विचार करें, जो एक-दूसरे से बहुत दूर रहते हैं और जो उस दिन के बारे में टेलीफोन पर प्रतिदिन साथ बात करते हैं। बॉब को केवल तीन गतिविधियों में दिलचस्पी है: पार्क में घूमना, खरीदारी करना और अपने अपार्टमेंट की सफाई करना। क्या करना है इसका चुनाव विशेष रूप से किसी दिए गए दिन के मौसम द्वारा निर्धारित किया जाता है। ऐलिस को मौसम के बारे में कोई निश्चित जानकारी नहीं है, लेकिन वह सामान्य रुझान जानती है। बॉब उसे जो बताता है उसके आधार पर वह हर दिन करता है, ऐलिस यह अनुमान लगाने की कोशिश करती है कि मौसम कैसा रहा होगा।

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

एलिस क्षेत्र में सामान्य मौसम के रुझान को जानती है, और बॉब औसतन क्या करना पसंद करता है। दूसरे शब्दों में, एचएमएमके पैरामीटर ज्ञात हैं। उन्हें पायथन प्रोग्रामिंग भाषा में निम्नानुसार दर्शाया जा सकता है:

states = ("Rainy", "Sunny")

observations = ("walk", "shop", "clean")

start_probability = {"Rainy": 0.6, "Sunny": 0.4}

transition_probability = {
    "Rainy": {"Rainy": 0.7, "Sunny": 0.3},
    "Sunny": {"Rainy": 0.4, "Sunny": 0.6},
}

emission_probability = {
    "Rainy": {"walk": 0.1, "shop": 0.4, "clean": 0.5},
    "Sunny": {"walk": 0.6, "shop": 0.3, "clean": 0.1},
}

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

इसी प्रकार के उदाहरण को विटरबी एल्गोरिथम # उदाहरण पृष्ठ में और विस्तृत किया गया है।

संरचनात्मक वास्तुकला

नीचे दिया गया चित्र तत्काल एचएमएम के सामान्य आर्किटेक्चर को दिखाता है। प्रत्येक अंडाकार आकार यादृच्छिक चर का प्रतिनिधित्व करता है जो कई मानों को अपना सकता है। यादृच्छिक चर x(t) समय पर छिपी हुई अवस्था है t (उपरोक्त आरेख से प्रारूप के साथ, x(t) ∈ { x₁, एक्स₂, एक्स₃}). यादृच्छिक चर y(t) समय पर अवलोकन है t (y(t) ∈ { y₁, और₂, और₃, और₄}). आरेख में तीर (प्रायः जाली (ग्राफ)ग्राफ़) कहा जाता है) सशर्त निर्भरताओं को दर्शाता है।

आरेख से, यह स्पष्ट है कि समय पर अदृश्यचर x(t) का सशर्त संभाव्यता वितरण t, अदृश्यचर के मान दिए गए हैं x हर समय, केवल अदृश्यचर x(t − 1) के मान पर निर्भर करता है; समय t − 2 और इससे पहले के मूल्यों का कोई प्रभाव नहीं है। इसे मार्कोव संपत्ति कहा जाता है। इसी तरह, प्रेक्षित चर y(t) का मान केवल अदृश्यचर x(t) के मान पर निर्भर करता है (दोनों समय पर t).

यहां माने गए अदृश्यमार्कोव प्रारूप के मानक प्रकार में, अदृश्य चर का अवस्था स्थान असतत है, जबकि अवलोकन स्वयं असतत हो सकते हैं (सामान्यतः स्पष्ट वितरण से उत्पन्न) या निरंतर (सामान्यतः गॉसियन वितरण से)। अदृश्यमार्कोव प्रारूप के पैरामीटर दो प्रकार के होते हैं, संक्रमण संभावनाएँ और उत्सर्जन संभावनाएँ (जिन्हें आउटपुट संभावनाएँ भी कहा जाता है)। संक्रमण की संभावनाएं समय पर अदृश्य स्थिति को नियंत्रित करती हैं t समय पर अदृश्यअवस्था को चुना जाता है $t-1$.

यह माना जाता है कि अदृश्यअवस्था स्थान में से सम्मिलित है N संभावित मान, श्रेणीबद्ध वितरण के रूप में प्रतिरूपित। (अन्य संभावनाओं के लिए एक्सटेंशन पर नीचे दिया गया अनुभाग देखें।) इसका मतलब है कि इनमें से प्रत्येक के लिए N संभावित बताता है कि समय पर अदृश्य चर t में हो सकता है, इस अवस्था से प्रत्येक में संक्रमण की संभावना है N समय पर अदृश्यचर की संभावित अवस्थाएँ $t+1$, कुल के लिए $N^{2}$ संक्रमण की संभावनाएं। ध्यान दें कि किसी दिए गए अवस्था से संक्रमण के लिए संक्रमण संभावनाओं का सेट 1 होना चाहिए। इस प्रकार, $N\times N$ संक्रमण संभावनाओं का आव्यूह स्टोकेस्टिक आव्यूह है। क्योंकि किसी भी संक्रमण संभावना को बार अन्य ज्ञात होने के बाद निर्धारित किया जा सकता है, कुल मिलाकर $N(N-1)$ संक्रमण पैरामीटर।

इसके अतिरिक्त, प्रत्येक के लिए N संभावित राज्यों, उस समय अदृश्य चर की स्थिति को देखते हुए किसी विशेष समय पर देखे गए चर के वितरण को नियंत्रित करने वाली उत्सर्जन संभावनाओं का सेट होता है। इस सेट का आकार देखे गए चर की प्रकृति पर निर्भर करता है। उदाहरण के लिए, यदि प्रेक्षित चर असतत है M संभावित मान, श्रेणीबद्ध वितरण द्वारा शासित होंगे $M-1$ अलग पैरामीटर, कुल के लिए $N(M-1)$ सभी अदृश्यराज्यों पर उत्सर्जन पैरामीटर। दूसरी ओर, यदि प्रेक्षित चर है M-आयामी सदिश मनमाना बहुभिन्नरूपी गाऊसी वितरण के अनुसार वितरित किया जाएगा M पैरामीटर साधनों को नियंत्रित करते हैं और ${\frac {M(M+1)}{2}}$ सहप्रसरण आव्यूह को नियंत्रित करने वाले पैरामीटर, कुल के लिए $N\left(M+{\frac {M(M+1)}{2}}\right)={\frac {NM(M+3)}{2}}=O(NM^{2})$ उत्सर्जन पैरामीटर। (ऐसी स्थिति में, जब तक कि का मान M छोटा है, अवलोकन वेक्टर के अलग-अलग तत्वों के मध्य सहप्रसरण की प्रकृति को प्रतिबंधित करना अधिक व्यावहारिक हो सकता है, उदा। यह मानते हुए कि तत्व दूसरे से स्वतंत्र हैं, या कम प्रतिबंधात्मक रूप से, आसन्न तत्वों की निश्चित संख्या को छोड़कर सभी से स्वतंत्र हैं।)

निष्कर्ष

एचएमएम के अवस्था संक्रमण और आउटपुट संभावनाओं को आरेख के ऊपरी भाग में लाइन अपारदर्शिता द्वारा दर्शाया गया है। यह देखते हुए कि हमने आरेख के निचले हिस्से में आउटपुट अनुक्रम देखा है, हम उन राज्यों के सबसे संभावित अनुक्रम में दिलचस्पी ले सकते हैं जो इसे उत्पन्न कर सकते थे। आरेख में उपस्थित तीरों के आधार पर, निम्नलिखित अवस्था अनुक्रम उम्मीदवार हैं:
5 3 2 5 3 2
4 3 2 5 3 2
3 1 2 5 3 2
हम अवस्था अनुक्रम और प्रत्येक मामले के अवलोकन दोनों की संयुक्त संभावना का मूल्यांकन करके सबसे अधिक संभावित अनुक्रम पा सकते हैं (केवल प्रायिकता मानों को गुणा करके, जो यहां सम्मिलित तीरों की अस्पष्टता के अनुरूप हैं)। सामान्यतः , इस प्रकार की समस्या (अर्थात अवलोकन अनुक्रम के लिए सबसे अधिक संभावित स्पष्टीकरण खोजना) को विटरबी एल्गोरिथ्म का उपयोग करके कुशलता से हल किया जा सकता है।

अदृश्यमार्कोव प्रारूप के साथ कई अनुमान समस्याएं जुड़ी हुई हैं, जैसा कि नीचे बताया गया है।

देखे गए अनुक्रम की संभावना

प्रारूप के मापदंडों को देखते हुए, किसी विशेष आउटपुट अनुक्रम की संभावना को देखते हुए कार्य सर्वोत्तम तरीके से गणना करना है। इसके लिए सभी संभावित अवस्था अनुक्रमों पर योग की आवश्यकता है:

किसी अनुक्रम के प्रेक्षण की प्रायिकता

$Y=y(0),y(1),\dots ,y(L-1)\,$

लंबाई एल द्वारा दिया गया है

$P(Y)=\sum _{X}P(Y\mid X)P(X),\,$

जहां योग सभी संभावित छिपे-नोड अनुक्रमों पर चलता है

$X=x(0),x(1),\dots ,x(L-1).\,$

गतिशील प्रोग्रामिंग के सिद्धांत को लागू करते हुए, इस समस्या को भी आगे एल्गोरिथ्म का उपयोग करके कुशलता से नियंत्रित किया जा सकता है।

अव्यक्त चर की संभावना

प्रारूप के मापदंडों और टिप्पणियों के अनुक्रम को देखते हुए कई संबंधित कार्य या अधिक अव्यक्त चर की संभावना के बारे में पूछते हैं $y(1),\dots ,y(t).$

छानना

कार्य गणना करना है, प्रारूप के पैरामीटर और अवलोकनों का अनुक्रम दिया गया है, अनुक्रम के अंत में अंतिम गुप्त चर के अदृश्य राज्यों पर वितरण, यानी गणना करने के लिए $P(x(t)\ |\ y(1),\dots ,y(t))$. यह कार्य सामान्य रूप से तब उपयोग किया जाता है जब अव्यक्त चर के अनुक्रम को अंतर्निहित राज्यों के रूप में माना जाता है कि समय के प्रत्येक बिंदु पर संबंधित टिप्पणियों के साथ प्रक्रिया समय के बिंदुओं के अनुक्रम से गुजरती है। फिर, अंत में प्रक्रिया की स्थिति के बारे में पूछना स्वाभाविक है।

फॉरवर्ड एल्गोरिथम का उपयोग करके इस समस्या को कुशलता से नियंत्रित किया जा सकता है।

चौरसाई

यह फ़िल्टरिंग के समान है लेकिन अनुक्रम के मध्य में कहीं गुप्त चर के वितरण के बारे में पूछता है, यानी गणना करने के लिए $P(x(k)\ |\ y(1),\dots ,y(t))$ कुछ के लिए $k<t$. ऊपर वर्णित परिप्रेक्ष्य से, इसे समय टी के सापेक्ष अतीत में बिंदु k के लिए अदृश्यराज्यों पर संभाव्यता वितरण के रूप में माना जा सकता है।

आगे-पीछे एल्गोरिदम सभी अदृश्य स्टेट वेरिएबल्स के लिए स्मूथ वैल्यू की गणना करने के लिए अच्छा तरीका है।

सबसे अधिक संभावना स्पष्टीकरण

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

इस कार्य के लिए सभी संभावित अवस्था अनुक्रमों में अधिकतम खोजने की आवश्यकता है, और Viterbi एल्गोरिथ्म द्वारा कुशलतापूर्वक हल किया जा सकता है।

सांख्यिकीय महत्व

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

प्रज्ञता

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

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

अनुप्रयोग

प्रोफ़ाइल एचएमएम बहु अनुक्रम संरेखण मॉडलिंग

एचएमएम को अनेक क्षेत्रों में प्रारम्भ किया जा सकता है जहां लक्ष्य डेटा अनुक्रम को पुनर्प्राप्त करना है जो तुरंत देखने योग्य नहीं है (किन्तु अनुक्रम पर निर्भर अन्य डेटा हैं)। अनुप्रयोगों में सम्मिलित हैं:

• कम्प्यूटेशनल वित्त।
• एकल-अणु प्रयोग गतिज विश्लेषण।
• तंत्रिका विज्ञान।
• क्रिप्ट एनालिसिस।
• वाक् पहचान, सिरी सहित।
• भाषा संकलन।
• पार्ट-ऑफ-स्पीच टैगिंग।
• स्कैनिंग समाधान में दस्तावेज़ पृथक्करण।
• मशीन अनुवाद।
• आंशिक डिस्चार्ज।
• जीन भविष्यवाणी।
• हस्तलिपि अभिज्ञान।
• जैव अनुक्रमों का संरेखण।
• समय श्रृंखला।
• गतिविधि पहचान।
• प्रोटीन की तह
• अनुक्रम वर्गीकरण
• मेटामॉर्फिक वायरस का पता लगाना
• अनुक्रम मूल भाव
• डीएनए संकरण कैनेटीक्स
• क्रोमेटिन अवस्था के शोध
• परिवहन पूर्वानुमान
• सौर विकिरण परिवर्तनशीलता

इतिहास

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

1980 के दशक के उत्तरार्ध में, एचएमएम को जैविक अनुक्रमों के विश्लेषण के लिए प्रारम्भ किया जाने लगा, विशेष रूप से डीएनए में होता है। तब से, वे जैव सूचना विज्ञान के क्षेत्र में सर्वव्यापी हो गए हैं।

विस्तार

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

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

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

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

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

फिर भी अन्य संस्करण फैक्टोरियल हिडन मार्कोव प्रारूप है, जो एकल अवलोकन को समुच्चय के संबंधित अदृश्यचर पर वातानुकूलित करने की अनुमति देता है। $K$ एकल मार्कोव श्रृंखला के अतिरिक्त स्वतंत्र मार्कोव श्रृंखला है। यह एचएमएम के समान है, साथ में $N^{K}$अवस्था (यह मानते हुए कि वहाँ हैं $N$ प्रत्येक श्रृंखला के लिए अवस्था), और इसलिए, ऐसे प्रारूप में सीखना कठिन है: लंबाई के अनुक्रम के लिए $T$, सरल विटरबी एल्गोरिथम में जटिलता $O(N^{2K}\,T)$है। त्रुटिहीन समाधान के शोध के लिए, जंक्शन ट्री एल्गोरिथम का उपयोग किया जा सकता है, किन्तु इसका परिणाम $O(N^{K+1}\,K\,T)$ जटिलता होता है। व्यवहार में, अनुमानित प्रौद्योगिकी, जैसे परिवर्तनशील दृष्टिकोण, का उपयोग किया जा सकता है।

उपरोक्त सभी प्रारूपों को अदृश्य अवस्थाओं के मध्य अधिक दूर की निर्भरता की अनुमति देने के लिए बढ़ाया जा सकता है, उदा, किसी दिए गए अवस्था को पिछले अवस्था के अतिरिक्त पिछले दो या तीन अवस्थाओं पर निर्भर होने की अनुमति देना; अर्थात तीन या चार आसन्न अवस्थाओं (या सामान्यतः ) के समुच्चय को सम्मिलित करने के लिए संक्रमण की संभावनाओं को बढ़ाया जाता है $K$ आसन्न राज्य)। ऐसे प्रारूपों की हानि यह है कि उनके प्रशिक्षण के लिए डायनेमिक-प्रोग्रामिंग एल्गोरिदम में है $O(N^{K}\,T)$ के गति करने का समय, $K$ के लिए आसन्न अवस्था और $T$ कुल अवलोकन (अर्थात लंबाई-$T$ मार्कोव श्रृंखला) है।

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

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

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

यह भी देखें

• एंड्री मार्कोव
• बॉम-वेल्च एल्गोरिथम
• बायेसियन अनुमान
• बायेसियन प्रोग्रामिंग
• रिचर्ड जेम्स बॉयज़
• सशर्त यादृच्छिक क्षेत्र
• अनुमान सिद्धांत
• प्रोटीन सीक्वेंस सर्च के लिए HHpred / HHsearch फ्री सर्वर और सॉफ्टवेयर
• HMMER, प्रोटीन अनुक्रम विश्लेषण के लिए एक मुक्त छिपा हुआ मार्कोव मॉडल प्रोग्राम
• छिपा हुआ बर्नौली मॉडल
• छिपा हुआ अर्ध-मार्कोव मॉडल
• पदानुक्रमित छिपा हुआ मार्कोव मॉडल
• स्तरित छुपा मार्कोव मॉडल
• अनुक्रमिक गतिशील प्रणाली
• स्टोकेस्टिक संदर्भ-मुक्त व्याकरण
• समय श्रृंखला विश्लेषण
• चर-क्रम मार्कोव मॉडल
• विटरबी एल्गोरिथम

बाहरी संबंध

अवधारणाएं

• Teif, V. B.; Rippe, K. (2010). "क्रोमैटिन में प्रोटीन-डीएनए बंधन के लिए सांख्यिकीय-यांत्रिक जाली मॉडल". J. Phys.: Condens. Matter. 22 (41): 414105. arXiv:1004.5514. Bibcode:2010JPCM...22O4105T. doi:10.1088/0953-8984/22/41/414105. PMID 21386588. S2CID 103345.
• अदृश्यमार्कोव प्रारूप का खुलासा परिचय मार्क स्टैम्प, सैन जोस स्टेट यूनिवर्सिटी द्वारा।
• अपेक्षा-अधिकतमकरण के साथ एचएमएमकी फिटिंग - पूर्ण व्युत्पत्ति
• HMMs पर चरण-दर-चरण ट्यूटोरियल Archived 2017-08-13 at the Wayback Machine (लीड्स विश्वविद्यालय)
• अदृश्यमार्कोव प्रारूप (बुनियादी गणित का उपयोग करके प्रदर्शनी)
• अदृश्यमार्कोव प्रारूप (नारद वारकागोडा द्वारा)
• अदृश्यमार्कोव मॉडल: बुनियादी सिद्धांत और अनुप्रयोग भाग 1, /hmmtutorialpart2.pdf भाग 2 (वी. पेट्रुशिन द्वारा)
• जेसन आइजनर द्वारा स्प्रेडशीट पर व्याख्यान, वीडियो और इंटरैक्टिव स्प्रेडशीट

श्रेणी:अदृश्यमार्कोव मॉडल श्रेणी:मार्कोव मॉडल श्रेणी:जैव सूचना विज्ञान श्रेणी:लेख उदाहरण के साथ पायथन (प्रोग्रामिंग भाषा) कोड