2
$\begingroup$

I want to use a statistical test to show that there is a significant difference between 9 algorithms over 2 datasets. I have read Demsar's paper and used Friedman's test (also used Iman's corrected Friedman test). The test find a p-value of 0.08 which is higher than the 5% threshold thus the null hypothesis is not rejected (null-h: all algorithms are equal). If you look at the accuracies, it is obvious that might not be the case (I might be mistaken). I then run it through a post-hoc method to adjust the p-values using the Bergmann adjustment or Bonferroni. Below are the accuracies of each algorithm on the 2 datasets and my R code results. Can you please help me understand them and potentially find a better solution? Basically, I am trying to compare the algorithms to the first algorithm in the table which I wrote myself (Clf1).

Accuracies:

enter image description here

Ranking of Classifiers:

     X1 X2 X3 X4 X5 X6 X7 X8 X9
[1,]  1  8  6  4  7  2  5  3  9
[2,]  1  6  3  9  7  2  8  4  5

Friedman Test:

      Friedman's rank sum test

data:  data
Friedman's chi-squared = 11.733, df = 8, p-value = 0.1635

This gives me a p-value of 16%! Which is not good. I assume this is due to small number of datasets I have tested on. If I use the adjusted Friedman test:

Iman's adjustment to F-test:

     Iman Davenport's correction of Friedman's rank sum test

data:  data
Corrected Friedman's chi-squared = 2.75, df1 = 8, df2 = 8, p-value = 0.08697

I get 8% which is better and can be acceptable. Now, I must use a post-hoc method to evaluate the p-values and test the hypothesis:

Nemenyi Test:

     Nemenyi test

data:  data
Critical difference = 10.834, k = 9, df = 9

Plotting the confusion matrix shows this:

> abs(test$diff.matrix) > test$statistic
      X1    X2    X3    X4    X5    X6    X7    X8    X9
[1,] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
[2,] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
[3,] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
[4,] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
[5,] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
[6,] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
[7,] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
[8,] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
[9,] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE

If I do a Bergmann adjustment:

> raw.p <- friedmanPost(data)
> adjustBergmannHommel(raw.p)
Applying Bergmann Hommel correction to the p-values computed in pairwise comparisons of 9 algorithms. This requires checking54466sets of hypothesis. It may take a few seconds.
   X1 X2 X3 X4 X5 X6 X7 X8 X9
X1 NA  1  1  1  1  1  1  1  1
X2  1 NA  1  1  1  1  1  1  1
X3  1  1 NA  1  1  1  1  1  1
X4  1  1  1 NA  1  1  1  1  1
X5  1  1  1  1 NA  1  1  1  1
X6  1  1  1  1  1 NA  1  1  1
X7  1  1  1  1  1  1 NA  1  1
X8  1  1  1  1  1  1  1 NA  1
X9  1  1  1  1  1  1  1  1 NA

The adjustment just results in these p-values which have no significance. I would greatly appreciate your explanation in what I am doing wrong and what I can do to fix this problem.

Thank you in advance,

$\endgroup$
  • $\begingroup$ Accuracies are associated with a confidence intervals, so it does not appear unreasonable that there would be overlap, leading to a failure to reject the null hypothesis. $\endgroup$ – ReneBt Mar 9 '18 at 11:07
  • $\begingroup$ @ReneBt What do you recommend me to do in order to conduct a meaningful test? $\endgroup$ – MichaelMMeskhi Mar 10 '18 at 16:23
  • $\begingroup$ It is very inappropriate to try new tests just because the one you first done did not quite succeed. If you want to have a look at the confidence intervals for accuracy, check if any ranges overlap with the interval for your algorithm of interest. You have already committed to an analysis, tried it out and it failed to reject the null hypothesis. Therefore, if you wish to carry out a second test you are now in exploratory (not confirmatory) analysis mode and should also apply a multiple test correction, which means that each new test must pass an ever more stringent barrier. $\endgroup$ – ReneBt Mar 12 '18 at 12:12
  • $\begingroup$ @ReneBt I had read Demsar's paper and figured that these tests would be most beneficial. $\endgroup$ – MichaelMMeskhi Mar 13 '18 at 3:39
4
+50
$\begingroup$

It sounds like you are randomly throwing statistical tests at the problem. Instead, I would recommend trying to understand what you are actually trying to test, what assumptions you could make and then figure out how to get the statistic you are after.

You have only tried the classifiers on 2 datasets. Are you trying to estimate the probability that your classifier will perform better than the other classifiers on another dataset of the same size, randomly sampled from the same underlying population? Are you assuming that that the first 2 datasets were also of the same size and randomly sampled from the population? Do you also assume that your classifier scores on these datasets are normally distributed for each classifier? These could be unreasonable assumptions to make, depending on your application.

But assuming these are reasonable assumptions, you could easily run a Monte-Carlo simulation of your problem to estimate the probability you are after.

No statistics is better than bad statistics.

Edit to place relevant comments into the answer:

Since your datasets are not similar, it may actually be impossible to prove that your algorithm is better than the others in general because it may be false due to the "no free lunch" theorem - e.g. see https://en.wikipedia.org/wiki/No_free_lunch_theorem#Implications_for_the_scientific_method. What you may actually be after is proving that your algorithm is better on particular kinds of datasets, even if that range may be very broad. But that can be very difficult to define formally and thus difficult to prove, and you would rarely see such proofs in ML literature.

What may be a good idea instead is to prove that your algorithm does better than others on a particular benchmark universe. If you have a sizeable dataset, you could do it by satisfying the assumptions I or jbowman listed by constructing your test datasets by sampling from this universe. It would then be easy to show that your algorithm does better on that universe. Ideally, such a benchmark universe would be widely used as a benchmark, so you would be able to compare against the results of the authors of the other algorithms.

One common problem with such comparisons is that the author would carefully tune their own algorithm, but not spend as much effort on tuning the other algorithms, which would result in inflated metrics of the author's algorithm relative to the other algorithms. If that is the case here, you may also need to try to address that.

Edit 2:

This paper, which you might have already seen, appears to deal with the problem that you are having: Demšar, Janez. "Statistical comparisons of classifiers over multiple data sets." Journal of Machine learning research (2006). But again, I would advise against blindly applying their methodology as you need to understand their assumptions and caveats of their research. For example, in the conclusion they state:

We have observed the behaviour of the proposed statistics on several real-world classifiers and data sets. We varied the differences between the classifiers by biasing the selection of data sets, and measured the likelihood of rejection of the null-hypothesis and the replicability of the test. We have indeed found that the non-parametric tests are more likely to reject the null-hypothesis, which hints at the presence of outliers or violations of assumptions of the parametric tests and confirms our theoretical misgivings about them. The empirical analysis also shows that replicability of the tests might be a problem, thus the actual experiments should be conducted on as many data sets as possible.

In the empirical study we provided no analysis of Type 1/Type 2 error rates. The main reason for this is that the correct result—rejection or non-rejection of the null-hypothesis—is not well defined and depends upon the kind of difference between the algorithms we intend to measure. Besides, conducting the experiments in which we knew the true hypotheses would require artificial data sets and classifiers with the prescribed probabilities and distributions of errors. For this we would need to make some assumptions about the real-world distributions; these assumptions are, however, exactly what we were testing in the first place.

There is an alternative opinion among statisticians that significance tests should not be performed at all since they are often misused, either due to misinterpretation or by putting too much stress on their results (Cohen, 1994; Schmidt, 1996; Harlow and Mulaik, 1997). Our stance is that statistical tests provide certain reassurance about the validity and non-randomness of the published results. For that to be true, they should be performed correctly and the resulting conclusions should be drawn cautiously. On the other hand, statistical tests should not be the deciding factor for or against publishing the work. Other merits of the proposed algorithm that are beyond the grasp of statistical testing should also be considered and possibly even favoured over pure improvements in predictive power.

$\endgroup$
  • $\begingroup$ Thanks for your insight. My two datasets are not same. This is a domain adaptation problem. I feed a source dataset and target dataset to each algorithm. D1 has 850 instances and D2 11964. My goal is to do this. I ran these algorithms on shuffled, randomly sampled 50% size of target dataset aka test dataset. I have these accuracies and want to say that algorithm X1 is better than the rest or not. $\endgroup$ – MichaelMMeskhi Mar 7 '18 at 18:14
  • 2
    $\begingroup$ @MichaelMMeskhi In that case, it may actually be impossible to prove that your algorithm is better than the others in general because it may be incorrect due to the "no free lunch" theorem - e.g. see en.wikipedia.org/wiki/…. What you may actually be after is proving that your algorithm is better on particular kinds of datasets, even if that range may be very broad. But that can be very difficult to define formally and thus difficult to prove, and you would rarely see such proofs in ML literature. $\endgroup$ – rinspy Mar 8 '18 at 9:45
  • 2
    $\begingroup$ @MichaelMMeskhi What may be a good idea instead is to prove that your algorithm does better than others on a particular benchmark universe. If you have a sizeable dataset, you could do it by satisfying the assumptions I or jbowman listed by constructing your test datasets by sampling from this universe. It would then be easy to show that your algorithm does better on that universe. Ideally, such a benchmark universe would be widely used as a benchmark, so you would be able to compare against the results of the authors of the other algorithms. $\endgroup$ – rinspy Mar 8 '18 at 9:50
  • 3
    $\begingroup$ @MichaelMMeskhi One common problem with such comparisons is that the author would carefully tune their own algorithm, but not spend as much effort on tuning the other algorithms, which would result in inflated metrics of the author's algorithm relative to the other algorithms. If that is the case here, you may also need to try to address that. $\endgroup$ – rinspy Mar 8 '18 at 9:52
  • $\begingroup$ @MichaelMMeskhi Thanks! Don't forget to accept the answer if it solved your problem. $\endgroup$ – rinspy Mar 15 '18 at 16:59
2
$\begingroup$

We can construct a custom test for this problem. If we assume that algorithm D1 is the same as the other algorithms, that they are all the same as well on average across the problem domain (highly dubious), and that differences in the algorithms' performances are independent across test problems (also dubious) then we can attribute differences in performance to randomness in the choice of problems. In that case, the rank of algorithm D1's performance would be uniformly distributed over the integers $1, 2, \dots, 9$.

We have two experiments, so the sum of the ranks $R_1+R_2$ of algorithm D1 on the two experiments will, under the null hypothesis, have the same distribution as the sum of two uniformly-distributed numbers from the set $\{1, 2, \dots, 9\}$. This distribution we can generate explicitly (there aren't that many combinations, after all), and see what the probability is of observing the actual or a greater rank sum.

In this case, $R_1+R_2 = 2$, and the probability of such a sum occurring by chance is easily seen to be $1/81$. Since there are no more extreme values possible, this is also the probability of such a sum or a more extreme one occurring by chance, and corresponds to the p-value associated with the test of whether D1's performance really is uniformly distributed over $\{1, 2, \dots, 9\}$.

Having written all this, though, I would STRONGLY suggest generating more test problems for your comparison than just two, and trying very, very hard to make sure they are representative of the problem domain and not subtly biased towards your algorithm. If you get substantially more data, you'll be able to use more powerful ranking procedures that can, to some extent, take into account lack of independence between algorithms across test problems as well as differences between algorithm performance - but that is well beyond the scope of this question. Any conclusions from what you've done are more heavily dependent upon the rather stringent assumptions made above than I personally would be comfortable with.

$\endgroup$
  • $\begingroup$ Thank you @jbowman for your answer. It was very insightful and clearly laid out. I completely agree with running my algorithms on more datasets as that would give way to better tests with more significant results. $\endgroup$ – MichaelMMeskhi Mar 8 '18 at 0:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.