Fisher 线性判别式
前面讲过的感知器准则、最小平方和准则属于用神经网络的方法解决分类问题。
下面介绍一种新的判决函数分类方法。
由于线性判别函数易于分析，关于这方面的研究工作特别多。
历史上，这一工作是从R.A.Fisher 的经典论文（1936年）开始的。
我们知道，在用统计方法进行模式识别时，许多问题涉及到维数，在低维空间行得通的方法，在高维空间往往行不通。
因此，降低维数就成为解决实际问题的关键。
Fisher 的方法，实际上涉及维数压缩。
如果要把模式样本在高(d )维的特征向量空间里投影到一条直线上，实际上就是把特征空间压缩到一维，这在数学上容易办到。
另外，即使样本在高维空间里聚集成容易分开的群类，把它们投影到一条任意的直线上，也可能把不同的样本混杂在一起而变得无法区分。
也就是说，直线的方向选择很重要。
在一般情况下，总可以找到某个最好的方向，使样本投影到这个方向的直线上是最容易分得开的。
如何找到最好的直线方向，如何实现向最好方向投影的变换，是Fisher 法要解决的基本问题。
这个投影变换就是我们寻求的解向量*
w 。
1．线性投影与Fisher 准则函数
在21/w w 两类问题中，假定有n 个训练样本),....,2,1(n k x k =其中1n 个样本来自i w 类型，2n 个样本来自j w 类型，21n n n +=。
两个类型的训练样本分别构成训练样本的子集1X 和2X 。
令：k T
k x w y =，n k ,...,2,1= (4.5-1)
k y 是向量k x 通过变换w 得到的标量，它是一维的。
实际上，对于给定的w ，k y 就是判决函数的值。
由子集1X 和2X 的样本映射后的两个子集为1Y 和2Y 。
因为我们关心的是w 的方向，可以令1||||=w ，那么k y 就是k x 在w 方向上的投影。
使1Y 和2Y 最容易区分开的w 方向正是区分超平面的法线方向。
如下图：
图中画出了直线的两种选择，图(a)中，1Y 和2Y 还无法分开，而图(b)的选择可以使1Y 和2Y 区分开来。
所以图(b)的方向是一个好的选择。
下面讨论怎样得到最佳w 方向的解析式。
各类在d 维特征空间里的样本均值向量：
∑∈=
i
k X x k
i
i x
n M 1，2,1=i (4.5-2)
通过变换w 映射到一维特征空间后，各类的平均值为：
∑∈=
i
k Y y k
i
i y
n m 1，2,1=i (4.5-3)
映射后，各类样本“类内离散度”定义为：
2
2
()
k i
i k i y Y S y m ∈=
-∑
，2,1=i (4.5-4)
显然，我们希望在映射之后，两类的平均值之间的距离越大越好，而各类的样本类内离散度越小越好。
因此，定义Fisher
准则函数：
2
122
2
12
||()F m m J w s s -=
+ (4.5-5)
使F J 最大的解*
w 就是最佳解向量，也就是Fisher 的线性判别式。
2．求解*
w
从)(w J F 的表达式可知，它并非w 的显函数，必须进一步变换。
已知：∑∈=
i
k Y y k
i i y
n m 1，2,1=i , 依次代入(4.5-1)和(4.5-2)，有：
i T
X x k i
T
k X x T i
i M w x n w x w n m i k i
k ===
∑
∑
∈∈)1(
1，2,1=i (4.5-6)
所以：2
212
2
12
21||)(||||||||M M w M
w M w m m T
T
T
-=-=-
w S w w M M M M w b T
T
T
=--=))((2121 (4.5-7) 其中：T
b M M M M S ))((2121--= (4.5-8)
b S 是原d 维特征空间里的样本类内离散度矩阵，表示两类均值向量之间的离散度大小，因此，b S 越大越容易区分。
将(4.5-6)i T
i M w m =和(4.5-2)∑∈=
i
k X x k
i
i x
n M 1代入(4.5-4)2
i S 式中：
∑∈-=
i k X x i T k T
i M w x w
S 2
2
)(
∑∈⋅--⋅
=i
k X x T
i k i k
T
w M x M x
w ))((
w S w i T
= (4.5-9)
其中：T
i X x k i k
i M x M x
S i
k ))((--=
∑=，2,1=i (4.5-10)
因此：w S w w S S w S S w T
T
=+=+)(212
22
1 (4.5-11) 显然：21S S S w += (4.5-12)
i S 称为原d 维特征空间里，样本“类内离散度”矩阵。
w S 是样本“类内总离散度”矩阵。
为了便于分类，显然i S 越小越好，也就是w S 越小越好。
将上述的所有推导结果代入)(w J F 表达式：
w J w T
b T
F =
)( —— 广义Rayleigh 商 (4.5-13)
式中b S 和w S 皆可由样本集X 计算出。
用lagrange 乘子法求解)(w J F 的极大值点。
令分母等于非零常数，也就是：0≠==c w S w c w T。
定义lagrange 函数：
)(),(c w S w w S w w L w T
b T --=λλ (4.5-14)
L 对w 求偏导数：
)(2),(w S w S w
w L w b λλ-=∂∂
令
0),(=∂∂w
w L λ得到：
*
*w S w S w b λ= (4.5-15)
从上述推导(4.5-10)～(4.5-12)可知，w S 是d 维特征的样本协方差矩阵，它是对称的和半正定的。
当样本数目d n >时，w S 是非奇异的，也就是可求逆。
则：*
1
*
w S S w b w
-=λ (4.5-16)
问题转化为求一般矩阵b w
S S 1
-的特征值和特征向量。
令A S S b w
=-1
，则λ是A 的特征根，*
w 是A 的特征向量。
*
2121*
}))({(w M M M M w S T
b --=
})){((*
2121w M M M M T
--=
γ⋅-=)(21M M (4.5-17)
式中：
*
21)(w M M T -=γ
是一个标量。
所以*
w S b 总是在)(21M M -方向上。
将(4.5-17)代入到(4.5-15)，可以得到：
)(211
*
M M S w w
-=
-λ
γ
其中，
λ
γ是一个比例因子，不影响*
w 的方向，可以删除，从而得到最后解：
)(211
*
M M S w w
-=- (4.5-18)
*
w 就使)(w J F 取得最大值，*
w 可使样本由d 维空间向一维空间映射，其投影方向最好。
)
(211
*
M M S w w
-=-是一个Fisher 线性判断式。
讨论：
如果21M M =，0*
=w ，则样本线性不可分。
21M M ≠，未必线性可分。
w S 不可逆，未必不可分。
3.Fisher 算法步骤
由Fisher 线性判别式)(211
*
M M S w w
-=-求解向量*
w 的步骤：
① 把来自两类21/w w 的训练样本集X 分成1w 和2w 两个子集1X 和2X 。
② 由∑∈=
i
k X x k
i
i x
n M 1，2,1=i ，计算i M 。
③ 由T
i X x k i k
i M x M x
S i
k ))((--=
∑=计算各类的类内离散度矩阵i S ，2,1=i 。
④ 计算类内总离散度矩阵21S S S w +=。
⑤ 计算w S 的逆矩阵1
-w S 。
⑥ 由)(211
*
M M S w w
-=-求解*
w 。
这一节所研究的问题针对确定性模式分类器的训练，实际上，Fisher 的线性判别式对于随机模式也是适用的。
Fisher 算法注释:
（1）Fisher 方法可直接求解权向量*
w ；
（2）对线性不可分的情况，Fisher 方法无法确定分类，Fisher 可以进一步推广到多类问题中去。