证明:经过有限次迭代,可以得到一个将线性可分的训练数据集完全正确划分的分离超平面及感知机模型
当训练数据集线性不可分时,算法不收敛
假设前提:
初值(w0,b0)=0
证明前的一些定义
(1)令
w^=(wT,b)Tx^=(x,1)向量一般默认为列向量 则
w^⋅x^=w⋅x+b (2)
所有训练数据点都线性可分
⇒∃一个超平面,使得所有训练数据集都被正确划分
令这个超平面为
w^opt⋅x^=0且∣∣w^opt∣∣=115 (3)令
γ=mini{yi(w^opt⋅x^i)}1 (4)令w^k为更新了k次之后的w^
(5)令
R=max1≤i≤n∣∣x^i∣∣10 证明过程
超平面w^opt⋅x^=0将所有数据都完全正确的分开
⇒∀(x^i,yi),有yi与w^opt⋅x^i符号相同,且两者都不为0
⇒∀(x^i,yi),有yi(w^opt⋅x^i)>0
以上结论结合公式(1)得:
yi(w^opt⋅x^i)≥γ>02 假设算法已经更新了k次,则至少有一个样本点在超平面w^k−1⋅x^=0上分类错误
假设(xi,yi)就是这个分类错误的点,则
yi(w^k−1⋅x^i)<09 且:
{wk=wk−1+ηyixibk=bk−1+ηyi(3) 计算w^k与w^k−1的关系:
w^k=(wk,bk)=(wk−1+ηyixi,bk−1+ηyi)=(wk−1,bk−1)+(ηyixi,ηyi)=w^k−1+ηyi(xi,1)=w^k−1+ηyix^i 得到:
w^k=w^k−1+ηyix^i4 Note: 由公式(3)推公式(4)本来很简单,之前一直推不出来是因为我把公式(4)ηyix^i当成了一个数,用numpy里面向量和数值相加的公式来算公式(4)。实际上ηyix^i也是一个n+1的向量,应该使用向量的加法来计算公式(4)。
证明w^k⋅w^opt≥kηγ:
w^k⋅w^opt=(w^k−1+ηyix^i)⋅w^opt5=w^k−1⋅w^opt+ηyix^i⋅w^opt≥w^k−1⋅w^opt+ηγ6≥w^k−2⋅w^opt+2ηγ⋯≥w^0⋅w^opt+kηγ≥kηγ7 公式说明:
1. 步骤(5):由公式(4)得到
2. 步骤(6):由公式(2)得到
3. 步骤(7):假设初值(w0,b0)=0? 最终得到:
w^k⋅w^opt≥kηγ8 证明∣∣w^k∣∣2≤kη2R2:
∣∣w^k∣∣2=∣∣w^k−1∣∣2+2w^k−1ηyix^i+(ηyix^i)211<∣∣w^k−1∣∣2+0+η2x^i212≤∣∣w^k−1∣∣2+η2R213≤∣∣w^k−2∣∣2+2η2R2⋯≤∣∣w^0∣∣2+kη2R213≤kη2R2 公式说明:
1. 步骤(11):结合公式(4)得到
2. 步骤(12):结合公式(9)得到第二项小于,第三项中yi2=1
3. 步骤(13):结合公式(10)得到
最终得到:
∣∣w^k∣∣2≤kη2R214 公式8⇒kηγ≤w^k⋅w^opt⇒k2η2γ2≤∣∣w^k∣∣2∣∣w^opt∣∣2⇒k2η2γ2≤∣∣w^k∣∣2≤η2R216⇒k≤(γR)2 公式说明:
1. 步骤(16):结合公式(15)
最终结论:
k≤(γR)2 命题得证