专访乔治亚理工宋乐教授：为图论组合优化问题寻找“元算法”

大数据文摘作品，转载要求见文末

作者｜钱天培

导读：

从交通优化、信息传播优化、用户网络分析，组合优化这一传统计算问题在日常应用中无处不在。然而，这类问题往往是NP难题（NP-hard），并需要大量的专业知识和试错来解决。在许多实际生活的应用中，相似的组合优化问题一次又一次的出现，而每次面对具有相同形式、但数据不同的问题，却需要大量人力一遍又一遍的设计新的算法方案。在机器学习席卷各个行业的同时，我们不禁想问：组合优化这一传统的应用数学问题是否也会有新的自动化的解决方法呢？

后台回复“图论”获取宋乐教授论文Learning Combinatorial optimisation Algorithms over Graphs原文等资源。

基于图论的组合优化问题：被重复解决的老大难题

广告商如何在资源有限的情况下投放广告，使得广告信息在投放用户的相互传播后抵达尽可能多的人群？货运公司如何合理安排送货路线来提高送货效率？在社交网站的聚类分析中，我们如何根据每个用户的差异指数将用户分为两个用户组，从而最大化两个组之间的差异指数？

以上这些常见的问题都可以被归类为基于图论的组合优化问题（combinatorial optimization problems over graphs），这三个问题分别对应为最小顶点覆盖问题（minimum vertex cover, MVC）、最大割问题（maximum cut, MAXCUT）、巡回售货员问题（graph travelling salesman problem, GTSP）。从交通优化、信息传播优化到用户网络分析，这一类问题在日常应用中无处不在。然而，这类问题往往是NP难题（NP-hard），并需要大量的专业知识和试错来解决。在许多实际生活的应用中，相似的组合优化问题一次又一次的出现，而每次面对具有相同形式、仅仅是数据不同的问题，我们却需要一遍又一遍的设计新的算法方案。在机器学习席卷各个行业的同时，我们不禁想问：组合优化这一传统的应用数学问题是否也会有新的自动化的解决方法呢？

今年三月，一篇题为Learning Combinatorial optimisation Algorithms over Graphs的论文对这个问题提出了最新看法。这篇论文运用了强化学习（reinforcement learning）和一个叫structure2vec的图嵌入（graph embedding）方法，提出了解决这一类问题的一种“元算法”，即学习算法的算法——通过这一类算法，同一类的基于图论的组合优化问题将不再需要被逐一解决。这一“元算法”的提出对基于图论的组合优化问题这一领域的研究有着开创性的建设作用。

近日，大数据文摘有幸邀请到这篇论文的作者之一——来自佐治亚理工计算机学院的宋乐教授，进行了一次专访。宋乐教授目前是佐治亚理工大学机器学习中心的associate director,领导机器学习的研究试验室，其主要研究领域为大规模机器学习，图嵌入，以及机器学习跨学科领域研究（如社交网络分析、神经科学等）。在这篇论文中，他之前的多个研究成果也得到了进一步的应用。

传统解决方案的瓶颈

首先，宋乐教授为我们介绍了解决这类组合优化问题的传统方法和它们各自的缺点。

第一种，精准算法。精准算法往往通过穷举或是基于整数规划的分支界限算法寻找问题的最优解，因此，这类算法无法被应用到数据规模较大的组合优化问题上。

第二种，近似算法。我们可以通过多项式时间的算法来近似最优解。现有的这类算法可被用来解决数据规模较大的组合优化问题，然而它们的最坏情况保证往往不尽如人意。另外，有部分问题是无法被近似解决的。

第三种，启发式搜索。启发式搜索指那些快速有效但缺乏理论支撑的算法。现有的这类算法的设计需要大量的专业知识和试错，因此无法被广泛使用。

除此之外，这三类解决方案都忽略了实际优化问题的一个共性。

相似的组合优化问题一次又一次的出现，他们具有相同形式，而区别仅仅是数据的不同。换句话说，在许多应用中，每个问题的目标函数和限制都可以被当成是从某个概率分布中取出的样本。

算法总览：基于图嵌入和强化学习的贪心算法

和大多数近似算法和启发式搜索类似，这篇论文所提出的名为Structure2Vec Deep Q-learning的新算法也是一种贪心算法（greedy algorithm），也就是说，此算法基于最大化某个“评价函数”（evaluation function）的目标，逐步添加节点的方法得到问题的解。具体算法如下，数学符号的具体含义课参见原论文。

宋教授说，这一算法的关键在于找到问题对应的评价函数Q。我们说一个评价函数Q*是最优的，当且仅当对任意一个问题具例，这个函数都能在此贪心算法下为我们找出最优解。通常情况下，寻找最优的评价函数这一任务本身就是NP难题，因此我们往往需要近似找出一个评价函数Q。解决这类问题的传统贪心算法需要算法设计人手动给出一个Q，（比如在最大割问题中，这个Q可以是节点的邻居数），而手动设计一个合理的评价函数在复杂问题中是不现实的。因此，这篇论文提出了用图嵌入寻找评价函数的方案。

具体来说，此论文使用了structure2vec这一图嵌入网络。宋教授说，通过这一网络所寻找到的评价函数Q能够整合节点和它一步两步，甚至三步以外所有邻居的信息，并将这一信息压缩成一个有限维的非线性向量。具体算法如下，

最后，这篇论文提出用强化学习中的n-step Q-learning这一方法来学习图嵌入网络的参数。

n-step Q-learning的使用可实现强化学习中的延迟回报。

整体算法可被下图概括。

实证研究：远超传统算法

此论文提出的新算法实现了基于图论的组合优化问题的“自动化”解决，那么这一算法的效率又如何呢？这篇论文将提出的新算法Structure2Vec Deep Q-learning和其他基于深度学习的算法（Pointer Networks With Actor-Critic）及近似/启发式算法作比较，发现这一算法所找出的解普遍更接近最优解（在下图中，approximation ratio越小表示解越优）。尤其是在MVC中，Structure2Vec Deep Q-learning得到解和最优解几乎没有差别（approximation ratio约等于1）。

宋教授表示，他们已将这些研究成果运用到材料和医药领域（研究分子图谱，从而进行分子特征提取，从来检验药品是否有效）的问题，并预计将这一研究成果推进到包括知识图谱研究、企业运营管理在内的其他领域。除此之外，我们也有理由相信，机器学习的发展将浸入更多其他学科领域的研究。曾经困扰我们多年的难题或将被机器学习一朝攻破。

在访谈最后，宋教授也谈到了目前机器学习课程在高校的开展盛况。在佐治亚理工学院，宋教授开展的研究生阶段的机器学习课程的报名人数达到了数百人，可谓一座难求。此外，紧跟卡耐基梅龙大学的步伐，佐治亚理工也将设立全球第二个机器学习的博士生专业。宋教授认为，在机器学习大热的趋势下，更多的高校将开展机器学习相关的专业和项目。此外，宋教授提到，参与机器学习课程的学生不仅仅来自计算机,统计和数学专业，更有医疗、生物、建筑等专业的学生前来报名学习。除了作为一门专门的学科而被学习研究，机器学习也将成为一项普及于其他各项学科领域的研究工具。