基于约翰逊-林登斯特劳斯引理的判别性字典学习的最优监督投影方法

《Computers and Electrical Engineering》：Optimal supervised projections for discriminative dictionary learning using the Johnson–Lindenstrauss lemma

　　马杜里·加德瓦尔|阿图尔·内吉|卡卢里·V·兰加拉奥
印度特伦甘纳邦海得拉巴市海得拉巴大学计算机与信息科学学院AI实验室，邮编500046

**摘要**
现有基于降维的字典学习方法多采用迭代随机投影技术。这类方法的收敛性在很大程度上取决于初始种子值。主成分的数量是随机选取的，而随机投影后数据点的几何结构可能因此被破坏。此外，基于梯度下降的更新方式可能导致局部最小值问题。本文提出了一种利用改进的监督主成分分析（MSPCA）和约翰逊-林登斯特劳斯引理来消除投影矩阵随机性的构造性方法。同时，文中还提出了一种启发式方法，用于确定最优的数据扰动程度以及字典原子的合适描述长度（SDL）。该方法并非通过随机投影降低维度，而是使用基于改进的监督主成分分析得到的投影矩阵。该投影矩阵不仅能实现变换后空间中特征与标签的最大一致性，还能保持原始数据的几何结构。经证明，如此构建的投影矩阵属于满足子空间限制等距性质（RIP）的约翰逊-林登斯特劳斯嵌入。尽管泰卢固文存在字符混淆的问题，但在该变换空间中训练得到的字典仍能生成具有较低复杂度的判别性稀疏系数。在人脸识别和光学字符识别数据集上的实验结果表明，该方法在高维多类场景下依然有效，且相比其他基于降维的方法更具优势。

**引言**
对于高维多类信号分类任务，要实现有效的判别性稀疏特征提取，就需要训练一个共享的全局字典。为降低训练多类高维数据字典的复杂度，人们通常会对系数矩阵施加低秩和稀疏性等约束。稀疏表示模型通过寻找稀疏的潜在特征空间，避免了手动设计特征的过程。该模型与哺乳动物视觉皮层的感受野特性类似[1]。在稀疏表示模型中，使用过完备的（列数大于行数）学习字典[2][3]，可以提升表示能力和分类效果。具有所有类别全局及局部特征的低维原子（列）能够构成紧凑的共享过完备字典，从而节省空间和时间。不过，即便如此，训练得到的字典仍需生成具有判别性的系数作为分类特征。

用于降维的主成分分析是通过随机选择主成分数量，将数据映射到低维空间。这些主成分是从数据中直接提取的。如果随机投影无法保持变换后特征空间中的距离关系，那么基于距离的分类器很可能会出现误分类现象[4]。另一种更有效的降维方法是基于局部线性嵌入的均匀流形近似与投影技术[5]。高斯随机投影方法则需要计算K近邻信息以及构建随机投影森林，这会增加计算负担。此外，还存在多种核学习方法用于降维，即从多种核函数中选择最优核函数。例如，MKL-DR方法[6]通过谱回归和迹比最大化来确定最优核函数。但这类方法严重依赖所使用的隐式核函数。在NSSE方法[7]中，研究者们利用从权重矩阵导出的类间和类内拉普拉斯矩阵的拉普拉斯特征映射，提出了非线性监督降维方法。该降维映射通过学习分类器的误差梯度并进行多次迭代来不断优化。稳健且稀疏的线性判别分析方法[8]则通过增加类间差异的同时减少类内差异来提升分类性能。该算法后来又被发展为RSLDA+方法[9]，它采用了混合稀疏正则化技术和交替方向乘子法。不过，RSLDA+方法使用了硬阈值处理机制，这可能会导致一些重要的判别特征丢失。

本文没有采用随机投影进行降维，而是提出了一种基于数学原理的构造性方法，利用约翰逊-林登斯特劳斯引理设计出无随机性的投影矩阵。约翰逊-林登斯特劳斯引理[10]给出了将数据映射到低维空间时所需的最小维度p值，且在此过程中原始数据的几何结构不会发生过度扭曲。如果两个数据点在原始空间中相距较远，但在变换后的空间中却非常接近，那么很有可能这两个数据点会被用同一组字典原子来表示，从而导致错误表示和误分类。针对这一问题，本文提出了基于约翰逊-林登斯特劳斯引理的启发式方法，用于确定合适的数据扰动阈值以及相应的维度，这一方法具有很强的实用价值。根据约翰逊-林登斯特劳斯引理确定的维度p，就成为了变换空间中字典原子的合适描述长度（SDL）。为保持数据点间的成对距离，字典原子的SDL并不取决于数据集的特征，而仅与训练样本数量（N）以及所需的数据扰动程度（?）有关。无监督投影无法保证特征与标签的一致性。为避免出现此类问题，本文还提出了改进的SPCA方法，用于生成包含p个正交奇异向量的无随机性投影矩阵。该投影矩阵是根据复现核希尔伯特空间的希尔伯特-施密特独立性准则[12]设计的，其目的是最大化数据与标签之间的关联度。

与随机选择奇异向量数量的监督主成分分析方法[12]不同，本文提出的MSPCA方法能够根据每个数据集的特点确定最优的奇异向量数量p，进而得到最优的变换矩阵。监督主成分分析方法是在对数据减去均值向量之后才应用的，而这种数据居中处理方式会破坏数据的几何结构和类别相关结构。在信号处理以及人脸识别等图像处理应用中，均值信号往往包含重要信息。本文提出的方法避免了数据居中处理，从而保留了均值信号，同时抓住了数据的能量特征，并通过MSPCA方法生成p个奇异向量。这样一来，均值信号以及有助于数据集分类的次要成分都能被保留下来。确保等距性质的最优投影维度p是通过约翰逊-林登斯特劳斯引理以启发式方式确定的。在变换后的空间中，通过学习字典可以得到具有局部和全局特征的原子，这些原子对应的判别性系数可作为特征，进一步提升分类性能。

•本文提出的JLSPCADL方法用基于MSPCA的确定性、受监督的投影矩阵取代了迭代随机投影，该投影矩阵由奇异向量构成。这些奇异向量的数量是通过约翰逊-林登斯特劳斯引理以启发式方式确定的。
•为保持数据的几何结构，JLSPCADL方法会确定最优的扰动阈值，再利用约翰逊-林登斯特劳斯引理计算出对应的投影维度p，最终得到p个能够最大化特征与标签关联度的受监督分量。
•该方法避免了数据居中处理，从而保留了均值信号，同时抓住了数据的能量特征，因此那些对分类有用的次要成分也不会丢失。
•经证明，该投影矩阵属于约翰逊-林登斯特劳斯嵌入，因此满足子空间限制等距性质。
•在该特征空间中，数据簇既保持分离性又具备最大程度的特征与标签关联度。在该特征空间中学习得到的字典既紧凑又具有判别性。因此，同一类别的样本会使用相同的字典原子，而生成的稀疏系数也具备良好的分离性和判别性。
•在光学字符识别数据集（UHTelPCC、Banti）、手写数字数据集（MNIST、USPS、ARDIS）以及人脸识别数据集（Extended YaleB、Cropped YaleB）上的实验表明，JLSPCADL方法在准确率和计算效率方面通常优于其他基于降维的字典学习方法。

本文中使用的符号说明见表1。第2节将介绍相关研究工作，2.4节则会阐述约翰逊-林登斯特劳斯引理的应用方式。第3节将详细介绍本文提出的字典学习方法，以及该投影矩阵能够使数据满足子空间限制等距性质的详细证明过程。第3.4节会解释分类规则，第4节则会展示实验结果。第5节和第6节分别对实验结果进行分析并得出结论。附录中则会对改进的KSPCA方法及其复杂度进行说明。

**相关研究**
此前已有研究试图先降低数据的维度，再在变换后的空间中学习字典[13]。找到正确的数据嵌入或投影方式至关重要，只有这样，在变换后的空间中学习得到的字典才能生成具有相关性且稀疏的系数，作为有效的判别特征。当类别数量较多时，与其分别为每个类别学习字典并搭配分类器[14][15][16]，不如直接学习一个共享的判别字典，这样的做法在计算成本上更为合理。

**提出的方法：JLSPCADL**
该方法的实施步骤首先是计算最优的数据扰动程度?和最优的投影维度p。随后，通过MSPCA方法（当p≤d时）或M-KSPCA方法（当p>d时）得到包含p个奇异向量的变换矩阵。在变换后的空间中，可以学习到共享字典以及对应的判别性稀疏系数。JLSPCADL方法的框架如图1所示。

**实验与结果**
由于YaleB人脸识别数据集的维度远高于样本数量，因此被选为实验对象。Extended YaleB和Cropped YaleB数据集由于姿态和光照条件不同，分类难度较高。泰卢固文光学字符识别数据集UHTelPCC和Banti存在严重的类别不平衡问题，且字符较为相似，同时由于字体不同还会出现类内差异。手写数字数据集MNIST、ARDIS和USPS则存在类间相似性，同时由于字体不同也会出现类内差异。

**讨论**
通过MSPCA方法得到的约翰逊-林登斯特劳斯嵌入U能够在保持数据全局几何结构的同时，借助改进的SPCA组件（基于希尔伯特-施密特独立性准则）实现特征与标签的最大程度一致性。在具有最大特征与标签一致性的变换空间中，可以学习到特定于各类别的原子以及对应的稀疏系数。通过高斯先验群对原子进行自动相关性筛选，最终可以在字典中得到特定于各类别的原子。根据……的类型……

**结论**
本文提出了一种基于降维的深度学习方法——JLSPCADL。约翰逊-林登斯特劳斯引理为确定字典原子的合适描述长度提供了依据，从而使子空间具备可分离性；而MSPCA方法则能确保变换矩阵包含约翰逊-林登斯特劳斯引理所规定的最优数量的分量，进而实现特征与标签的最大程度一致性。与其他监督投影方法不同，JLSPCADL方法得到的变换矩阵能够保持原始数据点之间的距离和角度。

**利益冲突声明**
作者声明不存在任何可能影响本文研究成果的已知财务利益或个人关系。

**致谢**
作者感谢匿名审稿人提出的宝贵意见和建议，这些意见和建议帮助提升了文章的质量。第三位作者衷心感谢海得拉巴大学计算机与信息科学学院的领导及全体工作人员一直以来给予的支持与配合。第一位作者马杜里·加德瓦尔感谢印度大学拨款委员会授予的UGC–NET JRF/SRF奖学金（编号20688）。