Active clustering for labeling training data
Authors: Quentin Lutz
Elie De Panafieu
Maya Stein
Alex Scott
Venue: NeurIPS 2021 Poster (2021)
Keywords: clustering
active learning
annotation
training data

Abstract: Gathering training data is a key step of any supervised learning task, and it is both critical and expensive. Critical, because the quantity and quality of the training data has a high impact on the performance of the learned function. Expensive, because most practical cases rely on humans-in-the-loop to label the data. The process of determining the correct labels is much more expensive than comparing two items to see whether they belong to the same class. Thus motivated, we propose a setting for training data gathering where the human experts perform the comparatively cheap task of answering pairwise queries, and the computer groups the items into classes (which can be labeled cheaply at the very end of the process). Given the items, we consider two random models for the classes: one where the set partition they form is drawn uniformly, the other one where each item chooses its class independently following a fixed distribution. In the first model, we characterize the algorithms that minimize the average number of queries required to cluster the items and analyze their complexity. In the second model, we analyze a specific algorithm family, propose as a conjecture that they reach the minimum average number of queries and compare their performance to a random approach. We also propose solutions to handle errors or inconsistencies in the experts' answers.

Active clustering for labeling training data
Quentin Lutz" Nokia Bell Labs
Élie de Panafieu
Nokia Bell Labs
quentin. www.:l/tooooi-belllleeeeee com
elie bee com
Alex Scott
Maya Stein University of Chile msteinedim. uchile.. cl
University of Oxford scott mhott@maths.co ox. ac uk
Abstract
Gathering training data is a key step of any supervised learning task, and it is both critical and expensive. Critical, because the quantity and quality the training data has high impact on the performance of the learned function. Expensive, because most practical cases rely on humans-in- -n-th-loot to label the data. The process determining the correct labels is much more expensive than comparing two items to see whether they belong to the same class. Thus motivated, we propose a setting for training data gathering where the human experts perform the comparatively cheap task of answering pairwise queries, and the computer groups the items into classes (which can be labeled cheaply at the very end of the process). Given the items, we consider two random models for the classes: one where the set partition they form is drawn uniformly, the other where each item chooses its class independently following a fixed distribution. In the first model, we characterize the algorithms that minimize the average number of queries required cluster the items and analyze their complexity. In the second model, we analyze a specific algorithm family, propose conjecture that they reach the minimum average number of queries and compare their performance to a random approach. We also propose solutions handle errors or inconsistencies the experts' answers.
Introduction
There is an increasing demand for software implementing supervised learning for classification. Training data input for such software consists of items belonging to distinct classes. The output is classifier: a function that predicts, for any new item, the class it most likely belongs to. Its quality depends critically
the available learning data, in terms of both quantity and quality [21]. But labeling large quantities of data is costly. This task cannot be fully automated, as doing so would assume access to already trained classifier. Thus, human intervention, although expensive, is required. In this article, we focus on helping the human experts build the learning data efficiently.
One natural way for the human experts to proceed is to learn (or discover) the classes and write down their characteristics. Then, items are considered one by one, assigning an existing class to each of them, or creating a new one if necessary. This approach requires the experts to learn the various classes, which, depending on the use-case, can be difficult. different approach, proposed us by Nokia engineer Maria Laura Maag, is to discover the partition by querying the experts two items at time asking whether these belong to the same class or not. This approach avoids the part of process where classes are learned, and can therefore be cheaper. It is the setting consider here, and we call the corresponding algorithm an active clustering algorithm, or for short, AC algorithm.
Authors presented in alphabetical order.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

More precisely, we assume there is a set of size n. with partition unknown to us. An AC AC algorithm will. in each step, choose pair of elements and asks the oracle whether they belong to the same partition class or not. The choices of the queries of the algorithm are allowed to depend on earlier answers. The algorithm will use transitivity inside the partition classes: if each of the pairs z, y and y. is known to lie in the same class (for instance because of positive answers from the oracle), then the algorithm will 'know' that a and z are also in the same class, and it will not submit a query for this pair. The algorithm terminates once the partition is recovered, i.e. when all elements from the same partition class have been shown to belong to the same class, and when for each pair of partition classes, there has been at least one query between their elements.
We investigate AC algorithms under two different random models for the unknown set partition. In Section 2.1, the set partition is sampled uniformly at random, while in Section 2.2, the number of blocks is fixed and each item chooses its class independently following the same distribution. Section 2.3 analyzes the cases where the experts' answers contain errors or inconsistencies. Our proofs, sketched in Section 3, rely on a broad variety of mathematical tools: probability theory, graph theory and analytic combinatorics. We conclude in Section 4, with some interesting open problems and research topics.
Related works. Note that our model has similarities with sorting algorithms. Instead of an array of elements equipped with an order, we consider set of items equipped with a set partition structure. In the sorting algorithm, the oracle determines the order of pair of elements, while in our setting, the oracle tells whether two items belong to the same class. Both in sorting and AC algorithms, the goal is the design of algorithms using few queries.
The cost of annotating raw data to turn it into training data motivated the exploration of several variants of supervised learning. Transfer learning reduces the quantity of labeled data required by using the knowledge gained while solving a different but related problem. Semi-supervised learning reduces it by learning also from the inherent clustering present in unlabeled data. In active learning, the learner chooses the data needing labeling and the goal is to maximize the learning potential for given small number of queries. However, users who want to use supervised learning software for classification as a black-box can mitigate the annotating cost only by modifying the labeling process.
Recent papers [9, 18] acknowledge that humans prefer pairwise queries over pointwise queries as they are better suited for comparisons. Pairwise queries have been considered in semi-supervised clustering [5, 24, 16] where they are called must-link and cannot-link constraints. The pairs of vertices linked by those constraints are random in general, but chosen adaptively in active semi-supervised clustering [4]. In both cases, the existence of a similarity measure between items is assumed, and a general theoretical study of this setting is provided by [19]. This is not the case in [11, 17], where hierarchical clustering is built by successively choosing pairs of items and measuring their similarity. There, the trade-off between the number of measurements and the accuracy of the hierarchical clustering is investigated. The difference with the current paper is that the similarity measure takes real values, while we consider Boolean queries, and that their output is a hierarchical clustering, while our clustering (a set partition) is flat.
The problem we consider is motivated by its application to annotation for supervised machine learning. also belongs to the field of combinatorial search [1, 7]. Related papers [2, 15] consider the problem of reconstructing set partition using queries on sets of elements, where the answer to such a query is whether there is an edge in the queried set, or the number of distinct blocks of the partition present in the queried set, respectively. Our setting is two. Another similar setting is that of entity resolution [13] where recent developments also assume perfect oracles and transitive properties using pairwise queries to reconstruct set partition [23, 25]. In this case, clusters correspond to duplicates of the same entity. Most solutions have a real-valued similarity measure between elements but rely on human verification to improve the results. The entity resolution literature also considers the noisy case for fixed number of clusters [8, 9, 18, 10].
constrained case corresponding to queries of size
2
Our results
2.1
Uniform distribution on partitions
We start by considering the setting where the partition of the n-set is chosen uniformly at random among all possible partitions. The average complexity of an AC algorithm is the average number of
2

---

13
24
13
24
14
13
13
Figure I: Aggregated graphs obtained after various queries and organized into query trees. The positive answers are displayed on top, the negative ones on the bottom. Left, non-chordal query, leading to an average complexity of 13/5. Right, chordal queries from the same initial situation, leading to an optimal average complexity of 12/5.
queries used to recover the random partition. We will define class of AC algorithms, called chordal algorithms, and prove in Theorem that an algorithm has minimal average complexity if and only it is chordal. Theorem 3 shows that all chordal algorithms have the same distribution on their number of queries. Finally, this distribution is characterized both exactly and asymptotically Theorem 4.
It will be useful to use certain graphs marking the 'progress' of the AC algorithm on our n-set. Given a partition of n-set and an AC algorithm, we can associate graph G, to each step of the algorithm. Namely, Go has n vertices, labeled with the elements of our set, and at time > 1, the graph G2 is obtained by adding an edge for each regatively-answert merging pairs of vertices that received a positive answer. (A vertex obtained by joining vertices v, w adjacent all neighbors of each of v, w,, and we label with the union of its earlier labels.) We call G, the aggregated graph at time f. Note that after the last step of the algorithm, the aggregated graph is complete and each of its vertices corresponds to one of the blocks P. Also note that any fixed G. (with labels on vertices also fixed) may appear as the aggregated graph for more than one partition (possibly at a different time t'). We call the set of all these partitions the realizations G Those notions are illustrated in Figure 1.
query, and successively
We now need a quick graph-theorete definition. cycle C a graph is induced if all edges induced by V(C) belong to the cycle. A graph is chordal if its induced cycles all have length three. Chordal graphs appear many applications. We say that an AC algorithm is chordal one of the following equivalent conditions is satisfied (see the Appendix for a proof of the equivalence of the conditions):
(i) for all input partitions, each aggregated graph is chordal,
iii) for all input partitions, no aggregated graph has an induced C4.
(iii) for all input partitions, and for every query u, v made on some aggregated graph G., the intersection of the neighborhoods of u and e separates u and v in G,
where a set S (possibly empty) is said to separate vertices u E ((G) \ S if u and v lie in distinct components of G - S. The queries that keep a graph chordal are exactly those satisfying Condition (ii). Thus, it is used in chordal algorithms to identify the candidate queries. On the other hand, a query satisfying Condition (ii) might turn chordal graph non-chordal by creating an induced cycle of length more than 4 (in which case, Condition (ii) will fail on a later query). Two examples of presented below.
chordal algorithms
The clique algorithm is AC algorithm that gradually grows the partition, starting with the empty partition. Each new item is compared successively to an item of each block of the partition, until it is either added to a block (positive answer to a query) or all blocks have been visited, in which case a new block is created for this item. The universal algorithm finds the block containing the item of largest label by comparing applied to partition the other items, and the previous block is added to the result.
Definition 1.
all remaining items. The algorithm is then
3

---

Theorem 2. On partitions of size n chosen uniformly ar random, an AC algorithm has mininal average complexity if and only if is chordal.
The complexity distribution of an AC algorithm of set S with 2 1 elements is tuple (ag, (1, 02, .0.....) where a; the number of partitions S for which the algorithm has complex- for all < n - 1, and ((z) = 1, for any AC algorithm. Our next result shows that constraining the average complexity to be minimal fixes the complexity distribution.
ity i. Clearly,
Theorem 3. On partitions of size n chosen uniformly at random, all chordal AC algorithms have the same complexity distribution.
Note that either Theorems 2 and implies weaker statement that chordal AC algorithms of an ri-set have the same average complexity, but with very different proofs. Sketches of the proofs of Theorems and can be found in sections 3.1 and 3.2.
In practice, several human experts work in parallel to annotate the training data. The chordal algorithms can easily parallelized: when an expert becomes available, give him query that would keep the aggregated graph chordal if all pending queries received negative answers. The condition ensures the chordality of the parallelized algorithm.
Our third theorem for this setting describes the distribution the number of queries used by chordal algorithms partitions chosen uniformly random. Two formulas for the probability generating function are proposed. The first one is well suited for computer algebra manipulations, while the second one, elegant, is better suited for asymptotic analysis. It g-analog of Dobiński's formula for Bell numbers
n!
m20
(see e.g. [14, p.762)), counting the number of partitions of size n. In order to state the theorem, we introduce the q-analogs of integer, the factorial, the Pochhammer symbol and the exponential
n [b) k=1
n-1 II ag*), c,(2)=
[n],
(a;g),
Σ A20
n
Observe that the q-analog reduce to their classic counterparts for q = 1. The Lambert function W (a) defined for any positive the unique solution of the equation we" As x. tends to infinity, we have W (z:) = log(x)) - log(log(z)) + o(1).
Theorem 4. Let X,, denote the complexity of a chordal algorithm on a purtition of size chosen uniformly random. The distribution of Xn, has probability generating function in the variable equal to the two following expressions
Σ 1
(-1)
(+ (1-2:0)
and
113
1 111
Σ
[m]] [m]]]
Bn
Bn (1/9))
m20
The normalized variable (Xn En)/or converges distribution to a standard Gaussian law, where
E, = = (2W - (m)
1 (W(n) - 4W(n) + ew and - W(n) +1
As corollary, the average complexity chordal algorithms is asymptotically (*) /lg(()).. Because of this almost quadratic optimal complexity, using pairwise queries only be better than direct classification for relatively small data sets. We arrive at a different conclusion for the model presented in the next section, where AC algorithm have linear complexity.
2.2 Random partitions with fixed number of blocks
In many real-world applications, we have information on the number classes and their respective sizes in the data requiring annotation. This motivates the introduction of the following alternative random model for the set partition investigated by the AC algorithms. Now, the of partitions of the neset S is distributed in not necessarily uniform way, but each element of S has probability of

---

P; to belong to the partition class C2 (and the probabilities sum to 1). Our main focus here will be on the most applicable and accessible variant of the above-described model, where the number of partition class is a fixed number k. and & is small compared to n. Without loss of generality, we can assume that the probabilities p1, P2......... Pk in this model satisfy p1 2 P2 2 ... Pk-
Intuitively, an algorithm with low average complexity should avoid making many comparisons between different classes (one such comparison is always necessary between any pair of classes, but more comparisons are not helpful). For this reason, it seems plausible that an AC algorithm with optimal complexity should compare new element first with the largest class identified up this moment, as both the new element and the largest class are most likely to coincide with C1, the 'most likely class'. This is precisely how the clique AC algorithm from Definition operates, where we add the additional refinement that each new item is compared to the blocks discovered so far in decreasing order of their sizes. With this refinement, we conjecture the following.
Conjecture 5. For an n-set with a random partition with probabilities P1.P2.... Plo the clique algorithm has minimal average complexity umong all AC algorithms.
In support of Conjecture 5, we present the following results. Firstly, we exhibit the limit behaviour of the expected number of queries of the clique algorithm. The simple proof of this theorem can be found in the appendix. It allows one to decide for practical cases whether direct classification by human experts or pairwise queries will be more efficient to annotate the training data.
Theorem 6. Let pr 2 ... 2 Pk be fixed with Σ P: 1. Let X denote the expected number of queries made by the clique algorithm with these parameters for n-set. Then E[X] E ip.n.
We now compare the complexity of the clique algorithm with the complexity of an algorithm that chooses its queries randomly. More precisely, we define the random algorithm to be the one that at each step compares a pair elements chosen uniformly at random among all pairs whose relation is not known at this time (that is, they are neither known to belong to the same class, nor known to belong to different classes). The reason for analyzing the random algorithm is that one may think of this algorithm experts, which might make this procedure cheap to implement. It turns out, however, that there is a cost in form of larger average complexity associated the random algorithm, if compared to proposed candidate for the optimal algorithm, the clique algorithm.
the one that models the situation where no strategy at all is used by the human
Theorem 7. Let P1 2 ... 2 Pk be fixed with Σx= =
1. Let X be the number of queries of random algorithm with these parameters for an n-set. Then [[X] ~ n - k Eies (Ps,P;)n, where
2a 2008
B
f(a B)
In(a/3) a + B.
a-B
Note that all the p; are equal to 1/k, then by Theorems 6 and 7, the expected number of queries produced by the random algorithm is asymptotically n - k + (2))k((a) = k(n - 1)), while for the clique algorithm this number (k + 1)m/2.
2.3
Noisy queries
We now discuss the situation when answers to the query can be inconsistent, due to errors from the human experts or ambiguity in the data. Different perspectives can be found in [10. 18]. Let G denote the graph where vertices correspond to items from the data set, edges to queries, so each edge is either positive or negative depending on the answer. Because of potential errors, the aggregated graph not sufficient for the analysis anymore, but it can be recovered by contracting to a vertex each positive component of G.
Correcting errors. An inconsistency is detected if and only if G contains a contradictory cycle: a cycle where all edges except one are positive. At each step, we consider the shortest contradictory cycle and ask a query that cuts it in two, following a divide-and-conque number of queries, if no additional error occurred, a false answer or ambiguous data is identified and the answer is corrected. At any point, if the number of contradictions detected grows out of proportion (edit war between human experts), a classic clustering algorithm can applied as last resort to settle the differences of opinions. We now focus on the problem of detecting inconsistencies.
strategy. After logarithmic
5

---

Bounded number of errors. To ensure the detection of at most & enrors, each positive component of graph G must be (k + 1>-edge-connecter and any two positive components must be linked by at least k + 1 negative edges. The minimal number of queries for items and b blocks, assuming no block has size 1, is then (A: + ()) + n2) because each vertex of G has at least h + positive neighbors.
Small probability of error. To avoid this high cost, the error detection criteria can be relaxed. We now consider that each answer has a small probability of error and add a few queries at the end of the AC algorithm, while keeping the probability of undetected errors low. More precisely, let co + Cip + c2p² + ... denote the Taylor expansion of this probability at O. Since is assumed be small, our aim is to minimize the vector (co, CI,...) for the lexicographic order. During the AC algorithm, when a query between two classes is needed, we choose the items in those classes to maintain the following structure. Any positive component should be a tree with vertices of degree at most 3. We call 2-path path of vertices of degree 2 linking two vertices of degree 3. The 2- 2-paths should all have length close to a parameter r of the algorithm. At the end of the algorithm, we introduce additional queries between pairs of leaves of the same tree, turning each positive component of size at least 2 into either a 5-edge-connected graph or a cycle of length close to r. Queries are also added to ensure that any two positive components are linked by at least 3 negative edges. Assuming the partition contains b blocks and the average length of the 2-paths is r. the number of additional inside the blocks, plus the
queries compared to the noiseless setting is approximately 3742
potential queries between blocks (at most 2 (()). This setting ensures Co C1 and minimizes C2 (see [6]). If the length of all 2-paths and the sizes of positive components that cycles are bounded by r', then c92 = (" +1)
2 3 Thus, the choice of the parameter is a trade-off between the number
of additional queries and the robustness noise of the algorithm.
3 Proofs
3.1 Proof of Theorem
We will prove Theorem 2 by analyzing the types of queries made by an AC algorithm. For this, we classify the queries made by an AC algorithm into three types:
Core queries are those that receive a positive answer.
A query time t is excessive if it compares vertices and y that joined by an induced path in G2 on an even number of vertices that alternates between two partition classes.
A query at time is productive if it is neither core nor excessive.
Note that each query of exactly one type, as excessive queries have receive negative answers. Also note that as the core queries are the only ones that shrink G,, the number of core queries does not depend on the algorithm.
Lemma 8. For any AC algorithm and any partition of a set of size n containing k classes, the number of core queries is exactly n k.
Next, we show that for random partition, also the number of productive queries is, in expectation, the same for all AC algorithms.
Lemma 9. Let Pi be the set of partitions of [n]] into exactly k sets, and choose P E Ps. uniformly at random. Then all algorithms have the same expected number of productive queries.
Because of space constraints, we only present sketch of the proof of this lemma here. The full proof of Lemma 9 is in the appendix.
Sketch of the proof of Lemma 9. Consider partition of [n]] into k sets C1, C2..... Cv. and let qu be the number of productive queries comparing a vertex from C. with a vertex from Cj. Then E(gyy] E((12] for all i, j. and by linearity of expectation the expected number of productive queries is (5) E[g12]. Thus, are done if we can prove that E[q12] is independent from the choice of the algorithm. It suffices to show that E[g12|C U C2 S] is independent from the choice of algorithm

---

because
E[q12]
Σ
Elq1a (012|Cuun 1 UC SC
Sc
In other words, we wish to understand the expected number of productive queries of an AC algorithm working on a partition with exactly two classes of set of size (S), chosen uniformly at random (there are 2| -2 2 such partitions). Observe that this very similar calculating the expected number of productive queries for a uniformly-chosen partition with al most two classes (there are 2| such partitions). In fact, it not hard to see that these numbers only differ by a factor of restrict our attention to the expectation of the latter number, which is easier calculate, the model is equivalent to assigning independently to each element of S a value in {0, 1 uniformly at random.
2| 2181-2 So we can
More precisely, we will now argue that the expected number of productive queries in this scenario is ",, for each partition algorithm. For this, note that each component of any aggregated graph G, is either single vertex colorings, and it is not hard to show by induction that these colorings are equally likely. So, whenever the algorithm makes query for two vertices from distinct components, answers "yes' and 'no" are equalty likely. As the algorithm makes n - such queries (since each such query reduces the number of components by 1), it follows from linearity of expectation, that the expected number of productive queries is (n 1).
nonempty bipartite graph. Moreover, each component has two possible
Finally, we analyze the excessive queries of an AC algorithm. Lemma 10. An AC algorithm makes excessive queries if and only if it is chordal.
For the proof, we need the following easy lemma whose proof can be found in the appendix. Lemma 11. For each non-chordal AC algorithm, there is an inpul partition and time such that Ge has an induced C1 one of whose edges comes from a negative query in step 1-
Proof of Lemma 10. By definition, a chordal AC algorithm has no aggregated graphs with induced cycles of length at least 4. So, since an excessive query. if answered negatively, creates an induced cycle of even length at least 4, chordal algorithms make no excessive queries.
For the other direction, let us show that any non-chordal AC algorithm makes at least one excessive query for some partition. By Fact 1 11, a non-chordal AC algorithm has, for some partition of the ground set, an aggregated graph G, with an induced C4, on vertices U1 02 Vg U4, in this order, such that the last query concerned the pair v1, 04. There is realization of G, where oi and vy in one partition class, and and i4 are in another partition class. For this partition, the query 0i, at time t is an excessive query.
We are ready for the proof of Theorem 2.
Proof of Theorem 2. By Lemmas 8 and 9, all AC algorithms have the same expected number of core queries and productive queries. So the optimal algorithms are the ones with the minimum expected number of excessive queries. By Lemma 10, these are the chordal algorithms.
3.2 Proof of Theorem
The full proof is in the appendix. We prove a more general result which allows for the algorithm to start with any aggregated graph instead of the empty graph. We prove this using induction on the number of non-edges of G = (V, E), the base case being trivial. We fix some useful notation now: For x, y V, set G(zy)= = (V, E U (ry)), and let Gay be obtained from G by identifying x and y.
For the induction step consider a graph G with k + 1 missing edges, and let Au, A be two distinct chordal AC algorithms for G. By induction, Say the first query of A, is u, D; for = 0, 1. Then G(u,v;) is chordal for i = 0, 1. Note that we can assume that uo f u1. We distinguish two cases.
can assume that Ag and A₁ differ in their first queries.
Case 1. G( (u) 01) is chordal and moreover, if up = in then uguu & F.))). Then, for = 0, 1, the edge iazn can be chosen the first edge of chordal AC algorithm for G(u1-1U1-1) or for
7

---

Gu As the induction hypothesis applies to G(u1-;U1-1) and to Gui-iFi-.- we can assume that 4 the second edge in Ai-i. Observe that for each i 0, 1 after the second query of A, we arrive at one of the four graphs (Gugro)uiyy ((ugvo) G(u (i)uono ((unt))) (ujvi). Thus the complexity distribution of Ag and A is identical (as can be computed from the complexity distribution for the algorithms starting at these four graphs).
Case 2. ( vi) is chordal, vo 01 and tgun E(G), or ((ugvo)(urt) is not chordal. This case is harder to analyze, but one can show that either there is an edge we E E(G) such that G(ur), G(uv) (un and (uuv)(u1e) are chordal, or G has very specific shape. In the former case, we proceed as in the previous paragraph using the edge we proxy. In the latter case our argument relies on our knowledge on the structure of G.
3.3 Proof of Theorem
According to Theorem 3, all chordal algorithms share the same complexity distribution, so we investigate specific chordal algorithm, the universal AC algorithm (see Definition without loss of generality. This algorithm first computes the block B containing the largest item by comparing it to all other items, then calculates the partition for the remaining items, and finally inserts the block B in Q. Let query denote the number of queries used by the universal AC algorithm to recover partition p. Let us introduce the generating function
query(()) (p) z|pl
P(z,g)
Σ
lp
partition
The symbolic method presented in [14] translates the description of the algorithm into the differential equation characterizing ()2.g)
0, 0_,(z) P(gz,
with initial condition P(O, = 1. Observing that the function e1-0= is solution of similar
differential equation, consider solutions of the form P(2, 9) A(2, 1"v. The differential equation on 4) translates into a differential equation on A(z,4)
0. A=,(2, + 1 A(z, = A(q2,))
with initial condition A(0, g) = 1. Decomposing A(z, ②) as series z, we find the solution
(-12g2)
A(2,
Σ k20
k!
By definition, the probability generating function PGF,, (4) of the complexity distribution when the set of items has size n is linked to our generating function by the relation
n!! B [ P((,
PGF
where the Bell number B, counts the number of partitions of size The first exact expression from the theorem is obtained directly by coefficient extraction. The second one requires using the following classic g-identities
(g: g)m
x
cg(z) ((1 - g)z; g)
(1 q)m
(x) g)
(g: q)
n20
To obtain the Gaussian limit law, we prove that the Laplace transform of the normalized random variable X = (X, Fn)/an
= PGF (. -een/o0
eEn/on
converges to the Laplace transform of the standard Gaussian e pointwise for in neighborhood of 0. To do so, we apply to the second expression the Laplace method for sums [14, p. 761], using in the process g-analog of Stirling's approximation [20].

---

3.4 Proof of Theorem 7
Since Lemma is still valid in this setting, suffices to prove the following, with f as in Theorem
Theorem 12. Let pt 2 ... 2 be fixed with >x - = 1. Let X denote the number of edges between classes using random algorithm. Then E. E Dies [(P, Py)
Proof. We only give sketch here, the appendix for further detail. Instead of analyzing the random algorithm, we analyze the following process. Begin with all vertices marked active, At each time step, pick (with replacement) a random pair {u, o} and:
If u, e are active and from distinct classes i,j then say we have generated an ij-crossedge. If u, U, both active and in class then mark exactly one of and inactive.
If one of u, v is inactive, then do nothing.
Note that as the process runs, the number of active vertices is monotonic decreasing, and we are increasingly likely to choose pairs where one vertex is inactive. These contribute to the new process, do not generate new comparisons between pairs. So we are looking a (randomly) slowed down version of the random algorithm; but this makes the analysis much simpler.
Let (t) denote the number of active class vertices after time steps, and (t)(t) denote the number of ij-crossedges that are generated in the first time steps. Then at step t + 1, the probability that we pick two active vertices in class is
(1((t)
(t) n
Writing = we estimate (t)() via a function I = xx() satisfying the differential equation 0,x(t)
=(t)² with r(0) = pn This has solution
n
pn
xt))
+ pt/n
One can show that with high probability, (t) tracks xx() quite closely.
Now we estimate the number ij-crossedges. Using our estimates for x1(()) and (i)(), we see that the probability of an ij crossedge at step /. + i
2x, (t)(()z
2n
x, (t)xz(((t))
n²
(t nt+:)/))(t-o n/p,)
Let p = Pt and q = py. Similarly as before, we can model the growth of mi (t) by a function c c(t) satisfying the differential equation
2n
0,0(1) = (t n/p)(t + n/g)
with c(0) 0. Calculations show that if p = q. then
1
c(t) = 2pm 1
2pm
2 2pt/n
and if p + g, then
2npg In(p/g)
<(t)
p 9
as t/n cc. In order to prove the theorem, we now run the process for time Kn, where K is large constant. We note that at this point, we have (with high probability) at most en remaining active vertices for some small constant c. But now we revert to the original process: noting that for any partition into i classes, fraction of at least (about) 1/k of the pairs lie inside some class, we see that at each step the process reduces the number of vertices with constant probability. The remaining expected running time is therefore (ken).

---

We note that it is also possible to prove a central limit theorem for the running time of the clique algorithm (roughly: after 1/2 comparisons, we are very likely to have seen representatives from every set in the partition, and more from the ith class than the jth class whenever p: > Pş: we estimate the contribution from the remaining steps by an sum of independent random variables). We do not pursue the details here.
4 Conclusion
In this article, motivated by the building of training data for supervised learning, we studied active clustering using pairwise comparisons and without any other additional information (such as similarity measure between items).
Two random models for the secret set partition where considered: the uniform model and the bounded number of blocks model. They correspond to different practical annotation situations. The uniform model reflects the case where nothing is known about the set partition. In that case, many clusters will typically be discarded at the end of the clustering process, as they are too small for the supervised learning algorithm to learn anything from them. Thus, this a worst case scenario. When some information is available on the set partition, such as its number of blocks or their relative sizes, the bounded number of blocks model becomes applicable.
Comparison between direct labeling and pairwise comparisons. As practical application of this work, we provided tools to decide whether direct labeling or pairwise comparisons will be more efficient for given annotation task. One should first decide whether the uniform model or the bounded number of blocks model best represents the data. In both cases, our theorems provide estimates for the number of pairwise queries required. Then the time taken by expert to answer a direct labeling query or a pairwise comparison should be measured. Finally, combining those estimates, the time required to annotate the data using direct labeling pairwise comparison can be compared. We also provided tools to detect and correct errors in the experts' answers.
Similarity measures. Generally, similarity measure on the data is available and improves the quality of the queries we can propose to the human experts. This similarity measure can be a heuristic that depends only the format of the data. For example, if we are classifying technical documents, a text distance can be used. The similarity could also be trained on a small set of data already labeled. This setting has been analyzed by [19]. Our motivation for annotating data is to train supervised learning algorithm. However, one could use active learning to merge and replace the annotation and learning steps. The problem is then find the queries that will improve the learned classifier the most.
In this article, we focused the case where such similarity measures not available. However, are confident that the mathematical tools developed here will be useful to analyze more elaborate settings well. In particular, the aggregated graph contains exactly the information the transitive closure of the answers to the pairwise queries, so its structure should prove relevant whenever pairwise comparisons considered.
Open problems. We leave as open problems the proof that the clique algorithm reaches the minimal average complexity in the bounded number of blocks model, and the complexity analysis of the random algorithm in the uniform model.
Acknowledgments and Disclosure of Funding
We thank Maria Laura Maag (Nokia) for introducing us the problem of clustering using pairwise comparisons, and Louis Cohen, who sadly could not continue working with us on this topic. The authors of this paper met through and were supported by the RandNET project (Rise project H2020- EU.1.3.3). Alex Scott was supported by EPSRC grant EP/V007327/1. Quentin Lutz and Élie de Panafieu produced part of this work at Lincs (www. lincc.cc.....ccc fr). Quentin Lutz is supported by Nokia Bell Labs (CIFRE convention 2018/1648). Maya Stein was supported by ANID Regular Grant 1 1180830, and by ANID PIA ACE210010.
10

---

References
[1] Martin Aigner. Combinatorial search. John Wiley Sons, Inc., 1988.
[2] Noga Alon and Vera Asodi. "Learning a Hidden Subgraph". In: SIAM J. Discret. Math. 18 (4 2005), pp. 697-712.
[3] Noga Alon and Joel Spencer. The probabilistic method. Fourth. Wiley Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, 2016, pp- xiv+375, ISBN: 978-1-119-061953
[4] Sugato Basu, Arindam Banerjee, and Raymond J Mooney. "Active semi-supervision for pairwise constrained clustering". In: Proceedings of the 2004 SIAM international conference on data mining. SIAM. 2004, pp. 333-344.
[5] Sugato Basu, Mikhail Bilenko, and Raymond J Mooney. "A probabilistic framework for semi- supervised clustering". In: Proceedings of the tenth ACM SIGKDD international conference Knowledge discovery and data mining. 2004, pp. 59-68.
[6] Douglas Bauer et al. "Combinatorial optimization problems in the analysis and design of probabilistic networks". In: Networks 15.2 (1985), pp. 257-271.
[7] Mathilde Bouvel, Vladimir Grebinski, and Gregory Kucherov. "Combinatorial search on graphs motivated by bioinformatics applications: brief survey". In: International Workshop on Graph-Theoretic Theoretic Concepts in Computer Science. Springer. 2005, pp. 16-27.
[8] Nicolo Cesa-Bianche et al. A correlation clustering approach to link classification in signed net- works. JMLR Workshop and Conference Proceedings, extended version on arXiv: 1ee1131114440 ,4769, 2012.
[9] Eli Chien, Huozhi Zhou, and Pan Li. "HS2: Active learning over hypergraphs with pointwise and pairwise queries". In: The 22nd International Conference on Artificial Intelligence and Statistics. PMLR. 2019, pp. 2466-2475.
[10] Susan Davidson et al. "Top-k and clustering with noisy comparisons". In: ACM Transactions Database Systems (TODS) 39.4 (2014), pp. 1-39.
[11] Brian Eriksson et al. "Active clustering: Robust and efficient hierarchical clustering using adaptively selected similarities". In: Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics. JMLR Workshop and Conference Proceedings. 2011 1,
pp. 260-268.
[12] Thomas Ernst. A comprehensive treatment of q-calculus. Springer Science & Business Media, 2012.
[13] Ivan Fellegi and Alan B Sunter. "A theory for record linkage". In: Journal of the American Statistical Association 64.328 (1969), pp. 1183-1210.
[14] Philippe Flajolet and Robert Sedgewick. Analytic combinatorics. Cambridge University Press, 2009.
[15] Vladimir Grebinski and Gregory Kucherov. "Reconstructing set partitions". In: Tenth Annual
ACM-SIAM Symposium on Discrete Algorithms- '99, ACM/SIAM. 1999, p. 2.
[16] Daniel Gribel, Michel Gendreau, and Thibaut Vidal. "Semi-SSpervisse" Clustering with Inac- curate Pairwise Annotations". In: arXiv preprint arXiv: (04.02/44 146 (2021).
[17] Akshay Krishnamurthy al. "Efficient active algorithms for hierarchical clustering". In: arXiv preprint arXiv: 4672 (2012).
[18] Arya Mazumdar and Barna Saha. Clustering with Noisy Queries. 2017. arXiv: 1706.07510 [stat. ML].
[19] Arya Mazumdar and Barna Saha. "Query complexity of clustering with side information". In: Advances in Neural Information Processing Systems. 2017, pp. 4685-4696.
[20] Daniel Moak. "The q- ananloog of Stirling's formula". In: The Rocky Mountain Journal of Mathematics (1 (1984), pp. 403-413.
[21] Curtis G Northcutt, Anish Athalye, and Jonas Mueller. "Pervasive label errors in test sets
destabilize machine learning benchmarks". In: arXiv preprint arXiv:2103. 14.449 (2021).
[22] The Sage Developers. SageMath, the Sage Mathematics Software System (Version 9.0). https://www. www.w.sageaahh...mmmmm org. 2020.
[23] Norases Vesdapunt, Kedar Bellare, and Nilesh Dalvi. "Crowdsourcing algorithms for entity resolution". In: Proceedings of the VLDB Endowment 7.12 (2014), pp. 1071-1082.

---

[24] Kiri Wagstaff et al. "Constrained k-means clustering with background knowledge", In: Ioml.
Vol. 1. 2001, pp. 577-584.
[25]
Jiannan Wang et al. "Leveraging Transitive Relations for Crowdsourced Joins". In: SIGMOD
11: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. arXiv Preprint 1408.69 6966. 2013, pp. 229-240.
12


Reviews:
[{"review_id": "YPk4B6F1Y5N", "reviewer": "Reviewer_onZc", "summary": "Given an unknown partition of the data, either randomly drawn uniformly from the space of partition, or complying to a distribution of items in cluster, this paper investigates the problem of having an optimal querying strategy to recover the aforesaid partition. \n\nThe paper explores this from a theoretical perspective, showing that the chordal property is a fundamental requirement in the first case (uniform sampling of partition), and suggesting that it may also be very useful in the distribution case (which is much closer to actual supervised learning). ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is very well-written, and although it is not exactly my field of expertise, I could easily follow it and get the main intuition /results, and have a reasonable check at the proofs (in the amount of time I could allocate to the paper), which seem correct to me. \n\nGiven the caveat related to my expertise, it is hard for me to really give an opinion about the originality in the paper, that is more about elicitation or recovering of partitions in an optimal sequence of queries than it is about supervised learning. I thin the results are really nice, but I cannot really say if some works in operations research or combinatorial optimisation have not considered similar problems before. \n\nI have only two main comments about this paper, who are not directly related to the main results, but rather to the presentation and to practical considerations:\n\n* The first is that the paper content seems to me completely disconnected from the initial motivation of the paper, which is to perform elicitation/active learning for supervised learning problem through comparative/pairwise queries (BTW, I am not convinced that these latter are always easier to solve for an expert). However, once the introduction is passed, there is nothing in the paper telling us how the provided (nice) results do connect to supervised learning, nor any evidence that they would do a better job at supervised learning than classical active learning techniques (as no experiments are present). I therefore do not perceive active learning in supervised setting as the main motivation of the paper, and would be actually surprised if it actually was, given the absence of experimental comparison or even theoretical insight as to how this would relate to, e.g., minimizing an expected loss function. In my opinion it would be more honest to mention supervised learning in the conclusions as a possible application of the presented results, rather than stating it as an initial motivation for the study, which rather appear artificial. I do think the results stand on their own, and I would avoid having a selling point that is not really followed by concrete application to it. \n\n* The second is that while we do have nice theoretical results about various possible algorithms and their optimality, one could wonder which of the two proposed algorithms (that could have been given as algorithm in a proper floating environment, at least in the appendices) actually works better and under which conditions in practice? It is one nice thing to provide theoretical arguments in favour of different methods, but practical/numerical results may actually tells a different story. It would therefore be a nice complement to at least have some experimental results, even simulated. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes they have", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6h"}, "extra_text": {}}, {"review_id": "6n1V7kDE4Xz", "reviewer": "Reviewer_9dwD", "summary": "The authors address the problem of pairwise clustering, where users are given pairs of instances and need to decide whether they belong to the same class or not. Given the human feedback, a clustering is computed. The authors show the importance of chordal algorithms for complexity and analyze random and clique algorithms. ", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The technical contribution is very strong and provides elaborate insights in active clustering mechanisms. The paper is overall very well written and, given the complexity, easy to understand, visualizations provide additional intuition. \n\nSome practical issues, like, e.g., dealing with noisy queries/answers however remain unclear. Though I agree that space is short, I would be interested in learning more about the integration of the provided strategy. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "-xToN3ncLWm", "reviewer": "Reviewer_sREn", "summary": "\nThe authors propose an active clustering algorithm where the oracle annotate examples in must-link, cannot-link fashion. Assuming that the cost of labeling pairwise relationships of unlabeled data is less costly than annotating examples.  They propose to represent the pairwise labeling process as an n-set partition overall the unlabeled set of size n. They study the distribution of the number of queries of the proposed with the objective to bound the average number of queries needed by an AC algorithm to recover the n-set partition, they suggest a first setting where the partition is assumed to be drawn from a uniform random distribution of all possible partitions over the n-set, they show that if the process of labeling forms a chordal graph for all queries in the AC algorithm, then the average complexity in terms of number of queries is minimal and comparable for all  AC algorithms with chordal graph constraint, the argument made to suggest that pairwise labeling is always better than sample labeling in this setting is unclear. For the second setting, they assume that the distribution of random partitions generates graphs with a fixed number of blocks which relates to the number of classes and class distribution of the unlabeled set, they show that the clique AC algorithm exhibits minimal linear complexity convergence in terms of number of query in this case. Lastly,  they propose a method for correcting errors in the process of labeling pairwise examples, they show that we can detect k labeling errors under strong connectivity conditions depending on k on the partition graph.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written, however there are no empirical results to back up the study\n* Underlying assumption made in this work (all unlabeled examples are uniformly informative) is too strong. In most active learning scenarios the cost of labeling (sample labeling or pairwise labeling) all the unlabeled set is costly,  in this case it is interesting to learn predictors with a labeling cost << n . \nA naive solution for AC algorithms would be to learn a classifier after every query t made, the stopping criterion will depend on the accuracy of the learned classifier.  Such solutions do not take into account the informativity of different examples to solve the classification task in hand.\n* Connectivity constraints for labeling error detection are hard to control empirically for larger k.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a well-written paper that makes a nice theoretical contribution in analyzing two models for the problem of gathering training data, where the human experts are able to answer pairwise queries.  There is a noted lack of experiments, but the theoretical contributions alone are enough to warrant acceptance.
Decision: Accept (Poster)