बायेसियन नेटवर्क

From Vigyanwiki

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

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

ग्राफिकल प्रारूप

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

उदाहरण

सशर्त संभाव्यता तालिकाओं के साथ साधारण बायेसियन नेटवर्क

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

संभाव्यता के श्रृंखला नियम द्वारा संयुक्त संभाव्यता वितरण है,

जहाँ G = घास गीला (सही/गलत), S = स्प्रिंकलर चालू (सही/गलत), और R = बारिश (सही/गलत)।

प्रारूप प्रभाव की उपस्थिति (तथाकथित व्युत्क्रम संभाव्यता) को देखते हुए किसी कारण की उपस्थिति के बारे में प्रश्नों का उत्तर दे सकता है, जैसे घास गीली होने पर बारिश होने की क्या संभावना है? सशर्त संभाव्यता सूत्र का उपयोग करके और सभी उपद्रव चरों पर योग करके:

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

फिर संख्यात्मक परिणाम (संबंधित चर मानों द्वारा सबस्क्रिप्टेड) ​​हैं

एक इंटरवेंशनल प्रश्न का उत्तर देने के लिए, जैसे कि बारिश होने की क्या संभावना है, यह देखते हुए कि हम घास को गीला करते हैं? उत्तर हस्तक्षेप के बाद के संयुक्त वितरण फलन द्वारा शासित होता है

इस प्रकार कारक को हटाकर पूर्व-हस्तक्षेप वितरण से प्राप्त किया गया हैं। इस प्रकार do संकारक G के मान को सत्य होने के लिए बाध्य करता है। बारिश की संभावना से अप्रभावित रहता है:

स्प्रिंकलर को चालू करने के प्रभाव का अनुमान लगाने के लिए:

अवधि के साथ हटा दिया, यह दर्शाता है कि यह प्रभाव घास को प्रभावित करती है अपितु बारिश को नहीं करता हैं।

अधिकांश नीति मूल्यांकन समस्याओं के रूप में, इन भविष्यवाणियों को अप्राप्य चरों को देखते हुए व्यवहार्य नहीं हो सकता है। इस प्रकार की क्रिया का प्रभाव चूंकि, अभी भी भविष्यवाणी की जा सकती है, जब भी पिछले दरवाजे की कसौटी पूरी होती है।[1][2] इसमें कहा गया है कि, यदि नोड्स का समुच्चय Z देखा जा सकता है यह इससे अलग हो जाता है,[3] इस प्रकार X से Y तक के सभी बैक-डोर पथ

एक बैक-डोर पथ वह है जो एक्स में तीर के साथ समाप्त होता है। बैक-डोर मानदंड को पूरा करने वाले समुच्चय को पर्याप्त या स्वीकार्य कहा जाता है। उदाहरण के लिए, समुच्चय Z = R G पर S = T के प्रभाव की भविष्यवाणी करने के लिए स्वीकार्य है, क्योंकि R d- (केवल) बैक-डोर पथ S ← R → G को अलग करता है। चूंकि, यदि S नहीं देखा गया है, तो कोई अन्य नहीं समुच्चय डी इस पथ को अलग करता है और घास (जी) पर स्प्रिंकलर (एस = टी) को चालू करने के प्रभाव को निष्क्रिय अवलोकन से भविष्यवाणी नहीं की जा सकती है। उस मामले में P(G | do(S = T)) की पहचान नहीं की जाती है। यह इस तथ्य को दर्शाता है कि, इंटरवेंशनल डेटा की कमी, S और G के बीच देखी गई निर्भरता कारण संबंध के कारण है या नकली है, (एक सामान्य कारण से उत्पन्न होने वाली स्पष्ट निर्भरता, आर)। (सिम्पसन का विरोधाभास देखें)

यह निर्धारित करने के लिए कि क्या मनमाना बायेसियन नेटवर्क से बिना देखे हुए चर के साथ कारण संबंध की पहचान की जाती है, कोई डू-कैलकुलस के तीन नियमों का उपयोग कर सकता है[1][4] और परीक्षण करें कि क्या सभी do शब्दों को उस संबंध की अभिव्यक्ति से हटाया जा सकता है, इस प्रकार यह पुष्टि करता है कि आवृत्ति डेटा से वांछित मात्रा का अनुमान लगाया जा सकता है।[5] यदि संयुक्त वितरण में निर्भरता विरल है, तो बायेसियन नेटवर्क का उपयोग संपूर्ण संभाव्यता तालिकाओं पर काफी मात्रा में मेमोरी बचा सकता है। उदाहरण के लिए, तालिका के रूप में 10 दो-मूल्यवान चरों की सशर्त संभावनाओं को संग्रहीत करने के लिए भोली विधि के लिए भंडारण स्थान की आवश्यकता होती है मान। यदि किसी चर का स्थानीय वितरण तीन से अधिक मूल चर पर निर्भर नहीं करता है, तो बायेसियन नेटवर्क प्रतिनिधित्व अधिक से अधिकतम संग्रहीत मान है ।

बायेसियन नेटवर्क का फायदा यह है कि मानव के लिए पूर्ण संयुक्त वितरण की तुलना में प्रत्यक्ष निर्भरता और स्थानीय वितरण को समझना सहज रूप से आसान है।

अनुमान और सीखना

बायेसियन नेटवर्क तीन मुख्य अनुमान कार्य करते हैं:

अनदेखे वैरियेबल का उल्लेख

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

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

पैरामीटर सीखना

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

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

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

संरचना सीखना

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

बायेसियन नेटवर्क (बीएन) की ग्राफ संरचना को स्वचालित रूप से सीखना मशीन सीखने के भीतर चुनौती है। इसके मूल विचार रिबेन और ज्यूडिया पर्ल द्वारा विकसित पुनर्प्राप्ति एल्गोरिथम पर वापस जाता है[6] और 3-नोड डीएजी में अनुमत तीन संभावित पैटर्नों के बीच अंतर पर आधारित है:

जंक्शन पैटर्न
पैटर्न प्रारूप
चैन
फोर्क
कोलिडर

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

इस प्रकार संरचनात्मक सीखने का वैकल्पिक तरीका अनुकूलन-आधारित खोज का उपयोग करता है। इसके लिए स्कोरिंग फलन और खोज रणनीति की आवश्यकता होती है। सामान्य स्कोरिंग फलन बायेसियन सूचना मानदंड या बीडीयू जैसे प्रशिक्षण डेटा को देखते हुए संरचना की पिछली संभावना है। इसके मान को अधिकतम करने के लिए उचित संरचना को लौटाने वाली संपूर्ण खोज की समय की आवश्यकता चर की संख्या में टेट्रेशन है। स्थानीय खोज रणनीति संरचना के स्कोर में सुधार लाने के उद्देश्य से वृद्धिशील परिवर्तन करती है। मार्कोव चेन मोंटे कार्लो जैसा वैश्विक खोज एल्गोरिदम मैक्सिमा और मिनिमा में फंसने से बच सकता है। फ्रीडमैन एट अल।[10][11] चरों के बीच आपसी जानकारी का उपयोग करने और इसे अधिकतम करने वाली संरचना खोजने पर चर्चा करें। वे पैरेंट के उम्मीदवार को k नोड्स तक सीमित करके और उसमें पूरी तरह से खोज करके ऐसा करते हैं।

सटीक बीएन सीखने के लिए विशेष रूप से तेज़ तरीका समस्या को अनुकूलन समस्या के रूप में डालना है, और पूर्णांक प्रोग्रामिंग का उपयोग करके इसे हल करना है। कटिंग-प्लेन विधि के रूप में हल करने के समय पूर्णांक कार्यक्रम (आईपी) में चक्रीयता बाधाओं को जोड़ा जाता है।[12] इस तरह की विधि 100 चर तक की समस्याओं को संभाल सकती है।

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

एक अन्य विधि में अपघटन योग्य प्रारूप के उप-वर्ग पर ध्यान केंद्रित करना उपस्थित है, जिसके लिए अधिकतम संभावना अनुमान का बंद रूप है। तब सैकड़ों चरों के लिए सुसंगत संरचना की खोज करना संभव है।[14]

बाउंडेड ट्रेविड्थ के साथ बायेसियन नेटवर्क सीखना सटीक, ट्रैक्टेबल अनुमान की अनुमति देने के लिए आवश्यक है, क्योंकि सबसे खराब स्थिति वाली इंट्रेंस जटिलता ट्रेविड्थ k (एक्सपोनेंशियल टाइम परिकल्पना के अनुसार) में एक्सपोनेंशियल है। फिर भी, ग्राफ की वैश्विक संपत्ति के रूप में, यह सीखने की प्रक्रिया की कठिनाई को काफी बढ़ा देता है। इस संदर्भ में प्रभावी शिक्षण के लिए K ट्री का उपयोग करना संभव है।[15]

सांख्यिकीय परिचय

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

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

यह बायेसियन_श्रेणीबद्ध_प्रारूपिंग का सबसे सरल उदाहरण है।

प्रक्रिया को दोहराया जा सकता है, उदाहरण के लिए, पैरामीटर बदले में अतिरिक्त पैरामीटर पर निर्भर हो सकता है , जिन्हें अपने स्वयं के पूर्व की आवश्यकता होती है। अंततः प्रक्रिया को समाप्त होना चाहिए, उनके साथ जो अनिर्दिष्ट मापदंडों पर निर्भर नहीं करते हैं।

परिचयात्मक उदाहरण

मापी गई मात्राओं को देखते हुए प्रत्येक ज्ञात मानक विचलन की सामान्य वितरण त्रुटियों के साथ ,

मान लीजिए कि हम के अनुमान लगाने में रुचि रखते हैं, इस प्रकार अनुमान लगाने की विधि होगी जो अधिकतम संभावना दृष्टिकोण का उपयोग करना हैं, चूँकि प्रेक्षण स्वतंत्र हैं, संभावना कारक है और अधिकतम संभावना अनुमान सरल है।

चूंकि, यदि मात्राएँ संबंधित हैं, तो उदाहरण के लिए व्यक्ति को अंतर्निहित वितरण से लिया गया है, तो यह संबंध स्वतंत्रता को नष्ट कर देता है और अधिक जटिल प्रारूप का सुझाव देता है, जैसे,

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

प्राथमिकताओं पर प्रतिबंध

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

परिभाषाएं और अवधारणाएं

बायेसियन नेटवर्क की कई समान परिभाषाएँ प्रस्तुत की गई हैं। निम्नलिखित के लिए, G = (v, e) निर्देशित चक्रीय ग्राफ (डीएजी) बनें और x = (xv), v ∈ v द्वारा अनुक्रमित यादृच्छिक चर का समुच्चय हो।

गुणनखंड परिभाषा

X, G के संबंध में बायेसियन नेटवर्क है यदि इसकी संयुक्त संभाव्यता घनत्व फलन (उत्पाद माप के संबंध में) को व्यक्तिगत घनत्व कार्यों के उत्पाद के रूप में लिखा जा सकता है, उनके पैरेंट चर पर सशर्त:[16]

जहां pa (v) v के पैरेंट का समुच्चय है (अर्ताथ वे वर्टिकल सीधे किनारे के माध्यम से वी को इंगित करते हैं)।

यादृच्छिक चर के किसी भी समुच्चय के लिए, संयुक्त वितरण के किसी भी सदस्य की संभावना की गणना सशर्त संभावनाओं से श्रृंखला नियम (प्रायिकता) (एक्स के सांस्थितिक क्रम को देखते हुए) का उपयोग करके की जा सकती है:[16]

उपरोक्त परिभाषा का उपयोग करते हुए, इसे इस प्रकार लिखा जा सकता है:

दो भावों के बीच का अंतर उनके किसी भी गैर-वंशज से चर की सशर्त स्वतंत्रता है, उनके मूल चर के मान दिए गए हैं।

स्थानीय मार्कोव संपत्ति

X, G के संबंध में बायेसियन नेटवर्क है यदि यह स्थानीय मार्कोव संपत्ति को संतुष्ट करता है: प्रत्येक चर अपने गैर-वंशजों की सशर्त स्वतंत्रता है जो इसके मूल चर हैं:[17]

जहाँ de(v) वंशजों का समुच्चय है और V \ de(v) v के गैर-वंशजों का समुच्चय है।

इसे पहली परिभाषा के समान शब्दों में व्यक्त किया जा सकता है, जैसे

पैरेंट का समुच्चय गैर-वंशजों के समुच्चय का सबसमुच्चय है क्योंकि ग्राफ साइकिल (ग्राफ सिद्धांत) है।

बायेसियन नेटवर्क विकसित करना

बायेसियन नेटवर्क का विकास अधिकांशतः डीएजी जी बनाने के साथ शुरू होता है जैसे कि x g के संबंध में स्थानीय मार्कोव संपत्ति को संतुष्ट करता है। कभी-कभी यह कारणात्मक ग्राफ डीएजी होता है। जी में अपने पैरेंट को दिए गए प्रत्येक चर के सशर्त संभाव्यता वितरण का मूल्यांकन किया जाता है। कई स्थितियों में, विशेष रूप से ऐसी स्थिति में जहां चर असतत होते हैं, यदि X का संयुक्त वितरण इन सशर्त वितरणों का उत्पाद है, तो X, G के संबंध में बायेसियन नेटवर्क है।[18]

मार्कोव कंबल

एक नोड का मार्कोव कंबल उसके पैरेंट, उसके बच्चों और उसके बच्चों के किसी भी अन्य पैरेंट से मिलकर नोड्स का समूह है। मार्कोव कंबल बाकी नेटवर्क से स्वतंत्र नोड को प्रस्तुत करता है, नोड के मार्कोव कंबल में चर का संयुक्त वितरण नोड के वितरण की गणना के लिए पर्याप्त ज्ञान है। X, G के संबंध में बायेसियन नेटवर्क है यदि प्रत्येक नोड अपने मार्कोव कंबल को देखते हुए नेटवर्क के अन्य सभी नोड्स से सशर्त रूप से स्वतंत्र है।[17]

डी-पृथक्करण

दो नोड्स के डी-पृथक्करण को परिभाषित करके इस परिभाषा को और अधिक सामान्य बनाया जा सकता है, जहां डी दिशात्मक है।[1]हम पहले निशान के डी-पृथक्करण को परिभाषित करते हैं और फिर हम उसके संदर्भ में दो नोड्स के डी-पृथक्करण को परिभाषित करेंगे।

पी को नोड यू से वी तक निशान होने दें। इस निशान के लिए दो नोड्स के बीच लूप-फ्री, अप्रत्यक्ष (अर्ताथ सभी किनारों की दिशाओं को नजरअंदाज कर दिया जाता है) पथ है। तब P को नोड्स Z के समुच्चय द्वारा d-पृथक कहा जाता है यदि निम्न स्थितियों में से कोई भी हो:

  • P में निर्देशित श्रृंखला उपस्थित है (अपितु पूर्ण रूप से होने की आवश्यकता नहीं है), या , जैसे कि मध्य नोड m Z में है,
  • P में कांटा होता है, , जैसे कि मध्य नोड m Z में है, या
  • पी में उलटा कांटा (या कोलाइडर) होता है, , जैसे कि मध्य नोड m Z में नहीं है और m का कोई वंशज Z में नहीं है।

नोड्स यू और वी जेड द्वारा डी-पृथक हैं यदि उनके बीच के सभी ट्रेल्स डी-पृथक हैं। यदि यू और वी डी-पृथक नहीं हैं, तो वे डी-कनेक्टेड हैं।

X, G के संबंध में बायेसियन नेटवर्क है, यदि किन्हीं दो नोड्स u, v के लिए इस प्रकार हैं:

जहाँ Z समुच्चय है जो d-u और v को अलग करता है। मार्कोव कंबल नोड्स का न्यूनतम समुच्चय है जो d-नोड v को अन्य सभी नोड्स से अलग करता है।

रीजन नेटवर्क

चूंकि बायेसियन नेटवर्क का उपयोग अधिकांशतः कार्य-कारण संबंधों का प्रतिनिधित्व करने के लिए किया जाता है, यह स्थिति नहीं होना चाहिए: Uv से V तक निर्देशित किनारे को X की आवश्यकता नहीं होती है, इस प्रकार Xu पर यथोचित रूप से निर्भर रहें. यह इस तथ्य से प्रदर्शित होता है कि बायेसियन नेटवर्क रेखांकन पर:

समतुल्य हैं: अर्ताथ वे ठीक वैसी ही सशर्त स्वतंत्रता आवश्यकताओं को लागू करते हैं।

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

अनुमान जटिलता और सन्निकटन एल्गोरिदम

1990 में, बड़े जैव सूचनात्मक अनुप्रयोगों पर स्टैनफोर्ड यूनिवर्सिटी में काम करते हुए, कूपर ने प्रमाणित किया कि बायेसियन नेटवर्क में सटीक अनुमान एनपी कठिन है।[19] इस परिणाम ने संभाव्य अनुमान के लिए ट्रैक्टेबल सन्निकटन विकसित करने के उद्देश्य से सन्निकटन एल्गोरिदम पर शोध को प्रेरित किया हैं। इस प्रकार 1993 में, पॉल डगम और माइकल लुबी ने बायेसियन नेटवर्क में संभाव्य अनुमान के सन्निकटन की जटिलता पर दो आश्चर्यजनक परिणाम को प्रमाणित किया हैं।[20] इसके लिए सबसे पहले उन्होंने यह प्रमाणित किया हैं कि कोई भी व्यवस्थित नियतात्मक एल्गोरिदम पूर्ण त्रुटि ɛ < 1/2 के भीतर संभाव्य अनुमान का अनुमान नहीं लगा सकता है। इसका दूसरा प्रमाण यह साबित किया कि कोई भी ट्रैक्टेबल यादृच्छिक एल्गोरिदम 1/2 से अधिक आत्मविश्वास की संभावना के साथ पूर्ण त्रुटि ɛ <1/2 के भीतर संभाव्य अनुमान का अनुमान नहीं लगा सकता है।

लगभग उसी समय, डेन रोथ ने साबित किया कि बायसियन नेटवर्क में सटीक अनुमान वास्तव में तीव्र-पी-पूर्ण| पी-पूर्ण है (और इस प्रकार संयोजन सामान्य फॉर्म फॉर्मूला (सीएनएफ) के संतोषजनक असाइनमेंट की संख्या की गणना करने जितना कठिन है) और इस कारक 2n1−ɛ जहाँ ɛ > 0 के लिए के भीतर अनुमानित अनुमान, यहां तक ​​कि प्रतिबंधित आर्किटेक्चर वाले बायेसियन नेटवर्क के लिए भी, एनपी-हार्ड है।[21][22]

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

सॉफ्टवेयर

बायेसियन नेटवर्क के लिए उल्लेखनीय सॉफ्टवेयर में उपस्थित हैं:

  • बस और गिब्स सैम्पलर (JAGS) - विन बग्स का ओपन-सोर्स विकल्प हैं। जो गिब्स नमूनाकरण का उपयोग करता है।
  • ओपेन बग्स - विन बग्स का ओपन-सोर्स विकास हैं।
  • एसपीएसएस प्रारूपर - व्यावसायिक सॉफ्टवेयर जिसमें बायेसियन नेटवर्क के लिए कार्यान्वयन उपस्थित है।
  • स्टेन (सॉफ्टवेयर) - स्टेन नो-यू-टर्न सैंपलर (एनयूटीएस) का उपयोग करके बायेसियन अनुमान प्राप्त करने के लिए ओपन-सोर्स पैकेज है,[24] हैमिल्टनियन मोंटे कार्लो का संस्करण।
  • PyMC3 - बायेसियन नेटवर्क का प्रतिनिधित्व करने के लिए एम्बेडेड डोमेन विशिष्ट भाषा को लागू करने वाला पायथन पुस्तकालय, और विभिन्न प्रकार के प्रमाण (एनयूटीएस सहित)
  • विनबग्स - एमसीएमसी सैंपलर्स के पहले कम्प्यूटेशनल कार्यान्वयन में अब नहीं रखा जाता।

इतिहास

बायेसियन नेटवर्क शब्द 1985 में जूडिया पर्ल द्वारा जोर देने के लिए गढ़ा गया था:[25]

  • इनपुट जानकारी की अधिकांशतः व्यक्तिपरक प्रकृति हैं।
  • जानकारी अपडेट करने के आधार के रूप में बायस कंडीशनिंग पर निर्भरता रहती हैं।
  • तर्क के कारण और साक्ष्य के तरीकों के बीच का अंतर हैं।[26]

1980 के दशक के अंत में इंटेलिजेंट सिस्टम्स में पर्ल की प्रोबेबिलिस्टिक रीज़निंग[27] और रिचर्ड ई. नीपोलिटन की विशेषज्ञ प्रणालियों में संभाव्य तर्क[28] उनके गुणों को सारांशित किया और उन्हें अध्ययन के क्षेत्र के रूप में स्थापित किया जाता हैं।

यह भी देखें

टिप्पणियाँ

  1. 1.0 1.1 1.2 1.3 1.4 Pearl, Judea (2000). Causality: Models, Reasoning, and Inference. Cambridge University Press. ISBN 978-0-521-77362-1. OCLC 42291253.
  2. "पिछले दरवाजे की कसौटी" (PDF). Retrieved 2014-09-18.
  3. "डी-बिना आँसू के जुदाई" (PDF). Retrieved 2014-09-18.
  4. Pearl J (1994). "क्रियाओं की एक संभाव्य गणना". In Lopez de Mantaras R, Poole D (eds.). UAI'94 Proceedings of the Tenth international conference on Uncertainty in artificial intelligence. San Mateo CA: Morgan Kaufmann. pp. 454–462. arXiv:1302.6835. Bibcode:2013arXiv1302.6835P. ISBN 1-55860-332-8.
  5. Shpitser I, Pearl J (2006). "Identification of Conditional Interventional Distributions". In Dechter R, Richardson TS (eds.). Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence. Corvallis, OR: AUAI Press. pp. 437–444. arXiv:1206.6876.
  6. Rebane G, Pearl J (1987). "The Recovery of Causal Poly-trees from Statistical Data". Proceedings, 3rd Workshop on Uncertainty in AI. Seattle, WA. pp. 222–228. arXiv:1304.2736.{{cite book}}: CS1 maint: location missing publisher (link)
  7. Spirtes P, Glymour C (1991). "विरल कारण रेखांकन की तेजी से वसूली के लिए एक एल्गोरिथ्म" (PDF). Social Science Computer Review. 9 (1): 62–72. doi:10.1177/089443939100900106. S2CID 38398322.
  8. Spirtes P, Glymour CN, Scheines R (1993). कारण, भविष्यवाणी, और खोज (1st ed.). Springer-Verlag. ISBN 978-0-387-97979-3.
  9. Verma T, Pearl J (1991). "कारण मॉडल की समानता और संश्लेषण". In Bonissone P, Henrion M, Kanal LN, Lemmer JF (eds.). UAI '90 Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence. Elsevier. pp. 255–270. ISBN 0-444-89264-8.
  10. Friedman N, Geiger D, Goldszmidt M (November 1997). "बायेसियन नेटवर्क वर्गीकरणकर्ता". Machine Learning. 29 (2–3): 131–163. doi:10.1023/A:1007465528199.
  11. Friedman N, Linial M, Nachman I, Pe'er D (August 2000). "अभिव्यक्ति डेटा का विश्लेषण करने के लिए बायेसियन नेटवर्क का उपयोग करना". Journal of Computational Biology. 7 (3–4): 601–20. CiteSeerX 10.1.1.191.139. doi:10.1089/106652700750050961. PMID 11108481.
  12. Cussens J (2011). "बायेसियन नेटवर्क कटिंग प्लेन के साथ सीख रहा है" (PDF). Proceedings of the 27th Conference Annual Conference on Uncertainty in Artificial Intelligence: 153–160. arXiv:1202.3713. Bibcode:2012arXiv1202.3713C.
  13. Scanagatta M, de Campos CP, Corani G, Zaffalon M (2015). "Learning Bayesian Networks with Thousands of Variables". NIPS-15: Advances in Neural Information Processing Systems. Vol. 28. Curran Associates. pp. 1855–1863.
  14. Petitjean F, Webb GI, Nicholson AE (2013). उच्च-आयामी डेटा के लिए स्केलिंग लॉग-रैखिक विश्लेषण (PDF). International Conference on Data Mining. Dallas, TX, USA: IEEE.
  15. M. Scanagatta, G. Corani, C. P. de Campos, and M. Zaffalon. Learning Treewidth-Bounded Bayesian Networks with Thousands of Variables. In NIPS-16: Advances in Neural Information Processing Systems 29, 2016.
  16. 16.0 16.1 Russell & Norvig 2003, p. 496.
  17. 17.0 17.1 Russell & Norvig 2003, p. 499.
  18. Neapolitan RE (2004). बायेसियन नेटवर्क सीखना. Prentice Hall. ISBN 978-0-13-012534-7.
  19. Cooper GF (1990). "The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks" (PDF). Artificial Intelligence. 42 (2–3): 393–405. doi:10.1016/0004-3702(90)90060-d.
  20. Dagum P, Luby M (1993). "Approximating probabilistic inference in Bayesian belief networks is NP-hard". Artificial Intelligence. 60 (1): 141–153. CiteSeerX 10.1.1.333.1586. doi:10.1016/0004-3702(93)90036-b.
  21. D. Roth, On the hardness of approximate reasoning, IJCAI (1993)
  22. D. Roth, On the hardness of approximate reasoning, Artificial Intelligence (1996)
  23. Dagum P, Luby M (1997). "बायेसियन अनुमान के लिए एक इष्टतम सन्निकटन एल्गोरिथम". Artificial Intelligence. 93 (1–2): 1–27. CiteSeerX 10.1.1.36.7946. doi:10.1016/s0004-3702(97)00013-1. Archived from the original on 2017-07-06. Retrieved 2015-12-19.
  24. Hoffman, Matthew D.; Gelman, Andrew (2011). "The No-U-Turn Sampler: Adaptively Setting Path Lengths in Hamiltonian Monte Carlo". arXiv:1111.4246.
  25. Pearl J (1985). Bayesian Networks: A Model of Self-Activated Memory for Evidential Reasoning (UCLA Technical Report CSD-850017). Proceedings of the 7th Conference of the Cognitive Science Society, University of California, Irvine, CA. pp. 329–334. Retrieved 2009-05-01.
  26. Bayes T, Price (1763). "संभावना के सिद्धांत में एक समस्या को हल करने की दिशा में एक निबंध". Philosophical Transactions of the Royal Society. 53: 370–418. doi:10.1098/rstl.1763.0053.
  27. Pearl J (1988-09-15). इंटेलिजेंट सिस्टम में संभाव्य तर्क. San Francisco CA: Morgan Kaufmann. p. 1988. ISBN 978-1-55860-479-7.
  28. Neapolitan RE (1989). Probabilistic reasoning in expert systems: theory and algorithms. Wiley. ISBN 978-0-471-61840-9.


संदर्भ

An earlier version appears as , Microsoft Research, March 1, 1995. The paper is about both parameter and structure learning in Bayesian networks.


अग्रिम पठन

बाहरी संबंध