Modelo Bradley-Terry

Modelo estadístico para comparaciones por pares.

El modelo Bradley-Terry es un modelo de probabilidad para el resultado de comparaciones por pares entre elementos, equipos u objetos. Dado un par de elementos i y j extraídos de alguna población , estima la probabilidad de que la comparación por pares i > j resulte verdadera, como

donde p _i es una puntuación positiva de valor real asignada al individuo i . La comparación i > j se puede leer como " i es preferible a j ", " i ocupa un lugar más alto que j " o " i vence a j ", dependiendo de la aplicación.

Por ejemplo, p _i podría representar la habilidad de un equipo en un torneo deportivo y la probabilidad de que i gane un juego contra j . ^{[1] [2]} O p _i podría representar la calidad o conveniencia de un producto comercial y la probabilidad de que un consumidor prefiera el producto i al producto j . ${\displaystyle \Pr(i>j)}$ ${\displaystyle \Pr(i>j)}$

El modelo Bradley-Terry se puede utilizar en dirección directa para predecir resultados, como se describe, pero se utiliza más comúnmente a la inversa para inferir las puntuaciones p _i dado un conjunto de resultados observados. ^[2] En este tipo de aplicación, p _i representa alguna medida de la fuerza o calidad de y el modelo nos permite estimar las fortalezas a partir de una serie de comparaciones por pares. En una encuesta sobre preferencias de vinos, por ejemplo, puede resultar difícil para los encuestados dar una clasificación completa de un gran conjunto de vinos, pero les resulta relativamente fácil comparar pares de vinos de muestra y decir cuál creen que es mejor. A partir de un conjunto de comparaciones por pares, el modelo Bradley-Terry puede utilizarse para obtener una clasificación completa de los vinos. ${\displaystyle i}$

Una vez calculados los valores de las puntuaciones p _i , el modelo también se puede utilizar en la dirección de avance, por ejemplo para predecir el resultado probable de comparaciones que aún no se han producido. En el ejemplo de la encuesta sobre vinos, por ejemplo, se podría calcular la probabilidad de que alguien prefiera el vino al vino , incluso si nadie en la encuesta comparó directamente ese par en particular. ${\displaystyle i}$ ${\displaystyle j}$

Historia y aplicaciones

El modelo lleva el nombre de Ralph A. Bradley y Milton E. Terry, ^[3] quienes lo presentaron en 1952, ^[4] aunque ya había sido estudiado por Ernst Zermelo en los años 1920. ^{[1] [5] [6]} Las aplicaciones del modelo incluyen la clasificación de competidores en deportes, ajedrez y otras competiciones, ^[7] la clasificación de productos en encuestas comparativas pareadas de elección del consumidor , análisis de jerarquías de dominancia dentro de animales y humanos. comunidades, ^[8] ranking de revistas , ranking de modelos de IA, ^[9] y estimación de la relevancia de documentos en motores de búsqueda de aprendizaje automático . ^[10]

Definición

El modelo Bradley-Terry se puede parametrizar de varias maneras. La ecuación ( 1 ) es quizás la más común, pero hay muchas otras. Los propios Bradley y Terry definieron funciones de puntuación exponenciales , de modo que ^[2] ${\displaystyle p_{i}=e^{\beta _{i}}}$

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

Alternativamente, se puede utilizar un logit , tal que ^[1]

${\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},}$

es decir, para ${\textstyle \operatorname {logit} p=\log {\frac {p}{1-p}}}$ ${\textstyle 0<p<1.}$

Esta formulación resalta la similitud entre el modelo Bradley-Terry y la regresión logística . Ambos emplean esencialmente el mismo modelo pero de diferentes maneras. En la regresión logística, normalmente se conocen los parámetros y se intenta inferir la forma funcional de ; Al clasificar según el modelo de Bradley-Terry, se conoce la forma funcional e intenta inferir los parámetros. ${\displaystyle \beta _{i}}$ ${\displaystyle \Pr(i>j)}$

Con un factor de escala de 400, esto equivale al sistema de calificación Elo para jugadores con calificaciones Elo R _i y R _j .

${\displaystyle \Pr(i>j)={\frac {e^{R_{i}/400}}{e^{R_{i}/400}+e^{R_{j}/400}}}={\frac {1}{1+e^{(R_{j}-R_{i})/400}}}.}$

Estimando los parámetros

La aplicación más común del modelo Bradley-Terry es inferir los valores de los parámetros dado un conjunto observado de resultados , como victorias y derrotas en una competencia. La forma más sencilla de estimar los parámetros es mediante estimación de máxima verosimilitud , es decir, maximizando la probabilidad de los resultados observados dados los valores del modelo y de los parámetros. ${\displaystyle p_{i}}$ ${\displaystyle i>j}$

Supongamos que conocemos los resultados de un conjunto de competiciones por parejas entre un determinado grupo de individuos, y sea w _ij el número de veces que el individuo i vence al individuo j . Entonces la probabilidad de este conjunto de resultados dentro del modelo Bradley-Terry es y la probabilidad logarítmica del vector de parámetros p = [ p ₁ , ..., p _n ] es ^[1] ${\displaystyle \prod _{ij}[\Pr(i>j)]^{w_{ij}}}$

${\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] demostró que esta expresión tiene un solo máximo, que se puede encontrar derivando con respecto a y estableciendo el resultado en cero, lo que conduce a ${\displaystyle p_{i}}$

Esta ecuación no tiene una solución de forma cerrada conocida, pero Zermelo sugirió resolverla mediante una simple iteración. A partir de cualquier conjunto conveniente de valores iniciales (positivos) para , se realiza la actualización de forma iterativa ${\displaystyle p_{i}}$

para todos yo a mi vez. Los parámetros resultantes son arbitrarios hasta una constante multiplicativa general, por lo que después de calcular todos los nuevos valores deben normalizarse dividiéndolos por su media geométrica de la siguiente manera:

Este procedimiento de estimación mejora la probabilidad logarítmica en cada iteración y garantiza que eventualmente alcanzará el máximo único. ^{[5] [11]} Sin embargo, su convergencia es lenta. ^{[1] [12]} Más recientemente se ha señalado ^[13] que la ecuación ( 2 ) también se puede reorganizar como

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

que se puede resolver iterando

normalizándose nuevamente después de cada ronda de actualizaciones usando la ecuación ( 4 ). Esta iteración da resultados idénticos a la de ( 3 ) pero converge mucho más rápido y, por lo tanto, normalmente se prefiere a ( 3 ). ^[13]

Ejemplo resuelto de procedimiento de solución

Consideremos una competición deportiva entre cuatro equipos, que juegan un total de 22 partidos entre ellos. Las victorias de cada equipo se muestran en las filas de la siguiente tabla y los oponentes se muestran en las columnas:

Por ejemplo, el equipo A venció al equipo B dos veces y perdió ante el equipo B tres veces; no jugó contra el equipo C en absoluto; ganó una vez y perdió cuatro veces contra el equipo D.

Nos gustaría estimar las fortalezas relativas de los equipos, lo cual hacemos calculando los parámetros , donde los parámetros más altos indican una mayor destreza. Para ello, inicializamos las cuatro entradas en el vector de parámetros p de forma arbitraria, por ejemplo asignando el valor 1 a cada equipo: [1, 1, 1, 1] . Luego aplicamos la ecuación ( 5 ) para actualizar , lo que da ${\displaystyle p_{i}}$ ${\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.}$$

Ahora, aplicamos ( 5 ) nuevamente para actualizar , asegurándonos de usar el nuevo valor de que acabamos de calcular: ${\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}$$

De manera similar para y obtenemos ${\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}$$

Luego normalizamos todos los parámetros dividiéndolos por su media geométrica para obtener los parámetros estimados p = [0,516, 1,413, 0,672, 2,041] . ${\displaystyle (0.429\times 1.172\times 0.557\times 1.694)^{1/4}=0.830}$

Para mejorar aún más las estimaciones, repetimos el proceso utilizando los nuevos valores de p . Por ejemplo,

$${\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.}$$

Repitiendo este proceso para los parámetros restantes y normalizando, obtenemos p = [0,677, 1,034, 0,624, 2,287] . Repetir 10 veces más produce una rápida convergencia hacia una solución final de p = [0,640, 1,043, 0,660, 2,270] . Esto indica que el equipo D es el más fuerte y el equipo B el segundo más fuerte, mientras que los equipos A y C son casi iguales en fuerza pero por debajo de los equipos B y D. De esta manera, el modelo Bradley-Terry nos permite inferir la relación entre los cuatro equipos. aunque no todos los equipos se han enfrentado entre sí.

Ver también

• Regresión ordinal
• modelo rasch
• Escala (ciencias sociales)
• Sistema de calificación Elo
• modelo thurstoniano

Referencias

1. Hunter, David R. (2004). "Algoritmos MM para modelos generalizados de Bradley-Terry". Los anales de la estadística . 32 (1): 384–406. CiteSeerX  10.1.1.110.7878 . doi :10.1214/aos/1079120141. JSTOR  3448514.
2. Agresti, Alan (2014). Análisis de datos categóricos . John Wiley e hijos. págs. 436–439.
3. EEM van Berkum. "Modelo Bradley-Terry". Enciclopedia de Matemáticas . Consultado el 18 de noviembre de 2014 .
4. Bradley, Ralph Allan; Terry, Milton E. (1952). "Análisis de rango de diseños de bloques incompletos: I. El método de comparaciones pareadas". Biometrika . 39 (3/4): 324–345. doi :10.2307/2334029. JSTOR  2334029.
5. Zermelo, Ernst (1929). "Die Berechnung der Turnier-Ergebnisse als ein Maximumproblem der Wahrscheinlichkeitsrechnung". Mathematische Zeitschrift . 29 (1): 436–460. doi :10.1007/BF01180541. S2CID  122877703.
6. Heinz-Dieter Ebbinghaus (2007), Ernst Zermelo: una aproximación a su vida y obra , Springer, págs. 268-269, ISBN 9783540495536
7. Shev, A.; Fujii, K.; Hsieh, F.; McCowan, B. (2014). "Pruebas sistémicas en el modelo Bradley-Terry frente a una jerarquía de clasificación no lineal". Más uno . 9 (12): e115367. doi : 10.1371/journal.pone.0115367 . PMC 4274013 . PMID  25531899. 
8. Boyd, Robert; Seda, Joan B. (1983). "Un método para asignar rangos cardinales de dominancia". Comportamiento animal . 31 (1): 45–58. doi :10.1016/S0003-3472(83)80172-9. S2CID  53178779.
9. "Chatbot Arena: nuevos modelos y actualización del sistema Elo | LMSYS Org". lmsys.org . Consultado el 30 de enero de 2024 .
10. Szummer, Martín; Yilmaz, Emine (2011). Aprendizaje semisupervisado para clasificar con regularización de preferencias (PDF) . CIKM.
11. Ford, hijo, LR (1957). "Solución de un problema de ranking a partir de comparaciones binarias". Mensual Matemático Estadounidense . 64 (8): 28–33. doi :10.1080/00029890.1957.11989117.
12. Dykstra, hijo, Otto (1956). "Una nota sobre el análisis de rango de diseños de bloques incompletos". Biometría . 12 : 301–306. doi :10.2307/2334029. JSTOR  2334029.
13. Newman, MEJ (2023). "Cálculo eficiente de clasificaciones a partir de comparaciones por pares". Revista de investigación sobre aprendizaje automático . 24 (238): 1–25.