Model Bradleya-Terry'ego

Bradleya -Terry'ego to model prawdopodobieństwa , który może przewidzieć wynik porównania w parach. Biorąc pod uwagę parę osobników $i$ i $j$ wylosowanych z jakiejś populacji , szacuje prawdopodobieństwo, że porównanie parami $i > j$ okaże się prawdziwe, ponieważ

{\ Displaystyle P (i> j) = {\ Frac {p_ {i}} {p_ {i} + p_ {j}}}}

gdzie $p i$ jest dodatnim wynikiem w wartościach rzeczywistych przypisanym do indywidualnego $i$ . Porównanie $i > j$ można odczytać jako „ $i$ jest preferowane w stosunku do $j$ ”, „ $i$ zajmuje wyższą pozycję niż $j$ ” lub „ $i$ bije $j$ ”, w zależności od zastosowania.

Na przykład $p i$ może reprezentować umiejętności drużyny w turnieju sportowym, oszacowane na podstawie liczby wygranych meczów $przez i .$ $_$ $wtedy$ prawdopodobieństwo $j$ . _ Innym przykładem używanym do wyjaśnienia celu modelu jest ocenianie produktów w określonej kategorii według jakości. Chociaż osobie trudno jest sporządzić bezpośredni ranking (wielu) marek wina, możliwe jest porównanie próbki par win i stwierdzenie dla każdej pary, która jest lepsza. Model Bradleya-Terry'ego można następnie wykorzystać do uzyskania pełnego rankingu.

Historia i zastosowania

Zermelo badał go już w latach 20. XX wieku.

Zastosowania tego modelu w świecie rzeczywistym obejmują szacowanie wpływu czasopism statystycznych lub porządkowanie dokumentów według trafności w wyszukiwarkach uczących się maszynowo . W tym ostatnim zastosowaniu $więc$ że dokument $i$ zapytania użytkownika niż dokument $j$ powinien być wyświetlany wcześniej na liście Indywidualne $pi .$ wyrażają wtedy istotność dokumentu i można je oszacować na podstawie częstotliwości, z jaką użytkownicy klikają poszczególne „trafienia”, gdy wyświetlana jest lista wyników

Definicja

Model Bradleya-Terry'ego można parametryzować na różne sposoby. Jednym ze sposobów na to jest wybranie pojedynczego parametru na obserwację, co prowadzi do modelu n $parametrów$ p $1, ..., p n$ . Inny wariant, w rzeczywistości wersja rozważana przez Bradleya i Terry'ego, wykorzystuje wykładnicze funkcje punktacji, tak że ${\ displaystyle p_ {i} = e ^ {\ beta _ {i}}}$

{\ Displaystyle P (i> j) = {\ Frac {e ^ {\ beta _ {i}}} {e ^ {\ beta _ { i}}+e^{\beta_{j}}}}}

lub używając logit (i odrzucając remisy),

{\ Displaystyle \ nazwa operatora {logit} (P (i> j)) = \ log \ lewo ({\ Frac {P (i> j)} {1-P (i> j)}} \ prawej) = \log \left({\frac {P(i>j)}{P(j>i)}}\right)=\beta _{i}-\beta _{j}}

sprowadzenie modelu do regresji logistycznej na parach osobników.

Szacowanie parametrów

Poniższy algorytm oblicza parametry $p i$ podstawowej wersji modelu z próby obserwacji. Formalnie oblicza maksymalne oszacowanie prawdopodobieństwa , tj. maksymalizuje prawdopodobieństwo obserwowanych danych. Algorytm pochodzi z prac Zermelo.

Wymagane obserwacje to wyniki poprzednich porównań, na przykład pary $(i, j)$ , gdzie $i$ pokonuje $j$ . Podsumowując te wyniki jako $w ij$ , ile razy $i$ pokonało $j$ , otrzymujemy logarytm wiarygodności wektora parametrów $p = p 1, ..., p n$ as

{\ Displaystyle L (\ mathbf {p}) = \ suma _ {i} ^ {n} \ suma _ {j} ^ {n} \ ln p_ {ij} ^ {w_ {ij}} = \ suma _ { i}^{n}\sum _{j}^{n}\ln \left({\frac {p_{i}}{p_{i}+p_{j}}}\right)^{w_{ij }}=\sum _{i}^{n}\sum _{j}^{n}w_{ij}\ln \left({\frac {p_{i}}{p_{i}+p_{j }}}\right)=\sum _{i}^{n}\sum _{j}^{n}[w_{ij}\ln p_{i}-w_{ij}\ln(p_{i} +p_{j})].}

Oznacz liczbę porównań „wygranych” przez $i$ jako $W i$ . Począwszy od dowolnego wektora $p$ , algorytm iteracyjnie dokonuje aktualizacji

{\ Displaystyle p'_ {i} = W_ {i} \ lewo (\ suma _ {j \ neq i}{\frac {w_{ij}+w_{ji}}{p_{i}+p_{j}}}\right)^{-1}}

dla wszystkich $ja$ . Po obliczeniu wszystkich nowych parametrów należy je ponownie znormalizować,

{\ Displaystyle p_ {i} \ leftarrow {\ Frac {p'_ {i}}} {\ suma _ {j = 1} ^ {n} p'_ {j}}}.}

Ta procedura szacowania poprawia logarytm wiarygodności w każdej iteracji i ostatecznie zbiega się do unikalnego maksimum.

Praktyczny przykład procedury iterowanej

Załóżmy, że są 4 drużyny, które rozegrały łącznie 22 mecze między sobą. Zwycięstwa każdej drużyny są podane w wierszach poniższej tabeli, a przeciwnicy w kolumnach. Na przykład Drużyna A dwukrotnie pokonała Drużynę B i trzykrotnie przegrała z Drużyną B; w ogóle nie grał w drużynie C; wygrał raz i przegrał cztery razy z drużyną D.

Wyniki
	A	B	C	D
A	-	2	0	1
B	3	-	5	0
C	0	3	-	1
D	4	0	3	-

Chcielibyśmy obliczyć względne siły drużyn; oznacza to, że chcemy obliczyć jeden parametr na zespół, przy czym wyższe parametry wskazują na większą sprawność. inicjalizujemy 4 wpisy w wektorze parametrów $p$ , na przykład przypisując każdemu zespołowi wartość 1: $[1, 1, 1, 1]$ .

${\ Displaystyle p_ {1}={\frac {W_{1}}{\sum _{j\neq 1}{\frac {w_{1j}+w_{j1}}{p_{1}+p_{j}}}} }={\frac {2+0+1}{{\frac {2+3}{1+1}}+{\frac {0+0}{1+1}}+{\frac {1+4 }{1+1}}}}=0,6}$

${\ Displaystyle p_ {2}={\frac {W_{2}}{\sum _{j\neq 2}{\frac {w_{2j}+w_{j2}}{p_{2}+p_{j}}}} }={\frac {3+5+0}{{\frac {3+2}{1+1}}+{\frac {5+3}{1+1}}+{\frac {0+0 }{1+1}}}}=1,231}$

${\ Displaystyle p_ {3}={\frac {W_{3}}{\sum _{j\neq 3}{\frac {w_{3j}+w_{j3}}{p_{3}+p_{j}}}} }={\frac {0+3+1}{{\frac {0+0}{1+1}}+{\frac {3+5}{1+1}}+{\frac {1+3 }{1+1}}}}=0,667}$

${\ Displaystyle p_ {4}={\frac {W_{4}}{\sum _{j\neq 4}{\frac {w_{4j}+w_{j4}}{p_{4}+p_{j}}}} }={\frac {4+0+3}{{\frac {4+1}{1+1}}+{\frac {0+0}{1+1}}+{\frac {3+1 }{1+1}}}}=1,556}$

Następnie normalizujemy wszystkie parametry, dzieląc je przez ${\ Displaystyle 0,6 + 1,231 + 0,667 + 1,556 = 4,053}$ , aby uzyskać oszacowane parametry $p = [0,148, 0,304, 0,164, 0,384]$ .

Aby uzyskać lepsze oszacowania, możemy powtórzyć proces, używając nowych wartości $p$ . Na przykład,

${\ Displaystyle p_ {1}={\frac {W_{1}}{\sum _{j\neq 1}{\frac {w_{1j}+w_{j1}}{p_{1}+p_{j}}}} }={\frac {2+0+1}{{\frac {2+3}{0,148+0,304}}+{\frac {0+0}{0,148+0,164}}+{\frac {1+4 }{0,148+0,384}}}}=0,147}$

Powtarzając to dla pozostałych parametrów i normalizując, otrzymujemy $p = [0,145, 0,280, 0,162, 0,413]$ . Powtórzenie tego procesu w sumie 20 razy pokaże szybką zbieżność do $p = [0,139, 0,226, 0,143, 0,492]$ . To pokazuje, że Drużyna D jest najsilniejsza, Drużyna B jest druga najsilniejsza, a Drużyna A i Drużyna C mają prawie taką samą siłę, ale mniejszą niż Drużyny B i D. Model Bradleya-Terry'ego pozwala nam ekstrapolować relacje między wszystkimi 4 zespołami , mimo że wszystkie drużyny nie grały ze sobą.

Zobacz też