论文部分内容阅读
随着机器学习各领域的快速发展,实现高效大规模近似最近邻搜索已成为了一个热门的研究问题。哈希学习技术作为解决大规模近似最近邻搜索问题的最主流技术之一受到广泛关注。然而在哈希学习过程中,仍然面临许多亟待解决的科学问题和技术挑战。本文主要围绕哈希学习过程中的高精度排序、高速度排序和分布式编码这三方面的挑战,提出了基于加权非对称距离的精准哈希排序方法、面向加权汉明空间的快速哈希排序方法和面向大规模哈希学习的分布式编码方法,具体研究内容和创新点总结如下。哈希学习方法在解决大规模近似最近邻搜索问题时可以获得较好的时间性能,但如何提高哈希学习方法的精度性能一直是研究者们最关注的问题。目前大多数研究关注在哈希编码过程中尽可能保持原始空间和投影空间点之间的相似度关系,很少有研究关注对已生成的二进制码的排序问题。尽管计算二进制码之间的汉明距离非常高效,但基于汉明距离的哈希排序精度很低。于是,有研究提出了基于非对称距离的哈希排序方法,可以将距离空间进行更浓密的划分,从而提高搜索精度。然而,这种哈希排序方法没有考虑不同投影位重要性的不同进行区分对待。本文提出了两种基于加权非对称距离的高精度哈希排序方法。二者的区别在于代表点的选择和权重的计算。第一种哈希排序方法的代表点依赖于Otsu阈值,权重计算与数据库点的近邻分布以及查询点与阈值之间的距离有关;第二种哈希排序方法的代表点依赖于均值和基于近邻分布概率,权重计算与哈希函数的平衡性和独立性有关。总体来说,第一种哈希排序方法更适用于特征数据集,第二种哈希排序方法更适用于图像数据集。实验证实了两种哈希排序方法的精度比汉明距离精度高达22%和比非对称距离精度高达13%,实验也在不同数据集上对比了两种哈希排序方法的精度。尽管为了提高哈希学习方法的精度,近年来提出了很多基于加权汉明距离的哈希排序方法。然而,在大规模近似最近邻搜索应用中,加权汉明空间中的线性搜索仍比较耗时,但目前并不存在加权汉明空间中除线性搜索外的快速搜索方法。尽管在汉明空间中,有研究提出了基于多表的索引结构,但将其直接应用到加权汉明空间的主要问题是,无法在每个子表上快速、准确地定位到与查询点加权汉明距离小于等于子表搜索半径的哈希篮子中。本文提出了一种面向加权汉明空间基于多表的快速近邻搜索方法。该方法的思想是,在离线时为每个子表建立两个和权重有关的向量,在搜索时通过比较子表搜索半径和两个向量中值的大小即可快速索引到对应的哈希篮子中。同时,通过建立一个候选点集合和一个缓存集合以避免对数据库点加权汉明距离的重复计算,进一步提高了搜索的时间性能。实验结果表明,在包含一百万数据点的数据集上,本文提出的快速搜索方法与线性搜索相比可达到几十倍时间性能的提高。由于在一些大规模近似最近邻搜索应用中,数据往往是分布式采集、存储的。因此需要提出适用于分布式环境的哈希编码方法。若将单机哈希编码方法直接应用到分布式环境中,需要将分布在各个节点上的所有数据都传输到同一个中心节点上,再像单机一样进行近似最近邻搜索。然而这种方法有两大问题:一是网络传输量太大;二是对中心节点的存储需求太高。因此,近期提出了一些分布式哈希编码方法,它们的思想大多数基于将某种已有的单机哈希编码方法扩展至分布式环境中。这些分布式哈希编码方法有两大缺点:一是由于它们基于某种单机哈希编码方法,所以最多可以获得与单机哈希编码方法一致的精度,并不能大幅度提高精度。二是它们的通用性太差,无法扩展至其它新的单机哈希编码方法上。本文提出了两种分布式哈希学习模型:通用分布式哈希学习模型和可扩展分布式哈希学习模型。二者的主要区别在于节点之间传输数据的不同,前者在节点之间传输的是候选点集合,后者在节点之间传输的是参数。总体来说,通用分布式哈希学习模型的精度更高,而可扩展分布式哈希学习模型的数据规模可扩展性更强。实验结果表明,两种分布式哈希学习模型的精度既比单机哈希编码方法的精度高达49%,也比目前最好的分布式哈希编码方法的精度高达15%。