分布漂移下的实时异常检测

理论分析与实验

理论分析和实验表明，裁剪随机梯度下降（clipped SGD）能够实现鲁棒的在线统计估计。异常检测旨在识别超出统计规范的行为，异常可能表明某种恶意活动，如网站密码破解尝试、未经授权的信用卡购买或服务器的侧信道攻击。

异常检测器通常是根据输入异常可能性进行评分的模型，并使用某个阈值将评分转换为二元决策。这些阈值通常通过对历史数据的静态分析确定。

在线统计估计的挑战

在许多实际场景中，单个数据项规模大、到达速度快且来源多样，静态分析不可行。此外，数据分布可能随时间变化——例如在假日购物活动期间，或在线服务突然变得更受欢迎时。在这些场景中，异常阈值需要自动调整。

因此，实际异常检测通常需要在线统计估计，即对稳定数据流中的分布进行持续估计。在某会议上，我们提出了一个分析框架，能够表征可同时处理以下情况的在线估计器：

异常值
分布漂移
高维数据
重尾数据
无需数据分布的先验假设

裁剪随机梯度下降方法

使用分析框架，我们证明了裁剪随机梯度下降（限制任何单个数据样本对结果统计模型的影响程度）可用于训练此类实时估计器。我们还展示了如何计算每个样本的影响上限——裁剪阈值——仅假设数据方差不是无限的。

该算法不需要任何关于数据方差的先验界限或估计；相反，它会自适应方差。梯度裁剪确保噪声和损坏的梯度不会对数据分布的估计产生不当影响。

理论框架与性能保证

我们将异常和分布漂移都建模为"遗忘"对手的工作，该对手选择干预后即离开。在学习游戏开始前，对手选择一系列概率分布和一系列损坏函数，这些函数损坏从分布中选择的随机样本。分布的变化模拟漂移，损坏的样本模拟异常。

当然，如果所有样本都损坏，或者数据流剧烈波动，就不存在异常：没有足够的统计规律性可偏离。然而，现实世界的数据很少是对抗性的，损坏数量和分布漂移幅度通常都是适度的。

我们建立了一个理论界限，表明在这种适度条件下，裁剪SGD表现良好。该算法不需要关于损坏数量或漂移幅度的先验信息或界限；其性能随着数据流复杂性（通过损坏数量和分布漂移幅度衡量）的增加而自动平滑下降。

算法收敛性证明

我们论文的核心是证明裁剪SGD在这种情况下会收敛到可靠的估计器。证明是归纳性的：首先显示给定特定输入的误差，后续输入误差的增加仅取决于该输入本身的可计算属性。基于该结果，我们显示如果给定输入的误差低于特定阈值，那么如果下一个输入未损坏，其误差也很可能低于该阈值。

接下来显示如果下一个输入损坏，则裁剪其梯度将确保误差再次很可能回落到阈值以下。我们使用两种主要方法证明这一结果：第一种是在误差函数中添加自由参数并相应计算误差阈值，以便将任何不等式转换为二次方程；第二种是使用鞅浓度证明，虽然新输入贡献的额外误差项可能暂时导致误差超过阈值，但很可能会在连续迭代中回落到阈值以下。

实验验证

除了理论分析，我们还在经典手写数字MNIST数据集上测试了方法。在我们的环境中，给定数字（我们从零开始）在不同旋转下的书写版本构成普通输入，其他数字构成异常。然而，随着时间的推移，基线输入从初始数字（例如0）切换到不同数字（例如1）以表示分布漂移。

我们的模型是逻辑回归模型，这是一个相对简单的模型，可以在每个输入后更新。实验表明，使用裁剪SGD更新模型确实能够同时适应分布漂移和识别异常。

然而，我们理论分析的结果之一是，虽然裁剪SGD很可能会收敛到一个好的估计器，但其收敛速度是次优的。在正在进行的工作中，我们正在研究如何提高收敛速度，以确保更准确的异常检测，使用更少的正常样本示例。