P P Y k
将上式代入迭代式，可得
a(k 1) a(k) Y
k Y k
式中 k 是当第k步迭代，用a(k)来分类时被误分类的样本集。
解释：
这种寻找解权向量的梯度下降法可描述为： 将被a(k)误分类的样本之和并与某个系数
的乘积之后，
k
再加上第k次的权向量a(k) ，即为第（k+1）次的权向量。 可证得，对于线性可分的样本集，经过有限步，一定可找 到一个解向量a*，即算法在有限步内收敛，其收敛速度取决于 初始权向量a(1)和系数 。
⑤ 函数 J (a) 在某点ak的梯度 [ J (a )] 是一个向量，它的方向
P
P k
与过点ak的等量面 J (a ) C 的法线方向重合，指向 J (a )
P k P k
增加的一方，是准则函数变化率最大的方向；反之，负梯
度的方向则是 J (a) 减少得最快的方向。
P
⑥ 所以，在求 J (a) 的极小值时，沿负梯度方向搜索有可能
P
最快地找到极小值。（梯度下降法的基本思想）。
⑦ 梯度下降法的实现
先任意给定一个初始权向量a(1)，计算a(1)上的梯度
▽[ JP ( a(1) ) ]，从a(1)出发在最陡方向（即负梯度方向）上
移动一个距离以得到下一个权向量值a(2)，反复下去，经过有
限步循环，就可找到解向量a*，其迭代算法如下：
建立二次准则函数，然后运用最优化技术求解权向量a。
如果Y是非奇异矩阵，则可得解a=Y-1b，但这在大多数情况
ˆ (即 下是不可能的，因为一般情况，样本数N总是大于维数d
N>d ˆ )，因此，Y是长方阵(即行数>列数)，也就是说，方程式数 大于未知数的数目，这是一个矛盾方程组，对其通常没有精确
将上述不等式组写成矩阵形式，另外为使解可靠，引入N维
余量向量 b > 0，则不等式组可写成：
Ya ≥ b > 0
ˆ 符号规范化增广样本矩阵,a是 d ˆ ×1权向量,bN×1。 其中,Y是N×d
针对我们的目标，由上式可定义如下准则函数（是一个分段 二次函数）： Jq1(a) =‖(Ya - b) -︱Ya – b ︳‖2 →说明yn能被正确分类。
如果样本集是非线性可分的，表明不存在a使所有的样本被 正确分类，即无论任何的a都有某些样本被错分。这时上述不等 式组不能成立，即不等式组是不一致的。不等式组无解。这时必 有某些样本被错分类。因此，我们的目标应是所求得的权向量a
使尽可能多的不等式被满足，即使最少的样本被错分。
aTYn>0
aTYn≥b
b/‖Yn‖
二. 感知准则函数及其梯度下降算法
1. 问题描述
设有一组d维样本Y1,…,YN，其中 Yn是规范化增广样本向量。
现在的问题是：找一个解向量a*，使得
aTYn>0 , (n=1,2,· · · · · · ,N)
为了解此线性不等式组，需构造一个准则函数：
J (a) (a Y)
多个解向量组成的区域（该区称为解区）。
对于二维问题，可看下图（书图4.5）。
解区
解区 解向量
． ． ． ．． ． 。
。
□ □
□ □
． ． ． ．． ． 。 。
解向 量
分界面
分界面
○：第一类样本 □：第二类样本 （a）未规范化 （b）规范化

5. 对解区的限制
目的是：使解向量更可靠。 一般，越靠近解区中间的解向量，越能正确分类。 所以，引入余量 b > 0 。 使 而 aTYn≥b 的解向量即为限制后的解向量。 aTYn≥b＞0 所产生的新解区位于原解区之中。
说明：• 如果 Ya > b，则 (Ya - b) 与︱Ya - b︳的各分量分别对
应相等，则 Jq1(a) = 0。
• 如果有某些yi分量不满足aTyi>bi，则分量( aTyi-bi ) 和 ︳aTyi - bi︱异号，则 Jq1(a) > 0。
显然，不满足不等式的（增广）样本yi数目越少，则Jq1(a)
4.3 感知准则函数
一.几个基本概念
1. 线性可分性
含义：若存在一个权向量a(即直线)，能将样本集按类分开， 则称之为是线性可分的。
定义：设有d维N个样本的样本集X1,X2· · · · · · Xn，且分别来自ω1
和ω2类。其线性判别函数为：
WTXi+W0
其中
WT=[W1,· · · ,Wd]，
3. 样本的规范化
若样本集Y1,· · · ,YN是线性可分的，则必存在某个/些权向量a，使得 若 aTYi > 0 则Yi∈ω1； 若 aTYj<0 则Yj ∈ω2 。
若令Yj′= -Yj，则上式可写为： aTYn′> 0 其中 Yi 样本的规范化式
Yi∈ ω1 Yj∈ ω2
Yn′=
-Yj yn′代表全部样本，其称为规范化增广样本向量。 现在的问题：只要找到满足aTYn′> 0 的权向量aT就行(n=1,…,N).
a(k 1) a(k) - [ J (a(k))]
k P
式中 k 是一个正的比例因子，称为步长或增量。
２. 求使JP(a)达到极小值的解权向量a*
因为 JP(a)的第k个梯度分量是
J (a ) a(k)
P
现在将JP(a)式对a求梯度，这是一个标量函数对向量的求导，
得如下式
J (a ) J (a) (-Y) a(k)
T P Y k
k
感知准则函数
式中 是被（增广）权向量a错分类的样本集合。
(因为当样本Y被错分类时，有aTY0 或 -aTY 0，此时 J (a) 0 )
P
说明： ① J (a) 是解权向量a的函数。
P
② 当且仅当 为空集时，即 时，J P (a)达到极小值。
k
k
即
J (a) min J (a) 0
注意：• H ˆ n的法向量为Yn。
• N个样本将产生N个超平面。
(4) 解向量如果存在，则必在 H ˆ n的正侧（因为只有正侧时才满 足aTYn>0）。
(5) 解区：由于每个超平面把权空间分为两个半空间，所以解向
量如果存在，必在N个正半空间的交迭区，而且该区中的任
意向量都是解向量。因此解向量往往不只一个，而是由无穷
就越小。
所以，使Jq1(a)取最小值时的a为最优解a*。 并且在样本集是线性可分时，即不等式组一致条件下，必
ˆ h 有Jq1(a*) = 0，即表明用a*构造的判别函数对所有样本均能正确
分类。 而在样本集是线性不可分时，即不等式组不一致条件下，
有Jq1(a*) > 0，但a*使误分样本数最少，我们称Jq1(a)为最小错 分样本数准则。
k =1，有3个样本在三维下的样本序列为： 例如：设a(1)=0，
y ˆ
1 2 1
y ˆ
2
y ˆ
3
y y ˆ
3 4
1
y y y y

2
y ˆ y
3
1
2
3
y y
5
1
2
y ˆ y
3
1
2
3
注：１）带 者为错分样本。 ２）第k步迭代时，有 个错分样本。
达到极小值的最优化算法，用共轭梯度法可求得序列 X0,X1,· · · ,X*，使得
f(X0) ≥ f(X1) ≥ ······≥ f(X*) 对于二次正定函数f(X)，最多用d步，就可收敛于f(X)的极值解X*.
4.5 最小平方误差准则函数
前述法是对于所有样本都能满足不等式组aTYi>0(i=1,2· · · · · · N) , 而建立的二次准则函数，从而使错分样本数最少。
k
第1步迭代时：∵ a(1)=0, 故
y1
∴ a(1)Tyi=0
(i=1,2,3)
a(2) = a(1)＋ y ＝y1+y2+y3
第2步迭代时：即用a(2)分类时，有a(2)Ty3≤0 故 a(3) ＝ a(2)＋y3 第3步时：∵ aT(3) y1≤0 ∴ a(4)=a(3)+ y1 第4步时：∵ aT(4) y3≤0 ∴ a(5)=a(4)+ y3 第5步时：∵ aT(5) yi>0 (i=1,2,3) 故 a(5)为解向量 。 a(5)
4. 解向量和解区
(1) 解向量：满足aTYn>0 (n=1,· · · ,N)的权向量a称之为解向量。
(2) 权空间：由权向量组成的空间。
权向量a可视为权空间中的一点，且每个样本Yn对a的可 能位置都起到作用，即要求aTYn>0。
ˆ n. (3) 权空间原点的超平面：是由aTYn=0确定的超平面 H
共轭梯度法简介：
共轭梯度法是一种改进搜索方向的方法，它是为快速迭代 而形成的一种方法，它要求迭代过程应沿梯度的共轭方向进行 搜索，从而得出序列解的方法。具体的说，就是把前一点的梯
度乘以适当的系数v，加到该点的梯度上，得到新的搜索方向。
而“共轭”是对一组向量而言。 例如，设X与Y是两个d维非0向量，而Bd×d是一个对称正定矩 阵，如果有 XTBY ＝ 0 则称X和Y关于B互为共轭。
aTYi
XiT=[Xi1,· · · ,Xid]
(i=1,· · · ,N)
则其齐次式为：
其中
aT=[W0,W1,· · · ,Wd]=[W0 W]
YiT=[1,xi1,· · · ,xid]=[1 XiT]
增广权向量
增广样本向量
即Yi为
ˆ 维(d+1维)增广样本向量。 d
如果存在一个权向量aT，满足下式： aTY > 0 aTY < 0 则 则 Yω1类 Yω2类