Thompson sampling
थॉम्पसन सैंपलिंग, जिसका नाम विलियम आर. थॉम्पसन के नाम पर रखा गया है, बहु-सशस्त्र डाकू समस्या में अन्वेषण-शोषण दुविधा को संबोधित करने वाले कार्यों को चुनने के लिए एक शोध है। इसमें उस कार्रवाई को चुनना शामिल है जो यादृच्छिक रूप से तैयार किए गए विश्वास के संबंध में अपेक्षित इनाम को अधिकतम करता है। विवरण संदर्भों के एक समूह, कार्यों के एक समूह और पुरस्कारों पर विचार करें। खिलाड़ी का उद्देश्य विभिन्न संदर्भों के तहत क्रियाएं खेलना है, जैसे कि संचयी पुरस्कारों को अधिकतम करना। विशेष रूप से, प्रत्येक दौर में, खिलाड़ी एक संदर्भ प्राप्त करता है, एक क्रिया खेलता है और एक वितरण के बाद एक पुरस्कार प्राप्त करता है जो संदर्भ और जारी कार्रवाई पर निर्भर करता है। थॉम्पसन सैंपलिंग के तत्व इस प्रकार हैंः एक संभावना कार्य; वितरण के मापदंडों का एक समूह; इन मापदंडों पर एक पूर्व वितरण; पिछले अवलोकन तीन गुना; एक पश्च वितरण, जहां संभावना कार्य है। थॉम्पसन सैंपलिंग में इस संभावना के अनुसार कार्रवाई करना शामिल है कि यह अपेक्षित इनाम को अधिकतम करता है; कार्रवाई को संभावना के साथ चुना जाता है जहां संकेतक कार्य है। व्यवहार में, नियम को नमूने द्वारा लागू किया जाता है। प्रत्येक दौर में, मापदंडों को पीछे से नमूना लिया जाता है, और एक ऐसी क्रिया का चयन किया जाता है जो अधिकतम होती है, अर्थात। नमूना मापदंडों, कार्रवाई और वर्तमान संदर्भ को देखते हुए अपेक्षित पुरस्कार। अवधारणात्मक रूप से, इसका मतलब है कि खिलाड़ी प्रत्येक दौर में पीछे के वितरण के अनुसार यादृच्छिक रूप से अपने विश्वासों को तुरंत प्रकट करता है, और फिर उनके अनुसार इष्टतम रूप से कार्य करता है। अधिकांश व्यावहारिक अनुप्रयोगों में, मॉडलों पर एक पश्च वितरण से बनाए रखना और नमूना लेना कम्प्यूटेशनल रूप से कठिन है। इस प्रकार, थॉम्पसन सैंपलिंग का उपयोग अक्सर अनुमानित सैंपलिंग तकनीकों के साथ किया जाता है। थॉम्पसन नमूनाकरण का इतिहास मूल रूप से 1933 में थॉम्पसन द्वारा वर्णित किया गया था। बाद में बहु-सशस्त्र डाकू समस्याओं के संदर्भ में इसे कई बार स्वतंत्र रूप से फिर से खोजा गया। डाकू मामले के लिए अभिसरण का पहला प्रमाण 1997 में दिखाया गया है। मार्कोव निर्णय प्रक्रियाओं के लिए पहला आवेदन 2000 में था। एक संबंधित दृष्टिकोण (बायेसियन नियंत्रण नियम देखें) 2010 में प्रकाशित किया गया था। 2010 में यह भी दिखाया गया था कि थॉम्पसन सैंपलिंग तुरंत आत्म-सुधार है। प्रासंगिक डाकुओं के लिए लक्षणहीन अभिसरण परिणाम 2011 में प्रकाशित किए गए थे। थॉम्पसन सैंपलिंग का व्यापक रूप से कई ऑनलाइन सीखने की समस्याओं में उपयोग किया गया है, जिसमें वेबसाइट डिजाइन और ऑनलाइन विज्ञापन में ए/बी परीक्षण और विकेंद्रीकृत निर्णय लेने में त्वरित शिक्षा शामिल है। डकैतों के बीच द्वंद्व के लिए एक डबल थॉम्पसन सैंपलिंग (डी-टीएस) एल्गोरिदम प्रस्तावित किया गया है, जो पारंपरिक एमएबी का एक प्रकार है, जहां प्रतिक्रिया जोड़ीदार तुलना के रूप में आती है। अन्य दृष्टिकोणों के साथ संबंध संभावना मिलान एक निर्णय रणनीति है जिसमें वर्ग सदस्यता की भविष्यवाणियां वर्ग आधार दरों के समानुपाती होती हैं। इस प्रकार, यदि प्रशिक्षण सेट में सकारात्मक उदाहरणों को 60 प्रतिशत समय पर देखा जाता है, और नकारात्मक उदाहरणों को 40 प्रतिशत समय पर देखा जाता है, तो संभावना-मिलान रणनीति का उपयोग करने वाला पर्यवेक्षक (बिना लेबल वाले उदाहरणों के लिए) 60 प्रतिशत उदाहरणों पर "सकारात्मक" के वर्ग लेबल और 40 प्रतिशत उदाहरणों पर "नकारात्मक" के वर्ग लेबल की भविष्यवाणी करेगा। बायेसियन नियंत्रण नियम मनमाने गतिशील वातावरण और कारण संरचनाओं के लिए थॉम्पसन नमूने का एक सामान्यीकरण, जिसे बायेसियन नियंत्रण नियम के रूप में जाना जाता है, क्रियाओं और टिप्पणियों के साथ अनुकूली कोडिंग समस्या का इष्टतम समाधान दिखाया गया है। इस सूत्रीकरण में, एक अभिकर्ता की अवधारणा व्यवहारों के एक समूह पर एक मिश्रण के रूप में की जाती है। जैसे ही एजेंट अपने पर्यावरण के साथ बातचीत करता है, यह कारण गुणों को सीखता है और उस व्यवहार को अपनाता है जो पर्यावरण के व्यवहार की सर्वोत्तम भविष्यवाणी के साथ व्यवहार के सापेक्ष एन्ट्रापी को कम करता है। यदि इन व्यवहारों को अधिकतम अपेक्षित उपयोगिता सिद्धांत के अनुसार चुना गया है, तो बायेसियन नियंत्रण नियम का एसिम्प्टोटिक व्यवहार पूरी तरह से तर्कसंगत एजेंट के एसिम्प्टोटिक व्यवहार से मेल खाता है। व्यवस्था इस प्रकार है। एक एजेंट द्वारा समय-समय पर जारी किए गए कार्यों को होने दें, और एजेंट द्वारा समय-समय पर एकत्र किए गए अवलोकनों को होने दें। फिर, अभिकर्ता संभाव्यता के साथ कार्रवाई को जारी करता हैः जहां "टोपी"-संकेतन इस तथ्य को दर्शाता है कि यह एक कारणात्मक हस्तक्षेप है (कारण देखें), न कि एक सामान्य अवलोकन। यदि अभिकर्ता अपने व्यवहार पर विश्वास रखता है, तो बायेसियन नियंत्रण नियम बन जाता है, जहां दिए गए कार्यों और टिप्पणियों पर पैरामीटर पर पश्च वितरण होता है। व्यवहार में, बायेसियन नियंत्रण नमूना लेने के बराबर है, प्रत्येक समय चरण पर, पश्च वितरण से एक पैरामीटर, जहां पश्च वितरण की गणना केवल टिप्पणियों की (कारण) संभावनाओं पर विचार करके और क्रियाओं की (कारण) संभावनाओं को नजरअंदाज करके और फिर क्रिया वितरण से कार्रवाई का नमूना लेकर की जाती है। उच्च-विश्वास-सीमा (यू. सी. बी.) एल्गोरिदम थॉम्पसन सैंपलिंग और उच्च-विश्वास-सीमा एल्गोरिदम एक मौलिक गुण साझा करते हैं जो उनकी कई सैद्धांतिक गारंटी को रेखांकित करता है। मोटे तौर पर, दोनों एल्गोरिदम उन कार्यों के लिए अन्वेषणात्मक प्रयास आवंटित करते हैं जो इष्टतम हो सकते हैं और इस अर्थ में "आशावादी" हैं। इस गुण का लाभ उठाते हुए, कोई भी यू. सी. बी. एल्गोरिदम के लिए स्थापित अफसोस सीमा को थॉम्पसन सैंपलिंग के लिए बायेसियन अफसोस सीमा में परिवर्तित कर सकता है या इन दोनों एल्गोरिदम और समस्याओं के कई वर्गों में अफसोस विश्लेषण को एकीकृत कर सकता है। संदर्भ आर्टिफिशियल इंटेलिजेंस ह्यूरिस्टिक एल्गोरिदम अनुक्रमिक विधियाँ अनुक्रमिक प्रयोग