द डरिकलेट प्रक्रिया चीनी रेस्तरां प्रक्रिया और अन्य अभ्यावेदन

• 20 मई 2014
• वासिलिस व्र्यनोटिस
• । कोई टिप्पणी नहीं

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

अद्यतन: डाटंबॉक्स मशीन लर्निंग फ्रेमवर्क अब खुला-स्रोत और मुफ्त है डाउनलोड। Java में Dirichlet Process Mixture मॉडल के कार्यान्वयन को देखने के लिए पैकेज com.datumbox.framework.machinelearning.clustering देखें।

भले ही हमारा लक्ष्य एक मॉडल का निर्माण करना है, जो डेटासेट पर क्लस्टरिंग करने में सक्षम है, इससे पहले हमें डिरिचलेट प्रक्रियाओं के बारे में चर्चा करनी चाहिए। हम सख्त गणितीय परिभाषा और डीपी की अधिक सहज व्याख्या दोनों प्रदान करेंगे और हम प्रक्रिया के निर्माण के तरीकों पर चर्चा करेंगे। उन निर्माणों / अभ्यावेदन को "वास्तविक जीवन" में डिरिचलेट प्रक्रिया की घटनाओं को खोजने के तरीके के रूप में देखा जा सकता है।

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

1. डिरिचलेट प्रक्रिया की परिभाषा

एक is स्थान पर एक डिरिचलेट प्रक्रिया एक स्टोकेस्टिक प्रक्रिया है। यह "अंतरिक्ष पर संभावना वितरण" और एक पर अधिक संभावना वितरण है इससे आकर्षित एक असतत वितरण है। अधिक औपचारिक रूप से एक डिरिचलेट वितरण संभाव्यता उपायों पर एक वितरण है। ए संभाव्यता माप अंतरिक्ष के सबसेट का एक कार्य है Θ [0,1]। G एक DP है जिसे यादृच्छिक संभाव्यता माप वितरित किया जाता है, जिसे इस रूप में दर्शाया जाता है , यदि किसी विभाजन के लिए (ए₁,…ए_n) अंतरिक्ष की of हमारे पास वह है .

चित्र 1:: नीट विभाजन पर मार्जिन डिस्ट्रीलेट वितरित किए जाते हैं।

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

एक सरल और अधिक सहज तरीका एक Dirichlet प्रक्रिया को समझाने के लिए निम्नलिखित है। मान लीजिए कि हमारे पास एक अंतरिक्ष a है जिसे किसी भी परिमित तरीके से विभाजित किया जा सकता है (ए₁,…,ए_n) और एक संभाव्यता वितरण G जो उन्हें संभाव्यता प्रदान करता है। जी Θ पर एक विशिष्ट संभावना वितरण है, लेकिन कई अन्य हैं। Exactly मॉडल पर डिरिचलेट प्रक्रिया बिल्कुल यही है; यह अंतरिक्ष पर सभी संभावित संभाव्यता वितरण पर एक वितरण है all। डिरिचलेट प्रक्रिया को जी के साथ मानकीकृत किया जाता है₀ आधार समारोह और α एकाग्रता पैरामीटर। हम कह सकते हैं कि G को डीपी के अनुसार पैरामीटर α और G के साथ वितरित किया गया है₀ यदि संभावनाओं का संयुक्त वितरण जो G itions के विभाजनों को असाइन करता है, तो डिरिचलेट वितरण का अनुसरण करता है। वैकल्पिक रूप से हम यह कह सकते हैं कि G Θ के किसी भी परिमित विभाजन के लिए G जिन संभावनाओं को असाइन करता है, वे डिरिचलेट डिस्ट्रीब्यूशन का अनुसरण करते हैं।

चित्र 2: डिरिचलेट प्रक्रिया का चित्रमय मॉडल

अंत में ऊपर हम देख सकते हैं डीपी का ग्राफिकल मॉडल। हमें ध्यान देना चाहिए कि α एक अदिश हाइपरपरमीटर, G है₀ डीपी का आधार वितरण है, जी डीपी से नमूना किए गए from पैरामीटर स्पेस पर एक यादृच्छिक वितरण जो मापदंडों और DP को संभाव्यता प्रदान करता है।_i एक पैरामीटर वेक्टर है जो G वितरण से लिया गया है और यह is स्पेस का एक तत्व है।

2. पोस्टीरियर डिरिचलेट प्रक्रियाएं

बाद के डिरिचलेट प्रक्रियाओं पर चर्चा की गई फरग्यूसन। हम एक डिरिचलेट प्रक्रिया से एक यादृच्छिक संभावना माप G खींचकर शुरू करते हैं, । चूंकि G Θ से अधिक संभावना वितरण है, इसलिए हम इस वितरण से नमूना भी ले सकते हैं और स्वतंत्र रूप से वितरित किए गए नमूने a आकर्षित कर सकते हैं₁,…, Θ_n ~ जी चूंकि एक डिरिचलेट प्रक्रिया से ड्रॉ असतत वितरण हैं, हम प्रतिनिधित्व कर सकते हैं जहां के लिए एक छोटी संकेतन है एक डेल्टा फंक्शन है जो 1 इफ़ेक्ट लेता है और 0 अन्यत्र। इसका एक दिलचस्प प्रभाव यह है कि चूंकि जी को इस तरह से परिभाषित किया गया है, इसलिए अलग-अलग नमूनों की समान मूल्य होने की सकारात्मक संभावना है । जैसा कि हम बाद में देखेंगे, यह एक क्लस्टरिंग प्रभाव बनाता है जिसका उपयोग डेटासेट पर क्लस्टर विश्लेषण करने के लिए किया जा सकता है।

उपरोक्त परिभाषाओं और टिप्पणियों का उपयोग करके हम नमूने above दिए गए डिरिक्लेट प्रक्रिया के पीछे के अनुमान का अनुमान लगाना चाहते हैं। फिर भी हम जानते हैं कि और बेयर्स रूल्स और कंजुगेसी का उपयोग ड्यूरिचलेट और मल्टीमोनियल के बीच हमारे पास है और .

समीकरण 1: पोस्टीरियर डिरिचलेट प्रक्रिया

यह संपत्ति बहुत महत्वपूर्ण है और इसका उपयोग विभिन्न डीपी अभ्यावेदन द्वारा किया जाता है।

3. डिरिचलेट प्रक्रिया प्रतिनिधित्व

पिछले खंडों में हमने डिरिचलेट प्रक्रिया को परिभाषित किया और इसके सैद्धांतिक मॉडल को प्रस्तुत किया। एक महत्वपूर्ण सवाल जिसका हमें जवाब देना चाहिए कि हम कैसे जानते हैं कि ऐसी कोई वस्तु मौजूद है और हम कैसे कर सकते हैं निर्माण और प्रतिनिधित्व करते हैं एक डिरिचलेट प्रक्रिया।

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

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

3.1 ब्लैकवेल-मैकक्वीन कलश योजना

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

यह योजना a का एक क्रम उत्पन्न करती है₁, θ₂,… साथ में सशर्त संभावनाएं । इस योजना में हम मानते हैं कि जी₀ रंगों और प्रत्येक and पर एक वितरण है_n उस रंग का प्रतिनिधित्व करता है जिसे कलश में रखा जाता है। कलन विधि इस प्रकार है:

· हम एक खाली कलश के साथ शुरू करते हैं।

· आनुपातिक संभावना के साथ α हम चित्र बनाते हैं और हम कलश में इस रंग की एक गेंद जोड़ते हैं।

· N-1 के लिए आनुपातिकता के साथ हम कलश से एक यादृच्छिक गेंद खींचते हैं, हम इसके रंग का निरीक्षण करते हैं, हम इसे वापस कलश में रख देते हैं और हम कलश में उसी रंग की एक अतिरिक्त गेंद जोड़ते हैं।

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

3.2 स्टिक-ब्रेकिंग निर्माण

स्टिक-ब्रेकिंग कंस्ट्रक्शन एक वैकल्पिक तरीका है जो एक डिरिचलेट प्रक्रिया का प्रतिनिधित्व करता है जिसे इसके द्वारा प्रस्तुत किया गया था सेथुरमन। यह एक रचनात्मक तरीका है वितरण और उपयोग करता है सादृश्य का पालन करना: हम मानते हैं कि हमारे पास लंबाई 1 है, हम इसे स्थिति β पर तोड़ते हैं₁ और हम π प्रदान करते हैं₁ उस छड़ी के हिस्से की लंबाई के बराबर जिसे हमने तोड़ा था। हम same प्राप्त करने के लिए उसी प्रक्रिया को दोहराते हैं₂, पी₃,… आदि; इस योजना को परिभाषित करने के तरीके के कारण हम इसे अनंत बार कर सकते हैं।

उपरोक्त π के आधार पर_k के रूप में मॉडलिंग की जा सकती है , जहां पिछली योजनाओं की तरह θ को आधार वितरण द्वारा सीधे नमूना लिया जाता है । नतीजतन जी वितरण को ed के साथ भारित डेल्टा कार्यों के योग के रूप में लिखा जा सकता है_k सम्भावनाएँ जो के बराबर है । इस प्रकार स्टिक-ब्रेकिंग निर्माण हमें एक सरल और सहज तरीके से एक डिरिचलेट प्रक्रिया का निर्माण करने के लिए देता है।

3.3 चीनी रेस्तरां प्रक्रिया

चीनी रेस्तरां प्रक्रिया, जिसे द्वारा पेश किया गया था Aldous, एक डिरिचलेट प्रक्रिया का प्रतिनिधित्व करने का एक और प्रभावी तरीका है और इसे सीधे ब्लैकवेल-मैकक्वीन कलश योजना से जोड़ा जा सकता है। इस योजना का उपयोग करता है सादृश्य का पालन करना: हम मानते हैं कि एक चीनी रेस्तरां है जिसमें अनंत कई टेबल हैं। जैसा कि ग्राहक रेस्तरां में प्रवेश करते हैं, वे किसी भी कब्जे वाली मेज पर बेतरतीब ढंग से बैठते हैं या वे पहले उपलब्ध खाली टेबल पर बैठने का विकल्प चुनते हैं।

सीआरपी सकारात्मक पूर्णांकों के विभाजन के स्थान पर वितरण को परिभाषित करता है। हम ड्राइंग θ से शुरू करते हैं₁... θ_n ब्लैकवेल-मैकक्वीन कलश योजना से। जैसा कि हमने पिछले खंडों में चर्चा की है, हम एक स्पष्ट प्रभाव देखने की उम्मीद करते हैं और इस प्रकार अद्वितीय k मान k की कुल संख्या n की तुलना में काफी कम होगी। इस प्रकार यह k क्लस्टर में सेट {1,2,…, n} के विभाजन को परिभाषित करता है। नतीजतन ब्लैकवेल-मैकक्वीन कलश योजना से ड्राइंग {1,2,…, n} सेट का एक यादृच्छिक विभाजन प्रेरित करता है। चीनी रेस्तरां प्रक्रिया यह प्रेरित है विभाजन पर वितरण। एल्गोरिथ्म इस प्रकार है:

· हम एक खाली रेस्तरां से शुरुआत करते हैं।

· 1^st ग्राहक हमेशा 1 पर बैठता है^st तालिका

· द n + १^th ग्राहक के पास 2 विकल्प हैं:

o संभावना के साथ 1 निर्वासित टेबल पर बैठें

o संभावना के साथ किसी भी kth के कब्जे वाली तालिकाओं पर बैठें
जहां उस मेज पर बैठे लोगों की संख्या है

जहां α डीपी का फैलाव मूल्य है और किसी निश्चित समय में रेस्तरां में ग्राहकों की कुल संख्या है। अव्यक्त चर z_i i की तालिका संख्या संग्रहीत करता है^th ग्राहक और 1 से k तक मान लेता है_n जहां के_n कब्जे वाले तालिकाओं की कुल संख्या है जब n ग्राहक रेस्तरां में हैं। हमें ध्यान देना चाहिए कि के_n हमेशा n से कम या बराबर होगा और औसतन यह लगभग होता है । अंत में हमें ध्यान देना चाहिए कि टेबल की व्यवस्था की संभावना क्रमपरिवर्तन के लिए अपरिवर्तनीय है। इस प्रकार जेड_i विनिमेय है जिसका अर्थ है कि ग्राहकों के समान आकार वाले तालिकाओं की समान संभावना है।

चीनी रेस्त्राँ प्रक्रिया पुलीया कलश योजना और डिरिक्लेट प्रक्रिया से दृढ़ता से जुड़ी हुई है। सीआरपी एक निर्दिष्ट करने का एक तरीका है विभाजन पर वितरण (तालिका असाइनमेंट) n बिंदुओं का और अव्यक्त चर z के स्थान पर पूर्व के रूप में उपयोग किया जा सकता है_i कौन कौन से क्लस्टर असाइनमेंट निर्धारित करता है। सीआरपी केवल अंतर के साथ पोल्लिया की कलश योजना के बराबर है कि यह प्रत्येक तालिका / क्लस्टर को पैरामीटर प्रदान नहीं करता है। जाना सीआरपी से पुल्लिया की कलश योजना हम चित्र बनाते हैं सभी तालिकाओं के लिए k = 1,2… और फिर प्रत्येक x के लिए_i जिसे टेबल z में समूहीकृत किया गया है_i असाइन करें । दूसरे शब्दों में नए x पर असाइन करें_i तालिका का पैरामीटर the। अंत में जब से हम असाइन नहीं कर सकते the शुरुआत से अनंत तालिकाओं तक, हम हर बार एक नया new असाइन कर सकते हैं जब कोई व्यक्ति किसी नई तालिका पर बैठता है। उपरोक्त सभी के कारण, CRP डेटासेट पर क्लस्टर विश्लेषण करने के लिए कम्प्यूटेशनल रूप से कुशल एल्गोरिदम बनाने में हमारी मदद कर सकता है।

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

मुझे उम्मीद है कि आपको यह पोस्ट रोचक लगी होगी। यदि आपने किया है, तो इसे फेसबुक और ट्विटर पर साझा करने के लिए कुछ समय निकालें। 🙂