英语原文共 14 页，剩余内容已隐藏，支付完成后下载完整资料
基于乘积量化的邻近搜索算法
摘要
我们提出了一个基于乘积量化的近似最近邻搜索方法，分解成低维子空间的笛卡尔乘积空间，分别量化每个子空间。一个矢量由和量化索引对应的短码代表。从他们的代码中，可以有效地估计2个向量之间的欧几里得距离。我们的方法有一个有利的非对称的版本，在一个矢量和一个代码之间的估计距离计算。我们的方法是用来有效地搜索最近的邻居，特别是在与一个倒置的文件系统的组合。实验进行筛选，依据图像描述符表现出优秀的搜索精度优于三个最先进的方法。我们的方法的可扩展性经过二十亿个向量数据集的验证。
HAL是一个为科学研究文献的寄存和传播的多学科开放存取档案，无论他们是否被出版。这些文件可能来自法国或国外的教学和研究机构，或来自公共或私人研究中心。
这个想法是把空间分解一个低维子空间的笛卡尔积并且分别来量化每个子空间。
一个由它的子空间量化指数组成的短码代表了一个矢量。两个矢量间的欧几里得距离能够从它们的代码中有效的估计出来。非对称版本增加了精度，因为它计算的是矢量和代码之间的近似距离。
实验结果表明，我们的方法有效地搜索最近的邻居，特别是在与一个倒置的文件系统相结合。结果SIFT和GIST图像描述符表现出优秀的搜索精度优于三个国家的最先进的方法。我们的方法的可扩展性进行验证的数据集的二十亿个向量。
索引词——高维索引，图像索引，非常大的数据库，近似搜索。
介绍
计算欧几里得高维向量之间的距离在许多应用程序中是一项基本要求。特别是用在最邻近搜索中。最近邻搜索天生就是昂贵由于维度的诅咒。专注于D维欧几里得空间RD，问题是在n个向量有限集yisin;RD找到元素NN（x），最小化到查询向量xisin;RD的距离
|
NN(x) = arg min d(x; y) |
(1) |
yisin;Y
一些多维的索引方法，例如流行的KD树或者其他分支界限法都是被提出来减少搜索时间的。但是，对于高维度来说这些方法没有强力详尽的距离计算有效，它的复杂度为O(nD)。
有大量的关于算法的文献，通过最邻近搜索克服了这个问题。这些算法的共同关键思想是发现最邻近算法有高概率的唯一，而不是概率1。大部分的努力一直致力于欧几里得距离,尽管最近提出了归纳其他指标。在这篇论文里，我们考虑到欧几里得距离，这与许多应用程序有关。在这种情况下，一个最流行的ANN算法是欧几里得位置敏感哈希算法，提供了理论保证搜索质量有限的假设。它已经成功地用于局部描述符和3 d对象索引。然而,对于真实数据,激光冲徊化优于启发式方法,利用向量的分布。这些方法包括随机KD-trees和分层的k - means,两者都是在FLANN选择算法中实现的。
相比基于ANN算法通常是搜索质量和效率之间的权衡。然而,这种权衡的内存需求没有考虑索引结构。对于E2LSH,内存使用甚至可能高于原来的向量。此外,E2LSH和FLANN需要执行最后的评估步骤基于精确L2距离,这需要索引向量存储在主内存访问速度是很重要的。这个约束严重限制向量的个数,可以由这些算法处理。直到最近,研究人员想出了方法限制了内存的使用。这是一个关键的标准问题涉及大量数据,即在大规模场景识别[17],数百万到数十亿的图像必须被索引。在[17],Terrible等人代表一个图像由一个全球要点描述符[18]这是映射到一个简短的二进制代码。当没有监督,这种映射是后天习得的,社区在嵌入空间中定义的汉明距离反映了社区的欧几里得空间的原始特性。欧几里得的搜索最近的邻居是近似搜索最近的邻居之间的汉明距离码。在[19],光谱散列（SH）显示outper-form生成的二进制代码限制玻尔兹曼机[17],增加和激光冲徊化。同样,汉明的嵌入方法Jegou et al。[20],[21]使用二进制签名来细化量化筛选或要点描述符bag-of-features图片搜索框架。
在本文中,我们使用量化构造短码。目标是使用vector-to-centroid距离估计距离,即。,查询向量不是量化,编码向量分配给数据库。这减少了quan-tization随后噪音和提高搜索质量。为了获得精确的距离,量化误差必须是有限的。因此,总数k的重心应该足够大,如,264 k = 264位代码。这就引发了几个问题如何学习速率和分配一个向量。首先,学习量化器所需样品的数量是巨大的,例如,几次k。第二,算法的复杂性本身是禁止的。最后,地球上可用的计算机内存数量是不够的存储表示质心的浮点值。
等级k均值改善了学习阶段的效率和相应的分配程序。然而，前述的限制仍然适用，特别是关于内存使用和学习集的大小。另一种可能性是标量量化，但他们在内存和重构误差之间的错误方面提供很少的量化误差特性。格的量化为统一的矢量分布提供更好的量化性能，但这种情况很少被真实的世界矢量所满意。在实践中，这些量化在索引任务中比k—均值差更难令人满意。在本文中，我们专注于产品的量化。据我们所知，这种半结构化的量化器从未在任何的最近邻搜索方法考虑。
我们方法的优点是双重的。首先，可能的距离的数量明显比汉明码嵌入技术高，因为用在这技术上的汉明码空间只支持很少的直接距离。其次，作为副产品的方法，我们得到了预期的平方距离的估计，这是需要“半径搜索或使用洛的距离比准则。在[ 20 ]，[ 17 ]，[ 19 ]使用的空间的动机是有效地计算距离。注意，有一个计算汉明距离的最快的方法是使用表查找。我们的方法是使用一个导致可比效率的类似查表数。所有代码的查询向量的一个详尽的比较是望而却步非常大的数据集。因此，我们引入一种改进的倒排文件结构，以快速访问最相关的向量。粗量化来实现这个倒排文件结构，其中对应于一个群集（索引）的向量被存储在相关联的列表中。列表中的向量用短码来表示，通过我们的产品量化计算，这里使用的是编码相对于聚类中心的残差向量。我们的方法的价值被两种向量所证实，即本地的SIFT描述符和全球的GIFT描述符。与最先进的国家相比，我们的方法优于现有技术，特别是光谱散列[ 19 ]，海明嵌入[ 20 ] [ 9 ]和FLANN。我们的论文组织如下。第二部分介绍了量化的符号，以及由我们的方法使用产品的量化。第三节介绍了我们的方法，神经网络搜索和第四节介绍的结构，以避免详尽的搜索。在第五部分给出我们的方法的参数的评价及与艺术的状态的比较。
背景
有大量的关于适量量化的文献，这里我们限制演示文稿中所用的符号和概念的其他部分。
- 矢量量化
量化是一个破坏性的过程，是信息理论[ 24 ]进行了广泛的研究。其目的是减少表示空间的基数，特别是当输入数据的实际值。正式地，一个量化器是一个函数q，它映射到一个D维向量xisin;R^D到另一个向量q(x)isin;C={ci;iisin;T}，索引集T是假定为有限的：T=0，1hellip;hellip;k-1。生殖词ci称为质心，再现值的集合是大小K的码本。再现值C的集合是大小K的码本。
映射到给定索引i矢量的集合Vi被称为（Voronoi图）细胞，并将其定义为：
(2)
量化器的k个细胞形成的分区。根据定义，所有位于同一单元上载体用相同的质心词重建。一个量化器的质量通常是由输入矢量x和其再生值之间的均方误差（MSE）测量:
(3)
其中的d(x,y)是x和y之间的欧几里德距离。其中，p（x）是随机变量X的分布函数。为了量化为最优，它必须满足被称为劳埃德最优两个属性条件。首先，向量x必须量化到其最近的代码簿的质心，在欧几里德距离:
(4)
其结果是，该细胞是由超平面分隔。第二劳埃德条件是，重建值必须趴在载体的期望Voronoi单元：
(5)
劳埃德量化器，其对应于k均值聚类算法，通过迭代地分配设定为质心，并重新估计从分配矢量这些质心训练的矢量找到近似最优码簿。在下面，我们假定两个劳埃德条件成立，因为我们使用k均值学习量化。但是请注意，该k-均值并不只发现在量化误差方面局部最优。
这将在下文中使用的另一种量的平均值的平方失真（Q; CI）由相应的重构的小区的Vi的矢量时所获得心词。通过PI表示= P Q（x）= CI的概率的矢量分配给形心词。
- 乘积量化
让我们考虑一个128维的矢量，例如SIFT描述符。一个产生64位代码的量化器，这就是说，每个组成部分“只有”0.5位，包含k=264 矩心。因此，使用劳埃德算法或者HKM算法是不可能的，因为样本需要的数量和学习量化器的复杂度是k的好几倍。
产品量化是解决有效的解决方案这些问题。它是在信源编码的常用技术，它允许选择元件的数量来共同量化（例如，组24的组件可以使用强大的蚂蟥格量化）。输入向量x被分成m个不同的子向量uj，1lt;=jlt;=m,子向量被使用m个不同的量化器分别量化，一个给出的向量x因此被映射成如下：
|
m(x) ; |
其中qj是一个和第j个子向量相关的低复杂度的量化器。
一个乘积量化器的再现值定义为乘积索引集T=T1times;T2hellip;hellip;times;Tm.码书因此被定义为笛卡尔乘积：
C=C1times;C2times;hellip;hellip;times;Cm
并且这个集合的质心是m个子量化器的质心的级联。从现在起，我们假设所有的子量化器有同样的有限的再现值K*。这样，总的质心数量给出：
K=(k*)m
注意特殊情况m=D时候，向量x的组成部分全都分别被量化。然后乘积量化器变成了标量量化器，其中每个组成本分的量化方法可能都不一样。
一个产品量化的强度，以产生一个大集从几个小的形心：那些与子量化器相关联。当使用劳埃德算法学习子量化器时候，在有限矢量的号码被使用，但该码本是，在一定程度，仍适于数据分布来表示。
如在本款以后示出，使用估计D或D导致低估，平均而言，描述符之间的距离。图3示出查询1000的SIFT特征矢量的数据集的SIFT描述时得到的距离。它比较反对用公式计算的12和13可以清楚地看出这些距离估计偏差估计真实距离。勿庸置疑，对称的版本是该偏差更为敏感。
论：图4示出了真实距离和由等式13和25已经在一个大组SIFT描述符测量估计的那些之间的差的概率分布函数。由式13的距离估计的偏置校正的版本显著降低。然而，我们观察到校正偏置引线，在这种情况下，给估计，这是在统计的COM纹现象的较高方差。此外，对于最近的邻居，校正项可能是更高。
非穷尽搜索
A.粗糙量化器，本地定义的乘积量化
类似于“视频谷歌”的方法[26]，一个代码簿是利用k均值教训，产生量化QC，称为在下面的粗量化。为SIFT描述符，与QC相关联的质心的数量K0通常为K0= 1000至K0= 1000 000相比，在第三部分中使用的产品量化因此小。除了粗量化，我们采用类似于在[20]，即矢量的描述是通过与产物量化而获得的代码精制提出的策略。然而，为了考虑到由粗量化所提供的信息，即，与一个矢量y相关联的质心QC（y）时，该产品量化QP用于编码残差矢量
该产品量化在一组从学习集收集残差矢量教训。虽然向量量化由粗量化不同的索引，将所得残余矢量用来学习一独特的产品量化。我们假定，当剩余的分布边缘在所有Voronoi单元的相同产品量化是准确的。这可能使劣质的结果，包括学习和使用每个Voronoi单元一个鲜明的产品量化的方法。然而，这将是计算昂贵的，并且需要存储K0产物量化码本，即，K0杀敌浮点值，这将是存储器难治为K0的共同值。
B.索引结构
我们使用粗量化来实现倒置的文件结构列表L1的数组：：：Lk0。 QC（Y）= CIG：如果Y是矢量数据集索引，该列表与李QC存储集风云2 Y的重心词相关联。在倒排列表李，对应于y一个条目包含一个向量标识符和被编码的残留QP（R（Y））：
|
field |
length (bits) |
|
identifier |
8–32 |
|
code |
mdlog2 k e |
标识符字段是的开销由于倒文件结构。取决于载体的性质，要被存储，标识符不一定是唯一的。例如，为了描述通过局部描述符的图像，图像识别符可以取代向量标识符，即，相同的图象的所有矢量具有相同的标识符。因此，一个20位字段足以从一百万的数据集识别图像。此存储器成本可以进一步使用索引压缩[27]，[28]，这可以减少该标识符存储到约8个位，这取决于参数2的平均成本可以降低。请注意，某些几何信息也可以在该条目被插入，如在[20]和[27]中提出。
- 搜索算法
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[30595]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
