机器算法验证 - 用于变化检测的功率鞅：M 变为零？ - 吾爱随笔录

用于变化检测的功率鞅：M 变为零？

机器算法验证鞅新奇检测

2022-04-09 12:40:31

我正在尝试应用 [ Vovk et al., 2003 ] 的幂鞅框架来更改未标记数据流中的检测，就像在 [ Ho and Wechsler, 2007 ] 中一样。基本思想涉及使用形式的幂鞅

M_{n}^{(ϵ)} := \prod_{i = 1}^{n} (ϵ p_{i}^{ϵ - 1}) = ϵ p_{n}^{ϵ - 1} M_{n - 1}^{(ϵ)} .

$M_n^{(\epsilon)} := \prod_{i=1}^n\left(\epsilon p_i^{\epsilon-1}\right) = \epsilon p_n^{\epsilon-1} M_{n-1}^{(\epsilon)}.$ 如果我正确理解该方法，它应该按如下方式工作：

$p_i$ 是一些输入序列的 p 值，它们均匀分布在 $[0,1]$ 当序列是可交换的；
当违反可交换性时， $p_i$ 变小，并且 $M_n$ 开始成长；
什么时候 $M_n$ 已经增长到某个阈值或相邻之间的差异 $M_n$ 已经超过了某个阈值，我们敲响警报，表示发生了一些变化并重新开始。

看起来很简单，但我无法让它工作：在我的数据上， $M_n$ 确实随机振荡了一段时间，但很快下降到零（到像 1e-100 这样的值）并停留在那里；数据发生实际变化时有一些很大的因素，但是从1e-100返回需要很多因素......

我尝试了一个简单的测试：生成均匀分布 $p_i$ 并计算 $M_n$ 为他们。这是我测试的完整python代码（ $\epsilon=0.92$ 是论文中的建议值，但我尝试过其他的 $\epsilon$ 结果相似）：

epsilon = 0.92
pv_test = [random.random() for _ in xrange(5000)]
test_mult = [epsilon * (x ** (epsilon - 1)) for x in pv_test]
Mtest = [1]
for i in xrange(len(test_mult)):
    Mtest.append(Mtest[i] * test_mult[i])

我观察到了同样的行为： $M_n$ 总是降为零！有时更快，有时更慢，但总是如此。以下是一些示例图 $M_n$ ：在此处输入图像描述

它看起来确实像随机游走，但即使对于完全一致的 p 值，它也总是最终下降到零。这显然不适用于变更检测，因为即使是相对较长的小 p 值序列也无法恢复 $M_n$ 从1e-100。

所以我的问题是：我做错了什么？

3个回答

你的实现是正确的。当 p 值均匀分布时，幂鞅趋于变得非常小（接近 0）。为避免这种情况，您只需在马丁格尔小于 1 时立即从 1 重新启动。所以只需添加：

Mtest[i] = max(Mtest[i], 1)

当 p 值均匀分布时，即使在很长一段时间内，这也会使您的鞅小（但不小于 1）。

我认为如果你计算出你需要多少“奇怪”的数据点，你可以看到问题的本质，因为你已经观察到了长期的“非奇怪”数据点（这里使用 Ho 和 Wechsler 的语言） .

让我们做一些粗略的计算：对于一个 $k$ 具有常数的数据点 $p_i = p$ 然后 $M_k \sim 10^{k(\text{log}_{10}(\epsilon) + (\epsilon-1) \text{log}_{10}(p))}$ . 假设在一个数字之后 $n$ 非奇怪的数据点 $p_i = .5$ （均匀 RV 的期望值超过 $[0,1]$ )，我们得到一个流 $\eta$ 奇怪的事件 $p_i \sim 10^{-3}$ . 然后我们问“有多大 $\eta$ 必须在之前 $M_{n+\eta} \sim 10$ ?”（Ho 和 Wechsler 给出的阈值）。

如果我们使用 $\epsilon = .92$ 然后在不奇怪的数据流之后（ $n$ 点与 $p_i=.5$ ) 我们有 $M_n \sim 10^{-.012n}$ . 稍微滥用符号让我们将令人惊讶的数据流的“贡献”表示为 $M_{\eta}$ （所以 $M_{n+\eta} = M_n M_{\eta}$ )，然后我们可以计算出 $M_{\eta} = 10^{.204 \eta}$ . 给定阈值 $10$ 我们想要 $M_{n+\eta} = 10^{.204\eta - .012n} = 10$ 或者 $.204\eta - .012n = 1$ ，因此 $\eta = \frac{1+.012n}{.204} \approx 5 + .06 n$ . 这意味着 $\eta$ 需要大约 6% $n$ 如果我们要通过 10 的门槛。

显然这只是一个粗略的计算，但我认为它对问题提出了一个清晰的直觉：这种鞅方法对于短期运行的令人惊讶的数据是稳健的。您拥有的数据越多，在得出发生变化的结论之前，您需要的数据就越多。因为你给它提供了 5000 个不奇怪的观察结果，所以你需要大约 300 个非常奇怪的观察结果来说服它发生了变化。请注意，在 Ho 和 Wechsler 中，他们似乎每 1000 个数据点输入一个令人惊讶的数据，这意味着他们只需要大约 60 个令人惊讶的数据点。

在我看来，您不了解更改概念。尝试这样做：

您必须实现一个数据集，其中至少包含 2 个具有 n 维向量的集群（因为测试是更好的 2 维）。
您的代码必须一对一地读取集群 #1 中的所有日期。当您的代码开始从集群 #2 读取日期时，您的 martigale 必须检测到更改。

关于算法。您需要实施（所有参考资料都在 Ho & Wechler 论文上）：

奇异性测量。我会尝试实现集群模型（公式 7）。计算直到那一刻（集群质心）之前读取的所有日期。接下来，您需要计算从质心到该时刻读取的每个点的欧几里得距离。
P 值函数（公式 7）。奇异性度量是该公式的输入。
在 Martingale 中引入每个 p 值。
您必须定义 Lambda 值才能触发更改警报。

其它你可能感兴趣的问题

上一篇使用 PCA 然后使用自动编码器进行预处理有用吗？下一篇在 R 中使用平方根链接模拟 GLM