模型

机器学习中，感知机（perceptron）是一种二值的监督学习的算法（相应的函数，能决定输入是否属于某个分类，其中输入由一个数值向量表示）。感知机是一个线性分类器，其分类函数基于线性预测函数对新的输入作出预测，即，将输入（实数向量）映射到{-1，1}二值空间：

f(x)=sign(wx+b)

其中，sign是符号函数

wx是w向量与x向量的内积，w向量与x向量均为n维，分别为如下形式

w=[w¹,w²,...,wⁿ]

x=[x¹,x²,...,xⁿ]^T

不难发现，f(x)是n+1维欧氏空间的超平面，n维空间中的点被f(x)分为两部分（即两类），为了方便计算和表示，我们增加一个维度，使得b = w⁰x⁰, 其中x⁰=1，并且将w也写成列向量形式，则有，

其中，w=[w⁰,w¹,w²,...,wⁿ]^T

感知机学习的目的就是要找到一个perceptron，能把不同类别的点区分开来，具体来说就是，由训练数据集

T={(x₁,y₁), (x₂,y₂), ... , (x_N, y_N)}

其中N表示有N个数据，x_i属于n+1维实数空间向量，yi属于{1, -1}，求n+1维向量w

 当然，这里需要有一个前提条件，训练数据要线性可分（比如如下图中的数据就不能线性可分）

 （n+1=3，假设圈圈表示y值为1，叉叉表示y值为-1，图中三点一线，线性不可分）

线性可分是指：

如果存在某个超平面w^Tx=0，对数据集中所有y_i=1的数据，w^Tx_i>0，对所有y_i=-1的数据，w^Tx_i<0，则这个数据集线性可分

学习策略

定义（经验）损失函数（参数为w），并设法将损失函数极小化，比如损失函数为误分类点的个数，然后极小化为0，则就是找到一个符合要求的超平面。巴特，这样的损失函数不是关于w连续可导，不容易找。

如果选择损失函数为误分类点到超平面的总距离，那么当误分类点为0时，总距离也为0，分类正确。

输入空间一点x到超平面的距离为

 其中，||w||为w的L2范数，然后，对于误分类点来说，距离则为

 因为对于误分类点，y值与w^Tx符号相反，所以需要加个负号，股损失函数为误分类点总距离，假设误分类点集合为SetM，则，

对于上式右边括号中的部分，我们可以认为分母是为了让w^T归一化，而我们目的也是为了让SetM最终为空集合，从而使L为0，所以这里分母并没有什么影响，为了简单起见，这里将分母去掉，

其中，SetM是误分类点集合，x_i为n+1维列向量，w为n+1维列向量，y_i为{1,-1}中的某个标量值，可以看出，误分类点越少，L越小，误分类点离超平面越近，L越小。当SetM为空集合（没有误分类点）时，L = 0，存在

误分类点时，在误分类点一定的情况下，L是w的线性函数。

学习算法

 采用随机梯度下降法，这是因为只有误分类的点参与优化w，优化过程中，一次选择一个误分类点使其梯度下降。

损失函数对w的偏导数为

这是一个与x_i一样的n维列向量，则针对某一个误分类点的梯度下降的优化为，

w← w + ay_ix_{i 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（*）}

其中 + 号表示梯度下降，a表示步长，范围为(0,1]，y_i为第i个点的分类值（1，或者-1）。

还记得前面说的那个超平面的截距b吗？b其实就是这里的w⁰,因为x⁰=1，故

b←b + ay_ix_i⁰ = b + ay_i

当然了，这里b作为w的第0个分量，没必要单独列出来优化。

算法：

输入：训练数据集{(x₁,y₁), (x₂,y₂), ... , (x_N, y_N)}，对某个数据点(xi,yi)，检测条件 yiwxi > 0 是否满足，如果不满足表示是误分类点，则进行优化

输出：w 值

1. 选择w初值，比如n+1维零向量[0,0, ... , 0]^{T ，}，补偿a选择1
2. 遍历训练集：

   a) 当(x_i, y_i)， y_iwx_i <= 0，则使用上面的（*）式对w进行优化，注意，xi的第0维值始终为1

   b) 如果优化后依然y_iwx_i <= 0，则继续a)，直到 y_iwx_i >0， 设置标志位flag 为true，表示有误差点

3. 继续check (x_i+1,y_i+1), 如果不满足检测条件，则跳到2.a)步骤进行优化，否则继续检测 i + 2 的数据点。如此一直到训练集遍历结束
4. 检测flag是否为true，如果为true，则跳至2步骤执行，否则退出

当然了，由于实际应用中，往往训练数据的x 是n维，可以将b 独立出来优化计算。

感知机