Transcript Empirical Methods in Computer Science

Statistical Methods in
Computer Science
Hypothesis Testing I:
Treatment experiment designs
Ido Dagan
Hypothesis Testing: Intro


We have looked at setting up experiments
Goal: To prove falsifying hypotheses
Goal fails =>
falsifying hypothesis not true (unlikely) =>
our theory survives

Falsifying hypothesis is called null hypothesis, marked H0

We want to show that the likelihood of H0 being true is low.
Empirical Methods in Computer Science
© 2006-now Gal Kaminka/Ido Dagan
Comparison Hypothesis Testing

A very simple design: treatment experiment

Also known as a lesion study / ablation test
treatment
control

Ind1 & Ex1 & Ex2 & .... & Exn ==> Dep1
Ex1 & Ex2 & .... & Exn ==> Dep2
Treatment condition: Categorical independent variable
What are possible hypotheses?
Empirical Methods in Computer Science
© 2006-now Gal Kaminka/Ido Dagan
Hypotheses for a
Treatment Experiment


H1: Treatment has effect
H0: Treatment has no effect

Any effect is due to chance
But how do we measure effect?
We know of different ways to characterize data:
 Moments: Mean, median, mode, ....
 Dispersion measures (variance, interquartile range, std. dev)
 Shape (e.g., kurtosis)
Empirical Methods in Computer Science
© 2006-now Gal Kaminka/Ido Dagan
Hypotheses for a
Treatment Experiment


H1: Treatment has effect
H0: Treatment has no effect

Any effect is due to chance
Transformed into:


H1: Treatment changes mean of population
H0: Treatment does not change mean of population

Any effect is due to chance
Empirical Methods in Computer Science
© 2006-now Gal Kaminka/Ido Dagan
Hypotheses for a
Treatment Experiment


H1: Treatment has effect
H0: Treatment has no effect

Any effect is due to chance
Transformed into:


H1: Treatment changes variance of population
H0: Treatment does not change variance of population

Any effect is due to chance
Empirical Methods in Computer Science
© 2006-now Gal Kaminka/Ido Dagan
Hypotheses for a
Treatment Experiment


H1: Treatment has effect
H0: Treatment has no effect

Any effect is due to chance
Transformed into:


H1: Treatment changes shape of population
H0: Treatment does not change shape of population

Any effect is due to chance
Empirical Methods in Computer Science
© 2006-now Gal Kaminka/Ido Dagan
Chance Results
The problem:
 Suppose we sample the treatment and control groups
 We find



mean treatment results = 0.7
mean control = 0.5
How do we know there is a real difference?

It could be due to chance!
In other words:
 What is the probability of getting 0.7 given H0 ?
 If low, then we can reject H0
Empirical Methods in Computer Science
© 2006-now Gal Kaminka/Ido Dagan
Testing Errors

The decision to reject the null hypothesis H0 may lead to errors
 Type I error: Rejecting H0 though it is true (false positive)
 Type II error: Failing to reject H0 though it is false (false negative)


Classification perspective of false/true-positive/negative
We are worried about the probability of these errors (upper bounds)
α = PrtypeIerror 
β = PrtypeIIerro r 

Normally, alpha is set to 0.05 or 0.01.


This is our rejection criteria for H0 (usually the focus of significance tests)
1-beta is the power of the test (its sensitivity)
Empirical Methods in Computer Science
© 2006-now Gal Kaminka/Ido Dagan
Two designs for treatment
experiments

One-sample: Compare sample to a known population


e.g., compare to specification
Two-sample: Compare two samples, establish whether they
are produced from the same underlying distribution
Empirical Methods in Computer Science
© 2006-now Gal Kaminka/Ido Dagan
1
1
One sample testing: Basics


We begin with a simple case
We are given a known control population P




Now we sample the treatment population


For example: life expectancy for patients (w/o treatment)
Known parameters (e.g. known mean)
Recall terminology: population vs. sample
Mean = Mt
Was the mean Mt drawn by chance from the known control
population?
To answer this, must know:
What is the sampling distribution of the mean of P?
Empirical Methods in Computer Science
© 2006-now Gal Kaminka/Ido Dagan
1
Sampling Distributions
Suppose given P we repeat the following:
 Draw N sample points, calculate mean M1
 Draw N sample points, calculate mean M2
 .....
 Draw N sample points, calculate mean Mn
The collection of means forms a distribution, too:
The sampling distribution of the mean
Empirical Methods in Computer Science
© 2006-now Gal Kaminka/Ido Dagan
1
Central Limit Theorem
The sampling distribution of the mean of samples of size N,
of a population with mean M and std. dev. S:
1. Approaches a normal distribution as N increases,
for which:
2. Mean = M
S
3. Standard Deviation =  N 
This is called the standard error of the sample mean
Regardless of shape of underlying population
Empirical Methods in Computer Science
© 2006-now Gal Kaminka/Ido Dagan
1
So? Why should we care?


We can now examine the likelihood of obtaining the
observed sample mean for the known population
If it is “too unlikely”, then we can reject the null hypothesis

e.g., if likelihood that the mean is due to chance is less than 5%.
The process:
 We are given a control population C


A sample of the treatment population


Mean Mc and standard deviation Sc
sample size N, mean Mt and standard deviation St
If Mt is sufficiently different than Mc then we can reject the
null hypothesis
Empirical Methods in Computer Science
© 2006-now Gal Kaminka/Ido Dagan
1
Z-test by example
We are given:
 Control mean Mc = 1, std. dev. = 0.948
 Treatment N=25, Mt = 2.8
We compute:
 Standard error = 0.948/5 = 0.19
 Z score of Mt = (2.8-population-mean-given-H0)/0.19
= (2.8-1)/0.19 = 9.47
 Now we compute the percentile rank of 9.47



This sets the probability of receiving Mt of 2.8 or higher by chance
Under the assumption that the real mean is 1.
Notice: the z-score has standard normal distribution

Sample mean is normally distributed, and subtracted/divided by
constants; Z has Mean=0, stdev=1.
Empirical Methods in Computer Science
© 2006-now Gal Kaminka/Ido Dagan
1
One- and two-tailed hypotheses

The Z-test computes the percentile rank of the sample mean


Assumption: drawn from sampling distribution of control population
What kind of null hypotheses are rejected?
Z=0
=P50
One-tailed hypothesis testing:
 H0: Mt = Mc
 H1: Mt > Mc
 If we receive Z >= 1.645, reject H0.
95% of
Population
Empirical Methods in Computer Science
© 2006-now Gal Kaminka/Ido Dagan
Z=1.645
=P95
1
One- and two-tailed hypotheses

The Z-test computes the percentile rank of the mean


Assumption: drawn from sampling distribution of control population
What kind of null hypotheses are rejected?
Two-tailed hypothesis testing:
 H0: Mt = Mc
 H1: Mt != Mc
 If we receive Z >= 1.96, reject H0.
 If we receive Z <= -1.96, reject H0.
Z=1.96
=P97.5
Z=-1.96
=P2.5
Z=0
=P50
95% of
Population
Empirical Methods in Computer Science
© 2006-now Gal Kaminka/Ido Dagan
1
Two-sample Z-test


Up until now, assumed we have population mean
But what about cases where this is unknown?
This is called a two-sample case:
 We have two samples of populations



Treatment & control
For now, assume we know std of both populations
We want to compare estimated (sample) means
Empirical Methods in Computer Science
© 2006-now Gal Kaminka/Ido Dagan
Two-sample Z-test
(assume std known)

Compare the differences of two population means



When samples are independent (e.g. two patient groups)
H0: M1-M2 = d0
H1: M1-M2 != d0 (this is the two-tailed version)
M  M 2   d 0
z= 1
 σ12 σ 22 
 + 
 n1 n2 


var(X-Y) = var(X) + var(Y) for independent variables
When we test for equality, d0 = 0
Empirical Methods in Computer Science
© 2006-now Gal Kaminka/Ido Dagan
1
Mean comparison when std
unknown
Up until now, assumed we have population std.
 But what about cases where std is unknown?
=> Have to be approximated

When N sufficiently large (e.g., N>30)
 When population std unknown: Use sample std

Population std is:

Sample std is:
Empirical Methods in Computer Science
 SS
σ=  X
 N
2




Xi

X




=


N



2




Xi

X
 SS X 


SX = 
= 

N 1 
 N 1


© 2006-now Gal Kaminka/Ido Dagan
2
2
The Student's t-test

Z-test works well with relatively large N



e.g., N>30
But is less accurate when population std unknown
In this case, and small N: t-test is used

It approaches normal for large N
t =0
=P50
t-test:
 Performed like z-test with sample std
 Compared against t-distribution



t-score doesn’t distribute normally
(denominator is variable)
Assumes sample mean is normally distributed
thicker tails
Requires use of size of sample

N-1 degrees of freedom, a different distribution for each degree
Empirical Methods in Computer Science
© 2006-now Gal Kaminka/Ido Dagan
2
t-test variations
Available in excel or statistical software packages
 Two-sample and one-sample t-test
 Two-tailed, one-tailed t-test
 t-test assuming equal and unequal variances
 Paired t-test

Same inputs (e.g. before/after treatment), not independent
The t-test is common for testing hypotheses about means
Empirical Methods in Computer Science
© 2006-now Gal Kaminka/Ido Dagan
2
Testing variance hypotheses

F-test: compares variances of populations

Z-test, t-test: compare means of populations
Testing procedure is similar
H0: σ12 = σ 22
H1: σ12  σ 22
OR σ12 > σ 22

Now calculate


f=
s 21
s
2
2
OR σ12 < σ 22
, where sx is the sample std of X
When far from 1, the variances likely different
To determine likelihood (how far), compare to F distribution
Empirical Methods in Computer Science
© 2006-now Gal Kaminka/Ido Dagan
2
The F distribution

F is based on the ratio of population and sample variances


S12 / σ12
F= 2 2
S2 / σ 2
According to H0, the two standard deviations are equal
F-distribution


Two parameters: numerator and denominator degrees-of-freedom
 Degrees-of-freedom (here): N-1 of sample
Assumes both variables are normal
Empirical Methods in Computer Science
© 2006-now Gal Kaminka/Ido Dagan
2
Other tests for two-sample testing



There exist multiple other tests for two-sample testing
Each with its own assumptions and associated power
For instance, Kolmogorov-Smirnov (KS) test

Non-parametric estimate of the difference between two distributions
Turn to your friendly statistics book for help
Empirical Methods in Computer Science
© 2006-now Gal Kaminka/Ido Dagan
2
Testing correlation hypotheses


We now examine the significance of r
To do this, we have to examine the sampling distribution of r

What distribution of r values will we get from the different samples?

The sampling distribution of r is not easy to work with

Fisher's r-to-z transform:
1+ r
z r  = 0.5ln
1 r
Where the standard error of the r sampling distribution is:
Empirical Methods in Computer Science
© 2006-now Gal Kaminka/Ido Dagan
2
Testing correlation hypotheses
We now plug these values and do a Z-test
For example:
 Let the r correlation coefficient for variables x,y = 0.14



Suppose n = 30
H0: r = 0
H1: r != 0
1 + 0.14
z0 = z 0.14  = 0.5ln
= 0.141
1  0.14
Cannot reject H0
Empirical Methods in Computer Science
© 2006-now Gal Kaminka/Ido Dagan
Treatment Experiments
(single-factor experiments)

Allow comparison of multiple treatment conditions
treatment1
treatment2
control


Ind1 & Ex1 & Ex2 & .... & Exn ==> Dep1
Ind2 & Ex1 & Ex2 & .... & Exn ==> Dep2
Ex1 & Ex2 & .... & Exn ==> Dep3
Compare performance of algorithm A to B to C ....
Control condition: Optional (e.g., to establish baseline)
Cannot use the tests we learned: Why?
Empirical Methods in Computer Science
© 2006-now Gal Kaminka/Ido Dagan
2