感知機的收斂性(Novikoff定理)證明

感知機的收斂性(Novikoff定理)證明

定理如下

—————————————————————————————-

證明如下:

(1)

因為訓練資料是線性可分的,所以存在超平面可使得資料完全分開,記此超平面為

                   令:                                                                                                                                               
                      

                  則

 

  則

對於 有

—————————————————————————————-

(2)首先證明兩個不等式:

證明第一個:

令感知機演算法的初始值為

若存在例項誤分類,則需要不斷更新權重

令wk-1是進行第k個誤分類之前的權重,即

則第k步更新過程為

證明第二個不等式:

綜合上述:

————————————————————————————————

END