Bayesian Decision Process for Budget-efficient Crowdsourced Clustering

1 Introduction

Clustering is one of the most important tasks in unsupervised machine learning with a wide range of applications. The goal of clustering is to group similar items together based on an appropriately chosen similarity or dissimilarity (distance) measure between pairs of items. Popular clustering methods include connectivity-based clustering [Nocetti et al., 2003], centroid-based clustering [Zhong, 2005] and distributionbased clustering [Xu et al., 1998]. When each item can be represented by a feature vector, a common practice is to define a similarity/dissimilarity measure (e.g., cosine similarity or Euclidean distance) between pairs of items based on their feature vectors. However, there exist many scenarios where such feature vectors either are difficult to construct or do not well reflect the similarity between items, especially when the similarity needs to be consistent with human's perception, e.g., the similarity between paintings, songs, and videos. In order to facilitate clustering tasks under these situations, human workers are often employed to exam pairs of items and manually determine whether each pair is similar or not. The clustering procedure based on human-provided similarity judgment is called crowdsourced clustering.

Crowdsourcing is an effective approach to integrate human's intelligence by decomposing a main task (e.g. clustering) into many micro tasks (e.g. measuring similarity between pairs) which can be completed by online workers in parallel. Crowdsourcing has been successfully utilized in various tasks, such as clustering [Mazumdar and Saha, 2016; Luo et al., 2018], classification [Tran-Thanh et al., 2013; Bragg et al., 2013], ranking [Chen et al., 2013] and entity resolution [Whang et al., 2013; Vesdapunt et al., 2014].

In spite of its popularity, the information collected from crowdsourcing can be very noisy because of the different backgrounds of the workers, especially when each micro task requires a worker's subjective decision, e.g., when a worker is asked to judge whether two pictures are similar or not. Moreover, information provided by careless or unreliable workers will also have a low quality. Hence, a common strategy in crowdsourcing is to assign the same micro task to multiple workers, hoping that the majority of workers are reliable and different opinions can be integrated into a correct final conclusion, e.g. by majority vote (see, e.g., [Tao et al., 2019; Zhang and Wu, 2018]). However, this strategy significantly increases the cost of crowdsourcing since a worker will receive a monetary reward for each completed micro task. When the owner of the tasks has only a small amount of budget, it is important to dynamically allocate the budget over micro tasks and workers such that the budget will shift towards more challenging micro tasks and more reliable workers, maximizing the quality of the final output before the budget runs out. This problem is called the budget allocation problem in crowdsourcing. A few budget allocation strategies have been developed for classification and ranking in crowdsourcing [Karger et al., 2011; Chen et al., 2015; Chen et al., 2016].

In the setting of the crowdsourced clustering problem, a micro task requires a worker to assign a binary label to each pair of items, indicating if they are similar or not. In this case, the two key factors affecting budget allocation are (1) the similarity between each pair of items and (2) the reliability of each worker. For a pair of highly similar/dissimilar items, the labels provided by workers are consistent and the true similarity can be easily estimated with a little budget.

On the contrary, when the similarity is ambiguous, the labels become inconsistent and thus more workers' opinions are needed. However, these two factors are unknown initially and can only be estimated after collecting some labels from workers. This motivates us to develop a multi-stage budget allocation strategy where these two factors are dynamically estimated based on the labels collected in earlier stages and used to guide the budget allocation in the remaining stages.

To do so, we model the similarity as a score between zero and one, and view the clustering problem as the minimum K-cut problem on a graph where each node is an item and each edge is weighted by the similarity between the nodes [Goldschmidt and Hochbaum, 1988]. We first consider the setting where all workers are fully reliable. In this case, we introduce a prior distribution for the similarity between each pair of items. Then we formulate the crowdsourced clustering problem into a finite-horizon Bayesian Markov decision process (MDP) [Puterman, 2014] where, in each stage, the state variables are posterior distributions of similarity scores given the collected labels, and the action is to select an edge (a pair of items) and send it to a random worker for labeling. Because solving a MDP is computationally challenging due to the curse of dimensionality, effective approximate policies, such as knowledge gradient (KG) [Gupta andMiescke, 1996; Frazier et al., 2008] and optimistic knowledge gradient (OptKG) [Chen et al., 2015], have been proposed. Our policy is related to the Opt-KG policy where the pair is selected based on the possible reduction of the minimum K-cut value when the label for the selected pair is returned fromworkers. After that, we further extend the model and the policy to the case where the workers are unreliable and have different reliability. In the latter case, the action in each stage is to select not only the pair but also the worker to label this pair.

The rest of the paper is organized as follows. In Section 2, we first introduce the problem setup and then provide the Bayesian decision process with reliable workers. In Section 3, we extend the proposed method to the case of unreliable workers. Section 4 provides the simulation studies with both reliable and unreliable workers. In Section 5, we present numerical results on real data. Conclusions and further works are given in Section 6.

2 Bayesian Decision Process with Reliable Workers

We first investigate the problem under the setting with only fully responsible workers. Here, being fully reliable means that the workers judge the similarity between items to the best of their knowledge. However, due to the subjective nature of human perception-based similarity, the labels provided by workers are not necessarily consistent (see Eq. (1) below for a more precise description on our modeling of fully reliable workers). We will extend our study to the setting with unreliable workers (see Section 3).

Suppose there are N items that need to be grouped into K clusters based on their pairwise similarity. We model the true similarity between items i and j (1 ≤ i < j ≤ N) by a latent similarity parameter θij ∈ [0, 1] and a larger θij represents a higher similarity between them. Assuming that the budget for clustering is T, one unit of budget is paid to a worker for each similarity label he or she provides. We model the crowdsourced clustering problem as a multi-stage decision making problem with T stages. In each stage, the decision maker chooses a pair of items (i, j) and assigns them to a worker randomly chosen from the crowd to request a similarity label. We denote by lij the binary similarity label provided by the worker with lij = 1 if the worker thinks i and j are similar and with lij = 0 otherwise. Furthermore, we assume that the number of workers is large enough and θij equals the proportion of the workers who think items i and j are similar. In other words, the label lij returned by a random reliable worker has the following Bernoulli distribution

We assume that θij follows a Beta prior Beta(a0ij , b0ij ) for 1 ≤ i < j ≤ N. Suppose, at stage t, Beta(atij ,btij ) is the posterior distribution for θij and a pair (it, jt) is assigned to a random worker who returns a similarity label litjt . According to (1), the posterior distribution of θij will still be a Beta distribution Beta(at+1 ij , bt+1 ij ) where for 1 ≤ i < j ≤ N,

Next, we will model this crowdsourced labeling process as a Markov decision process (MDP). To do so, we define the state variable at stage t by St = {(atij , btij )}1≤i<j≤N. Note that the conditional distribution of litjt conditioning on St is

After litjt is revealed, St is updated to St+1 and St+1 is different from St only at (aitjt , bitjt ) according to (2). Combined with (2), (3) can be viewed as the state transition probability at state St after a decision (it, jt). This also means that {St}t≥0 is Markovian because St+1 is fully determined by St and litjt . Given this property, it suffices to consider a policy that only depends on St to choose (it, jt). We denote such a policy by a sequence of mappings (π1, ..., πT ) with πt(St) ∈ {(i, j)|1 ≤ i < j ≤ N}.

Given the limited budget, a good policy must choose (it, jt) to collect sufficient information and quickly improve the quality of clustering. To measure the quality of clustering, we construct a similarity graph, which is a weighted, complete, undirected graph G = (V, E, {θij}) where the set of nodes V is the set of items for clustering, the set of edges E consists of all pairs of items, and the edge between i and j is weighted by θij . Given this graph, a classical approach for clustering the nodes is to partition the graph into K disconnected components by removing the edges with as small total weight as possible. This is known as the minimum-weight K-cut problem:

where {C1,C2, ...,CK} forms a partition of V and θij = θji if j < i. Since {θij} is unknown, the clustering at stage t needs to be performed based on E(θij|St) by solving MinCut({E(θij|St)}). We then use MinCut({E(θij|St)}) to measure the quality of clustering at stage t with a smaller value representing better clustering. To obtain a good clustering result after T stages, the budget allocation problem is then formulated as the following dynamic optimization

Problem (5) can be equivalently reformulated as

where R(St, it, jt, litjt )

represents the expected reduction of the total weight of the minimum K-cut after updating the posterior distribution of θitjt according to litjt . Note that St+1 depends on litjt . Eq. (7) can be also interpreted as the expected improvement of the quality of clustering. Hence, (6) is an MDP where the stage-wise reward is R(St, it, jt, litjt ).

However, (6) is difficult to solve optimally due to the curse of dimensionality. Therefore, we aim at a computationally efficient policy with a good performance in practice. A popular class of online learning policy is the knowledge gradient (KG) [Gupta and Miescke, 1996; Frazier et al., 2008], which chooses (it, jt) to maximize E[R(St, it, jt, litjt )|St], or equivalently, to minimize E[MinCut({E(θij|St+1)})|St].

According to (2) and (3), we have {E(θij|St+1)} =

when litjt = 1 and

when litjt = 0. According to (3), the KG policy can be described as

However, as shown in [Chen et al., 2015] for the crowdsourced classification problem, the KG policy is myopic and may keep labeling a few pairs without exploring others. To address this issue, [Chen et al., 2015] proposed the optimistic knowledge gradient (Opt-KG) policy which chooses (it, jt) to maximize the optimistic outcome of stage-wise reward rather than the expected reward. It is shown by [Chen et al., 2015] that the Opt-KG policy outperformed the KG policy because it balances exploration and exploitation better.

Algorithm 1 The Opt-KG policy for crowdsourced clustering with reliable workers

Input: Parameters of prior Beta distributions S0 = {(a0ij , b0ij )}1≤i<j≤N, the budget T, and the number of clusters K.

• 1: for t = 1, ..., T do
• 2: Compute R+ t (i, j) for 1 ≤ i < j ≤ N based on (7) and (8).
• 3: Select the pair of items (it, jt) according to:

and send it to a randomworker.

• 4: Acquire the similarity label litjt ∈ {1, 0}.
• 5: Update St to St+1 according to (2).
• 6: end for

Output: The K clusters {C1, ...,CK} that solve MinCut({E(θij |ST )}) defined by (4) and (3).

Motivated by [Chen et al., 2015], we define the optimistic reward as

and propose the Opt-KG policy for crowdsourced clustering which chooses

where the second equality is from (7) and the fact that MinCut({E(θij|St)}) does not depend on litjt . We formally state the Opt-KG policy in Algorithm 1.

In practice, we may make the Opt-KG policy more timeefficient by utilizing the capability of parallel processing of crowdsourcing. Indeed, in each stage, we can choose the B pairs with the largest R+ t (i, j) and send them to different random workers simultaneously. After receiving the similarity labels from them all, we update the parameters St+1 for the posterior distribution of each θij in a way similar to (2).

3 Bayesian Decision Process with Unreliable Workers

The method proposed in Section 2 requires that all workers are fully reliable. However, unreliable workers do exist in practice who provide noisy labels because of, e.g., not comparing items carefully. It is critical to accurately assess the reliability of each worker in an early stage so that items and budget can flow to more reliable workers. In this section, we show that this can be done by extending our Opt-KG policy.

We assume that there are W heterogeneous workers and introduce a parameter ρw ∈ [0, 1] to represent the w-th worker's reliability. We define ρw as the probability of worker w labeling a pair of items in the same way as a randomly selected fully reliable worker (i.e. labeling to the best of the worker's knowledge). Specifically, if we assign a pair (i, j) to worker w, the label returned, denoted by lijw, has the distribution:

Here, ρw can be also interpreted as the probability that worker w provides the label by flipping the label from a reliable worker. When worker w is fully reliable, we have ρw = 1 and (9) reduces to (1), namely, the randomness of labels is only because of the subjective judgment of worker. Similarly, ρw = 0.5 means worker w labels the pair randomly.

Similar to θij, we assume that each ρw is independently drawn from a Beta prior distribution Beta(c0w , d0w ). Then, given the similarity label lijw = l ∈ {0, 1}, the posterior distribution of θij and ρw is

Unfortunately, the posterior joint distribution for θij and ρw in (10) is no longer the product of Beta distributions. Therefore, after receiving a new label, we cannot update the posterior distribution as a state variable by updating the parameters a0ij , b0ij , c0w , and d0w as in (2). To address this issue, we apply variational approximation based on the moment matching to approximate the posterior distributions of θij and ρw as independent Beta distributions.

Suppose, at stage t, θij and ρw are independent and their posterior distributions are Beta(atij , btij ) and Beta(ctw , dtw ), respectively. (This is true for t = 0.) Let St = {(atij , btij )}1≤i<j≤N and Θt = {(ctw , dtw )}1≤w≤W be the state variables for MDP. After sending (it, jt) to worker wt, we receive a label litjtwt and approximate the posterior distributions for θitjt and ρwt as

for (i, j,w) = (it, jt,wt) and l = litjtwt . Here, the parameters ˜aij(l), ˜bij(l), ˜ cw(l), and ˜ dw(l) are defined as the values that make the distributions of θij and ρw on both sides of (11) have the same first and second moments, known as the moment matching technique. In particular, the moments of the right hand side are functions of ˜aij(l), ˜bij(l), ˜ cw(l), and ˜ dw(l), while the moments of the left hand side are functions of atij , btij , ctw , dtw , and lijw, leading to a system of four equations and four unknown parameters. Hence, ˜aij(l), ˜bij(l), ˜ cw(l), and ˜ dw(l) can be uniquely solved from that system for (i, j,w) = (it, jt,wt) according to lijw = l = 1 or 0. For (i, j,w) ̸= (it, jt,wt), the posteriors of θij and ρw are unchanged.

Applying this approximation in each stage, we are able to represent the state variables for our MDP as St+1 = {(at+1 ij , bt+1 ij )}1≤i<j≤N and Θt+1 = {(ct+1 w , dt+1 w )}1≤w≤W for stage t + 1, where

for 1 ≤ i < j ≤ N, and

Algorithm 2 Bayesian decision process with unreliable workers based on the Opt-KG policy

Input: Parameters of prior Beta distributions {a0ij , b0ij }1≤i<j≤N and {c0w , d0w }1≤w≤W, the budget T , the number of clusters K.

• 1: for t = 1, ..., T do
• 2: Compute R+ t (i, j,w) for 1 ≤ i < j ≤ N and 1 ≤ w ≤ W based on (15) and (16).
• 3: Select the pair of items (it, jt) and the worker wt according to:

and send items (it, jt) to worker wt.

• 4: Acquire the similarity label litjtwt ∈ {1, 0}.
• 5: Update St to St+1 according to (12) and update Θt to Θt+1 according to (13) .

6: end for

Output: The K clusters {C1, ...,CK} that solve MinCut({E(θij |ST )}) defined by (4) and (3).

Defining a policy as a sequence of mappings (π1, ..., πT ) with πt(St, Θt) ∈ {(i, j, w)|1 ≤ i < j ≤ N, 1 ≤ w ≤ W}, the crowdsourced clustering problem with unreliable workers can be approximated by the following MDP similar to (6):

where R(St, Θt, it, jt, wt, litjtwt )

Recall (12), (13) and (3). We have {E(θij|St+1)} = U t (it, jt, wt, litjtwt ) ≜ {utij (l)} where l = litjtwt and

Similar to (8), we define the optimistic reward as

and propose the Opt-KG policy for the setting with unreliable workers as

where the second equality is from (15). We formally state the Opt-KG policy in Algorithm 2. Similar to Algorithm 1, in Algorithm 2, we also can choose B different (i, j, w)'s with the largest R+ t (i, j,w) and receive B labels in each stage in order to improve the time efficiency.

4 Simulation Studies

In this section, we conduct the numerical experiments on the simulated data to show the performance of the proposed budget allocation policies in terms of their (a) labeling frequency and (b) clustering accuracy. Here, (a) means the distribution of the budget over item pairs (and workers). To measure (b), we generate the data in K clusters, denoted by C1, . . . , CK. And the clustering accuracy is defined as maxσ ∑Kk=1 rkσ(k) N , where rkl is the number of items in Ck assigned to cluster l and σ : {1, 2, . . . ,K} → {1, 2, . . . ,K} is a permutation of {1, 2, . . . ,K}. Besides, we also use the normalized mutual information (NMI) score to evaluate the clustering performance. We adopt the uniform prior Beta(1, 1) for each θij and the prior Beta(4, 1) for each ρw unless otherwise specified. We utilize the graph partitioning algorithm [Hespanha, 2004] based on spectral factorization to solve the Min-K-Cut problem. We compare our method (Opt-KG) with the knowledge gradient (KG) and random assignment (Random).

4.1 Simulation with ReliableWorkers

In this section, we assume all workers are fully reliable. We first investigate the labeling frequency. We generate 12 items that form three clusters {C1,C2,C3}. More specifically, the first four items are fromC1, the next four items are fromC2, and the last four items are from C3. We assume that the total budget T is 200 and the similarity parameter θij between items in the same cluster is generated from Beta(as, bs), and θij between items in different clusters is generated from Beta(ad, bd), where (ad, bd) = (bs, as). We consider three settings: (as, bs) = (10, 1), (4, 1), (5, 2). The labeling frequency for each setting is plotted in Figure 1. We note that each box represents one pair of items and the warmer color correponds to a higher percentage of the budget spent on labeling that pair. According to our setting, the difficulty of clustering increases from Figure 1(a) to 1(b) or 1(c) because the expectation of θij within clusters (i.e. as/(as + bs)) become closer to the expectation value of θij between clusters (i.e. bs/(as + bs)). We can observe from Figure 1 that, when as and bs are very different (clustering is easy), the labeling frequency is higher on the pairs from different clusters, and when as and bs are close (clustering is difficult), the labeling frequency of the pairs from the same cluster becomes higher.

Next, we investigate the robustness of the proposed method with the uniform prior distribution for θij by varying the true generating distribution of θij. Here, we use the same set of 12 items as described above. We plot the clustering accuracy for different levels of budget T = 10, 20, ..., 200 in Figure 2. For better visualization, we omit the standard deviation on the figures as the standard deviations are relatively small. As we can see, when as and bs become closer, the proposed method needs more budget to obtain a high clustering accuracy, which is consistent with the intuition.

Next, we compare the performance of the proposed OptKG policy with the KG policy and the random sampling policy (select item pairs randomly at every stage). We choose the simulated data with a larger size and conduct each policy with a mini-batch of size B = 100 and a total budget of T = 25. We simulate 30 items in three clusters and generate θij between the items in the same cluster from Beta(5, 2), and generate θij between the items in different clusters from Beta(2, 5). We report the clustering accuracy and NMI obtained by each policy for T = 1, 3, 5, ..., 25 in Figure 3. This figure shows that our Opt-KG policy increases both performance metrics more rapidly as the budget is consumed.

4.2 Simulation with UnreliableWorkers

In this section, we consider the simulation studies with unreliable workers. First, we investigate the sensitivity of the proposed method to the workers' reliability. We fix ten workers with reliability ρ = (ρ1, ρ2, ..., ρ10) = (0.55, 0.60, ..., 1). We simulate 12 items in 3 clusters and generate θij within clusters from Beta(4,1) and θij between clusters from Beta(1,4). We choose the total budget T = 400. Figure 4 reports the average labeling frequency over these ten workers, which shows that our policy will detect the reliable workers and the workers with higher reliability are assigned with more items to label. Such assignments efficiently increase the performance of clustering and save the budget.

Next, we investigate the robustness of the proposed method with the prior Beta(4, 1) for ρw by varying the true generating distribution of ρw. We generate θij and items as above and consider five workers with ρk generated from Beta(8,1), Beta(11,2) or Beta(3,1). Figure 5 displays how the clustering accuracy varies with the level of budget (T = 60, 120, ..., 600) in our Opt-KG policy when using Beta(4, 1)

as the prior for ρw and when using the true generating distributions of ρw as the prior. As we can see, the prior Beta(4, 1) leads to a better clustering result than the true distributions.

We compare the performance of the proposed Opt-KG policy with the KG policy and the random sampling policy with a total budget of T = 50 and a batch size B = 300. We simulate 50 items in 5 clusters and generate θij within clusters from Beta(5, 2) and θij between clusters from Beta(2, 5). We consider five workers with reliability ρ = (ρ1, ρ2, ..., ρ5) = (0.70, 0.75, ..., 0.90). We report the clustering accuracy and NMI obtained by each policy for T = 5, 10, ..., 50 in Figure 6. According to Figure 6, our Opt-KG policy increases the clustering quality fastest as the budget is consumed.

5 Experiment with Real Data

We compare different policies for clustering four datasets [Dua and Graff, 2017; Bagnall et al., 2019]: soybean, olive oil, meat and iris. In each dataset, we calculate the Euclidean distance between each pair of instances and obtain θij through a linear mapping based on the principle that pairs of instances with smaller distances have higher similarity. For instances i and j from the same cluster, θij ranges from 0.7 to 0.9. For instances from different clusters, θij ranges from 0.1 to 0.3. We first consider the reliable workers setting. We generate the labels from a random worker using (1) with the true θij. The uniform prior Beta(1,1) is used in the Opt-KG policy with the total budget T = 10, the batch size B = 200 for soybean and olive oil and B = 300 for meat and iris. We run each policy 10 times and report the averaged clustering accuracies under different budget levels (T = 1, 4, 7, 10) in Table 1. As we can see, our Opt-KG policy has the best performance. After only seven stages, the proposed method based on the Opt-KG policy can attain a high clustering accuracy.

Next, we consider the setting with unreliable workers. We consider five workers with reliability ρ = (ρ1, ρ2, ..., ρ5) = (0.70, 0.75, ..., 0.90) and generate labels according to (9). We choose the uniform prior Beta(1, 1) for θij and choose Beta(4, 1) as the prior for ρw in the Opt-KG policy with T = 10, B = 400 for soybean and olive oil and B = 1000 for meat and iris. From Table 1 we can see that the Opt-KG policy is superior to the KG policy and the random sampling policy under the setting with unreliable workers.

6 Conclusions

In this paper, we propose an online policy for the budget allocation problem in crowdsourced clustering. We transform the clustering problem into a graph partition problem based on the minimum-weight K-cut problem. We introduce the priors of the similarity parameters for item pairs and workers' reliability and then model the problem as a Bayesian Markov decision process. We develop a computationally efficient Opt-KG policy to approximately solve the MDP for both cases of reliable and unreliable workers. The experimental studies show that the proposed method achieves a good performance.

This paper uses Min-K-Cut function to solve the graph partition problem. In future work, it will be interesting to study the budget allocation problem through other graph partition methods. When only one label (or a batch of labels) is obtained at one stage, how to solve the optimization problem at the next stage locally and faster is challenging. Another interesting extension is to consider the dynamic pricing strategy. A novel pricing scheme instead of equal cost can motivate workers to provide labels with higher quality.

Acknowledgments

Xiaozhou Wang and Weidong Liu are supported by National Program on Key Basic Research Project (973 Program, 2018AAA0100704), NSFC Grant No. 11825104. Xi Chen is supported by the NSF Grant via IIS-1845444 and the Bloomberg Data Science Research Grant.