जंक्शन ट्री एल्गोरिथम
जंक्शन ट्री एल्गोरिथम (जिसे 'क्लिक ट्री' के रूप में भी जाना जाता है) सामान्य ग्राफ (असतत गणित) में सीमांत वितरण निकालने के लिए यंत्र अधिगम में उपयोग की जाने वाली विधि है। संक्षेप में, यह जंक्शन ट्री कहे जाने वाले संशोधित ग्राफ पर बिलीफ प्रचार करने पर जोर देता है। ग्राफ़ को ट्री कहा जाता है क्योंकि यह आँकड़े के विभिन्न वर्गों में विभाजित होता है; कोणबिंदु (ग्राफ़ सिद्धान्त) चर राशि की शाखाएँ हैं।[1] मूल आधार चक्र (ग्राफ सिद्धांत) को एकल नोड्स में गुच्छित करके समाप्त करना है। आँकड़े के बड़े ढांचे में एक ही समय में प्रश्नों के कई व्यापक वर्गों को संकलित किया जा सकता है।[1]विशिष्ट आवश्यकताओं को पूरा करने के लिए और गणना करने की आवश्यकता के लिए अलग-अलग कलन विधि हैं। बायेसियन नेटवर्क आँकड़े में नए योजनाएँ को इकट्ठा करता है और प्रदान की गई नई जानकारी के आधार पर इसकी गणना करता है।[2]
जंक्शन ट्री एल्गोरिथम
ह्यूगिन एल्गोरिथम
- यदि ग्राफ निर्देशित है तो फिर इसे निर्देशित करने के लिए इसे नैतिक ग्राफ बनाएं।
- सबूत समक्ष करते हैं।
- इसे कॉर्डल बनाने के लिए ग्राफ़ को त्रिकोणित करते हैं।
- त्रिकोणीय ग्राफ से जंक्शन ट्री का निर्माण करते हैं (हम जंक्शन ट्री के शीर्ष को सुपरनोड (सर्किट) कहते है।
- जंक्शन ट्री के साथ संभावनाओं का प्रचार करते हैं (बिलीफ प्रसार के माध्यम से)
ध्यान दें कि यह अंतिम चरण बड़े ट्रीविड्थ के ग्राफ़ के लिए अक्षम है। सुपरनोड्स के बीच पारित होने वाले संदेशों की गणना करने में दोनों सुपरनोड्स में चर राशि पर सटीक सीमांतीकरण करना सम्मिलित है। ट्रेविड्थ k वाले ग्राफ़ के लिए इस एल्गोरिथम को निष्पादित करने से कम से कम एक संगणना होगी जो k में घातीय समय लेती है। यह बिलीफ प्रसार एल्गोरिथम है।[3] शफर-शेनॉय की तुलना में समाधान खोजने के लिए ह्यूगिन एल्गोरिथम कम संगणना लेता है।
शेफर-शेनॉय एल्गोरिथम
- पुनरावर्ती रूप से गणना की गई[3]*
- शाफर-शेनॉय एल्गोरिद्म के एकाधिक पुनरावर्तन के परिणामस्वरूप हगिन एल्गोरिथम प्राप्त होता है[4]
- कंप्यूटर गुच्छित समीकरण द्वारा पाया गया[4]*
- सेपरेट्रिक्स (गणित) क्षमता संग्रहीत नहीं है[5]
शेफर-शेनॉय एल्गोरिथम जंक्शन ट्री का योग-उत्पाद एल्गोरिथ्म है।[6] इसका उपयोग इसलिए किया जाता है क्योंकि यह हगिन एल्गोरिथम की तुलना में अधिक कुशलता से प्रोग्राम और परिप्रश्न चलाता है। एल्गोरिथम बिलीफ फंक्शन्स के लिए शर्तों के लिए गणना संभव बनाता है।[7] सीमित संगणना करने के लिए संयुक्त वितरण की आवश्यकता होती है।[7]
अंतर्निहित सिद्धांत
पहला चरण केवल बायेसियन नेटवर्क से संबंधित है, और निर्देशित ग्राफ़ को अप्रत्यक्ष में बदलने की प्रक्रिया है। हम ऐसा इसलिए करते हैं क्योंकि यह निर्देश की परवाह किए बिना एल्गोरिथम की सार्वभौमिक प्रयोज्यता की अनुमति देता है।
दूसरा चरण चरों को उनके देखे गए मान पर सेट कर रहा है। यह सामान्यतः तब आवश्यक होता है जब हम सशर्त संभावनाओं की गणना करना चाहते हैं, इसलिए हम उन यादृच्छिक चरों के मान को ठीक करते हैं जिन पर हम शर्त करते हैं। उन चरों को उनके विशेष मान से कीलक कहा जाता है।
तीसरा चरण यह सुनिश्चित करना है कि ग्राफ़ को कॉर्डल ग्राफ़ बनाया जाए यदि वे पहले से ही कॉर्डल नहीं हैं। यह एल्गोरिदम का पहला आवश्यक कदम है। यह निम्नलिखित प्रमेय का उपयोग करता है:[8]
प्रमेय: ग्राफ़ (असतत गणित) ग्राफ़, G के लिए, निम्नलिखित गुण समतुल्य हैं:
- ग्राफ G त्रिकोणीय है।
- G के क्लिक ग्राफ में जंक्शन ट्री है।
- G के लिए विलोपन क्रम है जो किसी भी अतिरिक्त किनारों की ओर नहीं ले जाता है।
इस प्रकार, त्रिकोणासन (ज्यामिति) द्वारा ग्राफ, हम सुनिश्चित करते हैं कि संबंधित जंक्शन ट्री सम्मिलित है। ऐसा करने का सामान्य तरीका है, इसके नोड्स के लिए विलोपन क्रम तय करना और फिर चर विलोपन एल्गोरिथम चलाना है। परिवर्तनीय उन्मूलन एल्गोरिथम बताता है कि हर बार अलग परिप्रश्न होने पर एल्गोरिथम को चलाना चाहिए।[1]इसका परिणाम प्रारंभिक ग्राफ में अधिक किनारों को जोड़ना होगा, इस तरह से कि आउटपुट कॉर्डल ग्राफ होता है। सभी कॉर्डल ग्राफ़ में जंक्शन ट्री होता है।[4]अगला कदम जंक्शन ट्री का निर्माण करना है। ऐसा करने के लिए, हम पिछले चरण से ग्राफ़ का उपयोग करते हैं, और इसके संबंधित क्लिक ग्राफ बनाते हैं।[9] अब अगला प्रमेय हमें जंक्शन ट्री खोजने का तरीका देता है:[8]
प्रमेय: त्रिभुजित ग्राफ को देखते हुए, क्लिक ग्राफ के किनारों को उनकी कार्डिनलिटी, |A∩B|, आसन्न क्लिक्स A और B के प्रतिच्छेदन के द्वारा भारित करते हैं। फिर क्लिक ग्राफ का कोई भी अधिकतम भार वाला जंक्शन ट्री है।
इसलिए, जंक्शन ट्री का निर्माण करने के लिए हमें क्लिक ग्राफ से अधिकतम भार वाले ट्री को निकालना होगा। यह कुशलता से किया जा सकता है, उदाहरण के लिए, क्रुस्कल के एल्गोरिथ्म को संशोधित करके किया जा सकता है।
अंतिम चरण प्राप्त जंक्शन ट्री में बिलीफ प्रसार को लागू करना है।[10]
उपयोग: समस्या की संभावनाओं को देखने के लिए जंक्शन ट्री ग्राफ का उपयोग किया जाता है। ट्री की वास्तविक निर्माण के लिए द्विआधारी ट्री बन सकता है।[11] स्वतः कोडन (एनकोडर्स) में विशिष्ट उपयोग पाया जा सकता है, जो बड़े पैमाने पर स्वचालित रूप से ग्राफ और पासिंग नेटवर्क को जोड़ता है।[12]
अनुमान एल्गोरिदम
लूपी बिलीफ प्रसार: जटिल रेखांकन की व्याख्या करने का अलग तरीका है। लूप बिलीफ प्रचार का उपयोग तब किया जाता है जब सटीक समाधानों के अतिरिक्त अनुमानित समाधान की आवश्यकता होती है।[13] यह अनुमानित अनुमान है।[3]
कटसेट कंडीशनिंग: चर के छोटे सेट के साथ प्रयोग किया जाता है। कटसेट कंडीशनिंग सरल ग्राफ़ की अनुमति देता है जो पढ़ने में आसान होते हैं लेकिन सटीक समाधान नहीं होते हैं।[3]
संदर्भ
- ↑ Jump up to: 1.0 1.1 1.2 Paskin, Mark. "ग्राफिकल मॉडल पर एक लघु पाठ्यक्रम" (PDF). Stanford.
- ↑ "अनुमान एल्गोरिथम". www.dfki.de. Retrieved 2018-10-25.
- ↑ Jump up to: 3.0 3.1 3.2 3.3 "Recap on Graphical Models" (PDF).
- ↑ Jump up to: 4.0 4.1 4.2 "एल्गोरिदम" (PDF). Massachusetts Institute of Technology. 2014.
- ↑ Roweis, Sam (2004). "हगिन अनुमान एल्गोरिथम" (PDF). NYU.
- ↑ "अनुमान के लिए एल्गोरिदम" (PDF). Massachusetts Institute of Technology. 2014.
- ↑ Jump up to: 7.0 7.1 Kłopotek, Mieczysław A. (2018-06-06). "Dempsterian-Shaferian Belief Network डेटा से". arXiv:1806.02373 [cs.AI].
- ↑ Jump up to: 8.0 8.1 Wainwright, Martin (31 March 2008). "Graphical models, message-passing algorithms, and variational methods: Part I" (PDF). Berkeley EECS. Retrieved 16 November 2016.
- ↑ "ग्राफ़ पर क्लिक करें". Retrieved 16 November 2016.
- ↑ Barber, David (28 January 2014). "संभाव्य मॉडलिंग और तर्क, जंक्शन ट्री एल्गोरिथम" (PDF). University of Helsinki. Retrieved 16 November 2016.
- ↑ "Fault Diagnosis in an Industrial Process Using Bayesian Networks: Application of the Junction Tree Algorithm - IEEE Conference Publication" (in English). doi:10.1109/CERMA.2009.28. S2CID 6068245.
{{cite journal}}: Cite journal requires|journal=(help) - ↑ Jin, Wengong (Feb 2018). "मॉलिक्यूलर ग्राफ जनरेशन के लिए जंक्शन ट्री वैरिएशनल ऑटोएनकोडर". Cornell University. arXiv:1802.04364. Bibcode:2018arXiv180204364J.
- ↑ CERMA 2009 : proceedings : 2009 Electronics, Robotics and Automotive Mechanics Conference : 22-25 September 2009 : Cuernavaca, Morelos, Mexico. Institute of Electrical and Electronics Engineers. Los Alamitos, Calif.: IEEE Computer Society. 2009. ISBN 9780769537993. OCLC 613519385.
{{cite book}}: CS1 maint: others (link)
- Lauritzen, Steffen L.; Spiegelhalter, David J. (1988). "Local Computations with Probabilities on Graphical Structures and their Application to Expert Systems". Journal of the Royal Statistical Society. Series B (Methodological). 50 (2): 157–224. doi:10.1111/j.2517-6161.1988.tb01721.x. JSTOR 2345762. MR 0964177.
- Dawid, A. P. (1992). "Applications of a general propagation algorithm for probabilistic expert systems". Statistics and Computing. 2 (1): 25–26. doi:10.1007/BF01890546. S2CID 61247712.
- Huang, Cecil; Darwiche, Adnan (1996). "Inference in Belief Networks: A Procedural Guide". International Journal of Approximate Reasoning. 15 (3): 225–263. CiteSeerX 10.1.1.47.3279. doi:10.1016/S0888-613X(96)00069-2.
- Paskin, Mark A. "A Short Course on Graphical Models : 3. The Junction Tree Algorithms" (PDF). Archived from the original on March 19, 2015.
{{cite journal}}: Cite journal requires|journal=(help)CS1 maint: unfit URL (link) - Lepar, V., Shenoy, P. (1998). "A Comparison of Lauritzen-Spiegelhalter, Hugin, and Shenoy-Shafer Architectures for Computing Marginals of Probability Distributions." https://arxiv.org/ftp/arxiv/papers/1301/1301.7394.pdf
