Showing posts with label resampling. Show all posts
Showing posts with label resampling. Show all posts

Friday, February 19, 2010

Visualizing Confidence Intervals

This post is about visualizing confidence intervals. Matplotlib has some really neat capabilities that are useful in that regard, but before we get into the pictures, here’s a short digression on statistics.

I like resampling-based statistics a lot, as an engineer their practicality and intuitiveness appeals to me. It has been shown that students learn better and enjoy statistics more when they are taught using resampling methods. Here’s a nice description of the motivation for resampling (ok, maybe it's a bit over the top):

For more than a century the inherent difficulty of formula-based inferential statistics has baffled scientists, induced errors in research, and caused million of students to hate the subject.

Complexity is the disease. Resampling (drawing repeated samples from the given data, or population suggested by the data) is a proven cure. Bootstrap, permutation, and other computer-intensive procedures have revolutionized statistics. Resampling is now the method of choice for confidence limits, hypothesis tests, and other everyday inferential problems.

In place of the formidable formulas and mysterious tables of parametric and non-parametric tests based on complicated mathematics and arcane approximations, the basic resampling tools are simulations, created especially for the task at hand by practitioners who completely understand what they are doing and why they are doing it. Resampling lets you analyze most sorts of data, even those that cannot be analyzed with formulas.

– Resampling Stats

One of the useful things to do is resampling of residuals. The assumptions underlying most models are that the magnitude and sign of the residuals are not a function of the independent variable. This is the hypothesis which we’ll base our resampling on. First we fit a model (a line in these examples) to some data, then calculate all the residuals (difference between the data and the model). Then we can apply a couple of different resampling approaches towards understanding the confidence intervals.

A permutation-based way of establishing confidence intervals is easily accomplished in Python using the itertools module’s permutation function. This is an exact method, but the number of permutations grows as the factorial of the sample size. The six-sample example shown in figure 1 has 6! = 720 possible permutations of the residuals. With only ten samples the number of permutations grows to 3628800 (over three million). The point of this post is visualization, so plotting three million lines may not be worth our while.


PIC

Figure 1: Residual Permutations


Figure 1 shows the least-squares-fit line in solid black, with the lines fit using the permuted residuals slightly transparent. Here’s the Python to accomplish that:

 
nx = 6 
x = sp.linspace(0.0, 1.0, nx) 
data = x + norm.rvs(loc=0.0, scale=0.1, size=nx) 
yp = sp.polyfit(x, data, 1) 
y = sp.polyval(yp,x) 
r = data - y 
 
nperm = factorial(nx) 
for perm in permutations(r,nx): # loop over all the permutations of the resids 
    pc = sp.polyfit(x, y + perm, 1) 
    p.plot(x, sp.polyval(pc,x), k-, linewidth=2, alpha=2.0/float(nperm)) 
p.plot(x, y, k-) 
p.plot(x, data, ko)

We’ve used the alpha argument to set the level of transparency in each of the permutations. Where more of the lines overlap, the color is darker. This gives a somewhat intuitive display of the ’weight’ of the variation in the model fit (confidence).

As mentioned above, doing exact permutation-based statistics becomes computationally prohibitive rather quickly, so we have to go to the random-sampling based approximations. The bootstrap is one such approach.

Rather than generating all possible permutations of the residuals, the bootstrap method involves drawing random samples (with replacement) from the residuals. This is done in Python easily enough by using the random_integer function to index into our array of residuals.

 
import scipy as sp
 
bootindex = sp.random.random_integers
 
nboot = 400 
for i in xrange(nboot): # loop over n bootstrap samples from the resids 
    pc = sp.polyfit(x, y + r[bootindex(0, len(r)-1, len(r))], 1) 
    p.plot(x, sp.polyval(pc,x), k-, linewidth=2, alpha=3.0/float(nboot)) 
p.plot(x, y, k-) 
p.plot(x, data, ko)

Figure 2 shows the method applied to the same six data points as with the permutation.


PIC
Figure 2: Residual Bootstraps


Since the sampling in the bootstrap approach is with replacement we can get sets of residuals that have repeated values. This tends to introduce a bit of bias in the direction of that repeated residual. You can see that behaviour exhibited in Figure 2 by the spreading of the lines around the middle of the graph, in contrast to the tight intersection in the middle of Figure 1.

Of course the reason the bootstrap method is useful is we often have large samples that are impractical to do with permutations. The Python to generate the 12-sample example in Figure 3 is shown below.

 
nx = 12 
x = sp.linspace(0.0, 1.0, nx) 
data = x + norm.rvs(loc=0.0, scale=0.1, size=nx) 
yp = sp.polyfit(x, data, 1) 
y = sp.polyval(yp,x) 
r = data - y 
p.figure() 
for i in xrange(nboot): # loop over n bootstrap samples from the resids 
    pc = sp.polyfit(x, y + r[bootindex(0, len(r)-1, len(r))], 1) 
    p.plot(x, sp.polyval(pc,x), k-, linewidth=2, alpha=3.0/float(nboot)) 
p.plot(x, y, k-) 
p.plot(x, data, ko)


PIC
Figure 3: Residual Bootstraps, large sample


These sorts of graphs probably won’t replace the standard sorts of confidence intervals (see the graph in this post for example), but it’s a kind of neat way of looking at things, and a good demo of some of the cool stuff you can do really easily in Python with Matplotlib and Scipy.

Monday, October 19, 2009

JASSM Bootstrap Reliability II

I previously did an analysis of JASSM's reliability using Octave. It's a very simple exercise using the built-in Octave function empirical_rand() and public statements by various folks concerning the flight tests.

As reported by Reuters, JASSM has had success in recent tests. To be quantitative, 15 out of 16 test flights were a success. Certainly good news for a program that's been bedevilled by flight test failures and Nunn-McCurdy breaches.

The previous analysis can be extended to include this new information. This time we'll use Python rather than Octave. There is not (that I know of) a built-in function like empirical_rand() in any of Python's libraries, but it's relatively straightforward to use random integers to index into arrays and accomplish the same thing.

def bootstrap(data, nboot):
"""Draw nboot samples from the data array randomly with replacement, ie
a bootstrap sample."""
bootsample = sp.random.random_integers
return(data[bootsample(0, len(data)-1, (len(data), nboot))])

Applying this function to our new data vectors to get bootstrap samples is easy.

# reliability data for July 2009, based on Reuters report
d09_jul_tests = 19
d09_jul = sp.ones(d09_jul_tests, dtype=float)
d09_jul[0:3] = 0.0

# generate the bootstrap samples:
d09_jul_boot = sp.sum(bootstrap(d09_jul, nboot), axis=0) / float(d09_jul_tests)
# find the number of unique reliabilities to set the number of bins for the histogram:
d09_jul_nbins = sp.unique(d09_jul_boot).size



So, is it a 0.9 missile or a 0.8 missile? We should probably be a little more modest in the inferences we wish to draw from such small samples. As reported by Bloomberg the Air Force publicly contemplated cancellation for a missile with reliability distributions like the blue histogram shown below (six of ten failed), while stating that if 13 of 16 were successful (the green histogram) that would be acceptable. The figure below shows these two reliability distributions along with the actual recent performance.

This seems to be a reasonably supported inference from these sample sizes, the fixes that resulted in the recent 15 out of 16 successes had a measurable effect when compared to the 4 out of 10 performance.

Not that binary outcomes for reliability are a great measure, they just happen to be easily scrape-able from press releases. The figure below illustrates the problem, there just isn't much info in each 1 or 0, so really cranking up the number of samples only slowly improves the power (reduces the area of overlap between the two distributions).

Tuesday, July 7, 2009

JASSM bootstrap reliability

The Joint Air-to-Surface Stand-off Missile has been in the news lately. It's the same old story that's been going on ever since it was "fielded". A few missiles fail to function properly in testing, the Air Force says Lockheed-Martin needs to bring up the reliability or the program will be terminated. Lockheed-Martin agrees that more work needs to be done ("keep the money flowing") to improve the reliability, and they'll work diligently with their Air Force team members to serve the warfighter.

That's military-industrial complex business as usual, not that interesting. The neat part is that there's enough information in most of those press releases and news articles to do some resampling statistics on the reliability of the missile. So, in the interest of supporting "an alert and knowledgeable citizenry" (see the Eisenhower video at the bottom of this post) here are some bootstraps on JASSM reliability.

It is really easy to do in Octave using the empirical_rnd() function.

n_09 = 19; % number of tests, based on stated 79% success rate
f_09 = 4; % number of failures
nbins_09 = 14;
t_09 = ones(n_09, 1);
t_09(1:f_09) = 0;
boot_09 = empirical_rnd(t_09, n_09, nboot); % really easy to do
% bootstraps
reliability_09 = sum(boot_09, 1) / n_09;

The sample size n_09 and number of failures f_09 are based on the recent Reuters story:
Four JASSM missiles tested in November, January and February did not detonate on impact or had other problems, raising fresh questions about the program. But the missile still had a reliability rate of 79 percent, and was on track to reach the 90 percent goal, the Air Force said. --Reuters, 6 Jul 2009

So, according to the recent reports JASSM should work about four times out of five (the AF wants it to work nine times out of ten). Here's the "4 out of 5" reliability distribution (based on the bootstrap shown above) with 19 samples:

Back in 2004 JASSM had a claimed reliability of 76%:
We have had 29 launches of JASSM and we have a 76 percent success rate. --Judy Stokely, deputy of acquisition at the Air Armament Center

Which means it should work three times out of four. Here's a "3 out of 4" missile's reliability distribution with 29 samples:

The sampling distributions are too large to measure a change as small as the difference between 0.76 reliability and 0.79 reliability, so it's statistically the same missile now that it was back in 2004. In both distributions the desired 0.9 reliability is out on the tail of the distributions, i.e. you can't claim it's a "9 out of 10" missile with much credence.

A more interesting question is what sort of sampling distribution would you get from nine successes and one failure (the desired nine out of ten missile)?

With a sample size of only ten it would be pretty hard to tell the difference between a "9 out of 10" missile and a "4 out of 5" missile. Based on the press releases apparently a "4 out of 5" missile is unacceptable, but what level of confidence will the Air Force place on knowing that they have 0.9 reliability?

Eisenhower on the military industrial complex:


Here's the Octave file with the code for doing the bootstraps.

Also, thanks to Michael J.T. O'Kelly's bootstrap.py for showing how easy it is to resample with replacement from an array in Python using SciPy.

Sunday, October 26, 2008

The Shuffle

The shuffle, also known as the Fisher's Exact Test, is a permutation test that can be used to estimate the sampling distribution of a statistic without relying on parametric assumptions. This is especially important when sample sizes are small. The other neat thing about permutation tests is that you don't have to know what the distribution of your statistic is. So if you have a really odd function of your data that you want to use rather than one of the classical statistics you can.

Octave has a great built-in function called nchoosek which makes shuffling a breeze. Called with scalar arguments it returns the value of the binomial coefficient, which is the number of ways you can choose k things from n things (k<=n). For fixed n, nchoosek is maximum when k=n/2. That is plotted below for n=2:24.

Notice that's a log-log scale, as n increases it quickly becomes intractable to perform a complete permutation test.

Suppose we have two data vectors, and we want to know if they are from populations with different means. We can use the normrnd() function to draw 8 samples from a normal distribution with 0 mean and 8 samples from a normal distribution with a mean of 1.

n=8;
x1 = normrnd(0,1,n,1);
x2 = normrnd(1,1,n,1);
perms = nchoosek( [x1;x2], n );

We stored all 12870 permutations of the vectors (16 choose 8) in the matrix perms. Now we use the built-in function complement to find the difference of the means under each of those labellings.

for(i=1:length(m1) )
comps(i,:) = complement( perms(i,:), [x1;x2] );
endfor
m1 = mean( perms, 2 ); % take row-wise averages, DIM=2
m2 = mean( comps, 2 ); % take row-wise averages, DIM=2
m_shuff = m1 - m2;

Now we can use the distribution of m_shuff to decide if the difference in the means of our two data vectors is significant.


Octave script with all of these calculations: shuffle.m.

Thursday, October 23, 2008

Is Octave Slow?

The answer, like most things worth asking the question about, is "Well, it depends..."

I'm not going to talk about "computer time" vs. "programmer time"; though that's probably one of the most important considerations most of the time (check out Paul Graham's essays if you need convincing). I'll just talk about what takes a long time to compute in Octave, and what trade-offs can be made to improve the situation. We'll dwell mostly on the first tip from the Octave Manual (you'll see it's first for good reason). The other important thing to do is always allocate memory before looping over a vector (eg. x=zeros(n,1)).

Suppose we have a simple re-sampling problem. We would like to estimate the sampling distribution of a statistic of our data. The data could be a simple vector of 1 or 0 representing success or failure of a trial, and we want to estimate the probability of success.

x = [1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0];

One method to solve the problem would be to use a for loop:

X = empirical_rnd(N,x); % get a bootstrap sample from x
for(j=1:10) % timing loop, measure a couple times to get an idea of the
% variation
tic();
for( i=1:N-n ) % loop over the bootstrap samples
p(i) = sum( X(i:i+n-1) )/n;
endfor
fortime(j)=toc();
endfor

With N=20000, this takes 1.09 seconds on my old laptop, that seems kind of slow. The sampling distribution for the probability of success is shown in the figure below.

It is always a good idea to vectorize what you can when in Octave, so the method below does just that.

X = empirical_rnd(x,N,n);
for(j=1:10)
tic();
P = sum(X,2)/n;
vecttime(j) = toc();
endfor

With n=20000, this takes 0.009 seconds on the same old laptop, that's a speed-up of 2 orders of magnitude!

Well, those are trivial examples of vectorizing a calculation to avoid the dreaded for-loop. What happens when subsequent calculations depend on the results of previous iterations?

tic();
p1(1) = 0;
for(i=2:N)
t = t + dt;
p1(i) = p1(i-1)+dt*2*t;
endfor
toc()

This loop integrates x*x numerically, with N=20000 it takes ~0.75 seconds. We can't vectorize, so how do we speed it up? Octave has some good sparse matrix capabilities, maybe we could recast the problem as a sparse matrix solve.

Now we are trading memory for speed. In the for-loop implementation we just have to store the vector p. If we want to use Octave's sparse matrix facilities we need to store the two diagonals of our operator, so that roughly triples the memory requirements. Given the enormous size of modern computer memory, most toy problems should fit (if your problem doesn't fit, why are you still using Octave?).

tic();
A = spdiag( ones(N,1), 0 );
A = A + spdiag( -ones(N-1,1), -1 );
p2 = A\(dt*2*t);
toc()

The direct solution of the simple bi-diagonal system, with N=20000 takes ~0.019 seconds, better than 2 orders of magnitude speed-up over the for-loop implementation. For more complex sparse operators one of the iterative schemes might be appropriate.


The moral: if your problem is small enough to fit into memory, cram it all in and don't use for-loops!

Is Octave slow? Well, it depends, if you use for-loops it is.

Further Reading


A couple more posts on optimizing your Octave code.