An urn model for majority voting in classification ensembles
In this work we analyze the class prediction of parallel randomized ensembles by majority voting as an urn model. For a given test instance, the ensemble can be viewed as an urn of marbles of different colors. A marble represents an individual classifier. Its color represents the class label prediction of the corresponding classifier. The sequential querying of classifiers in the ensemble can be seen as draws without replacement from the urn. An analysis of this classical urn model based on the hypergeometric distribution makes it possible to estimate the confidence on the outcome of majority voting when only a fraction of the individual predictions is known. These estimates can be used to speed up the prediction by the ensemble. Specifically, the aggregation of votes can be halted when the confidence in the final prediction is sufficiently high. If one assumes a uniform prior for the distribution of possible votes the analysis is shown to be equivalent to a previous one based on Dirichlet distributions. The advantage of the current approach is that prior knowledge on the possible vote outcomes can be readily incorporated in a Bayesian framework. We show how incorporating this type of problem-specific knowledge into the statistical analysis of majority voting leads to faster classification by the ensemble and allows us to estimate the expected average speed-up beforehand.
In this paper, the authors describe a new algorithm for dynamic ensemble pruning for classification tasks. The main idea of the algorithm is to stop querying more classifiers of an ensemble if the probability that the current classification result for one instance will coincide with the result obtained by querying all classifiers of that ensemble reaches a preset threshold. This allows to trade off classification accuracy with classification speed. In contrast to previous approaches, this algorithm models the ensemble voting process as urn problem, where each classifier is represented as one marble in the urn and its classification result is modeled as the color of this marble. Querying a subset of classifiers can then be seen as a draw without replacement from this urn. This model makes it possible for each dataset to take into account the prior distribution of class biases of the different classifiers. In their paper, the authors show that their solution is equivalent to the Statistical Instance-Based Algorithm (SIBA) when a uniform prior distribution of those class biases is assumed. Furthermore, they propose to use Monte Carlo estimation to obtain non-parametric non-uniform prior distributions and compare their algorithm with SIBA. The authors report that the disagreement rate of their algorithm is closer to the preset threshold than SIBA’s, which leads to a significant speed up, since less classifiers need to be queried.       
           Technical quality:           In my opinion, the proofs provided for proposition 2 and 3 are correct. The performed experiments seem suitable to compare the proposed approach with SIBA with respect to disagreement rate and classification speed. One particular nice thing about the performed experiments is that the authors also compare their approach with a more simple dynamic pruning algorithm, which stops querying classifiers if their vote would not change the result. However, it would be nice if the authors would have evaluated the reported measurements using statistical measures or tests. For instance, the authors argue that Table 1 shows that their approach produces disagreement rates closer to the specified one than SIBA. This could be easier illustrated by at least reporting the mean disagreement rate over all datasets. Also, by performing statistical analysis the authors could potentially show significant differences between the disagreement rates of both algorithms.                      Novelty:           This paper improves on SIBA in that it allows to adjust to the class bias of an ensemble, instead of assuming a uniform distribution. It is novel in the way the authors model the classification using an ensemble of classifiers as drawn without replacement from an urn of marbles and derive from this model a sound way to determine the confidence that a queried subset of classifiers will agree with the complete ensemble.                      Potential impact:           I believe that this work can be interesting for many people, since it provides a sound way to trade off voting accuracy and speed in an ensemble of classifiers, which can be useful when dealing with large amounts of instances. It has also a broad applicability, since this algorithm is not limited to work with random forest, but could also be applied to an ensemble of different classifiers.                      Clarity and presentation:           Overall, the presentation of the paper is good and the work is clearly described and explained. Especially the main intuition behind the proposed algorithm is well explained and the shift from an urn of marbles to an ensemble of classifiers is done nicely.                      The mathematical notation as well as the proofs in section 2 are very clear and rather easy to follow. It is helpful that the authors state the Chu-Vandermonde Identity, upper negation and the symmetry property of the binomial, which they are using to prove proposition 2 and 3. However, there appear to be two minor editing mistakes in the proofs. In the equation under line 124, it is unclear how the authors arrived at the expression on the left-hand side. In my opinion, it would have been enough to copy the right-hand side of the equation under line 123, since applying upper negation to this expression yields the right-hand side of the equation under line 124. Additionally, there is a plus sign instead of a minus sign in the upper bound of the second sum symbol in the equation under line 138. The current upper bound is $T - \sum_{i=1}^{l-2} T_{i}^{*} + t_{l}$, but it should be $T - \sum_{i=1}^{l-2} T_{i}^{*} - t_{l}$ instead.                      One issue in the presentation of the paper are the plots. While the plot of the vote distribution is good, the plots depicting the disagreement rates should be revised. According to the values on the x-axis and the description in the paper the x-axis should be named “1 - alpha” instead of “alpha”. Additionally, it is impossible to distinguish the different lines in these plots in a black and white printout. Therefore, I would recommend to use different line types to make it more clear which line belongs to which label without relying on different marker types and colors.                      Throughout the paper, the authors refer to the used sampling technique as “Mortecarlo sampling”. However, I believe this should be changed to “Monte Carlo sampling” or properly referenced as different sampling technique. Other minor spelling issues are:           line 7: “to” missing after “possible”           line 36: “on” instead of “of”           line 71: repetition of the word “marbles”           line 98: “than” instead of “that”           line 108: “infinite” instead of “infinity”            line 131: “by” missing after “simplified”           line 255, 258, 263: “a” instead of “an”