Research Methods In Computer Science - UAntwerpen


Research Methodsin Computer Science(Serge Demeyer — University of Antwerp)AnSyMoAntwerp Systems and software Modelling Antwerpen

Helicopter View(Ph.D.)ResearchHow to perform research ?(and get “empirical” results)How to write research ?(and get papers accepted)How many of you havedone / will do a case-study ?1. Research Methods!2

Zürich KunsthausAntwerp Middelheim

1. Research MethodsIntroduction Origins of Computer Science Research PhilosophyResearch Methods 1. Feasibility study 2. Pilot Case 3. Comparative study 4. Observational Study [a.k.a. Etnography] 5. Literature survey 6. Formal Model 7. SimulationConclusion Studying a Casevs. Performing a Case Study Proposition Unit of Analysis Threats to Validity1. Research Methods!4

Computer ScienceAll science is either physics or stamp collecting (E. Rutherford)We study artifacts produced by humansComputer science is no more about computers thanastronomy is about telescopes. (E. Dijkstra)Computer scienceComputer engineeringInformaticsSoftware Engineering1. Research Methods!5

Science vs. EngineeringSciencePhysicsBiologyCivil ftware Chemistry and MaterialsMathematics Engineering?Geography1. Research MethodsEngineeringElectro-MechanicalEngineering!6

Mathematical OriginsTuring Machines Halting problemAlgorithmic Complexity P ? NPCompilers Chomsky hierarchyDatabases Relational model(inductive) Reasoning logical argumentation formal models,theorem proving, axioms & lemma’s foo, bar type of examples “deep” and generic universalknowledgeGödel theorem: consistency of the system is not provable in the system.A complete and consistent set of axiomsfor all of mathematics is impossible1. Research Methods!7

Engineering OriginsComputer Engineering Moore’s law: “the number oftransistors on a chip will doubleabout every two years” Self-fulfilling prophesy Hardware technology RISC vs. CISC MPSoC Compiler optimization peephole optimization branch predictionEmpirical Approach Tom De Marco: “you cannotcontrol what you cannotmeasure” quantify mathematical model Pareto principle 80 % - 20 % rule(80% of the effects comefrom 20% of the causes)As good as your next observation.Premise: The sun has risen in the east every morning up until now.Conclusion: The sun will also rise in the east tomorrow. Or Not ?1. Research Methods!8

Influence of SocietyLives are at stake(e.g., automatic pilot,nuclear power plants)Huge amounts of moneyare at stake(e.g., Ariane V crash,Denver Airport Baggage)Software became Ubiquitous its not a hobby anymoreCorporate success or failureis at stake (e.g., telephonebilling, VTM launching 2ndchannel)1. Research Methods!9

Interdisciplinary Science“Soft”Sciences1. Research 10

The Oak ForestRobert Zünd - 1882

Franz and LucianoFranz Gertsch - 1973

ObjectiveSubjective Plato’s cave Scientific Paradigm (Kuhn) Dominant paradigm / Competing paradigms / Paradigm shift Normal science vs. Revolutionary science1. Research Methods!13

Dominant view on Research MethodsPhysics(“The” Scientific method) form hypothesis about aphenomenon design experiment collect data compare data to hypothesis accept or reject hypothesis publish (in Nature) get someone else to repeatexperiment (replication)Medicine(Double-blind treatment) form hypothesis about atreatment select experimental and controlgroups that are comparableexcept for the treatment collect data commit statistics on the data treatmentdifference(statistically significant)Cannot answer the “big” questions in timely fashion smoking is unhealthy climate change darwin theory vs. intelligent design agile methods1. Research Methods!14

!"""!"# %&'()* % ,(-&./% (01(23456"Research Methods in Computer Science Easterbrook, S. M., Singer, J., Storey,M, and Damian, D. Selecting EmpiricalMethods for Software EngineeringResearch. Appears in F. Shull and J.Singer (eds) "Guide to AdvancedEmpirical Software Engineering",Springer, 2007. Gordona Dodif-Crnkovic, “ScientificMethods in Computer Science” Andreas Höfer, Walter F. Tichy, Statusof Empirical Research in SoftwareEngineering, Empirical SoftwareEngineering Issues, p. 10-19,Springer, 2007.1. Research MethodsStatic analysisLesso ns learnedLegacy dataLiterature searchValidation methodDifferent Sources Marvin V. Zelkowitz and Dolores R.Wallace, "Experimental Models forValidating Technology", IEEEComputer, May 1998.Field stu dyAssertio nCase stu dyProject mo nitorin g1995 (152 papers)1990 (217 papers)1985 (243 papers)Simulatio nDynamic analysisSyn theticReplicated"No experimen tatio n0371(81"# %&'"()* ,- .&,/"0& 1"/23 %&'/"*.,"1&-14&-1 ,5"&6" .*6-,78"0510"lection method that conforms to any one of the 12given data collection methods.Our 12 methods are not the only ways to classifydata collection, although we believe they are the mostcomprehensive. For example, Victor Basili6 calls anexperiment in vivo when it is run at a development location and in vitro when it is run in an isolated, controlledsetting. According to Basili, a project may involve oneteam of developers or multiple teams, and an experiment may involve one project or multiple projects. Thisvariability permits eight different experiment classifications. On the other hand, Barbara Kitchenham7 considers nine classifications of experiments divided intothree general categories: a quantitative experiment toidentify measurable benefits of using a method or tool,a qualitative experiment to assess the features providedby a method or tool, and a benchmarking experimentto determine performance.MODEL VALIDATIONTo test whether the classification presented here152025303540Percen tage o f papersvalidate the claims in the paper. For completeness weadded the following two classifications:1. Not applicable. Some papers did not address somenew technology, so the concept of data collection doesnot apply. For example, a paper summarizing a recentconference or workshop wouldn’t be applicable.2. No experiment. Some papers describing a newtechnology contained no experimental validations.In our survey, we were interested in the data collection methods employed by the authors of the papersin order to determine our classification scheme’s comprehensiveness. We tried to distinguish between dataused as a demonstration of concept (which mayinvolve some measurements as a “proof of concept,”but not a full validation of the method) and a trueattempt at validation of their results.As in the study by Walter Tichy,8 we considered ademonstration of technology via example as part ofthe analytical phase. The paper had to go beyond that "!15

Case studies - Spectrum7. Simulation what if ?case studies are widely used in computer science“studying a case” vs. “doing a case study”6. Formal Model underlying concepts ?5. Literature survey what is known/unknown ?4. Observational Study What is “it” ?3. Comparative study is it better ?2. Pilot Case, Demonstrator is it appropriate ?1. Feasibility study is it possible ?1. Research MethodsSource: Personal experience(Guidelines for Master Thesis Research –University of Antwerp)!16

The sixteenth of septemberRene Margritte

Feasibility StudyHere is a new idea, is it possible ? Metaphor: Christopher Columbus and western route to India Is it possible to solve a specific kind of problem effectively ? computer science perspective (P NP, Turing test, ) engineering perspective (build efficiently; fast — small) economic perspective (cost effective; profitable) Is the technique new / novel / innovative ? compare against alternatives See literature survey; comparative study Proof by construction build a prototype often by applying on a “CASE” Conclusions primarily qualitative; "lessons learned" quantitative- economic perspective: cost - benefit- engineering perspective: speed - memory footprint1. Research Methods!18

The ProphetPablo Gargallo

Pilot Case (a.k.a. Demonstrator)Here is an idea that has proven valuable; does it work for us ? Metaphor: Portugal (Amerigo Vespucci) explores western route proven valuable accepted merits (e.g. “lessons learned” from feasibility study) there is some (implicit) theory explaining why the idea has merit does it work for us context is very important Demonstrated on a simple yet representative “CASE” “Pilot case” “Pilot Study” Proof by construction build a prototype apply on a “case” Conclusions primarily qualitative; "lessons learned" quantitative; preferably with predefined criteria compare to context before applying the idea !!1. Research Methods!20

Walking manStanding Figure– Alberto Giacometti

Comparative StudyHere are two techniques, which one is better ? for a given purpose ! (Not necessarily absolute ranking) Where are the differences ? What are the tradeoffs ? Criteria check-list predefined- should not favor one technique qualitative and quantitative- qualitative: how to remain unbiased ?- quantitative: represent what you want to know ? Criteria check-list should be complete and reusable ! If done well, most important contribution (replication !) See literature survey Score criteria check-list Often by applying the technique on a “CASE” Compare typically in the form of a table1. Research Methods!22

Observational Study [Ethnography]Understand phenomena through observations Metaphor: Diane Fossey “Gorillas in the Mist” systematic collection of data derived from direct observation of theeveryday life phenomena is best understood in the fullest possible context observation & participation interviews & questionnaires Observing a series of cases “CASE” observation vs. participation ? example: Action Research Action research is carried out by people who usually recognize a problem or limitation intheir workplace situation and, together, devise a plan to counteract the problem,implement the plan, observe what happens, reflect on these outcomes, revise the plan,implement it, reflect, revise and so on. Conclusions primarily qualitative: classifications/observations/ 1. Research Methods!24

Torben GiehlerMatterhornPaul KleeNiesen

Literature SurveyWhat is known ? What questions are still open ? source: B. A. Kitchenham, “Procedures for Performing SystematicReviews”, Keele University Technical Report EBSE-2007-01, 2007Systematic “comprehensive” precise research question is prerequisite defined search strategy (rigor, completeness, replication) clearly defined scope- criteria for inclusion and exclusion specify information to be obtained- the “CASES” are the selected papers outcome is organizedclassificationtaxonomyconceptual modeltabletreefrequency1. Research Methods!26

Literature survey - exampleCornelissenet al. - An VOL.Systematicof ProgramIEEE TRANSACTIONS ON SOFTWAREENGINEERING,0, NO. Survey0, JANUARY2000 Comprehension through Dynamic Analysis5;!#1 '#0!#" 1'-!"# %&'()#)*%" #" 1'-0*#,.#'1'9!)"09')&' &1 0?@@0A0 &)'0BCD ) " !10!#" 1'-'1' " ,)7) " !10-'1' " ,): )!10-'1' " ,)#'*'#') '0 4' 3 )5 #" 1'-0*#,.,"4'#09')&'-!"# %&'()'&'%# * ""# %&"'*#!.'2,#3SourceBas Cornelissen, Andy Zaidman, Arie vanDeursen, Leon Moonen, Rainer Koschke. ASystematic Survey of ProgramComprehension through Dynamic AnalysisIEEE Transactions on Software Engineering(TSE): 35(5): 684-702, 2009.7) " !1!""# %&"'-!""# %&"'5')'#!1 /!" ,)!""# %&"' (')" * !" ,)!##" ,-#'( .' # / %0# * !"# %&',(("- .) %89'#9 '20,* 4!#! "'# /'(!#" 1'--&.!# /!" ,)0,*- . 1!#02,#3!""# %&"'!-- 5).')"Cornelissenet al. - An SystematicSurvey ofENGINEERING,Program ComprehensionDynamicAnalysisIEEE TRANSACTIONSON SOFTWAREVOL. 0, NO.through0, JANUARY2000!"# %&'(%10"0%#'" 20# * E' ,.')(!" ,)- )"'#6#'"!" ,)3 #'"4"'#0# * &**Fig. 1.Overview of the systematic survey process.22(#)*(&!"#% #(##!*vague, as it does not specify which properties are analyzed. To allow the definition to serve in"#multiple problem domains, the exact propertiesunder analysis are left open."*') '! % %While the definition of dynamic analysis is rather abstract,we can elaborateupon the benefits&% &%and limitations of using dynamic analysis in programcomprehensioncontexts. The benefits that *&'we consider are:&&((#&*##& && &*!The fact that a goal-oriented strategy can be used, which entails the definition of anexecution scenariosuch that only the parts of interest of the software system are analyzed.1. ResearchMethods5; 3:14,12-0 D731 74326,@2- 636, 4,C ,1;:C@ 32?32,/:,1 7 171/E1:. 62,341 197C3 :11/78F The preciseness with regard to the actual*behavior of the software system, for example, inthe context of object-oriented software software with its late binding mechanism. '* % # # " ' ,.0- /15-3 234678- 2-/93 ,:262 3 /,0;1 3 2;9/7 2 ?@2::;- : 72692 343 ,/62,8 /764- 0 3;?. ,/ A/ 86 5,46- B2,10;:C@ /636,;2 /7CCC- 6@3 2,;/66 ,/ -6 A3 D7 B-2?C7,46 6 1023;972, //6,;/4,; /,10 % %!27

KleeBergbahnVojin BakicBull

Formal ModelHow can we understand/explain the world ? make a mathematical abstraction of a certain problem analytical model, stochastic model, logical model, re-writesystem, . often explained using a “CASE” prove some important characteristics based on inductive reasoning, axioms & lemma’s, Motivate which factors are irrelevant (excluded) and which are not (included) ? which properties are worthwhile (proven) ? See literature surveyProblemProblemProperties?Abstraction1. Research MethodsMathematicalProperties!29

HodlerEiger, Mönch and Jungfrau in the Morning SunSeuratEiffel Tower

SimulationWhat would happen if ? study circumstances of phenomena in detail simulated because real world too expensive; too slow or impossible make prognoses about what can happen in certain situations test using real observations, typically obtained via a “CASE

Methods in Computer Science” Andreas Höfer, Walter F. Tichy, Status of Empirical Research in Software Engineering, Empirical Software Engineering Issues, p. 10-19, Springer, 2007. lection method that conforms to any one of the 12 given data collection methods. Our 12 methods are not the only ways to