英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料
用于大规模视觉搜索的多特征内核哈希
刘翔龙a,*，何俊峰b,c,博朗a
a北京航空航天大学软件开发环境国家重点实验室，北京100191，中国
b美国纽约哥伦比亚大学电气工程系10027，美国
c脸谱网，1601柳树路，门罗公园，加州94025，美国
文章信息
文章历史：
2012年12月26日收到
2013年7月1日以订正形式收到
2013年8月27日接受
2013年9月7日在线提供
关键词：
局部敏感哈希
多特征
紧凑哈希
多核
摘要
最近的哈希因其理论保证和实际成功而在大规模视觉搜索中变得很有吸引力。但是，大多数最先进的哈希方法只能使用单个特征类型来学习哈希函数。图像检索，聚类和其他领域的相关研究证明了融合多个特征的优势。在本文中，我们提出了一种新的多特征内核哈希框架，其中哈希函数被学习以保持与对应于不同特征的线性组合的多个内核的某些相似性。该框架不仅与一般类型的数据和不同类型的由不同视觉特征指示的相似性兼容，而且对于有监督和无监督情景都是普遍的。 我们提出高效的交替优化算法来学习哈希函数和最优内核组合。在三个大规模数据集CIFAR-10，NUS-WIDE和a-TRECVID上的实验结果表明，所提出的方法可以实现比最先进的方法更高的精度和效率。
＆2013 Elsevier Ltd.保留所有权利
- 介绍
近年来，视觉数据爆炸式增长，给可扩展视觉搜索带来了巨大挑战。像KD-Tree这样的巨大解决方案[1]，基于哈希的近似最近邻（ANN）搜索引起了很多关注，这是因为它在像姿势估计[2]，图像检索[3]，主动学习[4]等等这样的许多应用中具有很好的性能。局部敏感哈希（LSH）[5]通过引入名为“局部敏感度”的重要概念，将类似数据点散列成类似代码，开创了基于哈希的人工神经网络研究。使用嵌入式哈希码，搜索可以在恒定或次线性时间内完成。这个想法之后，Charikar[6]提出了基于随机投影的LSH，该算法能够高效地生成哈希位并保留余弦相似性。Datar等人[7]进一步研究了基于p-稳定分布的LSH的相似性度量，如lp-norm(pisin;(0,2])。在过去的几年中，已经提出了许多熟悉的哈希方法来解决在诸如无监督的各种情况下的视觉搜索问题[3,8]，（半）监督[9–11]，核化[12]，多探针[13]，和多位[14]。
尽管在基于哈希的视觉搜索方面有上述进展，但大多数现有技术的哈希方法都受限于哈希函数通常仅从单个特征学习的限制。但是，在实践中，对于相同的视觉对象存在多个表示：图像可以用来描述各种不同的视觉描述符，如SIFT[15]，GIST[16]，等等。在许多应用中已经证明，自适应地组合一组不同的和互补的特征比使用单一特征具有更好的性能。例如，基于内容的图像检索系统通过融合多种特征如颜色和纹理[17–19]来显着提高性能。特征组合在图像分类[20]和聚类[21]等其他领域也非常有用。
现有的多特征哈希方法[17,22] 通过融合不同的特征也取得了令人鼓舞的业绩增长。但是，要处理多个特征，这些方法要么将所有特征均等地预先拼接为一个特征，要么将各个特征类型的线性输出进行后合并。一方面，平等对待所有特征并不能充分利用每种特征类型的相关性和重要性。众所周知，不同的特征可能表现出不平衡和不同的信息，其中一些特征在不同的相似性度量[22]下可以相互补充。另一方面，特征拼接扩展了特征维度，因此在训练和搜索阶段带来了昂贵的计算（参见详细讨论第6.2节）。因此，将这些方法应用于具有许多高维视觉特征的大规模图像检索是不切实际的。
在本文中，我们提出了一种新的哈希框架来学习信息哈希函数，这些哈希函数结合了多个特征并在一定的相似性度量下保留了相邻关系。在这个框架中，不同的特征是非线性的，但隐式映射并连接到高维空间中，然后具有多个特征的哈希函数可以被表示为使用线性组合多重内核。内核技巧通常更加自然，以衡量一般数据类型的相似性，其中底层数据嵌入高维空间并不明确。许多哈希方法受益于使用特定于域的内核函数[9,12,23]。在我们的公式中，对应于不同特征的一组内核被自动加权并且作为一个线性组合。这与计算机视觉中被称为多核学习（MKL）[24]的流行方法非常相似，该方法能够学习更好地再现内核空间并提高性能。
由于内核表示，相应内核空间中的多个嵌入特征的组合不会带来比单个特征类型更多的计算。鉴于数据之间的相似性，我们分别使用特征值分解和二次规划有效地交替地优化哈希函数和核函数组合。值得强调的是本文的主要贡献：
1.本文将多特征哈希算法作为一个相似性保留问题，应用于一个通用框架中的有监督和无监督两种情况。通过将所有特征映射到核空间中并串联在核空间中，每个学习到的哈希函数被形成为关于多个核的组合的线性投影。该公式与具有任何内核函数的一般类型的数据兼容，并有助于存档快速计算。
2.对于有监督场景，该方法利用特征间的互补性，结合不同的特征来保持语义相似性。在没有任何监督信息的情况下，还可以通过恢复不同特征的不同相似性背后的低秩相似性来学习鉴别哈希函数。
3.针对这两种情况，我们分别提出了一种交替优化的方法来有效地学习哈希函数和核组合系数。
4.大量实验表明，与现有的压缩哈希算法相比，该算法具有更好的性能和效率(计算速度和存储效率通常小于64 )。
请注意，整个文件延伸到以前的会议刊物上[25] 并进一步探讨算法泛化（监督和非监督的情况），详细分析算法性质（与其他算法的联系，计算复杂性和参数敏感性）以及放大的实验结果。本文的其余部分安排如下：我们在第2节简要回顾了相关工作。第3节介绍了我们的多特征内核哈希的基本思想和制定。然后进入第4节和第5节我们将分别介绍基于给定公式的监督和无监督哈希算法。在第6节我们的方法演变计算问题进行了分析。第7节描述我们的评估设置和实验结果。最后，我们总结第8节。
- 相关工作
在过去的几年中，哈希已经成为解决像大规模视觉搜索这样的许多应用中的近似最近邻搜索的有前途的方法。局部敏感哈希（LSH）[5] 因为著名的开创性工作将类似的数据在特定的度量下嵌入到具有高概率的汉明空间中的类似的二进制码中。通过这些二进制码，可以构建多个哈希表来完成子线性搜索。由于投影向量是在LSH中随机生成的，所以很多以下研究致力于在不同场景下学习紧凑投影，包括用于一般数据类型的无监督哈希[3,8,12]，（半）监督哈希[10,11]，和内核的非线性哈希[9,12,23,26]。
频谱哈希（SH）[3] 试图将数据编码成紧凑的二进制码，保持汉明空间的原始相似性。它将哈希问题作为一个图分区问题来制定，其中包含良好二进制码的基本要求：位平衡和不相关
这里，Sij是第i和第j个样本之间的相似性，并且N和P分别是每个样本的数据样本和比特的数量。Yi，二进制矩阵Y的第i列，是第i个样本的哈希码。
与平衡图划分问题等价的离散约束问题是NP - hard问题。然而，在放宽约束后，它变成了一个图拉普拉斯矩阵的特征分解问题，可以有效地求解。对于一个新的样本，SH依赖于未知分布假设，这在现实世界中可能是不正确的。此外，它的数据相似性严格地定义在原始特征空间中，限制了它的能力。为了解决这些问题，何等[12]提出了一种最佳内核哈希(OKH )，它基于内核明确定义哈希函数。在它们的公式中，没有数据分布假设，并且所学习的哈希函数可以直接应用于泛型类型的新输入样本。
在许多视觉问题中，多特征融合已被证明是非常有用的[18，20]。但是除了[22]和[17]之外，没有太多的研究结合了多种特征。这两种方法都是基于SH的多特征哈希问题。在[22]中，哈希输出是不同源上所有线性哈希函数的凸输出组合，而[17]将所有特征串联为一个，并使用所学习的哈希超平面来投影它。特征连接导致昂贵的计算成本和对各种数据类型和相似性度量的不良通用性。
另一项相关工作是最近提出的多核学习[27]。它结合了多个核，对应于不同的相似性或来自不同来源的信息，而不是使用单个核，并试图通过不同的学习方法找到哪种核最有效。在先前的研究中，已经研究了几种组合方式，包括线性组合、非线性组合和数据相关组合[24]。加权线性组合是最常用的一种方法，其中核函数由满足圆锥或凸约束的核权重线性参数化。在分类[27 ]和域名转让[ 28 ]等几个领域的应用表明了它的成功。在这方面，最接近我们的工作是[29]。它直接将基于距离的哈希算法扩展到核化形式，然后结合多核学习选择最优核，这自然涉及多个特征。
- 多特征核哈希
我们提出的方法的关键思想是利用一组不同的特征及其相似性。这可以被表述为具有与多个视觉特征(图1)相对应的多个内核的最优组合的相似性保持哈希框架证明了所提出的框架。在本节中，我们将首先给出基本的符号，然后给出具有多个特征的通用哈希框架。
3.1注释
本文给出了一组具有M个视觉特征的N个训练样本。第n个样本的第m个特征(dm维度)可以表示为Xn(m)isin;Rdmtimes;1。然后X(m)=[X1(m)，X2(m)，hellip; ，XN(m)]isin;Rdmtimes;N是所有训练数据的第m个特征矩阵。
3.2哈希函数
与以往的核化方法不同，本文通过定义多特征映射函数phi;(·)
将哈希码隐含地与每个视觉特征对应的一系列嵌入函数phi;m(·)相关。它由M个独立的嵌入特征phi;m(Xi(m))被mu;m1/2加权而成。稍后我们将展示它将数据点映射到由不同特征上的核的凸组合定义的空间中。利用嵌入函数phi;(·)，定义了基于线性投影的第p哈希函数
因此，第i个样本的第p个代码将是Ypi=hp(Xi)。
核空间中的超平面向量Vp可以表示为嵌入在相应核空间[9，12，23]中的R个界标Zr的组合。
这里W是Rtimes;P的权重矩阵，并且界标可以是通过聚类[8]或随机采样[12]获得的聚类中心。
对于每个功能，让K(m)表示其对应的内核嵌入函数phi;m(·)，这就意味着Kij(m)=phi;m(Xi(m))Tphi;m(Xj(m))。然后，
因此，K=mu;mK(m)，即phi;(·)实际上为每个特征定义了一个从核线性组合的核。则第i个数据的代码Yi可以以内核形式重写:
其中Ki是R个界标和N个样本之间的Rtimes;N阶核矩阵KRtimes;N的第i列，以及b=[b1,b2,hellip;,bp]。
3.3目标函数
为了学习P哈希函数｛h1,hellip;,hp｝，我们给出了一个类似于[3]和[12]的公式。学习所有训练数据的哈希码Y(Ptimes;N矩阵)以保持第i点和第j点之间的一定相似性Sij(S是稀疏矩阵)，满足平衡和不相关的约束。
我们给出了多特征哈希框架的目标函数
在Yiisin;｛-1，1｝p：上有平衡和不相关的约束，在mu;：1Tmu;=1，mu;gt;=0上有凸约束。
该公式通过优化权重矩阵W和核组合权重mu;，强制学习的哈希函数保持给定的相似性S。虽然在问题7中，每个phi;(Xi)由phi;m(Xi(m))串联而成，但嵌入核空间后的最终尺寸仅为R，通常为因此，与现有方法[17，22]相比，计算将大大减少，现有方法将多个原始特征连接为一个(参见第6.2节中的复杂性讨论)。
- 多特征监督哈希
对于有监督的情况，通过
可以容易地获得相似度矩阵S，其中sigma;是根据数据估计的缩放参数，而表示具有相同标签的x的k最近邻集。则具有(7)中的目标函数的多特征核哈希可以被公式化为
利用拉普拉斯矩阵L=diag(S1)-S，将目标函数表示为
在实践中，为了考虑适当的数据缩放[ 22 ]，可以对图拉普拉斯矩阵进行归一化。相似性矩阵由D-1/2SD-1/2归一化，
全文共18619字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[11299]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
