【Science】谷歌、百度等搜索巨头应该从果蝇身上学习什么？专访解读果蝇算法

来源： science； nautil

作者：弗格森

【新智元导读】 Science 近日以《面向一种基础计算问题的神经网络算法》为题，介绍了一项十分前沿的研究：通过果蝇嗅觉回路，发现了一种一直被人们忽视的搜索算法。通过实验，作者证明，这种算法比起传统的搜索算法，性能提升30%-50%。该研究提供了新的搜索算法进化方式的思考。搜索引擎巨头，不管是国外的谷歌还是国内的百度，或者任何互联网和AI公司，搜索都是一个必须要解决的问题。随着数据库信息和数据来源的爆炸式增长，传统的搜索方法，比如线性搜索，需要突破。

Science 近日以《面向一种基础计算问题的神经网络算法》为题，介绍了一项十分前沿的研究：通过果蝇嗅觉回路，发现了一种一直被人们忽视的搜索算法。通过实验，作者证明，这种算法比起传统的搜索算法，性能提升了30%-50%。

该研究的主要意义有两个，首先，提供了新的搜索算法进化方式的思考。搜索引擎巨头，不管是国外的谷歌还是国内的百度，或者任何互联网和AI公司，搜索都是一个必须要解决的问题。随着数据库信息和数据来源的爆炸式增长，传统的搜索方法，比如线性搜索，需要突破。

另外，AI发展的一个重要突破路径就是对脑科学的研究：了解大脑如何以如此低的能耗，高效地完成令人惊叹的事情，这对AI未来的发展至关重要。在过去的十年左右，人们研对果蝇的大脑展开研究，计算了嗅觉回路不同部位的神经元数量，研究它们的激活特性，并追踪它们的突触之间的联系。这一项新的研究中，作者试图从算法的角度对相关研究成果进行分析，期待能获得洞见。

摘要

相似性搜索（例如，识别数据库中的相似图像或网上的类似文件）是大规模信息检索系统面临的基本计算问题。我们发现果蝇嗅觉通路通过计算机科学算法（称为局部敏感哈希）的变体解决了这个问题。果蝇通路将类似的神经活动模式分配给类似的气味，以便当经历类似的气味时，可以应用从一种气味学习的行为。然而，果蝇算法使用三种不同于传统方法的计算策略。这些策略可以被转换来提高计算相似性搜索的性能。这种观察有助于阐明支持重要感官功能的逻辑，并为解决基本的计算问题提供了一种概念上的新算法。

论文DOI：http://science.sciencemag.org/content/358/6364/793

算法在自然界找到新思想和新工程原则

"问，就会得到; 求，就会发现; 敲, 门就会对你打开"，马太福音七章七节一般被认为是对祷告的回应，但也可以说是关于搜索的力量。搜索已成为信息时代的关键技术之一，助力行业巨头，帮助我们做好日常的琐事。但这不是它的终点，科学家们开始明白，搜索也为自然界的许多能力提供了力量。

Saket Navlakha 在 Salk 生物研究所工作，研究计算机科学理论、机器学习和系统生物学，他和他的同事们将这一领域称之为“自然界的算法”。进化需要算法，正如软件工程师所需要的那样，Navlakha说，因为它“还必须处理建立有效，可靠，低成本的系统，帮助动物和有机体生存”。他的希望是在自然界找到“新思想和新工程原则”，可以被人类科学家和工程师利用。

在上周五发表的一项研究中，Navlakha和同事 Sanjoy Dasgupta 和Charles F. Stevens就是这样做的。他们发现果蝇大脑对于开发相似搜索算法都有一些宝贵的经验教训。 Stevens 一直在研究果蝇的神经回路，特别是他们如何将不同的行为（如接近或躲避）与环境中的气味联系起来。 “当他开始告诉我这件事的时候，”Navlakha说，“我意识到果蝇需要做的就是做类似的搜索。事实证明，在工程领域，这是几乎每一个科技公司都面临的一个非常普遍的问题，“果蝇的解决方案”改善了之前的工作”。

Nautilus专访：果蝇带来的这一个新想法，一直被忽视了

Nautilus采访了 Navlakha ，以下是详细介绍。

1. 果蝇的大脑如何启发更好的搜索算法？

果蝇和一般的计算机科学方法之间的主要区别之一是，计算机科学家通常会把他们的数据，无论是视频，图像或歌曲，做所谓的降维：他们把他们非常高维的对象，尽量多的降维，然后在这个较低维度的空间中寻找相似性。这就像做了一个主要的组件分析，用一个流行的技术来获取一些数据，并尝试绘制它，例如在二维空间，同时仍然保留结构，以便可以更好地形象化。果蝇实际上做的是，它不是将其缩小，而是将尺寸扩大得大得多，并且在高维度空间中创造了一个非常稀疏的点。

图：果蝇嗅觉回路和局部敏感哈希之间的示意图绘制

2. “果蝇扩展了维度”这句话是什么意思？ 假设你有100个人，你想把他们分成若干组。计算机科学家通常的做法是将人挤进一个小房间。它们将会在这个非常低维的空间中造成拥堵。但是现在想象一下，把这100人带到足球场上。确定团队结构将非常容易，因为您可以放置这些人的空间非常多。这就是果蝇正在做的事情。它使用称为“随机投影”（random projection）的方法来实现这一点，这是一种改变数据维度的方法，同时仍然保持数据描述的对象之间的距离。

3. 为什么果蝇的解决方案更加高效？

效率提高正是发生在随机投影发生的地方。这么说可能有点太技术了：通常在计算机科学中，计算随机投影的方式非常昂贵，这是一个高斯随机投影的过程。令人惊讶的是，果蝇也使用了随机投影，但它使用了更有效的随机投影类型：一种稀疏的二进制随机投影。这正是它们在计算上取胜的秘诀。即使果蝇大脑正在使用更多的神经元，由于这种随机投影类型，它的效率要高得多，这意味着果蝇有更多的神经元来表示数据库中的对象。

4. 你是怎么知道果蝇在做这些事？

在过去的十年左右，人们研究了果蝇的大脑，计算了嗅觉回路不同部位的神经元数量，研究它们的激活特性，并追踪它们的突触联系。他们给了我们关于电路每个部分在做什么的见解，然后我们从算法的角度分析。如果我有2000个神经元，那么就意味着每个物体都可以由2000个神经元的不同组合来表示。如果我以计算机科学的方式来做，那么每个对象都将被表示为10或20个神经元的组合。有更多的神经元相当于有这个更大的足球场空间来存储物体。

5. 为什么我们现在还没有一个比果蝇更好的搜索算法？

有一些果蝇正在使用的技巧，我们并没有想到，因为它们有点不直观。通常你会想要减少维度。但果蝇正在引入这个我们没有想到的新想法。自然界的进化已经有很多时间来找出新的策略，或者将它们结合起来的新方法。这是神经科学的目标之一：了解大脑如何以如此低的能耗，高效地完成令人惊叹的事情，以至于今天没有计算机能够与之匹配，也没能够将这些想法转化为机器计算。

6. 除了自然之外，我们对于更好的搜索算法的想法是基于什么的？

解决相似性搜索问题的第一种方法就是逐一去比较你的查询与数据库中的每个项目—— 线性搜索。很长一段时间，这是一个很好的解决方案，因为我们的数据库中只有几千个东西，但是现在我们有数十亿个视频和数百万种产品，我们不能一个一个搜索。这导致了一种叫做KD树的不同类别的算法的发明，在某些情况下，当你有大型数据库但是维数很低的对象时，这种算法是可行的。然后人们说：“这也不现实，我们需要在非常高的维度上做到这一点”，这是过去三十年来研究的一个迭代过程，随着数据的变化，问题的要求也发生了变化，因为我们已经获得了更多的数据。这是多年来发展起来的一个问题，而且我们通过这个解决方案进展缓慢。

果蝇算法与局部敏感哈希综合对比

7. 果蝇的搜索算法比现在常用的方法好多少？

平均来说，它可能要好30-50％。我们采取了一些人们用于评估这个问题的标准基准。我们做了两个图像数据集—不同数量的图像，另一个是自然场景的随机图像 -——然后是一个文档相似性搜索。所有数据集的改进量都是相似的。

8. 对于一个图像搜索来说，我是不是该留意一下响应时间？

响应时间将是相似的，但是性能或算法所暗示的事物的相关程度将会提高。

大脑中局部敏感哈希的比较

9. 果蝇搜索的研究什么时候会在技术中被采用？

这可能会在几个月内发生。我们希望能够在更大的数据集上和其他算法上进行测试，如果一切顺利的话，很快就可以将其转化为技术。