应用HTM算法实时异常检测流分析

一、摘要

  世界上的许多数据都是流式的时间序列数据，在这些数据中，异常数据在关键情况下提供了很多重要的信息。然而，检测流式数据中的异常是一项艰巨的任务，需要探测器实时处理数据，并在进行预测的同时能够学习。本文介绍一种新的基于在线序列记忆算法的异常检测技术——分层时间记忆(HTM)。

二、概述

  我们将异常定义为系统行为异常且与过去行为明显不同的时间点。 根据这个定义，异常并不一定意味着问题。 改变可能是由于负面原因，例如发动机上的温度传感器上升，表明可能即将发生故障。 或者更改可能是出于积极的原因，例如新产品页面上的网页点击异常高，显示需求强劲。 无论哪种方式，数据都是不寻常的，可能需要采取行动。 异常可以是空间的，意味着该值超出了典型范围，如下图1中的第一个和第三个异常（红色的点）。它们也可以是时间的，其值不在典型范围之外，但它发生的顺序是不寻常的。 下图1中的中间异常是时间异常。

图1.该图显示了来自大型工业机器内部组件的实际温度传感器数据。 异常用红色圆圈标记。 第一个异常是计划停工。 第三个异常是灾难性的系统故障。 第二个异常，一个微妙但可观察到的行为变化，表明问题的实际发生导致最终的系统故障。

  流应用中的异常检测特别具有挑战性。 检测器必须处理数据并实时输出决策，而不是通过批量文件进行多次传递。在大多数情况下，传感器流的数量很大，人类很少有机会，更不用说专家干预了。 因此，以无人监督的自动方式（例如，无需手动参数调整）操作通常是必要的。 底层系统通常是非平稳的，探测器必须不断学习和适应不断变化的统计数据，同时进行预测。本文的目的是介绍一种专为此类实时应用而设计的新型异常检测技术。 我们将展示如何使用Hierarchical Temporal Memory （HTM）网络以有原则的方式在各种条件下稳健地检测异常。
  由此产生的系统是高效的，非常容忍噪声数据，不断适应数据统计的变化，并检测非常微妙的异常，同时最大限度地减少误报。 我们展示了实时金融异常检测应用程序的定性示例。 我们还报告了实时异常检测的开放基准测试的领先结果。 该算法已经商业化部署。
   HTM是一种源自神经科学的机器学习算法，它模拟流数据中的空间和时间模式请见本人博客中另外论文《应用层级时空记忆模型（HTM）实现对实时异常流时序数据检测》。 HTM与序列预测中的一些现有算法相比是有利的，特别是复杂的非马尔可夫序列。 HTM不断学习系统，自动适应不断变化的统计数据，这是一种与流分析特别相关的属性。

三、使用HTM实现异常检测

  典型的流应用涉及分析实时发生的连续数据流。 此类应用包含一些独特的挑战。 我们将此形式化如下。 设矢量xt$x_t$时刻t$t$的实时系统的状态。 该模型接收连续的输入流：

  在每个时间点t$t$，我们希望确定系统的行为是否异常。 关键挑战之一是必须实时地进行确定，即在时间t+1$t+1$之前并且没有任何前瞻。 在实际应用中，系统的统计数据可以动态变化。 例如，在生产数据中心，可能会随时安装软件升级，从而改变系统的行为（下图2）。 模型的任何重新训练必须在时间t+1$t+1$之前在线完成。最后，各个测量不是独立的，并且包含可以被利用的重要时间模式。

图2. Amazon EC2实例的CPU利用率（百分比）。 对计算机上运行的软件进行更改会导致CPU使用率发生变化。 持续学习对于像这样对流数据执行异常检测至关重要（季节性或周期性的数据变化的学习能力非常重要）。
  HTM是一种似乎与上述约束相匹配的学习算法。 HTM网络不断学习和模拟其输入的时空特征。 HTM已被证明可以很好地用于预测任务，但HTM网络不直接输出异常分数。为了执行异常检测，我们利用HTM中可用的两种不同的内部表示。给定输入xt$x_t$，向量a(xt)$a(x_t)$是表示当前输入的稀疏二进制代码。我们还利用内部状态向量π(xt)$\pi (x_t)$表示对a(xt+1)$a(x_{t+1})$的预测，即对下一个输入x(xt+1)$x(x_{t+1})$的预测。预测向量包含关于当前序列的推断信息。特别地，给定输入将导致不同的预测，这取决于当前检测到的序列和序列内输入的当前推断位置。预测的质量取决于HTM对当前数据流建模的程度。有关这些表示的更详细说明，请参阅（Hawkins＆Ahmad，2016）。xt$x_t$和a(xt)$a(x_t)$在每次迭代时重新计算，但不直接表示异常。 为了创建一个强大的异常检测系统，我们引入了两个额外的步骤。 我们首先从两个稀疏向量计算原始异常分数（raw anomaly score）。 然后，我们计算一个异常似然值（anomaly likelihood），该阈值被阈值化以确定系统是否是异常的。 图3显示了我们的算法的框图。 这两个步骤详述如下。 然后，我们将描述如何稳健地处理由多个不同模型组成的更大系统。

三、（一）计算原始异常分数（raw anomaly score St$S_t$）

  我们计算一个原始异常分数，用于衡量模型预测输入与实际输入之间的偏差。 它是根据预测稀疏矢量和实际稀疏矢量之间的交集来计算的。 在时间t$t$，原始异常分数St$S_t$给出为：

如果当前输入被完美预测，则原始异常分数将为0；如果完全不可预测，则原始异常分数将为1，或者取决于输入和预测之间的相似性，原始异常分数将介于两者之间。该评分的一个有趣方面是正确处理分支序列。 在HTM中，多个预测以表示为每个单独预测的二元并集。 与Bloom过滤器类似，只要向量足够稀疏且具有足够的维度，就可以同时表示中等数量的预测，并且指数上的误差几率很小。 异常分数在以下意义上优雅地处理分支序列。 如果两个完全不同的输入都是可能的和预测的，接收任一输入将导致0异常分数。 任何其他输入将产生正异常分数。由于HTM的持续学习性质，也可以优雅地处理对底层系统的更改。 如果系统的行为发生变化，则异常分数在移位点处会很高，但在模型适应“新常态”时会自动降级为零。 除了基础度量值的空间移位之外，还处理系统的时间特性的变化。

三、（二）计算异常似然值（anomaly likelihood Lt$L_t$）

  上述原始异常分数表示当前输入流的可预测性的瞬时度量。 这适用于可预测的场景，但在许多实际应用中，底层系统本质上是噪声和不可预测的。 在这些情况下，通常可预测性的变化表明了无意义的行为。 例如，请考虑下图4.此数据显示负载均衡器在生产网站上提供HTTP请求时的延迟。 尽管延迟通常较低，但偶尔出现随机跳跃并且异常得分相应的峰值并不罕见。 直接对原始异常分数进行阈值处理会导致许多误报。 然而，如图的后半部分所示，高延迟请求频率的持续增加是不寻常的，因此报告为异常。

图4.非常嘈杂，不可预测的流。 数据显示生产网站上负载均衡器的延迟（以秒为单位）。 红点表示延迟异常增加的大致位置。
  为了处理这类场景，我们引入了第二步。 我们不是直接对原始分数进行阈值处理，而是对异常分数的分布进行建模，并使用此分布来检查当前状态是否异常的可能性。 因此，异常可能性是定义当前状态如何基于HTM模型的预测历史异常的度量。 为了计算异常可能性，我们维持最后W原始异常分数的窗口。 我们将分布建模为滚动正态分布，其中样本均值和方差从先前的异常分数不断更新，如下所示：

然后我们计算最近的异常分数的短期平均值，并对高斯尾概率（Q函数）应用阈值来决定是否声明异常。 我们将异常可能性定义为尾部概率的补充：
这里W′$W^{\prime }$是一个短期均线的窗口，其中W′<<W$W^{\prime }<<W$。我们阈值Lt$L_t$并报告异常，如果它非常接近1：

三、（三）结合多个独立模型实现大型系统

  许多工业或复杂环境包含大量传感数据流。理论上，给定足够的资源，可以创建一个大的复杂模型，整个矢量流作为输入。在实践中，通常将大型系统分解为许多较小的模型。训练较小的模型更容易，因为训练和推理的复杂性比输入维度的大小线性增长快得多。因此，将解决方案组合成一组较小的模型可以提高准确性并且更快地实现性能。然而，即使进行这样的分解，重要的是计算累积单个模型的结果的全局度量并且指示系统的那些部分是否处于异常状态。例如，考虑运行生产网站的数据中心。自动警报系统可能需要不断决定是否生成警报并可能唤醒随叫随到的工程师。
  我们假设代表系统的输入被分解为M$M$个不同的模型。 设xmt$x_t^m$是第m$m$个模型在时间t$t$的输入，而Smt$S_t^m$是与每个模型相关的原始异常分数。 我们希望计算一个全局度量，指示系统中异常的总体可能性（参见下图5）。

图5.说明具有多个独立模型的复杂系统的功能图。
  一种可能的方法是估计联合分布P(S0t,...,Sm−1t)$P(S_t^0,...,S_t^{m-1})$并对尾部概率应用阈值。对联合分布进行建模可能具有挑战性，特别是在流式上下文中。 如果我们进一步假设模型是独立的，我们可以简化并估算：

鉴于此，我们的异常可能性可以计算为：
  上述方法存在一个缺陷。 在实时动态场景中，系统某个部分的关键问题通常可以级联到其他区域。 因此，通常存在内置的随机时间延迟，这反过来导致各种模型中的异常分数之间的不同时间延迟。 例如，在不同模型中多个异常事件彼此接近发生的情况比单个模型中的单个事件更不可能和不寻常。 正是这些情况对于在复杂系统中检测和捕获是有价值的。
  理想情况下，我们能够估计出可追溯到时间的异常分数的联合分布，即P(S0t−j,S1t−j,...,SM−2t,SM−1t)$P(S_{t-j}^0,S_{t-j}^1,...,S_t^{M-2},S_t^{M-1})$。 理论上，这将捕获所有依赖关系，但这比公式(8)的联合概率更难估计。 或者，在系统拓扑相对清晰且受自己控制的情况下，可以创建依赖关系的显式图，监视节点对之间的预期行为，并检测与这些期望相关的异常。实践中已经证明这种技术非常精确确定监测服务之间特定呼叫的网站中的异常。 然而，在大多数应用中，这种技术也是不切实际的。 对各种依赖关系进行建模可能很困难，并且通常可以设置任意系统来创建该图。
  现在希望系统能够快速计算，做出相对较少的假设，并且具有自适应性。 提出了一种简单的通用机制，通过修改公式（9）来处理多个模型。 合并一个平滑的时间窗口。 窗口机制允许系统结合尖峰，其可能性在时间上接近但不完全重合。 设G是高斯卷积核：
我们将此卷积应用于每个单独的模型以获得最终的异常可能性得分:
  和前面的方法一样，如果组合异常可能性大于阈值Lt$L_t$，我们会检测到异常Lt≥1−ϵ$L_t\ge 1-ϵ$。公式（11）表示用于检测复杂实时流应用中的异常实用的方法。 和以前一样，是间接测量，在每个模型的原始异常分数之上计算。 它反映了模型在特定时间点的潜在可预测性，并不直接模拟传感器测量本身。

四、实际考虑的问题

  单个模型场景中有三个参数：W$W$，W′$W^{\prime }$和ϵ$ϵ$。 W$W$是计算异常分数分布的持续时间。 系统性能对W$W$不敏感，只要它足够大以计算可靠的分布。 W′$W^{\prime }$数字控制异常分数的短期平均值。 在下面的所有实验中，我们使用W=8000$W=8000$和W′=10$W^{\prime }=10$的宽大值。参数ϵ$ϵ$也许是最重要的参数。 它控制异常报告的频率，以及误报和漏报之间的平衡。 在实践中我们发现了ϵ=10−5$ϵ={10}^{-5}$适用于各种领域。 直观地说，这应该代表每10,000条记录一次的误报。
  多重模型场景引入了一个附加参数，即窗口宽度σ$\sigma$。 这在某种程度上取决于域，但由于软高斯卷积，系统对此设置不是非常敏感。 在所有实验中σ=6$\sigma =6$。
  每个模型在当前高端笔记本电脑上每个输入向量需要不到10毫秒。 并行运行多个模型的基于服务器的部署可以在高端服务器上运行大约5,000个模型。