การสุ่มแบบทอมป์สัน

ตัวอย่างการใช้ การสุ่มแบบทอมป์สัน ในการจำลองการประเมินประสิทธิภาพของการรักษา

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

คำอธิบาย

พิจารณาชุดของบริบท $𝒳$ ชุดของการกระทำ $𝒜$ และรางวัลใน $ℝ$ เป้าหมายของผู้เล่นคือการเลือกการกระทำในบริบทต่าง ๆ เพื่อเพิ่มรางวัลสะสมให้ได้มากที่สุด โดยในแต่ละรอบ ผู้เล่นจะได้รับบริบท $x\in 𝒳$ เลือกการกระทำ $a\in 𝒜$ และได้รับรางวัล $r\in ℝ$ ซึ่งมีการกระจายตัวที่ขึ้นอยู่กับบริบทและการกระทำที่เลือก

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

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

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

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

4. ชุดข้อมูลการสังเกตในอดีต $𝒟=(x;a;r)$;

5. การกระจายตัวหลัง (posterior distribution) $P(\theta |𝒟)\propto P(𝒟|\theta )P(\theta )$ โดยที่ $P(𝒟|\theta )$ คือฟังก์ชันความน่าจะเป็น

การสุ่มแบบทอมป์สันประกอบด้วยการเลือกการกระทำ $a^{\ast }\in 𝒜$ ตามความน่าจะเป็นที่การกระทำนั้นจะเพิ่มรางวัลคาดหวังสูงสุด โดยเลือกการกระทำ $a^{\ast }$ ด้วยความน่าจะเป็น

$\int 𝕀[𝔼(r|a^{\ast },x,\theta )=\underset{a^{\prime }}{\max }𝔼(r|a^{\prime },x,\theta )]P(\theta |𝒟)d\theta ,$

โดยที่ $𝕀$ คือ ฟังก์ชันบ่งชี้ (indicator function)

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

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

ประวัติ

การสุ่มแบบทอมป์สันถูกอธิบายครั้งแรกโดย Thompson ในปี 1933 และถูกค้นพบอีกหลายครั้งอย่างอิสระในบริบทของปัญหาหลายแขนโจร (multi-armed bandit problems) โดยมีการพิสูจน์การลู่เข้าครั้งแรกสำหรับกรณีปัญหา bandit ในปี 1997 และการประยุกต์ใช้ครั้งแรกกับ กระบวนการตัดสินใจของมาร์คอฟ (Markov decision process) ในปี 2000

แนวทางที่เกี่ยวข้อง (ดู Bayesian control rule) ได้รับการเผยแพร่ในปี 2010 ในปีเดียวกัน ยังมีการแสดงให้เห็นว่าการสุ่มแบบทอมป์สันสามารถ แก้ไขตนเองในทันที (instantaneously self-correcting) ผลการลู่เข้าที่ไม่จำกัดสำหรับปัญหา contextual bandits ถูกตีพิมพ์ในปี 2011

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

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

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

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

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

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

การตั้งค่ามีดังนี้ ให้ $a_1,a_2,\dots ,a_T$ เป็นการกระทำของเอเจนต์จนถึงเวลา $T$ และ $o_1,o_2,\dots ,o_T$ เป็นการสังเกตที่เอเจนต์ได้รับจนถึงเวลา $T$ จากนั้นเอเจนต์จะออกการกระทำ $a_{T+1}$ ด้วยความน่าจะเป็น:

$P(a_{T+1}|\hat{a}1:T,o1:T),$

โดยที่สัญลักษณ์ "hat" $\hat{a}t$ หมายถึงว่า $a_t$ เป็นการแทรกแซงเชิงสาเหตุ (ดู Causality) ไม่ใช่การสังเกตธรรมดา หากเอเจนต์มีความเชื่อ $\theta \in \mathrm{\Theta }$ เกี่ยวกับพฤติกรรมของมัน กฎการควบคุมแบบเบย์จะกลายเป็น

$P(aT+1|\hat{a}1:T,o1:T)=\underset{\mathrm{\Theta }}{\int }P(a_{T+1}|\theta ,\hat{a}1:T,o1:T)P(\theta |\hat{a}1:T,o1:T),d\theta$,

โดยที่ $P(\theta |\hat{a}1:T,o1:T)$ เป็นการแจกแจงหลังการสังเกตพารามิเตอร์ $\theta$ ที่พิจารณาจากการกระทำ $a_{1:T}$ และการสังเกต $o_{1:T}$

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

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

การสุ่มแบบทอมป์สันและอัลกอริทึม UCB มีคุณสมบัติพื้นฐานร่วมกันที่สนับสนุนความน่าเชื่อถือทางทฤษฎีของทั้งสองวิธี กล่าวคือ ทั้งสองวิธีจัดสรรความพยายามในการสำรวจไปยังการกระทำที่อาจเป็นการกระทำที่เหมาะสมที่สุด และในแง่นี้ถือว่า "มองโลกในแง่ดี" การใช้คุณสมบัตินี้ ทำให้สามารถแปลงขอบเขตความเสียใจ (regret bounds) ที่กำหนดไว้สำหรับอัลกอริทึม UCB ไปเป็นขอบเขตความเสียใจแบบเบย์เซียน (Bayesian regret bounds) สำหรับการสุ่มแบบทอมป์สันได้ หรือรวมการวิเคราะห์ความเสียใจสำหรับทั้งสองวิธีนี้และหลายคลาสของปัญหาได้