Friedman Test

Elizabeth Fons Alejandro Sztrajman July 28, 2021

Friedman Test is a non-parametric method to determine the significance of differences between multiple ($M$) classification algorithms evaluated over multiple ($N$) datasets. The first step in our analysis will be to do a hypothesis test to determine whether there is a significant difference in the performance of the classifiers. Our null hypothesis $H_0$ states that there is no difference between all classifiers, while the alternative hypothesis $H_A$ is that there is. To test these hypotheses, Friedman ranks the algorithms per dataset and then compares the average ranks, as detailed below:

1. Rank each algorithm by their performance on each dataset. In case of ties, average ranks are assigned. Example: if in a given dataset we have classifiers with the following accuracies, $m_1=0.7$, $m_2=0.9$, $m_3=0.7$ and $m_4=0.5$ we can see that $m_1$ and $m_3$ are tied, $m_2$ has the highest accuracy and $m_4$ has the lowest, so the rankings would be: $r_1=2.5$, $r_2=1$, $r_3=2.5$ and $r_4=4$.

    

2. Calculate the average rank $R_j$ of each method over all $N$ datasets:

3. Calculate the Friedman statistic:

   $$\chi_F^2 = \frac{12N}{M(M+1)}\left[\sum_j R_j^2 - \frac{M(M+1)^2}{4} \right].\nonumber$$

4. For large values of $M$ and $N$ (approximately $N>10$ and $M>5$), the Friedman statistic $\chi^2_F$ follows the $\chi^2$ distribution with $M-1$ degrees of freedom. Hence we need to search for the critical value of $\chi^2_{(M-1)}$ for a chosen significance level (typically $\alpha = 0.05$) in order to decide whether we can reject or not the null hypothesis. A $\chi^2$ distribution table can be found here. When the conditions for $M$ and $N$ are not met, the following table of critical values should be used.$^{1}$

Note: Iman and Davenport$^2$ showed that Friedman's $\chi^2$ tends to be conservative (i.e., it may have a high likelihood of type II error) and thus derived the following statistic:

which follows the $F$-distribution with $M-1$ and $(M-1)(N-1)$ degrees of freedom.

Example

The full table reporting the accuracies for all classifiers on all datasets can be downloaded from this link.

Let's analyse a numerical example, using a subset of the classification accuracies of multiple classifiers on the UCR datasets, provided by the UEA & UCR Time Series Classification Repository$^3$. For convenience, we will select only 5 classifiers from the table (ts-chief, rocket, boss, weasel, catch22) and 12 datasets (which correspond to the rows of the table).

The null hypothesis is that the accuracy is the same for all five classifiers and the alternative is that it is not:

Note that the alternative hypothesis is not that all classifiers have different accuracies $i.e., H_A: \theta_1 \neq \theta_2 \neq \cdots \neq \theta_5$ because this implies that all five means must differ from one another in order to reject the null hypothesis.

Step 1: We rank each algorithm on each dataset:

In the Beef datasets, ROCKET has the highest accuracy (0.76) thus it's ranked as $1^{st}$, while Catch22 has the lowest accuracy (0.47) and hence it's ranked as $5^{th}$.

Step 2: We can now calculate the average rank of each method, which is simply the average of each individual column on the above table.

We can see that TS-CHIEF and ROCKET have the lowest rankings, so they are the best performing classifiers, while Catch22 has the higher average ranking (close to 5) which seems to indicate that it's consistently the worst performing classifier.

Step 3: Compute the Friedman statistic to decide whether the classifiers are significantly different. We have 12 datasets and 5 classifiers, thus $N=12$ and $M=5$:

Step 4: The critical value for the $\chi^2$ distribution with 4 degrees of freedom for $\alpha=0.05$ is 9.487, so we can reject the null hypothesis (Reject $H_0$).

Finally, we can also compute the correction by Iman and Davenport$^{2}$:

The critical value for the $F$ distribution with $5-1=4$ and $(5-1)\cdot(12-1) = 44$ degrees of freedom for $\alpha=0.05$ is $2.583$, thus rejecting $H_0$, consistently with the results from the Friedman statistic.

Next steps

After applying the Friedman test, if the null hypothesis is rejected, we can proceed with a post-hoc test to establish which are the significant differences between the algorithms. We will explain possible post-hoc tests in future blog posts.

References

[1] Jerrold H. Zar. Biostatistical Analysis. 5th ed. Prentice-Hall/Pearson, 2010.

[2] Ronald L. Iman and James M. Davenport. Approximations of the critical region of the Friedman statistic. Communications in Statistics, pages 571–595, 1980.

[3] Anthony Bagnall, Jason Lines, William Vickers and Eamonn Keogh. The UEA & UCR Time Series Classification Repository, www.timeseriesclassification.com.