Linear Discriminant Functions Precedure The Perceptron Algorithm
感知器模型 感知准则函数及梯度下降法
Least Squares Methods Support Vector Machines
The Perceptron Algorithm (cont.)
新内容
迭代过程为： ① 首先任意指定初始权向量w(0); ② 如果第k步不能满足 X T ( Xw(k ) b) 0，则按下式求第(k+1)步 的权向量w(k+1):
w(k 1) w(k ) rk (bk w(k ) xk ) xk
T
Widrow-Hoff算法
H-K(Ho-Kashyap)迭代算法
单样本修正法
rk rk0
Widrow-Hoff
批量样本修正——迭代算法
w1 , 任意初始值 T w ( k 1 ) w ( k ) X ( Xw(k ) b) k
新内容
迭代过程为： ① 首先任意指定初始权向量w(0); ② 如果第k步不能满足 X T ( Xw(k ) b) 0，则按下式求第(k+1)步 的权向量w(k+1):
e.g.,: t
c t
9
新内容
最小平方误差准则
问题： 一次准则函数及其算法（如感知器算法）：
适用于线性可分的情况
如果是线性不可分的，分类过程将不收敛
在实际问题中，往往无法事先知道源自式集能否线性可分。能否找到一种算法，使之能够
测试出模式样本集是否线性可分
并且对线性不可分的情况也能给出“次最优”的解
命名由来：这一准则函数是20世纪50年代由Rosenblatt
提出来的，试图用于脑模型感知器中，故一般称为感知 器准则函数。
5
新内容
The Perceptron Algorithm (cont.)
Gradient descent algorithm
The Cost Function
J (w*) min(J (w)) min( (w x))
如果方程组有唯一解，极小值点即是该解，说明训练模式集
是线性可分的；
如果方程组无解，极小值点是最小二乘解。在这里，最小二
乘的含义是对于给定的b，使J极小。在相当多的情况下等价 于误分模式数目最少。
MSE准则函数的伪逆解
2 2 N
新内容
MSE准则函数 J (W ) || e || || XW b || W X i bi min i 1
若b的某些分量取得不当，所求得的W可能不稳定
另b各分量选取不当也会影响收敛速度
新内容
批量样本及单样本修正法：余量b——常矢量
H-K(Ho-Kashyap)算法
H-K(Ho-Kashyap)迭代算法
新内容
H-K(Ho-Kashyap)迭代算法
MSE准则函数
新内容
H-K(Ho-Kashyap)算法
When Y=0 (empty set) a solution is achieved and
J ( w) 0
x 1 if x Y and x 1 x 1 if x Y and x 2

J ( w) 0
4
新内容
The Perceptron Algorithm (cont.)
T xY
梯度下降法，就是利用负梯度方向来决定每次迭代的新的
搜索方向，每次迭代能使待优化的目标函数逐步减小。梯 度下降法是2范数下的最速下降法。
最速下降法的一种简单形式是：x(k+1)=x(k)-a*g(k),其中a
称为学习速率，可以是较小的常数；g（k）是x(k)的梯度。
直观的说，就是在一个有中心的等值线中，从初始值开始，
MSE准则函数的迭代解
w*=X+b, X+=(XTX)-1XT，计算量大
实际中常用梯度下降法：
J(W) 2 W T X i bi X i 2 X T ( XW b) i 1
N
新内容


w0 , 任意初始值 批量样本修正法 T w ( k 1 ) w ( k ) X ( Xw(k ) b) k w0 , 任意初始值 T w ( k 1 ) w ( k ) r ( b w ( k ) xk ) xk k k
w(k 1) w(k ) k X ( Xw(k ) b)
T
可以证明：如果 k 1 / k ，其中 1 是任意正常数，则这个 算法产生的权向量序列wk，k=1,2,…,收敛于满足方程式 J(W) 0
单样本修正——迭代算法
w0 , 任意初始值 T w ( k 1 ) w ( k ) r ( b w ( k ) xk ) xk k k
1 X # ( X T X ) 1 X T 1 1 1 1 2 3 / 2 1 / 2 1 / 2 1 / 2
xY
J ( w) J ( w) ( x) w xY
(1)
The iteration formula is: w(t 1) w(t ) t J (w)

w(t 1) w(t ) t x
xY
Where Y is the subset of the vectors wrongly classified by w.

WTXi>0
引入余量(目标向量) b=[b1, b2, …, bN]T， bi为任意给定正 常数， WTXi = bi >0 N个线性方程的的矩阵表示：

WTXi=b
一般N>n，矛盾方 程组，没有精确解
最小平方误差准则
定义误差向量e=XW-b≠0
新内容
： 定义平方误差准则函数J(w):
2 2 N i 1
J (W ) || e || || XW b || W X bi i T



2
最小二乘近似解（MSE解）：
w* arg min ( J s (W ))
w
MSE方法的思想：对每个样本，设定一个“理想”的判别函 数输出值，以最小平方误差为准则求最优权向量
新内容
平方误差准则函数
每次沿着垂直等值线方向移动一个小的距离，最终收敛在 中心。
6
新内容
The Perceptron Algorithm (cont.)
Gradient descent algorithm
The Cost Function
w(t 1) w(t ) t * g (t )
T
J (w) (w x)
解决思路：对线性不可分样本集，求一解矢量使得错
分的模式数目最少
最小平方误差准则
新内容
规范化增广样本向量Xi，增广权向量w，正确分类要求：
wTXi>0, i=1,…,N 线性分类器设计求一组N个线性不等式的解w* 样本集增广矩阵X及一组N个线性不等式的的矩阵表示：
X 1 X 11 X 12 .... X 1n X 2 X 21 ... ... ... X ..... ... ... ... ... X N X N 1 X N 2 ... X Nn
Dr. Jing Bai baijing_nun@
Review
线性分类器的目标 基本步骤 预备知识 线性可分性 样本的规范化 解向量和解区 对解区的限制 感知器模型 感知器算法 两类问题(实例) 多类问题(实例)
复 习
2
Outlines
Introduction
2 2 N i 1
J (W ) || e || || XW b || W T X bi i


2
分析准则函数，W的优化就是使J(W)最小,称为MSE准则。 若WTXi=bi, (i=0,1,2,…,N) ，那么此时的J=min(J)=0； 若某些Xi有WTXi ≠ bi ，则J>0 。当b给定后，可以采用最 优化技术搜索极小值点以求解等式方程组WTXi=bi。
w(k) w(k+1) O w
8
梯度法的示意图
新内容
The perceptron algorithm converges in a finite
number of iteration steps to a solution if
lim k , lim k
2 t k 0 t k 0 t t
【 例 】 已 知 两 类 训 练 样 本 ： w1:(0,0)T,(0,1)T; w2:(1,0)T,(1,1)T,使用最小均方误差算法求解解向 0 0 1 1 量w*。 X 0 1 0 1 解 训练样本的增广矩阵： 1 1 1 1 e1的各分量均为0，则w(1)就是所求的解向量
T


2
对准则函数求导并令其为零，有
J(W) 2 W T X i bi X i 2 X T ( XW b) 0 i 1
N


解上方程得准则函数极小化的必要条件： XTXW=XTb
若( X T X ) 1 存在，w* ( X T X ) 1 X T b X b, X ( X T X ) 1 X T T 1 * T T T T 若 ( X X ) 不存在， w ( X X ) X b , ( X X ) 为 X X的广义逆矩阵
Our goal:
新内容
w x( )0 x
T
i j