本文首发于 vivo 互联网技术微信公众号 mp.weixin.qq.com/s/wLMvJPXXa…
作者：Eike Dehling
翻译：杨振涛
本文由来自 Textkernel 的软件与数据工程师 Eike Dehling 于2018年10月23日发布与其Linkedin 的 pulse 上，已获得翻译授权。
目录：
一、Fast Nearest Neighbours
二、Elasticsearch 插件
三、集成工作
四、结论
最近我在帮一个数据科学家同事工程化一个基于深度学习模型的搜索系统。他们的项目是关于在文档嵌入应用深度学习模型，然后使用嵌入向量到我们的搜索系统中来查找相似文档。
一个文档嵌入本质上其实是一个（长的）数值数组，查找相似文档就相当于查找其他与其较相近的（长的）数值数组；可以采用诸如欧氏距离等来衡量相似性。
可以借此来查找相似文档，但是因为不是直接基于关键词而是基于“嵌入”，所以可以自动获得与同义词扩展相媲美的效果。它会查找相关文档，即使它们使用不同的关键词，因此能比关键词检索表现更好。
已经有解决这种问题的工具了，比如 facebook 的 FAISS 库(github.com/facebookres…)。这个类库速度非常快，并且支持多种智能方法使用嵌入向量实现快速检索。不过它不能友好地集成到类似 Elasticsearch 这样的搜索引擎中。
对于 Elasticsearch 来说，也有一些插件(github.com/muhleder/el…)提供了相似度计算功能，但是它们的速度并不怎么样，因为它们只计算了向量相似度而没有做过滤。
所以我们自己动手实现了更好的解决方案。
一、Fast Nearest Neighbours
为了更快速检索通常会使用各种“索引”，这种数据结构支持高效地过滤出相关的匹配，而无需单独评估每一个匹配。基于关键词的检索一般使用“倒排索引”；基于地理位置的检索，一般使用一种叫做 KD树 的数据结构。我们也需要诸如此类的机制来快速过滤出最相关的匹配，因此我们只需要在这个较小的集合上计算精确得分。这一点非常重要，因为在一个高维向量的超大集合上计算距离，是代价非常高昂（慢）的操作。
上文提到的 FAISS 库提供了多种方式来解决这个问题：
- PCA 降维
- K 均值聚类
- 局部敏感哈希
- 可能还有其他我不知道方法
这些方法中的每一种都能实现高效的索引方法，因此可以快速地筛选出较近邻的文档，然后通过计算精确的距离来查找最近邻文档。在降维以后就可以使用 KD树，聚类或者局部敏感哈希后也可以使用倒排索引。
上图揭示了如何通过过滤数据集来加速计算，需要计算精确距离的文档数与计算时间之间是线性关系；同时也说明了高效地过滤掉不相似文档多么重要。
当然所有这些方法都是有可能在 Elasticsearch 里得到实现的，其优点是便于和其他检索系统集成。届时就可以组合使用关键词查询或其他基于深度学习的查询结果了。
实验表明在我们的数据集上，结合了 PCA 降维后再使用 KD 树索引，能带给我们速度和精度的最佳y组合。
上图揭示了缩小数据集是如何影响结果精确度的。能够看到，过滤得太狠意味着我们会丢失一些最近邻文档；而如果过滤掉 50k 到 75k 的文档，就可以找到所有的最近邻文档，同时计算时间只占暴力计算所有距离的很小一部分。
二、Elasticsearch 插件
在 Lucene 即 Elasticsearch的底层类库中，KD树的数据结构已经实现了，但还没有通过 Elasticsearch 的 API 暴露出来。已经有插件可以计算精确的向量距离，所以我们只需要开发一个小插件来支持使用这种索引结构即可。参见这里：github.com/EikeDehling…
三、集成工作
现在集成工作只是相当于把拼图图片按照正确的顺序拼到一起：
- 安装 Elasticsearch 插件
- PCA降维(Python/sklearn 或者 Java/Smile)
- 索引降维后的完整向量到 Elasticsearch 中（以及其他必要属性）
- 整装待发！
安装插件、创建索引以及添加文档请参考这里(github.com/EikeDehling…)。完成这些步骤后，现在就可以使用我们的嵌入向量了！请注意 pca_reduced_vector 上的范围查询，这才是我们新插件起到的作用。
四、结论
我们展示了如何应用深度学习向量来实现高效的搜索。这一方法适用于想要寻找相似文档而普通关键词查询不够好的任何应用场景。其中的嵌入向量，可以使用诸如 doc2vec 等来实现。
更多内容敬请关注 vivo 互联网技术 微信公众号
注：转载文章请先与微信号：labs2020 联系。
