बहु-सशस्त्र डाकू: गतिशील गामा-पॉइसन मॉडल

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




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

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


( याहू मुखपृष्ठ से वास्तविक समाचार नमूना)

औपचारिक रूप से, हमारे पास उत्पादों / साइटों का एक सेट है; अब हम व्यक्तिगत रूप से, स्वतंत्र रूप से उनमें से प्रत्येक के सीटीआर का मूल्यांकन करना चाहते हैं, इसलिए भविष्य में हम उनमें से एक के साथ काम करेंगे। हम समय अवधि t (छोटे) को ठीक करते हैं और छापों (कुल प्रयोगों की संख्या) और क्लिकों ("जैसे" अंक या अन्य वांछित परिणाम) पर विचार करते हैं । मान लीजिए कि पीरियड टी के दौरान हमने साइट को n _टी बार दिखाया और रेटिंग r _t मिला ( r _t एक पूर्णांक है जो n _t से कम है)। फिर, समय टी के प्रत्येक क्षण में , हमें एक अनुक्रम दिया जाता है , और हम समय t + 1 पर p _{t + 1} , क्लिकथ्रू दर (CTR) की भविष्यवाणी करना चाहते हैं।

हम पहले प्राकृतिक विचारों को सूचीबद्ध करते हैं:

• करंट की तरह ; इस तरह की छंटाई वास्तव में जल्दी से जवाब देगी, लेकिन सबसे अधिक संभावना है कि बहुत जल्दी प्रतिक्रिया होगी, अर्थात। यह बेहद अस्थिर होगा: यादृच्छिक उतार-चढ़ाव का एक प्रतिकूल प्रभाव पड़ेगा;
• कुल औसत के आधार पर छाँटें ; इस दृष्टिकोण में विपरीत समस्याएं होंगी - यह परिवर्तनों के लिए बहुत धीरे-धीरे प्रतिक्रिया करेगा, और लंबे समय तक "फीका" समाचार शीर्ष में रहेगा;
• स्लाइडिंग विंडो द्वारा गणना की गई औसत के अनुसार, ; यह काफी उचित अनुमान है, लेकिन यहां हमें विचरण p _{+ 1 के} लिए अनुमान नहीं मिलता है, और हम विभिन्न "पेन" में बदलाव की विभिन्न गति के लिए भी अनुकूल नहीं हो सकते हैं।

इस समस्या को हल करने के लिए, तथाकथित गतिशील गामा - पॉइसन मॉडल (गतिशील गामा - पॉइसन मॉडल, डीजीपी) का उपयोग करने का प्रस्ताव है। DGP की संभाव्य धारणाएँ इस प्रकार हैं:

• (नियत n _t और p _{t के लिए हमें} Poisson वितरण पर r _t वितरित किया जाता है);
• जहाँ (औसत सफलता दर p _t
  परिवर्तन बहुत तेज़ नहीं हैं, लेकिन एक यादृच्छिक चर which _t से गुणा करके, जिसमें एकता के आसपास एक गामा वितरण है);
• मॉडल पैरामीटर वितरण पैरामीटर हैं ।
  और यह भी पैरामीटर η, जो दिखाता है कि पी _टी कितनी आसानी से भिन्न हो सकते हैं; तदनुसार, कार्य पीछे वितरण के मापदंडों का मूल्यांकन करना है
  

बहुत गणितीय पीड़ा के बाद (जो मैं यहां छोड़ दूँगा), इस मॉडल के मापदंडों को पुनर्गणना करने के लिए एक बहुत ही सरल पुनरावृत्ति एल्गोरिथ्म प्राप्त किया जाता है (वास्तव में, वितरण का विशिष्ट रूप ठीक चुना गया था ताकि यह पता चले: गामा वितरण प्यूसन वितरण के लिए एक पूर्व वितरण है)। मान लीजिए कि पिछले चरण टी -1 में हमें कुछ अनुमान μ _टी , मॉडल मापदंडों के लिए previous टी मिले:

और फिर हमें एक नया बिंदु (समय की एक नई अवधि के लिए माप) n _t , r _{t मिला} । हम निरूपित करते हैं (प्रभावी नमूना आकार)। फिर हम पहले μ _t ,: _t के अनुमानों को परिष्कृत करते हैं:

और फिर के लिए एक नई भविष्यवाणी उत्पन्न करते हैं :


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


(DGP मॉडल प्रेडिक्टिव न्यूज सैंपल का हिस्सा)

इस मॉडल का और सुधार नए पेन के लिए अच्छे प्राथमिकताओं के वितरण (अच्छा μ ₀ और this ₀ ) को चुनने के साथ जुड़ा हुआ है - यह बहुत महत्वपूर्ण है, क्योंकि नए उत्पादों (उदाहरण के लिए, नवीनतम समाचार) को जल्दी से ऑपरेशन में डाल दिया जाना चाहिए, और उनके बारे में पहले डेटा पर इतना नहीं (एक ही ठंड शुरू)। एक प्राथमिकता वितरण का एक अच्छा अनुमान नकारात्मक द्विपद वितरण से प्राप्त होता है - मान लीजिए कि हमारे पास डेटाबेस एन ऐतिहासिक रिकॉर्ड ( एन अन्य साइटें) हैं, जिसके लिए संकेतक ज्ञात हैं और (समय की पहली अवधि के लिए छापों और सफल छापों की संख्या); हम एक नई, अज्ञात साइट के लिए μ ₀ और a ₀ का अनुमान प्राप्त करना चाहते हैं, जो एक नई साइट के लिए अपेक्षित r ₁ और n ₁ को अच्छी तरह से अनुमानित करना चाहिए। फिर, मैं गणित को छोड़ दूंगा, लेकिन जवाब यह है कि इसे माना जाना चाहिए

जहाँ - गामा समारोह। आप ग्रेडिएंट उदय को अधिकतम कर सकते हैं - उस बिंदु से हम ग्रेडिएंट की ओर बढ़ते हैं, अर्थात्। आंशिक डेरिवेटिव वैक्टर।

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

अगली बार हम शायद कुछ पूरी तरह से अलग विषय पर बात करेंगे; इसके अलावा, सिफारिश प्रणालियों में ठंड शुरू चक्रों के लिए बने रहें। नए ग्रंथों के लिए!