接学习笔记|感知机（一） 。

6. 感知机学习算法

感知机学习的具体算法包括原始形式和对偶形式。

6.1. 感知机学习算法的原始形式

6.1.1. 简述

感知机学习算法等价于以下最优化问题的算法。

给定一个训练数据集

其中M为误分类点的集合。

给出。

随机选取一个误分类点，对ω,b进行更新：

其中，η∈(0,1]是步长，又称学习率。

6.1.2. 算法

输入：训练数据集

，其中，，i=1,2,...,N，学习率η∈(0,1]；
输出：&omega,b；感知机模型f(x)=sign(ω⋅x+b)。

学习过程：

6.1.3 算法收敛性

定理（Novikoff） 设训练数据集是线性可分的，其中，，i=1,2,...,N，则
（1）存在满足条件的ω的超平面ωω将训练数据集完全正确分开；且存在γ>0，对所有i=1,2,...,N

（2）令，则感知机算法在训练数据集上的误分类次数k满足不等式

所以存在

使

则第k个误分类实例的条件是

定理表明，误分类的次数k是有上界的。

6.2 感知机学习算法的对偶形式

6.2.1. 简述

6.2.2. 算法

输入：线性可分的数据集，其中，，i=1,2,...,N；学习率η(0<η≤1)；

输出：α，b；感知机模型f(x)=sign(α)，其中α=ααα。

学习过程：
（1）α←0,b←0；
（2）在训练集中选取数据；
（3）如果≤0，

（4）转至（2）直到没有误分类数据。

对偶形式中训练实例仅以内积的形式出现。为了方便，可以预先将训练集中实例间的内积计算出来以矩阵的形式存储，这个矩阵就是所谓的Gram矩阵