统计模式识别——各种各样的线性分类器（2）

1.感知器

概念

感知机算法是错误驱动的在线学习算法。首先初始化一个权重W0、截距b,然后每次分错样本时，就用这个样本改变权重以及截距b。其实就是构造了一个分类超平面。感知器用来解决线性可分样本集分类问题。

线性可分性

线性可分性：若训练样本集可以被某个线性分类器完全正确分类，则该样本集是线性可分的。即如果样本集是线性可分的——则至少存在一个权向量，能将该样本集中的每个样本都正确分类。

问题描述

已知：

1. L=2，M维分类问题的样本集

2. 该样本集是线性可分的

求解：能够对样本集正确分类的解（某个线性分类器）

样本集的规范化

感知器采用增广向量的形式，增广形式的判别函数为：g(x) = aTy；

对于未知样本x，若g(x) > 0，则x决策为ω1类若g(x) < 0，则x决策为ω2类；

规范化：对ω2类样本的增广向量全部乘以-1；

规范化之后的分类结果：

aTyi> 0——正确分类

aTyi< 0——错误分类

解向量和解区

解向量——能将线性可分样本集中的每个样本都正确分类的权向量；

解区——解向量往往不是一个，而是由无穷多个解向量组成的（角度）区域，称为解区。

感知准则函数

对于权向量a，如果某个样本yk被错误分类，则。我们可以用对所有错分样本的求和来表示对错分样本的惩罚：

其中Yk是被a错分的样本集合。当且仅当JP(a*) = min JP(a) = 0 时，a*是解向量。这就是Rosenblatt提出的感知器（Perceptron）准则函数。

采用梯度下降法求优化准则函数极值（极小值）

其中，k为迭代次数，η为调整的步长。即下一次迭代的权向量是把当前时刻的权向量向目标函数的负梯度方向调整一个修正量。

因此，迭代修正的公式为：

即在每一步迭代时把错分的样本按照某个系数叠加到权向量上。

感知准则（分类器）的特点：

1. 解决两类问题的线性分类器
2. 样本集必须是线性可分的
3. 采用感知准则函数求极值解（最优决策）

4. 分类器设计过程复杂

2. 最小平方误差准则

问题提出

感知器只能解决线性可分的问题，而工程实际中的问题不一定都是线性可分问题，对于线性不可分问题，工程上往往是求误差平方和最小。

数学描述

引入余量bi，将不等式组改造为等式组aTyi= bi > 0(i = 1,…,N)；

求解：满足等式组的最小平方误差解（权向量）；

优化准则函数

优化求解

求梯度：

令梯度为零得：

极值解为：

最小平方误差准则（分类器）的特点

1. 解决两类问题的线性分类器
2. 样本集不限，可以是线性不可分的
3. 求最小平方误差的权向量（最优）
4. 分类器设计过程相对简单