计算机视觉研究院专栏
作者：Edison_G
提出一种基于度量学习的小样本学习算法（DeepEMD）。之前的基于度量学习的小样本学习算法通常是利用一个特征提取网络将支持集图像和查询集图像映射到一个特征空间，然后再设计或选择一种距离度量方式，来描述支持集图像和查询集图像之间的相似程度，并以此进行类别预测。而本文则是将图片拆分成多个图块，然后引入一种新的距离度量方式陆地移动距离（Earth Mover’s Distance，EMD），计算查询集和支持集图像的各个图块之间的最佳匹配代价来表示二者之间的相似程度。
计算机视觉研究院
回复“DeepEMD”获取下载论文
EDC.CV
1. 简要
事实证明，深度学习在大量标记数据的学习中是非常有效的。很少有shot learning，相反，试图学习只有少数标签数据。
在本次介绍中，从图像区域之间最优匹配的新角度开发了few-shot图像分类的方法。使用Earth Mover’s Distance(EMD)作为度量，计算密集图像表示之间的结构距离，以确定图像相关性。该EMD在具有最小匹配成本的结构单元之间产生最优匹配流，用于计算图像距离进行分类。为了生成EMD公式中元素的重要权重，还设计了一种交叉引用机制，它可以有效地缓解背景杂乱和类内外观变化大所造成的不利影响。为了处理k-shot分类，提出学习一个结构化的全连接层，它可以直接用所提出的EMD对密集图像表示进行分类。基于隐式函数定理，EMD可以作为一个层插入到网络中进行端到端训练。
广泛的实验验证了新算法的有效性，在四个广泛使用的few-shot分类基准上表现出很大的优势，即 miniImageNet, tieredImageNet, Fewshot-CIFAR100 (FC100) and Caltech-UCSD Birds-200-2011 (CUB)。
2.背景
深度神经网络在许多视觉任务中取得了巨大的成功，通常需要大量的标记数据。深度学习方法的一个臭名昭著的缺点是它们的样本效率很差。这与我们人类如何学习形成了鲜明的对比。在机器学习中，提出了小样本学习来解决这个问题，这可以看作是更广泛的元学习的一个特例。元学习试图学习一个模型，它可以快速地推广到新的任务，并进行少量的适应工作。元学习算法研究最充分的测试平台之一是小样本图像分类，其目的是对仅有有限数量标记训练数据的新图像类别进行分类。这是这里工作的重点！
确定两个复杂结构表示的相似性的一种自然方法是比较它们的构建块。困难在于，我们没有他们的通信监督训练，并不是所有的建筑要素都能在其他结构中找到他们的同行。
为了解决上述问题，将少样本分类形式化为最优匹配的实例，并提出利用两种结构之间的最优匹配成本来表示它们的不同。给定两幅图像生成的局部特征表示集，使用EMD计算它们的结构相似性。EMD是计算结构表示之间距离的度量，最初是为图像检索而提出的。给定所有元素对之间的距离，EMD可以获得具有最小总体距离的两个结构之间的最佳匹配流。它也可以解释为相对于另一个结构表示重建结构的最小成本。
新算法提出的动机的例子如上图所示。EMD具有transportation问题，通过求解线性规划问题可以达到全局最小值。为了将优化问题嵌入到模型中进行端到端训练，应用隐式函数定理（implicit function theorem），形成最优优化变量相对于problem parameters的雅可比矩阵。
探索了从图像中提取局部表示的多种方法，包括全卷积网络、图像网格和图像区域采样；还在特征层次和图像层次上应用金字塔结构来捕获不同尺度的局部表示。
在EMD公式中，一个重要的特定于问题的参数是每个元素的权重。具有较大权重的元素产生更多的匹配流，从而对整体距离做出更大的贡献。理想情况下，无论它们与哪些元素匹配，该算法应该考虑到对不相关区域分配较少权重的灵活性，使得它们对总体距离的贡献较小。
为了实现这一目标，提出了一个交叉引用机制来确定元素的重要性。在所提出的交叉引用机制中，通过将每个节点与其他结构的全局统计量进行比较来确定每个节点的权重。直观地说，显示与其他图像更相关的图像区域更有可能是对象区域，并且应该分配更多的权重，而高方差背景区域和两幅图像中不同时发生的对象部分的权重应该尽可能地消除，以计算匹配成本。
3.新方法
我们首先简要回顾了EMD，并描述如何将少样本分类描述为一个可以训练到底端到端的最优匹配问题；然后，描述交叉引用机制来生成每个节点的权重，这是EMD公式中的一个重要参数；最后，演示了如何使用EMD距离函数来处理k-shot学习与提出的结构化全连接层。提出的少样本分类框架的概述如下图所示。
3.1 Revisiting the Earth Mover’s Distance
首先介绍下EMD的计算过程，EMD的计算本身是来源于线性规划中的运输问题，假设有一系列的货源地mathcal{S}={s_i|i=1,…,m}，S={si∣i=1,…,m}和一系列的目的地mathcal{D}={d_j|j=1,…,k}，D={dj∣j=1,…,k}，si和dj分别表示货源地ii的货物供应量和目的地jj的货物需求量，cij表示两地之间的单位运输成本，xij表示两地之间的运输量，那么运输问题的目的就是寻找运输成本最低的运输方案tilde{mathcal{X}}={tilde{x}_{ij}|i=1,…,m,j=1,…,k}，X~={x~ij∣i=1,…,m,j=1,…,k}，过程如下：
3.2 EMD for Few-Shot Classification
本次新技术，将mathcal{S}和mathcal{D}分别看作支持集图像和查询集图像对应的特征图，特征图中的每个像素点都是一个带有权重的结点，而si和dj分别对应各个结点的权重，支持集特征图每个像素点对应的特征向量为ui，而查询集特征图每个像素点对应的特征向量为vj，则两个结点间的运输成本cij可定义为：
通过求解上述的线性规划问题，寻找最优的运输方案tilde{mathcal{X}}，则两幅特征图之间的相似性可由下式计算：
3.3 End-to-End Training
具体来说，为了从原始优化中构造紧致矩阵，可以在下面建立稀疏矩阵，用于等式约束：
以及不等式约束可以写成：
3.4 Weight Generation
证明了求解tilde{x}_{ij}x~ij的过程是可微分的，因此可以采用梯队下降的方式进行求解。而在求解过程中结点上的权重si和dj是很重要的，他直接影响了运输方案的设计，因此提出一种相互参考机制（cross-reference mechanism），权重si计算过程（dj的计算方法与其类似）如下：
通过比较两方结点之间的关系来计算每个结点处的权重，这样做的目的是对于方差较大，变化较多的背景区域分配更少的权重，而对于两幅图*现的目标区域分配更多的权重，然后再对所有的权重做正则化处理：
3.5 Structured Fully Connected Layer
将分类器中全连接层后的点乘操作，改为本次技术的EMD距离度量操作，就得到查询集图像与支持集图像的各个类别之间的相似性关系，进而预测分类结果，整体网络流程如下图所示：
算法步骤如下：
4.实验
Experiment on 5-way k-shot classification
不同基于度量的1-shot分类方法的比较。以EMD为距离度量的模型明显优于基于图像级表示和局部表示的基线模型。
Cross-domain实验(Mini Imagenet→CUB)。以95%的置信区间报告了1-shot 5-way和5-shot 5-way任务的性能。使用FCN提取KNN的局部特征和提出的新方法。提出的新算法在很大程度上优于基线方法。
金字塔结构应用于DeepEMD-FCN和DeepEMD-Grid上，以提取局部嵌入。特征金字塔结构(A)采用在特征映射上具有不同输出大小的RoI池化生成多尺度的局部嵌入，而图像金字塔结构(B)根据不同的网格大小将输入图像裁剪成块，并将所有块送到CNN以生成局部嵌入。
Results on miniImageNet and tieredImageNet datasets
DeepEMD-FCN的可视化
Visualization of full matching flows in DeepEMD-FCN
5.总结
EMD距离最早是应用于图像检索等领域的，将其引入图像分类算法中，主要是看中了其考虑局部图块之间的匹配关系。在先前的文章中，相对于将一整幅图像压缩为一个高度抽象的特征向量，并计算两个特征向量之间的距离作为相似性度量的方式而言，通过比较各个局部图块之间的相似程度来反映两幅图像是否属于同一类别，则更为可靠和准确。但如果是每两个图块之间都逐一比对的话，这计算成本也过于高昂，于是作者就利用EMD方法，通过线性规划的方式寻找两幅图像各个图块之间的最佳匹配方式，并且为不同的位置的图块分配了不同的权重，类似于注意力机制，对于目标区域给予更多注意。
／End.
计算机视觉研究院主要涉及深度学习领域，主要致力于人脸检测、人脸识别，多目标检测、目标跟踪、图像分割等研究方向。研究院接下来会不断分享最新的论文算法新框架，我们这次改革不同点就是，我们要着重”研究“。之后我们会针对相应领域分享实践过程，让大家真正体会摆脱理论的真实场景，培养爱动手编程爱动脑思考的习惯！
计算机视觉研究院
回复“DeepEMD”获取下载论文
EDC.CV