本文是NeurIPS 2021 论文 “Detecting Anomalous Event Sequences with Temporal Point Processes” 的笔记

本文需要用到点过程的一些基本性质，建议先去看看这篇文章：

点过程及其性质介绍（Point Processes）

Detecting Anomalous Event Sequences with Temporal Point Processes

我们会在很多地方遇到事件类型的数据，比如日志，金融，用户活动等场景。在这类数据上做异常检测是一件非常重要的事情。

异常检测的常用方法就是，out-of-distribution(OoD)检测，换句话说，就是如果出现一个在正常情况下很难发生的事件，我们就可以称为异常。

然而，如果要判断OoD，我们需要已知正常数据的分布，而这往往是未知的，且估计分布的方法也往往不太靠谱，所以我们一般倾向于使用goodness of fit(GoF)的方法，即判断一个数据，是否属于一个模型，这是相对好做的，因为模型是已知的，也就是计算goodness of fit就可以了。

为了检验点过程的goodness of fit，我们可以将点过程(Temporal Point Processes TPP)转化为标准的泊松过程：

Theorem 1 (Random time change theorem (Brown et al., 2002)). A sequence X = ( t 1 , … , t N ) X=( t_{1} ,\dotsc ,t_{N}) X=(t1​,…,tN​) is distributed according to a TPP with compensator Λ ∗ \Lambda ^{*} Λ∗ on the interval [ 0 , V ] [0,V] [0,V] if and only if the sequence Z = ( Λ ∗ ( t 1 ) , … , Λ ∗ ( t N ) ) Z=\left( \Lambda ^{*}( t_{1}) ,\dotsc ,\Lambda ^{*}( t_{N})\right) Z=(Λ∗(t1​),…,Λ∗(tN​)) is distributed according to the standard Poisson process on [ 0 , Λ ∗ ( V ) ] \left[ 0,\Lambda ^{*} (V)\right] [0,Λ∗(V)].

其中 Λ ∗ = ∫ 0 t λ ∗ ( u ) d u \Lambda ^{*} =\int ^{t}_{0} \lambda ^{*}( u) du Λ∗=∫0t​λ∗(u)du表示intensity在时间[0,t]内的累计量， λ ∗ ( t ) \lambda ^{*}( t) λ∗(t)表示在t时刻的intensity，表示受到过去事件激发的程度。

这个定理告诉我们，任意一个点过程的序列，用compensator重写一下得到的序列，这个序列就是一个标准的泊松过程。具体解释可以参考我的文章：

因此，我们可以使用这个转换后的序列，使用任何标准泊松分布的GoF检验来检验我们的点过程。那么一般标准泊松过程的检验方法有哪些呢？这里介绍两种，分别利用了泊松过程的两种不同性质。

第一种性质是在一个发生N次事件的区间 [ 0 , T ] \displaystyle [ 0,T] [0,T]内，事件发生的时间是服从在均匀分布 U ( 0 , T ) \displaystyle U( 0,T) U(0,T)的。因此，我们只需要用Kolmogorov–Smirnov (KS)-test来检验序列这样一个序列是否服从 [ 0 , T ] \displaystyle [ 0,T] [0,T]的均匀分布就可以了。

第二个性质就是，每个到达时间的区间长度是服从指数分布 E x p ( 1 ) \displaystyle Exp( 1) Exp(1)的。因此，我们只算出区间长度，然后检验这个序列是否服从指数分布就可以了。

然而这两种方法的问题在于，他们对事件发生次数是不敏感的 (即使一个非常异常的事件发生次数也有可能被认为正常)，这会导致很多case不敏感，导致无法判别异常，如下图所示：

这篇文章提出一种3S统计量(sum-of-squared-spacings (3S) statistic)，对于泊松分布序列 Z = ( v 1 , . . . , v N ) \displaystyle Z=( v_{1} ,...,v_{N}) Z=(v1​,...,vN​)满足

ψ ( Z ) = 1 V ∑ i = 1 N + 1 w i 2 = 1 V ∑ i = 1 N + 1 ( v i − v i − 1 ) 2 \psi (Z)=\frac{1}{V}\sum ^{N+1}_{i=1} w^{2}_{i} =\frac{1}{V}\sum ^{N+1}_{i=1}( v_{i} -v_{i-1})^{2} ψ(Z)=V1​i=1∑N+1​wi2​=V1​i=1∑N+1​(vi​−vi−1​)2

这里V是时间区间长度 [ 0 , V ] \displaystyle [ 0,V] [0,V]，并且假设 v i \displaystyle v_{i} vi​是已经经过排序的。从图2a中也可以看到，3S统计量对N是非常敏感的，这有助于我们发现异常的事件。那么怎么用这个3s统计量来检验我们的泊松过程呢？这里介绍他的均值和方差的性质：

Proposition 1. Suppose the sequence Z Z Z is distributed according to the standard Poisson process on the interval [ 0 , V ] [0,V] [0,V]. Then the first two moments of the statistic ψ : = ψ ( Z ) \psi :=\psi (Z) ψ:=ψ(Z) are

E [ ψ ∣ V ] = 2 V ( V + e − V − 1 )  and  Var ⁡ [ ψ ∣ V ] = 4 V 2 ( 2 V − 7 + e − V ( 2 V 2 + 4 V + 8 − e − V ) ) \mathbb{E} [\psi \mid V]=\frac{2}{V}\left( V+e^{-V} -1\right) \ \text{and} \ \operatorname{Var} [\psi \mid V]=\frac{4}{V^{2}}\left( 2V-7+e^{-V}\left( 2V^{2} +4V+8-e^{-V}\right)\right) E[ψ∣V]=V2​(V+e−V−1) and Var[ψ∣V]=V24​(2V−7+e−V(2V2+4V+8−e−V))

From Proposition 1 it follows that

lim ⁡ V → ∞ E [ ψ ∣ V ] = 2    lim ⁡ V → ∞ Var ⁡ [ ψ ∣ V ] = 0 \lim _{V\rightarrow \infty }\mathbb{E} [\psi \mid V]=2\ \ \lim _{V\rightarrow \infty }\operatorname{Var} [\psi \mid V]=0 V→∞lim​E[ψ∣V]=2  V→∞lim​Var[ψ∣V]=0

当时间趋于无穷的时候，均匀为2，方差为0，也就是等于一个常数2，所以，一个最简单的方法就是看他是不是等于2.

最后一个检测样本是否为ood，并计算p值的算法流程如下

def compute_p_value (x_test , samples , score_fn ):
	scores_id = [ score_fn (x) for x in samples ]
	score_x = score_fn ( x_test )
	num_train = len( samples )
	num_above = 0
	for s in scores_id :
	if s > score_x :
		num_above += 1
			num_below = num_train - num_above
	return min(
		( num_below + 1) / ( num_train + 1),
		( num_above + 1) / ( num_train + 1)
)

score_fn就是计算统计量的函数，比如3s统计量，samples可以是从数据集中采样的样本，也可以是由模型生成的样本，这里有很多份采样的样本。x_test则是我们要检验是否异常的样本，具体来说，就是我们通过估计统计量在该分布上的一个分布情况，然后看看测试的数据落在这个分布的那个位置。