< List of probability distributions > Mallows distribution
What is the Mallows distribution?
The Mallows distribution, or Mallows model, is used to model the order of rankings. It is an exponential probability distribution over permutations, based on distances. In the context of the Mallows distribution, distances — usually measured with Kendall’s Tau, are measures of similarity between two rankings. Introduced in the mid-1950s by Mallows [1], it is perhaps the most popular member of the distance-based ranking models, which also include the Thurstone, Pearson and Plackett-Luce models.
The Mallows distribution can be viewed as being like a normal distribution for permutations: given a center permutation with the highest probability value (π0) and a parameter for spread (θ,) the model defines a distribution for all permutations [2].
Mallows distribution properties
The Mallows distribution is parameterized by a parameter θ, which controls the amount of “disagreement” in the rankings. If θ = 0, then the Mallows distribution is the uniform distribution, which means that all rankings are equally likely. As θ increases, the Mallows distribution becomes more concentrated around the “most popular” ranking.
Formally, the Mallows distribution is a probability distribution that satisfies, for all rankings π ∈ 𝕊n:
where
- θ defines the concentration around the distribution’s peak π0,
- Rankings π0 and θ ≥ 0 are the model parameters,
- φ (0) is a normalizing constant [3],
- d is the distance in 𝕊n, which can be one of many distances including those defined by Kendall, Cayley and Spearman [4].
The most popular method for defining distance is Kendall’s Tau which is the number of concordant pairs minus the number of discordant pairs. A concordant pair is a pair of items that are ranked the same way in both rankings, while a discordant pair is a pair of items that are ranked in opposite ways in the two rankings. The Cayley distance is the number of transpositions (swaps) needed to transform one permutation into another. The distance measure defined by Spearman is the Spearman footrule distance.
If θ = 0, a uniform distribution is obtained; for θ = +∞, Mallows model assigns probabilities equal to 1 to π0 and zero for the remaining permutations [5].
Key challenges in using the Mallows distribution are the exponential support size and the absence of a closed-form expression for choice probabilities [6].
Other distance-based ranking models
While the most popular distance-based ranking model is Mallows — due to its simplicity — there are other models including Plackett-Luce, Bradley-Terry, Thurstone, and Spearman. These models estimate rankings using item distances based on various factors, such as similarity, voter preferences, or item values.
- The Plackett-Luce model and the Bradley-Terry model are based on pairwise comparisons. Both are popular but more complex.
- The Thurstone model focuses on item similarities and offers flexibility.
- The Spearman model, based on Spearman’s footrule distance, is a non-probabilistic model based on item values and serves as a benchmark.
Mallows Cp vs Mallows distribution
There is a relationship between the Mallows distribution and Mallows Cp. Mallows Cp serves as a criterion for model selection, and it is based on the Mallows distribution.
Mallows Cp is defined as the expected value of the residual sum of squares (RSS) for a model within the Mallows distribution. The RSS measures the fit of a model to the data, with a smaller RSS indicating a better fit.
In simple terms, Mallows Cp quantifies the expected fit of a model to the data, assuming that the true ranking follows the Mallows distribution. The lower the value of Mallows Cp, the greater the likelihood that the model is a good fit to the data.
References
[1] Mallows CL (1957) Non-null ranking models. Biometrika 44(1): 114–130.
[2] Chierichetti et. al. Mallows Models for Top-k Lists
[3] Recent Trends in Applied Artificial Intelligence. 26th International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2013, Amsterdam, The Netherlands, June 17-21, 2013, Proceedings. p. 104.
[4] Fligner & Verducci. Distance based ranking models. Journal of the Royal Statistical Society 48(3), 359-369 (1986).
[5] Symbolic and Quantitative Approaches to Reasoning with Uncertainty. 15th European Conference, ECSQARU 2019, Belgrade, Serbia, September 18-20, 2019, Proceedings. p. 353.
[6] Desir et. al. Mallows-Smoothed Distribution over Rankings Approach for Modeling Choice. OPERATIONS RESEARCH. Vol. 69, No. 4, July–August 2021 pp. 1206–1227.