Caron 2012 - Plackett-Luce Model for Full Rankings

Summary

The Plackett-Luce (PL) model generalises Bradley-Terry to ranked lists: pick the winner among all items with probability proportional to skill, remove it, repeat. A latent exponential variable per ranking position gives a Gamma Gibbs sampler and Hunter’s MM update as EM.

Overview

Racing results, preference orderings from surveys, and ranked search results are lists ${\rho }_i=({\rho }_{i1},\dots ,{\rho }_{i{p}_i})$ over $p_i\le K$ of the $K$ items. PL is the “exploded logit” of choice modelling: a sequence of multinomial-logit choices from shrinking choice sets (Discrete Choice Models).

Main Content

Plackett-Luce likelihood

$$P({\rho }_i\mid \lambda )=\prod _{j=1}^{p_i-1}\frac{{\lambda }_{{\rho }_{ij}}}{{\sum }_{k=j}^{p_i}{\lambda }_{{\rho }_{ik}}}.$$

The last position contributes a factor 1, so only $p_i-1$ stages appear.

Latent variables

For each ranking $i$ and stage $j=1,\dots ,p_i-1$: $Z_{ij}\sim \text{Exp}\left({\sum }_{k=j}^{p_i}{\lambda }_{{\rho }_{ik}}\right)$ (waiting time until the first of the remaining items arrives). Complete log-likelihood: $\ell (\lambda ,z)={\sum }_i{\sum }_{j<p_i}[\log {\lambda }_{{\rho }_{ij}}-({\sum }_{k\ge j}{\lambda }_{{\rho }_{ik}})z_{ij}]$.

EM and Gibbs for Plackett-Luce

Let $w_k$ = number of rankings in which item $k$ is not in the last position, and ${\delta }_{ijk}=1\{k\in \{{\rho }_{ij},\dots ,{\rho }_{i{p}_i}\}\}$.

• EM (MAP, prior $\mathcal{G}(a,b)$): ${\lambda }_k^{(t)}=\frac{a-1+w_k}{b+{\sum }_{i=1}^n{\sum }_{j=1}^{p_i-1}{\delta }_{ijk}/{\sum }_{k^{\prime }=j}^{p_i}{\lambda }_{{\rho }_{i{k}^{\prime }}}^{(t-1)}}$. For $a=1,b=0$ this is the Hunter (2004, p. 398) MM update.
• Gibbs: $Z_{ij}\sim \text{Exp}({\sum }_{k\ge j}{\lambda }_{{\rho }_{ik}}^{(t-1)})$, then ${\lambda }_k\sim \mathcal{G}(a+w_k,b+{\sum }_{i,j}{\delta }_{ijk}{Z}_{ij})$.

Proof sketch. The numerator count $w_k$ is the number of stages at which $k$ is the “winner”; the rate accumulates exposure $\sum {\delta }_{ijk}{Z}_{ij}$. This is the Poisson-process/exponential-family analogue of a Gamma-Poisson conjugate pair.

Extensions (stated in the paper): mixtures of PL models (Gormley & Murphy 2008) reuse the same augmentation for the within-component update.

Examples

Ranking four creatives

Setup. Five panelists rank creatives A-D: ABCD, ABCD, BACD, ABCD, ACBD. Flat prior. Solution. Wins in the sense of $w_k$: A is not last in 5 rankings, B in 5, C in 5, D in 0 (D is last in all five). So $w_D=0$ and the MLE for ${\lambda }_D$ is zero; the MLE does not exist as a finite positive value. Under the Gamma prior ($a>1$), ${\lambda }_D$ gets the posterior $\mathcal{G}(a+0,b+\dots )$, positive and shrunk. Interpretation. This is exactly the NASCAR issue (drivers always last) discussed in Caron 2012 - Experiments NASCAR and Chess; Hunter’s MLE required deleting such drivers, the Bayesian model does not.

import numpy as np
def pl_em(rankings, K, a=1.0, b=0.0, iters=300):
    lam = np.full(K, 1.0/K)
    w = np.zeros(K)
    for r in rankings:
        for k in r[:-1]: w[k] += 1
    for _ in range(iters):
        denom = np.full(K, b)
        for r in rankings:
            tail = np.array([lam[r[j:]].sum() for j in range(len(r)-1)])
            for j in range(len(r)-1):
                for k in r[j:]: denom[k] += 1.0/tail[j]
        lam = (a-1+w)/denom
        lam /= lam.sum()
    return lam
print(pl_em([[0,1,2,3],[0,1,2,3],[1,0,2,3],[0,1,2,3],[0,2,1,3]], 4, a=2, b=3))

PyMC-style sketch (untested): PL log-likelihood can be written with pm.math.logsumexp over suffix sets, or via pm.Potential; E67 applies it to Formula 1 finishing orders.

Connections

• PL with covariates is a rank-ordered (exploded) multinomial logit; see Discrete Choice Models and Random Coefficients Logit Model for heterogeneity beyond mixtures.
• PL is the likelihood behind some RLHF reward-model objectives when more than two responses are ranked (Reward Modeling from Human Preferences).

See Also

Caron 2012 - Home Advantage, Ties and Team Comparisons · Caron 2012 - Identifiability, Hyperparameters and Further Extensions