A geometrical extension of the Bradley-Terry model

The Bradley-Terry (BT) model is a basic probability model for item ranking or user preference from paired comparison data. For example, it can be used for estimating intrinsic strength of football teams based on results in the league. Also it can be applied for solving multi-class discriminant problem with binary classifiers.

In the BT model, each item (or user) is given a positive value, and comparison result of two items is modeled by a Bernoulli distribution parametrized by the ratio of values given to these two items. So far, estimation methods of this model have been discussed from several contexts, and most of them are based on the maximum likelihood method, i.e. minimizing the sum of weighted Kullback-Leibler (KL) divergences between Bernoulli distributions and paired comparison data.

We focus on the following two important facts: 1) a set of normalized values given to items (sum up to 1) can be identified with a categorical distribution, 2) observations, i.e. paired comparison data, can be regarded as incomplete data from categorical distributions, and each observation constructs an m-flat submanifold in the space of categorical distributions represented as a probability simplex. Based on these notions, we construct an objective function with the sum of KL divergences between a categorical distribution and a submanifold, and derive an em-like algorithm, which is an iterative estimation method with e-projections and m-projections. Moreover, by considering the geometrical relationship between empirical influence functions and m-flat submanifolds, we can introduce a natural estimation method of confidence in each observation. We will demonstrate effectiveness and advantages of our proposal with synthetic and real-world data.

This work was done in collaboration with my colleague, Yu Fujimoto and Hideitsu Hino.