感知机模型及其对偶形式

1. 对偶

• 输入：线性可分的数据集 T={(x1,y1),(x2,y2),…,(xN,yN)}，其中 xi∈Rn,yi∈{−1,+1} ，学习率为 η，

• 输出：α,b，感知机模型为 f(x)=sgn(∑j=1Nαjyjxj⋅x+b)，显然 α 是长度为 N 的向量；

• 算法：

  • (1) α←0,b←0
  • (2) 在训练集中选取数据 (xi,yi)
  • (3) 如果 yi(∑j=1Nαjyjxj⋅x+b)≤0，
    
    • αi←αi+η
    • b←+ηyi
  • (4) 转至(2), 直至没有误分类数据；

对于 ∑jxj⋅x，也即对偶形式中训练实例仅以内积的形式出现，为了方便（离线训练），可以预先将训练集中实例间的内积计算出来，并以矩阵的形式存储，这个矩阵就是所谓的 Gram 矩阵，

Gi,j=⟨xi,xj⟩