2.3 小样本情况下的线性鉴别分析_人工智能：模式识别-QQ阅读男生玄幻网

上QQ阅读APP看本书，新人免费读10天

设备和账号都新为新人

2.3 小样本情况下的线性鉴别分析

本书2.2节所讨论的各种费希尔线性鉴别分析方法的构架都是建立在大样本情况下的，即要求类内散布矩阵是非奇异的。然而，在图像识别领域存在着大量的典型的小样本问题，在该类问题中，类内散布矩阵是奇异的。这是因为待识别的图像向量的维数较高，而在实际问题中难以找到或根本不可能找到足够多的训练样本来保证类内散布矩阵的可逆性。因此，在小样本情况下，如何抽取费希尔最优鉴别特征成为一个公认的难题。目前，处理该问题的方法概括起来可分为以下两类。

一类是从模式样本出发，通过事先降低样本向量的维数来达到消除奇异性的目的。基于这一思想的处理方法又可以分为两种：一种是直接在图像空间内操作，通过降低图像的分辨率达到降维的目的^[9，10]；另一种是通过PCA变换进行降维，最为典型的例子是Belhumeur^[16]等提出的Fisherfaces方法和Liu^[17]提出的EFM方法。前一种方法无疑损失了图像的某些细节信息，而后一种方法舍弃了次分量上的投影信息。也就是说，尽管通过这两种降维方法可以消除奇异性，但都是以鉴别信息的损失为代价的，从而无法保证所抽取的特征是最优的。

另一类方法是从算法本身入手，发展直接针对小样本问题的算法来解决问题。Liu^[13]、Guo^[15]、Hong^[18]和Chen^[19]等人分别在这方面进行了探索，他们所建立的算法理论无疑为这一问题的彻底解决奠定了基础。但就其算法本身而言，存在着一个共同的弱点，那就是需要在原始样本空间内求解最优鉴别向量集。比如，对于92×112分辨率（该分辨率并不算高）的图像，其对应的原始样本空间的维数高达10 304。在如此高维的空间内求解最优鉴别向量集，所耗费的计算量是可想而知的。也就是说，就计算量而言，利用以上方法从高维的原始图像向量上直接抽取最佳鉴别特征几乎是不可行的。

本节建立了高维、小样本情况下线性鉴别分析的统一的理论框架^[20]，在该框架下，无论是Foley-Sammon线性鉴别，还是统计不相关线性鉴别，都可以拓展为直接处理高维奇异性问题的方法。该方法体现了通过变换（映射）降维来消除奇异性的思想，但与Fisherfaces方法有着根本的区别，那就是在利用映射原理进行降维的过程中，不损失任何费希尔最优鉴别信息。从理论上我们证明了这一点。另外，更为重要的是，在我们的理论框架下，求解最优鉴别向量集的全过程只需要在一个低维的变换空间内进行，这一点与以往的各种算法，如Liu^[13]、Guo^[15]、Hong^[18]和Chen^[19]等提出的算法，有着本质上的不同。

在以上理论框架下，本节具体给出Foley-Sammon线性鉴别分析和不相关线性鉴别分析的实现方法，并在分析了两者优缺点的基础上，进一步发展了小样本情况下线性鉴别分析的理论，建立了能同时融合二者优点而消除彼此弱点的组合鉴别分析方法。

2.3.1 两种线性鉴别方法的统一模型

在此，我们采用准则函数式（2-5）进行讨论。首先，给出Foley-Sammon线性鉴别和不相关线性鉴别的统一描述。

Foley-Sammon最优鉴别向量集是满足以下正交条件且使得费希尔准则函数达到极值的一组鉴别向量ϕ₁，…，ϕ_d：

具体地讲，该最优鉴别向量集的第一个鉴别向量ϕ₁取为费希尔最优投影方向；当前i个鉴别向量ϕ₁，…，ϕ_i取定后，第i+1个鉴别向量可由求解以下最优化问题得到：

这里，；Ω表示可行解空间（即最优鉴别向量的取值空间），它对应着原始样本空间R^N，即Ω=R^N。

不相关最优鉴别向量集ϕ₁，…，ϕ_d满足以下共轭正交条件：

不相关最优鉴别向量集的第一个鉴别向量ϕ₁取为费希尔最优投影方向；前i个鉴别向量ϕ₁，…，ϕ_i取定后，第i+1个鉴别向量仍可利用模型2-3确定，不过此时模型中的内积定义为：。

我们知道，当总体散布矩阵S_t可逆时，最优鉴别向量集的问题在本书2.2节中已经得到圆满解决。接下来，具体讨论S_t奇异情况下最优鉴别向量集的求解问题。

2.3.2 压缩映射基本原理

解决问题的总体思想是，在不损失任何有效鉴别信息的前提下，利用映射原理，将高维的原始样本空间变换为低维的欧几里得空间。而在低维的欧几里得空间内，总体散布矩阵是可逆的。这样，我们不仅消除了奇异性，而且大大缩小了最优鉴别向量的搜索范围，即求解最优鉴别向量只需要在低维的欧几里得空间内进行。

首先分析在奇异情况下，可行解空间R^N的构成。

设β₁，β₂，…，β_N表示S_t的标准正交的特征向量，则R^N=span{β₁，β₂，…，β_N}。

定义2-1 定义R^N的子空间Φ_t=span{β₁，β₂，…，β_m}，其正交补空间为，其中，m=rank（S_t），β₁，β₂，…，β_m为S_t的非零特征值所对应的标准正交的特征向量。

引理2-5 设A为一个N×N非负定矩阵，ϕ为一个N维向量，则ϕ^TAϕ=0，当且仅当Aϕ=0。

由引理2-5易得，为矩阵S_t的零空间。

引理2-6 当矩阵S_t奇异时，ϕ^TS_tϕ=0，当且仅当ϕ^TS_wϕ=0，并且ϕ^TS_bϕ=0。

证明：因为S_w、S_b非负定，故ϕ^TS_wϕ≥0且ϕ^TS_bϕ≥0。

又ϕ^TS_tϕ=ϕ^TS_wϕ+ϕ^TS_bϕ，所以，ϕ^TS_tϕ=0当且仅当ϕ^TS_wϕ=0并且ϕ^TS_bϕ=0。证毕。

定义2-2J_b（ϕ）=ϕ^TS_bϕ，J_w（ϕ）=ϕ^TS_wϕ。

对于任意φ∈R^N，由定义2-1，φ可表示为φ=ϕ+ξ，其中，ϕ∈Φ_t，。映射L：R^N→Φ_t定义如下：

易证明，L是从R^N到Φ_t的线性变换，我们称之为压缩映射，如图2-1所示。

图2-1 压缩映射示意图

定理2-9 （压缩映射原理）在压缩映射L：φ=ϕ+ξ→ϕ下，有

J_f(φ)=J_f(ϕ),J(φ)=J(ϕ)

证明：由引理2-5、引理2-6和的定义可知，ξ^TS_bξ=0，ξ^TS_bϕ=0。

因此，φ^TS_bφ=ξ^TS_bξ+2ξ^TS_bϕ+ϕ^TS_bϕ=ϕ^TS_bϕ。

故J_b（φ）=J_b（ϕ）。

同理可证，J_w（φ）=J_w（ϕ）。

由定义2-2和准则函数式（2-15）和式（2-16）的定义可知，J_f（φ）=J_f（ϕ），J（φ）=J（ϕ）。

定理2-9告诉我们，最优鉴别向量可在子空间Φ_t内选取，就费希尔准则而言，不损失任何最优鉴别信息。也就是说，根据压缩映射原理，模型2-3等价于

2.3.3 同构映射基本原理

以下我们讨论如何求解模型2-4。

由定义2-1可知，dim（Φ_t）=m。根据线性代数理论，Φ_t同构于m维欧几里得空间R^m，相应的同构映射定义为

该映射是从R^m到Φ_t上的一一映射。

在同构映射ϕ=Pξ下，准则函数J（ϕ）变为

定义以下两个函数：

这里，。

易证明，均为m阶非负定矩阵，故可视为类似于J（ϕ）的一个准则函数。此外，由定义2-1可知，是可逆矩阵，故是正定的。

易证明，同构映射具有以下性质，即定理2-10。

定理2-10 （同构映射原理）设ϕ=Pξ是R^m到Φ_t上的同构映射，则ϕ^∗=Pξ^∗是准则函数J（ϕ）或J_b（ϕ）的极值点，当且仅当ξ^∗是准则函数或的极值点。

定理2-11 设矩阵P=（β₁，β₂，…，β_m），ϕ_i=Pξ_i，ϕ_j=Pξ_j，则

（1）ϕ₁与ϕ₂正交，当且仅当ξ₁与ξ₂正交；

（2）ϕ₁与ϕ₂关于S_t共轭正交，当且仅当ξ₁与ξ₂关于共轭正交。

证明：（1）由已知条件P^TP=I（单位阵），故，命题得证。

（2）由于，故结论成立。

在同构映射ϕ=Pξ下，模型2-4变换为

根据定理2-10和定理2-11，我们不难得出以下结论，即定理2-12。

定理2-12 设ξ₁，…，ξ_d（d≤m）为模型2-5（令i=1，…，d-1）的最优解，则ϕ₁=Pξ₁，…，ϕ_d=Pξ_d（d≤m）为最优鉴别向量集。

更具体地讲，若模型2-5中的约束条件为正交条件，即，由定理2-12所得的ϕ₁，…，ϕ_d为Foley-Sammon最优鉴别向量集；反之，若该模型中的约束条件为共轭正交条件，即，则由定理2-12所得的ϕ₁，…，ϕ_d为统计不相关最优鉴别向量集。

最后，值得一提的是如何高效地计算以上压缩映射中的矩阵P。既然P的列向量β₁，β₂，…，β_m为S_t的非零特征值所对应的特征向量，我们可根据奇异值分解定理，按照本书2.1.4节提供的方法在M维空间内求解，这里M表示训练样本数。

总的说来，与Liu^[13]、Guo^[15]、Hong^[18]和Chen^[19]等人的方法相比，我们给出的求解最优鉴别向量集的思想具有明显的优势，即最优鉴别向量集的计算只需要在R^m空间内进行。由于m≤M-1，而训练样本数M远远小于原始样本特征的维数N，故我们的方法极大地降低了计算量，提高了求解速度。以ORL人脸图像库为例，图像的分辨率为92×112，图像总数为400幅，一般地，训练样本数取为200。在该情况下，我们的求解算法只需要在199维的空间内进行，而Liu^[13]、Guo^[15]、Hong^[18]和Chen^[19]的方法则需要在92×112=10 304维的空间内进行，这必然耗费大量的计算时间。

2.3.4 奇异情况下线性鉴别分析的实质：PCA+LDA

由定理2-12所得的最优鉴别向量集可构成以下变换进行特征抽取：

这里，W^T=（ϕ₁，ϕ₂，…，ϕ_d）^T=（Pξ₁Pξ₂，…，Pξ_d）^T=（ξ₁，ξ₂，…，ξ_d）^TP^T。

从而该变换可分解为以下两个变换：

现考虑变换Y=P^TX，既然变换矩阵P的列向量为S_t的非零特征值所对应的特征向量，故该变换即为PCA变换，且在变换空间（特征空间）内，样本的总体散布矩阵为

因此，该矩阵恰为。类似地，变换空间内样本的类间散布矩阵为。于是，准则函数的物理意义即为PCA变换空间内的费希尔鉴别准则函数。因此，模型2-5确定的最优解ξ₁，ξ₂，…，ξ_d（d≤m）即为变换空间内基于费希尔鉴别准则的最优鉴别向量集。

从这个角度来看，我们不仅对奇异情况下求解最优鉴别向量集的过程有了更深刻的理解，同时也揭示了奇异情况下费希尔鉴别分析的本质，即先进行主成分分析（PCA），再进行普通的费希尔线性鉴别分析（LDA）。

2.3.5 奇异情况下的组合鉴别分析方法

当S_t奇异时，设m=rank（S_t），β₁，β₂，…，β_m为S_t的非零特征值所对应的标准正交的特征向量，令P=（β₁，β₂，…，β_m）。按照本书2.3.4节提供的理论框架，费希尔最优鉴别特征的抽取过程可分为两步进行：第一步，作PCA变换，Y=P^TX，将高维的原始样本压缩为m维。第二步，在变换空间R^m内，利用费希尔鉴别分析方法进行特征抽取。

因此，只需要在变换空间R^m内讨论问题。设变换空间R^m内的类间散布矩阵、类内散布矩阵和总体散布矩阵分别表示为和。明显地，=P^TS_bP、和，且和为非负定矩阵，为正定矩阵（必可逆）；而且，和的秩满足下面定理2-13中的关系。

定理2-13 。

利用引理2-5、引理2-6和分块矩阵的理论，易证明该定理是成立的。

费希尔准则函数定义为

推广的费希尔准则函数定义如下：

在S_t奇异的情况下，一般地，矩阵S_t的秩m=M-1。其中，M表示训练样本数；矩阵S_w的秩为M-c-1=m-c，这里c表示样本类别数；矩阵S_b的秩为c-1。相应地，在变换空间R^m内，由定理2-13可得

也就是说，在R^m内，类内散布矩阵往往是奇异的。于是，该情况下的有效鉴别向量分为两类，第一类是满足条件和；第二类满足条件和。接下来，具体讨论两类鉴别向量的取值范围。

设γ₁，…，γ_m为的标准正交的特征向量，则R^m=span{γ₁，…，γ_m}。

定义2-3 定义R^m的子空间，其中，γ₁，…，γ_q为的非零特征值所对应的标准正交的特征向量，。的正交补空间为。

定理2-14 在空间R^m内，ξ≠0，则，当且仅当。

证明：先证明充分性。

因为为非负定矩阵，由定义2-3和引理2-5可知：

，必有，j=q+1，…，m。

任意，必可表示为γ_q₊₁，…，γ_m的线性组合，故，则。

必要性由定义2-3易证明。

定理2-15 任意且ξ≠0，有恒成立。

证明：由的正定性，任意ξ≠0∈R^m，有；

又，满足，而，故

任意且ξ≠0，恒有。

定理2-14和定理2-15告诉我们，第一类鉴别向量取值空间为；而第二类鉴别向量只能从集合（R^m-）中取值。明显地，若规定两类鉴别向量之间满足正交条件，则第二类鉴别向量的取值空间为，即为的正交补空间。

1.鉴别准则的优化选择

对于取自空间的任意两个鉴别向量ξ₁和ξ₂，若按照费希尔准则函数的定义式（2-49）来衡量，均有。也就是说，对于第一类的鉴别向量，费希尔准则无法判别哪一个更优，也就失去了鉴别准则的作用。本节借鉴参考文献[19，21]的思想，改用以下准则选取第一类的鉴别向量：

该准则的物理意义是：当投影后的类内散布量为零时，取类间散布量作为衡量投影方向优劣的标准。

式（2-50）中的准则函数等价于以下瑞利商函数：

至于第二类鉴别向量，仍采用费希尔准则函数式（2-49）来衡量。当然，也可采用费希尔准则函数式（2-48）进行衡量，因为当类内散布量不为零时，两准则完全等价。

2.组合最优鉴别向量集的确定

样本往第一类鉴别向量上投影后，其类内散布量为零，这个性质是很好的，故在此我们优先选择第一类鉴别向量。第一类鉴别向量的第i+1个最优鉴别向量可由以下模型确定：

式中，为正交约束条件。当求解第一个最优鉴别向量时，相当于没有该约束条件。由于子空间的维数为l=m-q。因此，令i=0，…，l-1，由模型2-6可确定l个彼此正交的最优鉴别向量ξ₁，…，ξ_l。

第二类鉴别向量ξ_l₊₁，…，ξ_d由以下模型确定：

注意，与模型2-6不同的是，在模型2-7中我们取共轭正交的约束条件。也就是说，所得的第二类最优鉴别向量ξ_l₊₁，…，ξ_d是关于共轭正交的。同时，模型中的约束条件与表明，两类鉴别向量之间是彼此正交的。

我们可利用2.3.2节中建立的同构映射原理直接求解以上两个模型。接下来，先来求解模型2-6。

作同构映射ξ=P₁ψ，其中，P₁=（γ_q₊₁，…，γ_m），模型2-6作同构映射后，可得

式中，，l=m-q，这里为正定矩阵。

既然目标函数等价于瑞利商函数，由瑞利商的极值性质，那么模型2-8的最优解ψ₁，…，ψ_l为的标准正交的特征向量。相应地，由模型2-6确定的最优鉴别向量为ξ_j=P₁ψ_j，j=1，…，l，且为彼此正交的。由同构映射原理可知，它们为准则函数在空间内的极值点。这也是我们为何在模型2-6中采用正交约束的原因。