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 方法的表现

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

论文链接：

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

05 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 在异构图池化方面具有更好的效果。

图10：不同用户建模方法的比较。UaG 是 User-as-Graph 的缩写

图11：不同图池化方法的比较

*博客内容为网友个人发布，仅代表博主个人观点，如有侵权请联系工作人员删除。