自学习快速哈希相似度搜索外文翻译资料

英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料

自学习快速哈希相似度搜索

摘要

大规模快速相似度搜索的能力对于许多信息检索（IR）应用是非常重要的。加速相似度搜索的一种有希望的方法是语义散列，其为大量文档设计紧凑二进制代码，使得语义相似的文档被映射到类似的代码（在短的汉明距离内）。虽然一些新出的技术能够知晓的文档生成高质量代码，但是获得先前未见的文档的代码仍然是一个非常具有挑战性的问题。在本文中，我们强调这个问题，并提出一种新的自学习散列（STH）方法语义哈希：我们首先通过无监督学习找到给定语料库中的所有文档的最优l位二进制代码，然后训练l分类器通过监督学习来预测任何查询文档之前未见过的l位代码。我们对三个真实世界文本数据集的实验表明，使用二值化拉普拉斯特征图（LapEg）和线性支持向量机（SVM）的建议方法显着优于最先进的技术。

介绍

相似搜索（也称为最近邻搜索）问题是：给定查询文档，从非常大的文档集合（语料库）找到其最相似的文档。 这对于许多信息检索（IR）[30]应用非常重要，例如近似重复检测，剽窃分析协作过滤，缓存和基于内容的多媒体检索。

近来，随着互联网的快速发展和要处理的数据量的增加，如何进行大规模的快速相似性搜索已成为迫切的研究问题。 一种有希望相似性搜索的的方法是语义哈希，其为大量文档设计紧凑二进制代码，使得语义相似的文档被映射到相似的代码（在短汉明距离内）。 在这样的二进制代码上执行相似性搜索是非常快的，因为：

编码数据被高度压缩，并且因此可以被主存储器加载

可以通过使用位异或运算和计算位数来有效地计算两个二进制码之间的汉明距离：现在的常规PC将能够在几毫秒内完成数百万的汉明距离计算 。

此外，我们通常只需要针对给定查询文档检索少量最相似的文档（即，最近邻），而不是计算其与集合中的所有文档的相似性。 在这种情况下，我们可以简单地将所有散列的文档返回到以查询文档的二进制代码为中心的紧凑汉明球。 例如，假设我们使用4位二进制代码，如果查询文档表示为“0000”，则我们可以只检查这个代码以及在到它的一个汉明距离内的那些代码（即，具有一个位差 与它） - 1000，0100，0010和0001 - 并返回相关联的文档。 还将容易基于它们的全部内容来过滤或重新排序数量非常小的“优秀”文档集合（由语义散列返回），以便花费仅仅稍微额外的时间来进一步提高检索有效性

此外，相似性搜索作为一种基于非参数机器学习方法的基础，k-最近邻（kNN）算法，用于自动文本分类等等。 通过在大规模上实现快速相似性搜索，语义散列使得利用“数据的不合理的有效性”来完成传统上困难的任务是可行的。 例如，研究人员最近在网络上使用数百万个图像作为训练数据在场景完成和场景识别方面取得了巨大的成功

虽然一些新提出的的技术能够为在文献中已知的文件生成高质量的代码，但是获得先前未见的文档的代码仍然是一个非常具有挑战性的问题[42]。 现有的方法具有非常高的计算复杂性或者对数据分布施加了非常严格的限制性假设（见第3.2节）。 在本文中，我们强调这个问题，并提出一种新的自我散列散列（STH）方法进行语义散列。 如图1所示，我们首先通过无监督学习找到给定语料库中所有文档的最优l位二进制代码，然后通过监督学习来训练l个分类器，以预测任何查询文档前面的l-bit代码 。

我们对三个真实世界文本数据集的实验表明，使用二值化拉普拉斯特征映射（LapElg）和线性支持向量机（SVM）提出的方法显着优于最先进的技术，同时保持高运行速度。

本文的其余部分组织如下。 在第2节中，我们回顾了相关工作。 在第3部分，我们详细介绍我们的方法。 在第4节，我们显示实验结果。 在第5节中，我们做出结论。

相关工作

由于其在许多应用中的重要性，已经对快速相似性搜索进行了广泛的研究。 对于低维特征空间，可以使用预构建的空间分区索引结构（例如KD树）或数据分区索引结构（例如R树）有效地执行相似性搜索。 然而，当特征空间的维数较高（比如gt; 10）时，旨在返回精确结果的相似性搜索不能比天真方法（整个集合的线性扫描）更好。 在IR域中，文档通常表示为超过上千个空间的特征向量。 然而，如果结果的完全准确性不是真正必要的，在高维空间中的相似性搜索可以通过使用基于散列的方法而被显着加速，该方法被有目的地设计为在实质上恒定的时间

用于快速相似性搜索的这种基于哈希的方法可以被认为是用于将高维特征向量嵌入到低维汉明空间（长度为l的所有2l二进制串的集合），同时尽可能保留语义的 数据的相似性结构。 与标准降维技术如潜在语义索引（LSI）和位置保留索引（LPI）不同，散列技术将特征向量映射到二进制代码，这是极快的相似性搜索的关键 见第1节）。 获得文本文档的二进制代码的一种可能的方法是通过阈值二值化实数低维向量（从诸如LSI的维度降低技术获得）。 最近提出了对二元化LSI的改进，其直接优化基于汉明距离的目标函数，即拉普拉斯共同杂交（LCH）

保留相似性信息的最着名的散列技术可能是位置敏感散列（LSH）。 LSH简单地使用随机线性投影（随后是随机阈值处理）将在欧几里德空间中接近的数据点映射到类似的代码。 理论上保证随着代码长度增加，两个代码之间的汉明距离将渐近地接近它们相应的数据点之间的欧几里得距离。 然而，由于用于LSH的散列函数的设计是数据无关的，所以LSH在实践中可能导致相当低效（长）的代码

最近提出的几种哈希技术试图通过机器学习找到良好的数据感知哈希函数来克服这个问题。在[34]中，作者提出使用堆叠限制玻尔兹曼机（RBM）[19,20]，并表明它确实能够生成紧凑的二进制代码，以加速文档检索。研究人员还尝试了相似性敏感编码（SSC）[38]和宽容散列（FgH）[2]的增强方法 - 他们首先训练AdaBoost [35]分类器通过类似的项目作为积极的例子（非相似项目对作为SCC中的否定示例），然后将给定文档上的所有（决策树桩）弱学习器的输出作为其二进制代码。在文献[44]中，当应用于包含数千万个图像的数据库时，堆叠RBM和增强SSC被发现工作明显比LSH更好和更快。在[48]中，提出了一种称为频谱散列（SpH）的新技术。它已经证明了在LSH，堆叠RBM和增强SSC方面在找到良好相似项目所需的位数方面的显着改进。在SpH的第一步和我们的STH方法的无监督学习阶段之间有一些相似之处，因为它们都与光谱图分割有关。然而，我们使用不同的光谱方法，并采取不同的方式来解决熵最大化标准（见第3.1节）。更重要的是，为了处理查询文档，SpH必须假设数据均匀分布在超矩形中，这显然是非常有限的。相比之下，我们提出的STH方法可以与任何数据分布一起工作，并且更灵活（参见第3.2节）。我们的实验结果证实了STH对SpH的优越性（见第4节）。

一个有点相关，但不同的研究方向是使用机器学习的散列表示。 这种技术的目的是加速复杂的学习算法，而不是相似性搜索。 我们的工作基本上是相反的

方法

提出的自我教学散列（STH）方法的语义散列是一个通用的学习框架，包括两个不同的阶段，如图1所示。我们称之为“自学”的方法，因为散列函数是学习的数据来自远在前一阶段自动标记

第一步：二进制码的无监督学习

给定被表示为m维向量的n个文档的集合。 令X表示条件文档矩阵：。 假设期望的码长度为l比特。 我们使用表示文档向量xi的二进制代码，其中yi的第p个元素，即，如果代码的第p位为 on，否则为-1。 设Y表示第i行是第i个文档的代码的ntimes;1矩阵，即

“好”语义散列应该保持相似性以确保有效性。 也就是说，语义上类似的文档应当被映射到短汉明距离内的类似代码

与旨在保持所有文档对的全局相似性结构的现有方法（诸如SpH）不同，我们关注每个文档的局部相似性结构，即k-最近邻。 由于IR应用程序通常强调给定查询文档的少量最相似的文档，保留全局相似性结构不仅不必要，而且可能对于我们的问题是次优的。 因此，使用余弦相似性，我们构造我们的ntimes;n局部相似性矩阵W as

其中表示文档x的k个最近邻的集合。 换句话说，W是给定语料库的k-最近邻图的邻接矩阵[3]。 关注这种局部相似性结构而不是全局相似性结构的副产物是W变成稀疏矩阵。 这不仅导致低得多的存储开销，而且显着降低了后续操作的计算复杂性。 此外，我们引入对角ntimes;n矩阵D，其条目由给出。 矩阵D提供了文档重要性的自然度量：的值越大，文档xi越重要，因为文档xi的邻居与它强烈相关

两个二进制码yi和yj（对应于文档xi和xj）之间的汉明距离由它们之间不同的位数给出，其可以被计算为。 为了满足相似性保存标准，我们寻求最小化加权平均汉明距离（如在SpH中）

因为如果两个相似的文档被映射得相隔得很远，则会招致重罚。 在一些简单的数学变换之后，上述目标函数可以以矩阵形式重写为，其中L = D-W是图形拉普拉斯，Tr（·）是矩阵的迹

我们发现上述目标函数（2）实际上是公知的流形学习算法，拉普拉斯特征映射（LapEig），除了LapEig不具有约束。 因此，如果我们放松这个离散性条件，但只保持相似性保持要求，我们可以通过求解以下LapEig问题来获得最优的一维实数值向量来表示每个文档xi：

其中给出加权平均汉明距离的实际松弛，并且这两个约束防止崩溃成小于l维的子空间。 该优化问题的解由下式给出：，其是对应于以下广义特征值问题（除了平凡特征值0）的最小特征值的l个特征向量：

上述LapEig公式（3）可以看起来类似于SpH的第一步骤。 这是因为SpH由光谱图分割方法比率切割激励，而LapEig与另一光谱图分割方法归一化切割紧密相关。 许多独立研究表明，归一化切割具有比切割更好的理论性能和经验性能

现在，我们将上述l维实数值向量通过阈值处理转换为二进制码：如果的第p个元素大于指定阈值，则= 1（即，第i个码的第p位 上）; 否则，= -1（即，第i个代码的第p位关闭）。

“好的”语义散列也应该是熵最大化以确保效率，[2]指出。根据信息理论：最大熵的通过具有均匀的概率分布来获得源字母表。如果语料库上的代码的熵较小，则意味着文档仅被映射到少量代码（散列箱），从而使得散列表效率低。为了满足这个熵最大化标准，我们设置二值化阈值为的中值。以这种方式，第p位将为半个语料库打开，而关闭另一半。此外，作为特征向量由LapEig给出的彼此正交，不同的位是不相关的。因此，该阈值方法给予每个不同的二进制代码在文档集合中发生的大致相等的概率，从而实现对散列表的最佳利用

步骤二：哈希函数的监督学习

将给定语料库中的所有文档映射为二进制代码并不能完全解决语义哈希的问题，因为我们还需要知道如何获得查询文档的二进制代码，即以前看不到的新文档。这个问题，在流形学习中被称为样本外扩展，通常使用Nystrom方法来解决。然而，计算新文档的Nystrom扩展与在语料库（可能包含数百万个文档）上的详尽的相似性搜索一样在计算上是昂贵的，这使得其对于语义散列是不切实际的。在LPI中，通过将线性函数近似于LapEig的嵌入来扩展LapEig以处理新样本。然而，LPI的计算复杂度非常高，因为它的学习算法包括两个大密度矩阵的特征分解。如果给定的训练语料库大，则不可能应用LPI。在SpH 中，通过利用关于图形拉普拉斯特征向量到汇聚的拉普拉斯 特征函数的收敛的最新结果来处理新样本。它可以实现快速学习和快速预测，但是它依赖于非常限制性的假设，即数据均匀地分布在超矩形中。

克服上述技术的局限性，本文提出了一种通过将其作为监督学习问题来计算查询文档的二进制代码的新方法：我们认为每个位 将文档xi的二进制代码作为该文档的二进制类标签（类“on”或类“off”），并且在给定语料库上训练二进制分类器 已经通过上述二值化LapEig方法“标记”，则我们可以使用学习的二进制分类器以预测l位二进制码对任何查询文档x。 如前面部分所述，不同的位是不相关的。 因此，在二进制分类器，并且它们也可以独立地训练.

在本文中，我们选择使用支持向量机（SVM）算法来训练这些二进制分类器。 SVM在其最简单的形式，线性SVM始终为文本分类任务提供最先进的性能。 给定文档以及它们对于第p个位的自学习二进制标签可以通过求解以下二次优化问题来训练对应的线性SVM:

在这里使用SVM分类器的一个显着的优点是，如果必要的话，我们可以很容易地实现非线性映射，通过插入非线性内核，虽然我们没有在这篇文章中探讨这种潜力。

3.3算法总结

我们将上面提出的两阶段方法称为自学习哈希（STH）。 在本文中，我们选择二元化LapEig用于无监督学习阶段和线性SVM用于监督学习阶段，但是显然可以使用其他机器学习算法

给定语料库的STH的学习过程可以总结如下。

二进制代码的无监督学习：

bull;构造给定语料库的k-最近邻图;

bull;通过LapEig将文档嵌入到l维空间中，以获得每个文档的l维实值向量

通过在其中间点处对上述向量进行阈值处理来获得每个文档的1位二进制代码，然后将每个位视为该文档的二进制类标签

2.监督学习哈希函数：

基于给定的语料库训练SVM分类器，该语料库已经如上所述被“标记”

令s表示每个文档的非零特征的平均数。在第一阶段，构建k-最近邻图使用选择算法取O（）时间，使用t迭代的Lanczos算法解析LapEig问题需要O（）时间（t的值通常相当小），并且基于中值的二值化再次使用选择算法来取O（ln）时间。在第二阶段，由于大规模优化的最新进展，l个线性SVM分类器中的每一个可以在O（sn）时间或甚至更少训练，因此所有训练可以在O（lsn）时间完成。 l的值和k的值都可以被认为是小常数，因为通常期望短的码长度并且仅需要几个最近的邻居。例如，在

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[141327]，资料为PDF文档或Word文档，PDF文档可免费转换为Word