Bayesian nonparametric models for ranked data

Introduction

Data in the form of partial rankings, i.e. in terms of an ordered list of the top-$m$ items, arise in many contexts. For example, in this paper we consider datasets consisting of the top 20 bestselling books as published each week by the New York Times. The Plackett-Luce model is a popular model for modeling such partial rankings of a finite collection of $M$ items. It has found many applications, including choice modeling , sport ranking , and voting . [6, Chap. 9] provides detailed discussions on the statistical foundations of this model.

In the Plackett-Luce model, each item $k\in[M]=\{1,\ldots,M\}$ is assigned a positive rating parameter $w_{k}$, which represents the desirability or rating of a product in the case of choice modeling, or the skill of a player in sport rankings. The Plackett-Luce model assumes the following generative story for a top-$m$ list $\rho=(\rho_{1},\ldots,\rho_{m})$ of items $\rho_{i}\in[M]$: At each stage $i=1,\ldots,m$, an item is chosen to be the $i$th item in the list from among the items that have not yet appeared, with the probability that $\rho_{i}$ is selected being proportional to its desirability $w_{\rho_{i}}$. The overall probability of a given partial ranking $\rho$ is then:

with the denominator in (1) being the sum over all items not yet selected at stage $i$.

In many situations the collection of available items can be very large and potentially unknown. In this case, a nonparametric approach can be sensible, where the pool of items is assumed to be infinite and the model allows for the possibility of items not observed in previous top-$m$ lists to appear in new ones. In this paper we propose such a Bayesian nonparametric Plackett-Luce model. Our approach is built upon recent work on Bayesian inference for the (finite) Plackett-Luce model and its extensions . Our model assumes the existence of an infinite pool of items $\{X_{k}\}_{k=1}^{\infty}$, each with its own rating parameter, $\{w_{k}\}_{k=1}^{\infty}$. The probability of a top-$m$ list of items, say $(X_{\rho_{1}},\ldots,X_{\rho_{m}})$, is then a direct extension of the finite case (1):

To formalize the framework, a natural representation to encapsulate the pool of items along with their ratings is using an atomic measure:

Using this representation, note that the top item $X_{\rho_{1}}$ in our list is simply a draw from the probability measure obtained by normalizing $G$, while subsequent items in the top-$m$ list are draws from probability measures obtained by first removing from $G$ the atoms corresponding to previously picked items and normalizing. Described this way, it is clear that the Plackett-Luce model is basically a partial size-biased permutation of the atoms in $G$ , and the existing machinery of random measures and exchangeable random partitions can be brought to bear on our problem.

In particular, in Section 2 we will use a gamma process as the prior over the atomic measure $G$. This is a completely random measure with gamma marginals, such that the corresponding normalized probability measure is a Dirichlet process. We will show that with the introduction of a suitable set of auxiliary variables, we can characterize the posterior law of $G$ given observations of top-$m$ lists distributed according to (2). A simple Gibbs sampler can then be derived to simulate from the posterior distribution. In Section 3 we develop a time-varying extension of our model and derive a simple and effective Gibbs sampler for posterior simulation. In Section 4 we apply our time-varying Bayesian nonparametric Plackett- Luce model to the aforementioned New York Times bestsellers datasets, and conclude in Section 5.

A Bayesian nonparametric model for partial ranking

A nonparametric Plackett-Luce model can now be easily derived by taking the limit as the number of choice items $M\rightarrow\infty$. For those items $k$ that have appeared among the observed partial rankings, the limiting conditional distribution (5) is well defined since $n_{k}>0$. For items that did not appear in the observations, (5) becomes degenerate at 0. Instead we can define $w_{*}=\sum_{k:n_{k}=0}w_{k}$ to be the total desirability among all infinitely many previously unobserved items, and show that

2 A Bayesian nonparametric Plackett-Luce model

The above construction is depicted on Figure 1(left). We visualize on right some top-$m$ lists generated from the model, with $\tau=1$ and different values of $\alpha$.

3 Posterior characterization

The joint probability of the item lists and auxiliary variables is then (c.f. (7)):

Taking expectation of (13) with respect to $G$ using the Palm formula gives:

The marginal probability of the $L$ partial rankings and auxiliary variables is:

where $\psi(z)$ is the Laplace transform of $\lambda$,

and $\kappa(n,z)$ is the $n$th moment of the exponentially tilted Lévy intensity $\lambda(w)e^{-zw}$:

Details are given in the appendix. Another application of the Palm formula now allows us to derive a posterior characterisation of $G$:

where $G^{*}$ and $w^{*}_{1},\ldots,w^{*}_{K}$ are mutually independent. The law of $G^{*}$ is still a gamma process,

4 Gibbs sampling

Note that this update was derived with $w^{*}_{*}$ marginalized out, so after an update to $\alpha$ it is necessary to immediately update $w^{*}_{*}$ via (22) before proceeding to update other variables.

Dynamic Bayesian nonparametric ranking models

In this section we develop an extension of the Bayesian nonparametric Plackett-Luce model to model time-varying rankings, where the rating parameters of items may change smoothly over time and reflected in a changing series of rankings. Given a series of times indexed by $t=1,2,\ldots$, we may model the rankings at time $t$ using a gamma process distributed random measure $G_{t}$ as in Section 2.2, with Markov dependence among the sequence of measures $(G_{t})$ enabling dependence among the rankings over time.

We will construct a dependent sequence $(G_{t})$ which marginally follow a gamma process $\Gamma(\alpha,\tau,H)$ using the construction of . Suppose $G_{t}\sim\Gamma(\alpha,\tau,H)$. Since $G_{t}$ is atomic, we can write it in the form:

Define a random measure $C_{t}$ with conditional law:

where $\phi_{t}>0$ is a dependence parameter. Using the same method as in Section 2.3, we can show:

Suppose the law of $G_{t}$ is $\Gamma(\alpha,\tau,H)$. The conditional law of $G_{t}$ given $C_{t}$ is then:

where $G_{t}^{*}$ and $(w^{*}_{tk})_{k=1}^{\infty}$ are all mutually independent. The law of $G_{t}^{*}$ is given by a gamma process, while the masses are conditionally gamma,

The idea of is to define the conditional law of $G_{t+1}$ given $G_{t}$ and $C_{t}$ to coincide with the conditional law of $G_{t}$ given $C_{t}$ as in Proposition 3. In other words, define

where $G_{t+1}^{*}\sim\Gamma(\alpha,\tau+\phi_{t},H)$ and $w_{t+1,k}\sim\operatorname{Gamma}(c_{tk},\tau+\phi_{t})$ are mutually independent. If the prior law of $G_{t}$ is $\Gamma(\alpha,\tau,H)$, the marginal law of $G_{t+1}$ will be $\Gamma(\alpha,\tau,H)$ as well when both $G_{t}$ and $C_{t}$ are marginalized out, thus maintaining a form of stationarity. Further, although we have described the process in order of increasing $t$, the joint law of $G_{t},C_{t},G_{t+1}$ can equivalently be described in the reverse order with the same conditional laws as above. Note that if $c_{tk}=0$, the conditional distribution of $w_{t+1,k}$ will be degenerate at 0. Hence $G_{t+1}$ has an atom at $X_{tk}$ if and only if $C_{t}$ has an atom at $X_{tk}$, that is, if $c_{tk}>0$. In addition, it also has atoms (those in $G_{t+1}^{*}$) where $C_{t}$ does not (nor does $G_{t}$). Finally, the parameter $\phi_{t}$ can be interpreted as controlling the strength of dependence between $G_{t+1}$ and $G_{t}$. Indeed it can be shown that

Another measure of dependence can be gleaned by examining the “lifetime” of an atom. Suppose $X$ is an atom in $G_{1}$ with mass $w>0$. The probability that $X$ is an atom in $C_{2}$ with positive mass is $1-\exp(-\phi_{1}w)$, in which case it has positive mass in $G_{2}$ as well. Conversely, once it is not an atom, it will never be an atom in the future since the base distribution $H$ is non-atomic. The lifetime of the atom is then the smallest $t$ such that it is no longer an atom. We can show by induction that: (details in appendix)

The probability that an atom $X$ in $G_{1}$ with mass $w>0$ is dead at time $t$ is given by

where $y_{t|1}$ can be obtained by the recurrence $y_{t|t-1}=\phi_{t-1}$ and $y_{t|s-1}=\frac{y_{t|s}\phi_{s-1}}{\phi_{s-1}+\tau+y_{t|s}}$.

2 Posterior characterization and Gibbs sampling

Assume for simplicity that at each time step $t=1,\ldots,T$ we observe one top-$m$ list $Y_{t}=(Y_{t1},\ldots,Y_{tm})$ (it trivially extends to multiple partial rankings of differing sizes). We extend the results of the previous section in characterizing the posterior and developing a Gibbs sampler for the dynamical model.

3 Continuous time formulation using superprocesses

with $\xi$ parametrizing the rate of evolution. Figure 2 gives a sample path, where we see that it is continuous but non-differentiable.

For efficient inference, it is desirable to be able to integrate out all $G_{t}$’s except those $G_{t_{1}},G_{t_{2}},\ldots$ at observation times. An advantage to using the Dawson-Watanabe superprocess is that, the conditional distribution of $G_{t_{s}}$ given $G_{t_{s-1}}$ is remarkably simple . In particular it is simply given by the discrete-time process of the previous section with dependence parameter $\phi_{t_{s}|t_{s-1}}=\frac{\tau}{e^{\tau\xi(t_{s}-t_{s-1})}-1}.$ Thus the inference algorithm developed previously is directly applicable to the continuous-time model too.

Experiments

We apply the discrete-time dynamic Plackett-Luce model to the New York Times bestsellers data. These consist of the weekly top-20 best-sellers list from June 2008 to April 2012 in various categories. We consider here the categories paperback nonfiction (PN) and hardcover fiction (HF), for which respectively 249 and 916 books appear at least once in the top-20 lists over the 200 weeks. We consider that the correlation parameter $\phi_{t}=\phi$ is constant over time, and assign flat improper priors $p(\alpha)\propto 1/\alpha$ and $p(\phi)\propto 1/\phi$. In order to take into account the publication date of a book, we do not consider books in the likelihood before their first appearance in a list. We run the Gibbs sampler with 10000 burn-in iterations followed by 10000 samples. Mean normalized weights for the more popular books in both categories are shown in Figure 3.

The model is able to estimate the weights associated to each book that appeared at least once, as well as the total weight associated to all other books, i.e. the probability that a new book enters at the first rank in the list, represented by the black curve. Moreover, the Bayesian approach enables us to have a measure of the uncertainty on the weights. The hardcover fiction category is characterized by rapid changes in successive lists, compared to the paperback nonfiction. This is quantified by the estimated value of the parameter $\phi$, which are respectively $85\pm 20$ and $140\pm 40$ for PN and HF. The estimated values of the shape parameter $\alpha$ are $7\pm 1.5$ and $2\pm 1$ respectively.

Discussion

We have proposed a Bayesian nonparametric Plackett-Luce model for ranked data. Our approach is based on the theory of atomic random measures, where we showed that the Plackett-Luce generative model corresponds exactly to a size-biased permutation of the atoms in the random measure. We characterized the posterior distribution, and derived a simple MCMC sampling algorithm for posterior simulation. Our approach can be see as a multi-stage generalization of posterior inference in normalized random measures , and can be easily extended from gamma processes to general completely random measures.

We also proposed dynamical extensions of our model for both discrete and continuous time data, and applied it to modeling the bestsellers’ lists on the New York Times. Our dynamic extension may be useful for modeling time varying densities or clusterings as well. In our experiments we found that our model is insufficient to capture the empirical observation that bestsellers often start off high on the lists and tail off afterwards, since our model has continuous sample paths. We adjusted for this by simply not including books in the model prior to their publication date. It may be possible to model this better using models with discontinuous sample paths, for example, the Orstein-Uhlenbeck approach of where the process evolves via a series of discrete jump events instead of continuously.

Acknowledgements

YWT thanks the Gatsby Charitable Foundation for generous funding.

References

Appendix A Proof of Theorem 1

The marginal probability (14) is obtained by taking the expectation of (13) with respect to $G$. Note however that (13) is a density, so to be totally precise here we need to work with the probability of infinitesimal neighborhoods around the observations instead, which introduces significant notational complexity. To keep the notation simple, we will work with densities, leaving it to the careful reader to verify that the calculations indeed carry over to the case of probabilities.

Appendix B Proof of Theorem 2

The proof is essentially obtained by calculating the numerator and denominator of (32). The denominator is already given in Theorem 1. The numerator is obtained using the same technique with the inclusion of the term $e^{\int f(x)G(dx)}$, which gives:

Dividing the numerator (31) by the denominator (33), the characteristic functional of the posterior $G$ is:

Appendix C Proof of Proposition 4

Appendix D Gibbs sampler for the dynamic nonparametric Plackett-Luce model

For ease of presentation, we assume that $\phi_{t}$ takes the same value $\phi$ at each time step. The Gibbs sampler will iterate between the following steps

b. For $t=1,\ldots,T$, update $(c_{t},c_{t\ast})$ given $(w_{t},w_{t\ast},w_{t+1},w_{t+1\ast},\phi,\alpha)$

Update $w_{t\ast}$ given $(c_{t-1\ast},Z,\phi,\alpha)$

Update $c_{t\ast}$ given $(w_{t\ast},Z,\phi,\alpha)$

For $t=1,\ldots,T$, update ($w_{t},w_{t\ast})$ given $(c_{t-1},c_{t-1\ast},c_{t},c_{t\ast},Z_{t},\alpha,\phi)$

For $t=1,\ldots,T$, update $Z_{t}$ given $(w_{t},w_{t\ast})$

Update $\phi$ given $w,w_{\ast},\alpha,\phi$

1.b) Sample $(c,c_{\ast})$ given ($w,w_{\ast},\phi,\alpha)$

Consider first the sampling of $c_{1:T}$. We have, for $t=1,\ldots,T$ and $k=1,\ldots,K$

Hence we can have the following MH update. If $w_{t+1,k}>0$, then we necessarily have $c_{tk}>0$. We sample $c_{tk}^{\ast}\sim$zPoisson$(\phi w_{tk})$ where zPoisson$(\phi w_{tk})$ denotes the zero-truncated Poisson distribution and accept $c_{tk}^{\ast}$ w.p.

If $w_{t+1,k}=0$, we only have two possible moves: $c_{tk}=0$ or $c_{tk}=1$, given by the following probabilities

Note that the above Markov chain is not irreducible, as the probability is zero to go from a state $\left(c_{tk}>0,w_{t+1,k}>0\right)$ to a state $\left(c_{tk}=0,w_{t+1,k}=0\right)$, even though the posterior probability of this event is non zero in the case item $k$ does not appear after time $t$. We can resolve that by the following procedure, that uses a backward forward recursion.

Assume that item $k$ does not appear after time step $\tau_{k}^{+}$ (the same procedure applies if item $k$ does not appear before time step $\tau_{k}^{-}$). Then we can sample jointly the whole sequence $(w_{k,t},c_{k,t})_{t=\tau_{k}+1,\ldots,T}$ using the following backward forward recursion.

We have, for $k=1,\ldots,K$ and $t=\tau_{k}^{+}$

We can sample from the full conditional which is given by

where $x_{1}$ and $y_{1}$ are obtained with the following recursion

2.b) Sample $(c_{\ast},w_{\ast})$ given $(Z,\phi,\alpha)$

We can sample from the full conditional which is given by

where $x_{1}$ is defined above. Then for $t=2,\ldots,T$, let

3) Sample $(w,w_{\ast})$ given $\left(Z,\alpha,c,c_{\ast},\phi\right)$

if $c_{tk}+c_{t-1,k}+n_{tk}>0$, otherwise, set $w_{tk}=0.$ The occurence indicator $\delta_{tik}$ is defined as

For $t=1,\ldots,T$ and $i=1,\ldots m$, sample

5) Sample $\phi$ given $w,w_{\ast},\alpha,\phi$

We sample $\phi$ using a MH step. Propose $\widetilde{\phi}=\phi\exp(\sigma\varepsilon)$ where $\sigma>0$ and $\varepsilon\sim\mathcal{N}(0,1)$. And accept it with probability