从标题就可以看出来，这篇文章提出了一种无监督的困难样本挖掘(hard training example mining)的框架。
问题提出
一方面，现有的深度学习方法大多需要数据标签。另一方面，传统的非线性降维方法或者流形学习方法，并没有学到从输入空间到嵌入空间的精确的映射，对于新数据的泛化能力较差。为了解决这两个不足，作者提出了本文的无监督学习框架。
基本思路
文章中用到了两种距离，欧氏距离(Euclidean)与流形(Manifold)距离。作者认为，对于某一个锚点(anchor point)，正样本应该分布在同一流形上，而负样本应分布在不同的流形上。在新学习到的空间中，正样本应被锚点吸引，而负样本应该被挤开(repelled)。
作者首先利用预训练的CNN网络提取图像的特征，并基于提取到的特征定义hard positive sample与hard negative sample，进而获得三元组。通过优化定义在三元组上的损失函数达到训练的目的。
具体方法
预备知识
作者用$X=\{x_1, \dots, x_n\}\subset\mathcal{X}$表示原始的输入空间$f(\cdot:\theta):\mathcal{X}\rightarrow\mathbb{R}^d$将数据从输入空间映射到了d维的嵌入空间。这些输入的数据通过它们的特征进行表示，$Y=\{y_1,\dots,y_n\}\subset\mathcal{Y}\quad, \quad y=g{(x)}$.这里的$g$可以是直接由输入学到的$f$，也可以是从一个相似模型学习得到的。
用$NN_k^e(y)$表示欧氏距离下$y\in Y$的k近邻，欧氏相似度由$s_e:\mathcal{Y}^2\rightarrow\mathbb{R}$给出。类似的，用$NN_k^m(y)$表示流形距离下的k近邻，流形相似度 $s_m:Y^2\rightarrow\mathbb{R}$.
定义以$Y$为结点的图$G$的邻接矩阵$A=(a_{ij})\in\mathbb{R}^{n\times n}$,
从任意的$\boldsymbol{f}^{(0)}\in\mathbb{R}^n$开始，进行如下迭代
其中$\hat{A}=D^{-1/2}AD^{-1/2}\ ,\ D=\mathrm{diag}(A1)$.这里的$1=[1,\dots,1]^T$,$A1$也就是按行求和。因此$D$就是图的度矩阵。对于一个线性系统，上式会收敛到下式的解$\boldsymbol{f}^*_i$
这一步可以用共轭梯度下降法来求解。而流形距离下的相似度矩阵可以写成
训练数据的选择
有了$s_m$之后就可以计算流形下的距离，也就有了$NN_k^m$,接下来就可以定义正样本与负样本。给定锚点$x^r$,对应的特征$y^r=g(x^r)$
分别为锚点的正、负样本池。
在训练的时候，并不会将每个点都作为锚点进行一次训练，而是会找到一个$\mathcal{A}\subset X$，我们希望找到的锚点能够满足：
- 这个锚点有着很多和它相关的图片
- 锚点之间有足够大的差异
这两点都可以利用近邻图$G$满足。首先计算在$G$上随机游走时的静态概率分布$\pi$,$\pi P=\pi$,其中$ \ P=D^{-1}A$，为状态转移的概率矩阵(matrix of transition probabilities),$p_{ij}\in P$表示由当前所在位置$i$到达位置$j$的概率。这一步可以通过power iteration method求解。这里的$\pi$代表的每个结点的重要性，越重要的结点越可能在随机游走的时候被访问到。取概率最大的固定数量的结点，就构成了锚点的集合$\mathcal{A}$.
Training
每次训练的时候，会首先选择$x^r\in\mathcal{A}$,然后随机挑选$x^+\in P^+(x^r)$与$x^-\in P^-(x^r)$。计算$z^r=f(x^r;\theta)$,$z^+=f(x^+;\theta)$,$z^-=f(x^-;\theta)$.
计算contrastive loss或triplet loss
这里的$[\cdot]_+=\max(\cdot, 0)$,$m$被称为margin parameter,表示凡是落在这个间隔内的差异都是可以接受的，不会被算到损失函数中。
如果要考虑不同样本的权重，那么可以给损失函数乘上$s_m(x^r, x^+)$，这意味着降低了正样本过于难以挖掘的三元组的权重。
此外，还可以在训练的过程中交替的更新图、样本池、更新embedding.这时，每一步的$Y$都是上一步的$Z=\{f(x;\theta):x\in X\}$.