1
$\begingroup$

I would appreciate suggestions on how I could make some specific statistical claims about the efficacy of changes to an algorithm. My statistics background is pretty minimal (I'm working on it).

I would like to compare two versions of the same basic algorithm, however, one has been tweaked (hopefully improved). These are stochastic, population based optimization algorithms, think Genetic Algorithm, or Particle Swarm Optimization.

For instance, my results may look like this (the specific values, functions may vary of course):

benchmark fn     Before        After
dampened_sine    -0.597       -0.721        
fn1              69.308     -132.688    
fn3           -8457.388    -9000.000    
fn4              -0.394       -0.463        
fn5               0.153       -0.217        
haupt_fn1         9.627        1.000        
haupt_fn2         5.291        0.000

Any claims I would be making would be specific to the benchmark functions used. I was thinking of using a paired t-test (before and after the change of the algorithm), but I am not sure if that's the correct approach.

I would run each algorithm on each benchmark function N ( > 30?) times for a fixed number of generations and use the mean of these runs as a result to compare. The populations are generated with random values, I could use the same initial seed for each algorithm, but I am assuming that running each algorithm N times with different random seeds would put them more or less on equal footing.

My goal is to write this up in a paper, and be able to state that any observed changes for this specific set of benchmark functions wasn't just due to luck or randomness (given the stochastic nature of these algorithms) but is statistically significant. I am looking for some guidance on how to do this.

I hope the above is clear, I'd be happy to clarify/reword if it would be helpful.

Improve this question
$\endgroup$
3
  • $\begingroup$ can you explain what you mean by different seeds. basically to minimise randomness you should look at change for each seed, not take mean of 30 seeds. (ie you treat seed as 'subject' in paired test) $\endgroup$
    – seanv507
    Commented Jun 5, 2015 at 15:59
  • $\begingroup$ @seanv507 If I use the same seed number to initialize the random number generator and generate e.g., 100 random numbers subsequently, the sequence of numbers will be the same. So if I want to create the same two random populations for two different runs (i.e., for each algorithm) I could use the same seed. If I don't specify a specific value for the seed, the random number generator picks its own (usually using the system clock). $\endgroup$
    – Levon
    Commented Jun 5, 2015 at 16:58
  • $\begingroup$ right, and I was checking that you were using the same seed, and looking at the individual before- after differences ( ie matching 'randomness' , see en.wikipedia.org/wiki/Paired_difference_test in particular discussion of var(D bar) ). Because the way you were describing it, it sounded like the pairing was between test functions... maybe I just misunderstand your terminology. $\endgroup$
    – seanv507
    Commented Jun 5, 2015 at 17:27

2 Answers 2

Reset to default
1
$\begingroup$

A fair number of papers still simply report the means and variances, bold the lower number in each column, and call it a day, so it's nice to see you're trying to get it right.

Generally, I avoid parametric tests like the t-test, because I'm never 100% confident I'm getting all the assumptions right. Kruskal-Wallis is popular in the literature as a non-parametric test (or Mann-Whitney if you only have two populations you're comparing).

I think those would be good places to start, and then you can branch out if it seems you need something else.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks, .. and yes, I've seen those tables, and if these were deterministic algorithms, I could live with that sort of analysis, but given all the randomness involved I do want some "oomph" behind my claims/results. I'll read up on the two tests you mention. $\endgroup$
    – Levon
    Commented Jun 4, 2015 at 15:31
  • $\begingroup$ Hi again, I googled Man-Whitney, and I discovered that it's also known as Wilcoxon rank-sum test. It seems I ought to be using the Wilcoxon signed-rank test if I'm doing a simple pairwise comparison, is that incorrect? I'm not quite clear on the significant difference between these two test, I found another source that recommended the rank-sum version. $\endgroup$
    – Levon
    Commented Jul 2, 2015 at 20:50
  • $\begingroup$ I found this stats.stackexchange.com/questions/91034/… also suggesting the signed-rank ... somewhat confusing, but based on this I think signed-rank might be the way to go. $\endgroup$
    – Levon
    Commented Jul 3, 2015 at 14:28
1
$\begingroup$

I am dealing with similar question as you are. Since you are testing the same algorithm with different parameter's configurations (might be even considered as tunning) I believe that data you generate should be considered dependent (paired). Maybe I'm wrong.

Anyway, I distinguish two tests: (1) when comparing performance of the algorithm (or whatever else) on the same instance, (2) when comparing performance on the set of more instances. In the first case (1) the set of data is generated by running the algorithms multiple times. We have to do that, because different seeds are changing the final result. Here I use ANOVA with repeated measures when the data is not heavily skewed (ezANOVA in R). When comparing on different sets of instances, (case 2), usually Friedman's test (blocking for instance) is used. This is similar to repeated measures ANOVA however no need for data to be normally distributed.

Permutation test become more popular for the stochastic algorithms. Bootstrapping as well. Both are covered by the R libraries, so no worries there. Didn't use them much so can't provide more details about it.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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