Cost-efficient Crowdsourcing for Span-based Sequence Labeling:Worker Selection and Data Augmentation (2024)

Abstract: “This paper introduces a novel crowdsourcing worker selection algorithm, enhancing annotationquality and reducing costs. Unlike previous studies targeting simpler tasks, this study con-tends with the complexities of label interdependencies in sequence labeling. The proposedalgorithm utilizes a Combinatorial Multi-Armed Bandit (CMAB) approach for worker selec-tion, and a cost-effective human feedback mechanism. The challenge of dealing with imbal-anced and small-scale datasets, which hinders offline simulation of worker selection, is tack-led using an innovative data augmentation method termed shifting, expanding, and shrink-ing (SES). Rigorous testing on CoNLL 2003 NER and Chinese OEI datasets showcased thealgorithm’s efficiency, with an increase in F1 score up to 100.04% of the expert-only base-line, alongside cost savings up to 65.97%. The paper also encompasses a dataset-independenttest emulating annotation evaluation through a Bernoulli distribution, which still led to animpressive 97.56% F1 score of the expert baseline and 59.88% cost savings. Furthermore,our approach can be seamlessly integrated into Reinforcement Learning from Human Feed-back (RLHF) systems, offering a cost-effective solution for obtaining human feedback. All re-sources, including source code and datasets, are available to the broader research community athttps://github.com/blcuicall/nlp-crowdsourcing.”

## introduction crowdsourcing, the practice of obtaining labeled data from a multitude of contributors @xcite , has emerged as a pivotal tool in data collection for deep learning models. it offers a cost-effective alternative to expert labeling, making it especially valuable in today's data-driven research landscape @xcite . while its application spans various domains, from image labeling to text classification @xcite , this paper narrows its focus on span-based sequence labeling tasks, which assign categorical labels to individual words within a sentence @xcite . notable examples of such tasks include named entity recognition (ner) and opinion expression identification (oei) @xcite . the inherent complexity of sequence labeling lies in the interdependencies of labels within a sequence. unlike simpler tasks where labels are independent, sequence labeling requires contextual understanding, making it inherently more challenging @xcite . consequently, annotations from crowd workers, who might not possess the expertise of trained annotators, often exhibit reduced accuracy. this underscores the imperative to enhance annotation quality, a challenge that this study addresses. a significant motivation driving this research is the potential application of a mixed feedback mechanism in reinforcement learning from human feedback (rlhf) systems. rlhf systems traditionally rely heavily on expert feedback, which, while accurate, is expensive and often not scalable @xcite . by integrating feedback from both experts and aggregated crowd workers, we can achieve a balance between accuracy and cost. this hybrid approach not only maintains the quality of feedback but also significantly reduces the financial burden, making rlhf systems more accessible and scalable. historically, research in this domain has concentrated on annotation aggregation @xcite @xcite , employing methods post data collection. however, given the varied skill levels among crowd workers, a proactive approach that identifies and leverages the most accurate workers during the data collection phase can significantly enhance data quality. termed as online worker selection, this strategy involves iterative allocation of a set budget across a pool of workers to optimize annotation quality @xcite . this dynamic process grapples with the uncertainty of worker skill levels, necessitating a balance between exploring new workers and exploiting currently identified proficient ones. in the context of sequence labeling, traditional bandit-based algorithms @xcite fall short due to the intricacies introduced by label dependencies. these intricacies manifest challenges in both annotation evaluation and aggregation. to address the evaluation challenge, this study employs the span-level f 1 score @xcite , a widely recognized metric, as the feedback signal in the worker selection process. the core challenge here is the accurate computation of the f 1 score in the absence of expert annotations as a reference. the objective is to minimize reliance on costly expert annotations. for aggregation, while the majority voting method is employed for its simplicity and effectiveness, its reliability can be compromised when faced with divergent annotations from different annotators. the overarching goal of this research is to maximize the quality of annotations while minimizing costs. this involves strategically replacing expert ground truth labels with aggregated crowd-sourced labels, ensuring that the overall f 1 score remains high. such replacements are made only when there's a high level of agreement among crowd workers, indicating that expert evaluation might be redundant for that particular sequence. the proposed worker selection algorithm, as illustrated in figure 1 , adopts an iterative approach: tasks are assigned to a subset of workers, their annotations are evaluated, and the resulting scores inform worker selection in subsequent rounds. however, real-world datasets present challenges due to their imbalanced nature and limited scale @xcite . addressing these challenges, this paper introduces a data augmentation method tailored for span-based sequence labeling datasets. this method, designed to emulate potential human annotation errors, ensures that aggregated annotations remain meaningful. three specific modifications, namely shifting, expanding, and shrinking, are applied to expert annotations, c c l 2 0 2 4 generating a spectrum of potential human annotations. this augmentation addresses dataset limitations, facilitating the offline evaluation of worker selection algorithms. in summary, this paper's contributions are manifold: ## related work many studies @xcite @xcite have used crowdsourcing for its efficiency and scalability. however, crowdsourcing suffers from the diversity of crowd workers' expertise and effort levels that are hardly measurable to task requesters. different approaches to improving the quality of collected data have been proposed and studied. for span-based sequence labeling tasks, prior studies mainly focus on annotation aggregation. rodrigues et al. (2014) proposed crf-ma, a crf-based model with an assumption that only one worker is correct for any label. hmmcrowd from nguyen et al. (2017) outperforms crf-ma, but the effect of sequential dependencies is not taken into account. simpson and gurevych (2019) uses a fully bayesian approach bsc which is proved to be more effective in handling noise in crowdsourced data. aggregation methods are used after the data collection process completes. but we aim to assure data quality and reduce cost during collecting. to this end, we focus on worker selection in our paper. in online worker selection, we need to balance between exploring new workers and exploiting observed good workers. this exploration-exploitation tradeoff is extensively studied in the bandit literature @xcite . in practice, we usually employ multiple crowd workers at the same time to finish the tasks more effectively. the combinatorial multi-armed bandit (cmab) @xcite models this circumstance. @xcite and @xcite reformulate the problem as a bounded knapsack problem (bkp) and address it with the b-kube @xcite algorithm. @xcite introduce empirical entropy as the metric in cmab and minimize the cumulative entropy with upper confidence bound (ucb) based algorithm. @xcite consider the scalability of worker selection on large-scale crowdsourcing systems. these studies propose different methods under the cmab settings, but on more complex span-based sequence labeling tasks there exists no discussion. we present the study of worker selection with cmab on span-based sequence labeling tasks and show that our work performs well on the quality and efficiency of data collection. ## methodology consider an online crowdsourcing system that can reach out to a group of crowd workers @xmath0, w 2 , . . . , w n }. the workers are required to provide sequential annotations to a set of sentences @xmath1, s 2 , . . . , s m }. more specifically, a worker annotates a sentence by assigning a tag from a finite possible tag set c (e.g., a set of bio tags @xcite ) to each word. an annotation on sentence s i by worker w j is a tag sequence a @xmath2. . . a k . . . a l where a @xmath3. we assume that every sentence is annotated by k different workers independently. we define a task as the process of annotating one entire sentence, and hence there are in total km tasks. we seek to acquire an annotated dataset in which the average f 1 score of a ij is maximized. if we know which workers give the best annotations a priori, we can simply ask these workers to finish all the tasks. however, such information is unavailable in practice, and we aim to design an algorithm that learns the best workers throughout the crowdsourcing process. ## conclusion in this study, we introduced a cmab-based worker selection strategy tailored for span-based sequence labeling tasks, leveraging the span-level f 1 with exp.+mv as a feedback mechanism. to address the challenges posed by unbalanced and limited real datasets, we innovated a data augmentation method. this technique not only facilitates offline simulation but also mirrors the genuine annotation behaviors of workers closely. our empirical evaluations underscore the efficacy of the proposed method. on the chinese oei dataset, our approach achieved an impressive 99.47% f 1 score, translating to a substantial 47.19% reduction in expert costs. similarly, on the conll 2003 dataset, we observed a remarkable 100.04% f 1 score, with savings of up to 65.97% in expert costs, both benchmarks set against expert-evaluation-only baselines. furthermore, our method demonstrated its robustness with a 94.86% f 1 score and a 65.97% reduction in expert costs on a data-free simulator. our approach also boosts ml model performance, optimizing both accuracy and cost. algorithm 1 the worker selection algorithm with the expert+mv metric. t j ← 1 3: t ← |w | 4: while unannotated sentences exist do 5: t ← t + 1 6: select w t ⊂ w based on certain criterion (e.g., (6), (7)) 7: split w t into several disjoint subsets {w t1 , . . . , w ti , . . . , w tn }, each containing k workers 8: for all w ti do 9: let each w @xmath4: if κ(a i ) > τ then 11: update t j and μj with f mv 1 (a ij (t)) 12: else 13: update t i and μj with f exp 1 (a ij (t)) 14: end if 15: the main proof follows the proof of theorem 1 in @xcite . the key contribution here is that we need to specify that the evaluation signal (generated by majority voting) is a generalized linear model of workers' true reward signal (generated by expert/oracle). to this end, we utilize the following form of the chernoff bound which applies for any random variables with bounded support. for the purpose of our discussion, let x @xmath5, 1} be a binary random variable, where x @xmath6, and x @xmath7. define @xmath8. we aim to approximate p mv , which is the probability that the majority of the n workers provide the correct estimate. we apply the chernoff bound in lemma 1 to p mv . we can compute algorithm 2 the annotation selection algorithm. 1: for each worker w @xmath9, maintain (1)a variable φj as the average f 1 score of the selected annotations by w j so far, (2)a set a j of selected annotations by w j 2: generate all possible annotations a p 1 on s 1 ∈ s, calculate f exp 1 (a 1k ) for each a 1k ∈ a p 1 3: for each @xmath10, initialize φj with the f exp 1 (a 1k ) closest to φj , and append the a 1k to a j 4: for all s @xmath11 update φj with the maximal f exp 1 (a ik ) less than φj , and append a ik to a j 9: else 10: update φj with the minimal f exp 1 (a ik ) greater than φj , and append a ik to a j 11: