Thompson örneklemesi

Adını William R. Thompson'dan alan Thompson örneklemesi, K-silahlı haydut probleminde keşif-sömürü ikilemini çözen eylemleri seçmek için sezgisel bir algoritmadır . Rastgele çizilmiş bir inanca kıyasla beklenen ödülü en üst düzeye çıkaran eylemi seçmekten ibarettir.

Tanım

Bir dizi bağlamı , bir dizi eylemi ve içindeki ödülleri düşünün . Her turda, oyuncu bir bağlam alır , bir eylem gerçekleştirir ve bağlama ve gerçekleştirilen eyleme bağlı bir dağıtımı takiben bir ödül alır . Oyuncunun amacı, birikimli kazançları en üst düzeye çıkaran eylemleri gerçekleştirmektir. X{\ displaystyle {\ mathcal {X}}}AT{\ displaystyle {\ mathcal {A}}}R{\ displaystyle \ mathbb {R}}x∈X{\ mathcal {X}}} içinde {\ displaystyle x \-de∈AT{\ mathcal {A}}} içinde {\ displaystyle a \r∈R{\ displaystyle r \ in \ mathbb {R}}

Thompson örneklemesinin unsurları aşağıdaki gibidir:

1. bir olasılık işlevi ;P(r|θ,-de,x){\ displaystyle P (r | \ theta, a, x)}
2. dağılımının bir dizi parametresi ;Θ{\ displaystyle \ Theta}θ{\ displaystyle \ theta}r{\ displaystyle r}
3. önsel dağılım ;P(θ){\ displaystyle P (\ theta)}
4. gözlemler ;D={(x;-de;r)}{\ displaystyle {\ mathcal {D}} = \ {(x; a; r) \}}
5. olabilirlik fonksiyonu nerede bir posteriori dağılım .P(θ|D)∝P(D|θ)P(θ){\ displaystyle P (\ theta | {\ mathcal {D}}) \ propto P ({\ mathcal {D}} | \ theta) P (\ theta)}P(D|θ){\ displaystyle P ({\ mathcal {D}} | \ theta)}

Thompson'ın örneklemesi , beklenen kazancın beklentisini en üst düzeye çıkaran oyunlardan oluşur : -de∗∈AT{\ mathcal {A}}} içinde {\ displaystyle a ^ {\ ast} \

∫ben[E(r|-de∗,x,θ)=max-de′E(r|-de′,x,θ)]P(θ|D)dθ,{\ displaystyle \ int \ mathbb {I} \ sol [\ mathbb {E} (r | a ^ {\ ast}, x, \ theta) = \ max _ {bir '} \ mathbb {E} (r | a ', x, \ theta) \ sağ] P (\ theta | {\ mathcal {D}}) d \ theta,}

gösterge işlevi nerede . ben{\ displaystyle \ mathbb {I}}

Uygulamada, bu kural, bir posteriori dağılımından gelen parametrelerin her dönüşünde örneklenerek ve örneklenen parametre, eylem ve mevcut bağlam dikkate alınarak beklenen kazanım beklentisini maksimize eden eylemi seçerek uygulanır. . Kavramsal olarak bu, oyuncunun inançlarını her dönüşte rastgele olarak somutlaştırdığı ve bu bilgilerden en iyi şekilde hareket ettiği anlamına gelir. Çoğu pratik uygulamada, bellekte tutmak ve kesin posterior dağıtımlardan örnek almak hesaplama açısından pahalıdır. Thompson örnekleme genellikle kaba örnekleme teknikleriyle kullanılır.θ∗{\ displaystyle \ theta ^ {\ ast}}P(θ|D){\ displaystyle P (\ theta | {\ mathcal {D}})}-de∗{\ displaystyle a ^ {\ ast}}E[r|θ∗,-de∗,x]{\ displaystyle \ mathbb {E} [r | \ theta ^ {\ ast}, a ^ {\ ast}, x]}

Tarih

Thompson örneklemesi 1933'te Thompson tarafından tanımlandı. Daha sonra, K silahlı haydut sorunları bağlamında bağımsız olarak defalarca yeniden keşfedildi. Haydutlara başvuru için ilk yakınsama kanıtı 1997'de sunuldu. Markov'un karar alma süreçlerine ilk başvuru 2000 yılına kadar uzanıyor. Bununla ilgili bir yaklaşım 2010'da yayınlandı. 2010'da, Thompson örneklemesinin otomatik olarak anında düzeldiği de gösterildi . Bağlamsal bilgi haydutları için asimptotik yakınsamayı gösteren sonuçlar 2011'de yayınlandı.

Günümüzde, Thompson örneklemesi birçok e-öğrenme probleminde yaygın olarak kullanılmaktadır: Thompson örneklemesi, web tasarımı ve çevrimiçi reklamcılıkta A / B testine de uygulanmıştır; Thompson örneklemesi, merkezi olmayan karar vermede hızlandırılmış öğrenmenin temelini oluşturur.

Diğer yaklaşımlarla bağlantılar

Olasılık eşleşmesi

Eşleşme olasılığı ( Olasılık eşleştirme ), üyelik tahmin sınıfının temel sınıf oranlarıyla orantılı olduğu bir politika kararıdır. Thompson'ın örneklemesi, bu genel ilkenin haydut sorununa bir uygulamasıdır.

Bu nedenle, eğitimde vakaların% 60'ında olumlu ve% 40'ında olumsuz çekiliş gözlemlenirse, olasılık eşleştirme stratejisi kullanan gözlemci (etiketsiz örnekler için) bir sonucu tahmin edecektir. Vakaların% 60'ında "pozitif" ve vakaların% 40'ında "negatif" sonuç.

Üst güven sınırı (UCB) algoritmaları

Thompson örnekleme algoritmaları ve üst güven sınırıyla ilgili algoritmalar "iyimser" algoritmalardır: parametrelerin tahminindeki belirsizliği hesaba katarlar ve optimal olma olasılığı sıfır olmayan bir olasılıkla eylemleri keşfederler.

Bu özelliği kullanarak, UCB algoritmaları için oluşturulan pişmanlık sınırlarını Thompson örneklemesi için Bayes pişmanlık sınırlarına çevirmek veya bu algoritmalar ve diğer problem sınıfları arasında pişmanlık analizini birleştirmek mümkündür.

Referanslar

1. Thompson, William R. "İki örneklemin kanıtı açısından bilinmeyen bir olasılığın diğerini geçme olasılığı üzerine" . Biometrika , 25 (3–4): 285–294, 1933.
2. Daniel J. Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband ve Zheng Wen (2018), "A Tutorial on Thompson Sampling", Foundations and Trends in Machine Learning: Cilt. 11: No. 1, sayfa 1-96. https://web.stanford.edu/~bvr/pubs/TS_Tutorial.pdf
3. J. Wyatt. Pekiştirmeden Öğrenmede Keşif ve Çıkarım . Doktora tezi, Yapay Zeka Bölümü, Edinburgh Üniversitesi. Mart 1997.
4. PA Ortega ve DA Braun. "Öğrenme ve Harekete Geçme İçin Minimum Göreceli Entropi İlkesi", Yapay Zeka Araştırmaları Dergisi , 38, sayfa 475–511, 2010.
5. MJA Strens. "Güçlendirmeli Öğrenme için Bayesçi Bir Çerçeve", Onyedinci Uluslararası Makine Öğrenimi Konferansı Bildirileri , Stanford Üniversitesi, California, 29 Haziran - 2 Temmuz 2000, http://citeseerx.ist.psu.edu/viewdoc/summary?doi= 10.1.1.140.1701
6. BC May, BC, N. Korda, A. Lee ve DS Leslie. "Bağlamsal haydut problemlerinde iyimser Bayes örneklemesi". Teknik rapor, İstatistik Grubu, Matematik Bölümü, Bristol Üniversitesi, 2011.
7. Chapelle, Olivier ve Lihong Li. "Thompson örneklemesinin ampirik bir değerlendirmesi." Sinirsel bilgi işleme sistemlerindeki gelişmeler. 2011. http://papers.nips.cc/paper/4321-an-empirical-evaluation-of-thompson-sampling
8. O.-C. Granmo. "Bayes Öğrenme Otomatı Kullanarak İki Kollu Bernoulli Haydut Problemlerini Çözmek", International Journal of Intelligent Computing and Cybernetics , 3 (2), 2010, 207-234.
9. Ian Clarke . "Orantılı A / B testi", 22 Eylül 2011, http://blog.locut.us/2011/09/22/proportionate-ab-testing/
10. OC Granmo ve S. Glimsdal , "  Goore Oyunu uygulamaları ile merkezi olmayan iki kollu haydut tabanlı karar verme için hızlandırılmış Bayes öğrenimi  ", Applied Intelligence ,2012( DOI  10.1007 / s10489-012-0346-z )
11. Daniel J. Russo ve Benjamin Van Roy (2014), "Posterior Örneklemeyle Optimize Etmeyi Öğrenmek", Mathematics of Operations Research, Cilt. 39, No. 4, s. 1221-1243, 2014. https://pubsonline.informs.org/doi/abs/10.1287/moor.2014.0650
12. Daniel J. Russo ve Benjamin Van Roy (2013), "Eluder Dimension and the Sample Complexity of Optimistic Exploration", Advances in Neural Information Processing Systems 26, s. 2256-2264. http://papers.nips.cc/paper/4909-eluder-dimension-and-the-sample-complexity-of-optimistic-exploration.pdf

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">