Title: MAX-MIG: AN INFORMATION THEORETIC APPROACH FOR JOINT LEARNING FROM CROWDS

Abstract: Eliciting labels from crowds is a potential way to obtain large labeled data. Despite a variety of methods developed for learning from crowds, a key challenge remains unsolved: learning from crowds without knowing the information structure among the crowds a priori, when some people of the crowds make highly correlated mistakes and some of them label effortlessly (e.g. randomly). We propose an information theoretic approach, Max-MIG, for joint learning from crowds, with a common assumption: the crowdsourced labels and the data are independent conditioning on the ground truth. Max-MIG simultaneously aggregates the crowdsourced labels and learns an accurate data classifier. Furthermore, we devise an accurate data-crowds forecaster that employs both the data and the crowdsourced labels to forecast the ground truth. To the best of our knowledge, this is the first algorithm that solves the aforementioned challenge of learning from crowds. In addition to the theoretical validation, we also empirically show that our algorithm achieves the new state-of-the-art results in most settings, including the real-world data, and is the first algorithm that is robust to various information structures.

1. INTRODUCTION:

Lack of large labeled data is a notorious bottleneck of the data-driven-based machine learning paradigm. Crowdsourcing provides a potential solution to this challenge: eliciting labels from crowds. However, the elicited labels are usually very noisy, especially for some difficult tasks (e.g. age estimation, medical images annotation). In the crowdsourcing-learning scenario, two problems are raised:

(i) how to aggregate and infer the ground truth from the imperfect crowdsourced labels?

(ii) how to learn an accurate data classifier with the imperfect crowdsourced labels?

One conventional solution to the two problems is aggregating the crowdsourced labels using majority vote and then learning a data classifier with the majority answer. However, this naive method will cause biased results when the task is difficult and the majority of the crowds label randomly or always label a particular class (say class 1) effortlessly.

Another typical solution is aggregating the crowdsourced labels in a more clever way, like spectral method (Dalvi et al., 2013; Zhang et al., 2014) , and then learning with the aggregated results. This method avoids the above flaw that the majority vote method has, as long as their randomnesses are mutually independent. However, the spectral method requires that the experts' labeling noise are mutually independent, which often does not hold in practice since some experts may make highly correlated mistakes (see Figure 2 for example). Moreover, the above solutions aim to train an accurate data classifier and do not provide a method that can employ both the data and the crowdsourced labels to forecast the ground truth.

A common assumption in the learning from crowds literature is that conditioning on the ground truth, the crowdsourced labels and the data are independent, as shown in Figure 1 (a). Under this assumption, the crowdsourced labels correlate with the data due to and only due to the ground truth. Thus, this assumption tells us the ground truth is the "information intersection" between the crowdsourced labels and the data. This "information intersection" assumption does not restrict the information structure among the crowds i.e. this assumption still holds even if some people of the crowds make highly correlated mistakes.

Figure 1: (a) The general information structure under the "information intersection" assumption. (b) Possible information structures under the "information intersection" assumption, where the crowdsourced labels are provided by several experts: (1) independent mistakes: all of the experts are correlated with the ground truth and mutually independent of each other conditioning on the ground truth; for (2), (3) the senior experts are mutually conditional independent and (2) naive majority: the junior experts always label class 1 without any effort; (3) correlated mistakes: the junior experts, who were advised by the same senior expert before, make highly correlated mistakes.

We present several possible information structures under the "information intersection" assumption in Figure 1 (b). The majority vote will lead to inaccurate results in all cases if the experts have different levels of expertise and will induce extremely biased results in case (2) when a large number of junior experts always label class 1. The approaches that require the experts to make independent mistakes will lead to biased results in case (3), when the experts make highly correlated mistakes In this paper, we propose an information theoretic approach, Max-MIG, for joint learning from crowds, with a common assumption: the crowdsourced labels and the data are independent conditioning on the ground truth. To the best of our knowledge, this is the first algorithm that is both theoretically and empirically robust to the situation where some experts make highly correlated mistakes and some experts label effortlessly, without knowing the information structure among the experts. Our algorithm simultaneously aggregates the crowdsourced labels and learns an accurate data classifier.

In addition, we propose a method to learn an accurate data-crowds forecaster that can employ both the data and the crowdsourced labels.

At a high level, our algorithm trains a data classifier and a crowds aggregator simultaneously to maximize their "mutual information". This process will find the "information intersection" between the data and crowdsourced labels i.e. the ground truth labels. The data-crowds forecaster can be easily constructed from the trained data classifier and the trained crowds aggregator. This algorithm allows the conditional dependency among the experts as long as the intersection assumption holds.

We design the crowds aggregator as the "weighted average" of the experts. This simple "weighted average" form allows our algorithm to be both highly efficient in computing and theoretically robust to a large family of information structures (e.g. case (1), ( 2), (3) in Figure 1 (b) ). Particularly, our algorithm works when there exists a subset of senior experts, whose identities are unknown, such that these senior experts have mutually independent labeling biases and it is sufficient to only use the seniors' information to predict the ground truth label. For other junior experts, they are allowed to have any dependency structure among themselves or between them and the senior experts. We assume the seniors' labeling biases are mutually independent. However, for two juniors that were advised by the same senior before, they make highly correlated mistakes when labeling the images. We assume that 5 experts are from hospital A, 50 experts are from hospital B, and 5 experts are from hospital C. If we use majority vote to aggregate the labels, the aggregated result will be biased to hospital B. If we still pretend the experts' labeling noises are independent and apply the approaches that require independent mistakes, the aggregated result will still be biased to hospital B.

2. RELATED WORK:

A series of works consider the learning from crowds problem and mix the learning process and the aggregation process together. Raykar et al. (2010) reduce the learning from crowds problem to a maximum likelihood estimation (MLE) problem, and implement an EM algorithm to jointly learn the expertise of different experts and the parameters of a logistic regression classifier. Albarqouni et al. (2016) extend this method to combine with the deep learning model. Khetan et al. (2017) also reduce the learning problem to MLE and assume that the optimal classifier gives the ground truth labels and the experts make independent mistakes conditioning on the ground truth. Unlike our method, these MLE based algorithms are not robust to correlated mistakes. Recently, Guan et al. (2017) and Rodrigues & Pereira (2017) propose methods that model multiple experts individually and explicitly in a neural network. However, their works lack theoretical guarantees and are outperformed by our method in the experiments, especially in the naive majority case. Moreover, unlike our method, their methods cannot be used to employ both the data and the crowdsourced labels to forecast the ground truth.

Several works focus on modeling the experts. Whitehill et al. (2009) model both expert competence and image difficulty, but did not consider expert bias. Welinder et al. (2010) model each expert as a multidimensional classifier in an abstract feature space and consider both the bias of the expert and the difficulty of the image. Rodrigues et al. (2014) model the crowds by a Gaussian process. Khetan & Oh (2016); Shah et al. (2016) consider the generalized Dawid-Skene model (Dawid & Skene, 1979) which involves the task difficulty. However, these works are still not robust to correlated mistakes. We model the crowds via the original Dawid-Skene model and do not consider the task difficulty, but we believe our Max-MIG framework can be incorporated with any model of the experts and allow correlated mistakes.

Our method differs from the works that focus on inferring ground truth answers from the crowds' reports and then learn the classifier with the inferred ground truth (e.g. (Dawid & Skene, 1979; Zhou et al., 2012; Liu et al., 2012; Karger et al., 2014; Zhang et al., 2014; Dalvi et al., 2013; Ratner et al., 2016) ) since our method simultaneously infers the ground truth and learns the classifier. In addition, our method provides a data-crowds forecaster while those works do not.

Our method is also closely related to co-training. Blum & Mitchell (1998) first propose the co-training framework: simultaneously training two classifiers to aggregate two views of data. Our method interprets joint learning from crowds as a co-training style problem. Most traditional co-training methods require weakly good classifier candidates (e.g. better than random guessing). We follow the general information theoretic framework proposed by Kong & Schoenebeck (2018) that does not have this requirement. However, Kong & Schoenebeck (2018) only provide theoretic framework and assume an extremely high model complexity without considering the over-fitting issue, which is a too strong assumption for practice. Our work apply this framework to the learning from crowds problem and provide the proper design for the model complexity as well as the experimental validations.

3. METHOD:

In this section, we formally define the problem, introduce our method, Max-MIG, and provide a theoretical validation for our method.

Notations For every set A, we use ∆ A to denote the set of all possible distributions over A. For every integer M , we use [M ] to denote {1, 2, . . . , M }. For every matrix A = (A i,j ) i,j ∈ R + s×t , we define log A as a s × t matrix such that its the (i, j) th entry is log(A i,j ). Similarly for every vector v = (v i ) i ∈ R + s , we define log v as a vector such that its the i th entry is log(v i ).

Problem statement There are N datapoints. Each datapoint x ∈ I (e.g. the CT scan of a lung nodule) is labeled by M experts y [M ] ∶= {y 1 , y 2 , . . . , y M y m ∈ C} (e.g. C = {benign, malignant}, 5 experts' labels: {benign, malignant, benign, benign, benign}). The datapoint x and the crowdsourced labels y [M ] are related to a ground truth y ∈ C (e.g. the pathological truth of the lung nodule).

We are aiming to simultaneously train a data classifier h and a crowds aggregator g such that h ∶ I ↦ ∆ C predicts the ground truth y based on the datapoint x ∈ I, and g ∶ C M → ∆ C aggregates M crowdsourced labels y [M ] into a prediction for ground truth y. We also want to learn a data-crowds forecaster ζ ∶ I × C M ↦ ∆ C that forecasts the ground truth y based on both the datapoint x ∈ I and the crowdsourced labels y [M ] ∈ C.

3.1. MAX-MIG: AN INFORMATION THEORETIC APPROACH:

Figure 3 illustrates the overview idea of our method. Here we formally introduce the building blocks of our method.

Data classifier h:

The data classifier h is a neural network with parameters Θ. Its input is a datapoint x and its output is a distribution over C. We denote the set of all such data classifers by H N N .

Crowds aggregator g:

The crowds aggregator g is a "weighted average" function to aggregate crowdsourced labels with parameters {W m ∈ R C × C } M m=1 and b. Its input y [M ] is the crowdsourced labels provided by M experts for a datapoint and its output is a distribution over C. By representing each y m ∈ y [M ] as an one-hot vector e (y m ) ∶= (0, . . . , 1, . . . , 0) ⊺ ∈ {0, 1} C where only the y m th entry of e (y m ) is 1,

g(y [M ] ; {W m } M m=1 , b) = softmax( M m=1 W m ⋅ e (y m ) + b)

where W m ⋅ e (y m ) is equivalent to pick the y m th column of matrix W m , as shown in Figure 3 . We denote the set of all such crowds aggregators by G W A .

Data-crowds forecaster ζ Given a data classifier h, a crowds aggregator g and a distribution p = (p c ) c ∈ ∆ C over the classes, the data-crowds forecaster ζ, that forecasts the ground truth based on both the datapoint x and the crowdsourced labels y [M ] , is constructed by

ζ(x, y [M ] ; h, g, p) = Normalize ( h(x) c ⋅ g(y [M ] ) c p c ) c

where Normalize(v) ∶= v ∑ c vc .

f -mutual information gain M IG f f -mutual information gain M IG f measures the "mutual information" between two hypotheses, which is proposed by Kong & Schoenebeck (2018) . Given N datapoints x 1 , x 2 , . . . , x N ∈ I where each datapoint x i is labeled by M crowdsourced labels Step 1: finding the "information intersection" between the data and the crowdsourced labels: we train a data classifier h and a crowds aggregator g simultaneously to maximize their f -mutual information gain M IG f (h, g, p) with a hyperparameter p ∈ ∆ C . h maps each datapoint x i to a forecast h(x i ) ∈ ∆ C for the ground truth. g aggregates M crowdsourced labels y

[M ] i into a forecast g(y

[M ] i

) ∈ ∆ C by "weighted average". We tune the parameters of h and g simultaneously to maximize their f -mutual information gain. We will show the maximum is the f -mutual information (a natural extension of mutual information, see Appendix C) between the data and the crowdsourced labels.

Step 2: aggregating the "information intersection": after we obtain the best h, g, p that maximizes M IG f (h, g, p), we use them to construct a data-crowds forecaster ζ that forecasts ground truth based on both the datapoint and the crowdsourced labels. To calculate the f -mutual information gain, we reward them for the average "agreements" between their outputs for the same task, i.e. h(x i ) and g(y

[M ] i

) , as shown by the black lines, and punish them for the average "agreements" between their outputs for the different tasks, i.e. h(x i ) and g(y

[M ] j

) where i ≠ j, as shown by the grey lines. Intuitively, the reward encourages the data classifier to agree with the crowds aggregator, while the punishment avoids them naively agreeing with each other, that is, both of them map everything to (1, 0, . . . , 0). The measurement of "agreement" depends on the selection of f . See formal definition for M IG f in (1).

y 1 i , y 2 i , . . . , y M i ∈ C

, the f -mutual information gain between h and g, associated with a hyperparameter p = (p c ) c ∈ ∆ C , is defined as the average "agreements" between h and g for the same task minus the average "agreements" between h and g for the different tasks, that is,

M IG f ({x i }, {y [M ] i }; h, g, p) = 1 N i ∂f c∈C h(x i ) c ⋅ g(y [M ] i ) c p c (1) - 1 N (N -1) i≠j f ⋆ ⎛ ⎝ ∂f c∈C h(x i ) c ⋅ g(y [M ] j ) c p c ⎞ ⎠

where f is a convex function satisfying f (1) = 0 and f ⋆ is the Fenchel duality of f . We can use Table 1 as reference for ∂f (⋅) and f ⋆ (∂f (⋅)).

Table 1 : Reference for common f -divergences and corresponding M IG f 's building blocks. This table is induced from Nowozin et al. (2016) .

f -divergence f (t) ∂f (K) f ⋆ (∂f (K)) KL divergence t log t 1 + log K K Pearson χ 2 (t -1) 2 2(K -1) K 2 -1 Jensen-Shannon -(t + 1) log t+1 2 + t log t log 2K 1+K -log( 2 1+K )

Since the parameters of h is Θ and the parameters of g is {W m } M m=1 and b, we naturally rewrite

M IG f ({x i }, {y [M ] i }; h, g, p) as M IG f ({x i }, {y [M ] i }; Θ, {W m } M m=1 , b, p).

We seek {Θ, {W m } M m=1 , b, p} that maximizes M IG f . Later we will show that when the prior of the ground truth is p * (e.g. p * = (0.8, 0.2) i.e. the ground truth is benign with probability 0.8 and malignant with probability 0.2 a priori), the best b and p are log p * and p * respectively. Thus, we can set b as log p and only tune p. When we have side information about the prior p * , we can fix parameter p as p * , and fix parameter b as log p * .

3.2. THEORETICAL JUSTIFICATION:

This section provides a theoretical validation for Max-MIG, i.e., maximizing the f -mutual information gain over H N N and G W A finds the "information intersection" between the data and the crowdsourced labels. In Appendix E, we compare our method with the MLE method (Raykar et al., 2010) theoretically and show that unlike our method, MLE is not robust to the correlated mistakes case.

Recall that we assume that conditioning on the ground truth, the data and the crowdsourced labels are mutually independent. Thus, we can naturally define the "information intersection" as a pair of data classifier and crowds aggregator h * , g * such that they both fully use their input to forecast the ground truth. Kong & Schoenebeck (2018) shows that when we have infinite number of datapoints and maximize over all possible data classifiers and crowds aggregators, the "information intersection" will maximize M IG f (h, g) to the f -mutual information (Appendix C) between the data and the crowdsourced labels. However, in practice, with a finite number of datapoints, the data classifier and the crowds aggregator space should be not only sufficiently rich to contain the "information intersection" but also sufficiently simple to avoid over-fitting. Later, the experiment section will show that our picked H N N and G W A are sufficiently simple to avoid over-fitting. We assume the neural network space is sufficiently rich. It remains to show that our weighted average aggregator space G W A is sufficiently rich to contain g * .

Model and assumptions Each datapoint x i with crowdsourced labels provided by M experts y 1 i , ..., y M i are drawn i.i.d. from random variables X, Y 1 , ..., Y M . Assumption 3.1 (Co-training assumption). X and Y [M ] are independent conditioning on Y .

Note that we do not assume that the experts' labels are conditionally mutually independent. We define p * ∈ ∆ C as the prior for Y , i.e. p * c = P (Y = c). Definition 3.2 (Information intersection). We define h * , g * and ζ * such that

h * (x) c = P (Y = c X = x) g * (y [M ] ) c = P (Y = c Y [M ] = y [M ] ). ζ * (x, y [M ] ) c = P (Y = c X = x, Y [M ] = y [M ] )

We call them Bayesian posterior data classifier / crowds aggregator / data-crowds forecaster respectively. We call (h * , g * ) the information intersection between the data and the crowdsourced labels.

We also assume the neural network space is sufficiently rich to contain h * . Assumption 3.3 (Richness of the neural networks). h * ∈ H N N . Theorem 3.4. With assumptions 3.1, 3.3, when there exists a subset of experts S ⊂ [M ] such that the experts in S are mutually independent conditioning on Y and Y S is a sufficient statistic for Y , i.e.

P (Y = y Y [M ] = y [M ] ) = P (Y = y Y S = y S ) for every y ∈ C, y [M ] ∈ C M , then (h * , g * , p * ) is a maximizer of max h∈H N N ,g∈G W A ,p∈∆ C E X,Y [M ] M IG f (h(X), g(Y [M ] ), p)

and the maximum is the f -mutual information between X and Y [M ] . Moreover, ζ * (x, y [M ] ) = ζ(x, y [M ] ; h * , g * , p * ) for every x, y [M ] .

Our main theorem shows that if there exists a subset of senior experts such that these senior experts are mutually conditional independent and it is sufficient to only use the information from these senior experts, then Max-MIG finds the "information interstion". Note that we do not need to know the identities of the senior experts. For other junior experts, we allow any dependency structure among them and between them and the senior experts. Moreover, this theorem also shows that our method handles the independent mistakes case where all experts can be seen as senior experts (Proposition D.3).

To show our results, we need to show that G W A contains g * , i.e. there exists proper weights such that g * can be represented as a weighted average. In the independent mistakes case, we can construct each expert's weight using her confusion matrix. Thus, in this case, each expert's weight represents her expertise. In the general case, we can construct each senior expert's weight using her confusion matrix and make the junior experts' weights zero. Due to space limitation, we defer the formal proofs to Appendix D.

4. EXPERIMENT:

In this section, we evaluate our method on image classification tasks with both synthesized crowdsourced labels in various of settings and real world data. 

4.1. RESULTS:

We train the data classifier h on the four datasets through our method1 and other related methods. The accuracy of the trained data classifiers on the test set are shown in Table 2 and Figure 4 . We also show the accuracy of our data-crowd forecaster and on the test set and compare it with AggNet (Table 3 ).

For the performances of the trained data classifiers, our method Max-MIG (red) almost outperform all other methods in every experiment. For the real-world dataset, LabelMe, we achieve the new state-of-the-art results. For the synthesized crowdsourced labels, the majority vote method (grey) fails in the naive majority situation. The AggNet has reasonably good performances when the experts are conditionally independent, including the naive majority case since naive expert is independent with everything, while it is outperformed by us a lot in the correlated mistakes case. This matches the theory in Appendix E: the AggNet is based on MLE and MLE fails in correlated mistakes case. The Doctor Net (green) and the Crowd Layer (blue) methods are not robust to the naive majority case. Our data-crowds forecaster (Table 3 ) performs better than our data classifier, which shows that our data-crowds forecaster actually takes advantage of the additional information, the crowdsourced labels, to give a better result. Like us, Aggnet also jointly trains the classifier and the aggregator, and can be used to train a data-crowds forecaster. We compared our data-crowds forecaster with Aggnet.

The results still match our theory. When there is no correlated mistakes, we outperform Aggnet or have very similar performances with it. When there are correlated mistakes, we outperform Aggnet a lot (e.g. +30%).

Recall that in the experiments, for each of the situation (H) (L), all three cases have the same senior experts. Thus, all three cases' crowdsourced labels have the same amount of information. The results show that Max-MIG has similar performances for all three cases for each of the situation (H) (L), which validates our theoretical result: Max-MIG finds the "information intersection" between the data and the crowdsourced labels.

5. CONCLUSION AND DISCUSSION:

We propose an information theoretic approach, Max-MIG, for joint learning from crowds, with a common assumption: the crowdsourced labels and the data are independent conditioning on the ground truth. We provide theoretical validation to our approach and compare our approach experimentally with previous methods (Doctor net (Guan et al., 2017) , Crowd layer (Rodrigues & Pereira, 2017) , Aggnet (Albarqouni et al., 2016 )) under several different information structures. Each of the previous methods is not robust to at least one information structure and our method is robust to all and almost outperform all other methods in every experiment. To the best of our knowledge, our approach is the first algorithm that is both theoretically and empirically robust to the situation where some people make highly correlated mistakes and some people label effortlessly, without knowing the information structure among the crowds. We also test our method on real-world data and achieve the new state-of-the-art result.

Our current implementation of Max-MIG has several limitations. For example, we implement the aggregator using a simple linear model, which cannot handle the case when the senior experts are latent and cannot be linearly inferred from the junior experts. However, note that if the aggregator space is sufficiently rich, the Max-MIG approach is still able to handle any situation as long as the "information intersection" assumption holds. One potential future direction is designing more complicated but still trainable aggregator space. A DATA-CROWDS FORECASTER COMPARISON Here (dc) is the shorthand for data-crowds forecaster and (d) is the shorthand for data-classifier. We take the average of five times experiments and the variance is pretty small. Due to space limitation, we omit the variance here.

For Labelme data, We apply the same setting of Rodrigues & Pereira (2017) : we use pre-trained VGG-16 deep neural network and apply only one FC layer (with 128 units and ReLU activations) and one output layer on top, using 50% dropout. We use Adam optimizer with learning rate 1.0 × 10 -4 for both the data classifier and the crowds aggregator.

For our method MAX-MIG's crowds aggregator, for Dogs vs. Cats and LUNA16, we set the bias b as log p and only tune p. For CIFAR-10 and Labelme data, we fix the prior distribution p to be the uniform distribution p 0 and fix the bias b as log p 0 .

Initialization For AggNet and our method Max-MIG, we initialize the parameters {W m } m using the method in Raykar et al. ( 2010):

EQUATION

where 1(y

m i = c ′ ) = 1 when y m i = c ′ and 1(y m i = c ′ ) = 0 when y m i ≠ c ′

and N is the total number of datapoints. We average all crowdsourced labels to obtain

Q(y i = c) ∶= 1 M M ∑ m=1 1(y m i = c).

For Crowd Layer method, we initialize the weight matrices using identity matrix on Dogs vs. Cats and LUNA as Rodrigues & Pereira (2017) suggest. However, this initialization method leads to pretty bad results on CIFAR-10. Thus, we use (2) for Crowd Layer on CIFAR-10, which is the best practice in our experiments.

C f -MUTUAL INFORMATION:

C.1 f -DIVERGENCE AND FENCHEL'S DUALITY f -divergence (Ali & Silvey, 1966; Csiszár et al., 2004) 

f -divergence D f ∶ ∆ Σ × ∆ Σ ↦ R is a

non-symmetric measure of the difference between distribution p ∈ ∆ Σ and distribution q ∈ ∆ Σ and is defined to be

D f (p, q) = σ∈Σ p(σ)f q(σ) p(σ)

where f ∶ R ↦ R is a convex function and f (1) = 0.

C.2 f -MUTUAL INFORMATION:

Given two random variables X, Y whose realization space are Σ X and Σ Y , let U X,Y and V X,Y be two probability measures where U X,Y is the joint distribution of (X, Y ) and V X,Y is the product of the marginal distributions of X and Y . Formally, for every pair of (x, y)

∈ Σ X × Σ Y , U X,Y (X = x, Y = y) = Pr[X = x, Y = y] V X,Y (X = x, Y = y) = Pr[X = x] Pr[Y = y].

If U X,Y is very different from V X,Y , the mutual information between X and Y should be high since knowing X changes the belief for Y a lot. If U X,Y equals to V X,Y , the mutual information between X and Y should be zero since X is independent with Y . Intuitively, the "distance" between U X,Y and V X,Y represents the mutual information between them.

Definition C.1 (f -mutual information (Kong & Schoenebeck, 2016) ). The f -mutual information between X and Y is defined as

M I f (X, Y ) = D f (U X,Y , V X,Y )

where D f is f -divergence. f -mutual information is always non-negative. Kong & Schoenebeck (2016) show that if we measure the amount of information by f -mutual information, any "data processing" on either of the random variables will decrease the amount of information crossing them. With this property, Kong & Schoenebeck (2016) propose an information theoretic mechanism design framework using f -mutual information. Kong & Schoenebeck (2018) reduce the co-training problem to a mechanism design problem and extend the information theoretic framework in Kong & Schoenebeck (2016) to address the co-training problem.

D PROOF OF THEOREM 3.4

This section provides the formal proofs to our main theorem. Definition D.1 (Confusion matrix). For each expert m, we define her confusion matrix as

C m = (C m c,c ′ ) c,c ′ ∈ R C × C where C m c,c ′ = P (Y m = c ′ Y = c).

We denote the set of all possible classifiers by H ∞ and the set of all possible aggregators by G ∞ . Lemma D.2. (Kong & Schoenebeck, 2018) With assumption 3.1, 3.3, (h * , g * , p * ) is a maximizer of

max h∈H∞,g∈G∞,p∈∆ C E X,Y [M ] M IG f (h(X), g(Y [M ] ), p)

and the maximum is the f mutual information between X and Y [M ] , M I f (X, Y [M ] ). Moreover, ζ * (x, y [M ] ) = ζ(x, y [M ] ; h * , g * , p * ) for every x, y [M ] .

Proposition D.3. [Independent mistakes] With assumptions 3.1, 3.3, if the experts are mutually independent conditioning on Y , then g * ∈ G W A and

g * (y [M ] ) = g(y [M ] ; {log C m } M m=1 , log p * ) for every y [M ] ∈ C M .

This implies that (h * , g * , p * ) is a maximizer of

max h∈H N N ,g∈G W A ,p∈∆ C E X,Y [M ] M IG f (h(X), g(Y [M ] ), p)

and the maximum is the f mutual information between X and Y [M ] , M I f (X, Y [M ] ). Moreover, ζ * (x, y [M ] ) = ζ(x, y [M ] ; h * , g * , p * ) for every x, y [M ] .

Proof. We will show that when the experts are mutually conditionally independent, then g * (y [M ] ) = g(y [M ] ; {log C m } M m=1 , log p * ).

This also implies that g * ∈ G W A . Based on the result of Lemma D.2, by assuming that h * ∈ H N N , we can see (h * , g * , p * ) is a maximizer of max h∈H N N ,g∈G W A ,p∈∆ C M IG f (h, g, p) and the maximum is the f mutual information between X and Y [M ] . Moreover, Lemma D.2 also implies that ζ * (x, y [M ] ) = ζ(x, y [M ] ; h * , g * , p * ) for every x, y [M ] .

For every c ∈ C, every y

[M ] ∈ C M , (log g * (y [M ] )) c = log P (Y = c Y [M ] = y [M ] ) = log P (Y [M ] = y [M ] Y = c)P (Y = c) -log P (Y [M ] = y [M ] ) = M m=1 log P (Y m = y m Y = c) + log P (Y = c) -log P (Y [M ] = y [M ] )

Thus,

( M m=1 log C m ⋅ e (y m ) + log p * ) c = M m=1 log P (Y m = y m Y = c) + log P (Y = c) =(log g * (y [M ] )) c + log P (Y [M ] = y [M ] )

Then,

(sof tmax( m log C m ⋅ e (y m ) + log p * )) c = e (log g * (y [M ] ))c+log P (Y [M ] =y [M ] ) ∑ c e (log g * (y [M ] ))c+log P (Y [M ] =y [M ] ) = e (log g * (y [M ] ))c ∑ c e (log g * (y [M ] ))c

=(g * (y [M ] )) c (since g * (y [M ] ) ∈ ∆ C , ∑ c g * (y [M ] ) c = 1) Thus,

g * (y [M ] ) = sof tmax( m log C m ⋅ e (y m ) + log p * ) = g(y [M ] ; {log C m } M m=1 , log p * ).

We restate our main theorem, Theorem 3.4, here with more details and prove it. This implies that (h * , g * , p * ) is a maximizer of

max h∈H N N ,g∈G W A ,p∈∆ C E X,Y [M ] M IG f (h(X), g(Y [M ] ), p)

and the maximum is the f mutual information between X and Y [M ] , M I f (X, Y [M ] ). Moreover, ζ * (x, y [M ] ) = ζ(x, y [M ] ; h * , g * , p * ) for every x, y [M ] .

Proof. Like the proof for the above proposition, we need to show that g * (y [M ] ) = g(y [M ] ; {W * m } m , log p * ).

This also implies that g * ∈ G W A as well as the other results of the theorem.

When Y S is a sufficient statistic for Y , we have

g * (y [M ] ) = g * (y S ).

Proposition D.3 shows that g * (y S ) = g(y S ; {log C s } s∈S , log p * ).

Thus, we have

g * (y [M ] ) = g * (y S ) = g(y S ; {log C s } s∈S , log p * ) = g(y [M ] ; {W * m } m , log p * )

where for every m ∈ S, W * m = log C m , for every m ∉ S, W * m = 0. (Albarqouni et al., 2016) extends it to combine with the deep learning model. In this section, we will theoretically show that these MLE based methods can handle the independent mistakes case but cannot handle even the simplest correlated mistakes case-only one expert reports meaningful information and all other experts always report the same meaningless information-which can be handled by our method. Therefore, in addition to the experimental results, theoretically, our method is still better than these MLE based methods. We first introduce these MLE based methods.

E THEORETICAL COMPARISONS WITH MLE:

Let Θ be the parameter that control the distribution over X and Y . Let Θ m be the parameter that controls the distribution over Y m and Y .

For each each x, y [M ] ,

P (Y [M ] = y [M ] X = x; Θ, {Θ m } m ) (3) = y P (Y = y X = x; Θ)P (Y [M ] = y [M ] Y = y; {Θ m } m ) (conditioning on Y , X and Y [M ] are independent) = y P (Y = y X = x; Θ)Π M m=1 P (Y m = y m Y = y; Θ m )

(experts are mutually conditional independent.)

The MLE based method seeks Θ and Θ m that maximize

N i=1 log c P (Y = c X = x i ; Θ)Π M m=1 P (Y m i = y m i Y = c; Θ m )

To theoretically compare it with our method, we use our language to reinterpret the above MLE based method.

We define T as the set of all C × C transition matrices with each row summing to 1.

For each expert m, we define W m ∈ T as a parameter that is associated with m.

Given a set of data classifiers h ∈ H where h ∶ I ↦ ∆ C , the MLE based method seeks h ∈ H and transition matrices

W 1 , W 2 , ⋯, W M ∈ T that maximize N i=1 log c h(x i ) c Π M m=1 W m c,y m i .

The expectation of the above formula is

E X,Y [M ] log c h(X) c Π M m=1 W m c,Y m .

Note that Raykar et al. (2010) set the data classifiers space H as all logistic regression classifiers and Albarqouni et al. (2016) extend this space to the neural network space.

Proposition E.1 (MLE works for independent mistakes). If the experts are mutually independent conditioning on Y, then h * and C 1 , C 2 , ⋯, C M are a maximizer of

max h,W 1 ,W 2 ,⋯,W m ∈T E X,Y [M ] log c h(X) c Π M m=1 W m c,Y m . Proof. E X,Y [M ] log c h(X) c Π M m=1 W m c,Y m = x,y [M ] P (X = x, Y [M ] = y [M ] ) log c h(x) c Π M m=1 W m c,y m = x P (X = x) y [M ] P (Y [M ] = y [M ] X = x) log c h(x) c Π M m=1 W m c,y m Since W 1 , W 2 , ⋯, W m ∈ T , thus, y [M ] ∈C M c∈C h(x) c Π M m=1 W m c,y m = 1 which means (∑ c∈C h(x) c Π M m=1 W m c,y m ) y [M ]

can be seen as a distribution over all possible y [M ] ∈ C M . Moreover, for any two distribution vectors p and q, p ⋅ log q ≤ p ⋅ log p, thus Thus, the MLE based method handles the independent mistakes case. However, we will construct a counter example to show that it cannot handle a simple correlated mistakes case which can be handled by our method. Example E.2 (A simple correlated mistakes case). We assume there are only two classes C = {0, 1} and the prior over Y is uniform, that is, P (Y = 0) = P (Y = 1) = 0.5. We also assume that X = Y .

There are 101 experts and one of the experts, say her the first expert, fully knows Y and always reports Y 1 = Y . The second expert knows nothing and every time flips a random unbiased coin whose randomness is independent with X, Y . She reports Y 2 = 1 when she gets head and reports Y 2 = 0 otherwise. The rest of experts copy the second expert's answer all the time, i.e. Y m = Y 2 , for m ≥ 2.

Note that our method can handle this simple correlated mistakes case and will give all useless experts weight zero based on Theorem 3.4.

We define h 0 as a data classifier such that h 0 (x) 0 = h 0 (x) 1 = 0.5. We will show this meaningless data classifier h 0 has much higher likelihood than h * , which shows that in this simple correlated mistakes case, the MLE based method will obtain meaningless results.

We define a data classifier h's maximal expected likelihood as max

W 1 ,W 2 ,⋯,W m ∈T E X,Y [M ] log c h(X) c Π M m=1 W m c,Y m .

Theorem E.3 (MLE fails for correlated mistakes). In the scenario defined by Example E.2, the meaningless classifier h 0 's maximal expected likelihood is at least log 0.5 and the Bayesian posterior classifier h * 's maximal expected likelihood is 100 log 0.5 ≪ log 0.5.

The above theorem implies that the MLE based method fails in Example E.2. (W m is a transition matrix and p ⋅ log q ≤ p ⋅ log p) =100 log 0.5 (Y 2 equals 0 with probability 0.5 and 1 with probability 0.5 as well)

The maximal value is obtained by setting W 1 as an identity matrix and setting W 2 = ⋯ = W M as 0.5 0.5 0.5 0.5 . Thus, the Bayesian posterior data classifier h * 's maximal expected likelihood is Note when we set every W m as an identity matrix, the above formula equals log 0.5. Thus, the meaningless data classifier h 0 's maximal expected likelihood is at least log 0.5.

:

The results of Max-MIG are based on KL divergence. The results for other divergences are similar.

We denote the matrix whose entries are all zero by 0.

Figures and Tables:

Figure 2: Medical image labeling example: we want to train a data classifier to classify the medical images into two classes: benign and malignant. Each image is labeled by several experts. The experts are from different hospitals, say hospital A, B, C. Each hospital has a senior who has a high expertise.We assume the seniors' labeling biases are mutually independent. However, for two juniors that were advised by the same senior before, they make highly correlated mistakes when labeling the images. We assume that 5 experts are from hospital A, 50 experts are from hospital B, and 5 experts are from hospital C. If we use majority vote to aggregate the labels, the aggregated result will be biased to hospital B. If we still pretend the experts' labeling noises are independent and apply the approaches that require independent mistakes, the aggregated result will still be biased to hospital B.

Figure 3: Max-MIG overview:Step 1: finding the "information intersection" between the data and the crowdsourced labels: we train a data classifier h and a crowds aggregator g simultaneously to maximize their f -mutual information gain M IG f (h, g, p) with a hyperparameter p ∈ ∆ C . h maps each datapoint x i to a forecast h(x i ) ∈ ∆ C for the ground truth. g aggregates M crowdsourced labels y

Figure 4: Results on Dogs vs. Cats, CIFAR-10, LUNA16.

Theorem 3.4 (General case). With assumption 3.1, 3.3, when there exists a subset of experts S ⊂ [M ] such that the experts in S are mutually independent conditioning on Y and Y S is a sufficient statistic for Y , i.e.P (Y = y Y [M ] = y [M ] ) = P (Y = y Y S = y S ) for every y ∈ C, y [M ] ∈ C M , then g * ∈ G W A and g * (y [M ] ) = g(y [M ] ; {W * m } m , log p * )for every y[M ] ∈ C M where for every m ∈ S, W * m = log C m , for every m ∉ S, W * m = 0 2 .

(X = x) y [M ] P (Y [M ] = y [M ] X = x) log c h(x) c Π M m=1 W m c,y m ≤ x P (X = x) y [M ] P (Y [M ] = y [M ] X = x) log P (Y [M ] = y [M ] X = x)

For the Bayesian posterior classifierh * , since X = Y = Y 1 and Y 2 = ⋯ = Y M , then h * (X = c) is an one-hot vector where the c th entry is 1 and everything is determined by the realizations of Y and Y2 . c)P (Y 2 = c ′ ) log W 1 c,c Π M m=2 W m c,c ′ (X = Y = Y 1 , Y 2 = ⋯ = Y M ) 2 = c ′ ) log P (Y 2 = c ′ )

For the meaningless data classifier h 0 , (Y = c)P (Y 2 = c ′ ) log 0

Case 4.2. (Naive majority) M s senior experts are mutually conditional independent, while other M j junior experts label all datapoints as the first class effortlessly.

Table content: <table><tr><td>Case 4.3. (Correlated mistakes) M s senior experts are mutually conditional independent, and each</td></tr><tr><td>junior expert copies one of the senior experts.</td></tr><tr><td>Real-world dataset The LabelMe data (Rodrigues &amp; Pereira, 2017; Russell et al., 2008) consists</td></tr><tr><td>of a total of 2688 images, where 1000 of them were used to obtain labels from multiple annotators</td></tr><tr><td>from Amazon Mechanical Turk and the remaining 1688 images were using for evaluating the different</td></tr><tr><td>approaches. Each image was labeled by an average of 2.547 workers, with a mean accuracy of 69.2%.</td></tr></table>

Accuracy on LabelMe (real-world crowdsourced labels)

Table content: <table><tr><td>Method</td><td>Majority Vote Crowd Layer Doctor Net</td><td>AggNet</td><td>Max-MIG</td></tr></table>

Filipe Rodrigues, Francisco Pereira, and Bernardete Ribeiro. Gaussian process classification and active learning with multiple annotators. In International Conference on Machine Learning, pp. 433-441, 2014. Optimal estimation and robustness. arXiv preprint arXiv:1606.09632, 2016. Peter Welinder, Steve Branson, Pietro Perona, and Serge J Belongie. The multidimensional wisdom of crowds. In Advances in neural information processing systems, pp. 2424-2432, 2010. Jacob Whitehill, Ting-fan Wu, Jacob Bergsma, Javier R Movellan, and Paul L Ruvolo. Whose vote should count more: Optimal integration of labels from labelers of unknown expertise. In Advances in neural information processing systems, pp. 2035-2043, 2009.

Table content: <table><tr><td>Bryan C Russell, Antonio Torralba, Kevin P Murphy, and William T Freeman. Labelme: a database</td></tr><tr><td>and web-based tool for image annotation. International journal of computer vision, 77(1-3):</td></tr><tr><td>157-173, 2008.</td></tr><tr><td>Arnaud Arindra Adiyoso Setio, Francesco Ciompi, Geert Litjens, Paul Gerke, Colin Jacobs, Sarah J</td></tr><tr><td>Van Riel, Mathilde Marie Winkler Wille, Matiullah Naqibullah, Clara I Sánchez, and Bram van</td></tr><tr><td>Ginneken. Pulmonary nodule detection in ct images: false positive reduction using multi-view</td></tr><tr><td>convolutional networks. IEEE transactions on medical imaging, 35(5):1160-1169, 2016.</td></tr><tr><td>Nihar B Shah, Sivaraman Balakrishnan, and Martin J Wainwright. A permutation-based model for</td></tr><tr><td>crowd labeling:</td></tr></table>

Data-Crowds Forecaster Comparison: Max-MIG VS AggNet

Table content: <table><tr><td>Dataset</td><td>Method</td><td colspan="4">4.1(H) 4.2(H) 4.3(H) 4.1(L) 4.2(L) 4.3(L)</td></tr><tr><td/><td>Max-MIG (d)</td><td>79.52</td><td>80.25</td><td>78.94</td><td>71.44 71.07 68.40</td></tr><tr><td>Dogs vs.Cats</td><td colspan="2">Max-MIG (dc) 88.80 AggNet (d) 79.36</td><td>87.60 79.53</td><td>87.17 71.97</td><td>73.99 73.38 70.75 70.46 70.07 63.85</td></tr><tr><td/><td>AggNet (dc)</td><td>88.00</td><td>88.56</td><td>75.00</td><td>71.27 70.75 61.14</td></tr><tr><td/><td>Max-MIG(d)</td><td>86.33</td><td>86.55</td><td>86.71</td><td>70.16 69.99 67.59</td></tr><tr><td>CIFAR-10</td><td>Max-MIG(dc) AggNet(d)</td><td>98.10 86.13</td><td>98.18 86.27</td><td>99.06 63.91</td><td>75.55 75.11 72.47 70.21 62.50 38.27</td></tr><tr><td/><td>AggNet(dc)</td><td>99.05</td><td>99.01</td><td>70.01</td><td>74.76 72.02 29.03</td></tr><tr><td/><td>Max-MIG(d)</td><td>90.88</td><td>91.06</td><td>91.15</td><td>88.90 89.04 88.85</td></tr><tr><td>LUNA16</td><td>Max-MIG(dc) AggNet(d)</td><td>94.56 89.56</td><td>93.97 90.23</td><td>92.63 83.47</td><td>91.16 91.23 92.05 81.42 83.53 81.68</td></tr><tr><td/><td>AggNet(dc)</td><td>91.13</td><td>91.94</td><td>65.14</td><td>70.97 74.41 61.76</td></tr></table>

Raykar et al. (2010) propose a maximum likelihood estimation (MLE) based method in the learning from crowds scenario. Raykar et al. (2010) use logistic regression and Aggnet

Table content: <table/>

Peer review (iclr2019):
 EDIT: I thank the authors for providing all clarifications. I think this paper is a useful contribution. It will be of interest to the audience in the conference. Summary: This paper provides a method to jointly learn from crowdsourced worker labels and the actual data. The key claimed difference is that previous works on crowdsourced worker labels ignored the data. At a higher level, the algorithm comprises maximizing the mutual information gain between the worker labels and the output of a neural network (or more generally any ML model) on the data. Evaluation: I like the idea behind the algorithm. However there are several issues on which I ask the authors to provide some clarity. I will provide a formal "evaluation" after that. (For the moment, please ignore the "rating". I will provide one after the rebuttal.) (1) As the authors clarified, one key aspect of the "information intersection" assumption is that the crowdsourced labels are statistically independent from the data when conditioned on the ground truth. How strongly does this coincide with reality? Since the work is primary empirical, is there any evidence on this front? (2) In the abstract, introduction etc., what does it mean to say that the algorithm is an "early algorithm"? -- Thanks for the clarification. I would suggest using the term "first algorithm" in such cases. However, is this the first algorithm towards this goal? See point (3). (3) The submitted paper misses an extremely relevant piece of literature: "Learning From Noisy Singly-labeled Data" (arXiv:1712.04577). This paper also aims to solve the label + features problem together. How do the results of this paper compare to that of this submission? (4) "Model and assumptions" Is the i.i.d. assumption across the values of "i"? Then does that not violate the earlier claim of accommodating correlated mistakes? (5) Recent papers on crowdsourcing (such as Achieving budget-optimality with adaptive schemes in crowdsourcing arXiv:1602.03481 and A Permutation-based Model for Crowd Labeling: Optimal Estimation and Robustness arXiv:1606.09632) go beyond restricting workers to have a common confusion matrix for all questions. In this respect, these are better aligned with the realistic scenario where the error in labeling may depend on the closeness to the decision boundary. How do these settings and algorithms relate to the submission? (6) Page 5: "Later we will show...." Later where? Please provide a reference. (7) Theorem 3.4, The assumption of existence of experts such that Y^S is a sufficient statistic for Y: For instance, suppose there are 10 experts who all have a 0.999 probability of correctness (assume symmetric confusion matrices) and there are 5 non-experts who have a 0.001 probability of correctness and even if we suppose all are mutually independent given the true label, then does this satisfy this sufficient statistic assumption? This appears to be a very strong assumption, but perhaps the authors have better intuition? (8) The experiments comprise only some simulations. The main point of experiments (particularly in the absence of any theoretical results) towards bolstering the paper is to ensure that the assumptions are at least somewhat reasonable. I believe there are several datasets collected from Amazon Mechanical Turk available online? Otherwise, would it be possible to run realistic experiments on some crowdsourcing platforms?