Could you say more about the efficient sampling through convolutions? Bad interactive latency was a major reason I didn't spend any time exploring Bayesian approaches for my quick-and-dirty resorter script.
I take it you are not using a conjugate approach for fast exact estimates, nor a Laplacian approximation, nor full slow MCMC, but I'm not sure what sort of speed you actually get from your approach.
The bottleneck for sampling from the posterior is sampling from the truncated normal distribution, which I'm doing using this implementation of minimax tilting rejection sampling. It's not exactly instant, but on my laptopt it's a few CPU-ms/sample up to ~100 comparisons and 50 CPU-ms up to ~200 comparisons. This probably prevents it from being useful for lists with many hundreds of items, but I've found it to be fine for interactive use since selecting the next comparison doesn't require any sampling. The only thing which is prohibitively slow (for me at least) is computing the entropy of the full posterior since it involves so many evaluations of .
Fullrank is an interactive CLI tool for Bayesian inference of list rankings based on noisy comparisons. It takes a list of items, then efficiently prompts the user to compare pairs of items until the user decides that the posterior distribution is sufficiently low entropy. It can then sample from the resulting posterior distribution and compute various statistics.
Deterministic sorting algorithms rank lists by comparing pairs of items. If an item is greater than another, it is moved higher in the list. However, sometimes it is uncertain which item is greater. For example:
Estimating rankings in the presence of this uncertainty is called noisy sorting. A common approach is to model comparisons between items as depending on a latent numerical value ("skill" or "rating") for each item. For example, the commonly used Bradley–Terry model assumes that
where denotes the latent skill of item and is the logistic function.
@gwern's Resorter is a CLI tool for noisy sorting of lists based on the Bradley–Terry model. However, its frequentist approach limits it in a few ways:
As a project to learn more about Bayesian inference, I decided to build a Bayesian version of Resorter.
The Bradley–Terry model is quite nice for maximum-likelihood estimation, but I was unable to get it to work well in a Bayesian setting. Given a normal prior on the skills , the posterior density is
where denotes the normal density, is the number of comparisons, and and are the winning and losing items in comparison . It appears some researchers have designed efficient sampling procedures for this posterior, but frankly they are beyond me.
Instead, I used a probability model very similar to Bradley–Terry, but using a probit link instead of a logit link. That is, under the Thurstonian model,
where denotes the cumulative distribution function of the standard normal distribution.
I'll now derive the posterior density in the Thurstonian model. For convenience, I'll represent the observed comparisons as a matrix mapping score vectors to probits for each comparison. That is, if item wins comparison , if item loses comparison , and otherwise.
where and .
It turns out that the normalization constant can be represented quite nicely using the multivariate normal CDF :
And since , we have
Likewise, . Therefore,
This is called a unified skew-normal (SUN) distribution, and it is the posterior of most probit models. Using the convention of Arrellano-Valle and Azzalini[1], we can write
Arrellano-Valle and Azzalini[1:1] also gives us a convolutional representation of the posterior. If
where denotes the normal distribution truncated below , then
Fullrank exploits this fact to efficiently sample from the posterior using samples of and .
Ideally, Fullrank should always present the user with the most informative comparison. That is, the comparison whose probit has maximal entropy.
Unified skew-normal distributions are closed under full-rank linear transformations, so each comparison probit is distributed according to a one-dimensional SUN distribution. At least in the case of a standard normal prior, each comparison has identical first and second moments, so intuitively the entropy should be controlled by the skewness.
Fullrank currently assumes that the entropy is decreasing in the norm of the skewness parameter , which seems to work well in practice. However, I haven't been able to prove that this works, and it definitely fails for certain non-scalar choices of prior covariance (though these are currently not supported anyway). If you have any better ideas for choosing comparisons, please let me know!