# Measuring statistical significance of machine learning algorithms comparison

Let us consider a comparison of two machine learning algorithms (A and B) on some dataset. Results (root mean squared error) of both algorithms depend on randomly generated initial approximation (parameters).

Questions:

1. When I use the same parameters for both algorithms, "usually" A slightly outperforms B. How many different experiments (with different parameters / updated /) have I to perform to make "sure" that A is better than B?
2. How to measure significance of my results? (To what extent I am "sure"?)

PS. I've seen papers in which authors use t-test and p-value; but i'm not sure if it is ok to use them in a such situation.

UPDATE. The problem is that A (almost) always outperforms B if initial params and learning/validation/testing sets are the same; but it doesn't neccessarily hold if they differ.

I see the following approaches here:

• split data into disjoint sets D_1, D_2, ...; generate parameters params_1; compare A(params_1, D_2, ...,) and B(params_1, D_2, ...,) on D_1; generate params_2; compare A(params_2, D_1, D_3,...) and B(params_2, D_1, D_3,...) on D_2 and so on. Remember how often A outperforms B.

• split data into disjoint sets D_1, D_2, ...; generate parameters params_1a and params_1b; compare A(params_1a, D_2, ...,) and B(params_1b, D_2, ...,) on D_1; .... Remember how often A outperforms B.

• first, do cross-validation for A. Then, independently, for B. Compare results.

Which approach is better? How to find significance of the result in this best case?

-
It would be helpful if you could give a bit more detail about the nature of the machine learning algorithms, in particular what is meant by "randomly generated initial approximation (parameters)" - does this mean something like a random set of initial weights for a neural network, or do you mean somplething like a random choice of kernel parameters for an SVM? The correct evaluation protocol may depend on the nature of these "parameters". –  Dikran Marsupial Oct 27 '10 at 14:32
This initial approximation is a couple of matrixes filled in with random values drawn uniformly & independently from [0;0.02]. (In fact, I'm comparing matrix factorizations via SGD with different loss functions; this matrixes are initial approximation of factors). So, it's closer to weights for NN –  bijey Oct 27 '10 at 14:46
In that case, I'd probably use the bootstrap, but generate a different initial matrix for each iteration, so that the resampling procedure averages over the variability due to the partitioning of the dataset and due to the initialisation, but I would use the same initialisation in each iteration for both methods. I'd then use the Wilcoxon signed rank test for performance evaluation (fewer assumptions). –  Dikran Marsupial Oct 27 '10 at 15:28
Thank you! Wilcoxon signed rank test looks promising. –  bijey Oct 27 '10 at 15:41
show 1 more comment

1. You have two biases to remove here -- the selection of the initial parameters set and the selection of train/test data. So, I don't think it is good to compare algorithms based on the same initial parameters set; I would just run the evaluation over few different initial sets for each of the algorithms to get more general approximation. The next step is something that you are probably doing already, so using some kind of cross-validation.
2. t-test is a way to go (I assume that you are getting this RMS as a mean from cross validation [and evaluation over few different starting parameters set, supposing you decided to use my first suggestion], so you can also calculate the standard deviation); more fancy method is to use Mann-Whitney-Wilcoxon test.

Wikipedia article about cross validation is quite nice and have some references worth reading.

UPDATE AFTER UPDATE: I still think that making paired test (Dikran's way) looks suspicious.

-
Thank you for your answer! But I have some doubts. The problem is that A always outperforms B if initial params and learning/validation/testing sets are the same; but it doesn't neccessarily hold if they differ. See question update. –  bijey Oct 27 '10 at 14:13
Note that if you adjust parameters of an algorithm after seeing its performance on the test set, test set error is no longer guaranteed to be an unbiased estimate of true error. –  Yaroslav Bulatov Oct 27 '10 at 16:41
Yaroslav! Actually, I've got learn,validation and test sets. I use validation set to tune some params like regularization term weight and optimization step (via simplex Cross Validated Metaoptimization), while initial weights (the parameters I was talking about before) are not adjusted at all... surely, the test set is used only to calculate quality metrics –  bijey Oct 27 '10 at 16:51
mbq, I'm not sure if I was clear enough =| I do not want to nail this weight –  bijey Oct 27 '10 at 20:07
I thought so; then stick to paired test, yet don't hide this fact. This is because in a sense you can say that they are equivalent -- B can be better than A when started with luckily picked seed. –  mbq Oct 27 '10 at 22:02