Title: MACHINE TRUTH SERUM

Abstract: Wisdom of the crowd (Surowiecki, 2005) revealed a striking fact that the majority answer from a crowd is often more accurate than any individual expert. We observed the same story in machine learning -ensemble methods (Dietterich, 2000) leverage this idea to combine multiple learning algorithms to obtain better classification performance. Among many popular examples is the celebrated Random Forest (Ho, 1995) , which applies the majority voting rule in aggregating different decision trees to make the final prediction. Nonetheless, these aggregation rules would fail when the majority is more likely to be wrong. In this paper, we extend the idea proposed in Bayesian Truth Serum (Prelec, 2004) that "a surprisingly more popular answer is more likely the true answer" to classification problems. The challenge for us is to define or detect when an answer should be considered as being "surprising". We present two machine learning aided methods which aim to reveal the truth when it is minority instead of majority who has the true answer. Our experiments over real-world datasets show that better classification performance can be obtained compared to always trusting the majority voting. Our proposed methods also outperform popular ensemble algorithms. Our approach can be generically applied as a subroutine in ensemble methods to replace majority voting rule.

1. INTRODUCTION:

Wisdom of the crowd harnesses the power of aggregated opinion of a diverse group rather than a few individuals. Though initially proposed for mainly aggregating human judgements, this idea has been successfully implemented in the context of machine learning. In particular, ensemble learning was proposed and studied to improve prediction performance by combining several learning models to obtain better results compared to a single one (Dietterich, 2000) . The developed ensemble techniques have shown consistent benefits in real-world machine learning applications, evidenced by the Netflix Competition (Bennett et al., 2007) and Kaggle competition. Popular ensemble methods include Boosting (e.g., AdaBoost (Freund & Schapire, 1997) ), Bootstrap aggregating (bagging), Stacking (Bishop, 2006), and Random Forest (Ho, 1995) .

The most popular, as well as simple, way to perform aggregation is via majority voting rule. The classical example is Random Forest, which outputs the majority answer from multiple trained decision trees. Inference methods (Raykar et al., 2010; Zhang et al., 2014; Liu et al., 2012; Zhou et al., 2012; 2014) have been applied to perform smarter aggregation that aims to outperform majority-voted answers. These methods often leverage homogeneous assumption of certain hidden models over a large number of data points in order to perform joint inference. Nonetheless, all above methods rely on the assumption that the majority answer is more likely to be correct -this is also true for the more sophisticated inference models, as the inferences will mostly likely initiate based on majority-voted answers (when the algorithm has no prior information). While enjoying this assumption that majority tends to be correct, this claim is questionable in settings where special knowledge is needed to infer the truth, but it is owned by few individuals when they are not widely shared (Chen et al., 2004; Simmons et al., 2010; Prelec et al., 2017) . Echoing to the above problem of aggregating human judgements, we face similar challenge when aggregating classifiers' predictions in machine learning. For example, we have a deep learning (Goodfellow et al., 2016) classification model which performs the best among multiple models when used in the ensemble method. For some data point, the classification result of this deep learning model may be the correct minority. In this situation, applying majority voting leads to wrong answers.

We aim to complement the literature via studying whether we can aggregate classifiers better than majority voting even when majority opinion is wrong. We also target a method that can operate over each data point separately without assuming homogeneous assumptions across a massive dataset.

The question sounds unlikely to resolve at a first look, but we are inspired by the seminal work Bayesian Truth Serum (BTS) (Prelec, 2004; Prelec et al., 2017) which approached this question in the setting of incentivizing and aggregating truthful human judgements. The core idea behind BTS is simple and elegant: the correctness of an answer does not rely on its popularity, but rather whether it is "surprisingly" popular or not -here an answer that has a higher posterior (computed from reports of the crowds) than its prior is taken as being "surprisingly" popular, and should be considered as the true answer. This argument has a very intuitive Bayesian reasoning: the signal that improves over its prior is more likely to be informative. Prelec et al. (2017) also argued that via eliciting a peer prediction information, which is defined as the fraction of "how many other people would agree with you" from each agent, he will be able to construct an informative prior to compare with the majority vote posterior aggregation. BTS operates over each single question separately, without seeing a large number of similar tasks (in order to leverage a certain homogeneity assumption).

In this paper, we make a connection between these two seemingly irrelevant topics, and extend the key idea in Bayesian Truth Serum to aggregating classifiers' predictions. The challenge is that we would not be able to elicit a belief from a classifier on "how many other classifiers would agree with themselves", which renders the task of computing the prior difficult. We proposed two machine learning aided algorithms to mimic the procedure of reporting the peer prediction information, which we jointly name as Machine Truth Serum (MTS). We firstly propose Heuristic Machine Truth Serum (HMTS). In HMTS, we pair each baseline classifier (an agent) with a regressor model, which is trained to predict the peer prediction information using a processed training dataset. With the predictions from the regressors, we will be able to apply the idea of BTS to decide on whether to adopt the minority as the answer via comparing the prior (computed using the regressor) and the posterior for each label. Then we proposed Discriminative Machine Truth Serum (DMTS). In DMTS, we directly train one classifier to predict whether adopting the minority as the answer or not. As for the training complexity of our algorithm, the training time of HMTS is linear in the number of label classes because of the training of extra regressors. DMTS will only need to train one additional classifier and both the training and the running time are almost the same as the basic majority voting algorithm. Therefore our proposed methods are very practical to implement and run.

Our contributions summarize as follows: (1) We propose Heuristic Machine Truth Serum (HMTS) and Discriminative Machine Truth Serum (DMTS) to complement ensemble methods, which can detect when minority should be considered the final prediction instead of the majority. (2) Our experiments over 6 binary and 6 multiclass classification real-world datasets reveal promising results of our approach in improving over majority voting. Our proposed methods also outperform popular ensemble algorithms. (3) To pair with our experimental results, we also provide analytical evidences for the correctness of our proposed approaches. (4) Our approaches can be generically applied in ensemble methods to replace simple majority voting rules.

The rest of the paper is organized as follows. Section 2 introduces some related works. Section 3 reviews preliminaries and BTS. Section 4 introduces our Machine Truth Serum approaches. Section 5 presents our experimental results. Section 6 concludes our paper.

2. RELATED WORK:

Wisdom of the crowd (Surowiecki, 2005) are often considered as being more accurate than a few elite individuals in applications including decision making of public policy (Morgan, 2014), answering the questions on general world knowledge (Singh et al., 2002) , and so on. Typical algorithms for extracting wisdom of the crowd are based on majority voting, and the assumption that the majority opinion is more likely to be correct (Surowiecki, 2005) . There is another line of machine learning works on proposing inference methods, including Expectation Maximization method (Raykar et al., 2010; Zhang et al., 2014) , Variational Inference (Liu et al., 2012; Chen et al., 2015) , and Minimax Entropy Inference (Zhou et al., 2012; 2014) to crowdsourcing settings, aiming to uncover the true labels from the noisy labels provided by non-expert crowdsourcing workers. Most relevant to us, (Prelec, 2004; Prelec et al., 2017) proposed a Bayesian Truth Serum method to extract the subjective judgment of minority expert by collecting not only people's judgements but also how many percentage of the population share the same opinion.

In machine learning, ensemble methods combining multiple learning algorithms usually performs better than any single method (Dietterich, 2000) . Ensemble methods consist of a rich family of algorithms. For instance, AdaBoost (Freund & Schapire, 1997) and Random Forest (Ho, 1995) are two different and commonly used ones. AdaBoost tries to optimize weighted voting outcomes, while Random Forest train and test using the majority voting rule. But these popular ensemble methods will be wrong when the minority is the correct answer.

In both the setting of aggregating human judgements and classifiers' predictions, most works, except for (Prelec, 2004) , would fail when the majority opinion is instead likely to be wrong. But BTS only works in the setting of aggregating human judgements by collecting subjective judgment data. Based on the ideas proposed by Prelec (2004) and Prelec et al. (2017) , we proposed two machine learning aided algorithms to find the correct answer when it is minority instead of majority in the setting of classifiers' predictions. As our proposed methods are machine learning algorithms, they can be trained and the predictions will be made automatically instead of collecting subjective judgment data as the case in (Prelec, 2004) .

3. PRELIMINARY:

In this paper, we consider both binary and multiclass classification problems. Nonetheless, for simplicity of demonstration, our main presentation focuses on binary classification. A multi-class extension of our method is presented in Section 4.3.

Suppose that we have a training dataset:

D := {(x i , y i )} N i=1 and a test dataset T := {(x i , y i )} T i=1 , where x i ∈ X ⊆ R d is a d-dimensional vector. We have K baseline classifiers F := {f 1 , f 2 , ..., f K : X → {0, 1}}

that map each feature vector to a binary classification outcome. Ensemble method such as boosting algorithms can combine {f 1 , f 2 , ..., f K } to get better prediction results than each single one. For instance, Random Forest first applies the bootstrap aggregating to train multiple different decision trees to correct overfitting problems of decision trees. After training, the majority rule will be applied to generate the prediction result.

The above dependence on the majority voting rule is ubiquitous in ensemble methods. The key assumption of using the majority rule is that the majority is more likely to be correct than random guessing. Denoting as Maj({f 1 (x), f 2 (x), ..., f K (x)}) the majority answer from the K classifiers, formally, most, if not all, methods require that P (Maj({f 1 (x), f 2 (x), ..., f K (x)}) = y) < 0.5. Our goal is still to construct a single aggregator A({f 1 , f 2 , ..., f K }) that takes the classifiers' predictions on each data point as inputs and generates an accurate aggregated prediction. But we aim to provide instruction to cases where it is possible that P (Maj({f 1 (x), f 2 (x), ..., f K (x)}) = y) > 0.5. The challenge is to detect when the minority population has the true answer.

3.1 BAYESIAN TRUTH SERUM (Prelec, 2004) considers the following human judgement elicitation problem: There are a set of agents denoted by {a i } K i=1 . The designer aims to collect subjective judgement from each agent about an unknown event y ∈ {0, 1} and aggregate accordingly. Each of the agent i needs to report his own predicted label l i ∈ {0, 1} for y, and the percentage of other agents he believes will agree with him p i ∈ [0, 1]. We will also call this second belief information as the peer prediction information.

Denote the belief of agent i as B i . p i is defined as follows:

p i = E Bi j =i 1(lj=li) K-1 .

We, as the designer, obtain the prediction labels {l i } K i=1 and the percentage information {p i } K i=1 from all the agents. The posterior for each label is defined as the actual percentage of this label which can be easily calculated utilizing the prediction results: (for label 1)

Posterior(1) = i 1(l i = 1) K (1)

In (Prelec, 2004; Prelec et al., 2017) , Prelec et al. promote the idea of using the average predicted percentage of the responding label as the approximation of the priors: (for label 1).

Prior(1) = K i=1 p 1(li=1) i • (1 -p i ) 1-1(li=1) K (2)

If Posterior(1) > Prior(1), label 1 will be taken as the surprisingly more popular answer, which should be considered as the true answer ŷ, even though it might be in minority's hands. The same rule is applied to label 0. Formally, if we denote ŷ as the aggregated answer:

EQUATION

The rest of the paper will focus on generalizing the above idea to aggregate classifiers' predictions.

4. MACHINE TRUTH SERUM:

In this section, we introduce Machine Truth Serum (MTS). Suppose we have access to a set of baseline classifiers. Each classifier can be treated as an agent. We'd like to build a BTS-ish aggregation method to aggregate the classifiers' predictions. The challenge is to compute the priors from the classifiersmachine-trained classifiers do not encode beliefs as human agents do, so we cannot elicit the peer prediction information from them directly. We propose two machine learning aided approaches to perform the generation of this peer prediction information. We firstly introduce two MTS approaches for binary classification and then extend these approaches to multiclass classification case.

4.1. HEURISTIC MACHINE TRUTH SERUM:

We first introduce heuristic machine truth serum (HMTS). The high level idea is to train a regression model for each classifier to predict the percent of the agreement from other classifiers on the prediction of each particular data point. After getting the predicted labels and the predicted peer prediction information of the classifiers, we can again approximate the priors using the predicted peer prediction information for each classifier, compute the average and compare it to posterior. In this part, HMTS for binary classification will be introduced firstly and its multiclass extension is stated in Section 4.3.

Given the training data D = {(x i , y i )} N i=1 and multiple classifiers {f j } K j=1 , we first try to compute the j-th classifier's "belief" of the fraction of other classifiers that would "agree" with it. Denote this number as ȳj i for each training sample (x i , y i ). ȳj i can be computed as follows:

EQUATION

By above, we have pre-processed the training data to obtain D H j := {(x i , ȳj i )} N i=1 , j = 1, ..., K, which can serve as the training data to predict the peer prediction information of classifier j (again to recall, peer prediction information is the fraction of other classifiers that classifier j believes would agree with it). We then train peer prediction regression models {g j } K j=1 on D H j := {(x i , ȳj i )} N i=1 , j = 1, ..., K respectively to map x i to ȳj i . We consider different class labels and will first train two regression models: g j,0 and g j,1 are two belief regression models of classifier j and trained on the examples whose predicted labels are 0s (D H j,0 := {(x i , ȳj i ) :

f j (x i ) = 0} N i=1 ) and 1s (D H j,1 := {(x i , ȳj i ) : f j (x i ) = 1} N i=1

) respectively. Then compute the following prior of label 1 for each x i :

EQUATION

After obtaining these peer prediction regression models g j s, the prior and posterior of (x i , y i ) ∈ T in the test dataset are then calculated by,

Prior(x i , l = 1) := j g j (x i ) K (6) Posterior(x i , l = 1) := j 1(f j (x i ) = 1) K (7)

Algorithm 1 Heuristic Machine Truth Serum (Binary classification) Require:

1: Input: 2: D = {(x 1 , y 1 ), ..., (x N , y N )}: training data 3: T = {(x 1 , y 1 ), ..., (x T , y T )}: testing data 4: F = {f 1 , ..., f K }: classifiers Procedure:

5: Train K classifiers (F) on the training data 6: for j = 1 to K do 7:

for i = 1 to N do 8:

Compute ȳj i according to Eqn.(4) 9:

end for 10:

Train machine belief g j,0 , g j,1 on training dataset D H j := {(x i , ȳj i )} N i=1 . 11: end for 12: for t = 1 to T do 13:

Compute Prior(x i , l = 1) and Posterior(x i , l = 1) according to Eqn.( 6) and Eqn. (7) 14:

if Prior(x i , l = 1) < Posterior(x i , l = 1) then 15:

Output "surprising" answer 1 as the final prediction.

16: else if Prior(x i , l = 1) > Posterior(x i , l = 1) then 17:

Output "surprising" answer 0 as the final prediction.

18::

end if 19: end for If Prior(x i , l = 1) < Posterior(x i , l = 1), the "surprsing" answer 1 will be considered as the true answer. The decision rule is similar for label 0. The procedure is illustrated in Algorithm 1.

4.2. DISCRIMINATIVE MACHINE TRUTH SERUM:

The Heuristic Machine Truth Serum above relies on training models to predict the peer prediction information for each classifier (which will be used to compute the priors) and compare them to the posteriors, and then decide on whether to follow the minority opinion or not. We notice the above task of determining whether to follow the minority or not is also a binary classification question. We can therefore utilize a classification model to directly predict for each data point whether the minority should be chosen as the answer or not.

We propose Discriminative Machine Truth Serum (DMTS). Again, DMTS for binary classification will be introduced firstly and its multiclass extension is stated in Section 4.3. With DMTS, a new training dataset D D := {x i , ŷi } N i=1 about whether considering the minority as the final answer or not is constructed. Each data D D := (x i , ŷi ), for i = 1, ..., N , in this new training dataset is calculated as follows: for each (x i , y i ) ∈ D ŷi = 1 if majority of F on x i is different from the true label; 0 if majority of F on x i is same as the true label.

Now with above preparation, predicting whether majority is correct or not becomes a standard classification problem on D D := {x i , ŷi } N i=1 . This is readily solvable by applying standard techniques. In our experiments, we will mainly use a Multi-Layer Perceptron (MLP) (Goodfellow et al., 2016) denoted as f . f is trained on this new training dataset and can directly predict whether we should adopt the minority as the answer or not. f does not restrict to MLP and can be other classifiers. We have tried several other methods, such as logistic regression, and similar conclusions are obtained. The procedure is further illustrated in Algorithm 2 in Appendix A.3.

4.3. MULTICLASS EXTENSION OF HMTS AND DMTS:

HMTS and DMTS can be extended to multiclass classification problem with the same ideas by modifying them accordingly. In the multiclass case, l ∈ C = {0, 1, ..., L} is denoted as the class label of the dataset. Consider HMTS first. For each classifier j, we need to consider different class labels of regression models {g j,l }, where l ∈ C = {0, 1, ..., L}. g j,l is the belief regression model of classifier j and trained on the examples whose predicting labels are ls.

Again compute the following prior for each x:

EQUATION

where ratio l = g j,l (xi) c∈C:c =f j (x i ) gj,c(xi) is defined as the ratio of the l's belief to the summation of all the other classes' beliefs except for the predicted class utilizing majority rule.

In HMTS, Eqn. ( 6) and ( 7) can be modified to the following:

Prior(x i , l = c) := K j=1 g * j,c (x i ) K (10) Posterior(x i , l = c) := K j=1 1(f j (x i ) = c) K (11)

We then compute all the priors and posteriors of each class label based on Eqn. ( 10) and ( 11). It is possible that there exist more than one class labels whose posterior is larger than its prior. We define the set containing all these label classes as

C sat = {c | Prior(x i , l = c) < Posterior(x i , l = c), c ∈ C}.

We predict the class label which has the biggest improvement from its prior to posterior:

argmax c∈Csat Posterior(x i , l = c) -Prior(x i , l = c) .

In DMTS, firstly we need to train a model that decides whether to apply the minority as the final answer which are very similar to the binary case. The difference is that we will then choose the minority answer as the predicted answer instead of using majority if i) it has the most votes in the minority answers and ii) the prediction result of classifier obtained in the training phase is 1 (we should use minority).

4.4. THEORETICAL ANALYSIS:

We conduct a formal analysis about the correctness of our proposed algorithms. Not surprisingly, the key ideas of the proofs are adapted from the proof for BTS (Prelec et al., 2017) . For simplicity, we only present the theorems for binary classification. The proofs of multiclass ones are similar to the binary case. The details of proofs are left to the Appendix A.1.

To set up for presenting the theorems, we restate our problem: we assume that each x i can take on any value in the discrete set {s 1 , ..., s m } for the simplicity of proof. In practice, conceptually each feature vector can be represented by an assigned (large-enough) categorical number. One can consider s k (k = 1, 2, , , m) as a code for each feature vector. The proof based on continuous value can be deduced similarly.

Here we have two worlds w io (o = 0 or 1) of different class labels for any x i . One world is actual, the other one is counterfactual. If we say w i1 is the actual world for x i , it means the predicting answer of x i in this world is 1 and y = 1 is also the ground truth label of x i . w i0 is the counterfactual world and the predicting answer of x i in this world is 0. In this paper, we are considering infinite samples. While finite samples is practical setting, it is important to first analyze and conclude some deductions in the infinite sample ideal case. Theorem 4.2. For any x i , the average estimate of the prior prediction for the correct classification answer will be underestimated if not every classifier provides the correct classification prediction. Therefore, the minority should be the final answer instead of the majority if the prior (estimated prediction) is less than the posterior.

Theorem 1 indicates that exclusively posterior probabilities based methods such as majority voting can not infer the true answer for all the time. In Theorem 2, the posterior and prior are the prediction distribution of other classifiers for each classifier -both are provided by our proposed MTS algorithms.

Complexity For HMTS, for example in our experiments, another 15 • (L + 1) (label classes {0, 1, ..., L}) simple regressors will be trained to predict others' beliefs based on 15 baseline classifiers.

So the total training time is linear in the number of label classes. After training the extra regressors, running the algorithm only requires taking L + 1 averages (15 of the 15 • (L + 1) regressors each) and compare with average posterior. DMTS will only need to train one additional classifier based on 15 classifiers and both the training and the running time are almost the same as the basic majority voting algorithm. The above complexity analysis shows our methods are very practical.

5. EXPERIMENTS:

In this section, we present our experimental results. Particularly we test our proposed two MTS algorithms on 6 binary and 6 multiclass real-world classification datasets. Experimental results show that consistently better classification accuracy can be obtained compared to always trusting the majority voting outcomes.

5.1. DATASETS:

In this section, 6 binary and 6 multiclass classification benchmark datasets (Pang & Lee, 2004 ) are used to conduct the experiments. The statistical information of these datasets are described in Table 4 in Appendix A.2. In this paper, each of the datasets we used has a small size -we chose to focus on the small data regime where the classifiers are likely to make mistakes. This is a better fit to our setting where majority opinion can be wrong with a good chance. For the splitting of training and testing, we used the original setting for the datasets providing training and testing files separately. For other datasets, only one data file is given. For the testing results' statistical significance, more data is distributed to testing dataset and 50/50 is considered as the splitting of training and testing.

5.2. EXPERIMENTAL SETUP AND RESULTS:

Table 1 : Overall accuracy and the number of increased correct predictions in the "high disagreement" cases of Uniformly-weighted Majority Voting, HMTS, and DMTS on the 6 binary classification datasets. The "high disagreement" means that the difference between the number of predicting 0 and 1 is small. We have 15 classifiers and the instance will be considered as having "high disagreement" if the vote number of majority class is 8 or 9. In HMTS, the numbers of "high disagreement" instances we consider in 6 datasets are 51, 52, 37, 149, 43, 45. As for DMTS, the numbers are 30, 64, 37, 76, 13, 38 . The results having the highest accuracy for each dataset are highlighted. In our binary classification experiments, we consider 5 commonly used binary classification algorithms which are Perceptron (Rosenblatt, 1958) , Logistic Regression (LR) (Peng et al., 2002) , Random Forest (RF), Support Vector Machine (SVM) (Chang & Lin, 2011) , and MLP. In order to test the usefulness of our methods, we experiment with a noisy environment -we flipped the true class label with three noisy rates to construct three binary classifiers for each of the 5 methods which have mediocre performance on the test datasets. We wanted to diversify our classifiers by introducing different noisy rates (varying the data distribution). Our experiments used 0.06, 0.08, and 0.1 (probability of flipping the label) for each family of classifier. We also tried other values such as 0.1, 0.2, and 0.3, and we reached similar conclusions. In total, 15 different classifiers are obtained as the baseline classifiers.

The experimental results on the 6 binary classification datasets are reported in Table 1 . From these results, we observe that Heuristics Machine Truth Serum (HMTS) tends to have more robust and better performances than Discriminative Machine Truth Serum (DMTS) in most datasets, especially in the small-size datasets. These can be explained by the fact DMTS itself is a MLP classifier which Under review as a conference paper at ICLR 2020 needs a larger size of data to get good results. That HMTS can improve the classification accuracy in the small size of dataset is particularly useful in some fields such as healthcare in which collecting data is very time-consuming and expensive. As for the running time, DMTS is faster than HMTS as HMTS needs to compute the peer prediction results of all the 15 classifiers and DMTS only predicts once.

Table 2 : Overall accuracy and the number of increased correct predictions in the "high disagreement" cases of Uniformly-weighted Majority voting, HMTS, and DMTS on the 6 multi-class classification datasets. We have 15 classifiers and the instance will be considered as having "high disagreement" if the vote number of majority class is less or equals to 6 for the 3-class and 4-class datasets. The threshold number is 5 for 6-class and 3 for 10-class datasets. In HMTS, the numbers of "high disagreement" instances we consider in 6 datasets are 61, 54, 27, 65, 15, 157 We also tested our extension to multi-class classification problems. Experimental results on 6 multiclass classification datasets are reported in Table 2 . We observe that HMTS and DMTS obtained similarly good performance in the accuracy metric because the size of multi-class classification datasets is larger and the MLP of DMTS can perform better than the binary case. Finally, we compare between several popular ensemble algorithms and our proposed approaches. We list the testing accuracy for Adaboost with 15 decision tree base estimators, Random Forest with 15 decision trees, Weighted Majority (Germain et al., 2015) , Stacking with the same setting of 15 classifiers utilized in our two MTS algorithms and Logistic Regression or SVM as meta classifier, HMTS, and DMTS for all 12 datasets in Table 3 . As shown in the table, HMTS and DMTS outperform Adaboost, Random Forest, Weighted Majority, and Stacking in 8 datasets and are very close to the best in 3 datasets. An outlier dataset is Wall-Following and we found that decision tree based methods can get perfect performance on it. Compared to other weighted methods, we'd like to note that our aggregation operates on each single task separately -this means that our method will be more robust when the difficulty levels of tasks differ drastically in the dataset. None of the other weighted methods (with fixed and learned weights) has this feature. We also find that our method is robust to a smaller number of classifiers, in contrast to, say Adaboosting.

6. DISCUSSION AND CONCLUDING REMARKS:

This paper proposes two machine learning aided methods HMTS and DMTS to detect when the minority should be the final answer instead of majority. Our experiments over 6 binary and 6 multiclass real-world datasets show that better classification performance can be obtained compared to always trusting the majority voting. Our proposed methods also outperform popular ensemble algorithms on three randomly selected datasets and can be generically applied as a subroutine in ensemble methods to replace majority voting. For future work, we plan to try more types of classifiers, especially the recent deep learning models, to train the belief models for baseline classifiers and apply our methods to more real-world datasets. 1: Input: 2: D = {(x 1 , y 1 ), ..., (x N , y N )}: training data 3: T = {(x 1 , y 1 ), ..., (x T , y T )}: testing data Procedure:

4: for i = 1 to N do Predict with the minority answer. 

:



Figures and Tables:

Theorem 4.1. No algorithm exists for deducting the correct classification answer relying exclusively on feature vector distribution of true class label, P (s k |y o * ), k = 1, ..., m and correctly computed posterior distribution over all possible classification labels given feature vectors, P (y o |s k ), k = 1, ..., m, o = 0, 1 for any x i . o * is the true class label.

DMTS classifier f on the dataset {x i , ŷi } N i=1 8: for t = 1 to T do 9:Compute the classification result y t := f (x t )

. As for DMTS, the numbers are48, 45, 25, 81, 25, 40. The results having the highest accuracy for each dataset are highlighted.

Table content: <table><tr><td>Datasets</td><td>Abalone</td><td>Waveform</td><td>Wall-Following</td><td>Statlog</td><td>Optical</td><td>Pen-Based</td></tr><tr><td># of class</td><td>3</td><td>3</td><td>4</td><td>6</td><td>10</td><td>10</td></tr><tr><td>Majority</td><td>51.25%</td><td>85.04%</td><td>90.22%</td><td>86.70%</td><td>97.50%</td><td>95.08%</td></tr><tr><td colspan="7">HMTS 51.45% (+4/61) 85.48% (+11/54) 90.26% (+1/27) 87.10% (+8/65) 97.61% (+2/15) 95.57% (+17/157)</td></tr><tr><td colspan="7">DMTS 51.40% (+3/48) 85.60% (+14/45) 90.59% (+10/25) 86.75% (+1/81) 97.66% (+3/25) 95.51% (+15/40)</td></tr></table>

Comparison between popular ensemble and our proposed approaches

Table content: <table><tr><td>Methods</td><td>Adaboost</td><td>Random Forest</td><td>Weighted Majority</td><td colspan="2">Stacking HMTS</td><td>DMTS</td></tr><tr><td>Breast Cancer</td><td>94.37%</td><td>94.37%</td><td>94.01%</td><td colspan="3">94.72% 96.13% 94.01%</td></tr><tr><td>Hill Valley</td><td>62.05%</td><td>57.93%</td><td>53.30%</td><td colspan="3">62.38% 81.69% 81.03%</td></tr><tr><td>Movie Review</td><td>75.10%</td><td>77.20%</td><td>81.60%</td><td>70.30%</td><td colspan="2">80.85% 80.60%</td></tr><tr><td>Spambase</td><td>74.74%</td><td>74.65%</td><td>74.17%</td><td>75.91%</td><td colspan="2">76.87% 77.35%</td></tr><tr><td>Australian</td><td>82.03%</td><td>84.06%</td><td>84.06%</td><td colspan="3">85.22% 83.44% 82.94%</td></tr><tr><td>German</td><td>72.20%</td><td>74.80%</td><td>73.80%</td><td colspan="3">77.20% 77.20% 76.20%</td></tr><tr><td>Abalone</td><td>48.70%</td><td>54.25%</td><td>55.35%</td><td>54.55%</td><td colspan="2">51.45% 51.40%</td></tr><tr><td>Waveform</td><td>81.80%</td><td>82.60%</td><td>85.36%</td><td>84.00%</td><td colspan="2">85.48% 85.60%</td></tr><tr><td>Wall-Following</td><td>99.00%</td><td>95.22%</td><td>95.37%</td><td>89.07%</td><td colspan="2">90.26% 90.59%</td></tr><tr><td>Statlog</td><td>85.85%</td><td>86.15%</td><td>86.85%</td><td>82.70%</td><td colspan="2">87.10% 86.75%</td></tr><tr><td>Optical</td><td>93.99%</td><td>94.88%</td><td>92.21%</td><td>95.83%</td><td colspan="2">97.61% 97.66%</td></tr><tr><td>Pen-Based</td><td>94.97%</td><td>95.45%</td><td>90.59%</td><td colspan="3">95.43% 95.57% 95.51%</td></tr></table>

Statistics of 6 binary and 6 multiclass classification datasets

Table content: <table><tr><td>Data set</td><td colspan="6">Breast cancer Movie Review German Australian Hill Valley Spambase</td></tr><tr><td># of Inst.</td><td>569</td><td>1000</td><td>1000</td><td>690</td><td>606</td><td>4601</td></tr><tr><td># of Attr.</td><td>30</td><td>77</td><td>24</td><td>14</td><td>100</td><td>57</td></tr><tr><td>% of Maj.</td><td>62.7%</td><td>50%</td><td>70.0%</td><td>67.8%</td><td>50.7%</td><td>60.6%</td></tr><tr><td>Data set</td><td colspan="6">Abalone Waveform Wall-Following Stalog landsat Optimal Pen-Based</td></tr><tr><td># of Inst.</td><td>4177</td><td>5000</td><td>5456</td><td>4435</td><td>3823</td><td>7494</td></tr><tr><td># of Attr.</td><td>8</td><td>21</td><td>24</td><td>36</td><td>62</td><td>16</td></tr><tr><td>% of Maj.</td><td>34.6%</td><td>33.9%</td><td>40.4%</td><td>24.2%</td><td>10.2%</td><td>10.4%</td></tr><tr><td colspan="5">Algorithm 2 Discriminative Machine Truth Serum (Binary classification)</td><td/><td/></tr><tr><td>Require:</td><td/><td/><td/><td/><td/><td/></tr></table>

Peer review (iclr2020):
Update after author response: I would like to thank the authors for the thoughtful response, and for addressing several of the concerns raised by the reviewers. The updated draft look cleaner and conveys the value of the proposal better. I am changing my assessment to *6: Weak Accept* (the smallest jump from 3 is to 6 in the portal. I would choose a 5 if that was possible). My concerns for the significance of results and lack of a baseline that takes worker quality into account still stand, but the results look better and the authors make a more convincing case prompting me to change my rating. --------------------------- In this paper, the authors propose a way to measure a notion of surprise (disparity between prior and posterior) and using that as a classification rule. So, if the posterior for a class is larger than its prior, the method outputs that class label. In order to estimate the average prior for a pool of models, the method recommends building additional models to predict these “peer-priors”, whereas the posterior is simply estimated by a maximum likelihood model (P(y=1) = Indicator(y=1)/K). The authors also propose a variant that directly tries to predict when the majority answer might be wrong. The authors show that such methods can do better than majority voting and some ensemble methods on a few datasets. The paper looks at an interesting problem of when a majority vote response might be wrong by extending the notion of surprise previously defined for human labelers to machine learning models. The strong points of the paper: 1. Simple and interpretable extension of a previously studied method. 2. The method can be plugged into existing frameworks to replace majority voting. 3. The results on the datasets considered seem good. Here are some of my concerns: 1. The baseline of majority voting is fairly weak, since there are several models that take worker quality into account when aggregating responses. For example, the classic Dawid-Skene (1979) model. It’s not very promising to see a model just beat majority voting. 2. The presentation of results in Table 1 and 2 can be improved. Even though it’s good to know how many predictions were corrected, it will also be good to see the overall accuracy numbers (like the ones Table 3). 3. DMTS doesn’t really have the same underlying machinery as HMTS, since it doesn’t operate on the surprise measure, and putting them together in the same paper dilutes the focus. 4. What are the weights in the weighted majority? 5. The results in Table 3 show that HMTS is better than other ensemble methods but only marginally. Since HMTS uses more complex intermediate models (MLPs), I am not convinced whether the small improvement is from the proposed method or just more expressive models. For example, what would happen if the base classifiers in Adaboost were MLPs? 6. How is minority defined in multi-class scenario? 7. Minor formatting and grammatical issues: “likely to the correct”, “majority is tending to be correct”, “seemingly irrelevant topics”, “whether adopting the minority”, “aim to provide instruction to cases”, “linear regression” (should be “logistic regression” since it’s a classifier), and so on. In summary, I think the paper has an interesting approach to an important problem, but with results that are only marginally convincing. I would have liked to see a more thorough empirical investigation to clearly establish the value of the proposed method. Based on these observations, I think the paper misses the mark and is slightly below the acceptance threshold for me.