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 typischen Falls 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 Programmen, die von verschiedenen Compilern compiliert
wurden).
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?).
Overloaded graphics
3D Graphics
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://plato.asu.edu/ftp/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