Lec 2: Learning to Answer Yes/No
上一節(jié)中介紹了機器學習的概念和符號表示剧蹂，這節(jié)主要介紹一個簡單的模型PLA渗柿，這將是學習其他模型的基礎與出發(fā)點。本章符號含義參照上一章肛走。
1焚志、Perceptron Hypothesis Set
在進行“yes／no”分類時，對輸入 x＝(x1,x2,...,xd) 胆筒，計算weighted score邮破，當score>閾值，我們就得出yes（＋1）結果腐泻，score<閾值時决乎，我們得出no（－1）結果。這就是簡單的Perceptron派桩。所以它的output ?y ＝ ｛＋1构诚，－1｝，h可以寫作：
感知機的向量形式：
那這個h（x）長什么樣子铆惑？以最直觀的二維平面為例范嘱，它就是一條直線送膳，將平面分為yes／no兩個部分。
Perceptron是線性分類器 linear（binary）classifiers丑蛤，更高維度時與二維類似叠聋，例如三維時是平面分割空間等等。
2受裹、PLA（perceptron learning algorithm）
（可以在直觀的二維空間進行想象）
H是平面上所有的線碌补，我們需要選擇出 g .那什么樣子的線是理想的線？當然是能正確劃分所有data的線棉饶。但是我們無法得到f厦章，不過我們可以在已有的data上找出像是f的g，即g正確劃分全部已有的data照藻。由于H是無限大的袜啃，找出這樣的g似乎也不太容易，那應該怎么做呢幸缕？PLA群发！先找出一條線g0，然后再去correct它在data上的mistakes发乔，讓線變的越來越好熟妓。如何實現(xiàn)這個idea？
給出一些解釋：
先找一個w0初始化栏尚，然后逐步糾錯滑蚯。
“Cyclic”表示：如果有N個點，就從1到N順序循環(huán)看是否有出錯的點抵栈。當然也可以用其他方式進行循環(huán)告材。
（1）找出一個錯誤的點，即目前得到的“線”給出的結果與yn不等（符號不同）古劲。
（2）更新w向量斥赋。為什么要用這種更新方式？下面介紹
一直到?jīng)]有錯誤产艾。
關于更新w向量：
mistakes有兩種情況：
1）y為＋1疤剑，g(x)為－1
幾何含義為w（紅色）和x的夾角太大了，如何變忻票ぁ隘膘？w和x相加，紫色為糾正后的w杠览。
如下面這個栗子中弯菊，此時在x9上產(chǎn)生了錯誤，x9和w（紅色）夾角是鈍角踱阿，更新w（紫色）后管钳，新的線是下一張圖2钦铁。（注意：幾何代數(shù)知識可知w是線的法向量，即w與線垂直才漆。）
2）y為－1牛曹，g(x)為＋1
幾何含義為w和x的夾角小了，如何變大醇滥？w和x相減黎比。
接上圖1，此時是銳角情況鸳玩。
經(jīng)過不斷的更新糾錯調整焰手，最終可以得到滿意的g。
現(xiàn)在考慮一個問題：PLA一定可以停下來嗎怀喉？即一定可以完美劃分現(xiàn)有data嗎？如果可以停下來（halt）船响，在未來data上g會等于f嗎躬拢？如果不能halt，情況會怎么樣见间？
3聊闯、PLA的理論保障
這節(jié)將會證明在一些情況下，PLA可以停下來米诉。至于在未來data上的表現(xiàn)菱蔬，之后的課會涉及。
沒有錯的時候PLA終止史侣，所以首先拴泌，我們手上的data要可以被一條“線”分開，這樣的D叫做linear separable 惊橱。相反情況叫做not linear separable蚪腐，如圖：
那有了線性可分的D之后PLA是不是就能找到這樣的線了呢？
我們可以看下Wf（理想的w）和Wt＋1（更新后的w）是否在逐漸接近税朴？作內積回季，內積越大越接近。
最后一步中正林，為什么min項>0泡一？很簡單，Wf對應的線是理想中的線觅廓，一定可以正確劃分xn鼻忠，所以y和score相乘一定>=0。不等于0表示所有data離線都有一定的距離杈绸。
這樣我們就得到Wf和Wt+1的內積越來越大粥烁。但是你是否有一個疑惑贤笆？兩個向量內積越來越大也有可能是向量長度在作祟。確實讨阻，那如何證明Wf和Wt+1是在接近呢芥永？這就會用到PLA一個關鍵點：mistake的時候更新w《鬯保可以證明mistake會限制||Wt||平方的增長埋涧，最多增長最長的Xn的平方大小。
其實可以證明經(jīng)過T次糾錯后奇瘦，Wf和WT的單位向量內積會大于根號T乘一個常量棘催，這就表示wf和wt是在靠近（角度越來越小）耳标。并且T有上限醇坝，即有限次更新后可以得到g。具體證明略次坡。
到這可以感受到呼猪，雖然PLA很簡單，其實也蘊含了數(shù)學理論保障砸琅。有沒有覺得很奇妙宋距？后面的model會更奇妙。
4症脂、Pocket
通過上一節(jié)知道谚赎，D線性可分的時候，PLA可以halt诱篷，但是其實我們并不能提前知道D是否可分壶唤。如果D不是線性可分的，該怎么辦棕所？
在機器學習中视粮，事實上我們取得的Data一般都有noise（Noisy Data）。這時橙凳，就算理想的f是一條完美的線蕾殴，我們取得的data也不見得就是線性可分的。在不確定D是否線性可分的情況下岛啸，我們如何得到一條較好的線钓觉？很自然的想法就是，可以試著找到一條犯錯最少的線:
可惜坚踩，這個問題是個NP－h(huán)ard問題荡灾。不過，可以試著去接近這個“good” g，即Pocket算法：
第三步和PLA不一樣批幌，當新的w比手中的wt犯錯少的時候才更新础锐，可以看做是modify PLA，循環(huán)足夠多輪后停止荧缘。其思想很簡單皆警，一直keep得到的最好的w。
