2016-10-09 12 views
6

मैं समझने की कोशिश कर रहा हूं कि मूर्ख बेयस क्लासिफायर बेवकूफ धारणा के बिना एक ही विचार की तुलना में सुविधाओं की संख्या के साथ रैखिक रूप से स्केलेबल क्यों है। मैं इसके बारे में how the classifier works और what's so "naive" समझता हूं। मैं अस्पष्ट हूं कि क्यों बेवकूफ धारणा हमें रैखिक स्केलिंग देती है, जबकि उस धारणा को उठाना घातीय है। मैं एक उदाहरण के चलने की तलाश में हूं जो रैखिक जटिलता के साथ "बेवकूफ" सेटिंग के तहत एल्गोरिदम दिखाता है, और उसी धारणा के बिना एक ही उदाहरण जो घातीय जटिलता का प्रदर्शन करेगा।बेवकूफ धारणा के बिना बेवकूफ बेयस

उत्तर

8

समस्या यहां मात्रा

P(x1, x2, x3, ..., xn | y) 

जो आप अनुमान लगाने के लिए निम्नलिखित में निहित है। जब आप "naiveness" (सुविधा स्वतंत्रता) मान लें कि आपके

P(x1, x2, x3, ..., xn | y) = P(x1 | y)P(x2 | y) ... P(xn | y) 

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

अब, बिना भलाई के आपके पास कोई अपघटन नहीं है। इस प्रकार आप आप vi से प्रत्येक संभावित मान के लिए प्रपत्र

P(x1=v1, x2=v2, ..., xn=vn | y) 

के सभी संभावनाओं का ट्रैक रखने के लिए है। सबसे सरल मामले में, vi केवल "सत्य" या "झूठा" (घटना हुई या नहीं) है, और यह आपको 2^n अनुमानों को अनुमानित करने के लिए पहले से ही n बूलियन चर के एक श्रृंखला के लिए "सत्य" और "झूठी" के प्रत्येक संभावित असाइनमेंट देता है) । नतीजतन आप एल्गोरिदम जटिलता की घातीय वृद्धि है। हालांकि, यहां सबसे बड़ा मुद्दा आमतौर पर कम्प्यूटेशनल नहीं है - बल्कि डेटा की कमी है। चूंकि 2^n संभावनाएं अनुमान लगाने के लिए हैं कि 2^n डेटा पॉइंट्स किसी भी सभी संभावित घटनाओं के अनुमान के लिए हैं। वास्तविक जीवन में आपको कभी भी 10,000,000,000,000 अंकों के डेटासेट का सामना नहीं करना पड़ेगा ... और इस तरह के दृष्टिकोण के साथ 40 विशेषताओं के लिए यह कई आवश्यक (अद्वितीय!) अंक हैं।

+0

भावना बनती है, लेकिन कारण है कि हम 2^n व्यक्ति संभावनाओं का आकलन करने की समस्या के साथ फंस रहे हैं? हमें कुछ रैखिक (या यहां तक ​​कि परिमित) पैरामीटर की संख्या के साथ संयुक्त वितरण पर एक मॉडल डालने से रोक रहा है (उदाहरण के लिए, उदाहरण के लिए, एक प्रतिगमन समस्या के संभावित दृष्टिकोण में)? – dkv

+1

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

+0

@lejlot मैं अपनी समझ को स्पष्ट करना चाहता हूं: मान लें कि मेरे पास एक प्रशिक्षण डेटासेट 'x_1 = 1, y_1 = 0, z = 1',' x_2 = 0, y_2 = 0, z = 1' तो इसका अर्थ है 'पी (z = 1 | x = 1, y = 0) = 1/2' और यदि मेरा टेस्ट डेटा 'x_3 = 0 है, y_3 = 1' , इसका मतलब है 'पी (जेड = 1 | एक्स = 0, वाई = 1) = 0'? –

2

कैंडी चयन

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

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

हर साल, दादी प्रत्येक बच्चे को कैंडी पेश करती। दादी के पास दस अलग-अलग प्रकार की कैंडीज़ से भरा एक बड़ा बॉक्स था।वह बच्चों में से प्रत्येक को एक कैंडी देगी, क्योंकि वह अपने दांत खराब नहीं करना चाहती थी। लेकिन, जैसे ही वह बच्चों से बहुत प्यार करती थी, उसने यह तय करने के लिए बड़े प्रयास किए कि कौन सी कैंडी उस बच्चे को पेश करे, जैसे कि वह अपनी कुल खुशी को अधिकतम करेगी (अधिकतम संभावना अनुमान, जैसा कि वह इसे कॉल करेगी)।

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

10 बच्चों में से प्रत्येक के लिए 10 बच्चों में से प्रत्येक के लिए अलग-अलग प्राथमिकताएं थीं।

इसके अलावा, उनकी प्राथमिकताएं बड़े पैमाने पर बाह्य कारकों पर निर्भर थीं जो अज्ञात थीं (छुपे हुए चर) दादी को।

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

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

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

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

उस वर्ष, बच्चे आखिरकार एक बार में सबसे ज्यादा खुश थे, और दादी को उनकी 100 वीं जन्मदिन की पार्टी में बहुत अच्छा समय था। उस दिन के कुछ महीनों बाद, दादी उसके चेहरे पर एक मुस्कुराहट के साथ निधन हो गईं और शेल्डन रॉस की एक प्रति उसके हाथ में गिर गई।

Takeaway: सांख्यिकीय मॉडलिंग में, परस्पर निर्भर यादृच्छिक परिवर्तनीय होने यह वास्तव में कठिन प्रत्येक चर है कि सेट की संचयी संभावना अधिकतम के लिए मूल्यों के इष्टतम काम पता लगाने के लिए बनाता है।

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

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

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

ऐसा क्यों है "भोली" क्या है?

बेवकूफ बेयस क्लासिफायरफायर मानता है कि एक्स | वाईएक्स | वाई आमतौर पर एक्सएक्स के किसी भी घटक के बीच शून्य संवहनी के साथ वितरित किया जाता है। चूंकि यह किसी भी वास्तविक समस्या के लिए पूरी तरह से असंभव धारणा है, इसलिए हम इसे बेवकूफ मानते हैं।

अनुभवहीन Bayes निम्नलिखित धारणा कर देगा:

अचार की तरह आप हैं, और आइसक्रीम की तरह आप, अनुभवहीन Bayes स्वतंत्रता मान लेते हैं और आप एक अचार आइसक्रीम देने के लिए और लगता है कि आप इसे पसंद करेंगे होगा।

कौन सा है बिल्कुल सच नहीं हो सकता।

एक गणितीय उदाहरण के लिए देखें: https://www.analyticsvidhya.com/blog/2015/09/naive-bayes-explained/

संबंधित मुद्दे