संभाव्य मॉडल: लघुकोष्ठक की कला

एक लंबे ब्रेक के बाद, हम ग्राफिकल प्रोबेबिलिस्टिक मॉडल ( भाग 1 , भाग 2 ) पर चक्र जारी रखते हैं। आज, हम अंततः कार्य परिभाषाओं से एल्गोरिदम तक आगे बढ़ेंगे; हम सबसे सरल लेकिन अक्सर उपयोगी कारक-ग्राफ़ आउटपुट एल्गोरिदम - संदेश पासिंग एल्गोरिदम के बारे में बात करेंगे। या, जैसा कि यह कहा जा सकता है, कोष्ठक के सही स्थान के लिए एक एल्गोरिथ्म।


सेर्गेई-लेसियुक द्वारा

उदाहरण

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

यहां, औपचारिक रूप से, चार शब्द हैं, तीन कारकों में से प्रत्येक, केवल तीन जोड़ और आठ गुणा।

आइए त्वरित बुद्धिमत्ता के चमत्कार दिखाएं और ध्यान दें कि दो एकल योगों के उत्पाद में डबल योग विघटित होता है:

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

"न्यूटन के द्विपद के बारे में सोचो!" पाठक मुझे बताएंगे; और वे सही होंगे, यह वास्तव में न्यूटन के बिन के समान है। और चौकस पाठकों को भी आश्चर्य होगा कि वास्तव में एक खेल की आवश्यकता क्यों थी - वास्तव में, इस उदाहरण में यह स्पष्ट रूप से शानदार दिखता है।

आइए उसी उदाहरण को सामान्य बनाने का प्रयास करें - अब कुछ अज्ञात फ़ंक्शन को गुणन के बजाय हमारे चर के साथ होने दें:

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

इंटरमीडिएट मामले में चाल चलेगी - हम अभी भी विचार में एक सामान्य कार्य छोड़ देंगे, लेकिन अब हम यह मानेंगे कि यह x और y के कार्य और y और z के कार्य में अंत में विघटित होता है (अंत में, y होगा ):

प्रश्न के इस सूत्रीकरण के साथ, हम दो छोटे लोगों के उत्पाद में उसी तरह से एक बड़ी राशि को विघटित कर सकते हैं:

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

इस उदाहरण का नैतिक क्या है? यदि हमें किसी बड़े कार्य को संक्षेप में प्रस्तुत करने की आवश्यकता है, और यह छोटे कार्यों के उत्पाद में विघटित हो जाता है, तो संभव है कि हम कोष्ठक के उत्पाद में एक सफल विस्तार पा सकें ...

संभाव्य मॉडल के लिए

... लेकिन यह एक चित्रमय संभाव्य मॉडल पर अनुमान की स्थिति है! उन चरों के बीच सुसंगत संबंध को याद करें, जिनकी हमने पहली श्रृंखला में चर्चा की थी :

एक संभावित दृष्टिकोण से, इसका मतलब है कि संयुक्त वितरण के रूप में विघटित है


और इसका मतलब यह है कि तीन चर x , y और z का कार्य x और y के फलन और y और z के फलन में विघटित होता है, बिल्कुल हमारे भोले उदाहरण की तरह। और यह सम्मिश्रण हाशिए की समस्या से मेल खाता है: इस मॉडल के अनुसार और, संभवतः, कुछ चर के मान, सीमांत संभाव्यता वितरण का पता लगाते हैं

और अब हम समझते हैं कि इस अभिव्यक्ति को बहुत सरल बनाया जा सकता है

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

कारक रेखांकन और श्रृंखला के रूप में ग्राफ

इस सब की सुंदरता यह है कि इस तरह के तर्कों को हर बार नए सिरे से आविष्कार करने की आवश्यकता नहीं है, लेकिन सामान्यीकरण किया जा सकता है। सबसे सीधा सामान्यीकरण एक सीरियल कनेक्शन द्वारा जुड़ी कई घटनाओं की एक श्रृंखला है:


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


चलिए अब इसे स्पष्ट रूप से आकर्षित करते हैं:


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

अब x _{k के} संबंध में अपनी चाल को हाशिए की समस्या पर लागू करते हैं। पहले, हम पहले राशि में लाते हैं, फिर दूसरा, फिर तीसरा, और इसी तरह के ऊपर; परिणाम शिखर के बाईं ओर का अधिक कॉम्पैक्ट प्रतिनिधित्व है, जो दाएं पक्ष के साथ प्रतिच्छेद नहीं करता है (लंबे सूत्र के लिए खेद है, लेकिन यह शब्दों की तुलना में बहुत अधिक दृश्य है):

आप सही पक्ष के साथ भी ऐसा कर सकते हैं, और परिणाम है


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

सामान्य मामला

मैसेजिंग एल्गोरिदम का सामान्य मामला वह मामला है जब कारक ग्राफ एक पेड़ है (यानी, इसका कोई चक्र नहीं है)। इस मामले में, हम यह साबित कर सकते हैं कि कुछ शीर्ष के संबंध में हाशिए पर रखने के लिए यह पर्याप्त है:

• इस चोटी को एक पेड़ की अस्थायी जड़ के रूप में मानते हैं;
• पत्तियों से जड़ की ओर संदेश भेजें; प्रत्येक संदेश ठीक एक चर का एक कार्य है - एक जो उस किनारे के निकट है जिसके साथ यह संदेश जाता है;
• मूल में आए सभी संदेशों को गुणा करें।

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


चर नोड प्रसारित करने वाला संदेश बस प्राप्त होने वाले सभी संदेशों का उत्पाद है (एक शीट, एक समान इकाई के मामले में):

और फ़ंक्शन नोड के संदेश को पुनः प्राप्त करने के लिए, आंशिक रूप से हाशिए पर ले जाने के लिए आवश्यक है; यदि कार्य पहले से ही संदेश मिले हैं सभी चर से , यह चर x पर संदेश भेज सकता है

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

निष्कर्ष और अगली श्रृंखला की घोषणा

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

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