快速近似近邻检索的哈希方法研究

摘要

随着互联网的普及，过去的几年里，网络上的数据快速增长。对机器学习来说，大量的数据意味着可以训练更加复杂的模型，模型的泛化能力也得到提高，但同时，模型在训练和使用阶段的计算和时间代价使某些机器学习算法面临较大的可用性问题。特别的，KNN检索作为机器学习领域经常用到的一种基本算法，大规模数据集上简单的线性搜索会消耗大量时间。哈希算法作为最有效的近似近邻检索方法之一，能有效权衡检索速度和检索准确度，在过去几年时间里得到了国内外学者越来越多的关注。
　　另一方面，网络上的很多对象同时包含多个模态进行展示，例如微博通常同时包括文本和图片，或者文本和视频。随着多模态数据的增多，在学术和工业上，跨模态检索逐渐成为一个新的需求。由于不同模态的数据往往有不同维度的特征，目前常用的方法是把不同模态的数据投影到同一个隐空间以消除不同模态之间的异构性，从而数据可以直接在隐空间中寻找近邻。在此基础上，跨模态哈希可以加快检索速度。
　　本文的主要工作是无监督哈希算法和跨模态哈希算法的研究。由于二进制编码计算的高效性，使用哈希算法进行检索往往比线性搜索K近邻快数十甚至上百倍。本文主要进行了两方面的研究:1）一种欧几里得空间线性无监督哈希（USEH算法）。部分无监督哈希算法使用径向基核函数来度量欧几里得空间中数据样本之间的相似度，构造相似度矩阵。USEH算法也采用了相似的思路，以确保投影到海明空间后样本间的相似度保一致。但由于构造这样一个相似度矩阵占用的空间过大，USEH利用LSH向量来近似径向基函数的。具体的，USEH算法利用LSH从无监督数据集中生成伪标签信息，用标签矩阵和它转置的乘积来近似相似度矩阵，从而减少训练过程中占用的内存空间和训练时间。另外，由于哈希编码正交约束会导致较多的信息丢失，USEH算法使用顺序学习的策略逐个学习哈希函数，忽略正交约束以获取训练集数据更多的方差信息。随着哈希编码长度增加，相比于正交约束算法，USEH顺序学习方法的优势越来越明显。2）一种基于字典学习的跨模态检索哈希（DLCMH算法）。DLCMH算法把不同模态的数据投影到同一个海明空间，并假设同一个对象的不同模态数据有相同的哈希编码。通常情况下，同一个模态内样本特征之间的欧氏距离和语义相似度之间存在不一致的情况，而线性哈希投影矩阵很难纠正两者之间的偏差。为了使投影后数据间的距离和语义相似度更好的匹配，DLCMH算法引入了字典学习，通过字典表示来自动学习语义信息，然后用线性投影矩阵把数据的字典表示投影到海明空间。在目标函数优化阶段，DLCMH对哈希编码矩阵进行松弛使目标函数容易求导，并把较难求解的优化问题拆分成多个容易求解的子问题。
　　为了验证上述两种算法的有效性，本文设计了几组实验，在多个公开的数据集上，分别把USEH算法、DLCMH算法与目前先进的几种无监督哈希算法、跨模态哈希算法进行比较。由于无监督哈希算法和跨模态哈希算法在机器学习、计算机视觉和信息检索等领域有广泛的应用，本文的研究内容具有较好的应用前景。

目录

声明

摘要

第1章 绪论

1．1 研究背景

1．2 相关研究工作

1．2．1 海明编码快速检索相关研究工作

1．2．2 无监督哈希相关研究工作

1．2．3 跨模态哈希相关研究工作

1．3 本文的主要工作

1．3．1 欧几里得空间线性无监督哈希

1．3．2 基于字典学习的跨模态检索哈希

1．4 论文的组织结构

第2章 欧几里得空间近似近邻搜索的线性无监督哈希

2．1 概述

2．2 USEH算法介绍

2．2．1 局部敏感哈希LSH生成伪标签

2．2．2 USEH算法目标函数

2．2．2 余弦相似度及相似矩阵

2．2．3 学习正交投影矩阵

2．2．4 学习非正交投影矩阵

2．2．5 计算复杂度分析

2．3 实验设计和结果分析

2．3．1 数据集和度量方法

2．3．2 参数设置

2．3．3 算法比较

2．4 本章小节

第3章 基于字典学习的跨模态检索哈希

3．1 概述

3．2 DLCMH算法介绍

3．2．1 数学符号和问题定义

3．2．2 DLCMH算法的目标函数

3．2．3 目标函数优化算法

3．2．4 训练集外样本

3．3 实验设计和结果分析

3．3．1 Wiki数据集上的实验结果

3．3．2 NUS-WIDE数据集上的实验结果

3．4 本章小节

第4章 总结和展望

参考文献

致谢

攻读学位期间发表的学术论文