林学通瓶2015年2月第60卷第5-6期 习”(one-pass learning)的思想，力图在学习中只扫描 一遍数据、且使用常数级存储来保存中间计算结果， 在AUC优化这样的复杂学习任务上已取得很好的效 果.此外还有很多新进展，本文不再赘述 哈希学习(learning to hash)2-2通过机器学习机 制将数据映射成二进制串的形式，能显著减少数据 的存储和通信开销，从而有效提高学习系统的效率. h(自由女神)= h(拿设仑1)= h(享报它2)= 10001010 01100001 01100101 哈希学习的目的是学到数据的二进制哈希码表示， 不同的位 使得哈希码尽可能地保持原空间中的近邻关系，即 相似度尽可能小 相似度尽可能大 保相似性.具体来说，每个数据点会被一个紧凑的二 图1（网络版彩色）哈希学习示意图 进制串编码，在原空间中相似的2个点应当被映射到 Figure 1 (Color online)lllustration of learning to hash 哈希码空间中相似的2个点.图1是哈希学习的示意 图，以图像数据为例，原始图像表示是某种经过特征 哈希编码位数就能取得理想的精度，从而进一步提 抽取后的高维实数向量，通过从数据中学习到的哈 高检索和学习效率，降低存储和通信开销. 希函数h变换后，每幅图像被映射到一个8位(bit)的二 进制哈希码，原空间中相似的两幅图像将被映射到 1 研究进展 相似（即海明距离较小）的2个哈希码，而原空间中不 哈希学习由Salakhutdinov和Hinton2.,1于2007年 相似的两幅图像将被映射到不相似（即海明距离较 推介到机器学习领域，于近几年迅速发展成为机器学 大)的2个哈希码.使用哈希码表示数据后，所需要的 习领域和大数据学习领域的一个研究热点422.26-刃 存储空间会被大幅减小.举例来说，如果原空间中每 并广泛应用于信息检索38,39)、数据挖掘40,4、模式识 个数据样本都被1个1024B的向量表示，1个包含1亿 别2.4)、多媒体信息处理4,4、计算机视觉6,47刃、推 个样本的数据集要占用100GB的存储空间.相反， 荐系统4)、以及社交网络分析49,50等领域.值得一提 如果把每个数据样本哈希到1个128位的哈希码，一 的是，国内学者在这方面也进行了有意义的探 亿个样本的存储空间只需要1.6GB.单台机器（包括 索32-37,43,45-47.50,5 配置很高的单台服务器)处理原始表示时，需要不断 由于从原空间中的特征表示直接学习得到二进 地进行外内存交换，开销非常大.但如果用哈希码表 制的哈希编码是一个NP难问题4.现在很多的哈希 示，所有计算都可以在内存中完成，单台普通的个人 学习方法4,17-20都采用两步学习策略：第一步，先对 电脑(PC)也能很快地完成计算.由于很多学习算法， 原空间的样本采用度量学习(metric learning)s2l进行 比如k近邻kNN)、支持向量机(SVM)等的本质是利用 降维，得到1个低维空间的实数向量表示；第二步， 数据的相似性，哈希学习的保相似性将在显著提高 对得到的实数向量进行量化（即离散化）得到二进制 学习速度的同时，尽可能地保证精度.另一方面，因 哈希码.现有的方法对第二步的处理大多很简单，即 为通过哈希学习得到的哈希码位数（维度）一般会比 通过某个阈值函数将实数转换成二进制位.通常使 原空间的维度要低，哈希学习也能降低数据维度， 用的量化方法为1个國值为0的符号函数.即如果向 从而减轻维度灾难问题.因此，哈希学习在大数据 量中某个元素大于0，则该元素被量化为1，否则如果 学习中占有重要地位. 小于或等于0，则该元素被量化为0.例如.假设样本 需特别指出的是，数据库研究领域早已使用二 在原空间中的特征表示为1个5维实数向量(1.1,2.3， 进制哈希码来表示数据23-2，但他们使用的哈希函 1.5,4,3.2),经过某种度量学习（通常把降维看成度量 数是人工设计或者随机生成的：与之不同，哈希学习 学习的一种)处理后得到1个三维的实数向量(1.8. 是希望从数据中自动地学习出哈希函数.从哈希技 -2.3,0.6),然后经过符号函数量化后，得到的二进制 术的角度来看，前者被称为数据独立方法，后者被称 哈希码为(1,0,1).一般来说，度量学习阶段首先得 为数据依赖方法.有研究表明.181，与数据独立方法 构建学习模型，然后对模型的参数进行优化和学习. 相比，数据依赖方法（即哈希学习方法）只需用较短的 下面我们将从学习模型、参数优化和量化策略3方面 4862015 年 2 月 第 60 卷 第 5-6 期 486 习”(one-pass learning)的思想, 力图在学习中只扫描 一遍数据、且使用常数级存储来保存中间计算结果, 在AUC优化这样的复杂学习任务上已取得很好的效 果. 此外还有很多新进展, 本文不再赘述. 哈希学习(learning to hash)[12~22]通过机器学习机 制将数据映射成二进制串的形式, 能显著减少数据 的存储和通信开销, 从而有效提高学习系统的效率. 哈希学习的目的是学到数据的二进制哈希码表示, 使得哈希码尽可能地保持原空间中的近邻关系, 即 保相似性. 具体来说, 每个数据点会被一个紧凑的二 进制串编码, 在原空间中相似的2个点应当被映射到 哈希码空间中相似的2个点. 图1是哈希学习的示意 图, 以图像数据为例, 原始图像表示是某种经过特征 抽取后的高维实数向量, 通过从数据中学习到的哈 希函数h变换后, 每幅图像被映射到一个8位(bit)的二 进制哈希码, 原空间中相似的两幅图像将被映射到 相似(即海明距离较小)的2个哈希码, 而原空间中不 相似的两幅图像将被映射到不相似(即海明距离较 大)的2个哈希码. 使用哈希码表示数据后, 所需要的 存储空间会被大幅减小. 举例来说, 如果原空间中每 个数据样本都被1个1024 B的向量表示, 1个包含1亿 个样本的数据集要占用100 GB的存储空间. 相反, 如果把每个数据样本哈希到1个128位的哈希码, 一 亿个样本的存储空间只需要1.6 GB. 单台机器(包括 配置很高的单台服务器)处理原始表示时, 需要不断 地进行外内存交换, 开销非常大. 但如果用哈希码表 示, 所有计算都可以在内存中完成, 单台普通的个人 电脑(PC)也能很快地完成计算. 由于很多学习算法, 比如k近邻(kNN)、支持向量机(SVM)等的本质是利用 数据的相似性, 哈希学习的保相似性将在显著提高 学习速度的同时, 尽可能地保证精度. 另一方面, 因 为通过哈希学习得到的哈希码位数(维度)一般会比 原空间的维度要低, 哈希学习也能降低数据维度, 从而减轻维度灾难问题. 因此, 哈希学习在大数据 学习中占有重要地位. 需特别指出的是, 数据库研究领域早已使用二 进制哈希码来表示数据[23~25], 但他们使用的哈希函 数是人工设计或者随机生成的; 与之不同, 哈希学习 是希望从数据中自动地学习出哈希函数. 从哈希技 术的角度来看, 前者被称为数据独立方法, 后者被称 为数据依赖方法. 有研究表明[17,18], 与数据独立方法 相比, 数据依赖方法(即哈希学习方法)只需用较短的 图 1 (网络版彩色)哈希学习示意图 Figure 1 (Color online)Illustration of learning to hash 哈希编码位数就能取得理想的精度, 从而进一步提 高检索和学习效率, 降低存储和通信开销. 1 研究进展 哈希学习由Salakhutdinov和Hinton[12,13]于2007年 推介到机器学习领域, 于近几年迅速发展成为机器学 习领域和大数据学习领域的一个研究热点[14~22,26~37], 并广泛应用于信息检索[38,39]、数据挖掘[40,41]、模式识 别[42,43]、多媒体信息处理[44,45]、计算机视觉[46,47]、推 荐系统[48]、以及社交网络分析[49,50]等领域. 值得一提 的 是 , 国内学者在这方面也进行了有意义的探 索[32~37,43,45~47,50,51]. 由于从原空间中的特征表示直接学习得到二进 制的哈希编码是一个NP难问题[14]. 现在很多的哈希 学习方法[14,17~20]都采用两步学习策略: 第一步, 先对 原空间的样本采用度量学习(metric learning)[52]进行 降维, 得到1个低维空间的实数向量表示; 第二步, 对得到的实数向量进行量化(即离散化)得到二进制 哈希码. 现有的方法对第二步的处理大多很简单, 即 通过某个阈值函数将实数转换成二进制位. 通常使 用的量化方法为1个阈值为0的符号函数, 即如果向 量中某个元素大于0, 则该元素被量化为1, 否则如果 小于或等于0, 则该元素被量化为0. 例如, 假设样本 在原空间中的特征表示为1个5维实数向量(1.1, 2.3, 1.5, 4, 3.2), 经过某种度量学习(通常把降维看成度量 学习的一种)处理后得到1个三维的实数向量(1.8, 2.3, 0.6), 然后经过符号函数量化后, 得到的二进制 哈希码为(1, 0, 1). 一般来说, 度量学习阶段首先得 构建学习模型, 然后对模型的参数进行优化和学习. 下面我们将从学习模型、参数优化和量化策略3方面