बहु-सशस्त्र डाकू: परिचय और UCB1 एल्गोरिथ्म

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

सिफारिश प्रणालियों पर पिछली श्रृंखला का सारांश:

• सिफारिश प्रणाली: समस्या का बयान ;
• उपयोगकर्ता-आधारित और आइटम-आधारित सहयोगी फ़िल्टरिंग ;
• एसवीडी, भाग I ;
• एसवीडी और बुनियादी भविष्यवक्ता ;
• पर्ल पर एसवीडी ;
• ओवरफिटिंग और नियमितीकरण ;
• बेयस प्रमेय और भोले बेयस ;
• LDA (अव्यक्त डिरिचलेट आवंटन, विषयगत मॉडलिंग) ।

इस बार हम एक नया विषय शुरू कर रहे हैं - बहु-सशस्त्र डाकुओं के बारे में। बैंडिट सबसे सरल हैं, लेकिन तथाकथित सुदृढीकरण प्रशिक्षण में समस्या का केवल अधिक महत्वपूर्ण बयान ...



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

समस्या के इस तरह के एक बयान को सुदृढीकरण सीखने कहा जाता है : एक एजेंट है जो किसी प्रकार के वातावरण में कार्य करता है; एजेंट कुछ करने की कोशिश कर रहा है, और उसके कार्यों के जवाब में माध्यम एजेंट को बन्स देता है या, इसके विपरीत, एक बिजली का झटका देता है। एजेंट बड़े बन्स प्राप्त करने की कोशिश कर रहा है, और कम बार वर्तमान के साथ। सामान्य तौर पर, एक भूलभुलैया में एक विशिष्ट माउस।

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


( Microsoft रिसर्च से तस्वीर)

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

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

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

एक उदाहरण के रूप में, मैं तुरंत प्रशिक्षण घाटे के इस बहुत ही उपाय के लिए कुछ सर्वोत्तम गारंटी के साथ एक एल्गोरिथ्म दूंगा। यह UCB1 एल्गोरिथ्म है; एल्गोरिथ्म अपने आप में बहुत सरल है, इसकी इष्टतमता का प्रमाण, ज़ाहिर है, इतना सरल नहीं है, लेकिन हम इसमें नहीं जाएंगे, और मैं लेख में रुचि रखने वालों का उल्लेख करूंगा [ Auer et al।, 2002 ]; वहाँ आप बेहतर स्थिरांक के साथ एक और अधिक "उन्नत" संस्करण पा सकते हैं।

• इनिशियलाइज़ेशन: प्रत्येक हैंडल को एक बार खींचें
• जबकि काम जारी है:
  
  • संभाल जे खींचो, जिसके लिए अधिकतम मूल्य
    ।
    जहाँ - हैंडल j से औसत आय, n _j वह संख्या है जो हमने हैंडल j को झटका दिया है, और n वह संख्या है जब हमने सभी हैंडल को झटका दिया।

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

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

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