感知机
感知机是一种二分类的线性分类模型，感知机的核心思想是在特征空间中找到一个超平面，将所有的实例分隔为正例和反例。
1.分类策略
假设在特征空间 $R^N$ 中，定义一个超平面： $$W\cdot X+b=0$$
对任一点 $X_i，W\cdot X_i+b > 0，y_i = 1$，反之 $y_i=-1$。
进一步，我们改写式子 $X_i = (1, x_1,….,x_n),~W=(b, w_1,…,w_n)$，超平面的数学表达式改为：
$$W\cdot X = 0$$
2.学习策略
感知机的学习策略十分简单：
- 初始化一个超平面 $W_0, b_0$
遍历样本中的每个点：
- 假如超平面分类正确，不做任何修改
假如超平面分类错误，修改超平面的方向，使平面的向误分类点的一侧移动，$\eta$ 为学习率或步长 $$W_{n+1} = W_n + \eta y_iX_i$$
如果所有的点都分类正确，结束循环。
假如样本线性可分，根据我们的直观经验，必然存在多个超平面可以完美的将所有的样本正确分隔开。因此，不同的初始化平面，不同的学习率，会导致我们最终得到的不同感知机（感知机不唯一）。
3. 先决条件和收敛证明
由1.2可知，感知的训练过程是一个不断循环的过程，我们要最终得到一个感知机，则循环必须终止，而循环终止有两个条件：
- 样本本身线性可分（存在平面可以正确分隔所有的点）
- 平面在经过有限次的迭代后，能够正确的分类
现在我们假设样本S中所有的点在特征空间中线性可分，存在一个平面 $W_f$ 将所有的点正确分类。因此：
$$y_n W_f\cdot X_n\geq\min_{i}y_i W_f\cdot X_i>0$$
假设我们初始化的 $W_0 = 0$，已知每次迭代：
$W_n = W_{n-1} + \eta y_{n-1}X_{n-1}$
$W_f\cdot W_n = W_f\cdot (W_{n-1} + \eta y_{n-1}X_{n-1}) \geq W_f\cdot W_{n-1} + \eta\min_{i} y_iW_f\cdot X_i$
$~~~~~~~~~~~~~\geq n~\eta \min_{i} y_iW_f\cdot X_i$
由于只有当分类错误时，感知器才会迭代更新：
$$y_nW_n\cdot X_n < 0$$
$||W_{n}||^2 = ||W_{n-1} + \eta y_{n-1}X_{n-1}||^2 = ||W_{n-1}||^2 + 2\eta y_{n-1}W_{n-1}\cdot X_{n-1} + ||\eta y_{n-1}X_{n-1}||^2$
$~~~~~~~~~~~~~~~\leq ||W_{n-1}||^2 + ||\eta y_{n-1}X_{n-1}||^2 \leq ||W_{n-1}||^2 + ||\eta X_{longest}||^2$
$~~~~~~~~~~~~~~~\leq n ||\eta X_{longest}||^2$
这里我们求迭代后的平面向量 $W_n$ 与 $W_f$ 之间的夹角$\theta$，两个向量的夹角越小，他们之间的相似度越高。
$\cos\theta = \frac{W_f\cdot W_{n}}{||W_f||||W_{n}||}\geq\frac{n~\eta\min_{i} y_iW_f\cdot X_i}{\sqrt{ n \eta}||W_f|| ||X_{longest}|| } = \sqrt{n} \frac{\sqrt{\eta }\min_{i} y_iW_f\cdot X_i}{||W_f|| ||X_{longest}||} = \sqrt{n} \times constant$
$\cos\theta \sim O(\sqrt{n})$
$\cos\theta$ 随着迭代的次数增加，越来越大，意味着经过迭代 $W_n$ 与 $W_f$ 越来越接近，因为 $\cos\theta \leq 1$，因此经过有限次的迭代，就可以得到完美分类的感知机。
4.样本线性不可分的情况
假如样本在特征空间中线性不可分，那么我们永远无法得到一个完美的感知机，在这种情况下，我们只能退而求其次，使感知机的错误尽可能的少。
$$W_g = argmin \sum_{i=1}^N [y_n \neq sign(W\cdot X_n)]$$
但求解这个最优问题是个NP问题，在实际操作中，我们保存一个分类效果最好的感知机，在每次更新感知机后，我们计算感知机的分类误差，如果新的感知机效果更好，就将新得到的感知机保存为最优感知机。
我们限制一定的迭代次数，最终得到一个近似的最优感知机。