为什么jackknife的计算量比bootstrap少?

机器算法验证 引导程序 重采样 折刀
2022-01-20 16:22:34

人们经常声称折刀的计算量较小怎么回事?

我的理解是折刀涉及以下步骤:

  1. 删除 1 个数据点
  2. 估计剩余点上感兴趣的统计量(例如样本均值)
  3. 重复步骤 1) 和 2) 以获得感兴趣统计量的抽样分布。

引导程序包括以下步骤:

  1. 生成引导样本(带替换的样本)
  2. 在 bootstrap 样本上估计感兴趣的统计量(例如样本均值)
  3. 重复步骤 1) 和 2) 以获得感兴趣统计量的抽样分布。

在我看来,第 2 步是计算量更大的部分,并且在折刀和引导程序之间完全相同。如果是这样,那么折刀如何减少计算密集度?

1个回答

正如 Cliff AB 在下面指出的那样,折刀本质上并不比引导程序快。然而,有两个因素有时会使其在实践中比自举更快。

  1. 约定在折刀期间,估计步骤总是准确地完成n次:从每个折刀估计中省略一个数据点。如果你有一个数据集n=50点,因此您将运行估计程序 50 次,依次忽略第 1、2、...n 个点。相比之下,Bootstrap 几乎运行了“很多次”(~1000 次);仅引导k=50重复几乎是闻所未闻的,人们很少从绝对大量的样本中计算折刀估计(n=109),部分原因是它会毫无意义地缓慢。

  2. 优化由于每次迭代都会重新绘制整个 bootstrap 样本,因此每个 bootstrap 样本可能与其他样本完全不同,因此需要从头开始计算统计量。然而,每个折刀样本几乎与之前的样本相同,除了两个数据点:在上一次迭代期间删除的一个(现在添加回来)和在当前迭代中删除的一个(以前存在) . 这为一些计算优化打开了大门。

例如,您想估计平均值。对于引导程序,您无法添加所有n每次都值一起;bn需要添加b引导迭代。对于折刀估计,您可以改为添加所有n数字*一次*找到S=x. 接下来,计算样本的平均值,其中ith 数据点被删除为Sxin1. 这只需要2n整个折刀的加法/减法。其他统计数据也存在类似的技巧。

事实上,对于某些数量的折刀估计,可以导出封闭形式的表达式,让您完全跳过(重新)采样!例如,Bandos、Guo 和 Gur 在这里为 auROC 的方差提供了一个封闭形式的解。