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

एक छुपा मार्कोव मॉडल (एचएमएम) एक सांख्यिकीय मॉडल मार्कोव मॉडल है जिसमें गणितीय मॉडल वाली प्रणाली को मार्कोव प्रक्रिया माना जाता है - इसे कॉल करें $X$ - अप्राप्य (छिपी हुई) अवस्थाओं के साथ। परिभाषा के भाग के रूप में, एचएमएम की आवश्यकता है कि एक अवलोकन योग्य प्रक्रिया हो $Y$ जिनके परिणाम के प्रभाव से प्रभावित होते हैं $X$ एक ज्ञात तरीके से। तब से $X$ प्रत्यक्ष रूप से नहीं देखा जा सकता है, लक्ष्य के बारे में सीखना है $X$ अवलोकन करके $Y.$ HMM की एक अतिरिक्त आवश्यकता है कि इसका परिणाम $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) की है।

एलिस क्षेत्र में सामान्य मौसम के रुझान को जानती है, और बॉब औसतन क्या करना पसंद करता है। दूसरे शब्दों में, 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 के लिए छिपे हुए राज्यों पर संभाव्यता वितरण के रूप में माना जा सकता है।

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

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

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

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

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

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

सीखना

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

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

अनुप्रयोग

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

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

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

इतिहास

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

एक्सटेंशन

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

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

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

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

फिर भी एक अन्य संस्करण फैक्टोरियल हिडन मार्कोव मॉडल है, जो एक एकल अवलोकन को एक सेट के संबंधित छिपे हुए चर पर वातानुकूलित करने की अनुमति देता है। $K$ एकल मार्कोव श्रृंखला के बजाय स्वतंत्र मार्कोव श्रृंखला। यह एक एचएमएम के बराबर है, साथ में $N^{K}$ राज्य (यह मानते हुए कि वहाँ हैं $N$ प्रत्येक श्रृंखला के लिए राज्य), और इसलिए, ऐसे मॉडल में सीखना मुश्किल है: लंबाई के अनुक्रम के लिए $T$, एक सरल Viterbi एल्गोरिथम में जटिलता है $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.
• छिपे हुए मार्कोव मॉडल का एक खुलासा परिचय मार्क स्टैम्प, सैन जोस स्टेट यूनिवर्सिटी द्वारा।
• अपेक्षा-अधिकतमकरण के साथ HMM की फिटिंग - पूर्ण व्युत्पत्ति
• HMMs पर चरण-दर-चरण ट्यूटोरियल Archived 2017-08-13 at the Wayback Machine (लीड्स विश्वविद्यालय)
• छिपे हुए मार्कोव मॉडल (बुनियादी गणित का उपयोग करके एक प्रदर्शनी)
• छिपे हुए मार्कोव मॉडल (नारद वारकागोडा द्वारा)
• छिपे हुए मार्कोव मॉडल: बुनियादी सिद्धांत और अनुप्रयोग भाग 1, /hmmtutorialpart2.pdf भाग 2 (वी. पेट्रुशिन द्वारा)
• जेसन आइजनर द्वारा एक स्प्रेडशीट पर व्याख्यान, वीडियो और इंटरैक्टिव स्प्रेडशीट

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