Press "Enter" to skip to content

论文笔记(七)Earth Mover’s Distance for FSL CVPR 2020

DeepEMD: Differentiable Earth Mover’s Distance for Few-Shot Learning CVPR-2020

 

Abstract

 

深度学习在大量标记数据的学习中被证明是非常有效的。但小样本学习(FSL)尝试只用少量的标记数据进行学习。本文从图像子区域之间的最优匹配( optimal matching between image regions)的角度出发,提出一种新的小样本方法。采用推土机距离( the Earth Mover’s Distance ,EMD)来作为度量方式,去图像表示之间的结构距离,以确定图像相关性。EMD在结构元素之间生成匹配代价最小的最优匹配流,用于计算图像距离进行分类。为了生成EMD公式中元素的权重。本文设计了一种交叉参照机制(cross-reference mechanism),可以有效的缓解杂乱的背景和较大的类内差异带来的不利影响。为了解决k-shot分类(每类样本只出现k个),提出学习一个结构化的完全连接层(FC),可以利用EMD直接对图像表征进行分类。基于隐函数定理( the implicit function theorem),EMD可以作为一层结构插入到网络中进行端到端训练。大量的实验表明提出方法的有效性,在小样本分类任务中以显着的优势取得SOTA。

 

目前该论文已经被CVPR-2020接受,目前似乎正在改投期刊,原文链接和代码如下:

DeepEMD: Few-Shot Image Classification with Differentiable Earth Mover’s Distance and Structured Classifiers ​ arxiv.org
https://git.io/DeepEMD ​ git.io

Introduction

 

深度学习在大量的视觉任务取得了巨大的成功,但是依赖于大量标记的数据。小样本学习被提出用于解决该类问题。本文的动机如下图一所示,使用EMD来计算两张图局部表征之间的相似度,用于避免无关背景和类间差异的影响。EMD可以表述成运输问题( the transportation problem),通过求解线性规划问题可以得到全局最小值。同时应用隐函数定理构建基于最优变量的雅可比矩阵。

在EMD中一个重要的参数是每个元素的权重。在理想情况,算法应该能灵活的赋予无关区域较少的权重,无论这些区域匹配到了什幺。因此,本文提出了一种交叉参照机制来决定每个元素的重要性,通过将每个节点与另一个结构的全局统计信息进行比较来确定每个节点的权重。与其他图像相关性较大的图像区域更有可能是目标区域,应该赋予更多的权重;而对于背景区域和高度差异部分的权重应该尽量小。

 

在k-shot分类中,提出结构化的完全连接层来利用训练图片。该层中,每个类包含一组可学习的向量。该结构化的FC可以看做是标准全连接层的扩展,使用EMD来代替点积操作,使得能直接对feature maps见分类。结构化的FC层也可以理解为学习每个类别的虚拟图像生成的原型表征( prototype embedding),使测试图像能够与每个类别匹配进行分类。

 

该文章的贡献总结如下:

 

 

    1. 将小样本分类问题转换成最优匹配问题,同时利用EMD作为距离度量。EMD层能加入到网络结构中进行端到端的训练

 

    1. 提出交叉参照机制来产生元素的权重,能有效减少图像中无关区域带来的noise

 

    1. 提出了结构化的全连接层,能够直接对结构化的图像表征进行分类

 

    1. 大量的实验表明方法的优异性能,达到了SOTA

 

 

Method

the Earth Mover’s Distance

 

EMD(推土机距离)是一种用于测量两组带权元素或分布之间的距离。该距离能够被表示为传输问题( transportation problem,TP),其目标是找到一个最低成本的货物运输方案:

 

 

其中s_i表示资源,di表示目的地,将资源i运到目的地j的成本是cij,数量记为xij。

 

EMD for Few-Shot Classification

 

局部表征更有可能提供跨类别的可迁移信息。在提出的框架中,将图像分解成一组局部表征,并通过在两幅图像中为局部表征分配适当的权值,可以使用它们之间的最优匹配代价来表示它们的差异。在这里尝试了3种方法来产生图像的局部表征:

 

 

    1. 全连接卷积网络:每一张图片都被表示为dense表征:

    1. ,每一个向量

    1. 被看作集合中的节点

 

    1. 网格划分:直接将输入图像进行划分成

    1. 个区域,每个区域分别输入到CNN

 

    1. 图像随机取样:在图像中随机抽取M个大小和长宽比不同的patch。然后随机采样的小块被缩放到相同的输入大小,再输入到CNN

 

 

这三种方案分别被称为 DeepEMD-FCN, DeepEMD-Grid 和 DeepEMD-Sampling。

 

在取得图像的表征后,开始计算距离。具体来说,通过计算两个图像特征的表征节点 , 之间的距离得到单位代价:

 

 

一旦获得最优匹配方案,就可以计算图像表征之间的相似度得分s:

 

End-to-End Training

 

为了将优化问题嵌入到神经网络中进行端到端的训练,就要使得求解最优匹配的问题可微分。本文采用基于KKT条件的隐函数定理来获取 Jacobian矩阵。为了表达完整性,将公式(1)写成以下的矩阵形式:

 

 

其中 表示需要优化的变量, 。这几个公式分别表示公司(1)的相等约束和不等约束。后面的数学推导没看懂,,,略/(ㄒoㄒ)/~~ 希望大佬赐教!

 

Weight Generation

 

直观地看,权值较大的节点在两个集合的比较中起着更重要的作用。对于FSL分类任务,我们认为两幅图像中同时发生的区域更有可能是前景区域,而不是单独检查单个图像来确定权重,节点特征的权重应该通过比较两边的节点来生成。因此为了实现这一目标,提出了一种交叉引用机制,该机制使用一个节点特征与另一个结构中的平均节点特征的点积来生成一个相关性评分,作为权重值:

 

 

其中 表示来自两个特征图的向量, 函数保证权重是非负的。最后,对结构中所有的权值进行标准化,使两边的总权值相同,以进行匹配:

 

Structured Fully Connected Layer

 

目前本文只考虑了one-shot的情况,下面开始考虑k-shot的情况。对于标准的FC层,FC层的学习可以看作是为每个类找到一个原型向量,这样就可以使用距离度量来对图像进行分类。

 

使用用同样的形式,可以学习一个采用EMD作为距离函数直接对一个结构化特征表示进行分类的结构化全连通层(structured fully connected layer)。每个类的可学习嵌入变成了一组向量,而不是一个向量,这样就可以使用结构化的距离函数EMD来进行图像分类。这也可以解释为学习由每个类的虚拟图像生成的原型特征映射。

算法1为在推理时的伪代码。

Experiments

 

关于实验的详细设置和数据集介绍请查看原文

 

methods based on image-level and local-level

Weights in the EMD

Local embedding extractor

Comparison with other k-shot methods

Cross-Domain Experiments

Comparison with State-of-the-art Methods

Personal Thought

 

优点:

 

 

    1. 确实是一篇非常solid的工作,达到了CVPR的水平。应该是首次将EMD引入到小样本学习领域中,比较新颖,具有一定的可解释性

 

    1. 提出交叉参照机制来产生元素的权重,能有效减少图像中无关区域带来的noise

 

    1. 提出了结构化的全连接层,能够直接对结构化的图像表征进行分类,相当于FC层的扩展

 

    1. 由于作者最近又准备扩展成期刊,又加入了大量的实验,特别是在原来的DeepEMD-FCN ,又提出了 DeepEMD-Grid和DeepEMD-Sampling

 

    1. 进行了大量的消融实验和对比,验证了方法的有效性

 

 

Comments:

 

 

    1. 由于引入了EMD,所以导致时间复杂度是较高的,解LP的时间复杂度是四次方,即使用了近似的方法也有三次方,对于小样本问题是可行的,但大一点的样本复杂度就很高了

 

    1. 相对于传统的小样本学习,其算法流程也是更繁琐的,让人看起来对比不是那幺“fair”,特别是对于k-shot,该EMD方法首先需要进行预训练,然后再进行episodic training,training介绍后,在testing阶段仍需要进行梯度的更新。

 

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注