5
$\begingroup$

For my master thesis I want to set-up several experiments. One thing my professor has been complaining about is that most computer science experiments are lacking scientifically. To not fall into this trap I want to properly design my experiments. Unfortunately I could not find much literature on CS experiment design. (Except for D. Feitelson's "Experimental Computer Science: The Need for a Cultural Change" available here which is more of an appeal than a guide.)

I remember that in statistics people often use a H_0 and H_1 hypothesis together with the Type I and Type II error. I wonder if this is applicable in the field of computer science.

A quick example that I could think of:

H_0: Both methods create the same output in this scenario

H_1: One method creates a worse output in this scenario (worse: according to metric X)

But then how would I calculate the Type I and Type II errors? In a speed-benchmark I could run the experiments multiple times and then possibly calculate how likely it is that the benchmark result is still wrong. However often I just want to compare the output of two deterministic methods. Measuring the quality according to a certain metric. This result doesn't change when running the experiment multiple times. What do I do then? Is the null hypothesis approach not a good fit for these kind of experiments?

Improve this question
$\endgroup$
1
  • $\begingroup$ You need to differentiate study design (the logic guiding how you get your data) from statistical analysis (what inferences you make based on your observed data and study design). $\endgroup$
    – Alexis
    Commented Jun 7, 2014 at 14:22

2 Answers 2

Reset to default
2
$\begingroup$

I don't know exactly what kind of computer experiments you are trying to do. If you are trying to judge the performance of algorithms, there is now a field called experimental algorithmics which has a textbook, journals, and conferences. If you're comparing the performance of two or more algorithms on different inputs, you should probably look at references from this field; this is exactly the kind of thing they study, and they have figured out ways to do this which work much better than the naive first approach that you might think of. Furthermore, the fact that you are following the techniques of an established subfield of computer science should address your professor's complaints that the experiments are lacking scientifically. Even if the experimental design you come up with after looking at the techniques in this field is the same as the one you would have come up on your own, your professor is less likely to object to it.

If you just have two algorithms you want to compare, one input, and one output for each algorithm, there is very little statistical analysis you can do, as this scenario gives you only two data points, and without some kind of model for the behavior of these algorithms, there is absolutely nothing you can do statistically with two data points.

Improve this answer
$\endgroup$
8
  • 2
    $\begingroup$ On the other hand, if "input" and the associated "output" are interpreted as subject, and there's lots of different possible inputs and outputs, then algorithm becomes like group or treatment, right? While CS has historically been interested in boundaries and limits of performance, in some applications those things are of more theoretical interest, since most inputs and outputs are located inside some continuum. $\endgroup$
    – Alexis
    Commented Jun 7, 2014 at 14:20
  • 1
    $\begingroup$ @Alexis: there are some issues you have to worry about with experimental algorithms that you don't with traditional "subjects" and "treatments". In particular, there are lots more ways of choosing inputs than there usually are of choosing "subjects". $\endgroup$
    – Peter Shor
    Commented Jun 7, 2014 at 14:22
  • 1
    $\begingroup$ Yes, but you generally do not have only two data points. As an example: assessing different sorting algorithm performance based on a sample of inputs with different orderings. And, with due respect, there are virtually infinite ways of choosing human subjects (with implications for study generalizability), so epidemiologic design (my area) is perhaps not as simple as you imply. $\endgroup$
    – Alexis
    Commented Jun 7, 2014 at 14:24
  • $\begingroup$ @Alexis: for sorting algorithms, the question is: how do you choose the inputs? If you just test your algorithm on random inputs, then you may find to your surprise that it works very badly on nearly-sorted inputs. And if you test your algorithm on both randomized and nearly-sorted inputs, how do you know there isn't another class of inputs on which the algorithm works very badly. I have experience with an algorithm which worked well on most classes of inputs, but when you used as a subroutine for a different, the inputs it received made it incredibly slow for reasons we never figured out. $\endgroup$
    – Peter Shor
    Commented Jun 7, 2014 at 17:18
  • $\begingroup$ Well, if one does not assume that one knows the degree of shuffling a priori, then experimental design might, if something about the distribution of inputs is known, produce results that characterize the distribution of outputs in a manner that is useful when evaluating relative performance of different algorithms. My point still stands: you generally would not have two data points. $\endgroup$
    – Alexis
    Commented Jun 7, 2014 at 17:37
3
$\begingroup$

You should take a look at Catherine McGeoch's book, "A Guide To Experimental Algorithmics" McGeoch has been criticized for her work on a study of the performance of the D-wave quantum computer, but I think the book is a good source.

http://www.amazon.com/Guide-Experimental-Algorithmics-Catherine-McGeoch/dp/0521173019

Improve this answer
$\endgroup$
1

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.