0 寫在前面

參考資料：Statistical Learning Theory- Models， Concepts， and Results 最近需要做一個統計學習理論的總結，筆者主要參考上面資料做了前面5章的總結，特此分享 ：）。

1 引言

統計學習理論（SLT）為當代很多機器學習演算法提供理論基礎，也是AI最美的發展分支之一。它起源於1960年代的俄羅斯，並且在1990年代，當SVM成為從計算機視覺到計算生物學等主要領域中模式識別的的一個標準工具之後，SLT開始流行起來。

本篇主要展示一個非技術性綜述，讀者不需要深入的數學統計、計算機背景。現已有很多傑出的文獻總結SLT，Vapnik的專著（1995，1998）中是SLT的基石之一，。。。

2 SLT的標準框架

2。1 背景

在我們文章中，學習指的是從觀察案例中推匯出的一般性規律。比如孩子們能夠透過觀察一些物體例項來知道車是什麼，而不需要知道如何製造汽車的規則，僅僅是觀察。

機器學習不是學習生命體學習的過程，而是從抽象上學習這個學習的過程。問題在於機器或者說計算機如何能夠透過一些特定的學習演算法來“學習”執行一些特定的任務。

常見的問題有分類、迴歸和聚類，機器學習針對這些問題有不同的焦點，其中之一便是歸納泛化能力。

目前研究最透徹的是分類。這裡我們需要處理兩種空間：輸入空間

\mathcal X

和輸出空間

\mathcal Y

。如果需要將給定物件分成有限類，那麼

\mathcal X

就是所有可能物件（例項）的空間，

\mathcal Y

就是包含所有分類的空間，學習演算法使得給定一些訓練例項如

\left(X_{1}, Y_{1}\right), \ldots,\left(X_{n}, Y_{n}\right)

，然後貼上不同的分類標籤。我們的目標就是找到這樣一個對映（mapping）

f: X \rightarrow Y

，使得分類的錯誤率越來越小，這樣的對映就是分類器。

SLT是機器學習的理論分支，以下是SLT中的幾個基本問題：

什麼樣的學習任務能夠由計算機完成？

機器學習需要哪些假設條件？

學習演算法成功的關鍵屬性是什麼？

對於特定的學習演算法我們能保證有怎樣的表現？

我們首先關注監督學習，尤其是典型的二分類問題，其他學習問題的理論仍然處於幼年時期。

2。2 假設條件

首先我們需要假設 輸入輸出空間

\mathcal X \times \mathcal Y

之間存在聯合分佈機率（joint probability distribution）

P

，訓練樣本

\left(X_{i}, Y_{i}\right)

獨立於該分佈

P

進行取樣，這種型別的取樣通常稱為iid取樣（獨立同分布）。以下兩點假設比較重要：

沒有關於P的假設。在標準SLT中，我們沒有對機率分佈P進行任何假設：它可以是上的任何分佈。從這個意義上說，統計學習理論的不可知性（agostic setting）不同於標準統計，從標準統計中，通常會假設機率分佈屬於某個分佈族，目標是估計該分佈的引數。

沒有因為標籤噪聲或類別重疊導致的不確定標籤。請注意，P不僅是例項X的機率分佈，而且是標籤Y的機率分佈。因此，資料中的標籤Yi不一定只是物件Xi的確定性函式，它們本身可以是隨機的。出現這種情況的主要原因有兩個。第一個原因是資料生成過程可能會受到標籤噪聲的影響。也就是說，在學習過程中作為培訓標籤獲得的標籤Yi可能是錯誤的。這是一個重要而現實的假設。例如，為了生成用於檢測電子郵件垃圾郵件的訓練資料，需要人工將電子郵件手工標記為“垃圾郵件”和“非垃圾郵件”類別。所有人類都會不時犯錯。因此，即使某些電子郵件不是垃圾郵件，也有可能偶然將其標記為“垃圾郵件”，反之亦然。當然，希望這樣的錯誤標籤僅以相對較小的機率出現。導致非確定性標籤的第二個主要原因是重疊類的情況。例如，考慮根據身高預測一個人的性別的任務。顯然，身高1。80米的人原則上可以是男性或女性，因此我們不能為輸入X = 1。80分配唯一的標籤Y。

其他的一些假設：

獨立取樣

分佈

P

是固定的

分佈

P

在學習過程中未知

2。2。1 損失函式和風險函式

損失函式，又叫代價函式，是將隨機事件或其有關隨機變數的取值對映為非負實數以表示該隨機事件的“風險”或“損失”的函式。簡單的0-1分類損失函式如下：

\ell(X, Y, f(X))=\left\{\begin{array}{ll}{1} & {\text { if } f(X) \neq Y} \\ {0} & {\text { otherwise }}\end{array}\right.

還有更常見的方差損失函式：

\ell(X, Y, f(X))=(Y-f(X))^{2}

。

基於損失函式，風險函式被定義為所有資料點的平均損失：

R(f):=E(\ell(X, Y, f(X)))

如果風險越小，那麼分類器就越好。

2。2。2 貝葉斯風險

我們考慮貝葉斯分類器（它是所有可測函式中最優的），對於給定分佈

P

，如下：

f_{\text {Bayes}}(x):=\left\{\begin{array}{ll}{1} & {\text { if } P(Y=1 | X=x) \geq 0.5} \\ {-1} & {\text { otherwise. }}\end{array}\right.

但是基本不可能直接計算出貝葉斯分類，因為對於學習者來說機率分佈P不可知，並且同樣因此也不能計算風險函式

R(f)

，這時候就需要用到SLT了。

2。3 泛化與相合性（一致性）

2。3。1 泛化（genelization）

儘管不能計算真實的風險函式，但是可以計算訓練集中的錯誤個數，稱為經驗風險或者訓練誤差：

\mathrm{R}_{\mathrm{emp}}(f):=\frac{1}{n} \sum_{i=1}^{n} \ell\left(X_{i}, Y_{i}, f\left(X_{i}\right)\right)

通常對於特定的訓練樣本，觀察風險相對較小。然而，分類器

f_{n}

在訓練集中產生一些錯誤後會不會對剩下的樣本空間產生誤差還不清楚。一個好的分類器中經驗風險都會接近於真實風險，即如果

\left|R\left(f_{n}\right)-\mathrm{R}_{\mathrm{emp}}\left(f_{n}\right)\right|

很小，我們稱一個分類器

f_{n}

能夠泛化得很好。但是通常經驗誤差會小於真實誤差，而且有些情況甚至差距很大。

2。3。2 bias/variance tradeoff（誤差/方差權衡）

2。3。2 相合性（consistency）

對於給定的函式或者分類器空間

\mathcal F

，如果一般分類器

f_{n} \in \mathcal{F}

，可以認為這些分類器是最好的分類器，記作

f_{\mathcal{F}}

，換句話說它們的風險最小，即：

f_{\mathcal{F}}=\underset{f \in \mathcal{F}}{\operatorname{argmin}} R(f)

第三種分類器就是貝葉斯分類器

f_{B a y e s}

，即認為最好的分類器，根據這三種分類器可以定義三種相合性：

類

\mathcal{F}

相合

即對於所有

\varepsilon>0

貝葉斯相合

即對於所有

\varepsilon>0

普遍相合

對於所有分佈

P

都滿足貝葉斯相合性

以上的相合性稱為弱收斂，即以機率收斂，而強收斂即幾乎必然收斂。

2。4 trade-off（權衡）

2。4。1 bias/variance tradeoff（誤差/方差權衡）

比如對於迴歸問題，我們通常會討論時用線性函式

y=\theta_{0}+\theta_{1} x

去擬合，還是用更復雜的多項式函式

y=\theta_{0}+\theta_{1} x+\cdots \theta_{5} x^{5}

擬合，如下圖：

統計學習理論淺要綜述

儘管右圖的複雜模型能夠很好的擬合訓練資料，但是應用到測試資料上可能會差，即泛化不一定好，發生過擬合，而簡單如左圖的缺點就是系統偏差bias較大，可能會欠擬合。泛化的另外一個問題就是訓練資料的隨機性，即方差variance，所以就更沒有必要在訓練集中追求完美。綜上，在偏差方差之間會有一個權衡的過程。

2。4。2 estimation-approximation trade-off（估計/逼近權衡）

對於貝葉斯相合性，可以拆解為以下兩個部分：

R\left(f_{n}\right)-R\left(f_{B a y e s}\right)=\underbrace{\left(R\left(f_{n}\right)-R\left(f_{\mathcal{F}}\right)\right)}_{\text {estimation error }}+\underbrace{\left(R\left(f_{\mathcal{F}}\right)-R\left(f_{\text {Bayes}}\right)\right)}_{\text {approximation error }}

如下圖，一個是估計誤差，一個是逼近誤差。估計誤差設計隨機取樣的不確定性，即對於給定樣本我們需要找到最佳函式空間

\mathcal{F}

這個過程中產生的誤差。逼近誤差跟隨機樣本無關，它是在小空間

\mathcal{F}

的基礎上再找到最佳的函式產生的，用於衡量這些函式近似

\mathcal{F}_{all}

效果的量。

統計學習理論淺要綜述

在統計學中，估計誤差也叫方差（variance），逼近誤差也叫偏差（bias）。下圖描述了兩個誤差之間隨著函式複雜度的權衡，可以看出最佳的風險值在中等複雜度處。在SLT中，重點關注估計錯誤，逼近錯誤的分析較為困難。

統計學習理論淺要綜述

3 kNN分類器的泛化與相合性

第一個被嚴格證明具有普遍相合性的分類器是在1977年有Stone完成，這個分類器就是kNN。kNN是最簡單、應用最廣泛的分類器之一。Stone給出瞭如下定理：

貝葉斯普遍相合性

f_{n}

為對於

n

個樣本點的k鄰近分類器，如果

n \rightarrow \infty

，

k \rightarrow \infty

並且

k / n \rightarrow 0

，那麼對於所有機率分佈

P

，就有

R\left(f_{n}\right) \rightarrow R\left(f_{\text {Bayes }}\right)

這個定理告訴我們如果選擇增長較為緩慢的引數

k

，即滿足

k / n \rightarrow 0

比如

k \approx \log (n)

，那麼kNN就具有普遍相合性，注意這是對大樣本極限情況而言，對於有限或者小樣本，kNN並不算好。

4 經驗風險最小化

前面提到經驗風險表示式如下：

R(f)=E(\ell(X, Y, f(X))

但是由於分佈

P

未知，所以我們不能計算

R(f)

。但是我們可以透過已知訓練樣本推出一個分佈

P

和函式

f

，使其風險達到最佳，這種思路應用了歸納原理。通常用經驗風險

R_{\mathrm{emp}}(f)

代替

R(f)

：

R_{\mathrm{emp}}(f)=\frac{1}{n} \sum_{i=1}^{n} \ell\left(X_{i}, Y_{i}, f\left(X_{i}\right)\right.

這樣我們需要找到一個函式或者說分類器使得經驗風險最小：

f_{n}:=\underset{f \in \mathcal{F}}{\operatorname{argmin}} \mathrm{R}_{\mathrm{emp}}(f)

4。1 大數定律

大數定律是統計學中重要理論之一。它的內容是當樣本大小趨近於無窮大的時候，滿足獨立同分布的隨機變數

\xi_{i}

的均值收斂於收斂於基礎分佈（underlying distribution）的均值（或者說期望）：

\frac{1}{n} \sum^{n} \xi_{i} \rightarrow E(\xi) \quad \text { for } n \rightarrow \infty

那麼它的經驗風險可以收斂於其真實風險

R(f)

：

\mathrm{R}_{\mathrm{emp}}(f)=\frac{1}{n} \sum_{i=1}^{n} \ell\left(X_{i}, Y_{i}, f\left(X_{i}\right)\right) \rightarrow E(\ell(X, Y, f(X))) \quad \text { for } n \rightarrow \infty

即對於給定的有限樣本，我們可以用經驗風險近似真實風險，霍夫丁不等式（切爾諾夫界）表徵了經驗風險逼近真實風險的效果。即如果隨機變數

\xi_{i}

只在區間

[0,1]

取值，那麼有：

P\left(\left|\frac{1}{n} \sum_{i=1}^{n} \xi_{i}-E(\xi)\right| \geq \epsilon\right) \leq 2 \exp \left(-2 n \epsilon^{2}\right)

從該式可以看出當

n

越大，偏差的機率就會越低，應用於經驗和真實風險有：

P\left(\left|R_{\mathrm{emp}}(f)-R(f)\right| \geq \epsilon\right) \leq 2 \exp \left(-2 n \epsilon^{2}\right)

上式也就切諾夫邊界，它的一個關鍵特性就是他本質上是基於機率性的。但是注意，切諾夫邊界只對固定函式

f

有效，即不依賴於訓練函式。然而，分類器

f_{n}

確實依賴於訓練資料，因為我們就是用訓練資料選擇它的。儘管這是一個細微的數學差異，但也很可能是經驗風險最小化完全出錯的地方。

4。2 為什麼經驗風險最小化可能會不相合？

設資料空間

\mathcal X=[0,1]

，選擇

\mathcal X

上的均勻分佈，對於一個輸入點

X

，定義標籤

Y

如下：

Y=\left\{\begin{array}{ll}{-1} & {\text { if } X<0.5} \\ {1} & {\text { if } X \geq 0.5}\end{array}\right.

假設給定訓練點

\left(X_{i}, Y_{i}\right)_{i=1, \dots, n}

，考慮如下分類器：

f_{n}(X)=\left\{\begin{array}{ll}{Y_{i}} & {\text { if } X=X_{i} \text { for some } i=1, \ldots, n} \\ {1} & {\text { otherwise. }}\end{array}\right.

該分類器

f_{n}

能夠完美分類所有訓練點，即經驗風險

\mathrm{R}_{\mathrm{emp}}\left(f_{n}\right)=0

。但是該分類器並沒有學習任何東西，僅僅是記住了訓練標籤並且在其他情況下僅僅預測為1，即該分類器將不相合。比如，給定一個測試點

(X, Y)

，通常該測試點不同於任何訓練集中的點，在這種情況下它僅輸出標籤1。如果

X>0.5

，那麼這就是一個錯誤標籤。可以知道它的真實風險為

R\left(f_{n}\right)=1 / 2

。事實上，這是一個典型的過擬合，即分類器很好地適應了訓練資料但是不能從新的測試資料學習到任何東西。所以該分類器不相合。注意到標籤是關於輸入點的一個確定函式，即可以得到貝葉斯風險為0，於是有

1 / 2=R\left(f_{n}\right) \not \rightarrow R\left(f_{B a y e s}\right)=0

。

4。3 一致收斂

經驗風險最小化所需的條件包括限定可允許的函式集。VC （Vapnik-Chervonenkis）理論認為經驗風險最小化的相合性（一致性）取決於所有函式

f \in \mathcal{F}

的最壞情況行為。上面可以看出這個最壞的情況不是標準大數定律，而是大數定律其中的一個版本，即統一大數定律。下圖給出了統一大數定律和一致性問題的簡化描述。

統計學習理論淺要綜述

y

軸表示風險。 對於每個固定函式

f

，大數定律告訴我們，隨著樣本量達到無窮大，經驗風險

R_{\mathrm{emp}}(f)

向真實風險

R(f)

收斂（如箭頭所示）。 但是，這並不意味著在無限樣本量的限制內，經驗風險的最小值fn會導致該風險的值與函式類別中最佳函式

f_{F}

的風險一樣好（在圖中用

f_{F}

表示）。 為了使後者正確，我們要求

R_{\mathrm{emp}}(f)

向

R(f)

的收斂在F中的所有函式上都是統一的（Scholkopf和Smola，2002）。

因此一種確保

\mathcal F

中所有函式的最小值收斂的一種方法是在

\mathcal F

上均勻收斂：我們要求所有函式

f \in \mathcal{F}

，真實風險與經驗風險之差必須同時變小。也就是說，我們要求存在足夠大的

n

，並且樣本大小至少大於

n

，這樣對於所有

f \in \mathcal{F}

，都會有

\left|R(f)-\mathrm{R}_{\mathrm{emp}}(f)\right|

小於一個給定值

\varepsilon

，我們使用一個上確界（supremum）來表達：

\sup _{f \in \mathcal{F}}\left|R(f)-\operatorname{R}_{\mathrm{emp}}(f)\right| \leq \varepsilon

因此，有：

\left|R(f)-\mathrm{R}_{\mathrm{emp}}(f)\right| \leq \sup _{f \in \mathcal{F}}\left|R(f)-\mathrm{R}_{\mathrm{emp}}(f)\right|

特別地，該關係對於基於有限訓練樣本的函式

f_{n}

也成立，即推出：

P\left(\left|R\left(f_{n}\right)-\mathrm{R}_{\mathrm{emp}}\left(f_{n}\right)\right| \geq \varepsilon\right) \leq P\left(\sup _{f \in \mathcal{F}}\left|R(f)-\mathrm{R}_{\mathrm{emp}}(f)\right| \geq \varepsilon\right)

式子右邊跟統一大數定律（uniform law of large numbers）有關，即當所有

\varepsilon >0

具有一致性，

P\left(\sup _{f \in \mathcal{F}}\left|R(f)-\mathrm{R}_{\mathrm{emp}}(f)\right| \geq \varepsilon\right) \rightarrow 0 \text { as } n \rightarrow \infty

證明過程如下，

\begin{array}{l}{\left|R\left(f_{n}\right)-R\left(f_{\mathcal{F}}\right)\right|} \\ {\left.\quad \text { (by definition of } f_{\mathcal{F}} \text { we know that } R\left(f_{n}\right)-R\left(f_{\mathcal{F}}\right) \geq 0\right)} \\ {=R\left(f_{n}\right)-R\left(f_{\mathcal{F}}\right)} \\ {=R\left(f_{n}\right)-\operatorname{R}_{\mathrm{emp}}\left(f_{n}\right)+\operatorname{R}_{\mathrm{emp}}\left(f_{n}\right)-\operatorname{R}_{\mathrm{emp}}\left(f_{\mathcal{F}}\right)+\mathrm{R}_{\mathrm{emp}}\left(f_{\mathcal{F}}\right)-R\left(f_{\mathcal{F}}\right)} \\ {\quad\left(\text {note that } \mathrm{R}_{\mathrm{emp}}\left(f_{n}\right)-\mathrm{R}_{\mathrm{emp}}\left(f_{\mathcal{F}}\right) \leq 0 \text { by def. of } f_{n}\right)} \\ {\leq R\left(f_{n}\right)-\mathrm{R}_{\mathrm{emp}}\left(f_{n}\right)+\mathrm{R}_{\mathrm{emp}}\left(f_{\mathcal{F}}\right)-R\left(f_{\mathcal{F}}\right)} \\ {\leq 2 \sup _{f \in \mathcal{F}}\left|R(f)-\mathrm{R}_{\mathrm{emp}}(f)\right|}\end{array}

即：

P\left(\left|R\left(f_{n}\right)-R\left(f_{\mathcal{F}}\right)\right| \geq \varepsilon\right) \leq P\left(\sup _{f \in \mathcal{F}}\left|R(f)-\mathrm{R}_{\mathrm{emp}}(f)\right| \geq \varepsilon / 2\right)

在大數定律下，右邊趨近於0，這將導致經驗風險（ERM）相對於函式類（underlying function class）

\mathcal{F}

具有相合性，也就是說，

\mathcal{F}

的一致收斂導致是其經驗風險最小化的充要條件。那麼是不是必要條件呢？

VC（（Vapnik & Chervonenkis））定理3給出了證明，即一致收斂條件：

P\left(\sup <em>{f \in \mathcal{F}}\left|R(f)-R</em>{\mathrm{emp}}(f)\right|>\epsilon\right) \rightarrow 0 \text { as } n \rightarrow \infty

對於所有

\varepsilon >0

5 容量概念與泛化界（Capacity concepts and generalization bounds）

上面討論了一致收斂和經驗風險最小化的關係，下面將看到對於如下機率更為廣泛的情況：

P\left(\sup <em>{f \in \mathcal{F}}\left|R(f)-R</em>{\mathrm{emp}}(f)\right|>\epsilon\right)

在此過程中需要用到兩個技巧：並界和影子樣本對稱化。

5。1 並界（union bound）

並界是一個將單個函式的標準大數定律轉換為有限函式集的大數定律的簡便工具。設集合

\mathcal F

包含有限函式，即

\mathcal{F}=\left\{f_{1}, f_{2}, \ldots, f_{m}\right\}

。那麼對於每個函式

f_{i} \in \mathcal{F}

都滿足切爾諾夫界形式下的大數定律，即：

P\left(\left|R\left(f_{i}\right)-\mathrm{R}_{\mathrm{emp}}\left(f_{i}\right)\right| \geq \varepsilon\right) \leq 2 \exp \left(-2 n \varepsilon^{2}\right)

現在將個體函式

f_{i}

轉換到統一大數定律（uniform law of large numbers）下，即：

\begin{array}{l}{P\left(\sup _{f \in \mathcal{F}}\left|R(f)-R_{\mathrm{emp}}(f)\right| \geq \varepsilon\right)} \\ {=P\left(\left|R\left(f_{1}\right)-R_{\mathrm{emp}}\left(f_{1}\right)\right| \geq \varepsilon \text { or }\left|R\left(f_{2}\right)-R_{\mathrm{emp}}\left(f_{2}\right)\right| \geq \varepsilon \text { or } \ldots \text { or }\left|R\left(f_{m}\right)-R_{\mathrm{emp}}\left(f_{m}\right)\right| \geq \varepsilon\right)} \\ {\leq \sum_{i=1}^{m} P\left(\left|R\left(f_{i}\right)-R_{\mathrm{emp}}\left(f_{i}\right)\right| \geq \varepsilon\right)} \\ {\leq 2 m \exp \left(-2 n \varepsilon^{2}\right)}\end{array}

第一個等式利用了上確界的定義，注意是“or”， 第二個則用到機率論中的一個標準工具，也就是本部分所講的並界。最後仍然可以簡化為類似於如下的個體函式切爾諾夫界：

P\left(\left|R_{\mathrm{emp}}(f)-R(f)\right| \geq \epsilon\right) \leq 2 \exp \left(-2 n \epsilon^{2}\right)

可以看到，切爾諾夫界對於單個函式和函式集的差別在於有個因子

m

，即函式的個數。但是當

n \rightarrow \infty

時，

2 m \exp \left(-2 n \varepsilon^{2}\right)

仍然趨近於0，也就是仍然滿足經驗風險最小化的相合性。

5。2 對稱化

對稱化是使用函式類容量度量的重要技術步驟。它的重要目的就是用一個基於給定樣本計算的量替換上確界

\sup _{f \in \mathcal{F}}\left|R(f)-R_{\mathrm{emp}}(f)\right|

。設給定樣本

\left(X_{i}, Y_{i}\right)_{i=1, \ldots, n}

，現在引入一個新樣本，稱之為影子樣本（ghost sample）

\left(X_{i}^{\prime}, Y_{i}^{\prime}\right)_{i=1, \ldots, r}

。影子樣本同樣也是獨立同分布的，並且能夠計算出其經驗風險為

\mathrm{R}_{\mathrm{emp}}^{\prime}(f)

。由此給出VC定理4，如下：

即對於所有

m \epsilon^{2} \geq 2

，都有：

P\left(\sup <em>{f \in \mathcal{F}}\left|R(f)-R</em>{\mathrm{emp}}(f)\right|>\epsilon\right) \leq 2 P\left(\sup <em>{f \in \mathcal{F}}\left|R</em>{\mathrm{emp}}(f)-R_{\mathrm{emp}}^{\prime}(f)\right|>\epsilon / 2\right)

第一個P是大小為n的獨立同分布（iid），第二個P則是兩個大小為n的iid（原始和影子樣本），也就是大小為2n的iid。

從該定理不難看出，如果兩個獨立的n樣本的經驗風險很接近，那麼他們應該也接近於真實風險，這個定理又叫對稱化定理。這條定理的主要目的就是用能夠從有限樣本計算得出的

\mathrm{R}_{\mathrm{emp}}^{\prime}(f)

來替換不能計算的

R(f)

。

現在來解釋對稱化定理能夠用在什麼地方，前面提到我們能夠確定關於有限函式類的一致收斂邊界：

P\left(\sup <em>{f \in \mathcal{F}}\left|R(f)-R</em>{\mathrm{emp}}(f)\right|>\epsilon\right)

但其實即使

\mathcal{F}

包含無限個函式，但是它分類包含

n

個樣本點的訓練集的方式卻是有限的。例如，對於給定的

n

個訓練點

X_{1}, \ldots, X_{n}

，和標籤值

{-1,+1}

，一個函式最多表現

2^{n}

個不同的方式，即它能給每個

Y_{i}

選定-1或者+1值。考慮如下式子：

\sup _{f \in \mathcal{F}}\left|R_{\mathrm{emp}}(f)-R_{\mathrm{emp}}^{\prime}(f)\right|

由於標籤值有限，那麼肯定存在兩個函式

f, g \in \mathcal{F}

在給定樣本上具有相同的輸出值和經驗風險，即

\mathrm{R}_{\mathrm{emp}}(f)=\mathrm{R}_{\mathrm{emp}}(g)

，同理對於影子樣本和

\mathrm{R}_{\mathrm{emp}}^{\prime}(f)

也相同，從而他們的

\left|R_{\mathrm{emp}}(f)-R_{\mathrm{emp}}^{\prime}(f)\right|

也將會相同。

因此我們只需要考慮有效的

2^{2 n}

個函式就行，換句話說可以將無限函式類

\mathcal{F}

替換為包含至多

2^{2 n}

個函式的優先函式類（finite function class）。

5。3 粉碎係數（shattering coefficient）

上節講到一個函式類至多有

2^{2 n}

個有效函式，但實際上一般都小於

2^{2 n}

。比如對於給定大小為

n

的樣本，令

Z_{n}:=\left(\left(X_{1}, Y_{1}\right), \ldots,\left(X_{n}, Y_{n}\right)\right)

，我們用

\left|\mathcal{F}_{Z_{n}}\right|

分別表示有限化後的函式類

\mathcal F

（即包含

2_{n}

個函式）中能夠正確區分每個樣本點的函式個數，其中最大值

\mathcal{N}(\mathcal{F}, n)

我們稱為粉碎係數：

\mathcal{N}(\mathcal{F}, n)=\max \left\{\left|\mathcal{F}_{Z_{n}}\right| | X_{1}, \ldots, X_{n} \in \mathcal{X}\right\}

當

\mathcal{N}(\mathcal{F}, n)=2^{n}

時，稱之為完全粉碎，它就是一個函式的容量，用來表示函式類的複雜度和多樣性，這裡再提醒一下，所說的函式在機器學習中指的就是分類器。

5。4 一致收斂邊界

在並界這一節中已經推出了包含多個函式的函式類的收斂邊界，但是這還不夠精確，尤其是對於包含較多函式的函式類，根據對稱化得出的結論（不管函式類包含多少個函式，它都可以看作至多包含

2^{n}

個函式的有限函式類），現在可以用粉碎係數來進一步精確的推出收斂邊界：

\begin{array}{l}{P\left(\sup <em>{f \in \mathcal{F}}\left|R(f)-R</em>{\text {emp }}(f)\right|>\epsilon\right)} \ {\text { (due to symmetrization) }} \ {\leq 2 P\left(\sup <em>{f \in \mathcal{F}}\left|R</em>{\text {emp }}(f)-R_{\text {emp }}^{\prime}(f)\right|>\epsilon / 2\right)} \ {\leq 2 P\left(\sup <em>{f \in \mathcal{F}}\left|R</em>{\text {emp }}(f)-R_{\text {emp }}^{\prime}(f)\right|>\epsilon / 2\right)} \ {\text { (only functions in } \mathcal{F}<em>{Z</em>{2 n}} \text { are important) }} \ {\left.=2 P\left(\sup <em>{f \in \mathcal{F}</em>{Z_{2 n}}} | R_{\text {emp }}(f)-R_{\text {emp }}^{\prime}(f)\right) |>\epsilon / 2\right)} \ {\quad\left(\mathcal{F}<em>{Z</em>{2 n}} \text { contains at most } \mathcal{N}(\mathcal{F}, 2 n) \text { functions, independently of } Z_{2 n}\right\rangle} \ {\text { (use union bound argument and Chernoff) }} \ {\leq 2 \mathcal{N}(\mathcal{F}, 2 n) \exp \left(-n \varepsilon^{2} / 4\right)}\end{array}

即得出：

P\left(\sup <em>{f \in \mathcal{F}}\left|R(f)-R</em>{\mathrm{emp}}(f)\right|>\epsilon\right) \leq 2 \mathcal{N}(\mathcal{F}, 2 n) \exp \left(-n \varepsilon^{2} / 4\right)

那麼同樣也可以得出當

n \rightarrow \infty

右邊式子收斂於0時，經驗風險最小化具有相合性這個結論。結合並界那一節，現在可以依次寫出單個函式的收斂邊界、有限函式的一致收斂邊界以及更為有限與無限函式的一致收斂邊界了：

P\left(\left|R_{\mathrm{emp}}(f)-R(f)\right| \geq \epsilon\right) \leq 2 \exp \left(-2 n \epsilon^{2}\right)

P\left(\left|R_{\mathrm{emp}}(f)-R(f)\right| \geq \epsilon\right) \leq 2m \exp \left(-2 n \epsilon^{2}\right)

P\left(\sup <em>{f \in \mathcal{F}}\left|R(f)-R</em>{\mathrm{emp}}(f)\right|>\epsilon\right) \leq 2 \mathcal{N}(\mathcal{F}, 2 n) \exp \left(-n \varepsilon^{2} / 4\right)

並且式子右邊都滿足當

n \rightarrow \infty

右邊式子收斂於0，也就滿足了經驗風險最小化相合性的充要條件，如下

VC（（Vapnik & Chervonenkis））定理3給出了證明，即一致收斂條件：

P\left(\sup <em>{f \in \mathcal{F}}\left|R(f)-R</em>{\mathrm{emp}}(f)\right|>\epsilon\right) \rightarrow 0 \text { as } n \rightarrow \infty

對於所有

\varepsilon >0

5。5 泛化邊界

對於上節得出的式子：

P\left(\sup <em>{f \in \mathcal{F}}\left|R(f)-R</em>{\mathrm{emp}}(f)\right|>\epsilon\right) \leq 2 \mathcal{N}(\mathcal{F}, 2 n) \exp \left(-n \varepsilon^{2} / 4\right)

與其固定

\epsilon

值來求解機率，不如令其右邊式子等於一個

\delta>0

\epsilon=\sqrt{\frac{4}{n}(\log (2 \mathcal{N}(\mathcal{F}, n))-\log (\delta))}

對於左邊式子，由於其

>\epsilon

R(f) \leq R_{\mathrm{emp}}(f)+\sqrt{\left.\frac{4}{n}(\log (2 \mathcal N(\mathcal{F}, n))-\log (\delta)\right)}

這對於所有

f \in \mathcal{F}

都成立，一方面這是一個優點，另一方面不是所有函式或者說分類器滿足經驗風險最小化條件，但是這個邊界仍然使用，這也可以理解為是一個缺點。