## 作为多目标优化的多任务学习：寻找帕累托最优解+组合在线学习：实时反馈玩转组合优化-微软研究院+用于组合优化的强化学习：学习策略解决复杂的优化问题_从高维空间中找出距离最大的 n个点。这是一个组合优化问题,

NIPS 2018：作为多目标优化的多任务学习：寻找帕累托最优解

优化器是提供了一个可以使用各种优化算法的接口，可以让用户直接调用一些经典的优化算法，如梯度下降法等等。优化器（optimizers）类的基类。这个类定义了在训练模型的时候添加一个操作的API。用户基本上不会直接使用这个类，但是你会用到他的子类比如GradientDescentOptimizer, AdagradOptimizer, MomentumOptimizer（tensorflow下的优化器包）等等这些算法。

组合在线学习：实时反馈玩转组合优化

看似无比困难的权衡问题，如今组合在线学习就能帮你“算出”最优解，轻松破解传统组合优化问题。本文中，我们邀请到微软亚洲研究院资深研究员陈卫为大家多面解读组合在线学习的奥妙之处。

---

什么是组合在线学习？大家都曾有过这样的经历，在我们刷微博或是阅读新闻的时候，经常会看到一些自动推荐的内容，这些信息可以根据你对推送的点击情况以及阅读时间等来调整以后的推送选择。再比如，手机导航往往会在你输入地点时推荐一条最合适的路线，当你按照推荐走的时候，手机导航也会收集这次行程的信息，哪里比较堵，哪里很顺畅，从而可以调整系统今后的推荐。

有人会提出质疑：这不就是推荐系统吗？是的，但是传统的推荐系统只能离线学习用户和对象的各种特征，作出尽量合适的推荐，是一个相对静态的系统。而我们这里强调的是在线学习（online learning），即迅速利用在线反馈，不断迭代调整推荐策略，从而尽快提高学习效果和整体收益。而组合在线学习（combinatorial online learning）的组合性则体现在学习的输出上，它不是一个简单结果，而是一个组合对象。比如上述情形中，手机导航输出的路线其实是若干路段的组合或者包括不同交通工具换乘的组合，而手机助手的推荐也是不同消息渠道的组合。

传统的推荐系统通过与组合在线学习相结合，就可以通过即时反馈调整策略达到更好的推荐效果。而组合在线学习应用范围远不止推荐系统，任何传统的组合优化问题，只要问题的输入有不确定性，需要通过在线反馈逐步学习的，都可以应用组合在线学习方法。组合在线学习也是当前大热的强化学习（reinforcement learning）的一个组成部分，而组合在线学习的强大理论支持也会给强化学习提供很好的理论指导。所以组合在线学习就是下面图示所表达的组合优化和在线学习不断交互迭代更新的反馈环路。

在线学习的核心：权衡探索和守成

要介绍组合在线学习，我们先要介绍一类更简单也更经典的问题，叫做多臂老虎机（multi-armed bandit或MAB）问题。赌场的老虎机有一个绰号叫单臂强盗（single-armed bandit），因为它即使只有一只胳膊，也会把你的钱拿走。而多臂老虎机（或多臂强盗）就从这个绰号引申而来。假设你进入一个赌场，面对一排老虎机（所以有多个臂），由于不同老虎机的期望收益和期望损失不同，你采取什么老虎机选择策略来保证你的总收益最高呢？这就是经典的多臂老虎机问题。

这个经典问题集中体现了在线学习及更宽泛的强化学习中一个核心的权衡问题：我们是应该探索（exploration）去尝试新的可能性，还是应该守成（exploitation），坚持目前已知的最好选择?在多臂老虎机问题中，探索意味着去玩还没玩过的老虎机，但这有可能使你花太多时间和金钱在收益不好的机器上；而守成意味着只玩目前为止给你收益最好的机器，但这又可能使你失去找到更好机器的机会。而类似抉择在日常生活中随处可见：去一个餐厅，你是不是也纠结于是点熟悉的菜品，还是点个新菜？去一个地方，是走熟知的老路还是选一条新路？而探索和守成的权衡就是在线学习的核心。

多臂老虎机的提出和研究最早可以追述到上世纪三十年代，其研究模型和方法已有很多。想进一步了解其技术细节的读者可参考综述[1]。其中一类重要的模型是随机多臂老虎机，即环境给予的反馈遵从某种随机但未知的分布，在线学习的过程就是要学出这个未知分布中的某些参数，而且要保证整个学习过程的整体收益尽量高。这其中最有名的一个方法是UCB（Upper Confidence Bound）方法，能够通过严格的理论论证说明UCB可达到接近理论最优的整体收益。

组合在线学习：组合优化和在线学习的无缝对接

介绍了多臂老虎机问题，我们现在终于可以介绍组合在线学习，更具体的是组合多臂老虎机（CMAB）问题了。在组合多臂老虎机问题中，你一次拉动的不是一个臂，而是多个臂组成的集合，我们称之为超臂（super arm），原来的每个臂我们称之为基准臂（base arm），以示区别。拉完这个超臂后，超臂所包含的每个基准臂会给你一个反馈，而这个超臂整体也给你带来某种复合的收益。

以前面的手机导航作为一个例子。城市中的每一个路段可以被看成是一个老虎机（一个基准臂），而你一次选择的并不是一个路段，而是从出发点到终点的一条路线，会包括很多路段，整个这个路线就是一个的超臂。当你实际走这条路线时，每一个路段都会给你反馈，就是该路段的拥堵时间（注意这个拥堵时间是随机的，不是每次都一样，而平均拥堵时间就是你需要学习的），而你的整体收益就是整个路线的拥堵时间（在这个例子里拥堵越短越好，所以用整体损失表达更贴切些）。这就是组合多臂老虎机问题。很多组合推荐，组合选择优化问题都可以用多臂老虎机来表达。

那么如何解决组合多臂老虎机的问题呢？你可能首先想到的就是把每一个超臂看成是经典多臂老虎机问题中的一个臂。但是超臂是多个基准臂的组合，而这样组合的数目会大大超过问题本身的规模——组合问题中经典的组合爆炸现象，因此传统的方法并不适用。所以在线学习不能在超臂这个层次进行，而需要在基准臂层次上进行，并需要与离线组合优化巧妙地结合。我们在ICML2013的论文[2]中给出了组合多臂老虎机的一般框架和基于UCB方法的CUCB算法。CUCB算法将组合优化和在线学习无缝对接实现了前面图示中的反馈回路。较之前的涉及组合多臂老虎机的研究，我们的模型适用范围更广，尤其是我们通过给出收益函数的两个一般条件，能够涵盖非线性的收益函数，这是第一个能解决非线性多臂老虎机问题的方案。我们的工作，包括之后我们和他人的后续工作，都强调对在线学习部分和离线优化部分的模块化处理和无缝对接。也即我们将离线优化部分作为一个黑盒子神谕（oracle），这部分可以由具有相关领域知识的专家来完成。而一旦离线优化问题可以精确解决或近似解决，我们就可以把这个离线算法当作黑盒子拿过来和我们在线学习方法相结合，达到有严格理论保证的组合在线学习效果。这使得我们的方法可以适用于一大批已经有离线优化算法的组合在线学习问题，比如最短路径、最小生成树、最大匹配、最大覆盖等问题的在线学习版本，而不需要对每个问题单独再设计在线学习算法。

在论文[2]的期刊版本[6]中,我们进一步将组合多臂老虎机模型扩展为允许有随机被触发臂的模型。这一模型可以被用于在线序列推荐、社交网络病毒式营销等场景中，因为在这些场景中前面动作的反馈可能会触发更多的反馈。然而在[6]的理论结果中，我们包含了一个和触发概率有关的项，而这个项在序列推荐和病毒营销场景中都会过大，造成在线学习效果不好。在今年刚被录取的NIPS论文[9]中，我们彻底解决了这个问题：一方面我们论证了序列推荐和病毒营销等满足某种特定条件的问题都不会有这个不好的项，另一方面我们指出在更一般的组合多臂老虎机中这个项又是不可避免的。这是目前研究可触发臂的组合多臂老虎机中最好的一般结果。

除此之外，我们还在与组合多臂老虎机相关的方面做了若干工作，比如如何在反馈受限情况下达到好的学习效果[3]；如何解决先探索再找到最佳方案的组合探索问题[4]；当离线优化基于贪心算法时，如果更好地将离线贪心算法和在线学习相结合[5]；如何在有上下文的场景中解决组合序列推荐问题[7]；以及当超臂的期望收益取决于每个基准臂的随机分布而不仅是每个基准臂的分布均值时，如何同样有效地进行组合在线学习[8]。

总之，组合在线学习将离线组合优化和在线学习有机地结合起来。由于组合优化的普遍存在和在线即时反馈机制的日益完善，将优化和反馈不断迭代结合的组合在线学习势必会找到更多的应用，而组合在线学习坚实的理论根基会对其实际应用起到很好的指导作用。这个方向有很多的理论和实践问题需要进一步研究，我们也希望在这个方向继续做出新的贡献。

 

[1] Sébastien Bubeck and Nicolò Cesa-Bianchi. Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems. In Foundations and Trends in Machine Learning, Vol 5: No 1, 1-122, 2012

[2] Wei Chen, Yajun Wang, and Yang Wang. Combinatorial Multi-Armed Bandit: General Framework, Results and Applications. In Proceedings of the 30th International Conference on Machine Learning (ICML'2013), Atlanta, Georgia, U.S.A., June 2013. View abstract, Download PDF, View external link

[3] Tian Lin, Bruno Abrahao, Robert Kleinberg, John C.S. Lui, and Wei Chen. Combinatorial Partial Monitoring Game with Linear Feedback and its Applications. In Proceedings of the 31st International Conference on Machine Learning (ICML'2014), Beijing, China, June 2014. View abstract, Download PDF

[4] Shouyuan Chen, Tian Lin, Irwin King, Michael R. Lyu, and Wei Chen. Combinatorial Pure Exploration of Multi-Armed Bandits. In Proceedings of the 27th Annual Conference on Advances in Neural Information Processing Systems (NIPS'2014), Montreal, Canada, December 2014. View abstract, Download PDF

[5] Tian Lin, Jian Li, and Wei Chen. Stochastic Online Greedy Learning with Semi-bandit Feedbacks. In Proceedings of the 28th Annual Conference on Advances in Neural Information Processing Systems (NIPS'2015), Montreal, Canada, December 2015. View abstract, Download PDF

[6] Wei Chen, Yajun Wang, Yang Yuan, and Qinshi Wang. Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms. In Journal of Machine Learning Research 17 (2016) 1-33, 2016. View abstract, Download PDF

[7] Shuai Li, Baoxiang Wang, Shengyu Zhang, and Wei Chen. Contextual Combinatorial Cascading Bandits. In Proceedings of the 33rd International Conference on Machine Learning (ICML'2016), New York, NY, USA, June 2016. View abstract, Download PDF

[8] Wei Chen, Wei Hu, Fu Li, Jian Li, Yu Liu, and Pinyan Lu. Combinatorial Multi-Armed Bandit with General Reward Functions. In Proceedings of the 29th Annual Conference on Advances in Neural Information Processing Systems (NIPS'2016), Barcelona, Spain, December 2016. View abstract, Download PDF

[9] Qinshi Wang, and Wei Chen. Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications. In Proceedings of the 30th Annual Conference on Advances in Neural Information Processing Systems (NIPS'2017), Long Beach, U.S.A., December 2017. View abstract

 

 

作者介绍

陈卫，微软亚洲研究院资深研究员，清华大学交叉信息学院兼职教授，中科院计算所客座研究员。主要研究方向包括社交和信息网络、在线机器学习、网络博弈论和经济学、分布式计算、容错和可靠系统等。他在社交网络和在线学习方面的基础性研究得到广泛关注，这方面的论文他引逾4000次。陈卫是中国计算机协会第一届大数据专家委员会成员和《大数据》期刊的编委，也是多个顶级学术会议(KDD、WWW、WSDM、SIGMOD、NIPS等)的程序委员会成员，并有一本关于信息和影响力传播的专著。

用于组合优化的强化学习：学习策略解决复杂的优化问题

src=“http://imgcdn.atyun.com/2019/04/1_clCe_SIJvZsFx4Eqe8U_WQ.jpg” alt=“用于组合优化的强化学习：学习策略解决复杂的优化问题” width=“780” height=“480”>

从人类诞生之初，每一项技术创新，每一项改善我们生活的发明都是经过奇思妙想后设计出来的。从火到车轮，从电力到量子力学，我们对世界的理解和我们周围事物的复杂性，已经增长到难以直观地掌握它们的程度。

如今，飞机，汽车，船舶，卫星等复杂结构的设计者在很大程度上依赖于算法，使其变得更完美，这通常是人类无法以微妙的形式实现的。除了设计之外，优化在日常事务中起着至关重要的作用，例如网络路由（互联网和移动），物流，广告，社交网络甚至医学。

在未来，随着我们的技术不断改进和复杂化，对解决大规模难题的能力可能会有更高的要求，并且需要在优化算法方面取得突破。

组合优化问题

从广义上讲，组合优化问题涉及从有限的一组对象中找到“最佳”对象。在这种情况下，“最佳”是通过给定的评估函数来测量的，该函数将对象映射到某个分数或成本，目标是找到最低成本的对象。大多数实际中有趣的组合优化问题也非常困难，因为即使问题的大小只增加了一点，集合中的对象数量也会以极快的速度增加，导致穷举搜索不切实际。

为了讲这件事解释清楚，我们将专注于一个特定的问题，即着名的旅行商问题（TSP）。假设我们有N个城市，我们的销售员必须全部访问它们。然而，在城市之间穿梭会产生一些费用，我们必须找到一种方案，在旅行到所有城市并返回起始城市过程中最大限度地减少总累积成本。例如，下图显示了美国所有省会城市的最佳旅游路线：

这个问题出现在许多重要的应用中，例如计划，交付服务，制造，DNA测序等。寻找更好的旅行团队有时会产生严重的财务影响，促使科学界和企业投入大量精力来解决这些问题。

在用K个城市建立TSP实例之旅的同时，我们在旅游建设过程的每个阶段都去除了一个城市，直到不再有城市为止。在第一阶段，我们有K个城市可以选择，在第二阶段我们有K-1个，然后是K-2个，以此类推。我们可以构建的可能的游览数量是我们在每个阶段的选项数量的乘积，因此这个问题的复杂性表示为O（K！）。

如果数字较小，这并不困难：假设我们有5个城市，可能的旅行次数是5！= 120。但是对于7个城市，它增加到5040，对于10个城市，已经达到3628800，对于100个城市来说，它高达9.332622e + 157，这比宇宙中的原子数多出许多个数量级。

在现实世界中出现的TSP的实际实例通常包含数千个城市，为了在合理的时间（几个小时）内得到解决，需要开发了几十年的高度复杂的搜索算法和启发式算法。遗憾的是，在现实世界的应用程序中出现的许多COP具有独特的细微差别和约束，使我们无法仅使用最先进的方案解决TSP等已知问题，并且还要求我们开发针对该问题的方法和启发式算法。这个过程可能是漫长而艰巨的，并且可能需要领域专家来检测特定问题的组合搜索空间中的某些结构。

由于近年来深度学习在许多领域取得了巨大成功，让机器学会如何自己解决问题听起来非常有潜力。将算法设计自动化，可为COP节省大量的金钱和时间，而且可能产生比人类设计的方法更好的解决方案。

学习图形表示

2016年，一篇名为“Learning Combinatorial Optimization Algorithms over Graphs”的论文对这个问题进行了早期尝试。作者训练了一种叫做structure2vec的图神经网络，构建几个硬COP的解决方案，并获得非常好的近似比率（生产成本与最优成本之间的比率）。

其基本思想是：问题的状态可以表示为图形，在图形上，神经网络构建解决方案。在解决方案构建过程的每次迭代中，网络观察当前图形，并选择要添加到解决方案的节点，之后根据该选择更新图形，并且重复该过程直到获得完整的解决方案。

作者使用DQN算法训练神经网络，并证明了学习模型能够推广到比训练更大的问题实例。模型甚至可以顺利推广到1200个节点的实例（同时在大约100个节点的实例上进行训练），并且可以在12秒内生成解决方案，这些解决方案有时比在1小时内找到的商业解决方案更好。他们的方法的一大缺点是他们使用了辅助函数，以帮助神经网络找到更好的解决方案。这个辅助函数是人为设计的，并且是特定于问题的，而这正是我们想要避免的。

使用基于图形的状态表示非常有意义，因为许多COP可以通过这种方式非常自然地表达，如TSP图的示例中所示：

节点代表城市，边缘包含城市间距离。可以在没有边缘属性的情况下构建非常相似的图形（如果由于某种原因不假设距离的知识）。近年来，在图形上运行的神经网络模型（无论是否具有假设结构）越来越流行，最显著的是在自然语言处理领域，Transformer风格模型已成为许多任务的实现技术。

Transformer体系结构用于解决NLP中出现的序列问题。不同的是，在递归神经网络中，例如LSTMs，是显式地输入一个序列的输入向量，而Transformer是作为一组对象输入的，必须采取特殊的方法来帮助它看到序列中的顺序。Transformer使用由一个多头自注意子层和一个完全连接的子层组成的若干层。

与图形的关系在注意层中变得明显，注意层实际上是输入“节点”之间的一种消息传递机制。每个节点都观察其他节点并参与那些看起来更有意义的节点。这与Graph Attention Networks发生的过程非常相似，事实上，如果我们使用掩码来阻止节点将消息传递给不相邻的节点，我们将获得一个等效的过程。

学会解决没有人类知识的问题

在论文“Attention! Learn to Solve Routing Problems”中（arxiv.org/pdf/1803.08475.pdf），作者解决了几个涉及在图形上路由代理的组合优化问题，包括我们现在讨论的旅行商问题。

将输入视为一个图形，并将其提供给一个经过修改的Transformer体系结构，该体系结构嵌入图的节点，然后依次选择要添加到tour的节点，直到构建完整的tour为止。

将输入作为图形处理比给它一系列节点更好，因为它消除了对输入中给出城市的顺序的依赖性，只要它们的坐标不变。这意味着，无论我们如何对城市进行排列，给定的图神经网络的输出都将保持不变，这与序列方法不同。

在本文提出的体系结构中，图形由transformer式编码器嵌入，为所有节点生成嵌入，并为整个图形生成单个嵌入向量。为了获取解决方案，单独的解码器网络每次赋予特殊上下文向量，即由图嵌入和那些最后和最前面的城市，和未访问城市的嵌入，并且它在未访问的输出概率分布，被抽样以生成下一个要访问的城市。解码器顺序产生城市直到游览完成，然后根据游览的长度给出奖励。

作者使用了一种增强学习算法来训练模型，这是一种基于策略梯度的算法。版本的伪代码如下：

他们使用roll-out network评估实例的难度，并使用策略网络的参数定期更新roll-out network。使用这种方法，作者在几个问题上取得了优异的成果，超越了前面几节中提到的其他方法。但是，他们仍然是在小型实例上训练和评估他们的方法，最多有100个节点。虽然这些结果很有希望，但与现实世界相比，依然微不足道。

扩展到大型问题

最近，通过“Learning Heuristics Over Large Graphs Via Deep Reinforcement Learning”一文（arxiv.org/pdf/1903.03332.pdf），研究者朝着现实世界的问题迈出了重要一步。在论文中，作者训练了一个图卷积网络来解决大型问题，如最小顶点覆盖（MVC）和最大覆盖问题（MCP）。他们使用流行的贪婪算法来训练神经网络嵌入图形，并预测每一阶段要选择的下一个节点，然后使用DQN算法对其进行进一步的训练。

团队在具有数百万个节点的图表上评估了他们的方法，结果比当前标准算法更快更好。虽然他们确实利用手工制作的启发式方法来帮助训练模型，但未来的工作可能会消除这种限制，并学会解决类似Tabula Rasa的大型问题。

总的来说，在大量搜索空间问题中寻找结构的探索是强化学习的一个重要而实用的研究方向。强化学习的许多批评者声称，到目前为止，它只用于解决游戏和简单的控制问题，并且将其迁移到现实世界的问题仍然很遥远。

虽然这些说法也没错，但在本文中概述的方法代表了其非常真实的用途，可以在近期内为强化学习带来好处，而遗憾的是，它们不能像电子游戏方法那样吸引大量的关注。

AI热点