? ? ?感知機（perceptron）是二分類的線性分類模型，輸入為實例的特征向量，輸出為實例的類別（取+1和-1）。感知機對應于輸入空間中將實例劃分為兩類的分離超平面。感知機旨在求出該超平面，為求得超平面導入了基于誤分類的損失函數，利用梯度下降法 對損失函數進行最優化（最優化）。感知機的學習算法具有簡單而易于實現的優點，分為原始形式和對偶形式。感知機預測是用學習得到的感知機模型對新的實例進行預測的，因此屬于判別模型。感知機由Rosenblatt于1957年提出的，是神經網絡和支持向量機的基礎。

行文脈絡

感知機模型

感知機學習策略

感知機學習算法

• • 原始形式
  • 對偶形式

????? 4. Github地址

1. 感知機模型

定義

假設輸入空間(特征向量)為X?Rⁿ，輸出空間為Y={-1, +1}。輸入x∈X表示實例的特征向量，對應于輸入空間的點；輸出y∈Y表示示例的類別。由輸入空間到輸出空間的函數為

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?f(x)=sign(w·x + b) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（1）

稱為感知機。其中，參數w叫做權值向量，b稱為偏置。w·x表示w和x的內積。sign為符號函數，即

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （2）

?

?

幾何解釋 ? ?

感知機模型是線性分類模型，感知機模型的假設空間是定義在特征空間中的所有線性分類模型，即函數集合{f|f(x)=w·x+b}。線性方程 w·x+b=0對應于特征空間Rⁿ中的一個超平面S，其中w是超平面的法向量，b是超平面的截踞。這個超平面把特征空間劃分為兩部分。位于兩側的點分別為正負兩類。超平面S稱為分離超平面，如下圖：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

?

?

學習與預測

感知機學習即由訓練數據集T={(x₁,y₁),(x₂,y₂)...(x_N,y_N)}（其中x_i∈X=Rⁿ，y_i∈Y={-1, +1}，i=1,2...N）求得感知機模型（1），即求得參數w,b；感知機預測即根據得到的感知機模型（1），對新的輸入實例給出對應的類型。

?

2. 感知機學習策略

? ? 假設訓練數據集是線性可分的，感知機學習的目標是求得一個能夠將訓練數據的正負實例點完全分開的分離超平面，即最終求得參數w、b。這需要一個學習策略，即定義（經驗）損失函數并將損失函數最小化。

? ? 損失函數的一個自然的選擇是誤分類的點的總數。但是這樣得到的損失函數不是參數w、b的連續可導函數，不宜優化。損失函數的另一個選擇是誤分類點到分里面的距離之和。

? ? 首先，對于任意一點xo到超平面的距離為

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(3)

? ? 其次，對于誤分類點（x_i,y_i）來說 -y_i(w·x_i+b)>0

? ? 這樣，假設超平面S的總的誤分類點集合為M，那么所有誤分類點到S的距離之和為

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??? ? ? ? ? ? ? ? ? ? ? ? ? ?(4)

不考慮1/||w||，就得到了感知機學習的損失函數。

經驗風險函數

? ? 給定數據集T={(x₁,y₁),(x₂,y₂)...(x_N,y_N)}（其中x_i∈X=Rⁿ，y_i∈Y={-1, +1}，i=1,2...N），感知機sign(w·x+b)學習的損失函數定義為

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??? ? ? ? ? ? ? ? ? ? ?(5) ? ? ? ? ? ? ??

其中M為誤分類點的集合，這個損失函數就是感知機學習的經驗風險函數。 ? ? ? ? ? ? ? ? ? ? ? ? ??

? ? 顯然，損失函數L(w,b)是非負的。如果沒有誤分類點，那么L(w,b)為0，誤分類點數越少，L(w,b)值越小。一個特定的損失函數：在誤分類時是參數w,b的線性函數，在正確分類時，是0.因此，給定訓練數據集T,損失函數L(w,b)是w,b的連續可導函數。

?

3. 感知機學習算法

? ? 最優化問題：給定數據集T={(x₁,y₁),(x₂,y₂)...(x_N,y_N)}（其中x_i∈X=Rⁿ，y_i∈Y={-1, +1}，i=1,2...N），求參數w,b,使其成為損失函數的解（M為誤分類的集合）：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ?（6）

3.1 感知機學習的原始形式

? ? 感知機學習是誤分類驅動的，具體采用隨機梯度下降法。首先，任意選定w₀、b₀，然后用梯度下降法不斷極小化目標函數（6），極小化的過程不知一次性的把M中的所有誤分類點梯度下降，而是一次隨機選取一個誤分類點使其梯度下降。

? ? 假設誤分類集合M是固定的，那么損失函數L(w,b)的梯度由（7）（8）給出

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （7）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （8）

隨機選取一個誤分類點（xi,yi）,對w,b進行更新：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （9）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （10）

式中η（0≤η≤1）是步長，在統計學是中成為學習速率。步長越大，梯度下降的速度越快，更能接近極小點。如果步長過大，有可能導致跨過極小點，導致函數發散；如果步長過小，有可能會耗很長時間才能達到極小點。

?

算法（感知機學習算法的原始形式）

輸入：T={(x1,y1),(x2,y2)...(xN,yN)}（其中xi∈X=Rn，yi∈Y={-1, +1}，i=1,2...N，學習速率為η） 輸出：w, b;感知機模型f(x)=sign(w·x+b) (1) 初始化w0,b0 (2) 在訓練數據集中選取（xi, yi） (3) 如果yi(w xi+b)≤0w = w + ηyixib = b + ηyi (4) 轉至（2）

直觀解釋：當一個實例點被誤分類時，調整w,b，使分離超平面向該誤分類點的一側移動，以減少該誤分類點與超平面的距離，直至超越該點被正確分類。

例1

對于訓練數據集，其中正例點是x1=(3,3)T,x2=(4,3)T，負例點為x3=(1,1)T，用感知機學習算法的原始形式求感知機模型f(x)=w·x+b。這里w=(w⁽¹⁾,w⁽²⁾)^T，x=(x⁽¹⁾,x⁽²⁾)^T

解：構建最優化問題：

? ? ? ? ? ? ? ? ??

按照算法求解w， b。η=1

(1)取初值w₀=0, b₀=0

(2)對于（3，3）:-(0+0)+0=0未被正確分類。更新w,b

? ? ? ? ? ? ? ?w1=w₀+1*y₁·x₁ = (0,0)T+1(3,3)T=(3,3)T

? ? ? ? ? ? ? ?b₁=b₀+y₁=1

? ? ? ? ?得到線性模型w₁x+b₁ = 3x⁽¹⁾+3x⁽²⁾+1

(3)返回（2）繼續尋找y_i(w·x_i+b)≤0的點，更新w,b。直到對于所有的點y_i(w·x_i+b)>0，沒有誤分類點，損失函數達到最小。

分離超平面為x⁽¹⁾+x⁽²⁾-3=0

感知機模型為 f(x)=sign(x⁽¹⁾+x⁽²⁾-3)

? ? 在迭代過程中，出現w·x_i+b=-2，此時，取任意一個點，都會是其小于0，不同的取值順序會導致最終的結果不同，因此解并不是唯一的。為了得到唯一的超平面，需要對分離超平面增加約束條件，這就是支持向量機的想法。

實現代碼

import os import sys# An example in that book, the training set and parameters' sizes are fixed training_set = []w = [] b = 0 lens = 0 n = 0# update parameters using stochastic gradient descent def update(item):global w, b, lens, nfor i in range(lens):w[i] = w[i] + n * item[1] * item[0][i]b = b + n * item[1]print w, b # you can uncomment this line to check the process of stochastic gradient descent# calculate the functional distance between 'item' an the dicision surface def cal(item):global w, bres = 0for i in range(len(item[0])):res += item[0][i] * w[i]res += bres *= item[1]return res# check if the hyperplane can classify the examples correctly def check():flag = Falsefor item in training_set:if cal(item) <= 0:flag = Trueupdate(item)if not flag: #Falseprint "RESULT: w: " + str(w) + " b: "+ str(b)tmp = ''for keys in w:tmp += str(keys) + ' 'tmp = tmp.strip()modelFile.write(tmp + '\n')modelFile.write(str(b) + '\n')modelFile.write(str(lens) + '\n')modelFile.write(str(n) + '\n')modelFile.close()os._exit(0)flag = Falseif __name__=="__main__":if len(sys.argv) != 4:print "Usage: python perceptron.py n trainFile modelFile"exit(0)n = float(sys.argv[1])trainFile = file(sys.argv[2])modelFile= file(sys.argv[3], 'w')lens = 0for line in trainFile:chunk = line.strip().split(' ')lens = len(chunk) - 1tmp_all = []tmp = []for i in range(1, lens+1):tmp.append(int(chunk[i]))tmp_all.append(tmp)tmp_all.append(int(chunk[0]))training_set.append(tmp_all)trainFile.close()for i in range(lens):w.append(0)for i in range(1000):check()print "The training_set is not linear separable. " View Code

??

3.2 感知機學習的對偶形式

對偶形式的基本想法是，將w,b表示成為實例x_i和標記y_i的線性組合的形式，通過求解其系數而得到w和b。不失一般性，將初始值w₀,b₀設為0.對誤分類點（x_i,y_i）通過

w = w + ηyixib = b + ηyi

的轉換逐步修該w,b，設修改了n次，則w,b關于（xi,yi）的增量分別為a_iy_ix_i和a_iy_i，這里a_i=n_iη最終學習到的w,b可以表示為

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

實例點更新次數越多，意味著它距離分離超平面越近，也就越難正確分類。換句話說，這樣的實例對學習結果影響很大。

算法（感知機學習算法的對偶形式）

輸入：T={(x1,y1),(x2,y2)...(xN,yN)}（其中xi∈X=Rn，yi∈Y={-1, +1}，i=1,2...N，學習速率為η） 輸出：a,b;感知機模型f(x)=sign(w·x+b) (1) 初始化w0,b0 (2) 在訓練數據集中選取（xi, yi） (3) 如果

ai = ai + η b = b + ηyi (4) 轉至（2）

對偶形式中訓練數據僅以內積的形式出現，為了方便可以預先把訓練數據間內積計算出來并以矩陣的形式存儲起來，這個矩陣就是所謂的Gram矩陣。

實現代碼

import os import sys# An example in that book, the training set and parameters' sizes are fixed training_set = []w = [] a = [] b = 0 lens = 0 n = 0 Gram = []def calInnerProduct(i, j):global lensres = 0for p in range(lens):res += training_set[i][0][p] * training_set[j][0][p]return resdef AddVector(vec1, vec2):for i in range(len(vec1)):vec1[i] = vec1[i] + vec2[i]return vec1def NumProduct(num, vec):for i in range(len(vec)):vec[i] *= numreturn vec def createGram():global lensfor i in range(len(training_set)):tmp = []for j in range(0, len(training_set)):tmp.append(calInnerProduct(i, j))Gram.append(tmp)# update parameters using stochastic gradient descent def update(k):global a, b, na[k] += nb = b + n * training_set[k][1] print a, b # you can uncomment this line to check the process of stochastic gradient descent# calculate the functional distance between 'item' an the dicision surface def cal(k):global a, bres = 0for i in range(len(training_set)):res += a[i] * int(training_set[i][1]) * Gram[i][k]res += bres *= training_set[k][1]return res# check if the hyperplane can classify the examples correctly def check():global w, aflag = Falsefor i in range(len(training_set)):if cal(i) <= 0:flag = Trueupdate(i)if not flag: #Falsefor i in range(len(training_set)):w = AddVector(w, NumProduct(a[i] * int(training_set[i][1]), training_set[i][0]))print "RESULT: w: ", w, " b: ", btmp = ''for keys in w:tmp += str(keys) + ' 'tmp = tmp.strip()modelFile.write(tmp + '\n')modelFile.write(str(b) + '\n')modelFile.write(str(lens) + '\n')modelFile.write(str(n) + '\n')modelFile.close()os._exit(0)flag = Falseif __name__=="__main__":if len(sys.argv) != 4:print "Usage: python perceptron_duality.py n trainFile modelFile"exit(0)n = float(sys.argv[1])trainFile = file(sys.argv[2])modelFile= file(sys.argv[3], 'w')lens = 0for line in trainFile:chunk = line.strip().split(' ')lens = len(chunk) - 1tmp_all = []tmp = []for i in range(1, lens+1):tmp.append(int(chunk[i]))tmp_all.append(tmp)tmp_all.append(int(chunk[0]))training_set.append(tmp_all)trainFile.close()createGram()for i in range(len(training_set)):a.append(0)for i in range(lens):w.append(0)for i in range(1000):check()print "The training_set is not linear separable. " View Code

?

4. GitHub地址

https://github.com/jihite/Perceptron-python-

轉載于:https://www.cnblogs.com/kaituorensheng/p/3561091.html

總結

以上是生活随笔為你收集整理的感知机（python实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

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