读书笔记：感知机

宏观层面

感知机(Perceptron)是有监督的、二分类模型，属于判别模型因为直接利用决策函数$y=f(x)$进行判断，不涉及联合概率分布学习。它对+1和-1两个类别进行判断。

该算法解决什么问题？

感知机主要用于解决线性可分数据集的分类问题。线性可分数据集是指能够找到一个超平面，完全正确的将数据集分割在该超平面的两侧。

算法基本思想和原理是什么？

感知机根据输入的实数特征向量，通过特征加权和来判断最终结果。

$f(x) = sign(\sum_i^nWX_i + b)$

这里，$X$是特征向量，可能是m维，$sign$是指示函数，

$sign(g)=\{_{-1, g < 0}^{+1, g >=0}$

个人理解是什么？

感知器是模拟人类神经元的形式而设计的算法，它是人工神经网络(ANN)的基础，只不过这里的激活函数比较特殊为指示函数。

微观层面：

公式详细推导过程是否领会和记忆？

根据书中定义，感知器的函数形式如下：

$f(x) = sign(w\cdot x + b)$

这里，$w,x$均是向量。
为了能够对该算法进行训练学习，需要设计目标函数，且目标函数需是参数$w,b$的函数，因此这里选择错误分类点到平面的距离总和。点超平面的距离距离为：

$d = \frac{1}{||w||_2}|w\cdot x + b|$

所谓误分类点，对于正例来说，错误分类时它在平面下方$f(x)<0$，距离为$-d$，对于负例，错误分类时它在平面上方$f(x)>0$，距离为$+d$，总结而言即预测结果$f(x_i)$和真实值$y_i$异号，距离为$-y_i(w\cdot x_i + b) > 0$.

记录书中的算法原始形式

输入：选了数据集$T=\{(x_1, y_1),(x_1, y_1),\cdots, (x_N, y_N) \}$,其中，$x$为实向量，$y={-1, +1}, i=1,2,3,\cdots,N$, 学习率为$\eta$;
输出:$w,b$,感知器模型$f(x)=sign(w\cdot x+b)$
(1) 选取初始值$w_0, b_0$
(2) 在训练集中选取样本$(x_i, y_i)$
(3) 如果分类错误，即$y_i(w\cdot x_i + b) \leq 0$,
$w \leftarrow{w}+\eta{y_ix_i} \\ b \leftarrow{b} + \eta{y_i}$
(4) 转至(2),直到训练集中没有错误分类。

算法优化目标

对于一个具有$M$个点的数据集，所有错误分类点的总距离和如下，

$-\frac{1}{||w||_2}\sum_{i=1}^{M}y_i(w\cdot x_i + b)$

由于$||w_2||$为具体数值，因此可以进行舍去，则得到感知器模型的损失函数,

$L(w,b)=-\sum_{i=1}^{M}y_i(w\cdot x_i + b)$

优化的目标是使得损失函数最小，而优化的方式是采用GD下降算法，让loss沿着梯度下降的方向进行减少。损失函数对其中的参数求偏导得到梯度，

$\frac{\partial{L(w,b)}}{\partial{w}}=-\sum_{i=1}^My_ix_i \\ \frac{\partial{L(w,b)}}{\partial{b}}=-\sum_{i=1}^{M}y_i$

对于一个特定点$(x_i, y_i)$，对$w,b$进行更新公式为，

$w \leftarrow{w}+\eta{y_ix_i} \\ b \leftarrow{b} + \eta{y_i}$

$\eta$为学习率。

这个学习过程，直观的理解为，当一个点被错误分类时，即它位于分类超平的另一侧，通过调整$w,b$使超平面向这个点所在的一侧进行移动，减少该误分类点到平面的距离。(SVM中也存在这个过程，不断的移动超平面，但是移动有个限度，即最大分类间隔)

对偶形式

书中提到了感知器算法的对偶形式，该方式支持向量机及其对偶形式相对应，这里做个记录。
对偶形式的思想是将参数和变量进行互换，将$w,b$表示为$x_i, y_i$的线性组合形式，通过求解其系数，等到$w,b$。根据之前的更新规则，设$w,b$修改了$n$次，则对于$(x_i, y_i)$的增量为

$\Delta w = n_i\eta{y_ix_i} \\ \Delta b =n_i\eta{y_i}$

令$\alpha_i=ni_i\eta_i$,则增量表示

$\Delta w = \alpha_i{y_ix_i} \\ \Delta b = \alpha_i{y_i}$

则最后学习到的$w,b$为：

$w = \sum_{i=1}^{N}\alpha_i{y_ix_i} \\ b = \sum_{i=1}^{N}\alpha_i{y_i}$

$\alpha_i \geq 0, 当\eta=1$时，表示第$i$个实例点由于误分类而进行修改的次数，更新次数越多，意味着它距离超平面越近，越难被正确分类，对学习结果影响越大。(试想，什么样的点会被频繁更新，为什么频繁更新，因为经常被分错，什么情况下的点会经常被分错，就是超平面一动就被分错，说明什么，这个点离平面很近，平面一动就跑到了对侧，这种点在SVM中被称作支撑向量！)
上述的过程，其实是在说，对于每个参数的更新，可以通过考虑增量的形式来进行转换。
感知器学习算法对偶形式

输入：选了数据集$T=\{(x_1, y_1),(x_1, y_1),\cdots, (x_N, y_N) \}$,其中，x为实向量，$y={-1, +1}, i=1,2,3,\cdots,N$, 学习率为$0 < \eta \leq 1$;
输出:$\alpha ,b$,感知器模型$f(x)=sign(\sum_{j=1}^N\alpha_jy_jx_j\cdot x+b), \alpha = (\alpha_1, \alpha_2, \cdots, \alpha_N)^T$,
(1) 选取初始值$\alpha \leftarrow{0}, b \leftarrow 0 $
(2) 在训练集中选取样本$(x_i, y_i)$
(3) 如果分类错误，即$y_i(\sum_{j=1}^N\alpha_j y_jx_j\cdot x_i + b) \leq 0$,(对$\alpha_i,b$求偏导，前者剩余)
$\alpha_i \leftarrow{\alpha_i}+\eta \\ b \leftarrow{b} + \eta{y_i}$
(4) 转至(2),直到训练集中没有错误分类。

对偶中出现了<$x_j,x_i$>内积的形式，这其实就是一种核函数运算，可以事先计算出来并以矩阵的形式存储，这个矩阵称作Gram矩阵。

关于感知器对偶形式的深入讨论，可以参考文献1

优缺点是什么？

优点：

模型简单
训练速度快
对线性可分数据集可以快速构建baseline

缺点：

只能处理线性可分问题，对于非线性或线性不可分则不好(线性不可分，可以采用多层，或NN)

应用层面

算法的使用场景或任务有哪些？

感知器常用于简单分类场景，实际工作中暂时未使用过。

问题思考

感知机损失函数为什么不定义为误分类点总数？

如果损失函数定义为误分类点的总数，则损失函数不是参数$w, b$的连续可导函数，不容易进行优化，因此将误差函数定义为错误分类点到超平面的距离。
感知器为什么不能表示异或？
样本集线性可分的充分必要条件是正实例点集所构成的凸壳和负实例点集构成的凸壳不相交。
感知机学习结果是否唯一？

感知机学习结果不唯一，它即依赖于初始值选择，也依赖于更新时选择样本的顺序，因此如果希望得到唯一超平面，需要添加约束条件。

参考文献

感知器对偶形式讨论