英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料
摘要
近年来，基于哈希的近似近邻搜索以其计算量小、检索速度快等优点，在大数据应用领域引起了广泛关注。在文献中，现有的哈希算法大多是集中式的。然而，在许多大型应用程序中，数据通常以分布式的方式存储或收集。在这种情况下，集中式哈希方法不适合作为哈希学习函数。在本文中，我们考虑了分布式学习的哈希问题。我们提出了一种新的分布式图哈希模型，该模型基于网络上分布在多个代理上的数据来学习有效的哈希函数。图哈希模型涉及一个图矩阵，其中包含了原始空间中的相似信息。我们证明了该分布式哈希模型中的图矩阵可以分解成多个局部图矩阵，每个局部图矩阵可以由一个特定的代理独立构造，通信和计算成本适中。然后，分布式哈希模型的整体目标函数可以表示为多个代理的局部目标函数的和，哈希问题可以表示为一个非凸约束的分布式优化问题。为了便于求解，将非凸约束分布优化问题转化为等价的双凸分布优化问题。在此基础上，提出了两种基于交替方向乘子法思想的分布式求解方法。结果表明，所提出的两种算法都具有适度的通信复杂度和计算复杂度，并且都是可扩展的。通过对基准数据集的实验验证了该方法的有效性。
关键词：交替方向乘子法（ADMM）；分布式哈希；图哈希；大规模图像检索；哈希学习（LH）
第1章 绪论
基于哈希的近似近邻搜索在信息检索、图像搜索、机器学习、计算机视觉等领域得到了广泛的关注[1]-[13]。哈希的主要思想是将高维数据点编码成压缩的二值码，二值码应保持相似性。换句话说，哈希技术将有共性的数据点映射到相邻的二进制哈希码上。通过哈希，最近邻搜索可以在一个恒定的时间复杂度内完成，这使得在存储和计算速度上都有很大的效率提高。
现有的哈希方法主要分为两类：1）数据无关型和2）数据相关型。数据无关的哈希方法不使用任何数据信息来获取哈希函数。局部敏感哈希[14]是最著名的数据无关哈希方法之一，它根据随机投影生成哈希函数。近年来，越来越多的研究集中在数据相关的哈希上，因为它可以有效地将大量的数据点映射到非常短的紧凑的二进制码上。代表性的方法有谱哈希化[4]、球面哈希化[21]、迭代量化（ITQ）[3]、结构敏感哈希化[51]、自适应二进制量化（ABQ）[17]，以及最近提出的一种解决一般二进制代码学习问题的快速优化方法DPLM[11]。与数据无关的哈希方法不同，数据相关的哈希方法是使用数据来学习二进制代码和哈希函数，因此也称为哈希学习（Learning to Hash，LH）方法[25]。
哈希学习方法主要有两种：1）无监督哈希化[3]、[4]、[15]、[16]、[18]、[20]、[27]、[28]、[51]；2）监督哈希化[22]、[24]、[26]、[32]、[35]、[38]。这两种类型的主要区别在于数据的标签信息是否可用于学习哈希函数。一般情况下，监督哈希能更好地保持原始空间中的语义相似性，并证明了它比非监督哈希具有更好的准确性。虽然监督哈希法有很好的性能，但是这种方法有一个根本的缺点，那就是它需要监督标签。在许多实际的应用中，获取语义标签通常是非常昂贵的，甚至是不可能的，因此在这些情况下，只能执行无监督的哈希。因此，在本文中，我们关注无监督哈希。
在无监督的哈希方法中，在学习算法足够有效的情况下，图哈希方法有望比其他无监督哈希方法取得更好的性能，因为图哈希散列码学习和哈希函数可以直接利用相似性（位置结构），这通常反映了成对的两个数据点之间的关系。图哈希的目标与相似性保持哈希的目标是一致的。此外，图哈希通常要求二进制码的比特是不相关的、平衡的[4]，[29]，这进一步保证了哈希的效率。现有的图哈希方法有谱哈希法、锚图哈希法[8]、离散图哈希法[29]、有序约束哈希法[30]、可伸缩图哈希（SGH）法[31]等。在文献中，大多数图哈希方法与其他无监督哈希方法相比，具有更高的精度，特别是对于长比特码。
上述所有哈希方法都是集中的。换句话说，这些方法只适用于单台机器学习哈希函数。但是在实际应用中，我们需要处理大量的大数据问题，比如大规模的图像处理[36]、[37]，大规模的信息检索[39]。这些问题往往超出一台机器（计算机）的能力。在这种情况下，数据通常被分区并存储在多台计算机中。此外，在搜索引擎的应用中，数据通常是由许多代理收集的，整个数据应该被用来建立索引。因此，我们需要设计分布式算法来解决这些问题。分布式算法在信号处理[40]-[43]、机器学习[44]-[46]、自动控制[47]-[49]等诸多领域得到了广泛的研究。在分布式环境中，每个代理只能与它的邻居进行信息交换，其目的是合作解决一个大规模的问题，并且通信成本适中。如果能够采用这种分布式的方式来学习基于多台机器存储/收集的数据的哈希函数，将会有很大的好处。然而，正如我们所知道的，这样一个关键的问题在实际中是很少被考虑的。我们知道的最相关的方法是[50]和[52]。Leng等人将集中式哈希问题分解为多个子问题，提出了一种分布式哈希方法DisH。DisH通过学习字典矩阵来获得哈希码和哈希函数。Liu等人[52]提出了分布式ABQ （distributed ABQ， DABQ），将ABQ方法扩展到分布式学习框架中，加速了ABQ的训练。然而，这些方法并没有充分利用原始空间的相似性。此外，这些方法不限制二进制码的位元不相关和平衡，而位元不相关和平衡是紧凑二进制码学习[4]的两个关键特性。
为了充分利用数据样本间的相似性，本文提出了一种高效分布式学习哈希函数的图哈希模型。受[8]的启发，我们构造了一个基于锚点的图矩阵来对分布式图哈希进行建模。结果表明，所提出的分布式哈希模型中的图矩阵可以分解为多个局部图矩阵，每个局部图矩阵可以由一个特定的代理独立构造，且通信和计算成本适中，满足分布式设置。利用这个图矩阵，我们建立了我们的图哈希模型。我们加入广泛使用的位不相关和平衡约束，使学习的二进制代码和哈希函数更有效率。为了设计分布式算法，我们将这个图哈希模型的目标函数分解为一组局部目标函数，这样整个问题就可以转化为一个含约束的分布式优化问题。约束优化问题是一个非协调优化问题。为了便于处理，我们将该问题重新表述为一个等价的双凸优化问题。接着我们提出了两种基于交替方向乘子法（ADMM）[46]的分布式算法来解决问题，分别为：顺序分布式哈希（SDH）和并行分布式哈希（PDH）。这两种算法都表现良好，同时各有其优点，PDH的时间效率更高，而SDH消耗的资源更少。
本文的其余部分组织如下：在第二节中，我们将介绍一些必要的记号和预备；在第三节中，我们提出了一个分布式图哈希模型，并给出了问题的表达式；我们在第四部分提出了两种分布式算法来解决这个问题；第五部分给出了通信和计算复杂度分析；第六部分给出了对大规模基准数据集的数值模拟；最后，我们在第七部分得出结论。
第2章 预备知识
2.1 符号说明
本文用小写字母表示列向量，用大写字母表示矩阵。对于向量x，我们用来表示x的转置，我们用表示x的-范数。对于矩阵X，表示x在第i行和第j列的项，表示Frobenius范数，tr（X）表示X的迹。我们使用符号表示向量的点乘函数。我们用I来表示单位矩阵。
2.2 图哈希
令表示n个样本的数据集，其中d为数据的维数。在不失一般性的前提下，假设数据点以原点为中心，即。哈希就是将每个高维数据点编码成一个紧凑的二进制代码，其中c是编码长度。一般来说，我们会学习c个二进制哈希函数，或者等价地，一个c维哈希函数，这样，一个查询x的二进制代码可以很容易地计算为。图哈希将二进制代码学习问题表示为
（1）
其中称为图矩阵，表示和之间的欧几里德相似度。在这里，参数定义了在空间中对应相似项的距离。最后两个约束要求二进制码分别是平衡的和不相关的。从目标函数可以看出，图哈希倾向于为相似的数据点分配相邻的二进制码，这与相似性保持哈希的目标是一致的。
2.3 网络模型
在本文中，我们认为数据是分布在m个代理（每个代理可以视为一个单独的机器），且m个代理一起构成了一个网络（例如图1）。网络的拓扑结构是由一个无向图G = （V， E）， 其中表示顶点的集合，表示边的集合。图中的每个顶点都被称为一个代理。表示代理l和j是邻居，可以通过无向链接直接交换信息。我们用表示代理l的邻居集合（不包括它自己），用表示代理l的度。我们假设整个网络是强连接的，任何两个代理都可以直接或间接地相互通信。
网络模型可以描述各种网络。在不同的网络中，代理代表不同的机器。例如，在无线传感器网络中，每个代理代表一个传感器节点；在小蜂窝网络中，每个代理代表一个基站；在摄像机网络中，每个代理代表一个摄像机；在计算机网络中，每个代理代表一台计算机。
图1 随机生成10个代理的网络
第3章 分布式图哈希的公式
在本节中，我们提出了一个分布式图哈希模型，该模型基于一个连接网络中（如图1）分布在m个代理上的数据上来学习哈希函数。对于每个，令表示代理l的局部数据集，其每一列为该代理中的数据点。那么整个数据集X就是局部数据集的拼接，即。
3.1 分布式图哈希模型
由于数据点分布在多个代理上，具有不可接受的通信和计算成本，因此很难构造一个形如（1）中的邻接图矩阵，来对分布式图哈希进行建模。受[8]的启发，我们选择构造一个基于锚点的图矩阵而不是邻域图矩阵，我们将证明这样一个图矩阵可以以一种分布式的方式进行计算和存储，并且通信和计算成本适中。为了实现这一点，我们需要选择个分布在多个代理上的全部数据点的代表性锚点。一种简单的方法是，每个代理l从本地数据集中随机选择个数据点作为本地锚点，并预先广播它们。所有锚点的总数是。为了获得更好的性能，使锚点更能代表整个数据点，一种更有效的方法是采用分布式矢量量化的方法[54]、[55]来生成锚点。分布式矢量量化方法在高密度区域生成更多的锚点，在整个数据集的低密度区域生成更少的锚点，虽然它消耗了更多的计算资源，但更合理。当得到锚点后，我们用它们来构造一个可以衡量训练数据点和锚点之间相似性的图矩阵，其中。图矩阵可以表示为局部图矩阵的串联，即，其中为代理l的局部图矩阵
（2）
局部图矩阵可以由代理 l独立计算，每个代理 l计算的时间复杂度适中，满足了分布式设置的要求。
在构造了图矩阵之后，我们通过解决以下问题来训练二进制哈希码：
资料编号：[238458]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
