為什麼jackknife的計算量比bootstrap少？

人們經常聲稱折刀的計算量較小。怎麼回事？

我的理解是折刀涉及以下步驟：

1. 刪除 1 個數據點
2. 估計剩餘點上感興趣的統計量（例如樣本均值）
3. 重複步驟 1) 和 2) 以獲得感興趣統計量的抽樣分佈。

引導程序包括以下步驟：

1. 生成引導樣本（帶替換的樣本）
2. 在 bootstrap 樣本上估計感興趣的統計量（例如樣本均值）
3. 重複步驟 1) 和 2) 以獲得感興趣統計量的抽樣分佈。

在我看來，第 2 步是計算量更大的部分，並且在折刀和引導程序之間完全相同。如果是這樣，那麼折刀如何減少計算密集度？

正如 Cliff AB 在下面指出的那樣，折刀本質上並不比引導程序快。然而，有兩個因素有時會使其在實踐中比自舉更快。

1. 約定在折刀期間，估計步驟總是準確地完成 $ n $ 次：從每個折刀估計中省略一個數據點。如果你有一個數據集 $ n=50 $ 點，因此您將運行估計程序 50 次，依次忽略第 1、2、…n 個點。相比之下，Bootstrap 幾乎運行了“很多次”（~1000 次）；僅引導 $ k=50 $ 重複幾乎是聞所未聞的，人們很少從絕對大量的樣本中計算折刀估計（ $ n=10^9 $ )，部分原因是它會毫無意義地緩慢。
2. 優化由於每次迭代都會重新繪製整個 bootstrap 樣本，因此每個 bootstrap 樣本可能與其他樣本完全不同，因此需要從頭開始計算統計量。然而，每個折刀樣本幾乎與之前的樣本相同，除了兩個數據點：在最後一次迭代中刪除的一個（現在添加回來）和在當前迭代中刪除的一個（以前存在） . 這為一些計算優化打開了大門。

例如，您想估計平均值。對於引導程序，您無法添加所有 $ n $ 每次都值一起； $ bn $ 需要添加 $ b $ 引導迭代。對於折刀估計，您可以改為添加所有 $ n $ 數字一次找到 $ S=\sum x $ . 接下來，計算樣本的平均值，其中 $ i $ th 數據點被刪除為 $ \frac{S-x_i}{n-1} $ . 這只需要 $ 2n $ 整個折刀的加法/減法。其他統計數據也存在類似的技巧。

事實上，對於某些數量的折刀估計，可以導出封閉形式的表達式，讓您完全跳過（重新）採樣！例如，Bandos、Guo 和 Gur 在這里為 auROC 的方差提供了一個封閉形式的解。

引用自：https://stats.stackexchange.com/questions/461996