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 real positiva asignada al individuo i . La comparación i > j puede leerse como " i es preferible a j ", " i ocupa un lugar más alto que j " o " i supera a j ", según 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 partido contra j . ^{[1] [2]} O p _i podría representar la calidad o deseabilidad de un producto comercial y la probabilidad de que un consumidor prefiera el producto i sobre el producto j . ${\displaystyle \Pr(i>j)}$ ${\displaystyle \Pr(i>j)}$

El modelo Bradley-Terry se puede utilizar en la dirección hacia adelante para predecir resultados, como se describió, pero se utiliza más comúnmente en sentido inverso para inferir las puntuaciones p _i dado un conjunto observado de resultados. ^[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 vino, por ejemplo, puede ser difícil para los encuestados dar una clasificación completa de un gran conjunto de vinos, pero relativamente fácil para ellos comparar pares de vinos de muestra y decir cuál creen que es mejor. Con base en un conjunto de tales comparaciones por pares, el modelo Bradley-Terry se puede utilizar para derivar 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 sentido progresivo, por ejemplo, para predecir el resultado probable de comparaciones que todavía no se han producido. En el ejemplo de la encuesta sobre el vino, por ejemplo, se podría calcular la probabilidad de que alguien prefiera el vino al vino , incluso si nadie en la encuesta comparara directamente ese par en particular. ${\displaystyle i}$ ${\displaystyle j}$

Historia y aplicaciones

El modelo recibe su 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 la década de 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 de comparación por pares de elección del consumidor , análisis de jerarquías de dominio dentro de comunidades animales y humanas, ^[8] clasificación de revistas , clasificación de modelos de IA, ^[9] y estimación de la relevancia de documentos en motores de búsqueda con 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 varias otras. Bradley y Terry definieron las funciones de puntuación exponencial , 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, uno normalmente conoce los parámetros e intenta inferir la forma funcional de ; en la clasificación según el modelo Bradley-Terry, uno 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 es equivalente al sistema de clasificación Elo para jugadores con clasificaciones 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}}}.}$

Estimación de 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 la 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 competencias por pares entre un determinado grupo de individuos y que w _ij es 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 verosimilitud 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 único máximo, que se puede encontrar diferenciando con respecto a y fijando el resultado en cero, lo que conduce a ${\displaystyle p_{i}}$

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

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

Este procedimiento de estimación mejora la verosimilitud logarítmica en cada iteración y se garantiza que finalmente se alcance el máximo único. ^{[5] [11]} Sin embargo, es lento para converger. ^{[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

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

Ejemplo práctico 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 indican en las filas de la tabla siguiente y los oponentes en las columnas:

Por ejemplo, el equipo A venció al equipo B dos veces y perdió contra 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 que hacemos calculando los parámetros , donde los parámetros más altos indican 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 utilizar el nuevo valor 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 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] . Repitiendo otras 10 veces, obtenemos una convergencia rápida 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 hayan jugado entre sí.

Véase también

• Regresión ordinal
• Modelo de Rasch
• Escala (ciencias sociales)
• Sistema de clasificación Elo
• Modelo thurstoniano

Referencias

1. Hunter, David R. (2004). "Algoritmos MM para modelos Bradley-Terry generalizados". Anales de 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 & Sons. 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 rangos de diseños de bloques incompletos: I. El método de comparaciones por pares". 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 del modelo Bradley-Terry frente a una jerarquía de clasificación no lineal". PLOS One . 9 (12): e115367. doi : 10.1371/journal.pone.0115367 . PMC 4274013 . PMID  25531899. 
8. Boyd, Robert; Silk, Joan B. (1983). "Un método para asignar rangos de dominancia cardinal". Animal Behaviour . 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, Martin; Yilmaz, Emine (2011). Aprendizaje semisupervisado para clasificar con regularización de preferencias (PDF) . CIKM.
11. Ford, Jr., LR (1957). "Solución de un problema de clasificación a partir de comparaciones binarias". American Mathematical Monthly . 64 (8): 28–33. doi :10.1080/00029890.1957.11989117.
12. Dykstra, Jr., Otto (1956). "Una nota sobre el análisis de rangos de diseños de bloques incompletos". Biometrics . 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 en aprendizaje automático . 24 (238): 1–25.