आर्म्स, पुल्स, इनाम
स्लॉट मशीनों की एक पंक्ति
कल्पना करें कि K स्लॉट मशीनें एक पंक्ति में लगी हुई हैं। प्रत्येक मशीन अलग-अलग औसत इनाम देती है, लेकिन आपको उन औसतों का कोई ज्ञान नहीं है। हर चरण में आप एक मशीन चुनते हैं, उसका लीवर खींचते हैं, और भुगतान देखते हैं। आपका लक्ष्य: कई पुल्स में कुल इनाम को अधिकतम करना।
यह सेटअप एक मल्टी-आर्म्ड बैंडिट समस्या को परिभाषित करता है। K = आर्म्स की संख्या। एक पुल एक आर्म चुनता है। इनाम उस आर्म के छिपे वितरण से आता है। आर्म k का mean_reward(k) k के पुल्स पर चलते औसत को ट्रैक करता है।
अन्वेषण बनाम शोषण
दो दबाव एक-दूसरे के विपरीत खींचते हैं:
शोषण उच्चतम देखे गए औसत_पुरस्कार वाली बांह को खींचता है। लालची। जोखिम: 2 खींचने के बाद जो बांह शानदार लगी हो, वह निचले सच्चे औसत की ओर प्रतिगमन कर सकती है।
अन्वेषण अनिश्चितता को कम करने के लिए कम-परीक्षित बांह को खींचता है। जोखिम: अन्वेषण में बिताया समय उस ज्ञात अच्छी बांह से पुरस्कार एकत्र करने का खर्च करता है जो आप प्राप्त कर सकते थे।
एक अच्छी नीति दोनों को मिलाती है। शुद्ध शोषण प्रारंभिक विजेताओं को हमेशा के लिए लॉक कर देता है। शुद्ध अन्वेषण कभी भुगतान एकत्र नहीं करता।
ANDREA की भुजाएँ = डेटा स्रोत
ANDREA प्रशिक्षण को एक बैंडिट के रूप में फ्रेम करती है। प्रत्येक डेटा स्रोत (hermes3-general, gutenberg, dictionary, synthetic-chat, smoltalk, आदि) एक भुजा के रूप में कार्य करता है। प्रत्येक प्रशिक्षण चरण एक भुजा खींचता है: उस स्रोत से एक दस्तावेज़ लोड करें, फॉरवर्ड पास चलाएँ, हानि में कमी का अवलोकन करें। प्रति स्रोत औसत पुरस्कार ट्रैक करता है कि वह स्रोत औसतन हानि में कितना सुधार करता है।
यह क्यों फिट बैठता है: प्रशिक्षण के दौरान मॉडल की आवश्यकताएँ बदलती हैं। प्रारंभिक चरणों को व्यापक एक्सपोज़र (कई स्रोतों) से लाभ होता है। बाद के चरणों को लक्षित पॉलिश (कुछ उच्च-पुरस्कार स्रोतों) से लाभ होता है। एक बैंडिट अनुकूलित होता है; एक निश्चित सैंपलिंग अनुपात नहीं कर सकता।
टुकड़ों का नामकरण
UCB1 स्कोर
Auer, Cesa-Bianchi & Fischer, 2002
पीटर ऑयर और उनके सहयोगियों ने 2002 में UCB1 को एक finite-time bandit policy के रूप में प्रकाशित किया, जिसमें O(log N) की regret bound है। UCB1 एक arm को चुनता हैโดย इसके वर्तमान औसत पुरस्कार को एक exploration bonus के साथ जोड़कर, जो arm के pull होने पर सिकुड़ता जाता है।
सूत्र
UCB(k) = mean_reward(k) + C * sqrt(ln(N) / n_k)
शब्द दर शब्द:
- mean_reward(k): आर्म k के n_k पुलों में देखा गया औसत पुरस्कार। शोषण पद।
- N: अब तक सभी आर्म्स पर कुल पुल। हर कदम पर बढ़ता है।
- n_k: विशेष रूप से आर्म k के पुल। केवल तब बढ़ता है जब k चुना जाता है।
- C: अन्वेषण स्थिरांक। मानक पाठ्यपुस्तक मान: 1.4 (sqrt(2))। ANDREA C=0.5 का उपयोग करता है।
- sqrt(ln(N) / n_k): विश्वास त्रिज्या। कम पुला गया आर्म छोटा n_k होने से बड़ा बोनस पाता है; अच्छी तरह पुला गया आर्म बड़ा n_k होने से छोटा बोनस पाता है।
सूत्र क्यों काम करता है
ln(N) धीरे-धीरे बढ़ता है (लघुगणकीय), इसलिए अंश कुल अनुभव के साथ धीरे चढ़ता है। न_k विभाजक में होने से विशिष्ट आर्म के लिए साक्ष्य जमा होने पर पद सिकुड़ता है। वर्गमूल प्रतिक्रिया को नरम बनाता है, जो एक एकल कम-अन्वेषित आर्म को हमेशा हावी होने से रोकता है।
हर कदम पर argmax_k UCB(k) द्वारा चयन करना दोनों दबावों को स्वचालित रूप से संतुलित करता है। कोई epsilon पैरामीटर नहीं, कोई शेड्यूल नहीं, कोई तापमान नहीं। गणित इसे संभाल लेता है।
UCB स्कोर की गणना करें
C=0.5 क्यों 1.4 के बजाय
पाठ्यपुस्तक मूल्य
Auer, Cesa-Bianchi & Fischer ने पुरस्कार [0, 1] में होने की धारणा के तहत एक पछतावा बंध प्राप्त किया। बंध C = sqrt(2) लगभग 1.414 के लिए मान्य है। अधिकांश पाठ्यपुस्तकें C=1.4 को सुरक्षित डिफ़ॉल्ट के रूप में सिखाती हैं।
ANDREA के पुरस्कार परिमाण
ANDREA प्रति-चरण हानि सुधारों को पुरस्कार के रूप में रिपोर्ट करता है। कच्चे सुधार लगभग 0.001 के आसपास होते हैं (हानि 4.521 से 4.520 तक गिरती है)। 1000x स्केलिंग फैक्टर (गतिविधि 78, पुरस्कार असाइनमेंट में कवर) के बाद, स्केल्ड पुरस्कार परिमाण में लगभग 1.0 पर आ जाते हैं। एक आर्म के इतिहास में औसत पुरस्कार 0.5 से 3.0 बैंड में स्थिर हो जाते हैं।
अब N=10000, n_k=100 के साथ C=1.4 पर अन्वेषण बोनस पर विचार करें:
1.4 sqrt(ln(10000) / 100) = 1.4 sqrt(9.21 / 100) = 1.4 * 0.303 = 0.425
0.425 इनाम बैंड के अंदर आता है। स्वीकार्य। अब n_k=10 (एक दुर्लभ आर्म):
1.4 sqrt(9.21 / 10) = 1.4 0.960 = 1.344
1.344 अधिकांश देखे गए mean_rewards से ऊपर आता है। अन्वेषण हावी होता है: दुर्लभ आर्म अपनी वास्तविक औसत के बावजूद जीत जाता है। कई स्रोतों और लंबे प्रशिक्षण रनों के साथ, यह शेड्यूल को कम-औसत आर्म्स से भर देता है।
समाधान: C=0.5
0.5 sqrt(9.21 / 10) = 0.5 0.960 = 0.480
0.480 अधिकांश पुरस्कार औसत से नीचे बैठता है। अन्वेषण अभी भी होता है (दुर्लभ आर्म्स को अभी भी बोनस मिलता है), लेकिन mean_reward नेतृत्व करता है। ANDREA अधिक शोषण करता है, कम अन्वेषण करता है, और अन्वेषण प्रभुत्व से बचता है।
ट्यूनिंग को इंजीनियरिंग के रूप में, सिद्धांत के रूप में नहीं
पाठ्यपुस्तक बाउंड [0, 1] में पुरस्कार मानती है। ANDREA के पुरस्कार लगभग [0, 5] में रहते हैं। स्थिरांक को स्केल करना स्थिरांक को पुरस्कार की परिमाण से जोड़ता है। एक ही एल्गोरिदम, कैलिब्रेटेड वातावरण।
निदान: अन्वेषण प्रभुत्व
आगामी
आपके पास क्या है
UCB1 उच्चतम ऊपरी विश्वास सीमा वाले आर्म को चुनता है। यह सीमा mean_reward (शोषण) को sqrt(ln(N) / n_k) के साथ जोड़ती है जिसे C (अन्वेषण) से स्केल किया जाता है। ANDREA C=0.5 ट्यून करती है क्योंकि प्रति-चरण पुरस्कार 0.5 से 3.0 की रेंज में हैं, & पाठ्यपुस्तक का 1.4 कम-औसत आर्म्स से शेड्यूल को भर देता है।
क्या बाकी है
Vanilla UCB1 एक समय में एक आर्म चुनता है। ANDREA प्रति चरण कई फोकस आर्म्स चुनता है, पहले रैंडम आर्म्स मिलाता है, & प्रत्येक चरण को 7 से 42 स्टेप्स तक रखता है। वह संरचना (गतिविधि 77: डाइस फेज़) UCB को शुरुआती विजेताओं पर अति-प्रतिबद्ध होने से रोकती है जबकि इसे प्रयास केंद्रित करने देती है।
रिवार्ड अTRIB्यूशन (गतिविधि 78) दिखाता है कि mean_reward(k) वास्तव में कहाँ से आता है। फ्लोर्स & एपॉक पेनल्टीज़ (गतिविधि 79) UCB आउटपुट पर सुरक्षात्मक नियमों की परतें जोड़ते हैं।
संदर्भ
- Auer, Cesa-Bianchi, Fischer (2002). "Finite-time Analysis of the Multiarmed Bandit Problem." Machine Learning, 47, 235-256.
- ANDREA whitepaper, धारा 3.1 और 3.4।