感知机（perceptron）

  感知机模型属于二分类线性分类模型，属于判别模型和非几率模型。用一句话描述这个模型，就是找到一个超平面，把线性可分数据集分到超平面两侧。html

线性可分数据集

  存在某个超平面能够将数据集的正实例点和负的实例点彻底正确的划分到超平面的两侧，这样的数据集称做线性可分数据集，不然是非线性可分数据集。感知机要求数据集是线性可分的。web

原始形式

统计学习方法三要素

模型： $y=sign(\omega ^{T}x+b)$
策略： $L(\omega,b)=\sum\limits_{i \in m}-y_{i}(\omega ^{T}x_{i}+b)$，m是误分类的数据集
学习：SGD
$\frac{\partial L}{\partial \omega}=\sum\limits_{i \in m}-y_{i}x_{i}, ~~~~~~\frac{\partial L}{\partial b}=\sum\limits_{i \in m}-y_{i}$
因此参数的更新过程为( $\eta为学习率$)
$\omega=\omega-\eta \frac{\partial L}{\partial \omega}=\omega+\sum\limits_{i \in m}\eta y_{i}x_{i}$
$b=b-\eta \frac{\partial L}{\partial b}=b+\sum\limits_{i \in m}\eta y_{i}$
因为学习方法是随机梯度降低法，因此每次找到一个误分类的 $(x_{i},y_{i})$便可。
  学习算法直观上能够当作，当被选择的实例点位于超平面错误的一侧，则调整 $\omega与b$，使得超平面向该误分类点一侧移动，减少该误分类点到超平面的距离，直至全部超平面都被正确分类。结合下图简单解释一下，假设目前的决策函数位置在 $\omega^{T}x+b=0$处， $x_{i}$被误分类，因为其在 $\omega$指向一侧，因此目标函数把其分类为正(关于超平面知识看我写的SVM里面的超平面部分知识)，实际 $y_{i}=-1$，因为 $\eta>0$， $\eta y_{i}x_{i}$是图上关于 $x_{i}$原点对称点的放缩，假设就在图上表示的点， $\omega$加上 $\eta y_{i}x_{i}$后， $\omega$方向变成 $\omega_{2}$方向， $\omega_{2}$表示的直线假设是图上红线表示的点，可见决策超平面在向着 $x_{i}$能被正确分类的方向转动。

  值得一提的是，在构造感知机的损失函数时，最天然的选择是误分类点的总数，这样的话损失函数长这样 $L(\omega, b)=\sum\limits_{i \in m}-y_{i}sign(\omega^{T}x_{i}+b)$，这样的损失函数不是连续可导函数，因此损失函数选择为误分类点到超平面的总距离(在SVM中可知，这种距离称做函数距离)，其对应绝对值损失函数。
  因为学习算法能够采用不一样的初值或选取不一样的误分类点，最终的感知机模型可能不一样。算法

学习流程

输入：训练集 $T=\{(x_{1},y_{1}),(x_{2},y_{2}),(x_{3},y_{3})\dots (x_{n},y_{n})\}，\eta(0<\eta \leq 1),y_{i}\in \{-1,1\}$。
输出： $\omega, b$；决策函数 $y=sign(w^{T}x+b)$
执行流程：app

1. 初始化参数 $\omega与b$，通常初始化为0。
2. 从训练集中找出一个点 $(x_{i},y{_i})$。
3. 若是该点是误分类的点，利用 $(x_{i},y{_i})$与公式 $\omega = \omega + \eta y_{i}x_{i}，b=b+\eta y_{i}$更新参数 $\omega与b$。
4. 重复执行2-3步骤，直到没有误分类的点。

伪代码：svg

def train(T,n):  #T为数据集，n为步长
    初始化w与b，通常w=0，b=0
    
    do:
        i = 0
        do：
            i += 1
            y = sign(wT·xi+b)
        while(yi·y<0 or i>len(T))
        
        if i <= len(T):
            w = w+nxiyi
            b = b+nyi
    while(i>len(T))
    
    return w,b

对偶形式

原理

$从最终结果考虑\omega与b的更新，表示以下：$
$\omega =\omega_{初始化}+\sum\limits_{i=1}^{n}\eta n_{i}y_{i}x_{i}=\omega_{初始化}+\sum\limits_{i=1}^{n}\alpha_{i}y_{i}x_{i}，\\n_{i}表示第i条记录用于更新\omega与b次数。$
$b=b_{初始化}+\sum\limits_{i=1}^{n}\eta n_{i}y_{i}=b_{初始化}+\sum\limits_{i=1}^{n}\alpha_{i}y_{i}，n_{i}表示第i条记录用于更新\omega与b次数。$
$决策函数能够变成y=sign(\omega^{T}x+b)=sign(\sum\limits_{i=1}^{n}\alpha_{i}y_{i}x_{i}x+b)，\alpha_{i}=\eta n_{i}，\\n_{i}表示第i条记录被用于更新模型的次数，这里要求\omega 与b为零初始化。$
$这样咱们就把更新\omega与b变为更新\alpha与b。$函数

学习流程

输入：训练集 $T=\{(x_{1},y_{1}),(x_{2},y_{2}),(x_{3},y_{3})\dots (x_{n},y_{n})\}，\eta(0<\eta \leq 1),y_{j}\in \{-1,1\}$。
输出： $\alpha_{j}, b$；决策函数 $y=sign(\sum\limits_{j=1}^{n}\alpha_{j}y_{j}x_{j}x+b)$
执行流程
1. $初始化\alpha_{j}=0,j=1\dots n，b=0。$
2. $从训练集中选择一个点(x_{i},y_{i})。$
3. $若是该点是误分类的点，则更新\alpha_{i}=\alpha_{i}+\eta，b=b+\eta y_{i}，\\可见b的更新同原始形式同样。$
4. $重复2-3直到没有点被误分类$。
因为在断定一个点是不是误分类的点时，会频繁用到内积 $<x_{i},x_{j}>$，因此能够构建一个矩阵保存内积结果，这个矩阵叫作Gram矩阵。学习

参考书籍：《统计学习方法》spa