【文献阅读笔记】2018-KDD-Efficient Similar Region Search with Deep Metric Learning

Abstract

要解决的问题：使用者给出一个指定的查询区域，我们要找到与之对应的相似区域。

该问题在相似性的定义上以及搜索效率上存在两大挑战。

为应对这两大挑战，我们提出的解决方案包括：
（1）一个能同时考虑到目标属性和目标之间相对位置的用于学习相似性的深度学习方法
（2）一个用于寻找top-N区域的高效的分支定界搜索算法

1 Introduction

背景：随着移动设备和定位服务的普及化，大量的标注位置的目标可以从各种源公开获取到。这些目标逐渐被标上丰富的信息。这给我们提供了一个很大的机会去了解一个特定城市区域的信息。但由于信息的快速增长和城市的复杂性，人们只是获取到并熟悉自己生活的一小片区域的信息，并不能将自己对本区域的了解应用到其它新区域上。因此我们需要在地理空间上搜寻相似区域，这样能使人们能应用他们在熟悉区域了解的信息去探寻相似的新区域。

寻找相似区域面临两大挑战：

如何建立区域相似度模型
一个简单的方法是直接用目标区域内部的属性向量之和代表该区域，然后在两个区域的属性向量之间计算相似度。但这样就会忽略掉目标区域的空间信息，而目标之间的相对空间位置是衡量区域相似度的一个很重要的维度。而且，空间信息数据经常是有噪声的，建立一种对噪声具有鲁棒性的衡量标准也是很困难但很有必要的。
相似区域的搜寻效率需要比较高。

为解决第一个挑战，我们利用一个深度度量学习模型来学习一个排序的度量标准以比较区域。它使用CNN提取特征（可捕捉到目标之间的局部关系以用于相似性学习）。我们提出一个使用难负例挖掘的方法产生训练数据以让相似性度量对小的噪声和目标移动有稳健性。我们也提出一个基于比率的训练损失以对高度扭曲的空间数据具有稳健性。

为解决第二个挑战，我们先通过共享所有区域的计算来减少计算相似度时的时间开销；之后提出一个叫ExactSFRS的分支界定算法来大幅减少搜索空间；然后提出一个叫ApproxSFRS的近似方法，它的最坏时间复杂度是可调节的，它可以在准确性和效率之间找到折衷以支持不同的应用。

3 Problem Definition

在一个2维矩形地理空间 $P$ 中，考虑一个空间目标的集合 $\cal O$ 。每个目标 $o \in {\cal O}$ 都与一个属性向量 ${\rm a}_o \in {\Bbb R}^{1 \times d}$ 和一个地理定位 $(o.x,o.y)$ 相关联。在不同应用中目标属性可以是不同的。

定义1 区域 $R$

区域 $R$ 是 $P$ 中的一个矩形子空间，即 $R \subset P$ ， $R$ 的边界是 $(t,b,l,r)$ （分别代表top,bottom,left,right），其中包含的目标构成集合 ${\cal O}_R$ （不包含边界上的目标点），即 ${\cal O}_R \subset {\cal O}$ 。

对于两个区域 $R_1$ 和 $R_2$ ，定义它们间的相似度为 $sim(R_1,R_2)$ 。函数 $sim(·)$ 需要同时考虑区域中目标的属性和相对位置。

令查询区域为 $R_q$ 。

定义2 SRS问题

给定地理空间 $P$ ，一个查询区域 $R_q$ 和一个相似度量函数 $sim(·)$ ，则SRS问题指检索出一个由N个区域构成的集合（记为 $\cal R$ ）：
$sim(R_q,R_i) \geq sim(R_q,R_j),\forall R_i \in {\cal R}, \forall R_j \notin {\cal R}$ .

4 Region Similarity Learning

我们考虑一个叫triplet network（三元组网络）的深度度量学习方法，直接从数据中学出 $sim(·)$ 。

相似性学习部分的有关符号说明：

相似度学习符号说明.PNG

排序度量学习模型

triplet network（三元组网络）：在CV领域广泛应用于图像的排序度量。一个triplet network由一个共享CNN的三个实例组成，输入包含：查询样本 $x_q$ ，一个正例样本（相似） $x_+$ ，一个负例样本（不相似） $x_-$ 。当喂入这三个样本时，triplet network会产生出两个欧氏距离：
$d_+=||Net(x_q)-Net(x_+)||_2$ 和 $d_-=||Net(x_q)-Net(x_-)||_2$ ，
其中 $Net(x)$ 是 $x$ 对应的CNN最后一层特征图。要注意的是CNN的全连层被移除了，因为我们只对嵌入特征感兴趣。

triplet network的结构示意（这张图是网上找的）：

triplet网络结构.PNG

triplet network的学习目标是训练 $Net(·)$ 使得正样本与查询样本之间的距离小于负样本与查询样本之间的距离：
${\cal L} = \sum_{x_q,x_+,x_-} {max\{0,d_+ -d_- +\delta \}}+\lambda ||Net(·)||_2$
其中 $\delta$ 是两个距离之间的差距参数（需要让正例对应的那个距离比负例对应的那个距离至少小多少）， $\lambda ||Net(·)||_2$ 是 $Net(·)$ 的L2正则化项。

为了将一个区域喂入 $Net(·)$ ，我们将区域用一个预先定义的粒度分割成网格。我们为每个网格关联一个向量，这个向量是通过对单元格中目标的属性向量求和得到的。对于空单元格直接将其与0关联。于是，一个区域就被表示成了一个3维张量 $R \in {\Bbb R}^{w \times h \times d}$ ，其中前两维是单元格的空间维度，d维度代表属性。

将输出特征图 $Net(R)$ 表示为： ${\cal X} \in {\Bbb R}^{w^* \times h^* \times K}$ ，其中K是输出特征的维度数量。K维中的每一个都是一个包含空间信息的潜在特征。

为比较不同尺寸的特征图，我们在 $Net(·)$ 之后使用一个特征聚合层 $g(·)$ 以将每个特征图聚合成一个K维的特征向量 ${\bf v}=g({\cal X}),{\bf v} \in {\Bbb R}^{1 \times K}$ 。在本文中，我们是用一个全局max-pooling层作为 $g(·)$ 。因此输出的距离就是 $d_+=||{\bf v}_q-{\bf v}_+||_2$ 和 $d_-=||{\bf v}_q-{\bf v}_-||_2$ 。

通过使用学习到的度量，我们定义 $R_1$ 与 $R_2$ 间的相似度：
$sim(R_1,R_2) = \frac{1}{1+||{\bf v}_1-{\bf v}_2||_2}$

训练鲁棒的Triplet Network

由于没有标好标记的区域相似性数据，我们提出一种自监督的学习策略，通过学习自相似性来使模型具备鲁棒性，无需再获取标签。

训练数据的产生

$sim(·)$ 的鲁棒性也可以理解成：一个原始区域和一个由前者经少量噪声和移动而产生的区域应被视为是相似的。所以我们如此创造出查询区域 $R_q$ ，负例输入 $R_-$ 和正例输入 $R_+$ ：

随机在任意位置以各种尺寸取查询区域 $R_q$ 。

对每个 $R_q$ ，先通过给 $R_q$ 添加噪声和移动产生出 $R_+$ ，方法包括：
(1) 随机去除目标
(2) 在随机的位置添加随机的目标
(3) 随机移动目标的位置
我们用噪声率和移动率来控制噪声和移动的产生：
噪声率设为0.1意思是随机删除10%的目标，之后再在该区域的随机位置上添加进相同数量的随机目标
移动率设为0.1意思是将每个实例沿随机方向移动不超过区域高和宽的10%的随机的距离。

之后为每个 $R_q$ 产生 $R_-$ 。我们在地图上随机找出不与 $R_q$ 重叠的区域作为 $R_-$ 。不过一些 $R_-$ 与 $R_q$ 的差距过大，可能导致模型收敛到的解不够好，所以还要添加一些难例：我们也通过向 $R_q$ 添加更多一些的噪声（相比创造 $R_+$ 的时候）来产生出 $R_-$ 。我们会在训练集中添加一小部分这样的难负例。这会迫使模型学到更多更有区分性的特征以正确区分 $R_+$ 和 $R_-$ ，进而能最小化损失值。

使用这样的产生式数据，模型学到的特征对小的噪声和移动也就具有了鲁棒性。

基于比率的训练损失

不同区域中的目标数差别很大，这可能会导致一些训练数据组的损失值很大，盖过了其它训练数据的影响。一般遇到这种情况的处理方法会是对输入数据做归一化，但这里如果这么做又会丢失掉区域中目标数量的信息，而目标数量差得很多的区域显然应该是不相似的。
所以我们采用下面这样一个基于比率的训练损失：
${\cal L} = \sum_{x_q,x_+,x_-} {max\{0,\frac{d_+}{d_+ +d_-} -\delta \}}+\lambda ||Net(·)||_2$
这样每个训练组的损失值都被限制在 $[0,1-\delta]$ 之间，极端的训练实例也不会过于影响到整个损失函数 $\cal L$ 。

训练Triplet网络的过程示意：

训练triplet网络的过程.PNG

5 Region Search Algorithm

在度量学习中我们将 $P$ 分成了粒度相同的网格。一个简单的搜寻相似度的方法是将查询区域 $R_q$ 与所有 $P$ 中的候选区域都比较一遍，但这样的时间开销是非常大的（两方面：计算相似度时计算特征图的时间开销很大；由于地图很大，候选区域是很多的，不可能穷举搜索）。

区域搜寻部分的有关符号说明：

搜寻算法部分符号说明.PNG

通过共享计算转化问题

共享计算

由于对每个区域都做 $Net(·)$ 的前向传播很慢，我们预计算出整个地理空间的特征图，也就是 ${\cal X}_P=Net(P)$ ，并将其共享以计算 ${\cal X}_c$ 。

共享特征图以计算相似度.PNG

如上图，我们先计算出查询区域的向量 ${\bf v}_q=g(Net(R_q))$ 。之后我们将图 $P$ 中的区域 $R_c$ （也就是区域 $(t,b,l,r)$ ）映射到特征图 ${\cal X}_P$ 中的区域 ${\cal X}_c$ 上（表示为区域 $(t^*,b^*,l^*,r^*)$ ）。这样我们就能以 $O(1)$ 的复杂度直接从 ${\cal X}_P$ 上获取到 ${\cal X}_c$ 。

问题转化

在本文的之后部分我们称 ${\cal X}_P$ 是特征空间，称 ${\cal X}_c$ 是一个特征区域。我们之前所说的SRS问题便转化为了Similar Feature Region Search (SFRS)问题：

定义3 SFRS问题

给定 ${\cal X}_q$ 和 ${\cal X}_P$ ，在 ${\cal X}_P$ 上寻找一个由 $N$ 个特征区域组成的集合（表示为 $\cal F$ ）：
$||g({\cal X}_q)-g({\cal X}_i)||_2 \leq ||g({\cal X}_q)-g({\cal X}_j)||_2, \forall {\cal X}_i \in {\cal F},\forall {\cal X}_j \notin {\cal {\cal F}}$

在找到top-N的相似特征区域后，我们可以将它们在 ${\cal X}_P$ 上的区域映射回它们在 $P$ 上的对应区域。于是就找到了top-N区域。

用于SFRS的提取算法

代表搜索空间

特征空间 ${\cal X}_P \in {\Bbb R}^{W^* \times H^* \times K}$ 是一个三维张量，一个候选特征区域 ${\cal X}_c \in {\Bbb R}^{w^* \times h^* \times K}$ 是 ${\cal X}_P$ 的一个子张量，特征维度相同都是 $K$ 。候选特征区域的位置可以用一个参数化元组表示： $(t^*,b^*,l^*,r^*)$ ，其中 $1 \leq l^* \leq r^* \leq H^*$ ，且 $1 \leq b^* \leq t^* \leq W^*$ 。可以用下面的搜寻空间的概念来代表四个坐标对应的四个间隔区域：

定义4 搜索空间

搜索空间：一个特征区域位置的集合 ${\cal S}={\bar t} \times {\bar b} \times {\bar l} \times {\bar r}$ ，其中 ${\bar t}=[t_{min}^{*},t_{max}^{*}],{\bar b}=[b_{min}^{*},b_{max}^{*}],{\bar l}=[l_{min}^{*},l_{max}^{*}],{\bar r}=[r_{min}^{*},r_{max}^{*}]$ ，使得 $\forall (t^*,b^*,l^*,r^*) \in {\cal S}$ ，满足 $t^* \in {\bar t},b^* \in {\bar b},l^* \in {\bar l},r^* \in {\bar r}$ 。

其中×是笛卡尔积。搜索空间的概念如下图中灰色区域所示：

搜寻空间图示.PNG

一个候选搜索区域就应是上图灰色区域中的虚线框（也就是说 ${\cal X}_{\cap} \subset {\cal X}_c \subset {\cal X}_{\cup}, \forall {\cal X}_c \in {\cal S}$ ）。利用这种表示形式，整个搜寻空间可以表示成： ${\cal S}_{\forall} = [1,H^*] \times [1,H^*] \times [1,W^*] \times [1,W^*]$ 。

分支定界搜索

直观来说，地理空间中的目标分布并非随机的，一些搜索子空间中更可能包含最优的结果。

我们先定义给定查询 ${\cal X}_q$ 时 $\cal S$ 的距离下界： ${\hat f}({\cal S}|{\cal X}_q) \leq ||g({\cal X}_q)-g({\cal X}_c)||_2, \forall {\cal X}_c \in {\cal S}$ 。直观来看 ${\hat f}({\cal S}|{\cal X}_q)$ 越小说明 $\exists {\cal X}_c \in {\cal S}$ 是 ${\cal X}_q$ 的一个top-N区域的机会越大。

我们之后就要构造出这个 ${\hat f}({\cal S}|{\cal X}_q)$ 。

首先考虑上面所说的这个 ${\cal X}_{\cap} \subset {\cal X}_c \subset {\cal X}_{\cup}, \forall {\cal X}_c \in {\cal S}$ 式子，而因为 $g(·)$ （本文中就是max-pooling）又是个单调增函数，我们可以得到这样的结论： $g({\cal X}_{\cap}) \leq g({\cal X}_c) \leq g({\cal X}_{\cup}), i.e., {\bf v}_{\cap}[k] \leq {\bf v}_c[k] \leq {\bf v}_{\cup}[k],\forall k \in [1,K]$ ，其中 ${\bf v}[k]$ 表示 ${\bf v}$ 的第 $k$ 个维度。

于是我们可以将 ${\cal X}_c$ 与 ${\cal X}_q$ 之间的距离表示成 $\sqrt{\sum_{k\in [1,K]}{({\bf v}_q[k]-{\bf v}_c[k])^2}}$ ，其中这K项中的每一项 $({\bf v}_q[k]-{\bf v}_c[k])^2$ 都能够利用 ${\bf v}_{\cap}[k] \leq {\bf v}_c[k] \leq {\bf v}_{\cup}[k]$ 得到以下的两条界限：
$(i) \quad ({\bf v}_q[k]-{\bf v}_c[k])^2 \geq ({\bf v}_q[k]-{\bf v}_{\cap}[k])^2,\quad {\rm if} \, {\bf v}_{\cap}[k] \geq {\bf v}_q[k] \\ (ii) \quad ({\bf v}_q[k]-{\bf v}_c[k])^2 \geq ({\bf v}_q[k]-{\bf v}_{\cup}[k])^2,\quad {\rm if} \, {\bf v}_{\cup}[k] \leq {\bf v}_q[k]$
我们令满足 ${\bf v}_{\cap}[k] > {\bf v}_q[k]$ 的 $k$ 为 $k_1$ ，满足 ${\bf v}_{\cup}[k] < {\bf v}_q[k]$ 的 $k$ 为 $k_2$ 。于是我们可以得到距离的下界：
${\hat f}({\cal S}|{\cal X}_q)=\sqrt{\sum_{k_1}{{(\bf v}_q[k_1]-{\bf v}_{\cap}[k_1])^2}+\sum_{k_2}{{(\bf v}_q[k_2]-{\bf v}_{\cup}[k_2])^2}}$
注意到当 $t_{min}^*<b_{max}^*$ 或 $r_{min}^*<l_{max}^*$ 时，特征区域 ${\cal X}_{\cap}$ 不存在，所以这种情况下就直接采用 ${\hat f}({\cal S}|{\cal X}_q)=\sqrt{\sum_{k_2}{{(\bf v}_q[k_2]-{\bf v}_{\cup}[k_2])^2}}$ 作为搜寻界限。

下面是对ExactSFRS分支定界搜索算法的说明：

ExactSFRS算法.PNG

算法说明：

初始化（line2-3）：定义空结果集 $\cal F$ ，优先队列 $Q$ 。将初始搜寻空间 ${\cal S}_{\forall}$ 入队列 $Q$ 。
分支步骤（line6-7）：从优先队列 $Q$ 的队首弹出一个搜索空间 $S'$ （弹出的搜索空间的距离最小界限 ${\hat f}({\cal S'}|{\cal X}_q)$ 一定是队列中最小的）。之后，将 ${\cal S}'$ 分成两个不相交的子空间 ${\cal S}_1$ 和 ${\cal S}_2$ ，分的方式是：将 $\bar t,\bar b, \bar l, \bar r$ 中最大的那个区间间隔平分，其余三个间隔不变。
定界步骤（line8-9）：计算 ${\hat f}({\cal S}_1|{\cal X}_q)$ 和 ${\hat f}({\cal S}_2|{\cal X}_q)$ ，之后将它们的值分别与 ${\cal S}_1$ 和 ${\cal S}_2$ 放入队列 $Q$ 中。

重复分支和定界步骤直到 $|{\cal S}'|=1$ ，也就是队首取出的搜索空间只包含1个特征区域（将其表示为 ${\cal X}'$ ），此时一定有 $t_{max}^*=t_{min}^*，b_{max}^*=b_{min}^*，l_{max}^*=l_{min}^*，r_{max}^*=r_{min}^*$ 。且对于此时的 ${\cal S}'$ ，有 ${\cal X}_{\cap}={\cal X}_{\cup}={\cal X}'$ 且 $k_1 \cup k_2=[1,K]$ （这里如果这么说我感觉前面的k1和k2就应该是小于等于或大于等于，而不是小于或大于）。所以有 ${\hat f}({\cal S}'|{\cal X}_q)=||{\bf v}_q-{\bf v}'||_2$ （不等号变等号了）。所以， ${\cal X}'$ 可以作为 ${\cal X}_q$ 的top-N候选区域：（是此时队列里最相似的特征区域）
$||{\bf v}_q-{\bf v}'||_2 \leq {\hat f}({\cal S}|{\cal X}_q) \leq ||{\bf v}_q-{\bf v}_c||_2, \forall {\cal S}\in Q, \forall {\cal X}_c \in {\cal S}$
我们将 ${\cal X}'$ 放入 ${\cal F}$ 中，继续搜索过程，直到找到了 $N$ 个结果。 ${\cal F}$ 中的特征区域就是top-N相似特征区域，可以将它们映射回 $P$ 上的top-N相似区域。

时间复杂度分析

在分支步骤中，分开一个搜寻空间花费 $O(1)$ 级别的时间；在定界步骤中，使用积分直方图计算 ${\bf v}_{\cap}$ 和 ${\bf v}_{\cup}$ ，定界步骤的总复杂度是 $O(K)$ 。

在最坏情况下，搜寻过程需要检查一共 $2|{\cal S}_{\forall}|-1$ 个搜索空间，并且花费 $O({\rm log}|{\cal S}_{\forall}|)$ 级别时间维护 $Q$ ，其中 $|{\cal S}_{\forall}|$ 表示候选特征区域的总数量。因此，总复杂度是 $O(K|{\cal S}_{\forall}|{\rm log}|{\cal S}_{\forall}|)$ 。尽管最坏情况复杂度很高，但ExactSFRS在实验中按经验来说还是很高效的。

SFRS的近似算法

由于在实际的应用中，使用者需要很快的回应，可以忍受准确率的一点下滑，所以这里提出一种叫ApproxSFRS的近似SFRS方法，在只损失一点准确率的情况下提升效率。

ApproxSFRS的策略与ExactSFRS基本相同，唯一的区别在于这里会用一个常数 $M$ 限制 $Q$ 的大小，其中 $M \leq |{\cal S}_{\forall}|$ 。当搜寻过程中 $Q.size>M$ 时，会将 $Q$ 中的最坏搜寻空间（也就是有最大 ${\hat f}({\cal S}|{\cal X}_q)$ 的搜寻空间）丢弃。我们使用最小-最大堆来作为 $Q$ ，这样插入和删除最小或最大值的时间复杂度就是 $O({\rm log}M)$ 。

时间复杂度分析

ApproxSFRS的时间复杂度是 $O(KM{\rm log}M(1+{\rm log}|{\cal S}_{\forall}|-{\rm log}M))$ 。可以根据不同应用需求调节 $M$ 来调节时间复杂度。

6 Experiments

实验设置

数据集

本实验使用三个空间目标数据集，如下图所示。每个POI的属性是分类，表现为一个one-hot向量。US的那个大数据集是为了评估本算法的效率，它是将很多条推特用LDA模型训练，让每条都与一个主题分布向量关联并作为它的属性。

测试数据的产生

为评价方法的有效性，我们使用与生成训练数据类似的方法生成测试数据。具体来说，随机采样2000个区域，包含多于50个作为测试查询的目标，将该集合记为 $D_q$ 。对于一个查询 $R_q \in D$ ，通过向它添加小的噪声和移动创建出一个相似性区域 $R_+$ 作为ground truth。我们创建一个候选区域数据库 $D_c=(D_q/R_q) \cup R_+$ （在 $D_q$ 集合中除掉 $R_q$ ，另外也除掉那些和 $R_q$ 有重叠的），考虑 $D_q$ 中的其它区域作为与 $R_q$ 不相似的区域。我们使用 $R_q$ 从 $D_c$ 中检索它的相似区域。理想情况下 $R_+$ 应该是排在最顶部的。

为评价方法的效率，我们重新使用这2000个随机采样的 $R_q$ 以在 $P$ 上搜寻并记录每种方法的平均运行时间。

基线

评价有效性：将Triplet与下列相似性度量基线方法比较：
SPM，Grid，SVSM

评价效率：将ExactSFRS方法与下列搜寻基线方法比较：
Quad，BruteSFRS

评价指标

HR@10：给出一个查询返回的top-10区域集合 $\cal R$ ，如果 $R_+ \in {\cal R}$ 那么记HR@10=1，否则记HR@10=0。
MRR： ${\rm MRR}=\frac{1}{rank}$ 。其中 $rank$ 表示对于查询 $R_q$ ， $R_+$ 在 $D_c$ 中的排序。我们在实验中汇报的是所有查询的平均MRR值。

Triplet有效性

改变噪声比率

确定移动距离为50m（方向任意），噪声比率改变范围从0.05到0.2。

可以看到Triplet在新加坡和纽约两个数据集上HR@10和MRR两个指标都显著高于基线方法。且通过噪声比率增大后Triplet减小的幅度很小可以看到它对噪声的鲁棒性很强。

改变噪声比率的实验结果.PNG

改变移动距离

固定噪声比率为0.05，改变移动距离从50m到200m。

在新加坡和纽约两个数据集上Triplet依然在两个衡量标准上都是最好的。

另外可以看到当添加较大的移动的时候Triplet的表现会有明显的下降，这是因为大幅度移动目标可能会改变相对位置的形式，这会影响到相似度（因为本模型的相似度本来就把相对位置考虑进去了）。

改变移动距离的实验结果.PNG

消融实验

图中斜杠后面的部分表示从完整的Triplet模型中去除的部分。

RL:基于比率的训练损失，HM：难例挖掘，LF：在CNN中使用大的滤波器作为改进（因为小的滤波器经常应用于图像数据）

可以看出使用大滤波器（LF）和难例挖掘（HM）是对在地理区域上训练triplet网络最重要的。另外结果也表明基于比率的训练损失（RL）能够提升效果。

ExactSFRS和ApproxSFRS的效率

整体效率

下图展现了在三个数据集上找top-1相似区域各方法的平均运行时间，可以看到ExactSFRS显著胜过两种基线方法。

在不同数据集上的运行时长.PNG

可扩展性

相似区域N的变化：
N从1变化到100，可以看到ExactSFRS在N从1到100的情况下在美国数据集上运行时只增加5%。

区域中目标数量的变化：
ExactSFRS方法在处理含有更多目标的查询时反倒会更快。

区域范围大小的变化：
这种变化下ExactSFRS和基线Quad的变化趋势都是随区域增大运行时间增长

效率和准确率的折衷

我们将ApproxSFRS方法中队列最大长度M从1变化到 ${\cal S}_{\forall}$ （ ${\cal S}_{\forall}$ 时其实就是ExactSFRS方法），下图为做top-1相似区域搜寻时平均运行时和误差随M变化的情况，其中“误差”定义为ExactSFRS方法和ApproxSFRS方法所产生出的值的差距。

可以找到 $M=10^3$ 这样一个很好的折衷点。

ApproxSFRS的trade-off.PNG

词汇表

metric learning 度量学习
branch and bound 分支定界
perceive 察觉，感觉
interactively 交互式地
skewed 歪斜的，曲解的
germane 有密切关系的，贴切的
prone to 易于，倾向于
latent 潜在的，隐藏的
exhaustive search 穷举搜索
recursively 递归地

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 211,561评论 6赞 492
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,218评论 3赞 385
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 157,162评论 0赞 348
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,470评论 1赞 283
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,550评论 6赞 385
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,806评论 1赞 290
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,951评论 3赞 407
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,712评论 0赞 266
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,166评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,510评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,643评论 1赞 340
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,306评论 4赞 330
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,930评论 3赞 313
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,745评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,983评论 1赞 266
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,351评论 2赞 360
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,509评论 2赞 348

【文献阅读笔记】2018-KDD-Efficient Similar Region Search with Deep Metric Learning

Abstract

1 Introduction

3 Problem Definition

4 Region Similarity Learning

排序度量学习模型

训练鲁棒的Triplet Network

训练数据的产生

基于比率的训练损失

5 Region Search Algorithm

通过共享计算转化问题

共享计算

问题转化

用于SFRS的提取算法

代表搜索空间

分支定界搜索

时间复杂度分析

SFRS的近似算法

时间复杂度分析

6 Experiments

实验设置

数据集

测试数据的产生

基线

评价指标

Triplet有效性

改变噪声比率

改变移动距离

消融实验

ExactSFRS和ApproxSFRS的效率

整体效率

可扩展性

效率和准确率的折衷

词汇表

推荐阅读更多精彩内容