【源头活水】无监督异常检测场景下如何自动选择模型？

“问渠那得清如许，为有源头活水来”，通过前沿领域知识的学习，从其他研究领域得到启发，对研究问题的本质有更清晰的认识和理解，是自我提高的不竭源泉。为此，我们特别精选论文阅读笔记，开辟“源头活水”专栏，帮助你广泛而深入的阅读科研文献，敬请关注。

来源：知乎—芝士确实是热量

地址：https://zhuanlan.zhihu.com/p/429199775

Title: Automatic Unsupervised Outlier Model Selection

Conference: NIPS 2021

论文地址：

https://www.andrew.cmu.edu/user/yuezhao2/papers/21-neurips-metaod.pdf

论文代码: 

https://github.com/yzhao062/UOMS

该篇paper的第一作者赵越（Yue Zhao）是异常检测领域贡献突出的作者之一，其贡献的pyod package是异常检测领域中的sklearn库，可以方便快捷的部署目前主流的异常检测算法；其github repo中anomaly detection resources更是收录了近几年异常检测算法中学习价值较高的书籍和paper，以及各类data与code，两个repo目前均超过了5k stars...

01

问题描述与基本思想

该篇paper要解决的核心问题在于，如何在无监督异常检测场景下，自动筛选最优的异常检测模型（包括所使用的算法框架+超参数）？这件事情乍一看是容易的，我们可以设立验证集，并利用验证集中的真实标签评判/选择最优的模型框架与超参数。但如果在没有真实标签的无监督场景应该怎么做这件事？——无监督场景下：1）通过验证集标签数据评判模型将不可用；2）模型之间的目标函数往往是不可以直接比较的，因而也无法通过loss进行评判。

该问题可以通过协同过滤算法（collaborative filtering, CF）在商品推荐中的冷启动问题来理解：对于一个新的顾客（数据库中没有该顾客的相关购买商品记录），如何依据数据库中现有的顾客购物记录对新的顾客进行精准推荐？

针对于上述提及的无监督异常检测模型选择（unsupervised outlier model selection, UOMS）问题，作者提出了METAOD方法对其进行有效解决。METAOD利用meta-learning的思想，对于待检测的数据集提取meta-feature，并利用meta-feature作为task similarity的一个衡量标准，寻找在以往task中表现最优的模型框架+模型超参数，从而在新的检测任务中进行快速部署。

读到这里可能有的读者会有疑问：那么METAOD的适用性有无可能仅限于new task和historical task比较相近的时候才work？事实上作者在paper中证明，当new task和historical task关联性不大时，METAOD也是SOTA...

02

算法部分

1. 整体逻辑

注：这里有个小typo，图的注释中U应该是指data matrix，V是指model matrix

首先，我们一起来厘清一下算法的整体逻辑：通过训练数据，得到模型在各数据集下通过某个指标反映的性能矩阵    ，进而通过矩阵因子分解（matrix factorization）将    分解为    和    ，其中    为data matrix，    为model matrix，即通过因子分解的方法构建了dataset-to-model之间的仿射变换关系；对于新的data而言，用    和原来的    做矩阵运算即可得到在新的data（新的task）下模型的性能矩阵，从而选出最优模型。下面我们分别按照训练部分和测试部分介绍算法框架：

2. 算法框架——训练阶段/meta-learner training/offline

首先是得到    矩阵。   矩阵的维度是    ，其中    为训练过程中数据集的个数，    为待选择的模型个数（为算法框架与超参数的组合数，文中共尝试了302种组合，见下图），    为第    个模型在第    个数据集下的表现（注意该步骤需要训练集中各个数据集的ground-truth label），通过Area under the precision-recall curve (AP)进行刻画。

关于矩阵分解    。矩阵分解的目的在于将衡量模型性能的矩阵    分解为    以及    ，即在    维的隐空间中构建dataset-to-model的仿射变换关系。文中使用了在推荐算法中常用的DCG（discounted cumulative gain）目标函数实现该矩阵分解。

DCG 提出在搜索结果（这里对应某个数据集）列表的较低位置上出现相关性较高的文档时（这里对应在该数据集上表现较好的模型），应该对评测得分施加惩罚。惩罚比例与文档的所在位置的对数值相关。DCG常用的公式形式如下，DCG的优化目标在于其值越大越好：

其中    代表出现在 第   个位置的文档与搜索结果的真实相关性，反映到paper即为第    个位置的模型与该数据集的模型真实性能。将    通过模型性能矩阵    代入重写可得

其中    为对某个模型在某个数据及下的预测性能，通过示性函数可以得到该模型的排名。参数    为放缩因子，一般取2。然而对于上述的DCG目标函数，由于其分母包含示性函数，导致DCG是不可导的，因此需要对示性函数这种nonsmooth indicator function进行smoothing，一个较好的方法是将示性函数替换为sigmoid平滑函数，如下式所述：

综上，DCG的目标函数可以转换为如下形式：

 对与上述目标函数，可以通过梯度更新的方式迭代计算得到    和    :

其中  ，  （详见论文中Appendix C）。

关于    的初始化与建模。上述步骤介绍了如何依据模型在不同数据集下的性能矩阵    进行因子分解得到    和    。但还有两个问题需要解决：1）    矩阵的初始化，作者发现    的初始化在很大程度上影响了DCG算法迭代的稳定性；2）上述算法得到的    矩阵（data matrix），只是反映了训练集中的数据集特性，对于新的测试数据集，如何得到    ？换言之如何构建映射关系，使得每一个新的数据集都能得到其对应的    ?

1) 文章通过利用统计特征+模型（对应第一个图中的函数    ），提取某个数据集d维的meta-feature，并进而通过PCA降至k维（对应第一个图中的函数    ），作为矩阵    的初始值    。

2) 学习一个实值映射函数    （某个回归模型即可，文中使用了random forest regressor），将    映射到DCG求解的矩阵    。该做法的目的在于，对于测试阶段，我们可以得到某个数据集的meta-feature，并且可以做PCA，得到    。但我们无法通过    得到    ，因为测试集没有ground-truth的labels可以让我们计算得到模型在数据集下的性能矩阵    进而实施DCG算法，所以需要学习映射函数    将    映射至    ，得到与数据集相关的data matrix。至于model matrix    ，利用训练集得到的矩阵    即可，因为model池是不变的。

关于    的初始化。矩阵   通过标准正态分布进行初始化。

介绍完算法框架在训练阶段的逻辑，读者应该对下述的算法流程框架有着更好的理解：

3. 算法框架——测试阶段/model selection/online

有了对上述训练阶段的解析，对于测试阶段是很好理解的：对于测试集数据集    （没有label），对其抽取meta-feature，然后通过PCA进行降维，之后通过random forest regressor得到    ，与训练阶段通过DCG算法求得的model matrix    做矩阵运算就得到了权衡在当前数据集下每个model的得分，将得分最高的model筛选出来即为最优模型：

4. 剩下需要解释的事情

meta-feature如何抽取？——文章通过统计特征+模型的方式得到某个数据集的meta-feature，如下表所示。其中统计特征包含样本个数、特征维数、均值、中位数等统计指标，模型则利用了四个可以快速部署、且算法特性不同（可以捕捉数据不同维度的特性）的方法：HBOD、LODA、PCA以及iForest。

测试阶段的成本？——测试阶段的主要三个成本来源：计算meta-feature、PCA降维以及random forest regressor预测，由于meta-feature主要包含统计特征与快速部署的模型，该部分成本并不高，而PCA降维以及regressor预测更时成本极少，所以METAOD整体算法在测试阶段能够快速筛选出当前数据集下最优的算法

03

实验部分

dataset：文章分别在两个场景下探究了METAOD的效果，如下图所示——1）不同的数据集呈现簇状的形式，相似性较高（共包含100个数据集，详见文章附录）；2）不同的数据集呈现离散的形式，相似性较低（共包含62个数据集，详见文章附录）。前者往往是做meta-learning比较合适的数据集，因为在依据测试集的相似性挑选出训练集中表现最好的模型，大概率也能在测试集中表现良好；后者为更加严苛的情况，文章也在后一种场景中探究了模型的适用性。

baseline：文章的baseline包括以下几种模型

1）无模型选择——包括LOF以及iForest

2）对所有模型进行集成——名为Mega Ensemble (ME)

3）simple meta-learners（例如简单选取在训练集中平均表现最好的模型）——包括Global Best (GB)，ISAC以及ARGOSMART (AS)

4）optimization-based meta-learners——包括Supervised Surrogates (SS)以及ALORS

5）METAOD的变体——METAOD_C，在训练阶段做因子分解时合并了meta-feature的信息；METAOD_F，固定data matrix    ，不让其参与DCG的优化过程。

实验结果

下图展示了不同模型对应的平均排名以及平均的AP。EUB (Emprical Upper Bound)反映了模型的上限。

图3反映出METAOD算法优于所有的baseline，并且几乎和EUB的效果相当。此外，有三个重要结论也可通过分析上图得到：1）将所有的模型预测结果进行集成并不能保证取得好的结果，ME甚至在所有模型中表现最差；2）并没有哪个模型是“常胜将军”，no free lunch理论再一次印证了这个结论；3）optimization-based meta learners普遍要比simple meta learners要好。

图4反映出METAOD甚至在数据集弱关联的情况下也有SOTA的效果。数据集的弱关联会影响meta-learning算法的效果，即算法的迁移性会受到影响。实验结果显示除了METAOD的meta-learning算法均在该场景中表现较差，但METAOD即使在数据集之前弱关联的情况下仍然取得了不俗的表现。此外，文章通过分析实验结果得出：1）对于optimization-based methods，训练阶段的稳定性对于算法的性能而言有着显著影响；2）在各数据集相似度较低的情况下，简单基于数据集相似度选择模型算法会失效（原文表述为“Glolabl methods outperform local methods under limited task similarity”）。

在文章最后，作者也分析了METAOD算法所需的计算成本。METAOD在大部分数据集下只需要不到1秒的时间即可选择出最优算法，且该过程相对于模型的建模而言只占了不到10%的时间（如图5所示）。模型生成meta-feature，以及选择最优模型的成本相对于训练而言基本可以忽略（如图6所示）。

04

结论与启发

该篇论文给予了我们一个全新的视角：在设计算法框架之外，利用合理的逻辑自动根据数据集选择合适的算法，从而达到SOTA的效果。METAOD不仅在学术界有贡献，在工业界的应用性甚至更广，因其能够较好的维护扩展（不断扩充算法池），并且有极快的部署效率（算法选择速度快）。此外，这篇文章对于笔者的启发在于，如何更好地根据数据集的特性选择合适的算法，未来可以比较METAOD和目前学术界其他sota算法之间的性能与理论差异。

参考文献

Zhao, Yue, Ryan A. Rossi, and Leman Akoglu. "Automatic Unsupervised Outlier Model Selection."

本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。

“源头活水”历史文章

更多源头活水专栏文章，

请点击文章底部“阅读原文”查看

分享、在看，给个三连击呗！