上節(jié)課沈撞，我們主要簡述了機器學(xué)習(xí)的定義及其重要性蜈垮，并用流程圖的形式介紹了機器學(xué)習(xí)的整個過程：根據(jù)模型H，使用演算法A菊碟，在訓(xùn)練樣本D上進行訓(xùn)練节芥，得到最好的h，其對應(yīng)的g就是我們最后需要的機器學(xué)習(xí)的模型函數(shù)逆害，一般g接近于目標函數(shù)f头镊。本節(jié)課將繼續(xù)深入探討機器學(xué)習(xí)問題，介紹感知機Perceptron模型魄幕，并推導(dǎo)課程的第一個機器學(xué)習(xí)算法：Perceptron Learning Algorithm（PLA）相艇。
引入這樣一個例子：某銀行要根據(jù)用戶的年齡纯陨、性別坛芽、年收入等情況來判斷是否給該用戶發(fā)信用卡×舸ⅲ現(xiàn)在有訓(xùn)練樣本D，即之前用戶的信息和是否發(fā)了信用卡咙轩。這是一個典型的機器學(xué)習(xí)問題获讳，我們要根據(jù)D，通過A活喊，在H中選擇最好的h丐膝，得到g，接近目標函數(shù)f胧弛，也就是根據(jù)先驗知識建立是否給用戶發(fā)信用卡的模型尤误。銀行用這個模型對以后用戶進行判斷：發(fā)信用卡（+1），不發(fā)信用卡（-1）结缚。
在這個機器學(xué)習(xí)的整個流程中损晤，有一個部分非常重要：就是模型選擇，即Hypothesis Set红竭。選擇什么樣的模型尤勋，很大程度上會影響機器學(xué)習(xí)的效果和表現(xiàn)。下面介紹一個簡單常用的Hypothesis Set：感知機（Perceptron）茵宪。
還是剛才銀行是否給用戶發(fā)信用卡的例子最冰，我們把用戶的個人信息作為特征向量x，令總共有d個特征稀火，每個特征賦予不同的權(quán)重w暖哨，表示該特征對輸出（是否發(fā)信用卡）的影響有多大。那所有特征的加權(quán)和的值與一個設(shè)定的閾值threshold進行比較：大于這個閾值凰狞，輸出為+1篇裁，即發(fā)信用卡；小于這個閾值赡若，輸出為-1达布，即不發(fā)信用卡。感知機模型逾冬，就是當特征加權(quán)和與閾值的差大于或等于0黍聂，則輸出h(x)=1；當特征加權(quán)和與閾值的差小于0身腻，則輸出h(x)=-1产还，而我們的目的就是計算出所有權(quán)值w和閾值threshold。
為了計算方便嘀趟，通常我們將閾值threshold當做w0w_0雕沉，引入一個x0=1x_0=1的量與w0w_0相乘，這樣就把threshold也轉(zhuǎn)變成了權(quán)值w0w_0去件，簡化了計算坡椒。h(x)的表達式做如下變換：
為了更清晰地說明感知機模型，我們假設(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è)是負類（-1）。權(quán)重w不同授霸，對應(yīng)于平面上不同的直線巡验。
那么，我們所說的Perceptron碘耳，在這個模型上就是一條直線显设，稱之為linear(binary) classifiers。注意一下辛辨，感知器線性分類不限定在二維空間中捕捂，在3D中，線性分類用平面表示斗搞，在更高維度中指攒，線性分類用超平面表示，即只要是形如wTxw^Tx的線性模型就都屬于linear(binary) classifiers僻焚。
同時允悦，需要注意的是，這里所說的linear(binary) classifiers是用簡單的感知器模型建立的虑啤，線性分類問題還可以使用logistic regression來解決隙弛，后面將會介紹。
二咐旧、Perceptron Learning Algorithm(PLA)
根據(jù)上一部分的介紹驶鹉，我們已經(jīng)知道了hypothesis set由許多條直線構(gòu)成。接下來铣墨，我們的目的就是如何設(shè)計一個演算法A室埋，來選擇一個最好的直線，能將平面上所有的正類和負類完全分開伊约，也就是找到最好的g姚淆，使g≈fg\approx f。
如何找到這樣一條最好的直線呢屡律？我們可以使用逐點修正的思想腌逢，首先在平面上隨意取一條直線，看看哪些點分類錯誤超埋。然后開始對第一個錯誤點就行修正搏讶，即變換直線的位置佳鳖，使這個錯誤點變成分類正確的點。接著媒惕，再對第二個系吩、第三個等所有的錯誤分類點就行直線糾正，直到所有的點都完全分類正確了妒蔚，就得到了最好的直線穿挨。這種“逐步修正”，就是PLA思想所在肴盏。
下面介紹一下PLA是怎么做的科盛。首先隨機選擇一條直線進行分類。然后找到第一個分類錯誤的點菜皂，如果這個點表示正類贞绵，被誤分為負類，即wTtxn(t)<0w_t^Tx_{n(t)}<0幌墓，那表示w和x夾角大于90度但壮，其中w是直線的法向量。所以常侣，x被誤分在直線的下側(cè)（相對于法向量蜡饵，法向量的方向即為正類所在的一側(cè)），修正的方法就是使w和x夾角小于90度胳施。通常做法是w←w+yx,y=1w\leftarrow w+yx,\ y=1舞肆，如圖右上角所示，一次或多次更新后的w+yxw+yx與x夾角小于90度椿胯，能保證x位于直線的上側(cè)筷登，則對誤分為負類的錯誤點完成了直線修正。
同理哩盲，如果是誤分為正類的點前方，即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è)遥缕，則對誤分為正類的錯誤點也完成了直線修正。
按照這種思想宝穗，遇到個錯誤點就進行修正户秤，不斷迭代。要注意一點：每次修正直線逮矛，可能使之前分類正確的點變成錯誤點鸡号，這是可能發(fā)生的。但是沒關(guān)系须鼎，不斷迭代鲸伴，不斷修正，最終會將所有點完全正確分類（PLA前提是線性可分的）晋控。這種做法的思想是“知錯能改”汞窗，有句話形容它：“A fault confessed is half redressed.”
實際操作中，可以一個點一個點地遍歷赡译，發(fā)現(xiàn)分類錯誤的點就進行修正仲吏，直到所有點全部分類正確。這種被稱為Cyclic PLA蝌焚。
下面用圖解的形式來介紹PLA的修正過程：
對PLA裹唆，我們需要考慮以下兩個問題：
PLA迭代一定會停下來嗎？如果線性不可分怎么辦只洒？
PLA停下來的時候许帐，是否能保證f≈gf\approx g？如果沒有停下來毕谴，是否有f≈gf\approx g成畦？
PLA什么時候會停下來呢析珊？根據(jù)PLA的定義羡鸥，當找到一條直線，能將所有平面上的點都分類正確忠寻，那么PLA就停止了惧浴。要達到這個終止條件，就必須保證D是線性可分（linear separable）奕剃。如果是非線性可分的衷旅，那么捐腿，PLA就不會停止。
對于線性可分的情況柿顶，如果有這樣一條直線茄袖，能夠?qū)⒄惡拓擃愅耆珠_，令這時候的目標權(quán)重為wfw_f嘁锯，則對每個點宪祥，必然滿足yn=sign(wTfxn)y_n=sign(w_f^Tx_n)，即對任一點：
PLA會對每次錯誤的點進行修正家乘，更新權(quán)重wt+1w_{t+1}的值蝗羊，如果wt+1w_{t+1}與wfw_f越來越接近，數(shù)學(xué)運算上就是內(nèi)積越大仁锯，那表示wt+1w_{t+1}是在接近目標權(quán)重wfw_f耀找，證明PLA是有學(xué)習(xí)效果的。所以业崖，我們來計算wt+1w_{t+1}與wfw_f的內(nèi)積：
從推導(dǎo)可以看出野芒，wt+1w_{t+1}與wfw_f的內(nèi)積跟wtw_t與wfw_f的內(nèi)積相比更大了。似乎說明了wt+1w_{t+1}更接近wfw_f双炕，但是內(nèi)積更大狞悲，可能是向量長度更大了，不一定是向量間角度更小雄家。所以效诅，下一步，我們還需要證明wt+1w_{t+1}與wtw_t向量長度的關(guān)系：
wtw_t只會在分類錯誤的情況下更新趟济，最終得到的||w2t+1||||w_{t+1}^2||相比||w2t||||w_{t}^2||的增量值不超過max||x2n||max||x_n^2||乱投。也就是說，wtw_t的增長被限制了顷编，wt+1w_{t+1}與wtw_t向量長度不會差別太大戚炫！
如果令初始權(quán)值w0=0w_0=0，那么經(jīng)過T次錯誤修正后媳纬，有如下結(jié)論：
下面貼出來該結(jié)論的具體推導(dǎo)過程：
上述不等式左邊其實是wTw_T與wfw_f夾角的余弦值双肤，隨著T增大，該余弦值越來越接近1钮惠，即wTw_T與wfw_f越來越接近茅糜。同時，需要注意的是素挽，T??√?constant≤1\sqrt T\cdot constant\leq 1蔑赘，也就是說，迭代次數(shù)T是有上界的。根據(jù)以上證明缩赛，我們最終得到的結(jié)論是：wt+1w_{t+1}與wfw_f的是隨著迭代次數(shù)增加耙箍，逐漸接近的。而且酥馍，PLA最終會停下來（因為T有上界）辩昆，實現(xiàn)對線性可分的數(shù)據(jù)集完全分類。
上一部分汁针，我們證明了線性可分的情況下，PLA是可以停下來并正確分類的砚尽，但對于非線性可分的情況扇丛，wfw_f實際上并不存在，那么之前的推導(dǎo)并不成立尉辑，PLA不一定會停下來。所以较屿，PLA雖然實現(xiàn)簡單隧魄，但也有缺點：
對于非線性可分的情況，我們可以把它當成是數(shù)據(jù)集D中摻雜了一下noise隘蝎，事實上购啄，大多數(shù)情況下我們遇到的D，都或多或少地摻雜了noise嘱么。這時狮含，機器學(xué)習(xí)流程是這樣的：
在非線性情況下，我們可以把條件放松曼振，即不苛求每個點都分類正確几迄，而是容忍有錯誤點，取錯誤點的個數(shù)最少時的權(quán)重w：
事實證明冰评，上面的解是NP-hard問題映胁，難以求解。然而甲雅，我們可以對在線性可分類型中表現(xiàn)很好的PLA做個修改解孙，把它應(yīng)用到非線性可分類型中，獲得近似最好的g抛人。
修改后的PLA稱為Packet Algorithm弛姜。它的算法流程與PLA基本類似，首先初始化權(quán)重w0w_0妖枚，計算出在這條初始化的直線中廷臼，分類錯誤點的個數(shù)。然后對錯誤點進行修正，更新w中剩，得到一條新的直線忌穿，在計算其對應(yīng)的分類錯誤的點的個數(shù)，并與之前錯誤點個數(shù)比較结啼，取個數(shù)較小的直線作為我們當前選擇的分類直線掠剑。之后，再經(jīng)過n次迭代郊愧，不斷比較當前分類錯誤點個數(shù)與之前最少的錯誤點個數(shù)比較朴译，選擇最小的值保存。直到迭代次數(shù)完成后属铁，選取個數(shù)最少的直線對應(yīng)的w眠寿，即為我們最終想要得到的權(quán)重值。
如何判斷數(shù)據(jù)集D是不是線性可分焦蘑？對于二維數(shù)據(jù)來說盯拱，通常還是通過肉眼觀察來判斷的。一般情況下例嘱，Pocket Algorithm要比PLA速度慢一些狡逢。
本節(jié)課主要介紹了線性感知機模型拼卵，以及解決這類感知機分類問題的簡單算法：PLA奢浑。我們詳細證明了對于線性可分問題，PLA可以停下來并實現(xiàn)完全正確分類腋腮。對于不是線性可分的問題雀彼，可以使用PLA的修正算法Pocket Algorithm來解決。
原文CSDN博客地址：
NTU林軒田機器學(xué)習(xí)基石課程學(xué)習(xí)筆記2 -- Learning to Answer Yes/No
注明：
文章中所有的圖片均來自NTU林軒田《機器學(xué)習(xí)基石》課程即寡。
