一、感知機(jī)算法收斂定理

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

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

在介紹感知機(jī)算法收斂定理前需先定義： 對(duì)于某一個(gè)Xi，其增廣向量Xiz為：

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

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

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

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

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

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

感知機(jī)算法收斂定理的表述如下：

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

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

二、感知機(jī)算法收斂定理的證明

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

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

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

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

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

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

將上式兩邊同時(shí)減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

因?yàn)棣?k)TXiz<0，所以：

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

又因?yàn)閷?duì)任意的i=1~N，ωoptTXiz>0，且||Xiz||2是一個(gè)有界的值，所以當(dāng)a的值足夠大時(shí)，可使

||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的距離至少減少一個(gè)單位。

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

審核編輯：劉清