【學習筆記】斯坦福大學公開課：cs229 Part 6 Learning Theory【上】

來自專欄 Cjf的CS成長史4 人贊了文章

今天進入到cs229的學習理論部分，這一部分說簡單也簡單，畢竟在Coursera上學過一遍Ng的課，關於bias/variance tradeoff的相關內容有了一些了解，可是cs229里一上來證明，還是值得好好琢磨琢磨的。那麼這節課講了什麼呢？

前面學的是演算法，無論是線性回歸、邏輯回歸、廣義線性模型、指數分布族，還是樸素貝葉斯、SVM，以及涉及到的梯度下降法、牛頓法、最大似然估計、拉普拉斯平滑等等，都是一些具體的方法，在戰場上叫做「戰術」，相當於我們的武器。不過打仗不能憑藉一腔奮勇之情，還得講究方法和謀略。那麼學習理論就是告訴我們如何戰略布局，從根本上如何決策，以及為什麼要這樣決策的。

1 Bias/variance tradeoff偏差/方差權衡

簡而言之，模型的參數過少時，根本無法根據輸入準確地預測輸出，比方說我的數據本來是二次分布，你拿一個線性函數來糊弄我，那肯定不行，這時無論是訓練誤差還是泛化誤差（就是測試集上的誤差）都比較大，術語叫「high bias」；

模型的參數過多時，就會「過猶不及」，在已知的訓練集上，模型表現的很好，百發百中，沒有一個預測錯誤的；但是一到測試集上就露出馬腳了。就彷彿你把書上的題目都背會了，考試時來個沒見過的題目，就懵圈了。本來我就是一個二次函數分布，拋物線的形狀簡潔得很，你來了個五次函數的曲線，幾里拐彎的，怎麼可能預測的准。這時，訓練誤差很小，泛化誤差很大，術語叫「high variance」。

那麼，我們追求的，就是二者之間的平衡。

2 預熱——兩條引理

上面說到訓練誤差和泛化誤差，而訓練一個機器學習模型時我們只能知道前者，而看不到後者，所以這兩種誤差之間有什麼聯繫呢？能否根據訓練誤差很小就判斷出泛化誤差也很小呢?

首先安德魯老師拋出了兩條引理。一個是概率論中的公理：一堆事件中至少有一件事發生的概率一定不會超過這堆事件的發生概率總和。

另外一個是霍弗丁不等式：

什麼意思？說的是z1到zm是m個獨立同伯努利分布的隨機變數，即要麼是0，要麼是1，每個隨機變數的數學期望都是?，那麼，這m個變數一經生成（比如做了m次獨立重複試驗），我就可以用他們的平均數來估計他們每一個的期望，也就是?，並且對於任意小的整數γ，估計誤差超過γ的概率都不超過不等式右面的式子。

這倆引理對於接下來的論證很有幫助。為了簡便，安德魯老師使用二元分類問題舉例說明，可以推廣到回歸問題以及多分類問題。假設每組訓練數據（xi,yi）都是獨立同分布的，服從某種概率分布D。好的，表演開始。

這節課的符號很多，我偷個懶，就不詳細寫了。首先定義我們的經驗風險，也叫經驗誤差：empirical risk（empirical error），他其實說的就是m組訓練數據中，誤分類所佔比例，也就是用我們學習到的模型（假設）去預測輸出，和實際輸出不相符的數據所佔整體的比例。那麼泛化誤差（generalization error）的定義就是我們依據概率分布D抽取一組新數據（x,y），我們的模型會誤分類的概率P。

ERM（empirical risk minimize）經驗風險最小化其實我們已經接觸過了，在線性分類中，我們就曾經試圖找到一組參數θ，根據θ transpose x的正負來劃分h(x)是0還是1，做法就是用最大似然（梯度下降）等方法，找到使cost function最小的θ，這其實就是ERM。為了更具普適意義，現在我們說，我們是要在整個假設空間中找到某種假設（不一定是線性的了，有可能是神經網路那樣的），使得在這種假設下，經驗誤差最小。

3 假設空間有限

先來考慮假設空間中只有有限個（k個）假設的情況。

我們要套用之前的理論去做一些事情。從假設空間中隨意選取一個h，我們讓一個伯努利變數Z來指示h表現的怎麼樣，要是分類錯誤，Z=1，分類正確，Z=0. 注意，這裡有兩套符號，Z對應h在測試集上的表現（即新的example），Zj(1≤j≤m)對應h在訓練集上的表現。

注意到，由於bernoulli分布的特點，Z的數學期望，就等於Z=1的概率?，就等於我們的泛化誤差（上文提到，泛化誤差就是模型在new example上誤分類的概率），而經驗誤差，則可表示為Zj們的平均值，因此，根據引理2，我們就做出以下估計：

帶帽的是經驗誤差，不帶帽的是泛化誤差，也即bernoulli分布的數學期望。我們看到，前者對後者做了一個漂亮的估計。

但是注意，這裡只是針對假設空間H中的其中一個假設我們做出了這樣的保證，而我們要的是對H中所有假設，都滿足這一點，那麼引理1就要出場了。

事件 Ai表示的就是對於假設空間中第i個假設，它對應的經驗誤差和泛化誤差相差超過了γ的概率（我們姑且叫做演砸了），正因如此，使用引理1就是在算至少有一個假設演砸了的概率，因此，取個非，就是所有假設都演得很棒的概率了~並且，這個概率相當的高，注意到，對於任意γ>0成立，又是指數衰減，因此這個概率非常接近1了。這個結果叫做uniform convergence。

我想，這大概已經可以說明用ERM訓練模型在理論上的可行性了，然而我們還是要深究一下。

注意到，有三個變數，m,γ,還有概率誤差，即那個絕對值項，我們可以根據任意兩項確定第三項。比如，我們希望所有假設演技都棒的概率越大越好，如果令δ=2kexp(-2γ2m)，那麼當

時，就會達到我們的期望效果。上式表明，如果要使用ERM，我們至少需要多少訓練數據。能夠do a good performance的m，我們叫它sample complexity。注意到,m是k的對數函數，這很漂亮。

現在我們已經說明了，對於假設空間H中每一個假設，都可以用經驗誤差近似的代表它的泛化誤差，讓其經驗誤差最小，基本上也就做到了泛化誤差最小，即達到準確預測的目的。不過，這裡用了「基本上」，即還是會存在一些偏差的。也就是說，我們使用經驗誤差最小化，在H中挑了一個最好的假設h^，這個h^和真正能使得泛化誤差最小的某個同樣在H中的h*可能並不是同一個假設。那麼，h^和h*在泛化誤差方面，表現得究竟差了多少呢？兩次利用絕對值項，並注意到「帶帽」和「不帶帽」分別代表的是經驗誤差和泛化誤差，對h^和h*便有：

於是看到了，我們根據ERM選出來的h^比理想情況下的h*壞不到哪裡去，最多不超過2γ！好了，現在我們可以把上述歸納成一個定理了：

以及一個推論：

再說最後一個問題！

根據我們的定理，其實可以看出一些關於bias/variance tradeoff的端倪。如果我們擴大假設空間H變成H『，在H』中選擇模型，那麼定理中第一項只會變小（因為H是H『的子集），而到了H』之後，由於k變大了，第二項就會變大。這就說明，如果我們在更大的假設空間中選擇模型（簡單理解為，線性模型中，我們考慮更高次的多項式函數），偏差只可能變小，而方差則可能會變大，這和我們最開始的論述是一致的。

好了，下一篇筆記中，我再接著記錄H中假設數目無限的情況下的學習情況~

（圖片來源：Andrew Ng ，Stanford University cs229講義）

********分割線************

PS：經歷了各種偷懶，拖了不知道幾天之後，終於，，，把這篇寫完了[捂臉]