ch2-感知机 |

定义如下：

$sign(x)= \left\{ \begin{array}{ll}+1,& x \geq 0\\ -1,& x < 0 \end{array} \right.$

给定一个数据集 $T$ ，存在一个超平面 $S$ ，满足能够将数据集的正实例点和负实例点完全正确地划分到超平面两侧，则称此数据集是线性可分的。

由超平面 $S$ 的方程 $wx+b$ 可以得到对于任意一个点，到超平面的距离是

$\frac{1}{||w||} \cdot | wx + b|$

其中 $\frac{1}{||w||}$ 是 L2 范数。

那么对于某一误分类点，则有：

$- \frac{y_{i}}{||w||} |wx+b| > 0$

考虑所有误分类点，则有：

$- \sum_{i=1}^{n} \frac{y_{i}}{||w||} (wx+b)$

我们忽略 $\frac{1}{||w||}$ ，则得到了感知机算法的损失函数：

$- \sum_{i=1}^{n} y_{i} (wx_{i}+b)$

使用随机梯度下降算法对损失函数进行最优化。

输出：参数 $w,b$

$f(x) = sign (wx+b)$

选取初始值 $w{0}$ , $b{0}$ （一般默认为 0 ）
在训练集中选取数据 $(x{i},y{i})$
如果 $y{i}(w \cdot x{i} + b) <= 0$ 则：
$w \gets w +\eta x_{i} y_{i} \\ b \gets b + \eta y_{i}$
重复步骤 2 和 3 ，直到完全分类未知。

对于线性可分的数据集，感知机算法是收敛的。

$k <= (\frac{R}{\gamma})^2$

其中 $R=max|x_{i}|$ , $\gamma > 0$ 。

我们知道利用随机梯度函数优化的时候，有：

$w \gets w +\eta x_{i} y_{i}$ $b \gets b + \eta y_{i}$

这里我们可以知道每次修改的量都是一定的，这里我们定义 $\alpha{i} = n{i} \cdot \gamma$ , 其中 $n_{i}$ 表示该点被选择了第 $i$ 次，那么

$w = \sum_{i=1}^{N} \alpha_{i}x_{i}y_{i}$ $b = \sum_{i=1}^{N} \alpha_{i} y_{i}$

这样，则模型变为：

$f(x) = sign( \sum_{i=1}^{N} \alpha_{i}x_{i}y_{i} \cdot x + \sum_{i=1}^{N} \alpha_{i} y_{i})$

其中我们只需要对 $\alpha_{i}$ 进行迭代就好了,训练步骤基本同上。

那我们为什么要对偶形式呢？疑问我们可以看到 $f(x)$ 中样本点的特征向量以内积的形式存在，如果我们可以提前计算好，那么就可以大大滴加快训练速度。

$G_{ij}=x_{i} \cdot x_{j}$

感知机学习算法是基于随机梯度下降法的对损失函数的最优化算法，有对偶形式，算法简单。若数据集线性可分，则感知机是收敛的

Q：感知机为什么线性不可分？

A: 因为 XOR 的训练集线性不可分。坐标轴上点（0，0） = （1,1） = 1 ，（0，1） = （1,0 ） = 0 ，此时异或无法线性可分。

很好地一篇学习笔记: 感知机学习笔记