分享到微博 分享到人人 分享到LinkedIn 分享到Email
微软亚洲研究院博士生学术交流会——2016年第一期:量化和哈希
作者 微软亚洲研究院实习生 张婷 陈斌
2016年1月26日

为了加强计算机领域博士生之间的学术交流和研究合作,微软亚洲研究院联合培养博士班推出“博士生学术交流会”系列学术交流活动。2016年1月20日,在第一次交流会上,我们邀请了近几年在“量化和哈希”方向上表现出色的博士生和教师作学术分享,并与现场的博士生们一起探讨“量化和哈希”的研究现状和未来趋势。

哈希在应用方面未来会是一个很大的研究方向 ——刘祥龙 ,北京航空航天大学

基于哈希的最近邻搜索最开始应用于图像检索中,即将图像转变成哈希码,并使相似图像的哈希码尽量相同,不相似图像的哈希码尽量不同,然后我们可以使用两幅图像的海明距离来排序,或者我们可以利用图像的哈希码建立一个倒排表进行哈希查询。随着哈希的发展,从最初是数据独立的哈希函数,到通过机器学习方法学习数据依赖的哈希函数,哈希的贡献在未来将会越来越多应用在其他方面,比如手机端进行大规模检索,3D重建快速匹配,推荐系统等。同时,传统的哈希只处理表现形式为向量的数据,现在针对不同的应用,哈希需要处理许多不同形式的数据,比如树/图结构,3D云图,视频等,如何在这些复杂数据上进行训练也是一个有待考虑的问题。

如何处理流式数据? ——冷聪 ,中科院

很多针对近似最近邻搜索的哈希方法都忽略了两个重要的问题。第一,在现实生活中,总是有不断的新数据加入,数据集并不是固定不变的,而是一直在更新。第二,当数据集的规模变得非常大时,在如此大规模的数据上训练哈希函数是非常困难的。基于data sketching的思想,我们提出不需要存储所有数据,而只存储数据的框架也即sketch。当新数据来临时,我们并不更新数据集,而只更新这个框架,然后在这个数据框架上训练哈希函数。

处理流式数据还有一个问题就是每重新训练一次哈希函数,数据集里面的哈希码需要重新编码一次,当数据集越来越大,这方面的时间消耗会越来越不可忍受。

搜索精度更依赖于KNN分类准确度—— 丁昆,中科院

基于这样一个观察,搜索精度与KNN分类准确度是高度正相关的,我们提出一种用KNN来学习哈希函数的监督方法。更具体的说,在学习的过程中,我们的目标函数是最大化训练数据哈希码的KNN分类准确度。同时,为了减少训练过程中所需的时间以及内存,我们将KNN based的 近邻表示矩阵分解为两个更小的矩阵相乘。考虑到现实生活中数据在大多数情况下是线性不可分的,我们首先用核函数将数据映射到另一个特征空间,然后在映射后的特征空间里训练哈希函数。

量化可以使近似最近邻搜索的精度更高 —— 张婷,中国科学技术大学-微软亚洲研究院联合培养博士生

近似最近邻搜索的研究方向主要包含了两个大的领域,一个是哈希算法,将数据映射到二进制编码,然后用二进制编码的海明距离用来排序搜索近似最近邻,另外一个是量化算法,将数据空间剖分成许多子空间,每个子空间用一个中心数据来表示,然后数据之间的距离用其所在子空间的中心数据的距离来近似。我们提出子空间的中心不一定只能用一个数据来表示,还可以用多个数据的和来表示一个中心数据,从而达到更准确的数据近似,得到更满意的近似最近邻搜索结果。