ხელები, გაშეშუბლებები, ჯილდოები
სლოტ-მანქანების რიგი
წარმოიდგინეთ K სლოტ-მანქანა ერთმანეთის გვერდით. თითოეული მანქანა განსხვავებულ საშუალო ჯილდოს იხდის, მაგრამ არ იცით არც ერთი საშუალო. ყოველ ნაბიჯზე ირჩევთ ერთ მანქანას, უჭერთ მის როლს და აკვირდებით გადახდას. თქვენი მიზანი: მაქსიმალურად გაზარდოთ მთლიანი ჯილდო მრავალ გაშეშუბლებაში.
ეს კონფიგურაცია განსაზღვრავს მრავალხელსულ ბანდიტის პრობლემას. K = ხელების რაოდენობა. გაშეშუბლება ირჩევს ერთ ხელს. ჯილდო მოდის იმ ხელის ფარული განაწილებისგან. mean_reward(k) ხელ k-ის მიმდინარე საშუალოს აკონტროლებს მის გაშეშუბლებებში. [DESCRIPTION /]
ძიება vs ექსპლუატაცია
ორი ზეწოლა ერთმანეთის საწინააღმდეგოდ მუშაობს:
ექსპლუატაცია ირჩევს მკერძოებულად ყველაზე მაღალი საშუალო ჯილდოს მქონე მკერძოებას. მოთხოვნადი. რისკი: მკერძოება, რომელიც 2 გაჭერის შემდეგ შესანიშნავად გამოიყურებოდა, შეიძლება უკან დაიხევდეს უფრო დაბალ ნამდვილ საშუალოზე.
ძიება ირჩევს ნაკლებად გამოცდილ მკერძოებას გაურკვევლობის შესამცირებლად. რისკი: ძიებაზე დახარჯული დრო ჯილდოს ღირსეული ცნობილი მკერძოებისგან ჩამორთმევს.
კარგი პოლიტიკა ორივეს შერევას გულისხმობს. სუფთა ექსპლუატაცია ადრეულ გამარჯვებულებს სამუდამოდ ჩერდება. სუფთა ექსპლორაცია არასდროს იღებს შედეგს.
ANDREA-ს მკლავები = მონაცემთა წყაროები
ANDREA ტრენინგს ბანდიტად წარმოაჩენს. თითოეული მონაცემთა წყარო (hermes3-general, gutenberg, dictionary, synthetic-chat, smoltalk და ა.შ.) მოქმედებს როგორც მკლავი. თითოეული ტრენინგის ნაბიჯი იზიდავს ერთ მკლავს: იტვირთება დოკუმენტი იმ წყაროდან, ხორციელდება ფორვარდ გამოთვლა, შენიშნება ზარალის შემცირება. საშუალო შედეგი წყაროს მიხედვით აკონტროლებს იმას, თუ რამდენად აუმჯობესებს ეს წყარო ზარალს საშუალოდ.
რატომ შეხტომილია ეს: მოდელის საჭიროებები იცვლება ტრენინგის დროს. ადრეული ნაბიჯები სარგებლობს ფართო ხილვადობისგან (მრავალი წყარო). შემდგომი ნაბიჯები სარგებლობს სამიზნე გაპრიალებიდან (چند მაღალშედეგიანი წყარო). ბანდიტი ადაპტირდება; ფიქსირებული სემპლინგის თანაფარდობა ვერ.
ნაწილების დასახელება
UCB1 ქულა
Auer, Cesa-Bianchi & Fischer, 2002
პეტერ აუერმა და მისმა კოლეგებმა გამოაქვეყნეს UCB1 2002 წელს, როგორც შეზღუდული დროის ბანდიტის პოლიტიკა, რომელსაც აქვს მონატრევის ზღვარი O(log N). UCB1 ირჩევს მკლავს მისი მიმდინარე საშუალო ჯილდოს შეკომბინებით ექსპლორაციის ბონუსთან, რომელიც მცირდება მკლავის გადაწევის შემდეგ.
ფორმულა
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) ნელა იზრდება (ლოგარითმულად), ამიტომ მნიშვნელივნელი ნომერატორი ნელა იზრდება საერთო გამოცდილებასთან ერთად. 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-მდე ზოლში სტაბილიზდება.
ახლა განვიხილოთ კვლევის ბონუსი C=1.4-ით, N=10000, n_k=100-ით:
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 მდებარეობს უმეტეს შენიშნული საშუალო ჯილდოების ზემოთ. კვლევა დომინირებს: იშვიათი მკლავი იგებს მიუხედავად მისი ნამდვილი საშუალოსა. მრავალი წყაროსთან და გრძელ ტრენინგებთან ერთად, ეს ჩააგდებს გრაფიკს დაბალ-საშუალო მკლავებით.
გამოსწორება: C=0.5
0.5 sqrt(9.21 / 10) = 0.5 0.960 = 0.480
0.480 მდებარეობს უმეტეს შეჯახებულ საშუალო მაჩვენებლებზე. შესწავლა მაინც ხდება (იშვიათი მკლავები მაინც იღებენ ბონუსს), მაგრამ შეჯახებული საშუალო ლიდერობს. 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-ს ადრეული გამარჯვებულებზე გადაჭარბებულ ჩართულობაში, მაგრამ მაინც საშუალებას აძლევს ძალისხმევის კონცენტრაციას.
შეჯამებული ჯილდო (აქტივობა 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.