简要介绍Active Learning(主动学习)思想框架,以及从IF(isolation forest)衍生出来的算法:FBIF(Feedback-Guided Anomaly Discovery)

1.引言本文所讨论的内容为笔者对外文文献的翻译,并加入了笔者自己的理解和总结,文中涉及到的原始外文论文和相关学习链接我会放在reference里,另外,推荐读者朋友购买StephenBoyd的《凸优化》ConvexOptimization这本书,封面一半橘黄色一半白色的,有国内学者翻译成了中文版,淘宝可以买到。这本书非常美妙,能让你系统地学习机器学习算法背后蕴含的优化理论,体会数学之美。本文主要围...

简要介绍Active Learning(主动学习)思想框架,以及从IF(isolation forest)衍生出来的算法:FBIF(Feedback-Guided Anomaly Discovery)

1. 引言

本文所讨论的内容为笔者对外文文献的翻译,并加入了笔者自己的理解和总结,文中涉及到的原始外文论文和相关学习链接我会放在reference里,另外,推荐读者朋友购买 Stephen Boyd的《凸优化》Convex Optimization这本书,封面一半橘黄色一半白色的,有国内学者翻译成了中文版,淘宝可以买到。这本书非常美妙,能让你系统地学习机器学习算法背后蕴含的优化理论,体会数学之美。

本文主要围绕下面这篇paper展开内涵和外延的讨论:

[1] Siddiqui M A, Fern A, Dietterich T G, et al. Feedback-guided anomaly discovery via online optimization[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM, 2018: 2200-2209.

同时会在文章前半部分介绍这篇paper涉及到的2个主要理论:1)Active Learn;2)(online) Convex Optimization;3)isolation forest的相关内容请参阅另一篇blog。

笔者这里先简单概括一下这篇笔者所理解的这篇paper的主要核心思想:

1. 主动学习思想的融合:

主动学习,也叫查询学习,它要求算法在每轮学习迭代中能够基于某种策略,从当前样本集中选择出“最不确定的一个或一组样本”。从这个角度来思考,无监督异常检测算法普遍都能胜任这个目标,作者在paper中也提到了这个框架的可插拔性,paper中选择了isolation forest孤立森林算法,每一轮迭代中,通过不断将 isolation tree 当前不确定的数据(无监督模型发现的异常数据),也即最浅路径叶节点输出给外部反馈者并接受feedback label(正例 or 负例),以此获得一批打标样本。

值得注意的是,这种反馈算法框架和具体的abnormal detection algorithm无关,不管是generalized linear anomaly detectors (GLADs)还是tree-based anomaly detectors,都可以应用。相关的讨论可以参阅其他的文章:

Active Anomaly Discovery (AAD) algorithmhttps://www.onacademic.com/detail/journal_1000039828922010_bc30.htmlhttps://www.researchgate.net/publication/318431946_Incorporating_Feedback_into_Tree-based_Anomaly_Detection Loda: Lightweight on-line detector of anomalieshttps://link.springer.com/article/10.1007/s10994-015-5521-0SSAD (Semi-Supervised Anomaly Detection)Active learning for network intrusion detectionhttps://www.deepdyve.com/lp/association-for-computing-machinery/active-learning-for-network-intrusion-detection-4Y5zwDUev5 Toward Supervised Anomaly Detectionhttps://jair.org/index.php/jair/article/view/10802

但是仅仅融入和主动学习还不够的, IF算法是无监督的,无法处理这批打标样本,我们还需要引入有监督训练过程,将外部反馈的新信息输入到模型中被存储以及记忆。

2. 凸优化框架的融合:

Isolation tree是一种树状结构,每个样本数据都是树中的一个叶节点。作者创造性在原始 Isolation tree 的基础上,将叶节点所在边赋予了权重w的概念,并将feedback数据(相当于label有监督标签)作为目标label值。这样,每次获得feedback反馈后,就可以基于这批feedback数据(例如100个)进行多元线性回归的参数学习,即回到了有监督学习的范畴内。具体的涉及到Loss Function如何选择,文章接下来会详细讨论。

2. Active Learning(主动学习)

0x1:主动学习基本概念

主动学习(查询学习),是机器学习的一个子领域。主要的思想是:通过一定的算法查询最有用的未标记样本,并交由专家进行标记,然后用查询到的样本训练分类模型来提高模型的精确度

0x2:什么场景下需要主动学习

1. 项目是冷启动的,在冷启动初期,标签数据是非常稀少的,而且打标成本也相对比较高;2. 项目虽然不是冷启动,但是很难通过专家构建多元线性分类器,换句话说就是很难通过写出一条条实值规则的逻辑组合。这在实际工作中也是非常常见的,典型地表现会是安全运营人员会发现自己的专家经验“很难准确定义”,往往是通过长时间地不断调整逻辑组合以及判别阈值threshold后,可能依然无法做到0误报0漏报。显然,人脑不适合高维的、高精确度的复杂线性函数的处理。但是与此同时,人脑又善于根据复杂的高纬度特征,得出一个模糊性的综合判断。例如,当一个安全专家具体拿到某个样本的时候,他通过经验还是能够较快判断出正例/负例,在大多数时候,这个判断又是非常准确的。笔者认为,我们需要通过机器学习辅助我们进行安全数据分析的一个原因就在于:人脑似乎可以进行非常复杂的逻辑判断,但是却很难数学化地准确表达出自己具体是怎么得到这个结果的。人的经验在很多时候是很准的,但是你要是问他到底是怎么判断的,他往往只能沉思片刻,然后露出一副坚定而微笑的表情,凭经验判断的!而通过机器学习的训练过程,让机器从数据中学习到人的模糊经验,得到一个数值化的、可稳定复现的决策系统。3. 无监督算法得到的异常未必就对应了业务场景中的一个真实异常事件,即算法层面的outlier和真实业务场景中的abnormal_target往往是存在一个gap的。我们知道,无监督异常检测算法是根据特征工程后的特征向量进行数值计算后,得到一个异常值排序,这就导致特征工程的结果会极大影响之后的算法运行结果。针对这一困难,传统方法是需要模型开发者基于对业务的理解去优化特征设计,甚至优化样本集。这一优化通常是纯粹基于经验和尝试的,过程中由于缺少标签指引,其迭代过程甚为繁琐。

0x3:主动学习算法模型框架

主动学习的模型如下:

A = (C,Q,S,L,U)

其中L 是用于训练已标注的样本;
C为一组或者一个算法模型,用户接收上一轮的标记样本集,通过负反馈调整模型参数,并输出对应的预测结果向量集;
Q是查询函数,用于从当前剩余的未标注样本池(未标记样本会逐渐减少)U 中查询信息量最大(最不确定)的top样本;
S是督导者,可以为 U 中样本标注正确的标签;
active learning模型通过少量初始标记样本 L 开始学习,通过一定的查询函数 Q 选择出一个或一批最有用的样本,并向督导者询问标签,然后利用获得的新知识来训练分类器和进行下一轮查询。主动学习是一个循环的过程,直至达到某一停止准则为止。
需要注意的是,active learning是一个算法框架,上图中的单个模块具备可替换性(alternative),我们接下来讨论具体每个子模块的选择原则。

1. 机器学习模型C

只要是有监督学习算法即可。

2. 查询函数Q

查询函数的设计最常用的策略是:不确定性准则(uncertainty)差异性准则(diversity)

1)不确定性准则对于不确定性,我们可以借助信息熵的概念来进行理解。我们知道信息熵是衡量信息量的概念,也是衡量不确定性的概念。信息熵越大,就代表不确定性越大,包含的信息量也就越丰富。

不确定性策略就是要想方设法地找出不确定性高的样本,因为这些样本所包含的丰富信息量,对我们训练模型来说就是有用的。

2)差异性准则(diversity)

查询函数每次迭代中,查询一个或者一批样本。我们希望所查询的样本提供的信息是全面的,各个样本提供的信息不重复不冗余,即样本之间具有一定的差异性(概率分布尽量全面)。
在每轮迭代抽取单个信息量最大的样本加入训练集的情况下,每一轮迭代中模型都被重新训练,以新获得的知识去参与对样本不确定性的评估可以有效地避免数据冗余。但是如果每次迭代查询一批样本,那么就应该想办法来保证样本的差异性,避免数据冗余。

0x4:Online Active learning or Batch-size Active learning?

通俗地理解,Online active learning就是模型一次只输出一个预测样本给打标员,打标员通过检视后将反馈结果输入回模型,完成一次迭代。

Batch-size active learning是模型一次输出一整批数据(例如128),打标员统一打标后,统一将结果输入回模型。

理论上说,online learning更利于逼近全局最优,但是在实际工程中,online learning并不容易做到,因为人是不可能持续地一个样本一个样本的打标的,人毕竟不是机器,人会疲劳。因此,笔者在实际项目中,对原始论文中的Online部分修改为了Batch-size,通过一次积累一个batch样本,然后依然流式地逐一输入给原算法。

和online GD和batch-size GD问题一样,batch-size可以理解为对online的一种近似模拟,一般情况下,只要batch不要设置地太大(32-64),对最终结果的影响基本上可以忽略不计。

论文原作者提出的是online active learning,在实际工业场景中,online active learning的部署成本很大,我们一般采用small batch-size active learning代替,总体上效果影响有限。

Relevant Link:

https://blog.csdn.net/Jinpeijie217/article/details/80707978https://www.jianshu.com/p/e908c3595fc0https://www.cnblogs.com/hust-yingjie/p/8522165.html

3. (Online) Convex Optimization Framework

0x1:凸优化简介

凸优化在数学规划领域具有非常重要的地位,一旦将一个实际问题表示为一个凸优化问题,大体上意味着对应问题已经得到彻底解决。从理论角度看,用凸优化模型对一般非线性优化模型进行局部逼近,始终是研究非线性规划问题的主要途径。

从理论推演脉络角度来说,凸优化理论是研究优化问题的一个重要分支。实际上,最小二乘以及现行规划问题都属于凸优化问题。

0x2:在线凸优化算法流程

下图展示在线凸优化的伪码流程图:

在一轮的迭代中,都要从凸集中选择一组向量序列w,并选择一个损失函数f()用于计算和目标值之间的差距。

算法的最终目标是:通过选择一组权重w序列,以及一组损失函数,并使总体的离差最小。

Relevant Link:

https://www.cnblogs.com/wzdLY/p/9569576.htmlhttps://www.cnblogs.com/wzdLY/p/9570843.html https://www.jianshu.com/p/e908c3595fc0

4.Feedback-Guided Anomaly Discovery via Online Optimization

0x1:FBIF和传统IF(isolation forest)的区别

我们在文章的开头已经讨论了FBIF的主要思想,下面通过一个图例来说明,FBIF是如何具体解决传统IF的缺陷的。

1. 传统IF问题

传统IF检测异常时通常会将头部异常样本集(通常不会太多)输出给分析师,借助他们的专家经验判定是否为所要抓捕的风险,若准确率满足要求则进行生产部署,若不满足要求,则需要建模人员和分析师一起尝试修改特征工程,或者通过白名单排除一些样本集,这是一个将分析师的

源文地址:https://www.guoxiongfei.cn/cntech/18372.html