5
$\begingroup$

I have to solve a ranking ML issue. To start with, I have successfully applied the pointwise ranking approach.

Now, I'm playing around with pairwise ranking algorithms. I've created the pairwise probabilities (i.e. probability of item i being above item j) but I'm not sure how I can transform this to rankings.

For the historical data (let's assume these are queries), I have their pairwise probs AND the actual ranking (the ideal one). I want a solution that will provide a ranking for a new query as well (i.e. the ideal ranking is what I'm looking for here).

Any python package that has, at least partially, the functionality I'm looking for?

EDIT: I have the pairwise probs for for all possible pairs of i and j.

$\endgroup$
6
$\begingroup$

Pairwise comparison models such as that of Bradley and Terry can easily be extended to your case, when you have pairwise comparison probabilities instead of binary outcomes.

Let $N$ be the number of items, and let $p_{ij}$ be the probability that query $j$ is better than query $i$. Then, the log-likelihood of the Bradley-Terry parameters $\lambda_1, \ldots, \lambda_N$ given probabilities $\{ p_{ij} \}$ is

$$ \sum_{i,j} p_{ij} [\log(\lambda_j) - \log(\lambda_i + \lambda_j)] $$

This can be reparametrized into a convex function, and the maximum-likelihood parameters can be found by one of many convex opimization methods.

Here is a simple Python algorithm that will find the ML estimate, using a minorization-maximization approach.

import numpy as np

def mle(pmat, max_iter=100):
    n = pmat.shape[0]
    wins = np.sum(pmat, axis=0)
    params = np.ones(n, dtype=float)
    for _ in range(max_iter):
        tiled = np.tile(params, (n, 1))
        combined = 1.0 / (tiled + tiled.T)
        np.fill_diagonal(combined, 0)
        nxt = wins / np.sum(combined, axis=0)
        nxt = nxt / np.mean(nxt)
        if np.linalg.norm(nxt - params, ord=np.inf) < 1e-6:
            return nxt
        params = nxt
    raise RuntimeError('did not converge')

Example usage:

import itertools

# Generating pairwise probability matrix.
pmat = np.zeros((10, 10))
for i, j in itertools.permutations(range(10), r=2):
    pmat[i][j] = (j + 1) / (i + j + 2)

# Estimating Bradley-Terry model parameters.
params = mle(pmat)

# Ranking (worst to best).
ranking = np.argsort(params)

Source: I am an author of a Python library for parameter inference in various statistical comparison models, choix.

$\endgroup$
2
  • $\begingroup$ I tried it on a fake small dataset and it does not return the ranking I was expecting (this doesn't mean there's something wrong with your code of course). I'm not sure how I can share with you what I'm testing. $\endgroup$ – Stergios May 23 '17 at 7:55
  • $\begingroup$ Will this only work with a square matrix (pmat)? $\endgroup$ – Jarad Jul 8 '19 at 19:42
1
$\begingroup$

I believe you can find some material in David Barber's book Bayesian Reasoning and Machine Learning. Check out chapter 22 for 'rankings from pairwise comparisons'. The book has a MATLAB toolbox with a Rasch model function implemented there. Ranking models such as the Bradley-Terry-Luce are modifications from the Rasch model, so I believe this code can provide you a head start. The routines are small, so converting from MATLAB to Python will not be very difficult.

$\endgroup$
0
$\begingroup$

One option is to create a directed acyclic graph (DAG) from the pairwise probabilities, where the nodes are the items and the direction of the connections are driven by the pairwise probabilities (the connection goes from item A to item B if p(A > B) > 0.5, else the connection goes from B to A), and then compute the topological sorting of the graph. This would give you a sequence of nodes that respects the pairwise orderings derived from the probabilities.

The python code to implement topological sort can be implemented from the algorithm, but there are python packages like toposort.

$\endgroup$
2
  • 1
    $\begingroup$ Do you think this would also work in case of inconsistent pairwise rankings e.g. q1> q2, q2>q3 but q3>q1? Also, this ignores the probabilities and just cares about one item being above another one, is that right? $\endgroup$ – Stergios May 9 '17 at 8:50
  • $\begingroup$ You are right, the inconsistent pairwise rankings would lead to cycles, making the graph cyclic and hence topological sort would not be applicable. Cycles should therefore be resolved before. And you are right that this approach does not care about the actual values of the probabilities, but only if they are above an arbitrary threshold. $\endgroup$ – noe May 16 '17 at 9:24
0
$\begingroup$

Use a framework for ranking that is designed to supporting ranking, such as the Bradley-Terry model. See also Elo rankings and all the general statistical theory on pairwise comparison.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.