前言

最近半年时间（2019年1月到今天），我和几个小伙伴参加了清华大学举办的【多维监测指标的异常定位】AI OPS比赛。总共327个队伍参加比赛，经过我们的努力，我们进入决赛，并且通过代码审核，成为最终进入决赛阶段的14个队伍中的一员。今天就是决赛的尾声，程序已经调通，正在调参等待结果，所以想借这个时间写点什么，对这段工作做一个总结。

问题背景

多维度指标的异常定位是AI Ops领域的一个典型且有挑战的问题。在互联网服务运维中，当某个总指标（如总流量）发生异常时，需要快速准确地定位到是哪个交叉维度的细粒度指标（如“省份=北京 & 运营商=联通”的流量）的异常导致的，以便尽快做进一步的修复止损操作。由于运维中的指标维度多、每个维度取值范围大，导致异常定位时的搜索空间非常大(可能的搜索空间$2^{10000}$)。

本质上这是一个搜索问题，而不是传统机器学习比赛中的回归或者分类问题。所以，我们平时积累的机器学习技术能力只有很少的一部分能够使用。不过，从另一个角度来看，说明我们平时积累的技术有短板，正好通过这个机会补足。

我们经历了什么？

接到这个比赛的任务的时间是今年1月初，当时官方给了参考资料如下，

经过一个多月的学习，我们大概对上面三个算法有所了解，三篇文章解决的思路为，

  • 整体框架使用启发式规则；
  • 局部行为使用数据挖掘，机器学习或统计等技术，提高准确率；
  • 算法实现难度：Aditributor $<$ iDice $<$ HotPot；
  • 算法精准度：Aditributor $<$ iDice $<$ HotPot，（HotSpot的论文实验数据显示）

具体的论文导读，可以参考本文最后的附录。

预赛第一个阶段3月底结束，我们当时实现了Aditributor算法，最后的得分为0.18，而排行榜第一名的得分可以达到0.97（1为满分）。令人窒息，感觉这次果然是跨界打酱油了。我们决定果断放弃实现iDice，而是直接开始实现HotPot，希望可以得到比较理想的成绩。

预赛第二阶段，Hotspot那篇论文花了两到三周的时间琢磨整个算法，然后花了2周的时间实现，最后在5.1劳动节假期实现了完整版本，在预赛第二阶段的比赛中得到了0.49的得分，排名为18名。不过，在代码中有个bug（在预赛第三阶段才发现，所以导致得分不是特别理想）。

预赛第三阶段，找到了之前提到了那个bug，并修复，得分有大幅度提升，但是没有排到理想位置。后来，我们发现一个规律可以筛选出潜在候选集，然后使用MCTS在这个候选集中找到根因，可以极大的提升得分。并且，我们发现即使不需要MCTS，只需要在这个候选集合中直接计算PS，都可以得到比较好的结果。所以，我们认为MCTS的作用不是特别大。最终，在5月26日，我们用完了最后的提交机会，获得了0.64的分数，较稳的排在了前16的位置，进入了决赛。

决赛阶段只有一周时间，主要是将算法改为增量执行模式。在这个过程中，无法使用异常时刻之后的数据，这样会很大的影响KPI预测质量。整个结果已调通并且提交可执行程序，最终得分为0.6089，排名14/327,Top 5%。期间还有个小插曲，在进入决赛前，也就是第三阶段结束后，组委会review代码。由于提交代码时，有个非常重要的参数写错了，导致结果不能复现，经过紧急与组委会沟通，调整该参数，最终结果在组委会提供的环境复现，进入决赛，虚惊一场。

收获和总结

经过这次比赛，本人还收获了不少，

  1. 开阔了视野，了解了AI在运维领域中的实践，尤其是多维监控问题；
  2. 实战应用了MCTS的运行机制，后面也许有用；
  3. 累积了平级跨团队合作的经验，对后面的工作有所帮助；
  4. 连续3个多月的周末和假期都投入到这个比赛中，这种体验也比较难得，多年后回忆起这段时光，也许别有一番滋味。

附录1 Aditributor导读

着重阅读第3章，算法介绍。第4章将算法扩展到衍生指标，与本次比赛无关，有兴趣的同学可以看下。其他章节是背景介绍，问题定义，实验等。算法核心规则如下，

Explanatory Power

  • $ EP_{ij} = \frac{A_{ij}(m)-F_{ij}(m)}{A(m)-F(m)} $
  • 度量变化占比

Surperise

  • 度量指标分布的变化
  • 使用JL散度，KL散度的变种。
  • KL不对称，而且在概率为0有严格要求，不适合当前场景。

附录2 iDice导读

第四章介绍iDice核心算法。核心算法主要分为三部分，

Impact based Prunning

  • 核心思想：一个有用组合必须引起较大数量变化。
  • 频繁集合裁剪非频繁项，与时间无关，例如啤酒和尿布问题。

Change Dection based Pruning

  • 核心思想：一个有用组合必须在时间点上符合变化特征。
  • 检查集合下数据是否在时序上符合特征，例如Figure 1中跳跃点在8th-Dec。使用Generalized Likelihood Ratio计算时序差异。

Isolation Power based Pruning

  • 核心思想：合并多余组合。
  • 方法借鉴决策树中信息增益的思路，将Entry增减明显的属性集合放在前面。

附录3 HotSpot导读

此论文核心思想有三个

  1. Potential Score计算，这个指标还是比较赞，虽然仍有不完美，但是在我们的比赛中起到了较关键的作用；
  2. MCTS启发式搜索，其实只用了TS，没用MC；我们认为这个比较鸡肋，估计用了这个好发文章，毕竟Alpha Go也用了这个技术。
  3. 贪心逐层剪枝策略。