Einige Referenzen sind derzeit nicht in dem Skriptum; sie sind über meine Bibliographie zu finden.
Wissenschaftliche Methodik in der praktischen Informatik

Ziele in der Wissenschaft

Allgemein, Leser: Neues, relevantes Wissen
Autor: Papers publizieren, Ruf erwerben.
Publikation/Reviewer: hohe Qualität der Papers sicherstellen


Qualitätskriterien

Relevance
Appropriateness for the journal/conference
Originality
Quality of presentation
Technical quality


Methoden

Physik:
Daten->Theorie (Hypothese)->Voraussage->Experiment->Daten
Reproduzierbarkeit

Sozialwissenschaften: Umfragen, Interviews, Experimente; statistische
Auswertung.

Mathematik, Theoretische Informatik: Beweis.

Praktische Informatik:
Problem->Loesungsvorschlag->Implementation/Simulation->Benchmarks

Allgemeine Probleme von Benchmarks:
Nur wenige Fälle von vielen möglichen; wie repräsentativ?

Zuviele Einflussfaktoren bei Runs auf echten Maschinen.

Simulationen dauern lang.


Theoretische Aussagen über alle Fälle, aber: 

Oft qualitativ, nicht quantitativ ("A ist immer so gut und manchmal
besser als B").

Wenn quantitativ (z.B. algorithmische Komplexität), wie oft kommt
welcher Fall vor?

Wenn ein bestimmter Fall/Modell angenommen wird, entspricht er der
Realität?  (hasegawa&shigei85)

Vereinfachte Annahmen oder eingeschränkte Problemstellung (z.B. keine
Code replication bei code motion).

Optimale Methoden oft NP-hard oder schlimmer.

Oft keine Berücksichtigung von Interaktionen mit anderen Komponenten
(z.B. cache-effekte).


Andere Methoden

Modell, mit statistischen Daten gefüttert (oskin+00, zhu&wong98),
vgl. Thermodynamik.

Probleme: Zugrundelegende Prozesse nicht-stetig (diskret); bei
parallelen Prozessen nichtlineare Effekte (max-Funktion); die
statistischen Daten stammen aus Benchmarks (Probleme siehe oben).

Siehe auch synthetische Benchmarks: sehr eingeschränkte Anwendbarkeit.


Wichtige Prinzipien (aus johnson02):

Perform Newsworthy Experiments

Tie your Paper to the Literature

Use Instance Testbeds that Can Support General Conclusions
  (die richtigen Fragen stellen)

Use Efficient and Effective Experimental Designs
  (z.B. Varianz reduzieren, z.B. indem man bei zufällig erzeugten
   Testdaten Läufe mit den gleichen Daten vergleicht und nicht nur
   Läufe mit irgendwelchen Daten)

Use Reasonably Efficient Implementations

Ensure Reproducability

Ensure Comparability

Report the Full Story

Draw Well-Justified Conclusions and Look for Explanations

Present Your Data in Informative Ways


Häufige Fehler:

Nicht repräsentative Benchmarks (z.B. Laufzeiten der SpecJVM suite).

Fehlende Begründung für die Wahl der Benchmarks (warum nicht
Standard-Benchmark?  Warum dieser Standard-Benchmark?)

Microbenchmarks (nützlich zum Herausarbeiten von Spezialfällen, aber
nicht brauchbar für allgemeine Vorhersagen).

Synthetische Benchmarks: Selbst wenn sie in einer Umgebung
repräsentativ sind, kann sich die Umgebung schnell ändern
(z.B. Strings in Dhrystone auf der Alpha).

Tuning auf das Benchmark hin (allgemein schwer vermeidbar, aber
zumindest bei Profile-feedback sollte der gemessene
Benchmark/Datensatz nicht für das Profile benutzt werden).

Vergleich des besten Falles einer Methode mit dem typischen Fall einer
anderen Methode, oder eines typischer Fall mit einem schlechtesten
Fall etc.

Fehlende Erklärung für ungewöhnliche Resultate.

Behauptungen ohne empirische Grundlage.

Eindimensionaler Vergleich von Techniken, bei denen mehrere
Dimensionen wichtig sind (z.B. Code-Qualität (Laufzeit)
vs. Compile-Zeit eines JIT-Compilers).

Zuviele Faktoren (z.B. Vergleich der Registerallokatoren anhand der
Laufzeit von von verschiedenen Compilern compilierten Programmen).

Missing the big picture: Vergleich von zwei Teilen, die keine grosse
Rolle spielen.

Arbeiten mit indirekten Metriken (z.B. Anzahl der aliases in der
Alias-Analyse; Anzahl der gebrauchten Register bei der
Registerallokation), ohne zu zeigen, wie sich das auf die
interessierenden Metriken auswirkt.

Vergleich relativer Zahlen bei wechselnder Bezugsgröße.  Besonders
leicht, wenn die relative Zahl eine Standard-Größe ist (z.B. Cache
miss rate).  Positives Beispiel: mueller&whalley92.

Angaben ohne Beschreibung der Messumgebung (z.B. CPU (nicht nur
Architektur), Taktrate, Cache, Speicher, OS, Compiler,
Optimierungslevel).

Ineffiziente Implementierungen erlauben keinen Vergleich der Effizienz
der Methoden (bei einer Methode kann sich die Ineffizienz stärker
auswirken).

Falscher Mittelwert: arithmetisches/harmonisches/geometrisches Mittel,
Median, Bestes (arithmetisches Mittel ist fuer Rates (z.B. MIPS)
Unsinn).

Verlust von Code und/oder Daten; insbesondere: welche Daten stammen
aus welchem Experiment mit welchen Randbedingungen.  Welche Version
des Codes wurde dafür benutzt.

Verwendung der Laufzeit als Abbruchkriterium bei Heuristiken (nicht
reproduzierbar).


Präsentation:

Unklarer Inhalt; welche Erkenntnisse werden in dem Paper beschrieben?

Prozentangaben mit unklarem Nullpunkt (sind 150% ein Faktor 1.5 oder 2.5?).

Prozentangaben ohne Bezugsgröße (sind 50% ein Faktor 2 oder 1.5?).

Überladene Graphiken

3D-Graphiken

Linien zwischen ungeordneten Punkten (besser: Balkendiagramme).

Schwer unterscheidbare Linien

Fehlende Achsenbezeichnungen

Fehlende Einheiten

Fehlende/Schlechte Angabe der Aggregierung
(arithmetisches/harmonisches/geometrisches Mittel, Median, Bestes).

Unterschiedliche Skalierungen in vergleichbaren Graphen.

Verschiedene Reihenfolgen (z.B. im Text vs. in den Tabellen; oder in
der Legende einer Graphik und in der Graphik).


Literatur:

Allgemeine Tips über Forschung, besonders Doktorarbeiten (hat mir auch
bei meiner Diplomarbeit geholfen):

@Manual{bundy+85,
  title =	 {The Researcher's Bible},
  author =	 {Alan Bundy and Ben du Bolay and Jim Howe and Gordon
                  Plotkin},
  year =	 {1985},
  url =          {http://homepages.inf.ed.ac.uk/bundy/how-tos/resbible.html},
  annote =	 {Good advice on the problems on the way to a
                  Ph.D. and how to overcome them. An earlier version
                  is \cite{bundy+84}; this version is being maintained.}
}

Viele Tips für Forschung in der praktischen Informatik:

@InProceedings{johnson02,
  author =	 {David S. Johnson},
  title =	 {A Theoretician's Guide to the Experimental Analysis
                  of Algorithms},
  booktitle =	 {Proceedings of the 5th and 6th DIMACS Implementation Challenges},
  year =	 {2002},
  url =		 {http://davidsjohnson.net/papers/experguide.pdf},
  annote =	 {Gives much useful advice on producing empirical
                  papers, most of it applicable beyond algorithm work,
                  including lists of pitfalls, suggestions, and pet
                  peeves. One important principle discussed is
                  comparability (as differentiated from
                  reproducability).}
}

@Article{bailey91,
  author =	 {David H. Bailey},
  title =	 {Twelve Ways to Fool the Masses When Giving
                  Performance Results on Parallel Computers},
  journal =	 {Supercomputing Review},
  year =	 {1991},
  pages =	 {54--55},
  month =	 aug,
  url =		 {http://www.pdc.kth.se/training/twelve-ways.html},
  annote =	 {Most of these ways are somewhat specific to
                  supercomputing, but you can probably learn lessons
                  applicable to other fields.}
}

Über Aggregation:

@Article{smith88,
  author = 	 {James E. Smith},
  title = 	 {Characterizing Computer Performance with a Single Number},
  journal = 	 cacm,
  year = 	 {1988},
  volume =	 {31},
  number =	 {10},
  month =	 oct,
  pages =	 {1202--1206},
  annote =	 {Advocates the use of the arithmetic mean for times,
                  the harmonic mean for rates, and normalizing after
                  aggregating (i.e., not averaging normalized numbers).}
}

@Article{fleming&wallace86,
  author = 	 {Philip J. Fleming and John J. Wallace},
  title = 	 {How not to Lie with Statistics: The Correct Way to
                  Summarize Benchmark Results},
  journal = 	 cacm,
  year = 	 {1986},
  volume =	 {29},
  number =	 {3},
  month =	 mar,
  pages =	 {218--221},
  annote =	 {Advocates the use of the geometric mean in
                  summarizing normalized benchmark results.}
}

@Misc{mashey2005,
  author =	 {John Mashey},
  title =	 {{SPEC} use of Geometric Mean},
  howpublished = {Usenet Article
                  <1115972116.172947.194880@g44g2000cwa.googlegroups.com>},
  month =	 may,
  year =	 {2005},
  url =          {http://groups.google.at/group/comp.arch/msg/416e58b5e48c1715},
  annote =	 {Discusses why the geometric mean is appropriate in
                  many cases for aggregating benchmark results (like
                  SPEC) into one number: The statistical distribution
                  of the values is usually log-normal (and the reasons
                  for this are discussed), and the right way to
                  aggregate such values is the geometric mean (which
                  is the arithmetic mean in the log scale).}
}

Methoden im Bereich Software Engineering:

@InProceedings{shaw02,
  author =	 {Mary Shaw},
  title =	 {What Makes Good Research in Software Engineering?},
  booktitle =	 {Presented at the European Joint Conference of Theory
                  and Practice of Software (ETAPS 2002), Grenoble,
                  France. To appear in the International Journal on
                  Software Tools for Technology Transfer.},
  url =           {http://www-2.cs.cmu.edu/afs/cs.cmu.edu/project/compose/www/ftp/shaw-fin-etaps.pdf},
  annote =	 {Takes a look at various research strategies used in
                  software engineering.}
}

@Article{zelkowitz&wallace98,
  author =	 {Marvin V. Zelkowitz and Dolores R. Wallace},
  title =	 {Experimental Models for Validating Technology},
  journal =	 ieeecomputer,
  year =	 {1998},
  volume =	 {31},
  number =	 {5},
  pages =	 {23--31},
  month =	 may,
  annote =	 {Presents a classification of software engineering
                  validation models and discusses them. They also
                  classified 612 papers in software engineering; the
                  most popular methods are no experimentation (167
                  papers) and Assertion (ad-hoc validation techniques
                  for the proposed technology, with danger of bias;
                  192 papers).}
}

Allgemein über empirische Forschung in Informatik und Software Engineering:

@Article{tichy98,
  author =	 {Walter F. Tichy},
  title =	 {Should Computer Scientists Experiment More?},
  journal =	 ieeecomputer,
  year =	 {1998},
  volume =	 {31},
  number =	 {5},
  pages =	 {32--40},
  month =	 may,
  url =		 {http://wwwipd.ira.uka.de/~tichy/},
  annote =	 {Discusses the role experimentation should play in
                  computer science, and why some of the excuses given
                  for not doing it are invalid.}
}

@Article{tichy+95,
  author =	 {Walter F. Tichy and Paul Lukowicz and Lutz Prechelt
                  and Ernst A. Heinz},
  title =	 {Experimental Evaluation in Computer Science: A
                  Quantitative Study},
  journal =	 {Journal of Systems and Software},
  year =	 {1995},
  volume =	 {28},
  number =	 {1},
  pages =	 {9--18},
  month =	 jan,
  url =
                  {http://wwwipd.ira.uka.de/~prechelt/Biblio/1994-17.ps.gz},
  annote =	 {Classifies the papers in several journals and
                  conferences (non-CS: Optical Engineering, Neural
                  Computation; CS: TOCS, PLDI, TOPLAS, TSE, and a
                  random smaple of ACM papers) into Theory, Design,
                  Empirical, Hypothesis, and Other papers; for the
                  Design papers it classifies the amount of space
                  dedicated to the empirical validation. They observe
                  that the CS papers have a higher percentage of
                  design articles without empirical validation than
                  the non-CS papers (35\%--55\% vs. $<15$\%). They do
                  some error analysis, some of which is not convincing
                  (e.g., they use a confidence interval of 70\%
                  without justification). The paper is very good on
                  reproducability: it presents the papers used and the
                  classification used in the appendix.}
}

Über Fehler in der statistischen Methodik:

Darrel Huff
How to Lie with Statistics

Hans-Peter Beck-Bornholdt, Hans-Hermann Dubben
Der Hund, der Eier legt

Über Graphische Darstellung von Daten

Edward R. Tufte
The Visual Display of Quantitative Information