Bu, Multi-Armed Bandits serimizin dördüncü bölümünde, haydut problemini çözmek için kullanılabilecek Üst Güven Sınırı (UCB) algoritmasına bir göz atacağız.
Haydut problemine ve terminolojisine henüz aşina değilseniz, önce bu dizinin aşağıdaki gibi önceki bölümlerine bir göz atmak isteyebilirsiniz:
Bebek Robot alışveriş merkezinde kayboldu. Pekiştirmeli Öğrenmeyi kullanarak, annesine dönüş yolunu bulmasına yardımcı olmak istiyoruz. Bununla birlikte, onu aramaya bile başlamadan önce, her biri biraz farklı miktarda şarj sağlayan bir dizi prizden şarj etmesi gerekiyor.
Çok kollu haydut probleminin stratejilerini kullanarak, Bebek Robot'un şarj olmasını ve yoluna devam etmesini sağlamak için en kısa sürede en iyi soketi bulmamız gerekiyor.
Baby Robot 5 farklı priz içeren şarj odasına girdi. Bu soketlerin her biri, biraz farklı bir miktar şarj döndürür. Baby Robot'u minimum sürede şarj etmek istiyoruz, bu yüzden en iyi soketi bulmalı ve şarj tamamlanana kadar kullanmalıyız.
Bu, Multi-Armed Bandit problemiyle aynıdır, tek fark, en iyi ödemeyi veren bir slot makinesi aramak yerine, en fazla şarjı veren bir priz arıyoruz.
En kısa sürede en fazla şarjı almaya çalıştığımız Güç Soketi probleminde, keşfetmeye, en iyi soketi aramak için harcadığımız zaman arasında bir değiş tokuş olduğunu gördük. Şu anda en iyi getiriyi sağlayan soketi kullanmak için harcanan süre. Çok uzun süre araştırma yaparsak, zaten yüksek getiri gösteren soketleri kullanma konusunda potansiyel olarak eksik kalırız. Alternatif olarak, iyi performans gösteren soketlerden yararlanırsak, o zaman en iyi soketi bulamayabilir ve potansiyel olarak mümkün olan maksimum getiriyi elde etmeyi kaçırabiliriz.
Açıkçası en iyi yaklaşım, her seferinde en iyi soketi seçmek olacaktır ve bu, en uygun politika olarak bilinir . Başlangıçta hangi soketin en iyi olduğunu bilmediğiniz için, bu yaklaşımın aslında pratik olmadığı da açıktır. En iyisini bulmak için soketlerin nasıl performans gösterdiğini araştırmak için biraz zaman harcanması gerekir ve bu nedenle en iyi eylemi seçmek her zaman mümkün olmaz.
Optimal politika, sadece teorik olmasına rağmen, diğer politikaları değerlendirmek, optimal olmaya ne kadar yaklaştıklarını görmek için kullanılabilir. Optimal politika tarafından elde edilecek getiri ile test edilen politikanın fiilen elde ettiği getiri miktarı arasındaki fark pişmanlık olarak bilinir . Bu durumda, iade, soketlerden gelen ücret miktarıdır ve politika, denenecek soketleri seçmek için kullanılan yöntem veya stratejidir.
Gördüğümüz gibi, Epsilon-Greedy'nin doğrusal bir pişmanlığı var . Bu eylemlerden hangilerinin kötü eylemler olduğunu bilmek için yeterli bilgiyi edindikten çok sonra, tüm eylemler kümesini keşfetmeye devam eder.
Toplam ödülü maksimize etme açısından daha iyi bir yaklaşım, örneklemeyi zaman içinde en iyi performansı gösteren eylemlerle sınırlamak olacaktır. Üst Güven Sınırı (UCB) stratejisinin benimsediği kesin yaklaşım budur.
Sabit kalan bir olasılıkla seçilen rastgele bir eylemi seçerek keşif yapmak yerine, UCB algoritması, çevre hakkında daha fazla bilgi topladıkça keşif-sömürü dengesini değiştirir. Öncelikle keşfe odaklanmaktan, en az denenen eylemler tercih edildiğinde, bunun yerine sömürü üzerine yoğunlaşarak tahmini en yüksek ödülü alan eylemi seçmeye geçer.
UCB ile, ' Aₜ', ' t ' adımında seçilen eylem şu şekilde verilir:
nerede;
Sömürü:
UCB algoritmasının performansını araştırmak için test sistemimize başka bir soket sınıfı ekleyeceğiz. Bu test sisteminin tüm detayları, bu serinin 2. Bölümünde açıklanmıştır ve tüm kod, github havuzunda bulunabilir.
UCB soketinin, bir soketi değerlendirmek için kullandığı ölçüye belirsizlik eklemek için temel güç soketi sınıfını biraz değiştirmesi gerekir. Dolayısıyla, ' örnek ' işlevi artık tahmini ortalama ödülün toplamını ve soketin denenme sayısının ve geçerli zaman adımının bir işlevi olarak hesaplanan belirsizlik değerinin toplamını döndürür.
Soket test cihazı sınıfı, standart soket test cihazına geri döner, soketler sadece kendi örnekleme fonksiyonundan en büyük değeri döndüren sokete göre seçilir (yani epsilon-açgözlü algoritmanın rastgele örneklemesi artık gerekli değildir).
Test sistemimizi kullanarak UCB algoritmasının performansını analiz edebiliriz. Karşılaştırmayı basitleştirmek için standart setimizden sadece ilk 2 soketi aldık. Bu 2 soket, sırasıyla 6 ve 4 saniyelik şarj ortalama ödül değerlerine sahiptir. Keşif ve kullanım terimlerinin her birinin göreceli katkıları aşağıdaki grafikte açıkça görülebilir.
Burada dikkat edilmesi gereken ana noktalar şunlardır:
UCB grafiğinden bazı derinlemesine gözlemler aşağıdaki gibidir:
* Bir soket henüz denenmediyse soket belirsizlik değeri sonsuza ayarlanır ve bu, her eylemin başlangıç değerini almak için bir kez denendiği bir başlangıç hazırlama turunun gerçekleştirilmesine neden olur. Bu, daha sonra eylemler henüz denenmediğinde ve Nₜ (a) sıfıra eşit olduğunda, keşif teriminde sıfıra bölme hatalarını önler. Açıkçası bu, yalnızca 'k' olası eylemleri ' t ' zaman adımlarından daha az olduğunda uygulanabilir , aksi takdirde her eylemi denemek için yeterli zaman olmazdı.
* Hazırlama turu nedeniyle, grafik 2. adımda başlar. Her bir soketin seçilme sayısı, her çubuğun üstündeki sayı ile gösterilir. Böylece, 2. adımda, her soketin bir kez seçildiği görülebilir. Her soket aynı sayıda denendiğinden, belirsizlik teriminin katkısı her soket için aynıdır. Bununla birlikte, daha büyük ödül tahmini olan 'Q' nedeniyle, soket 1 en büyük toplam UCB değerine sahiptir ve bu nedenle argmax işlevi tarafından seçilir .
* 3. adımda, 1. yuva önceki zaman adımında seçilen yuvaydı, bu nedenle denenme sayısının sayısı 2'ye yükselir. Sonuç olarak, bu yuvanın belirsizlik terimi küçülür, bu nedenle kesintisiz mavi çubuk boyut olarak küçüldüğü görülebilir. Taranmış sarı çubuk da bu yuvanın örneklenmesi nedeniyle azalır ve gerçek yuva ödülü için daha iyi bir tahmin oluşturur.
Öte yandan, 2. yuva seçilmedi, bu nedenle ödül tahmini aynı kalıyor. Seçilme sayısı da aynı kalırken, zaman adımlarının sayısı artıyor, sonuç olarak belirsizlik teriminin boyutu artıyor, böylece kesintisiz yeşil çubuğun büyüdüğü görülebilir.
Bununla birlikte, soket 1 için UCB teriminin toplam boyutu, soket 2'ninkinden hala daha büyüktür, bu nedenle bir kez daha seçilen sokettir.
* Sonunda, 5. zaman adımında, soket 2'nin belirsizlik terimi, toplam UCB değerini soket 1'inkinden daha büyük yapacak kadar artmıştır ve bu nedenle, seçilen sokettir. Bu gerçekleştiğinde, tahmini ödül değeri gerçek ortalama ödüle yaklaşır, belirsizlik terimi küçülür ve tüm süreç yeniden başlar.
UCB algoritmasının bir dizi güven değeri üzerindeki davranışı aşağıda gösterilmiştir. Güven parametresi, keşif düzeyini kontrol eder. Basit Güç Soketi deneyimiz durumunda, aslında keşif seviyesi ne kadar yüksekse ortalama toplam ödül o kadar düşük olduğu görülebilir. Bunun nedeni, her bir soketin farklı bir değere ve sınırlı bir olası değer aralığına sahip olmasıdır, öyle ki diğer soketlerin aynı aralıkta değerler üretmesi olası değildir.
Sonuç olarak, basit deneyimizde, keşif aslında gereksiz gibi görünüyor. İlk hazırlama adımından sonra, UCB algoritması zaten optimum sokete kilitlendi ve bu bilgiden yararlanabildiğinde en iyi sonuçları üretiyor. Güven parametresinin değerini artırmak, ortalama toplam ödülü keskin bir şekilde azaltır ve bu azalma, algoritma rastgele aramadan daha iyi olmayana kadar devam eder.
Güven seviyesi arttıkça ortalama toplam ödülün değişiminin daha yakından incelenmesi aşağıda gösterilmiştir. Burada, ortalama toplam ödülün, bir güven parametresi sıfırdan yaklaşık 0.6 değerine kadar hafifçe arttığı ve ardından hızla düştüğü görülebilir. Bu nedenle, en iyi sonuçları elde etmek için küçük bir araştırma derecesi gereklidir.
Güven parametresi 0,6 değerine (yukarıda gösterildiği gibi maksimum ortalama toplam ödülü veren değer) ayarlanmış olarak her soketin ne sıklıkla seçildiğini analiz etmek, aşağıda gösterilen grafiği verir. Burada, ilk hazırlama turu sırasında, bir soketin belirsizliği henüz denenmemişse sonsuza ayarlandığında, her bir soketin ilk 5 zaman adımında tam olarak bir kez seçildiği görülebilir. Bu noktadan sonra en uygun soket (soket 4) zaten en iyi soket olarak tanımlanmıştır ve bu nedenle neredeyse kalan tüm denemeler için seçilmiştir.
Optimal eylemin hızlı bir şekilde tanımlanması ve yalnızca yüksek belirsizliğe sahip olduklarında diğer eylemlerin denenmesi nedeniyle, UCB yöntemi, Epsilon-Greedy yönteminde görülenden çok daha düşük bir pişmanlık düzeyi gösterir.
Aşağıdaki grafiklerde görülebileceği gibi, optimum ve gerçek ödüller neredeyse aynıdır (öyle ki, gerçek çizgi optimal çizgi tarafından gizlenir) ve pişmanlık neredeyse düzdür.
Pişmanlığın büyük çoğunluğu, her soketin ilk tahminini almak için bir kez denendiği ilk hazırlama turu sırasında meydana gelir. Aslında, UCB'nin beklenen kümülatif pişmanlığının , toplam zaman adımı sayısı olan ' T'de logaritmik olduğu gösterilmiştir .
Genel olarak UCB pişmanlığı ve UCB'nin derinlemesine incelenmesi için aşağıdaki kaynakları inceleyin:
Soket Seçimi veya Çok Silahlı Haydut gibi problemlerde, en iyi getiriyi sağlayan eylemleri aramakla zaten bulunmuş olanları kullanmak arasında nasıl bir denge kurulacağı ikilemi ile karşı karşıya kaldığında, bir yaklaşım kullanmak önemlidir. keşif ve kullanım düzeylerini değiştirebilen.
Epsilon-Greedy algoritmasında gördüğümüz gibi, zaman ilerledikçe tüm eylemler kümesini keşfetmeye devam ederek, sabit bir keşif düzeyini korur. Sonuç olarak, doğrusal bir pişmanlığa sahiptir. Elde ettiği ödül ile mümkün olan maksimum ödül arasındaki fark zamanla artmaya devam ediyor.
Öte yandan, Üst Güven Sınırı (UCB) algoritması, keşif ve kullanım düzeylerini değiştirir. Başlangıçta, mevcut eylemler hakkında çok az bilgiye sahip olduğunda ve yapılacak en iyi eylemlere olan güveni düşük olduğunda, denkleminin keşif kısmı, tüm olası eylemler kümesini araştırmasına neden olur.
Keşif ilerledikçe, her eylem tarafından verilen ödüller için daha iyi tahminler oluşturulur. Bu nedenle keşif seviyesi azaltılabilir ve bulunan iyi eylemlerin kullanımı artırılabilir. Yavaş yavaş algoritmanın odak noktası keşiften sömürü lehine değişir. Zaman ilerledikçe bu dengeyi değiştirerek, UCB algoritması pişmanlığını azaltır ve sonuç olarak Epsilon-Greedy'de görülenden çok daha düşük bir pişmanlık seviyesine ulaşabilir.
Bir sonraki bölümde, keşif ve sömürü arasında denge kurmaya yönelik daha sofistike bir yaklaşım olan Thompson Örneklemesine bir göz atacağız. Bunu kullanarak Baby Robot'u hemen şarj edeceğiz ve neredeyse hiç vakit kaybetmeden gitmeye hazır hale getireceğiz!
< Part 3: Bandit Algorithms
Zaman zaman bir veya iki kitap okumayı gerçekten çok isteyip de bir türlü okumaya başlayamayan insanlarla karşılaşıyoruz. Okuma motorlarını yeniden başlatmak isteyen yeni başlayan veya eski bir kepçe okuyucu olsun - başlamak her zaman zordur ve burada ele alacağımız şey bu.
Bir süredir MLOps ile ilgileniyorum. Bunu ilk önce makine öğrenimi mühendislerinden öğrendim ve o sırada doktora öğrencisi olduğum için varlığından haberdar değildim.
MIT Seçim Laboratuvarı'nda yüksek lisans araştırmacısı ve doktora derecesi olan Jesse Clark tarafından yazılmıştır.
Oakland, CA'da halka açık verileri kullanarak hava kalitesini tahmin etmek Google ve EDF, Oakland'daki hava kirliliğini haritalama çalışmalarını yayınladığında, bu çalışmanın sonuçları büyük ilgi gördü. Yayınladıkları veriler, hava kalitesinin Doğu ve Batı Oakland'daki şehir bloklarına göre nasıl değiştiğini gösteren ilk veri kümelerinden biriydi.
Daniel Fleck ve David Lubert ile yazılmıştır Dizimizin ilk blogu, bir veri bilimi projesini uygun şekilde değerlendirmek için Net Şimdiki Değer (NPV), İç Getiri Oranı (IRR) ve Karlılık Endeksi'ni (PI) kullanmaya odaklanacaktır. Ayrıca, bir veri bilimi metodolojisinin kullanılmasının, bu aynı ekonomik ölçütlerin girdilerini daha yüksek kaliteli değerlendirmeler geliştirmek için nasıl daha da iyileştirebileceğini tartışacağız.
Öz bileşimi ve SVD için yararlı olan doğrusal cebir temel kavramını anlayın Bu makalede, öz ayrıştırma veya tekil değer ayrıştırma (SVD) gibi matris çarpanlara ayırma yöntemlerini anlamanın ilginç bir yolu olan temel kavramını öğreneceksiniz. Tanımlar Temel, vektör uzaylarını (vektör setleri) tanımlamak için kullanılan bir koordinat sistemidir.