New Bounds on the Accuracy of Majority Voting for Multi-Class
  Classification
Sina Aeeneh Nikola Zlatanov Jiangshan Yu
Majority voting is a simple mathematical function that returns the value that
appears most often in a set. As a popular decision fusion technique, the
majority voting function (MVF) finds applications in resolving conflicts, where
a number of independent voters report their opinions on a classification
problem. Despite its importance and its various applications in ensemble
learning, data crowd-sourcing, remote sensing, and data oracles for
blockchains, the accuracy of the MVF for the general multi-class classification
problem has remained unknown. In this paper, we derive a new upper bound on the
accuracy of the MVF for the multi-class classification problem. More
specifically, we show that under certain conditions, the error rate of the MVF
exponentially decays toward zero as the number of independent voters increases.
Conversely, the error rate of the MVF exponentially grows with the number of
independent voters if these conditions are not met.
  We first explore the problem for independent and identically distributed
voters where we assume that every voter follows the same conditional
probability distribution of voting for different classes, given the true
classification of the data point. Next, we extend our results for the case
where the voters are independent but non-identically distributed. Using the
derived results, we then provide a discussion on the accuracy of the truth
discovery algorithms. We show that in the best-case scenarios, truth discovery
algorithms operate as an amplified MVF and thereby achieve a small error rate
only when the MVF achieves a small error rate, and vice versa, achieve a large
error rate when the MVF also achieves a large error rate. In the worst-case
scenario, the truth discovery algorithms may achieve a higher error rate than
the MVF. Finally, we confirm our theoretical results using numerical
simulations.