因为感知机，我被周某人嘲笑了，在哪里跌倒就要在哪里爬起来并写一篇博客！

感知机

• 输入空间：$\chi\subseteq R^n$χ⊆Rn
• 输出空间：$y=\{+1,-1\}$y={+1,−1}
• 函数：$f(x)=sign(w\cdot x+b)$f(x)=sign(w⋅x+b) $sign(x)=\begin{cases}+1&x\ge 0\\-1&x<0\end{cases}$sign(x)={+1−1​x≥0x<0​
• $w\cdot x+b=0$w⋅x+b=0可看做分离超平面，$w$w为超平面的法向量，$b$b为截距
• 小知识：
  • 感知机为二分类的线性分类模型，只能处理完全线性可分的数据

感知机分类策略

• 损失函数——虽然很自然的想到用误分类点个数作为损失函数，但是这样的损失函数不是$w,b$w,b的连续可导函数（分段）了，不易对损失函数进行优化，所以，一个更好的选择是——
  • 将所有误分类点到超平面的总距离作为损失函数
  • 任意一点$x_0$x0​到超平面$w\cdot x+b=0$w⋅x+b=0的距离为：$\frac1{\parallel w\parallel}_2|w\cdot x_0+b|$∥w∥1​2​∣w⋅x0​+b∣ $\parallel w\parallel_2$∥w∥2​为$L_2$L2​范数
  • 不想要分数形式，可将超平面归一化，即$w\cdot x+b=0\Rightarrow\frac{w}{\parallel w\parallel}\cdot x+\frac{b}{\parallel w\parallel}=0$w⋅x+b=0⇒∥w∥w​⋅x+∥w∥b​=0令$w:=\frac{w}{\parallel w\parallel},b:=\frac{b}{\parallel w\parallel}$w:=∥w∥w​,b:=∥w∥b​
  • 再想着能不能把绝对值去了，减少一下计算机的计算负担，发现对于误分类点来说，$-y_i(w\cdot x_i+b)>0$−yi​(w⋅xi​+b)>0恒成立
  • 所以损失函数最终变成了$L(w,b)=-\sum\limits_{x_i\in M}y_i(w\cdot x_i+b)$L(w,b)=−xi​∈M∑​yi​(w⋅xi​+b) M为所有误分类点的集合

感知机学习算法

• 训练集：$T=\{(x_1,y_1),...,(x_N,y_N)\}$T={(x1​,y1​),...,(xN​,yN​)}
• 对损失函数极小化：$\min\limits_{w,b}L(w,b)=-\sum\limits_{x_i\in M}y_i(w\cdot x_i+b)$w,bmin​L(w,b)=−xi​∈M∑​yi​(w⋅xi​+b)
• $\triangledown_wL(w,b)=-\sum\limits_{x_i\in M}y_ix_i$▽w​L(w,b)=−xi​∈M∑​yi​xi​ $\triangledown_bL(w,b)=-\sum\limits_{x_i\in M}y_i$▽b​L(w,b)=−xi​∈M∑​yi​
• 这里采用的是随机梯度下降（stochastic gradient descent）：一次随机选择一个误分类点使其梯度下降
  • 若选$(x_i,y_i),对w,b$(xi​,yi​),对w,b更新：
    • $\triangledown_wL(w,b)=-y_ix_i,\triangledown_bL(w,b)=-y_i$▽w​L(w,b)=−yi​xi​,▽b​L(w,b)=−yi​
    • $w:=w-\eta\triangledown_wL(w,b)=w+\eta y_ix_i$w:=w−η▽w​L(w,b)=w+ηyi​xi​$b:=b-\eta\triangledown_bL(w,b)=b+\eta y_i$b:=b−η▽b​L(w,b)=b+ηyi​ $\eta$η为移动步长

原始算法

• 输入：数据集$T,学习率\eta(0<\eta\le1)$T,学习率η(0<η≤1)
• 输出：$w,b$w,b
• 模型：$f(x)=sign(w\cdot x+b)$f(x)=sign(w⋅x+b)
• 步骤：
  • (1)选取初值$w_0,b_0$w0​,b0​
  • (2)选取数据$(x_i,y_i)$(xi​,yi​)
  • (3)若该点为误分类点，即$y_i(wx_i+b)\le0$yi​(wxi​+b)≤0 $w:=w+\eta y_ix_i$w:=w+ηyi​xi​ $b:=b+\eta y_i$b:=b+ηyi​
  • (4)转至（2），直到训练集没有误分类点（或许这就是要求数据完全线性可分的原因？）

对偶算法

• 设$(x_i,y_i)$(xi​,yi​)会误分$n_i$ni​次，则关于$(x_i,y_i)$(xi​,yi​)点，$w,b$w,b变化为$\eta n_iy_ix_i,\eta n_iy_i$ηni​yi​xi​,ηni​yi​，记$\alpha_i=\eta n_i$αi​=ηni​
• 最后学习到的$w,b$w,b为$w:=w_0+\sum\limits_{i=1}^N\alpha_iy_ix_i$w:=w0​+i=1∑N​αi​yi​xi​ $b:=b_0+\sum\limits_{i=1}^N\alpha_iy_i$b:=b0​+i=1∑N​αi​yi​
• 对偶算法，转化为求$\alpha=(\alpha_1,\alpha_2,...,\alpha_N)^T(其实是n_i),b$α=(α1​,α2​,...,αN​)T(其实是ni​),b
• 模型：$f(x)=sign(\sum\limits_{j=1}^N\alpha_jy_jx_j\cdot x+b)$f(x)=sign(j=1∑N​αj​yj​xj​⋅x+b)
• 步骤：
  • (1)初始化：$\alpha=0,b=0$α=0,b=0
  • (2)在训练集中选取$(x_i,y_i)$(xi​,yi​)
  • (3)若$y_i(\sum\limits_{j=1}^N\alpha_jy_jx_j\cdot x_i+b)\le 0$yi​(j=1∑N​αj​yj​xj​⋅xi​+b)≤0:$\alpha_i:=\alpha_i+\eta$αi​:=αi​+η $b:=b+\eta y_i$b:=b+ηyi​
  • (4)转至（2），直到训练集没有误分类点
  • 这里有$x_i\cdot x_i$xi​⋅xi​，表示内积，可以先生成Gram矩阵：$G=[x_i\cdot x_j]_{N\times N}$G=[xi​⋅xj​]N×N​