नमस्कार, हेब्र! मैं आपके सामने सॉल्विंग मल्टिमेटेड डाकुओं का पहला पृष्ठ प्रस्तुत करता हूं : एप्सिलॉन-लालची और थॉम्पसन नमूनाकरण लेख की तुलना।

बहु-सशस्त्र दस्यु समस्या

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

समस्या यह है: हम कैसे सबसे अधिक कुशलता से समझते हैं कि कौन सी मशीन सबसे उपयुक्त है, और एक ही समय में वास्तविक समय में कई विशेषताओं का प्रयास करें? यह किसी प्रकार की सैद्धांतिक समस्या नहीं है, यह एक समस्या है जो हर समय एक व्यवसाय का सामना करती है। उदाहरण के लिए, एक कंपनी के पास संदेशों के लिए कई विकल्प होते हैं जो उपयोगकर्ताओं को दिखाए जाने की आवश्यकता होती है (उदाहरण के लिए, संदेशों में विज्ञापन, साइट, चित्र) शामिल होते हैं ताकि चयनित संदेश एक निश्चित व्यावसायिक कार्य (रूपांतरण, क्लिक करने योग्यता आदि) को अधिकतम करें

इस समस्या को हल करने का एक विशिष्ट तरीका कई बार ए / बी परीक्षण चलाना है। यही है, कई हफ्तों के लिए प्रत्येक विकल्प को समान रूप से अक्सर दिखाने के लिए, और फिर, सांख्यिकीय परीक्षणों के आधार पर, तय करें कि कौन सा विकल्प बेहतर है। यह विधि उपयुक्त है जब कुछ विकल्प हैं, कहते हैं, 2 या 4. लेकिन जब कई विकल्प होते हैं, तो यह दृष्टिकोण अप्रभावी हो जाता है - दोनों खोए हुए समय और खोए हुए लाभ में।

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

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

अवधारणाओं का संक्षिप्त शब्दकोश

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

अन्वेषण और शोषण

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

एप्सिलॉन-लालची एल्गोरिथ्म

इस दुविधा से बाहर एक विशिष्ट तरीका एप्सिलॉन-लालची एल्गोरिथ्म है। "लालची" का मतलब वही है जो आपने सोचा था। कुछ प्रारंभिक अवधि के बाद, जब हम गलती से प्रयास करते हैं - कहते हैं, 1000 बार, एल्गोरिथ्म उत्सुकता से ई प्रतिशत के प्रयासों में सबसे अच्छा विकल्प चुनता है। उदाहरण के लिए, यदि e = 0.05, समय का 95% एल्गोरिथ्म सबसे अच्छा विकल्प चुनता है, और शेष 5% समय में यह यादृच्छिक प्रयासों का चयन करता है। वास्तव में, यह एक अधिक प्रभावी एल्गोरिथ्म है, हालांकि, यह विकल्पों के स्थान का पता लगाने के लिए पर्याप्त नहीं हो सकता है, और इसलिए, यह मूल्यांकन करने के लिए पर्याप्त नहीं होगा कि कौन सा विकल्प सबसे अच्छा है, एक सबॉप्टिमल विकल्प पर अटक जाता है। आइए कोड में दिखाएं कि यह एल्गोरिदम कैसे काम करता है।

लेकिन पहले, कुछ निर्भरताएँ। हमें पर्यावरण को परिभाषित करना चाहिए। यह वह संदर्भ है जिसमें एल्गोरिदम चलेगा। इस मामले में, संदर्भ बहुत सरल है। वह एजेंट को बुलाता है ताकि एजेंट तय करे कि किस कार्रवाई को चुनना है, तो संदर्भ इस कार्रवाई को लॉन्च करता है और इसके लिए प्राप्त बिंदुओं को एजेंट को वापस कर देता है (जो किसी तरह अपने राज्य को अपडेट करता है)।

class Environment: def __init__(self, variants, payouts, n_trials, variance=False): self.variants = variants if variance: self.payouts = np.clip(payouts + np.random.normal(0, 0.04, size=len(variants)), 0, .2) else: self.payouts = payouts #self.payouts[5] = self.payouts[5] if i < n_trials/2 else 0.1 self.n_trials = n_trials self.total_reward = 0 self.n_k = len(variants) self.shape = (self.n_k, n_trials) def run(self, agent): """Run the simulation with the agent. agent must be a class with choose_k and update methods.""" for i in range(self.n_trials): # agent makes a choice x_chosen = agent.choose_k() # Environment returns reward reward = np.random.binomial(1, p=self.payouts[x_chosen]) # agent learns of reward agent.reward = reward # agent updates parameters based on the data agent.update() self.total_reward += reward agent.collect_data() return self.total_reward

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

 class BaseSampler: def __init__(self, env, n_samples=None, n_learning=None, e=0.05): self.env = env self.shape = (env.n_k, n_samples) self.variants = env.variants self.n_trials = env.n_trials self.payouts = env.payouts self.ad_i = np.zeros(env.n_trials) self.r_i = np.zeros(env.n_trials) self.thetas = np.zeros(self.n_trials) self.regret_i = np.zeros(env.n_trials) self.thetaregret = np.zeros(self.n_trials) self.a = np.ones(env.n_k) self.b = np.ones(env.n_k) self.theta = np.zeros(env.n_k) self.data = None self.reward = 0 self.total_reward = 0 self.k = 0 self.i = 0 self.n_samples = n_samples self.n_learning = n_learning self.e = e self.ep = np.random.uniform(0, 1, size=env.n_trials) self.exploit = (1 - e) def collect_data(self): self.data = pd.DataFrame(dict(ad=self.ad_i, reward=self.r_i, regret=self.regret_i))

नीचे हम प्रत्येक के लिए 10 विकल्प और पेबैक परिभाषित करते हैं। सबसे अच्छा विकल्प 9 विकल्प है, जिसमें 0.11% का पेबैक है।

 variants = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] payouts = [0.023, 0.03, 0.029, 0.001, 0.05, 0.06, 0.0234, 0.035, 0.01, 0.11]

बनाने के लिए कुछ करने के लिए, हम भी randomSampler वर्ग को परिभाषित करते हैं। बेसलाइन मॉडल के रूप में इस वर्ग की आवश्यकता है। वह बस विशुद्ध रूप से बेतरतीब ढंग से प्रत्येक प्रयास पर एक विकल्प चुनता है और अपने मापदंडों को अपडेट नहीं करता है।

 class RandomSampler(BaseSampler): def __init__(self, env): super().__init__(env) def choose_k(self): self.k = np.random.choice(self.variants) return self.k def update(self): # nothing to update #self.thetaregret[self.i] = self.thetaregret[self.i] #self.regret_i[self.i] = np.max(self.thetaregret) - self.theta[self.k] #self.thetas[self.i] = self.theta[self.k] self.thetaregret[self.i] = np.max(self.theta) - self.theta[self.k] self.a[self.k] += self.reward self.b[self.k] += 1 self.theta = self.a/self.b self.ad_i[self.i] = self.k self.r_i[self.i] = self.reward self.i += 1

अन्य मॉडलों में निम्नलिखित संरचना होती है। सभी में select_k और update विधियाँ हैं। select_k वह विधि लागू करता है जिसके द्वारा एजेंट एक विकल्प का चयन करता है। अद्यतन एजेंट के मापदंडों को अद्यतन करता है - यह विधि यह बताती है कि विकल्प को चुनने के लिए एजेंट की क्षमता कैसे होती है (रैंडमस्म्लर के साथ यह क्षमता किसी भी तरह से बदलती नहीं है)। हम निम्नलिखित पैटर्न का उपयोग करके पर्यावरण में एजेंट चलाते हैं।

 en0 = Environment(machines, payouts, n_trials=10000) rs = RandomSampler(env=en0) en0.run(agent=rs)

एप्सिलॉन-लालची एल्गोरिथ्म का सार इस प्रकार है।

N प्रयासों के लिए अनियमित रूप से k का चयन करें।
प्रत्येक विकल्प के लिए, प्रत्येक विकल्प के लिए, जीत का मूल्यांकन करें।
सभी n प्रयासों के बाद:
संभावना 1 के साथ - ई उच्चतम लाभ के साथ कश्मीर चुनें;
संभाव्यता के साथ ई K को अनियमित रूप से चुनें।

एप्सिलॉन-लालची कोड:

 class eGreedy(BaseSampler): def __init__(self, env, n_learning, e): super().__init__(env, n_learning, e) def choose_k(self): # e% of the time take a random draw from machines # random k for n learning trials, then the machine with highest theta self.k = np.random.choice(self.variants) if self.i < self.n_learning else np.argmax(self.theta) # with 1 - e probability take a random sample (explore) otherwise exploit self.k = np.random.choice(self.variants) if self.ep[self.i] > self.exploit else self.k return self.k # every 100 trials update the successes # update the count of successes for the chosen machine def update(self): # update the probability of payout for each machine self.a[self.k] += self.reward self.b[self.k] += 1 self.theta = self.a/self.b #self.total_reward += self.reward #self.regret_i[self.i] = np.max(self.theta) - self.theta[self.k] #self.thetaregret[self.i] = self.thetaregret[self.i] self.thetas[self.i] = self.theta[self.k] self.thetaregret[self.i] = np.max(self.thetas) - self.theta[self.k] self.ad_i[self.i] = self.k self.r_i[self.i] = self.reward self.i += 1

नीचे दिए गए ग्राफ़ पर आप विशुद्ध रूप से यादृच्छिक नमूने के परिणाम देख सकते हैं, अर्थात्, दूसरे शब्दों में, यहाँ कोई मॉडल नहीं है। ग्राफ़ दिखाता है कि प्रत्येक प्रयास पर एल्गोरिथ्म क्या पसंद करता है, अगर 10 हजार प्रयास थे। एल्गोरिथ्म केवल कोशिश करता है, लेकिन सीखता नहीं है। कुल मिलाकर, उन्होंने 418 अंक बनाए।

आइए देखें कि एक ही वातावरण में एप्सिलॉन-लालची एल्गोरिदम कैसे व्यवहार करता है। ई = 0.1 और n_learning = 500 के साथ 10 हजार प्रयासों के लिए एल्गोरिथ्म को चलाएं (एजेंट बस पहले 500 प्रयासों की कोशिश करता है, फिर यह संभावना ई = 0.1 के साथ प्रयास करता है)। आइए हम एल्गोरिदम का मूल्यांकन करें कि पर्यावरण में कुल कितने अंक हैं।

 en1 = Environment(machines, payouts, n_trials) eg = eGreedy(env=en1, n_learning=500, e=0.1) en1.run(agent=eg)

एप्सिलॉन-लालची एल्गोरिथ्म ने 788 अंक बनाए, यादृच्छिक एल्गोरिथम की तुलना में लगभग 2 गुना बेहतर - सुपर! दूसरा ग्राफ इस एल्गोरिथ्म को बहुत अच्छी तरह से समझाता है। हम देखते हैं कि पहले 500 चरणों के लिए क्रियाएं लगभग समान रूप से वितरित की जाती हैं और K को यादृच्छिक रूप से चुना जाता है। हालांकि, फिर यह विकल्प 5 का अत्यधिक शोषण करना शुरू कर देता है - यह एक बहुत मजबूत विकल्प है, लेकिन सबसे अच्छा नहीं है। हम यह भी देखते हैं कि एजेंट अभी भी बेतरतीब ढंग से 10% समय का चयन करता है।

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

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

थॉम्पसन का नमूना

थॉम्पसन का नमूना एप्सिलॉन-लालची एल्गोरिदम से तीन मुख्य बिंदुओं से मौलिक रूप से अलग है:

यह लालची नहीं है।
यह अधिक परिष्कृत तरीके से प्रयास करता है।
यह बायेसियन है।

मुख्य बिंदु पैराग्राफ 3 है, पैराग्राफ 1 और 2 इसका पालन करते हैं।

एल्गोरिथ्म का सार यह है:

प्रत्येक विकल्प के भुगतान के लिए 0 और 1 के बीच प्रारंभिक बीटा वितरण सेट करें।
इस वितरण से विकल्पों का नमूना लें, अधिकतम थीटा पैरामीटर चुनें।
विकल्प k चुनें जो सबसे बड़ी थीटा से जुड़ा हो।
देखें कि कितने अंक बनाए गए हैं, वितरण मापदंडों को अपडेट करें।

बीटा वितरण के बारे में यहाँ पढ़ें।
और पायथन में इसके उपयोग के बारे में - यहाँ ।

एल्गोरिथम कोड:

  class ThompsonSampler(BaseSampler): def __init__(self, env): super().__init__(env) def choose_k(self): # sample from posterior (this is the thompson sampling approach) # this leads to more exploration because machines with > uncertainty can then be selected as the machine self.theta = np.random.beta(self.a, self.b) # select machine with highest posterior p of payout self.k = self.variants[np.argmax(self.theta)] #self.k = np.argmax(self.a/(self.a + self.b)) return self.k def update(self): #update dist (a, b) = (a, b) + (r, 1 - r) self.a[self.k] += self.reward self.b[self.k] += 1 - self.reward # ie only increment b when it's a swing and a miss. 1 - 0 = 1, 1 - 1 = 0 #self.thetaregret[self.i] = self.thetaregret[self.i] #self.regret_i[self.i] = np.max(self.theta) - self.theta[self.k] self.thetas[self.i] = self.theta[self.k] self.thetaregret[self.i] = np.max(self.thetas) - self.theta[self.k] self.ad_i[self.i] = self.k self.r_i[self.i] = self.reward self.i += 1

एल्गोरिथ्म का औपचारिक अंकन इस तरह दिखता है।

आइए इस एल्गोरिदम को प्रोग्राम करें। अन्य एजेंटों की तरह, ThompsonSampler BaseSampler से विरासत में मिला है और अपने स्वयं के select_k और अद्यतन विधियों को परिभाषित करता है। अब हमारे नए एजेंट को लॉन्च करें।

  en2 = Environment(machines, payouts, n_trials) tsa = ThompsonSampler(env=en2) en2.run(agent=tsa)

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

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

थॉम्पसन एल्गोरिथ्म की एक और उल्लेखनीय संपत्ति: चूंकि यह बायेसियन है, इसलिए हम अपने मापदंडों का उपयोग करके प्रत्येक विकल्प के लिए पेबैक अनुमान में अनिश्चितता का अनुमान लगा सकते हैं। नीचे दिया गया ग्राफ़ 6 अलग-अलग बिंदुओं पर और 20,000 प्रयासों में पीछे के वितरण को दिखाता है। आप देखते हैं कि कैसे वितरण धीरे-धीरे सबसे अच्छे पेबैक वाले विकल्प में परिवर्तित होने लगता है।

अब 100 सिमुलेशन में सभी 3 एजेंटों की तुलना करें। 1 सिमुलेशन 10,000 प्रयासों पर एक एजेंट लॉन्च है।

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

अफसोस (अफसोस)

अफसोस का मूल्यांकन करने के लिए एल्गोरिथ्म कितनी अच्छी तरह काम करता है इसका मूल्यांकन करने का एक और तरीका है। मोटे तौर पर, पहले से ही किए गए कार्यों के संबंध में यह जितना छोटा है, उतना ही बेहतर है। नीचे त्रुटि के लिए कुल अफसोस और पछतावा का एक ग्राफ है। एक बार फिर - कम अफसोस, बेहतर।

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

निष्कर्ष

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

महत्वपूर्ण! थॉम्पसन के नमूने का मतलब यह नहीं है कि आपको ए / बी परीक्षण करने की आवश्यकता नहीं है। आमतौर पर, वे पहले उसकी मदद से सबसे अच्छे विकल्प ढूंढते हैं, और फिर पहले से ही उन पर ए / बी परीक्षण करते हैं।

द मल्टी-आर्म्ड बैंडिट प्रॉब्लम - तुलना एप्सिलॉन-लालची रणनीति और थॉम्पसन सैम्पलिंग से करें