IJCAI 2021 | 一文了解微软亚洲研究院机器学习方向前沿进展

2021 年 8 月 24 日 微软研究院AI头条

（本文阅读时间：15 分钟）

编者按：第30届国际人工智能联合大会 IJCAI 2021 于8月19日-26日在线上正式召开。此次大会共收到4204篇投稿，其中587篇论文被接收，接收率为13.9%。在本届会议中，微软亚洲研究院也有多篇论文入选，今天我们精选了其中的5篇来为大家进行简要介绍。欢迎大家积极参与文末的投票活动，我们将邀请大家最感兴趣的论文的作者进行深度讲解，与大家线上交流！

利用独立性的优势函数估计方法

论文链接：

https://www.ijcai.org/proceedings/2021/0461.pdf

在强化学习中，优势函数 (advantage function) 普遍采用蒙特卡洛 (MC)、时间差分 (TD)，以及一种将前两者结合的优势函数估计算法（GAE) 等进行估计，而这些算法都存在方差较高的问题。因此，微软亚洲研究院的研究员们首次提出通过利用环境中存在于当前动作和未来状态之间的独立性，来降低优势函数估计中的方差。

在该方法中，存在于环境中的独立性可以用来构建一个基于重要性采样 (importance sampling) 的优势函数估计量。该估计量可以忽略未来无关的部分奖励，从而减小估计中的方差。为了进一步减少优势函数估计的方差，研究员们把该估计量和已有的蒙特卡洛估计量进行融合，并将最终的优势函数估计量命名为 IAE (Independence-aware Advantage Estimation)。实验结果表明，在策略优化算法中，IAE 与现有的优势函数估计方法 (GAE, MC) 相比，达到了更高的样本利用率。

事实上，现有方法往往先估计值函数 Q(s,a) 和 V(s)，再将二者相减，进而估计优势函数。但当值函数覆盖的时间范围较大时，估计值函数就需要考虑未来较长时间内的总奖励，因此导致了高方差的问题。

当环境中存在独立性时，优势函数的估计就不需要考虑环境中的部分奖励，从而使得估计中的方差减小。举个例子：假设智能体当前的任务是打乒乓球，在该环境下，智能体每赢得一分或输掉一分后，游戏的状态都会被重新设置到起始状态，并继续进行下一轮游戏。当对智能体每一个动作的优势函数进行估计时，由于智能体每个动作的影响都被限制在当前回合内，所以下一轮及之后的奖励实质上不影响优势函数的估计。

上述例子表明，如果执行当前的动作不影响未来某些状态的概率，那么这些未来状态上的奖励在估计优势函数时就可以被忽略。研究员们对上述观察进行了概括和抽象，并提出了基于重要性采样的优势函数估计量。下面给出的是基于重要性采样推导出来的该估计量的形式：

此公式证明了如下的估计量是优势函数的无偏估计量：

在后续推导中，研究员们进一步将上述基于重要性采样的估计量与基于蒙特卡洛的优势函数估计量进行结合，并通过优化结合后估计量的方差，使优势函数估计的方差更小。同时，研究员们将组合后的优势函数估计量命名为 IAE，并在实验中测量了 IAE 的估计性能。最后，研究员们还提出了上述公式中重要性采样的概率比值的估计方法，并且还利用其对该概率比值进行了准确的估计。

在 tabular 设置下，研究员们构建了多种包含3个状态的马尔可夫决策过程 (MDP)，并且在这些设置中包含了不同的转移函数设置和不同的奖励设置。研究员们比较了 IAE、蒙特卡洛、重要性采样三种优势函数估计量在不同设置下的标准差，结果见表1。实验结果表明，IAE 的估计量的标准差显著小于蒙特卡洛和重要性采样的估计量的标准差。

表1：不同设置下 IAE、MC、IS 的标准差

为了验证 IAE 在策略优化中的作用，研究员们将 IAE、蒙特卡洛、GAE 分别作为 PPO 算法中的优势函数估计方法，使用 PPO 算法进行策略优化，并观察不同优势函数估计方法在策略优化中的性能。该实验使用高维图像作为状态，即智能体的策略和优势函数的估计均只使用图像输入。PPO 算法在不同优势函数估计方法下的训练曲线图1，两幅图对应于两种不同的奖励设置。实验结果表明，IAE 作为优势函数估计算法时，策略优化过程的样本利用率更高。

图1：PPO 算法在不同优势函数估计方法下的训练曲线

面向合作与非合作任务的多智能体强化学习方法MFVFD

论文链接：

https://www.ijcai.org/proceedings/2021/0070.pdf

多智能体强化学习（Multi-agent Reinforcement Learning, MARL）有望帮助解决各种现实世界中的问题。然而，追求有效的MARL 面临着两大挑战：部分可观察性和可扩展性限制。为了应对这两大挑战，并使得 MARL 适用于竞争任务、合作任务以及混合任务，微软亚洲研究院和北京大学的研究员们在中心训练分散执行（Centralized Training with Decentralized Execution，CTDE）的框架下，从个体值函数分解（Value Function Decomposition，VFD）的角度，结合平均场理论（Mean Field Theory，共同提出了一种新颖的多智能体 Q 学习方法——MFVFD。

正所谓“非宅是卜，唯邻是卜”，如果邻里和睦，则利人利己；而邻里不和，则多是非。也就是说，在多智能体系统中，个体不仅要考量最大化自身的利益，也要考量其临近智能体的行为对齐本身的影响。比如，在足球环境中，球员射门得分与否，除去依赖球员个体自身的射门能力之外，还会受到近邻智能体的影响，即优秀的队友与糟糕的对手会促进得分，而糟糕的队友和优秀的对手则会阻碍得分。

为了研究多智能体如何在既有合作又有竞争的环境下的表现，研究员们基于平均场理论将个体在多智能体系统中基于全局信息的动作值函数，近似为基于局部信息估计的个体动作值函数与基于近邻信息的平均场影响函数的和，公式如下：

其中，Q_LOC^i 为基于局部信息的个体 i 的动作值函数，用于动作选择；Q_MF^i 为基于近邻信息的平均场影响函数，用于辅助对 Q_LOC^i 的估计。考虑到智能体不同近邻的重要性不同，所以研究员们使用注意力机制（Attention）建立了单体与近邻的权重 λ^i (o^i,o^k,a^i,a^k)，并基于此计算带有重要性权重的近邻观测分布 μ_o (o^(-i) ) 和动作分布 μ_a (a^(-i) ) ，以构建平均场影响函数 Q_MF^i。

图2：MFVFD 网络结构图

在主试验部分，研究员们选取了 MAgent Battle 任务，对 MFVFD 在具有大规模智能体且具有部分观测的限制下的性能进行了验证。在该任务中，红蓝双方各具有400个智能体，每个智能体具有局部观测，且无法通讯，其通过消灭敌人来获得奖励。由于每个智能体以优化各自的奖励为目标，所以单体会与同伴竞争杀敌数量，来获取更多的个人奖励。除此之外，单体还会与同伴配合避免被杀害，以消灭所有敌人获取更多的团队奖励。因此，这是一个合作和竞争混合的复杂任务。如图3所示，MFVFD（红色）与基线方法的（蓝色）相比，学会了更难的团体配合的围歼策略，取得了胜利。从对抗胜率上可以看出，MFVFD 在所有的基线方法中，几乎处于不败地位。

图3：MFVFD 与基线方法相比

此外，研究员们还选取了三个任务对 MFVFD 方法进行了理论分析，分别是：重复矩阵博弈任务----鹰鸽博弈与非单调合作博弈；合作导航任务----Cooperative Navigation；交通任务----Traffic Benchmark。从长远来看，MFVFD 在实际环境中能够有实际可行的研究价值。

CUC：云计算中基于不确定约束的预测作业调度算法

论文链接：

https://www.ijcai.org/proceedings/2021/0499.pdf

在云计算中，由于需求的庞大和多样性，平台计算资源的容量管理一直是一个极大的挑战。为了更好地根据整个云计算平台的容量进行规划，平台往往会提前收集一部分非即时的计算作业需求，这些计算作业可以持续运行指定长度的时间，且起止时间更加灵活。通过根据非即时计算作业的需求和平台在未来一段时间内的容量情况来进行统一调度，有助于平衡整个平台的工作负荷，提升平台资源的利用效率。但是，由于平台上未来可用的计算容量是不确定的，所以对这些非即时作业的调度，在不确定的计算资源约束下进行安排是一个巨大的挑战。

对于具有不确定约束的优化问题，传统的优化方法无法直接进行求解，而是需要结合对不确定约束进行预测的步骤来进行优化。然而，单独进行预测和优化的两阶段方法有明显的不足之处：两阶段方法假设预测结果是准确的，可是在实际中预测误差却无法避免，从而导致优化得出的解会违反（violate）约束。

在本篇论文中，微软亚洲研究院的研究员们将这类问题建模成一个预测+优化（Prediction + Optimization）框架下的问题，并针对这类问题提出了不确定约束下的作业调度算法 CUC（Controlling under Uncertain Constraints），该算法的架构如图4所示。其架构大体上可以概括为以下三个方面：

1）在预测阶段预测未来容量的大小，同时对预测的不确定性进行建模；

2）用预测的未来容量的分布来指导作业调度的优化问题，得到相应的调度方案；

3）利用调度结果结合贝叶斯优化来进一步提升容量预测的表现。

图4：CUC 方法的架构

此外，研究员们还针对实际应用中难以避免的违反约束情况，提出了相应的控制方式。该方式可以根据系统的要求，将实际违反约束的比例控制在特定水平以下，使得调度方案更加可靠与稳健。

为了验证 CUC 算法的有效性，本文将 CUC 算法与包含经典预测方法以及精确优化求解方法的两阶段法进行了对比，结果如表2和表3所示。结果表明 CUC 算法可以高效准确地得到违反约束比例很小的调度方案，同时可以尽可能使得更多的作业得到调度。而且通过改变违反约束水平的参数p，CUC 算法也可以灵活控制实际的违反约束情况出现的比例，以满足不同系统对于调度方案的实际违反约束情况的要求。

表2：不同方法在公开数据集上的表现对比

表3：不同违反约束水平参数 p 下，CUC 方法的表现

用于学习三维隐式符号距离场的样条位置编码

论文链接：

https://www.ijcai.org/proceedings/2021/0151.pdf

近日，全连接神经网络（MLP）被提出作为三维形状的隐式表达。MLP 以 3D 坐标为输入，可以直接输出该 3D 坐标点到三维形状表面的距离，即带符号的距离场（SDF），如图5所示。距离为正的点在三维形状外部，距离为负的点在三维形状内部，距离为0的点则代表三维形状本身。相对于传统的离散三维形状表达而言，MLP 的表达非常紧致，只需要极少量的存储就能表达复杂的形状，因而引起了科研人员的广泛关注。

图5：算法流程图

Spline Positional Encodings 可以帮助 MLP 更好地拟合三维形状的细节

在使用 MLP 从点云中重建 SDF 的任务中，微软研究院的研究人员发现，如果直接将 3D 坐标作为 MLP 的输入，那么输出的形状会被过度平滑，丢失高频细节（见图6-(a)）。为了解决这一问题，研究员们提出将三维坐标通过一系列正弦/余弦函数映射到高维空间，即 Fourier Positional Encodings（见图6-(b)），然后再作为 MLP 的输入；或者将 MLP 中常用的 ReLU 激活函数替换为正弦函数（见图6-(c)）。这些方法虽然能够拟合三维形状的几何细节，但是输出的 SDF 非常杂乱，其低频量无法被很好地重建。因此，微软研究院的研究员们提出了基于样条的位置编码，即 Spline Positional Encodings。该方法不仅可以重建三维形状的高频细节，还能够输出高质量的 SDF（见图6-(d)）。

图6：各个方法的比较

Spline Positional Encodings 的结果如 (d) 所示

具体而言，研究员们将输入的三维坐标通过一系列可以训练的 B 样条函数映射到高维空间。当 B 样条基函数足够稠密的时候，B 样条函数就可以很好地逼近各种连续函数，包括正弦/余弦函数。B 样条函数的权重可以随着 MLP 一起优化，所以本篇论文提出的方法可以被当成是 Fourier Positional Encodings 的推广，因而该方法具有很强的表达能力，可以拟合形状的高频细节。另外，由于 B 样条基函数可以不断被细分，所以研究员们可以用多尺度的方式对网络进行训练，使得 MLP 能够收敛到更好的局部极小。在训练 MLP 的时候，可以先以低分辨率的 B 样条基函数作为初始，让 MLP 先拟合 SDF 的低频成分；然后将 B 样条基函数进行细分，增强 MLP 的拟合能力，让 MLP 逐步地恢复三维形状的几何细节。

此外，研究员们还在单个形状重建和 DFaust 数据集上的形状空间重建任务上对本文的方法进行了验证。相较于现有的方法，本文提出的方法能取得更好的结果。另外，研究员们还在图片拟合任务上进行了测试。实验表明，本文的方法能够取得更好的性能，且具有较强的通用性。

User-as-Graph: 基于异构图池化的新闻推荐用户建模

论文链接：

https://www.ijcai.org/proceedings/2021/0224.pdf

用户建模是各项个性化服务（如推荐系统）中的关键技术。基于用户行为的用户建模，是实际推荐系统中的主要建模方法。已有的基于用户行为的用户建模方法，通常将用户建模为他们行为的集合或序列，亦或是用户-物品二分图上的节点。但是这些建模方法难以对行为之间的复杂联系和上下文信息进行充分建模。为了解决这一问题，微软亚洲研究院的研究员们提出了 User-as-Graph 方法。该方法将用户建模为一个由行为组成的异构图，这样就可以更好地理解行为之间复杂的关系和上下文信息，进而更加准确地表示用户，以实现“一人一图，千图千面”。

在 User-as-Graph 方法中，每个用户都被表示为一个个性化异构图。图7展示了一个构建示例。图中的节点是一个用户的异构行为，边是行为之间的关系。

图7：个性化异构图的构建示例

此外，用户建模的任务可以转化为一个异构图池化的问题，即从个性化的异构图中学习用户的表示。然而，对异构图池化方面的研究非常稀缺，并且现有的同构图池化方法对于异构图池化可能不是最优的。基于此，研究员们又提出了一种名为 HG-Pool 的异构图池化方法，如图8所示。该方法的核心思想是经过多次迭代，将一个大的异构图池化，并不断压缩为一个更小的异构图，直到获得最终的用户表示。在每次迭代中，研究员们使用类型特定的 GNN 模型从整个异构图的信息中学习每种节点的池化函数，这样能够充分考虑异构节点的特性。

图8：从个性化异构图学习用户表示的迭代图池化过程

HG-Pool 方法的框架如图9所示。对于每种节点，首先使用一个不同的池化 GNN 模型来学习类型特定的节点表示。然后使用带 softmax 激活函数的线性变换，将这些节点表示转换为类型特定的池化矩阵。最后使用 padding 后的池化矩阵，将当前邻接矩阵和节点特征矩阵转换为更小的矩阵。

图9：HG-Pool的示意图

研究员们基于 MIND 新闻推荐数据集进行了实验。表4的结果显示 User-as-Graph 可以显著提升新闻推荐中用户建模的效果，从而取得更好的个性化新闻推荐的性能。

表4：不同方法在 MIND 数据集上的比较

图10进一步比较了 User-as-Graph 和几种常用的基于用户行为的用户建模方法。实验结果表明，User-as-Graph 在用户建模上有更好的效果。同时图11比较了所提出的 HG-Pool 方法和几种同构图池化方法在新闻推荐上的性能。实验结果表明，HG-Pool 在异构图池化方面具有更好的效果。