《機器學(xué)習(xí)基石》是國立臺灣大學(xué)林軒田講授的一門課程熏矿，課程的續(xù)集是《機器學(xué)習(xí)技法》已骇。《機器學(xué)習(xí)基石》是網(wǎng)上熱薦的一門機器學(xué)習(xí)課程票编，相關(guān)資源可以在youtube找到褪储，也可在評論區(qū)索要云盤鏈接。本文主要是我學(xué)完一遍基石&技法后的筆記梳理慧域，如果存疑請以原課程講授內(nèi)容為準(zhǔn)鲤竹，歡迎討論~[注]本文僅適用于幫助復(fù)習(xí)，不適用于代替視頻課程昔榴。
基石分為4個部分辛藻，分別為什么時候機器能夠?qū)W為什么機器能夠?qū)W習(xí)，機器是如何學(xué)習(xí)的互订，怎樣讓機器學(xué)得更好吱肌，什么時候機器能夠?qū)W習(xí)？本文主要梳理前兩部分仰禽。
一氮墨、什么時候機器能夠?qū)W習(xí)？
1 關(guān)于機器學(xué)習(xí)
1.1 不嚴(yán)格定義
人通過觀察習(xí)得技能吐葵，機器模仿人规揪，通過觀察(數(shù)據(jù))來獲得技能(某種表現(xiàn)的增進)，例如說温峭，機器通過觀察股票數(shù)據(jù)來提高投資的收益猛铅。
1.2 PK傳統(tǒng)方法
識別一棵樹，傳統(tǒng)方法是找到樹的定義诚镰，但沒人能講出它的具體定義奕坟。而機器學(xué)習(xí)方法則比較簡單祥款，只需喂給機器足量的樹，讓它自己找出其中的規(guī)律學(xué)會識別月杉，這個規(guī)律是抽象的難以描述的刃跛，否則直接用傳統(tǒng)方法就好了。
1.3 機器學(xué)習(xí)的必要條件
有規(guī)則（預(yù)測下一個嬰兒是否在奇數(shù)分鐘哭是沒有意義的）苛萎，但不明確（判斷一張圖里面是不是有一個圓直接用傳統(tǒng)方法來做就可以了）桨昙。有相關(guān)資料（預(yù)測地球會不會在核戰(zhàn)爭中毀滅是不可行的，因為我們沒有”核戰(zhàn)爭-地球是否毀滅”的資料）腌歉。
1.4 機器學(xué)習(xí)的應(yīng)用
食衣住行育樂蛙酪，生活中的方方面面。例如電影推薦系統(tǒng)(詳見技法)翘盖。
1.5 機器學(xué)習(xí)的符號化圖示(5個元素)
1.6?機器學(xué)習(xí)和人工智能、統(tǒng)計學(xué)的關(guān)系
人工智能如”下棋”汰瘫，可以用傳統(tǒng)方法(定義規(guī)則樹)也可以用機器學(xué)習(xí)讓機器自己從資料找到規(guī)律狂打，所以說機器學(xué)習(xí)是人工智能的一種實現(xiàn)方式。
統(tǒng)計學(xué)也是用資料推斷未知混弥，它更注重證明趴乡，為機器學(xué)習(xí)提供了非常多的工具，下面會見到的蝗拿。
2?二元分類
2.1?一種簡單的假說集:Perceptron感知器
2.1.1 Perceptron的向量形式(更簡潔)
2.1.2 Perceptron的圖形表達(dá)
這里取X只有2個維度(x,y)或（x1,x2）晾捏，這樣一來的假說函數(shù)剛好是條直線所以這樣的感知器又稱線性分類器。圖中的點是一個個數(shù)據(jù)點((x1,x2),z)蛹磺，其中y以o或×的形式畫出粟瞬。圖中的底色則表示感知器的預(yù)測(eg.將藍(lán)色區(qū)域的任意一個點代入感知器將得到+1的結(jié)果)，可以看到左圖的分類是存在問題的（部分x在藍(lán)底區(qū)域萤捆，部分o在紅底區(qū)域）裙品，而右圖的感知器則正確。這兩個感知器的w不同俗或，構(gòu)成了假說集中的兩個假說市怎，顯然，我們的演算法應(yīng)該選擇第二個感知器當(dāng)作g辛慰，因為這個g與f長的最像区匠。
2.2 PLA算法(Perceptron Learning Algorithm)
上面我們提到最好的一條線g雏亚，事實上在這張圖上我們能做出無數(shù)條線出來聚凹，我們怎么找到這個最好的線出來呢蹂季？如果最好太難绣的，那我們就用迭代法，不斷地改善使它越來越好從而做到最好戚篙，這個思想產(chǎn)生的就是PLA算法(2步)五鲫。
從2.1我們已經(jīng)知道線的不同是w的不同造成的，PLA算法每次選一個錯誤點岔擂，然后往正確的方向更新w位喂。它的圖像表達(dá)如下所示：
上圖wx=|w||x|cosα，α＞90°乱灵，故x的預(yù)測是-1與y=+1不符塑崖，故修正(將w向x旋轉(zhuǎn)一半)，下圖同理痛倚。
2.1 Cyclic PLA
2.2 PLA真的有效嗎蝉稳？
2.3 PLA能停下來嗎聋呢，最后一定無錯嗎？
如果PLA能夠停下來颠区，那一定存在一個w在D不犯錯，我們稱這樣的D是線性可分的通铲。
那如果D線性可分毕莱，PLA就能夠停下來嗎？
這里設(shè)wf是完美直線的權(quán)重颅夺，即任何一個點都是正確的點(yn與wtxn同號朋截，乘積>0)而任何一個”錯誤”點都是正確點。第二個式子證明了wt在不斷逼近wf吧黄，PLA能夠停下來部服！不過還要排除向量變長的影響。
這里證明了wt的長度最多增長離遠(yuǎn)點最遠(yuǎn)的數(shù)據(jù)點的距離的平方拗慨，不會增長太快廓八。故wt真的在不斷逼近wf，PLA能夠停下來赵抢！事實上剧蹂，wt和wf的距離（兩個矢量之間的角度）的余弦如下所示，隨著T的增大不斷接近1：
關(guān)于constant的計算：
2.4 PLA的優(yōu)缺點
優(yōu)點是容易實現(xiàn)烦却，適用于任意維度宠叼。缺點是我們無法確定D是不是線性可分的，也不確定到底要多久才能停下來其爵，因為ρ的計算依賴于wf冒冬，wf是我們的目標(biāo)權(quán)重這在一開始是不知道多少的伸蚯。
2.5.帶雜訊的資料
左圖藍(lán)底中的x可以認(rèn)為是雜訊，解這類問題最直觀的想法是找一條犯錯最少的線简烤，但這是一個NP-hard問題剂邮，幾乎不可能解出來。
2.6.口袋演算法Pocket Algorithm
3.機器學(xué)習(xí)的種類
二元分類乐埠，多元分類抗斤，回歸(邏輯回歸/線性回歸)，結(jié)構(gòu)化學(xué)習(xí)(輸出句子結(jié)構(gòu)/蛋白質(zhì)結(jié)構(gòu)等)
監(jiān)督丈咐，無監(jiān)督（分群瑞眼，密度估計），半監(jiān)督(少量標(biāo)注)棵逊，增強式(隱式標(biāo)注,獎懲制,eg廣告系統(tǒng))
批學(xué)習(xí)伤疙，線上學(xué)習(xí)(eg.垃圾郵件分類器來一封學(xué)一封)，主動學(xué)習(xí)(主動挑出最具價值的樣本)
具體特征辆影，生特征(簡單的物理意義eg.手寫數(shù)字需轉(zhuǎn)”對稱性-密度”圖)徒像，抽象特征(幾乎沒有物理意義,如”學(xué)號”,需提取出它的偏好等才有意義)
4.機器學(xué)習(xí)的可行性（訓(xùn)練出來的模型真的可以用于預(yù)測嗎？）
根據(jù)Hoeffding不等式蛙讥，隨機獨立大量抽樣的預(yù)測結(jié)果大概差不多是對的(PAC)
實際ML會評估多個假說函數(shù)h
然后從中選一個最好的旁涤。[注]抽樣只負(fù)責(zé)選球，顏色是h染上去的
如果抽樣不符合堅持獨立隨機原則迫像，就有可能人為選到”magic coin”劈愚，那樣無法保證大概差不多是對的(PAC)，這種樣本稱為“BAD”樣本闻妓，可以證明抽到BAD樣本地概率很低菌羽。
5.所以什么時候機器能夠?qū)W習(xí)呢？
只要隨機獨立抽樣由缆，我們就可以選一個在sample犯錯最少的h當(dāng)作g
訓(xùn)練出來的模型真的可以用于預(yù)測注祖，機器學(xué)習(xí)是可行的。
二均唉、為什么機器能夠?qū)W習(xí)氓轰？
1.上式M能bound住嗎？
上述公式中浸卦，如果M是無限大就又不行了署鸡。
假設(shè)M是無限大的，那么，
式子右邊就是無限大靴庆，而左邊是個小于1的概率时捌。這說明右邊明顯過度估計了壞事情發(fā)生的概率，這是因為右邊把所有h都當(dāng)作獨立事件炉抒，而實際上h之間很可能是有交集的奢讨。所以更準(zhǔn)確的做法是用樣本量為N時h的種類數(shù)effective(N)代替h的個數(shù)M。
如上圖焰薄，3個點的二分類問題拿诸，effective(N)最大=8，當(dāng)3點共線的時候則=6塞茅。
記這個最大的數(shù)為成長函數(shù)值mH(N)亩码，即mH(3)=8。對于二維二分類問題mH(N)≤2N
當(dāng)上式不能取”=”時野瘦，我們稱這時的N為break point描沟，打破了mH(N)的指數(shù)增長
對于二維二分類問題，它的最小break point是4鞭光，H無法shatter N=4這種情況：
對于其它H有以下結(jié)論：
對于相同k不同H惰许，記最大的mH(N)為界限函數(shù)B(N,K)席覆，則B(N,K)一定=2N-1
可以得到下表
取其三維，則為
可見無法shatter任何三點汹买，故娜睛，橙區(qū)則無法shatter任何兩點，故卦睹，
化簡可得
可以證明其實是=，如B(5,4)=26=1+3+7+15方库。
所以2D perceptron可以進一步被bound住為B(N,4)结序，即
現(xiàn)在考慮用mH(N)去取代下式中的M
對于左邊，由于Eout有無限種可能纵潦，我們將Eout改寫成對于測試集的E’in徐鹤，
如圖，如果Ein很糟糕邀层，有大于1/2的概率抽到對于Ein很糟糕的E’in
整理并用mH(N)進行放縮返敬，
2N=在D中的N個點+在D’中的N個點
進一步用hoeffding進行放縮則為：
綜上我們得到了VC bound
當(dāng)存在break point時，
可以進一步放縮為
說明M能夠被bound住寥院，只要數(shù)據(jù)量N夠大劲赠，存在break point，我們還是能機器學(xué)習(xí)
2. VC Dimension
將上式k-1定義為dvc，物理意義：整個D中能被H shatter的最大點數(shù)
則有
2.1高維perceptrons的dvc
故高維perceptrons的dvc=d+1
2.2 dvc的形象化解釋(機械學(xué)科中的自由度)
2.3 dvc對模型復(fù)雜度的懲罰
Ω稱為對模型復(fù)雜度的懲罰凛澎，dvc越大霹肝，模型越復(fù)雜，Eout上限越大
dvc應(yīng)該適可而止塑煎，使Eout做到最小
2.4 dvc對樣本(量)復(fù)雜度的影響
導(dǎo)致理論和實際采用的樣本量差距懸殊的原因時VC bound一路的推導(dǎo)都在放縮
dvc越大沫换，需要的樣本量就越大。
綜合2.3 2.4可以知道dvc不是越大越好最铁，不要一昧追求最強的H
3.雜訊與誤差
3.1雜訊
之前證明VC bound時讯赏，同理可證當(dāng)雜訊服從某分布的時候，VC bound仍然有效冷尉，即
所以即使存在某分布的雜訊漱挎，機器仍然能夠?qū)W習(xí)，能夠保證Ein接近Eout
其中P(y|x)稱為”目標(biāo)分布”网严，區(qū)別于沒有雜訊時的f(x)目標(biāo)函數(shù)识樱，
圖中最理想的預(yù)測是o(0/1誤差)，雜訊等級是0.3
3.2誤差
誤差函數(shù)的選擇對演算法A會選出一條怎樣的h作為g很重要
上圖采用0/1誤差時會選最大目標(biāo)分布作為最理想預(yù)測震束，
采用平方誤差則會計算出所有分布的加權(quán)平均值作為最理想預(yù)測
3.2.1誤差成本
對于CIA怜庸，如果錯誤的指紋被識別為正確則要付出1000的成本。
對于加權(quán)分類問題垢村，之前的PLA算法任然有效割疾，因為PLA跑完Ein=0，和成本無關(guān)
而口袋算法需要考慮成本對誤差的影響嘉栓，x的成本是1000=做錯1個x就認(rèn)為做錯1000個x宏榕，故只需將點x復(fù)制1000倍即可，
或者不復(fù)制侵佃，只需令口袋算法的第一步(查改錯)時以1000倍的概率檢查x點麻昼。
3.2.2不平衡樣本
上例樣本極其不平衡，x極少馋辈，o極多抚芦，導(dǎo)致h(x)≡+1被認(rèn)為是個不錯的結(jié)果
對于不平衡樣本，需要更加小心地設(shè)置誤差成本迈螟。
4 所以為什么機器能夠?qū)W習(xí)呢叉抡？
這是因為并不是任意數(shù)量的資料都能被shatter，M能夠被替換掉答毫。無論資料有沒有雜訊褥民，P(BAD)都能被VC bound住。即使資料有雜訊洗搂，我們也能夠用加權(quán)口袋演算法進行分類消返。
