摘要：本文考虑的是在有限数量的M个过程中检测单个异常过程的问题，每次我们可以观测到一系列的过程，并且每次被选择的观测过程都依据这个过程是否正常而分别遵循两个不同的分布。我们的目标是在一定的误差允许范围内制定出一个序列搜索策略，能够最小化搜索时间。这个问题可以被看成一个特殊的主动假设检验过程。本文展示了一种简单的确定性的测试过程，并且达到了渐进最优，同事在有限时间内有更好的结果。作者还扩展了这个问题到有多个异常过程同时发生的情况，作者还检查了一种实际情况，即异常过程数目的上界已知时该算法的表现。

关键词：序列检测, 异常检测, 动态搜索, 主动假设检验.

1.Introduction

  本文考虑的是在有限数量的$M$个过程中检测单个异常过程的问题，从目标搜索问题中借用术语，我们把这些过程看成cells，并且把异常过程看成在这$M$个cells中要搜索的一个目标。决策者允许在同一时间从$K$且$(1 \le K \le M)$个目标中搜索cells。搜索一个cell所得到的观测是从两个不同的分布$f$和$g$中得到的独立同分布实现。选择哪个分布取决于目标是否在这个cell中。本文的最终目的是找到一个序列性的搜索策略，能在每个时刻决定搜索哪些cells。并且在保证错误概率被限制在一定范围内时所需要的搜索时间最小化。

  该问题可以应用于网络的入侵检测，即一个子网络被入侵，然后需要定位子网中的不正常组件的情况。（因为每个组件被感染的可能性比较小，只有一个不正常的组件会有较大概率），此外它也可以以用于目标搜索，欺诈检测，认知无线网络的光谱扫描等等。

1.1 A Case of Active Hypothesis Testing

  以上的问题是Chernoff于1959年提出的序列实验设计问题的一个个例，和传统的在每个假设下的观测模型是已经预先知道的序列假设检验模型相比，Chernoff的模型允许决定着选择在每个时间需要执行的动作，这在一定程度上能控制实验的走向，每个假设的分布不同，不同的实验也会生成不同的观察结果。直观的来看，随着观测数量增多，决策和对于正确假设的确信度也越高，这也会反过来导致更好的选择结果。Chernoff关注的是二项分布假设问题，并且提出了一个随机决策模型，我们把它称为Chernoff test，随着最大错误概率减少是渐进最优的。特别的，Chernoff test依据以前的行为和观测选择当前的实验。

  不难看出本文研究的异常检测问题是主动假设检验问题的一个特殊模型，在每个假设中目标位于一个特定的cell里,下一个观测的分布是$f$还是$g$取决于选择探测的cells，在这篇文章在Chernoff test模型上进行改进，使用的是一种deterministic test模型，也能达到渐进最优并且在有限时间内有更好的结果。

1.2 Main Results

  本文关注的是在错误概率接近0的时候最小化监测时间并且达到渐进最优的问题，Chernoff test中的渐进最优要求在任何实验条件下，任意两个假设之间是有区分度的，即他们的Kullback-Liebler divergence大于0，然而在本文的异常检测问题中，这样的假设并不成立，例如在检测第i个cell的时候，目标在j cells $(j \neq i)$和k cells$(k \neq i)$的情况都满足概率分布$f$.然而，我们在Theorem A中证明了哪怕Chernoff test不满足Kullback-Liebler divergence条件也依旧满足渐进最优性，在结果中它提供了一个比较基准。

  当把Chernoff test直接用于异常检测问题重视，会生成一个随机化的cell选择规律，即当前时间需要搜索的cell根据之前的观测和行为被随机的给出，这篇文章的主要贡献是给出了一个简单的决定性策略模型，并且能给出同样的渐进最优结果，并且在有限时间内效果更好，降低了复杂度。特别的，在被提出的策略中，选择规则$\phi(n)$指示了在时间$n$需要搜索的$K$个cells。他的表示如下：

\begin{equation}
\phi =
\left({m}^{1} \left(n \right),{m}^{2} \left(n \right),...,{m}^{K} \left(n \right) \right),
\text{ if } D(g||f) \geq \frac{D(f||g)}{(M-1)} \text{ or } K=M \
\left({m}^{2} \left(n \right),{m}^{3} \left(n \right),...,{m}^{K+1} \left(n \right) \right),
\text{ if } D(g||f) < \frac{D(f||g)}{(M-1)} \text{ and } K<M
\end{equation}

  其中${m}^{i} \left(n \right)$代表到时间$n$为止这个cell的指数似然率LLR的总和第$i$大的的那个cell的编号。而$D(\cdot ||\cdot )$是两个分布的KL散度。因为$D(g ||f )$是cell选择规则的关键性质，我们把这个决定策略称作DGF策略。

  这个策略直观来说是满足条件的，考虑一个例子，当$K=1$时，在这个情况下，DGF策略根据$D(g||f)$和$D(f||g)/(M-1)$的大小关系选择$(LLR)$的总和最大或者次优的cell。在这个策略之后我们可以直观的看出根据$D(g||f)$和$D(f||g)/(M-1)$可以推测那个有target的cell的比率和那$M-1$个没有target的cell的比率，依靠这两个比率的大小顺序，DFG策略可以找出那个有target的cells或者那$M-1$个没有target的cells。选择规则非常清晰，因为搜索LLR总和第二大的cell能充分地体现对$M-1$个没有目标的区域的搜索情况，因为这个区域被搜索的越少，那么在这$M-1$个cells中他的LLRs总和会越高，第三部分会有更清楚的证明和讨论。

  我们之后讲这个问题扩展到多异常检测的情况，特别的，我们检查了异常过程总量的上界已知的情况，我们发现Chernoff test在这种情况下的效果并不好，所以我们思考了一种修正的贝叶斯风险模型能够更好地在这样的实际系统中达到目标，并且我们证明了这种天情况下决策算法的渐进最优性质。

1.3 Related Work

  略过

1.4 Organization

  在第二部分我们讨论和系统模型和问题的建模，第三部分我们提出了决定性的DGF策略并且建立了它的渐进最优性，我们也比较了DGF策略与Chernoff test。第四部分我们讲这个问题扩展到了多个异常过程同事存在的情况，并且思考了在异常过程已知和为止两种情况下的例子，第五部分我们给出了一些数值例子来描述我们提出的策略与Chernoff test的表现情况，第六部分对全文进行了总结。

2. SYSTEM MODEL AND PROBLEM FORMULATION

2.1 System Model

  考虑以下的异常检测问题，一个决策者需要检测M个cells中的一个异常物体（可以看成一个目标），如果这个目标在cell $m$中，我们就说假设$H_m$为真，$H_m$为真的先验概率用$\pi_m$,其中$\sum_{m=1}^{M}{\pi_m}=1$.假设条件对于所有$m$是$0<\pi_m<1$.

  每次只有$K(1\leq K \leq M)$个cells能被观测到，在时间n中cell m被观测到，得到了一个独立的单次观测$y_m(n)$.如果假设m为假，$y_m(n)$遵循分布$f(y)$，如果假设m为真，$y_m(n)$遵循分布$g(y)$，让$\textbf{P}_m$为假设$H_m$的概率度量，而$E_m$为$P_m$对应的期望（Em的解释存疑）。

  我们定义停止规则$\tau$为声明目标的位置并结束搜索的时间，让$\delta \in { 1,2,...,M }$作为一个决策规则，如果$H_m$为真那么$\delta=m$,让$\phi(n) \in {{ 1,2,...,M }}^K$表明在时间$n$时选择$K$个cells的选择规则，选择规则的时间序列向量为$\phi=(\phi(n),n=1,2,...)$,让$y_{\phi(n)}(n)$为在时间n在$\phi(n)$选择规则下的观测向量，而让$y(n)={{\phi(n),y_{\phi(t)}(t)}}^{n}_{t=1}$编程到时间n位置所有的cell的选择和观测，在决定性选择规则中，n时刻的$\phi(n)$是$y(n-1)$到${{ 1,2,...,M }}^K$的一个映射，在随机选择规则中，n时刻的$\phi(n)$是$y(n-1)$到${{ 1,2,...,M }}^K$的概率密度函数的映射。（最后这里的解释存疑）。

  定义1：一个可行的用于序列异常检测问题的策略$\Gamma$可以用元组$\Gamma=(\tau ,\delta ,\phi)$表示。

2.2 Objective

  策略$\tau$的错误概率为$P_e(\Gamma)=\sum_{m=1}^{M}{\pi_m}{\alpha_m}(\Gamma)$，其中${\alpha_m}(\Gamma)=\textbf{P}_m(\delta \neq m|\Gamma)$是当${H_m}$为真时申明$\delta \neq m$的概率。让${\textbf{E}}(\tau | \Gamma )=\sum_m=1^M\pi_m\textbf{E}_m(\tau|\Gamma)$为策略$\Gamma$下的平均检测延时。

  我们采用一种贝叶斯估计的方法，使用$c$作为每次观测的损失，并且以$1$作为误判的损失，所以当$Hm$为真时的策略$\Gamma$下的贝叶斯风险为：

\begin{equation}
\textbf{R}_m(\Gamma) \triangleq \alpha_m(\Gamma)+c \textbf{E}_m(\tau|\Gamma)
\end{equation}

  其中$c$代表采样相对于误判的相对损失。

  平均贝叶斯风险由以下公式给出：

\begin{equation}
\textbf{R}(\Gamma) = \sum^M_{m=1}\pi_m\textbf{R}_m(\Gamma)=\textbf{P}_m(\Gamma)+c \textbf{E} (\tau|\Gamma)
\end{equation}

  我们的目标是找到一个策略$\tau$来最小化贝叶斯损失${\textbf{R}}(\tau)$:

\begin{equation}
\inf_\Gamma {\textbf{R}}(\Gamma)
\end{equation}

2.3 Notations

  让$\textbf{1}_m (n)$为时刻n时cell $m$是否被观察的指数函数，当$\textbf{1}_m (n)=1$是被观察，否则没被观察。让：

\begin{equation}
{l}_{m}(n) \triangleq \log\frac{g(y_m(n))}{f(y_m(n))}
\end{equation}

  和

\begin{equation}
S_m(n) \triangleq \sum_{t=1}^{n}l_m(t)\textbf{1}_{m}(t)
\end{equation}

  分别作为指数指数率LLR,和各个cell m在时间 n时观测的指数似然率的总和。

  我们之后再定义${m}^{i} \left(n \right)$为在时间n观测到的总LLRs第i大的cell的下标，让：

\begin{equation}
\Delta S(n) \triangleq S_{m^{(1)}(n)}(n)-S_{m^{(2)}(n)}(n)
\end{equation}

  代表在时间n时最大总LLRs和次优LLRs之差。

  最后我们定义：

\begin{equation}
I^*(M,K) \triangleq
D(g||f)+D(f||g),\text{ if } K=M \
\max\left[\frac{K D(f||g)}{M-1},D(g||f)+\frac{(K-1)D(f||g)}{M-1}\right],\text{ if } K<M
\end{equation}

  在后面的章节中我们会说明$I^* (M,K)$扮演速率函数的作用，他决定了模型在渐进最优情况下的表现，增加$I^* (M,K)$会减少贝叶斯风险的渐进最低边界，很明显随着观测能力$K$的增加和假设综数$M$的减小，$I^* (M,K)$会随之增加。

3. THE DETERMINISTIC DGF POLICY

  在这一部分我们提出了一个决定性策略模型，被称为DGF策略模型用以解决公式3的问题，理论1说明随着$c \rightarrow 0$DGF策略是渐进最优的.

3.1 The DGF Policy

  在每个时间n，DGF策略按照他的总LLRs选择要检测的$\phi(n)$，特殊的，依靠$D(g||f)$和$D(f||g)/(M-1)$的相对大小，选择前K个总LLRs最大的cells或选择第二个到第K+1个大小的总LLRs被选择：

\begin{equation}
\phi =
\left({m}^{1} \left(n \right),{m}^{2} \left(n \right),...,{m}^{K} \left(n \right) \right),
\text{ if } D(g||f) \geq \frac{D(f||g)}{(M-1)} \text{ or } K=M \
\left({m}^{2} \left(n \right),{m}^{3} \left(n \right),...,{m}^{K+1} \left(n \right) \right),
\text{ if } D(g||f) < \frac{D(f||g)}{(M-1)} \text{ and } K<M
\end{equation}

  DGF策略下的停止规则和决定规则根据以下两个公式给出：

\begin{equation}
\tau = \inf { n: \Delta S(n)\geq - \log c }
\end{equation}

  和

\begin{equation}
\delta = {m}^{1}(\tau)
\end{equation}

  DFG策略的决定性选择规则可以按照以下的方式直观的解释，考虑$K=1$的情况，如果在每次给的时间n都选择${m}^{1}(n)$,渐进检测时间接近$-\log c/D(g||f)$,因为这个有目标的cell（假设第m个）每次都以最大的概率被观察到，并且这个测试在收集到关于这个cell的足够的信息时会终止，在这种情况下，因为$E_m(l_m)=D(g||f)$,所以$D(g||f)$可以决定它的渐进最优性质（详细可以参考附录A）。另一种情况下，如果在每次给的时间n都选择${m}^{2}(n)$,渐进检测时间接近$-(M-1)\log c/D(f||g)$,因为那$M-1$个没有目标的cell每次都大的概率被观察到，这个测试在收集到关于这些cell的足够的信息时会终止，并且因为$E_m(l_j)=-D(f||g)$对于所有的$j \neq m$成立,所以$D(f||g)/(M-1)$可以决定它的渐进最优性。因此，这个选择规则根据$\max \left[D(g||f),D(f||g)/(M-1)\right]$选择策略来最小化渐进最优的检测时间，当$K>1$时，cell m状态和M-1个cells状态下的速率能够通过$\frac{K D(f||g)}{M-1}$和$D(g||f)+\frac{(K-1)D(f||g)}{M-1}$较好的区分，因为$D(g||f)>D(f||g)/(M-1)$等同于$D(g||f)+\frac{(K-1)D(f||g)}{M-1}>\frac{K D(f||g)}{M-1}$，所以DGF选择规则的原理就很清楚了。

3.2 Performance Analysis

  下列理论说明DGF策略在c趋近于0时的是渐进最优的：

  Theorem 1:

  让$R^*$和$R(\Gamma)$分别是在DGF策略下和任意其他的策略$\Gamma$下的贝叶斯风险，那么：

\begin{equation}
R^* \sim \frac{-c \log c}{I^*(M,K)} \sim \inf_\Gamma R(\Gamma) \text{ as } c\rightarrow 0
\end{equation}

  其中符号 $f \sim g \ as \ c \rightarrow 0$指$\lim_{c\rightarrow 0}f/g = 1$

  具体证明部分先不写，以后补上。

3.3 Comparison With the Chernoff Test

  这一节我们分析传统的Chernoff test在异常检测问题中的运用，并且将它与DGF policy进行比较。

  The Chenoff Test：Chenoff Test有一个随机的选择规则，特别的，让$q=(q_1,...,q_N)$为一系列N个可选实验$u={u_i}^{N}_{i=1}$的概率质量函数，其中$q_i$是选择实验$u_i$的概率，对于一个通常的M进制主动假设检验问题，时间$n$的Chernoff test服从一个依赖于过去行为和观察的分布$q^*(n)=(q^*_1(n),...,q^*_N(n),)$:

\begin{equation}
q^*(n)=\arg \max_q \min_{j \in \mathcal{M} \setminus { \hat{i}(n) }} \sum_{u_i}q_i D(p^{u_i}_{\hat{i}(n)}||p^{u_i}_{j})
\end{equation}

  其中$\mathcal{M}$是$M$个假设的集合，$\hat{i}(n)$在艺考过去的行为和观测对时间n时正确假设的最大似然估计，而$p^{u_i}_{j}$是在假设$j$下当$u_i$被执行师观测的概率分布，停止规则与决定规则在式(9),(10) 中被提出。

  当应用在异常检测问题是，Chernoff Test的工作过程如下，当$D(g||f) \geq D(f||g)/(M-1)$时，Chernoff Test选择了cell ${m}^{1}(n)$并且从剩下的$M-1$个cells中随机的选择$K-1$个cells,当$D(g||f) < D(f||g)/(M-1)$时,所有的K个cells从${m^{(2)}(n),m^{(3)}(n),...,m^{(M)}(n)}$等概率随机选择。

  下列理论说明chernoff策略在c趋近于0时的是渐进最优的：

  Theorem 2:

  让$R_{CT}$和$R(\Gamma)$分别是在chernoff策略下和任意其他的策略$\Gamma$下的贝叶斯风险，那么：

\begin{equation}
R_{CT} \sim \frac{-c \log c}{I^*(M,K)} \sim \inf_\Gamma R(\Gamma) \text{ as } c\rightarrow 0.
\end{equation}

  其中符号 $f \sim g \ as \ c \rightarrow 0$指$\lim_{c\rightarrow 0}f/g = 1$

  具体证明在附录B，以后补上。

  Comparison：尽管两个策略都是渐进最优的，但是在有限时间内的表现却不同，接下来我们将通过对异常检测问题和分批调度问题进行比较来直观的解释为什么DGF策略有更好的性能。

  考虑这样一个问题，给K台平行的机器安排M个工作。（$K \leq M$）,每个工作都需要一个$T_p$单位时长的决策过程时间，目标是最小化完成M项工作的调度时间，当$K>1$时，持续操作一项工作直到它完成为止可能是一个次优的方案，应为存在一定数量的机器是限制的，同事还有小于K的工作未完成。这里注意，在$K>1$时，在调度过程中如果存在机器闲置，则相当于增加了调度时间，这个问题的最优解决方案是通过LRPT（处理时间最长的进程优先的规则）来进行调度，即在任何时间n，执行的都是处理时间最长的K项工作。

  异常检测问题可以看成是在使用K台机器（决策者同时能够探查的数量）调度M-1项工作（每一项工作都是区别将这M-1个错误假设中的任意一个与真实假设区分开来），首先考虑当$D(g||f) < D(f||g)/(M-1)$时,DGF同时探查了${m^{(2)}(n),m^{(3)}(n),...,m^{(K+1)}(n)}$，而chernoff模型随机的从${m^{(2)}(n),m^{(3)}(n),...,m^{(M)}(n)}$等概率随机选择，两个测试都在$\Delta S(n)\geq - \log c$满足条件时停止，假设$H_m$为真，直白的来说，一旦$\Delta S(m,j) \triangleq S_{m}(n)-S_{j}(n)> - \log c$,决策者就有了足够的证据区分错误假设$H_j$与正确假设$H_m$，除了在无关紧要的渐进估计的原始阶段，cells ${m^{(2)}(n),m^{(3)}(n),...,m^{(M)}(n)}$都是没有目标的cells，在这个过程中DGF的策略可以看做是选择了有较长共时的工作优先处理，而chenoff模型可能会造成探查容量的浪费，并且有可能重复探查已经满足确信条件的区域，这可以看做是调度一个已经完成的工作，这样的情况在DGF中不会发生。

  所以在$D(g||f) > D(f||g)/(M-1)$的异常监测模型可以看做是在K-1台机器上完成M-1项工作的问题，要注意DGF模型和Chernoff模型都只拍了一个机器完成$m^{(1)}(n)$,因为在$D(g||f) > D(f||g)/(M-1)$情况下派机器探索那个有目标的cell可以加速整个检测过程。

4. NUMERICAL EXAMPLES

  在这个部分我们列出了一些数值的例子来描述DGF模型和Chernoff模型的表现，我们仿真了一个在M个cells中有单异常的情况，他的一些参数如下：

  m个cell的先验概率：$\pi_m=1/M$ 对于所有的 $1 \leq m \leq M$，当在时间n观察cell m时，观测$y_m(n)$是从分布$f\sim \exp(\lambda_f)$或$g\sim \exp(\lambda_g)$中独立的得到的（取决于该区域是否有目标），已经证实了：

$D(g||f)=\log(\lambda_g)-\log(\lambda_f)+\frac{\lambda_f}{\lambda_g}-1$

$D(f||g)=\log(\lambda_f)-\log(\lambda_g)+\frac{\lambda_g}{\lambda_f}-1$

  让 $R_{DGF},R_{CH}$为DGF模型和Chernoff模型各自对应的贝叶斯风险因子。让$R_{LB}=\frac{-c \log c}{I^*(M,K)}$为$c \rightarrow 0$的风险因子的渐进最低边界。我们定义：

$L_{DGF} \triangleq \frac{R_{DGF}-R_{LB}}{R_{LB}}$

$L_{Ch} \triangleq \frac{R_{Ch}-R_{LB}}{R_{LB}}$

  为两个模型的贝叶斯风险相对损失（相对于渐进下界），因为两个模型都满足渐进最优，我们知道随着$c \rightarrow 0$时$L_{DGF}$和$L_{Ch}$都趋近于0，但两者在有限时间下有不同的表现。

  首先我们考虑M=5和K=1的情况，当$K=1$和$D(g||f) \geq D(f||g)/(M-1)$时，DFG模型与Chernoff模型一直，他们都选择了cell $m^{(1)}(n)$.当$D(g||f) < D(f||g)/(M-1)$时，每个时刻n中DFG模型选择$m^{(2)}(n)$，然而Chernoff模型从$j \neq m^{(1)}(n)$的cell里随机选了一个。我们一开始设置$\lambda_f=0.5$且$\lambda_g=10$，此时$D(g||f)\approx 2.05$且$D(f||g)/(M-1) \approx 4$两者有不同的表现，具体如下图。

  之后，我们考虑了M=5和K=2的情况，情况如上不再赘述。