语义哈希是一种非常高效的寻找与提供的文档相似的文档的方法,给定一个数据集,语义哈希试图找到一种编码方法/语义哈希函数,使得在编码后的内存地址中,距离越近的地址所含的文档更相似。在语义哈希中,数据库中的每个项目都由一个简介的二进制代码表示。 该代码的构造使相似的项目将具有相似的二进制代码,并且有一个简单的前馈网络可以计算新输入的项目的二进制码,检索相似的文档只需要通过简单地检索所有二进制码与目标文档的二进制码的汉明距离(Hamming distance)足够小的文件。
由下图可见,数据集中每一个文档都会被语义哈希函数映射到地址空间的一个点上,而在这个空间中点之间的距离越小就代表文档之间的语义越相近。
在实际操作中,这种检索速度可以非常快——标准计算机上达到每秒钟数百万次的查询。语义哈希成功的关键是根据数据集学习到一个好的编码方法。理想的编码方法应该:
- 易于计算新输入的文档的二进制码
- 只需要少量的字节(bit)来编码整个数据集
- 能够将类似的文档映射到类似的二进制码
[描述来源:Salakhutdinov S.; Hinton G. (2009). Semantic hashing. International Journal of Approximate Reasoning. 50(7): 969-978.]
发展历史
语义哈希方法是由Salakhutdinov和Hinton提出的,语义哈希实际上是自编码(autoencoder)的一种应用,Hinton和Salakhutdinov在提出语义哈希之前就在2006年发表的论文中探讨了利用自编码降低数据维度的应用。Weiss,Torralba和Fergus证明可为给定数据集找到最佳编码方法可能是NP难的,他们松弛优化条件,将原问题转化为谱问题,并提出了谱哈希(spectral hash)来求解问题,他们的实验表明该方法明显优于当时使用的其他技术。2013年Wang等人提出目前的方法所创造的标签信息尚未充分利用现实的文档的信息,关键词特征空间的相似性并不能完全反映除关键词匹配以外的语义关系,他们提出了使用标签和主题建模(SHTTM)的语义哈希,以结合标签信息和来自概率主题建模(probabilistic topic modeling)的相似信息。2015年Carreira-Perpinan和Raziperchikolaei提出的算法是语义哈希的一种变体,他们利用二进制自编码(binary autoencoder)模型,从哈希函数生成的二进制代码重建图像,并通过实证检验显示该方法所得到的哈希函数至少与目前常用方法所得到的哈希函数一样好。
主要事件
年份 | 事件 | 相关论文/Reference |
2006 | Salakhutdinov和Hinton探讨了利用自编码降低数据维度的应用 | Hinton G.;Salakhutdinov S.(2006). Reducing the Dimensionality of Data with Neural Networks. Science. 313(5786):504-507. |
2009 | Salakhutdinov和Hinton提出语义哈希方法 | Salakhutdinov S.;Hinton G. (2009).Semantic hashing.International Journal of Approximate Reasoning. 50(7): 969-978. |
2009 | Weiss,Torralba和Fergus提出了谱哈希(spectral hash) | Weiss Y.; Torralba A.; Fergus R.(2009). Spectral hashing. NIPS, pp 1753–1760. |
2013 | Wang等人提出了使用标签和主题建模(SHTTM)的语义哈希 | Wang Q.; Zhang D.; Si L. (2013). Semantic hashing using tags and topic modeling.Proceedings of the 36th international ACM SIGIR conference on Research and development in information retrieval. pp 213-222. |
2015 | Carreira-Perpinan和Raziperchikolaei提出语义哈希算法的一种变体,从哈希函数生成的二进制代码重建图像 | Carreira-Perpinan M. A.; Raziperchikolaei R. (2015). Hashing with binary autoencoders. CVPR, pp 557–566. |
发展分析
瓶颈
Weiss等学者在论文中提到给定一个数据集,为其寻找最佳编码方法的问题与图分区(graph partitioning)问题密切相关,并且可能是NP难的,因此,如何找到合适的编码方法是一个难点。
未来发展方向
拓展算法以使其有更广泛的应用(如目前已在图像检索中有应用),或寻找在某方面性能更优的编码方法。
Contributor: Yuanyuan Li