# How is approximately unbiased bootstrap better than a regular bootstrap with regards to hierarchical clustering?

I asked this question at BioStar but did not get a reply, so Im posting the question here.

What is a simple explanation of what an approximately unbiased bootstrap is with regards to hierarchical clustering?

From what I read, it alters the sample size during randomization to calculate p-values.

How is this approach better than the regular bootstrap which keeps the sample size intact while randomizing and also is it randomization with replacement?

Edit: There is an R package pvclust that calculates p-value and approximately unbiased p-value. My apologies for being unclear as I thought this was due to a difference in the bootstrap method. Thanks for all the answers and comments!

-
Welcome to the site, @helen. Providing references would have helped. My gut feeling is that you are referring to some highly specific forms of the bootstrap developed in a small niche of the bootstrap literature, so more guidance may be needed for simple folks like us. Michael Chernick might be able to answer this off the top of his head, but I would personally like to see more of the explanation of the "approximately unbiased" bootstrap does (as well as your understanding of what the "regular" bootstrap does, as to me, there is no such thing as the regular bootstrap.) – StasK Jul 6 '12 at 0:25
"Approximately unbiased bootstrap" is a phrase, not a technique. It shows up, e.g., in a recent paper by Wang et al in Nature.‌​. The description is obscure and without references: "After bootstrap re-sampling (10,000 iterations), approximately unbiased (AU) P value is provided in the output figure. AUP value, which is calculated by multiscale bootstrap re-sampling, is a better approximation to unbiased P value than bootstrap probability value calculated by ordinary bootstrap re-sampling." – whuber Jul 6 '12 at 16:23
My answer was a guess that it refers to the m-out-of-n bootstrap because that is the only bootstrap variant that I knwo that sounds like what you describe. There are other variants called the wild bootstrap and the Bayesian bootstrap. But they don't seem to fit. Also it is puzzling that hypotehsis testing and p-values enter in the discussion since that would not seem to relate to descriptive methods like clustering but would be likely to arise in classification error rate estimation. – Michael Chernick Jul 6 '12 at 16:25
@whuber I read the article and saw the reference to approximately unbiased bootstraps referring to a figure. But I could not find any more details about it. Did you get the rest of the information from the referenced online article? – Michael Chernick Jul 6 '12 at 18:43
@Michael This was about the only credible hit on the entire Internet when searching for "approximately unbiased bootstrap" (after excluding the hits for here and the BioStar site!). Now you know as much as (and probably more than) the rest of us... . – whuber Jul 6 '12 at 18:45
show 1 more comment

Helen: I am the author of books on the bootstrap but I don't know what you mean by the term approximately unbiased bootstrap. As a guess based on your description that you may be talking about the $m$ out of $n$ bootstrap. The $m$ out of $n$ bootstrap takes an original sample of size $n$ and samples $m$ times with replacement from that sample where $m < n$. Each sample of size $m$ is an $m$ out of $n$ bootstrap sample. Most of the time the ordinary bootstrap provides consistent estimates for the parameter but there are situations where it fails to be consistent. In those cases the $m$ out of $n$ bootstrap is often consistent as long as $m$ approaches infinity at a slower rate than $n$. One example is the estimate of a population mean when the distribution of the samples does not have a finite variance. Such results have been proven in papers by Peter Bickel and his coauthors.

Bill Huber has shown that my guess was wrong. It appears that in the paper they are referring to a p-value estimate that is determined by bootstrap and they happen to choose the modifier "approximately unbiased". But it is not a variant of the bootstrap.

-
m-out-of-n bootstrap is also commonly referred to as subsampling, as the title of the book by Politis, Romano and Wolf goes. – StasK Jul 6 '12 at 1:17
That is not quite right. Subsampling is different. It is another technique in the calss called resampling procedures but it does not involve sampling with replacement from the original sample. – Michael Chernick Jul 6 '12 at 1:55

Bootstrap is a technique used in classification, not so much in cluster analysis. It is meant to prevent overfitting on the class labels, but as the class labels are not used in cluster analysis, this is not possible anyway.

In cluster analysis, it can mostly serve as a randomization/diversity source; drawing different samples and clustering them will produce a set of different clusterings, out of which you can then choose one that suits you best.

-
 to clarify your point that the bootstrap is meant to prevent overfitting in classification, what the bootstrap is used for mostly in classification is getting "honest" (nearly unbiased) estimates of the classification error rate. If you have accurate unbiased estimates of the error rates you will not pick a model that overfits. Other methods might if they provide optimistically biased estimates of error rate such as in the case of the resubstitution estimate. – Michael Chernick Jul 6 '12 at 11:50