复杂稀缺类分析：稀缺与不重要能否划等号？-白红宇

复杂稀缺类分析：稀缺与不重要能否划等号？

阅读量：2242 次

发布时间：2019-05-09

本文共 4846 字，大约阅读时间需要 16 分钟。

⬆⬆⬆ 点击蓝字

关注我们

AI TIME欢迎每一位AI爱好者的加入！

在当代众多领域以及应用中，稀缺类经常扮演着极为重要的角色，如金融诈骗检测，流行预测，稀有疾病诊断等。然而现有机器学习技术的成功很大程度上依赖于大量的标签数据，以及对数据分布平衡的假设。众多机器学习模型在分析稀缺类的问题上经常受到很大的限制。因此，我们提出复杂稀缺类分析（Complex Rare Category Analysis）这个课题，并致力于以下三个子方向：

Q1.稀缺类特征描述（Rare Category Characterization）：如何在无标签或稀少标签的情况下对稀缺类进行特征描述？

Q2.稀缺类解释（Rare Category Explanation）：如何对稀缺类的预测模型以及其输出提供解释？

Q3.稀缺类生成（Rare Category Generation）：如何在学习到稀缺类的特征以及数据分布之后模拟生成稀缺类？

本期AI TIME PhD直播间，来自伊利诺伊大学厄巴纳-香槟分校计算机学院的周大为博士生做了题为《复杂稀缺类分析》的专题报告，为大家介绍了复杂稀缺类分析的挑战、具体研究的问题，并分享了他的相关研究成果以及未来研究方向。

周大为：伊利诺伊大学厄巴纳-香槟分校计算机学院学院博士生，导师为何京芮教授。主要研究方向为机器学习，数据挖掘以及复杂稀缺类分析。在上述相关领域，共发表国际会议和期刊20余篇, 如 KDD、WWW、AAAI、IJCAI、ICDM、CIKM、TKDD、DMKD。近五年，曾在多个计算机顶级国际会议中、任program committee，其中包括 ICML’20。

一、背景

我们生活的真实世界中，数据通常是长尾（long-tailed）分布的，类别数量分布存在严重不平衡。除了常见的头部数据，事实上在尾部还有很多并不被熟知的类别，比如洗钱、内部威胁、未知星系等，我们将其统称为“稀缺类（Rare Category/Class）”。

在很多领域稀缺类已被单独研究过，例如内部威胁、洗钱、独狼恐怖主义、基因疾病、身份盗窃、新兴趋势等。说到这里或许有人会问既然已经是稀缺类，那对我们的生活可能影响并不大，为什么还要花费大量精力进行研究？但事实上并不是这样的。

在很多领域，若缺乏对稀缺类的深入研究，可能会造成巨大损失。据数据显示，全球因恐怖事件导致的伤亡率正在逐年递增。世界范围内金融诈骗案层出不穷，造成的经济损失越来越大。仅2019年，网络犯罪就使美国公民损失超过了35亿美元。除此之外，重要信息的内部泄露，可能还会造成公关危机，导致国际关系紧张。这些惊人的事实背后是稀缺类分析的重要性。

稀缺类分析指分析不平衡数据集中代表性不足的少数群体类别，以解决以上提到的问题。之前这方面的研究主要关注本身的稀缺性或不可分离性，但显然这在当前的大数据时代是远远不够的，还有很多新的挑战和未被解决的问题。

C1：异构性

异构性主要体现在两个方面：

（1）不同的信息来源；

（2）不同类型的目标。

因异构性这一挑战的存在，提出了问题一：如何基于数据和任务异构性来表征稀缺类？

C2：可解释性

目前，许多机器学习模型本质上仍然是黑盒状态，没有办法提供准确的解释。但传统行业又非常依赖于模型的可解释性，因此问题二便尤为重要：如何解释预测结果并为终端用户提供相关线索？

C3:数据缺乏

由于数据敏感性（含性别，年龄等敏感信息）、数据安全和隐私、数据所有权等问题，导致分析时缺乏足够的数据。为突破这一困境，提出了问题三：如何减轻数据缺乏，并实现数据增强？

与很多现有研究课题不同，稀缺类分析考虑的是更为复杂的问题。在分析不平衡类时，通常会假设每个类都带有标签数据，但稀缺类分析一般没有/有一个/有很少标签数据。另外，不平衡类模型考虑的是所有类的整体准确性，而稀缺类模型则着重于学习表现良好的少数类。

另一个与稀缺类分析有关的领域是离群点/异常检测。虽然现已有很多方法可进行离群点/异常检测，但常用的还是统计上的定义，寻找统计上不符合常规数据分布的异常点。然而在很多现实应用中，这些离群点/异常并不是特别有意义，因为它们可能来源于一些噪声或已知特征的组合。稀缺类分析只关注异常中的一小部分，更为复杂和困难，但会更有意义。

复杂稀缺类分析主要围绕上文提到的三个挑战展开，致力于三个对应的子方向，分别提出了Characterization（特征描述）、Explanation（解释）、Generation（生成）三类模型，并且模型之间还可以进行交互，彼此互相影响。

二、稀缺类特征描述（Rare Category Characterization）

稀缺类特征描述是指在无标签或稀少标签的情况下对稀缺类进行特征描述，具体问题定义如下图所示。之前这类工作主要考虑样本之间的成对关系，但研究发现现实应用中高阶连通性模式（high-order connectivity patterns）可能更为有用。

高阶连通性模式主要研究两个问题：

（1）如何在大规模图形中通过高阶连通性模式检测稀缺类？

（2）是否可用一个带标签的样本来描述稀缺类？

讲者在《A local algorithm for structure-preserving graph cut》一文中将这些问题转化为局部图形切割问题和NP-hard问题，并提出了HOSPLOC(High-Order Structure-Preserving Local Cut，高阶结构保留局部切割)算法这一解决方案。

相较之前的工作，HOSPLOC算法具有多方面的优势。与Edge-based方法相比，HOSPLOC使用户能够灵活地对任何高阶网络结构进行建模。与全局方法相比，HOSPLOC采用的局部形式可扩展性更强、速度更快。

HOSPLOC算法主要分为三个步骤：

Step 1.通过构造原始图的邻接张量建模高阶模体；

Step 2.通过截断的高阶随机游走探索初始节点相邻上下文；

Step 3.在高阶随机游走的平稳分布向量上通过扫描切割程序进行结构保留的图形切割。

最后实验结果表明，HOSPLOC算法性能表现良好，具有很好的有效性和可扩展性。

三、稀缺类解释（Rare Category Explanation）

稀缺类解释是指对稀缺类的预测模型以及其输出提供解释，以帮助用户理解模型、数据结构和数据分布，具体问题定义如下图所示。之前相关工作更多考虑的是提高预测模型的表现，但大多本质上依然是黑盒状态，缺乏可解释性。因此，我们希望将二者结合起来，模型可以兼顾性能表现和可解释性，同时得到的结果符合规定。

基于以上，将研究问题分为了两个部分：

（1）数据方面，数据如何分布？对于给定的任务，哪一条信息相比其他更有价值？

（2）模型方面，为什么模型会对特定的信息做出特定的预测？

为了解决数据方面的两个问题，周大为提出了SPARC算法。SPARC采用组合的形式，有效地融合了稀缺类嵌入表示（Rare category embedding representation，RCE)和稀缺类特征描述（Rare category characterization，RCC)，既可以很好地进行预测，又能够通过embedding帮助用户理解数据分布。在这当中，RCE是指学习一个显著的代表，将稀缺类和其他类完全区分开来，RCC是指确定一组可能来自稀缺类的样本。最后的实验结果表明，SPARC算法在两个问题上都有很好的表现。

关于模型方面的问题，采用的解决办法是RCA_NALYZER，一个用于动态图中稀缺类分析的可视化分析系统，主要包括了数据探索、特征选择、稀缺类分析三个模块。

四、稀缺类生成（Rare Category Generation）

稀缺类生成是指在学习到稀缺类的特征以及数据分布之后模拟生成稀缺类，具体问题定义如下图所示。之前稀缺类分析很少考虑到数据稀疏的问题，因此在处理稀疏网络时是存在极大困难的。另外，已有的SMOTE（ Synthetic Minority Oversampling Technique，合成少数类过采样技术）可以对少数类样本合成新样本，但并不适用于图结构数据。

稀缺类生成部分主要解决两个问题：

（1）无监督的稀缺类生成，是否可以通过加入合成连接增强稀疏网络？

（2）有监督的稀缺类生成，是否可以在不发布敏感信息的情况下生成特定任务的数据集？

针对问题（1）提出的解决办法是TagGen，是第一个用于时间交互网络的数据驱动的图形生成模型，可生成数据增强的合成时间交互网络。而问题（2）是未来的研究方向，希望构造具有隐私保护的标签信息图生成模型。

现有的传统生成模型大多数都是为静态网络设计的，并且它们一般都需要基于某些特定的结构假设，如重尾度分布、小直径、局部聚类等。最近的深层生成模型更多的是数据驱动，不需要加入预先的结构假设，并且在动态图形中同样适用。

时间节点和时间发生是TagGen涉及的两个概念，具体定义如下图所示。

下图描述了TagGen模型的问题定义，给定一个被表示为时间戳边缘集合的时间交互网络，模型的任务是生成一个新的合成时间交互网络，可以准确地捕获所观察到的时间网络的结构和时间特性。

在框架结构上，TagGen主要包括采样、生成、鉴别、收集四个部分。首先通过一种新的采样策略，通过采样一组时间随机游动来提取时间交互网络的网络上下文信息。其次，开发了一个深层生成机制，它定义了一组简单而有效的操作（即在时间边缘上添加和删除）来生成合成随机游动。然后，在采样的时间随机游动上训练鉴别器，以确定生成的时间随机游动是否遵循与实际随机游动相同的分布。最后，通过鉴别器收集符合条件的合成时态行走，生成时态交互网络。