Chow–Liu tree
संभाव्यता सिद्धांत और सांख्यिकी में चौ-लिउ वृक्ष एक संयुक्त संभाव्यता वितरण के दूसरे क्रम के उत्पाद सन्निकटन के निर्माण के लिए एक कुशल विधि है, जिसे पहली बार एक पेपर में चौ-लिउ वृक्ष द्वारा वर्णित किया गया है। इस तरह के अपघटन के लक्ष्य, सामान्य रूप से ऐसे बायेसियन नेटवर्क के साथ, या तो डेटा संपीड़न या अनुमान हो सकते हैं। चाउ-लिउ प्रतिनिधित्व चाउ-लिउ विधि एक संयुक्त संभाव्यता वितरण को दूसरे क्रम के सशर्त और सीमांत वितरण के उत्पाद के रूप में वर्णित करती है। उदाहरण के लिए, छह-आयामी वितरण को अनुमानित किया जा सकता है जहां उत्पाद में प्रत्येक नया शब्द केवल एक नए चर का परिचय देता है, और उत्पाद को प्रथम-क्रम निर्भरता वृक्ष के रूप में दर्शाया जा सकता है, जैसा कि चित्र में दिखाया गया है। चाउ-लिउ एल्गोरिथ्म (नीचे) निर्धारित करता है कि उत्पाद सन्निकटन में किन सशर्त संभावनाओं का उपयोग किया जाना है। सामान्य तौर पर, जब तक कोई तृतीय-क्रम या उच्च-क्रम अंतःक्रिया नहीं होती है, तब तक चाउ-लिउ सन्निकटन वास्तव में एक सन्निकटन है, और मूल वितरण की पूरी संरचना को नहीं पकड़ सकता है। बायेसियन नेटवर्क के रूप में चाउ-लिउ पेड़ का एक आधुनिक विश्लेषण प्रदान करता है। चाउ-लिउ एल्गोरिथ्म चाउ और लियू दिखाते हैं कि उत्पाद सन्निकटन के लिए दूसरे क्रम के शब्दों का चयन कैसे किया जाए ताकि, ऐसे सभी दूसरे क्रम के सन्निकटनों (प्रथम क्रम निर्भरता पेड़) के बीच, निर्मित सन्निकटन में वास्तविक वितरण के लिए न्यूनतम कुलबैक-लीबलर विचलन हो, और इस प्रकार शास्त्रीय सूचना-सैद्धांतिक अर्थ में निकटतम सन्निकटन है। दूसरे क्रम के उत्पाद सन्निकटन और वास्तविक वितरण के बीच कुलबैक-लीबलर विचलन को चर और उसके मूल के बीच पारस्परिक जानकारी के रूप में दिखाया गया है और यह चर समुच्चय की संयुक्त एन्ट्रापी है। चूँकि शब्द और वृक्ष में निर्भरता क्रम से स्वतंत्र हैं, केवल जोड़ीदार पारस्परिक सूचनाओं का योग, सन्निकटन की गुणवत्ता को निर्धारित करता है। इस प्रकार, यदि वृक्ष की प्रत्येक शाखा (किनारे) को उसके शीर्ष पर चरों के बीच पारस्परिक जानकारी के अनुरूप वजन दिया जाता है, तो वह वृक्ष जो लक्ष्य वितरण के लिए इष्टतम द्वितीय-क्रम सन्निकटन प्रदान करता है, केवल अधिकतम वजन वाला वृक्ष है। उपरोक्त समीकरण सन्निकटन में निर्भरताओं की भूमिका पर भी प्रकाश डालता हैः जब कोई निर्भरता मौजूद नहीं होती है, और समीकरण में पहला पद अनुपस्थित होता है, तो हमारे पास केवल प्रथम क्रम के मार्जिन के आधार पर एक सन्निकटन होता है, और सन्निकटन और सही वितरण के बीच की दूरी उन अतिरेकों के कारण होती है जो चर को स्वतंत्र माने जाने पर गणना नहीं की जाती है। जैसे-जैसे हम दूसरे क्रम की निर्भरताओं को निर्दिष्ट करते हैं, हम उस संरचना में से कुछ को पकड़ना शुरू करते हैं और दो वितरणों के बीच की दूरी को कम करते हैं। चाउ और लियू इष्टतम वृक्ष के निर्माण के लिए एक सरल एल्गोरिथ्म प्रदान करते हैं; प्रक्रिया के प्रत्येक चरण में एल्गोरिथ्म केवल वृक्ष में अधिकतम पारस्परिक सूचना जोड़ी जोड़ता है। पूर्ण विवरण के लिए मूल पेपर देखें। विरल डेटा के सामान्य मामले के लिए एक अधिक कुशल वृक्ष निर्माण एल्गोरिदम को रेखांकित किया गया था। चाउ और वैगनर ने बाद के एक शोध पत्र में साबित किया कि चाउ-लिउ पेड़ का सीखना लगातार दिए गए नमूनों (या टिप्पणियों) के अनुरूप है। एक वृक्ष-संरचित वितरण से। दूसरे शब्दों में, एक गलत वृक्ष को सीखने की संभावना शून्य हो जाती है क्योंकि नमूनों की संख्या अनंत हो जाती है। प्रमाण में मुख्य विचार जोड़ीदार सीमांत वितरण में पारस्परिक जानकारी की निरंतरता है। हाल ही में, त्रुटि संभाव्यता के अभिसरण की घातीय दर प्रदान की गई थी। चाउ-लिउ पेड़ों पर भिन्नताएँ स्पष्ट समस्या जो तब होती है जब वास्तविक वितरण वास्तव में एक द्वितीय-क्रम निर्भरता पेड़ नहीं होता है, फिर भी कुछ मामलों में एक "बड़े-नोड" चाउ-लिउ पेड़ प्राप्त करने के लिए चर के घने जुड़े उपसमुच्चय को फ्यूज या एक साथ जोड़कर, या लालची अधिकतम शाखा वजन चयन के विचार को गैर-पेड़ (कई मूल) संरचनाओं तक विस्तारित करके संबोधित किया जा सकता है। (परिवर्तनशील प्रतिस्थापन और निर्माण की समान तकनीकें बेयस नेटवर्क साहित्य में आम हैं, उदाहरण के लिए, लूप से निपटने के लिए। देखें।) चाउ-लिउ वृक्ष के सामान्यीकरण तथाकथित टी-चेरी जंक्शन वृक्ष हैं। यह साबित होता है कि टी-चेरी जंक्शन ट्री एक असतत बहुभिन्नरूपी संभाव्यता वितरण के लिए बेहतर या कम से कम उतना ही अच्छा अनुमान प्रदान करते हैं जितना कि चाउ-लिउ ट्री देता है। थर्ड ऑर्डर टी-चेरी जंक्शन ट्री के लिए देखें, kth-ऑर्डर टी-चेरी जंक्शन ट्री के लिए देखें। दूसरे क्रम का टी-चेरी जंक्शन पेड़ वास्तव में चाउ-लिउ पेड़ है। बायेसियन नेटवर्क नॉलेज रिप्रेजेंटेशन नोट्स रेफेरेंस भी देखें। .. .. .. .. .. .. ज्ञान प्रतिनिधित्व