Kollar, Çekişler ve Ödüller
Bir Sıra Slot Makinesi
K adet slot makinesinin yan yana dizildiğini hayal edin. Her makine farklı ortalama ödül verir, ancak bu ortalamaları bilmezsiniz. Her adımda bir makine seçer, kolunu çekersiniz ve bir ödeme alırsınız. Amacınız: çok sayıda çekiş boyunca toplam ödülü en üst düzeye çıkarmaktır.
Bu kurulum çok kollu kumar makinesi problemini tanımlar. K = kol sayısıdır. Bir çekiş, bir kolu seçmektir. Ödül, o kolun gizli dağılımından gelir. Kol k’nın mean_reward(k) değeri, o kola yapılan çekişlerin çalışan ortalamasını tutar.
Keşif vs Sömürü
İki baskı birbirine karşı çekişir:
Sömürü, en yüksek gözlemlenen mean_reward değerine sahip kolu çeker. Açgözlüdür. Risk: 2 çekişten sonra harika görünen bir kol, daha düşük gerçek ortalamaya gerileyebilir.
Keşif, belirsizliği azaltmak için daha az test edilmiş bir kolu çeker. Risk: keşfe harcanan zaman, bilinen iyi bir koldan toplanabilecek ödülü kaybettirir.
İyi bir politika ikisini de karıştırır. Saf sömürü (exploitation), erken kazananları sonsuza kadar kilitler. Saf keşif (exploration) ise hiçbir zaman kazanç elde edemez.
ANDREA'nın Kolları = Veri Kaynakları
ANDREA eğitimi bir bandit problemi olarak ele alır. Her veri kaynağı (hermes3-general, gutenberg, dictionary, synthetic-chat, smoltalk vb.) bir kol olarak davranır. Her eğitim adımında bir kol çekilir: o kaynaktan bir belge yüklenir, ileri geçiş yapılır ve kayıp azalması gözlemlenir. Her kaynağın ortalama ödülü, o kaynağın ortalama olarak kaybı ne kadar iyileştirdiğini takip eder.
Neden uyuyor: model eğitim sırasında değişen ihtiyaçlara sahiptir. Erken adımlar geniş maruziyetten (çok sayıda kaynaktan) yararlanır. Sonraki adımlar ise hedefli cilalamadan (birkaç yüksek ödüllü kaynaktan) yararlanır. Bir bandit uyum sağlar; sabit bir örnekleme oranı bunu yapamaz.
Parçaları Adlandırma
UCB1 Skoru
Auer, Cesa-Bianchi & Fischer, 2002
Peter Auer ve arkadaşları UCB1’i 2002’de sonlu zamanlı bir bandit politikası olarak yayınladı; pişmanlık sınırı O(log N) seviyesindedir. UCB1, bir kolu mevcut ortalama ödülü ile kol çekildikçe küçülen bir keşif bonusunu birleştirerek seçer.
Formül
UCB(k) = mean_reward(k) + C * sqrt(ln(N) / n_k)
Terim terim:
- mean_reward(k): kol k için gözlemlenen ortalama ödül (n_k çekiliş boyunca). Sömürü terimi.
- N: şu ana kadar tüm kollar için toplam çekiliş sayısı. Her adımda artar.
- n_k: yalnızca k kolunun çekiliş sayısı. Sadece k seçildiğinde artar.
- C: keşif sabiti. Standart ders kitabı değeri: 1.4 (sqrt(2)). ANDREA C=0.5 kullanır.
- sqrt(ln(N) / n_k): güven yarıçapı. Nadiren çekilen bir kol küçük n_k’ye sahip olur ve büyük bonus alır; sık çekilen bir kol büyük n_k’ye sahip olur ve küçük bonus alır.
Formülün Neden İşe Yaradığı
ln(N) yavaş büyür (logaritmik), bu yüzden pay toplam deneyimle yavaşça yükselir. Paydadaki n_k, belirli bir kol için kanıt biriktikçe terimi küçültür. Kare kök tepkisini yumuşatır, böylece tek bir az keşfedilmiş kolun sonsuza kadar baskın olmasını engeller.
Her adımda argmax_k UCB(k) ile seçim yapmak, her iki baskıyı da otomatik olarak dengeler. Epsilon parametresi, çizelge veya sıcaklık gerekmez. Matematik bunu halleder.
Bir UCB Skoru Hesapla
Neden C=0.5 Değil de 1.4
Ders Kitabı Değeri
Auer, Cesa-Bianchi & Fischer, ödüllerin [0, 1] aralığında olduğunu varsayarak bir pişmanlık sınırı türetir. Bu sınır C = sqrt(2) ≈ 1.414 için geçerlidir. Çoğu ders kitabı C=1.4’ü güvenli varsayılan değer olarak öğretir.
ANDREA’nın Ödül Büyüklükleri
ANDREA, her adımda kayıp iyileştirmelerini ödül olarak raporlar. Ham iyileştirmeler yaklaşık 0.001 civarındadır (kayıp 4.521’den 4.520’ye düşer). 1000x ölçekleme faktöründen sonra (aktivite 78’de ele alınmıştır, ödül atfı), ölçeklenmiş ödüller yaklaşık 1.0 büyüklüğünde olur. Bir kolun geçmişindeki ortalama ödüller 0.5 ile 3.0 arasında bir bantta yerleşir.
Şimdi C=1.4, N=10000, n_k=100 için keşif bonusunu düşünün:
1.4 sqrt(ln(10000) / 100) = 1.4 sqrt(9.21 / 100) = 1.4 * 0.303 = 0.425
0.425 ödül bandı içinde yer alıyor. Kabul edilebilir. Şimdi n_k=10 (nadir bir kol):
1.4 sqrt(9.21 / 10) = 1.4 0.960 = 1.344
1.344, gözlemlenen ortalama ödüllerin ÇOĞUNUN ÜZERİNDE yer alıyor. Keşif baskın: nadir kol, gerçek ortalaması ne olursa olsun kazanır. Çok sayıda kaynak ve uzun eğitim çalıştırmalarında bu durum, zamanlamayı düşük-ortalamalı kollarla doldurur.
Çözüm: C=0.5
0.5 sqrt(9.21 / 10) = 0.5 0.960 = 0.480
0.480, çoğu ödül ortalamasının altında kalır. Keşif hâlâ gerçekleşir (nadir kollar hâlâ bonus alır), ancak mean_reward öncülüğü ele alır. ANDREA daha fazla sömürü, daha az keşif yapar ve keşif baskınlığını önler.
Ayarlama: Teori Değil, Mühendislik
Ders kitabı sınırı, ödüllerin [0, 1] aralığında olduğunu varsayar. ANDREA'nın ödülleri yaklaşık [0, 5] aralığındadır. Sabiti ölçeklendirmek, sabiti ödül büyüklüğüne uyarlar. Aynı algoritma, kalibre edilmiş ortam.
Keşif Baskınlığını Teşhis Et
Sırada Ne Var
Neler Öğrendiniz
UCB1, en yüksek üst güven sınırına sahip kolu seçer. Sınır, mean_reward (sömürü) ile C ile ölçeklenmiş sqrt(ln(N) / n_k) (keşif) bileşimidir. ANDREA, C=0.5 ayarlar çünkü adım başına ödüller 0.5 ile 3.0 bandındadır ve ders kitabı değeri 1.4 düşük-ortalamalı kolları programa taşır.
Kalanlar
Vanilla UCB1 her seferinde tek bir kolu seçer. ANDREA her fazda birden fazla odak kolu seçer, önce rastgele kolları karıştırır ve her fazı 7 ila 42 adım boyunca tutar. Bu yapı (aktivite 77: zar fazları) UCB’nin erken kazananlara aşırı bağlanmasını önlerken yine de çabasını yoğunlaştırmasına izin verir.
Ödül atfı (aktivite 78) mean_reward(k) değerinin aslında nereden geldiğini gösterir. Tabanlar ve dönem cezaları (aktivite 79) UCB çıktısının üzerine koruyucu kurallar ekler.
Referans
- Auer, Cesa-Bianchi, Fischer (2002). "Finite-time Analysis of the Multiarmed Bandit Problem." Machine Learning, 47, 235-256.
- ANDREA teknik raporu, bölüm 3.1 & 3.4.