四线性判别函数

.
投影后数据的均值（ n1 , n2 是两类样本的个 数）
n1 µ1 + n2 µ 2 . b= n1 + n2
4.2 最小平方误差准则(MSE)
4.2 最小平方误差准则

线性分类器的齐次表达式：

原始表达式：
T
g ( x) = w x + b = ∑ w x + b.
i i i =1

d
权、样本增广向量：

准则的描述：

4.1 Fisher线性判别

符号含义：



度矩阵。 µ1 , µ 2 分别表示两类（投影后，一维）数 据的均值。 σ 1, σ 2 分别表示两类（投影后，一维）数 据的离散度。
m1 , m2 ——两类（原始）数据的均值向量。 S1 , S 2 分别表示两类（原始）数据的离散
zi zi = − z i

xi ∈ ω1 . xi ∈ ω 2
i = 1,2, L , n.
要找增广权向量尽可能满足：
z i a > 0.
T
4.3 最小错分样本数准则

线性可分性：
线性可分
线性不可分
4.3 最小错分样本数准则

线性可分性的判断：

线性可分 — 若存在增广权向量对规范化的 样本满足：
第一类 第二类
同类样本对应相同值，投影方向 w 与Fisher判别器所得结果相同。
4.2 最小平方误差准则

解释：这时，最小平方误差相当于给定类间 距的条件下，使类内距最小。
2 i i
Za − c = ∑ (a T zi − ci ) 2 =∑ ( wT xi + b − ci ) 2 = ∑ ( wT xi + b − c+ ) 2 +
{( xi , yi ), i = 1,2,L n}
x
g(x)
y

最简单的判别函数是线性函数，相应的 分类面是超平面。
4.0 引言

线性判别函数（两类）： > 0 ω1 T g ( x) = w x + b < 0 ω 2

设计线性分类器的关键是给出估计w, 的准则。
g ( x) = 0 是分类面方程； w 是分类面的法向量； b 是分类面的偏移；
zi a > 0,
T
i = 1,2, L , n.
4.3 最小错分样本数准则

算法： 为避免得到 a = 0 的解，引入小量 δ ，判 断 T
zi a ≥ δ ,
n
i = 1,2, L , n.
T
是线性规划问题：
松弛变量
min ∑ ξ i
ξi ,a
i =1
s.t.
zi a ≥ δ − ξ i
ξi ≥ 0
4.1 Fisher线性判别
•均值向量和离散度矩阵
1 mi = ∑ x N
i = 1,2
T
Si = ∑ ( x − mi )( x − mi )
(
)
i = 1,2
4.1 Fisher线性判别

原始数据与做 w 方向投影后数据统计量 之间的关系：
µ i = w mi ,
T
σ i = ∑ ( w x − µi )
4.2 最小平方误差准则
1 1 n 1 n T 2 J s ( a ) = ∑ ( g ( xi ) − ci ) = ∑ ( a z i − ci ) 2 N N i =1 N i =1 N N2 1 1 2 T a z c = 1* ( − ) + * ( a T z i − ci ) 2 ∑ ∑ i i N N 1 i∈I N N 2 i∈II

称 S b = ( m1 − m2 )(m1 − m2 ) 类间离散度矩阵。 称
T

St = S1 + S 2
类内总离散度矩阵。
w Sb w J F ( w) = T . w St w
T
4.1 Fisher线性判别

Fisher准则的合理性：
J F ( w) 只与投影方向有关，与 w 大小无关— kw 也是最优解，k 是 若 w 是一个最优解，
2 T 2
xi ∈II
∑ (w
xi ∈II
T
xi + b − c− ) ( xi − m2 ))
2
= ∑ ( w ( xi − m1 )) +
∑ (w
T
2
= N1wT Σ1w + N 2 wT Σ 2 w = wT ( N1Σ1 + N 2 Σ 2 ) w = wT S w w.
与Fisher准则等价！
T
wopt =
c
λ
St (m1 − m2 ).
−1
4.1 Fisher线性判别

只关心投影的方向：
wopt = S t (m1 − m2 ) = ( S1 + S 2 ) (m1 − m2 ).
−1
−1
4.1 Fisher线性判别

分类阈值 b 的确定：

两类均值的中点：
b=

µ1 + µ 2
2
xi ∈I xi ∈II 2 T ( w x + b − c ) ∑ i −
必有：
wT m1 + b − c+ = 0, wT m2 + b − c− = 0.
wT ( m1 − m2 ) = c+ − c− .
类间距给定。
4.2 最小平方误差准则
∑ (w
xi ∈I xi ∈I T
xi + b − c+ ) +

支持向量机(Support Vector Machine)

Cortes and Vapnik, 1995. 最大边界距离分类器。
T +
T
Z ) 可逆.
a = ( Z Z ) Z c = Z c.
T
−1
Z + = ( Z T Z ) −1 Z T
是 Z 的最小二乘广义逆。
4.2 最小平方误差准则

与Fisher线性判别的关系： 两类样本数分别为 N1 , N 2 ; N = N1 + N 2 .
令：
c = ( c+ , L , c+ , c− , L , c− ) T .
N →∞
≈ P (ω1 ) ∫ ( a T z − 1) 2 P ( x | ω1 ) dx + P (ω 2 ) ∫ ( a T z + 1) 2 P ( x | ω 2 ) dx P ( x , ω1 ) − P ( x , ω 2 ) ] * P( x) P( x)
= ∫ ( a T z − 1) 2 P ( x , ω1 ) dx + ∫ ( a T z + 1) 2 P ( x , ω 2 ) dx = ∫ {(a T z ) 2 [ P ( x , ω1 ) + P ( x , ω 2 )] − 2 a T z[ + [ P ( x , ω1 ) + P ( x , ω 2 )]}dx = ∫ ( a T z ) 2 P ( x ) dx − 2 ∫ ( a T z ) g 0 ( x ) P ( x ) dx + 1
任何不为零的常数。
4.1 Fisher线性判别

Fisher最佳投影方向的求解：

要求：
St = S1 + S 2 正定。
否则，存在投影方向
T
w ，使得
w St w = 0. 所有数据被投影到一点上！ J F ( w) 没有极大值。
4.1 Fisher线性判别

求出最佳投影方向上任何一个 w 即可。

J F ( w)有上界，最佳投影方向一定存在！
λ ( Sb ) max J F ( w) ≤ . λ ( St ) min
最小、最大的特征根。
λ ( S w ) min , λ ( Sb ) max 分别是矩阵 S , S 的 t b
4.1 Fisher线性判别

一定存在一个最优的
w ，满足：
T
2 T
2 T
i = 1,2.
i
=w
T
∑ ( x − m )( x − m )
i
w
= w Si w.
T
4.1 Fisher线性判别

Fisher准则函数：
( µ1 − µ 2 ) J F ( w) = 2 . 2 σ1 + σ 2
2
1
类间距 总类内离散度
wopt = arg max J F ( w).
T T
∂L( w, λ ) = S b w − λSt w. ∂w
最优解满足：
S b wopt − λS t wopt = 0.
4.1 Fisher线性判别
根据类间离散度定义：
(m1 − m2 )(m1 − m2 ) wopt = λSt wopt .
T
注意
(m1 − m2 ) wopt 是一个数，记作 c ,
2 = ∫ [a T z − g 0 ( x )] 2 dx + [1 − ∫ g 0 ( x )P ( x ) dx ]
= e 2 + [1 − ∫ g 2 ( x )P ( x ) dx ] 0
4.3 最小错分样本数准则
4.3 最小错分样本数准则

样本增广向量的规范化表示：

样本增广向量规范化：
只有被错分的样本 zi a < δ 有贡献。
4.3 最小错分样本数准则

求解算法：

无约束最优化的各种算法，如共轭梯度法。 带约束的二次规划：

min ∑ ξ i
ξi ,a
i =1
n
2
s.t.
zi a ≥ δ − ξ i
T
ξi ≥ 0
i = 1,2, L , n.
4.4 线性支持向量机
4.4 线性支持向量机
4.2 最小平方误差准则

与Bayes决策的关系：如果 当样本数趋于无穷时，MSE的解以最小 均方误差逼近Bayes判别函数：
P( x, ω1 ) − P( x, ω2 ) g 0 ( x) = P(ω1 | x) − P(ω2 | x) = P ( x)
c = (1L,1,−1L,−1)T
令 e 2 = ∫ [z T a − g 0 ( x)]2 P( x)dx ˆ = arg min e 2 = Z + c 则a
平方误差和：
n 2 n T 2 2
J s (a ) = ∑ ( g ( xi ) − ci ) = ∑ (a zi − ci ) = Za − c
i =1 i =1
4.2 最小平方误差准则

增广权向量的求解：
∇J s (a ) = 2 Z T ( Za − c).
Z Za = Z c.
T T
一般样本数大于维数, ( Z
第四章 线性判别函数

4.0 4.1 4.2 4.3 4.4
引言 Fisher线性判别 最小平方误差准则 最小错分样本数准则 线性支持向量机（SVM）
4.0 引言
4.0 引言

Bayes决策尽管是最优决策，但实现困难。

模式识别的任务是分类，可直接设计判 别函数 — 即分类面。
4.0 引言
4.1 Fisher线性判别
( µ1 − µ 2 ) J F ( w) = 2 2 σ1 + σ 2 ( w m1 − w m2 ) = T T w S1w + w S 2 w
T T 2 2
w (m1 − m2 )(m1 − m2 ) w . = T w ( S1 + S 2 ) w
T T
4.1 Fisher线性判别
b
4.0 引言

线性判别函数的几何意义：
w
w x+b=0
T
4.0 引言

选择 w 就是找一个最佳投影方向。只与方 向有关，和 w 大小无关！ 投影后是一维数据的分类问题。

4.1 Fisher线性判别
4.1 Fisher线性判别

Fisher判别的基本思想：
希望投影后的一维数据满足：

两类之间的距离尽可能远； 每一类自身尽可能紧凑。 用投影后数据的统计性质—均值和离散度的 函数作为判别优劣的标准。
a = (b, w1 , w1 , L , w d )T , z = (1, x1 , x1 , L , x d )T .
4.2 最小平方误差准则

判别函数的齐次表达式：
g ( x) = a T z

样本的增广矩阵：
1 1 x1 1 1 x2 T Z = ( z1 , z 2 , L , z n ) = M M d 1 xn
i = 1,2, L , n.
线性可分，当且仅当解为 所有 ξ i
= 0。
4.3 最小错分样本数准则

Fisher判别与最小平方误差判别的准则函 数考虑了所有的样本。 最小错分样本数准则只考虑被错分的样 本。
J (a ) = ( Za − c) − Za − c
T

2
.
c = (δ , Lδ )
T
L x L x M d L xn
d 1 d 2
4.2 最小平方误差准则

最小平方误差(MSE)方法的思想： 对每个样本 xi ，设定一个“理想”的判别函 数输出值 ci ，以最小平方误差为准则求最优 投影方向 w （增广权向量 a ）。 T c = ( c , c , L , c ) . 令 1 2 n
w S t w = 1.
T

因为 S t 正定！
w S w b 无约束最优化：max . T w St w
等价于带约束的最优化：
max w S b w s.t. wT St w = 1.
Байду номын сангаас
T
4.1 Fisher线性判别

带等式约束的最优化，用Lagrange乘子法：
L( w, λ ) = w S b w − λ ( w S t w − 1).