图片搜索在 Dropbox 中的工作原理

照片是 Dropbox 中最常见的文件类型之一，但按文件名搜索照片的效率甚至低于基于文本的文件。当您从几年前的野餐中寻找那张照片时，您肯定不记得相机设置的文件名是2017-07-04 12.37.54.jpg。

相反，您会查看单张照片或它们的缩略图，并尝试识别与您要搜索的内容相匹配的对象或方面 - 无论是恢复您存储的照片，还是在公司的档案中发现新广告系列的完美镜头。如果 Dropbox 可以为您仔细研究所有这些图像，并指出那些与您口述的几个描述性单词最匹配的图像，那不是很好吗？这几乎就是我们的图像搜索所做的。

“野餐”的图片内容搜索结果

在这篇文章中，我们将基于机器学习技术描述我们的图像内容搜索方法背后的核心思想，然后讨论我们如何在Dropbox的现有搜索基础设施上构建高性能的实现。

我们的方法

下面是陈述图像搜索问题的简单方法：查找一个相关性函数，该函数采用（文本）查询 q 和图像 j，并返回相关性分数 s，指示图像与查询的匹配程度。

s = f（q， j）

给定此功能，当用户进行搜索时，我们会对其所有图像运行该搜索，并返回那些产生高于阈值的分数的图像，按其分数排序。我们使用机器学习中的两个关键发展来构建这个函数：准确的图像分类和词向量。

图像分类
图像分类器读取图像并输出描述其内容的类别评分列表。分数越高，表示图像属于该类别的可能性越高。

类别可以是：

• 图像中的特定对象，例如树或人物
• 整体场景描述符，如户外或婚礼
• 图像本身的特征，例如黑白或特写

在过去的十年中，使用卷积神经网络的图像分类取得了巨大进步，从Krizhevsky等人在2012年ImageNet挑战赛上的突破性结果开始。从那时起，随着模型架构的改进，更好的训练方法，像Open Images或ImageNet这样的大型数据集，以及像TensorFlow和PyTorch这样易于使用的库，研究人员已经构建了可以识别数千个类别的图像分类器。

看看当今图像分类的工作原理：

典型未暂存照片的图像分类器输出

图像分类使我们能够自动了解图像中的内容，但这本身并不足以启用搜索。当然，如果用户搜索海滩，我们可以返回该类别得分最高的图像，但是如果他们搜索海岸呢？如果他们不是苹果，而是寻找水果或奶奶史密斯呢？

我们可以整理一个包含同义词和近同义词以及单词之间层次结构关系的大型字典，但这很快就会变得笨拙，特别是如果我们支持多种语言。

所以让我们重新构建这个问题。我们可以将图像分类器的输出解释为向量j_c每个类别的分数。此向量将图像的内容表示为 C 维类别空间中的一个点，其中 C 是类别数（几千个）。如果我们能够在此空间中提取查询的有意义的表示形式，则可以将图像向量与查询向量的接近程度解释为图像与查询匹配程度的度量。

幸运的是，提取文本的向量表示是自然语言处理领域大量研究的重点。该领域最着名的方法之一在Mikolov等人2013年的word2vec论文中有所描述。Word2vec 为字典中的每个单词分配一个向量，这样具有相似含义的单词将具有彼此接近的向量。这些向量位于 d 维词向量空间中，其中 d 通常为几百个。

我们只需查找搜索查询的 word2vec 向量即可获得其向量表示。此向量不在图像分类器向量的类别空间中，但我们可以通过引用图像类别的名称将其转换为类别空间，如下所示：

1. 对于查询词 q，获取 d 维词向量q_w，归一化为单位向量。我们将对词空间中的向量使用 w 下标，对类别空间中的向量使用 c 下标。
2. 对于每个类别，获取类别名称的规范化词向量c^我_w.然后定义米^我 =q_w·c^我_w，查询向量和第 i 个类别向量之间的余弦相似性。此分数介于 -1 和 1 之间，指示查询词与类别名称的匹配程度。通过将负值剪切为零，以便m^我= 最大值（0，米^我），我们得到的分数与图像分类器输出的范围相同。
3. 这让我们计算q_c = [m¹m²...m^C]，C 维类别空间中的一个向量，它表示查询与每个类别的匹配程度，就像每个图像的图像分类器向量表示图像与每个类别的匹配程度一样。

步骤 3 只是一个向量矩阵乘法，q_c = q_wC，其中 C 是矩阵，其列是类别词向量c^我_w.

将查询映射到类别空间向量后q_c，我们可以将其与每个图像的类别空间向量的余弦相似性取为图像的最终相关性分数，s = q_cj_c.

这是我们的相关性函数，我们按此分数对图像进行排名以显示查询结果。将此函数应用于一组图像也可以表示为向量矩阵乘法，s = q_cJ，其中 J 的每列都是分类器输出向量j_c对于图像，s 是所有图像的相关性分数的向量。

示例

让我们看一个只有几个维度的例子，其中词向量只有三个维度，分类器只有四个类别：苹果，海滩，毯子和狗。

假设用户已搜索岸上。我们查找词向量以获得 [0.35 -0.62 0.70]，然后乘以类别词向量矩阵以将查询投影到类别空间中。

由于海岸词向量靠近海滩词向量，因此此投影在海滩类别中具有较大的值。

将查询词向量投影到类别空间中

建模细节
我们的图像分类器是在OpenImages数据集上训练的PrestificNet网络。它为大约8500个类别生成分数。我们发现，这种架构和数据集以合理的成本提供了良好的准确性，如果我们想为 Dropbox 规模的客户群提供服务，这一点很重要。

我们使用TensorFlow来训练和运行模型。我们使用预先训练的概念网数字批处理词向量。这些给出了很好的结果，对我们来说重要的是，它们支持多种语言，为具有相似含义的不同语言中的单词返回相似的向量。这使得支持多种语言的图像内容搜索变得容易：英语中dog和法语中的chien的单词向量相似，因此我们可以支持两种语言的搜索，而无需执行显式翻译。

对于多词搜索，我们将查询解析为单个单词的 AND。我们还维护了一个多词术语列表，例如沙滩球，可以将其视为单个单词。当查询包含这些术语之一时，我们执行备用解析并运行两个已解析查询的 OR - 查询沙滩球变为（沙滩球）或（沙滩球）。这将匹配大型，彩色，充气球和沙子中的网球。

生产架构

每当用户进行搜索时，获取完整的，最新的J矩阵是不切实际的。用户可能有权访问数十万甚至数百万张图像，并且我们的分类器输出是数千个维度，因此此矩阵可能包含数十亿个条目，每当用户添加，删除或修改图像时都需要更新。这根本无法为数亿用户（尚未）进行经济规模扩展。

因此，我们不是为每个查询实例化J，而是使用上述方法的近似值，该方法可以在Dropbox的Nautilus搜索引擎上有效实现。

从概念上讲，Nautilus由一个正向索引组成，该索引将每个文件映射到某些元数据（例如文件名）和文件的全文，以及一个倒排索引，该索引将每个单词映射到包含该单词的所有文件的发布列表。对于基于文本的搜索，一些配方文件的索引内容可能如下所示：

用于基于文本的搜索的搜索索引内容

如果用户搜索白葡萄酒，我们会在倒排索引中查找这两个单词，发现doc_1和doc_2同时包含这两个单词，因此我们应该将它们包含在搜索结果中。Doc_3只有一个单词，所以我们应该把它省略掉，或者把它放在结果列表中的最后一个。

找到可能要返回的所有文档后，我们会在正向索引中查找它们，并使用那里的信息对它们进行排名和筛选。在这种情况下，我们的排名可能doc_1高于doc_2因为这两个词彼此相邻。

重新调整文本搜索方法的用途以进行图像搜索
我们可以使用相同的系统来实现我们的图像搜索算法。在正向索引中，我们可以存储类别空间向量 j_c 每个图像。在倒排索引中，对于每个类别，我们存储一个具有该类别正分的图像的发布列表。

搜索索引内容以进行图像内容搜索

因此，当用户搜索野餐时：

1. 查找单词向量q_w用于野餐并乘以类别空间投影矩阵C得到q_c如上所述。C是一个固定的矩阵，对所有用户都是一样的，所以我们可以把它放在内存中。
2. 对于在 中具有非零条目的每个类别q_c，从倒排索引中提取过帐列表。这些列表的并集是匹配图像的搜索结果集，但这些结果仍然需要排名。
3. 对于每个搜索结果，获取类别空间向量j_c从正向索引乘以q_c以获取相关性分数 s。返回分数高于阈值（按分数排名）的结果。

针对可扩展性
进行优化 这种方法在存储空间和查询时处理方面仍然很昂贵。如果我们有 10，000 个类别，那么对于每个图像，我们必须在正向索引中存储 10，000 个分类器分数，如果我们使用四字节浮点值，则成本为 40 KB。由于分类器分数很少为零，因此典型图像将被添加到这10，000个帖子列表中的大多数。如果我们对映像 ID 使用四字节整数，则另外为 40 KB，每个映像的索引开销为 80 KB。对于许多图像，索引存储将大于图像文件！

至于查询时间处理 - 它对执行搜索的用户显示为延迟 - 我们可以预期大约一半的查询类别匹配分数米^我为了积极，因此我们将从倒排索引中读取大约5，000个发布列表。这与文本查询相比非常糟糕，文本查询通常读取大约十个发布列表。

幸运的是，我们可以丢弃许多接近零的值，以获得更有效的近似值。上面给出了每张图片的相关性分数，如下所示 = q_cj_c哪里q_c保存查询与大约 10，000 个类别中的每一个类别之间的匹配分数，以及j_c保存来自分类器的大约 10，000 个类别分数。这两个向量主要由接近零的值组成，对 s 的贡献很小。

在我们的近似值中，我们将设置除以下几个条目之外的所有条目q_c和j_c为零。通过实验，我们发现保留q_c和前 50 个条目j_c足以防止质量下降。存储和处理节省是可观的：

• 在正向索引中，而不是10，000维密集向量中，我们存储具有50个非零条目的稀疏向量 - 每个图像的前50个类别分数。在稀疏表示中，我们存储每个非零条目的位置和值;50 个双字节整数位置和 50 个四字节浮点值大约需要 300 个字节。
• 在倒排索引中，每个图像被添加到 50 个发布列表而不是 10，000 个，成本约为 200 个字节。因此，每个映像的总索引存储为 500 字节，而不是 80 KB。
• 在查询时，q_c有 10 个非零条目，因此我们只需要扫描 10 个发布列表 — 与文本查询的工作量大致相同。这给了我们一个更小的结果集，我们也可以更快地得分。

通过这些优化，索引和存储成本是合理的，并且查询延迟与文本搜索的延迟相当。因此，当用户启动搜索时，我们可以并行运行文本和图像搜索，并一起显示完整的结果集，而不会使用户等待比纯文本搜索更长的时间。

当前部署

目前，我们所有的专业级和企业级用户都启用了图像内容搜索。我们将一般图像的图像内容搜索、基于 OCR 的文档图像搜索和文本文档的全文搜索相结合，通过基于内容的搜索，使大多数用户的文件可用。

视频搜索？
当然，我们正在努力让您搜索所有 Dropbox 内容。图像搜索是朝着这一目标迈出的一大步。最终，我们希望能够搜索视频内容。在视频中查找一帧的技术，或者通过改编静止图像技术来索引整个剪辑以进行搜索的技术仍处于研究阶段，但就在几年前，“找到我野餐的所有照片，其中有我的狗”只在好莱坞电影中起作用。

我们的目标是：如果它在您的 Dropbox 中，我们会为您找到它！