论文阅读理解 - Deep Metric Learning via Lifted Structured Feature Embedding
该论文提出了一种名为“提升结构特征嵌入”的方法，用于深度度量学习。该方法的核心思想是通过将批处理中的所有样本对的成对距离矩阵化，利用批处理中的全部样本信息来优化语义嵌入，从而更高效地学习样本间的语义距离度量。与现有方法相比，该方法能够更好地利用批处理中的数据，避免了传统方法中随机采样对训练效果的影响。实验结果表明，该方法在保持计算效率的同时，能够显著提高度量学习的性能。
Deep Metric Learning via Lifted Structured Feature Embedding
令人惊讶地超越了Deep Metric Learning在CVPR 2016上的发表，该研究论文在性能方面展现了显著优势，这主要得益于其简洁的设计和高效的代码实现。
摘要 - 提出一种样本间距离度量方法，其出发点在于：(一)通过学习样本语义特征的嵌入表示，在语义嵌入空间中，相似样本的映射距离更趋近于零，不相似样本的映射距离则更远离零。 (二)充分利用 batch 训练中的批量处理能力，将 batch 内样本的成对距离向量提升为成对距离矩阵，从而将问题转化为一个多标签分类问题。
1. Introduction
度量学习与降维技术，旨在学习语义距离度量和嵌入，以使相似的样本被映射到流形中的邻近点，不相似的样本被映射到距离较远的点。
基于输入图像的标注信息，通过训练神经网络结构，直接学习输入图像与低维嵌入之间的非线性映射关系。网络的优化目标是将不同类样本间的距离增大，相同类样本间的距离减小。通过判别性训练的网络模型，同时进行特征表示和语义嵌入的联合训练，使其对类间变化更加鲁棒。
现有方法未能有效利用网络mini-batch SGD训练中training batches的优势。其主要原因是首先在构建training batch的过程中，随机采样pairs或triplets，然后计算每个training batch中独立的pairs或triplets的损失。
本文方法通过 training batch中成对距离向量的转化，构建了成对距离矩阵，并同时构建了一种新的结构化损失函数。
首先回顾了基于判别性网络训练来学习语义嵌入的方法.
1.1 Contrastive embedding
对比嵌入是在成对数据 {(\mathbf{x_i}, \mathbf{x_j}, y_{ij})} 上进行训练的.
对比学习方法通过优化，使得相同类别样本的配对距离被最小化，同时对那些负对距离小于阈值 α 的配对，增加了惩罚项。
代价函数[1,2]定义：
J = \frac{1}{m} \sum_{(i, j)}^{m/2} y_{i, j} D_{i, j}^2 + (1-y_{i,j})[\alpha - D_{i, j}]_{+}^2
其中，
m - batch 内图片数，即batchsize.
f(\cdot) - 网络输出的特征嵌入.
D_{i, j} = ||f(\mathbf{x}_i) - f(\mathbf{x}_i)||_2
y_{i, j} \in {0, 1} - 表示一对样本 (\mathbf{x}_i, \mathbf{x}_j) 是否是同类样本.
[\cdot]_+ - 表示 hinge 函数 max(0, \cdot) 操作.
1.2 Triplet embedding
三元组嵌入基于三元组数据 \{(\mathbf{x}_a^{(i)}, \mathbf{x}_p^{(i)}, \mathbf{x}_n^{(i)})\}，其中，\{(\mathbf{x}_a^{(i)}, \mathbf{x}_p^{(i)})\} 是同一类的特征，\{(\mathbf{x}_a^{(i)}, \mathbf{x}_n^{(i)})\} 是不同类的特征。\{\mathbf{x}_a^{(i)}\} 是该三元组的锚点。
在triplet training框架下，通过计算语义嵌入，确保正样本对之间的距离超过负样本对之间的距离并加上一个预设的边缘参数。
代价函数[3]定义：
J = \frac{3}{2m} \sum_{i}^{m/3} [D_{ia, ip} ^2 - D_{ia, in}^2 + \alpha]_{+}
其中，
D_{ia, ip} = ||f(\mathbf{x}_i^a) - f(\mathbf{x}_j^p)||
D_{ia, ip} = ||f(\mathbf{x}_i^a) - f(\mathbf{x}_i^n)||
Figure 2展示了六个样本的训练批次中的不同训练示例。红色线条和蓝色线条分别代表了相似样本和不相似样本。通过对比可以看出，Lifted结构嵌入能够考虑批次内部所有成对的距离。
Figure 3展示了不同嵌入方法的训练网络示意图。其中，表示 batch 内图片数量的术语称为 batch_size，即批次大小。每个批次中的一个样本被突出显示为绿色框。
(a) 网络采用二值labels作为输入；
网络无需输入label，anchor、positive以及negative的顺序编码了label信息；
(c) 网络采用 multiclass label 作为输入.
Figure 5. 随机从 training batch 中采样，当采用 contrastive loss 和 triplet loss 时出现失败的情况。以三类为例，分别对应棕色圆点、绿色方块和紫色棱形。虚线灰色弧线表示在 hinge loss 下的决策边界（超出边界后，损失函数值变为0）。品红色箭头表示 positives 的负梯度方向。
若随机选取的 negative 样本 \mathbf{x}_j 与其他类别样本呈线性相关，则 Contrastive embedding 方法在此情况下会失效；
在随机采样过程中，negative样本位于边界内部时，Triplet嵌入将导致Triplet嵌入失效。
2. Lifted structured feature embedding
基于训练集中的所有 positive 和 negetive 样本定义 loss 函数：
其中，
\check{P} - 训练集中的 positive 样本对 集合
\check{N} - 训练集中的 negative 样本对 集合
该 loss 函数面临的计算上的挑战：
该函数的估计和其subgradient的计算涉及对所有样本对的多次最小化。
解决方案：
- 1 - 对函数上界进行优化；
- 2 - 采用随机化方法对大规模数据集进行处理。
启发点：
- 1 - 偏向于对“困难”样本对，正如 J_{i,j} 的 subgradient 计算 采用的接近的 negative pairs. (it biases the sample towards including “difficult” pairs, just like a subgradient of Ji;j would use the close negative pairs).
- 2 - 对一次采样的 mini-batch 内的所有样本信息进行利用，而不仅是单独的样本对.
key idea：
- 加速 mini-batch 的优化，以充分利用 batch 内的全部 O(m^2) 对样本信息 .
考虑一个批次的c维特征向量X \in R^{m×c}，及其内部各元素经函数f后的平方L2范数的列向量\check{\mathbf{x}} = [||f(\mathbf{x}_1)||_2^2, ..., ||f(\mathbf{x}_m)||_2^2]^T。
即可构建 密集平方距离对矩阵(dense pairwise squared distance matrix)：
D^2 = \check{\mathbf{x}} \mathbf{1}^T + \mathbf{1} \check{\mathbf{x}}^T - 2XX^T
D_{ij}^2 = ||f(\mathbf{x}_i) - f(\mathbf{x}_j)||_2^2
需要注意的是，随机采样的样本对的 negative edges 具有有限的信息.
该方法并非完全随机采样，而是引入了重要性采样元素。随机采样了一些positive样本对，随后又添加了difficult neighbors以训练mini-batch。这种处理并引入了subgradient的相关信息。
对于每个 positive pair的样本，识别其左右的 hard negative edges。每个batch包含6个样本，x3和x4分别与该batch内的所有negative edges进行比较，以识别 hardest negative edges。
考虑到采用嵌套的max函数来寻找单个hardest negative，往往会导致网络收敛至一个欠佳的局部最优解。为了优化这一问题，这里采取了优化其平滑上界\check{J}(D(f(\mathbf{x})))。具体定义如下：针对每一个batch，损失函数如下所示：
BP计算过程：
其中，
3. Results
成功的：
失败的：
Reference
该研究在产品设计中应用卷积神经网络进行视觉相似性学习，取得了显著成果。
[2] - 降维通过学习不变映射
[3]：一种用于面部识别和聚类的统一嵌入方法