TL，DR：看起來，與經常重複的建議相反，留一法交叉驗證（LOO-CV）——也就是說，-折疊簡歷（折疊次數）等於（訓練觀察的數量）——產生泛化誤差的估計值，它是任何變量的最小變量，而不是最大的變量，假設模型/算法、數據集或兩者都有一定的穩定性**條件（我不確定哪個是正確的，因為我不太了解這種穩定性條件）。

• 有人可以清楚地解釋這種穩定條件到底是什麼嗎？
• 線性回歸確實是這樣一種“穩定”算法，這是否意味著在這種情況下，就泛化誤差估計的偏差和方差而言，LOO-CV 嚴格來說是 CV 的最佳選擇？

---

傳統觀點是，選擇在-fold CV 遵循偏差-方差折衷，這樣較低的值（接近 2）導致泛化誤差的估計具有更多的悲觀偏差，但方差更低，而更高的值（接近) 導致估計偏差較小，但方差較大。對這種方差現象的傳統解釋隨著在《統計學習的要素》（第 7.10.1 節）中可能最突出地給出：

在 K=N 的情況下，交叉驗證估計器對於真實（預期）預測誤差近似無偏，但可能具有高方差，因為 N 個“訓練集”彼此非常相似。

這意味著驗證錯誤的相關性更高，因此它們的總和更具可變性。在這個網站（例如，這裡、這裡、這裡、這裡、這裡、這里和這裡）以及各種博客等上的許多答案中都重複了這種推理。但實際上從未給出詳細的分析，而是只是對分析可能是什麼樣子的直覺或簡要概述。

然而，人們可以找到相互矛盾的陳述，通常引用我並不真正理解的某種“穩定性”條件。例如，這個矛盾的答案引用了 2015 年一篇論文中的幾段話，其中除其他外，“對於低不穩定性的模型/建模程序，LOO 通常具有最小的可變性”（強調添加）。本文（第 5.2 節）似乎同意 LOO 代表變量最小的選擇只要模型/算法是“穩定的”。甚至在這個問題上採取另一種立場，還有這篇論文（推論 2），它說“折疊交叉驗證 […] 不依賴於，”再次引用某種“穩定”條件。

關於為什麼 LOO 可能是最多變的解釋-fold CV 足夠直觀，但有一種反直覺。均方誤差 (MSE) 的最終 CV 估計值是每個折疊中 MSE 估計值的平均值。這樣增加到，CV 估計值是越來越多的隨機變量的平均值。我們知道，均值的方差隨著被平均的變量數量而減小。所以為了讓 LOO 成為最大的變數-fold CV，必須正確的是**，由於 MSE 估計之間的相關性增加而導致的方差增加超過了由於平均折疊次數更多而導致的方差減少**。這一點也不明顯。

考慮到這一切，我變得徹底困惑，我決定為線性回歸案例運行一個小模擬。我模擬了 10,000 個數據集= 50 和 3 個不相關的預測變量，每次使用估計泛化誤差-折疊簡歷=2、5、10 或 50=. R代碼在這裡。以下是所有 10,000 個數據集（以 MSE 為單位）的 CV 估計值的結果均值和方差：

        k = 2 k = 5 k = 10 k = n = 50
mean     1.187 1.108  1.094      1.087
variance 0.094 0.058  0.053      0.051

這些結果顯示了較高值的預期模式導致不那麼悲觀的偏差，但似乎也證實了在 LOO 情況下，CV 估計的方差是最低的，而不是最高的。

因此，線性回歸似乎是上述論文中提到的“穩定”案例之一，其中增加與 CV 估計值的方差減少而不是增加有關。但我仍然不明白的是：

• 這種“穩定”條件究竟是什麼？它是否在某種程度上適用於模型/算法、數據集或兩者兼而有之？
• 有沒有一種直觀的方式來考慮這種穩定性？
• 還有哪些其他穩定和不穩定的模型/算法或數據集的例子？
• 假設大多數模型/算法或數據集是“穩定的”是否相對安全，因此通常應該選擇計算上可行的高嗎？

這個答案跟進了我在留一法與 K 折交叉驗證中的偏差和方差中的答案，討論了為什麼 LOOCV並不總是導致更高的方差。遵循類似的方法，我將嘗試強調 LOOCV在存在異常值和“不穩定模型” 的情況下確實會導致更高方差的情況。

算法穩定性（學習理論）

算法穩定性是最近的一個話題，在過去的 20 年中已經證明了幾個經典的、有影響力的結果。以下是一些經常被引用的論文

• 模型選擇中的不穩定性和穩定性啟發式（1996）：Leo Breiman
• LOOCV (1997) 的算法穩定性和健全性檢查界限：Kearns, Ron
• 穩定性和泛化（2002）：Bousquet，Elisseef
• 交叉驗證和均方穩定性(2011) Kale, Kumar, Vassilvitskii
• 幾乎無處不在的算法穩定性和泛化錯誤（2012）：Kutin，Niyogi
• 關於該主題的一些註釋：亞利桑那大學

獲得理解的最佳頁面當然是wikipedia 頁面，它提供了由可能非常博學的用戶編寫的出色摘要。

穩定性的直觀定義

直觀地說，一種穩定的算法是一種在訓練數據稍作修改時預測不會發生太大變化的算法。

形式上，有六個版本的穩定性，通過技術條件和層次結構聯繫在一起，例如從這裡查看此圖：

然而，目標很簡單，當算法滿足穩定性標準時，我們希望對特定學習算法的泛化誤差有嚴格的限制。正如人們所預料的那樣，穩定性標準越嚴格，相應的界限就越嚴格。

符號

以下符號來自維基百科文章，該文章本身複製了 Bousquet 和 Elisseef 論文：

• 訓練集從未知分佈 D 中抽取 iid
• 損失函數一個假設的關於一個例子定義為
• 我們通過刪除-th 元素：
• 或者通過更換-th 元素：

正式定義

也許一個有趣的學習算法可能會遵守的最強穩定性概念是一致穩定性：

一致穩定性 算法具有一致穩定性關於損失函數如果以下成立：

被認為是一個函數， 術語可以寫成. 我們說算法是穩定的減少為. 稍弱的穩定性形式是：

假設穩定性

如果去掉一個點，學習算法結果的差異是通過損失的平均絕對差來衡量的（規範）。直觀地說：樣本的微小變化只會導致算法移動到附近的假設。

這些穩定性形式的優點是它們為穩定算法的偏差和方差提供了界限。特別是，Bousquet 在 2002 年證明了 Uniform 和 Hypothesis 穩定性的這些界限。從那時起，已經做了很多工作來嘗試放寬穩定性條件並概括界限，例如在 2011 年，Kale、Kumar、Vassilvitskii 認為均方穩定性 提供更好的方差定量方差減少界限。

一些穩定算法的例子

以下算法已被證明是穩定的，並且已經證明了泛化界限：

• 正則化最小二乘回歸（具有適當的先驗）
• 具有 0-1 損失函數的 KNN 分類器
• 具有有界核和大正則化常數的 SVM
• 軟邊距支持向量機
• 分類的最小相對熵算法
• bagging 正則化器的一個版本

實驗模擬

重複上一個線程的實驗（見這裡），我們現在在數據集中引入一定比例的異常值。特別是：

• 97%的數據有均勻噪聲
• 3% 的數據均勻噪聲

作為階多項式模型沒有正則化，它會受到小數據集的一些異常值的嚴重影響。對於較大的數據集，或者當存在更多異常值時，它們的影響較小，因為它們往往會被抵消。有關 60 和 200 數據點的兩種模型，請參見下文。

如前所述執行模擬並繪製得到的平均 MSE 和 MSE 方差的結果與Bengio & Grandvalet 2004論文的實驗 2 非常相似。

左側：沒有異常值。右手邊：3% 的異常值。

（有關最後一個圖的解釋，請參見鏈接的論文）

解釋

在另一個線程上引用Yves Grandvalet 的回答：

直觀上，[在算法不穩定的情況下]，留一法CV可能對存在的不穩定性視而不見，但可能不會通過改變訓練數據中的單個點來觸發，這使得它的實現具有很大的可變性訓練集。

在實踐中，很難模擬由於 LOOCV 引起的方差增加。它需要特定的不穩定性組合，一些異常值但不是太多，以及大量的迭代。也許這是意料之中的，因為線性回歸已被證明是相當穩定的。一個有趣的實驗是對更高維數據和更不穩定的算法（例如決策樹）重複此操作

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