1.2.2 如何在機器學習場景中應用大數定律

回顧一下大數定律的數學表達，即霍夫丁不等式P[|v-u|＞?]≤2exp(-2?2N)。在機器學習場景中應用該公式時，需要對其略做改變。

首先，觀測樣本的統計值v對應到機器學習場景，是模型在訓練樣本上取得的效果E_in（訓練誤差）。真實世界的統計值u可以認為是模型在預測樣本上的表現E_out（真實誤差）。任何模型的訓練誤差和真實誤差的差距均應滿足霍夫丁不等式的限制：

P[|E_in-E_out|＞?]≤2exp(-2?2N)

這是因為機器學習模型并不是隨意指定的函數關系，它是在M大小的假設空間中選擇能最佳擬合訓練數據的函數，如圖1-9所示。這個選擇過程（優化）會對上述不等式造成何種影響呢？

圖1-9 在M個函數中進行最優選擇的過程，使得E_in和E_out滿足某個差距的概率增大了M倍

可以這樣思考，在訓練數據集上，E_in表現得非常優秀（E_in很小）的可能有兩種：第一種是模型捕捉到了正確的關系函數；第二種是模型捕捉到了一個虛假的關系函數，只是該函數湊巧在收集到的有限訓練樣本上表現得不錯，而實際并不是正確的（應用到未知樣本上的預測錯誤很多）。一旦發生后一種情況，我們稱犯了“小概率事件”錯誤（E_in和E_out的差距很大）。假設出現這種情況的概率為P，如果僅僅隨機指定一種關系，出現“小概率事件”錯誤的概率是滿足霍夫丁不等式的。但從M種關系可能中選擇表現最好的，會使“小概率事件”錯誤的概率增大M倍。假設M個函數中有M-個在訓練數據上表現良好（M-≤M），因為每個關系均以P的概率為“小概率事件”錯誤，且一旦某個關系出現“小概率事件”錯誤，我們肯定會選擇它（因為它在訓練樣本上表現好），所以最終結果為“小概率事件”錯誤的概率增大M-倍。考慮到M-最多可以等于M，所以在M大小的假設空間中做優化學習，最多會使得E_in和E_out滿足某個差距的概率增大M倍，即需要在上述不等式的右側乘以M。

P[|E_in-E_out|＞?]≤2Mexp(-2?2N)

可見，模型的假設空間大小M極大地影響了大數定律在機器學習過程中的作用，它究竟和什么因素有關？讓我們從兩個實際案例來感受一下。

M函數的兩個案例

假設空間的大小M究竟和什么因素有關呢？對于分類問題，給定樣本數量，假設空間代表存在多少種樣本分布，分類函數能正確地將每個類別的樣本區分開。例如，對于二分類問題，若有兩個樣本，則共有4種樣本分布（正正、正負、負正、負負），如果模型能將這四種情況均正確地分類，它的假設空間大小為4。換句話說，假設空間是一個模型的函數表示能力——能夠完美地擬合多少種關系。假設空間越大，模型的表示能力越強，也就能更好地學習那些現實世界中的復雜關系。

案例6 線性二元分類

線性二元分類是使用一條直線區分兩種可能或正或負的樣本。形象地說，就是對散布在一張紙上的圓圈和叉叉，嘗試畫一條直線將兩者分開。

對于N個樣本，每個樣本有正負兩種分類可能，最理想的假設空間M有2N種分布，即正確地劃分每種樣本分布。但線性分類模型能夠達到這個極限嗎？

先來看看樣本數量較少的簡單場景，通過觀察來猜測規律。

1）1個樣本點：共有2種樣本分布的可能（樣本分布：該樣本為正樣本或負樣本），全部可以用一條直線分割。

2）2個樣本點：共有4種樣本分布的可能（樣本分布：正正、正負、負正、負負），全部可以用一條直線分割。

3）3個樣本點：共有8種樣本分布的可能（樣本分布：在2個樣本點的4種分布上，再加入一種新樣本為正和一種新樣本為負的情況），全部可以用一條直線分割。

4）4個樣本點：共有16種樣本分布的可能，其中有2種情況無法用一條直線分割，可分割的情況有14種，如下圖所示。

通過觀察，我們發現4個樣本點不能全部可分。這僅僅是故事的開始，隨著樣本數量越來越多，不可分割的情況也越來越多。也就是說，線性二元分類的假設空間M隨著樣本量N的增長是小于2的指數次冪的。

P[|E_in-E_out|＞?]≤2Mexp(-2?2N)

其中，M達不到2的指數次冪增長。

因為霍夫丁不等式右側有一個e指數次冪，如果M的增長達不到2的指數次冪，隨著N的增大，不等式右側依然會趨近于0（只是需要的樣本量N更多）。也就是說，線性二元分類模型是滿足大數定律的。如果基于大量數據學習出一個線性二分類模型，且它在訓練數據上表現良好，那么它大概率是真實的（在未知數據上也會表現良好）。

案例7 二元凸多邊形的分類模型

與案例6一樣，樣本或為正或為負，但可用凸多邊形對樣本做出分類。下面在一種略極端的樣本分布場景下探討凸多邊形假設空間M的大小。

假設有n個數據點，它們分布在一個圓上，每個樣本點均可為正樣本或負樣本，共有2n種可能。無論哪種可能，均可以用凸多邊形將正負樣本分開。如圖所示，只要將所有的正樣本用一個多邊形連接起來，然后將該多邊形略微外擴一點（從每個正樣本點的位置略向外延展），它就會將所有的正樣本點圈進來，而把所有的負樣本點排除在外，即完美地區分開正負樣本。

P[|E_in-E_out|＞?]≤2Mexp(-2?2N)

其中，M以2的指數次冪增長。

由此可見，凸多邊形的分類模型的假設空間M的增長速度是2n。在這種情況下，大數定律的限制失效了。霍夫丁不等式的右側并不會隨著樣本量N的增長而減少。也就是說，我們永遠無法用這種假設空間學習到一種可從統計上相信的規律。無論真實的關系如何，均可以用凸多邊形學習出一種將訓練數據擬合得很好的關系，但它往往是虛假的。

由上述兩個案例可見，假設空間的大小與兩個因素相關，即假設H和樣本量N，可以寫成兩者的函數M(H,N)，這稱為增長函數。我們喜歡那些增長函數小于2的指數次冪的假設，因為在這種時候，學習才是可能的！