बाउम-वेल्च एल्गोरिथ्म

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

बाउम-वेल्च एल्गोरिथ्म अपेक्षा-अधिकतमीकरण (EM) एल्गोरिथ्म का एक विशेष मामला है, जिसका उपयोग छिपे हुए मार्कोव मॉडल (HMM) के अज्ञात मापदंडों को खोजने के लिए किया जाता है। यह HMM में अनुमान लगाने की प्राथमिक विधि है, जो अपेक्षा चरण के लिए आँकड़ों की गणना करने हेतु फॉरवर्ड-बैकवर्ड एल्गोरिथ्म का उपयोग करती है। इस एल्गोरिथ्म का नाम लियोनार्ड ई. बाउम और लॉयड आर. वेल्च के नाम पर रखा गया है, जिन्होंने इसे 1960 के दशक के अंत और 1970 के दशक की शुरुआत में प्रिंसटन में IDA सेंटर फॉर कम्युनिकेशंस रिसर्च में सहयोगियों के साथ विकसित किया था।

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

औपचारिक विवरण

मान लीजिए \(X_t\) एक असतत छिपा यादृच्छिक चर है जिसमें \(N\) संभावित मान हैं, जो कुल \(N\) अवस्थाओं का प्रतिनिधित्व करते हैं। संक्रमण प्रायिकताएँ समय-स्वतंत्र मानी जाती हैं, जिससे स्टोकेस्टिक संक्रमण मैट्रिक्स \(A = \{a_{ij}\} = P(X_t = j \mid X_{t-1} = i)\) की परिभाषा प्राप्त होती है। प्रारंभिक अवस्था वितरण \(\pi_i = P(X_1 = i)\) द्वारा दिया जाता है।

अवलोकन चर \(Y_t\) \(K\) संभावित मानों में से एक ले सकते हैं। समय \(t\) पर अवस्था \(X_t = j\) के लिए एक निश्चित अवलोकन \(y_i\) की प्रायिकता \(b_j(y_i) = P(Y_t = y_i \mid X_t = j)\) द्वारा दी जाती है। इससे \(N \times K\) मैट्रिक्स \(B = \{b_j(y_i)\}\) प्राप्त होता है। एक अवलोकन अनुक्रम \(Y = (Y_1 = y_1, Y_2 = y_2, \ldots, Y_T = y_T)\) द्वारा दिया जाता है। इस प्रकार, एक छिपी मार्कोव श्रृंखला को \(\theta = (A, B, \pi)\) द्वारा वर्णित किया जा सकता है। बाउम-वेल्च एल्गोरिथ्म \(\theta^* = \arg\max_\theta P(Y \mid \theta)\) के लिए एक स्थानीय अधिकतम खोजता है।

एल्गोरिथ्म के चरण

एल्गोरिथ्म पैरामीटर अनुमानों को पुनरावृत्त रूप से परिष्कृत करता है। अपेक्षा चरण में, यह फॉरवर्ड-बैकवर्ड एल्गोरिथ्म का उपयोग करके फॉरवर्ड प्रायिकताएँ \(\alpha_t(i) = P(Y_1, \ldots, Y_t, X_t = i \mid \theta)\) और बैकवर्ड प्रायिकताएँ \(\beta_t(i) = P(Y_{t+1}, \ldots, Y_T \mid X_t = i, \theta)\) की गणना करता है। इनका उपयोग अपेक्षित पर्याप्त आँकड़ों की गणना के लिए किया जाता है, जैसे कि समय \(t\) पर अवस्था \(i\) में होने की प्रायिकता और समय \(t\) और \(t+1\) के बीच अवस्था \(i\) से अवस्था \(j\) में संक्रमण की प्रायिकता।

अधिकतमीकरण चरण में, एल्गोरिथ्म अपेक्षित लॉग-संभावना को अधिकतम करने के लिए मापदंडों \(A\), \(B\), और \(\pi\) को अद्यतन करता है। अद्यतन संक्रमण प्रायिकताओं की गणना अवस्था \(i\) से अवस्था \(j\) में संक्रमणों की अपेक्षित संख्या और अवस्था \(i\) में होने की अपेक्षित संख्या के अनुपात के रूप में की जाती है। इसी प्रकार, उत्सर्जन प्रायिकताओं को प्रत्येक अवस्था में अवलोकनों की अपेक्षित संख्या के आधार पर अद्यतन किया जाता है। प्रारंभिक अवस्था वितरण को समय 1 पर प्रत्येक अवस्था में होने की अपेक्षित प्रायिकता के आधार पर अद्यतन किया जाता है।

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

संख्यात्मक स्थिरता

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

अनुप्रयोग

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

औपचारिक विवरण

एल्गोरिथ्म के चरण

संख्यात्मक स्थिरता

अनुप्रयोग

संबंधित अवधारणाएँ