Lec 2: Learning to Answer Yes/No
上一節(jié)中介紹了機(jī)器學(xué)習(xí)的概念和符號(hào)表示，這節(jié)主要介紹一個(gè)簡(jiǎn)單的模型PLA，這將是學(xué)習(xí)其他模型的基礎(chǔ)與出發(fā)點(diǎn)。本章符號(hào)含義參照上一章。
1、Perceptron Hypothesis Set
在進(jìn)行“yes／no”分類時(shí)，對(duì)輸入 x＝(x1,x2,...,xd) ，計(jì)算weighted score，當(dāng)score>閾值，我們就得出yes（＋1）結(jié)果，score<閾值時(shí)，我們得出no（－1）結(jié)果。這就是簡(jiǎn)單的Perceptron。所以它的output ?y ＝ ｛＋1，－1｝，h可以寫作：
感知機(jī)的向量形式：
那這個(gè)h（x）長(zhǎng)什么樣子？以最直觀的二維平面為例，它就是一條直線，將平面分為yes／no兩個(gè)部分。
Perceptron是線性分類器 linear（binary）classifiers，更高維度時(shí)與二維類似，例如三維時(shí)是平面分割空間等等。
2、PLA（perceptron learning algorithm）
（可以在直觀的二維空間進(jìn)行想象）
H是平面上所有的線，我們需要選擇出 g .那什么樣子的線是理想的線？當(dāng)然是能正確劃分所有data的線。但是我們無法得到f，不過我們可以在已有的data上找出像是f的g，即g正確劃分全部已有的data。由于H是無限大的，找出這樣的g似乎也不太容易，那應(yīng)該怎么做呢？PLA！先找出一條線g0，然后再去correct它在data上的mistakes，讓線變的越來越好。如何實(shí)現(xiàn)這個(gè)idea？
給出一些解釋：
先找一個(gè)w0初始化，然后逐步糾錯(cuò)。
“Cyclic”表示：如果有N個(gè)點(diǎn)，就從1到N順序循環(huán)看是否有出錯(cuò)的點(diǎn)。當(dāng)然也可以用其他方式進(jìn)行循環(huán)。
（1）找出一個(gè)錯(cuò)誤的點(diǎn)，即目前得到的“線”給出的結(jié)果與yn不等（符號(hào)不同）。
（2）更新w向量。為什么要用這種更新方式？下面介紹
一直到?jīng)]有錯(cuò)誤。
關(guān)于更新w向量：
mistakes有兩種情況：
1）y為＋1，g(x)為－1
幾何含義為w（紅色）和x的夾角太大了，如何變小？w和x相加，紫色為糾正后的w。
如下面這個(gè)栗子中，此時(shí)在x9上產(chǎn)生了錯(cuò)誤，x9和w（紅色）夾角是鈍角，更新w（紫色）后，新的線是下一張圖2。（注意：幾何代數(shù)知識(shí)可知w是線的法向量，即w與線垂直。）
2）y為－1，g(x)為＋1
幾何含義為w和x的夾角小了，如何變大？w和x相減。
接上圖1，此時(shí)是銳角情況。
經(jīng)過不斷的更新糾錯(cuò)調(diào)整，最終可以得到滿意的g。
現(xiàn)在考慮一個(gè)問題：PLA一定可以停下來嗎？即一定可以完美劃分現(xiàn)有data嗎？如果可以停下來（halt），在未來data上g會(huì)等于f嗎？如果不能halt，情況會(huì)怎么樣？
3、PLA的理論保障
這節(jié)將會(huì)證明在一些情況下，PLA可以停下來。至于在未來data上的表現(xiàn)，之后的課會(huì)涉及。
沒有錯(cuò)的時(shí)候PLA終止，所以首先，我們手上的data要可以被一條“線”分開，這樣的D叫做linear separable 。相反情況叫做not linear separable，如圖：
那有了線性可分的D之后PLA是不是就能找到這樣的線了呢？
我們可以看下Wf（理想的w）和Wt＋1（更新后的w）是否在逐漸接近？作內(nèi)積，內(nèi)積越大越接近。
最后一步中，為什么min項(xiàng)>0？很簡(jiǎn)單，Wf對(duì)應(yīng)的線是理想中的線，一定可以正確劃分xn，所以y和score相乘一定>=0。不等于0表示所有data離線都有一定的距離。
這樣我們就得到Wf和Wt+1的內(nèi)積越來越大。但是你是否有一個(gè)疑惑？?jī)蓚€(gè)向量?jī)?nèi)積越來越大也有可能是向量長(zhǎng)度在作祟。確實(shí)，那如何證明Wf和Wt+1是在接近呢？這就會(huì)用到PLA一個(gè)關(guān)鍵點(diǎn)：mistake的時(shí)候更新w?？梢宰C明mistake會(huì)限制||Wt||平方的增長(zhǎng)，最多增長(zhǎng)最長(zhǎng)的Xn的平方大小。
其實(shí)可以證明經(jīng)過T次糾錯(cuò)后，Wf和WT的單位向量?jī)?nèi)積會(huì)大于根號(hào)T乘一個(gè)常量，這就表示wf和wt是在靠近（角度越來越?。２⑶襎有上限，即有限次更新后可以得到g。具體證明略。
到這可以感受到，雖然PLA很簡(jiǎn)單，其實(shí)也蘊(yùn)含了數(shù)學(xué)理論保障。有沒有覺得很奇妙？后面的model會(huì)更奇妙。
4、Pocket
通過上一節(jié)知道，D線性可分的時(shí)候，PLA可以halt，但是其實(shí)我們并不能提前知道D是否可分。如果D不是線性可分的，該怎么辦？
在機(jī)器學(xué)習(xí)中，事實(shí)上我們?nèi)〉玫腄ata一般都有noise（Noisy Data）。這時(shí)，就算理想的f是一條完美的線，我們?nèi)〉玫膁ata也不見得就是線性可分的。在不確定D是否線性可分的情況下，我們?nèi)绾蔚玫揭粭l較好的線？很自然的想法就是，可以試著找到一條犯錯(cuò)最少的線:
可惜，這個(gè)問題是個(gè)NP－h(huán)ard問題。不過，可以試著去接近這個(gè)“good” g，即Pocket算法：
第三步和PLA不一樣，當(dāng)新的w比手中的wt犯錯(cuò)少的時(shí)候才更新，可以看做是modify PLA，循環(huán)足夠多輪后停止。其思想很簡(jiǎn)單，一直keep得到的最好的w。
