1 Empirical Research Methods in Computer Science Lecture 1, Part 1 October 12, 2005 Noah Smith http://nlp.cs.jhu.edu/~nasmith/erm

2 Empirísmo empeiros: experimentado (peira = análisis o prueba) cf. rationalismo

3 Exploración & Experimento Análisis Exploratorio de Data Prueba de Hipótesis Modelo para explorar visualizar resumir confirmar Experimento si/no?

4 Qué HW? Teoría  Algoritmos, Computación Práctica  Software Engineering, Areas de Aplication Sistemas  OS, Arquitectura

5 A quién le interesa? 1. cualquier persona que quiera hacer investigación 2. cualquier persona que quiera seguir la investigación (i.e., read papers) 3. cualquier persona que quiere ser capaz de tomar decisiones inteligentes / sacar conclusiones 4. cualquier persona que le gusta pensar críticamente

6 Basic Research Questions

7 Preguntas Básicas de Investigación int foo() {... }

8 Por qué molestarse? int foo() {... } int foo() {... } int foo() {... } int foo() {... } int foo() {... } int foo() {... }

9 Variation → Statistics int foo() {... } el determinismo no es lo suficientemente bueno como cualquier otro!

10 Statistics, in this Course Nonparametric tests Sampling Later: Parametric tests (when and why)

11 Warning Theory (complexity analysis, etc.) is important, too! Many phenomena aren’t surprising if you know your math.

12 Goals Know how to look for the interesting experiments Know how to construct experiments Know how to analyze the results Be critical of all claims Develop an aesthetic for good empirical work!

13 Empiricism is FUN! Especially in computer science!

14 Basic Course Information instructors: Noah and David {n,d}[email protected] Wednesdays 4-5:15 pm no class Thanksgiving week homeworks (65%); final exam (30%)

15 About Us Combined 19 years of experience in CS; 36 years programming Autodidact empiricists Research interests in statistical modeling and machine learning (Eisner/Yarowsky lab) NEB 332

16 Plan Hypothesis testing, statistics (2) Case study: runtime (2) Exploratory data analysis (1) Parametric testing, modeling (1-2) Statistical analysis of computer programs (1)

17 MO Come to class. Send us feedback anytime.  What do you want to know?  Bring us papers.

18 Empirical Research Methods in Computer Science Lecture 1, Part 2 October 12, 2005 David Smith

19 Terminological Prelude Populations  Population distributions  “All possible files”. How big? Samples  Sampling distributions  “Files on my system” Statistics  Functions of data  “Size of my files” Models  Parameters

20 And now for some data

21 Abnormality

22

23 The Bootstrap Simulates the sampling distribution Proposed by Efron in 1979  Anticipated by permutation tests, jackknife, cross-validation From original sample of size n, draw B samples of size n with replacement and calculate the statistic on each

24 Sampling Distributions μ μ μ μ μ

25 Bootstrapping the Mean

26 What’s Going On? Why is bootstrap distribution normal? Remember, this is a mean Linearity of Expectation Central Limit Theorem Closed form standard error for means

27 More Heavy Tails

28 Sampling Still Normal

29 Bivariate Data

30 Compression Performance

31 Bootstrapping Correlation

32 Error, Confidence, Testing Standard error from sampling distribution Confidence intervals: bounding error probability (e.g. to 5%) Hypothesis testing: how likely is a particular statistic under our assumptions?

33 Hypothesis Testing One-sample  “Are these data normal/Poisson/…?” Two-sample  “Are these two samples from the same distribution?” Paired-sample  “Is this technique better than that?”

34 Your First Assignment Data compression Three-way tradeoff  Compression  Speed  Loss Degenerate cases (cat, echo ‘’, …) Unknown distribution of input