社区所有版块导航
Python
python开源   Django   Python   DjangoApp   pycharm  
DATA
docker   Elasticsearch  
aigc
aigc   chatgpt  
WEB开发
linux   MongoDB   Redis   DATABASE   NGINX   其他Web框架   web工具   zookeeper   tornado   NoSql   Bootstrap   js   peewee   Git   bottle   IE   MQ   Jquery  
机器学习
机器学习算法  
Python88.com
反馈   公告   社区推广  
产品
短视频  
印度
印度  
Py学习  »  机器学习算法

组合优化问题的机器学习求解丨图神经网络与组合优化读书会·周六直播

集智俱乐部 • 1 年前 • 448 次点击  


导语


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


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






分享内容简介




本次报告会介绍机器学习求解组合优化问题,特别是图上的组合优化问题,如最小节点覆盖问题、网络瓦解问题、自旋玻璃基态求解问题的一些进展,包括基于自回归的方法和基于非自回归的方法。同时也会介绍一些其他有意思的进展,如如何提高模型的泛化能力、如何与成熟求解器结合、如何处理更自然的输入等。




分享内容大纲




1.组合优化(Combinatorial Optimization ,CO)和ML4CO
2.图上的组合优化问题求解

3.一些有趣的研究进展





主要涉及到的前置知识




  • 组合优化问题(Combinatorial Optimization Problem)

集智百科:https://wiki.swarma.org/index.php/%E7%BB%84%E5%90%88%E4%BC%98%E5%8C%96

  • 图神经网络(Graph Neural Network)

  • 强化学习(Reinforcement Learning)

  • 旅行商问题(Travelling Salesman Problem)

维基百科:https://en.wikipedia.org/wiki/Travelling_salesman_problem

  • 最小节点覆盖(Minimum Vertex Cover)

科普文章:http://www.tastones.com/stackoverflow/dynamic-programming/solving-graph-problems-using-dynamic-programming/minimum_vertex_cover/

  • 网络瓦解(Network Disintegration)





主讲人介绍




范长俊国防科技大学系统工程学院副教授。研究方向包括图深度学习、组合优化、强化学习及其在智能决策、复杂系统和指挥控制中的应用。以第一作者或通讯作者在Nature Machine Intelligence、Nature Communications、AAAI等顶级期刊和会议发表论文多篇。





主要涉及到的参考文献




1.Khalil E, Dai H, Zhang Y, et al. Learning combinatorial optimization algorithms over graphs[J]. Advances in neural information processing systems, 2017, 30.

这篇文章探讨了组合优化问题的一般形式,提出了一种使用自回归方式学习图上组合优化问题的求 解算法。
GitHub代码:https://github.com/Hanjun-Dai/graphnn
知乎介绍:https://zhuanlan.zhihu.com/p/497144608

2.Fan C, Zeng L, Sun Y, et al. Finding key players in complex networks through deep reinforcement learning[J]. Nature machine intelligence, 2020, 2(6): 317-324.
这篇文章是本次主讲人范长俊老师的研究成果:提出基于深度强化学习框架,该框架可以在小型网络上进行训练,以理解复杂网络系统的 组织原则,从而帮助我们设计更加抗攻击和抗故障的网络。
集智俱乐部报道:用强化学习寻找关键节点——复杂网络研究新范式
GitHub代码:https://github.com/FFrankyy/FINDER

3.Fan C, Shen M, Nussinov Z, et al. Searching for spin glass ground states through deep reinforcement learning[J]. Nature Communications, 2023, 14(1): 725.
这篇文章是本次主讲人范长俊老师的研究成果:介绍了一种深度强化学习框架 DIRAC,可以仅在小规模的自旋玻璃实例上进行训练,然后应用于任意规模的实例上。该框架有助于更好地理解低温自旋玻璃的性质,其采用的规范变换技术在物理学和人工智能之间建立了深刻的联系,此外,也为强化学习在巨大的构型空间中探索开辟了一条充满希望的道路。
集智俱乐部报道:Nat. Commun. 前沿:深度强化学习搜索自旋玻璃基态

4.Nair, Vinod, et al. "Solving mixed integer programs using neural networks." arXiv preprint arXiv:2012.13349 (2020).
线性规划用于最大化或最小化受一个或多个约束的线性目标函数,而混合整数规划 (MIP) 增加了一个附加条件:至少一个变量只能取整数值。这篇研究DeepMind 和 Google Research 的一个团队利用神经网络从 MIP 实例的数据集中自动构建有效的启发式算法。这种新颖的方法明显优于经典的 MIP 求解器技术,展示了对最先进的SCIP(求解约束整数程序)7.0.1 求解器的特别令人印象深刻的改进。
报道链接:https://medium.com/syncedreview/deepmind-google-use-neural-networks-to-solve-mixed-integer-programs-bf41e3521950
知乎介绍:https://zhuanlan.zhihu.com/p/403130522
GitHub代码:https://github.com/ds4dm/learn2branch
一作解读视频:https://www.youtube.com/watch?v=qf8TeiGTZys

5.Donti Priya L., Rolnick David, Kolter J.Zico. DC3: A learning method for optimization with hard constraints. arXiv:2104.12225, 2021
在许多设置中都会出现具有硬约束的大型优化问题,但经典求解器通常非常慢,这促使人们将深度网络用作廉价的“近似求解器”。但是简单的深度学习方法通常无法强制执行此类问题的硬约束,从而导致解决方案不可行。这篇文章提出了深度约束补全和校正(Deep Constraint Completion and Correction ,DC3),解决上述挑战。具体来说,该方法通过一个可微过程来加强可行性,隐含地完成部分解决方案以满足等式约束并展开基于梯度的校正以满足不等式约束。DC3 在综合优化任务和 AC 最佳功率流的实际设置中都达到了很好的效果,在这两种情况下,DC3 在保持可行性的同时实现了接近最优的目标值。
OpenReview: https://openreview.net/forum?id=V1ZHVxJ6dSS
GitHub代码:https://github.com/locuslab/DC3

6.Fu Z H, Qiu K B, Zha H. Generalize a small pre-trained model to arbitrarily large tsp instances[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2021, 35(8): 7474- 7482.
这篇文章尝试采用监督学习方式,训练一个小规模的模型,利用图采样、图转换以及热图合并等一 系列技术,构建可重复用于任意规模TSP实例的热图。此外,通过输入热图到强化学习方法(蒙特卡  洛树搜索),以指导搜索高质量的解决方案。
OpenReview: https://openreview.net/forum?id=TLnReGgZEdW
GitHub代码: https://github.com/Spider-scnu/TSP

7.Pogančić M V, Paulus A, Musil V, et al. Differentiation of blackbox combinatorial solvers[C]//International Conference on Learning Representations. 2020.
图神经网络在处理自然输入等上游任务中发挥着重要作用,可直接从自然输入如图片、语音和文本等中提取特征,并应用于组合优化问题的求解。这篇论文模型的自然输入为图片,利用神经网络解决TSP、最短路径等组合优化问题。
OpenReview: https://openreview.net/forum?id=BkevoJSYPB
GitHub代码:  https://github.com/martius-lab/blackbox-differentiation-combinatorial-solvers




直播信息




时间:
2023年6月17日(本周六)晚上19:00-21:00

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


集智学园最新AI课程,

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

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


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


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


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


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


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

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

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


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

Python社区是高质量的Python/Django开发社区
本文地址:http://www.python88.com/topic/156451
 
448 次点击