沈复民作者

无问西东,只问哈希

编者按:“假设我是一串高维数据,这串数据将被加密,当数据的加密完成,它会生成一段二值码,当这段码字代替原始数据被用于检索任务时,就会加速检索的过程,这个加密过程,就是哈希。”

哈希,是化繁为简、以简驭繁;是在纷繁的数据世界中,通过学习千千万万个它,来寻找那个独一无二的你。今天,来自电子科技大学的沈复民教授,将带领大家一起,在纷繁的数据世界中,无问西东,只问哈希。

文末,大讲堂特别提供文中提到所有文章的下载链接。


我的报告将分为四部分,首先介绍什么是哈希,接下来介绍哈希中的一个独特方法——离散优化,然后是离散哈希的应用,最后介绍我们在SIGIR 2017上一个利用哈希汉明检索的分类工作。

什么是哈希(Hashing)


针对图像、视频或者文本数据库,哈希的主要工作是将高维数据变成低维紧凑的二值码,比如将d维数据变成r维,d远远大于r,一般r维数据在几十比特到几百比特之间。将数据变成哈希码后计算数据之间的距离或相似性会非常快,常用汉明距离来衡量,汉明距离的计算可以用CPU的一些快速指令,比如XNOR(异或非)或POPCOUNT。

哈希里面最著名的一个工作,也是工业界应用最多的一个工作是Locality-sensitive hashing(LSH),它在1999年被提出来。假设有一堆数据x,我们将这堆数据投影到空间里,通过如下操作将它变为0或者1。

如上图左边所示,随机在空间里划几个超平面,就可以把数据分到不同空间里,比如中间这个小三角的区域就可以赋值为101,之前w,b是随机生成得到的,而现在更多是基于机器学习或者依赖于数据而得到的。

哈希的一个主要应用是最近邻搜索,比如对于一个蝴蝶图片,我们希望在数据库中搜索到和它在视觉上最近似的图片。

LSH有很多不同的变种,它不仅支持欧几里得空间,还可以支持更多的维度,比如 lp 范数、余弦相似度、高斯、卡方核等。它的优点是简单易用,有次线性的搜索时间,缺点是需要很长比特的哈希码或者非常多的哈希表才能达到预期的性能。

因此,最近的学术界更多的研究集中于基于学习的哈希,期望通过此方法学习到更有效紧致的哈希码。

这里简单列了些无监督的哈希方法,比如最早的PCAH(PCA Hash)通过主成分分析方法学习到转置矩阵w,SH引入了无监督的图哈希,ITQ基于PCA采用正交旋转矩阵对初始投影矩阵进行优化,AGH利用anchor graphs解决SH,IMH从通用数据模型中生成二进制代码,DGH采用离散优化解决SH,AIBC是不对称的哈希方法等等。

有监督的哈希方法也非常多,比如SSH同时利用有标签和无标签的数据进行哈希,MLH基于结构化的支持向量机,KSH是基于核的有监督哈希,FastH通过经典算法Graph Cuts解决哈希问题,SDH通过离散优化生成二进制码,COSDISH是基于列抽样的离散监督哈希,以及近来基于深度学习方法的哈希DSeRH等等。

深度学习目前在计算机视觉和多媒体领域已经取得了显著的成绩,哈希领域也涌现了非常多的深度学习方法,效果都很不错。但是,目前大多数基于深度学习的哈希都是有监督的,而无监督方法却寥寥无几。

如上图是有监督的基于深度哈希方法和基于浅层模型方法的比较,可以看出深度方法比传统方法效果好很多。但是如下面表格所示,左边ITQ和IMH是基于浅层模型的无监督方法,右边的DH和UH是典型的基于深度学习的无监督方法,中间是结合卷积神经网络的特征和浅层ITQ模型的方法,可以看出目前的无监督深度哈希方法很大程度依赖于深度学习提取的特征,因此目前无监督的深度哈希还有很大的提升空间。

哈希和流形学习方法有什么区别呢?如图左边是著名的Laplacian Eigenmaps(拉普拉斯特征映射)公式,加上如下三个条件后,就是我们所谓的spectral hashing(谱哈希)

第一个条件保证所学哈希码的离散性,第二个条件保证学习出来的哈希码是平衡的,第三个条件保证学习到的哈希码是不相关的,以此可以学到更有效的紧凑的哈希码。从形式上看,哈希和流形学习之间的区别很小,主要在如上三个限制条件上。但其中最主要的,离散条件(二值化)的限制使得哈希学习的研究和传统的流形学习方法或其他降维方法产生很大区别,主要体现在优化上面。

所谓哈希学习问题只指,对于数据X,我们期望学到它的紧致表达哈希码B(r比特),B是r×n的,同时期望学习到一个预测函数(哈希函数)。因为变量B是离散的,所以不能用传统的梯度下降方法去解,这一问题是典型的混合整数问题,通常为NP hard(non-deterministic polynomial,缩写NP,非确定性多项式)问题。

在2015年之前,求解该问题基本分两步。第一步是将离散限制去掉,这就变成了连续优化的问题,可以用传统的梯度下降方法去求解,它的缺点是很难得到比较好的局部最优解;第一步去掉离散限制之后得到了连续的结果,第二步通过设定阈值进行二值化操作,比如将大于阈值的转为1,小于阈值的转为0,由此就得到了哈希码。当然,也可以利用类似2011年ITQ这篇工作去减少量化损失。这种方法的缺点是对于长哈希码(比如超过100比特),量化偏差会很大,使得学出来的哈希码不是很有效。


离散优化


我们从2015年开始研究离散优化问题,试图在不去掉binary constraint的条件下去解哈希问题,这是哈希和传统流形学习方法的区别,我们希望能够求解哈希的原本问题。

这是我们在CVPR2015的一个有监督的离散哈希工作。假设有一个数据X,我们希望学习到它的二进制代码B,同时使其很容易被分类到Y(groundtruth)这个标签矩阵上,希望通过W这个矩阵将B很容易分到正确的类别上。这里面有三个变量B,W,F

可以用迭代优化来求解该问题,依次求解W,F,B。其中最主要的就是求解B,它其实是一个二进制值优化问题。

B是离散的,因此我们提出了Discrete Cyclic Coordinate descent(DCC,离散循环坐标下降)方法,保留了binary constraint,直接求解矩阵B难度是很大的,因此我们通过逐比特地学习来解决这个问题。

在每一次迭代的时候都可以得到optimal,close-form solution,所以整个优化过程非常快。

如左图是对离散方法和常用two-step方法的对比,可以看出,随着比特数的升高,差距越来越大,离散方法比relaxed方法好很多。右图是和主流的有监督方法的比较。结论:离散优化对哈希问题本身是比较重要的。

我们沿着这个方向做了很多工作,总结起来,离散优化对于哈希问题本身来说是非常重要的。简单统计了一下,有监督的离散哈希方法(SDH)不仅支持linear cascaded loss,还支持hinge loss;更重要的,它训练的复杂度是O(n)的,因此可以快速学习整个数据库的二进制值,可以把整个数据库放入训练过程中,而不需要抽取一部分训练数据学出哈希函数之后再做inference。

刚才说的SDH方法可以支持几种损失函数,但它毕竟不是通用的,对于非常复杂的loss error,SDH方法就不能胜任了,因此我们能不能找到一种方法满足loss是任意的,只要是平滑的就可以求解。

这是我们在TIP2016做的一个工作,我们的方法被证明一定是能够收敛的,也通过实验证明了这个方法比relaxed方法好很多。如果B属于C,则损失是0,否则损失为正无穷,也就是将原本问题转化为该问题,就是smooth+non-smooth loss 问题,通过这个方法可以快速得到。该方法和SD方法区别在于,SDH需要逐比特地学,而这个方法可以学整个B。

该方法被证明一定是可以收敛的,并且比SDH更快,可以把该方法应用到有监督和无监督哈希中。

离散哈希的应用



这部分主要介绍离散哈希的应用。

这里其中一个应用是做了MIPS(Maximum Inner Product Search,内积最大值搜索),和approximate nearly search还是有很大区别的,

这个问题是指,假设数据库A中存储了很多样本a,我们希望依据query q从数据库中搜索到与query q有最大内积的样本a。这是一个无监督学习的工作,假设S是groundtruth,这里用A和X做一个内积,希望对数据库的A学一个哈希函数,对X学另一个哈希函数,通过同时学习这两个哈希函数去拟合groundtruth,这其实是一个inner product fitting的问题,通过学一个非对称的哈希函数来实现。

这个工作发表在ICCV2015上,这是和当时无监督哈希方法的比较结果。

这是我们2016SIGIR上和新加坡国立大学张含望老师合作的一个工作。Collaborative filtering,大家知道协同滤波一般用在推荐系统里,它实际是一个矩阵分解问题。一般推荐系统中用户量和数据量是非常大的,当时我们希望通过二值哈希技术来将它加速。

这是一些结果,可以看出DCF方法较其他方法有明显的提升。


利用哈希汉明检索分类


下面介绍SIGIR2017上的一个工作,初衷是,现在有非常多的哈希工作,基本都是针对检索问题,很少有针对分类问题的算法。能不能把哈希用在分类问题上呢?另外,把图像变成哈希码后,对图像分类是用传统的分类方法,还是把哈希码当作real-valued features呢,能不能利用二进制码本身的特质,来加速分类的过程呢?

这里的思想非常简单,一句话称之为“classify binary data with binary weights”,之后用二进制码进行分类,比如从d维变成r维,分类器W是d×C维的,把他变成r×C维的二进制,将得分y也变成二值的。很显然的好处是,左边需要dC次浮点数乘积操作,右边需要rC次XNOR操作,速度比左边快很多。这个工作是我们组和北大、腾讯AI Lab以及英国的东英吉利亚大学合作的。

简单介绍一下它的框架,通过对训练图片提取特征,得到HD real-valued features,通过joint learning方式同时学习图像和标签的binary code,利用binary code把分类问题变成利用哈希码做汉明检索的问题。

这是它的formulation,其中主要部分如上图红框所示,bi是imagei的二进制码,wci是指第i张图片groundtruth的类别,希望wci和bi的内积大于wc和bi的内积,我们定义这个部分叫inter-class margin,这里的损失函数可以是任意的,这里采用了两个算法,一个是exponential loss,一个是linear loss。

W和B都是binary metrics,因此求解是非常相似的,我们通过逐比特的方式去解。

这是在SUN397数据集上的结果,可以看出当哈希码的长度超过128比特时,我们的算法准确率超过linear SVM,训练时间比linear SVM少很多。

我们在SUN397,ImageNet,Caltech-256三个数据集上做了比较,准确率和SVM基本持平,在训练时间和测试时间上明显优于SVM,也比传统哈希方法好。

这是和其他哈希方法的比较结果。

总结起来,我们将线性分类问题转化成了汉明检索问题,把数据和分类器同时进行二值化处理,它也支持很多empirical loss函数,并且有效减小存储和训练测试消耗资源。

接下来简要介绍我们在CVPR2017上一个sketch retrieval问题,可以搜索和sketch query语义相关的图片,传统上有很多基于手工特征和深度特征的方法,这里我们采用哈希方法来做。

如图是DSH(deep sketch hashing)方法的框架,natural image 和 sketch image在图像结构上的差异是非常大的,如果直接用cross model retrieval的跨模态检索方法去做,效果不佳, 所以提出了自动提取sketch token的方法,希望Bs和BI内积能够和groundtruth吻合,同时我们还利用了word embedding把类别映射到一个word vector上,希望能够更多地获取语义类别之间的相关性。整体上这个工作把CNN和discrete binary code learning结合起来放到一个统一的框架下。

这是我们整个的formulation,W是groundtruth label metrix,BI是natural image的binary code,Bs是sketch图像的binary code。

这是一个优化的过程,通过迭代优化的方式逐步求解。

这是我们的DSH方法和以前SBIR(Sketch based image retrieval)方法的比较。

这是我们和之前的cross-modality方法的比较,因为cross-modality不是针对sketch retrieval的方法去设计的,所以它的效果不是特别理想,和real-valued方法比较,我们的方法还具有一定的优势。

这是一些通过deep sketch hashing做的成功案例,这是我们和英国的东英吉利亚大学一起做的工作。

最后讲一下我们在CVPR2017上用哈希去做partial action recognition的工作,传统方法是通过视频序列判断动作,action prediction是通过前序帧来预测后序帧。我们partial action recogtion在丢帧、遮挡的情况下依旧能够预测动作。

这是整个工作的框架,在公式中,X是partially observed actions,Y是fully-observed actions,希望通过W矩阵对它做一个还原,希望学fully observed action的二进制码,希望二进制码能够还原原先的similarity,这是比较常用的学习哈希码的损失函数,整个学习过程我们通过discrete alternating optimization方法求解。

这是一些结果,虽然学习到的特征是二进制的,但是整个效果可以看出还是不错的。这个工作是我们和北航、东英吉利亚大学以及上交大一起合作的。

除了这个工作,我们在离散哈希中还做了很多工作,如上图所示。

谢谢大家!


文中沈老师提到的文章下载链接为: 

https://pan.baidu.com/s/1qZZUEJi

入门哈希
相关数据
分类问题技术
Classification

分类问题是数据挖掘处理的一个重要组成部分,在机器学习领域,分类问题通常被认为属于监督式学习(supervised learning),也就是说,分类问题的目标是根据已知样本的某些特征,判断一个新的样本属于哪种已知的样本类。根据类别的数量还可以进一步将分类问题划分为二元分类(binary classification)和多元分类(multiclass classification)。

收敛技术
Convergence

在数学,计算机科学和逻辑学中,收敛指的是不同的变换序列在有限的时间内达到一个结论(变换终止),并且得出的结论是独立于达到它的路径(他们是融合的)。 通俗来说,收敛通常是指在训练期间达到的一种状态,即经过一定次数的迭代之后,训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说,如果采用当前数据进行额外的训练将无法改进模型,模型即达到收敛状态。在深度学习中,损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变,暂时形成收敛的假象。

卡方技术
Chi-Square

卡方常常与卡方分布和卡方检验联系在一起: 卡方分布(chi-square distribution)是常用于概率论和统计检验中的一种概率分布;卡方检验是(chi-square test)是一种基于卡方分布的常用的统计检验,其统计量在原假设(null hypothesis)成立时服从卡方分布。

计算机视觉技术
Computer Vision

计算机视觉(CV)是指机器感知环境的能力。这一技术类别中的经典任务有图像形成、图像处理、图像提取和图像的三维推理。目标识别和面部识别也是很重要的研究领域。

协同过滤技术
Collaborative filtering

协同过滤(英语:Collaborative Filtering),简单来说是利用某兴趣相投、拥有共同经验之群体的喜好来推荐用户感兴趣的信息,个人通过合作的机制给予信息相当程度的回应(如评分)并记录下来以达到过滤的目的进而帮助别人筛选信息,回应不一定局限于特别感兴趣的,特别不感兴趣信息的纪录也相当重要。协同过滤又可分为评比(rating)或者群体过滤(social filtering)。其后成为电子商务当中很重要的一环,即根据某顾客以往的购买行为以及从具有相似购买行为的顾客群的购买行为去推荐这个顾客其“可能喜欢的品项”,也就是借由社区的喜好提供个人化的信息、商品等的推荐服务。除了推荐之外,近年来也发展出数学运算让系统自动计算喜好的强弱进而去芜存菁使得过滤的内容更有依据,也许不是百分之百完全准确,但由于加入了强弱的评比让这个概念的应用更为广泛,除了电子商务之外尚有信息检索领域、网络个人影音柜、个人书架等的应用等。

降维技术
Dimensionality reduction

降维算法是将 p+1 个系数的问题简化为 M+1 个系数的问题,其中 M<p。算法执行包括计算变量的 M 个不同线性组合或投射(projection)。然后这 M 个投射作为预测器通过最小二乘法拟合一个线性回归模型。两个主要的方法是主成分回归(principal component regression)和偏最小二乘法(partial least squares)。

卷积神经网络技术
Convolutional neural network

卷积神经网路(Convolutional Neural Network, CNN)是一种前馈神经网络,它的人工神经元可以响应一部分覆盖范围内的周围单元,对于大型图像处理有出色表现。卷积神经网路由一个或多个卷积层和顶端的全连通层(对应经典的神经网路)组成,同时也包括关联权重和池化层(pooling layer)。这一结构使得卷积神经网路能够利用输入数据的二维结构。与其他深度学习结构相比,卷积神经网路在图像和语音识别方面能够给出更好的结果。这一模型也可以使用反向传播算法进行训练。相比较其他深度、前馈神经网路,卷积神经网路需要考量的参数更少,使之成为一种颇具吸引力的深度学习结构。 卷积网络是一种专门用于处理具有已知的、网格状拓扑的数据的神经网络。例如时间序列数据,它可以被认为是以一定时间间隔采样的一维网格,又如图像数据,其可以被认为是二维像素网格。

范数技术
Frobenius Norm

范数(norm),是具有“长度”概念的函数。在线性代数、泛函分析及相关的数学领域,是一个函数,其为向量空间内的所有向量赋予非零的正长度或大小。半范数反而可以为非零的向量赋予零长度。

梯度下降技术
Gradient Descent

梯度下降是用于查找函数最小值的一阶迭代优化算法。 要使用梯度下降找到函数的局部最小值,可以采用与当前点的函数梯度(或近似梯度)的负值成比例的步骤。 如果采取的步骤与梯度的正值成比例,则接近该函数的局部最大值,被称为梯度上升。

机器学习技术
Machine Learning

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

映射技术
Mapping

映射指的是具有某种特殊结构的函数,或泛指类函数思想的范畴论中的态射。 逻辑和图论中也有一些不太常规的用法。其数学定义为:两个非空集合A与B间存在着对应关系f,而且对于A中的每一个元素x,B中总有有唯一的一个元素y与它对应,就这种对应为从A到B的映射,记作f:A→B。其中,y称为元素x在映射f下的象,记作:y=f(x)。x称为y关于映射f的原象*。*集合A中所有元素的象的集合称为映射f的值域,记作f(A)。同样的,在机器学习中,映射就是输入与输出之间的对应关系。

损失函数技术
Loss function

在数学优化,统计学,计量经济学,决策理论,机器学习和计算神经科学等领域,损失函数或成本函数是将一或多个变量的一个事件或值映射为可以直观地表示某种与之相关“成本”的实数的函数。

流形学习技术
Manifold learning

流形学习(manifold learning)是机器学习、模式识别中的一种方法,在维数约简方面具有广泛的应用。它的主要思想是将高维的数据映射到低维,使该低维的数据能够反映原高维数据的某些本质结构特征。流形学习的前提是有一种假设,即某些高维数据,实际是一种低维的流形结构嵌入在高维空间中。流形学习的目的是将其映射回低维空间中,揭示其本质。

最近邻搜索技术
Nearest neighbor search

最邻近搜索(Nearest Neighbor Search, NNS)又称为“最近点搜索”(Closest point search),是一个在尺度空间中寻找最近点的优化问题。问题描述如下:在尺度空间M中给定一个点集S和一个目标点q ∈ M,在S中找到距离q最近的点。很多情况下,M为多维的欧几里得空间,距离由欧几里得距离或曼哈顿距离决定。

推荐系统技术
Recommender system

推荐系统(RS)主要是指应用协同智能(collaborative intelligence)做推荐的技术。推荐系统的两大主流类型是基于内容的推荐系统和协同过滤(Collaborative Filtering)。另外还有基于知识的推荐系统(包括基于本体和基于案例的推荐系统)是一类特殊的推荐系统,这类系统更加注重知识表征和推理。

主成分分析技术
Principal component analysis

在多元统计分析中,主成分分析(Principal components analysis,PCA)是一种分析、简化数据集的技术。主成分分析经常用于减少数据集的维数,同时保持数据集中的对方差贡献最大的特征。这是通过保留低阶主成分,忽略高阶主成分做到的。这样低阶成分往往能够保留住数据的最重要方面。但是,这也不是一定的,要视具体应用而定。由于主成分分析依赖所给数据,所以数据的准确性对分析结果影响很大。

监督学习技术
Supervised learning

监督式学习(Supervised learning),是机器学习中的一个方法,可以由标记好的训练集中学到或建立一个模式(函数 / learning model),并依此模式推测新的实例。训练集是由一系列的训练范例组成,每个训练范例则由输入对象(通常是向量)和预期输出所组成。函数的输出可以是一个连续的值(称为回归分析),或是预测一个分类标签(称作分类)。

深度学习技术
Deep learning

深度学习(deep learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。 深度学习是机器学习中一种基于对数据进行表征学习的算法。观测值(例如一幅图像)可以使用多种方式来表示,如每个像素强度值的向量,或者更抽象地表示成一系列边、特定形状的区域等。而使用某些特定的表示方法更容易从实例中学习任务(例如,人脸识别或面部表情识别)。 近年来监督式深度学习方法(以反馈算法训练CNN、LSTM等)获得了空前的成功,而基于半监督或非监督式的方法(如DBM、DBN、stacked autoencoder)虽然在深度学习兴起阶段起到了重要的启蒙作用,但仍处在研究阶段并已获得不错的进展。在未来,非监督式学习将是深度学习的重要研究方向,因为人和动物的学习大多是非监督式的,我们通过观察来发现世界的构造,而不是被提前告知所有物体的名字。 至今已有数种深度学习框架,如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。

准确率技术
Accuracy

分类模型的正确预测所占的比例。在多类别分类中,准确率的定义为:正确的预测数/样本总数。 在二元分类中,准确率的定义为:(真正例数+真负例数)/样本总数

支持向量机技术
Support Vector Machines

深度学习大讲堂
深度学习大讲堂

机器之心编辑

深度学习大讲堂
深度学习大讲堂

高质量原创内容平台,邀请学术界、工业界一线专家撰稿,致力于推送人工智能与深度学习最新技术、产品和活动信息。

返回顶部