标准和草图Fisher核判别分析的性质

                      本文是来自北京科技大学刘佳敏老师的分享

Fisher核判别分析是基于Fisher线性判别分析提出的一种经典的非线性分类方法。但是在大数据分析中，Fisher核判别分析的计算面临很大的挑战。本文将介绍近期发表在人工智能、模式识别与计算机视觉领域国际顶尖期刊《IEEE Transactions on Pattern Analysis and Machine Intelligence》上的一篇工作，论文在再生核希尔伯特空间（RKHS）中研究了Fisher核判别分析的理论性质，并提出用随机草图矩阵来降低计算复杂度。原文如下：

J. Liu, W. Xu, F. Zhang and H. Lian, "Properties of Standard and Sketched Kernel Fisher Discriminant," in IEEE Transactions on Pattern Analysis and Machine Intelligence, doi: 10.1109/TPAMI.2023.3242681.

Fisher核判别分析(Kernel Fisher Discriminant, KFD)是基于核技术对Fisher线性判别的一种非线性扩展。首先我们简单回顾线性判别分析的基本思想：寻找一个投影方向将样本进行很好地分类，即各组内方差最小。令表示样本量为的一组样本，其中为观测到的特征，表示样本属于的类别。方便起见，我们假设样本顺序为 , 且。对于此分类问题，我们通常可以找到个投影方向。令

分别为第组的均值和整体均值。对于向量，令。定义, 组内方差和组间方差可以表示为和。如果用 维的矩阵表示个投影方向，线性判别分析的优化问题可以表示为：

该问题的解是矩阵的前个特征向量。为克服非线性问题，Mika et al. (1999)提出Fisher核判别分析。令是从到高维特征空间的映射，核判别分析是在特征空间中解优化问题：

但是上述优化问题是在样本层面定义的，估计的总体形式尚不清楚，并且渐近性质也很少被研究。为此，我们将基于算子理论，给出标准KFD的总体形式，并给出其解的收敛性。但是，标准KFD的计算复杂度为。因此，我们进一步考虑了基于草图矩阵（sketch matrix）的草图KFD估计来降低计算负担，并给出近似解的理论性质。

为便于表述，我们先介绍一些记号。令是的分布。空间中的范数记为。令是定义在上的正定核。定义函数和的内积为

相应的范数定义为。在这个内积下定义再生核希尔伯特空间，再生性是指对任意函数, 都有。对于函数，定义。

1 标准Fisher核判别分析

1.1 标准Fisher核判别分析的总体形式

直观上，RKHS中的Fisher判别的思想是在中找到一个函数，使得对于不同的尽可能分开，而是最小的。我们首先用来定义组内方差算子。令，我们有，其中通过定义。类似地，组间方差算子可以用来定义。定义总方差算子用。由于，因此总方差可以分解为组间方差和组内方差，即。进一步，RKHS中Fisher核判别分析的优化问题可以表示为：

由于, 上述优化问题也等价于

一个理论问题是(1)中的极值是否可以通过中的某个实现，否则投影方向在RKHS框架中没有明确定义。因此我们证明了，当是上的紧算子时，优化问题(1)在中有解。假设前个投影方向存在，则KFD的第个方向为：

即的特征函数。

1.2 标准Fisher核判别分析的估计

如上所述，在总体形式下，第一个投影方向为：

其中是的最大特征值。假设前个特征值为，KFD的个投影方向为对应的特征函数。给定i.i.d样本，我们分别用和估计和，其中。我们可以通过的最大特征值对应的特征函数估计，即：

其中是正则参数。这等价于求解正则优化问题：

根据表示定理，该优化问题的解可以写成。把它代入上式，求解KFD的估计将转换为求解特征值问题：

其中为维的核矩阵且

是一个块对角矩阵，其中为的元素全为1的矩阵。KFD的第一个投影方向为，其中从(4)中解得。我们首先研究了与(2)中 的收敛性，其余特征方向的收敛性也类似。

的收敛速度与下面定义的复杂度函数有关。设核矩阵的特征值分解为：, 其中是正交矩阵，为元素为的对角矩阵，核复杂度函数定义为

进一步定义

和

核复杂度函数的总体形式为

并可以定义

Koltchinskii and Yuan(2010)表明，和同阶的，因此我们不区分两者，只是将写成。下面的定理给出以上KFD估计的收敛速度：

定理1 假设 是问题(2)的个特征函数，对应于前个特征值，(4)的前个特征向量满足。令，其中 是的第个元素。当且充分大时，存在常数, ，使得

2 草图Fisher核判别分析

当样本量很大时，求解(4)中的特征值问题是比较困难的。因此我们提出用随机草图的方法来得到近似解以减轻计算负担。但是由于草图矩阵需要作用在维的核矩阵上，因此草图KFD只能定义在样本层面，与标准KFD的(4)类似。为得到随机草图近似解，我们首先构造一个随机矩阵，其中。常用的sketch矩阵有亚高斯矩阵和随机正交矩阵(randomized orthogonal system, ROS)。对于亚高斯矩阵，中的元素是独立的亚高斯随机变量，例如方差为的高斯随机变量。在ROS中，从维的固定正交矩阵中无放回的随机抽取列，并随机改变元素的正负来得到随机矩阵。当时，使用可以减少计算量，但理论上必须满足适当的条件，这样草图估计器才能获得所需的统计性质。接下来我们介绍了草图矩阵的-satisfiable性质，这意味着的大小取决于所选择的投影矩阵的类型，并且为保证草图估计和标准估计具有相同的收敛率，应该随发散。

的-satisfiable性是指，存在常数使得

其中由的前列组成，由剩余的列组成，。Yang et al.(2017)的Lemma 5表明，对于高斯草图矩阵，当时， 或者对于ROS，当时,，矩阵大概率是-satisfiable的。

对于给定的，草图KFD估计可以定义为如下的特征值问题：

进而，

其中是维向量的第个元素。因此草图KFD和判别分析的主要思想是：对(4)中的和分别左乘和右乘sketch矩阵，使新的特征值问题的大小为，因此当时便于计算。下面的命题建立了草图KFD的特征值问题(5)和其总体形式间的联系。

命题1  假设具有-satisfiable性质，且对于充分大的常数有。给定任意的和，令，。如果，则。

基于命题1，定理2给出草图KFD估计的收敛性。定理2也说明，当至少和一样大时，草图KFD的估计误差和标准KFD的估计误差接近。同时，定理1的结论可以视为是sketch矩阵取单位矩阵时定理2的特例。

定理2 假设 是问题(2)的个特征函数，对应于前个特征值，(5)的前个特征向量满足。令。如果具有-satisfiable性质，当且充分大时，存在常数, ，使得

3 数值模拟

我们在二维情形下，模拟了两分类和三分类问题，分别计算标准KFD和草图KFD估计的MSE()以及分类错误率，并比较了两种方法的运行时间。模拟结果表明sketch矩阵的选择对估计误差（MSE）的影响很小。随着增加（但仍小于时），草图KFD的估计误差会收敛到标准KFD的估计误差，分类错误率也快速降低。最后，我们通过四个二分类数据集再次比较了标准KFD和草图KFD的分类错误率。

4 小结

论文研究了标准Fisher核判别分析和草图Fisher核判别分析的性质。基于算子理论，我们首先定义了总体水平下Fisher核判别分析的优化问题，给出了估计形式及理论性质。为了减轻较大时的计算负担，我们基于随机sketch矩阵考虑了Fisher核判别分析的近似解。理论结果表明，当远小于时，草图估计量具有与标准估计量相同的收敛速度。最后，我们用一些数值例子说明了草图KFD的表现。

参考文献

[1] S. Mika, G. Ratsch, J. Weston, B. Scholkopf, and K. Mullers, “Fisher discriminant analysis with kernels,” in Neural Networks for Signal Processing, 1999, pp. 41–48.

[2] V. Koltchinskii and M. Yuan, “Sparsity in multiple kernel learning,” The Annals of Statistics, vol. 38, no. 6, pp. 3660–3695, 2010.

[3] Y. Yang, M. Pilanci, and M. J. Wainwright, “Randomized sketches for kernels: Fast and optimal nonparametric regression,” Annals of Statistics, vol. 45, no. 3, pp. 991–1023, 2017.