Bradley-Terry Model for Pairwise Rankings
Retrieval & Ranking Systems DS practice problem on Onlearn.
Difficulty: medium.
Topics: Bradley-Terry Model for Pairwise Rankings, Logit Link Function, Newton-Raphson Iteration, Hessian Matrix Computation, Pairwise Preference Labels, Bradley-Terry Log-Likelihood, Probability Theory, Statistical Inference, Optimization Theory, Information Retrieval, Machine Learning Theory, Generalized Linear Models, Maximum Likelihood Estimation, Convex Optimization, Learning to Rank, Latent Variable Modeling.
Implement the Bradley Terry model, a probabilistic model for ranking items based on pairwise comparison outcomes. This model is widely used in sports rankings, recommendation systems, and LLM evaluation (e.g., Chatbot Arena leaderboards). The Bradley Terry model assumes that each item i has a latent strength parameter beta i. The probability that item i beats item j is modeled as: P(i beats j) = sigmoid(beta i beta j) = 1 / (1 + exp( (beta i beta j))) Given a dataset of pairwise comparison outcomes, your task is to estimate the strength parameters using maximum likelihood estimation via gradient ascent. Function to implement: fit bradley terry(comparisons, n items, learning rate, n iterations) Estimate strength parameters from comparison data. Args: comparisons: List of (winner idx, loser idx) tuples, where each tuple represents one comparison outcome n items: Total number of items being ranked learning rate: Step size for gradient ascent n iterations: Number of optimization iterations Returns: numpy array of shape (n items,) containing estimated strength parameters, centered so they sum to 0 Notes: Initialize all beta parameters to 0 After each gradient update, center the parameters by subtracting their mean (this handles the identifiability constraint) Use numerically stable sigmoid computation