การชักตัวอย่างแบบทอมป์สัน

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

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

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

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

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

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

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

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

การชักตัวอย่างแบบทอมป์สันประกอบด้วยการเลือกการกระทำ a^\ast \in \mathcal{A} ตามความน่าจะเป็นที่การกระทำนั้นจะเพิ่มรางวัลคาดหวังสูงสุด โดยเลือกการกระทำ a^\ast ด้วยความน่าจะเป็น
:\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,
โดยที่ \mathbb{I} คือ ฟังก์ชันบ่งชี้ (indicator function)

ในทางปฏิบัติ กฎนี้ถูกใช้งานโดยวิธีการชักตัวอย่าง (sampling) ในแต่ละรอบ จะมีการชักตัวอย่างค่าพารามิเตอร์ \theta^\ast จากการกระจายตัวหลัง P(\theta|\mathcal{D}) และเลือกการกระทำ a^\ast ที่เพิ่มรางวัลคาดหวังสูงสุด \mathbb{E}[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, \ldots, a_T เป็นการกระทำของเอเจนต์จนถึงเวลา T และ o_1, o_2, \ldots, o_T เป็นการสังเกตที่เอเจนต์ได้รับจนถึงเวลา T จากนั้นเอเจนต์จะออกการกระทำ a_{T+1} ด้วยความน่าจะเป็น:
:P(a_{T+1}|\hat{a}{1:T}, o{1:T}),
โดยที่สัญลักษณ์ "hat" \hat{a}t หมายถึงว่า a_t เป็นการแทรกแซงเชิงสาเหตุ (ดู Causality) ไม่ใช่การสังเกตธรรมดา หากเอเจนต์มีความเชื่อ \theta \in \Theta เกี่ยวกับพฤติกรรมของมัน กฎการควบคุมแบบเบย์จะกลายเป็น
: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,
โดยที่ P(\theta|\hat{a}{1:T}, o{1:T}) เป็นการแจกแจงหลังการสังเกตพารามิเตอร์ \theta ที่พิจารณาจากการกระทำ a_{1:T} และการสังเกต o_{1:T}

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

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

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

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