الاستدلال البايزي لعمق المنافسة واحتمالية قلب النتائج غير الصفرية في التصنيف الزوجي

Maximilian Jerdee, Mark Newman

latex

مُلَخَّص

تقدم هذه الورقة منهجًا لاستنتاج عمق المنافسة واحتمالية قلب النتائج غير الصفرية في نماذج التصنيف الزوجي. نستخدم الاستدلال البايزي لتقدير هذه الكميات استنادًا إلى البيانات المرصودة من المباريات. ونظرًا لأن النماذج التقليدية لا تأخذ في الاعتبار تقلبات أداء المتنافسين، يوفر منهجنا تحسنًا ملحوظًا في دقة التنبؤات.

مُقَدِّمَة

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

النموذج

نقترح نموذجًا يعتمد على الاستدلال البايزي لتقدير عمق المنافسة واحتمالية قلب النتائج. يُعرّف عمق المنافسة بأنه مقياس لقرب مستويات الأداء بين المتنافسين، بينما تُعنى احتمالية قلب النتائج بمدى احتمال تغيّر النتائج المتوقعة جراء تقلبات الأداء.

تعريف النموذج

يتم تمثيل النموذج بالمعادلات التالية: \[\begin{aligned} P(A \text{ يَفُوز } B) &= \frac{1}{1 + e^{-(\alpha_A - \alpha_B)}}, \\ \alpha_i &= \mu + \sigma X_i,\end{aligned}\] حيث \(\alpha_A\) و\(\alpha_B\) هما معاملا الأداء للمتنافسين \(A\) و\(B\) على التوالي، و\(X_i\) متغير عشوائي يتبع التوزيع الطبيعي.

تقدير المعلمات

يُقدَّر المعلمان \(\mu\) و\(\sigma\) باستخدام البيانات المرصودة من المباريات، وذلك عبر الاستدلال البايزي. تُحدَّث المعتقدات حول هذه المعلمات استنادًا إلى البيانات الجديدة التي يتم جمعها، مما يسمح بتحسين التقديرات مع مرور الوقت.

التحقق من صحة النموذج

للتحقق من صحة النموذج، نجري تحليلاً تجريبيًا باستخدام بيانات من مسابقات رياضية حقيقية. نقارن النتائج التي يتنبأ بها النموذج مع النتائج الفعلية لتقييم دقته.

النتائج

تُظهر النتائج أن النموذج يتمتع بدقة تنبؤية عالية، خاصة في الحالات التي يكون فيها التقلب في الأداء مرتفعًا. وهذا يؤكد أهمية تضمين تقلبات الأداء في نماذج التصنيف الزوجي.

الخاتمة

يوفر نموذجنا إطارًا قويًا لفهم وتقدير عمق المنافسة واحتمالية قلب النتائج في التصنيف الزوجي. من خلال تضمين تقلبات الأداء، يمكن لنموذجنا تحسين دقة التنبؤات في مختلف السياقات التنافسية.

مُقَدِّمَة

عند دراسة نتائج المنافسات واختيارات المستهلكين والترتيبات الاجتماعية، غالبًا ما تكون هناك حاجة لتحويل المقارنات الزوجية بين مجموعة من العناصر إلى ترتيب كامل للمجموعة بأكملها. فقد يتنافس مجموعة من لاعبي الشطرنج في بطولة ويتم تسجيل الفوز والخسارة بينهم؛ أو قد تُسجل سلسلة من التفضيلات بين أزواج المنتجات في اختبارات A/B؛ أو قد يتقاتل سرب من الدجاج بينما يسجل الباحث من قام بالنقر على من. تدعو هذه البنية المتشابهة في السيناريوهات إلى استخدام أدوات مشتركة لاستنباط ترتيب أساسي للعناصر: لإيجاد أفضل لاعب شطرنج، وأكثر المنتجات جاذبية، وأعلى دجاجة (وفي الواقع لإيجاد الترتيب الكامل للنقرات). سنفضل الحديث عن اللاعبين الذين يتغلبون على بعضهم البعض في المباريات، رغم أن نفسها التقنيات تنطبق على مختلف الإعدادات.

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

على مدى القرن الماضي، تم تطوير مجموعة واسعة من النماذج والأساليب لهذه المهمة. في العديد من هذه النماذج، تبدأ القصة بتعيين كل لاعب \(i\) معامل "نقاط" أساسي \(s_i\) يعكس قوته - ميله للتغلب على اللاعبين الآخرين. ثم تفترض هذه النماذج أنه عندما يلعب اللاعب \(i\) ضد اللاعب \(j\)، تحدد النتيجة بقلب عملة مرجحة بشكل مستقل - يفوز اللاعب \(i\) بالاحتمال \(p_{ij} = f(s_i - s_j)\)، وهي دالة للفرق في نقاط اللاعبين. \(f\) دالة متزايدة أحادية؛ فإذا كان \(s_i > s_j\) (اللاعب \(i\) أفضل من اللاعب \(j\))، فإن اللاعب \(i\) أكثر عرضة للفوز. في هذا الإطار، يتم عادةً العثور على النقاط الأكثر احتمالًا لتوليد النتائج الملحوظة والإبلاغ عنها كتقديرات الاحتمال الأقصى لـ \(s_i\).

إذا كانت \(f\) هي الدالة السيجمويدية، فإننا نتحدث عن نموذج برادلي-تيري المستخدم على نطاق واسع (صُمم أصلاً من قبل زيرميلو). وإذا كانت \(f\) دالة التوزيع التراكمي الطبيعي، فإن هذا البناء ينتج نموذج ثورستون. بشكل عام، أي دالة \(f\) ضمن افتراضات بسيطة تنتج نموذجًا جديدًا للنظر فيه، وقد اقترح العديد منها. أُطلق على هذه النماذج اسم النماذج الخطية وفق تسميات ديفيد. (يشير Cattalan إلى أن هذا يعود إلى David 1988، إلا أن المصطلح لم يلقَ قبولًا واسعًا.)

في هذا التقليد، نقترح في هذه الورقة عائلة جديدة من النماذج، محددة باختيارات جديدة لدالة النقاط \(f\). تسمى هذه الفئة بتوسعات الدالة السيجمويدية، مما يعمم نموذج برادلي-تيري.

الجديد في اقتراحنا هو أن دوال النقاط المقترحة تسمح بضبط حدة قلب النتائج الديناميكي واستيعاب الاختلافات الزمنية في الأداء، مما يجعل النموذج أكثر مرونة للتطبيقات المتنوعة.

من بين هذه النماذج، نجد أن إعادة التعبير عن المعلمات بمتغيرات أكثر قابلية للتفسير فيزيائيًا مفيدة.

التحقق المتقاطع

على غرار ورقة SpringRank، سنقوم بإنتاج التوزيع التنبؤي اللاحق وتقييم أداء النموذج من خلال إجراء تحقق متقاطع متعدد الطيات.

النموذج

نموذج برادلي-تيري

لنفترض أننا نراقب مباريات بين \(n\) لاعبين. نمثل هذه المباريات بمصفوفة \(A\)، حيث يمثل العنصر \(A_{ij}\) عدد المرات التي يفوز فيها اللاعب \(i\) على اللاعب \(j\) لكل \(i, j = 1,\dots,n\). في سياق تنافسي، يمكن فهم هذه المصفوفة \(A\) كجدول للسجلات المباشرة بين اللاعبين الـ\(n\). ثم نرغب في استنتاج ترتيب العناصر الـ\(n\) استنادًا إلى هذه التفاعلات المسجلة.

سننظر في النماذج التوليدية التي تحدد احتمال ملاحظة مصفوفة التفاعل \(A\) بناءً على المعلمات الكامنة الحقيقية \(s_i\in\mathbb{R}\) لكل \(i=1,\dots,n\)، والتي تُعتبر "درجات القوة" لكل عنصر. بين كل زوج من العناصر، يُؤخذ الاحتمال الكامن للعناصر \(i\) و\(j\) بالفوز وفق فرق درجاتهم فقط: \(p_{ij}=f(s_i - s_j)\)، حيث \(s_{ij}\equiv s_i-s_j\). ثم يكون احتمال الملاحظة الكاملة:

\[\begin{aligned} P(A|\vec{s},f)&=\prod_{(i,j)}f(s_{ij})^{A_{ij}}, \end{aligned}\]حيث جمعنا الدرجات في المتجه \(\vec{s}\) وامتد الجداء على جميع أزواج العناصر \( (i,j)\) التي لها تفاعلات مسجلة (\(A_{ij}\neq0\)).

ينشأ نموذج برادلي-تيري (BT52) إذا اخترنا الدالة السيجمويدية كدالة درجاتنا:

\[\begin{aligned} f_{BT}(s)=\frac{1}{1+e^{-s}}. \end{aligned}\] وتؤدي اختيارات دوال أخرى إلى نماذج بديلة. على سبيل المثال، النموذج ثورستون ينشأ باختيار دالة التوزيع التراكمي الطبيعي:

\[\begin{aligned} f_{TH}(s)=\Phi(s). \end{aligned}\] في تحليلنا سنقدم تعميمًا لنموذج برادلي-تيري، مع أن طرقنا قابلة للتطبيق أيضًا على تعميم نموذج ثورستون.

بالنظر إلى التفاعلات الملحوظة \(A\) واختيار دالة الدرجات \(f\)، نعرف تقدير الاحتمال الأقصى (ML) للدرجات:

\[\begin{aligned} \vec{s}_{ML}=\arg\max_{\vec{s}}P(A|\vec{s},f). \end{aligned}\] ومع ذلك، يعاني هذا النهج من ضعف الاحتواء: إن لم تكن شبكة التفاعلات متصلة جيداً، فقد يتباعد تقدير الدرجات إلى مالانهاية.

تُعالَج هذه المشكلات بإدخال أولوية (سابقية) على الدرجات. أفكار عديدة طرحت لاختيار أولوية مناسبة لنموذج برادلي-تيري (Whelan17). في أولويتنا، تُسحب الدرجات بشكل مستقل من التوزيع الغاوسي القياسي:

\[\begin{aligned} P(\vec{s})=\prod_{i=1}^n\frac{1}{\sqrt{2\pi}}\exp\Bigl(-\frac{s_i^2}{2}\Bigr). \end{aligned}\]

مع هذه الأولويات، يمكن تعريف تقدير الحد الأقصى للملصق (MAP) للدرجات:

\[\begin{aligned} \arg\max_{\vec{s}}P(\vec{s}|A,f)=\arg\max_{\vec{s}}P(A|\vec{s},f)\,P(\vec{s}). \end{aligned}\] تجدر الإشارة إلى أن تقديرات ML للدرجات تمثل تقديرات MAP في حالة أولوية زائفة موحدة. كما يمكن الحصول على تقديرات متوقعة بعد الملصق (EAD) عبر توقع الدرجات تحت التوزيع اللاحق.

في تحليلنا، ندرس عائلة من الدوال \(f\) التي تحدد بالتالي عائلة من النماذج. لاختيار النموذج الأمثل لمجموعة بيانات معينة، نجري اختيار نموذج بايزي بمقارنة الأدلة البايزية لهذه النماذج:

\[\begin{aligned} P(A|f)=\int d\vec{s}\,P(A,\vec{s}|f) =\int d\vec{s}\,P(A|\vec{s},f)\,P(\vec{s}). \end{aligned}\] ثم نبحث عن:

\[\begin{aligned} f^*=\arg\max_fP(A|f). \end{aligned}\] هذا التحليل البايزي الكامل مكثف حسابيًا، لكن استخدام تقنيات مونت كارلو الهاملتونية الحديثة يوفر تقديرات متقاربة للأدلة البايزية لأغراضنا.

تعميمنا

قبل تعميم نموذج برادلي-تيري (الدالة السيجمويدية \(f_{BT}=1/(1+e^{-s})\))، نفكر في الخصائص اللازمة لأي دالة تقييم \(f\) أخرى. بما أن \(p_{ij}=f(s_i-s_j)\) تعبر عن احتمال فوز \(i\) على \(j\)، يجب أن يتحقق لكل \(s\in\mathbb{R}\):

\[\begin{aligned} 0\le f(s)\le1, \end{aligned}\]وعند غياب التعادلات، إما أن يفوز \(i\) أو \(j\)، فينبغي:

\[\begin{aligned} 1=p_{ij}+p_{ji}=f(s)+f(-s), \end{aligned}\]وبالتالي شرط التماثل:

\[\begin{aligned} f(-s)=1-f(s). \end{aligned}\] كما يُفضل أن تكون \(f\) دالة غير تناقصية لضمان تفسير سلس للفروق في المهارة.

التحسين

بمجرد اختيارنا للمعلمات الفائقة، يتحول اهتمامنا إلى إيجاد أفضل نموذج وفقًا لـ \(P(\eta,u|A)\). بعد تبسيط وتطبيق بعض الحيل التحليلية والمونت كارلو الهاملتوني، نحصل على تقديرات عملية لهذا الاحتمال اللاحق.

الدليل البايزي

هل من الممكن أداء التكامل داخل التوقع؟ أم لا أعتقد ذلك.

اختبار قيمة \(p\) على التوزيع التنبؤي اللاحق

لشبكة مراقبة معينة \(A\)، نرغب في حساب احتمالية ملاحظتنا للشبكة (أو شبكات أكثر احتمالًا) تحت التوزيع التنبؤي اللاحق لنموذجنا، أي:

\[\begin{aligned} P(\log P(\tilde{A}|A)<\log P(A|A)), \end{aligned}\]حيث تُسحب \(\tilde{A}\) من \(P(\tilde{A}|A)\).

يمكننا كتابة:

\[\begin{aligned} \log P(\tilde{A}|A) &=\log\Bigl[\int d\vec{s}\,d\alpha\,d\beta\;P(\tilde{A}|\vec{s},\alpha,\beta)\,P(\vec{s},\alpha,\beta|A)\Bigr]\\ &=\int d\vec{s}\,d\alpha\,d\beta\;\log P(\tilde{A}|\vec{s},\alpha,\beta)\;P(\vec{s},\alpha,\beta|A). \end{aligned}\]

التحقق من صحة العينات الخارجية

في هذا القسم، نقارن أداء نموذجنا مع مجموعة من النماذج الأخرى في أدبيات الترتيب الزوجي. نستخدم اختبار التحقق المتقاطع بخمس طيات: ندرب النماذج على 80% من البيانات ونختبرها على الـ20% المتبقية.

سنقيم النموذج بناءً على مقياسين رئيسيين. أولاً، في الإطار البايزي الكامل، أي نموذج يعظم التوزيع التنبؤي اللاحق \(P(A_{\text{test}}|A_{\text{train}})\):

\[\begin{aligned} P(A_{\text{test}}|A_{\text{train}}) &=\int d\vec{s}\,du\,dd\;P(A_{\text{test}}|\vec{s},u,d)\;P(\vec{s},u,d|A_{\text{train}})\\ &\equiv\Big\langle P(A_{\text{test}}|\vec{s},u,d)\Big\rangle_{\vec{s},u,d|A_{\text{train}}}. \end{aligned}\]

نقرب هذا بتوسط عينات من التوزيع اللاحق:

\[\begin{aligned} P(A_{\text{test}}|A_{\text{train}})\approx\frac{1}{N}\sum_{i=1}^N P(A_{\text{test}}|\vec{s}^{(i)},u^{(i)},d^{(i)}). \end{aligned}\]

ثم نجري مقارنة بين النماذج التالية:

النتائج

قيم العوامل المثلى

التأثير على التصنيفات

قارن النتائج وفق النماذج: Bradley–Terry (ML)، MAP والتنبؤ اللاحق، إلى جانب نماذج SpringRank.

التقريبات العملية

يتطلب الإطار البايزي الكامل حسابات مكثفة بسبب استخدام مونت كارلو الهاملتوني. في العديد من التطبيقات العملية، قد يكون من الصعب تنفيذه بسرعة مناسبة.

لا مفاجآت: \(u=0\)

يمكننا تقييم درجات الاحتمال الأقصى اللاحق بسرعة لنموذج برادلي-تيري المعتاد باستخدام الأولوية اللوجستية. ومن ثم نجري تقريبًا غاوسيًا للتوزيع اللاحق للمعامل \(\eta\).

تمتاز الألولويات التالية:

\[\begin{aligned} P(\vec{s}|\eta)&=\prod_i\frac{\Gamma(2\eta)}{\Gamma(\eta)^2}\Bigl[\frac{e^{-s_i}}{(1+e^{-s_i})^2}\Bigr]^\eta,\\ \log P(\vec{s}|\eta)&=\sum_i\Bigl[\log\frac{\Gamma(2\eta)}{\Gamma(\eta)^2}+\eta\log\frac{e^{-s_i}}{(1+e^{-s_i})^2}\Bigr],\\ P(\eta)&=e^{-\eta}. \end{aligned}\]

بواسطة قاعدة بايز:

\[\begin{aligned} P(\eta|A)&=\frac{P(\eta)\,P(A|\eta)}{P(A)} =\frac{P(\eta)}{P(A)}\int d\vec{s}\;P(A|\vec{s})\,P(\vec{s}|\eta). \end{aligned}\]

نوسع \(\log P(A,\vec{s}|\eta)\) حول نقطة السرج \(\vec{s}^*\) للحصول على تقريب غاوسي للتكامل.

دالة الخطوة: \(\eta=0\)

في الحالة المتطرفة \(\eta=0\)، يعادل نموذجنا تقريب الاحتمال الأقصى لنموذج برادلي-تيري. من منظور بازي، يُنظر إلى دالة النقاط وكأنها تقفز من \(u\) إلى \(1-u\).

يمكن التعبير عن احتمال المعلمات عند \(\eta=0\):

\[\begin{aligned} P(0,u|A) &\propto\int d\vec{s}\;P(A|\vec{s},u)\\ &\propto\sum_{\pi\in\mathfrak{S}_n}\prod_{(i,j)}\bigl[1_{\pi(i)<\pi(j)}\,u+1_{\pi(i)>\pi(j)}\,(1-u)\bigr]^{A_{ij}}\\ &\propto\sum_{\pi\in\mathfrak{S}_n}u^{m_{\pi,A}}(1-u)^{m-m_{\pi,A}}, \end{aligned}\]حيث \(m_{\pi,A}=\sum_{(i,j)}A_{ij}1_{\pi(i)<\pi(j)}\).

الأولوية الفائقة على \(d\)

يمكن اختيار أولوية أولية بسيطة لعمق اللعبة \(d>0\) مثل:

\[\begin{aligned} P(d)=e^{-d}. \end{aligned}\]

وصف مجموعة البيانات

في هذا القسم نصف بالتفصيل مجموعات البيانات المستخدمة في تحليلنا. جميعها متاحة للعامة وتشمل منافسات احترافية وإعدادات إلكترونية متنوعة.