????????在上一篇筆記中目尖，我們討論了NFL定理嘹承，該定理指出不結(jié)合具體問題去比較學習算法之間的優(yōu)劣是沒有意義的摔蓝。那么如果針對具體的問題我們又可能會提出如下的一些問題：

1. 為了獲得一個好的模型膘侮，需要多少訓(xùn)練數(shù)據(jù)呢清女？

2. 在某個訓(xùn)練集上機器學習方法針對某個具體問題得到的模型在作預(yù)測時能達到多好的效果呢阳惹？

3. 針對具體的問題谍失，如果去比較使用不同的學習算法產(chǎn)生的模型的優(yōu)劣呢？

在這一篇文章中我們將試圖討論這些問題莹汤。

????????首先引入一個概念：泛化能力

????????學習方法泛化能力是指由該方法學習到的模型對未知數(shù)據(jù)的預(yù)測能力快鱼。我們使用模型在測試集上的測試誤差來評價學習方法的泛化能力，這個測試誤差又稱為“泛化誤差”纲岭。如果A算法學習到的模型的泛化誤差比B算法學習到的模型的泛化誤差小抹竹，那么A算法就比B算法更有效。

????????使用泛化誤差來評價模型的預(yù)測能力有個問題止潮，泛化誤差依賴于測試數(shù)據(jù)集窃判，而相對于整個樣本空間來說測試數(shù)據(jù)集是有限的，很有可能得到的評價結(jié)果是不可靠的喇闸，真的可以用泛化誤差去衡量模型的預(yù)測能力嗎袄琳？下面討論的計算學習理論將從理論上來分析這個問題询件，這些理論的正式的分析和證明的數(shù)學味道有點重，但是其中的數(shù)學原理并不難唆樊，在筆記中我會以大白話的方式來描述宛琅。

????????計算學習理論的原理是這樣的：在輸入少量的樣本后，任何包含嚴重錯誤的假設(shè)都幾乎一定會以較高的概率被發(fā)現(xiàn)逗旁，因為它將做不正確的預(yù)測嘿辟。因此，與足夠大的訓(xùn)練數(shù)據(jù)集一致的任何假設(shè)都不可能包含嚴重錯誤片效，也就是說它必定是概率近似正確的（probably approximately correct, PAC）红伦。這個原理又叫“PAC學習理論”，接下來將通過PAC理論來回答筆記開頭提出的幾個問題堤舒。

一色建、“需要多少訓(xùn)練數(shù)據(jù)”

????????“PAC學習理論”的內(nèi)涵還是比較多的，其中之一就是解答了為了獲得一個好的模型我們需要多少訓(xùn)練數(shù)據(jù)的問題舌缤，內(nèi)容可以描述如下：

????????存在一個數(shù)量N箕戳，使得在容量為N的訓(xùn)練集上訓(xùn)練出的所有假設(shè)在預(yù)測新的數(shù)據(jù)集時其錯誤率error(h)能以至少1-??的概率小于等于?，其中?和??均為小常量国撵。也就是說與N個訓(xùn)練樣本一致的假設(shè)陵吸，能以較高的概率（至少1-??）近似正確（預(yù)測新數(shù)據(jù)集時錯誤率小于等于?）。

????????在做簡單的證明之前介牙，需要說明的是我們這里假設(shè)我們所面對的輸入空間（即我們的訓(xùn)練數(shù)據(jù)和未來要預(yù)測的數(shù)據(jù)）是穩(wěn)定的（即輸入的分布規(guī)律不會變化壮虫，如果說輸入空間不是穩(wěn)定的，那么我們在訓(xùn)練數(shù)據(jù)集上學習到的模型就是過時的了环础，我們要做機器學習那么至少要確定輸入空間最多是緩慢變化的囚似，不然學習就沒有意義了）。

????????簡單的證明：

????????在假設(shè)空間H中存在很多的假設(shè)函數(shù)线得，我們雖然不知道它們的預(yù)測性能饶唤，但是我們知道我們可以將假設(shè)空間中的假設(shè)函數(shù)分為兩類，一類是所有近似正確的假設(shè)的集合Hg贯钩，Hg中的每個假設(shè)hg的預(yù)測錯誤率error(hg)小于等于我們給定的小常量?募狂，另一類是嚴重錯誤的假設(shè)的集合Hb，Hb中的每個假設(shè)hb的預(yù)測錯誤率error(hb)都大于?角雷。

????????假定我們有N個訓(xùn)練樣本構(gòu)成的訓(xùn)練數(shù)據(jù)集祸穷，我們的學習算法的任務(wù)是從假設(shè)空間中搜索出與N個訓(xùn)練數(shù)據(jù)相一致的假設(shè)函數(shù)，那么這個被搜索出來的與N個訓(xùn)練數(shù)據(jù)一致的假設(shè)函數(shù)有多大的概率是在Hb中呢勺三？我們當然希望這個概率越小越好雷滚，因為在Hb中意味著它的預(yù)測錯誤率大于?，是個嚴重錯誤的假設(shè)吗坚。下面我們來計算下這個概率：

????????已知對于Hb中的假設(shè)hb有error(hb)﹥?揭措，因此它與一個給定的樣本一致的概率最多為1- ?胯舷，因為樣本之間是相互獨立的，對于N個樣本绊含，hb能同時與它們都一致的概率邊界為：

????????考慮最好的情況桑嘶，即Hb中所有的假設(shè)函數(shù)都能以上面的概率上界與N個樣本一致，并令：

????????那么躬充，因為Hb中的假設(shè)函數(shù)之間相互獨立逃顶，所以整個Hb中與N個樣本一致的假設(shè)的個數(shù)c服從二項分布c~B(|Hb|, p)，

????????那么E(c) = |Hb|p充甚，同時按照求期望的公式我們有：

????????再看Hb中至少包含一個假設(shè)hb與N個樣本都一致的概率：

不難看出:

????????進一步以政，我們利用不等式（引入這個不等式，一是為了找出后面說的概率的上界伴找，二是可以方便求出N盈蛮，因為N是一個指數(shù)，不好求解技矮，引入e后就可以求對數(shù)把N從指數(shù)中拿出來抖誉。這個不等式很好證明，簡單的證法可以是衰倦，用不等式兩邊的函數(shù)的商構(gòu)成一個新的函數(shù)袒炉，對新的函數(shù)對?求導(dǎo)可以發(fā)現(xiàn)導(dǎo)數(shù)小于等于0，所以新函數(shù)是減函數(shù)樊零，再令?＝0可以得到新函數(shù)的值為1我磁，因為0<＝?<＝1，所以新函數(shù)的值f(?) <= f(0)＝1驻襟，即新函數(shù)的分子小于等于分母夺艰，即不等式得證）

????????進一步找到P(Hb中至少包含一個一致假設(shè))的一個上界：

????????如果我們希望Hb中至少包含一個一致假設(shè)的概率很小（即沉衣，我們希望與N個樣本一致的假設(shè)盡量不要出現(xiàn)在Hb中郁副，因為如果在Hb中那么這個一致假設(shè)將是嚴重錯誤的），小于某個給定的小常量??厢蒜，那么我們就應(yīng)該使這個概率的上界小于??，即：

????????對上式兩邊取對數(shù)烹植，進行簡單的整理后可以得到：

????????上面的證明過程也就是尋找N的過程斑鸦，我們可以看到，對于任意給定的?和??草雕，我們找到了一個N巷屿，當訓(xùn)練數(shù)據(jù)集中至少有N個訓(xùn)練樣本時，學習算法得到的假設(shè)函數(shù)可以以至少1-??的概率有至多?的錯誤率墩虹。

二嘱巾、“模型的泛化能力能有多好”

????????PAC學習定理除了告訴我們需要多大的訓(xùn)練數(shù)據(jù)集外憨琳，還告訴了我們一個算法的泛化誤差上界是多少，即它能有多準確旬昭。

????????泛化誤差上界通常具有以下性質(zhì)：它是訓(xùn)練數(shù)據(jù)集中樣本容量的函數(shù)篙螟，當樣本容量增加時，泛化上界趨于0问拘；它是假設(shè)空間容量的函數(shù)遍略，假設(shè)空間容量越大，模型就越難學骤坐，泛化誤差上界就越大绪杏。

????????為了簡化問題，這里只看二分類問題且假設(shè)空間包含有限個函數(shù)時的泛化誤差上界纽绍。

????????對于一個二分類問題蕾久，一個訓(xùn)練數(shù)據(jù)集T = {(x1, y1), (x2, y2), ..., (xN, yN)}，X屬于n維實數(shù)空間拌夏，Y∈{-1, 1}僧著。假設(shè)空間是函數(shù)的有限集合F={f1, f2, f3, ..., fd}，d是函數(shù)的個數(shù)辖佣。設(shè)f是從F中選取的函數(shù)霹抛，我們使用0-1損失作為損失函數(shù)，即損失函數(shù)L(Y, f(X))的取值為：當預(yù)測值f(X)和真實值Y相等時為0卷谈，不等時為1杯拐。那么關(guān)于f的期望風險和經(jīng)驗風險分別是：

????????那么我們的機器學習算法按照經(jīng)驗風險最小化原則搜索出來的假設(shè)函數(shù)就是：

????????我們現(xiàn)在關(guān)心的就是這個被搜索出來的假設(shè)函數(shù)fN的泛化能力：

????????這里直接給出關(guān)于這個泛化誤差上界的結(jié)論，其證明的關(guān)鍵點是用到Hoeffding不等式世蔗，其余的推導(dǎo)很簡單端逼，具體可以查閱《統(tǒng)計學習方法》這本書。

二分類問題的泛化誤差上界：

????????對二分類問題污淋，當假設(shè)空間是有限個函數(shù)的集合F={f1, f2, f3, ..., fd}時顶滩，對任意一個函數(shù)f∈F，至少以概率1- ??寸爆，以下不等式成立：

其中礁鲁，

從上面的結(jié)論可以看出：

1. 模型的泛化誤差是有上界的，對于這里討論的假設(shè)空間有限的二分類問題赁豆，只要給出一個訓(xùn)練數(shù)據(jù)集和假設(shè)空間大小仅醇，再給定一個任意的0<??<1我們就能找到模型的泛化誤差上界；

2. 對于這里討論的問題魔种，泛化誤差上界由兩部分構(gòu)成析二，第一部分是訓(xùn)練誤差，訓(xùn)練誤差越小，泛化誤差也越幸渡恪属韧；第二部分是一個關(guān)于訓(xùn)練樣本容量N的單調(diào)減函數(shù)，N越大這部分的值越小蛤吓，N趨于無窮時值趨于0宵喂，也就是說如果我們的訓(xùn)練數(shù)據(jù)已經(jīng)包含了所有可能的輸入輸出對情況，那么我們在訓(xùn)練數(shù)據(jù)集上的訓(xùn)練誤差就是泛化誤差了柱衔；同時第二部分還是關(guān)于假設(shè)空間容量d的函數(shù)樊破，d越大即假設(shè)空間包含的函數(shù)越多，第二部分的值就越大唆铐，泛化誤差可能就越大哲戚。

三、“如何比較不同學習方法的優(yōu)劣”

????????這個問題就簡單了艾岂，可以通過比較兩種學習方法的泛化誤差上界的大小來比較它們的優(yōu)劣顺少。

至此我們就解答了筆記開頭提出的幾個問題了，這篇筆記主要介紹了機器學習中的計算學習理論王浴，的確比較枯燥脆炎，但是它是機器學習的基石，它確定了機器學習的可行性氓辣。

參考資料：

Stuart J. Russelll《人工智能 一種現(xiàn)代的方法》

李航《統(tǒng)計學習方法》