导语


在解决实际问题时，算法面临两个关键问题：如何获取所需的特定输入以及如何提高数据效率。而深度学习方法在处理自然输入和灵活计算方面具有优势。近年来，将深度学习方法与算法相结合成为一个新兴的问题领域。这种结合一方面可以提高算法的求解效率和解的质量，另一方面可以增强深度学习方法的推理能力和泛化性。在本次分享中，我们将一起探讨几种将算法与深度学习方法结合的实现途径。


为了探讨图神经网络在算法神经化求解的发展与现实应用，集智俱乐部联合国防科技大学系统工程学院副教授范长俊、中国人民大学高瓴人工智能学院助理教授黄文炳，共同发起「图神经网络与组合优化」读书会。读书会将聚焦于图神经网络与算法神经化求解的相关领域，包括神经算法推理、组合优化问题求解、几何图神经网络，以及算法神经化求解在 AI for Science 中的应用等方面，希望为参与者提供一个学术交流平台，激发参与者的学术兴趣，进一步推动相关领域的研究和应用发展。读书会从2023年6月14日开始，每周三晚 19:00-21:00 举行，持续时间预计8周。欢迎感兴趣的朋友报名参与！





分享内容简介




算法是组合推理的一种纯粹的形式，和计算模型无关，与任何形式的感知无关。但算法在用于解决实际问题时，存在两个无法避免的问题：如何获得算法所需的特定输入，以及如何提高算法的数据效率？深度学习方法能够更好的处理自然输入，也能对数据进行更灵活的计算。但深度学习方法目前大多用于解决感知型任务，其推理能力依然存疑。

考虑将深度学习方法与算法进行结合，是近年来新兴的问题领域。借助深度学习方法，可以提高算法的求解效率以及解的质量；借助算法的推理过程，可以提高深度学习方法的推理能力以及泛化性。

本次分享将与大家共同探讨将算法与深度学习方法结合的几种实现途径，包括使用神经网络学习经典算法执行过程、使用Transformer解决推理任务，以及算法求解器的神经求解等。





分享内容大纲




  • 神经算法推理的蓝图
  • 图神经算法推理及CLRS-30介绍
  • 一种通用的图神经算法推理器
  • 对偶算法推理及其在脑血管数据集上的应用
  • 使用Transformer解决推理型任务

  • 在神经网络中加入离散求解器模块





开放问题




我们到时候会依据具体分享时间，现场决定是否对这些问题进行开放讨论。

1.神经算法推理的不可替代性如何体现？用神经网络执行经典算法，无论模型性能多么突出，得到的结果都是近似解，和算法本身得到的精确解相比还存在不小差距。因此，是否存在传统算法无法解决只能依靠神经算法推理解决的杀手级应用呢？

2.神经算法推理的发展方向是什么？目前算法推理的主流方向是面向多任务处理，设计通用的算法处理器。理论上，设计多任务模型需要预先确定算法共享的子例程；实践中，往往没有必要去建立一个处理多任务的模型，生活生产中更倾向于通过充分训练，建立一个SOTA的单任务算法模型。因此，目前多任务的算法推理是否是必要的发展呢？





主讲人介绍




刘佳玮，北京邮电大学博士研究生，主要研究方向为图数据挖掘与机器学习。


韩瑞，中国科学院软件研究所硕士研究生，目前二年级在读，主要研究方向为自动推理与约束求解。


刘明昊，中国科学院软件研究所博士研究生，主要研究方向为自动推理与约束求解，以及符号推理与机器学习的融合方法，部分研究成果发表于AAAI, IJCAI, CP, SAT, JAIR等国际会议和期刊。


贾富琦，中国科学院软件研究所博士研究生，主要研究方向为自动推理与约束求解，部分研究成果发表于ISSTA, AAAI等国际会议和期刊。





主持人




张柄旭，国防科技大学系统工程学院2021级硕士研究生，师从刘忠教授和范长俊副教授，研究方向为图神经网络与组合优化。





主要涉及到的参考文献




  • （重点解读）Veličković P., Blundell C.. Neural algorithmic reasoning, 2021, 2(7): 100273
这篇文章提出神经算法推理的概念，通过用深度学习方法更好地模仿算法，让深度学习实现算法的高度可泛化性，同时保留对问题的最优解。

  • （重点解读）Ibarz B., Kurin V., Papamakarios G.. A generalist neural algorithmic learner, 2022, 2: 1-2: 23
这篇文章提出一个通用的神经算法推理器，该模型依赖单一参数集的GNN，能够同时学习诸如排 序、搜索、贪心算法、动态规划、图算法、字符串排序和几何算法等经典算法任务，并且达到专家 模型的平均水平。

  • （重点解读）Keyulu Xu, Jingling Li, Mozhi Zhang, et al. What Can Neural Networks Reason About?. arXiv:1905.13211, 2020
这篇文章引入了算法对齐的概念，这一概念构成了神经算法推理的核心思想。

  • （重点解读）Numeroso Danilo, Bacciu Davide, Veličković Petar. Dual algorithmic reasoning. arXiv:2302.04496, 2023
利用问题底层的对称性，使用多任务学习来增强学习的效果，具体在最大流问题上做了研究。

  • （重点解读）Yang Zhun, Ishay Adam, Lee Joohyung. Learning to Solve Constraint Satisfaction Problems with Recurrent Transformer, 2022
使用recurrent transformer跨膜态（图片、文本）的数独问题求解。

  • Rasmus Palm, Ulrich Paquet, and Ole Winther. Recurrent relational networks. In Proceedings of Advances in Neural Information Processing Systems, pp. 3368–3378, 2018.
对标方法(baseline): RRN

  • Po-Wei Wang, Priya L Donti, Bryan Wilder, and Zico Kolter. SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. In Proceedings of the 35th International Conference on Machine Learning (ICML), 2019.
对标方法(baseline): SATNet

  • Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16×16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.11929, 2020.
模型基础: 视觉Transformer

  • Zhun Yang, Joohyung Lee, and Chiyoun Park. Injecting logical constraints into neural networks via straight-through estimators. In International Conference on Machine Learning, pp. 25096–25122. PMLR, 2022.
离散约束的应用: 使用STE评估指标来让离散约束可微

  • （重点解读）Sahoo Subham Sekhar. Backpropagation through combinatorial algorithms: Identity with projection works. arXiv:2205.15213, 2022

对于同时需要“感知”和“推理”两种能力的复杂任务，当前的深度学习并不能很好地解决。部分研究人员试图引入离散求解器负责完成推理部分，但如何将求解器和神经网络两个模块耦合起来，则成为一个重要的挑战。已有工作提出可以为离散求解器构造称为blackbox backpropagation (BB)的近似梯度，从而能够训练这种特殊的网络。本文在此基础上进一步提出了几种改进策略：一是提出identity近似梯度，使得计算梯度无需再调用求解器；二是通过人工对数据做投影，可以提升训练效果；三是对数据附加随机噪声，从而增强模型的鲁棒性。





主要涉及的前置知识




 • 图神经网络(GNN)
 • 最大流问题
最大流问题（Maximum Flow Problem）是图论中的一个经典问题，用于计算在一个有向图中从源节点到汇节点能够传输的最大流量。
在最大流问题中，我们考虑一个有向图，其中每条边都有一个容量限制，表示该边能够传输的最大流量。图中有一个源节点（source）和一个汇节点（sink），我们的目标是找到从源节点到汇节点的最大流量，同时满足每条边的容量限制。

 • Ford-Fulkerson算法
解决最大流问题的经典算法是Ford-Fulkerson算法，该算法通过不断地寻找增广路径来增加流量，直到无法找到增广路径为止。增广路径是指一条从源节点到汇节点的路径，一般由广度搜索得到其最短路径，其上所有边的剩余容量大于0。Ford-Fulkerson算法使用一个辅助的残余图来记录每条边的剩余容量，并通过反向边来表示逆流。
在每次找到增广路径后，算法通过沿该路径增加流量来更新图的状态。重复这个过程直到无法找到增广路径为止，此时得到的流量即为最大流量。

 • Transformer 
Transformer由论文《Attention is All You Need》提出，现在是谷歌云TPU推荐的参考模型。它采用了encoder-decoder的架构，并且通过attention机制提升了长距离“记忆”能力。

 •RNN难以并行. https://zhuanlan.zhihu.com/p/368592551

 •Transformer. https://zhuanlan.zhihu.com/p/338817680

 •Mask的机制. https://ifwind.github.io/2021/08/17/Transformer相关——（7）Mask机制

 •Attention的本质. https://zhuanlan.zhihu.com/p/379722366

•Self-attention. https://speech.ee.ntu.edu.tw/~hylee/ml/2021-spring.php

•Recurrent Transformer. https://zhuanlan.zhihu.com/p/598526793




直播信息




时间：
2023年7月5日（本周三）晚上20:00-22:00

参与方式：

扫码参与图神经网络与组合优化读书会，加入群聊，获取系列读书会回看权限，成为图神经网络社区的种子用户，与社区的一线科研工作者与企业实践者沟通交流，共同推动图神经网络社区的发展。


集智学园最新AI课程，

张江教授亲授：第三代人工智能技术基础

——从可微分编程到因果推理


自1956年“人工智能”诞生于达特茅斯会议以来，已经经历了从早期的以符号推理为主体的第一代人工智能，和以深度神经网络、机器学习为主体的第二代人工智能。ChatGPT的横空出世、生成式AI的普及、AI for Science等新领域的突破，标志着第三代人工智能的呼之欲出。可微分编程、神经微分方程、自监督学习、生成式模型、Transformer、基于图网络的学习与推理、因果表征与因果推断，基于世界模型的强化学习……，所有这些脱胎于前两代人工智能的技术要素很有可能将构成第三代人工智能的理论与技术的基础。


本课程试图系统梳理从机器学习到大语言模型，从图神经网络到因果推理等一系列可能成为第三代人工智能基础的技术要素，为研究者或学生在生成式AI、大模型、AI for Science等相关领域的学习和研究工作奠定基础。


https://campus.swarma.org/course/5084?from=wechat


AI+Science 读书会


AI+Science 是近年兴起的将人工智能和科学相结合的一种趋势。一方面是 AI for Science，机器学习和其他 AI 技术可以用来解决科学研究中的问题，从预测天气和蛋白质结构，到模拟星系碰撞、设计优化核聚变反应堆，甚至像科学家一样进行科学发现，被称为科学发现的“第五范式”。另一方面是 Science for AI，科学尤其是物理学中的规律和思想启发机器学习理论，为人工智能的发展提供全新的视角和方法。

集智俱乐部联合斯坦福大学计算机科学系博士后研究员吴泰霖（Jure Leskovec 教授指导）、哈佛量子计划研究员扈鸿业、麻省理工学院物理系博士生刘子鸣（Max Tegmark 教授指导），共同发起以“AI+Science”为主题的读书会，探讨该领域的重要问题，共学共研相关文献。读书会从2023年3月26日开始，每周日早上 9:00-11:00 线上举行，持续时间预计10周。欢迎对探索这个激动人心的前沿领域有兴趣的朋友报名参与。


详情请见：
人工智能和科学发现相互赋能的新范式：AI+Science 读书会启动


图神经网络与组合优化读书会启动


现实世界中大量问题的解决依赖于算法的设计与求解。传统算法由人类专家设计，而随着人工智能技术不断发展，算法自动学习算法的案例日益增多，如以神经网络为代表的的人工智能算法，这是算法神经化求解的缘由。在算法神经化求解方向上，图神经网络是一个强有力的工具，能够充分利用图结构的特性，实现对高复杂度算法的高效近似求解。基于图神经网络的复杂系统优化与控制将会是大模型热潮之后新的未来方向。

为了探讨图神经网络在算法神经化求解的发展与现实应用，集智俱乐部联合国防科技大学系统工程学院副教授范长俊、中国人民大学高瓴人工智能学院助理教授黄文炳，共同发起「图神经网络与组合优化」读书会。读书会将聚焦于图神经网络与算法神经化求解的相关领域，包括神经算法推理、组合优化问题求解、几何图神经网络，以及算法神经化求解在 AI for Science 中的应用等方面，希望为参与者提供一个学术交流平台，激发参与者的学术兴趣，进一步推动相关领域的研究和应用发展。读书会从2023年6月14日开始，每周三晚 19:00-21:00 举行，持续时间预计8周。欢迎感兴趣的朋友报名参与！

详情请见：
加速经典算法效率，突破现实技术瓶颈：图神经网络与组合优化读书会启动



点击“阅读原文”，报名直播