一、感知機算法收斂定理

由于感知機算法通過調(diào)整ω和b的值以使所有訓(xùn)練樣本滿足設(shè)定條件，人們可能直觀感覺會出現(xiàn)當ω和b可使某一樣本滿足設(shè)定條件，就會使另一個樣本不滿足設(shè)定條件的情況，從而使感知機算法出現(xiàn)無限循環(huán)，無法終止的情況。

對于上述情況，弗蘭克·羅森布拉特（Frank Rosenblatt）證明了如下結(jié)論：只要訓(xùn)練數(shù)據(jù)線性可分，感知機算法一定可以終止。該結(jié)論所對應(yīng)的定理為感知機算法收斂定理。

在介紹感知機算法收斂定理前需先定義： 對于某一個Xi，其增廣向量Xiz為：

（1）若yi=+1，則Xiz=(Xi,1)T；

（2）若yi=-1，則Xiz=(Xi,-1)T。

上述定義可將原問題：尋找(ω,b)，使得對i=1~N，有：

（1）若yi=+1，則ωTXi+b<0；

（2）若yi=-1，則ωTXi+b>0。

簡化為：尋找W=(ω,b)T，使得對i=1~N，有：WTXiz>0。

感知機算法收斂定理的表述如下：

對于N個增廣向量X1z，X2z，…，XNz，如果存在一個權(quán)重向量ωopt，使得對于每一個i=1~N，有： ωoptTXiz>0 則運用上述感知機算法在有限步內(nèi)可找到一個ω，使得對于所有的i=1~N，有： WTXiz>0。

感知機算法收斂定理中，ωoptTXiz>0等價于樣本線性可分，且ω不一定與ωopt相等（如果存在一個超平面可將樣本分為兩類，則一定存在無數(shù)個超平面可將樣本分為兩類，ω和ωopt可以是無數(shù)個超平面權(quán)重向量中的兩個）。

二、感知機算法收斂定理的證明

假設(shè)：||ωopt||=1。

（該假設(shè)成立的原因是向量W和aW代表的是同一平面，因此，ωopt可被a加權(quán)調(diào)整為||ωopt||=1）

定義ω(k)為第k次改變后的權(quán)重向量值，則可能出現(xiàn)以下兩種情況：

（1）若ω(k)TXiz>0對所有i=1~N，則所有點已經(jīng)達到平衡，感知機算法收斂。

（2）若存在i，使得ω(k)TXiz<0，則根據(jù)感知機算法：

ω(k+1)=ω(k)+Xiz

將上式兩邊同時減aωopt（aωopt與ωopt代表同一超平面的權(quán)重向量），得：

ω(k+1)-aωopt=ω(k)-aωopt+Xiz

上式兩邊取模的平方，可轉(zhuǎn)化為：

||ω(k+1)-aωopt||2=||ω(k)-aωopt+Xiz||2=||ω(k)-aωopt||2+2ω(k)TXiz-2aωoptTXiz+||Xiz||2

因為ω(k)TXiz<0，所以：

||ω(k+1)-aωopt||2≤||ω(k)-aωopt||2-2aωoptTXiz+||Xiz||2

又因為對任意的i=1~N，ωoptTXiz>0，且||Xiz||2是一個有界的值，所以當a的值足夠大時，可使

||Xiz||2-2aωoptTXiz≤-1

（課程中為||Xiz||2-2aωoptTXiz＜-1）。 因此，||ω(k+1)-aωopt||2≤||ω(k)-aωopt||2-1，即W的值每更新一次（W=(ω,b)T）,其距離aωopt的距離至少減少一個單位。

綜上，假設(shè)W的初值為ω(0)，則至多經(jīng)過||ω(0)-aωopt||2次迭代，ω將收斂于aωopt。

審核編輯：劉清