从果蝇的搜索算法可以学到什么

一个Sk，我会给你的;寻找，就寻见。叩门，就给你们开门。”马太福音第7节通常被认为是对祷告的评论，但它也可能是关于搜索的力量。搜索已经成为信息时代的关键技术之一，为工业巨头提供动力，帮助我们处理日常琐事。但这并不是终点。科学家们开始认识到，搜索也能在自然界的很多地方发挥作用。

索尔克生物研究所(Salk Institute for Biological Studies)的萨克特·纳夫拉卡(Saket Navlakha)致力于“理论计算机科学、机器学习和系统生物学的结合”，他告诉我，他和同事们把这个领域称为“自然界的算法”。Navlakha说，就像软件工程师一样，进化也需要算法，因为它“还必须建立高效、可靠、低成本的系统，帮助动物和有机体生存。”他希望在自然界中找到可供人类科学家和工程师利用的“新思想和新工程原理”。

在上周五发表的一项研究中，纳夫拉卡和同事桑乔伊·达斯古普塔(Sanjoy Dasgupta)和查尔斯·f·史蒂文斯(Charles F. Stevens)正是这么做的。他们发现果蝇的大脑对任何开发相似性搜索算法的人都有一些宝贵的经验。史蒂文斯一直在研究苍蝇的神经回路，特别是它们如何将不同的行为（如接近或回避）与环境中的气味联系起来。纳夫拉卡说：“当他开始告诉我这件事时，我意识到苍蝇需要做的是类似于相似性搜索的事情。事实证明，在工程领域，这是当今几乎所有科技公司都面临的一个非常普遍的问题。”果蝇对这一问题的解决方案“改进了以前的工作。”

鹦鹉螺跟纳夫拉卡聊了聊结果。

果蝇的大脑如何激发出更好的搜索算法?

果蝇和通常的计算机科学方法的主要区别之一是，计算机科学家通常会获取他们的数据，无论是视频、图像或歌曲，然后进行所谓的降维:他们取高维的物体，试着简化它然后在低维空间中寻找相似之处。这有点像做主成分分析，这是一种流行的技术，取一些数据并试图在二维中绘制它，同时仍然保留结构，这样你可以更好地可视化它。苍蝇实际上所做的，不是缩小它，而是将维度扩展到比原来大得多的地方，并在高维空间中创建一个非常稀疏的点。

苍蝇正在引入我们还没有想到的新想法。

你说的“果蝇扩展维度”是什么意思？

假设你有100个人，你想把他们分成若干组。计算机科学家通常会把人们挤到一个小房间里。他们会被困在这个非常低维的空间里。但是现在想象一下，你把那100个人分散在一个足球场上。对你来说，识别群体结构是非常容易的，因为你可以在很大的空间里安置这些人。苍蝇就是这么做的。它使用一种称为“随机投影”的方法来实现这一点，这种方法可以改变数据的维度，同时仍然保持数据所描述的对象之间的距离。

为什么果蝇解决方案更有效?

效率的增益是随机投影发生的地方。这有点技术性。通常在计算机科学中，计算随机投影的方法是非常昂贵的高斯随机投影，如果你想知道专业术语的话。令人惊讶的是，苍蝇也使用了随机投影，但它使用了一种更有效的随机投影类型:稀疏二进制随机投影。这才是真正的计算胜利。尽管苍蝇的大脑使用了更多的神经元，但由于这种随机投射类型，它的效率要高得多，这意味着苍蝇有更多的神经元来代表它数据库中的对象。

你怎么知道这一切都是果蝇做的?

在过去十年左右的时间里，人们进入果蝇的大脑，计算嗅觉回路不同部分的神经元数量，研究它们的放电特性，并追踪它们的突触连接。它们让我们了解到电路的每个部分在做什么，然后我们从算法的角度进行分析。如果我有2000个神经元，那就意味着每个物体都可以由2000个神经元的不同组合来表示。如果我用计算机科学的方法来做，每个物体都将由10或20个神经元的组合来表示。拥有更多的神经元就相当于拥有更大的足球场空间来存储物体。

为什么我们没有比果蝇更好的搜索算法?

苍蝇正在使用的一些技巧我们只是没有想到使用，因为它们有些不直观。通常，您会希望减少维度。但是苍蝇引入了这个我们根本没有想到的新想法。进化已经花了很多时间来找出新的策略，或是将它们结合起来的新方法。这是神经科学的目标之一：理解大脑是如何以如此低的能量、高效地完成令人惊奇的事情的，这是当今计算机无法比拟的，并且能够将这些想法转化为机器计算。

除了自然，我们对更好的搜索算法的想法是基于什么呢?

解决相似性搜索问题的第一种方法是逐个比较查询与数据库线性搜索中的每个项。在很长一段时间里，这是一个足够好的解决方案，因为我们的数据库中只有几千件东西，但现在我们有数十亿的视频和数百万的产品，我们不能只做一个接一个的搜索。这导致了另一类称为KD树的算法，在某些情况下，当您拥有大型数据库但维度非常低的对象时，这种算法会起作用。然后人们说，“这也不现实，我们需要在非常高的维度上做这件事。”这是一个迭代过程，在过去三十年中进行了研究，因为问题的需求发生了变化，数据发生了变化，我们得到了更多的数据。这是一个多年来不断发展的问题，通过缓慢的进展，我们找到了这个解决方案。

果蝇的搜索算法比主要的方法好多少?

平均来说，它可能会好30%到50%。我们采用了一些人们用于解决这个问题的标准基准。我们做了两个图像数据集，一个是不同数字的图像，另一个是自然场景的随机图像，然后一个文档相似性搜索。它在所有数据集上的改进量是相似的。

我会注意到图像搜索的响应时间有什么不同吗?

响应时间将是相似的，但性能或算法建议的内容的相关性将会提高。

果蝇搜索何时在技术上实现？

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

布莱恩·加拉格尔是《浪漫的事实》的编辑鹦鹉螺博客在推特上关注他@brianga11agher．

观看：数学生物学的吸引力。