统计学习方法 李航-第2章 感知机
统计学习方法 李航---第2章 感知机
第2章 感知机
感知机(perceptron)是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和-1二值。感知机对应于输入空间(特征空间)中将实例划分为正负两类的分离超平面，属于判别模型。
感知机学习旨在求出将训练数据进行线性划分的分离超平面，为此，导入基于误分类的损失函数，利用梯度
下降法对损失函数进行极小化求得感知机模型。
2.1 感知机模型
定义(感知机)：假设输入空间(特征空间)是X--Rn，输出空间是 Y={+1,-1}.输入x属于X表示实例的特征向量，对应于输入空间（特征空间）的点;输出y属于 Y表示实例的类别。由输入空间到输出空间的如下函数
f (x)=sign(w*x+b)
其中，w和b为感知机模型参数，w叫作权值(weight)或权值向量(weightvectot) b叫作偏置(bias).
感知机是一种线性分类模型，属于判别模型.感知机模型的假设空间是定义在特征空间中的所有线性分类模型(linear classification model)或线性分类器(linear classifier)。
感知机是一种线性分类模型，属于判别模型.感知机模型的假设空间是定义在特征空间中的所有线性分类模型(linear classification model)或线性分类器(linear classifier)。
2.2 感知机学习策略
数据集的线性可分性：如果存在某个超平面S: w*x+b=0能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧，则称数据集为线性可分数据集(linearly aeparahle data sec);否则，称数据集线性不可分。
感知机学习策略：为了找出这样的超平面，即确定感知机模型参数w,b。需要确定一个学习策略，即定义(经验)损失函数并将损失函数极小化。
损失函数：误分类点到超平面S的总距离。
2.3 感知机学习算法
感知机学习问题转化为求解损失函数的最优化问题，最优化的方法是随机梯度下降法.感知机学习的具体算法包括原始形式和对偶形式。
感知机学习算法的原始形式：
损
失函数极小化问题
采用随机梯度下降法(( stochastic gradient descent)。
感知机学习算法由于采用不同的初值或选取不同的误分类点，解可以不同
算法的收敛性：
定理2.1 (Novikoff) 设训练数据集T =｛(x1,y1),....,(xN,yN)｝是线性可分的，则
(1) 存在满足条件||w^opt||，的超平面将训练数据集完全正确分开：且存在 r>0，对所有i=1,2,...,N
(2) 令R=max||xi||，则感知机算法2.1在训练数据集上的误分类次数k满足不等式，
定理表明，误分类的次数k是有上界的，当训练数据集线性可分时，感知机学习算法原始形式迭代是收敛的。但是感知机学习算法存在许多解，这些解既依赖于初值的选择，也依赖于迭代过程中误分类点的选择顺序。当训练集线性不可分时，感知机学习算法不收敛，迭代结果会发生震荡。
感知机学习算法的对偶形式：
对偶形式的基本想法是：将w和b表示为实例xi和标记yi的线性组合的形式，通过求解其系数而求得w和b。
设初始值为0，N次更新后为：
对偶形式中训练实例仅以内积的形式出现。为了方便，可以预先将训练集中实例间的内积计算出来并以矩阵的形式存储，这个矩阵就是所谓的Gram矩阵( Gram matrix )