triplet loss原理推导及变体

简介

参考一下几篇文章：

• triplet loss 原理以及梯度推导
• facenet 代码阅读笔记：如何训练基于triplet-loss的模型
• Beyond triplet loss—— Re-ID
• 论文笔记之： Person Re-Identification by Multi-Channel Parts-Based CNN with Improved Triplet Loss Function
• 论文笔记之： Deep Metric Learning via Lifted Structured Feature Embedding
• 阅读小结Deep Metric Learning via Lifted Structured Feature Embedding
• 论文阅读理解 - Deep Metric Learning via Lifted Structured Feature Embedding

Triplet Loss

最近，learning to rank 的思想逐渐被应用到很多领域。learning to rank中其中重要的一个步骤就是找到一个好的similarity function，而triplet loss是用的非常广泛的一种。

triplet

如上图所示，triplet是一个三元组，这个三元组是这样构成的：从训练数据集中随机选一个样本，该样本称为Anchor，然后再随机选取一个和Anchor (记为x_a)属于同一类的样本和不同类的样本,这两个样本对应的称为Positive (记为x_p)和Negative (记为x_n)，由此构成一个（Anchor，Positive，Negative）三元组。

理解triplet loss

有了上面的triplet的概念， triplet loss就好理解了。针对三元组中的每个元素（样本），训练一个参数共享或者不共享的网络，得到三个元素的特征表达，分别记为：$f(x_i^a)$，$f(x_i^p)$，$f(x_i^n)$。triplet loss的目的就是通过学习，让$x_i^a$和$x_i^p$特征表达之间的距离尽可能小，而$x_i^a$和$x_i^n$的特征表达之间的距离尽可能大，并且要让$x_i^a$与$x_i^n$之间的距离和$x_i^a$与$x_i^p$之间的距离之间有一个最小的间隔$\alpha$。公式化的表示就是：

$$||f(x_i^a)-f(x_i^p)||_2^2+\alpha<||f(x_i^a)-f(x_i^n)||_2^2, \forall(f(x_i^a),f(x_i^p),f(x_i^n)) \in \mathcal{T}$$

对应的目标函数也就很清楚了：

$$\sum_i^N [||f(x_i^a)-f(x_i^p)||_2^2-||f(x_i^a)-f(x_i^n)||_2^2+\alpha]_+$$

这里距离用欧式距离度量，$+$表示$[]$内的值大于零的时候，取该值为损失，小于零的时候，损失为零。
由目标函数可以看出:

• 当$x_i^a$与$x_i^n$之间的距离小于 $x_i^a$与$x_i^p$之间的距离加$\alpha$，$[]$内的值大于零，就会产生损失。
• 当$x_i^a$与$x_i^n$之间的距离大于或等于 $x_i^a$与$x_i^p$之间的距离加$\alpha$时，损失为零。

triplet loss 梯度推导

上述目标函数记为$L$。则当第$i$个triplet loss大于零的时候，仅就上述公式而言，有：

$$\frac{\partial L}{\partial f(x_i^a)}=2·(f(x_i^a)-f(x_i^p))-2·(f(x_i^a)-f(x_i^n))=2·(f(x_i^n)-f(x_i^p))$$ $$\frac{\partial L}{\partial f(x_i^p)}=2·(f(x_i^a)-f(x_i^p))·(-1)=2·(f(x_i^p)-f(x_i^a))$$ $$\frac{\partial L}{\partial f(x_i^n)}=-2·(f(x_i^a)-f(x_i^n))·(-1)=2·(f(x_i^a)-f(x_i^n))$$

实现时的trick

可以看到，对$x_i^p$和$x_i^n$特征表达的梯度刚好利用了求损失时候的中间结果，给的启示就是，如果在CNN中实现 triplet loss layer, 如果能够在前向传播中存储着两个中间结果，反向传播的时候就能避免重复计算。这仅仅是算法实现时候的一个trick。

选取batch

对于整个数据集来说，这样的三元组的数量是非常多的，假设总共有$N$张图片，每个人有$K$张图，那么数量级大概是$N·N·K$, 而且这些组合当中有一些是非常容易满足上述条件的，那么对于优化的意义不大，所以应该通过更加合理的方式来选择这样的三元组。

如论文中所说，我们应该选择违背上述条件最严重的组合，是否违背上述条件是要通过计算图片之间的embedding的欧式距离得到，但是embedding又是不断在优化更新，也就是说违背条件最严重的组合是有可能不断变化的，如果每次更新都重新选择一次，那么对训练效率会有很大影响。文中提到了两种替代的方案：

1. 每经过特定的迭代次数，选用最新的checkpoint，在一个训练数据子集上面选择一次三元组。
2. 在线方法，每训练一次minibatch，选择一次三元组。

Beyond Triplet Loss

一篇讲Person Re-ID的论文，来自CVPR2017，改进了Triplet Loss。

文章链接： 《Beyond triplet loss: a deep quadruplet network for person re-identification》

引言

文章的出发点就在上面这张图。 如上图a，传统的triplet Loss可能在test集上泛化效果一般，主要是因为类内方差依然比较大。文章对此增加了新的约束，用于减小类内方差和增加类间方差。

即，新的Loss不仅要求 $B1B3<B1A3$ 同时要求 $C1C2<B1A3$。

方法

首先是传统的triplet Loss，如下式：$x_i$ 、$x_j$属于同一类，$x_k$属于另一类，$α_{trp}$ 表示预设的margin, $f(x_i)$表示归一化的高度嵌入的特征。 其描述的网络结构如上图a所示。

$$L_{trp}=\sum_{i,j,k}^N [||f(x_i^a)-f(x_i^p)||_2^2-||f(x_i^a)-f(x_i^n)||_2^2+\alpha_{trp}]_+$$

上式直接使用欧式距离作为相似性度量，作者准备用一种可以学习的方式来代替，于是就有了下式： $g(x_i,x_j)$表示一种新的相似性测度，其描述的网络结构如上图b所示。

$$L_{trp}=\sum_{i,j,k}^N [g(x_i,x_j)^2-g(x_i,x_k)^2+\alpha_{trp}]_+$$

上式中的$g(x_i,x_j)$还有必要约束一下范围，否则会造成学习很不稳定。(比如要求 $g_1−g_2< 0.1$, 如果g不约束范围，那么$g_1$和$g_2$ 同时放大10000倍将会使得约束阈值毫无意义。）于是作者在后面增加了一个softmax约束来获得$[0,1]$的相似度，同时作者也增加了一个softmax loss，整体网络结构如上图c所示。

在上面的基础上，作者完善了自己的Quadruplet Loss：

$$L_{quad}=\sum_{i,j,k}^N[g(x_i,x_j)^2-g(x_i,x_k)^2+\alpha_1]_+\sum_{i,j,k,l}^N[g(x_i,x_j)^2-g(x_l,x_k)^2+\alpha_2]_+,s_i=s_j,s_l \neq s_k, s_i \neq s_l, s_i \neq s_k$$

上式共有两项，前一项是传统的Triplet Loss，后一项用于进一步缩小类内差距。 由于前一项的重要更大，因此作者控制$\alpha_1 > \alpha_2$。

另一方面，如何确定margin的值也是一件让人很头疼的事情，选择小了收敛不好，选择大了不好收敛。 文章为此采用了一种自适应margin设定策略：

$$\begin{align*} \alpha &= w(\mu_n-\mu_p) \\ &= w(\frac{1}{N_n}\sum_{i,k}^Ng(x_i,x_k)^2-\frac{1}{N_p}\sum_{i,j}^Ng(x_i,x_j)^2),s_i=s_j,s_i \neq s_k \end{align*}$$

即margin设定为同类距离均值与异类距离均值之差，$w$用来调整大小，具体地对于$\alpha_1,w=1$；对于$\alpha_2,w=0.5$。

训练初期，上面的margin策略可能导致难以收敛，因此作者前期先使用固定的margin，稳定后再实行该策略。

具体训练时，作者采用了如下图所示的四元组：

评价

实验部分就不分析了。 最近改进triplet Loss来做Re-ID的很多，虽然各各都声称效果不错，但实际上也都没有特别明显的提高。 同时，很多文章里面的一些结论或者说经验都有相互冲突的地方。因此，我还是比较欣赏那个说法：

我只能保证我的方法在这个任务上比较好，对于其它任务，还需要实际的检验。

参考文献

[1] L. Wu, C. Shen, and A. van den Hengel. Deep linear discriminant analysis on fisher networks: A hybrid architecture for person re-identification. Pattern Recognition, 2016

[2] D. Cheng, Y. Gong, S. Zhou, J. Wang, and N. Zheng. Person re-identification by multi-channel parts-based cnn with improved triplet loss function. In CVPR, 2016

In Defense of the Triplet Loss

前言

triplet loss是非常常用的一种deep metric learning方法，在图像检索领域有非常广泛的应用，比如人脸识别、行人重识别、商品检索等。传统的triplet loss训练需要一个三元组，包括三张图片：achor,positive,negative，分别简写为a,p,n。triplet loss的缺点在于随机从训练集中挑选出三张图片，那么可能会出现挑选出来的很可能是简单的样本，比如很像的正样本对和很不像的负样本对。作者认为，让网络一直学习简单的样本会限制网络的泛化能力，因此提出一种在线batch hard sample mining的改进版triplet loss，我喜欢简写为TriHard loss。我复现了这种方法，并且大量实验表明，这种改进版的方法效果非常好。

方法

TriHard loss的核心思想是：对于每一个训练batch，随机挑选$P$个ID的行人，每个行人随机挑选$K$ 张不同的图片，即一个batch含有$P×K$张图片。之后对于batch中的每一张图片$a$，我们可以挑选一个最难的正样本和一个最难的负样本和$a$组成一个三元组。首先我们定义和a为相同ID的图片集为$A$，剩下不同ID的图片图片集为$B$，则TriHard损失表示为：

$$L_{th} = \frac{1}{P \times K}\sum_{a \in batch}(\max_{p \in A} d_{a,p}-\min_{n \in B} d_{a,n}+\alpha)_+$$

其中$α$是人为设定的阈值参数。TriHard loss会计算$a$和batch中的每一张图片在特征空间的欧式距离，然后选出与$a$距离最远（最不像）的正样本$p$和距离最近（最像）的负样本$n$来计算三元组损失。通常TriHard损失效果比传统的三元组损失要好。

代码

用keras复现了一版triplet loss和TriHard loss，代码没怎么整理但是能用，可供大家参考复现，代码链接：keras_reid

Improved Triplet Loss

$$d^n(I_i^o,I_i^+,I_i^-,w)=d(\phi_w(I_i^o),\phi_w(I_i^+))-d(\phi_w(I_i^o),\phi_w(I_i^-)) \le \tau_1$$

但是，这个损失函数并没有显示的表示：Anchor和正样本间的距离应该有多近。所造成的一个结果，就可能是：属于同一个行人的距离可能构成一个大的簇，并且在所学习的特征空间里有一个较大的类间距。明显的是，并没有一个需要的输出，这不可避免的会损害再识别的性能。

基于以上观察，我们做了相应的改进。我们添加了相应的新的损失函数来增强约束。Anchor和正样本之间的距离应该小于一个阈值 $\tau_2$, 并且这个阈值应该小于$\tau_1$。

这个改进的损失函数进一步的拉近了同一个行人之间的距离，并且拉远了不同行人之间的距离。

$$L(I,w)=\frac{1}{N}\sum_{i=1}^N(max\{d^n(I_i^o,I_i^+,I_i^-,w),\tau_1\}+\beta max\{d^p(I_i^o,I_i^+,w),\tau_2\})$$

其中，$N$是triplet训练样本的个数，$β$平衡了类别内部和类别之间的约束。距离函数$d(.,.)$ 是 L2-norm距离。

Lifted Structured Loss

动机

现有的三元组方法却无法充分利用 minibatch SGD training 的 training batches 的优势。

方法

$$J=\frac{1}{2|\widehat {\mathcal {P}}|}\sum_{(i,j) \in \widehat {\mathcal {P}}}max(0, J_{i,j})^2,$$ $$J_{i,j}=max(max_{(i,k) \in \widehat {\mathcal {N}}} \alpha-D_{i,k},max_{(j,l) \in \widehat {\mathcal {N}}} \alpha-D_{j,l})+D_{i,j}$$

其中，$P$是正样本的集合，$N$是负样本的集合，前一项为数据$i$最难区分的$k$和数据$j$最难区分的数据$l$的距离中较大者，后一项为数据$i$，$j$之间的距离，相当于$O(m)$变为了现在的$O(m^2)$pairs一个完全图。这个函数提出了两个计算上的挑战：

1. 非平滑（non-smooth）
2. 评价和计算其子梯度需要最小化所有样本对若干次。

以两种方式解决了上述挑战：
首先，我们优化上述函数的一个平滑上界；
第二，对于大数据常用的方法类似，我们采用随机的方法。
然而，前人的工作都是用SGD的方法，随机的均匀的选择triplet对。我们的方法从这之中得到了借鉴：
(1)选取最近的负样本；
(2)一次采样就充分的利用了一个mini-batch的全部信息，而不仅仅是两个对之间的信息。

方法改为并非完全随机，而是引入了重要性采样的元素。我们随机的采样了一些正对，然后添加了一些对它们来说是难的负样本来训练mini-batch。

注意到方法可以从两端开始搜索，而三元组则仅仅只能和定义好的结构上的元素进行搜索。

随机对 training batch 采样，采用contrastive loss 和 triplet loss 失败的情况。这里以三类为例，分别对应棕色圆、绿色方块和紫色棱形。虚线灰色弧线表示在 hinge loss 中的边界(超出边界后，loss变为0)。品红色箭头表示对于 positives 的 negative 梯度方向。
(a)当随机采样的 negative ($x_j$) 与其它类的样本共线时，contrastive embedding 会失败；
(b)当随机采样的 negative ($x_n$) 相对于 positive ($x_p$) 和 anchor ($x_a$)，在边界内时，triplet embedding 会失败。

平滑优化上界：

$$\tilde J_{i,j}=log(\sum_{(i,k) \in \mathcal N}exp\{\alpha - D_{i,k}\}+\sum_{(j,l) \in \mathcal N}exp\{\alpha - D_{j,l}\})+D_{i,j}$$ $$\tilde J=\frac{1}{2|\mathcal P|} \sum_{(i,j) \in \mathcal P} max(0,\tilde J_{i,j})^2$$

其中，$P$是batch中 positive pairs 集合，$N$是negative pairs 的集合。

$$\frac{\partial \tilde J}{\partial D_{i,j}}=\frac{1}{|\mathcal P|}\tilde J_{i,j} \mathbb{1}[\tilde J_{i,j}>0]$$ $$\frac{\partial \tilde J}{\partial D_{i,k}}=\frac{1}{|\mathcal P|}\tilde J_{i,j} \mathbb{1}[\tilde J_{i,j}>0]\frac{-exp\{\alpha-D_{i,k}\}}{exp\{\tilde J_{i,j}-D_{i,j}\}}$$ $$\frac{\partial \tilde J}{\partial D_{j,l}}=\frac{1}{|\mathcal P|}\tilde J_{i,j} \mathbb{1}[\tilde J_{i,j}>0]\frac{-exp\{\alpha-D_{j,l}\}}{exp\{\tilde J_{i,j}-D_{i,j}\}}$$

其中的 $\mathbb{1} [*]$ 是指示函数，如果括号内的判断为真，那么输出为1，否则就是0。

本文是在三元组损失函数基础上的一个改进。并非仅仅考虑预先定义好的样本之间的差异性，而是考虑到一个 batches 内部 所有的样本之间的差异。在这个过程中，文章中引入了类似 hard negative mining 的思想，考虑到正负样本之间的难易程度。