Abstract：
极限学习机自动编码器（extreme learning machine auto-encoder ：ELM-AE）的抽象降维（DR）领域取得了不错的效果。然而现有的ELM-AEs仅以无监督的方式考虑DR问题，当这些信息可用时忽略了有价值的监督信息。为了发现原始数据的区别特征，本文提出了一种基于图嵌入的基于ELM的DR框架（graph embedding-based DR framework with ELM：GDR-ELM）。提出的GDR-ELM不需要自重构，而是根据包含监督信息的图矩阵中的权值重构所有样本。此外，GDR-ELM可以像其他ELM-AEs一样作为构建块来构建多层框架，用于更复杂的表示学习任务。在不同数据集上的实验证明了所提出的GDR-ELM及其多层框架的有效性。
Introduction：
降维技术在计算机视觉和机器学习领域的应用越来越广泛，自动编码器（auto-encoder，AE）已成为DR领域的一个新的发展方向，AE将原始的高维数据转换为低维特征。近年来的研究表明，AE在表征学习任务中具有很好的应用前景。然而，这些方法的BP（back-propagation）训练过程非常耗时，并且容易陷入局部最优解。因此，研究人员有兴趣开发一种能够快速从原始数据中学习有意义表示的AE。极限学习机（ELM）最初是作为一种具有良好泛化能力和快速训练速度的“广义”单隐层前馈网络（SLFN）提出的。
基于ELM的自动编码器（ELM-AE）技术优点有两方面：一方面，这些ELM-AEs能够高效地从原始数据中提取有意义的表示。另一方面，ELM-AEs也可以作为构建块来构建多层体系结构，以解决更复杂的特征学习问题，而不需要繁琐的微调。其缺点也有两个方面：一方面ELM-AEs只无监督的的DR问题，忽略了有价值的标签信息。另一方面：经典的ELM-AE算法在提取压缩表示时可能会破坏原始数据中的距离信息。这种距离违规问题会导致ELM-AEs的压缩表示不太满意和性能不稳定。所以在此基础上对 ELM-AE技术进行了改造，提出了基于图嵌入的ELM降维方法（ graph embedding based DR with ELM：GDR-ELM ）
GDR-ELM 主要思想是通过嵌入一个图矩阵，以有监督的方式在ELM-AE框架中执行DR过程。与现有的ELM-AEs只考虑自重构不同，GDRELM尝试根据图矩阵中的权值来重构所有的样本。在有监督信息的情况下，我们的方法利用了同一类的内在特征，保证了不同类之间的区别。此外，引入图学习可以解决上述距离违规问题，保证算法的稳定性。本文的贡献总结如下。
（1）比较现有的ELM-AEs算法，GDR-ELM算法从原始数据中提取有区别的低维表示，具有更稳定的性能。GDR-ELM的解可以用封闭形式（ closed form）计算。
（2）在一定的图矩阵下，我们的方法将退化为经典的ELM-AE，这表明经典的ELM-AE是我们的GDR-ELM的一个特例。
（3）提供了经典ELMAE作为DR算法时的理论分析，这在以前的相关工作中是没有研究过的
（4）提出的GDR-ELM也可以像其他ELM-AEs一样作为构建块来建立多层GRD-ELM网络。
（5）实验结果证明了该方法的有效性。
总结：利用自动编码器（auto-encoder）降维但是速度比较慢，所以引入ELM进行加速，但是ELM-AE是无监督存在忽略标签信息和性能不稳定的缺点，所以引入图矩阵进行监督，保证其鲁棒性。
Related Work:
（一）、DR技术：从传统方法到（auto-encoder）AEs：
相对于过去的降维技术，自动编码降维技术（auto-encoder：AE）具有更加优越的性能（这项技术也是有T-SNE降维技术的提出者之一Hinton教授提出来的，AutoEncoder的思想最早被提出来要追溯到1988年[1]，当时的模型由于数据过于稀疏高维计算复杂度高很难优化，没能得到广泛的引用。直到2006年，Hinton等人采用梯度下降来逐层优化RBM（受限玻尔兹曼：Restricted Boltzmann Machine）从而实现对原始样本/特征的抽象表示，并在特征降维上取得显著效果。这才使得采用神经网络来构建AutoEncoder的方法得到广泛关注。），具有很强的提取特征的鲁棒性。但是存在过拟合的问题，AutoEncoder框架的基本思想，如下图所示：
（二）、极限学习机（Extreme Learning Machine:ELM）
极限学习机是新加坡南洋理工大学黄广斌教授建立的一个模型，即一个单隐藏的前馈神经网络。但是与传统的前馈神经网络不同，ELM 的主要思想是：（机器或生物）学习可以不需要调整隐层节点，也就是说 ELM 网络隐藏层节点的权重随机生成或者人工定义，学习过程仅需计算输出权重。ELM也被修改以发现原始数据的低维嵌入，例如无监督ELM（US-ELM）、判别聚类ELM和谱回归ELM（SRELM）。与这些DR方法相比，该方法利用AE结构来处理DR问题。此外，我们的GDR-ELM可以用来构建一个深层的体系结构，并且这种分层堆叠的GDR-ELM可以进一步提高DR任务的性能。
ELM最大的贡献主要有两个：
（1）输入层和隐含层的连接权值、隐含层的阈值可以随机设定，且设定完后不用再调整。这和BP神经网络不一样，BP需要不断反向去调整权值和阈值。因此这里就能减少一半的运算量了，目前ELM已经被应用于解决迁移学习问题、工业领域。
（2）隐含层和输出层之间的连接权值β不需要迭代调整，而是通过解方程组方式一次性确定。研究表明，通过这样的规则，模型的泛化性能很好，速度提高了不少。一言概之，ELM最大的特点就是对于传统的神经网络，尤其是单隐层前馈神经网络(SLFNs)，在保证学习精度的前提下比传统的学习算法速度更快。
极限学习机不是一个新的东西，只是在算法（方法）上有新的内容。在神经网络结构上，就是一个前向传播的神经网络，基本框架如下：
NOTATIONS AND BACKGROUND
（一）Notations
Let {X,T} = {(xi,ti)}Ni=1和H = {hi∈ R1×L}Ni=1分别是一组N个标记样本及其对应的隐藏表示，其中D是样本的原始维数，L是隐藏节点数。在图1中，ELM中的随机矩阵用A∈RD×L表示，重建权值和特征提取矩阵用β∈RL×D表示，ELM-AE中的正则项系数用C表示，IL是L×L恒等式矩阵。在图1中，我们使用表示输入样本席的重建。经典的ELM-AE和GDR-ELM分别利用重建误差图1（a）和（b）来寻找特征提取矩阵。图矩阵S中的重构权重用sij表示。此外，用dj表示S的第i列中所有元素的和，D是对角线为di的对角矩阵。在生成矩阵S的过程中，最近邻（NN）的个数用p表示。
（二）Background
ELM-AE
ELM-AE的主要思想是通过最小化原始输入和重建输出之间的重建误差来寻找原始数据的有效表示。给定样本席，ELM-AE首先使用A（正交随机权）、偏差b（输入节点和隐藏节点之间的正交随机偏差）、g是一个激活函数（sigmoid函数）来对样本进行投影，然后隐藏层用表示为
ELM-AE聚类算法步骤：
multilayer ELM-AE
分层叠加ELM-AEs可以建立多层ELM-AE结构，其表示形式可以由
在ML-ELM中添加层。（a）ELM-AE相对于输入数据x的输出权重β1是ML-ELM的1层权重。（b）相对于ML-ELM的隐藏层输出hi，ELM-AE的输出权重βi+1是ML-ELM的（i+1）第三层权重。（c）使用正则化最小二乘法计算ML-ELM输出层权重。
Graph Embedding-Based Dimension Reduction framework With ELM
（一）GDR-ELM
这部分首先提出GDR-ELM。然后介绍了如何构造一个图矩阵，以及如何以封闭形式求解GDR-ELM问题。此外，还对嵌入图提高ELM-AE性能的原因进行了理论分析。
GDR-ELM与ELM-AE相似，GDR-ELM首先使用A将输入随机映射到隐藏层表示，然后使用β根据重建权重sij在图矩阵S重建样本，的加权重建误差表示为
（二）Graph Matrix
在这一部分中，构造了一个适当的图矩阵，其中包含原始数据的标签和流形信息。如我们所见，如果矩阵S等于一个恒等式矩阵，则GDR-ELM将退化为经典ELM-AE。
图构造的核心思想：
（1）对于具有多个不同类别邻域的样本，我们称之为“边缘样本”（marginal samples），重建边缘样本可能会导致识别率降低。因此，我们在边缘样本的自重构上投入较少的精力，而在“内部样本”（其大多数邻域来自同一类）的重构上投入更多的精力，以保证学习特征的识别。见图2（a）。
（2）除了自重构外，利用隐层表示来重构相似数据（样本与同一类的欧氏距离较小）可以帮助算法将同一类的样本聚集在所得到的子空间中。见图2（b）。
（三）Solving the GDR-ELM
公式（8）可以通过将关于β的J的梯度设置为0以封闭形式解决：
如前所述，经典ELM-AE中的随机投影会破坏距离信息。在这里，我们提供了一个简单的例子来说明这种损害是如何发生的。给定二维空间中的两类（图3），ELM-AE首先用随机向量（红线）将原始数据投影到随机一维空间。当随机向量位于区域a时，原始数据的判别信息数据还在。当位于B区域时，会出现违例问题，并且会损坏判别信息（特别是当随机向量接近y坐标时，会损坏所有判别信息）。这可能会对提取的特征造成不良影响。
然而，GDR-ELM可以通过嵌入图来纠正这种违反。为了进一步了解它，我们提供以下分析。在不丧失一般性和简化分析的情况下，我们放弃了正则化项。那么公式（8）可以表示为：
方程（14）是ELM-AE问题。在（14）中，第一项找到近似于隐藏层表示的β，第二项找到保持输入数据的最大变化的β。第二项和第三项可以平衡自己，这意味着它防止||β||不要太大（因为x和h都是有界的）。从分析中可以看出，ELM-AE的工作原理与PCA类似。逼近隐层表示可以进一步提高ELM-AE的泛化能力。然而，当隐藏表示中的鉴别信息被破坏时，ELM-AE的性能无法得到保证。在（13）中，一方面，第二项搜索这些内部样本变化最大的方向。另一方面，（13）中的第一项通过控制样本对的重构努力，帮助GDR-ELM提取鉴别特征。（14）中的第一项表明，ELM-AE发现的特征近似于重叠的隐藏层表示。因此，获得的特征可以不那么具有区分性。在图3中，重建蓝色部分中的隐藏表示可以导致来自两个类的样本在获得的子空间中重叠。虽然GDR-ELM也重建了隐藏层表示，但它嵌入了一个图矩阵来控制重建的力度，从而使GDR-ELM能够保留原始数据中的鉴别信息。因此，即使当随机投影矩阵位于区域B时，GDR-ELM也可以解决冲突问题，并且仍然可以成功地提取鉴别特征。这在补充材料I-A节的分析实验中得到了证实。
Multilater GDR-ELM Framework
基于ELM-AE的多层框架比单层网络具有更好的性能。在本节中，我们将展示如何将我们的方法扩展到使用GDR-ELM作为构建块的多层GDR-ELM（GDR-ML-ELM）体系结构
如图4所示。在GDR-ML-ELM中，前一个网络的输出被用作下一层的输入。网络可以作为独立的部分进行分层训练。最后的特征可以用第k层表示来表示。该算法可以描述如下。定义矩阵S后，使用GDR-ELM的网络第一层从原始数据X中提取特征，新的表示可以写成
无需BP算法，可解析计算各层的全局最优解。第二，多层网络建立后，不需要微调。这种训练机制保证了GDR-ML-ELM的快速性。与其他多层ELM-AEs相比，GDR-MLELM以有监督的方式解决DR问题。因此，可以发现更多的区别特征。此外，由于ELM-AEs可能会遇到冲突问题，使用ELM-AEs构建多层体系结构可能会进一步放大这种冲突问题。然而，GDR-ML-ELM解决了每个GDR-ELM块中的违规问题，并确保了性能的稳定性。除了充当DR方法外，我们的方法还可以看作是一个多层感知器框架（这意味着隐藏的数量不必小于输入维度）。框架的最后一层可以是经典的ELM，也可以使用最小二乘法进行分类任务。
Multilayer GDR-ELM步骤;
Performance evaluation and analysis
（一） Analytical Experiments
通过两个实验验证了GDR-ELM算法是否能有效地解决冲突问题，以及GDR-ELM算法是否能比经典的ELM-AE算法找到更具鉴别能力的特征。
(二) Performance Evaluation of the GDR-ELM
数据集规范：实验中的数据集包括UCI存储库中的页面块分类（PageBlocks）、陆地卫星（Landsat）、葡萄酒和DrivFace（DrivF）数据集、LIBSVM中的DNA和蛋白质数据集、和一些流行的图像数据集。哥伦比亚物体图像库（COIL20）是一个包含1440个灰度图像的多类图像分类数据集。在实验中，图像大小调整为32×32。USPST数据集是美国邮政（USPS）手写数字数据集4的一个子集（测试集），由2007张16×16的数字0到9的图片组成。有关数据集的信息列在表一中。
超参数选择：需要搜索两个指定参数，包括正则化项C和生成邻接矩阵的最近邻域p（NN）。我们使用UMIST人脸数据集、UPSPT数据集和Wine数据集来测试这些不同超参数的变化对性能的影响。结果如图5所示。
表二的实验结论有一下三点:
（1）本文提出的GDR-ELM方法在两个方面都优于其他基于ELM的灾难恢复方法：a）较高的精度和b）较低的标准偏差。这是由GDR-ELM以有监督的方式解决DR问题，并发现有利于后续分类的更具歧视性的特征来解释的。此外，较低的标准差表明，GDR-ELM保证了GDR-ELM的稳定性，并在出现违规问题时予以补救。
（2）提出的GDR-ELM也优于AE和DAE。一方面，GDR-ELM借助于标签信息搜索鉴别特征，这在经典的声发射和声发射中是不被利用的。另一方面，由于AE或SAE的问题非常严重，每个数据集的每个类的训练样本数如下所示。ORL5个，Y aleB 20个，UMNIST 15个，COIL20 15个，USPST15个。非凸优化问题，BP算法只能找到局部最优解。从理论上讲，如果我们能够求解AE的全局最优解，它必须优于其他ELM-AEs。然而，在实际应用中，AE和DAE总是陷入局部最优解的陷阱。
（3）与US-ELM和SR-ELM相比，GDRELM是一种值得称赞的DR算法。实际上，在实验中，US-ELM和SR-ELM将输入特征投影到更高的随机特征空间，然后根据流形或标签信息提取低维子空间。因此，它们是两层神经网络特征学习结构。在实验中，SR-ELM在COIL-20和USPS-T上取得了较好的性能。然而，该方法通过单层的特征学习结构可以达到竞争性的效果。
（三） Additional Experiments:
为了进一步评估该方法的性能，我们用不同的分类器证明了表1中的5个数据集上的GDRELM与其他5个DR方法，包括核PCA（KPCA）[53]、t-分布随机邻域嵌入（t-SNE）[54]、局部线性嵌入（LLE）[20]和核ELM[55]。补充材料第三节提供了附加实验。为了进一步评估该方法的性能，我们用不同的分类器证明了表1中的5个数据集上的GDRELM与其他5个DR方法，包括核PCA（KPCA）[53]、t-分布随机邻域嵌入（t-SNE）[54]、局部线性嵌入（LLE）[20]和核ELM[55]。补充材料第三节提供了附加实验。
本节包含一系列实验来评估所提出的GDR-ML-ELM的效能。首先对基于ELM的压缩表示学习方法进行了评价，其中ELM-AE[10]、H-ELM[11]、ELM-AEIF[12]，并在CMU-PIE和MNIST数据集上进行了验证。然后进一步评价了不同的多层感知器，包括ML-ELM[9]、H-ELM、叠层AE（SAE）[32]、叠层去噪AE（SDA）[3]和我们的方法。基于ELM方法的可调参数的选择方法与前一节的实验设置相同。我们使用验证集搜索每个层中具有给定范围的可调参数，然后使用验证集上具有最佳性能的参数来测试模型。
Performance of ELM-Based Methods on CMU PIE
基于CMU-PIE的ELM方法的性能：CMU-PIE数据库[56]包含来自68名受试者的41368张人脸图像。我们选择了常用的五个子集（C05、C07、C09、C27和C29），实验中使用了11544幅图像。在不同的光照和表情下，每个人有170个图像。所有图像的大小都调整为32×32
实验在不同的网络结构和训练样本数下进行。我们根据给定的比率（见表三）将数据集分成两个子集，其中一个子集用于训练，另一个子集用于测试。首先使用GDR-ML-ELM提取压缩特征。在文献[11]中的实验设置之后，一个经典的ELM被实现为最终的分类器。网络如表3所示，带括号的数字表示最后一层ELM分类器中的隐藏节点数。
将网络的输入和输出设置为原始数据的维数和类数，对每个算法进行十次测试，以更好地估计识别精度。结果见表三，实验说明如下。
（1）该方法在大多数实验中都具有较高的识别精度，特别是在训练样本不足的情况下。利用标签和流形信息，GDR-ELM提取出更具鉴别能力的特征，便于后续的分类。
（2）随着训练样本数的增加，各种方法的性能都有增加的趋势，这是我们所期望的。大量的训练样本可以帮助算法从原始数据中找到更多的内在特征。因此，泛化精度将提高
（3）由于GDR-ELM需要计算训练样本的图矩阵，因此该方法比其他方法稍慢。但时间总是可以接受的。
Performance of ELM-Based Methods on MNIST
国家标准与技术混合研究所（MNIST）的手写数据集有60000个训练样本和10000个测试样本，这些样本是来自从0到9的28×28维度的数字图像和统一的背景。本节的实验设置与上一节相似。为了生成不同的训练集，我们按照给定的比例随机分割原始训练集。结果见表四。
实验结果表明，该方法在MNIST数据集上与其它基于ELM的多层网络相比，尤其是在训练样本数不足的情况下，具有很好的竞争性能。这是因为我们的算法可以找到带有标签和流形信息的区别表示。然而，当训练样本数量过大时，GDR-ML-ELM可能会相对耗时。原因已在上一节中提供。这说明在使用MNIST的原始训练集时，我们的方法在表4中的训练时间超过300s。（原MNIST培训集中有60000个培训样本）
Compared Experiments With Multilayer Perceptron（比较多层感知器的实验结果）
实验结果如表五所示。与目前最先进的基于ELM的多层方法相比，由于我们的方法需要计算邻接矩阵，当训练样本数太多时，邻接矩阵的计算会非常耗时，因此我们的方法可以在较长的训练时间内获得有竞争力的结果。但是对于SAE和SDA来说，他们需要数百个epoch的训练时间。因此，GDR-ML-ELM的训练时间仍然可以接受。对于NORB数据集上的SAE和SDA，我们直接引用了文献[11]的结果，可以看出SAE和SDA即使使用原始图像大小96×96，也能在较长的训练时间内取得较好的性能。
CONCLUSION
本文提出了一种基于图嵌入的ELM-DR方法。与现有的基于ELM-ae的DR方法相比，GDR-ELM以有监督的方式解决了DR问题，并且可以发现更多的鉴别特征。GDR-ELM还可以在违规问题发生时进行补救，确保性能的稳定性。此外，GDR-ELM可以作为构建块进行堆叠，以构建用于更复杂实际应用的多层框架（GDR-ML-ELM）。实验结果表明，该算法优于其它基于ELM-AE的DR算法和一些常用的传统DR方法。并与其它多层ELM体系结构和基于深度体系结构的特征学习方法进行了比较。实验表明，该方法在多层场景下也能取得令人满意的性能。
