下面三張圖的模型分別是：y=θ0+θ1x，y=θ0+θ1x+θ2x2，y=θ0+θ1x+…θ5x5。
第一幅圖和第三幅圖都有很大的泛化誤差，但它們的問題是不一樣的。第一幅圖的問題是欠擬合，y 和 x 的關係不是線性的，但我們非要用線性模型去擬合，即使有大量的訓練數據，也不能精確捕捉到數據中隱藏的結構信息，這種情況被稱為模型的偏差。第三幅圖的問題是過擬合，使用五階多項式來擬合數據，就有很大的風險是，我們擬合得到的模型，僅僅適用於當前的小量的、有限的訓練數據集，不能代表 y 和 x 在更大範圍的關係模式，譬如在訓練集中的房屋價格在這裡只是隨機地比均值低，在另一處又隨機地比均值高，如果訓練集中的這種假的模式都要捕捉，那必定要產生巨大的泛化誤差，這種情況被稱為模型的方差。
偏差和方差之間常常有一個權衡。如果模型很簡單，參數很少，那麼偏差就會很大，但方差小。如果模型很複雜，參數很多，那就可能有很大的方差，但偏差很小。上例中，二次函數明顯比一階和五階多項式好。
下面開始介紹學習理論，這有助於磨練我們的直覺，給出在不同情況下更好地應用學習算法的準則。我們將試圖回答這些問題：首先，我們能不能形式化偏差/方差的權衡？這最終會引導我們討論模型選擇方法，例如自動決定使用何階多項式來擬合訓練集；其次，在機器學習中最關心泛化誤差，大多數學習算法都在訓練數據中擬合模型，為什麼訓練集中表現好會告訴我們關於泛化誤差的情況？訓練集的誤差和泛化誤差有關聯嗎？最後，有沒有什麼條件，可以證明一種學習算法好？
先來兩個簡單有用的定理：
定理1：設 A1,A2,...Ak 為 k 個不同的事件（它們不一定獨立），那麼 P(A1∪...∪Ak)≤P(A1)+...P(Ak)
定理2：設 Z1,...,Zm 為 m 個獨立同分布的隨機變量，都服從伯努利分佈 Bernoulli(Φ) ，P(Zi=1)=Φ，P(Zi=0)=1-Φ。設
為隨機變量的均值，設 γ>0 為定值，得：
也稱 Hoeffding 不等式。
我們先來考察下不等式的右邊，先看當 γ 為定值（分別為 0.2、0.3、0.4）時，右邊值的變化情況，再看 m 為定值（分別是 20、50、80）時，右邊值的變化。如下圖所示。加號展開即是繪圖 Python 代碼。
import numpy as npimport matplotlib.pyplot as plt
fig = plt.figure()
#當 gama 為定值時，不等式右邊值隨 m 的變化
m=np.linspace(1,100,100)
gama=0.2
p=2*np.exp(-2*m*(gama**2))
ax=fig.add_subplot(231)
ax.set_title('gama=0.2')
ax.set_xlabel('m')
ax.set_ylabel("2exp(-2mgama^2)")
plt.sca(ax)
plt.plot(m,p)
gama=0.3
p=2*np.exp(-2*m*(gama**2))
ax=fig.add_subplot(232)
ax.set_title('gama=0.3')
ax.set_xlabel('m')
plt.sca(ax)
plt.plot(m,p)
gama=0.4
p=2*np.exp(-2*m*(gama**2))
ax=fig.add_subplot(233)
ax.set_title('gama=0.4')
ax.set_xlabel('m')
plt.sca(ax)
plt.plot(m,p)
#當 m 為定值時，不等式右邊值隨 gama 的變化
gama=np.linspace(0.01,1,100)
m=20
p=2*np.exp(-2*m*(gama**2))
ax=fig.add_subplot(234)
ax.set_title('m=20')
ax.set_xlabel('gama')
ax.set_ylabel("2exp(-2mgama^2)")
plt.sca(ax)
plt.plot(gama,p)
m=50
p=2*np.exp(-2*m*(gama**2))
ax=fig.add_subplot(235)
ax.set_title('m=50')
ax.set_xlabel('gama')
plt.sca(ax)
plt.plot(gama,p)
m=80
p=2*np.exp(-2*m*(gama**2))
ax=fig.add_subplot(236)
ax.set_title('m=80')
ax.set_xlabel('gama')
plt.sca(ax)
plt.plot(gama,p)
plt.show()
從上圖可以看出，當 γ 和 m 增大時，不等式右邊值隨著減小。也就是說，當 m 增大時，Φ 尖和 Φ 的誤差是變小的。
這個定理是說，當 m 很大時，如果我們通過 Φ 尖來估計 Φ，那麼它偏離真實值的概率是很小的。還有種說法，如果你拋一枚不均衡的硬幣 m 次，那麼以頭向上的比例來估計頭朝上的概率 Φ，那麼它就有很大的概率是個好估計。
用這兩個定理，就可以證明學習理論中一些深刻的、重要的結論。
為敘述簡單起見，下面只關注二分類，y∈{0,1}，此處講的所有內容都可以推廣到其它問題，如迴歸和多分類問題。
設有訓練集 S={(x(i),y(i));i=1,...,m} ，訓練集 (x(i),y(i)) 由同一概率分佈 D 生成，對於假設 h，定義訓練錯誤為：
在學習理論中也稱為經驗風險或者經驗錯誤。
這是 h 在訓練集上誤分類的比例。要明確 ε(h) 尖對訓練集 S 的依賴關係時，也可以寫成 εS(h)。我們也定義泛化誤差為
這個概率表示，如果從分佈 D 中生成一個新例子 (x,y) ，h 會給它分錯類。
注意我們假定訓練數據來自同一分佈 D，我們將通過泛華誤差的定義來評估假設。有時這也是 PAC 的假設之一。
考慮線性分類的情況，使 hθ(x)=1{θTx≥0}，擬合參數 θ 的合理方法是什麼？我們的方法是最小化訓練誤差：
這個過程稱為經驗風險最小化(ERM)，輸出的結果假設是學習算法
，ERM 是最基礎的學習算法，像 Logistic 迴歸也被看作經驗風險最小化的估計。
在學習理論的研究中，從特定的參數化假設或題目如是否使用線性分類器中抽離出來是很有用的，我們定義學習算法使用的假設類 H 為所有分類器的集合，對於線性分類，H={hθ : hθ(x)=1{θTx≥0},θ∈Rn+1} 是所有線性決策邊界的分類器的集合。再比如，如果學習神經網絡，就可以使 H 為代表一些神經網絡架構的分離器集合。
經驗風險最小化可以被認為是函數類 H 中的最小化，學習算法選擇假設：
先來看個學習問題，有限假設類 H={h1,...,hk} 由 k 個假設組成。所以 H 是 k 個從 X 到 {0,1} 的映射函數的集合，經驗風險最小化選擇 h^ 為這 k 個函數有最小的訓練誤差。
我們要對 h 尖的泛華誤差進行擔保。分兩步進行：第一步，證明對於對於所有的 h，ε^(h) 都是 ε(h) 的可靠估計，第二步，證明 h^ 的泛化誤差是有上界的。
取任意一個固定的 hi∈H，有一個伯努利隨機變量 Z，分佈定義如下，採樣 (x,y)~D，設 Z=1{h(x)≠y}，即，取個例子，讓 Z 表示 hi 有沒有錯分。類似的，定義 Zj=1{hi(x(j))≠y(j)}，訓練集來自獨立同分布 D，Z 和 Zj 來自同一分佈。
可以看出，在隨機例子中的誤分概率 ε(h) 正好是 Z(Zj) 的期望值。而且，訓練誤差可寫為
所以 ε^(hi) 正好是 m 個隨機變量 Zj 的均值，Zj 是來自均值為 ε(h) 的伯努利分佈。所以，我們可以使用 Hoeffding 不等式
這表示，對於特定的 hi，假定 m 很大，訓練誤差以很高的概率接近泛化誤差，但我們不僅僅只是想擔保特定的 ε^(hi) 以高概率趨近 ε(hi)，而是要證明所有的 h 都這樣。為此，設 A 表示事件 |ε(hi)-ε^(hi)|>γ，已經證明，對於特定的 Ai，有 P(Ai)≤2exp(-2γ2m)，所以有
兩邊都由 1 減去，得
也就是說，至少有 1-2kexp(-2γ2m) 的概率，對於所有的 h，ε(h) 和 ε^(h) 之間相差 γ，稱為均勻收斂結果。
在上面的討論中，對於特定的 m 和 γ，對概率給定一個界限，對於 h∈H，|ε(h)-ε^(h)|>γ ，這裡有三個量化點：m，γ 和錯誤概率。我們可以變動任意一個，依據另外兩個。
例如問題，給定 γ 和 δ>0，那麼 m 為多大才能保證訓練誤差和泛化誤差之差 γ 的概率為 1-δ？設 δ=2kexp(-2γ2m)，解出 m。我們發現當
時，至少 1-δ 的概率，對於所有的 h∈H，有 |ε(h)-ε^(h)|≤γ（因為至多有 δ 的概率使 |ε(h)-ε^(h)|>γ），這個界可以告訴我們需要多少例子來做保證。為使算法達到一定性能所需的訓練集大小 m 被稱為採樣複雜度。
上面界限的一個關鍵屬性是 k 的 log 值，H 中的假設個數，這在後面很重要。
類似的，也可以固定 m 和 δ，解出 γ，那麼就有 1-δ 的概率有
現在假設滿足均勻收斂條件，即對所有的 h∈H，有 |ε(h)-ε^(h)|≤γ。那麼取 h^=argminh€Hε^(h)，關於學習算法的泛化，能證明什麼？
定義 h*=argminh€Hε(h) 為 H 中最好的假設。有
第一行根據 |ε(h^)-ε^(h^)|≤γ，即通過均勻收斂假設。
第二行根據 h^=argminh€Hε^(h)，所以 ε^(h^)≤ε^(h)，特別的，ε^(h^)≤ε^(h*)。
第三行再次根據均勻分佈假設，ε^(h*)≤ε(h*)+γ。
上式表示，如果均勻收斂，那麼 h^ 的泛化誤差至多比 H 中最好的假設 h* 壞 2γ。
我們把這些合成一個定理。
定理：設 |H|=k，設 m，δ 為定值，那麼至少有 1-δ 的概率
證明此式，只需使 γ 等於根號部分，然後使用上面的結果即可。
這就量化了我們之前講的模型選擇中，偏差和方差的權衡。假設有一些假設類 H，現在切換到一個更大的假設類 H‘⊇H，那麼第一項 minhε(h) 只可能減少，因為我們從一個更大的函數集合中取最小。所以，學習使用一個更大的假設類，我們的偏差只會減少。如果 k 增加，那麼第二項 2√· 也會增加，即方差也會增加。（參考文 3 的解釋：當選擇一個複雜的模型假設時，|H|=k 會變大，導致不等式後的第二項變大，意味著方差變大，但第一項又會變小，因為使用一個更加大的模型集合，意味著可供選擇的模型假設變多了，在多的那部分中可能有比原來還要小的模型，這樣偏差就會變小。選擇一個最優值，使得偏差與方差之和最小，才能得到一個好的模型）
令 γ 和 δ 固定，跟之前一樣解出 m，就得到下面的採樣複雜度界限。
推論：令 |H|=k，固定 δ 和 γ，那麼至少有 1-δ 的概率使 ε(h^)≤minh€Hε(h)+2γ。它滿足
現在，我們證明了有限假設類的一些有用的理論。但有許多假設類包含了無數的函數，如參數為實值的，如線性分類中。這種情況也能得到類似證明嗎？
先來看一些不是正確的討論，更好和更多的廣義參數是存在的，這對於磨練我們在這個領域的直接是很有用的。
假設 H 有 d 個實值參數，因為我們用電腦來表示實數值，IEEE 的雙精度浮點用 64 位比特來表示一個浮點數，假定使用雙精度浮點數，這意味著我們的學習算法參數有 64d 位，所以，我們的假設類是由至多 k=264d 個不同的假設組成。從上面的推論可得，為保證至少有 1-δ 的概率，使 ε(h^)≤ε(h*)+2γ，它滿足
下標 γ 和 δ 表示大 O 隱藏了依賴於 γ 和 δ 的常數。
所以，所需的訓練集數目至多跟模型參數呈線性關係。
64 位浮點數表示參數的事實並不完全對，但結論無疑是正確的。如果想最小化訓練誤差，為了用好 d 個參數的假設類，通常使用跟 d 呈線性關係的訓練例子數目。
在這一點上，值得一提的是，這些結果是隻被使用經驗風險最小化（ERM）的算法所證明，所以，對於大多數試圖最小化訓練誤差的判別學習算法，對 d 的採樣複雜度的線性依賴滿足時，這些結論並不總能應用到判別學習算法。對很多非 ERM 學習算法一個理論保證，依然是一個研究熱點。
之前的討論的另一部分，對於 H 的參數的依賴就不太讓人滿意了。直觀上，好像沒多大關係：線性分類器為 hθ(x)=1{θ0+θ1x1+...+θnxn≥0}，有 n+1 個參數 θ0,...,θn，但它也可以寫成 h(x)=1{(u02-v02)+(u12-v12)x1+...+(un2-vn2)xn≥0}，有 2n+2 個參數 ui,vi。這些都定義了同一個 H：n 維線性分類器的集合。
為了導出一個更加滿意的結果，我們再來定義一些東西。
給定一個集合 S={x(i),...,x(d)}（跟訓練集沒關係），點 x(i)∈X，如果 H 能識別 S 的一些標籤，那麼就說 H 分散了 S。例如，如果對於一些標籤集合 {y(1),...,y(d)}，那麼對於所有的 i=1,..,d，存在 h∈H 使 h(x(i))=y(i)。
給定假設類 H，我們能定義它的 Vapnik-Chervonenkis dimension，記作 VC(H)，為被 H 分散的最大集合的大小。（如果 H 能分散任意大的集合，那麼 VC(H)=∞）。
例如，考慮下面三個點的集合：
兩維的線性分類器（h(x)=1{θ0+θ1x1+θ2x2≥0}）的集合 H 能分散這個點集嗎？可以。對於 8 個可能的標籤組合，我們能找到一個線性分類器來獲得一個 0 訓練誤差：
進一步，可能有 4 個點的集合不能被假設類分散，所以，H 能分散的最大集是 3，所以，VC(H)=3。
注意，這裡即使有 3 個點的集合不能被分散，H 的 VC 維依然是 3。例如如果有三個點在一條直線上，就不能用線性分類器分開。但這無關緊要，只要存在一個三個點的集合，不論以任何的標記方式，直線集合都能將其線性分開的話，就認為直線集合能分散的點的數目是 3。對於 4 個點的集合，不存在一個 4 點集合，無論以任何標記方式，都能將其用線性分類器分開，所以，就得到，在二維平面上，對於直線集合，它能分散的點的最大數目是 3。
換句話說，在 VC 維的定義下，為了證明 VC(H) 至少是 d，我們要展示的僅僅是存在至少有一個大小為 d 的集合 H 能分散。
下面的定理，根據 Vapnik，能被證明。這是學習理論中最重要的定理。
定理：給定 H，使 d=VC(H)，那麼至少有 1-δ 的概率，對於所有 h∈H，有
所以，至少有 1-δ 的概率，有
換句話說，如果一個假設類有有限 VC 維，那麼當 m 變得很大時，就會均勻收斂。跟之前一樣，這允許我們可以給 ε(h) 一個關於 ε(h*) 的邊界，有下列推論：
推論：對於所有的 h∈H，滿足 |ε(h)-ε^(h)|≤γ，至少有 1-δ 的概率，使 m=Oγ,δ(d)。
換句話說，使用 H 能學好的訓練集數目跟 H 的 VC 維是呈線性關係的，對於大多數假設類，VC 維也同參數個數大致呈線性關係。總而言之，對於一個最小化訓練誤差的算法，所需的訓練集的數目通常跟 H 的參數個數呈線性關係。
參考資料：
1、http://cs229.stanford.edu/notes/cs229-notes4.pdf
2、http://blog.csdn.net/stdcoutzyx/article/details/18407259
本文來自天善智能社區作者：瘋狂的拖鞋