统计学习——感知机（超详细）
1. 感知机原理
感知机是一个二类分类模型，输入为实例的特征向量，输出为实例的类别，取值为+1和-1。
定义1-1：数据的线性可分性
假设训练数据集是线性可分的，感知机学习的目标是求得一个能够将训练数据集正实例点和负实例点完全正确分开的分离超平面。如果是非线性可分的数据，则最后无法获得超平面。
2. 感知机模型
3. 感知机的学习策略
为了找出可以将数据集完全正确分开的分离超平面，为了找出这样的超平面，即确定感知机模型参数w，b，需要确定一个学习策略，也就是定义一个经验损失函数并将损失函数极小化。
损失函数可以由误分类点的总数来确定，但是由点的数量确定的损失函数不是模型参数的连续可导函数，不易用梯度下将的方法来进行优化。
因此感知机的损失函数是误分类点到超平面S的总距离
3.1 输入空间任意一点X0到超平面S的距离
输入空间中任意一点X0到超平面S的距离为：
证明
3.2 感知机的损失函数
这个损失函数就是感知机学习的经验风险函数。
损失函数L(w,b)是非负的，如果没有误分类点，损失函数值是0，而且，误分类点越少，或误分类点离超平面越近，损失函数就越小。对于一个特定的样本点来说，如果当前的感知机模型对这个样本点的分类是错误的，那么这个样本点的损失函数是参数w，b的线性函数，如果当前感知机模型对这个样本点的分类正确，那么这个样本点的损失函数是0。因此，对给定的数据集，损失函数L（w，b）是w，b的连续可导函数。
3.3 为什么在损失函数中忽略1/||w||
个人理解是这样的：
1/||w|| 是不影响感知机的最终学习结果的。因为感知机的学习终止学习条件是训练数据集中没有误分类点，这是损失函数的值为0，分子为0，因此1/||w||不影响最终的损失函数为0的。
4. 感知机学习算法
感知机学习问题就转化为了求损失函数的最优化（极小化）问题，方法是随机梯度下降法。
4.1 随机梯度下降法
式子中η（0<η<=1）是每次调整的步长，又称学习率。这样通过迭代，可以是损失函数L(w,b)不断减小，直至为0。
4.2 感知机学习算法的原始形式
找误分类点的时候，不是遍历一遍训练集即可，而是要反复遍历，直到数据集中没有误分类点。
4.3 感知机学习算法的对偶形式
对偶形式的基本想法是，将损失函数的参数w和b表示成训练集中的实例Xi和标记Yi的线性组合形式。通过求解组合的系数来求解具体的w和b。不失一般性，假设原始算法中的参数的初始值为W0和B0。对于误分类点通过：
来逐步修改参数w和b。
假设从开始到学习终止，w和b一共学习了n次（对于训练集中的某一个实例点，其作为误分类点的次数可能不止一次，设为ni，0<=ni<=n）。
感知机学习算法的具体过程如下：
4.4 原始形式和对偶形式的选择问题
- 在特征向量的维数过高时（每一个向量有很多特征），选择对偶形式算法加速。
- 当样本数过多时，选择原始算法。
5. 原始算法的收敛性
收敛：对于一个特定的数据集来说，感知机的学习算法，一定能经过有限次的迭代找出一个超平面，将数据集中的数据完全地正确分开。
感知机的的学习算法可以得到许多解，解既依赖于参数处置的选择，也依赖于迭代规程中误分类点的选择顺序。
为了得到唯一的超平面，就需要对分离超平面增加约束条件，即线性支持向量机。
当训练数据集不可分时，感知机学习算法并不收敛，迭代结果会发生震荡。
其具体的证明过程参见李航老师的统计学习方法。