上節(jié)課，我們主要簡(jiǎn)述了機(jī)器學(xué)習(xí)的定義及其重要性，并用流程圖的形式介紹了機(jī)器學(xué)習(xí)的整個(gè)過(guò)程：根據(jù)模型H，使用演算法A，在訓(xùn)練樣本D上進(jìn)行訓(xùn)練，得到最好的h，其對(duì)應(yīng)的g就是我們最后需要的機(jī)器學(xué)習(xí)的模型函數(shù)，一般g接近于目標(biāo)函數(shù)f。本節(jié)課將繼續(xù)深入探討機(jī)器學(xué)習(xí)問(wèn)題，介紹感知機(jī)Perceptron模型，并推導(dǎo)課程的第一個(gè)機(jī)器學(xué)習(xí)算法：Perceptron Learning Algorithm（PLA）。
引入這樣一個(gè)例子：某銀行要根據(jù)用戶的年齡、性別、年收入等情況來(lái)判斷是否給該用戶發(fā)信用卡?，F(xiàn)在有訓(xùn)練樣本D，即之前用戶的信息和是否發(fā)了信用卡。這是一個(gè)典型的機(jī)器學(xué)習(xí)問(wèn)題，我們要根據(jù)D，通過(guò)A，在H中選擇最好的h，得到g，接近目標(biāo)函數(shù)f，也就是根據(jù)先驗(yàn)知識(shí)建立是否給用戶發(fā)信用卡的模型。銀行用這個(gè)模型對(duì)以后用戶進(jìn)行判斷：發(fā)信用卡（+1），不發(fā)信用卡（-1）。
在這個(gè)機(jī)器學(xué)習(xí)的整個(gè)流程中，有一個(gè)部分非常重要：就是模型選擇，即Hypothesis Set。選擇什么樣的模型，很大程度上會(huì)影響機(jī)器學(xué)習(xí)的效果和表現(xiàn)。下面介紹一個(gè)簡(jiǎn)單常用的Hypothesis Set：感知機(jī)（Perceptron）。
還是剛才銀行是否給用戶發(fā)信用卡的例子，我們把用戶的個(gè)人信息作為特征向量x，令總共有d個(gè)特征，每個(gè)特征賦予不同的權(quán)重w，表示該特征對(duì)輸出（是否發(fā)信用卡）的影響有多大。那所有特征的加權(quán)和的值與一個(gè)設(shè)定的閾值threshold進(jìn)行比較：大于這個(gè)閾值，輸出為+1，即發(fā)信用卡；小于這個(gè)閾值，輸出為-1，即不發(fā)信用卡。感知機(jī)模型，就是當(dāng)特征加權(quán)和與閾值的差大于或等于0，則輸出h(x)=1；當(dāng)特征加權(quán)和與閾值的差小于0，則輸出h(x)=-1，而我們的目的就是計(jì)算出所有權(quán)值w和閾值threshold。
為了計(jì)算方便，通常我們將閾值threshold當(dāng)做w0w_0，引入一個(gè)x0=1x_0=1的量與w0w_0相乘，這樣就把threshold也轉(zhuǎn)變成了權(quán)值w0w_0，簡(jiǎn)化了計(jì)算。h(x)的表達(dá)式做如下變換：
為了更清晰地說(shuō)明感知機(jī)模型，我們假設(shè)Perceptrons在二維平面上，即h(x)=sign(w0+w1x1+w2x2)h(x)=sign(w_0+w_1x_1+w_2x_2)。其中，w0+w1x1+w2x2=0w_0+w_1x_1+w_2x_2=0是平面上一條分類直線，直線一側(cè)是正類（+1），直線另一側(cè)是負(fù)類（-1）。權(quán)重w不同，對(duì)應(yīng)于平面上不同的直線。
那么，我們所說(shuō)的Perceptron，在這個(gè)模型上就是一條直線，稱之為linear(binary) classifiers。注意一下，感知器線性分類不限定在二維空間中，在3D中，線性分類用平面表示，在更高維度中，線性分類用超平面表示，即只要是形如wTxw^Tx的線性模型就都屬于linear(binary) classifiers。
同時(shí)，需要注意的是，這里所說(shuō)的linear(binary) classifiers是用簡(jiǎn)單的感知器模型建立的，線性分類問(wèn)題還可以使用logistic regression來(lái)解決，后面將會(huì)介紹。
二、Perceptron Learning Algorithm(PLA)
根據(jù)上一部分的介紹，我們已經(jīng)知道了hypothesis set由許多條直線構(gòu)成。接下來(lái)，我們的目的就是如何設(shè)計(jì)一個(gè)演算法A，來(lái)選擇一個(gè)最好的直線，能將平面上所有的正類和負(fù)類完全分開(kāi)，也就是找到最好的g，使g≈fg\approx f。
如何找到這樣一條最好的直線呢？我們可以使用逐點(diǎn)修正的思想，首先在平面上隨意取一條直線，看看哪些點(diǎn)分類錯(cuò)誤。然后開(kāi)始對(duì)第一個(gè)錯(cuò)誤點(diǎn)就行修正，即變換直線的位置，使這個(gè)錯(cuò)誤點(diǎn)變成分類正確的點(diǎn)。接著，再對(duì)第二個(gè)、第三個(gè)等所有的錯(cuò)誤分類點(diǎn)就行直線糾正，直到所有的點(diǎn)都完全分類正確了，就得到了最好的直線。這種“逐步修正”，就是PLA思想所在。
下面介紹一下PLA是怎么做的。首先隨機(jī)選擇一條直線進(jìn)行分類。然后找到第一個(gè)分類錯(cuò)誤的點(diǎn)，如果這個(gè)點(diǎn)表示正類，被誤分為負(fù)類，即wTtxn(t)<0w_t^Tx_{n(t)}<0，那表示w和x夾角大于90度，其中w是直線的法向量。所以，x被誤分在直線的下側(cè)（相對(duì)于法向量，法向量的方向即為正類所在的一側(cè)），修正的方法就是使w和x夾角小于90度。通常做法是w←w+yx,y=1w\leftarrow w+yx,\ y=1，如圖右上角所示，一次或多次更新后的w+yxw+yx與x夾角小于90度，能保證x位于直線的上側(cè)，則對(duì)誤分為負(fù)類的錯(cuò)誤點(diǎn)完成了直線修正。
同理，如果是誤分為正類的點(diǎn)，即wTtxn(t)>0w_t^Tx_{n(t)}>0，那表示w和x夾角小于90度，其中w是直線的法向量。所以，x被誤分在直線的上側(cè)，修正的方法就是使w和x夾角大于90度。通常做法是w←w+yx,y=?1w\leftarrow w+yx,\ y=-1，如圖右下角所示，一次或多次更新后的w+yxw+yx與x夾角大于90度，能保證x位于直線的下側(cè)，則對(duì)誤分為正類的錯(cuò)誤點(diǎn)也完成了直線修正。
按照這種思想，遇到個(gè)錯(cuò)誤點(diǎn)就進(jìn)行修正，不斷迭代。要注意一點(diǎn)：每次修正直線，可能使之前分類正確的點(diǎn)變成錯(cuò)誤點(diǎn)，這是可能發(fā)生的。但是沒(méi)關(guān)系，不斷迭代，不斷修正，最終會(huì)將所有點(diǎn)完全正確分類（PLA前提是線性可分的）。這種做法的思想是“知錯(cuò)能改”，有句話形容它：“A fault confessed is half redressed.”
實(shí)際操作中，可以一個(gè)點(diǎn)一個(gè)點(diǎn)地遍歷，發(fā)現(xiàn)分類錯(cuò)誤的點(diǎn)就進(jìn)行修正，直到所有點(diǎn)全部分類正確。這種被稱為Cyclic PLA。
下面用圖解的形式來(lái)介紹PLA的修正過(guò)程：
對(duì)PLA，我們需要考慮以下兩個(gè)問(wèn)題：
PLA迭代一定會(huì)停下來(lái)嗎？如果線性不可分怎么辦？
PLA停下來(lái)的時(shí)候，是否能保證f≈gf\approx g？如果沒(méi)有停下來(lái)，是否有f≈gf\approx g？
PLA什么時(shí)候會(huì)停下來(lái)呢？根據(jù)PLA的定義，當(dāng)找到一條直線，能將所有平面上的點(diǎn)都分類正確，那么PLA就停止了。要達(dá)到這個(gè)終止條件，就必須保證D是線性可分（linear separable）。如果是非線性可分的，那么，PLA就不會(huì)停止。
對(duì)于線性可分的情況，如果有這樣一條直線，能夠?qū)⒄惡拓?fù)類完全分開(kāi)，令這時(shí)候的目標(biāo)權(quán)重為wfw_f，則對(duì)每個(gè)點(diǎn)，必然滿足yn=sign(wTfxn)y_n=sign(w_f^Tx_n)，即對(duì)任一點(diǎn)：
PLA會(huì)對(duì)每次錯(cuò)誤的點(diǎn)進(jìn)行修正，更新權(quán)重wt+1w_{t+1}的值，如果wt+1w_{t+1}與wfw_f越來(lái)越接近，數(shù)學(xué)運(yùn)算上就是內(nèi)積越大，那表示wt+1w_{t+1}是在接近目標(biāo)權(quán)重wfw_f，證明PLA是有學(xué)習(xí)效果的。所以，我們來(lái)計(jì)算wt+1w_{t+1}與wfw_f的內(nèi)積：
從推導(dǎo)可以看出，wt+1w_{t+1}與wfw_f的內(nèi)積跟wtw_t與wfw_f的內(nèi)積相比更大了。似乎說(shuō)明了wt+1w_{t+1}更接近wfw_f，但是內(nèi)積更大，可能是向量長(zhǎng)度更大了，不一定是向量間角度更小。所以，下一步，我們還需要證明wt+1w_{t+1}與wtw_t向量長(zhǎng)度的關(guān)系：
wtw_t只會(huì)在分類錯(cuò)誤的情況下更新，最終得到的||w2t+1||||w_{t+1}^2||相比||w2t||||w_{t}^2||的增量值不超過(guò)max||x2n||max||x_n^2||。也就是說(shuō)，wtw_t的增長(zhǎng)被限制了，wt+1w_{t+1}與wtw_t向量長(zhǎng)度不會(huì)差別太大！
如果令初始權(quán)值w0=0w_0=0，那么經(jīng)過(guò)T次錯(cuò)誤修正后，有如下結(jié)論：
下面貼出來(lái)該結(jié)論的具體推導(dǎo)過(guò)程：
上述不等式左邊其實(shí)是wTw_T與wfw_f夾角的余弦值，隨著T增大，該余弦值越來(lái)越接近1，即wTw_T與wfw_f越來(lái)越接近。同時(shí)，需要注意的是，T??√?constant≤1\sqrt T\cdot constant\leq 1，也就是說(shuō)，迭代次數(shù)T是有上界的。根據(jù)以上證明，我們最終得到的結(jié)論是：wt+1w_{t+1}與wfw_f的是隨著迭代次數(shù)增加，逐漸接近的。而且，PLA最終會(huì)停下來(lái)（因?yàn)門有上界），實(shí)現(xiàn)對(duì)線性可分的數(shù)據(jù)集完全分類。
上一部分，我們證明了線性可分的情況下，PLA是可以停下來(lái)并正確分類的，但對(duì)于非線性可分的情況，wfw_f實(shí)際上并不存在，那么之前的推導(dǎo)并不成立，PLA不一定會(huì)停下來(lái)。所以，PLA雖然實(shí)現(xiàn)簡(jiǎn)單，但也有缺點(diǎn)：
對(duì)于非線性可分的情況，我們可以把它當(dāng)成是數(shù)據(jù)集D中摻雜了一下noise，事實(shí)上，大多數(shù)情況下我們遇到的D，都或多或少地?fù)诫s了noise。這時(shí)，機(jī)器學(xué)習(xí)流程是這樣的：
在非線性情況下，我們可以把條件放松，即不苛求每個(gè)點(diǎn)都分類正確，而是容忍有錯(cuò)誤點(diǎn)，取錯(cuò)誤點(diǎn)的個(gè)數(shù)最少時(shí)的權(quán)重w：
事實(shí)證明，上面的解是NP-hard問(wèn)題，難以求解。然而，我們可以對(duì)在線性可分類型中表現(xiàn)很好的PLA做個(gè)修改，把它應(yīng)用到非線性可分類型中，獲得近似最好的g。
修改后的PLA稱為Packet Algorithm。它的算法流程與PLA基本類似，首先初始化權(quán)重w0w_0，計(jì)算出在這條初始化的直線中，分類錯(cuò)誤點(diǎn)的個(gè)數(shù)。然后對(duì)錯(cuò)誤點(diǎn)進(jìn)行修正，更新w，得到一條新的直線，在計(jì)算其對(duì)應(yīng)的分類錯(cuò)誤的點(diǎn)的個(gè)數(shù)，并與之前錯(cuò)誤點(diǎn)個(gè)數(shù)比較，取個(gè)數(shù)較小的直線作為我們當(dāng)前選擇的分類直線。之后，再經(jīng)過(guò)n次迭代，不斷比較當(dāng)前分類錯(cuò)誤點(diǎn)個(gè)數(shù)與之前最少的錯(cuò)誤點(diǎn)個(gè)數(shù)比較，選擇最小的值保存。直到迭代次數(shù)完成后，選取個(gè)數(shù)最少的直線對(duì)應(yīng)的w，即為我們最終想要得到的權(quán)重值。
如何判斷數(shù)據(jù)集D是不是線性可分？對(duì)于二維數(shù)據(jù)來(lái)說(shuō)，通常還是通過(guò)肉眼觀察來(lái)判斷的。一般情況下，Pocket Algorithm要比PLA速度慢一些。
本節(jié)課主要介紹了線性感知機(jī)模型，以及解決這類感知機(jī)分類問(wèn)題的簡(jiǎn)單算法：PLA。我們?cè)敿?xì)證明了對(duì)于線性可分問(wèn)題，PLA可以停下來(lái)并實(shí)現(xiàn)完全正確分類。對(duì)于不是線性可分的問(wèn)題，可以使用PLA的修正算法Pocket Algorithm來(lái)解決。
原文CSDN博客地址：
NTU林軒田機(jī)器學(xué)習(xí)基石課程學(xué)習(xí)筆記2 -- Learning to Answer Yes/No
注明：
文章中所有的圖片均來(lái)自NTU林軒田《機(jī)器學(xué)習(xí)基石》課程。
