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 problemindeki stratejileri kullanarak, Bebek Robot'un şarj olmasını ve yoluna girmesini sağlamak için en kısa sürede en iyi soketi bulmamız gerekiyor.
Bu, Multi-Armed Bandits'in altı bölümlük serisinin üçüncü bölümüdür. Şimdiye kadar , Çözmeye çalıştığımız sorunu tanımladığımız ve tanımlamak için kullanacağımız temel kod bloklarının ayrıntılarını verdiğimiz Multi-Armed Bandits ve The Bandit Framework'te kullanılan Matematiksel Çerçeve ve Terminolojiyi ele aldık. ve sorunlu ortamı test edin.
Artık terminolojiye, notasyona ve test çerçevesine sahip olduğumuza göre, eksik olan tek şey, en iyi eylemi bulmak için farklı seviyelerde ödül veren eylemler arasından seçim yaparak haydut problemini çözebilen gerçek bir algoritmadır. Sonraki birkaç bölümde, karmaşıklığı artan bu tür birkaç algoritmaya bakacağız.
Başlamak için önce Haydut Problemini çözmek için en temel yaklaşımlardan bazılarına bir göz atacağız ve aşağıdaki algoritmaları inceleyeceğiz:
Bandit algoritmaları ve test çerçevesi için tüm kodlar github'da bulunabilir: Multi_Armed_Bandits
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.
Bir sokete her taktığımızda, bir miktar şarj şeklinde bir ödül alırız ve aldığımız her ödül, bir soketin gerçek çıktısının daha doğru bir tahminini hesaplamamıza izin verir. O zaman en yüksek tahmine sahip soketi seçersek, umarız bu mevcut en iyi soket olur.
En yüksek değere sahip eylem seçilirken, ' t ' adımında seçilen eylem aşağıdaki formülle ifade edilebilir:
" Argmax ", Qₜ (a) ' nın maksimize edildiği ' a ' eyleminin seçilmesini belirtir . ' Qₜ (a)' nın 't' adımındaki ' a ' eyleminin tahmini değeri olduğunu unutmayın , bu nedenle şu anda en yüksek tahmini değeri olan eylemi seçiyoruz .
Bu yaklaşımı benimserken, tahmini değeri en yüksek olan eylemi seçerken, “ açgözlülükle tercih ettiğiniz” söylenir ve birden fazla olabilen maksimum değerlere sahip eylemler “açgözlü eylemler” olarak bilinir.
Tüm bunlar kulağa iyi bir eylem seçmenin makul bir yolu gibi geliyor, ancak büyük bir kusur var: Açgözlü Algoritma eylemi en iyi tahminle seçmek istiyor, ancak bu tahminleri oluşturmak için hiçbir yol sunmuyor. Yalnızca mevcut bilgilerden yararlanır, ancak bu bilgileri oluşturmak için gereken keşiflerin hiçbirini yapmaz.
Sonuç olarak, açgözlü algoritma başlangıçta henüz denenmemiş ve bu nedenle gerçek değerleri hakkında hiçbir tahminde bulunmayan eylemler arasından seçim yapıyor. Ek olarak, iyi bir eylemin seçilmesi ihtimaline karşı, bunun en iyi eylem olduğuna dair bir garanti yoktur ve açgözlü algoritma artık seçilen eyleme kilitlenmiş olacağından, mevcut eylemi onaylamak için başka hiçbir eylem test edilmeyecektir. biri en iyisidir ya da değildir. Bu nedenle daha uzun vadeli getiri sağlayabilecek eylemler kaçırılacaktır.
Açgözlü Algoritmayı değiştirmenin, en uygun eylemi ararken mevcut eylemler kümesini keşfetmesini sağlamanın çok basit bir yolu, ilk eylem tahminlerini çok yüksek değerlere ayarlamaktır.
Güç soketi probleminde, eylem tahminleri sıfıra getirilirse, bir eylem yapılır yapılmaz, soketin en küçük şarj miktarını bile döndürdüğünü varsayarak, bu eylemin ortalama ödülü sıfırdan büyük olacaktır. Sonuç olarak, açgözlü algoritmanın gözünde, bu eylem diğerlerinden daha iyi olacak ve bu nedenle sonsuza kadar seçilen eylem olacaktır.
Bunun yerine eylem tahminleri, olası soket çıktılarının herhangi birinden daha yüksek bir değere başlatılırsa, bir soket ilk denendiğinde, ortalama ödülü azalır. Daha sonra, diğerlerinden daha düşük bir değer tahminine sahiptir ve bu nedenle bir sonraki adımda seçilmez. Bu, her soketin ilk ' k ' zaman adımlarında denenmesine neden olur (' k ', soket sayısıdır).
Bu algoritmayı uygularsak, tam olarak neler olduğunu görebiliriz:
Dolayısıyla, yukarıdaki kodda, Bölüm 2'de tanımladığımız standart PowerSocket sınıfından yeni bir OptimisticPowerSocket türetiyoruz . Tek fark, soketin ödül değerinin tahmini olan " Q " nun, sağlanan bir ilk tahmin değerine başlatılması ve bu soketin denenme sayısı olan " n " nin 1 olarak ayarlanmasıdır. başlatma.
Soket tahminlerimizi mümkün olan maksimum ödül değerinden biraz daha yüksek bir değere başlatırsak, bu, hangi soketin en yüksek ödülü verdiğini keşfetmek çok uzun sürmeden erken zaman adımlarında araştırmayı teşvik etmelidir.
Her soket için ödül dağılımının Keman Grafiğine dönüp bakıldığında, en yüksek çıktı yaklaşık 16 saniyelik şarjdır. Bu nedenle, mümkün olan maksimum ödülden biraz daha yüksek olan 20 değerini seçtik ve aşağıdaki tabloda gösterildiği gibi tüm yuva tahminlerini buna göre başlattık.
Tablo 1, 20 zaman adımında alınan 5 soketin her biri için ödül tahminlerini göstermektedir. Sarıyla vurgulanan hücreler, her adımda seçilen soketi gösterir. Bundan dikkat edilmesi gereken noktalar şunlardır:
Yukarıdaki grafikten, İyimser Açgözlü algoritmasının oldukça iyi çalıştığı görülebilir. Optimal olmayan eylemlerin atılması ve odak noktasının optimum eyleme dönmesi çok uzun sürmez; bu, en kısa miktarda maksimum şarj miktarını alacaksak yapmak istediğimiz eylemdir. zamanın.
Bununla birlikte, deneyimizle ilgili birkaç sorun var:
Yukarıdaki grafiklerde birkaç nokta var:
Diğer bir büyük dezavantaj, keşfin ilk zaman adımlarıyla sınırlı olması ve kullanımını , her eylem için ödüllerin asla değişmediği sabit problemlerle sınırlandırmasıdır . Devam eden keşif eksikliğinden dolayı eylem ödüllerinin zamanla değişebileceği durağan olmayan durumlar için uygun değildir .
Gördüğümüz gibi, saf bir Açgözlülük stratejisi, optimal olmayan bir soket seçme ve ardından bu seçime bağlı kalma riski çok yüksektir. Sonuç olarak, en iyi soket asla bulunamayacak.
Bu sorunun üstesinden gelmenin basit bir yolu, bir keşif unsuru tanıtmaktır. Epsilon-Greedy'nin yaptığı tam olarak budur:
Epsilon-Greedy stratejisini uygulama kodu aşağıda gösterilmiştir. Bunun, gerçek soketlerdeki bir değişiklik yerine mevcut soketler arasında seçim yapma şeklini değiştirerek soket test cihazı sınıfının davranışını değiştirdiğini unutmayın.
Her seferinde ' select_socket ' adımı çağrılır. Rastgele ' p ' değeri Epsilon'dan küçükse, rastgele bir eylem seçilecektir, aksi takdirde güncel tahmini ödülü en yüksek olan yuva seçilecektir.
Aşağıdaki grafiklere bakıldığında, ε değerinin soket probleminde keşfi ve kullanımı nasıl etkilediği görülebilir :
Soket seçimi probleminde, her adımda en iyi soket seçilirse mümkün olan maksimum ödül elde edilecektir. Optimal olmayan bir soket seçildiğinde, elde edilebilecek toplam olası ödül, bu teorik maksimumdan daha da azalır. Sonuç olarak, bu soketi seçtiğiniz için pişman oluyorsunuz ve bunun yerine en iyisini seçmiş olmayı diliyorsunuz. Pişmanlık teriminin ima ettiği gibi, optimal olmayan bir seçim yaptığınızı önceden bilmenin hiçbir yolu olmayabilir, ancak geriye dönüp baktığınızda hatanızın farkına varırsınız.
En iyi eylemi seçip seçmediğinizi önceden söylemek mümkün olmasa da, seçim politikanızın her adımda en iyi eylemin seçildiği optimum politikayla karşılaştırıldığında nasıl performans gösterdiğini hesaplayabilirsiniz. Bu iki politika ile elde edilen toplam ödüldeki fark, pişmanlığı temsil etmektedir.
En uygun eylem şu şekilde verilir:
En uygun eylem, her adımda seçildiğinde beklenen (ortalama) ödülü maksimize eden eylemdir.
Pişmanlık ' L ', uygulanan politika tarafından elde edilen ödül ile bunun yerine optimum politika izlenirse elde edilecek ödül arasındaki farkın toplam ' T ' zaman adımlarında alınmasıyla hesaplanır :
Bu nedenle, tüm ' T ' zaman adımları için optimum politika, her adımda optimum eylemi gerçekleştirirken elde edilen beklenen ödülü alır. Bundan, politikamız tarafından seçilen eylemlerden beklenen ödüllerin toplamını çıkarıyoruz; burada seçilen eylem ve dolayısıyla beklenen ödülü her adımda değişebilir.
Pişmanlığın değerini en aza indirerek, ödüllerin toplamını maksimize edebiliriz.
Epsilon-Greedy, olası eylemlerden herhangi birini rastgele ve ' ε ' olasılığı ile seçerek keşif uygular . Bu nedenle, ' T ' zaman adımları boyunca, eylemlerin ' ' T '' si rasgele seçilmiş olacaktır.
Ek olarak, soket seçimi probleminin genel bir biçiminde, seçilebilecek ' k ' farklı soket vardır ve bunlardan sadece biri mümkün olan maksimum ödülü verecektir. Kalan ' k-1' soketleri, optimumun altında bir ödül verecektir. Sonuç olarak, bir alt optimal soketin seçildiği ' εT (k-1) / k' turları vardır.
Eğer turlar sırasında, optimal olmayan eylem seçildiğinde, şanslı olursak ve bunun yerine ödülün en iyi soketten sabit bir 'Δ' (delta) kadar farklı olduğu ikinci en iyi soketi seçersek, bu bize şunu verecektir Epsilon-Greedy için mümkün olan en düşük pişmanlık. Bu şu şekilde verilir:
Optimal olmayan diğer tüm soketler için, elde edilen ödül ile en uygun ödül arasındaki fark 'Δ' değerinden daha yüksek olacaktır, dolayısıyla büyük veya eşittir işareti bu durumda daha büyük olacaktır.
'Ε', 'Δ' ve ' k ' tüm sabitler olduğundan, Epsilon-Greedy için ortaya çıkan en düşük sınırlar zamanla doğrusaldır (' T ' sadece sabit bir değerle çarpılacaktır). Bu, pişmanlığın, optimal eylem bulunduktan çok sonra da artmaya devam edeceği anlamına gelir.
Bu, aşağıda gösterilen Epsilon Greedy Regret grafiklerinde görülebilir. İlk birkaç adımdan sonra, Epsilon Greedy yöntemiyle elde edilen toplam birikmiş ödül doğrusal olarak artar. Bununla birlikte, hala meydana gelen rastgele keşif nedeniyle, bu artış oranı, optimum eylemin ödülünü biriktireceği orandan biraz daha azdır ve bu, pişmanlıkta zaman içinde doğrusal bir artışa neden olur. Çalışmanın erken aşamalarında ortaya çıkan pişmanlık oranının biraz daha yüksek olması, en iyi eylemin henüz tespit edilmemiş olmasından kaynaklanmaktadır ve bu nedenle bu zaman adımlarında alt-optimal bir soket seçilmesi daha olasıdır.
Multi-Armed Bandits'e bakışımızın bu bölümünde nihayet haydut sorununu çözmek için kullanılabilecek bazı algoritmaları araştırmamız gerekti.
Saf Açgözlü algoritması, olası eylem ödüllerine ilişkin bazı ilk bilgilere sahip olmadığı sürece, basit bir rastgele seçim yönteminden çok daha iyi sonuç vermez. Ancak, İyimser-Açgözlü’nin büyük başlangıç değerlerini kullanması veya Epsilon Greedy’in rastgele keşif yapma yaklaşımı gibi bazı küçük değişikliklerle, seçim performansı büyük ölçüde iyileştirilebilir.
Bununla birlikte, bu iyileştirmelerle bile, iade edilen toplam ödül hala optimalin çok altında. İyimser-Açgözlülük'ün performansı, ilk ödülleri için seçilen değerlere çok bağlıdır ve Epsilon Greedy , bu eylemlerden hangilerinin alınacak kötü eylemler olduğunu bilmek için yeterli bilgi edindikten çok sonra, tüm eylemleri keşfetmeye devam etmektedir. Sonuç olarak, Epsilon Greedy algoritmasının doğrusal pişmanlığa sahip olduğu gösterildi, burada geri dönen ödül ile en uygun ödül arasındaki fark zamanla doğrusal olarak artmaya devam etti.
Bu serinin geri kalan bölümlerinde, Haydut Problemini çözmek için daha gelişmiş birkaç yaklaşıma, yani Üst Güven Sınır algoritmasına ve Thompson Örneklemesine bir göz atacağız ; her ikisi de pişmanlık düzeyini düşürerek daha yüksek bir düzeyle sonuçlanır. dönüş. Bunları kullanarak Baby Robot'u çok kısa sürede şarj edeceğiz!
< Part 2: The Bandit Framework Part 4: UCB Bandit Algorithm >
Başlarken Daha önce hiç bir sıralama problemini çözmediyseniz, biraz bunaltıcı görünebilir. Hatta kendinize "Nereden başlayabilirim?" diye soruyor olabilirsiniz. Kendinizi bu konumda bulursanız, bu blog size bir ana sayfadaki bileşenlerin sıralamasını kademeli haydutlar kullanarak nasıl optimize ettiğimizi gösterecek.
Takviyeli öğrenme, eylemlerinin sonuçlarından öğrenmek için algoritmaların kullanılmasını içeren bir makine öğrenimi türüdür. Bir robot veya bilgisayar programı gibi bir aracının, eylemleri için ödül veya ceza alarak davranışını optimize etmeyi öğrenebileceği fikrine dayanır.
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.