One of the most common methods for classifier comparison is Friedman's test. However, Friedman's test has a known flaw - ranking of classifiers A and B does not depend only on the properties of classifiersA and B, but also on the properties of all other evaluated classifiers. We illustrate the issue on a question: “What is better, bagging or boosting?”. With Friedman's test, the answer depends on the presence/absence of irrelevant classifiers in the experiment. Based on the application of Friedman's test on an experiment with 179 classifiers and 121 datasets we conclude that it is very easy to game the ranking of two insignificantly different classifiers. But once the difference becomes significant, it is unlikely that by removing irrelevant classifiers we obtain a significantly different classifiers but with reversed conclusion. Friedman's test Friedman's test, if applied on algorithm ranking, is defined as:
Friedman’s test is the recommended way how to compare
algorithms in machine learning (ML) [
Given data {xi j}n×k, that is, a matrix with n rows (the datasets), k columns (the algorithms) and a single performance observation at the intersection of each dataset and algorithm, calculate the ranks within each dataset. If there are tied values, assign to each tied value the average of the ranks that would have been assigned without ties. Replace the data with a new matrix {ri j}n×k where the entry ri j is the rank of xi j within dataset i. Calculate then rank sums of algon rithms as: r j = ∑i=1 ri j.
We can rank the algorithms based on rank sums r j [
IIA Independence of Irrelevant Alternatives [
If algorithm A is preferred to algorithm B out of the choice set {A,B}, introducing a third option X , expanding the choice set to {A,B,X }, must not make B preferable to A.
In other words, preferences for algorithm A or algorithm B, as determined by rank sums r j, should not be changed by the inclusion of algorithm X , i.e., X is irrelevant to the choice between A and B.
Illustration Boosting tends to outperform base algorithms (e.g. decision trees) by a large margin. But sometimes, boosting fails [2, Chapter 8.2] while bagging reliably outperforms base algorithms on all datasets, even if only by a small margin [2, Chapter 7.1]. This is illustrated in the left part of Figure 1. If we compare boosting only to bagging, then by the rank sums r j, boosting wins, because boosting is better than bagging on the majority of datasets. However, if we add irrelevant algorithms that are always worse than bagging, the conclusion may change. Bagging will be always the first or the second. But boosting will be either the first or (in the provided illustration) the last. And a few extreme values in the rank sum r j can result into the change of the conclusion. t e s a t a D 1-p {
m Irrelevant Bagging Boosting ...
...
Measure (e.g. AUC)
Ranks (bigger is better) m Irrelevant Bagging Boosting . . . m+1 m+2 . . . m+1 m+2 ... .. . m+...1 m+... 2 . . . m+1 m+2 ... .. . m+...2 1...
. . . m+2 1 Avg rank rj (1+-pp()m(m++21)) (1-p)(m+2) + p Equilibrium
rBagging = rBoosting (1-p)(m+1)+p(m+2) = (1-p)(m+2)+p p(m+2) = 1
Hypothesis Authors of highly cited papers, knowingly or not, frame their algorithms in the best possible light. Based on the equilibrium equation in Figure 1, we would expect that proponents of boosting algorithms use fewer algorithms than proponents of bagging in the design of experiments (DOE).
Evaluation Breiman, the author of bagging [
Threats to validity due to omitted variables Since both articles were published in the same year, the availability of algorithms for comparison should be comparable and cannot be used to explain the observed differences in the DOE.
Conclusion Since this is just a single observation, which can be just by chance, following section analyses the impact of DOE numerically. 3.2
A nice comparison of 179 classifiers on 121 datasets is
provided by Fernández-Delgado et al. [
If we directly compare just two classifiers, AdaBoostM1_J48_weka and Bagging_J48_weka, and calculate rank sums r j, then we get that boosting beats bagging 64 to 47. But if we calculate rank sums over all algorithms, then we get that bagging beats boosting 13136 to 12898. A completely reversed conclusion! How frequently does the ordering flip? If we perform above analysis over all unique pairs of classifiers ( 12 179(179 − 1) = 15753), then we get that the ordering flips in 5% of cases (831/15753).
Are the changes in the ranks significant? We repeated the experiment once again, but considered only classifier pairs that are based on Friedman’s test:
2. and significantly different in the presence of all the remaining classifiers .
If we do not apply multiple testing correction, the
classifiers flip the order in mere 0.05% cases (8/15753) at a
shared significance level α = 0.05. Once we add
multiple testing correction, the count of significant flips drops
to zero. In our case, the exact type of multiple testing
correction does not make a difference. Bonferroni, Nemeneyi,
Finner & Li and Bergmann & Hommel [
Related Work and Discussion
We are not the first one to notice that Friedman’s test does
not fulfill the IIA property. The oldest mention of the issue
in the literature, that we were able to track down, dates
back to 1966 [
Benevoli et al. [
α β γ δ ε
A
to come with a fair vote method arose. Two competitors,
Condorcet and Borda1, came with two different methods.
And they did not manage to agree, which of the methods
is better. This disagreement spurred an interest into vote
theory. One of the possible alternatives to Friedman test
that vote theory offers is Ranked pairs method [
rithms. 2. Sort the pairs by the difference of the win counts
in the pair. 3. “Lock in” the pairs beginning with the strongest
difference of the win counts.
While Ranked pairs method also fails IIA criterium, it at least fulfills a weaker criterium calledLocal Independence from Irrelevant Alternatives (LIIA). LIIA requires that the following conditions hold:
If the best algorithm is removed, the order of the remaining algorithms must not change. If the worst algorithm is removed, the order of the remaining algorithms must not change.
An example where Friedman’s test fails LIIA criterium
is given in Figure 3 [
α β γ δ ε Rank sum
A Ak. When A0 is better, the rank is A0 A1 . . .
Ak B. Therefore, the presence of A1, A2, . . . , Ak artificially increases the difference betweenA0 and B.
But Ranked pairs method fulfills this criterion.
Finally, Friedman’s test violates Majority criterion [
We have already observed a violation of this criterion in
the though example with bagging versus boosting — even
thought boosting was the best algorithm on the majority
of the datasets, this fact alone did not guarantee boosting’s
victory. The violation of Majority criterion also implies a
violation of Condorcet criterion [
If there is an algorithm which wins pairwise to each other algorithm, then that algorithm must win.
Which is, nevertheless, once again fulfilled with Ranked
pairs method. However, just like in machine learning we
have no free lunch theorem, Arrow’s impossibility
theorem [
If based on a set of datasets A an algorithm A is the best. And based on another set of datasets B an algorithm A is, again, the best. Then based on A ∪ B the algorithm A must be the best.
Notably, Friedman’s test fulfills this criterium while Ranked pairs method fails this criterium. For convenience, a summary table with the list of discussed criteria is given in Table 1. Contrary to our expectations, based on analysis of 179 classifiers on 121 datasets, Friedman’s test appears to be fairly resistant to manipulation, where we add or remove irrelevant classifiers from the analysis. Therefore, wecannot recommend avoiding Friedman’s test only because it violates Independence of Irrelevant Alternatives (IIA) criterium. 6
Acknowledgment I would like to thank Adéla Chodounská for her help. We furthermore thank the anonymous reviewers, their comments helped to improve this paper. The reported research has been supported by the Grant Agency of the Czech Technical University in Prague (SGS17/210/OHK3/3T/18) and the Czech Science Foundation (GACˇ R 18-18080S).
Non-dictatorship The outcome should not depend only upon a single dataset.
rithm A is preferred to algorithm B out of the choice set {A,B}, introducing a third option X , expanding the choice set to {A,B,X }, must not make B preferable to A.
Appendix: Criteria