summaries: This paper is in the field of Active learning, which has proven to be useful for minimizing labeling costs by selecting the most informative samples from unlabeled datasets, which are then to be labeled by a human in the loop. The goal is to achieve high accuracy of the trained model, while minimising the number of points to be labeled by the human in the loop. However, as the authors say, many existing state of the art active learning methods are trained on datasets which are not very realistic, and they do not perform well in many common real-life situations such as imbalance or rare classes, out-of-distribution data in the unlabeled set, and redundancy. Given the size of these datasets, cleaning them manually is not realistic. The authors propose an active learning framework which they call SIMILAR, which uses submodular information measures as acquisition functions. They argue that SIMILAR performs well on the realistic scenarios mentioned previously, and empirically demonstrate that SIMILAR outperforms previous state of the art methods in these scenarios.

summaries: In this paper, the authors propose methods for selecting a query set for batch active learning. These methods select a query set by maximizing a criterion based on submodular functions such as facility location function, graph cut function, and log-determinant function. The similarity matrix between data points, used in the definition of submodular functions, is defined by the inner product of the gradients of loss functions.  The authors empirically validate the efficiency of the proposed methods for batch active learning with rare classes, redundancy, and out-of-distribution data points. They adopt standard image datasets and standard deep neural network models. In each experimental setting, some of the proposed methods outperform existing methods for batch active learning.

summaries: This paper proposes a "unified active learning framework". The key element of this framework is a submodular information measure, denoted by $I_f(A;Q|P)$ where $f$ is a submodular score function, $A$ is a set of unlabeled samples whose "value" is measured, and $P$ and $Q$ are set of samples to be specified by the algorithm as parameters. $I_f(A;Q|P)$ is supposed to measure similarity and dissimilarity among $A$, $P$, and $Q$. In each round of the proposed "unified active learning framework", it chooses $A$ that maximizes $I_f$. By choosing $P$ and $Q$ properly (for example, for the class imbalance task, setting $Q$ to be a small labeled sample set from rare classes), this paper shows empirically the proposed algorithm outperforms other active learning algorithms on various tasks, including standard AL, AL with class imbalance, AL with redundant data, and AL with out of distribution data.

summaries: In this paper, the authors propose a new diversity based active learning algorithm by utilizing a series of information functions in submodular optimization (SO) problems. Specifically, they consider three submodular information measures (SIM) in SO: Submodular Mutual Information (SMI), Submodular Conditional Gain (SCG) and Submodular Conditional Mutual Information (SCMI) and found that SCMI ($I_f(\mathbf{A};\mathbf{Q}|\mathbf{P})$) is the most expressive SIM such that one could tailor $\mathbf{Q}$ and $\mathbf{P}$ to represent SCG and SMI, and thus propose to use it as a “unified” acquisition function for tackling three scenarios in realistic AL: rare class due to class imbalance, redundant data and out-of-distribution(OOD) data. The basic idea is to specify $\mathbf{Q}$ and $\mathbf{P}$ depending on the desired/un-desired classes, such that one could condition on data region that they want to exclude (OOD, redundant data), while up-sample regions that one want to include (rare class) by considering the mutual information w.r.t that region. To instantiate SIM acquisition function, the authors borrow the utility function from three well known graph-based SO problems for diversity coverage: Facility location (FL), Graph cut (GC) and Log Determinant (LOGDET), and use the similarity kernels computed with pairwise cosine similarity of the last layer gradients w.r.t the model-predicted label for every pair of unlabeled data points. They experiment with synthetic datasets rooted from MNIST/CIFAR-10/ImageNet to test for the three special scenarios, and show promising results against several strong baselines including BADGE.

abstractText: Active learning has proven to be useful for minimizing labeling costs by selecting the most informative samples. However, existing active learning methods do not work well in realistic scenarios such as imbalance or rare classes, out-of-distribution data in the unlabeled set, and redundancy. In this work, we propose SIMILAR (Submodular Information Measures based actIve LeARning), a unified active learning framework using recently proposed submodular information measures (SIM) as acquisition functions. We argue that SIMILAR not only works in standard active learning but also easily extends to the realistic settings considered above and acts as a one-stop solution for active learning that is scalable to large real-world datasets. Empirically, we show that SIMILAR significantly outperforms existing active learning algorithms by as much as ≈ 5%− 18% in the case of rare classes and ≈ 5%− 10% in the case of out-of-distribution data on several image classification tasks like CIFAR-10, MNIST, and ImageNet. SIMILAR is available as a part of the DISTIL toolkit: https://github.com/decile-team/distil.

authors:
Sami Abu-El-Haija
Nisarg Kothari
Joonseok Lee
Paul Natsev
George Toderici
Balakrishnan Varadarajan
Sudheendra Vijayanarasimhan

title: Youtube-8m: A large-scale video classification benchmark

venue: arXiv preprint arXiv:1609.08675,

authors:
David Arthur
Sergei Vassilvitskii

title: k-means++: the advantages of careful seeding

venue: In SODA ’07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms,

authors:
Jordan T Ash
Chicheng Zhang
Akshay Krishnamurthy
John Langford
Alekh Agarwal

title: Deep batch active learning by diverse, uncertain gradient lower bounds

title: Learning with submodular functions: A convex optimization perspective

venue: arXiv preprint arXiv:1111.6453,

title: Submodular functions: from discrete to continuous domains

venue: Mathematical Programming,

authors:
Christopher Berlind
Ruth Urner

title: Active nearest neighbors in changing environments

venue: In International Conference on Machine Learning,

authors:
Joy Buolamwini
Timnit Gebru

title: Gender shades: Intersectional accuracy disparities in commercial gender classification

venue: In Conference on fairness, accountability and transparency,

authors:
Holger Caesar
Varun Bankiti
Alex H Lang
Sourabh Vora
Venice Erin Liong
Qiang Xu
Anush Krishnan
Yu Pan
Giancarlo Baldan
Oscar Beijbom

title: nuscenes: A multimodal dataset for autonomous driving

venue: In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition,

authors:
Colin Campbell
Nello Cristianini
Alex Smola

title: Query learning with large margin classifiers

venue: In ICML,

authors:
Ciprian Chelba
Tomas Mikolov
Mike Schuster
Qi Ge
Thorsten Brants
Phillipp Koehn
Tony Robinson

title: One billion word benchmark for measuring progress in statistical language modeling

venue: arXiv preprint arXiv:1312.3005,

authors:
Laming Chen
Guoxin Zhang
Hanning Zhou

title: Fast greedy map inference for determinantal point process to improve recommendation diversity

venue: In Proceedings of the 32nd International Conference on Neural Information Processing Systems,

authors:
Shai Fine
Ran Gilad-Bachrach
Eli Shamir

title: Query by committee, linear separation and random walks

venue: Theoretical Computer Science,

authors:
Yoav Freund
H Sebastian Seung
Eli Shamir
Naftali Tishby

title: Selective sampling using the query by committee algorithm

venue: Machine learning,

title: Submodular functions and optimization

authors:
Denis Gudovskiy
Alec Hodgkinson
Takuya Yamaguchi
Sotaro Tsukizawa

title: Deep active learning for biased datasets via fisher kernel self-supervision

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,

authors:
Anupam Gupta
Roie Levin

title: The online submodular cover problem

venue: In ACM-SIAM Symposium on Discrete Algorithms,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Rishabh Iyer
Jeffrey Bilmes

title: A memoization framework for scaling submodular optimization to large scale problems

venue: In The 22nd International Conference on Artificial Intelligence and Statistics,

authors:
Rishabh Iyer
Ninad Khargoankar
Jeff Bilmes
Himanshu Asanani

title: Submodular combinatorial information measures with applications in machine learning

venue: In Algorithmic Learning Theory,

title: Submodular optimization and machine learning: Theoretical results, unifying and scalable algorithms, and applications

venue: PhD thesis,

authors:
Kimmo Karkkainen
Jungseock Joo

title: Fairface: Face attribute dataset for balanced race, gender, and age for bias measurement and mitigation

venue: In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision,

authors:
Vishal Kaushal
Rishabh Iyer
Suraj Kothawade
Rohan Mahadev
Khoshrav Doctor
Ganesh Ramakrishnan

title: Learning from less data: A unified data subset selection and active learning framework for computer vision

venue: IEEE Winter Conference on Applications of Computer Vision (WACV),

authors:
Vishal Kaushal
Suraj Kothawade
Ganesh Ramakrishnan
Jeff Bilmes
Rishabh Iyer

title: Prism: A unified framework of parameterized submodular information measures for targeted data subset selection and summarization

venue: arXiv preprint arXiv:2103.00128,

authors:
Krishnateja Killamsetty
Durga Sivasubramanian
Ganesh Ramakrishnan
Rishabh Iyer

title: Glister: Generalization based data subset selection for efficient and robust learning

venue: arXiv preprint arXiv:2012.10630,

authors:
Diederik P Kingma
Max Welling

title: Auto-encoding variational bayes

venue: arXiv preprint arXiv:1312.6114,

authors:
Andreas Kirsch
Joost Van Amersfoort
Yarin Gal

title: Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning

authors:
Alex Krizhevsky
Geoffrey Hinton

title: Learning multiple layers of features from tiny images

authors:
Alex Kulesza
Ben Taskar

title: Determinantal point processes for machine learning

venue: arXiv preprint arXiv:1207.6083,

authors:
Yann LeCun
Bernhard Boser
John S Denker
Donnie Henderson
Richard E Howard
Wayne Hubbard
Lawrence D Jackel

title: Backpropagation applied to handwritten zip code recognition

venue: Neural computation,

authors:
Yann LeCun
Corinna Cortes
CJ Burges

title: Mnist handwritten digit database

venue: at&t labs,

authors:
Ilya Loshchilov
Frank Hutter

title: Sgdr: Stochastic gradient descent with warm restarts

venue: arXiv preprint arXiv:1608.03983,

authors:
Baharan Mirzasoleiman
Ashwinkumar Badanidiyuru
Amin Karbasi
Jan Vondrák
Andreas Krause

title: Lazier than lazy greedy

venue: In Proceedings of the AAAI Conference on Artificial Intelligence,

authors:
George L Nemhauser
Laurence A Wolsey
Marshall L Fisher

title: An analysis of approximations for maximizing submodular set functions—i

authors:
Yuval Netzer
Tao Wang
Adam Coates
Alessandro Bissacco
Bo Wu
Andrew Y Ng

title: Reading digits in natural images with unsupervised feature learning

authors:
Adam Paszke
Sam Gross
Francisco Massa
Adam Lerer
James Bradbury
Gregory Chanan
Trevor Killeen
Zeming Lin
Natalia Gimelshein
Luca Antiga
Alban Desmaison
Andreas Kopf
Edward Yang
Zachary DeVito
Martin Raison
Alykhan Tejani
Sasank Chilamkurthy
Benoit Steiner
Lu Fang
Junjie Bai
Soumith Chintala

title: Pytorch: An imperative style, highperformance deep learning library

venue: Advances in Neural Information Processing Systems

authors:
Dan Roth
Kevin Small

title: Margin-based active learning for structured output spaces

venue: In European Conference on Machine Learning,

authors:
Olga Russakovsky
Jia Deng
Hao Su
Jonathan Krause
Sanjeev Satheesh
Sean Ma
Zhiheng Huang
Andrej Karpathy
Aditya Khosla
Michael Bernstein

title: Imagenet large scale visual recognition challenge

venue: International journal of computer vision,

authors:
Greg Schohn
David Cohn

title: Less is more: Active learning with support vector machines

authors:
Ozan Sener
Silvio Savarese

title: Active learning for convolutional neural networks: A core-set approach

venue: arXiv preprint arXiv:1708.00489,

title: Active learning literature survey

authors:
Samarth Sinha
Sayna Ebrahimi
Trevor Darrell

title: Variational adversarial active learning

venue: In Proceedings of the IEEE/CVF International Conference on Computer Vision,

authors:
Ehsan Tohidi
Rouhollah Amiri
Mario Coutino
David Gesbert
Geert Leus
Amin Karbasi

title: Submodularity in action: From machine learning to signal processing applications

venue: IEEE Signal Processing Magazine,

authors:
Dan Wang
Yi Shang

title: A new active labeling method for deep learning

venue: In 2014 International joint conference on neural networks (IJCNN),

authors:
Kai Wei
Rishabh Iyer
Jeff Bilmes

title: Submodularity in data subset selection and active learning

authors:
Xiang Zhang
Junbo Zhao
Yann LeCun

title: Character-level convolutional networks for text classification

venue: arXiv preprint arXiv:1509.01626,

authors:
Yukun Zhu
Ryan Kiros
Rich Zemel
Ruslan Salakhutdinov
Raquel Urtasun
Antonio Torralba
Sanja Fidler

title: Aligning books and movies: Towards story-like visual explanations by watching movies and reading books

venue: In Proceedings of the IEEE international conference on computer vision,

text:
1 Introduction
Deep neural networks (DNNs) have had a lot of success in a wide variety of domains. However, they require large labeled datasets which are often taxing, time-consuming, and expensive to obtain. Active learning (AL) [12, 13, 39, 3, 9] is a promising approach to solve this problem. It aims to select the most informative data points from an unlabeled dataset to be labeled in an adaptive manner with a human in the loop. The goal of AL is to achieve maximum accuracy of the model while minimizing the number of data points required to be labeled.
Current AL methods have been tested in relatively simple, clean, and balanced datasets. However, real-world datasets are not clean and have a number of characteristics that makes learning from them challenging [10, 46, 47, 38, 1, 8]. Firstly, these real-world datasets are im-
balanced, and some classes are very rare (e.g., Fig 1(a)). Examples of this imbalance are medical
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
imaging domains where the cancerous images are rare. Secondly, real-world data has a lot of redundancy (e.g., Fig 1(b)). This redundancy is more prominent in datasets that are created by sampling frames from videos (e.g., footage from a car driving on a freeway or surveillance camera footage). Thirdly, it is common to have out-of-distribution (OOD) (e.g., Fig 1(c)) data, where some part of the unlabeled data is not of concern to the task at hand. Given the amount of unlabeled data, it is not realistic to assume that these datasets can be cleaned manually; hence, it is the need of the hour to have active learning methods that are robust to such scenarios. We show that current AL approaches (including the state-of-the-art approach BADGE [3]) do not work well in the presence of the dataset biases described above. In this work, we address the following question: Can a machine learning model be trained using a single unified active learning framework that works for a broad spectrum of realistic scenarios? As a solution, we propose SIMILAR1, a unified active learning framework which enables active learning for many realistic scenarios like rare classes, out-of-distribution (OOD) data, and redundancy.

heading: 1.1 Related Work

text:
Active learning has enabled efficient training of complex deep neural networks by decreasing labeling costs. The most commonly used approach is to select the most uncertain items. Examples of uncertainty strategies include ENTROPY [41], LEAST CONFIDENCE [44], and MARGIN [37]. One challenge of this approach is that all the samples within a batch can be potentially similar even though they are uncertain. To overcome this problem in batch active learning, many recent works have attempted to select diverse yet informative data points. [45, 22] propose a simple approach: Filter a set of points using uncertainty sampling and then select a diverse subset from the filtered set. [40] propose CORESET, which forms core-sets using greedy k-center clustering while maintaining the geometric arrangement. BADGE [3], another recent approach, proposes to select data points corresponding to high-magnitude, diverse hypothesized gradients by using K-MEANS++ [2] initialization to distance from previously selected data points in the batch. Most existing AL approaches fail to ensure diversity across AL selection rounds and do not perform as well when there is a lot of redundancy. Sinha et al. [42] used a variational autoencoder (VAE) [25] to learn a feature space and an adversarial network [32] to distinguish between labeled and unlabeled data points. However, their approach is computationally expensive and requires extensive hyperparameter tuning. Similarly, BATCHBALD [26] does not scale to larger batch sizes since their method would need a large number of Monte Carlo dropout samples to obtain a significant mutual information. Such limitations reduce the scope of applying these methods to realistic settings.
Closely related to our work are two recently proposed works. The first is GLISTER-ACTIVE [24], which formulates the AL acquisition function by maximizing the log-likelihood on a held-out validation set. This validation set could consist of examples from the rare classes or in-distribution examples. The second approach is the work of Gudovskiy et al. [15], who study AL for biased datasets using a self-supervised FISHER kernel and pseudo-label estimators. They address this problem by explicitly minimizing the KL divergence between training and validation sets via maximizing the FISHER kernel. Although their method shows promising results, they make multiple unrealistic assumptions: a) They use a large labeled validation set, and b) they use feature representations from a model pretrained using unsupervised learning on a balanced unlabeled dataset. In this work, we compare against both GLISTER-ACTIVE [24] and FISHER [15] approaches in the more realistic setting of a small held-out validation set (smaller than the seed labeled set) and an imbalanced unlabeled set. Another work proposed a discrete optimization method for k-NN-type algorithms in the domain shift setting [6]. However, their approach is limited to k-NNs.
This work utilizes submodular information measures (SIM) by [19] and their extensions by [23]. SIMs encompass submodular conditional mutual information (SCMI), which can then be used to derive submodular mutual information (SMI); submodular conditional gain (SCG); and submodular functions (SF). We discuss these functions in detail in Sec. 2. [23] also studies these functions on the closely related problem of targeted data selection.

heading: 1.2 Our Contributions

text:
The following are our main contributions: 1) Given the limitations of existing approaches in handling active learning in the real world, we propose SIMILAR (Sec. 3), a unified active learning framework that can serve as a comprehensive solution to multiple realistic scenarios. 2) We treat SIM as a
1Submodular Information Measures based actIve LeARning
common umbrella for realistic active learning and study the effect of different function instantiations offered under SIM for various realistic scenarios. 3) SIMILAR not only handles standard active learning but also extends to a wide range of settings which appear in the real world such as rare classes, out-of-distribution (OOD) data, and datasets with a lot of redundancy. Finally, 4) we empirically demonstrate the effectiveness of SMI-based measures for image classification (Sec. 4) in a number of realistic data settings including imbalanced, out-of-distribution, and redundant data. Specifically, in the case of imbalanced and OOD data, we show that SIMILAR achieves improvements of more than 5 to 10% on several image classification datasets.

heading: 2 Background

text:
In this section, we enumerate the different submodular functions that are covered under SIM and the relationships between them.
Submodular Functions. We let U denote the unlabeled set of n data points U = {1, 2, 3, ..., n} and a set function f : 2U −→ R. Formally, a function f is submodular [14] if for x ∈ U , f(A∪x)−f(A) ≥ f(B ∪ x)− f(B), ∀A ⊆ B ⊆ U and x /∈ B. For a set A ⊆ U , f(A) provides a real-valued score for A. In the context of batch active learning, this is the score of an acquisition function f on batch A. Submodularity is particularly appealing because it naturally occurs in real world applications [43, 4, 5, 20] and also admits a constant factor 1− 1e [34] for cardinality constraint maximization. Additionally, variants of the greedy algorithm maximize a submodular function in near-linear time [33].
Submodular Mutual Information (SMI). Given sets A,Q ⊆ U , the SMI [16, 19] is defined as If (A;Q) = f(A) + f(Q) − f(A ∪ Q). Intuitively, SMI models the similarity between Q and A, and maximizing SMI will select points similar to Q while being diverse. Q here is the query set. Submodular Conditional Gain (SCG). Given sets A,P ⊆ U , the SCG f(A|P) is the gain in function value by adding A to P . Thus, f(A|P) = f(A∪ P)− f(P) [19]. Intuitively, SCG models how different A is from P , and maximizing SCG functions will select data points not similar to the points in P while being diverse. We refer to P as the conditioning set. Submodular Conditional Mutual Information (SCMI). Given sets A,Q,P ⊆ U , the SCMI is defined as If (A;Q|P) = f(A∪P)+ f(Q∪P)− f(A∪Q∪P)− f(P). Intuitively, SCMI jointly models the similarity between A and Q and their dissimilarity with P .
Relationship between SIM The relationship between the above measures is the key component that unifies our AL framework [19, 23]. The unification comes from the rich modeling capacity of SCMI: If (A;Q|P) where Q,P ⊆ U . This facilitates a single acquisition function that can be applied to multiple scenarios. Concretely, the submodular function f can be obtained
by setting Q ← U and P ← ∅. Next, the SMI can be obtained by setting Q ← Q and P ← ∅, while we obtain SCG by setting Q ← ∅, P ← P . We summarize the relationships between SIM in Tab. 1. Instantiations of SIM. The formulations for Facility Location (FL), Graph Cut (GC) and Log Determinant (LOGDET) are as in [19, 23] and we adapt them as acquisition functions for batch active learning. We use two variants for FL: FLQMI, which models pairwise similarities of only the query set Q to the unlabeled dataset, and FLVMI, which additionally considers the pairwise similarities within the unlabeled dataset U . The SCG and SCMI expressions corresponding to FL are referred as FLCG and FLCMI, respectively (see row 1 in Tab. 2a and 2b). For LOGDET, we refer to the SMI, SCG and SCMI expressions as LOGDETMI, LOGDETCG and LOGDETCMI, respectively (see row 5 in Tab. 2a and row 2 in Tab. 2b). Similarly, the SMI and SCG expressions are respectively referred to as GCMI and GCCG for GC (see row 3 in Tab. 2a and 2b). For notation in Tab. 2, the pairwise similarity matrix S between items in sets A and B is denoted as SA,B. Also, we denote Sij as the (i, j) entry of S.

heading: 3 SIMILAR: Our Unified Active Learning Framework

text:
In this section, we propose a unified active learning framework SIMILAR, which uses SIMs to address the limitations of the current work (see Sec. 1.1). We show that SIMILAR can be effectively applied to a broad range of realistic scenarios and thus acts as one-stop solution for AL.
The basic idea behind our framework is to exploit the relationship between the SIMs (Tab. 1) such that it can be applied to any real-world dataset. Particularly, we use the formulation of SCMI and appropriately choose a query set Q and/or a conditioning set P depending on the scenario at hand. Towards this end, we use the inspiration from [3] where they select data points based on diverse gradients. The SIM functions (see Tab. 2) are instantiated using similarity kernels computed using pairwise similarities Sij between the gradients of the current model. Specifically, we define Sij = 〈∇θHi(θ),∇θHj(θ)〉, where Hi(θ) = H(xi, yi, θ) is the loss on the ith data point. Similar to [45, 3], we use hypothesized labels for computing the gradients, and the corresponding similarity kernels. The hypothesized label for each data point is assigned as the class with the maximum probability. We then optimize a SCMI function:
max A⊆U,|A|≤B
If (A;Q|P) (1)
with appropriate choices of query setQ and conditioning set P . In the context of batch active learning, A is the batch and B is the budget (batch size in AL). We present our unified AL framework in Algorithm 1 and illustrate the choices of query and conditioning set for realistic scenarios in Fig. 2.
Algorithm 1 SIMILAR: Unified AL Framework Require: Initial Labeled set of data points: L, large unlabeled dataset: U , Loss function H for
learning modelM, batch size: B, number of selection rounds: N 1: for selection round i = 1 : N do 2: Train modelM with lossH on the current labeled set L and obtain parameters θ 3: Using model parameters θi, compute gradients using hypothesized labels {∇θH(xj , ŷj , θ),∀j ∈ U} and obtain a similarity matrix X . 4: Instantiate a submodular function f based on X . 5: Ai ← argmaxA⊆U,|A|≤BIf (A;Q|P) (Optimize SCMI with an appropriate choice of Q and P , see Tab. 1) 6: Get labels L(Ai) for batch Ai and L ← L ∪ L(Ai), U ← U −Ai 7: end for 8: Return trained modelM and parameters θ.
In the scenarios below, we will discuss how this paradigm can provide a unified view of active learning, handle aspects like standard active learning (Sec. 3.1), rare classes and imbalance (Sec. 3.2), redundancy (Sec. 3.3) and, OOD/outliers in the unlabeled data (Sec. 3.4).

heading: 3.1 Standard Active Learning

text:
We refer to standard active learning for ideal scenarios when there is no imbalance, redundancy or OOD data in the unlabeled dataset. In such cases, there is no requirement for having a query set and conditioning set. Hence, given a SCMI function If (A;Q|P), we get If (A;Q|P) = f(A) by setting Q ← U (the unlabeled dataset) and P ← ∅. In a nutshell, the standard diversified active learning setting can be seen as a special case of our proposed unified AL framework (Equ. (1)) by choosingQ,P as above. Note that this approach is very similar and closely related to BADGE [3], where the authors
also choose points based on diverse gradients. Furthermore, the authors discuss the use of Determinantal Point Processes (DPP) [28] for sampling, and this is very similar to maximizing log-determinants. In the supplementary paper, we compare the choice of different submodular functions for AL.

heading: 3.2 Rare Classes

text:
A very common and naturally occurring scenario is that of imbalanced data. This imbalance is because some classes or attributes are naturally more frequently occurring than others in the realworld. For example, in a self-driving car application, there may be very few images of pedestrians at night on highways, or cyclists at night. Another example is medical imaging, where there are many rare yet important diseases (e.g., various forms of cancers), and it is often the case that non-cancerous images are much more than compared to the cancerous ones. While such classes are rare, it is also critical to be able to perform well in these classes. The problem with running standard active learning algorithms in such a case is that they may not sample too many data points from these rare classes, and as a result, the model continues to perform poorly on these classes. In such cases, we can create a (small) held-out setR which contains data points from these rare classes, and try to encourage the AL by sampling more of these rare classes by maximizing the SMI function If (A;R):
max A⊆U,|A|≤B
If (A;R) (2)
This setting is shown in Fig. 2(a). R contains a small number of held-out examples of classes 5, 8 which are rare, and the AL acquisition function is Equ. (2). Note that this is exactly equivalent to maximizing the SCMI function withQ ← R and P ← ∅ (i.e. Equ. (1) in Line 5 of Algorithm 1). Furthermore, since the SMI functions naturally model query relevance and diversity, they will also try to pick a diverse set of data points which are relevant toR. Finally, we also point out that this setting was considered in [15] where they use a FISHER kernel based approach to sample data points. Note that for this setting to be realistic, it is critical that the size of this validation set is very small – [15] uses a much larger validation set which is not very realistic (e.g., 200× our set, see Appendix B for more details).
3.3 Redundancy in Unlabeled Data
Another commonplace scenario is where we are dealing with a lot of redundancy – e.g., frames sampled from a video, where subsequent frames are visually similar. In such cases, existing AL algorithms tend to pick data points that are semantically similar to the ones selected in some earlier batch. This is true even for the state-ofthe-art AL algorithm BADGE [3] that attempts to enforce diversity, but only in the current batch of data points and not the already selected labeled set. To illustrate this, consider the scenario in Fig. 2(b). The digits 0, 1 are redundant in the unlabeled set, and they are already present in the labeled set L. Algorithms which just focus on diversity in the current batch could fail at ensuring diversity across batches. To mitigate inter-batch redundancy, we use SCG acquisition function and condition upon the already labeled set L:
max A⊆U,|A|≤B
f(A|L) (3)
Notice that this is a special case of our proposed unified AL framework (Equ. (1)) since the SCG function f(A|L) is basically a SCMI function with Q ← ∅ and P ← L.

heading: 3.4 Out of Distribution Data

text:
In real world scenarios, we often have out-ofdistribution (OOD) data or irrelevant classes in the unlabeled set. Such OOD data is not useful for
the given classification task at hand. Using an acquisition function that selects a lot of OOD data points will lead to a waste of labeling effort and time. This is because annotators have to spend time in filtering out OOD data points and discard them from the training dataset. To account for OOD data, we add an additional class called "OOD" in our model. Since the goal is to improve on in-distribution classes , we ignore the prediction for the OOD class at test time. For our AL acquisition function, we use the currently labeled OOD points O as the conditioning set P , and the currently labeled in-distribution (ID) points I as the query setQ. In other words, our acquisition function is to optimize:
max A⊆U,|A|≤B
If (A; I|O) (4)
This is illustrated in Fig. 2(c), where the labeled set consists of six examples, four of them being ID data points (set I) and two being OOD data points (set O). In Fig. 2(c), the ID data are digits (digit classification) and the OOD examples are alphabets. This SCMI based approach will naturally pick points "close" to the ID data while avoiding the OOD points.
Another approach for designing the acquisition function is to not explicitly condition on the OOD data points. In other words, we can just optimize the SMI function:
max A⊆U,|A|≤B
If (A; I) (5)
We contrast the choices of SCMI (Equ. (4)) and SMI (Equ. (5)) functions in our experiments.

heading: 3.5 Multiple Co-occurring Realistic Scenarios

text:
We can also apply SIMILAR to datasets where more than one realistic scenarios are co-occurring. As illustrated in Tab. 3, we can use the formulation of SCMI and make appropriate choices of Q and P to tackle multiple realistic scenarios.
Rare classes and OOD: We set Q ← R and P ← O and maximize If (A;R|O). Intuitively, this function would pick points close toR while avoiding the OOD points. In this scenario, we can also optimize an SMI function If (A;R) if the data points belonging to the rare classes are not similar to the OOD data points, meaning that only searching for rare classes may suffice. Regardless, the SCMI approach above will further reinforce the avoidance of the OOD points.
Rare classes and Redundancy: We set Q ← R and P ← L − R̃. Here, R̃ is the subset of data points from the labeled set L that belong to the rare classes. Intuitively, this function would pick points close to R while avoiding points already in L − R̃, thereby avoiding redundant data. Just focusing on R by optimizing If (A;R) is also a feasible option because rare classes are generally not redundant. As before, the SCMI approach will only reinforce the avoidance of redundant samples in any non-rare class instances selected.
Redundancy and OOD: This is a more challenging scenario than the ones above. We start with using the SCMI formulation for the OOD scenario, i.e., If (A; I|O), where I is the set of ID samples and O is the set of OOD samples. Optimizing this function will pick diverse in-distribution samples within a batch. For selecting diverse samples across different batches, we can tackle this by using an appropriate kernel for the conditioning set. For instance, consider the FLCMI function in Tab. 2(b). On setting P ← O ∪ I, we can rewrite the FLCMI function by splitting the penalty term as follows:∑ i∈U max(min(max j∈A Sij ,max j∈I Sij)−max(max j∈O Sij ,max j∈I S′ij), 0). While S is computed using cosine similarity, we can compute S′ using an exponential kernel to magnify the value of S′ij using the exponent when i and j are very similar. This exponent is a hyperparameter which can be tuned to penalize selecting redundant samples from I (denoted as I ′ ) in Tab. 3.

heading: 3.6 Realizing Realistic Scenarios in Applications

text:
In this section, we discuss a few insights on how these realistic scenarios can be realized. To begin with, the initial labeled set used in AL usually follows the distribution of the unlabeled set. The
statistics of this set can be used to identify rare classes. If the initial seed set is small, the rare classes/OOD data points can be realized after a few rounds of standard AL. Until such scenarios are discovered, standard AL can be done using a diversity-based acquisition function like the log determinant (LOGDET). For production-level models, they go through a test deployment phase. During this phase, systematically recurring errors are often found. An example is of undetected bicycles at night in an object detector (false negatives). Such recurring failure cases can be due to rare classes in the labeled set. Moreover, we as users often know whether there are rare classes or if there is redundancy from domain knowledge. For instance, in the biomedical domain, images of cancer cells are typically rarer than ones of non-cancer cells because cancer inherently is a rare disease.

heading: 3.7 Scalability and Computational Aspects of SIMILAR

text:
Computational Complexity: The computational complexity of the different SMI functions are determined by (1) the kernel computation time, and (2) the time complexity of the greedy algorithm. All functions considered here are graph based functions and require computing a kernel matrix. The LOGDET functions (LOGDET, LOGDETMI, LOGDETCG, LOGDETCMI), some FL functions (FL, FLVMI, FLCMI), and GC, GCMI all require the n×n similarity matrix (n = |U| is the number of unlabeled points) which entails a complexity ofO(n2) to construct the similarity kernel. Once constructed, the complexity of the greedy algorithm for LOGDET class of functions is roughly O(B3n) [11], while the complexity of the greedy algorithm with FL, FLVMI, and FLCMI is O(Bn2) [18, 20](B is the batch size). Different from others, FLQMI does not require computing a n× n kernel, but only a n× q kernel (where q = |Q| is the number of query points). Correspondingly, the complexity of the greedy algorithm with FLQMI is O(nqB), and is linear in n. In Appendix. A, we provide a detailed summary of the complexity of different SF, SMI, SCG, and SCMI functions.
Partition Trick: The deal with the high O(n2) of the LOGDET, GC, and some of the FL variants (except FLQMI), we also propose the following partitioning algorithm: We randomly split the unlabeled set U into p partitions U1, · · · ,Up, and we then define the corresponding function (SF, SMI, SCMI, SCG) on each of the partitions and independently optimize them. In each partition, we select B/p points. The complexity of this reduces from O(n2) to O(n2/p) and with an appropriate choice of p, we can significantly reduce the computational complexity. We use this in our ImageNet experiments (see Sec. 4.1), and observe that our approaches continue performing well while being more scalable. We provide more details on partitioning in Appendix. A.
Last Layer Gradients: Deep models have numerous parameters leading to very high dimensional gradients. Since our kernel matrix is computed using the cosine similarity of gradients, this becomes intractable for most models. To solve this problem, we use last-layer gradient approximation by representing data points using last layer gradients. BADGE [3], CORESET [40] and GLISTER [24] are other baselines that also use this approximation. Using this representation, we compute a pairwise cosine similarity matrix to instantiate acquisition functions in SIMILAR (see lines 3,4 in Algorithm 1).

heading: 4 Experimental Results

text:
In this section, we empirically evaluate the effectiveness of SIMILAR on a wide range of scenarios like rare classes (Sec. 4.1), redundancy (Sec. 4.2) and out-of-distribution (Sec. 4.3). We do so by comparing the accuracy and selections of various SCMI based acquisition functions with existing AL approaches. Using these experiments, we cover the issues with the current AL methods and show that these issues can be mitigated by using a unified implementation using SCMI with appropriate choices of query and/or conditioning sets. Although this section focuses on realistic scenarios, we also study SIMILAR in a standard active learning setting and show that it performs at par with current AL methods (see Appendix. C). Furthermore, we present some experiments on a real-world medical dataset in Appendix. H and some experiments on multiple co-occurring realistic scenarios (Sec. 3.5) in Appendix. I.
Baselines in all scenarios: We compare SCMI based functions against several methods. Particularly, we compare against: (1) three uncertainty based AL algorithms: i)ENTROPY: Selects the top B data points with the highest entropy [41], ii) MARGIN: Select the bottom B data points that have the least difference in the confidence of first and the second most probable labels [37], iii)LEAST-CONF: SelectB samples with the smallest predicted class probability [44], (2) state-of-the-art diversity based algorithms: iv) BADGE [3] v) GLISTER [24] vi) CORESET [40] which are all discussed in section Sec. 1.1, and, 3) RANDOM: Select B samples randomly. Additionally, in the rare classes scenario, we compare against FISHER [15] which is also discussed in Sec. 1.1.
LOGDETMI
FLVMI
DIV-GCMI
FISHER-LV
BADGE
ENTROPY
MARGIN

heading: 125 250 375 500 625 750 875 1000 1125 1250

text: Datasets, model architecture and experimental setup: We apply our framework to CIFAR-10 [27] and MNIST [30] classification tasks. Additionally, we also evaluate our method on down sampled 32× 32 ImageNet-2012 [38] for the rare classes setting (Sec. 4.1). Due to the lack of test split on ImageNet, we used the validation split for evaluation. In the sections below, we discuss the individual splits for L, U ,R, I, and O in each realistic scenario. To ensure that all the selection algorithms that we are studying are given fair and equal treatment across all realistic scenarios, we use a common training procedure and hyperparameters. We use standard augmentation techniques like random crop, horizontal flip followed by data normalization except for MNIST which does not use horizontal flip to preserve labels. For training, we use an SGD optimizer with an initial learning rate of 0.01, the momentum of 0.9, and a weight decay of 5e-4. We decay the learning rate using cosine annealing [31] for each epoch. On all datasets except MNIST, we train a ResNet18 [17] model, while on MNIST we train a LeNet [29] model. For all the experiments in a particular scenario (rare classes, redundancy and OOD), we start with an identical initial modelM and initial labeled set D. We reinitialize the model parameters at the beginning of every selection round using Xavier initialization and train the model until either the training accuracy reaches 99% or the epoch count reaches 150. We run each experiment 3× on CIFAR10 and MNIST and 1× on ImageNet and provide error bars (std deviation). All experiments were run on a V100 GPU. For more details on the experimental setup, baselines, and datasets see Appendix. B.

heading: 4.1 Rare Classes

text:
Custom dataset: Following [15, 24], we simulate these rare classes by creating a class imbalance. We initialize the batch active learning experiments by creating a custom dataset which is a subset of the full dataset with the same marginal distribution. Given that C consists of data points from the imbalanced classes and D consists of data points from the balanced classes, we create an initial labeled set L such that |DL| = ρ|CL| and an unlabeled set |DU | = ρ|CU |, where ρ is the imbalance factor. We use a small and clean validation/query setR containing data points from the imbalanced classes (≈ 3 data points per imbalanced class). We create an imbalance in CIFAR-10 using 5 random classes, ρ = 10 and for MNIST we create an imbalance using the same classes as in [15] (5 · · · 9) and use ρ = 20. For both datasets: |CL|+ |DL| = 125, |CU |+ |DU | = 16.5K, B = 125 (AL batch size) and, |R| = 25 (size of the held out rare instances). For MNIST, we also present the results for B = 25 and ρ = 100 in the supplementary. On ImageNet, we randomly select 500 classes out
LOGDETCG FLCG GLISTER BADGE CORESET ENTROPY MARGIN RANDOM
of 1000 classes for imbalance and ρ = 5 such that |CL| + |DL| = 102K, |CU | + |DU | = 664K, B = 25K and, |R| = 2.5K. These data splits are chosen to simulate a low initial accuracy on the rare classes and at the same time maintain the imbalance factor in the labeled and unlabeled datasets.
Results: The results are shown in Fig. 3. We observe that SMI based functions not only consistently outperform uncertainty based methods (ENTROPY, LEAST-CONF and MARGIN) but also all the state-of-the-art diversity based methods (BADGE, GLISTER, CORESET) by ≈ 5 − 10% in terms of overall accuracy and ≈ 10− 18% in terms of average accuracy on rare classes (see Fig. 3a, 3d, 3g). The reason for the same can be seen in Fig. 3c, 3f, 3i which illustrates that they fail to pick an adequate number of examples from the rare classes. Evidently, FLQMI and LOGDETMI which balance between diversity and relevance perform better than GCMI which only models relevance. Furthermore, DIV-GCMI which is a linear combination of GCMI and a diversity term performs consistently worse, which suggest that a naive combination of the two may not be as effective. This suggests the need of SMI based acquisitions functions (Equ. (2)) with richer modeling capabilities like FLQMI and LOGDETMI within SIMILAR. Furthermore, all SMI based functions also outperform the FISHER kernel based method when the validation set is small and realistic, i.e., |R| = 25. Since, [15] use a very large validation set in their experiments, we try their method FISHER-LV with a 40× larger validation set of size 1000 (which is not practical) and observe a comparable performance with the SMI functions which use a small validation set. Furthermore, we see that FISHER-LV actually picks significantly larger number of rare class instances in MNIST, but yet is comparable in performance of FLQMI and LOGDETMI. This suggests that both these methods select higher quality and diverse rare class instances. We observe that the GC SMI variants( GCMI and DIV-GCMI) do not perform well on MNIST classification. Finally, we point out in the case of ImageNet, FLQMI performs the best and outperforms FLVMI and LOGDETMI – this is because we do not need to do the partition trick for FLQMI since it is already linear in time complexity. For FLVMI and LOGDETMI, we set the number of partitions p = 50 for ImageNet. Finally, we do a pairwise t-test to compare the performance of the algorithms (Appendix. D) and observe that the SMI functions (and particularly FLVMI and LOGDETMI) statistically significantly outperform all AL baselines.

heading: 4.2 Redundancy

text: Custom dataset: To simulate a realistic redundancy scenario we create a custom dataset by duplicating 20% of the unlabeled dataset 10×. For CIFAR-10, the number of unique points in the unlabeled set |U| = 5K, the initial labeled set |L| = 500, B = 500, whereas for MNIST |U| = 500, |L| = 50 and B = 50. For MNIST, we also present the results for 5× and 20× in the Appendix. E. SCG vs Baselines: As expected, the diversity and uncertainty based methods outperform random. Importantly, we observe that the SCG functions (FLCG and LOGDETCG) significantly outperform all baselines by ≈ 3− 5% towards the end as the conditioning gets stronger with increase in L (see Fig. 4a, 4b). This implies that simply relying on model parameters for diversity and/or uncertainty is not sufficient and that conditioning on the updated labeled set L (Equ. (3)) is required in batch active learning. In Fig. 4c we show that SCG based acquisition functions select significantly more unique data points than other baselines. We also perform a pairwise t-test (Appendix. E), to prove that the SCG functions consistently and statistically significantly outperform BADGE and other baselines.

heading: 4.3 Out-Of-Distribution

text:
Custom dataset: We simulated a scenario where we convert the classification problem in CIFAR-10 and MNIST to a 8-class classification, where the first 8 classes represent the set IF of in-distribution
LOGDETCMI
FLCMI
LOGDETMI
FLQMI
FLVMI
GCMI
DIV-GCMI
GLISTER
BADGE
CORESET
ENTROPY
MARGIN
RANDOM
1600 1850 2100 2350 2600 2850 3100 3350 3600 3850 Labeled Set Size
60
65
70
75
A cc
u ra
cy (a)CIFAR-10: SCMI vs Baselines

heading: 1600 1850 2100 2350 2600 2850 3100 3350 3600 3850

text:
Labeled Set Size
60
65
70
75
A cc
u ra
cy
(b)CIFAR-10: SCMI vs SMI
3600 3850
72.17
74.83
0.0
0.5
1.0
1.5
2.0
2.5
A v e ra
g e
V a ri
a n
ce
0.73
1.09
1.42 1.7 1.41
1.05 0.9
1.74
2.69
1.41
1.9
2.28 2.05
(c)OOD: Variance Comparison
(ID) data points and the last 2 represent the set OF of out-of-distribution(OOD) data points. The initial labeled set L consists only of ID points, i.e. OF ∩ L = ∅. The unlabeled set is simulated to reflect a realistic and somewhat extreme setting where the unlabeled ID data points |IF | is much smaller than the unlabeled OOD data points |OF |. Additionally, we also assume we have a very small validation set of ID points IV . For CIFAR-10: |L| = 1.6K, |IF | = 4K, |OF | = 10K, |IV | = 40, B = 250 whereas for MNIST which is a relatively simpler task, we use a smaller initial labeled sets and keep the unlabeled sets of the same size: |L| = 40, |IF | = 400, |OF | = 10K, |IV | = 16, B = 20. Recall that our algorithm uses ID set I (initialized to IV ) and OOD set O which we build as follows. Every time our selection approach selects a set A, we update I = I ∪ (A ∩ IF ) and O = O ∪ (A ∩OF ), i.e. we augment the ID and OOD points in A to the sets I and O respectively. SCMI vs Baselines: Since we care about the predictive performance of the ID classes, we report the ID classes accuracy. We see that SCMI based acquisition functions significantly outperform existing AL approaches by ≈ 5− 10% (see Fig. 5a, 5d). We also observe that existing acquisition functions have a high variance, which is undesirable in real-world deployment scenarios where deep models are being continuously developed. Our SCMI based acquisition functions (LOGDETCMI and FLCMI) show the lowest variance in training (see Fig. 5c). This reinforces the need of having a framework like SIMILAR that facilitates query and conditioning sets.
SCMI vs SMI: We compare SCMI functions against SMI functions to study the effect of conditioning and observe that the SCMI functions are comparable to the SMI functions initially but in the later selection rounds of active learning, the SCMI functions consistently outperform SMI functions. In particular, we see an improvement of 2− 3% as the conditioning becomes stronger (see Fig. 5b, 5e). We also observe the SCMI tends to select more ID points than SMI and other baselines (see Fig. 5f), and SCMI functions have a lower variance overall compared to even the SMI functions (Fig. 5c).

heading: 5 Conclusion

text:
In this paper, we proposed a unified active learning framework SIMILAR using the submodular information functions. We showed the applicability of the framework in three realistic scenarios for active learning, namely rare classes, redundancy, and out of distribution data. In each case, we observed that the functions in SIMILAR significantly outperform existing baselines in each of these tasks. Our real-world experiments on MNIST, CIFAR-10, and ImageNet show that many of the SIM functions (specifically the LOGDET and FL variants) yield ≈ 5% − 18% gain compared to existing baselines, particularly in the rare class scenario and ≈ 5%− 10% OOD scenarios. The main limitations of our work is the dependence on good representations to compute similarity. A potential negative societal impact of this work is the use of SIMILAR to perpetuate certain biases through a malicious use of the query and conditioning set. We discuss this in more detail in Appendix. G.
Acknowledgments and Disclosure of Funding
This work is supported by the National Science Foundation under Grant No. IIS-2106937, a startup grant from UT Dallas, and by a Google and Adobe research award. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation, Google or Adobe.

title: SIMILAR: Submodular Information Measures Based Active Learning In Realistic Scenarios


summaries: The authors propose asymptotic and non-asymptotic test for the hypothesis $\phi = \phi_0$ where $\phi$ is the spread parameter of a Mallows model. To do that, they first prove that we can derive a non-asymptotic test from an asymptotic one (Prop 4.1), then show that an optimal unbiased UMP test can be defined is too computationally costly when the number of items to order ($m$) is large (Theorem 5.1), due to the calculation of the probability in Eq (2).  To alleviate this limitation, they propose to estimate the most likely spread parameter $\hat{\phi}$ which allows them to efficiently approximate the quantity in Eq (2) and control the deviation (Theorem 5.4). Finally, the authors address testing for spread with unknown central ranking, by showing that the average rank aggregation is asymptotically close to the central ranking. Finally, they confirm the efficiency of their method in experiments.

summaries: Paper provided a UMPU test on Mallows model's spread parameter. And based on that paper introduced many variations and discussed their properties. Paper contributes to the testing literature by providing a UMPU test and associated math tools.

summaries: The paper studies the problem of identity testing for the Mallows model, which is a popular parametrized distribution over rankings. It gives identity testers for the non-asymptotic and asymptotic setting which are sample optimal but not necessarily computationally efficient. It also gives a efficient identity tester, with weaker guarantees, and also extends the results to the setting where the central ranking is not unknown.

summaries: This paper is concerned with the hypothesis testing of Mallows ranking models, which is parametrized by a central ranking and a spread parameter. The authors proposed two different methods: one based on the classical Type I error, and the other based on an optimal learning approach. The authors presented a complete theory regarding testing Mallows rankings, and also provided empirical results to corroborate the theory.

abstractText: In this paper, we devise identity tests for ranking data that is generated from Mallows model both in the asymptotic and non-asymptotic settings. First we consider the case when the central ranking is known, and devise two algorithms for testing the spread parameter of the Mallows model. The first one is obtained by constructing a Uniformly Most Powerful Unbiased (UMPU) test in the asymptotic setting and then converting it into a sample-optimal non-asymptotic identity test. The resulting test is, however, impractical even for medium sized data, because it requires computing the distribution of the sufficient statistic. The second nonasymptotic test is derived from an optimal learning algorithm for the Mallows model. This test is both easy to compute and is sample-optimal for a wide range of parameters. Next, we consider testing Mallows models for the unknown central ranking case. This case can be tackled in the asymptotic setting by introducing a bias that exponentially decays with the sample size. We support all our findings with extensive numerical experiments and show that the proposed tests scale gracefully with the number of items to be ranked.

authors:
Nir Ailon
Moses Charikar
Alantha Newman

title: Aggregating inconsistent information: Ranking and clustering

venue: In Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing,

authors:
Mark Braverman
Elchanan Mossel

title: Sorting from noisy information

authors:
Róbert Busa-Fekete
Eyke Hüllermeier
Balázs Szörényi

title: Preference-based rank elicitation using statistical models: The case of Mallows

venue: In ICML,

authors:
Róbert Busa-Fekete
Balázs Szörényi
Dimitris Fotakis
Manolis Zampetakis

title: Optimal learning for mallows block model

venue: In International Conference on Computational Learning Theory (COLT),

title: A Survey on Distribution Testing: Your Data is Big. But is it Blue? Number 9 in Graduate Surveys

venue: Theory of Computing Library,

authors:
Siu-on Chan
Ilias Diakonikolas
Gregory Valiant
Paul Valiant

title: Optimal algorithms for testing closeness of discrete distributions

authors:
Ayala Cohen
C.L. Mallows

title: Assessing goodness of fit of ranking models to data

venue: Journal of the Royal Statistical Society. Series D (The Statistician),

authors:
Noel Cressie
Timothy R.C. Read

title: Multinomial goodness-of-fit tests

venue: Journal of the Royal Statistical Society. Series B (Methodological),

authors:
Constantinos Daskalakis
Ilias Diakonikolas
Rocco A Servedio

title: Learning poisson binomial distributions

authors:
Persi Diaconis
Bernd Sturmfels

title: Algebraic algorithms for sampling from conditional distributions

authors:
Ilias Diakonikolas
Themis Gouleakis
John Peebles
Eric Price

title: Sample-optimal identity testing with high probability

venue: Electron. Colloquium Comput. Complex.,

authors:
Michael A Fligner
Joseph S Verducci

title: Distance based ranking models

title: The minimum description length principle

venue: The MIT Press

title: Theoretical statistics: Topics for a core

authors:
Guy Lebanon
Yi Mao

title: Non-parametric modeling of partially ranked data

venue: In Advances in Neural Information Processing Systems 20, Proceedings of the Twenty-First Annual Conference on Neural Information Processing Systems,

authors:
E.L. Lehmann
J.P. Romano

title: Testing Statistical Hypotheses

venue: Springer

authors:
Bruce G. Lindsay
Marianthi Markatou
Surajit Ray

title: Kernels, degrees of freedom, and power properties of quadratic distance goodness-of-fit tests

venue: Journal of the American Statistical Association,

authors:
Tyler Lu
Craig Boutilier

title: Effective sampling and learning for mallows models with pairwisepreference data

venue: J. Mach. Learn. Res.,

authors:
R. Luce
P. Suppes

title: Handbook of Mathematical Psychology

venue: chapter Preference, Utility and Subjective Probability, pages 249–410. Wiley

title: Non-null ranking models

authors:
Horia Mania
Aaditya Ramdas
Martin J. Wainwright
Michael I. Jordan
Benjamin Recht

title: On kernel methods for covariates that are rankings

venue: Electron. J. Statist.,

title: Analyzing and Modeling Rank Data

authors:
Marina Meila
Le Bao

title: An exponential model for infinite rankings

venue: Journal of Machine Learning Research,

title: Estimation in exponential families on permutations

venue: The Annals of Statistics,

authors:
Frank Nielsen
Vincent Garcia

title: Statistical exponential families: A digest with flash cards

venue: arXiv preprint arXiv:0911.4863,

title: A coincidence-based test for uniformity given very sparsely sampled discrete data

venue: IEEE Trans. Inf. Theory,

title: The analysis of permutations

venue: Applied Statistics, 24:193–202

authors:
Charvi Rastogi
Sivaraman Balakrishnan
Nihar Shah
Aarti Singh

title: Two-sample testing on pairwise comparison data and the role of modeling assumptions

venue: IEEE International Symposium on Information Theory (ISIT),

authors:
Mingxuan Sun
Guy Lebanon
Paul Kidwell

title: Estimating probabilities in recommendation systems

venue: In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics,

title: Mallows ranking models: maximum likelihood estimate and regeneration

venue: Proceedings of the 36th International Conference on Machine Learning,

authors:
Gregory Valiant
Paul Valiant

title: An automatic inequality prover and instance optimal identity testing

venue: SIAM Journal on Computing,

title: Jiaqi Gu

venue: and Hang Xu. Analysis of ranking data. Wiley Interdisciplinary Reviews: Computational Statistics

heading: 1 Introduction

text:
Identity testing of discrete distributions [9, 11] is one of the most fundamental problem which consists of answering a yes-or-no question about the closeness of some explicitly given distribution to an unknown distribution from which random samples are observed. This testing problem have been studied in the classical statistical literature [16], and several tests have been devised in the asymptotic regime which family hypothesis tests are often referred to as goodness-of-fit tests and are routinely used in data analysis [10]. In this work, we extend the identity testing setup to a more general domain that includes rankings over m items which can be viewed as a discrete distribution testing problem over a domain with size m!. As a consequence, identity testing of ranking data without any assumption is not feasible, since lower bound is known for identity testing for discrete distribution [26, 11] that is ⌦( p n) where n is the domain size. Therefore we study an important subclass of ranking distributions, which is introduced by [20] and also known as the exponential family on rankings. The model has two parameters, the central ranking ⇡0 2 Sm and the spread parameter 2 [0, 1]. Based on these, the probability of observing a ranking ⇡ 2 Sm is proportional to d(⇡,⇡0), where d is a ranking distance, such as the number of discordant pairs, a.k.a Kendall’s tau distance. There are many applications of the Mallows model in Machine Learning, to name a few, label ranking [18], online learning [3], recommendation systems [29, 15], clustering [23]. The focus of this study is to devise identity tests for Mallows model that are scalable with the number of items m. Identity testing is a central problem in analysing output of ranking systems where the goal is to
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
decide whether the output ranking data deviates from some expected behaviour, or is biased towards some group of object to be ranked or it is indeed fair ([24, 20, 32] and see Chapter 3-4 of [22]).
The hypothesis testing literature that is related to Mallows model, and more generally to ranking distributions, such as Plackett-Luce [27, 19] or Babington-Smith [22], is not extensive. In our work, we partially fill this gap by devising hypothesis tests for the Mallows model. We focus on identity testing problem, where we assume that the ground truth parameters of a Mallows model are given; this corresponds to the null hypothesis. Our goal is to decide whether the data we observe is generated by the null model or by an alternative one. We show that this kind of goodness-of-fit testing task can be tackled in the traditional asymptotic setting as well as in non-asymptotic scenario in an efficient way regardless whether the central ranking is known. We can summarize our main results as follows:
• We devise a Uniformly Most Powerful Unbiased (UMPU) test for asymptotic case to test spread parameter with known central ranking ⇡0. • We show that, in general, the UMPU test can be converted into a sample-optimal non-asymptotic test which result may be of independent interest. Based on this result, we come up with an optimal non-asymptotic test, however it is hard to apply even for medium sized data. • Next, we propose a non-asymptotic test that is optimal for small and easy to compute. • We also consider the case when the central ranking ⇡0 is not given, but needs to be estimated, and
devise tests for both testing setups. • We demonstrate the versatility of our algorithm running with large m on synthetic data, and we
show that for large m > 70 to test the spread parameter, only one single sample is enough.
The paper is organized as follows. Related work is presented in Section 2. Then, we recall the Mallows model and introduce notations. In Section 4, we describe the asymptotic and non-asymptotic testing setups and present our result on the relation of these two settings. In Section 5, we present our algorithms for testing the spread parameter . In Section 6, we present tests where both parameter of Mallows model are tested. Experiments are in Section 7 and finally conclude the paper in Section 8.

heading: 2 Related work

text:
The asymptotic testing has a long history [16] dating back to Pearson’s fundamental work. To come up with a asymptotic test for Mallows model is more challenging from a computational point of view than methodological point of view. Testing ranking distribution can be viewed as multinomial testing problem and thus applied, for example, [8], however the domain size is m!, so this approach becomes hard to apply even for small m.
The non-asymptotic testing has also long history [9, 6, 5] and references therein, including testing for discrete data. Nevertheless, sample optimal tests for wide range of parameter had been only devised recently [11] which was further strengthened in [31] by showing that this lower bound is instance optimal. Those results imply a sample complexity of order ⇥( p m!/"2) in our ranking setting if we do not exploit the structure induced by Mallows model. In the non-asymptotic setting, testing and learning are related problems. There are several so-called “testing by learning” algorithm which first learns a model, and then decides whether the learnt model is close to the null model or far enough from it which requires a tight lower bound on the total variation distance. Optimal learning, however, does not necessarily imply optimal testing in general, as it is the case for identity testing of discrete distributions (see Subsection 6.6 of [5] for further discussion). Nevertheless, it turned out that for identity testing of Mallows model this is indeed to be the case for a wide range of parameters, since interestingly, upper bound for sample complexity of optimal parameter learning of Mallows model requires asymptotically as many samples as it is needed to show that two models are far from each other in terms of total variation distance in a certain parameter regime. Optimal learning is recently devised for Mallows model by [4] which result we rely on.
The testing literature is very limited for ranking distribution in general. Mallows came up with an approximate solution, in [20, Section 11], to test uniformity against a single parameter Mallows model in the non-asymptotic setting. His approach relies on a normal approximation of the sufficient statistic. Cohen and Mallows [7] presents a goodness of fit test for ranking data in a way the ranking data is handled as a sample from a discrete distribution with m! parameters. That is why their analysis is restricted to m = 3 and m = 4. In addition to this, the authors presented a goodness of fit test for pairwise marginals of various ranking models for larger m including Mallows model, Placket-Luce
and the Thurstonian model, but their focus was to decide which model fits better to the data in terms of pairwise marginals. Whereas we were interested in testing the parameters of Mallows model with large m values. There are some recent paper for testing ranking data, but these works are not related to parametric ranking models. For example, [21, 17] uses statistics based on permutation kernel functions for testing the equality of two ranking distributions in the asymptotic setting. Finally, there is a very recent paper which testing identity of preference matrices which are marginals of ranking distributions [28].

heading: 3 Preliminaries and Notation

text:
Single Parameter Mallows Model. The Mallows model or, more specifically, Mallows - distribution is a parametrized, distance-based probability distribution that belongs to the family of exponential distributions R = {M ,⇡ | 2 [0, 1],⇡ 2 Sm} with probability mass function p ,⇡0(⇡) =
d(⇡,⇡0)/Z( ,⇡0) where and ⇡0 are the parameters of the model: ⇡0 2 Sm is the location parameter also called center ranking and 2 [0, 1] the spread parameter. Moreover, d(·, ·) is a distance metric on permutations, which for our paper will be the Kendall tau distance, that is, the number of discordant item pairs dK(⇡,⇡0) = P 1i<jm I {(⇡(i) ⇡(j))(⇡0(i) ⇡0(j)) < 0}. The normalization factor in the definition of the model is equal to Z( ,⇡0) = P
⇡2Sm p ,⇡0(⇡). When the distance metric d is the Kendall tau distance we have the identity Z( ,⇡0) = Z( ) =Qm 1
i=1 Pi j=0
j . Observe that the family of distributions as stated is not an exponential family because of the location parameter ⇡0. If we fix the permutation parameter then the family R(⇡0) = {M ,⇡0 | 2 [0, 1]} is an exponential family with natural parameter ✓ = ln . From now on, if we use the neutral parametrization, we shall write ✓, i.e. Z(✓) = Qm 1 i=1 Pi j=0 e
j✓. The log partition function is denoted by ↵(✓) = logZ(✓). In Appendix A, we review the basic properties of exponential families which we use in our work.
Metrics between distributions. Let p, q be two probability measures in the discrete probability space (⌦,A) then the total variation distance between p and q is defined as dTV (p, q) = 1 2 P x2⌦ |p(x) q(x)| = maxA2A |p(A) q(A)|, and the KL-divergence between p and q is defined as DKL (p||q) = P x2⌦ p(x) ln ⇣ p(x) q(x) ⌘ .

heading: 4 Testing ranking distributions

text:
We shall consider two types of identity tests: asymptotic and non-asymptotic tests. In the asymptotic case, a set of observations and a significance level ↵ > 0 are given in advance, and then our goal is to come up with a test that maximizes the power, i.e. the probability of rejection, if the alternative hypothesis is true, subject to the given level of significance ↵, i.e. the probability of rejection must be below or equal to ↵ if the null hypothesis is true [16]. More concretely, assume that we are given a parametric family of ranking distribution R = {M✓|✓ 2 ⌦} where ⌦ denotes the set of parameters. The observation consists of n rankings Dn = {⇡1, . . . ,⇡n} from a ranking distribution M. The null hypothesis is H0 : M 2 R0 where R0 ⇢ R. As an alternative hypothesis, we consider H1 : M 2 R1(⇢ R) such that R0 \R1 = ;. Then the test is a function f : SnM 7! {0, 1} where 0 corresponds to the acceptance, and 1 to the rejection, such that probability of rejection E [f(Dn)]  ↵ whenever M 2 R0 where the expectation is with respect to M. Our goal is to find a test f for which the power f (M) = E [f(Dn)] for all M 2 R1 is as large as possible. We will deal with randomized test so we consider tests in the form of f : SnM 7! [0, 1] where the output means the probability of rejection.
A test f is called most powerful for a given ↵ and M0 2 R1, if there is no test f 0 such that f (M0) < f 0(M0). A test is uniformly most powerful (UMP) if it is most powerful for any distribution from the alternative hypothesis class. Furthermore, a test is unbiased, if supM2R0 f (M)  ↵  infM2R1 f (M). The unbiased UMP test is referred to as UMPU test.
In case of non-asymptotic setup, the input is a tolerance parameter " > 0 and significance parameter 2 (0, 1), and we assume that the tester has sample access to the unknown distribution M. An (", ) non-asymptotic testing algorithm outputs a sample size n and a test function f : SnM 7! {0, 1} such that, generating Dn from M, we have the following guaranties for f :
1. if the null hypothesis H0 is true, then it outputs reject (f(Dn) = 1) with probability at most , i.e. E [f(Dn)]  2. if M 2 R1 such that dTV(M,R0) > ", then it outputs reject (f(Dn) = 1) with probability at least 1 where dTV(M,Ri) = infM02Ri dTV(M,M0)
Given " and , we say that a testing algorithm is sample-optimal for R0 versus R1 , if no algorithm can have the same confidence guarantee using less samples. If a testing algorithm sample-optimal for any " and , we say that it is uniformly sample-optimal (USO).
One can show that the existence of UMPU test implies the existence of sample-optimal non-asymptotic test as follows with a particular (", ).
Proposition 4.1 If there exists a UMPU test fn with a given significance level ↵ for R0 versus R1 for sample size n, n = 1, 2, . . . , then one can define a sample-optimal non-asymptotic testing algorithm that outputs n and f on input = ↵ and
"f = sup M2R1\R(f) dTV(M,R0) (1)
where R(f) = {M 2 R1 : f (M) 1 }.
The proof of Proposition 4.1 is deferred to Appendix B. The opposite direction does not hold, since a non-asymptotic test does not guarantee anything for any M 2 R1 such that dTV(M,R0)  ".

heading: 5 Testing spread parameter with known central ranking

text: In this section, we will focus on testing the spread parameter when the central ranking is known.

heading: 5.1 Asymptotic case: UMPU test for spread parameter

text:
We will characterize an UMPU test for testing the spread parameter of Mallows model in the asymptotic setting. The UMPU test simply rejects the null hypothesis when the Kendall distance of the data deviates from its expected value under the null hypothesis by a certain margin. This is formalized by Theorem 5.1 whose proof is deferred to Appendix C.
Theorem 5.1 Let us define a test fn(Dn) = gn(T⇡0(Dn)) with T⇡(D) = P ⇡02D dK(⇡,⇡ 0) and 0  t1  t2 where gn(`) = {` /2 [t1, t2]} + c1 · {` = t1} + c2 · {` = t2} with c1, c2 2 [0, 1] such that
1 ↵
2 =
X
`2[t1,µ]
(1 gn(`))PM 0,⇡0 (T⇡0(Dn) = `) = X
`2[µ,t2]
(1 gn(`))PM 0,⇡0 (T⇡0(Dn) = `) .
where µ = EM 0,⇡0 [T⇡0(Dn)]. Then fn is an UMPU level ↵ test with sample size n for H0 : M 2 R0 = {M 0,⇡0} versus H1 : M 2 R1 = {M ,⇡ : 6= 0,⇡ = ⇡0}.
Even if the UMPU test fn defined in Theorem 5.1 plays central role in the asymptotic regime, it is hard to compute exactly, as this is discussed next in Remark 1. However it can be approximated by using 2 distribution which is presented in Appendix D.
Remark 1 (Computational complexity) To determine the critical region of the test fn, one needs to compute the distribution of the sufficient statistic T⇡0(Dn) based on n samples under null hypothesis that is defined as
PM ,⇡ (T⇡(Dn) = `) = `
Z( )n N(`, n) (2)
where Nk = Nk(m) = #{⇡ 2 Sm : dK(⇡,⇡id) = k} is the Mahonian number 1. One can compute the Mahonian number in O(m2) time using the recursion formula. Similarly, N(`, n) can be computed using recursion in O(m2n) time. From practical point of view, it is more challenging to compute PM 0,⇡ (T (Dn) = `) for some ` that depends on the fraction of large integers. In this regime, the numerical error can get significant for large n or m.
1https://oeis.org/A008302

heading: 5.2 An optimal non-asymptotic test based on UMPU test

text:
To tackle the non-asymptotic case to test H0 : M 2 R0 = {M 0,⇡0} versus H1 : M 2 R1 = {M ,⇡0 : dTV (M ,⇡0 ,M 0,⇡0) > "}, first we convert the UMPU test fn into (", ) non-asymptotic test based on Proposition 4.1. For doing this, we pick the smallest n so as the dTV(M 0,⇡0 ,M ,⇡) " for where fn(M ,⇡) 1 . This algorithm is defined in Algorithm 1.
Algorithm 1 Non-asymptotic test for spread parameter based on UMPU 1: Input: ", 2: n⇤ = min {n 2 Z+ : s(n) "} where s(n) = supM2R1\R(fn) dTV (M,M 0,⇡0) 3: Take n⇤ samples Dn⇤ and ouput fn⇤(Dn⇤)
Based on the concentration of the sufficient statistic of exponential family one can compute an upper bound on n⇤. The proof of Theorem 5.2 is deferred to Appendix E.
Theorem 5.2 The sample size n⇤ required by Algorithm 1 is at most 12"2 log 2 .
According to Proposition 4.1, Algorithm 1 is a uniformly sample optimal non-asymptotic test, since it was derived from an UMPU test. However, the upper bound for the sample complexity given in Theorem 5.2 might not be tight. To show that it is indeed tight, we apply the result of [4] regarding optimal learning of Mallows model in terms of total variation.
Corollary 5.3 Any non-asymptotic testing algorithm which distinguishes H0 : M 2 R0 = {M 0,⇡0} from H1 : M 2 R1 = {M ,⇡0 : dTV (M ,⇡0 ,M 0,⇡0) > "} requires ⌦(1/"2) samples.
The proof of Corollary 5.3 is presented in Appendix F. The upper bound given in Theorem 5.2, on the one hand is tight up to a logarithmic factor, and on the other hand it does not depend on m in an explicit way, but R(fn) indeed does which is used in Line 2 of Algorithm 1 for computing s(n).
Algorithm 2 Non-asymptotic test for spread parameter 1: Input: ", 2: "L = min {x 2 [0, 0] : h(x) "} where h(x) = dTV (M 0,⇡0 ,M 0 x,⇡0) 3: "R = min {x 2 [0, 1 0) : h( x) "} 4: "0 = min{"L/2, "R/2}
5: Take n 2 ⌦ ⇣
log(1/ ) m"20 ⌘ samples Dn and solve r lnZ( ) 1nT⇡0(Dn) = 0 to obtain ̂
6: If |̂ 0|  "0 Then Output 0 Else Output 1 . Based on Theorem 5.4

heading: 5.3 Scalable non-asymptotic test based on optimal learning

text:
Algorithm 1 has nice optimality properties, however to solve the optimization in Line 2, the set R(fn) has to be computed, that requires to compute the distribution of the sufficient statistic for n samples which is not scalable according to Remark 1. Motivated by this fact, next we devise a more practical algorithm with weaker optimality guaranty. We recall the result of [4] for optimal parameter learning of Mallows models. For a known central ranking ⇡0, one can compute an estimate for ✓ = ln by finding the root of r lnZ(✓) 1nT⇡0(D) = 0. Since lnZ(✓) is monotone increasing in ✓ based on Theorem A.1 2), we can find an estimate ̂ such that |̂ | < in O(log(1/ )) time based on binary search, therefore we shall neglect the numerical error. If we are given enough sample, the parameter estimate ̂ determines a Mallows model that is close to the true one. We recall this result from [4] (see Theorem 7 therein for more details).
Theorem 5.4 For any < 1, if n ⌦ log (1/ )/(m"20) , then P ⇣ |̂ |  "0 ⌘ 1 .
Theorem 5.4 implies that with n ⌦ log (1/ )/(m"20) samples, we can estimate the true with additive error that is of order "0. This observation suggests a testing algorithm which is presented
in Algorithm 2. The proposed testing algorithm first computes the neighborhood 0 for which the total variation is smaller than " and then test whether the estimated spread parameter is in this neighborhood. Therefore this test falls in the family of “testing by learning”. In fact, [4, Corollary 9] implies that if "0 = ⌦( p log(1/ )/m), Algorithm 2 requires a single sample.
To show that the sample complexity O log (1/ )/(m"20) of Algorithm 2 is optimal, it is enough to show that it matches to the lower bound given in Corollary 5.3. In other words, we have to show that "0 is of order "/ p m. This claim is shown next in the Theorem 5.5 for a wide range of parameters.
Theorem 5.5 There exists a constant c > 0 such that, for any , 0 2 [0, 1] and for every ⇡ 2 Sm, it holds that
1. if | 0|  c/m and , 0 > c, then dTV(M ,⇡,M 0,⇡) 2 ⌦( p m| 0|), 2. if | 0|  c/ p m and , 0 > c then dTV(M ,⇡,M 0,⇡) 2 ⌦( p m| 0|2).
The proof of Theorem 5.5 is deferred to Appendix G. Theorem 5.5 implies that Algorithm 2 is optimal when the difference of parameters of the alternative and the null hypothesis is smaller than c/m, because in this case, dTV(M ,⇡,M 0,⇡) > " implies that "0 = ⌦("/ p m). Thus the sample complexity of Algorithm 2 is O(log(1/ )/"2) that matches the lower bound given in Corollary 5.3 up to a logarithmic factor. Albeit to show that Algorithm 2 is optimal for larger parameter values is an interesting open question. Nevertheless, we believe that this algorithm is optimal based on some numerical analysis that is shown in Figure 1.The lower bound that is linear in the difference of the parameters seems to be a very tight approximation even if | 0 | 1/m, whereas the approximation based on the Hellinger distance, i.e. Theorem 5.5 seems to underestimate the total variation distance for small | 0 |. On the other hand, the liner lower bound does not hold for large value of | 0 |, and the lower bound based on Hellinger distances captures the non-linearity of the total variation for larger | 0 |.
Remark 2 The Algorithm 1 and the Algorithm 2 are very close to each other when " is small enough and 0 is bounded away from 0 and 1. In this case the upper bound dTV
M 0,⇡0 ,M 00,⇡0
p m | 0 00| is very tight and hence both the test and the sample complexity of the two tests are essentially the same. When " is larger or 0 is close to either 1 or 0 then the testing problem becomes easier and Algorithm 1 takes advantage of this fact and needs less samples, whereas Algorithm 2 requires the number of samples given by the worst-case bound.
Remark 3 (Scalable implementation of Algorithm 2.) The optimization tasks defined in Lines 2 and 3 of Algorithm 2 can be solved by using binary search since the total variation distance is monotone increasing and decreasing function of "0 with 0 + "0 and 0 "0, respectively. Moreover, one can compute the total variation distance in an efficient way as dTV(M 0,⇡0 ,M ,⇡0) = 1 2 Pm(m 1)/2 `=0 N` `0/Z( 0) `/Z( ) . This implementation works for moderate number of items, i.e. m  30. However, based on Theorem 5.5, Algorithm 2 can be implemented in a more scalable way without computing the total variation distance. More detailed, Theorem 5.5 provides an easy way to decide whether the model with estimated parameter is "-close to the null model in terms of total variation distance.

heading: 6 Testing for spread parameter with unknown central ranking

heading: 6.1 Asymptotic case

text:
In this section, we consider that case when the null hypothesis consists of a single model H0 : M 2 R0 = {M 0,⇡0} and the alternative hypothesis set is H1 : M 2 R1 = {M ,⇡ : 6= 0 _ ⇡ 6= ⇡0}. Let us consider a hypothetical test which knows the central ranking ⇡ of the underlying model M and it always applies the f⇡n (Dn) = gn(T⇡(D)) where gn is defined in Theorem 5.1. The power of this test is clearly an upper bound for the UMPU tests for this testing problem– if there exists UMPU test at all– since we know that f⇡n is UMPU if ⇡ is known based on Theorem 5.1. However, one can show that in general there is no unbiased test in this case which follows from the following argument.
Remark 4 (Non-existence of UMPU test.) If there exists an ↵ level unbiased test f for testing H0 : M 2 R0 = {M 0,⇡0} vs H1 : M 2 R1 = {M ,⇡ : 6= 0 _ ⇡ 6= ⇡0}, based on Theorem 5.1 and the unbiasedness property, it necessarily accepts all sample D for which T⇡0(D) 2 (t1, t2) where t1 and t2 is the border of the critical region of the ↵ level test f⇡0n . By setting ↵ small enough, the critical region of f⇡0n will include T⇡0({⇡0}) for some ⇡0 such that dK(⇡0,⇡0) 1. Consequently, f (M0,⇡0) = 0 < f (M 0,⇡0) = ↵ which means that the test is biased.
Nevertheless, we will devise an easy-to-implement test with a small bias that is vanishing exponentially fast in n. To devise such a test, we need to get an estimate of the central ranking with high probability. To find the central ranking ⇡0 that maximizes likelihood under Mallows model is known to be an NP-hard, since there is a reduction to the weighted feedback are set problem [1]. Instead, we shall consider an estimator of central ranking based average ranking which can recover the central ranking with high probability as follows.
Lemma 6.1 Let Dn = {⇡1, . . . ,⇡n} is a set of rankings generated i.i.d. from M ,⇡ and let ⇡̄ is the ranking that sorts [m] descending order based on their average rank si = 1n Pn i=1 ⇡j(i). Then it holds that P(⇡̄ 6= ⇡)  e n(1 )/2+2 logm
The proof is based on [2] and presented in Appendix C. We would like to note that [30] analysed P(⇡̄ 6= ⇡) by giving lower bound and upper bound algorithm which approach can be used as well. Based on Lemma 6.1, we can have a simple 2-stage test: 1) take first half of Dn to compute ⇡̄, if ⇡̄ 6= ⇡0 then reject else 2) apply f ⇡̄n using the rest of Dn. Let us denote this 2-stage test by f̄n which works with n samples. Based on Lemma 6.1, one can compute an upper bound on the bias of this test.
Theorem 6.2 Using the notation above, for any ↵ 2 (0, 1/2) and n > 21 log 2 ↵m2 , it holds that f̄2n is an ↵ level test and its bias is at most 1/2e n(1 )/2+2 logm.
The proof is presented in Appendix I. The power of f̄n is at least 1 ↵ if the the central ranking of the alternative hypothesis does not coincide with ⇡0.

heading: 6.2 Non-asymptotic case

text:
Based on Lemma 6.1 it is easy to see that average ranking algorithm recovers the central ranking with O 1
1 log m samples with probability at least 1 , thus it can be applied in the non-
asymptotic case. This leads us to a two stage algorithm to test H0 : M 2 R0 = {M 0,⇡0} versus H1 : {M ,⇡ : dTV (M 0,⇡0 ,M ,⇡) > "} which first estimates the central ranking based on the average ranking algorithm, and then runs Algorithm 1 or 2 with the estimated central ranking. The sample complexity of this two stage algorithm is O(max{ 11 log(m/ ), 1 " log(1/ )}) which remains optimal up to a logm factor since the lower bound presented in Corollary 5.3 applies in this case as well.

heading: 7 Experiments

text: We shall present synthetic experiments to assess the performance asymptotic and non-asymptotic tests. Each result are computed based on 100 repetitions.

heading: 7.1 2 approximation of UMPU test

text: The goal of the first set of experiments is to compare the power of the non-asymptotic test fn defined in Theorem 5.1 based on exact computation of the distribution of the sufficient statistic and its 2 approximation. Figure 2 shows their power for various null and alternative hypothesis. We picked the central ranking to be the identity ranking, since it has no impact on the results. One can see that the approximation slightly deteriorates the power of fn for small sample size, but the difference is marginal for n = 50. We could not compute fn with m > 10 and n = 50 in python. However the 2 approximation can be run with larger m as well as n. As we can see from this experiment, the 2 approximations is accurate already for small sample size and small number of items.

heading: 7.2 Testing parameters of Mallows model for m  30

text: In the second experiments we compare Algorithm 1 and 2. To implement Algorithm 1, we need to compute s(n) = supM2R1\R(fn) dTV (M,M 0,⇡0), which is based on the distribution of the sufficient statistic. We used 2 approximation for the sufficient statistic when we compute s(n). More detailed, we carried out two nested binary searches, one over n and a second nested one over to compute s(n). To compute s(n), the and 1 quantile of the distribution of sufficient statistic based on n samples need to be estimated, so the 2 approximation has to be good on the tails. With this heuristic, there is no performance guaranty for Algorithm 1, that is why it is interesting to test its performance empirically versus an optimal algorithm. The power of Algorithm 1 and 2 are shown in Figure 3. We run Algorithm 2 with log (1/ ) /(2m"20). There are some general trends revealed by these experiments. First, note that the sample sizes are not increasing with m, as one we expected since the sample complexity of both algorithm is O(1/" log(1/ )). On the other hand, as we pointed out in Remark 2, these two tests are very close to each other when 0 is not close too neither 0 nor 1. It can be seen that for 0 = 0.5, the power of these two tests are very close to each other, and for 0 = 0.1 Algorithm 1 has higher power for almost the same number of samples. Note that we used an 2 approximation of Algorithm 1, whereas Algorithm 2 is based on exact computation. Hence, we can verify that the 2 approximation indeed does work well in our setting even for moderate m.

heading: 7.3 Scalable implementation, using single sample

text: As we observed Algorithm 2 requires only a single sample whenever "0 = ⌦( p log(1/ )/m). In addition to this, "0 goes to zero as m goes to infinity, since with a fixed ", the parameter " converges to when m goes to infinity. Therefore for large m single sample is enough for Algorithm 2. We tested this observation with large m. If we run Algorithm 1 and 2 on a single ranking, they boil down to a very simple algorithm which consists of estimating the based on a single sample and if the estimate is far from 0, i.e. |̂ 0| is bigger than a threshold, then it rejects. This threshold is computed by using 2 approximation for Algorithm 1 and based on Theorem 5.5 for Algorithm 2. Figure 4 shows the results for m 2 {100, 1000}. As we can see, very similar results can be obtained for large m like before for m  30, using only a single ranking which indeed shows that these testing algorithms do scale gracefully with m. For an intuitive explanation, our tests for the spread parameter extract information about from the outcome of pairwise comparisons between items in ⇡0, this is how the Kendall-tau distance is computed. The larger m, the more pairwise comparisons available that is why these tests can work based on a single sample intuitively.

heading: 7.4 Experiments with unknown central ranking

text: In the next set of experiments, we test the average ranking algorithm to recover the central ranking. We run this algorithms with different input sample size and estimate their accuracy, i.e. how many times they can recover the central ranking. The results are shown in Figure 5. Note that recovering the central ranking can be done based on relatively small number of examples, that is we need only ⇡ 100 to recover the central ranking with high probability, even if it is shown that this is an NP-hard problem.

heading: 8 Conclusion and Future Work

text:
We introduced several identity tests for Mallows model. We had found that the 2 approximation does not deteriorate the performance of the exact UMPU test fn by a significant margin. Based on the asymptotic exact test, we devised a non-asymptotic test for which we applied the same 2 approximation and we had found that this test achieves similar result to the non-asymptotic test based on optimal learning. Our results clearly show that scalable identity test for Mallows model is indeed feasible even for m = 1000, since the spread parameter can be tested based on a single ranking when m is large and, moreover, the central ranking can be also recovered based on a small number of samples when 0  0.5. This suggest a very simple and scalable approach for identity testing of ranking data that generated from Mallows model: take ⇡ 100 rankings, estimate the central ranking on 100 rankings, and use only a single sample to test the spread parameter by using either Algorithm 1 with 2 approximation or Algorithm 2.
One interesting future direction is to explore hypothesis testing for the Generalized Mallows Model [12]. Apart from testing for the vector of the spread parameters, it would be interesting if we can test whether the samples come from a simple Mallows model, with the alternative that the samples come from a Generalized Mallows Model.
Acknowledgments and Disclosure of Funding
Dimitris Fotakis is supported by the Hellenic Foundation for Research and Innovation (H.F.R.I.) under the “First Call for H.F.R.I. Research Projects to support Faculty members and Researchers and the procurement of high-cost research equipment grant”, project BALSAM, HFRI-FM17-1424.

title: Identity testing for Mallows model