感知器PLA是一種最簡單，最基本的線性分類算法（二分類）。其前提是數據本身是線性可分的。

模型可以定義為，sign函數是階躍函數，閾值決定取0或1。模型選擇的策略，利用經驗損失函數衡量算法性能，由于該算法最后得到一個分離超平面，所以損失函數可以定義為，由于對于誤分類點，yi和wx+b的正負屬性相反，所以，所以加一個符號，來表征樣例點與超平面的距離。

算法選擇，最終的目標是求損失函數的最小值，利用機器學習中最常用的梯度下降GD或者隨機梯度下降SGD來求解。

SGD算法的流程如下：輸入訓練集和學習率

1、初始化w0，b0，確定初始化超平面，并確定各樣例點是否正確分類（利用yi和wx+b的正負性關系）；

2、隨機在誤分類點中選擇一個樣例點，計算L關于w和b在該點處的梯度值；

3、更新w，b，按照如下方向；

4、迭代運行，直到滿足停止條件（限定迭代次數或者定義可接受誤差最大值）；

如上所述，初值的選擇，誤分類點的選擇順序都影響算法的性能和運行時間。PLA是一個很基本的算法，應用場景很受限，只是作為一個引子來了解機器學習，后面有很多高級的算法，比如SVM和MLP，以及大熱的deep learning，都是感知器的擴展。

對于PLA，還有一個對偶問題，此處，簡單介紹一下對偶問題相關的知識。

對偶問題：

每一個線性規劃問題，我們稱之為原始問題，都有一個與之對應的線性規劃問題我們稱之為對偶問題。原始問題與對偶問題的解是對應的，得出一個問題的解，另一個問題的解也就得到了。并且原始問題與對偶問題在形式上存在很簡單的對應關系：目標函數對原始問題是極大化，對對偶問題則是極小化。

原始問題目標函數中的收益系數（優化函數中變量前面的系數）是對偶問題約束不等式中的右端常數，而原始問題約束不等式中的右端常數則是對偶問題中目標函數的收益系數；原始問題和對偶問題的約束不等式的符號方向相反；原始問題約束不等式系數矩陣轉置后即為對偶問題的約束不等式的系數矩陣；原始問題的約束方程數對應于對偶問題的變量數，而原始問題的變量數對應于對偶問題的約束方程數；對偶問題的對偶問題是原始問題。

總之他們存在著簡單的矩陣轉置，系數變換的關系。當問題通過對偶變換后經常會呈現許多便利，如約束條件變少、優化變量變少，使得問題的求解證明更加方便計算可能更加方便。

對偶問題中，此處將w和b看成是x和y的函數，w和b可表示為，ni表示更新次數，模型，算法流程如下：輸入訓練集，學習率

1、；

2、隨機選取誤分類點對，并更新計算，具體更新，依據上面的表達式；

3、直至沒有誤分類點，停止計算，返回相應的參數；

原始問題和對偶問題都是嚴格可收斂的，在線性可分的條件下，一定可以停止算法運行，會達到結果，存在多個解。

如果線性不可分，可以利用口袋算法，每次迭代更新錯誤最小的權值，且規定迭代次數。口袋算法基于貪心的思想。他總是讓遇到的最好的線拿在自己的手上。 就是我首先手里有一條分割線wt，發現他在數據點（xn，yn）上面犯了錯誤，那我們就糾正這個分割線得到wt+1，我們然后讓wt與wt+1遍歷所有的數據，看哪條線犯的錯誤少。

如果wt+1犯的錯誤少，那么就讓wt+1替代wt，否則wt不變。 那怎樣讓算法停下來呢？？——–我們就 自己規定迭代的次數 由于口袋算法得到的線越來越好（PLA就不一定了，PLA是最終結果最好，其他情況就說不準了），所以我們就 自己規定迭代的次數 。

感知機python實現代碼

#coding = utf-8

import numpy as np

import matplotlib.pyplot as plt

class showPicture：

def __init__（self，data，w，b）：

self.b = b

self.w = w

plt.figure（1）

plt.title（‘Plot 1’， size=14）

plt.xlabel（‘x-axis’， size=14）

plt.ylabel（‘y-axis’， size=14）

xData = np.linspace（0， 5， 100）

yData = self.expression（xData）

plt.plot（xData， yData， color=‘r’， label=‘y1 data’）

plt.scatter（data［0］［0］，data［0］［1］，s=50）

plt.scatter（data［1］［0］，data［1］［1］，s=50）

plt.scatter（data［2］［0］，data［2］［1］，marker=‘x’，s=50，）

plt.savefig（‘2d.png’，dpi=75）

def expression（self，x）：

y = （-self.b - self.w［0］*x）/self.w［1］

return y

def show（self）：

plt.show（）

class perceptron：

def __init__（self，x，y，a=1）：

self.x = x

self.y = y

self.w = np.zeros（（x.shape［1］，1））

self.b = 0

self.a = 1

def sign（self，w，b，x）：

result = 0

y = np.dot（x，w）+b

return int（y）

def train（self）：

flag = True

length = len（self.x）

while flag：

count = 0

for i in range（length）：

tmpY = self.sign（self.w，self.b，self.x［i，：］）

if tmpY*self.y［i］0：

tmp = self.y［i］*self.a*self.x［i，：］

tmp = tmp.reshape（self.w.shape）

self.w = tmp +self.w

self.b = self.b + self.y［i］

count +=1

if count == 0：

flag = False

return self.w，self.b

#原始數據

data = ［［3，3］，［4，3］，［1，1］］

xArray = np.array（［3，3，4，3，1，1］）

xArray = xArray.reshape（（3，2））

yArray = np.array（［1，1，-1］）

#感知機計算權值

myPerceptron = perceptron（x=xArray，y=yArray）

weight，bias = myPerceptron.train（）

#畫圖

picture = showPicture（data，w=weight，b=bias）

picture.show（）

責任編輯：ct