ブラッドリー・テリーモデルは、アイテム、チーム、またはオブジェクト間のペアワイズ比較の結果に関する 確率モデル です。ある母集団 から抽出されたアイテムのペアi とjが与えられた場合、 ペアワイズ比較 i > j
ここで、p i は個人iに割り当てられた正の 実数値 スコアです。比較i > j iは j より好ましい」、「i は j より上位にランクされる」、「i は j に勝つ」などと解釈できます。
例えば、p i は スポーツトーナメントにおけるチームのスキルを表し、教授 （ 私 > j ） {\displaystyle \Pr(i>j)} i が j に対してゲームに勝つ確率。[ 1 ] [ 2 ] p i は 市販製品の品質や望ましさを表す可能性があり、教授 （ 私 > j ） {\displaystyle \Pr(i>j)} 消費者が製品i を 製品j よりも好む確率。
ブラッドリー・テリーモデルは、前述のように結果を予測するために順方向に使用できますが、より一般的には、観測された結果のセットに基づいてスコアp i を 推測するために逆方向に使用されます。[ 2 ] p i は、 私 {\displaystyle i}
スコアp i の値が計算されると、モデルは順方向にも使用できます。たとえば、まだ実際に行われていない比較の可能性のある結果を予測するために使用できます。たとえば、ワインの調査の例では、誰かがワインを好む確率を計算できます。私 {\displaystyle i} j {\displaystyle j}
意味 ブラッドリー・テリーモデルは様々な方法でパラメータ化できる。式（1 p 私 = e β 私 {\displaystyle p_{i}=e^{\beta _{i}}} [ 2 ]
教授 （ 私 > j ） = e β 私 e β 私 + e β j = 1 1 + e β j − β 私 。 {\displaystyle \Pr(i>j)={\frac {e^{\beta _{i}}}{e^{\beta _{i}}+e^{\beta _{j}}}}={\frac {1}{1+e^{\beta _{j}-\beta _{i}}}}。
あるいは、次のようなロジットを使用することもできます。 [ 1 ]
ロジット 教授 （ 私 > j ） = ログ 教授 （ 私 > j ） 1 − 教授 （ 私 > j ） = ログ 教授 （ 私 > j ） 教授 （ j > 私 ） = β 私 − β j 、 {\displaystyle \operatorname {logit} \Pr(i>j)=\log {\frac {\Pr(i>j)}{1-\Pr(i>j)}}=\log {\frac {\Pr(i>j)}{\Pr(j>i)}}=\beta _{i}-\beta _{j},}
どこで ロジット p = ログ p 1 − p {\displaystyle \operatorname {logit} p=\log {\frac {p}{1-p}}} 0 < p < 1 {\displaystyle 0<p<1}
この定式化は、ブラッドリー・テリーモデルとロジスティック回帰 の類似性を強調している。どちらも本質的に同じモデルを使用しているが、その方法は異なっている。ロジスティック回帰 では、通常、パラメータが既知である。β 私 \displaystyle \beta _{i}} 教授 （ 私 > j ） {\displaystyle \Pr(i>j)}
スケールファクター400、ベース10の場合、これはEloレーティングR i R j Eloレーティングシステム に相当します。 教授 （ 私 > j ） = 10 R 私 / 400 10 R 私 / 400 + 10 R j / 400 = 1 1 + 10 （ R j − R 私 ） / 400 。 {\displaystyle \Pr(i>j)={\frac {10^{R_{i}/400}}{10^{R_{i}/400}+10^{R_{j}/400}}}={\frac {1}{1+10^{(R_{j}-R_{i})/400}}}.}
BTモデルの標準的な一般化は、ランキングをモデル化したプラケット-ルース モデルである[ 12 ] [ 13 ]。 N {\displaystyle N} 教授 （ y 1 > ⋯ > y N ） = ∏ 私 = 1 N p y 私 ∑ k = 私 N p y k = p y 1 p y 1 + ⋯ + p y N p y 2 p y 2 + ⋯ + p y N ⋯ p y N p y N {\displaystyle \Pr(y_{1}>\cdots >y_{N})=\prod _{i=1}^{N}{\frac {p_{y_{i}}}{\sum _{k=i}^{N}p_{y_{k}}}}={\frac {p_{y_{1}}}{p_{y_{1}}+\dots +p_{y_{N}}}}{\frac {p_{y_{2}}}{p_{y_{2}}+\cdots +p_{y_{N}}}}\cdots {\frac {p_{y_{N}}}{p_{y_{N}}}}} 私 = N {\displaystyle i=N} N = 2 {\displaystyle N=2} 教授 （ y 1 > y 2 ） = p y 1 / （ p y 1 + p y 2 ） {\displaystyle \Pr(y_{1}>y_{2})=p_{y_{1}}/(p_{y_{1}}+p_{y_{2}})}
これは、復元抽出による壺からの抽出 として想像できます。壺には、p 1 、 p 2 、 … 、 p N {\displaystyle p_{1},p_{2},\dots ,p_{N}}
比率を考慮するとp 1 、 p 2 、 … 、 p N {\displaystyle p_{1},p_{2},\dots ,p_{N}} PLモデルは「指数 レース」法によってサンプリングできます。N {\displaystyle N} 指数 時計」、つまり、t 1 ～ E x p （ p 1 ） 、 … 、 t N ～ E x p （ p N ） \displaystyle t_{1}\sim \mathrm {Exp} (p_{1}),\dots ,t_{N}\sim \mathrm {Exp} (p_{N})} Luce の選択公理 (同じ Luce による) を満たすことがすぐにわかります。したがって、任意の 2 つのy 、 z {\displaystyle y,z} 教授 （ y > z ） = p y p y + p z {\displaystyle \Pr(y>z)={\frac {p_{y}}{p_{y}+p_{z}}}} y 1 、 … 、 y M {\displaystyle y_{1},\dots ,y_{M}} 教授 （ y 1 > ⋯ > y N ） = p y 1 p y 1 + ⋯ + p y M p y 2 p y 2 + ⋯ + p y M ⋯ p y M p y M {\displaystyle \Pr(y_{1}>\cdots >y_{N})={\frac {p_{y_{1}}}{p_{y_{1}}+\cdots +p_{y_{M}}}}{\frac {p_{y_{2}}}{p_{y_{2}}+\cdots +p_{y_{M}}}}\cdots {\frac {p_{y_{M}}}{p_{y_{M}}}}}
推論 ブラッドリー・テリーモデルの最も一般的な応用例は、パラメータの値を推定することです。p 私 {\displaystyle p_{i}} 私 > j {\displaystyle i>j} 最尤推定法 、つまり、モデルとパラメータの値が与えられた場合に観測された結果の尤度 を最大化することです。
ある特定のグループ間のペアワイズ競争の結果がわかっていると仮定し、w ij を個人i が 個人j に勝つ回数とします。この結果のセットのブラッドリー・テリーモデルにおける尤度は次のようになります。∏ 私 j [ 教授 （ 私 > j ） ] w 私 j {\displaystyle \prod _{ij}[\Pr(i>j)]^{w_{ij}}} p = [ p 1 , ..., p n ]の 対数 尤度は[ 1 ]
l （ p ） = ln ∏ 私 j [ 教授 （ 私 > j ） ] w 私 j = ∑ 私 = 1 n ∑ j = 1 n ln [ （ p 私 p 私 + p j ） w 私 j ] = ∑ 私 j w 私 j ln （ p 私 p 私 + p j ） = ∑ 私 j [ w 私 j ln （ p 私 ） − w 私 j ln （ p 私 + p j ） ] 。 {\displaystyle {\begin{aligned}{\mathcal {l}}(\mathbf {p} )&=\ln \prod _{ij}{{\bigl [}\Pr(i>j){\bigr ]}}^{w_{ij}}=\sum _{i=1}^{n}\sum _{j=1}^{n}\ln {\biggl [}\left({\frac {p_{i}}{p_{i}+p_{j}}}\right)^{w_{ij}}{\biggr ]}\\[6pt]&=\sum _{ij}w_{ij}\ln {\biggl (}{\frac {p_{i}}{p_{i}+p_{j}}}{\biggr )}=\sum _{ij}{\bigl [}w_{ij}\ln(p_{i})-w_{ij}\ln(p_{i}+p_{j}){\bigr ]}.\end{aligned}}}
Zermelo [ 5 ] p 私 {\displaystyle p_{i}}
この方程式には既知の閉形式解はありませんが、Zermelo は単純な反復によって解くことを提案しました。p 私 {\displaystyle p_{i}}
すべてのi について順に計算します。結果として得られるパラメータは、全体的な乗法定数を除いて任意であるため、すべての新しい値を計算した後、幾何平均 で割ることによって正規化する必要があります。
この推定手順は、反復ごとに対数尤度を改善し、最終的には一意の最大値に到達することが保証されています。[ 5 ] [ 14 ] [ 1 ] [ 15 ] 2 [ 16 ]。
p 私 = ∑ j w 私 j p j / （ p 私 + p j ） ∑ j w j 私 / （ p 私 + p j ） 、 {\displaystyle p_{i}={\frac {\sum _{j}w_{ij}p_{j}/(p_{i}+p_{j})}{\sum _{j}w_{ji}/(p_{i}+p_{j})}},}
これは反復することで解決できます
式（ 4 3 3 [ 16 ]
解決手順の具体的な例 4つのチームが合計22試合を行うスポーツ競技を考えてみましょう。各チームの勝利数は以下の表の行に、対戦相手は列に示されています。
例えば、チームAはチームBに2回勝ち、3回負けた。チームCとは全く対戦していない。チームDに対しては1回勝ち、4回負けた。
各チームの相対的な強さを推定するために、以下のパラメータを計算します。p 私 {\displaystyle p_{i}} p [1, 1, 1, 1] 。次に、式 ( 5 p 1 {\displaystyle p_{1}}
p 1 = ∑ j （ ≠ 1 ） w 1 j p j / （ p 1 + p j ） ∑ j （ ≠ 1 ） w j 1 / （ p 1 + p j ） = 2 1 1 + 1 + 0 1 1 + 1 + 1 1 1 + 1 3 1 1 + 1 + 0 1 1 + 1 + 4 1 1 + 1 = 0.429。 {\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 p 2 {\displaystyle p_{2}} p 1 {\displaystyle p_{1}}
p 2 = ∑ j （ ≠ 2 ） w 2 j p j / （ p 2 + p j ） ∑ j （ ≠ 2 ） w j 2 / （ p 2 + p j ） = 3 0.429 1 + 0.429 + 5 1 1 + 1 + 0 1 1 + 1 2 1 1 + 0.429 + 3 1 1 + 1 + 0 1 1 + 1 = 1.172 {\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}
同様にp 3 {\displaystyle p_{3}} p 4 {\displaystyle p_{4}}
p 3 = ∑ j （ ≠ 3 ） w 3 j p j / （ p 3 + p j ） ∑ j （ ≠ 3 ） w j 3 / （ p 3 + p j ） = 0 0.429 1 + 0.429 + 3 1.172 1 + 1.172 + 1 1 1 + 1 0 1 1 + 0.429 + 5 1 1 + 1.172 + 3 1 1 + 1 = 0.557 {\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}
p 4 = ∑ j （ ≠ 4 ） w 4 j p j / （ p 4 + p j ） ∑ j （ ≠ 4 ） w j 4 / （ p 4 + p j ） = 4 0.429 1 + 0.429 + 0 1.172 1 + 1.172 + 3 0.557 1 + 0.557 1 1 1 + 0.429 + 0 1 1 + 1.172 + 1 1 1 + 0.557 = 1.694 {\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}
次に、すべてのパラメータを幾何平均で割ることによって正規化します。（ 0.429 × 1.172 × 0.557 × 1.694 ） 1 / 4 = 0.830 {\displaystyle (0.429\times 1.172\times 0.557\times 1.694)^{1/4}=0.830} p = [0.516, 1.413, 0.672, 2.041]
推定値をさらに改善するために、新しいp
p 1 = 2 ⋅ 1.413 0.516 + 1.413 + 0 ⋅ 0.672 0.516 + 0.672 + 1 ⋅ 2.041 0.516 + 2.041 3 ⋅ 1 0.516 + 1.413 + 0 ⋅ 1 0.516 + 0.672 + 4 ⋅ 1 0.516 + 2.041 = 0.725。 {\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 = [0.677, 1.034, 0.624, 2.287]p = [0.640, 1.043, 0.660, 2.270]
バリエーション
クラウドBT Chen らによって 2013 年に開発された Crowd-BT モデル[ 17 ] は、各審査員の信頼性を考慮することで必要な比較回数を減らしつつ、クラウドソーシング 環境向けに標準的な Bradley–Terry モデルを拡張しようと試みています。特に、スパム行為者 (ランダムに選択する) または悪意のある (常に間違った選択をする) と思われる審査員を特定して除外します。624 人の審査員がそれぞれ最大 40 回のペアワイズ比較を行い、文書を読解難易度でランク付けするクラウドソーシング タスクにおいて、Crowd-BT は標準的な Bradley–Terry とランキング システムTrueSkill の両方を上回ることが示されました。効率よりも質の高い結果が重視され、比較回数が多い場合に推奨されています。[ 18 ]
参考文献 1 2 3 4 5 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. 2021-02-09 に取得 。 1 2 3 Agresti, Alan (2014). Categorical Data Analysis . John Wiley & Sons. pp. 436–439 . ↑ EEM van Berkum. 「ブラッドリー・テリーモデル」 . 数学百科事典 . 2014年 11月18日 取得. ↑ Bradley, Ralph Allan; Terry, Milton E. (1952). "不完全ブロック計画の順位分析: I. ペア比較法". Biometrika . 39 (3/4): 324– 345. doi : 10.2307/2334029 . JSTOR 2334029 . 1 2 3 エルンスト、ツェルメロ (1929)。 「Turnier-Ergebnisse als ein Maximumproblem der Wahrscheinlichkeitsrechnung」。 数学的ツァイシュリフト 。 29 (1): 436–460 。 土井 : 10.1007/BF01180541 。 S2CID 122877703 。 ↑ ハインツ＝ディーター・エビングハウス（2007）『 エルンスト・ツェルメロ：その生涯と作品へのアプローチ』シュプリンガー、 268-269 頁 、 ISBN 978-3-540-49553-6 ↑ Shev, A.; Fujii, K.; Hsieh, F.; McCowan, B. (2014). "非線形ランキング階層に対するBradley-Terryモデルの体系的テスト" . PLOS One . 9 (12) e115367. Bibcode : 2014PLoSO...9k5367S . doi : 10.1371/journal.pone.0115367 . PMC 4274013 . PMID 25531899 . ↑ Boyd, Robert; Silk, Joan B. (1983). "A method for assigning cardinal dominance ranks". Animal Behaviour . 31 (1): 45– 58. doi : 10.1016/S0003-3472(83)80172-9 . S2CID 53178779 . ↑ 「チャットボットアリーナ：新モデルとEloシステムアップデート｜LMSYS Org」 . lmsys.org . 2024年1月30日 取得 。 ↑ von Csefalvay, Chris (2026). Post-Training: A Practical Guide for AI Engineers and Developers . No Starch Press. p. 115. ISBN 978-1-7185-0520-9 。↑ Szummer, Martin; Yilmaz, Emine (2011). 選好正則化によるランキングのための半教師あり学習 (PDF) . CIKM. ↑ Plackett, RL (1975). "順列の分析". Applied Statistics . 24 (2): 193– 202. doi : 10.2307/2346567 . JSTOR 2346567 . ↑ Luce, RD (1959). Individual Choice Behavior: A Theoretical Analysis . Wiley. ↑ Ford, Jr., LR (1957). "二項比較による順位付け問題の解法". American Mathematical Monthly . 64 (8): 28–33 . doi : 10.1080/00029890.1957.11989117 . ↑ Dykstra, Jr., Otto (1956). "不完全ブロック設計の順位分析に関する注記". Biometrics . 12 : 301–306 . doi : 10.2307/2334029 . JSTOR 2334029 . 1 2 Newman, MEJ (2023). "Efficient computation of rankings from pairwise comparisons" . Journal of Machine Learning Research . 24 (238): 1– 25. 2024-10-06 のオリジナルから アーカイブ 。2023-08-15 に取得 。 ↑ Chen, Xi; Bennett, Paul N.; Collins-Thompson, Kevyn; Horvitz, Eric (2013年2月4日). 「クラウドソーシング環境におけるペアワイズランキング集約」. 第6回ACM国際ウェブ検索・データマイニング会議議事録 . pp. 193–202 . doi : 10.1145/2433396.2433420 . ISBN 978-1-4503-1869-3 。↑ Zhang, Xiaohang; Li, Guoliang; Feng, Jianhua (2016年4月)「クラウドソーシングによるトップkアルゴリズム：実験的評価」 VLDB Endowment論文集 9 ( 8): 612–623 . doi : 10.14778/2921558.2921559 . 
![{\displaystyle \prod _{ij}[\Pr(i>j)]^{w_{ij}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6e9f1f2f0134654c2b24cdfa3963042cf530df7b)
![{\displaystyle {\begin{aligned}{\mathcal {l}}(\mathbf {p} )&=\ln \prod _{ij}{{\bigl [}\Pr(i>j){\bigr ]}}^{w_{ij}}=\sum _{i=1}^{n}\sum _{j=1}^{n}\ln {\biggl [}\left({\frac {p_{i}}{p_{i}+p_{j}}}\right)^{w_{ij}}{\biggr ]}\\[6pt]&=\sum _{ij}w_{ij}\ln {\biggl (}{\frac {p_{i}}{p_{i}+p_{j}}}{\biggr )}=\sum _{ij}{\bigl [}w_{ij}\ln(p_{i})-w_{ij}\ln(p_{i}+p_{j}){\bigr ]}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c2bc45a979c3613318a743a0b4a4ef9d5a2c3cad)
