أخذ عينات طومسون

الموسوعة الحرة
مثال عملي على استخدام أسلوب تومسون لأخذ العينات لمحاكاة تقييم فعالية العلاج

تُعدّ طريقة أخذ العينات من تومسون ، [ 1 ] [ 2 ] [ 3 ] نسبةً إلى ويليام راي تومسون ، أسلوبًا استدلاليًا لاختيار الإجراءات التي تعالج معضلة الاستكشاف والاستغلال في مسألة قطاع الطرق متعددي الأذرع . وتتمثل هذه الطريقة في اختيار الإجراء الذي يُعظّم المكافأة المتوقعة بناءً على اعتقاد مُختار عشوائيًا.

وصف

لنفترض مجموعة من السياقاتX{\displaystyle {\mathcal {X}}}مجموعة من الإجراءاتأ{\displaystyle {\mathcal {A}}}والمكافآت فيR{\displaystyle \mathbb {R} }يهدف اللاعب إلى تنفيذ الإجراءات في سياقات مختلفة، مثل تعظيم المكافآت التراكمية. تحديدًا، يحصل اللاعب في كل جولة على سياق معين.x∈X{\displaystyle x\in {\mathcal {X}}}، يقوم بعملأ∈أ{\displaystyle a\in {\mathcal {A}}}ويحصل على مكافأةر∈R{\displaystyle r\in \mathbb {R} }يتبع ذلك توزيع يعتمد على السياق والإجراء الصادر.

عناصر أخذ عينات طومسون هي كما يلي: [ 3 ] : القسم 4

  1. دالة الاحتمالP(ر|θ،أ،x){\displaystyle P(r|\theta ,a,x)}؛
  2. مجموعةΘ{\displaystyle \Theta }من المعلماتθ{\displaystyle \theta }توزيعر{\displaystyle r}؛
  3. التوزيع المسبقP(θ){\displaystyle P(\theta )}بناءً على هذه المعايير؛
  4. ثلاثيات الملاحظات السابقةد={(x؛أ؛ر)}{\displaystyle {\mathcal {D}}=\{(x;a;r)\}}؛
  5. توزيع خلفيP(θ|د)∝P(د|θ)P(θ){\displaystyle P(\theta |{\mathcal {D}})\propto P({\mathcal {D}}|\theta )P(\theta )}، أينP(د|θ){\displaystyle P({\mathcal {D}}|\theta )}هي دالة الاحتمال.

تتضمن عملية أخذ العينات من تومسون تشغيل الحركةأ*∈أ{\displaystyle a^{\ast }\in {\mathcal {A}}}وفقًا لاحتمالية تحقيق أقصى عائد متوقع؛ الإجراءأ*{\displaystyle a^{\ast }}يتم اختياره باحتمالية [ 3 ] : الخوارزمية 4

∫أنا[هـ(ر|أ*،x،θ)=الأعلىأ′هـ(ر|أ′،x،θ)]P(θ|د)دθ،{\displaystyle \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 ,}

أينأنا{\displaystyle \mathbb {I} }هي دالة المؤشر .

عمليًا، يتم تطبيق القاعدة عن طريق أخذ العينات. في كل جولة، يتم تحديد المعلمات.θ*{\displaystyle \theta ^{\ast }}يتم أخذ العينات من الخلفP(θ|د){\displaystyle P(\theta |{\mathcal {D}})}، [ 3 ] : 7 وفعلأ*{\displaystyle a^{\ast }}تم اختيارها لتحقيق أقصى قدر منهـ[ر|θ*،أ*،x]{\displaystyle \mathbb {E} [r|\theta ^{\ast },a^{\ast },x]}أي المكافأة المتوقعة بالنظر إلى المعلمات المأخوذة، والفعل، والسياق الحالي. من الناحية النظرية، يعني هذا أن اللاعب يُحدد معتقداته عشوائيًا في كل جولة وفقًا للتوزيع الاحتمالي اللاحق، ثم يتصرف على النحو الأمثل بناءً عليها. في معظم التطبيقات العملية، يُعد الحفاظ على التوزيع الاحتمالي اللاحق وأخذ عينات منه على النماذج أمرًا مُرهقًا حسابيًا. ولذلك، غالبًا ما تُستخدم طريقة أخذ عينات طومسون بالتزامن مع تقنيات أخذ العينات التقريبية. [ 3 ] : القسم 5

تاريخ

وُصفت طريقة أخذ العينات من نوع تومسون لأول مرة من قِبل تومسون عام 1933. [ 1 ] ثم أُعيد اكتشافها عدة مرات بشكل مستقل في سياق مسائل قطاع الطرق متعددي الأذرع. [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] وقد قُدِّم أول برهان على التقارب في حالة قطاع الطرق عام 1997. [ 4 ] وكان أول تطبيق لها على عمليات اتخاذ القرار ماركوف عام 2000. [ 6 ] ونُشر نهج ذو صلة (انظر قاعدة التحكم البايزية ) عام 2010. [ 5 ] وفي عام 2010، ثبت أيضًا أن طريقة أخذ العينات من نوع تومسون تُصحِّح نفسها تلقائيًا . [ 9 ] نُشرت نتائج التقارب التقاربي لخوارزمية قطاع الطرق السياقية في عام 2011. [ 7 ] استُخدمت خوارزمية أخذ عينات طومسون على نطاق واسع في العديد من مسائل التعلم عبر الإنترنت، بما في ذلك اختبار A/B في تصميم مواقع الويب والإعلان عبر الإنترنت، [ 10 ] والتعلم المُسرّع في اتخاذ القرارات اللامركزية. [ 11 ] اقتُرحت خوارزمية أخذ عينات طومسون المزدوجة (D-TS) [ 12 ] لخوارزمية قطاع الطرق المتنافسين ، وهي نوع مُعدّل من خوارزمية MAB التقليدية، حيث تأتي التغذية الراجعة على شكل مقارنة ثنائية.

العلاقة بالأساليب الأخرى

مطابقة الاحتمالات

تُعدّ مطابقة الاحتمالات استراتيجيةً لاتخاذ القرار، حيث تتناسب تنبؤات انتماء الفئة مع معدلاتها الأساسية. فعلى سبيل المثال، إذا لوحظت أمثلة إيجابية بنسبة 60% في مجموعة التدريب، وأمثلة سلبية بنسبة 40%، فإنّ المراقب الذي يستخدم استراتيجية مطابقة الاحتمالات سيتنبأ (بالنسبة للأمثلة غير المصنفة) بتصنيف "إيجابي" في 60% من الحالات، وتصنيف "سلبي" في 40% منها.

قاعدة التحكم البايزية

لقد ثبت أن تعميمًا لأسلوب أخذ العينات من نوع طومسون ليشمل بيئات ديناميكية وهياكل سببية عشوائية، والمعروف باسم قاعدة التحكم البايزية ، هو الحل الأمثل لمشكلة الترميز التكيفي مع الأفعال والملاحظات. [ 5 ] في هذه الصيغة، يُنظر إلى العامل على أنه مزيج من مجموعة من السلوكيات. فعندما يتفاعل العامل مع بيئته، يتعلم الخصائص السببية ويتبنى السلوك الذي يقلل من الإنتروبيا النسبية للسلوك الذي يُقدم أفضل تنبؤ لسلوك البيئة. إذا تم اختيار هذه السلوكيات وفقًا لمبدأ أقصى منفعة متوقعة، فإن السلوك التقاربي لقاعدة التحكم البايزية يتطابق مع السلوك التقاربي للعامل العقلاني تمامًا.

الإعداد كالتالي.أ1،أ2،...،أتي{\displaystyle a_{1},a_{2},\ldots ,a_{T}}تكون الإجراءات الصادرة عن الوكيل حتى وقت محددتي{\displaystyle T}ودعo1،o2،...،oتي{\displaystyle o_{1},o_{2},\ldots ,o_{T}}تكون الملاحظات التي جمعها الوكيل حتى وقت معينتي{\displaystyle T}ثم يقوم الوكيل بإصدار الإجراءأتي+1{\displaystyle a_{T+1}}باحتمالية: [ 5 ]

P(أتي+1|أ^1:تي،o1:تي)،{\displaystyle P(a_{T+1}|{\hat {a}}_{1:T},o_{1:T}),}

حيث تدوين "القبعة"أ^ت{\displaystyle {\hat {a}}_{t}}يدل على حقيقة أنأت{\displaystyle a_{t}}هو تدخل سببي (انظر السببية )، وليس مجرد ملاحظة عادية. إذا كان لدى الفاعل معتقداتθ∈Θ{\displaystyle \theta \in \Theta }عندئذٍ تصبح قاعدة التحكم البايزية هي التي تحدد سلوكياتها.

P(أتي+1|أ^1:تي،o1:تي)=∫ΘP(أتي+1|θ،أ^1:تي،o1:تي)P(θ|أ^1:تي،o1:تي)دθ{\displaystyle 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(θ|أ^1:تي،o1:تي){\displaystyle P(\theta |{\hat {a}}_{1:T},o_{1:T})}يمثل التوزيع الاحتمالي اللاحق على المعلمةθ{\displaystyle \theta }الإجراءات المعطاةأ1:تي{\displaystyle a_{1:T}}والملاحظاتo1:تي{\displaystyle o_{1:T}}.

عمليًا، تتمثل عملية التحكم البايزية في أخذ عينة، في كل خطوة زمنية، من معلمةθ*{\displaystyle \theta ^{\ast }}من التوزيع الخلفيP(θ|أ^1:تي،o1:تي){\displaystyle P(\theta |{\hat {a}}_{1:T},o_{1:T})}حيث يتم حساب التوزيع الاحتمالي اللاحق باستخدام قاعدة بايز من خلال النظر فقط في احتمالات المشاهدات (السببية).o1،o2،...،oتي{\displaystyle o_{1},o_{2},\ldots ,o_{T}}وتجاهل الاحتمالات (السببية) للأفعالأ1،أ2،...،أتي{\displaystyle a_{1},a_{2},\ldots ,a_{T}}ثم عن طريق أخذ عينة من الفعلأتي+1*{\displaystyle a_{T+1}^{\ast }}من توزيع الإجراءاتP(أتي+1|θ*،أ^1:تي،o1:تي){\displaystyle P(a_{T+1}|\theta ^{\ast },{\hat {a}}_{1:T},o_{1:T})}.

خوارزميات الحد الأعلى للثقة (UCB)

تشترك خوارزميات أخذ عينات طومسون وخوارزميات الحد الأعلى للثقة في خاصية أساسية تُشكل أساس العديد من ضماناتها النظرية. باختصار، تُخصص كلتا الخوارزميتين جهدًا استكشافيًا للإجراءات التي قد تكون مثالية، وهما بهذا المعنى "متفائلتان". بالاستفادة من هذه الخاصية، يُمكن ترجمة حدود الندم المُحددة لخوارزميات الحد الأعلى للثقة إلى حدود ندم بايزية لأخذ عينات طومسون [ 13 ] ، أو توحيد تحليل الندم عبر كلتا الخوارزميتين والعديد من فئات المشكلات. [ 14 ]

مراجع

  1. 1 2 تومسون، ويليام ر. "حول احتمال أن يتجاوز احتمال غير معروف احتمالًا آخر في ضوء الأدلة المستمدة من عينتين" . Biometrika ، 25(3–4):285–294، 1933.
  2. ↑ تومسون، دبليو آر (1935). حول نظرية التوزيع. المجلة الأمريكية للرياضيات ، 57(2)، 450-456.
  3. 1 2 3 4 5 دانيال ج. روسو، بنجامين فان روي، عباس كازيروني، إيان أوسباند، وتشنغ وين (2018)، "دليل تعليمي حول أخذ عينات طومسون"، أسس واتجاهات في تعلم الآلة: المجلد 11: العدد 1، الصفحات 1-96. https://web.stanford.edu/~bvr/pubs/TS_Tutorial.pdf
  4. 1 2 ج. وايت. الاستكشاف والاستدلال في التعلم من التعزيز . أطروحة دكتوراه، قسم الذكاء الاصطناعي، جامعة إدنبرة. مارس 1997.
  5. 1 2 3 4 PA Ortega و DA Braun. "مبدأ الحد الأدنى للإنتروبيا النسبية للتعلم والتصرف"، مجلة أبحاث الذكاء الاصطناعي ، 38، الصفحات 475-511، 2010، http://arxiv.org/abs/0810.3605
  6. 1 2 إم جيه إيه سترينز. "إطار بايزي للتعلم المعزز"، وقائع المؤتمر الدولي السابع عشر للتعلم الآلي ، جامعة ستانفورد، كاليفورنيا، 29 يونيو - 2 يوليو 2000، http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.140.1701
  7. 1 2 بي سي ماي، بي سي، إن. كوردا، إيه. لي، ودي إس ليزلي. "أخذ العينات البايزية المتفائلة في مسائل قطاع الطرق السياقية". تقرير فني، مجموعة الإحصاء، قسم الرياضيات، جامعة بريستول، 2011.
  8. ↑ شابيل، أوليفييه، ولي هونغ لي. "تقييم تجريبي لأخذ عينات طومسون". التطورات في أنظمة معالجة المعلومات العصبية. 2011. http://papers.nips.cc/paper/4321-an-empirical-evaluation-of-thompson-sampling
  9. 1 2 O.-C. Granmo. "حل مسائل قطاع الطرق برنولي ذات الذراعين باستخدام أتمتة التعلم البايزي"، المجلة الدولية للحوسبة الذكية وعلم التحكم الآلي ، 3 (2)، 2010، 207-234.
  10. ↑ كلارك، إيان (22 سبتمبر 2011). "الاختبار النسبي A/B" . مؤرشف من الأصل في 4 مايو 2013. تم الاسترجاع في 30 أبريل 2013 .
  11. ↑ غرانمو، أو سي؛ غليمسدال، إس. (2012). "التعلم البايزي المُسرَّع لاتخاذ القرارات اللامركزية القائمة على نموذج قطاع الطرق ذي الذراعين مع تطبيقات على لعبة غور". الذكاء التطبيقي . 38 (4): 479-488 . doi : 10.1007/s10489-012-0346-z . hdl : 11250/137969 . S2CID 8746483 . 
  12. ↑ وو، هواسن؛ ليو، شين؛ سريكانت، ر (2016)، أخذ عينات طومسون المزدوج لقطاع الطرق المتبارزين ، arXiv : 1604.07101 ، Bibcode : 2016arXiv160407101W
  13. ↑ روسو، دانيال جيه؛ فان روي، بنجامين (2014). "التعلم الأمثل عبر أخذ العينات اللاحقة". رياضيات بحوث العمليات . 39 (4): 1221-1243 . arXiv : 1301.2609 . doi : 10.1287/moor.2014.0650 .
  14. ↑ دانيال ج. روسو وبنيامين فان روي (2013)، "بعد المراوغ وتعقيد العينة للاستكشاف التفاؤلي"، التقدم في أنظمة معالجة المعلومات العصبية 26، ص 2256-2264. https://proceedings.neurips.cc/paper/2013/file/41bfd20a38bb1b0bec75acf0845530a7-Paper.pdf