此博客停止更新遷移至SnailDove's Blog，查看本文點擊此處

PLA(Perception Learning Algorithm) 適用于二維及高維的線性可劃分問題。問題的答案只有同意或者不同意。

例子

銀行可以根據(jù)顧客的個人信息來判斷是否給顧客發(fā)放信用卡。將顧客抽象為一個向量，包括姓名、年齡、年收入、負債數(shù)等。同時設(shè)定各個屬性所占的權(quán)重向量為，對于正相關(guān)的屬性設(shè)置相對較高的權(quán)重，如年收入，對于負相關(guān)的屬性設(shè)置較低的權(quán)重，如負債數(shù)。表示是否想該用戶發(fā)放了信用卡。通過求和的內(nèi)積減去一個閥值threshold，若為正則同意發(fā)放信用卡，否則不發(fā)放信用卡。我們假設(shè)存在著一個從到的映射，PLA算法就是用來模擬這個映射，使得求出的函數(shù)與盡可能的相似，起碼在已知的數(shù)據(jù)集(即樣本上)上一致。

PLA算法即用來求向量，使得在已知的數(shù)據(jù)中機器做出的判斷與現(xiàn)實數(shù)據(jù)相同。當為二維向量時，相當于在平面上畫出一條直線將所有的點分成兩部分，一部分同意發(fā)送，另一部分的不同意。內(nèi)積可以表示成：

其中，

的值域：，，(?表示樣本中的值，用于輸入到算法進行調(diào)整)

結(jié)合文中例子：?表示在給定的樣本數(shù)據(jù)中，給該用戶發(fā)放了信用卡，表示未發(fā)放。

PLA先假定為向量，然后找到一個不滿足條件的點，調(diào)整的值，依次進行迭代所有樣本數(shù)據(jù)使得最終可以將兩部分完全分開。

W的調(diào)整方案

錯誤驅(qū)動調(diào)整

解釋一下ppt的內(nèi)容，出現(xiàn)錯誤分2種情況：

在給定的已知數(shù)據(jù)中向該用戶發(fā)放了數(shù)據(jù)，即樣本中第個數(shù)據(jù)為，但算法給出的結(jié)果是不發(fā)放（），說明兩個向量的內(nèi)積為負，需要調(diào)整向量使得兩條向量更接近，此時令調(diào)整系數(shù)為樣本的，則調(diào)整后的，的下標表示調(diào)整的次數(shù)，示意圖:

在給定的已知數(shù)據(jù)中向該用戶發(fā)放了數(shù)據(jù)，即樣本中第個數(shù)據(jù)為，但算法給出的結(jié)果是不發(fā)放（），說明兩個向量的內(nèi)積為正，需要調(diào)整向量使得兩條向量更遠離，此時令調(diào)整系數(shù)為樣本的，則調(diào)整后的，示意圖:

注意：2種不同情況的調(diào)整的表達式都一樣

對于線性可分的數(shù)據(jù)集，PLA算法是可收斂的

兩個向量的內(nèi)積增大說明：

兩個向量夾角越小

或者向量的長度增大

老師的ppt上??其中，的值域?

因此?

這說明每次調(diào)整后，向量的長度增加有限。不妨

帶入上一公式得到：

因此最終是收斂的，到此已經(jīng)證明了PLA算法最終可以停止。

算法需要調(diào)整的次數(shù)

由上述過程可以得到以下兩個不等式：

那么來看這個式子：

再根據(jù)余弦值最大為1，可以得到，于是我們得到調(diào)整次數(shù)：.

PLA的優(yōu)缺點

一方面，我事先肯定不知道，另一方面為了應(yīng)對可能出現(xiàn)的噪聲。那么怎么衡量當前得到的直線能夠滿足要求呢？我們只能在每一步的時候都判斷一下，調(diào)整后的是否比上一次的能夠線性可分更多的數(shù)據(jù)，于是有了下面的改進算法Pocket PLA，PocketPLA比PLA在調(diào)整的時候多做一步：判斷當前改正犯的錯是否比之前更小，也就是貪心選擇。

Pocket PLA

參考

HappyAngel

DreamerMonkey

ppt全部來自臺大《機器學(xué)習(xí)基石》課堂

總結(jié)

以上是生活随笔為你收集整理的PLA算法总结及其证明的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。