網易公開課，第9,10課
這章要讨論的問題是，如何去評價和選擇學習算法
bias/variance tradeoff
還是用這組圖，學習算法追求的是generalization error（對未知資料的預測誤差），而不是training error（隻是對訓練集）
最左邊，underfit，我們說這種學習算法有較大的bias
informally, we define the bias of a model to be the expected generalization error even if we were to fit it to a very (say, infinitely) large training set.
即在用足夠多的訓練集的情況下，仍然有較大的generalization error
最右邊，overfit， 我們說這種學習算法有較大的variance
在比較小或有限的訓練集的情況下，更容易發生
是以對于學習算法，我們需要tradeoff bias vs. variance，避免過于簡單或複雜的學習模型
preliminaries
在這章為了達到評價和選擇算法的目的，我們需要解決下面幾個問題，
first, can we make formal the bias/variance tradeoff that was just discussed? the will also eventually lead us to talk about model selection methods, which can, for instance, automatically decide what order polynomial to fit to a training set.
是否可以形式化bias/variance，因為這樣的話，我們就可以對每個學習模型計算出bias/variance ，進而可以自動選擇模型
second, in machine learning it’s really generalization error that we care about, but most learning algorithms fit their models to the training set. why should doing well on the training set tell us anything about generalization error? specifically, can we relate error on the training set to generalization error?
對于學習算法，我們真正關心的是generalization error，而我們之前都是用training error來作為優化目标
這樣想當然應該是合理的，但是有理論依據嗎？我們真的可以用training error來近似generalization error嗎？他們之間有怎樣的關系？
這是我們下面首先要讨論的問題
third and finally, are there conditions under which we can actually prove that learning algorithms will work well?
結論性的問題，在滿足什麼樣的條件下，我們就可以證明這個學習算法是work well的？
在讨論上面問題之前，先介紹兩個lemma，後面會用到，
第一個是union bound，這個定理顯而易見
第二個是hoeffding inequality
給個例子，z滿足bernoulli分布，最好的例子就是抛硬币，對于均勻的硬币，正面的機率是1/2
但是如果你抛10次，計算出現正面的概念可能不是1/2，但如果你抛100萬次或更多，你抛的越多，那麼得到正面的概念一定是趨向于1/2（bernoulli大數定理）
下面開始定義我們的問題，即上面提到的第二問題，
實驗誤差，實驗值不等于真實值的個數/m，很容易了解
現在為了闡述簡單，假設h為線性分類函數
這個算法的問題是，往往很難求解，并且是非凸的，而邏輯回歸或svm都可以看做是erm的凸化的近似優化算法
但這裡讨論學習理論，出于簡單考慮，就以erm為例子
是以從通用考慮，我們這裡用h做為優化參數，這樣更通用，因為h可以為任意函數，隻要可以将input映射到{0,1}即可
是以上面的erm就表示成這樣，容易了解嗎？
the case of finite h
下面先讨論的case是，h用的h函數為有限個，我們要從有限個h中找到最優的h
好，然後這節的内容就是想證明，對于有限個，這裡假設k個h，training error是對于generalization error的可靠的estimate
其實，我覺得的基于hoeffding inequality，這個證明是顯然成立的呵呵，當然下面的證明關鍵是可以給出formal的形式
那麼就有，隻是把上面公式中的換成z
并把hoeffding inequality代入的到一個不等式
然後關鍵的一步，兩邊取反
這個結果稱為uniform convergence result，一緻性收斂結果
當然這個式子，其實還有另外兩種表達方式，
這個用上面的式子很容易算出，算出的m稱為algorithm’s sample complexity，樣本複雜度
可以了解為，需要多大的樣本，樣本誤差才可以近似于一般誤差，滿足上面的不等式
大家看看一緻性收斂結果，證明半天，隻是證明對于某個h，他的實驗誤差和真實誤差之間的關系，我們可以更進一步，
那麼我們是否可以找出h hat和h star之間誤差的關系了？ 于是得到如下結論
第一個不等式就是h hat一緻性收斂不等式的轉換，
這個式子很有意思，可以非formal的反應出之前說的bias/variance之間的tradeoff
但更大的函數空間，會導緻k變大，是以第二項會變大，這個對應于variance
最後，得到這個推論，即滿足上面定理，m的樣本複雜度，這個其實和前面那個一樣，因為這個定理本身就是由一緻性收斂推導出的，是以兩個樣本複雜度也是一樣的
the case of infinite h
上面讨論的是有限的hypothesis，但對于一些hypothesis classes是包含無限的functions的，比如任何以real number作為參數的case
對于無限的case，我們是否仍然可以得到上面類似的結論？
我們先來直覺的看一個argument，雖然不是很formal或right
我們假設h是以實數作為參數的，因為計算機裡面是用64bit來表示實數的，當我們有d個參數的時候，
可以看到那個log很關鍵，它把一個指數關系變成線性關系了
上面的式子說明，對于無限的hypothesis而言，如果要滿足corollary定理，樣本複雜度m隻需要和參數個數d滿足線性關系
雖然這個argument不是那麼正确或formal，不過很直覺
下面我們更formal的來闡述這個argument，
先介紹一些定義，
首先是，shatter
直覺的說，就是如果h中總能找到一個function可以正确的将s中的item正确分類（item可以任意取值）
看這個圖，可以說明二維的線性分類是可以shatter這個3個元素的集合的
再者，定義vc維
h可以shatter的最大集合的size就是h的vc維
前面說明的二維的線性分類器的vc維就是3，你可以試試對于任意size為4的set，二維線性分類器都無法shatter
其實對于某些size為3的set，也無法shatter，比如下面這個set
但是隻要存在size為3的set可以被h shatter，我們就可以說h的vc維為3
并且可以證明對于n維的線性分類器，它的vc維為n+1
故可以給出一緻性收斂，
表明對于無限的h中的每個h，一般誤差和實驗誤差的內插補點是有上屆的，并且對于有限的vc維，隻要讓樣本複雜度m足夠大，就可以達到一緻性收斂
第二個式子，因為對于有限的case，我們可以從一緻性收斂推導出
故對于無限的case，這裡可以直接代入，進而給出無限維的corollary定理
表明隻需要樣本複雜度m和h的vc維成線性關系，那麼就可以滿足一緻性收斂
本文章摘自部落格園，原文釋出日期：2014-06-06