Lifelong Anomaly Detection Through Unlearning(UCB,CCS'19)

主要贡献

  1. 首次提出终身的深度学习来进行异常检测。为此提出了一个unlearning框架。
  2. 提出了一个解决爆炸损失(exploding loss)和灾难性遗忘(catastrophic forgetting)的方法,前一个是异常检测的问题,后一个是解决终身学习的问题。
  3. 抽象了一个理论的框架可以生成异常检测的模块,unlearning方法可以作为一个普适的方法。
  4. 使用三个数据集:hdfs日志;Yahoo网络流;信用卡交易记录。

终身异常检测

实例

以CPU-high为例,可能是一种异常的表现。假设训练数据有ssh->program->exit->CPU-high和ssh->game->exit->CPU-high两种。zero-positive模型可能训练出来ssh->***->exit->CPU-high这样的模式。但是用这样的模式进行异常检测是,可能检测出ssh->notepad->exit->CPU-high,但是这是正常的。造成这样结果的原因是因为训练数据不完整因此不能有效识别出那些导致CPU-high的活动。

真实的场景中往往采用的是让管理反馈FN和FP的例子。本文使用的终身学习来检测异常,这是一种增量的方式可以更新模型来报告FN和FP的情况。

问题定义

形式化一个zero-positive异常检测问题并且阐述如何生成一个ML的模型来解决问题。

问题定义(Anomaly detection): 考虑一个事件\(x_t(1\leq t\leq T)\),采样自一个固定分布\(\mathcal{D}\),概率为\(1-\epsilon\)。对于接下来的实例\(x_t(t>T)\)进行检测其是否来自同样的分布。

上述定义中\(x_1,...x_T\)是训练数据,常量\(\epsilon\)表示的是异常出现的频率,当其等于0时则说明训练数据种不存在异常。

之前的zero-positive工作都假设训练数据完全正常,但是也存在偶尔人工标注错误的情况,因此在本文中考虑噪音数据,也就是说有\(\epsilon>0\)但是该值非常小。

分布假设: 不同应用对于分布有不同的假设,所以不同的ML模型应该被设定成可以利用这个分布。大体来说考虑以下两种分布:时间敏感分布和时间不敏感分布。

  • 时间不敏感分布: 在任意时间\(t\),每个值都是互相独立的,概率质量函数为\(Pr(x_t)\)
  • 时间敏感分布:时间\(t\)对应的值依赖于历史记录,概率质量函数为\(Pr(x_t|x_{t-1}...x_1)\)

终身学习: 在上述定义中,训练数据是无标签的因此会非常不准确。在真实场景中,可以人工检测一些可疑的样例然后提供一些标签。在本次工作中,我们主要考虑能不能通过这样的方法提高准确率。

问题定义(Lifelong Anomaly detection): 考虑一个事件\(x_t(1\leq t\leq T)\),采样自一个固定分布\(\mathcal{D}\),概率为\(1-\epsilon\)。此外,我们还有一个集合有n对\((t_i,l_i),1\leq t_i\leq T,l_i\in {-1,+1}\)。假如\(x_{t_i}\)是从\(\mathcal{D}\)中采样的那么\(l_i\)为负。对于接下来的实例\(x_t(t>T)\)进行检测其是否来自同样的分布。

注意这里人工标注数据量较少且可能出错,我们把\((t_i,l_i)\)\(l_i=+1\)的视作FN,\(l_i=-1\)视作FP。

通用的ML异常检测理论框架

通用的异常检测框架

通过一个事件序列我们可以很容易学习到其概率质量函数,也就是其分布,然后进行异常检测。因此,大多数的异常检测算法依赖ML通用模型。模型考虑两类随机变量:观测变量X和隐藏变量H。假设联合概率\(Pr(X,H)\)是通过函数\(f_\theta(X,H)\)模型化的,其中\(\theta\)是参数,那么\(X\)的边缘概率是 \[ \operatorname{Pr}(X)=\int_{h} f_{\theta}(X, H=h) \]

学习算法寻找一组参数\(\theta\)可以最大化相似性或者优化其等价转换:

\[ \begin{aligned} \theta^{\star} &=\underset{\theta}{\operatorname{argmax}} \prod_{x_{t}} \operatorname{Pr}\left(X=x_{t}\right) \\ &=\underset{\theta}{\operatorname{argmax}} \prod_{x_{t}} f_{\theta}\left(X=x_{t}, H=h\right) \end{aligned} \]

通过这样的模型我们可以找到某个实例\(x\)是否超出阈值。除此之外还有很多模型,比如说高斯混合模型、PCA、LSTM,自动编码器等。

LSTM

为了计算LSTM模型,公式如下: \[ \begin{aligned} h_{t-1} &=f_{\theta}\left(h_{t-2}, x_{t-1}\right) \\ \operatorname{Pr}\left(x_{t} | x_{1} \ldots x_{t-1}\right) &=g_{\rho}\left(h_{t-1}, x_{t}\right) \end{aligned} \] 这可以迭代计算每个时间\(t\)的值。一种计算概率从而确定异常的方式就是与其事先确定的阈值进行比较,如下图:

如果事件是连续的,一种方法是利用概率密度函数来预测下一个值,然后与实际值进行比较是否偏离过大。

LSTM的优点是可以自动学习去遗忘那些序列中的非基本事件,因此可以有效地处理截断的数据(模型从数据中间开始运行)和噪音数据(训练中的异常数据)。因此本文选择LSTM作为时间敏感分布的模型基础。

自动编码器

当事件与时间是独立的,我们就无需考虑历史记录。这种情况下,autoencoder是非常有效的。编码器为\(\phi\),解码器为\(\varphi\),这两个都是带参的函数。encoder可以将输入\(x\)映射到隐藏状态\(h=\phi(x)\), decoder可以将\(h\)映射到输入空间里的一个实例上\(x', x'=\varphi(h)\),作为一个通用的模型,联合概率为 \[ Pr(x,h) \propto exp(-||x-\varphi(\phi(x))||^2/2) \]

主要就是看一个输入通过encoder和decoder之后,结果与原输入的差别大小。

训练模型

为了严谨使用事件序列,我们将事件编码成一个数字向量,对于连续值的事件可以直接当作向量使用;离散值的事件使用one-hot编码;混合的既有离散值也有连续值的可以将他们分开进行转换然后连接向量成为一个较大的向量。

为了训练模型,等价于最小化\(-logPr(X)\),我们用损失函数进行定义,对于时间敏感的实例,RNN的模型loss-function可以定义为: \[ \mathcal{L}_{\theta, \rho}(X)=\sum_{t=1}^{T}-\log \left(g_{\rho}\left(h_{t-1}, x_{t}\right)\right) \]

其中\(h_t\)是可以递归定义的,且初始化为0。对于autoencoder,损失函数为 \[ \mathcal{L}\left(x_{t}\right)=\left\|x_{t}-\varphi\left(\phi\left(x_{t}\right)\right)\right\|^{2} \]

深度学习依赖反向传播来计算损失函数的梯度,并且通过梯度来更新\(\theta\),利用SGD作为例子,那么\(\theta\)的更新如下: \[ \theta_{\text {new }} \leftarrow \theta_{\text {old }}-\eta \cdot \nabla_{\theta} \mathcal{L}_{\theta} \] 其中\(\eta\) 是一个值很小的静态变量,代表学习速率和步长。

Unlearning用在异常检测模型的更新

当部署一个ML模型后,目标就是根据新报告的FP和FN样例进行更新模型。现有的生成模型并不会支持这样的更新过程。主要思路是,一旦我们知道了\(x_t\)是FN,我们要最小化概率\(Pr(x_t|x_1,...x_{t-1})\),如果直接做可能会有问题,比如梯度爆炸和灾难性遗忘。Unlearning方法可以不伤害其他无标签数据的情况下进行实现。

不仅仅是FP,正常的事件都可以用常规方法进行处理。

Unlearning 概览

考虑时间不敏感的例子(方法可以扩展到时间敏感的例子上)。首先考虑包含了一个positive样例\((t,+1)\)的有标签数据集,这样\(x_t\)被错误估计成负样本 \[ Pr(x_t) > \tau \] 对于一个阈值\(\tau\),等价于 \[ \mathcal{L}(x_t) < \tau' \] 对于对应的阈值\(\tau'\), 我们的目标是修改模型来减少\(Pr(x_t)\)的可能性,或者等价于增加\(\mathcal{L}(x_t)\) \[ \mathcal{L}_{unlearn}(x_t) = -\mathcal{L}(x_t) \] 因此我们可以应用同样的优化算法进行\(\mathcal{L}_{unlearn}\)的最小化训练,计算梯度: \[ \nabla_{\theta} \mathcal{L}_{\text {unlearn }}\left(x_{t}\right)=\nabla_{\theta}\left(-\mathcal{L}\left(x_{t}\right)\right)=-\nabla_{\theta} \mathcal{L}\left(x_{t}\right) \] 因此应用更新规则如下: \[ \theta_{\mathrm{new}} \leftarrow \theta_{\mathrm{old}}-\eta \cdot \nabla_{\theta} \mathcal{L}_{\mathrm{unlearn}}\left(x_{t}\right)=\theta_{\mathrm{old}}+\eta \cdot \nabla_{\theta} \mathcal{L}\left(x_{t}\right) \]

通过定义\(\mathcal{L}_{unlearn}(S)\)来处理集合\(S=\{x_t,l_t\}\) \[ \mathcal{L}_{\text {unlearn }}(S)=-\sum_{t} l_{t} \mathcal{L}\left(x_{t}\right) \] 那么SGD可以如下所示: \[ \theta_{\mathrm{new}} \leftarrow \theta_{\mathrm{old}}+\eta \sum_{t} l_{t} \cdot \nabla_{\theta} \mathcal{L}\left(x_{t}\right) \]

解决爆炸损失

当处理FN时,unlearning算法最大化\(\mathcal{L}(x_t)\),等价于最小化\(Pr(x_t)\),但是这个概率有可能接近于0,也就是说\(\mathcal{L}(x_t)\)可能会非常大。考虑下面的例子:\(x_1,....x_{t-1}\)标记为负样本,\(x_t\)标记为正样本,unlearning的损失函数: \[ \sum_{i=1}^{t-1} \mathcal{L}\left(x_{i}\right)-\mathcal{L}\left(x_{t}\right) \]

不考虑上式最后那个负项,最小化目标就是减小每个独立\(\mathcal{L}(x_i)\)的值。这是因为每个项都有一个下届(例如0)。假设整个求和的最小值是\(\tau\),那么每个单项的上界也一定是\(\tau\)

当考虑\(=\mathcal{L}(x_t)\),最小化上式可能就是最大化\(\mathcal{L}(x_t)\),在这种情况下我们保证模型预测概率\(Pr(x_t)\)趋近于0,同样的\(Pr(x_i)\)也趋近于0。结果就是通过上式简单预测异常。