مدل بردلی-تری

مدل برادلی-تری یک مدل احتمال برای نتیجه مقایسه‌های دوتایی بین آیتم‌ها، تیم‌ها یا اشیا است. با توجه به یک جفت آیتم i و j که از یک توزیع خاص گرفته شده است، این احتمال را تخمین می‌زند که مقایسه زوجی i > j درست باشد، این فرض به احتمال زیر صحیح است:

${\displaystyle P(i>j)={\frac {p_{i}}{p_{i}+p_{j}}}}$

(1)

بطوریکه p_i یک امتیاز عدد حقیقی مثبت است که به هر یک از iها اختصاص داده شده است. مقایسه i > j می‌توان به صورت " i به j ترجیح داده شده"، "رتبه i بالاتر از j است"، یا " i ,j را می‌زند " بسته به کاربرد، خواند و با استفاده از "قضاوت" امکان ارزیابی ذهنی را فراهم می‌کند.

به عنوان مثال، p_i ممکن است نشان دهنده مهارت یک تیم در یک تورنمنت ورزشی باشد و ${\displaystyle P(i>j)}$ به این معنای احتمال برد i در بازی مقابل j است.^[۱] یا p_i ممکن است نشان دهنده کیفیت یا مطلوبیت یک محصول تجاری باشد و ${\displaystyle P(i>j)}$ احتمال این است که مصرف‌کننده محصول i را بر محصول j ترجیح می‌دهد.

مدل بردلی-تری می‌تواند در جهت رو به جلو برای پیش‌بینی نتایج، همان‌طور که توضیح داده شد، استفاده شود، اما معمولاً به صورت معکوس برای استنتاج امتیازات p_i با توجه به مجموعه‌ای از نتایج مشاهده شده استفاده می‌شود. در این نوع کاربرد p_i نشان دهنده مقداری از قدرت یا کیفیت ${\displaystyle i}$ است و این مدل به ما امکان می‌دهد نقاط قوت را از یک سری مقایسه‌های زوجی تخمین بزنیم. به عنوان مثال، در بررسی ترجیحات شراب، ممکن است برای پاسخ دهندگان دشوار باشد که رتبه‌بندی کاملی از مجموعه بزرگی از شراب‌ها را ارائه دهند، اما برای آنها نسبتاً آسان است که جفت‌های نمونه شراب را با هم مقایسه کنند و بگویند که کدام یک از شراب‌ها بهتر است. بر اساس مجموعه‌ای از این مقایسه‌های زوجی، می‌توان از مدل بردلی-تری برای به دست آوردن رتبه‌بندی کامل شراب‌ها استفاده کرد.

هنگامی که مقادیر امتیاز p_i محاسبه شد، می‌توان از مدل در جهت رو به جلو نیز استفاده کرد، به عنوان مثال برای پیش‌بینی نتیجه احتمالی مقایسه‌هایی که هنوز واقعاً رخ نداده‌اند. به عنوان مثال، در مثال بررسی شراب، می‌توان احتمال ترجیح شراب ${\displaystyle i}$ بر شراب ${\displaystyle j}$ را محاسبه کرد، حتی اگر هیچ‌کس در نظرسنجی مستقیماً آن جفت خاص را مقایسه نکرده باشد.

تاریخچه و کاربردها

این مدل به افتخار رالف آ. بردلی و میلتون ای. تری،^[۲] که آن را در سال ۱۹۵۲ ارائه کردند، نامگذاری شده است،^[۳] اگرچه قبلاً توسط ارنست زرملو در دهه ۱۹۲۰ مورد مطالعه قرار گرفته بود.^[۱][۴][۵] کاربردهای این مدل شامل رتبه‌بندی رقبا در مسابقات ورزشی، شطرنج و سایر مسابقات،^[۶] رتبه‌بندی محصولات در نظرسنجی‌های مقایسه زوجی انتخاب مصرف‌کننده، تجزیه و تحلیل سلسله مراتب سلطه در جوامع حیوانی و انسانی،^[۷] رتبه‌بندی مجلات، رتبه‌بندی مدل‌های هوش مصنوعی،^[۸] و برآورد ارتباط اسناد در موتورهای جستجوی ماشینی و غیره است.

تعریف

مدل بردلی-تری را می‌توان به روش‌های مختلفی پارامتری کرد. معادله (1) شاید رایج‌ترین روش باشد، اما تعدادی دیگر نیز وجود دارد. بردلی و تری خود توابع امتیاز نمایی، ${\displaystyle p_{i}=e^{\beta _{i}}}$ ، را تعریف کرده‌اند به طوری که

${\displaystyle P(i>j)={\frac {e^{\beta _{i}}}{e^{\beta _{i}}+e^{\beta _{j}}}}.}$

به‌طور معادل می‌توان از یک logit استفاده کرد، به طوری که^[۱]

${\displaystyle \operatorname {logit} P(i>j)=\log {\frac {P(i>j)}{1-P(i>j)}}=\log {\frac {P(i>j)}{P(j>i)}}=\beta _{i}-\beta _{j},}$

یعنی ${\textstyle \operatorname {logit} p=\log {\frac {p}{1-p}}}$ برای ${\textstyle 0<p<1.}$

این فرمول شباهت بین مدل بردلی-تری و رگرسیون لجستیک را برجسته می‌کند. هر دو اساساً از یک مدل واحد، اما به روش‌های مختلف استفاده می‌کنند. در رگرسیون لجستیک فرد معمولاً پارامترهای ${\displaystyle \beta _{i}}$ را می‌داند و تلاش می‌کند تا شکل عملکردی ${\displaystyle P(i>j)}$ را استنباط کند؛ در رتبه‌بندی تحت مدل بردلی-تری، فرد شکل عملکردی را می‌شناسد و سعی می‌کند پارامترها را استنتاج کند.

تخمین پارامترها

رایج‌ترین کاربرد مدل برادلی-تری، استنتاج مقادیر پارامترهای ${\displaystyle p_{i}}$ با توجه به مجموعه ای از نتایج مشاهده شده ${\displaystyle i>j}$ است مانند برد و باخت در یک مسابقه. ساده‌ترین راه برای تخمین پارامترها ، تخمین حداکثر درستنمایی است، یعنی با به حداکثر رساندن احتمال نتایج مشاهده شده با توجه به مقادیر مدل و پارامتر.

فرض کنید نتایج مجموعه ای از رقابت‌های دوتایی بین گروه خاصی از افراد را می‌دانیم و اجازه دهید w_ij تعداد دفعاتی باشد که i فردی j را شکست می‌دهد. سپس احتمال این مجموعه از نتایج در مدل بردلی-تری${\displaystyle \prod _{ij}[P(i>j)]^{w_{ij}}}$ است و درستنمایی پارامتر p = [p₁, ..., p_n] برابر است با^[۱]

${\displaystyle {\begin{aligned}L(\mathbf {p} )&=\ln \prod _{ij}[P(i>j)]^{w_{ij}}=\sum _{i=1}^{n}\sum _{j=1}^{n}\ln \left({\frac {p_{i}}{p_{i}+p_{j}}}\right)^{w_{ij}}\\[6pt]&=\sum _{ij}w_{ij}\ln {\frac {p_{i}}{p_{i}+p_{j}}}=\sum _{ij}[w_{ij}\ln p_{i}-w_{ij}\ln(p_{i}+p_{j})].\end{aligned}}}$

Zermelo^[۴] نشان داد که این عبارت تنها دارای یک ماکزیمم واحد است که با اگر نسبت به ${\displaystyle p_{i}}$ مشتق گرفته و نتیجه را مساوی صفر قرار دهیم خواهیم داشت:

${\displaystyle p_{i}={\frac {\sum _{j}w_{ij}}{\sum _{j}(w_{ij}+w_{ji})/(p_{i}+p_{j})}}.}$

(2)

این معادله هیچ راه حل بسته شناخته شده‌ای ندارد، اما زرملو حل آن را با تکرار ساده پیشنهاد کرد. با شروع از هر مجموعه مناسبی از مقادیر اولیه (مثبت) برای ${\displaystyle p_{i}}$ ، یکی به‌طور مکرر به روز رسانی را انجام می‌دهد

${\displaystyle p_{i}'={\frac {\sum _{j}w_{ij}}{\sum _{j}(w_{ij}+w_{ji})/(p_{i}+p_{j})}}}$

(3)

برای همه i‌ها به نوبت این مقادیر محاسبه می‌شود. پارامترهای به دست آمده تا یک ضریب ثابت، دلخواه هستند، بنابراین پس از محاسبه همه مقادیر جدید باید با تقسیم بر میانگین هندسی آنها نرمال سازی شوند:

${\displaystyle p_{i}\leftarrow {\frac {p'_{i}}{\left(\prod _{j=1}^{n}p'_{j}\right)^{1/n}}}.}$

(4)

این فرایند تخمین، احتمال ورود به سیستم را در هر تکرار بهبود می‌بخشد و تضمین می‌شود که در نهایت به حداکثر منحصر به فرد برسد.^[۴][۹] با این حال، همگرایی کند است.^[۱][۱۰] اخیراً اشاره شده است^[۱۱] که معادله (2) را نیز می‌توان به صورت بازآرایی کرد.

${\displaystyle p_{i}={\frac {\sum _{j}w_{ij}p_{j}/(p_{i}+p_{j})}{\sum _{j}w_{ji}/(p_{i}+p_{j})}},}$

که با تکرار قابل حل است

${\displaystyle p_{i}'={\frac {\sum _{j}w_{ij}p_{j}/(p_{i}+p_{j})}{\sum _{j}w_{ji}/(p_{i}+p_{j})}},}$

(5)

پس از هر دور به روز رسانی با استفاده از معادله (4) دوباره عادی می‌شود. این تکرار نتایج یکسانی را با خروجی معادله (3) می‌دهد، اما خیلی سریعتر همگرا می‌شود و از این رو معمولاً بر (3) ترجیح داده می‌شود.^[۱۱]

نمونه کار شده از روش حل

یک رقابت ورزشی بین چهار تیم را در نظر بگیرید که در مجموع ۲۲ بازی را بین خود انجام می‌دهند. بردهای هر تیم در ردیف‌های جدول زیر و حریفان به صورت ستون آورده شده‌اند:

نتایج

	آ	ب	سی	D
آ	–	۲	۰	۱
ب	۳	–	۵	۰
سی	۰	۳	–	۱
D	۴	۰	۳	–

به عنوان مثال، تیم A دو بار تیم B را شکست داده و سه بار به تیم B باخته است و با تیم C اصلاً بازی نکرده است. یک برد و چهار باخت مقابل تیم D دارد.

ما می‌خواهیم نقاط قوت نسبی تیم‌ها را تخمین بزنیم که این کار را با محاسبه پارامترهای ${\displaystyle p_{i}}$ انجام می‌دهیم، بطوریکه پارامترهای بالاتر نشان دهنده مهارت بیشتر است. برای انجام این کار، چهار ورودی را در بردار پارامتر p به‌طور دلخواه مقداردهی می‌کنیم، به عنوان مثال مقدار ۱ را به هر تیم اختصاص می‌دهیم: [۱, ۱, ۱, ۱]. سپس معادله (5) را برای به روز رسانی ${\displaystyle p_{1}}$ اعمال می‌کنیم، که نتیجه زیر حاصل می‌شود:$${\displaystyle p_{1}={\frac {\sum _{j(\neq 1)}w_{1j}p_{j}/(p_{1}+p_{j})}{\sum _{j(\neq 1)}w_{j1}/(p_{1}+p_{j})}}={\frac {2{\frac {1}{1+1}}+0{\frac {1}{1+1}}+1{\frac {1}{1+1}}}{3{\frac {1}{1+1}}+0{\frac {1}{1+1}}+4{\frac {1}{1+1}}}}=0.429.}$$اکنون (5) را دوباره برای به روز رسانی ${\displaystyle p_{2}}$ اعمال می‌کنیم، مطمئن شوید که از مقدار جدید ${\displaystyle p_{1}}$ که محاسبه شد استفاده می‌کنید:$${\displaystyle p_{2}={\frac {\sum _{j(\neq 2)}w_{2j}p_{j}/(p_{2}+p_{j})}{\sum _{j(\neq 2)}w_{j2}/(p_{2}+p_{j})}}={\frac {3{\frac {0.429}{1+0.429}}+5{\frac {1}{1+1}}+0{\frac {1}{1+1}}}{2{\frac {1}{1+0.429}}+3{\frac {1}{1+1}}+0{\frac {1}{1+1}}}}=1.172}$$به‌طور مشابه برای ${\displaystyle p_{3}}$ و ${\displaystyle p_{4}}$ داریم:$${\displaystyle p_{3}={\frac {\sum _{j(\neq 3)}w_{3j}p_{j}/(p_{3}+p_{j})}{\sum _{j(\neq 3)}w_{j3}/(p_{3}+p_{j})}}={\frac {0{\frac {0.429}{1+0.429}}+3{\frac {1.172}{1+1.172}}+1{\frac {1}{1+1}}}{0{\frac {1}{1+0.429}}+5{\frac {1}{1+1.172}}+3{\frac {1}{1+1}}}}=0.557}$$$${\displaystyle p_{4}={\frac {\sum _{j(\neq 4)}w_{4j}p_{j}/(p_{4}+p_{j})}{\sum _{j(\neq 4)}w_{j4}/(p_{4}+p_{j})}}={\frac {4{\frac {0.429}{1+0.429}}+0{\frac {1.172}{1+1.172}}+3{\frac {0.557}{1+0.557}}}{1{\frac {1}{1+0.429}}+0{\frac {1}{1+1.172}}+1{\frac {1}{1+0.557}}}}=1.694}$$سپس تمام پارامترها را با تقسیم بر میانگین هندسی آنها نرمال می‌کنیم ${\displaystyle (0.429\times 1.172\times 0.557\times 1.694)^{1/4}=0.830}$ برای بدست آوردن پارامترهای تخمینی p = [۰٫۵۱۶, ۱٫۴۱۳, ۰٫۶۷۲, ۲٫۰۴۱].

برای بهبود بیشتر تخمین‌ها، با استفاده از مقادیر p جدید، فرایند را تکرار می‌کنیم؛ مثلاً،$${\displaystyle p_{1}={\frac {2\cdot {\frac {1.413}{0.516+1.413}}+0\cdot {\frac {0.672}{0.516+0.672}}+1\cdot {\frac {2.041}{0.516+2.041}}}{3\cdot {\frac {1}{0.516+1.413}}+0\cdot {\frac {1}{0.516+0.672}}+4\cdot {\frac {1}{0.516+2.041}}}}=0.725.}$$با تکرار این فرایند برای پارامترهای باقیمانده و عادی سازی، p = [۰٫۶۷۷, ۱٫۰۳۴, ۰٫۶۲۴, ۲٫۲۸۷] را دریافت می‌کنیم. تکرار ۱۰ بار دیگر همگرایی سریع به سمت حل نهایی p = [۰٫۶۴۰, ۱٫۰۴۳, ۰٫۶۶۰, ۲٫۲۷۰] می‌دهد. این نشان می‌دهد که تیم D قوی‌ترین و تیم B دومین قوی‌تر است، در حالی که تیم‌های A و C تقریباً از نظر قدرت برابر هستند اما کمتر از تیم‌های B و D هستند. حتی اگر همه تیم‌ها با هم بازی نکرده باشند.

جستارهای وابسته

• رگرسیون ترتیبی
• مدل راش
• مقیاس (علوم اجتماعی)
• سیستم رتبه‌بندی الو
• مدل تورستونی

منابع

1. Hunter, David R. (2004). "MM algorithms for generalized Bradley–Terry models". The Annals of Statistics. 32 (1): 384–406. CiteSeerX 10.1.1.110.7878. doi:10.1214/aos/1079120141. JSTOR 3448514. خطای یادکرد: برچسب <ref> نامعتبر؛ نام «hunter» چندین بار با محتوای متفاوت تعریف شده است. (صفحهٔ راهنما را مطالعه کنید.).
2. "Bradley-Terry model". Encyclopedia of Mathematics. Retrieved 18 November 2014.
3. Bradley, Ralph Allan; Terry, Milton E. (1952). "Rank Analysis of Incomplete Block Designs: I. The Method of Paired Comparisons". Biometrika. 39 (3/4): 324–345. doi:10.2307/2334029. JSTOR 2334029.
4. Zermelo, Ernst (1929). "Die Berechnung der Turnier-Ergebnisse als ein Maximumproblem der Wahrscheinlichkeitsrechnung". Mathematische Zeitschrift. 29: 436–460. doi:10.1007/BF01180541. خطای یادکرد: برچسب <ref> نامعتبر؛ نام «zermelo» چندین بار با محتوای متفاوت تعریف شده است. (صفحهٔ راهنما را مطالعه کنید.).
5. Heinz-Dieter Ebbinghaus (2007), Ernst Zermelo: An Approach to His Life and Work, Springer, pp. 268–269, ISBN 978-3-540-49553-6
6. Shev, A.; Fujii, K.; Hsieh, F.; McCowan, B. (2014). "Systemic testing on Bradley-Terry model against nonlinear ranking hierarchy". PLOS One. 9: e115367. doi:10.1371/journal.pone.0115367. PMC 4274013. PMID 25531899.
7. Boyd, Robert; Silk, Joan B. (1983). "A method for assigning cardinal dominance ranks". Animal Behaviour. 31: 45–58. doi:10.1016/S0003-3472(83)80172-9.
8. "Chatbot Arena: New models & Elo system update | LMSYS Org". lmsys.org (به انگلیسی). Retrieved 2024-01-30.
9. Ford, Jr., L. R. (1957). "Solution of a ranking problem from binary comparisons". American Mathematical Monthly. 64: 28–33. doi:10.1080/00029890.1957.11989117.
10. Dykstra, Jr., Otto (1956). "A note on the rank analysis of incomplete block designs". Biometrics. 12: 301–306. doi:10.2307/2334029. JSTOR 2334029.
11. Newman, M. E. J. (2023). "Efficient computation of rankings from pairwise comparisons". Journal of Machine Learning Research. 24: 1–25. خطای یادکرد: برچسب <ref> نامعتبر؛ نام «newman» چندین بار با محتوای متفاوت تعریف شده است. (صفحهٔ راهنما را مطالعه کنید.).