IJTCS 2021 | 大会特邀报告精彩回顾：机器学习方向
编者按
2021年8月16-19日，第二届国际理论计算机联合大会（International Joint Conference on Theoretical Computer Science，IJTCS）线上线下交互举行。大会由北京大学与中国工业与应用数学学会（CSIAM）、中国计算机学会（CCF）、国际计算机学会中国委员会（ACM China Council）联合主办，北京大学前沿计算研究中心承办。
小编将分方向带来“大会特邀报告”精彩回顾。本期为“机器学习”方向的3个特邀报告，分别来自微软亚洲研究院首席研究员陈卫、德国萨尔大学教授 Holger Hermanns、纽约州立大学布法罗分校副教授栗师，介绍了机器学习方法及其理论分析领域的研究成果。
Data-driven optimization --- Integrating data sampling, learning, and optimization
陈卫，微软亚洲研究院
在报告中，陈教授首先指出，传统研究中存在着机器学习和优化分离的问题，体现在二者有各自不同的目标，影响着各自效果的表现。陈教授用 GPS 导航等多个例子展示了这样分离的学习和优化方案伴随的缺乏端对端客观性及反馈等不足之处。
针对这些问题，陈教授给出了两种解决方案：其一称为OPSS（Optimization from Structured Samples），通过在抽样数据中得到更多有关于数据结构的信息，来提升优化效果，达到数据驱动型的优化方案；其二是结合在线学习的优势，利用在线学习的反馈提高采样和优化的有效性。
报告的研究证明了在分布满足三个条件（可行性，采样充分性和非正相关性）之时，OPSS 具有常数近似比，并且这三个条件缺一不可。陈教授还展示了这项工作在多种具体问题上的运用，并与传统的包括 UCB1 等在内的算法进行了对比，从中体现从样本结构出发的优化方案和在线学习算法的运用带来的对于优化结果的改善。
最后，陈教授提纲挈领地展望了未来可能的研究的方向，对该项技术运用的前景表示了期待。
Model-based Digital Engineering and Verification of Intelligent Systems
Holger Hermanns, Saarland University
在报告中，Hermanns 教授指出，许多未来科技的发展如自动驾驶等都希望排除人工干扰，这要求软件能够对环境自动做出决策，但这种排除人工的决策经常被人怀疑缺少可解释性与可信性，因此需要一些安全标准对软件的 RAMS（Reliability-Availability-Maintainability-Safety）做出评估。以自动驾驶为例，汽车行业的 ASIL 将安全等级按照严重性、暴露性、可控性进行分类，这其中体现了自动驾驶技术当前的挑战：自动驾驶意味着较为不可控，因而需要提供更高的安全保证；但基于 ML 的组件尤其是神经网络虽然平均性能很好却十分容易受到欺骗，难以提供这种保证。
现实中的自动驾驶过于复杂，为了进行评估需要将真实场景抽象为实验环境，Hermanns 教授给出了一种抽象：环境中只有实验车辆，去除其他交通参与者，并将其考虑为一个马尔可夫决策过程。具体地说，车在一个二维网格中移动，希望找到从起始的绿色格点到目标的红色格点的最优路径，每步状态包括起始位置、目标位置与当前位置；每一步根据当前速度改变位置，可选的决策为选择一个加速度来改变下一步的速度；除此之外还需要加入一定的失败率（噪声），如有20%的概率速度不会改变，作为路面湿滑等随机情况的模拟。
基于这种抽象，Hermanns 教授介绍了几篇相关的工作：
Deep Statistical Model Checking. 该工作使用统计学方法分析了神经网络模型在各种不同情况下的事故率与到达率，并提出了评估模型学习时间的方法。
TraceVis. 该工作将自动驾驶决策可视化，从而更直观地了解其机制。
Verification of NN-in-the-loop. 该工作提出了分析自动驾驶程序以验证安全性的方法。
Fuel Consumption, Road Conditions, Engine Variants. 该工作去除了一些抽象，加入油耗、路况变化及引擎功率限制，使模型更接近实际情况。
最后，Hermanns 教授指出我们离自动驾驶的最终目标虽然还有些遥远，但已经有了一些热点方法，如 Neuro-Symbolic Methods、Hierarchical Methods 等，并对自动驾驶的未来充满了信心。
Tight Online Algorithms for Unrelated Machine Load Balancing with Predictions
栗师，纽约大学布法罗分校
首先，栗教授简单介绍了这一工作的背景，即学习增强在线算法（Learning Augmented Online Algorithms）下的无关机器负载平衡（Unrelated Machine Load Balancing）问题：随着机器学习任务的增多，学习增强在线算法逐渐成为在线算法的一个新方向。我们现在要执行的任务具有一定程度上的周期性，即在不同时段内执行的任务会具有一定程度的相似性。那么，我们可以将之前若干周期的知识输入学习算法中，以便产生对当前周期需要执行的任务的一个预期。比起传统算法，该算法克服了最坏情况、无分布知识的缺点，并且更具有灵活性。此外，我们希望设计的算法有效、简洁、稳健。在这一背景下，无关机器负载平衡问题希望寻求一个算法，其输入是 n 个工作，m 个机器，每个工作与若干机器间的连边集合 E（表示可以执行该工作的机器的集合），以及对这些边的赋值 p（表示特定机器处理特定工作的任务量）。算法的输出是把每个工作分配给一个机器，而目标则是最小化最大负载，即最小化所有机器中任务量最多的机器的任务量。
在在线算法的运行过程中，每个工作按照某种顺序到来，在到来之前无法看到其对应的各机器的任务量。相对应的，离线情况下则是预先告知了所有工作及它们的任务量。“竞争比”定义为在线算法的花费和离线情况下最优解的花费之间的比例。
栗教授介绍了现在已知的结果：对于离线的任务，2倍最佳估计存在多项式时间的算法，而1.5倍则非常困难；对于在线的任务， 是竞争比的紧下界。
由此，栗教授引出了报告要讨论的问题：如果预先知道了输入的工作的某种信息（例如，通过总结经验），我们能否获得比 更好的结果？
首先，栗教授肯定了这个问题的答案：根据2020年 Lattanzi et.al 的结果，如果预先知道每个工作在每台机器上的运行时间都是恒定的，并且给定一个对于输入的预测权重向量 w，就可以得到一个竞争比为 的随机算法。
随后，栗教授介绍了自己在今年的工作：他和合作者证明，在一般的负载平衡问题中，如果以对偶向量 β 和权重向量 w 作为预测，那么，存在一个竞争比为 的确定性算法和一个竞争比为 的随机算法，并且这两个结果都是紧的。
Reference:
Lattanzi, S., Lavastida, T., Moseley, B., Vassilvitskii, S.: Online scheduling via learned weights. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1859-1877. SIAM, (2020).
相关链接
文字 | 艾瑞、霍子璇、李东晨、凌弘毅
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。
点“阅读原文”转大会相关报道