1. 背景介绍

首先介绍一下最近邻搜索：最近邻搜索问题，也叫相似性搜索，近似搜索，是从给定数据库中找到里查询点最近的点集的问题。

最近邻搜索

给定一个点集，以及一个查询点q，需要找到离q最近的点的集合；在大规模高维度空间的情况下，这个问题就变得非常难，而且大多数算法计算量极大，复杂度很高； 因此，一般用近似的最邻近搜索代替；哈希就是解决上述这类问题的主要方法;

2. 哈希学习概述

　　定义：哈希学习（learning to hash）是通过机器学习机制将数据映射成二进制串的形式，能显著减少数据的存储和通信开销，从而有效提高学习系统的效率。

​ 目的：通过机器学习机制将数据映射成简洁的二进制串的形式, 同时使得哈希码尽可能地保持原空间中的近邻关系, 即保相似性.（这一点很重要，如果失去了原来的相似性，那么哈希学习也就变得没有意义了）
　　以下面这幅图为例，原始数据是三幅图像，其中后面这两幅相似度比较高，也就是说在原始空间中从语义层次的距离或者欧氏距离都比较近，映射为哈希码之后，距离也应该更近。

image-20210902221647476

​ 图1 哈希学习示意图

图 1是哈希学习的示意图，以图像数据为例，原始图像表示某种经过特征抽取后的高维实数向量，通过从数据中学习到的哈希函数$h$ 换后，每幅图像被映射到一个8位 (bit) 的二进制哈希码，原空间中相似的两幅图像将被映射到相似 (即海明距离较小) 的两个哈希码，而原空间中不相似的两幅图像将被映射到不相似 (即海明距离较大) 的两个哈希码。

　　重要地位

  • 使用哈希码表示数据后，所需要的存储空间会被大幅减小。
  • 因为通过哈希学习得到的哈希码位数(维度)一般会比原空间的维度要低，哈希学习也能降低数据维度，从而减轻维度灾难问题。
  • 基于哈希学习得到的二进制哈希码可以构建索引机制，实现常数或者次线性级别的快速近邻检索，为上层学习任务的快速实现提供支撑。

分类：

  1. 第一种的代表是局部敏感哈希，这种方法主要是人工设计或者随机生成哈希函数，是一种数据独立的方法；

  2. 第二种是哈希学习的方法，希望从数据中自动学习出哈希函数，是一种数据依赖的方法；也是现在主流的方法；

    显然第二种具有数据依赖性，是一种更有适应性的方法。

3. 哈希学习的一般步骤

  1. 先对原空间的样本进行降维, 得到1个低维空间的实数向量表示;
  2. 对得到的实数向量进行量化(即离散化)得到二进制哈希码；

4. 参考