1、感知机和统计学习方法总结 感知机(Perceptron) 输入为实例的特征向量，输出为实例的类别，取+1和-1； 感知机对应于输入空间中将实例划分为正负两类的分离超平面，属于 判别模型； 导入基于误分类的损失函数； 利用梯度下降法对损失函数进行极小化； 感知机学习算法具有简单而易于实现的优点，分为原始形式和对偶形 式； 1957年由Rosenblatt提出，是神经网络与支持向量机的基础。 感知机模型 定义(感知机): 假设输入空间(特征空间)是 ，输出空间是 输入 表示实例的特征向量，对应于输入空间（特征空间）的 点，输出 表示实例的类别，由输入空间到输出空间的函数： 称为感知机， 模型参数：
2、w x，内积，权值向量，偏置， 符号函数： 感知机模型 感知机几何解释： 线性方程： 对应于超平面S，w为法向量，b截距，分离正、负类： 分离超平面： 感知机学习策略 如何定义损失函数？ 自然选择：误分类点的数目，但损失函数不是w,b 连续可导，不宜优化。 另一选择：误分类点到超平面的总距离： 距离： 误分类点： 误分类点距离： 总距离： 感知机学习策略 损失函数： M为误分类点的数目 感知机学习算法 求解最优化问题： 随机梯度下降法， 首先任意选择一个超平面，w，b，然后不断极小化目标函数,损 失函数L的梯度： 选取误分类点更新： 感知机学习算法 感知机学习算法的原始形式： 感知机学习算法
3、例：正例： 负例： 感知机学习算法 解：构建优化问题： 求解：w，b ， 得线性模型： 感知机学习算法 得到线性模型： 如此继续下去： 分离超平面： 感知机模型： 感知机学习算法 算法的收敛性：证明经过有限次迭代可以得到一 个将训练数据集完全正确划分的分离超平面及感 知机模型。 将b并入权重向量w，记作： 定理： 感知机学习算法 则 感知机学习算法 证明: (1) 由线性可分, 存在超平面： ,由有限的点，均有： 存在 使： 感知机学习算法 算法在训练集的误分类次数k满足不等式 , 证明：令 是第k个误分类实例之前的扩充权值向量，即： 第k个误分类实例的条件是： 则w和b的更新： 即： 感知机
4、学习算法 算法在训练集的误分类次数k满足不等式 , 推导两个不等式: (1) 由： 得： 感知机学习算法 感知机算法在训练集的误分类次数k满足不等式 , (2) 则： 感知机学习算法 感知机 算法在训练集的误分类次数k满足不等式 , 结合两个不等式： 得： 感知机学习算法 定理表明： 误分类的次数k是有上界的，当训练数据集线性可 分时，感知机学习算法原始形式迭代是收敛的。 感知机算法存在许多解，既依赖于初值，也依赖 迭代过程中误分类点的选择顺序。 为得到唯一分离超平面，需要增加约束，如SVM。 线性不可分数据集，迭代震荡。 感知机学习算法 感知机算法的对偶形式： 回顾 SVM 对偶形式： 基本想法： 将w和b表示为实例xi和标记yi的线性组会的形式， 通过求解其系数而求得w和b，对误分类点： 感知机学习算法 感知机学习算法的对偶形式： 感知机学习算法 感知机学习算法 例： 感知机学习算法 例： 统计学习方法总结 感知机 K近邻法 朴素贝叶斯 决策树 逻辑斯蒂回归与最大熵模型 支持向量机 提升方法 EM算法 隐马尔科夫模型 条件随机场 END Q&R
