感知机

机器学习

---

模型

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

$$sign(x)= \begin{cases} -1& {x<0}\\ 1& {x\geq 0} \end{cases}$$

分离超平面：$w \cdot x+b=0$

---

学习策略

目标：误分点总数尽量少，但这对w,b非连续可导，不易优化。转化为误分点到超平面的总距离尽量小。

误分点集M到超平面S的总距离：

$$\sum_{x_i \in M} \frac{|w \cdot x_i+b|}{||w||}$$

因为对于误分数据$(x_i,y_i)$有：$-y_i \cdot (w \cdot x_i+b)>0$
由此去掉绝对值，改写为

$$-\frac{1}{||w||}\sum_{x_i \in M} {y_i \cdot (w \cdot x_i+b)}$$

又因为最终的目标是二分类，而并非一味地追求误分总距离尽量小，因此可以不考虑$\frac{1}{||w||}$

得到损失函数为：

$$L(w,b)=-\sum_{x_i \in M} {y_i \cdot (w \cdot x_i+b)}$$

损失函数非负，越小越好，无误分点时为0。

---

学习算法

目标函数：

$$\min_{w,b}L(w,b)=-\sum_{x_i \in M} {y_i \cdot (w \cdot x_i+b)}$$

梯度：

$$\nabla_wL(w,b)=-\sum_{x_i \in M} {y_i x_i}$$

$$\nabla_bL(w,b)=-\sum_{x_i \in M} {y_i}$$

随机梯度下法：
1.初始化$(w_0,b_0 )$
2.在训练集中选取数据$(x_i,y_i)$
3.如果$y_i (w \cdot x_i+b)≤0$

$$w \leftarrow w+\eta y_i x_i$$

$$b \leftarrow b+\eta y_i$$

4.转至2，直到训练集中没有误分点

---

对偶形式

$$w \leftarrow w+\eta y_i x_i \Rightarrow w=\sum_{i=1}^{N}{n_i \eta y_i x_i}=\sum_{i=1}^{N}{\alpha_i y_i x_i}$$

当$\eta=1$时，$\alpha_i=n_i$，表示误分点$x_i$更新次数，次数越多表示离分离超平面越近，越难分。

对偶模型：$f(x)=sign(\sum_{j=1}^{N}{\alpha_j y_j x_j \cdot x+b})$，其中$\alpha=(\alpha_1,\alpha_2,\cdots,\alpha_N)^T$
1.$\alpha=0, b=0$
2.数据$(x_i,y_i)$，如果$y_i (\sum_{j=1}^{N}{\alpha_j y_j x_j \cdot x_i+b})≤0$

$$\alpha_i \leftarrow \alpha_i + \eta$$

$$b \leftarrow b+\eta y_i$$

3.转至2，直到训练集中没有误分点

好处是：可以预先将训练集內积计算存储，减少计算量。即Gram矩阵：

$$G=[x_i \cdot x_j ]_{N×N}$$