ดูต้นฉบับสำหรับ การสุ่มแบบทอมป์สัน

[[File:Visualization of Thompson sampling.gif|thumb|350px|ตัวอย่างการใช้ การสุ่มแบบทอมป์สัน ในการจำลองการประเมินประสิทธิภาพของการรักษา]]

'''การสุ่มแบบทอมป์สัน'''<ref name="ref1"/><ref name="ref1b"/><ref name="FnTTutorial"/> ซึ่งตั้งชื่อตาม [[วิลเลียม อาร์. ทอมป์สัน]] เป็นวิธีการแบบ [[heuristic]] สำหรับการเลือกการกระทำที่แก้ปัญหาความสมดุลระหว่าง [[การสำรวจและการแสวงหาผลประโยชน์]] (exploration-exploitation dilemma) ในปัญหา [[multi-armed bandit]] โดยวิธีนี้จะเลือกการกระทำที่เพิ่มรางวัลคาดหวังสูงสุดตามความเชื่อที่ถูกสุ่มขึ้นมา

== คำอธิบาย ==
{{No footnotes|section|date=May 2012}}

พิจารณาชุดของบริบท <math>\mathcal{X}</math> ชุดของการกระทำ <math>\mathcal{A}</math> และรางวัลใน <math>\mathbb{R}</math> เป้าหมายของผู้เล่นคือการเลือกการกระทำในบริบทต่าง ๆ เพื่อเพิ่มรางวัลสะสมให้ได้มากที่สุด โดยในแต่ละรอบ ผู้เล่นจะได้รับบริบท <math>x \in \mathcal{X}</math> เลือกการกระทำ <math>a \in \mathcal{A}</math> และได้รับรางวัล <math>r \in \mathbb{R}</math> ซึ่งมีการกระจายตัวที่ขึ้นอยู่กับบริบทและการกระทำที่เลือก

องค์ประกอบของการสุ่มแบบทอมป์สัน ได้แก่:

1. ฟังก์ชันความน่าจะเป็น <math>P(r|\theta,a,x)</math>;


2. ชุดของพารามิเตอร์ <math>\Theta</math> ที่กำหนดการกระจายตัวของ <math>r</math>;


3. การกระจายตัวก่อนหน้า (prior distribution) <math>P(\theta)</math> สำหรับพารามิเตอร์เหล่านี้;


4. ชุดข้อมูลการสังเกตในอดีต <math>\mathcal{D} = {(x; a; r)}</math>;


5. การกระจายตัวหลัง (posterior distribution) <math>P(\theta|\mathcal{D}) \propto P(\mathcal{D}|\theta)P(\theta)</math> โดยที่ <math>P(\mathcal{D}|\theta)</math> คือฟังก์ชันความน่าจะเป็น



การสุ่มแบบทอมป์สันประกอบด้วยการเลือกการกระทำ <math>a^\ast \in \mathcal{A}</math> ตามความน่าจะเป็นที่การกระทำนั้นจะเพิ่มรางวัลคาดหวังสูงสุด โดยเลือกการกระทำ <math>a^\ast</math> ด้วยความน่าจะเป็น
:<math>\int \mathbb{I} \left[ \mathbb{E}(r|a^\ast,x,\theta) = \max_{a'} \mathbb{E}(r|a',x,\theta) \right] P(\theta|\mathcal{D}) d\theta,</math>
โดยที่ <math>\mathbb{I}</math> คือ [[ฟังก์ชันบ่งชี้]] (indicator function)

ในทางปฏิบัติ กฎนี้ถูกใช้งานโดยวิธีการสุ่ม (sampling) ในแต่ละรอบ จะมีการสุ่มค่าพารามิเตอร์ <math>\theta^\ast</math> จากการกระจายตัวหลัง <math>P(\theta|\mathcal{D})</math> และเลือกการกระทำ <math>a^\ast</math> ที่เพิ่มรางวัลคาดหวังสูงสุด <math>\mathbb{E}[r|\theta^\ast,a^\ast,x]</math> ซึ่งหมายความว่า ผู้เล่นจะสุ่มความเชื่อของตนในแต่ละรอบตามการกระจายตัวหลัง จากนั้นจึงกระทำตามที่เหมาะสมที่สุดกับความเชื่อนั้น

ในแอปพลิเคชันที่ใช้งานจริง การคำนวณและการสุ่มจากการกระจายตัวหลังอาจใช้ทรัพยากรสูง ดังนั้น การสุ่มแบบทอมป์สันมักใช้งานร่วมกับเทคนิคการสุ่มแบบประมาณค่า (approximate sampling techniques) <ref name="FnTTutorial"/>

== ประวัติ ==

การสุ่มแบบทอมป์สันถูกอธิบายครั้งแรกโดย Thompson ในปี 1933<ref name="ref1"/> และถูกค้นพบอีกหลายครั้งอย่างอิสระในบริบทของปัญหาหลายแขนโจร (multi-armed bandit problems)<ref name="ref2"/><ref name="ref5"/><ref name="ref6"/><ref name="ref4"/><ref name="ref3"/><ref name="ref7"/> โดยมีการพิสูจน์การลู่เข้าครั้งแรกสำหรับกรณีปัญหา bandit ในปี 1997<ref name="ref2"/> และการประยุกต์ใช้ครั้งแรกกับ [[กระบวนการตัดสินใจของมาร์คอฟ (Markov decision process)]] ในปี 2000<ref name="ref6"/>

แนวทางที่เกี่ยวข้อง (ดู [[#Bayesian control rule|Bayesian control rule]]) ได้รับการเผยแพร่ในปี 2010<ref name="ref5"/> ในปีเดียวกัน ยังมีการแสดงให้เห็นว่าการสุ่มแบบทอมป์สันสามารถ ''แก้ไขตนเองในทันที'' (instantaneously self-correcting)<ref name="ref7"/> ผลการลู่เข้าที่ไม่จำกัดสำหรับปัญหา contextual bandits ถูกตีพิมพ์ในปี 2011<ref name="ref4"/>

การสุ่มแบบทอมป์สันถูกนำไปใช้ในปัญหาการเรียนรู้ออนไลน์ต่าง ๆ อย่างแพร่หลาย รวมถึงการทดสอบ A/B ในการออกแบบเว็บไซต์และการโฆษณาออนไลน์<ref name="ref9"/> และการเร่งกระบวนการเรียนรู้ในกระบวนการตัดสินใจแบบกระจายศูนย์<ref name="ref8"/> นอกจากนี้ ยังมีการเสนออัลกอริทึม Double Thompson Sampling (D-TS)<ref name="Wu2016DTS"/> สำหรับ [[dueling bandit]] ซึ่งเป็นตัวแปรของปัญหา MAB แบบดั้งเดิม ที่ให้ข้อเสนอแนะในรูปของการเปรียบเทียบเป็นคู่ (pairwise comparison)

== ความสัมพันธ์กับวิธีการอื่น ๆ ==

===การจับคู่ความน่าจะเป็น===

{{See also|การจับคู่ความน่าจะเป็น}}

การจับคู่ความน่าจะเป็น (Probability matching) เป็นกลยุทธ์การตัดสินใจที่การทำนายการเป็นสมาชิกของคลาสสอดคล้องกับอัตราส่วนของคลาสในข้อมูลฝึกอบรม ตัวอย่างเช่น หากในชุดข้อมูลฝึกอบรมมีตัวอย่างที่เป็นบวก 60% และตัวอย่างที่เป็นลบ 40% ผู้สังเกตการณ์ที่ใช้กลยุทธ์การจับคู่ความน่าจะเป็นจะทำนายคลาส "บวก" สำหรับตัวอย่างที่ไม่ระบุ 60% และคลาส "ลบ" สำหรับ 40% ของตัวอย่าง

===กฎการควบคุมแบบเบย์ (Bayesian control rule)===

การขยายการสุ่มแบบทอมป์สันให้ครอบคลุมสภาพแวดล้อมแบบไดนามิกและโครงสร้างเชิงสาเหตุ เรียกว่า '''กฎการควบคุมแบบเบย์''' (Bayesian control rule) ซึ่งถูกแสดงให้เห็นว่าเป็นคำตอบที่เหมาะสมที่สุดสำหรับปัญหาการเข้ารหัสแบบปรับตัวที่มีการกระทำและการสังเกต<ref name="ref5"/> ในการกำหนดนี้ เอเจนต์ถูกมองว่าเป็นการผสมผสานระหว่างพฤติกรรมต่าง ๆ เมื่อเอเจนต์มีปฏิสัมพันธ์กับสภาพแวดล้อม มันจะเรียนรู้คุณสมบัติเชิงสาเหตุและเลือกใช้พฤติกรรมที่ลดค่าความเอนโทรปีสัมพัทธ์ (relative entropy) ไปยังพฤติกรรมที่คาดการณ์พฤติกรรมของสภาพแวดล้อมได้ดีที่สุด หากพฤติกรรมเหล่านี้ถูกเลือกตามหลักการของอรรถประโยชน์ที่คาดหวังสูงสุด พฤติกรรมของกฎการควบคุมแบบเบย์ในระยะยาวจะสอดคล้องกับพฤติกรรมของเอเจนต์ที่มีเหตุผลสมบูรณ์

การตั้งค่ามีดังนี้ ให้ <math>a_1, a_2, \ldots, a_T</math> เป็นการกระทำของเอเจนต์จนถึงเวลา <math>T</math> และ <math>o_1, o_2, \ldots, o_T</math> เป็นการสังเกตที่เอเจนต์ได้รับจนถึงเวลา <math>T</math> จากนั้นเอเจนต์จะออกการกระทำ <math>a_{T+1}</math> ด้วยความน่าจะเป็น:<ref name="ref5"/>
:<math>P(a_{T+1}|\hat{a}{1:T}, o{1:T}),</math>
โดยที่สัญลักษณ์ "hat" <math>\hat{a}t</math> หมายถึงว่า <math>a_t</math> เป็นการแทรกแซงเชิงสาเหตุ (ดู [[Causality]]) ไม่ใช่การสังเกตธรรมดา หากเอเจนต์มีความเชื่อ <math>\theta \in \Theta</math> เกี่ยวกับพฤติกรรมของมัน กฎการควบคุมแบบเบย์จะกลายเป็น
:<math>P(a{T+1}|\hat{a}{1:T}, o{1:T}) = \int_{\Theta} P(a_{T+1}|\theta, \hat{a}{1:T}, o{1:T}) P(\theta|\hat{a}{1:T}, o{1:T}) , d\theta</math>,
โดยที่ <math>P(\theta|\hat{a}{1:T}, o{1:T})</math> เป็นการแจกแจงหลังการสังเกตพารามิเตอร์ <math>\theta</math> ที่พิจารณาจากการกระทำ <math>a_{1:T}</math> และการสังเกต <math>o_{1:T}</math>

ในทางปฏิบัติ กฎการควบคุมแบบเบย์คือการสุ่มพารามิเตอร์ <math>\theta^\ast</math> จากการแจกแจงหลัง <math>P(\theta|\hat{a}{1:T}, o{1:T})</math> ในแต่ละช่วงเวลา โดยการแจกแจงหลังคำนวณโดยใช้กฎของเบย์โดยพิจารณาเฉพาะความน่าจะเป็นเชิงสาเหตุของการสังเกต <math>o_1, o_2, \ldots, o_T</math> และละเลยความน่าจะเป็นเชิงสาเหตุของการกระทำ <math>a_1, a_2, \ldots, a_T</math> จากนั้นสุ่มการกระทำ <math>a^\ast_{T+1}</math> จากการแจกแจงการกระทำ <math>P(a_{T+1}|\theta^\ast,\hat{a}{1:T},o{1:T})</math>

===อัลกอริทึม UCB (Upper-Confidence-Bound)===

การสุ่มแบบทอมป์สันและอัลกอริทึม UCB มีคุณสมบัติพื้นฐานร่วมกันที่สนับสนุนความน่าเชื่อถือทางทฤษฎีของทั้งสองวิธี กล่าวคือ ทั้งสองวิธีจัดสรรความพยายามในการสำรวจไปยังการกระทำที่อาจเป็นการกระทำที่เหมาะสมที่สุด และในแง่นี้ถือว่า "มองโลกในแง่ดี" การใช้คุณสมบัตินี้ ทำให้สามารถแปลงขอบเขตความเสียใจ (regret bounds) ที่กำหนดไว้สำหรับอัลกอริทึม UCB ไปเป็นขอบเขตความเสียใจแบบเบย์เซียน (Bayesian regret bounds) สำหรับการสุ่มแบบทอมป์สันได้<ref name="RussoVanRoy2014"/> หรือรวมการวิเคราะห์ความเสียใจสำหรับทั้งสองวิธีนี้และหลายคลาสของปัญหาได้<ref name="RussoVanRoy2013"/>
== อ้างอิง ==
{{Reflist|refs=
<ref name="ref1">
Thompson, William R. [https://www.dropbox.com/s/yhn9prnr5bz0156/1933-thompson.pdf "On the likelihood that one unknown probability exceeds another in view of the evidence of two samples"]. ''[[Biometrika]]'', 25(3–4):285–294, 1933.
</ref>
<ref name="ref1b">
Thompson, W. R. (1935). On the theory of apportionment. ''American Journal of Mathematics'', 57(2), 450-456.
</ref>
<ref name="ref2">
J. Wyatt. ''Exploration and Inference in Learning from Reinforcement''. Ph.D. thesis, Department of Artificial Intelligence, University of Edinburgh. March 1997.
</ref>
<ref name="ref3">
Chapelle, Olivier, and Lihong Li. "An empirical evaluation of Thompson sampling." Advances in neural information processing systems. 2011.
http://papers.nips.cc/paper/4321-an-empirical-evaluation-of-thompson-sampling
</ref>
<ref name="ref4">
B. C. May, B. C., N. Korda, A. Lee, and D. S. Leslie. "Optimistic Bayesian sampling in contextual-bandit problems". Technical report, Statistics Group, Department of Mathematics, University of Bristol, 2011.
</ref>
<ref name="ref5">
P. A. Ortega and D. A. Braun. "A Minimum Relative Entropy Principle for Learning and Acting", ''Journal of Artificial Intelligence Research'', 38, pages 475–511, 2010, http://arxiv.org/abs/0810.3605
</ref>
<ref name="ref6">
M. J. A. Strens. "A Bayesian Framework for Reinforcement Learning", ''Proceedings of the Seventeenth International Conference on Machine Learning'', Stanford University, California, June 29–July 2, 2000, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.140.1701
</ref>
<ref name="ref7">
O.-C. Granmo. "Solving Two-Armed Bernoulli Bandit Problems Using a Bayesian Learning Automaton", ''International Journal of Intelligent Computing and Cybernetics'', 3 (2), 2010, 207-234.
</ref>
<ref name="ref8">{{Cite journal | last1 = Granmo | first1 = O. C. | last2 = Glimsdal | first2 = S. | title = Accelerated Bayesian learning for decentralized two-armed bandit based decision making with applications to the Goore Game | doi = 10.1007/s10489-012-0346-z | journal = Applied Intelligence | volume = 38 | issue = 4 | pages = 479–488 | year = 2012 | hdl = 11250/137969 | s2cid = 8746483 | hdl-access = free }}
</ref>
<ref name="ref9">[[Ian Clarke (computer scientist)|Ian Clarke]].  "Proportionate A/B testing", September 22nd, 2011, http://blog.locut.us/2011/09/22/proportionate-ab-testing/ {{Webarchive|url=https://web.archive.org/web/20130504042611/http://blog.locut.us/2011/09/22/proportionate-ab-testing |date=2013-05-04 }}</ref>
<ref name="Wu2016DTS">
{{citation
 | arxiv       = 1604.07101| last1     = Wu
 | first1    = Huasen
 | last2     = Liu
 | first2    = Xin
 | last3     = Srikant
 | first3    = R
 | title     = Double Thompson Sampling for Dueling Bandits
 | year      = 2016
| bibcode= 2016arXiv160407101W}}
</ref>
<ref name="FnTTutorial">
Daniel J. Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband and Zheng Wen (2018), "A Tutorial on Thompson Sampling", Foundations and Trends in Machine Learning: Vol. 11: No. 1, pp 1-96. https://web.stanford.edu/~bvr/pubs/TS_Tutorial.pdf
</ref>
<ref name="RussoVanRoy2013">
Daniel J. Russo and Benjamin Van Roy (2013), "Eluder Dimension and the Sample Complexity of Optimistic Exploration", Advances in Neural Information Processing Systems 26, pp. 2256-2264. https://proceedings.neurips.cc/paper/2013/file/41bfd20a38bb1b0bec75acf0845530a7-Paper.pdf</ref>
<ref name="RussoVanRoy2014">{{cite journal
| last1=Russo | first1=Daniel J.
| last2=Van Roy | first2=Benjamin
| title=Learning to Optimize Via Posterior Sampling
| journal=[[Mathematics of Operations Research]]
| volume=39
| issue=4
| pages=1221–1243
| date=2014
| doi=10.1287/moor.2014.0650| arxiv=1301.2609
}}
</ref>
}}

<!--- Categories --->[[หมวดหมู่:วิศวกรรมปัญญาประดิษฐ์]]
[[หมวดหมู่:ขั้นตอนวิธีแบบศึกษาสำนึก]]
[[หมวดหมู่:วิธีการทางสถิติ]]
[[หมวดหมู่:การทดลองแบบต่อเนื่อง]]