上節(jié)課，我們主要介紹了機器學(xué)習(xí)的可行性瞳抓。首先埃疫，由NFL定理可知，機器學(xué)習(xí)貌似是不可行的孩哑。但是栓霜，隨后引入了統(tǒng)計學(xué)知識，如果樣本數(shù)據(jù)足夠大横蜒，且hypothesis個數(shù)有限胳蛮，那么機器學(xué)習(xí)一般就是可行的。本節(jié)課將討論機器學(xué)習(xí)的核心問題丛晌，嚴格證明為什么機器可以學(xué)習(xí)仅炊。從上節(jié)課最后的問題出發(fā)，即當(dāng)hypothesis的個數(shù)是無限多的時候澎蛛，機器學(xué)習(xí)的可行性是否仍然成立抚垄？
一、Recap and Preview
我們先來看一下基于統(tǒng)計學(xué)的機器學(xué)習(xí)流程圖：
該流程圖中谋逻，訓(xùn)練樣本D和最終測試h的樣本都是來自同一個數(shù)據(jù)分布呆馁，這是機器能夠?qū)W習(xí)的前提。另外毁兆，訓(xùn)練樣本D應(yīng)該足夠大浙滤，且hypothesis set的個數(shù)是有限的，這樣根據(jù)霍夫丁不等式气堕，才不會出現(xiàn)Bad Data纺腊，保證Ein≈Eout，即有很好的泛化能力送巡。同時摹菠，通過訓(xùn)練，得到使Ein最小的h骗爆，作為模型最終的矩g次氨，g接近于目標函數(shù)。
這里摘投，我們總結(jié)一下前四節(jié)課的主要內(nèi)容：第一節(jié)課煮寡，我們介紹了機器學(xué)習(xí)的定義虹蓄，目標是找出最好的矩g，使g≈f幸撕，保證Eout(g)≈0薇组；第二節(jié)課，我們介紹了如何讓Ein≈0坐儿，可以使用PLA律胀、pocket等演算法來實現(xiàn)；第三節(jié)課貌矿，我們介紹了機器學(xué)習(xí)的分類炭菌，我們的訓(xùn)練樣本是批量數(shù)據(jù)（batch），處理監(jiān)督式（supervised）二元分類（binary classification）問題逛漫；第四節(jié)課黑低，我們介紹了機器學(xué)習(xí)的可行性，通過統(tǒng)計學(xué)知識酌毡，把Ein(g)與Eout(g)聯(lián)系起來克握，證明了在一些條件假設(shè)下，Ein(g)≈Eout(g)成立枷踏。
這四節(jié)課總結(jié)下來菩暗，我們把機器學(xué)習(xí)的主要目標分成兩個核心的問題：
- Ein(g)≈Eout(g)
- Ein(g)足夠小
上節(jié)課介紹的機器學(xué)習(xí)可行的一個條件是hypothesis set的個數(shù)M是有限的，那M跟上面這兩個核心問題有什么聯(lián)系呢呕寝？
我們先來看一下勋眯，當(dāng)M很小的時候，由上節(jié)課介紹的霍夫丁不等式下梢，得到Ein(g)≈Eout(g)客蹋，即能保證第一個核心問題成立。但M很小時孽江，演算法A可以選擇的hypothesis有限讶坯，不一定能找到使Ein(g)足夠小的hypothesis，即不能保證第二個核心問題成立岗屏。當(dāng)M很大的時候辆琅，同樣由霍夫丁不等式，Ein(g)與Eout(g)的差距可能比較大这刷，第一個核心問題可能不成立婉烟。而M很大，使的演算法A的可以選擇的hypothesis就很多暇屋，很有可能找到一個hypothesis似袁，使Ein(g)足夠小，第二個核心問題可能成立。
從上面的分析來看昙衅，M的選擇直接影響機器學(xué)習(xí)兩個核心問題是否滿足扬霜，M不能太大也不能太小。那么如果M無限大的時候而涉，是否機器就不可以學(xué)習(xí)了呢著瓶？例如PLA算法中直線是無數(shù)條的，但是PLA能夠很好地進行機器學(xué)習(xí)啼县，這又是為什么呢材原？如果我們能將無限大的M限定在一個有限的mH內(nèi)，問題似乎就解決了季眷。
二华糖、Effective Number of Line
我們先看一下上節(jié)課推導(dǎo)的霍夫丁不等式：
P[|Ein(g)?Eout(g)|>?]≤2?M?exp(?2?2N)
其中，M表示hypothesis的個數(shù)瘟裸。每個hypothesis下的BAD events Bm級聯(lián)的形式滿足下列不等式：
P[B1 or B2 or ?BM]≤P[B1]+P[B2]+?+P[BM]
當(dāng)M=∞時，上面不等式右邊值將會很大惰蜜，似乎說明BAD events很大荒辕，Ein(g)與Eout(g)也并不接近搀军。但是BAD events Bm級聯(lián)的形式實際上是擴大了上界，union bound過大沙郭。這種做法假設(shè)各個hypothesis之間沒有交集，這是最壞的情況裳朋，可是實際上往往不是如此病线，很多情況下，都是有交集的鲤嫡，也就是說M實際上沒那么大送挑，如下圖所示：
也就是說union bound被估計過高了（over-estimating）。所以暖眼，我們的目的是找出不同BAD events之間的重疊部分惕耕，也就是將無數(shù)個hypothesis分成有限個類別。
如何將無數(shù)個hypothesis分成有限類呢诫肠？我們先來看這樣一個例子司澎，假如平面上用直線將點分開，也就跟PLA一樣栋豫。如果平面上只有一個點x1挤安，那么直線的種類有兩種：一種將x1劃為+1，一種將x1劃為-1：
如果平面上有兩個點x1丧鸯、x2蛤铜，那么直線的種類共4種：x1、x2都為+1，x1昂羡、x2都為-1絮记，x1為+1且x2為-1，x1為-1且x2為+1：
如果平面上有三個點x1虐先、x2怨愤、x3，那么直線的種類共8種：
但是蛹批，在三個點的情況下撰洗，也會出現(xiàn)不能用一條直線劃分的情況：
也就是說，對于平面上三個點腐芍，不能保證所有的8個類別都能被一條直線劃分差导。那如果是四個點x1、x2猪勇、x3设褐、x4，我們發(fā)現(xiàn)泣刹，平面上找不到一條直線能將四個點組成的16個類別完全分開助析，最多只能分開其中的14類，即直線最多只有14種：
經(jīng)過分析椅您，我們得到平面上線的種類是有限的外冀，1個點最多有2種線，2個點最多有4種線掀泳，3個點最多有8種線雪隧，4個點最多有14（<24）種線等等。我們發(fā)現(xiàn)员舵，有效直線的數(shù)量總是滿足≤2N脑沿，其中，N是點的個數(shù)固灵。所以捅伤，如果我們可以用effective(N)代替M，霍夫丁不等式可以寫成：
P[|Ein(g)?Eout(g)|>?]≤2?effective(N)?exp(?2?2N)
已知effective(N)<2N巫玻，如果能夠保證effective(N)<<2N丛忆，即不等式右邊接近于零，那么即使M無限大仍秤，直線的種類也很有限熄诡，機器學(xué)習(xí)也是可能的。
三诗力、Effective Number of Hypotheses
接下來先介紹一個新名詞：二分類（dichotomy）凰浮。dichotomy就是將空間中的點（例如二維平面）用一條直線分成正類（藍色o）和負類（紅色x）我抠。令H是將平面上的點用直線分開的所有hypothesis h的集合，dichotomy H與hypotheses H的關(guān)系是：hypotheses H是平面上所有直線的集合袜茧，個數(shù)可能是無限個菜拓，而dichotomy H是平面上能將點完全用直線分開的直線種類，它的上界是2N笛厦。接下來纳鼎，我們要做的就是嘗試用dichotomy代替M。
再介紹一個新的名詞：成長函數(shù)（growth function）裳凸，記為mH(H)贱鄙。成長函數(shù)的定義是：對于由N個點組成的不同集合中，某集合對應(yīng)的dichotomy最大姨谷，那么這個dichotomy值就是mH(H)逗宁，它的上界是2N：
成長函數(shù)其實就是我們之前講的effective lines的數(shù)量最大值。根據(jù)成長函數(shù)的定義梦湘，二維平面上瞎颗，mH(H)隨N的變化關(guān)系是：
接下來，我們討論如何計算成長函數(shù)捌议。先看一個簡單情況言缤，一維的Positive Rays：
若有N個點，則整個區(qū)域可分為N+1段禁灼，很容易得到其成長函數(shù)<nobr style="font-family: "WenQuanYi Micro Hei Mono", "WenQuanYi Micro Hei", "Microsoft Yahei Mono", "Microsoft Yahei", sans-serif, Simsun !important; box-sizing: border-box;">mH(N)=N+1</nobr>。注意當(dāng)N很大時轿曙，<nobr style="font-family: "WenQuanYi Micro Hei Mono", "WenQuanYi Micro Hei", "Microsoft Yahei Mono", "Microsoft Yahei", sans-serif, Simsun !important; box-sizing: border-box;">(N+1)<<2N</nobr>弄捕，這是我們希望看到的。
另一種情況是一維的Positive Intervals：
若有N個點导帝，則整個區(qū)域可分為N+1段守谓，很容易得到其成長函數(shù)mH(N)=N+1。注意當(dāng)N很大時您单，(N+1)<<2N斋荞，這是我們希望看到的。
另一種情況是一維的Positive Intervals：
[圖片上傳中...(image.png-a6600a-1518362672206-0)]
它的成長函數(shù)可以由下面推導(dǎo)得出：
這種情況下虐秦，mH(N)=12N2+12N+1<<2N平酿，在N很大的時候，仍然是滿足的悦陋。
再來看這個例子蜈彼，假設(shè)在二維空間里，如果hypothesis是凸多邊形或類圓構(gòu)成的封閉曲線俺驶，如下圖所示幸逆，左邊是convex的，右邊不是convex的。那么还绘，它的成長函數(shù)是多少呢楚昭？
當(dāng)數(shù)據(jù)集D按照如下的凸分布時，我們很容易計算得到它的成長函數(shù)mH=2N拍顷。這種情況下抚太，N個點所有可能的分類情況都能夠被hypotheses set覆蓋，我們把這種情形稱為shattered菇怀。也就是說凭舶，如果能夠找到一個數(shù)據(jù)分布集，hypotheses set對N個輸入所有的分類情況都做得到爱沟，那么它的成長函數(shù)就是2N帅霜。
四、Break Point
上一小節(jié)呼伸，我們介紹了四種不同的成長函數(shù)身冀，分別是：
其中，positive rays和positive intervals的成長函數(shù)都是polynomial的括享，如果用mH代替M的話搂根，這兩種情況是比較好的。而convex sets的成長函數(shù)是exponential的铃辖，即等于M剩愧，并不能保證機器學(xué)習(xí)的可行性。那么娇斩，對于2D perceptrons仁卷，它的成長函數(shù)究竟是polynomial的還是exponential的呢？
對于2D perceptrons犬第，我們之前分析了3個點锦积，可以做出8種所有的dichotomy，而4個點歉嗓，就無法做出所有16個點的dichotomy了丰介。所以，我們就把4稱為2D perceptrons的break point（5鉴分、6哮幢、7等都是break point）。令有k個點志珍，如果k大于等于break point時家浇，它的成長函數(shù)一定小于2的k次方。
根據(jù)break point的定義碴裙，我們知道滿足mH(k)≠2k的k的最小值就是break point钢悲。對于我們之前介紹的四種成長函數(shù)点额，他們的break point分別是：
通過觀察，我們猜測成長函數(shù)可能與break point存在某種關(guān)系：對于convex sets莺琳，沒有break point还棱，它的成長函數(shù)是2的N次方；對于positive rays惭等，break point k=2珍手，它的成長函數(shù)是O(N)；對于positive intervals辞做，break point k=3琳要，它的成長函數(shù)是O(N2)。則根據(jù)這種推論秤茅，我們猜測2D perceptrons稚补，它的成長函數(shù)mH(N)=O(Nk?1) 。如果成立框喳，那么就可以用mH代替M课幕，就滿足了機器能夠?qū)W習(xí)的條件。關(guān)于上述猜測的證明五垮，我們下節(jié)課再詳細介紹乍惊。
五、總結(jié)
本節(jié)課放仗，我們更深入地探討了機器學(xué)習(xí)的可行性润绎。我們把機器學(xué)習(xí)拆分為兩個核心問題：Ein(g)≈Eout(g)和Ein(g)≈0。對于第一個問題诞挨，我們探討了M個hypothesis到底可以劃分為多少種凡橱，也就是成長函數(shù)mH。并引入了break point的概念亭姥，給出了break point的計算方法。下節(jié)課顾稀，我們將詳細論證對于2D perceptrons达罗，它的成長函數(shù)與break point是否存在多項式的關(guān)系，如果是這樣静秆，那么機器學(xué)習(xí)就是可行的粮揉。
注明：
文章中所有的圖片均來自臺灣大學(xué)林軒田《機器學(xué)習(xí)基石》課程。
