用机器学习近似 NP 困难问题（文字版）

点击这里收听本期节目音频版

编辑： 肖怡婷

本期嘉宾： 戴涵俊 (G)

主播： 舒晏 (S), 阿拉法特 (A)

A: 计算机科学中有一类问题，我们称之为 NP 困难问题。举个例子，比如说旅行推销员问题，这个问题的设定是：有一系列的城市，我们知道这些城市之间公路的长度，我们想找一条旅行线路，使得我们能够从某一个城市出发，最后回到同一个城市，并且旅途中能把每个城市访问一遍，且只访问一遍。
S: 这个时候观众朋友们可能想说，你们不是一个数据科学的节目吗？这种问题和数据科学有什么关系？其实我也这么觉得，但是我们今天请到的嘉宾，他最近的工作就是用机器学习的方法来解决这一类的优化问题。
A: 大家好，欢迎收听德塔赛。我是阿拉法特。
S: 我是舒晏。
A: 我们今天的嘉宾是戴涵俊。
G: 大家好。
S: 我和小阿都可以和戴涵俊互称校友，因为戴涵俊现在是在佐治亚理工读博士。我是佐治亚理工本科毕业的，但是我们之前并不认识，因为我毕业的时候他刚刚到这边。不过小阿和小戴是本科时候在复旦的同学，所以小阿介绍了我们认识。
A: 对，我和小戴不仅是校友，我们是在同一个宿舍，是室友。不如我们先让戴涵俊自我介绍一下。
G: 大家好。我叫戴涵俊，现在是佐治亚理工四年级的博士生。我的主要研究方向是深度学习以及如何用深度学习的技术去解决一类图数据上的问题。
S: 我们今天就从你最近投到 NIPS 的这篇文章说起。这篇文章中，你是尝试解决一些图上的组合优化问题。就像我们刚才所说的，对于不太熟悉这类问题的人，可能很难想象怎么把机器学习和组合优化这样的问题联系起来。你可以给大家说明一下吗？
A: 我觉得在切入这个问题之前，不如我们先定义一下什么是组合优化问题。戴涵俊你能从一个组合优化问题的例子开始说起吗？
G: 好的，其实从抽象层面来讲，这个工作试图解决的是一类离散空间上的整数规划问题，尤其是图论上的很多问题都属于这类范畴。具体的例子，比如说最小点覆盖，它的问题定义是说怎样在图中找到最小数目的点，使得图中的每一条边都至少有一个端点在你所选取的点的集合中。一个非常暴力的解法就是枚举整个问题的解空间，对于最小点覆盖问题，就是枚举所有可能的点的集合，然后一一验证这些点的集合能否覆盖到图中所有的边，再从这些可行的解法中选取一个最优的解。
A: 这类问题感觉和机器学习的关系并不是那么的显然，那它是怎么样和机器学习的算法联系起来的呢？
G: 首先，我了解到的解决组合优化问题一般有两种方法：第一种是搜索加上一定的剪枝，但是这种方法通常复杂度不是多项式的；另一种是构造性的方法，这类方法通常有一个近似度的保证，但是这个度又非常的宽松，像我们之前提到的最小点覆盖问题，已知最优的近似解只能保证找到的解的代价不会超过最优解的两倍。
A: 那传统的不用机器学习，人们一般怎么去解决这类问题？
G: 像这类构造方法一般就是找一种启发式的规则，想一些可以覆盖所有边的方案，同时这种方案花费的点要尽量少。这些规则反映了我们对问题的直观认识。像最小点覆盖问题，一个已知的近似解是通过不断添加那些没有被覆盖边的两个端点来实现的。当然这个构造性的方法或者搜索方法都不够理想。用搜索的方法虽然能够保证找到最好的解，但它的时间效率却没有保证；第二种方法，近似度又不够好。同时，这两种方法也需要针对问题的特定的方法与技巧，这需要非常多的研究员花费多年的心血来达成这样的目标。当然，我觉得最大的问题是，尽管你能无数遍地用同一种方法解决同一类问题的不同样例，但是仍然没有办法从你已经解决过的那些问题中获取经验来帮助你解决那些未知的问题，或者说对未知的问题提供任何帮助。所以在这方面，机器学习就有用武之地了。
S: 那么我可以说当一个机器学习的算法，或者说任何一个解决问题的机器，它去尝试解决一类问题的时候，它都会从训练数据中先学会一些经验，知道怎么样比较好的解决这样一类的问题。但是刚才你说的搜索、还有构造的传统方法，并没有积累经验的过程，所以它没有学会解决一类问题的规律。这是你所说的机器学习试图去改进的地方，对吗？
G: 对。
S: 我觉得这是一个非常有创新的想法。那你们具体会使用什么样的机器学习算法来解决这个最小点覆盖问题呢？
G: 具体来说，我们用到的方法叫做强化学习。可能大家都知道前段时间非常火的 AlphaGo，这个围棋软件打败了人类最顶尖的棋手，像这种软件的实现方式就是强化学习。一般这类问题，如果你能够很容易地获得监督信息，那么其实你根本就没有必要做这件事情。然而，对于某一类问题，比如 NP 完全类问题，你要获取带有标签的信息是非常困难的。因此我们应该另辟蹊径，让算法本身通过试错来找到最优，或者较优的策略来解决同样的问题。我认为这就是强化学习的基本思想。大家都知道围棋软件战胜了人类棋手，它的训练方式除了有之前的高手积累下来棋谱之外，还有无数的自我对弈的提升过程。在最近的一个版本中，它们甚至完全放弃了人类的棋谱，直接通过自我对弈完成训练。
S: 所以高手积累下来的棋谱是它训练的第一步，这是它的一个监督信息，等到它后面做自我对峙的时候，就是你说的强化学习了，是吗？
G: 对，可以这么说。当然它的第一步用高手的棋谱来积累经验的过程，我们一般把它叫做模仿学习，可以把它理解为一种监督学习。
A: 那你刚刚是提到了强化学习的一个动机，在我们接着往下聊之前，你能简单的补充一下强化学习的一些背景支持吗？
G: 我觉得强化学习的任务是让智能体学习一种策略，使得它获得的累积奖励最大。主要的组件有三个，分别是：状态、策略和奖励。其中，状态是对当前环境的一种描述；策略是指在当前环境下用怎样的方法去选择下一步的行为；奖励就是你当前这个行为的反馈。我这篇论文关注的是马尔可夫决策过程，也就是说我们所用的策略与当前时刻之前的状态无关，不过这个策略却需要考虑到长远的效用，而不是简单的贪心策略。
A: 你的工作让我想起了熟悉的动态规划。
G: 没错。在这种设定下，我们要解的就是一个动态规划问题，而这个问题是用贝尔曼最优方程组来描绘的。用动态规划的概念来说，我们需要关注状态表示、状态转移方式以及最优子结构，这分别对应到强化学习中的状态、决策以及未来的累积奖励。
S: 你们在解决最小点覆盖问题的时候，具体的算法是什么样的呢？
G: 我们具体用到的强化学习算法叫做 Q learning，这种方法会对当前的局面，以及你在当前局势下所做的决策进行估值。它有一个估值函数，我们把它叫做 Q。在最小点覆盖问题中，如果你已经选择了其中一些点，这些点就构成了一个部分解。如果我们把这个部分解当作当前的状态，那么下一个可行的决策就是从那些没有被选择的点中选择一个点，加入到你的覆盖集中。不同的部分解，最后需要用到的总点数也是不同的，所以我们会尽可能选择那些使我们最终覆盖集最小的决策来作为我们当前的决策，这就是我们这个算法所要学习的。
A: 这个估值函数的参数是当前的状态和当前你可以做的选择？
G: 对的。
A: 那具体到最小点覆盖问题，估值函数给我们返回的值是当下选择的点的数目吗？
G: 不是。估值函数描绘的是你对未来的预期，所以对最小点覆盖问题，估值函数是说，在当前状态下，你选择这个点之后，将来还要额外选择多少点才能完成你的点覆盖。我再举一个例子，我要教计算机怎么去玩一个游戏，比如打砖块游戏，大家都会玩。每个时刻，电脑屏幕上显示的图像就是我当前状态的表示，在这个状态下，我可以做一系列的决策，比如说可以选择把自己的板子往左移或者往右移。不同的行为显然会影响我的得分，因为板子移动的方向不同，球移动的方向也会不同，从而导致其未来的状态也不同。当然球如果有打到砖块的话，得分也会不一样，这个得分就是它所得到的反馈，或者叫奖励。
S: 那么在最小点覆盖这个问题中，反馈和奖励又是怎么定义的呢？这是每一步之后你都会得到的一个反馈，还是要很多步之后才能知道的呢？
G: 这个问题非常好。在最小点覆盖中，我们的目标是最小化所选取的点的数量，换句话说，我们每一步的奖励就是所对应的惩罚。我们的目标，最大化奖励，就是要最小化这个惩罚，所以在我们的问题中，这个奖励就是一个常数，为 -1。当然不是所有的问题对于每个决策都会有立刻的反馈，比如我们之前提到的围棋问题，如果把赢得这场游戏的奖励作为 1，输了这场游戏的奖励作为 -1，那么只有当你完成一系列决策之后，你才能得到这个奖励的信息。当然，这种设置下的问题就会更难一点。
S: 好，刚才小戴你介绍清楚了在最小点覆盖问题中状态、决策还有奖励这三个概念，那具体你是怎么用 Q 函数来进行学习的呢？
G: Q 函数主要是学习到了对未来的预期，如果有了这个估值函数，在看到新的问题之后，我们就可以通过贪心的方法在多项式时间内得到一个非常优的解。就像我刚刚说的 Q-learning 的学习方法是通过拟合贝尔曼最优化方程组，这个思想类似于动态规划，具体学到的就是不同状态不同决策下你的估值是多少。
A: 那 Q 函数需要对所有可能的状态还有决策的组合给出一个估值吗？
G: 对的，所以我们工作的重点就是如何去估计 Q 函数的值。一种方法是表格，另一种方法就是用函数将状态映射到向量空间。表格，就像我们平时用数组记录动态规划的过程，这种方法能够得到精确的解。然而，一般情况下，状态空间是指数级别，甚至是无穷大的，这样做局限性就很大；而后者，函数映射，大多数时候不能保证能够学到最优解，不过能够学到一个较优的解，通常已经足够了。在我们的工作中，我们是用函数映射的方式来表示状态，相当于把 Q 函数参数化了。
S: 所以说强化学习的表现如何，跟用来把这个状态映射到向量空间的函数有很大的关系。那你们的 Q 函数是用什么模型来参数化的呢？
G: 是这样，Q 函数的两个参数分别是状态和决策，如果我们已经把状态用向量表示了，那么我们可以简单地用两层的神经网络去表征一个回归函数，但是在我们的问题中状态是用图来表示的。
S: 这听起来是一个很困难的问题，怎么把一张图转化成一个向量，并且保存图内所有的信息。你们具体是怎么解决这个问题的呢？
G: 比较简单的做法是手工的去设计一些特征，比如说我可以数一下这个图中有多少个点，可以统计一下平均点的度数是多少。当然这些特征不一定有用，同时它可能并没有什么区分度。所以我们希望做的是用神经网络，用深度学习的方法去自动学习那些有用的特征。同时这个学习过程应该是和强化学习端到端一起训练的，这样我们才能够保证我们提取到的特征是我们想要的。我们的方法原本从图模型的推断算法中获取到了灵感，不过我决定从更直观的角度来解释我们的网络结构。大家都熟悉在图像处理中的卷积神经网络，卷积操作会对图像不同的局部结构执行同一个矩阵乘法，那么我们的做法对应的就是将卷积的操作运用到图数据结构中。
A: 那在这个类比中，图的每一部分具体是指什么呢？
G: 这个其实有自由发挥的空间了。在我们的神经网络设计结构中，局部结构就简单的是每一个点以及这个点直接相邻的那些点。
A: 在这个问题中我们也可以用和处理图像完全一样的网络结构吗？
G: 会有一些区别，在处理图像中，不同局部结构的大小是一样的，所以我们可以简单的用同一个矩阵乘法来完成。但是在图数据结构中，不同局部会有不同的邻接点的数量，所以我们用了一种 pooling 的操作。简单的说，我们会把一个点以及它周围点的所有向量表示用一种加权平均的方式规划成一个向量，这样就轻松解决了大小不一样的问题。当然我们也可以用更复杂的方法，比如用循环神经网络。不过，在这中间要注意的是我们的向量表示不应该和顺序相关。
A: 那具体到你们的实验中，你们有试过把这种表示和一些更加传统直接的表示，比如说我刚想到的例子是我们直接把图的邻接矩阵，把它拼接成一个向量。和这种表示方法相比，你们的工作会有怎样的优势？
G: 这是个很好的问题。如果直接用邻接矩阵来表示一张图的话，那么对于不同的图，你的向量表示的长度是不一样的，这就为之后的全连接神经网络造成了不小的困难。当然在我们的实验中，我们也试过用SVD的方法将图的邻接矩阵分解，同时简单地将每个点的向量表示加权平均，不过这种方法似乎表现的并不是很好。
A: 那也就是说你们这次 NIPS 的工作是基于之前 graph embedding 的成果了。那除了应用它来解决这种组合优化问题，你们还尝试过用这种图向量嵌入去解决别的问题吗？
G: 在我们之前的工作中，我们用图向量嵌入去做一些分子或者蛋白质的特性预测，因为分子和蛋白质同样可以用图来表示。另外一种应用就是半监督学习，在这种应用中我们可以把所有的样本用图来建立起关系，同时我们只对小部分的样本进行标注，但是通过图的结构信息，我们可以去对那些没有标注过的样本提取特征，从而能够帮助对未知的样本进行预测。
S: 其实 Q-learning 除了在组合优化问题以外，还有很多其他的应用，那么在以后的节目里如果有时间也可以和大家多讨论，今天的节目就到这里了。我们非常感谢戴涵俊来花时间和我们录节目。
G: 谢谢两位主持人，谢谢各位观众的收听。
A: 那么和往期节目一样，如果你想了解更多戴涵俊的工作，我们会把他的主页链接和他刚刚提到的论文都放在我们推送的文章中。
S: 如果你还没有关注我们的微信，请在微信平台搜索德塔赛三个汉字的中文全拼，并且关注我们的节目。
A: 我们下期节目再见。