专栏首页arxiv.org翻译专栏神经二部匹配(CS ML)
原创

神经二部匹配(CS ML)

图神经网络已经发现在算法空间学习中的应用。但是,从理论计算机科学家的角度来看,现有研究选择的算法(排序,广度优先搜索,最短路径查找等)通常是微不足道的。该报告描述了如何将神经执行应用于复杂算法,例如通过将最大二部匹配简化为流量问题并使用Ford-Fulkerson查找最大流量来找到最大二部匹配。 这仅通过基于单个GNN生成的特征的神经执行来实现。 评估显示出具有很强的概括性结果,其中网络几乎100%的时间都实现了最佳匹配。

原文标题:Neural Bipartite Matching

原文:Graph neural networks have found application for learning in the space of algorithms. However, the algorithms chosen by existing research (sorting, Breadth-First search, shortest path finding, etc.) are usually trivial, from the viewpoint of a theoretical computer scientist. This report describes how neural execution is applied to a complex algorithm, such as finding maximum bipartite matching by reducing it to a flow problem and using Ford-Fulkerson to find the maximum flow. This is achieved via neural execution based only on features generated from a single GNN. The evaluation shows strongly generalising results with the network achieving optimal matching almost 100% of the time.

原文作者:Dobrik Georgiev, Pietro Lió

原文地址:https://arxiv.org/abs/2005.11304

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 基于需求的黑箱反应系统自动化测试(CS)

    本文提出了一种黑箱无功系统一致性测试的新方法。我们将系统规范视为线性时序逻辑公式,将测试生成为输入/输出对序列:输入从对应于规范的Buchi自动机中提取,输出通...

    蔡秋纯
  • 用多结果超编译来控制超级编译程序的大小(CS PL)

    超级编译是一种强大的程序转换技术,有许多有趣的应用。然而,现有的超级编译方法对于生成的程序的大小通常是非常不可预测的。我们考虑了一种基于多结果超编译和特定泛化策...

    蔡秋纯
  • 从功能不确定性传感器到确定性双磁带自动机(CS CC)

    P = NP的问题围绕着有效生产与图灵机验证之间的差异。在本文中,我们研究了有限换能器和自动机的类似问题。每个不确定的有限换能器都定义一个二进制关系,将输入字与...

    蔡秋纯
  • 危重症儿童管理相关政策的初步学习方法(CS AI)

    电子健康记录的增加使得从患者记录中自动提取医疗政策成为可能,以帮助开发临床决策支持系统。我们采用一种强化的统计相关学习(SRL)框架,从临床医院记录中学习概率规...

    RockNPeng
  • 可控PtS TL公式的合成(CS AI)

    在本文中,我们介绍了可控PtS TL公式的合成,在这项工作中,我们开发了一种利用信号时间逻辑(S TL)检测和预防异常问题的方法。 该方法包括两个步骤:检测异常...

    时代在召唤
  • 释义与参照:同一枚硬币的两面(CS.CL)

    我们研究了两种不同的NLP任务之间的潜在协同作用,这两种任务都面临词汇变异性:识别谓词释义和事件共引用解析。首先,我们使用来自事件共参考数据集的注释作为远程监控...

    用户7236395
  • 存在输入延迟的非内省代理同构网络的调节状态同步:无标度协议设计

    本文研究了未知非均匀输入延迟情况下非内省智能体同构网络的调节状态同步问题。无标度协议是在附加信息交换的基础上设计的,它不需要任何有向网络拓扑和相关拉普拉斯矩阵谱...

    非过度曝光
  • 虚拟合成孔径雷达:基于深度学习的斑点噪声抑制算法的综合数据集(CS CV)

    合成孔径雷达(SAR)图像包含了大量的信息,但由于图像中存在斑点噪声,实际应用情况有限。近年来,基于深度学习的方法在去噪和图像恢复领域取得了显著的进步。然而,由...

    Elva
  • 自主舰队的分布式多目标跟踪(CS RO)

    我们提出了一种基于乘法器交替方向方法的可扩展分布式目标跟踪算法,该算法非常适合通过车对车网络进行通信的自动驾驶车队。 每个感测车辆与其邻居通信以执行类似卡尔曼滤...

    时代在召唤
  • 古典法国剧院放词和POS标签的语料库和模型(CS CL)

    本文介绍了为法国古典文学建立带注释的语料库和训练模型的过程,重点是戏剧,尤其是诗歌中的喜剧。它最初是作为在Cafiero和Camps [2019]中进行的笔势分...

    刘子蔚

扫码关注云+社区

领取腾讯云代金券