我們有一堆數據，默認他們是線性可分的。?
定義f為這個數據分割線的最優解，但是我們不知道他的值。?
我們僅有一個函數集H，這個函數一般是無窮大的。我們的目的就是從H中找出一條線g來盡可能的接近f。但是，我剛剛說了，H內的函數一般是無窮多的，我們不可能把H中的函數一 一 比較，得到最好的分割線g吧！！！

不過偉大的科學家就說，我們的目的不就是找出一條線把這些數據都分開嗎！！那我隨機的初始化一條分割線?g0,讓他一 一和數據點進行比較（數據總該是有限個的吧）, 如果 某一個數據點劃分對了，那這條線就不動，繼續比較下一個點。如果錯了，那就調整 這條線，讓他能把這個點分對。以此下去，直到我們發現所有的點都分隔對了為止。。。

那么問題就來了，我們怎么調整這條分隔線呢？？？?
首先要明確，只有當分類出錯誤的時候，才對分割線進行調整。?
假設我們遇到的數據點(xn,yn)是我們第t次分類錯誤。那么就有

當yn=+1?時，則我們的錯誤結果為wTxn=wt?→?xn?→=||w||?||xn||?cosΘ<0，即cosΘ<0?則Θ太大,為了能過糾正錯誤，決定減小Θ，就讓w→t+1=w→t+x→?
即?
紫色的就是更改后的wt+1

同理?
當yn=?1時，則我們的錯誤結果為wTxn=wt?→?xn?→=||w||?||xn||?cosΘ>0，即cosΘ>0?則Θ太小,為了能過糾正錯誤，決定增大Θ，就讓w→t+1=w→t?x→?
即?
紫色的就是更改后的wt+1

綜上所述，當分割線遇到點(xn,yn)時，如果分割正確，那么wt就不變，如果分割錯誤，那么就令

注意w是分割線wTx=0的法線，也就是說分割線的方向是與w的方向垂直的。。。

這個想法是挺好的，那么問題是，用這種方法到底行不行得通呢？？？現在，我們就來驗證這個算法的正確性！！！?
這種方法到底行不行得通，其實就是說這個算法到底能不能找到正確區分所有點的線。即這個算法到底能不能收斂？（收斂就是能停下來，算法只有找到了滿足要求的線才停下來，所以說法不同，但意思是一樣的）?
證明：?
首先有兩個前提：?
前提1：數據本就是可以線性可分的。（如果數據不是線性可分的話，那不管我們怎么找都找不到那條線）?
前提2：我們僅僅是遇到分錯的點時，才改變wt，遇到分對的點wt不變。

根據前提1，說明最終的線一定存在。?
假設wf是我們要的線，則有??
當線wTtx=0遇到(xn,yn)發生錯誤時，則更新wt+1,即?
遂有?
?
則?

根據前提2，有?
?
又有

則?

判斷w_t，wf是否相近，只需他們的Θ盡可能為0

我們初始化w0=0，則可以怎么得，在T次誤差矯正后，有?
?
所以，最終得到

?
即cosΘ>=T??√.Cconstant,即隨著T逐漸增大，cosΘ也會逐漸增大，那么Θ會逐漸減小到0，所以wt是越來越接近wf?又cosΘ<=1，所以?wt一定收斂。

這個算法最大的缺點就是假設數據點是線性可分的。問題是，我們并不知道數據到底是不是線性可分的！！如果不是，也就是說最終根本沒有上面的wf，即沒有一條不犯錯誤的線，那么以上的推論都是“白搭”！！！

那怎么辦？？？有個想法是，我們能不能把找出一條犯錯誤最少的線呢？？？？即?
其實，從實際意義上，是不能的。這是一個著名的NP hard 問題！！！因為線有無窮多個啊！！！

偉大的科學家又提出一條算法，來解決這個問題——-口袋算法?
口袋算法基于貪心的思想。他總是讓遇到的最好的線拿在自己的手上。。。?
就是我首先手里有一條分割線wt，發現他在數據點(xn,yn)上面犯了錯誤，那我們就糾正這個分割線得到wt+1,我們然后讓wt與wt+1遍歷所有的數據，看哪條線犯的錯誤少。如果wt+1犯的錯誤少，那么就讓wt+1替代wt，否則wt不變。?
那怎樣讓算法停下來呢？？——–我們就 自己規定迭代的次數?
由于口袋算法得到的線越來越好（PLA就不一定了，PLA是最終結果最好，其他情況就說不準了），所以我們就 自己規定迭代的次數 。?

最后一個問題，如果數據本就是線性可分，那么我們用 pocket algorithm 和用 PLA，那個更好？？？?
答案是PLA更好。先不說PLA可以找到最好的那條線。單從效率上來說，PLA也更好些。最主要的原因是，pocket algorithm 每次比較的時候，都要遍歷所有的數據點，且兩個算法都要遍歷一遍，才會決定那個算法好，而這還是比較一次，如果我們讓他迭代500次的，那就麻煩了！！！但是，所有前提是，數據是線性可分的。如果線性不可分，只能用pocket algorithm，因為PLA根本不會停下來（而且PLA的wt也不是每更改一次效果就會比之前的好）！！

總結一下，這篇博客講了些什么：?
1. 先 講解了 PLA算法?
2. 然后 證明PLA算法在數據是線性可分的情況下的正確性?
方法： 余弦定理+公式wt+1=wt+yn?xn?
3. 討論在線性不可分情況下的 口袋算法pocket algorithm?
4. 簡單的討論了 PLA和pocket algorithm的優缺點?

5. 那么你能否將這些內容復述一遍 -_-

來自 丁磊_ml博客 網址為 blog.csdn.net/MosBest

總結

以上是生活随笔為你收集整理的分类系列之感知器学习算法PLA 和 口袋算法Pocket Algorithm的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。