感知机学习

感知机简介

感知机模型

$$f(x)=sign(w\cdot x+b)$$

分离超平面

$$w\cdot x+b=0$$

感知机的学习策略

1. 误分类点总数
损失函数不是w、b的导数，不易优化

2. 所有误分类点到超平面的总几何距离
$$-\frac{1}{||w||}\sum_{x_i \in M} y_i\left(w \cdot x_i+b\right)$$

3. 所有误分类点到超平面的总函数间隔（即不考虑1/w）
$$L(w, b)=-\sum_{x_i \in M} y_i\left(w \cdot x_i+b\right)$$

感知机学习算法（原始形式）

随机梯度下降法

1. 求损失函数对参数w，b的导数
$$\begin{aligned}\nabla_w L(w, b) & =-\sum_{x_i \in M} y_i x_i \\\nabla_b L(w, b) & =-\sum_{x_i \in M} y_i\end{aligned}$$

2. 随机选取一个误分类点（x_i, y_i）对参数进行更新
$$\begin{aligned}&w+\eta y_i x_i \rightarrow w\\&b+\eta y_i \rightarrow b\end{aligned}$$
通过迭代不断是损失函数减少到0

算法流程

感知机学习算法（对偶形式）

对偶形式的参数

设w，b关于（x_i，y_i）修改 η_i 次，记

$$\alpha_i=\eta_i \eta$$

则参数w，b可表示为

$$\begin{aligned}&w=\sum_{i=1}^N \alpha_i y_i x_i\\&b=\sum_{i=1}^N \alpha_i y_i\end{aligned}$$

算法中关于w，b的更新可转化为 𝛼_i，b的更新

$$\begin{aligned}&\alpha_i+\eta \rightarrow \alpha_i\\&b+\eta y_i \rightarrow b\end{aligned}$$

对偶形式的优点

训练实例x_i，i=1,2,…仅以内积的形式出现，为了方便，可以预先存储矩阵

$$G=[x_i\cdot y_i]_{N\times N}$$

 

算法流程

感知机学习算法性能