Why Can Machines Learning?
按例放上學(xué)習進度:D
前面的4課解決了機器能學(xué)習的條件，即when，
現(xiàn)在開始思考機器能學(xué)習的原理。
一旭从、Recap and preview
首先整理下之前get到的知識:P
目前，我們已經(jīng)知道了场仲，當h的個數(shù)M有限時和悦，且N足夠大，A選中的那個g,會有Ein(g)≈Eout(g)（現(xiàn)成資料D里的g的錯誤率可以推出機器預(yù)測未知的資料的出錯率渠缕，并且很接近哦）鸽素；當A選擇的g,Ein(g)≈0的時候，Eout(g)≈0是PAC的亦鳞。Eout(g)≈0,就是說機器是可以學(xué)習的馍忽。
整個flow里可以理解為train（訓(xùn)練已有資料）和test（用新的資料來測試結(jié)果）兩部分。
learning可以說是在bath的D,監(jiān)督式學(xué)習燕差，二元分類器等條件下遭笋，通過保證Ein(g)≈Eout(g)和Ein(g)≈0，使g≈f （Eout(g)≈0）徒探。
那么learning可以分為2個核心問題:
- Ein(g)≈Eout(g)?
(M finite瓦呼，N large) - Ein(g)≈0?
關(guān)于上面的兩個問題:
- 如果M很小猖辫，從公式可以推出掷空，P[BAD]小，但是扼睬，選擇也變得小了偷溺，那么不一定找得到Ein(g)≈0的優(yōu)秀線
- 如果M很大，選擇多了钱贯，可P[BAD]也大了 :(
emmmm……
所以用合適的M超級重要呢~
前面的討論都是M有限的情況挫掏，如果M無限大呢?
解決方案是，用一個有限的m去替換無限的M：）
所以秩命，現(xiàn)在問題變成：怎么找到一個合適的m來替代M?
二尉共、Effective number of lines
先考慮為什么公式在infinite情況下不可行的褒傅？
每種BAD在獨立來看都是不一樣的，但是union bound 后就會有重疊部分袄友，疊加infinite個獨立p后變得無限大殿托，此時就變得無意義了。
BAD重疊可以理解為h1≈h2
總之剧蚣，B1,B2,B3……這些BAD其實是重疊了的支竹，但是union bound公式是沒有考慮重疊的，把每個BAD當成獨立的來計算鸠按，造成了無限大的上限礼搁。所以此時infinite個h是無法計算的。
好嘛目尖，既然是因為重疊了才不可計算馒吴，那就想辦法找出重疊部分:D
先考慮這樣一個問題:
如果平面上只有一個x,那么會有多少條h呢？
顯然是可以分為兩種瑟曲，一種是把x劃分為+1那邊的饮戳，一種是把x劃分到-1那邊的。
那么洞拨，有2個點的時候呢扯罐？
可以根據(jù)把x1,x2劃分到那一邊算出有4種h。
那么3個點的時候呢扣甲？
對的篮赢，8種。
這時候你有一個猜想琉挖，哇启泣，好像是2^n呢……
然而，如果3個點是在一條線上的呢?
emmm……
對的示辈，有的情況無法用一條直線劃分寥茫，所以這時候只有6條h.
當有4個點時，也會出現(xiàn)無法劃分的時候矾麻。
總的來說纱耻，結(jié)論如下:
我們把這種有效的條數(shù)稱為effective number of lines
從1,2,3,4個x可以發(fā)現(xiàn)它們的h總是有個上限的,沒有重疊部分的，最大不會超過2N(每個點的情況都是兩種险耀，所以最多不會超過2N)弄喘。所以,D里面的N個點的最大不會超過2^N條h。
那么是不是可以用effective（N）來替代那個無限的M呢甩牺？
三蘑志、Effective number of Hypotheses
現(xiàn)在引入一個概念dichotomy:
把點x,劃分到+1,-1的集合。
hypotheses H 與dichotomies H(x1,x2,...,Xn)的區(qū)別如圖。
前面說到effective(N)的概念急但，effective（N）正是dichotomies H(x1,x2,...,Xn)的h的個數(shù)呢澎媒。
既然dichotomies H(x1,x2,...,Xn)是沒有重疊部分的，那么可以作為替換M的候選了波桩。
|H(x1,x2,...,Xn)|是依賴x的(比如上面提到的3個x的時候戒努，擺放不同會有不同的結(jié)果，6和8）镐躲，現(xiàn)在我們除去對x的依賴储玫，只討論|H(x1,x2,...,Xn)|的max，把這稱為成長函數(shù)(Growth Function)匀油。
那么缘缚，怎么計算成長函數(shù)呢？
第一種情況:
把直線上一部分劃分為+1,像射線一樣敌蚜，N個點可以把一條線劃分為N+1個塊桥滨，這時有N+1條線可以劃分。
第二種情況:
一部分劃分為+1弛车。
此時N個點還是把線分為N+1塊齐媒，既然是取部分劃分為+1,那么取兩個塊作為線的端點，所以一共Nx(N+1)/2種纷跛，還有一種是全部取為+1喻括，所以
N(N+1)/2+1.
第三種情況:
凸的部分劃分為+1。
此時可以凸邊形做出來 ,即連點贫奠，突邊形外內(nèi)的都是里的都是+1,其他為-1.
所有點都可以這種方法劃分出來唬血，所以是2^N*.
總結(jié)：
四、Break point
通過得到的式子可以看出唤崭，當成長函數(shù)為多項式時效果比較好拷恨，指數(shù)時效果不好。
在二維下谢肾，
3個x時存在shatter(原意打碎腕侄，破壞，在這里可以理解為全部命中芦疏，比如3個x,有8種可能冕杠，存在8種都可行的狀態(tài)，即命中）,這時有6和8的情況酸茴，所以是'存在'分预。
4個x時不存在shatter,因為最多只有14種。
可以推出薪捍，自4以后都是不存在shatter的噪舀。
假設(shè)k為inputs的個數(shù)魁淳，
當k個inputs讓H不存在shatter時，稱k為break point.
在二維下与倡，4就是break point.
k+1,k+2,k+3……也是break point
五、Summary
總結(jié):
- 復(fù)習之前4個課程的知識
- 當M無限大時昆稿，因為union bound是把每個BAD加起來纺座，沒有考慮除去重疊部分造成了無限大，如果用eddective（N）替代M也許能解決這個問題
- 介紹了4種成長函數(shù)溉潭，其中多項式的替換效果比較好
- 介紹了break point , 比如4
- 總的來說解決了M 無限時的情況净响，大題的思路是找出一個有限的且有效的m去替代M,最后，我們找到了多項式的成長函數(shù)來替換
以上:D
注明:以上圖片都來自Cousera臺大林軒田老師的《機器學(xué)習基石》哦 QwQ
