{'fraction_non_alphanumeric': 0.04398262193756439, 'fraction_numerical': 0.01415326734447082, 'mean_word_length': 4.393236714975846, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Online Crowdsourcing

With the success of modern internet based platform, such as Amazon Mechanical Turk, it is now normal to collect a large number of hand labeled samples from non-experts. The Dawid- Skene algorithm, which is based on Expectation- Maximization update, has been widely used for inferring the true labels from noisy crowdsourced labels. However, Dawid-Skene scheme requires all the data to perform each EM iteration, and can be infeasible for streaming data or large scale data. In this paper, we provide an online version of Dawid- Skene algorithm that only requires one data frame for each iteration. Further, we prove that under mild conditions, the online Dawid-Skene scheme with projection converges to a stationary point of the marginal log-likelihood of the observed data. Our experiments demonstrate that the online Dawid- Skene scheme achieves state of the art performance comparing with other methods based on the Dawid- Skene scheme.


Introduction
Many fundamental tasks in machine learning, such as classification, detection, require a large number of hand labeled samples (items) in practice. With the rise of online platform such as Amazon Mechanical Turk, it becomes possible to collect vast amount of labels with the help of enormous man power on the Internet. However, the labels obtained in this way are often unreliable and not accurate enough to serve as training samples, due to the non-expert online workers and the anonymous nature of the platform. One straight forward approach is to collect multiple labels for each item and use the label who has the most workers' acceptance (Majority Voting). But, can we do better in crowdsourcing to estimate the true labels from the crowdsourced noisy labels?
Observing that different workers may have different talents, Dawid and Skene [1979] develop a maximum likelihood approach based on the idea that each worker has a confusion matrix. More precisely, suppose that the items can be divided into k classes, and assume that each worker is associated with a k × k confusion matrix, where the (l, c)-th entry represents the probability that a randomly chosen item in class l is labeled as class g by the worker. The true labels and the worker confusion matrices are jointly estimated by maximizing the marginal log-likelihood of the observed labels, where the unobserved true labels are treated as hidden variables. However, the value of the likelihood is extremely difficult to calculate, as the number of terms, whose sum is the likelihood of the observed labels, is exponentially growing with respect to the number of items. Instead, the worker confusion matrices are estimated iteratively by a Expectation-Maximization (EM) procedure McLachlan and Krishnan [2007].
Unfortunately, the memory consumption of Dawid-Skene scheme increases linearly with the size of data, as the intrinsic structure of this methods requires to access all the data in each iteration. Due to the same reason, Dawid-Skene algorithm has difficulty when the data frame is supplied to the system indefinitely. Notice that in reality, it is highly possible that we can only collect worker labels in an indefinite manner. For example, different worker may have different labeling speed and we may want to add more items to some classes afterwards. Therefore, it is of great interests to derive an online version of Dawid-Skene algorithm, which can still achieve comparable accuracy.
In this paper, we provide an online version of Dawid-Skene algorithm, which requires only one data frame for each iteration. For the ease of presentation and analysis, we consider the simple model, i.e., at each iteration, one item and its corresponding labels are supplied to the online algorithm. This simple setup can be easily generalized to more general cases. We show that, under some non-restrictive conditions, the online Dawid-Skene scheme converges to a stationary point of the marginal log-likelihood of the observed labels. Notice that, since the marginal log-likelihood is non-convex, the original Dawid-Skene scheme only guarantees to converge to a stationary point as well.
The rest of the paper is organized as follows: in Section 2, we compare and contrast our work with related literature. In Section 3, we introduce the notations and then formulate the crowdsourcing problem rigorously. Next, in Section 4, the mathematical form of Dawid-Skene scheme is revisited. Then, the online algorithm is presented in Section 5. After that, theoretical analysis of online Dawid-Skene scheme is included in Section 6. Then, empirical performance is investigated in Section 7. Finally, the conclusion is in Section 8.
In the existing literature, depending on different practical situations, there are many methods [Liu et al., 2012;Ghosh et al., 2011;Karger et al., 2013Karger et al., , 2014Dalvi et al., 2013;Zhang et al., 2014] developed and improved based on the Dawid-Skene algorithm [Dawid and Skene, 1979]. In particular, when we only have two classes, Ghosh et al. [2011] propose a method using Singular Value Decomposition to moderate online content given crowdsourced user ratings. Based on the assumption that each worker labels all items, Ghosh et al. [2011] show that if the number of observations increases, their algorithm can infer the quality of contributions with error that converges to zero. Dalvi et al. [2013] relax the assumption that the graph between worker and item is either random or complete and propose another SVD-based algorithm which considers arbitrary worker-item graph. Also, under the one coin model setting and considering random regular worker-item graph, Karger et al. [2014] uses an iterative approach to infer the true binary labels and later generalize it to multi-class labeling tasks in Karger et al. [2013]. Focusing on learning a classifier, Chen et al. [2013]; Raykar et al.
[2010]; Liu et al. [2012] proposes a Bayesian algorithm by imposing a prior distribution on the experts. By assuming that labels are generated by a probability distribution over workers, items, and labels Zhou et al. [2012 propose an algorithm by minimizing the Kullback-Leibler (KL) divergence between the probability distribution and the unknown truth. This method can also output item difficulty and worker expertise as by-products.  observe that it is difficult to distinguish between two adjacent ordinal classes while distinguishing between two far-away classes is much easier and they propose an algorithm based on minimax conditional entropy. Initialization is very important for Dawid-Skene algorithm, as it aims to maximize a nonconcave function. Addressing this issue, Zhang et al. [2014] propose to initialize Dawid-Skene algorithm using spectral methods and show that the resulting algorithm has a high probability to converge to the global optimum.
Our work is motivated by stochastic approximation methods and variants of online EM algorithms [Cappé and Moulines, 2008;Sato and Ishii, 2000;Delyon, 2000;Zhang and Liang, 2008;Kushner and Yin, 1997]. In particular, Cappé and Moulines [2008] replace the Expectation step by a stochastic approximation step to derive an online EM algorithm for latent data models, while our online algorithms can be seen as replacing the Maximization step by a stochastic approximation step. Further, Cappé and Moulines [2008] prove that, under some conditions, the online EM converges to a stationary points of the KL divergence between the marginal distribution of the observation and the model distribution, while we prove that our online Dawid-Skene scheme convergence to a stationary point of the the marginal log-likelihood functions. Notice our result directly connects to the objective function that we want to maximize. Sato and Ishii [2000] propose an online EM algorithm for Normalized Gaussian Network by introducing a discount factor to forget the previous incorrect estimated parameters. Later, Sato [2000] shows that if the probability distributions for both observed and unobserved data belong to an exponential family, then their algorithm converges to the corresponding stationary point of the marginal log-likelihood function. But, this is not applicable to our case, as under the crowdsourcing setting, the joint probability distribution does not belong to the exponential family defined in Sato [2000].

Notation
In this paper, given an integer a, we use [a] to denote the integer set {1, 2, · · · , a}. 3-mode tensors are denoted by upper case calligraphic letters (e.g. C, S ∈ R m×k×k ); matrices are denoted by upper case boldface letters (e.g. Z); vectors are denoted by lower case boldface letters (e.g. z); and scalars are denoted by lower case letters (e.g. z). Given a 3-mode tensor C ∈ R m×k×k , we use c ilg to denote the (i, l, g)-th entry of C. Given a matrix Z, we use z i to denote its i-th column, and z ij to denote its (i, j)-th entry. Given a vector z, its i-th element is denoted by z i . Next, sets are denoted by blackboard bold characters (e.g. R, D, O,) and functions are denoted by Fraktur characters (e.g. F, H, V, T). In particular, we use 1 to denote the indicator function, E to denote the Expectation for some random variable and Π to denote a projection mapping.

Estimate true labels form crowds
Throughout this paper, there are m workers, n items (objects) belonging to k classes (groups). We use y j to denote the true labels of item j ∈ [n] and y to denote the true labels for all items. Denote by a scalar z ij ∈ R the label that worker i assigns to item j. When the assigned label is g ∈ [k], we write z ij = g. If item j is not labeled by worker i, we write z ij = 0. Thus, we use the vector z j to denote all the worker labels corresponding to the jth item. Further more, we use the matrix Z to denote all the labels, whose j-th column is z j and (i, j)-th entry is z ij . Our target is to estimate the true labels y from the worker labels Z.

Dawid-Skene Scheme
In Dawid-Skene Scheme, assuming that the probability that worker i labels an item in class l as class g is independent of any particular chosen item, i.e., it is a constant over j ∈ [n]. Let us denote the constant probability by c ilg . Further, we restrict c ilg to be strictly positive, i.e. c ilg ∈ (0, 1). Then, the tensor C, whose (i, l, g)-th element is c ilg , is called the user confusion tensor. The joint likelihood of true labels y and observed labels Z , as a function of C, can be written as (1) Then, the maximum likelihood estimates of the unknown true label y can be obtained by maximizing the marginal loglikelihood function of the observed worker labels Then, we can find the maximum likelihood estimate of the marginal log-likelihood (2) using the EM algorithm: E Step: Calculate the expected value of the log-likelihood function, with respect to the conditional distribution of y given Z under the current estimate ofĈ: where for all j ∈ [n], l ∈ [k], Step: Find the estimateĈ that maximizes the function Q(C|Ĉ): . (6)

Online Dawid-Skene Scheme
The basic idea of the proposed method is to replace the Maximization step by a stochastic approximation step, while keeping the Expectation step unchanged. More precisely, set Then, the Maximization step of Dawid-Skene Scheme (6) can be rewritten asĉ .
Then, we use S to denote the tensor whose (i, l, g)-th element is s ilg . With tensor S and the user confusion tensor C. The E step of Dawid-Skene scheme can be seen as calculating S based on C. Correspondingly, the M step can be seen as calculating C based on S.
In order to define the online algorithm rigorously, we need to make some assumptions on how the labels are supplied to the online algorithm. One obvious choice is that we select one of the n objects randomly and supply its corresponding labels to the online algorithm at each iteration. More precisely, we make the following assumption.
Assumption 1. Give n items and their corresponding labels Z, at the beginning of each iteration, an item i ∈ [n] is uniformly selected and its corresponding labels z i are supplied to the online algorithm. (1) is to simplify presentation and analysis. The online Dawid-Skene Scheme (7) and (8) can be easily generalized to more general and practical cases.

Remark: Assumption
Let C(0) be initialized when we do not observe any labels and C(j) denote the confusion tensor after the online algorithm have received the labels of j-th object, i.e. after seeing z j . Thus, the corresponding probability label for the j-th ob- In online Dawid-Skene Scheme, s ilg (j) at iteration j is calculated by the following stochastic approximation step, with η j chosen to satisfy the following condition

Convergence Analysis
In this section, we show that under mild conditions, the online Dawid-Skene scheme with projection converges to a stationary point of the marginal log-likelihood (2).

Preliminary
In this subsection, we define some functions which capture the key update property of Dawid-Skene scheme and online Dawid-Skene scheme. Then, we analyse the online algorithm by investigating these functions. At iteration j, the M step can be seen as calculating C based on S. For online Dawid-Skene scheme, without loss of generality, we choose 0 < s ilg (0) < 1 for all i ∈ [m], l ∈ [k], g ∈ [k], then it can be easily shown that 0 < s ilg (i) < 1 at any iteration i. So, for convenience, we define D = (0, 1) m×k×k .
Then, given S ∈ D, we definie the function G : D → D as After that, suppose we have n items in total and their corresponding worker labels Z, we define the function T : where the (i, l, g)-th entry of W is w ilg = 1 n n j=1 P (y j = l|G(S), z j )1(z ij = g).

Main Results
The function T defined in (9) reveals how Dawid-Skene Scheme updates the confusion matrix C. We make the following assumptions on T, under which we will show that the online algorithm can convergence to a stationary point of the marginal log-likelihood function. 4. for all S / ∈ K, ∇V 2 (S), T(S) < 0.

Remark:
• Assumption (2) is based on the existence of two Lyapunov functions, i.e. V 1 and V 2 . The existence of a Lyapunov is a standard condition to prove the asymptotic stability in stochastic approximation theory. • The existence of a Lyapunov function is usually theoretically non-restrictive, as is critical to the convergence of the trajectories of the corresponding vector field, see Delyon [2000Delyon [ , 1996; Hahn and Baartz [1967] for more information. For Dawid-Skene Scheme, we mainly focus on the open set D, as the joint distribution is not defined on the boundary of D. But, this provides difficulties for analyzing the the asymptotic properties, as C(j) may converge to the boundary. The naive way to avoid this difficulty is to assume that the stationary points lie inside a compact subset of D. A more elegant projection procedure is proposed in Chen et al. [1987]; Delyon [2000]. Thus, in the following analysis, we focus on the projected version of (7). Considering the projection procedure in Delyon [2000], we assume that there is a sequence of compact sets K t , t = 0, 1, 2, · · · , whose union is D. Then, we begin with t = 1, at each iteration j, S(j) is out of K t , its value is reset arbitrarily in K 0 and we increase t by one. Mathematically, we consider the following algorithm where S ′ is chosen arbitrarily from K 0 and we use the following notation to denote the projected version of Dawid-Skene Scheme: Proof. We divide the proof into the following three steps: Step1: in this step, we prove that all the points in O are stationary points of the marginal log-likelihood (2). To do this, we first show that Dawid-Skene Scheme converges to one of the zeroes of the function T. Notice that each Expectation and Maximization step is equivalent to the following iterative steps 1. Give C, calculate S, where the (i, l, g)-th entry of S is 2. Given S, calculate C by Let S * be one of the points to which Dawid-Skene Scheme converges, i.e. S * will stay unchanged after updating using iterative steps (11) and (12). So, we have Writing (13) Step2: in this step, we show that the online Dawid-Skene Scheme can be seen as using stochastic approximation methods to find the zeroes of T . Notice that, at iteration j, for all i ∈ [m], l ∈ [k], g ∈ [k], {s ilg (j)} are updated based on the value P (y j = l|C(j − 1), z j )1(z ij = g), which can be seen as a function of (C(j − 1), z j ). Thus, we define the function F(C, z) : where the (i, l, g)-th entry of A is .
Step3: in this step, we show that the online Dawid-Skene Scheme converges to a stationary point of of the marginal loglikelihood (2). Given C ∈ D, since the function F is bounded for all z ∈ {z 1 , z 2 , · · · , z n }. Thus, if z is selected uniformly from {z 1 , z 2 , · · · , z n }, we have for any compact setK ⊂ D Under assumption (2) and (1), by Theorem 12 in Delyon [2000] (or equivalently stochastic approximation theories in Zhang and Liang [2008]; Kushner and Yin [1997]), we have S(j) → S * for some S * ∈ O such that T(S * ) = 0.

Remark:
• Sato [2000] shows that if the distribution P (x, z|θ) for both observed data x and missing data z belongs to the following exponential family where θ denotes the parameters of interests, R(x, z) denote the set of sufficient statistics and M(θ) is the normalization factor defined by Then, the online EM algorithm converges to a stationary point of the corresponding marginal log-likelihood function. Notice this result does not apply to our case, as for Dawid-Skene Scheme, the probability distribution is not of the form (16). Comparing the proofs, Sato [2000] treats the online algorithm as a stochastic gradient method with the inverse of the Fisher information matrix being the coefficient matrix, while we prove our results by finding the zeros of the function T. • Alternatively, one can use the results provided in Cappé and Moulines [2008] to show that the online Dawid-Skene Scheme converges to a stationary point of the KL divergence between the induced partial distribution P (y|C) and true distributionP for y, while our results directly connects to the marginal log-likelihood function that Dawid-Skene Scheme tries to maximize. • Notice that due to nonconvexity, the best Dawid-Skene Scheme can hope to achieve is to converge to a stationary point of the marginal log-likelihood (2). Under Assumptions 1 and 2, our result means that the online Dawid-Skene Scheme is as good as the original one.

Experiment
In this section, we investigate experimentally the performance and efficiency of the proposed online algorithm (7). The experiments are based on three datasets: one binary task and two multi-class tasks. The binary task is to recognize textual entailment Snow et al. [2008] (RTE). Multi-class tasks include labeling the images of 4 breads dogs from Ima-geNet Zhou et al. [2012] (DOG) and judging the relevance of query-URL pairs with a 5-level rating scale Zhou et al. [2012] (WEB). The characteristics of the data sets are summarized in

Step Size
Decreasing η j slowly with respect to j means the online algorithm learns at a fast rate and also means that it forgets the past inaccurate estimates at high speed. On the contrary,   Table 1: Performance comparison with other methods rapid decreasing of η j means the online scheme forgets the past slowly and learns from new information at a low rate. Thus, the speed of decreasing the learning rate η j is a tradeoff between learning and forgetting. Next, we investigate how to choose the learning rate in order to get the most accurate results. In our experiment, two online algorithms corresponding to two set of step sizes (learning rate) satisfying Condition (8) are considered. Specifically, one set of step sizes are chosen to be decreasing linearly with respect to the number of iterations and the corresponding online algorithm is referred as online1. The other set of step sizes are chosen to be decreasing slower than linear with respect to the number of iterations and we call the corresponding online scheme online2. Selecting two tunable variable a, b ∈ R, the algorithm online1 and online2 are summarized in the following: • Online1: η j = 1 aj+b . • Online2: η j = b j a with 0.5 < a < 1. Next, we investigate how the stability and the accuracy can be influenced by different tunable variable a, b ∈ R on the data set WEB. The reason to choose the WEB data set is because it is relatively more complicated and has more samples, which makes the online algorithm more sensitive with respect to the tunable variables.
The experiment results are illustrated in Figure 1. The best error rate that online1 can get is 14.21 when a = 2, b = 1.5 and online2's best record is 14.32 when a = 0.99, b = 0.4. For online1, the lowest error rate is achieved at a = 2, which means that both learning too fast or too slow will hurt the performance. For online2, when the step size decreases too slow, i.e. a = 0.75, online2 have the worst error rate. Morever, on-line2 can get smaller error rate when a is closer to 1, which suggests that decreasing the learning rate linearly might be a good choice.

Performace Comparison
Comparison with Dawid-Skene Scheme: we compare the convergence rate with respect to the number of epochs between online Dawid-Skene Scheme and the original version. Both algorithms starts from the same initialization. The comparison results are shown in Figure 2. The convergence rates between online online Dawid-Skene Scheme and the original one are comparable: both methods will converge after several epochs. For performance, the online Dawid-Skene Scheme works surprisingly well. Both online1 and online2 outperforms the Dawid-Skene Scheme on data sets RTE and WEB. On data set DOG, online2 is slightly worse than Dawid-Skene Scheme and online1 achieves the same error rate.
Comparison with other methods: we compare online1 and online2 with other methods which are also based on the generative model of Dawid-Skene. Specifically we compare online1, online2 and Dawid-Skene initialized by majority voting, majority voting method, Dawid-Skene scheme initialized by spectral method proposed by Zhang et al. [2014] (referred as Opt-Dawid-Skene), the multi-class labeling algorithm proposed by Karger et al. [2013] (referred as KOS). The results are summarized in table (1) and online Dawid-Skene scheme achieves state of the art results.