新算法通过模仿神经系统来改进二分匹配

Josiah02

当你要求拼车应用帮你找车时，公司的计算机就开始工作了。它们知道你想快速到达目的地。它们知道你不是唯一需要搭车的用户。它们还知道司机想在附近搭载乘客，以尽量减少空闲时间。冷泉港实验室副教授萨凯特·纳夫拉卡 (Saket Navlakha) 说，计算机的工作是将司机与乘客配对，以最大限度地提高每个人的幸福感。
纳夫拉卡等计算机科学家将此称为二分匹配。器官捐献者与移植候选人、医学院学生与住院医师培训项目以及广告商与广告位的匹配系统处理的任务相同。因此，这是深入研究的主题。
“这可能是计算机科学领域最著名的 10 个问题之一。”Navlakha 说。
现在，他从生物学中找到了更好的方法。纳夫拉卡发现了神经系统连接中的二分匹配问题。在成年动物中，身体的每一根肌肉纤维都与一个控制其运动的神经元配对。然而，在生命早期，每根纤维都是许多神经元的目标。为了让动物有效地运动，必须修剪多余的连接。那么，哪些匹配可以持久呢？
神经系统有一个有效的解决方案。纳夫拉卡解释说，最初连接到同一肌肉纤维的神经元相互竞争以维持匹配，使用神经递质作为“竞标”资源。输掉这场生物拍卖的神经元可以拿走它们的神经递质并竞标其他纤维。这样，每个神经元和纤维最终都会找到一个伙伴。
该示意图说明了身体的运动神经元和肌肉纤维在发育修剪之前（左）和之后（右）是如何连接的。“每个斑点对应一个运动单位，”Navlakha 解释道。“小型运动单位非常活跃，在肌肉收缩期间首先被招募（因为它们的神经元具有较低的激发阈值），并提供较小的力量。大型运动单位不太活跃，最后被招募（因为它们的神经元具有较大的激发阈值），并提供更大的力量。”图片来源：Navlakha 实验室/冷泉港实验室
Navlakha 设计了一种在神经系统之外实现这种匹配策略的方法。“这是一个简单的算法，”他说。“只有两个方程。一是连接到同一纤维的神经元之间的竞争，二是资源的重新分配。”这项工作已发表在《美国国家科学院院刊》上。
与目前最好的二分匹配程序相比，这种受神经科学启发的算法表现非常出色。它能创建近乎最优的配对，并且不会出现未匹配的情况。在日常应用中，这可能意味着拼车乘客的等待时间更短，没有住院医生的医院更少。
Navlakha 指出了另一个优点。新算法保护了隐私。大多数二分匹配系统都要求将相关信息转发到中央服务器进行处理。但在许多情况下——从在线拍卖到捐献器官匹配——分布式方法可能更受欢迎。由于有无数的潜在应用，Navlakha 希望其他人能将新算法应用于他们自己的工具。
他补充道：“这是研究神经回路如何揭示重要人工智能问题的新算法的一个很好的例子。”