终于，「最近邻搜索」有通用方法了

来源：Quanta Magazine

编译：Bing

如果你打算开一家咖啡馆，你一定想知道：“附近最近的一家咖啡馆在哪？”了解这些信息有助于应对商业竞争。

这种现象是计算机科学中广泛研究的问题，称为“最近邻搜索”。它的问题是，给定数据集和新的数据点，数据集中哪个数据离新数据点最近？这个问题出现的场景非常丰富，可以是基因搜索、图像查询，或者音乐推荐。

但是最近邻问题并不像咖啡馆那么容易解决。过去几十年，很多计算机科学家都在致力于寻找更好的解决办法。与此同时，他们还要解决随之而来的复杂情况，例如不同数据集对“相近”有着不同的定义。

现在，一个五人小组提出了开创性的解决办法，他们在两篇论文中（一篇已于4月发表，另一篇还未出炉）提出了解决复杂数据最近邻问题的通用方法。

麻省理工学院的计算机科学家、最近邻搜索领域的重要任务Piotr Indyk表示：“这是首个用单一算法捕捉大量空间的结果。”

不同的距离

我们已经习惯了用一种方法定义距离，常常会忽视其他方式。通常，我们用“欧几里得距离”测量距离，即在两点之间测量直线的距离。但在有些情况下，这样的测量方式就说不通了。例如在街道网格中，就需要用到“曼哈顿距离”了，直线距离5英里的目的地，可能需要走3英里之后转90°，再继续走4英里才能到达。

另外，还可以用非地理的术语表示距离。比如Facebook上的两名用户、两部电影、两组基因之间的距离怎么计算？在这些问题上，“距离”表示的是两个物体之间的相似程度。

有关距离的测量尺度有很多，例如两组基因，生物学家会用“编辑距离（edit distance）”来比较二者。这样一来，两组基因序列之间的距离就是从一组基因转换到另一组所需要添加、删除、插入、替换的数字。

编辑距离和欧几里得距离是两种完全不同的距离测量方法，二者是不能相互替代的。但是这样的情况对研究最近邻算法的科学家们来说很棘手，能有效计算一种距离的算法在另一种情况下就无法工作了。

在夹缝中求生存

为了找到最近邻，通常所用的方法是将数据分成好几份。假设你的数据就像在牧场中吃草的奶牛，给分散在草场中的牛群画不同的圆圈，现在进来了一头新奶牛，问它会落在哪个圆圈里？可以肯定的是，这头新奶牛的最近邻一定也在这个圈里。

然后重复这一过程，不断进行细分。最终会得到一个只包含两头牛的区域，这样就找到了最近邻。

现在，算法能够完成这一过程，好的算法还会将这一任务完成得又快又好。这里“好”的标准可以理解成，算法不会得出最近邻与新数据不在一个圈子里的结果。

近些年来，科学家们提出了多种分割数据的算法。对于低维数据（即每个数据点仅由少量的值定义，例如牧场中牛的位置），算法在解决最近邻问题时会生成Voronoi图。

对于高维数据（每个数据点可能有成百上千个值），Voronoi图要计算起来就十分费力了。所以科学家们用“局部敏感哈希（LSH）算法”对数据进行分割，这种算法于1998年由Indyk和Rajeev Motwani共同提出。LSH算法是随机对数据进行分类的，这使得它速度很快，但精确度较低。算法最终并不是找到确切的最近邻点，而是告诉你最近邻与已有数据的确切距离。（可以想象成在电影推荐时，推荐结果并不是最佳的，而是那些还不错的。）

上世纪90年代末，计算机科学家们提出的LSH算法以特殊的距离尺度对最近邻问题给出大致的解决方案。这些LSH算法都非常具体，无法通用。

“你可以为欧几里得距离或曼哈顿距离设计非常高效的算法。但是我们没有一种技术能在多种距离上通用，”Indyk说道。

受制于这种困境，科学家们想了一种应变方法：通过嵌入，在没有好的算法的距离标准之上“覆盖”一种距离尺度。但是这样的结果往往不准确，有的时候嵌入根本无法完成。所以他们仍需要想出一种合适的通用方法。

惊人的结果

在这项新研究开始之际，科学家们回过头思考当初具体的最近邻算法追求的目标是什么。他们提出了一个更宽泛的问题：对距离尺度来说，阻碍一款好的最近邻算法出现的原因是什么？

他们想原因可能与在寻找最近邻时复杂的“扩展图（expander graph）”有关。扩展图是一群由线条连接起来的点。这些图都有它们自己的距离尺度，图中两点之间的距离是你从一点到另一点所经过的最少线段。可以将其想象成社交网络中的各种人脉关系。

扩展图有两个明显矛盾的特点：它联系广泛，所以如果想切断与某一点的联系，就要切断之间的线段。但同时，大多数点都和其他的点相连。所以，最终有些点会越来越远。

这样的特征造成的结果是，在扩展图上可以很快地进行最近邻搜索，而将数据点分割的过程可以看成将最近的两点分开。

“任何分割扩展图的方法都会切断很多线，分开很多相近的点，”论文作者之一Waingarten说道。

从左至右：Alexandr Andoni、Ilya Razenshteyn、Erik Waingarten

2016年夏天，Andoni、Nikolov、Razenshteyn和Waingarten认为，是不可能存在对最近邻算法有效的扩展图的。但他们真正想证明的是，好的最近邻算法同样也不存在于其他距离尺度中。

他们证明的方法是在这些距离尺度中嵌入扩展尺度。这样一来，他们可以确定这些尺度有类似扩展图的无法工作的特征。

这四位科学家找到普林斯顿大学的Assaf Naor，他是一名数学家，同时也是计算机科学家，此前的研究非常适合回答有关扩展图的问题。他们询问了有关扩展图嵌入到其他距离类型中的问题，但答案并非所期望的那样，Assaf给出了完全相反的回答。

Naor证明，扩展图并不能嵌入到多种距离尺度中，研究者将这一论断作为基础，接着这个逻辑链条开始思考：如果扩展图不能嵌入到其他尺度，那么一个好的数据分割方法一定存在（因为他们证明扩展图的特征是阻碍良好数据分割的障碍）。因此，良好最近邻算法可能存在。

他们将发现结果写在第一篇论文中，而第二篇论文本月也即将发表。Waingarten表示：“第一篇论文证明了确实存在一种方法能良好地进行数据分割，但没有给出如何快速完成的方案。在第二篇论文中会详细解释。”

同时，这项新研究第一次用通用的方法对高维数据进行最近邻搜索。“任何尺度空间都可以用该算法实现最近邻搜索，”Waingarten说。

原文地址：www.quantamagazine.org/universal-method-to-sort-complex-information-found-20180813/

第一篇论文地址：https://www.ilyaraz.org/static/papers/spectral_gap.pdf