第四章线性判别函数
? 4.0 引言
? 4.1 Fisher线性判别
? 4.2 最小平方误差准则
? 4.3 最小错分样本数准则
? 4.4 线性支持向量机（SVM）
4.0引言
4.0引言
? Bayes决策尽管是最优决策，但实现困难。
?模式识别的任务是分类，可直接设计判别函数—即分类面。
4.0引言
{ }niyx
ii
L,2,1),,( =
y
?最简单的判别函数是线性函数，相应的分类面是超平面。
g(x)
x
4.0引言
?线性判别函数（两类）：
?是分类面方程；
?是分类面的法向量；
?是分类面的偏移；
?设计线性分类器的关键是给出估计的准则。
<
>
+=
2
1
0
0
)(
ω
ω
bxwxg
T
w
b
0)( =xg
,w
b
4.0引言
?线性判别函数的几何意义：
0=+bxw
T
w
4.0引言
?选择就是找一个最佳投影方向。只与方向有关，和大小无关！
?投影后是一维数据的分类问题。
w
w
4.1 Fisher线性判别
4.1 Fisher线性判别
? Fisher判别的基本思想：
希望投影后的一维数据满足：
?两类之间的距离尽可能远；
?每一类自身尽可能紧凑。
?准则的描述：
?用投影后数据的统计性质—均值和离散度的函数作为判别优劣的标准。
4.1 Fisher线性判别
?符号含义：
? ——两类（原始）数据的均值向量。
?分别表示两类（原始）数据的离散度矩阵。
?分别表示两类（投影后，一维）数据的均值。
?分别表示两类（投影后，一维）数据的离散度。
21
,μμ
21
,σσ
21
,mm
21
,SS
4.1 Fisher线性判别
均值向量和离散度矩阵
2,1
1
=∑= ix
N
m
i
( ) 2,1))(( =∑= imxmxS
T
iii
4.1 Fisher线性判别
?原始数据与做方向投影后数据统计量之间的关系：
w
,
i
T
i
mw=μ
.2,1=i
.
))((
)(
2
2
wSw
wmxmxw
xw
i
T
T
ii
T
i
T
i
=
=
=
∑
∑
μσ
4.1 Fisher线性判别
? Fisher准则函数：
.
)(
)(
2
2
2
1
2
21
σσ
μμ
+
=wJ
F
1
类间距总类内离散度
).(maxarg wJw
Fopt
=
4.1 Fisher线性判别
.
)(
))((
)(
)(
)(
21
2121
21
2
21
2
2
2
1
2
21
wSSw
wmmmmw
wSwwSw
mwmw
wJ
T
TT
TT
TT
F
+
=
+
=
+
=
σσ
μμ
4.1 Fisher线性判别
?称类间离散度矩阵。
?称类内总离散度矩阵。
T
b
mmmmS ))((
2121
=
21
SSS
t
+=
.)(
wSw
wSw
wJ
t
T
b
T
F
=
4.1 Fisher线性判别
? Fisher准则的合理性：
只与投影方向有关，与大小无关—
若是一个最优解，也是最优解，是任何不为零的常数。
)(wJ
F
w
w
kw
k
4.1 Fisher线性判别
? Fisher最佳投影方向的求解：
?要求：
正定。
否则，存在投影方向，使得没有极大值。
21
SSS
t
+=
w
.0=wSw
t
T
)(wJ
F
所有数据被投影到一点上！
4.1 Fisher线性判别
?求出最佳投影方向上任何一个即可。
?有上界，最佳投影方向一定存在！
分别是矩阵的最小、最大的特征根。
w
.
)(
)(
)(
min
max
t
b
F
S
S
wJ
λ
λ
≤
)(wJ
F
maxmin
)(,)(
bw
SS λλ
bt
SS,
4.1 Fisher线性判别
?一定存在一个最优的，满足：
?无约束最优化：
等价于带约束的最优化：
w
.1=wSw
t
T
.max
wSw
wSw
t
T
b
T
.1..
max
=wSwts
wSw
t
T
b
T
因为正定！
t
S
4.1 Fisher线性判别
?带等式约束的最优化，用Lagrange乘子法：
最优解满足：
).1(),(= wSwwSwwL
t
T
b
T
λλ
.
),(
wSwS
w
wL
tb
λ
λ
=
.0=?
opttoptb
wSwS λ
4.1 Fisher线性判别根据类间离散度定义：
注意是一个数，记作,
.))((
2121 opttopt
T
wSwmmmm λ=
opt
T
wmm )(
21
c
).(
21
1
mmS
c
w
topt
=
λ
4.1 Fisher线性判别
?只关心投影的方向：
).()(
)(
21
1
21
21
1
mmSS
mmSw
topt
+=
=
4.1 Fisher线性判别
?分类阈值的确定：
?两类均值的中点：
?投影后数据的均值（是两类样本的个数）
b
.
2
21
μμ +
=b
.
2211
nn
b
+
=
μμ
21
,nn
21
nn +
4.2 最小平方误差准则(MSE)
4.2 最小平方误差准则
?线性分类器的齐次表达式：
?原始表达式：
?权、样本增广向量：
.)(
1
bxwbxwxg
d
i
iiT
+=+=
∑
=
.),,,,1(
,),,,,(
11
11
Td
Td
xxxz
wwwba
L
L
=
=
4.2 最小平方误差准则
?判别函数的齐次表达式：
?样本的增广矩阵：
zaxg
T
=)(
==
d
n
d
n
d
d
T
n
xx
xx
xx
zzzZ
L
MMM
L
L
L
1
1
1
),,,(
2
1
2
1
1
1
21
4.2 最小平方误差准则
?最小平方误差(MSE)方法的思想：
?对每个样本，设定一个“理想”的判别函数输出值，以最小平方误差为准则求最优投影方向（增广权向量）。
?令平方误差和：
i
x
i
c
w
a
.),,,(
21
T
n
cccc L=
2
1
2
1
2
)())(()( cZaczacxgaJ
n
i
ii
T
n
i
iis
=?=?=
∑∑
==
4.2 最小平方误差准则
?增广权向量的求解：
是的最小二乘广义逆。
).(2)( cZaZaJ
T
s
=?
.cZZaZ
TT
=
.)(
1
cZcZZZa
TT +?
==
一般样本数大于维数,可逆.
)( ZZ
T
TT
ZZZZ
1
)(
+
= Z
4.2 最小平方误差准则
?与Fisher线性判别的关系：
?两类样本数分别为.;,
2121
NNNNN +=
.),,,,,(
T
ccccc
++
= LL
令：
与Fisher判别器所得结果相同。w
第一类第二类同类样本对应相同值，投影方向
4.2 最小平方误差准则
?解释：这时，最小平方误差相当于给定类间距的条件下，使类内距最小。
∑∑
∑∑
∈
∈
+
++?+=
+=?=?
IIx
i
T
Ix
i
T
i
ii
T
i
ii
T
ii
cbxwcbxw
cbxwczacZa
22
22
2
)()(
)()(
必有：
.0
,0
2
1
=?+
=?+
+
cbmw
cbmw
T
T
.)(
21?+
=? ccmmw
T
类间距给定。
4.2 最小平方误差准则
.
)(
))(())((
)()(
22112211
2
2
2
1
22
wSw
wNNwwwNwwN
mxwmxw
cbxwcbxw
w
T
TTT
IIx
i
T
Ix
i
T
IIx
i
T
Ix
i
T
ii
ii
=
Σ+Σ=Σ+Σ=
+?=
++?+
∑∑
∑∑
∈∈
∈
∈
+
与Fisher准则等价！
4.2 最小平方误差准则
?与Bayes决策的关系：如果当样本数趋于无穷时，MSE的解以最小均方误差逼近Bayes判别函数：
T
c )1,1,1,1(= LL
)(
),(),(
)|()|()(
21
210
xP
xPxP
xPxPxg
ωω
ωω
=?=
cZea
dxxPxgaze
T
+
==
=
∫
2
2
0
2
minarg
)()]([
则令
4.2 最小平方误差准则
])()(1[
])()(1[)]([
1)()()(2)()(
)]},(),([
)(*]
)(
),(),(
[2)],(),([){(
),()1(),()1(
)|()1()()|()1()(
)(
1
*)(
1
*
)(
1
))((
1
)(
1
22
22
0
0
2
21
21
21
2
2
2
1
2
2
2
21
2
1
2
2
2
2
1
1
1
2
1
2
0
0
dxxPxge
dxxPxgdxxgza
dxxPxgzadxxPza
dxxPxP
xP
xP
xPxP
zaxPxPza
dxxPzadxxPza
dxxPzaPdxxPzaP
cza
NN
N
cza
NN
N
cza
N
cxg
N
aJ
N
T
TT
TT
TT
TT
N
IiIIi
ii
T
ii
T
n
i
ii
T
n
i
iis
∫
∫∫
∫∫
∫
∫∫
∫∫
∑∑
∑∑
+=
+?=
+?=
++
+=
++?=
++?≈
+?=
=?=
∞→
∈∈
==
ωω
ωω
ωω
ωω
ωωωω
4.3 最小错分样本数准则
4.3 最小错分样本数准则
?样本增广向量的规范化表示：
?样本增广向量规范化：
?要找增广权向量尽可能满足：
.
2
1
∈?
∈
=
ω
ω
ii
ii
i
xz
xz
z
.0>az
T
i
.,,2,1 ni L=
4.3 最小错分样本数准则
?线性可分性：
线性可分线性不可分
4.3 最小错分样本数准则
?线性可分性的判断：
?线性可分—若存在增广权向量对规范化的样本满足：
,0>az
T
i
.,,2,1 ni L=
4.3 最小错分样本数准则
?算法：
为避免得到的解，引入小量，判断是线性规划问题：
0=a δ
,δ≥az
T
i
.,,2,1 ni L=
0
..
≥
≥
i
i
T
i
azts
ξ
ξδ
∑
=
n
i
i
a
i
1
,
min ξ
ξ
.,,2,1 ni L=
线性可分，当且仅当解为所有。
0=
i
ξ
松弛变量
4.3 最小错分样本数准则
? Fisher判别与最小平方误差判别的准则函数考虑了所有的样本。
?最小错分样本数准则只考虑被错分的样本。
只有被错分的样本有贡献。
.)()(
2
cZacZaaJ=
T
c ),( δδ L=
δ<az
T
i
4.3 最小错分样本数准则
?求解算法：
?无约束最优化的各种算法，如共轭梯度法。
?带约束的二次规划：
∑
=
n
i
i
a
i
1
2
,
min ξ
ξ
0
..
≥
≥
i
i
T
i
azts
ξ
ξδ
.,,2,1 ni L=
4.4 线性支持向量机
4.4 线性支持向量机
?支持向量机(Support Vector Machine)
? Cortes and Vapnik,1995.
?最大边界距离分类器。
4.4 线性支持向量机
?线性可分情形下的最大边界距离分类超平面
(maximal margin hyperplane),
margin
margin
4.4 线性支持向量机
?分类面与边界距离(margin)的数学表示：
?训练数据的集合：
),,(,),,(),,(
2211 nn
yxyxyx L
}.1,1{,?∈?∈
i
d
i
yx
，表示
1
1 ω∈=
ii
xy
.1
2
ω∈?=
ii
xy表示
4.4 线性支持向量机
?分类超平面表示为：
?则两类边界上，与分类超平面平行的两个平面的距离就是最大边界距离，假设等于，那么两个边界平面为：
.1=w
ρ
0=+bwx
T
2/:
2/:
2
1
ρπ
ρπ
=+
=+
bwx
bwx
T
T
4.4 线性支持向量机
?对于两类样本就有约束：
12/
12/
=?≤+
=≥+
i
T
i
i
T
i
ybwx
ybwx
ρ
ρ
4.4 线性支持向量机
?求解最大边界距离分类超平面：
ρ
bw,
max
.1
12/
12/
=
=?≤+
=≥+
w
ybwx
ybwx
i
T
i
i
T
i
ρ
ρ
..ts
4.4 线性支持向量机
?重新考虑上述问题：去掉约束条件，
考虑两条边界平行平面的距离：
1:
1:
2
2
1
2
=+
=+
bwx
bwx
w
T
T
π
π
1=w
4.4 线性支持向量机
?等价形式（只考虑法向量的方向）：
约束简化为：
,11
11
=?≤+
=≥+
i
T
i
i
T
i
ybwx
ybwx
2
,
2
1
min w
bw
..ts
w
1)( ≥+bwxy
T
ii
.,,2,1 ni L=
4.4 线性支持向量机
? Lagrange 乘子法：
ni
bwxywbwL
i
n
i
T
iii
,,2,1,0
]1)([
2
1
),,(
1
2
L=≥
+?=
∑
=
α
αα
0
),,(
1
=?=
∑
=
n
i
iii
xyw
w
bwL
α
α
0
),,(
1
==
∑
=
n
i
ii
y
b
bwL
α
α
4.4 线性支持向量机
?最大边界距离分类超平面满足：
.
1
∑
=
=
n
i
iii
xyw α
法向量是样本的线性组合！
.0
1
=
∑
=
n
i
ii
yα
4.4 线性支持向量机
?把上述表达式代入Lagrange函数：
j
T
ij
n
ji
iji
n
i
ijj
n
j
j
T
ii
n
i
i
n
i
i
n
i
n
i
i
n
i
iijj
n
j
j
T
iiijj
n
j
j
T
ii
n
i
i
n
i
T
iii
xxyyxyxy
ybxyxyxyxy
bwxyw
αααααα
αααααα
α
∑∑∑∑∑
∑∑∑∑∑∑
∑
=====
======
=
=?=
+=
+?
1,1111
111111
1
2
2
1
2
1
2
1
]1)([
2
1
4.4 线性支持向量机
?得到对偶形式，使下式最大化：
.)(
2
1
)(
1,1
∑∑
==
=
n
ji
j
T
ijiji
n
i
i
xxyyW αααα
.,,2,1,0.,nits
i
L=≥α
.0
1
=
∑
=
n
i
ii
yα
二次规划问题.
4.4 线性支持向量机
?由Karush-Kuhn-Tucker（KKT）条件，分类面是最优超平面的充分必要条件是：
?只有对应的不为0，这样的称为支持向量。
.0)1)(( =?+bwxy
T
iii
α
.,,2,1 ni L=
1)( =+bwxy
T
ii
i
α
i
x
4.4 线性支持向量机
?假设是上述二次规划问题的解，那么
ni
i
L,2,1,
0
=α
∑∑
==
=支持向量
iii
n
i
iii
xyxyw
0
1
0
0
αα
[]
类的支持向量。）分别为第一类和第二（）和（
）（）（有
）（
）（
由
11
11
2
1
,
11
11
000
0
0
+=
=+?
=+
T
i
T
i
T
i
T
i
T
i
T
i
xx
wxwxb
bwx
bwx
4.4 线性支持向量机
?几何意义：超平面法向量是支持向量的线性组合。
支持向量：
1)( =+bwxy
T
ii
非支持向量：
1)( >+bwxy
T
ii
0>
i
α
0=
i
α
4.4 线性支持向量机
?决策函数：
用内积符号表示：
.)()(
1
bxxybxwxg
n
i
T
iii
T
+=+=
∑
=
α
.)()(
1
bxxyxg
n
i
iii
+?=
∑
=
α
4.4 线性支持向量机
?线性不可分情形下，广义最大边界距离分类超平面：
?线性不可分：
iii
bwxy ξ?≥+? 1)(
.,,2,1 ni L=
.0≥
i
ξ
4.4 线性支持向量机
? Soft margin SVM:
C是预先设定的参数。
)(
2
1
min
1
2
,,
∑
=
+
n
i
i
bw
Cw ξ
ξ
iii
bwxyts ξ?≥+? 1)(..
.0≥
i
ξ
.,,2,1 ni L=
4.4 线性支持向量机
?对偶形式：
.)(
2
1
)(
1,1
∑∑
==
=
n
ji
jijiji
n
i
i
xxyyW αααα
.,,2,1,0.,niCts
i
L=≤≤α
.0
1
=
∑
=
n
i
ii
yα
4.4 线性支持向量机
?超平面仍是支持向量的线性组合：
.
1
∑
=
=
n
i
iii
xyw α
1)( =+? bwxy
ii
C
i
<<α0
1)( >+? bwxy
ii
0=
i
α
1)( <+? bwxy
ii
C
i
=α
4.4 线性支持向量机
?几何意义：
1)( >+? bwxy
ii
0=
i
α
1)( =+? bwxy
ii
C
i
<<α0
1)( <+? bwxy
ii
C
i
=α
4.4 线性支持向量机
?与Fisher判别的关系：
?线性可分情况下，只考虑支持向量，SVM与
Fisher判别等价：
SV
参考文献
? [1] Richard O,Duda,Peter E,Hart,David G,Stork,
Pattern Classification,2
nd
Edition,John Wiley & Sons,Inc,
2001
? [2] K,Fukunaga,Introduction to Statistical Pattern
Recognition,2
nd
Edition,Academic Press,1990.
? [3] B,Ripley,Pattern Recognition and Neural Networks,
Cambridge University Press,1996.
? [4] Vladimir N,Vapnik,Statistical Learning Theory,John
Wiley & Sons,Inc,1998.
? [5] Vladimir N,Vapnik,The Nature of Statistical Learning,Springer-
Verlag,New York,NY,1995 (中译本《统计学习理论的本质》，张学工译，清华大学出版社，2000年9月)
? 4.0 引言
? 4.1 Fisher线性判别
? 4.2 最小平方误差准则
? 4.3 最小错分样本数准则
? 4.4 线性支持向量机（SVM）
4.0引言
4.0引言
? Bayes决策尽管是最优决策，但实现困难。
?模式识别的任务是分类，可直接设计判别函数—即分类面。
4.0引言
{ }niyx
ii
L,2,1),,( =
y
?最简单的判别函数是线性函数，相应的分类面是超平面。
g(x)
x
4.0引言
?线性判别函数（两类）：
?是分类面方程；
?是分类面的法向量；
?是分类面的偏移；
?设计线性分类器的关键是给出估计的准则。
<
>
+=
2
1
0
0
)(
ω
ω
bxwxg
T
w
b
0)( =xg
,w
b
4.0引言
?线性判别函数的几何意义：
0=+bxw
T
w
4.0引言
?选择就是找一个最佳投影方向。只与方向有关，和大小无关！
?投影后是一维数据的分类问题。
w
w
4.1 Fisher线性判别
4.1 Fisher线性判别
? Fisher判别的基本思想：
希望投影后的一维数据满足：
?两类之间的距离尽可能远；
?每一类自身尽可能紧凑。
?准则的描述：
?用投影后数据的统计性质—均值和离散度的函数作为判别优劣的标准。
4.1 Fisher线性判别
?符号含义：
? ——两类（原始）数据的均值向量。
?分别表示两类（原始）数据的离散度矩阵。
?分别表示两类（投影后，一维）数据的均值。
?分别表示两类（投影后，一维）数据的离散度。
21
,μμ
21
,σσ
21
,mm
21
,SS
4.1 Fisher线性判别
均值向量和离散度矩阵
2,1
1
=∑= ix
N
m
i
( ) 2,1))(( =∑= imxmxS
T
iii
4.1 Fisher线性判别
?原始数据与做方向投影后数据统计量之间的关系：
w
,
i
T
i
mw=μ
.2,1=i
.
))((
)(
2
2
wSw
wmxmxw
xw
i
T
T
ii
T
i
T
i
=
=
=
∑
∑
μσ
4.1 Fisher线性判别
? Fisher准则函数：
.
)(
)(
2
2
2
1
2
21
σσ
μμ
+
=wJ
F
1
类间距总类内离散度
).(maxarg wJw
Fopt
=
4.1 Fisher线性判别
.
)(
))((
)(
)(
)(
21
2121
21
2
21
2
2
2
1
2
21
wSSw
wmmmmw
wSwwSw
mwmw
wJ
T
TT
TT
TT
F
+
=
+
=
+
=
σσ
μμ
4.1 Fisher线性判别
?称类间离散度矩阵。
?称类内总离散度矩阵。
T
b
mmmmS ))((
2121
=
21
SSS
t
+=
.)(
wSw
wSw
wJ
t
T
b
T
F
=
4.1 Fisher线性判别
? Fisher准则的合理性：
只与投影方向有关，与大小无关—
若是一个最优解，也是最优解，是任何不为零的常数。
)(wJ
F
w
w
kw
k
4.1 Fisher线性判别
? Fisher最佳投影方向的求解：
?要求：
正定。
否则，存在投影方向，使得没有极大值。
21
SSS
t
+=
w
.0=wSw
t
T
)(wJ
F
所有数据被投影到一点上！
4.1 Fisher线性判别
?求出最佳投影方向上任何一个即可。
?有上界，最佳投影方向一定存在！
分别是矩阵的最小、最大的特征根。
w
.
)(
)(
)(
min
max
t
b
F
S
S
wJ
λ
λ
≤
)(wJ
F
maxmin
)(,)(
bw
SS λλ
bt
SS,
4.1 Fisher线性判别
?一定存在一个最优的，满足：
?无约束最优化：
等价于带约束的最优化：
w
.1=wSw
t
T
.max
wSw
wSw
t
T
b
T
.1..
max
=wSwts
wSw
t
T
b
T
因为正定！
t
S
4.1 Fisher线性判别
?带等式约束的最优化，用Lagrange乘子法：
最优解满足：
).1(),(= wSwwSwwL
t
T
b
T
λλ
.
),(
wSwS
w
wL
tb
λ
λ
=
.0=?
opttoptb
wSwS λ
4.1 Fisher线性判别根据类间离散度定义：
注意是一个数，记作,
.))((
2121 opttopt
T
wSwmmmm λ=
opt
T
wmm )(
21
c
).(
21
1
mmS
c
w
topt
=
λ
4.1 Fisher线性判别
?只关心投影的方向：
).()(
)(
21
1
21
21
1
mmSS
mmSw
topt
+=
=
4.1 Fisher线性判别
?分类阈值的确定：
?两类均值的中点：
?投影后数据的均值（是两类样本的个数）
b
.
2
21
μμ +
=b
.
2211
nn
b
+
=
μμ
21
,nn
21
nn +
4.2 最小平方误差准则(MSE)
4.2 最小平方误差准则
?线性分类器的齐次表达式：
?原始表达式：
?权、样本增广向量：
.)(
1
bxwbxwxg
d
i
iiT
+=+=
∑
=
.),,,,1(
,),,,,(
11
11
Td
Td
xxxz
wwwba
L
L
=
=
4.2 最小平方误差准则
?判别函数的齐次表达式：
?样本的增广矩阵：
zaxg
T
=)(
==
d
n
d
n
d
d
T
n
xx
xx
xx
zzzZ
L
MMM
L
L
L
1
1
1
),,,(
2
1
2
1
1
1
21
4.2 最小平方误差准则
?最小平方误差(MSE)方法的思想：
?对每个样本，设定一个“理想”的判别函数输出值，以最小平方误差为准则求最优投影方向（增广权向量）。
?令平方误差和：
i
x
i
c
w
a
.),,,(
21
T
n
cccc L=
2
1
2
1
2
)())(()( cZaczacxgaJ
n
i
ii
T
n
i
iis
=?=?=
∑∑
==
4.2 最小平方误差准则
?增广权向量的求解：
是的最小二乘广义逆。
).(2)( cZaZaJ
T
s
=?
.cZZaZ
TT
=
.)(
1
cZcZZZa
TT +?
==
一般样本数大于维数,可逆.
)( ZZ
T
TT
ZZZZ
1
)(
+
= Z
4.2 最小平方误差准则
?与Fisher线性判别的关系：
?两类样本数分别为.;,
2121
NNNNN +=
.),,,,,(
T
ccccc
++
= LL
令：
与Fisher判别器所得结果相同。w
第一类第二类同类样本对应相同值，投影方向
4.2 最小平方误差准则
?解释：这时，最小平方误差相当于给定类间距的条件下，使类内距最小。
∑∑
∑∑
∈
∈
+
++?+=
+=?=?
IIx
i
T
Ix
i
T
i
ii
T
i
ii
T
ii
cbxwcbxw
cbxwczacZa
22
22
2
)()(
)()(
必有：
.0
,0
2
1
=?+
=?+
+
cbmw
cbmw
T
T
.)(
21?+
=? ccmmw
T
类间距给定。
4.2 最小平方误差准则
.
)(
))(())((
)()(
22112211
2
2
2
1
22
wSw
wNNwwwNwwN
mxwmxw
cbxwcbxw
w
T
TTT
IIx
i
T
Ix
i
T
IIx
i
T
Ix
i
T
ii
ii
=
Σ+Σ=Σ+Σ=
+?=
++?+
∑∑
∑∑
∈∈
∈
∈
+
与Fisher准则等价！
4.2 最小平方误差准则
?与Bayes决策的关系：如果当样本数趋于无穷时，MSE的解以最小均方误差逼近Bayes判别函数：
T
c )1,1,1,1(= LL
)(
),(),(
)|()|()(
21
210
xP
xPxP
xPxPxg
ωω
ωω
=?=
cZea
dxxPxgaze
T
+
==
=
∫
2
2
0
2
minarg
)()]([
则令
4.2 最小平方误差准则
])()(1[
])()(1[)]([
1)()()(2)()(
)]},(),([
)(*]
)(
),(),(
[2)],(),([){(
),()1(),()1(
)|()1()()|()1()(
)(
1
*)(
1
*
)(
1
))((
1
)(
1
22
22
0
0
2
21
21
21
2
2
2
1
2
2
2
21
2
1
2
2
2
2
1
1
1
2
1
2
0
0
dxxPxge
dxxPxgdxxgza
dxxPxgzadxxPza
dxxPxP
xP
xP
xPxP
zaxPxPza
dxxPzadxxPza
dxxPzaPdxxPzaP
cza
NN
N
cza
NN
N
cza
N
cxg
N
aJ
N
T
TT
TT
TT
TT
N
IiIIi
ii
T
ii
T
n
i
ii
T
n
i
iis
∫
∫∫
∫∫
∫
∫∫
∫∫
∑∑
∑∑
+=
+?=
+?=
++
+=
++?=
++?≈
+?=
=?=
∞→
∈∈
==
ωω
ωω
ωω
ωω
ωωωω
4.3 最小错分样本数准则
4.3 最小错分样本数准则
?样本增广向量的规范化表示：
?样本增广向量规范化：
?要找增广权向量尽可能满足：
.
2
1
∈?
∈
=
ω
ω
ii
ii
i
xz
xz
z
.0>az
T
i
.,,2,1 ni L=
4.3 最小错分样本数准则
?线性可分性：
线性可分线性不可分
4.3 最小错分样本数准则
?线性可分性的判断：
?线性可分—若存在增广权向量对规范化的样本满足：
,0>az
T
i
.,,2,1 ni L=
4.3 最小错分样本数准则
?算法：
为避免得到的解，引入小量，判断是线性规划问题：
0=a δ
,δ≥az
T
i
.,,2,1 ni L=
0
..
≥
≥
i
i
T
i
azts
ξ
ξδ
∑
=
n
i
i
a
i
1
,
min ξ
ξ
.,,2,1 ni L=
线性可分，当且仅当解为所有。
0=
i
ξ
松弛变量
4.3 最小错分样本数准则
? Fisher判别与最小平方误差判别的准则函数考虑了所有的样本。
?最小错分样本数准则只考虑被错分的样本。
只有被错分的样本有贡献。
.)()(
2
cZacZaaJ=
T
c ),( δδ L=
δ<az
T
i
4.3 最小错分样本数准则
?求解算法：
?无约束最优化的各种算法，如共轭梯度法。
?带约束的二次规划：
∑
=
n
i
i
a
i
1
2
,
min ξ
ξ
0
..
≥
≥
i
i
T
i
azts
ξ
ξδ
.,,2,1 ni L=
4.4 线性支持向量机
4.4 线性支持向量机
?支持向量机(Support Vector Machine)
? Cortes and Vapnik,1995.
?最大边界距离分类器。
4.4 线性支持向量机
?线性可分情形下的最大边界距离分类超平面
(maximal margin hyperplane),
margin
margin
4.4 线性支持向量机
?分类面与边界距离(margin)的数学表示：
?训练数据的集合：
),,(,),,(),,(
2211 nn
yxyxyx L
}.1,1{,?∈?∈
i
d
i
yx
，表示
1
1 ω∈=
ii
xy
.1
2
ω∈?=
ii
xy表示
4.4 线性支持向量机
?分类超平面表示为：
?则两类边界上，与分类超平面平行的两个平面的距离就是最大边界距离，假设等于，那么两个边界平面为：
.1=w
ρ
0=+bwx
T
2/:
2/:
2
1
ρπ
ρπ
=+
=+
bwx
bwx
T
T
4.4 线性支持向量机
?对于两类样本就有约束：
12/
12/
=?≤+
=≥+
i
T
i
i
T
i
ybwx
ybwx
ρ
ρ
4.4 线性支持向量机
?求解最大边界距离分类超平面：
ρ
bw,
max
.1
12/
12/
=
=?≤+
=≥+
w
ybwx
ybwx
i
T
i
i
T
i
ρ
ρ
..ts
4.4 线性支持向量机
?重新考虑上述问题：去掉约束条件，
考虑两条边界平行平面的距离：
1:
1:
2
2
1
2
=+
=+
bwx
bwx
w
T
T
π
π
1=w
4.4 线性支持向量机
?等价形式（只考虑法向量的方向）：
约束简化为：
,11
11
=?≤+
=≥+
i
T
i
i
T
i
ybwx
ybwx
2
,
2
1
min w
bw
..ts
w
1)( ≥+bwxy
T
ii
.,,2,1 ni L=
4.4 线性支持向量机
? Lagrange 乘子法：
ni
bwxywbwL
i
n
i
T
iii
,,2,1,0
]1)([
2
1
),,(
1
2
L=≥
+?=
∑
=
α
αα
0
),,(
1
=?=
∑
=
n
i
iii
xyw
w
bwL
α
α
0
),,(
1
==
∑
=
n
i
ii
y
b
bwL
α
α
4.4 线性支持向量机
?最大边界距离分类超平面满足：
.
1
∑
=
=
n
i
iii
xyw α
法向量是样本的线性组合！
.0
1
=
∑
=
n
i
ii
yα
4.4 线性支持向量机
?把上述表达式代入Lagrange函数：
j
T
ij
n
ji
iji
n
i
ijj
n
j
j
T
ii
n
i
i
n
i
i
n
i
n
i
i
n
i
iijj
n
j
j
T
iiijj
n
j
j
T
ii
n
i
i
n
i
T
iii
xxyyxyxy
ybxyxyxyxy
bwxyw
αααααα
αααααα
α
∑∑∑∑∑
∑∑∑∑∑∑
∑
=====
======
=
=?=
+=
+?
1,1111
111111
1
2
2
1
2
1
2
1
]1)([
2
1
4.4 线性支持向量机
?得到对偶形式，使下式最大化：
.)(
2
1
)(
1,1
∑∑
==
=
n
ji
j
T
ijiji
n
i
i
xxyyW αααα
.,,2,1,0.,nits
i
L=≥α
.0
1
=
∑
=
n
i
ii
yα
二次规划问题.
4.4 线性支持向量机
?由Karush-Kuhn-Tucker（KKT）条件，分类面是最优超平面的充分必要条件是：
?只有对应的不为0，这样的称为支持向量。
.0)1)(( =?+bwxy
T
iii
α
.,,2,1 ni L=
1)( =+bwxy
T
ii
i
α
i
x
4.4 线性支持向量机
?假设是上述二次规划问题的解，那么
ni
i
L,2,1,
0
=α
∑∑
==
=支持向量
iii
n
i
iii
xyxyw
0
1
0
0
αα
[]
类的支持向量。）分别为第一类和第二（）和（
）（）（有
）（
）（
由
11
11
2
1
,
11
11
000
0
0
+=
=+?
=+
T
i
T
i
T
i
T
i
T
i
T
i
xx
wxwxb
bwx
bwx
4.4 线性支持向量机
?几何意义：超平面法向量是支持向量的线性组合。
支持向量：
1)( =+bwxy
T
ii
非支持向量：
1)( >+bwxy
T
ii
0>
i
α
0=
i
α
4.4 线性支持向量机
?决策函数：
用内积符号表示：
.)()(
1
bxxybxwxg
n
i
T
iii
T
+=+=
∑
=
α
.)()(
1
bxxyxg
n
i
iii
+?=
∑
=
α
4.4 线性支持向量机
?线性不可分情形下，广义最大边界距离分类超平面：
?线性不可分：
iii
bwxy ξ?≥+? 1)(
.,,2,1 ni L=
.0≥
i
ξ
4.4 线性支持向量机
? Soft margin SVM:
C是预先设定的参数。
)(
2
1
min
1
2
,,
∑
=
+
n
i
i
bw
Cw ξ
ξ
iii
bwxyts ξ?≥+? 1)(..
.0≥
i
ξ
.,,2,1 ni L=
4.4 线性支持向量机
?对偶形式：
.)(
2
1
)(
1,1
∑∑
==
=
n
ji
jijiji
n
i
i
xxyyW αααα
.,,2,1,0.,niCts
i
L=≤≤α
.0
1
=
∑
=
n
i
ii
yα
4.4 线性支持向量机
?超平面仍是支持向量的线性组合：
.
1
∑
=
=
n
i
iii
xyw α
1)( =+? bwxy
ii
C
i
<<α0
1)( >+? bwxy
ii
0=
i
α
1)( <+? bwxy
ii
C
i
=α
4.4 线性支持向量机
?几何意义：
1)( >+? bwxy
ii
0=
i
α
1)( =+? bwxy
ii
C
i
<<α0
1)( <+? bwxy
ii
C
i
=α
4.4 线性支持向量机
?与Fisher判别的关系：
?线性可分情况下，只考虑支持向量，SVM与
Fisher判别等价：
SV
参考文献
? [1] Richard O,Duda,Peter E,Hart,David G,Stork,
Pattern Classification,2
nd
Edition,John Wiley & Sons,Inc,
2001
? [2] K,Fukunaga,Introduction to Statistical Pattern
Recognition,2
nd
Edition,Academic Press,1990.
? [3] B,Ripley,Pattern Recognition and Neural Networks,
Cambridge University Press,1996.
? [4] Vladimir N,Vapnik,Statistical Learning Theory,John
Wiley & Sons,Inc,1998.
? [5] Vladimir N,Vapnik,The Nature of Statistical Learning,Springer-
Verlag,New York,NY,1995 (中译本《统计学习理论的本质》，张学工译，清华大学出版社，2000年9月)
