Fullrank是一款交互式命令行工具，用于在存在不确定性的情况下对列表进行排序。它采用贝叶斯推理方法，通过询问用户对项目进行两两比较，直到后验分布的熵足够低。与传统的频率学方法不同，Fullrank基于Thurstonian模型，使用概率模型来处理不确定性，并提供了一种更 principled 的方式来量化排序的准确性并决定何时停止比较。该工具能够回答“项目 i 真正是最佳项目的概率是多少？”这类问题，并能高效地从后验分布中采样，计算各种统计量。Fullrank为处理带有噪声的列表排序问题提供了一个强大的贝叶斯解决方案。

📊 **Fullrank的贝叶斯推理核心**：Fullrank是一个交互式命令行工具，专门用于在存在不确定性的情况下对列表进行排序。它引入了贝叶斯推理方法，通过引导用户对列表中的项目进行两两比较，逐步收集信息，直到对项目排名的后验分布拥有足够低的熵（即不确定性降低）。这种方法与传统的频率学方法不同，能更有效地处理“噪声比较”的情况，例如在评估AI模型性能或用户偏好时，往往存在不确定性，而非简单的“大于”或“小于”。

📈 **Thurstonian模型与Bradley-Terry模型的对比**：文章详细介绍了Fullrank使用的Thurstonian模型，该模型基于概率模型p(i>j)=Φ(si-sj)，其中Φ是标准正态累积分布函数，si是项目i的潜在技能值。这与Bradley-Terry模型（p(i>j)=σ(si-sj)，σ为Logit函数）有所不同。作者提到Bradley-Terry模型在贝叶斯设置下难以处理，而Thurstonian模型在后验分布的推导上更为便利，并最终导出了一种称为“统一偏态正态（SUN）”的后验分布，Fullrank正是利用了这一分布的特性进行高效采样。

💡 **高效采样与最优比较选择**：Fullrank利用了SUN分布的卷积表示，通过对特定分布（如截断正态分布）进行采样，从而高效地从后验分布中提取信息。在选择下一个最能提供信息的比较时，Fullrank当前假设熵随偏斜参数的L2范数减小而减小，以此来指导用户进行最有效的比较，从而更快地收敛到可靠的排序结果。作者也欢迎社区就更优的比较选择策略提出建议。

🤔 **Fullrank的优势与应用场景**：相比于其频率学前身，Fullrank提供了量化排序准确性的 principled 方法，并能回答关于项目相对排名的概率性问题，这是频率学方法难以做到的。这使得Fullrank在需要精确评估和理解不确定性排序的场景中具有显著优势，例如在专家评估、用户偏好调查、机器学习模型能力比较等领域。

Published on July 24, 2025 7:03 PM GMT

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.

GitHub Repository

Background

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:

The best chess player wins only 60% of their non-draw games against the second-best player.Only three-quarters of human raters prefer one LLM completion over another.A person prefers one food over another, but only on 80% of days.

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

$$p(i>j)=\sigma (s_i-s_j)$$

where $s_i$ denotes the latent skill of item $i$ and $\sigma$ is the logistic function.

Motivation

@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:

It has to use imperfect heuristics to guess which comparison is most informative.There's no principled way to quantify how accurate the resulting maximum-likelihood ranking is, or tell when to stop comparing items.It can't answer questions like "What is the probability that item $i$ is truly the best item?"

As a project to learn more about Bayesian inference, I decided to build a Bayesian version of Resorter.

Thurstonian Model

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 $s\sim N(\mu ,\Sigma )$, the posterior density is

$$p(s|w>l)=\varphi (s;\mu ,\Sigma )\prod _i^m\sigma (s{w}_i-s{l}_i){\left[{\int }_{R^n}\varphi \right(s;\mu ,\Sigma \left)\prod _i^m\sigma \right(s{w}_i-s{l}_i\left)ds\right]}^{-1}$$

where $\varphi$ denotes the normal density, $m$ is the number of comparisons, and $w_i$ and $l_i$ are the winning and losing items in comparison $i$. 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,

$$p(i>j)=\Phi (s_i-s_j)$$

where $\Phi$ 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 $D\in R^{m\times n}$ mapping score vectors to probits for each comparison. That is, $D_{ij}=1$ if item $j$ wins comparison $i$, $D_{ij}=-1$ if item $j$ loses comparison $i$, and $D_{ij}=0$ otherwise.

$$\begin{array}{cc}p\left(s|D\right)& =p\left(s\right)\frac{p\left(D|s\right)}{p\left(D\right)}\\ & =\varphi (s;\mu ,\Sigma )\frac{Pr[Ds<z]}{Pr[Dt<z]}\end{array}$$

where $t\sim N(\mu ,\Sigma )$ and $z\sim N(0,I_m)$.

It turns out that the normalization constant can be represented quite nicely using the multivariate normal CDF ${\Phi }_m$:

$$\begin{array}{cc}Pr[Dt<z]& =Pr\left[D\right(t-\mu )+D\mu <z]\\ & =Pr[D\mu <z-D(t-\mu \left)\right]\end{array}$$

And since $D(t-\mu )\sim N(0,D\Sigma D^T)$, we have

$$\begin{array}{cc}z-D(t-\mu )& \sim N(0,I_m+D\Sigma D^T)\\ Pr[Dt<z]& ={\Phi }_m(D\mu ;I_m+D\Sigma D^T)\end{array}$$

Likewise, $Pr[Ds<z]=\Phi \left(Ds\right)$. Therefore,

$$p\left(s|D\right)=\varphi (s;\mu ,\Sigma ){\Phi }_m\left(Ds\right)\left[{\Phi }_m\right(D\mu ;I_m+D\Sigma D^T\left)\right]-1$$

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

$$s|D\sim {\text{SUN}}_{n,m}(\mu ,\Sigma ,{\Sigma }^{T}D,D\mu ,I_m+D\Sigma D^T)$$

Efficient Sampling

Arrellano-Valle and Azzalini^[1:1] also gives us a convolutional representation of the posterior. If

$$\begin{array}{cc}u& \sim N(0,\Sigma -{\Sigma }^{T}D(I_m+D\Sigma D^T{)}^{-1}{D}^T\Sigma ),\text{and}\\ v& \sim N_{-D\mu }(0,I_m+D\Sigma D^T)\end{array}$$

where $N_{\tau }$ denotes the normal distribution truncated below $\tau$, then

$$\mu +u+{\Sigma }^{T}D(I_m+D\Sigma D^T{)}^{-1}v\sim {\text{SUN}}_{n,m}(\mu ,\Sigma ,{\Sigma }^{T}D,D\mu ,I_m+D\Sigma D^T)$$

Fullrank exploits this fact to efficiently sample from the posterior using samples of $u$ and $v$.

Optimal Comparison Choice

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 $L_2$ norm of the skewness parameter $\Delta ={\Sigma }^{T}D$, 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!

---

R. B. Arellano-Valle and A. Azzalini, "Some properties of the unified skew-normal distribution," Statistical Papers, vol. 63, pp. 461–487, 2022. doi:10.1007/s00362-021-01235-2 ↩︎ ↩︎

Discuss