论文阅读 - Deep Metric Learning via Lifted Structured Feature Embedding

题目: Deep Metric Learning via Lifted Structured Feature Embedding - CVPR2016
作者: Hyun Oh Song, Yu Xiang, Stefanie Jegelka, Silvio Savarese
团队: Stanford University, MIT

Caffe-Code

样本间距离度量方法, 特征学习
出发点: (一)学习样本语义特征嵌入,使得在语义嵌入空间中,相似样本映射距离更接近,不相似样本映射距离更远. (二)更好的利用网络训练中 batch 训练的优势,提出将一个 batch 内样本的成对距离向量升级为成对距离矩阵(lifting the vector of pairwise distances within the batch to the matrix of pairwise distances).
问题被转化为了一个 multiclass label 问题.

1. Introduction

度量学习和降维技术,旨在学习语义距离度量和嵌入,以使相似的样本被映射为流形中邻近点,不相似的样本被映射为距离较远的点.

给定输入图像的标签标注信息,通过训练神经网络结构,直接学习输入图像到低维嵌入之间的非线性映射函数. 网络的优化目标是将不同类的样本间的距离变大,相同类的样本间的距离变小. 判别地训练的网络模型对特征表示和语义嵌入联合训练,对类间变化更加鲁棒.

现有方法不能充分利用网络 mini-batch SGD 训练中 training batches 的优势. 主要是首先随机采样 pairs 或 triplets,以构建 training batch,再对 training batch 中各独立的 pairs 或 triplets 计算 loss.

本文方法将 training batch 内的成对距离向量转化为成对距离矩阵,并设计一种新的结构化损失函数.

首先回顾了基于判别性网络训练来学习语义嵌入的方法.

1.1 Contrastive embedding

对比嵌入是在成对数据 ${ {(\mathbf{x_i}, \mathbf{x_j}, y_{ij})} }$ 上进行训练的.

contrastive training 最小化相同类别的成对样本间的距离,惩罚 negative 成对距离小于边缘参数 ${ \alpha }$ .

代价函数[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)}} }$ 是一个三元组中的参考项(anchor).

triplet training 寻找一个语义嵌入,使得 ${ {(\mathbf{x}_a^{(i)}, \mathbf{x}_n^{(i)})} }$ 间的距离大于 ${ {(\mathbf{x}_a^{(i)}, \mathbf{x}_p^{(i)})} }$ 间的距离加上一个边缘参数 ${ \alpha }$.

代价函数[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. 六个样本的 training batch 的不同训练例示. 红色线和蓝色线分别表示相似和不相似的样本. 对比而言,Lifted structured embedding 能够考虑 batch 内所有的成对距离.


Figure 3. 不同嵌入方法的训练网络例示. m 表示 batch 内图片数,即batchsize. 绿色框表示一个 batch 的一个样本.

(a) 网络采用二值labels作为输入;

(b) 网络不需要 label 输入,anchor , positive 和 negetive 的顺序编码了 label 信息;

(c) 网络采用 multiclass label 作为输入.


Figure5. 随机对 training batch 采样,采用contrastive loss 和 triplet loss 失败的情况. 这里以三类为例,分别对应棕色圆、绿色方块和紫色棱形. 虚线灰色弧线表示在 hinge loss 中的边界(超出边界后,loss变为0). 品红色箭头表示对于 positives 的 negative 梯度方向.

(a)当随机采样的 negative ${ (\mathbf{x}_j) }$ 与其它类的样本共线时,Contrastive embedding 会失败;

(b)当随机采样的 negative ${ (\mathbf{x}_n) }$ 相对于 positive ${ (\mathbf{x}_p) }$ 和 anchor ${ (\mathbf{x}_a) }$,在边界内时,Triplet embedding 会失败;

2. Lifted structured feature embedding

基于训练集中的所有 positive 和 negetive 样本定义 loss 函数:

其中,
${ \check{P} }$ - 训练集中的 positive 样本对 集合
${ \check{N} }$ - 训练集中的 negative 样本对 集合

该 loss 函数面临的计算上的挑战:

  • 非平滑
  • 函数的估计和其 subgradient 的计算需要对所有的样本对进行多次最小化.

解决方案:

  • 1 - 对函数的平滑上边界进行优化;
  • 2 - 采用随机(stochastic)方法对大数据集处理.

启发点:

  • 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)$ 对样本信息 .

给定 batch 的 c 维特征 ${ X \in R^{m×c} }$,及batch内各元素的二次方范数列向量 ${ \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 采用的相关信息.


Figure 4. 对于各 positive pairs的每个样本,找出其左右的 hard negative edge. batch内有 6 个样本,x3 和x4 分别与所有的其它 negative edges进行比较,以找到 hardest negative edge.

由于采用嵌套的 max 函数来寻找单个 hardest negative 往往导致网络收敛到一个 bad 局部最优解. 因此,这里采取优化其平滑上界 ${ \check{J}(D(f(\mathbf{x}))) }$. 针对各 batch, loss 函数定义如下:

BP计算过程:

其中,

3. Results

成功的:

失败的:

Reference

[1] - Learning visual similarity for product design with convolutional neural networks

[2] - Dimensionality reduction by learning an invariant mapping

[3] - Facenet: A unified embedding for face recognition and clustering

Last modification:October 10th, 2018 at 04:34 pm

Leave a Comment