คำศัพท์/Thompson Sampling
Thompson Sampling คืออะไร?
Thompson Sampling คือกลยุทธ์ตัดสินใจซ้ำ ๆ ภายใต้ความไม่แน่นอน แทนที่จะลงมือตามค่าประมาณที่ดีที่สุดค่าเดียว ให้สุ่มค่าที่เป็นไปได้มาหนึ่งค่าจากช่วงของสิ่งที่อาจเป็นจริง แล้วลงมือเสมือนว่าค่านั้นถูก ทำแบบนี้ทุกรอบ ทางเลือกที่ระบบมั่นใจจะถูกเลือกสม่ำเสมอ เพราะช่วงของมันแคบ ทางเลือกที่ระบบยังไม่แน่ใจจะถูกเลือกเป็นบางครั้ง ตามสัดส่วนความเป็นไปได้ที่มันจะดี มันจึงถูกทดสอบโดยไม่มีใครต้องกันงบทดสอบไว้ เมื่อใช้กับการยิงแอด นี่คือวิธีที่ระบบให้งบแคมเปญที่พิสูจน์แล้วต่อไปพร้อมกับเรียนรู้แคมเปญใหม่ไปด้วย
01/สูตร
สูตร
ทุกรอบ: สุ่มชุดพารามิเตอร์ที่เป็นไปได้มาหนึ่งชุดจาก posterior เลือกการกระทำที่ดีที่สุดถ้าค่าที่สุ่มมานั้นเป็นจริง posterior แคบ → ได้การกระทำเดิมแทบทุกรอบ (ทำกำไร) posterior กว้าง → การกระทำหลากหลายข้ามรอบ (สำรวจ)
ตัวอย่าง
แคมเปญ Shopee ตัวใหม่ที่มีข้อมูลสามวัน อัตราออเดอร์ต่อวันที่เป็นไปได้ กินช่วงตั้งแต่ใกล้ศูนย์ไปจนสูงกว่าค่าเฉลี่ยของบัญชีมาก บางรอบสุ่มได้ค่ามองโลกในแง่ร้าย มันจะได้งบขั้นต่ำ บางรอบสุ่มได้ค่ามองโลกในแง่ดี มันจะได้งบเต็ม ผ่านไปสองสัปดาห์ ช่วงแคบลง และงบก็นิ่งอยู่ที่ระดับที่มันเป็นจริง
02/รายละเอียด
การสำรวจแก้ปัญหาอะไร?
ปัญหาที่ระบบปรับตัวเองจนกลายเป็นคนไม่รู้อะไรเลย การให้งบตัวที่ดูดีที่สุดตอนนี้เสมอแปลว่าไม่มีวันได้หลักฐานที่จะเผยว่ามีตัวที่ดีกว่า และในการยิงแอดเรื่องนี้กัดแรง เพราะแคมเปญ สินค้า หรือคีย์เวิร์ดใหม่เริ่มต้นด้วยประวัติที่ดูแย่กว่าตัวที่อยู่มานานเสมอ คือมันไม่มีประวัติเลย ระบบจัดสรรที่โลภล้วนจึงฆ่าแคมเปญใหม่ก่อนที่มันจะผลิตข้อมูลพอให้ตัดสิน และค่อย ๆ กระจุกงบทั้งหมดไว้กับอะไรก็ตามที่บังเอิญเวิร์กก่อน การสำรวจคือการแก้ และเหตุผลที่ทำด้วยการสุ่มแทนการกันงบทดสอบตายตัวคือการสุ่มใช้ความพยายามสำรวจตามสัดส่วนความเป็นไปได้ที่ตัวเลือกนั้นจะดีจริง
ทำไมค่าที่สุ่มมาครั้งเดียวถึงผิดได้มาก?
เพราะการสุ่มจากช่วงที่กว้างตกลงตรงไหนก็ได้ในช่วงนั้น บนแคมเปญที่แทบไม่มีข้อมูล รอบติด ๆ กันให้ค่าที่เหมาะสมต่างกันสุดขั้วได้ ใกล้ศูนย์วันหนึ่งและสูงมากอีกวันหนึ่ง และนั่นคือวิธีการที่ทำงานตามที่ออกแบบไว้ ไม่ใช่ความผิดพลาด อันตรายอยู่ที่ระบบที่อ่านค่ามองโลกในแง่ร้ายค่าเดียวว่าเป็นหลักฐานแล้วลงมือแบบย้อนกลับไม่ได้ กฎการออกแบบที่ตามมาจึงสำคัญ คือระหว่างที่แคมเปญยังอยู่ในโหมดสำรวจ ค่าที่สุ่มได้แย่คือเหตุผลให้สุ่มต่อที่งบขั้นต่ำ ไม่ใช่เหตุผลให้ปิดถาวร การหยุดแคมเปญที่ยังสังเกตได้ไม่พอคือการทำลายข้อมูลที่วิธีนี้มีไว้เก็บพอดี
แคมเปญควรเลิกสำรวจเมื่อไร?
เมื่อความไม่แน่นอนแคบพอที่จะเชื่อการกระจายทั้งก้อนได้ ณ จุดนั้นการลงมือตามค่าที่สุ่มมาค่าเดียวคือการทิ้งข้อมูล แคมเปญที่โตเต็มที่ได้ประโยชน์มากกว่าจากการปรับให้ดีที่สุดกับการกระจายผลลัพธ์ทั้งก้อน คือทั้งผลที่คาดหวังและหางด้านลบพร้อมกัน แทนที่จะปรับกับสถานการณ์ที่สุ่มมาอันเดียว ในทางปฏิบัติแปลว่าระบบต้องมีสองโหมดและกฎว่าจะเลื่อนขั้นเมื่อไร ซึ่งมักอิงจำนวนช่วงเวลาที่แคมเปญสะสมผลงานจริงมาแล้ว การใช้โหมดสำรวจกับแคมเปญที่โตเต็มที่เพิ่มความแกว่งโดยเปล่าประโยชน์ ส่วนการใช้โหมดโตเต็มที่กับแคมเปญใหม่ฆ่ามันเร็วเกินไป
03/ทำไมจึงสำคัญ
กับดักในหนึ่งย่อหน้า
ทุกบัญชีโฆษณาเจอการแลกแบบเดียวกัน ระหว่างการให้งบสิ่งที่รู้ว่าเวิร์กกับการหาว่ามีอะไรอีกที่อาจเวิร์ก ถ้าจัดการด้วยสัญชาตญาณ มันมักยุบลงเป็นหนึ่งในสองความล้มเหลว คือไม่เคยทดสอบอะไรใหม่เลย หรือทดสอบไปเรื่อยโดยไม่เคยได้ข้อสรุป การสุ่มตามสัดส่วนความไม่แน่นอนแก้เรื่องนี้ให้เองโดยอัตโนมัติ และเป็นเหตุผลที่ระบบจัดสรรที่สร้างมาดีจะเก็บงบก้อนเล็กไว้กับแคมเปญที่ตอนนี้ดูธรรมดา แทนที่จะย้ายทุกบาทไปให้ตัวที่นำอยู่
ข้อผิดพลาดที่พบบ่อย
อ่านงบของแคมเปญใหม่ที่ขยับไปมารายวันว่าเป็นความไม่เสถียร บนแคมเปญที่ยังสังเกตได้ไม่พอ ความแกว่งนั้นคือการสำรวจที่กำลังทำงาน สิ่งที่ควรตรวจไม่ใช่ว่างบขยับไหม แต่คือแคมเปญถูกสั่งหยุดถาวรจากค่าที่สุ่มได้แย่ครั้งเดียวหรือเปล่า นั่นคือความล้มเหลวจริง
04/ใน DataGlass
Thompson Sampling ถูกใช้ใน DataGlass อย่างไร
DataGlass ปฏิบัติกับ campaign บน Shopee ที่ยังสังเกตได้ไม่พอต่างจากตัวที่โตเต็มที่ ระหว่างที่ยังเรียนรู้อยู่ มันได้งบจากสถานการณ์ที่สุ่มมาและถูกตั้งพื้นไว้แทนการหยุดถาวร แล้วย้ายไปสู่การปรับกับการกระจายทั้งก้อนเมื่อสะสมประวัติผลงานมากพอ โหมดที่ campaign อยู่แสดงไว้บนคำแนะนำ
05/แหล่งอ้างอิง
- [1] Russo, Van Roy, Kazerouni, Osband และ Wen — A Tutorial on Thompson Sampling (arXiv:1707.02038)
เอกสารอ้างอิงมาตรฐานเรื่องการสุ่มจาก posterior สำหรับการตัดสินใจต่อเนื่อง รวมถึงเหตุผลที่การสุ่มตามสัดส่วนความไม่แน่นอนสมดุลการสำรวจกับการทำกำไร
- [2] Thompson sampling
พื้นฐานของวิธีนี้ ที่มาในฐานะทางแก้ของปัญหา multi-armed bandit และคุณสมบัติด้าน regret
คำศัพท์ที่เกี่ยวข้อง