第二章感知机

1、统计学习方法 李航目录2.1 2.1 感知机模型感知机模型2.2 2.2 感知机学习策略感知机学习策略 2.2.1数据集的线性可分性 2.2.2感知机学习策略2.32.3感知机学习方法感知机学习方法 2.3.1感知机学习算法的原始形式 2.3.2算法的收敛些 2.3.3感知机学习算法的对偶形式01 01 介介绍绍19571957年年RosenblattRosenblatt提出提出，是神经网络和支持向量，是神经网络和支持向量机的机的基础。基础。02 02 定定义义感知机是二分类的线性分类模型感知机是二分类的线性分类模型感知机模型如下：感知机模型如下：f(x)= sign(w*x+b)感知机感知机

2、的的几何解释几何解释：线性方程线性方程： 对应于特征空间对应于特征空间 中的一个超平面中的一个超平面S,S,其中其中w w是超平面的法是超平面的法 向量向量，b b是超平面的截距是超平面的截距。nR0w xb2.2 2.2 感知机学习策略感知机学习策略2.2.1 2.2.1 数据集的线性可分性数据集的线性可分性感知机原则上只能感知机原则上只能解决线性可分的分类问题。解决线性可分的分类问题。 数据数据集集T T T=(x1,y1)(x2,y2)(xN,yN)T=(x1,y1)(x2,y2)(xN,yN) if exist S: w if exist S: wx+b=0 x+b=0 将将数据数据集

3、完全正确划分集完全正确划分到超平面到超平面两侧两侧， 则可称数据集则可称数据集T T线性可分。线性可分。 2.2 2.2 感知机学习策略感知机学习策略2.2.2 2.2.2 感知机学习策略感知机学习策略所有误分类点到超平面所有误分类点到超平面s s的总距离：的总距离： （其中（其中M M为误分类集合）为误分类集合） 1()iiixMy w xbw2.3 2.3 感知机感知机学习学习算法算法Hypothesis: h(x) = sign(wx + b)Cost function: Goal: min L(w , b)( , )()iiixML w by w xb 2.3 2.3 感知机学习算法感

4、知机学习算法2.3.1 2.3.1 感知机学习算法的原始形式感知机学习算法的原始形式Stochastic gradient descent随机选取一个误分类点 update w, b: s.t. L 0( , )iiixML w by xw ( , )iixML w byb ( ,)arg()0)iiiix yy w xbiiiwwy xbby2.3 2.3 感知机学习算法感知机学习算法2.3.2 2.3.2 算法的收敛性算法的收敛性定理可以证明，误分类次数定理可以证明，误分类次数k k是有上界的，是有上界的，经过有限次搜索可以找到将训练集完全正经过有限次搜索可以找到将训练集完全正确分开的分离

5、超平面确分开的分离超平面。感知机学习算法存在很多解感知机学习算法存在很多解，需要对分离需要对分离超平面增加约束超平面增加约束条件条件。2.3 2.3 感知机学习算法感知机学习算法2.3.3 2.3.3 感知机学习算法的对偶形式感知机学习算法的对偶形式不失一般性，假设不失一般性，假设w w 和和b b 初始值均为初始值均为0 0。 对误分类对误分类点点 通过通过if update n : 最后学习到的最后学习到的w w，b b可以表示为可以表示为 ( ,)iix yiiiwwy xbbyiiiwy xiiby ()iin其中1niiiiwa y x1niiiba y2.3 2.3 感知机学习算法感知机学习算法感知机模型：感知机模型：Step1: Step1: 首先置首先置Step2: Step2: 在训练集中选取在训练集中选取Step3: Step3: 转向转向2 2直到没有误分类点。直到