संभाव्य मॉडल: चक्र नियंत्रण और परिवर्तनशील सन्निकटन

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

पिछली श्रृंखला का सारांश

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


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

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

आपको याद दिला दूं कि इस चित्र में दिखाया गया मॉडल इस तरह से लंबाई N का एक नया दस्तावेज़ बनाता है:

• वेक्टर चुनें - दस्तावेज़ में प्रत्येक विषय की "अभिव्यक्ति की डिग्री" का वेक्टर;
• एन शब्दों में से प्रत्येक के लिए w :
  
  • एक विषय चुनें वितरण द्वारा ;
  • एक शब्द चुनें with में दी गई संभावनाओं के साथ।

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


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

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

लूप को शीर्ष पर बदलें

कभी-कभी एक चक्र को दर्द रहित रूप से एक वर्टेक्स द्वारा प्रतिस्थापित किया जा सकता है, जिससे संबंधित फ़ंक्शन के लिए केवल चर की संख्या बढ़ जाती है। उदाहरण के लिए, आप कारक ग्राफ में कहीं एक त्रिकोण में आए:


जैसा कि हम पहले से ही जानते हैं, इसका मतलब है कि यह अपघटन में होता है


ज्यादातर मामलों में, ऐसे त्रिकोण को आसानी से एक नए फ़ंक्शन के साथ बदल दिया जा सकता है।

और लूप चला जाएगा:


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

मैसेजिंग एल्गोरिदम

पहला व्यावहारिक रूप से महत्वपूर्ण तरीका है जिसका उपयोग किया जा सकता है यदि संदेश हस्तांतरण एल्गोरिथ्म लागू नहीं है, तो निश्चित रूप से, संदेश स्थानांतरण एल्गोरिथ्म। :) बेशक, यह चक्र के लिए, औपचारिक रूप से बोलना, काम नहीं करता है - शुरू करने के लिए कहीं नहीं है, कोई पत्तियां नहीं हैं। इसलिए, वे मैसेजिंग एल्गोरिथ्म के एक संशोधन का उपयोग करते हैं जिसे लोपी विश्वास प्रचार के रूप में जाना जाता है:

• प्रत्येक शीर्ष-चर को प्रत्येक शीर्ष-फ़ंक्शन से भेजें एक संदेश 1 के बराबर पहचान योग्य रूप से कार्य करता है;
• सामान्य मैसेजिंग एल्गोरिथ्म का उपयोग करना जारी रखें।

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

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

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

भिन्नताएं

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

यह समझने के लिए कि सामान्य रूप से यह सब क्या है, क्लासिक सरल उदाहरण पर विचार करें - वैचारिक रूप से कार्य के रूप में कार्य की कल्पना करें:

(यह समानता केवल λ - चेक के संबंध में व्युत्पन्न लेने से सत्यापित करना आसान है!)।

अब यह रैखिक कार्यों का एक परिवार है, जिनमें से प्रत्येक लघुगणक पर एक ऊपरी बाध्य देता है (दूसरे शब्दों में, लघुगणक इस परिवार का लिफाफा है), और अगर हम λ अच्छी तरह से चुन सकते हैं, तो हमें हमारे लिए ब्याज के क्षेत्र में अच्छे अनुमान मिलते हैं। यह कुछ इस तरह दिखता है (एक लेख से चित्र ( जॉर्डन एट अल।, 1999 ]):


यहाँ यह बहुत महत्वपूर्ण था कि लघुगणक एक अवतल कार्य है, अन्यथा ऐसा नहीं होता। लेकिन अक्सर आप उभार के गुणों को एक अलग तरीके से प्राप्त कर सकते हैं। दूसरा उदाहरण एक लॉजिस्टिक फ़ंक्शन है:

यह उत्तल नहीं है और अवतल नहीं है, लेकिन यह लॉग-अवतल है, अर्थात

एक्स का अवतल कार्य है। इसलिए, जी ( एक्स ) के लिए, कोई रैखिक अनुमान पा सकता है:

जहाँ , यानी। साधारण एन्ट्रापी। फिर से, व्यायाम करें - इसे देखें (आज कुछ ज्यादा ही व्यायाम है, लेकिन क्या करें)। तब हम घातांक ले जा सकते हैं (यह नीरस है, अर्थात, असमानता बनी रहेगी):

विशेष रूप से, हमें ऊपरी सीमा का एक परिवार मिलता है:

और हम जितना बेहतर λ का चयन करेंगे, उतना ही बेहतर मूल्यांकन करेंगे। रेखांकन, यह इस तरह दिखता है (एक लेख से चित्र ( जॉर्डन एट अल।, 1999 ]):


ग्राफिक मॉडल का इससे क्या लेना-देना है? लेकिन इसके साथ। मैं आपको याद दिलाता हूं कि हम हाशिए की समस्या से निपट रहे हैं: इस मॉडल का उपयोग करते हुए और संभवतः, कुछ चर के मूल्यों को, सीमांत संभावना वितरण का पता लगाएं

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

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

यदि आप वह सब कुछ देखते हैं जो थोड़ा अलग तरफ होता है, तो इस प्रकार के रूपांतरों का सार प्रस्तुत किया जा सकता है:

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

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

इसलिए, उदाहरण के लिए, एलडीए मॉडल के लिए विकसित परिवर्तनशील सन्निकटन योजना में, ऊपर दिखाए गए आलेख (आलेख के पहले खंड में) से चित्रमय मॉडल इस एक में बदल जाता है (चित्र [ Blei, Jordan, Ng, 2003 ] से चित्र):


जैसा कि आप देख सकते हैं, कोई चक्र नहीं बचा है, और सीमांतकरण समस्या का एक अनुमानित समाधान प्राप्त हुआ है, जो भिन्नता मानकों the और φ के संबंध में अनुकूलन समस्या को कम करता है।

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

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