Year: 2019

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.

heading: 1 INTRODUCTION
text: 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.

heading: 2 RELATED WORK
text: 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).

heading: 3 PRELIMINARY
text: 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 := {(xi, yi)}Ni=1 and a test dataset T := {(xi, yi)}Ti=1, where xi ∈ X ⊆ Rd is a d-dimensional vector. We have K baseline classifiers F := {f1, f2, ..., fK : X → {0, 1}} that map each feature vector to a binary classification outcome. Ensemble method such as boosting algorithms can combine {f1, f2, ..., fK} 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({f1(x), f2(x), ..., fK(x)}) the majority answer from the K classifiers, formally, most, if not all, methods require that P (Maj({f1(x), f2(x), ..., fK(x)}) 6= y) < 0.5. Our goal is still to construct a single aggregator A({f1, f2, ..., fK}) 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({f1(x), f2(x), ..., fK(x)}) 6= y) > 0.5. The challenge is to detect when the minority population has the true answer.

heading: 3.1 BAYESIAN TRUTH SERUM
text: (Prelec, 2004) considers the following human judgement elicitation problem: There are a set of agents denoted by {ai}Ki=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 li ∈ {0, 1} for y, and the percentage of other agents he believes will agree with him pi ∈ [0, 1]. We will also call this second belief information as the peer prediction information.
Denote the belief of agent i as Bi. pi is defined as follows: pi = EBi (∑ j 6=i 1(lj=li) K−1 ) .
We, as the designer, obtain the prediction labels {li}Ki=1 and the percentage information {pi}Ki=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(li = 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− pi)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 ŷ, even though it might be in minority’s hands. The same rule is applied to label 0. Formally, if we denote ŷ as the aggregated answer:
ŷ = { 1 if Prior(1) < Posterior(1); 0 if Prior(1) > Posterior(1). (3)
The rest of the paper will focus on generalizing the above idea to aggregate classifiers’ predictions.

heading: 4 MACHINE TRUTH SERUM
text: 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 classifiers - machine-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.

heading: 4.1 HEURISTIC MACHINE TRUTH SERUM
text: 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 = {(xi, yi)}Ni=1 and multiple classifiers {fj}Kj=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 ȳji for each training sample (xi, yi). ȳ j i can be computed as follows:
ȳji =
∑ j 6=k 1(fj(xi) = fk(xi))
K − 1 , (4)
By above, we have pre-processed the training data to obtain DHj := {(xi, ȳ j i )}Ni=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 {gj}Kj=1 onDHj := {(xi, ȳ j i )}Ni=1, j = 1, ...,K respectively to map xi to ȳ j i . We consider different class labels and will first train two regression models: gj,0 and gj,1 are two belief regression models of classifier j and trained on the examples whose predicted labels are 0s (DHj,0 := {(xi, ȳ j i ) : fj(xi) = 0}Ni=1) and 1s (DHj,1 := {(xi, ȳji ) : fj(xi) = 1}Ni=1) respectively. Then compute the following prior of label 1 for each xi:
gj(xi) = { gj,1(xi) if fj(xi) = 1; 1− gj,0(xi) if fj(xi) = 0. (5)
After obtaining these peer prediction regression models gjs, the prior and posterior of (xi, yi) ∈ T in the test dataset are then calculated by,
Prior(xi, l = 1) :=
∑ j gj(xi)
K (6)
Posterior(xi, l = 1) :=
∑ j 1(fj(xi) = 1)
K (7)
Algorithm 1 Heuristic Machine Truth Serum (Binary classification) Require:
1: Input: 2: D = {(x1, y1), ..., (xN , yN )}: training data 3: T = {(x1, y1), ..., (xT , yT )}: testing data 4: F = {f1, ..., fK}: 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 ȳji according to Eqn.(4) 9: end for 10: Train machine belief gj,0, gj,1 on training dataset DHj := {(xi, ȳ j i )}Ni=1. 11: end for 12: for t = 1 to T do 13: Compute Prior(xi, l = 1) and Posterior(xi, l = 1) according to Eqn.(6) and Eqn.(7) 14: if Prior(xi, l = 1) < Posterior(xi, l = 1) then 15: Output “surprising” answer 1 as the final prediction. 16: else if Prior(xi, l = 1) > Posterior(xi, l = 1) then 17: Output “surprising” answer 0 as the final prediction. 18: end if 19: end for
If Prior(xi, l = 1) < Posterior(xi, 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.

heading: 4.2 DISCRIMINATIVE MACHINE TRUTH SERUM
text: 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 DD := {xi, ŷi}Ni=1 about whether considering the minority as the final answer or not is constructed. Each data DD := (xi, ŷi), for i = 1, ..., N , in this new training dataset is calculated as follows: for each (xi, yi) ∈ D
ŷi = { 1 if majority of F on xi is different from the true label; 0 if majority of F on xi is same as the true label. (8)
Now with above preparation, predicting whether majority is correct or not becomes a standard classification problem on DD := {xi, ŷi}Ni=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.

heading: 4.3 MULTICLASS EXTENSION OF HMTS AND DMTS
text: 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 {gj,l}, where l ∈ C = {0, 1, ..., L}. gj,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 xi
g∗j,l(xi) = { gj,l(xi) if fj(xi) = l;( 1− gj,fj(xi)(xi) ) · ratiol if fj(xi) 6= l,
(9)
where ratiol = gj,l(xi)∑
c∈C:c 6=fj(xi) 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(xi, l = c) :=
∑K j=1 g ∗ j,c(xi)
K (10)
Posterior(xi, l = c) :=
∑K j=1 1(fj(xi) = 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
Csat = {c | Prior(xi, l = c) < Posterior(xi, l = c), c ∈ C}. We predict the class label which has the biggest improvement from its prior to posterior:
argmaxc∈Csat ∣∣Posterior(xi, l = c)− Prior(xi, 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).

heading: 4.4 THEORETICAL ANALYSIS
text: 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 xi can take on any value in the discrete set {s1, ..., sm} for the simplicity of proof. In practice, conceptually each feature vector can be represented by an assigned (large-enough) categorical number. One can consider sk(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 wio (o = 0 or 1) of different class labels for any xi. One world is actual, the other one is counterfactual. If we say wi1 is the actual world for xi, it means the predicting answer of xi in this world is 1 and y = 1 is also the ground truth label of xi. wi0 is the counterfactual world and the predicting answer of xi 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.1. No algorithm exists for deducting the correct classification answer relying exclusively on feature vector distribution of true class label, P (sk|yo∗), k = 1, ...,m and correctly computed posterior distribution over all possible classification labels given feature vectors, P (yo|sk), k = 1, ...,m, o = 0, 1 for any xi. o∗ is the true class label. Theorem 4.2. For any xi, 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.

heading: 5 EXPERIMENTS
text: 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.

heading: 5.1 DATASETS
text: 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.

heading: 5.2 EXPERIMENTAL SETUP AND RESULTS
text: 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
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.
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.

heading: 6 DISCUSSION AND CONCLUDING REMARKS
text: 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.

heading: A APPENDIX
text: A.1 PROOF OF THEOREMS IN SECTION 4.4
In this part, we provided the detailed proof of two theorems which are the analytical evidences for the correctness of our proposed approaches. For simplicity, we only show the proof details of binary classification. The proof of multiclass classification is similar to the binary case. This proof is largely adapted from (Prelec et al., 2017). Nonetheless we reproduce the details for completeness. Theorem A.1. No algorithm exists for inferring the correct classification answer relying exclusively on feature vector distribution of true class label, P (sk|yo∗), k = 1, ...,m and correctly computed posterior distribution over all possible classification labels given feature vectors, P (yo|sk), k = 1, ...,m, o = 0, 1 for any xi. o∗ is the true class label.
Proof. In this proof, for any arbitrarily selected class label, we can construct a world model in which this selected class label is predicted as the answer and it is also the ground truth class label. And this world model can also generate feature vector distribution of true class label and correctly computed posterior distribution over all possible classification labels given feature vectors.
Based on the description of theorem, P (sk|yo∗), k = 1, ...,m and P (yo|sk), k = 1, ...,m, o = 0, 1 are known. But we don’t know which class label is the correct answer yo∗ . We can arbitrarily selected any class label yo as the ground truth class label. In the following part, a corresponding world model Q(sk, yo) which can generate the known P (sk|yo∗) and P (yo|sk) will be constructed. Because the known parts don’t constrain the prior over the feature vector - these priors can model differences in the baseline classifiers. In particular, we can set the prior to:
Q(sk) = P (sk|yo∗) P (yo|sk) (∑ r P (sr|yo∗) P (yo|sr) )−1 , k = 1, ...,m
Because posteriors in the constructed world model must equal to known posteriors: Q(yo|sk) = P (yo|sk), for k = 1, ...,m, o = 0, 1. So we can get the joint distribution of answer yo and the feature vector sk in the constructed world model:
Q(yo, sk) = Q(yo|sk)Q(sk) = P (sk|yo∗) (∑
r
P (sr|yo∗) P (yo|sr)
)−1
Then we can get the marginal distribution yo in the constructed world by summing over k:
Q(yo) = ∑ k P (sk|yo∗) (∑ r P (sr|yo∗) P (yo|sr) )−1 = (∑ r P (sr|yo∗) P (yo|sr) )−1 After getting the marginal distributions Q(sk), Q(yo), and the matching posteriors, Q(yo|sk) = P (yo|sk), for k = 1, ...,m, the feature vector distribution of true class label in the constructed world, Q(sk|yo) can be calculated by:
Q(sk|yo) = Q(yo|sk)Q(sk)
Q(yo) = P (sk|yo∗)
Because yo was arbitrarily chosen, this theorem is proved.
Theorem 1 shows that any algorithm relying exclusively on feature vector distribution of true class label and correctly computed posterior distribution over all possible classification labels given feature vectors (e.g. majority voting) can not deduct the correct classification answer.
In the following part, we are considering the extra information which is the estimation of other classifiers’ prediction results. We use P (vo|sk) to represent the how many percentage of classifiers will predict yo given sk. We also define world classification function W (sk) = P (wo|sk). Two thresholds c0 and c1 = 1− c0 are given to make the final classification result. The classification rule is as follows:
W (sk) = { w0 if P (w0|sk) > c0; w1 if P (w1|sk) > c1.
Theorem A.2. For any xi, the average estimate of the prior prediction for the correct classification answer will be underestimated if not every classifier provides the correct classification prediction .
Proof. We first prove that the actual percentage of correctly predicted classifiers for the true answer in the actual world exceeds counterfactual world’s percentage for the true answer, P (vo∗ |wo∗) > P (vo∗ |wk), k 6= o∗. By the definition of W (sk), we can get P (wo∗ |vo∗) > co∗ , P (wo∗ |vk) < co∗ . Then we have P (wo∗ |vo∗)P (vk) > P (wo∗ |vk)P (vk). So
P (wo∗ |vo∗) > P (wo∗ |vo∗)P (vo∗) + P (wo∗ |vk)P (vk) = P (wo∗) (12) According to Bayesian rule, we have the following deduction:
P (vo∗ |wo∗) P (vo∗ |wk) = P (wo∗ |vo∗)P (wk) P (wk|vo∗)P (wo∗) = P (wo∗ |vo∗) 1− P (wo∗ |vo∗) 1− P (wo∗) P (wo∗)
(13)
Based on (12), (13) is greater than one. So P (vo∗ |wo∗) > P (vo∗ |wk), k 6= o∗ is proved. The estimate of classification prediction given the feature value sj can be computed by marginalizing the actual and counterfactual worlds, P (vo∗ |sj) = P (vo∗ |wo∗)P (wo∗ |sj) + P (vo∗ |wk)P (wk|sj). And we proved that P (vo∗ |wo∗) > P (vo∗ |wk), k 6= o∗. Therefore, P (vo∗ |sj) ≤ P (vo∗ |wo∗). It will be the strict inequality unless P (wo∗ |sj) = 1. Because some feature vectors will lead to strict inequality, the average estimate of the prior prediction will be strictly underestimated. This theorem is proved.
A.2 DATASETS
In this section, the detailed information of 6 binary and 6 multiclass classification datasets are described in Table 4. ‘#’ of Inst. stands for the number of instances. ‘#’ of Attr. stands for the number of attributes. ‘%’ of Maj stands for the percentage of majority class.
A.3 ALGORITHM 2 IN SECTION 4.2
In this part, we provided the detailed algorithm description for DMTS in Algorithm 2.
Algorithm 2 Discriminative Machine Truth Serum (Binary classification) Require:
1: Input: 2: D = {(x1, y1), ..., (xN , yN )}: training data 3: T = {(x1, y1), ..., (xT , yT )}: testing data
Procedure: 4: for i = 1 to N do 5: Compute ŷi according to Eqn.(8) 6: end for 7: Train DMTS classifier f on the dataset {xi, ŷi}Ni=1 8: for t = 1 to T do 9: Compute the classification result yt := f(xt) 10: if yt = 0 then 11: Stay with the majority answer. 12: else if yt = 1 then 13: Predict with the minority answer. 14: end if 15: end for

Review summaries:
This paper proposes two machine learning adaptations of the Bayesian truth serum approach to aggregating predictions from human experts. The first method proposed involves training two regression models for each classifier in the ensemble that predicts the proportion of other classifiers that assign the same label to a novel instance. The second approach is to train a binary classifier that, based on the features associated with an instance, determines whether the most common or second most common prediction made by individual ensemble members should be the prediction made by the ensemble.

Inspired by work in ensembling human decisions, the authors propose an ensembling technique called "Machine Truth Serum" (based off "Bayesian Truth Serum"). Instead of using majority vote to ensemble the decisions of several classifiers, this paper follows the "surprisingly popular" algorithm; the ensembled decision is the decision whose posterior probability (based on several classifiers) most exceeds a prior probability (given by classifier(s) trained to predict the posterior predictions). It's quite a nice idea to bring this finding from human decision-making to machine learning. If it worked in machine learning, it would be quite surprising, as the surprisingly popular algorithm risks that the ensemble makes a decision against the majority vote, which is usually consider the safe/default option for ensembling.