0
| 本文作者： AI研习社-译站 | 2018-07-30 15:01 |
雷锋网按：本文为 AI 研习社编译的技术博客，原标题 Detecting image similarity using Spark, LSH and TensorFlow，作者为 Andrey Gusev（Pinterest 工程师，内容质量分析师）。
翻译 | 沈波 张天航 校对 | 余杭 整理 | 凡江
作为一个视觉数据处理平台，拥有从海量图片中学习并理解其内容的能力是非常重要的。为了检测几近重复的相似图片，我们使用了一套基于 Spark 和 TensorFlow 的数据流处理系统——NearDup。这套系统的核心由一个使用 Spark 实现的批量化 LSH（locality-sensitive hashing，局部敏感哈希）搜索器和一个基于 TensorFlow 的分类器构成。这个数据流处理系统每天能够比较上亿个分析对象，并渐进式地完成各个图像类别的信息更新。在本文中，我们将讲解如何使用这项技术更好地理解海量图片内容，从而使得我们产品前端界面的推荐内容和搜索结果具有更高的信息准确性、更大的数据密度。
简介
我们将我们图片库中的所有图片划分为不同的图片类，每一类都由几近相同（以人类观察员的判断为标准）的图片组成。这种分类标准有一定的主观性，为了给你一个感性认识，下图展示了一些按照 NearDup 阈值进行图片分类的例子。注意，这些相似图片不一定来自同一图像源（参见右下图），也不一定有相同的背景（参见左下图）。同时，图像中可能包含一定的几何扭曲（参见左上图），或者旋转、剪切和翻转变化（见中心图和右上图）。
为图片库中的所有图片进行分类与划分的过程在数学上无法进行严格定义与求解，这是因为在 NearDup 系统中，图片之间的关系不具有传递性和相等性。为了说明这一点，我们可以想象将一张「猫」的图片通过 1000 步慢慢地形变为一张「狗」的图片的过程。容易推断，每一步微小形变前后的两张图片的相似度都将落入 NearDup 的阈值，从而将它们判断为「相似」图片。然而，究竟该将这一串前后相似的图片序列划分为哪几类？猫类，狗类，还是猫-狗类？为了解决这一问题，我们将问题模型转化为图：图的节点代表图片，边代表相应图片间的相似度。随后我们结合传递闭包法（ transitive closure ）和贪婪 k-cut 算法来最小化图的 k-cut 划分，从而近似求解整个图片库的最优划分。
使用批量化 LSH 进行数据预处理
嵌入和 LSH 对象
为了理解图片内容，我们将图片转换到一个嵌入向量空间（embedded vector space）中。这些图嵌入向量是图片的一种高维向量表示，能够抓取图片的视觉和语义相似性。它们一般通过神经网络架构如 VGG16 或 Inception 等处理生成。为了在 NearDup 系统中处理图片关系并对图片库进行分类，我们每天要比较几千万张新图片，并将它们分类到上亿个图片类别中。如果没有优化措施，如此大规模的近邻搜索（nearest neighbor search）问题的时间复杂度为平方（quadratic）复杂度，相应的计算时间将正比于甚至超过 10 个 quadrillion 秒（1 后面 16 个 0！）。为此，我们通过将图嵌入向量进一步缩减为 LSH 对象的方法，显著缩小了问题规模，降低了处理难度。
LSH 是一种先进的数据降维技术，降维前后数据点之间的距离关系保持不变。原向量空间首先通过随机投影法（random projection）和位抽样 LSH（bit sampling LSH）法进行一定的降维。随后，我们继续将所得到的向量位分组为多个 LSH 对象，分组过程有效地权衡了检测准确率和计算时间这一矛盾体。分组越精细，进行最近邻搜索的计算复杂度将越高，但检测准确率也将越高。这里，我们使用 LSH 对象之间的 Jaccard 重合度来近似表示原向量空间中相应向量间的余弦相似度。
批量 LSH 搜索
当所有图片都用一组 LSH 对象表示之后，我们继续为它们建立反向索引，并实现对所有图片的批量查询与搜索。从顶层看，我们通过函数式转换法（functional transformation）、压缩式反向索引与连接法（compressed inverted indexes and joins）等方法的结合，来实现对所有图片的一次性批量查询与比较。这个数据流处理过程是用 Spark 实现的，并需要借助一系列的优化措施来进一步保证这些海量数据能够转化到尽量简单有效地的LSH 对象空间中进行处理。我们所使用到的主要优化措施包括：
字典编码（ Dictionary encoding ） 使得所有数据都用具有最短宽度的数值进行表示
可变字节编码（ Variable byte encoding ） 被用于所有的反向索引
索引切分（ Index partitioning ） 提高了反向索引的平衡性
基于代价的优化器（ Cost-based optimizer ） 能够检测嵌入向量空间的密度，并计算最优的运行时参数
原始数据堆排（ Primitive data packing ） 进一步提高了内存使用率
Jaccard 重合度计数（ Jaccard overlap counting ） 基于低层次、高性能的数据收集实现
去堆化（ Off heaping ） 减少了垃圾回收（GC）过载
使用迁移学习的候选选择
批量化LSH是产生高查全率（召回率）同时又能最小化计算成本的一个很效果的方法。但是，它通常不会对候选项产生最优的查准率（准确率）和排序。我们通过使用一个有监督的分类器去挑选那些NearDups 认为足够相似的候选项。这个分类器是一个迁移学习在视觉嵌入上的例子。它使用了Tensorflow 前馈网络和一个 Adam 优化器 。我们已经在超过包含10亿不同对图像的样本集中训练了分类器。训练集由决策树分类器在SURF 视觉特征上的输出得到，并进行了几何验证，然后用于NearDup 系统的先前迭代。为了提高学习和每一对图像的收敛性，将 hamming 码字节进行异或运算后输入到输入层。该分类器被调整到很高的准确率并且在人类标记的样本上达到了 99% 以上准确率。
SparkContext 也可以对训练过的网络进行推断。使用 mapPartitions 和分组范式，我们可以使用预定义好尺寸的大批数据去有效地向量化和减少开销。在一个拥有1000万个参数的网络中，我们在一个r3.8xlarge 的机器集群上实现了平均2ms进行一个预测的速率。
结论
NearDup 检测需要进行计算代价很高的两两比较。通过在Spark 中使用批处理LSH实现，我们通过跳过不太相似的图像对大大降低了计算的复杂度。Spark-based 的实现结合了高效的工作负载分配和低层次的优化，以最小化内存和CPU占用。随后的调优步骤使用了一个有监督的前馈网络来选择和排序高于NearDup 相似性阈值的图相对。Spark 和Tensorflow 的推断结合使用了分布式计算和每个内核矢量化的最佳特性，实现了高吞吐量和低延迟的预测。然后，将这两个步骤的结果用于集群图像，每天帮助提供数百亿的搜索结果和在Pinterest 上的推荐。
欲了解更多关于这个问题的信息，请看我在 Spark+AI Summit 2018 的演讲。https://vimeo.com/274629687
致谢：感谢以下团队成员对本项目的所有贡献：Jiajing Xu, Vitaliy Kulikov, Jooseong Kim, Peter John Daoud, Andrew Zhai, Matthew Fang, Kevin Lau, Jacob Hanger, Zhuoyuan Li and Chao Wang
号外号外~
一个专注于
AI技术发展和AI工程师成长的求知求职社区
诞生啦！
欢迎大家访问以下链接或者扫码体验
https://club.leiphone.com/page/home
雷锋网雷锋网
雷峰网原创文章，未经授权禁止转载。详情见转载须知。
