感知机

感知机（perception）是一种二类分类的线性分类模型
输入：实例的特征向量
输出：实例的类别（+1，-1）
感知机：输入空间中将实例划分为正负两类的分离超平面，属于判别模型
感知机学习
目的：求出将训练数据进行线性划分的分离超平面
方法：导入基于误分类的损失函数，利用梯度下降法对损失函数进行极小化，求得感知机模型

2.1感知机模型
感知机：

$f(x)=sign(w⋅x+b)$

其中：w为权值（或权值向量weight vector, b为偏值（bias）,sign为符号函数

$ f(n)= \begin{cases}+1, & \text {n>=0} \ -1, & \text{n<0} \end{cases} $

2.2感知机学习策略
数据集线性可分：存在某个超平面S能够将数据集T的正负实例点完全正确地划分到超平面的两侧，即：
对所有yi=+1的实例，有w⋅xi+b>0
对所有yi=−1的实例，有w⋅xi+b<0
则称数据集T为线性可分数据集。
损失函数的选择：
1：误分类点总数，该函数不是参数w，b的连续可导函数，不易优化
2：误分类点到超平面S的总距离

损失函数是非负的，如果没有误分类点，损失函数值为0。

误分类点越少，误分类点离超平面越近，损失函数值就越小，损失函数是w，b的连续可导函数。

2.3感知机学习算法
原始形式、对偶形式

随机梯度下降法：
任意选取一个超平面w0,b0,利用梯度下降法不断极小化目标函数（极小化的过程是一次随机选取一个误分类点使其梯度下降）
随机选取误分类点(xi,yi),对w，b进行更新：（随机梯度下降）

原始形式：

每来一个样本 (xi,yi)，计算若yi(w⋅xi+b)≤0，

说明误分了，要用梯度下降：
1
2
3
4
5
w=w+ηyixi

b=b+ηyi

其中，η(0<η≤1)为步长（学习率）
更新权重 w,b

若大于0，说明分类正确，不用管。这样直到遍历整个样本都没有误分点，算法停止。通过迭代可使损失函数 L(w,b) 不断减小，直至0

通过观察上面梯度下降的更新公式，发现参数 w 最终的取值，其实是初值（初值为0可以忽略）加上每个样本的某个整数倍（其实就是分错的次数）

$$\begin{cases} w = \sum_{i=1}^{N}\alpha_iy_ixi \b = \sum{i=1}^{N}\alpha_iy_i \end{cases}$$

其中，$\alpha_i$≥0, i=1,2,…,N 表示每个样本点在更新过程中被误分类的次数。从 α 中我们还可以看出来，若该值越大，则说明对应的样本点被误分的次数越大，也就离超平面越近，因此难分类。

判断是否属于误分点时，我们用公式$yi(\sum{j=1}^n\alpha_jy_jx_j⋅x_i+b)≤0$来判断。对比之前的 w,b 版本，其实只是把 w 用 α代替而已。注意后面的点乘，即内积，我们可以先事先计算好并存储在Gram矩阵中$（G=[x_i⋅xj]{N×N}）$，以减少实时计算量。