[论文笔记]Dimensionality Reduction by Learning an Invariant Mapping
这篇论文提出了一种名为DrLIM的方法，用于学习一致的非线性函数以降维。该方法通过对比损失函数优化参数化函数G_W，使其能够将相似样本映射到流形上的相邻点，并将不相似样本推远。与传统降维技术相比，DrLIM能够学习对复杂变换不变的函数，并适用于未见过的新数据点。实验表明，在MNIST数据集上进行数字分类任务时，DrLIM在保持输出空间一致性的前提下表现优异。该方法通过对比损失函数有效地平衡了相似和不相似样本对的影响，并展示了在平移不变性任务中的有效性（179-184字）。
引言
这篇来自2005年的原始研究文献的笔记中提到了一项重要的降维技术。该研究探讨了一种通过学习不变映射实现数据降维的方法，并详细介绍了其理论基础和应用案例。
该论文中提出的对比损失(2.1节)可以用于训练嵌入模型。
为了简单，下文中以翻译的口吻记录，比如替换"作者"为"我们"。
降维涉及将一组高维输入点映射到低维流形(low dimensional manifold)上，以使得输入空间中“相似”的点被映射到流形上的相邻点。现有的大多数技术在解决这一问题时存在两个缺点。首先，它们大多数依赖于输入空间中一个有意义且可计算的距离度量。其次，它们不能计算出一个能够准确映射新输入样本的“函数”，这些新样本与训练数据的关系未知。
我们提出了一种名为DrLIM的方法——基于学习不变映射进行降维（Dimensionality Reduction by Learning an Invariant Mapping, DrLIM）。该方法旨在学习一个具有全局一致性的非线性函数，并以均匀分布的方式将数据映射到输出流形上。整个学习过程完全基于邻域关系，并不需要输入空间中的度量信息。此外，该方法能够有效地实现对某些特定输入变换保持不变的映射特性。
1. 总体介绍
现代应用程序对复杂高维数据的使用呈快速增长态势。在科学与工业领域产生的大规模高维图像数据集对新型分析、特征提取、降维及可视化技术的发展提出了迫切需求。
降维的目标在于将高维数据映射至低维空间。这种技术的主要应用是简化数据结构并保留其核心特征。然而，大多数现有的降维技术都存在两个主要缺陷：首先，在处理新数据时缺乏明确的功能（或映射）可供应用；其次，在输入空间中必须预先定义一个有意义且可计算的距离度量才能有效运作。例如，在局部线性嵌入中（LLE），每个样本被视为其邻居通过线性组合重构的结果向量。尽管这种方法对于完全对齐且高度相似的数据表现良好（如图像数据），但对于新样本缺乏普适性解决方案。拉普拉斯特征映射(Laplacian Eigenmap)和Hessian LLE等方法则放宽了这一限制条件：它们不需要预先定义有意义的距离度量即可运行；相反，则仅需每个样本对应的邻居列表信息即可完成嵌入过程。然而，在某些情况下这些扩展方法仍依赖于能够计算出有效的核函数来构建邻域矩阵
当前方法的另一个缺点是它们容易将输出集中在某些区域。这些情况有时会导致输出过于密集，在统计学上被视为退化解。然而，在某些情况下我们希望模型能够通过样本数据均匀地覆盖流形结构。
本文所提出的这种方法——命名为基于不变映射的学习降维技术——旨在解决上述问题。DrLIM 代表了一种全局一致地学习非线性变换的方法；这种变换能够将输入的数据映射至低维流形。该方法具有四个基本特征：
仅依赖于训练样本间的局部关系。这些邻域关系可源自先验知识或人工标注，并不受任何距离度量的影响。
能够学习出对复杂非线性变换具有不变性的函数。
所学函数可用于将未曾见过的新样本映射至输出空间中并无需依赖先验知识；同时，在输出空间中生成的映射呈现出"平滑"且一致的特点。
该方法通过对比损失函数实现参数化函数G_W的参数估计，并使其成为更接近的对象，并使非相关对象远离。可以通过引入先验知识辅助确定每个训练样本的邻域关系。
该方法采用基于能量的模型来处理问题。对于由参数化的函数族来说，在这种情况下我们希望确定一个合适的参数值以实现特定的目标。我们将一组高维输入被映射到流形上，并且在这一过程中确保流形上的点之间的欧几里得距离被计算为两组点在目标空间中的语义相似度度量的一种近似表示方式。这一度量通过构建一种从输入空间到目标空间的数据嵌入机制得以实现，并且这一过程完全依赖于所选择邻域关系所提供的语义信息。
1.1. 先前工作
研究将高维数据映射至低维流形的历史可以追溯到很久以前。为解决这一问题提供了主要思路的方法包括主成分分析法（PCA）和多维尺度分析法（MDS）。主成分分析法通过将数据投影至最大化方差的低维子空间来实现降维度；而多维度尺度化则通过计算保持输入点间原始距离的最佳二维或三维表示来进行降噪。值得注意的是，在一般情况下使用PCA进行降维度与基于欧氏距离的经典MDS方法所得结果一致。
近年来围绕该问题开展的非线性谱方法研究颇为活跃。这些研究主要集中在对特定矩阵求解其特征值的过程上。近期提出的诸多算法均包含三个关键步骤：首先，则是确定每个数据点的邻接列表；接着，则是利用上述信息构建Gram矩阵；最后则需解决该矩阵所对应的特征值问题。值得注意的是不同算法在构建Gram矩阵的过程中存在差异性：它们都未能建立能够映射新数据点到已有空间中的函数模型
在另一个方向上, Schölkopf及其团队开发了PCA的非线性扩展方法.其核心思想是将输入通过非线性变换映射至高维特征空间,随后提取主成分.该算法通过仅使用点积的形式来表达PCA计算过程,接着利用核技巧隐式地计算高维映射.核的选择至关重要:不同的核会产生显著不同的嵌入.在近期工作中,Weinberger等尝试通过将其形式化为半正定程序来学习当高维输入位于低维流形上的核矩阵.
我们所提出的这种新方法与现有方法不同；它通过学习一个能够具有一致性地将未见的新数据点映射到预定输出空间的能力来提升模型性能。该函数在设计时特别考虑了复杂数据分布的特点，并避免采用依赖于输入空间中简单距离度量的结构。
2. 学习低维映射
问题是构建一个参数化函数G_W: \mathbb{R}^D \rightarrow \mathbb{R}^d（其中d
在输出空间中采用一种经典的度量方式（如欧几里得距离），其结果能够较好地反映出输入空间中样本间的邻域关系特性。
为了提高模型的泛化能力，在设计映射函数时不宜仅依赖于简单的度量方法，
而应当发展出更具概括性的学习机制，
使其能够自主适应复杂的空间变换。
即使面对那些邻域关系不明确的测试样本，
这种映射函数依然应当保持良好的表现，
即其输出结果仍能有效反映输入样本的基本特征。
2.1. 对比损失函数
考虑高维训练向量\pmb{X}_i 的集合\mathcal I。假设对于每个\pmb{X}_i \in \mathcal I，都有一个训练向量集S_{\pmb{X}_i}，这些向量被认为与\pmb{X}_i 相似。这个集合可以通过一些先验知识来计算，这些不依赖于简单的距离。一个有意义的从高维到低维空间的映射会将相似的输入向量映射到输出流形上的相邻点，将不相似的向量映射到远离的点。现在介绍一个新的损失函数，其最小化可以生成这样的函数。与传统的学习系统中损失函数对样本的求和不同，这里的损失函数对样本对进行处理。设\pmb{X}_1, \pmb{X}_2 \in \mathcal I 为一对输入向量呈现给系统。设Y 为分配给这一对的二值标签。如果\pmb{X}_1 和\pmb{X}_2 被认为相似，则Y = 0；如果被认为不相似，则Y = 1。定义要学习的参数化距离函数D_W 为\pmb{X}_1 和\pmb{X}_2 之间的欧几里得距离，即：
D_W (\pmb{X}_1, \pmb{X}_2) = \| G_W (\pmb{X}_1) - G_W (\pmb{X}_2) \|_2 \tag 1
为了便于表示起见
\mathcal L(W, (Y, \pmb{X}_1, \pmb{X}_2)^i) = (1 - Y) L_S \left( D_W^i\right) + Y L_D \left( D_W^i \right)
在训练过程中，在每一轮迭代中我们采用三元组(Y, \pmb{X}_1^i, \pmb{X}_2^i)来进行学习操作，在这一设定下L_S^{(i)}表示两个相似样本点之间的分部损失函数（partial loss function），而$L_D^{(i)}则代表两个不相似样本点之间的分部损失函数。其中P代表总的正难例对的数量（理论上可能会达到所有样本配对的总数量）。
L_S 和 L_D 必须以特定的方式进行设计：通过最小化 W 的值来使相似对的 D_W 较低的同时不影响不相似对这一指标。
我们采用以下损失函数形式：
L(W, Y, \pmb{X}_1, \pmb{X}_2) = (1 - Y) \frac{1}{2} (D_W)^2 + Y \frac{1}{2} [\max(0, m - D_W)]^2 \tag 4
其中间隔值m>0设定了一个临界距离\|\mathbf{x}_i - g_w(\mathbf{x}_j)\|（见图 1）。只有当两个样本点之间的距离不超过该临界距离时才会影响整体损失计算结果。特别值得注意的是，在这种情况下引入的对比项具有重要意义，在实际应用中可能起到关键作用。特别地，在这种情况下引入的对比项具有重要意义，在实际应用中可能起到关键作用。如果仅考虑相似样本进行优化，则可能导致模型无法有效区分不同的类别（即所谓的坍塌解）。为了避免这种情况，在基于能量模型的设计中必须明确包含这样的对比项以确保系统的稳定性和有效性
2.2. 弹簧模型类比
图 2 展示了一个弹簧系统示意图。实心圆圈标记了与中心点相近的点；而空心圆圈则代表不相似的点。作用在这些点上的力则用蓝色箭头表示；箭头长度大致反映了力的大小。右侧图表中x轴标注的是距离D_W数值；y轴则是损失函数值。（a）图展示了仅由吸引弹簧连接而相互关联的不同相似点；（b）图则呈现了相关联的损失函数值及其变化趋势；（c）图描绘了位于半径m范围内的排斥关系所形成的连接模式；（d）图比较了不同排斥程度下的系统行为特征；（e）图模拟了一个典型的平衡状态形成过程
通过类比一个特定机械弹簧系统来直观理解在最小化损失函数时的情况。我们可以将G_W网络的输出结果视为由相互吸引与排斥作用的质量体所组成的一种复杂系统结构。为了更好地理解这一过程，请考虑以下弹簧方程：
F = -KX \tag 5
其中F表示施加的力大小，K为该弹簧的劲度系数（spring constant），而X则代表弹簧相对于平衡位置的位移量（displacement）。当位移值X为正值时会促使两端质量体相互吸引靠近；相反地，在这种情况下若x < m值，则会导致这两个质量体被推离彼此远离的状态变化趋势。然而需要注意的是，在这种特殊设计下，在满足x > m条件的情况下并不会产生吸引力作用以将其拉回到平衡位置上；换句话说，在这种情况下即使被拉伸超过了设定阈值m, 弹簧也不会施加拉力将其拉回原长状态。值得注意的是，在整个系统中每个节点都是通过这两类不同性质的连接方式与其他节点建立联系：即每个节点都通过具有吸引力作用的质量体连接到其相似度较高的邻居节点上，并且同时又通过排斥性作用的质量体连接到不那么相似的对象节点上（如图2所示）。
为了解释相似对之间的关系及其影响，我们引入了损失函数L_S(W, \pmb{X}_1, \pmb{X}_2)。该损失函数的形式定义如下：
L_S(W, \pmb{X}_1, \pmb{X}_2) = \frac{1}{2} (D_W)^2 \tag 6
为了优化该损失函数L_S，我们采用随机梯度下降算法进行参数更新。计算其关于权重矩阵W的梯度：
\frac{\partial L_S}{\partial W} = D_W \frac{\partial D_W}{\partial W} \tag 7
对比方程5与7可知，在这种设置下，
\frac{\partial L_S}{\partial W}
这一项实际上反映了两个点之间的吸引力关系。其中，
\frac{\partial D_W}{\partial W}
这一项可以看作是弹簧系统中的弹簧常数K，
而
D_W
则是衡量两点之间距离的一个指标变量，
它相当于弹簧从静止长度出发所受到的扰动量X。
值得注意的是，
即使是最微小的距离偏移量
D_W
也会通过上述机制产生相应的调整（即梯度），从而使得
D_W
逐渐减小。
这种机制对应于一种吸引式的相似性建模方法（如图2所示）。
对于部分损失函数L_D而言，在公式（8）中定义为：
L_D(W, \pmb{X}_1, \pmb{X}_2) = \frac{1}{2} \left( \max\{0, m - D_W\} \right)^2
其中,D_W代表距离,W为权重矩阵.当距离D_W超过阈值m时,根据方程（8）可知,
\frac{\partial L_D}{\partial W} = 0
即此时没有梯度（力）作用于这些点.相反地,当距离D_W小于m时,
\frac{\partial L_D}{\partial W} = - (m - D_W) \frac{\partial D_W}{\partial W}
可以看出,不相似损失函数L_D对应于m-仅排斥弹簧;其梯度给出了斥力,
而\frac{\partial D_W}{\partial W}则表示弹簧常数K,(m-D_W)表示弹簧受扰动的程度X.负号表明斥力性质.显然,当D_W=0时,斥力最大;而当D_W=m时,斥力消失.参考图2可以看到这一过程.
在此，在特定条件下（如图2e所示），有人可能认为：仅仅需要让所有仅吸引弹簧的损失值为零即可使系统达到平衡。然而，在实际情况中：假设节点b_1b_2b_3之间通过仅吸引性连接。减少它们之间的差异会使得节点b_1$$b_3之间的差异增加。因此，在优化整个系统的全局损失函数$L_S时（如图2e所示），最终能够使系统达到其平衡状态。
2.3 算法
算法首先生成训练集，然后训练模型。
步骤 1: 对于每个输入样本\pmb{X}_i，执行以下操作：
(a) 基于先验知识确定样本集合 S_{\bm{X_i}} = \{\bm{X_j}\}_{j=1}^n, 从而使得每个 \bm{X_j} 被认为与 \bm{X_i} 具有相似性
通过生成所有样本\pmb{X}_i 与训练集中其他样本的配对关系，并为每一对分配相应的标签值来完成这一过程：
其中，
Y_{ij} = \begin{cases} 0 & \text{如果 } \pmb{X}_j \in S_{\pmb{X}_i}, \\ 1 & \text{否则} \end{cases}
随后将所有这些配对关系整合至标记数据集中。
**步骤 2: ** 重复直到收敛：
(a) 对于训练集中的每对(\pmb{X}_i, \pmb{X}_j)，执行：
i. 如果Y_{ij} = 0，则更新W 以减少
D_W = \| G_W(\pmb{X}_i) - G_W(\pmb{X}_j) \|^2
ii. 如果Y_{ij} = 1，则更新W 以增加
D_W = \| G_W(\pmb{X}_i) - G_W(\pmb{X}_j) \|_2
通过最小化上述损失函数来实现输出空间中欧几里得距离的增加和减少。
3. 实验
3.1 训练架构
该系统采用孪生网络架构，在其主体结构中包含两个共享参数的G_W副本模块以及一个独立的损失计算单元。在系统输出层设置一个损失计算单元，在其上安置了一个综合考量两支预测结果的评估机制。系统接收输入数据对(\pmb{X}_1,\pmb{X}_2)以及对应标签变量\mathbf{Y}。图像数据依次经函数处理后分别生成两个特征表示结果：\mathbf{g} = G(\mathbf{x_1}), \mathbf{h} = G(\mathbf{x_2}). 损失计算单元则基于这两个特征表示结果\mathbf{g}和\mathbf{h}, 计算特征间距离d_w (\mathbf{g}, \mathbf{h}). 根据标签变量\mathbf{Y}的不同取值情况, 损失函数将此距离指标与标签信息相结合, 生成标量形式的目标函数L_S或L_D, 具体取决于标签类别. 通过随机梯度下降优化参数\theta, 并采用反向传播算法求取参数梯度总和, 从而实现模型权重的有效更新.
MNIST 数据集的实验则使用了卷积网络作为G_W（见图 3）。
3.2 MNIST 样本的学习映射
本研究工作致力于构建DrLIM方法的基础功能体系。邻接图基于欧几里得距离构建，在方法实施过程中未引入先验知识
训练集包含了300例手写形状4的图像与300例手写形状9的图像，这些图像均来自MNIST数据集中的随机抽取。测试集约包含1千张各个形状的图像。所有这些图像均被打乱后配对，并按照基于简单的欧几里得距离度量的方法进行了分类：每个样本\pmb{X}_i会与其中5个最接近的样本配对形成集合S_{\pmb{X}_i}。其余所有可能形成的配对则未被标记为相似关系，在这种处理下总共生成了3万组相似配对比及约1.8亿组非相似配对比。
该2D流形映射基于测试集构建，并如图4所示。其中浅色圆圈标记为数字9样本，深色圆圈标记为数字4样本。此外，在流形附近分布了一些输入测试样本。这两个类别（数字4和9）在两个稍有重叠的区域中占据主导地位。整体分布模式主要受样本倾斜角度的影响。
3.3 学习 MNIST 样本的平移不变映射
在本实验中，考察了DrLIM方法在MNIST数据集上的应对能力——具体而言是在面对水平偏移样本时的表现能力。研究的目标在于训练一个二维映射模型，在这种映射下输出结果不受输入样本水平偏移的影响。
从被扭曲的数据集中提取了数量为N_1=3,818的数字4和9的图像样本，并对这些图像在水平方向进行\pm6像素的平移操作后与原始图像组合使用，生成了总计约7,618张新的训练数据样本。作为测试集的一部分，在相同的变换策略下处理了N_2=2,818张样本数据
首先，在实验系统的构建中，默认采用欧几里得距离作为度量标准，并基于此生成邻域关系图（每个样本选取其5个最近邻居）。值得注意的是，在该过程中采用的是平移操作而非旋转操作。由于平移操作导致各原始样本之间的曼哈顿距离显著增加，在这种情况下形成了相互独立的邻域结构。处理后的输出点能够依据输入样本的平移位置实现精准分类（如图5所示）。值得注意的是，在同一簇内部的所有数据点呈现出高度一致性和良好的分布特征。
为了对比研究不同降维方法的效果，在本研究中我们采用LLE方法对经过扭曲处理的MNIST样本集合进行映射，并采用相同的欧几里得距离邻域图构建其邻域关系网络。映射结果形成一个退化结构，在嵌入空间中完全分离出不同配准的样本类别（如图6所示）。尽管存在局部组织碎片，在整体上缺乏全局一致性特征。
为了确保映射函数对于平移具有不变性，在欧几里得最近邻的基础上进行了扩展，并通过构建基于先验知识的配对关系实现了这一目标。每个样本被配对为以下几种形式：其五个最近邻居、四个不同的平移版本以及每个邻居对应的另外四个不同方向上的平移版本；同时将每个样本与其自身的所有可能配对比进行了扩展，并未考虑其余所有可能的配对情况以避免引入过多冗余信息。其余所有可能的配对则未被考虑在内以简化计算过程并提高效率
测试集样本通过映射关系如图7所示地呈现。其中使用较浅颜色标记的是数字4样本，而较深颜色标记的是数字9样本。正如预期所示，在映射中并不存在基于平移操作组织的数据结构；相反地，在流形上某些局部区域中存在许多相同字符的不同平移版本。
4. 讨论与未来工作
通过本节展示的实验结果可以看出，在缺乏引入特定先验知识建立相应不变特性的情况下，
这些外部干扰因素可能导致降维效果受到影响。
为此，
我们提出了一种名为DrLIM的新方法：
该方法能够通过引入特定先验知识来构建对低维流形的一种稳健映射关系。
其可调节不变性的复杂程度主要取决于参数化函数 G_W 的设计能力。
通过对实验数据的具体分析表明，
在这种情况下生成的结果能够较为均匀地覆盖整个目标流形空间。
此外，
在实际应用中，
该方法还能有效地将未见过的新样本准确地映射至其在目标空间中的合理位置上。
DrLIM的核心竞争力在于其采用差异比较的损失函数策略。该系统通过分别应用不同损失函数给相似与不相似样本对而实现动态平衡状态维持，并防止收敛至恒定值。
总结
改写说明