This paper was converted on www.awesomepapers.org from LaTeX by an anonymous user.
Want to know more? Visit the Converter page.

Bayesian Non-parametric Hidden Markov Model for Agile Radar Pulse Sequences Streaming Analysis

Jiadi Bao,  Yunjie Li, 
Mengtao Zhu,  and Shafei Wang
This work was supported by the National Natural Science Foundation (NSFC) of China under grants no. 61976019. (corresponding author: Mengtao Zhu).Jiadi Bao is with the School of Information and Electronics, Beijing Institute of Technology, Beijing, 100081, China (E-mail: [email protected]).Yunjie Li is with the School of Information and Electronics, Beijing Institute of Technology, Beijing, 100081, China, and also with the Peng Cheng Laboratory, Shenzhen, 518055, China (E-mail: [email protected]).Mengtao Zhu is with the School of Cyberspace Science and Technology, Beijing Institute of Technology, Beijing, 100081, China, and also with the Peng Cheng Laboratory, Shenzhen, 518055, China (E-mail: [email protected]). Shafei Wang is with the School of Information and Electronics, Beijing Institute of Technology, Beijing, 100081, China, and also with the Laboratory of Electromagnetic Space Cognition and Intelligent Control, Beijing, 100191, China (E-mail: [email protected]).
Abstract

Multi-function radars are sophisticated types of sensors with the capabilities of complex agile inter-pulse modulation implementation and dynamic work mode scheduling. The developments in MFRs pose great challenges to modern electronic reconnaissance systems or radar warning receivers for recognition and inference of MFR work modes. To address this issue, this paper proposes an online processing framework for parameter estimation and change point detection of MFR work modes. At first, this paper designed a fully-conjugate Bayesian Non-Parametric Hidden Markov Model with a designed prior distribution (agile BNP-HMM) to represent the MFR pulse agility characteristics. Then, the proposed framework is constructed by two main parts. The first part is the agile BNP-HMM model for automatically inferring the number of HMM hidden states and emission distribution of the corresponding hidden states. An error lower bound is derived for estimation performance and the proposed algorithm is shown to be closer to the bound compared with baseline methods. The second part combines the streaming Bayesian updating to facilitate computation, and designed an online work mode change detection framework based upon the weighted sequential probability ratio test. We demonstrate that the proposed framework is consistently highly effective and robust to baseline methods on diverse simulated radar signal data and real-life benchmark datasets.

Index Terms:
Change point detection, probabilistic graphical models, inter-pulse modulation, multi-function radar, non-parametric Bayesian model, variational inference.
publicationid: pubid: 0000–0000/00$00.00 © 2021 IEEE

I Introduction

Multi-Function Radars (MFRs) can schedule multiple simultaneous work modes for different tasks in the radar timeline [1, 2, 3], such as surveillance, target tracking, and track maintenance. With increased agility, MFRs can adapt and optimize their control parameters (such as Pulse Repetition Interval (PRI), Radio Frequency (RF), and Pulse Width (PW)) based on some mission-specific objectives [4]. The increased flexibility and adaptability of MFRs pose great challenges to modern Electronic Support (ES) systems [5, 6, 7]. To protect a target from the radar threat, the ES needs to recognize dynamic and complex work modes with possibly little prior information and detect the MFR work mode transition as soon as possible. Such that effective tactical and jamming countermeasures can be scheduled.

Traditionally, the recognition of MFR work mode is based on the supervised method. Various MFR models and recognition methods have been designed [8, 9, 10, 11]. However, due to the agility and software defined ability of modern MFR [12, 13], the prior information required for previous supervised methods for recognition is difficult to obtain or lose efficacy as new radars and radar signals always exists in the dynamic electromagnetic environments. To alleviate the requirements in prior information, model based time series clustering methods is proposed for unsupervised recognition and inter-pulse modulation parameter estimation of MFR pulse sequences [14]. However, the methods in [14] required further algorithmic designs for non-ideal conditions caused by spurious pulses and missing pulses in real world electromagnetic environments. In addition, facing the work modes with dynamic and agile inter-pulse modulations, they introduced a search-based method to find the true number of PRI levels [14]. This search operation is computationally expensive and is not suitable for online paradigm. It is necessary to develop methods for robust recognition and parameter estimation of different radar work modes especially under non-ideal situations and detecting the change point among consecutive work models in online manner.

Quickest change point detection[15] is a viable approach to solve the above motioned MFR problems. The first step is to effectively model the radar pulse sequence of different work modes. In general, the radar pulse sequences can be modeled though a parameterized model as a combination of inter and inner pulse modulations on multiple radar control parameters (such as PRI, RF and PW). For instance, in [14], four parametric models were used to represent pulse sequence with different inter-pulse modulations. In [16, 17], the Gaussian Mixture Model (GMM) was used to characterize the radar pulse sequences. In [1, 3, 2], hidden Markov model has been utilized for modeling pulse sequences of the well known “Mercury” multi-function radar111Different pulse sequences correspond to different “radar words” in their research.. The HMM can map both the inter-pulse modulation type and modulation parameters of different radar pulse sequence to a unified state space model. Each hidden state in a HMM corresponds to a specific pulse parameter value and the influence of non-ideal conditions can be modeled through introducing external hidden states. One problem of HMM inference in non-cooperative environments is that the number of hidden states KK is unknown and needs to be specified. Besides, since the hidden states in HMM for radar pulse sequences have explicit physical meanings, improper settings of KK would definitely degrade the performance and reduce the interpretability [18].

For a better representation model, the Bayesian Non-Parametric HMM (BNP-HMM) with infinite number of hidden state assumptions may serve as a potential candidate. In BNP-HMM each effective state corresponds to a hidden state with a relatively large posterior probability. The first attempts to use infinite number of hidden state assumption on HMM was performed in [19, 20]. Later, a variety of investigations have been conducted based on infinite number of hidden state assumption, such as in speaker diarization [21], radar High Resolution Range Profile (HRRP) recognition [22, 23], and human motion prediction [24]. The Bayesian non-parametric theory provided the theoretical foundation in modeling the MFR pulse sequences and achieving parameter estimation with little prior information. To the best of the authors’ knowledge, there has been no research of Bayesian non-parametric theory for intercepted radar signal analysis. Meanwhile, above mentioned investigations are based on non-agile or sticky assumptions about the hidden state transitions, and are unsuitable for estimating agile and dynamic MFR work-mode hidden state transitions with corruptions caused by non-ideal situations. Thus, for MFR applications, there are two problems that must be solved for existing BNP-HMM methods: 1) Specific designs are needed for the dynamic and agile property and non-ideal situations in MFR pulse sequences. 2) An online processing framework is needed that has efficient model learning and inference.

The second step for quickest change point detection of MFR work modes is to design the detection strategy. The quickest change point detection of the HMM model (actually the state space model) is challenging due to two main reasons: Firstly, if the pre-change distribution is known and the post-change distribution is unknown, estimating or even modeling the post-change distribution is often impractical as we may not know a priori what kind of change (including changes in structure and trend) will occur [25, 26, 27]. Secondly, computing the Kullback-Leibler (KL) divergence is necessary for evaluating the change point detection test. But calculating KL divergence in state space models is always non-trivial [28, 29]. For HMM, a common method is to use Markov chain Monte Carlo simulations to approximate the KL divergence, and asymptotic properties can be derived[26]. Fuh [28] treated the HMM as a big Markov chain, and recursive CUmulative SUM (CUSUM) was formulated based on mini-max criterion. Fuh [29] also derived the logarithmic likelihood and developed a non-Monte-Carlo method to compute KL divergence for two-state HMM. On the one hand, an effective numerical algorithm for KL divergence of any finite state HMM is remained to be solved as currently only two-state HMM was examined. On the other hand, the considered BNP-HMM for pre- and post-change distribution modeling is non-ergodic and has hidden state space with infinite cardinality, which makes the general results achieved in classical HMM not applicable.

Taking the above problems into consideration, this paper proposes a new framework that performs the Parameter Estimation task (PE task) and the Change Point Detection task (CPD task) of the MFR work modes. The framework is termed as Agile BNP-HMM-CUSUM and is consisted of three consecutive steps: MFR pulse sequence modeling, work mode parameter estimation, and change point detection. Firstly, for a better pulse sequence modeling a variant of the BNP-HMM, the agile BNP-HMM, is proposed to achieve improved control over the inferred HMM hidden states. Such control is crucial for the MFR problems we examine. Secondly, an efficient variational inference method is designed for the proposed agile BNP-HMM. The proposed method can automatically estimate the number of hidden states in BNP-HMM through the agile Dirichlet Process (DP). The agile DP is a measure on measures and is parameterized by a base distribution and a positive scaling parameter. To represent the designed agile DP, a corresponding agile stick-breaking construction method is proposed based on the conventional stick-breaking construction [30]. Our agile BNP-HMM model is further combined with streaming Bayesian updating [31] processing. The streaming updating can mitigate the PE task from local optimal and facilitate computation. Finally, to overcome the computationally demanding CPD test of HMM due to the real-time processing requirements and maintain high performance, We consider the initial distributions and transition matrices as nuisance parameters, as done in [29]. Then the problem of detecting change points for HMM is transformed into the problem of detecting change points for multivariate Gaussian and a weighted Sequential Probability Ratio Test (SPRT) is proposed for MFR applications222This simplification allows us to make use of the results from previous research on detecting change points for multivariate Gaussians [32]. Actually, similar simplifications can be found in Stephen Boyd’s method [33] for Markov Random Field. In [33], the highly structured variables are transformed into multivariate Gaussian inverse covariance matrices to simplify the raw problems with intensive computations..

The main contributions of this work can be summarized as follows:

  1. 1.

    An agile BNP-HMM is proposed to model MFR work modes with agile and dynamic properties. The proposed model is fully conjugated and permits high efficient variational inference.

  2. 2.

    An improved stick-breaking construction method is developed. Compared to the conventional stick-breaking construction method proposed by Sethuraman [30], our proposed method provides a more accurate estimation facing the agile inter-pulse modulation types. The error lower bound for estimation performance under non-ideal conditions is also derived.

  3. 3.

    An asymptotic optimal change point detection strategy is designed base upon a weighted Sequential Probability Ratio Test (weighted SPRT) [34]. The designed strategy does not require pre-specified window size information required for sliding window based methods, and is thus free of the window adjustment dilemma and achieves a simpler parameter tuning result.

  4. 4.

    The proposed agile BNP-HMM-CUSUM is combined with streaming Bayesian update techniques [31] for online processing. The computational redundancy is reduced.

The rest of the paper is organized as follows. Section II describes the PE and CPD task formulations. Section III introduces the proposed agile BNP-HMM-CUSUM framework for PE and CPD tasks. Section IV presents the simulation design, results, and discussions. Section V presents the experiments on real-life benchmark datasets. Section VI concludes the paper. Main notations of this paper is shown in Table I.

TABLE I: Main notations used in this paper
Notations Descriptions
𝑷t\boldsymbol{P}^{t} The data batch of index tt
𝑺\boldsymbol{S} The underlying state sequence of HMM
𝝅\boldsymbol{\pi} and 𝑨\boldsymbol{A} The initial and transition distribution of HMM
𝚯t\boldsymbol{\Theta}_{t} The set of Gaussian distributions at time tt
𝚼\boldsymbol{\Upsilon} The set of hyper-parameters of the BNP-HMM
𝒁t\boldsymbol{Z}^{t} The latent variable of data batch of index tt
𝝋k\boldsymbol{\varphi}^{k} The parametric model of the k th hidden state
TT The length of the data batch
LL The truncation level
KK The number of hidden states
NN The detected change point (stopping time)
ν\nu The true change point
𝜽0\boldsymbol{\theta}_{0} and 𝜽1\boldsymbol{\theta}_{1} The pre- and post-change distribution parameter
𝔼q\mathbb{E}_{q} The expectation with respect to distribution qq

II Problem Formulation

Without losing the generality, this paper defines the PE and CPD tasks of the MFR work modes by PRI parameters, but the proposed method can be extended to other Pulse Descriptive Word (PDW) and multi-parameters case. Firstly, a probabilistic generative model for different PRI modulations is presented. Then, the mathematical formulations of the PE and CPD tasks are given.

II-A PRI Modulation Representation via Probabilistic Graphical Models

There are six typical types of PRI modulations [5] that have been commonly used in related literature. Based on the hidden state self-transitioning tendency, common PRI types can be divided into two categories: agile and non-agile modulation types. Agile types including staggered PRI, sliding PRI, agile PRI. Non-agile types including jittered PRI, and Dwell and Switch (D&S) PRI. Since PRI sequence is timing data and is extracted from Time Of Arrival (TOA) sequences through first-order difference. Non-ideal conditions caused by spurious pulses and missing pulses would affect the first-order difference value (such difference is denoted as ΔTOA\Delta TOA for differentiation with the true PRI value) of its former pulses. The influence of a single missing pulse and a single spurious pulse in a pulse sequence are illustrated in Fig. 1. The existence of a spurious pulse will lead original PRI value splits into two adjacent smaller ΔTOA\Delta TOA values. A missing pulse will result in a large ΔTOA\Delta TOA value, whose value represents the sum of the PRI values of the missing pulse and it’s previous pulse. To enhance the modeling capability under non-ideal conditions, this paper employs the probabilistic graphical models to represent various types of modulation types.

Refer to caption
Figure 1: Non-ideal observations in an MFR PRI sequence. The existence of a spurious pulse will lead original PRI value splits into two adjacent smaller ΔTOA\Delta TOA values. A missing pulse will result in a large ΔTOA\Delta TOA value, which represents the summation of the original PRIs.

The MFR arranges a finite number of ordered pulses to achieve a certain radar work mode. Due to the measurement noise, the observation function of PRI values for each pulse can be modeled through a probability density function or probability mass function. This paper model the work mode as an HMM with Gaussian emissions (G-HMM). The G-HMM can be expressed as a three-tuple:

𝝀=(𝝅,𝑨,𝚯)\boldsymbol{\lambda}=(\boldsymbol{\pi},\boldsymbol{A},\boldsymbol{\Theta}) (1)

wherein 𝑨\boldsymbol{A} is the state transition matrix with KK states; 𝝅\boldsymbol{\pi} is the initial state distribution, and 𝚯\boldsymbol{\Theta} is the set of Gaussian distributions. Following Definition defines the mapping between the G-HMM and different PRI defined work modes.

Definition: The PRI sequence of a radar work mode can be represented by the Gaussian distribution set 𝚯=(𝝋1,,𝝋k,,𝝋K)\boldsymbol{\Theta}=(\boldsymbol{\varphi}^{1},...,\boldsymbol{\varphi}^{k},...,\boldsymbol{\varphi}^{K}). In this study, 𝝋k\boldsymbol{\varphi}^{k} represents the parametric model corresponds to the kkth hidden state. Under Gaussian assumptions 𝝋kN(μk,σk2)\boldsymbol{\varphi}^{k}\sim N(\mu_{k},\sigma_{k}^{2}). The probability density function (PDF) under 𝝋k\boldsymbol{\varphi}^{k} is defined as:

f𝝋k(pt)=12πσk2exp((ptμk)22σk2),1kKf_{\boldsymbol{\varphi}^{k}}(p_{t})=\frac{1}{\sqrt{2\pi\sigma_{k}^{2}}}\exp\bigg{(}-\frac{(p_{t}-\mu_{k})^{2}}{2\sigma_{k}^{2}}\bigg{)},1\leq k\leq K (2)

wherein ptp_{t} is the received pulse PRI value at time step tt. The PRI sequence follows an underlying transition pattern 𝑨=(𝒂j)j=1N,𝒂j=(aji)i=1N\boldsymbol{A}=(\boldsymbol{a}_{j})_{j=1}^{N},\boldsymbol{a}_{j}=(a_{ji})_{i=1}^{N}. For instance, considering a work mode with staggered PRI modulation, the transmitted stagger sequence in a single period is (2,3,5)(2,3,5). In this case, the received stagger sequence with measurement noise (assume noise variance is 0.1) can be represented by 𝚯=(𝝋1,𝝋2,𝝋3)\boldsymbol{\Theta}=(\boldsymbol{\varphi}^{1},\boldsymbol{\varphi}^{2},\boldsymbol{\varphi}^{3}) with 𝝋1=(μ1=2,σ12=0.1)\boldsymbol{\varphi}^{1}=(\mu_{1}=2,\sigma_{1}^{2}=0.1), 𝝋2=(μ2=3,σ22=0.1)\boldsymbol{\varphi}^{2}=(\mu_{2}=3,\sigma_{2}^{2}=0.1), 𝝋3=(μ3=5,σ32=0.1)\boldsymbol{\varphi}^{3}=(\mu_{3}=5,\sigma_{3}^{2}=0.1), respectively. Besides, a12=1,a23=1,a31=1,aji=0forji{12,23,31}a_{12}=1,a_{23}=1,a_{31}=1,a_{ji}=0\,{\rm~{}for~{}}\,ji\notin\{12,23,31\}. Fig. 2 shows an example of different modulated PRI sequences, corresponding graphical transitions and state transition matrix.

II-B MFR Work Mode Parameter Estimation and Change Point Detection

We formulate the difference in either the inter-pulse modulation type or the modulation parameters as a change point in two adjacent work modes. Assuming {pt}t1\{p_{t}\}_{t\geq 1} is a pulse sequence parameterized by {𝝀t}t1\{\boldsymbol{\lambda}_{t}\}_{t\geq 1}. Until the change point ν\nu, the parameter stays at 𝝀<ν\boldsymbol{\lambda}_{<\nu}, but after the change point, the parameter changes to 𝝀ν\boldsymbol{\lambda}_{\geq\nu}, as shown in (3).

(pt,𝝀t)={𝝀<νift<ν𝝀νiftν\mathcal{H}(p_{t},\boldsymbol{\lambda}_{t})=\begin{cases}\boldsymbol{\lambda}_{<\nu}&\rm{if}\ \emph{t}<\nu\\ \boldsymbol{\lambda}_{\geq\nu}&\rm{if}\ \emph{t}\geq\nu\end{cases} (3)

In traditional change point detection studies, the pre- and post-change distributions maybe known in advance (or at least their structures are known). But in radar interception applications with less prior assumption, we assume that the exact pre- and post-change distribution (both the structure and the parameters) is unknown. The structure of both distributions are modeled and determined by the proposed agile BNP-HMM, and the pre-change distribution can be estimated from the data according to the Bayesian theorem:

p(𝝀t|𝑷t)=p(𝝀t)p(𝑷t|𝝀t)p(𝑷t,𝝀t)𝑑𝝀tp(\boldsymbol{\lambda}_{t}|\boldsymbol{P}^{t})=\frac{p(\boldsymbol{\lambda}_{t})p(\boldsymbol{P}^{t}|\boldsymbol{\lambda}_{t})}{\int p(\boldsymbol{P}^{t},\boldsymbol{\lambda}_{t})d\boldsymbol{\lambda}_{t}} (4)

wherein p(𝝀t)p(\boldsymbol{\lambda}_{t}) is the prior distribution; 𝑷t={pt}t=1t\boldsymbol{P}^{t}=\{p_{t}\}_{t=1}^{t} is a batch of data and p(𝑷t,𝝀t)𝑑𝝀t\int p(\boldsymbol{P}^{t},\boldsymbol{\lambda}_{t})d\boldsymbol{\lambda}_{t} is the evidence integral. Specifically, the objective of the parameter estimation task is the number of PRI level in a period (KK), the Gaussian parameters of each PRI level (𝝋1,,𝝋K\boldsymbol{\varphi}^{1},...,\boldsymbol{\varphi}^{K}), and the modulation type of a pulse sequence (𝑨\boldsymbol{A}). After these hidden variables are inferred, a change point detection task will be performed through the estimated parameter sequence.

To clarify the detection criterion, the detector reaches the stopping time NN called the change point alarm time. From the online processing perspective, the alarm time should always happen after the actual change time. We consider Lorden’s “worst case” Mean Detection Delay (MDD) [35]:

τ¯=supt1esssup𝔼𝝀ν(NνNν,𝑷)\bar{\tau}^{*}=\sup_{t\geq 1}\operatorname{ess}\sup\mathbb{E}_{\boldsymbol{\lambda}_{\geq\nu}}\left(N-\nu\mid N\geq\nu,\boldsymbol{P}\right) (5)

The MDD should be as small as possible before a false alarm under the constraint of Mean Time to False Alarm (MT2FA), and the MT2FA is formulated as follows:

T¯=𝔼𝝀<ν(N)\overline{T}=\mathbb{E}_{\boldsymbol{\lambda}_{<\nu}}(N) (6)

wherein esssup\rm{ess}\sup denotes the essential supremum. The mean detection delay τ¯\overline{\tau}^{*} needs to be minimized while the mean time to false alarm T¯\overline{T} needs to be maximized:

minimizeMDD(N) subject to MT2FA(N)γ\operatorname{minimize}\operatorname{MDD}(N)\text{ subject to }\operatorname{MT2FA}(N)\geq\gamma (7)

wherein γ\gamma is the constraint of MT2FA. The above optimization problem is a minimax problem.

Refer to caption
Figure 2: PRI sequences and their corresponding Markov chain and state transition matrix. (a) D&S PRI, (b) Stagger PRI, (c) Sliding PRI, (d) Jittered PRI.

III Method

This paper proposes an online processing framework for MFR work mode parameter estimation and change point detection. This section at first introduces a fully conjugate generative model (agile BNP-HMM) and a new prior distribution (the agile prior distribution). Then, we describe the online processing procedure and corresponding implementations.

III-A Agile Bayesian Non-parametric HMM Construction

For non-cooperative tasks of MFR reconnaissance, the number of hidden states and corresponding parameters of the work mode are always unknown and need to be inferred. A novel agile prior distribution is designed to control the G-HMM hidden state self-transitioning tendency to model the transition process of the MFR work mode with an agile inter-pulse modulation type. In this section, we first present a generative model for an MFR work mode. Then we introduce an improved stick-breaking construction method for the agile modulation type prior distribution implementation. Finally, we derived closed-form variational Bayesian iteration functions based on the proposed graphical model.

III-A1 Agile Bayesian Non-parametric HMM

The graphical model of the agile BNP-HMM is shown in Fig. 3, wherein the intercepted pulses 𝑷={pt}t1\boldsymbol{P}=\{p_{t}\}_{t\geq 1}, hidden state assignments 𝑺={st}t1\boldsymbol{S}=\{s_{t}\}_{t\geq 1}, sufficient statistics 𝚯=(𝝋k)k=1\boldsymbol{\Theta}=({\boldsymbol{\varphi}^{k}})_{k=1}^{\infty}, initial distribution 𝝅=(πk)k=1\boldsymbol{\pi}=(\pi_{k})_{k=1}^{\infty}, transition matrix 𝑨=(𝒂j)j=1,𝒂j=(aji)i=1\boldsymbol{A}=(\boldsymbol{a}_{j})_{j=1}^{\infty},\boldsymbol{a}_{j}=(a_{ji})_{i=1}^{\infty}, concentration parameter απ,αA\alpha_{\pi},\alpha_{A}, the agile hyper-parameter κ\kappa and the length of the data batch TT are presented. The generative model can be formulated using the Bayesian theory as follows:

p(𝑷,𝑺,𝚯,𝝅,𝑨)\displaystyle p(\boldsymbol{P,S,\Theta,\pi,A}) (8)
=p(𝑷,𝑺|𝚯,𝝅,𝑨)p(𝝅)p(𝑨)p(𝚯)\displaystyle=p(\boldsymbol{P,S|\Theta,\pi,A})p(\boldsymbol{\pi})p(\boldsymbol{A})p(\boldsymbol{\Theta})
=[p(s1|𝝅)t=2Tp(st|st1,𝑨)t=1Tp(pt|st)]\displaystyle=\Bigg{[}p(s_{1}|\boldsymbol{\pi})\prod_{t=2}^{T}p(s_{t}|s_{t-1},\boldsymbol{A})\prod_{t=1}^{T}p(p_{t}|s_{t})\Bigg{]}
p(𝝅)p(𝑨)k=1p(𝝋k)\displaystyle~{}~{}~{}~{}p(\boldsymbol{\pi})p(\boldsymbol{A})\prod_{k=1}^{\infty}p(\boldsymbol{\varphi}^{k})

Based on the research presented in [36], to ensure the generative model is fully conjugate, the joint distribution of the sufficient statistics are generated using the Gaussian-Gamma distribution, which is given in (9).

p(𝝋k)\displaystyle p(\boldsymbol{\varphi}^{k}) =N(μk,σk2)\displaystyle=N(\mu_{k},\sigma_{k}^{2}) (9)
p(μk|σk2)\displaystyle p(\mu_{k}|\sigma_{k}^{-2}) =N(ξ0,σk2/λ0)\displaystyle=N(\xi_{0},\sigma_{k}^{2}/\lambda_{0})
p(σk2)\displaystyle p(\sigma_{k}^{-2}) =Gamma(a0,b0)\displaystyle=Gamma(a_{0},b_{0})

wherein μk,σk2\mu_{k},\sigma_{k}^{2} are the mean and variance of the Gaussian distribution, respectively; σk2=1σk2\sigma_{k}^{-2}=\frac{1}{\sigma_{k}^{2}} represents the precision of the Gaussian distribution; ξ0,λ0,a0,b0\xi_{0},\lambda_{0},a_{0},b_{0} are hyper-parameters of the Gaussian-Gamma distribution; NN refers to Gaussian distribution and GammaGamma refers to Gamma distribution333In MFR applications, each work mode is modeled by a BNP-HMM. The hidden state number in BNP-HMM generally varies across different MFR work modes. The work mode can change over time, and the number of hidden states would also change over time. The infinite assumption in Bayesian-nonparametric theory does not require the number of hidden states be pre-defined during inference.

The Dirichlet distribution to the HMM encourages hidden states to have similar transition distributions. However, it does not differentiate self-transitions from moves between the hidden states. Therefore, when modeling the MFR work mode with the agility characteristic, the self-transition nature of the Dirichlet distribution allows for a high posterior probability of hidden state persistence. Thus it tends to underestimate the hidden state number.

This paper proposed the agile BNP-HMM to determine the number of hidden states. The agile BNP-HMM is governed by placing an agile prior distribution over the state transition probability. The agile prior distribution is used to present the case of a few self-transitions. To implement the agile prior distribution, a novel stick-breaking construction method is designed.

Refer to caption
Figure 3: The graphical model of the proposed agile BNP-HMM.

III-A2 Agile Prior and Stick-breaking Construction

At first, the Dirichlet distribution is reviewed. For any partitions G={G1,,G}G=\{G_{1},...,G_{\infty}\} of the probability space Ω\Omega, the distribution of the base measure’s probability mass on the partition GG is defined as follows:

(aj1,aj2,,aj)=\displaystyle(a_{j1},a_{j2},...,a_{j\infty})= (10)
𝒟(αAH(G1),,αAH(G))\displaystyle\mathcal{DIR}(\alpha_{A}H(G_{1}),...,\alpha_{A}H(G_{\infty}))

wherein 𝒟\mathcal{DIR} denotes the Dirichlet process; HH is the base measure; αA\alpha_{A} represents the concentration parameter; 𝒂j\boldsymbol{a}_{j} is a random variable that follows the multi-nominal distribution, and the 𝒟\mathcal{DIR} can be implemented as a stick-breaking construction444The construction can be briefly explained. Suppose there is a stick with length 1. Let ajiBeta(1,αA)a_{ji}^{\prime}\sim Beta(1,\alpha_{A}) for i=1,2,3,,i=1,2,3,...,\infty, and regard them as fractions for how much we take away from the remainder of the stick every time. Then ajia_{ji} can be calculated by the length we take away each time: aj1=aj1,aj2=(1aj1),,aji=ajin=1i1(1ajn)a_{j1}=a_{j1}^{\prime},a_{j2}=(1-a_{j1}^{\prime}),...,a_{ji}=a_{ji}^{\prime}\prod_{n=1}^{i-1}(1-a_{jn}^{\prime}). By the stick-breaking construction, we will have i=1aji=1\sum_{i=1}^{\infty}a_{ji}=1. [30]:

aji\displaystyle a_{ji}^{\prime} =Beta(1,αA),\displaystyle=Beta(1,\alpha_{A}), (11)
aji\displaystyle a_{ji} =ajin=1i1(1ajn)\displaystyle=a_{ji}^{\prime}\prod_{n=1}^{i-1}(1-a_{jn}^{\prime})

wherein BetaBeta refers to the beta distribution and αA\alpha_{A} is the concentration parameter.

An agile hyper-parameter is introduced to the Dirichlet distribution to control the hidden states self-transitioning tendency of MFR pulse sequences, resulting in agile Dirichlet process (agile 𝒟\mathcal{DIR}), which is given by:

(aj1,,ajj,,aj)=\displaystyle(a_{j1},...,a_{jj},...,a_{j\infty})= (12)
𝒟(αAH(G1),,(αA+κ)H(Gj),,αAH(G))\displaystyle\mathcal{DIR}(\alpha_{A}H(G_{1}),...,(\alpha_{A}+\kappa)H(G_{j}),...,\alpha_{A}H(G_{\infty}))

wherein κ\kappa is the agile hyper-parameter, and a larger κ\kappa value encourages an HMM to move from the current state jj to another state instead of staying in the current state.

The agile 𝒟\mathcal{DIR} can be implemented via a new stick-breaking construction as follows:

aji\displaystyle a_{ji}^{\prime} =Beta(1,αA+κδ(ij)),\displaystyle=Beta(1,\alpha_{A}+\kappa\delta(i-j)), (13)
aji\displaystyle a_{ji} =ajin=1i1(1ajn)\displaystyle=a_{ji}^{\prime}\prod_{n=1}^{i-1}(1-a_{jn}^{\prime})

wherein iaji=1\sum_{i}^{\infty}a_{ji}=1, and δ\delta is the Dirichlet-delta function. When i=ji=j , ajja_{jj}^{\prime} is sampled from Beta(1,αA+κ)Beta(1,\alpha_{A}+\kappa), the BetaBeta distribution tends to put more mass on smaller values. Thus ajja_{jj}^{\prime} tends to smaller than ajia_{ji}^{\prime}, leading to break a shorter stick.

III-A3 Variational Inference for Agile BNP-HMM

In the inference procedure, it is necessary to estimate the posterior distribution from the observed data and the given hyper-parameters 𝚼={απ,αA,a0,b0,λ0,ξ0,κ}\boldsymbol{\Upsilon}=\{\alpha_{\pi},\alpha_{A},a_{0},b_{0},\lambda_{0},\xi_{0},\kappa\}. The inference of agile BNP-HMM is illustrated as Algorithm 1.

Variational inference is an efficient way to approximate the intractable posterior, which introduces a variational distribution q to approximate the true posterior. The basic idea of variational inference is to minimize the distance between the variational distribution q and the exact posterior p. The likelihood function is formulated as (14):

lnp(𝑷|𝑺,𝝅,𝑨,𝚯,𝚼)=(q(𝑺,𝝅,𝑨,𝚯))\displaystyle\ln p(\boldsymbol{P|S,\pi,A,\Theta,\Upsilon})=\mathcal{L}(q(\boldsymbol{S,\pi,A,\Theta})) (14)
+𝒦(q(𝑺,𝝅,𝑨,𝚯)||p(𝑺,𝝅,𝑨,𝚯|𝑷,𝚼))\displaystyle+\mathcal{KL}(q(\boldsymbol{S,\pi,A,\Theta})||p(\boldsymbol{S,\pi,A,\Theta|P,\Upsilon}))

wherein \mathcal{L} denotes the well-known evidence lower bound (ELBO), and 𝒦\mathcal{KL} is the Kullback-Leibler divergence. Minimizing the similarity between the variational distribution and the exact posterior is to maximize the evidence lower bound [36].

This paper considers the partial mean-field variational family [37] and truncation assumption for variational inference. The partial mean-field family assumes that (𝝅,𝑨,𝚯,𝚼)(\boldsymbol{\pi,A,\Theta,\Upsilon}) and (𝑺)(\boldsymbol{S}) are mutually independent. The truncation assumption considers the probabilities of LL states as the infinite hidden states, wherein LL is called the truncation level, and LL should be large enough to ensure the accuracy. The variational distribution is defined as follows:

q(𝚯)\displaystyle q(\boldsymbol{\Theta}) =q(𝑺)q(𝝅)q(𝑨)q(μ,σ2)\displaystyle=q(\boldsymbol{S})q(\boldsymbol{\pi}^{\prime})q(\boldsymbol{A}^{\prime})q(\mu,\sigma^{-2}) (15)
=q(s1)t=2Tq(st|st1)i=1Lq(πi)j=1Li=1Lq(aji)\displaystyle=q(s_{1})\prod_{t=2}^{T}q(s_{t}|s_{t-1})\prod_{i=1}^{L}q(\pi_{i}^{\prime})\prod_{j=1}^{L}\prod_{i=1}^{L}q(a_{ji}^{\prime})
j=1Lq(μj|σj2)q(σj2)\displaystyle~{}~{}~{}~{}\prod_{j=1}^{L}q(\mu_{j}|\sigma_{j}^{-2})q(\sigma_{j}^{-2})

Exponential family is chosen for each component of the variational distribution. The variational distributions can then be represented as follows:

q(πi)=Beta(η1(πi),η2(πi))q(\pi_{i}^{\prime})=Beta(\eta_{1}(\pi_{i}^{\prime}),\eta_{2}(\pi_{i}^{\prime})) (16)
q(aji)=Beta(η1(aji),η2(aji))q(a_{ji}^{\prime})=Beta(\eta_{1}(a_{ji}^{\prime}),\eta_{2}(a_{ji}^{\prime})) (17)
q(μj|σj2)=N(μj,σj2/λj)q(\mu_{j}|\sigma_{j}^{-2})=N(\mu_{j},\sigma_{j}^{-2}/\lambda_{j}) (18)
q(σj2)=Gamma(aj,bj)q(\sigma_{j}^{-2})=Gamma(a_{j},b_{j}) (19)

Then the evidence lower bound can be derived according to:

=𝔼q[lnp(𝝅,𝑺,𝑨,𝚯,𝑷)]𝔼q[lnq(𝝅,𝑺,𝑨,𝚯)]\mathcal{L}=\mathbb{E}_{q}[\ln p(\boldsymbol{\pi,S,A,\Theta,P})]-\mathbb{E}_{q}[\ln q(\boldsymbol{\pi,S,A,\Theta})] (20)

This paper uses the coordinate ascent algorithm [38] to maximize the ELBO. The universal update function is given by [36]:

ln[qn(𝒁n)]=𝔼n[lnp(𝑷,𝒁)]+ const \ln\left[q_{n}^{*}\left(\boldsymbol{Z}_{n}\right)\right]=\mathbb{E}_{-n}[\ln p(\boldsymbol{P},\boldsymbol{Z})]+\text{ const } (21)

wherein 𝒁={𝝅,𝑨,𝚯,𝑺}\boldsymbol{Z}=\{\boldsymbol{\pi,A,\Theta,S}\}, nn refers to the nnth hidden variable. The details of the derivation and the update function can be found in the supplementary material.

Input: a batch of data 𝑷n\boldsymbol{P}^{n}, hyperparameters 𝚼\boldsymbol{\Upsilon}, truncation level LL, and prior distribution priorprior
Output: transition matrix 𝑨\boldsymbol{A}, parameter set 𝚯\boldsymbol{\Theta}, and initial distribution 𝝅\boldsymbol{\pi}
1 if prior is None then
2       initialize 𝝅,𝑨,𝚯,𝑺\boldsymbol{\pi},\boldsymbol{A},\boldsymbol{\Theta},\boldsymbol{S};
3      
4else
5       𝝅,𝑨,𝚯,𝑺prior\boldsymbol{\pi,A,\Theta,\boldsymbol{S}}\leftarrow prior;
6      
7 end if
8repeat
9       Variational Inference (21);
10      
11until  Convergence ;
12Sample 𝝅,𝑨,𝚯\boldsymbol{\pi,A,\Theta} and return;
Algorithm 1 Agile Bayesian Non-parametric HMM (agile BNP-HMM)

III-B Implementation of MFR Work Mode Parameter Estimation and Change Point Detection

This paper considers a control chart base upon the weighted SPRT for online change point detection paradigm. To facilitate the inference in each new time step, streaming Bayesian updating[31] is designed to the iterative variational inference of the agile BNP-HMM model. This streaming process also prevents variational inference from falling into a local optimal.

III-B1 Initialization of the Agile BNP-HMM-CUSUM Framework

After setting the hyper-parameters Υ\Upsilon, pulse PRI values were collected in a buffer called the initial-batch. Since this paper assumes no knowledge about the data in the initial-batch, the Dirichlet Process Mixture Model (DPMM) [39] is used to obtain an initial guess of agile BNP-HMM model parameters of the data in initial-batch. For subsequent PE task, due to the streaming nature, six hyper-parameters that need to be tuned 𝚼={αA,απ,ξ0,λ0,a0,b0}\boldsymbol{\Upsilon}=\{\alpha_{A},\alpha_{\pi},\xi_{0},\lambda_{0},a_{0},b_{0}\}, wherein 𝚼\boldsymbol{\Upsilon} is time variant and thus not suitable for change point detection tasks. In this work, the agile hyper-parameter κ\kappa represents the time-series characteristics over time, and κ\kappa is the only parameter need to be tuned for the PE task. The whole framework is illustrated as Algorithm 2.

Since our model is fully conjugate, we only need to initialize the sufficient statistics of (16)-(19). Specifically, η1(π1),η2(π2),η1(aji),η2(aji),aj,bj\eta_{1}(\pi_{1}^{\prime}),\eta_{2}(\pi_{2}^{\prime}),\eta_{1}(a_{ji}^{\prime}),\eta_{2}(a_{ji}^{\prime}),a_{j},b_{j} are all set to one in the initialization step. The mean μj\mu_{j} and variance σj2/λj\sigma_{j}^{-2}/\lambda_{j} of each Gaussian distributions are set to 0 and 0.1 in the initialization step.

III-B2 Online Parameter Estimation Task for Agile BNP-HMM under Non-ideal Observations

After initialization, each pulse in the initial-batch belongs to a particular hidden state. In parameter estimation step, a new pulse is received and combined with previously arrived pulses to create a new data batch. Given the new data batch, the agile BNP-HMM algorithm is used to update the transition matrix and Gaussian distribution parameters. Due to the non-ideal observation conditions, there will be ΔTOA\Delta TOA values caused by missing and spurious pulses. These ΔTOA\Delta TOA values will result in a false hidden state with a relatively low visiting probability and a high transition probability. An acceptance threshold γu\gamma_{u} is set, when 𝔼[𝒂j]γu\mathbb{E}[\boldsymbol{a}_{j}]\leq\gamma_{u} satisfies, the corresponding hidden states are considered as ΔTOA\Delta TOA values caused by missing or spurious pulses and are deleted. The remaining hidden states are assumed originating from true PRI values.

Streaming Bayesian updating enables high efficient parameter estimation and reduces the risk of falling into local optima during the PE task. Assume that 𝑷n={pt}1m+n\boldsymbol{P}^{n}=\{p_{t}\}_{1}^{m+n}, and index mm and nn as the initial-batch length and the nnth arrived pulse after the initial-batch, respectively. For the initial-batch, applying the Bayesian rule yields p(𝒁0|𝑷0)=p(𝑷0|𝒁0)/p(𝑷0)p(\boldsymbol{Z}^{0}|\boldsymbol{P}^{0})=p(\boldsymbol{P}^{0}|\boldsymbol{Z}^{0})/p(\boldsymbol{P}^{0}). Superscript 0 denotes batch index 0. When a new pulse arrives, the batch index increases by one and a random hidden variable is assigned to the new arrived pulse. All underlying state sequences are combined and denoted as p(𝒁1)p(\boldsymbol{Z}^{1}). By applying the Bayesian rule again, instead of placing the prior p(𝒁1)p(\boldsymbol{Z}^{1}), the previous data batch’s variational posterior q(𝒁0|𝑷0)q(\boldsymbol{Z}^{0}|\boldsymbol{P}^{0}) is set as the current data batch’s prior. In variational inference, the true posterior for the nnth batch p(𝒁n|𝑷1:n)p(\boldsymbol{Z}^{n}|\boldsymbol{P}^{1:n}) is approximated by the variational distribution qn(𝒁n)q^{n}(\boldsymbol{Z}^{n}). Thus, the online variational inference is obtained by substituting qn1(𝒁n1)q^{n-1}(\boldsymbol{Z}^{n-1}) for the prior as follows:

p(𝒁n𝑷1:n)qn(𝒁)=p(𝑷n𝒁n)qn1(𝒁n1)p(𝑷1:n1)p\left(\boldsymbol{Z}^{\mathrm{n}}\mid\boldsymbol{P}^{1:n}\right)\approx q^{n}(\boldsymbol{Z})=\frac{p\left(\boldsymbol{P}^{n}\mid\boldsymbol{Z}^{\mathrm{n}}\right)q^{n-1}\left(\boldsymbol{Z}^{\mathrm{n}-1}\right)}{p\left(\boldsymbol{P}^{1:n-1}\right)} (22)

The estimated parameter tuple (𝝅,𝑨,𝚯)n(\boldsymbol{\pi},\boldsymbol{A},\boldsymbol{\Theta})^{n} for the nnth batch is sent to a stack. All parameter tuples estimated in the previous time step are pushed in the stack. Then, the newly estimated tuple and the stack are sent to the change point detector.

III-B3 Online Change Point Detection Strategy

Detecting the change point of the MFR work mode is equivalent to detecting the change point for BNP-HMM. However, BNP-HMM’s non-ergodicity and infinite hidden state space render general results [28, 27] invalid. Additionally, computing the invariant measure of HMM is computationally demanding. Directly detecting changes from HMM contradicts the basic principle of designing a system in MFR applications - that it should be computationally efficient while clear enough to distinguish various work modes. Therefore, we treat the prior distribution and the transition distributions as nuisance parameters similar to [29], which makes previous research results [32] valid. Our approach resembles Stephen Boyd’s method [33] by transforming learning complex structure problem into multivariate Gaussian inverse covariance matrices to simplify computationally intensive problems.

The change point detector considers the weighted SPRT [32]. Taking modulation parameter level change point as an example, the agile BNP-HMM sequentially returns the parameter set 𝚯0,𝚯1,𝚯2,,𝚯Lm\boldsymbol{\Theta}_{0},\boldsymbol{\Theta}_{1},\boldsymbol{\Theta}_{2},...,\boldsymbol{\Theta}_{L-m}. The parameter sets can be described as a multi-variate Gaussian distribution as follows:

(𝚯t)={N(𝜽0,𝚺)ift<νN(𝜽1,𝚺)iftν\mathcal{H}(\boldsymbol{\Theta}_{t})=\begin{cases}N(\boldsymbol{\theta}_{0},\boldsymbol{\Sigma})&\rm{if}\ t<\nu\\ N(\boldsymbol{\theta}_{1},\boldsymbol{\Sigma})&\rm{if}\ t\geq\nu\end{cases} (23)

wherein 𝜽0=(𝝁01,,𝝁0K)\boldsymbol{\theta}_{0}=(\boldsymbol{\mu}_{0}^{1},...,\boldsymbol{\mu}_{0}^{K}) and 𝜽1=(𝝁11,,𝝁1K)\boldsymbol{\theta}_{1}=(\boldsymbol{\mu}_{1}^{1},...,\boldsymbol{\mu}_{1}^{K}) are the pre- and post-change parameters, respectively. 𝚺\boldsymbol{\Sigma} is the unit covariance matrix.

Following common assumptions in asymptotic performance analysis of the change point detector, we assume that the pre-change parameter 𝜽0\boldsymbol{\theta}_{0} is known, and the post-change parameter 𝜽1\boldsymbol{\theta}_{1} is unknown. The change amplitude bb is known and given by:

b2=(𝜽1𝜽0)T𝚺1(𝜽1𝜽0)b^{2}=\boldsymbol{(\theta}_{1}-\boldsymbol{\theta}_{0})^{\rm{T}}\boldsymbol{\Sigma}^{-1}\boldsymbol{(\theta}_{1}-\boldsymbol{\theta}_{0}) (24)

The stopping time NN is expressed by:

N=inf{t1:max1<k<tm+1Dkt>λ}N=\inf\left\{t\geq 1:\max_{1<k<t-m+1}D_{k}^{t}>\lambda\right\} (25)
Dkt=(tk)b22+lnG(K2,b2(tk)2(χkt)24)D_{k}^{t}=-\frac{(t-k)b^{2}}{2}+\ln G\left(\frac{K}{2},\frac{b^{2}(t-k)^{2}\left(\chi_{k}^{t}\right)^{2}}{4}\right) (26)
(χkt)2=(𝑺kt¯)T𝚺1𝑺¯kt\left(\chi_{k}^{t}\right)^{2}=\left(\bar{\boldsymbol{S}_{k}^{t}}\right)^{T}\boldsymbol{\Sigma}^{-1}\bar{\boldsymbol{S}}_{k}^{t} (27)

wherein S¯kt=i=kt(𝚯i𝜽0)\bar{S}_{k}^{t}=\sum_{i=k}^{t}\left(\boldsymbol{\Theta}_{i}-\boldsymbol{\theta}_{0}\right),G(d,z)=1+zd++znd(d+1)(d+n1)n!+G(d,z)=1+\frac{z}{d}+\cdots+\frac{z^{n}}{d(d+1)\ldots(d+n-1)n!}+\cdots is generalized hyper-geometric function, wherein nn is the index of the nn th item of the expansion. The strategy is asymptotic optimal in the sense of mini-max criterion [32]. The result is stand by the following theorem:

Theorem 1

The “worst-case” mean detection delay for the χ2\chi^{2}-CUSUM is given by the following asymptotic equation as T¯\bar{T}\to\infty.

τ¯(T¯)lnT¯ρ(𝜽1,𝜽0)=2lnT¯b2\bar{\tau}^{*}(\bar{T})\sim\frac{\ln\bar{T}}{\rho\left(\boldsymbol{\theta}_{1},\boldsymbol{\theta}_{0}\right)}=\frac{2\ln\bar{T}}{b^{2}} (28)

wherein τ¯\bar{\tau}^{*} is the optimal mean detection delay; T¯\bar{T} is the mean time to false alarm; ρ=b22\rho=\frac{b^{2}}{2} is the Kullback-Leibler divergence of pre- and post-change distribution.

Refer to caption
Figure 4: Comparison between the simulation results and the asymptotic case.

The proof of Theorem 1 can be found in supplementary material555Currently, we do not consider the situation of changes only in transition matrix between adjacent work modes. Because this situation is relatively rare in MFR applications. But as stated in the Introduction Section, the change point detection of this situation is non-trivial. We leave this for future study.. We also show that the result of the comparison between the simulation results (green dots) and the asymptotic case (red dashed line) in Fig. 4, wherein each green dot represents the average value of 100 Monte Carlo simulations. The linear relationship between the MDD and the log of MT2FA in asymptotic cases is verified. The simulation results approach the asymptotic case when lnT¯\ln{\bar{T}} is large (such as lnT¯3×103\ln{\bar{T}}\geq 3\times 10^{3}). When lnT¯\ln\bar{T}\to\infty is not satisfied, the Berk’s theorem is not satisfied (see supplementary material), and the linear relationship between the lnT¯\ln\bar{T} and τ¯\bar{\tau}^{*} can not be guaranteed. Meanwhile, a smaller value of lnT¯\ln\bar{T} implies that it is easier for the detector to trigger an alarm. Consequently, a smaller value of lnT¯\ln\bar{T} leads to a smaller value of MDD. This explanation also clarifies why the MDD of the simulation result (green dots) is lower than the asymptotic case (red dashed line) when the value of lnT¯\ln\bar{T}\to\infty is small.

III-C Complexity Analysis

According to Blei [38], the complexity of the designed variational family determines the complexity of the optimization. The agile BNP-HMM chooses the structured (partial mean field) variational family  [37]. The time complexity of one single iteration is O(L2T)O(L^{2}T) and the space complexity is O(LT)O(LT), wherein LL is the truncation level and TT is the length of the sequence. The total time complexity of the algorithm is O(NL2T)O(NL^{2}T) (in space O(LT)O(LT)), wherein NN is the number of iterations. In this paper, we have designed an online variational inference method under the variational streaming Bayes framework [31]. Under streaming settings, the PE task is expected to converge in fewer steps compared to random initialization or initiated by fixed values, resulting in a lower NN. Meanwhile the PE task did not need to revisit the old data for current inference, resulting in a lower TT. Thus, the computational redundancy can be reduced.

III-D Error Analysis for Non-ideal Conditions

In this section, we establish a lower bound on the error probability for distinguishing true pulses from spurious ones using PRI data and maximum likelihood criterion. This bound can be used to assess how close an algorithm is to optimum, regardless of the specific algorithm. Although our focus is on spurious pulses, this bound can also be extended to cases involving missing pulses or mixtures of missing and spurious pulses666The derivation is inspired by [40], which establish a lower bound for the deinterleaving scheme of mixtures of renewal process..

In general, estimation error of the PRI value of a true pulse as a spurious pulse can significantly impact the estimation of subsequent modulation types and parameters. Specifically, defining the mmth pulse as the true pulse, and the mm^{\prime}th pulse be the nearest spurious pulse. The pulse index mm^{\prime} is formulated by m=argminm|TOAmTOAm|,mΩt,mΩsm^{\prime}={\rm arg}\min_{m^{\prime}}|TOA_{m}-TOA_{m^{\prime}}|,m\in\Omega_{t},m^{\prime}\in\Omega_{s}, wherein TOAmTOA_{m} is the arrival time of the mmth pulse, the Ωt\Omega_{t} is the set of true pulse’s indices, and Ωs\Omega_{s} is the set of spurious pulse’s indices. Let MtM_{t} represent the event wherein the mmth true pulse is identified as a spurious pulse and mm^{\prime}th spurious pulse is identified as a true pulse. We assess the performance of our algorithms by the error probability777Other possible errors are not considered in this study as we are developing a lower bound.:

Pe=limTP(sj^sj)P_{e}=\lim_{T\to\infty}P(\hat{s_{j}}\neq s_{j}) (29)

wherein sjs_{j} is the true hidden state, and sj^\hat{s_{j}} is the predicted hidden state. Then the lower bound on the error probability of the true pulse therefore is:

Pet\displaystyle P_{e}^{t} limTE[1Tt=1T𝟙(Mt)]=limTt=1TP(Mt)=P(Mt)\displaystyle\geq\lim_{T\rightarrow\infty}E\left[\frac{1}{T}\sum_{t=1}^{T}\mathds{1}\left(M_{t}\right)\right]=\lim_{T\rightarrow\infty}\sum_{t=1}^{T}P(M_{t})=P\left(M_{t}\right) (30)

wherein TT is the number of received pulses, 𝟙\mathds{1} is the indicator function. To derive the lower bound, we make two assumptions. Firstly, the elements of event {Mt}t=1T\{M_{t}\}_{t=1}^{T} are disjoint. Secondly, we assume that the true pulses and the spurious pulses are mutually independent. Theorem 2 provides the error probability lower bound.

Theorem 2

Suppose the true pulse and the spurious pulse can be represented by φtN(μt,σt2),φsN(μs,σs2)\varphi_{t}\sim N(\mu_{t},\sigma_{t}^{2}),\varphi_{s}\sim N(\mu_{s},\sigma_{s}^{2}), respectively. The lower bound on error probability for the true pulse is:

Pet\displaystyle P_{e}^{t}\geq (31)
0σsσtxexp(k24)2πQ(σsσtxμtσt)Q(2σsσtxμtσt)\displaystyle\int_{0}^{\infty}\int_{\frac{\sigma_{s}}{\sigma_{t}}x}^{\infty}\frac{\exp\left(-\frac{k^{2}}{4}\right)}{2\sqrt{\pi}Q\left(\frac{\sigma_{s}}{\sigma_{t}}x-\frac{\mu_{t}}{\sigma_{t}}\right)Q\left(2\frac{\sigma_{s}}{\sigma_{t}}x-\frac{\mu_{t}}{\sigma_{t}}\right)}
(Q[2(σsσtxμtσtk2)]+Q[2(2σsσtxμtσtk2)]\displaystyle\bigg{(}Q\left[\sqrt{2}\left(\frac{\sigma_{s}}{\sigma_{t}}x\right.\right.\left.\left.-\frac{\mu_{t}}{\sigma_{t}}-\frac{k}{2}\right)\right]+Q\left[\sqrt{2}\left(2\frac{\sigma_{s}}{\sigma_{t}}x-\frac{\mu_{t}}{\sigma_{t}}-\frac{k}{2}\right)\right]
1)dkx21Q(x2)2πexp(k22)dk\displaystyle-1\bigg{)}dk\int_{-\frac{x}{2}}^{\infty}\frac{1}{Q\left(-\frac{x}{2}\right)\sqrt{2\pi}}\exp\left(-\frac{k^{2}}{2}\right)dk
σsμsQ(xμsσs)dx\displaystyle\frac{\sigma_{s}}{\mu_{s}}Q\left(x-\frac{\mu_{s}}{\sigma_{s}}\right)dx

wherein Q(x)Q(x) is the right tailed function.

The proof can be found in the supplementary meterial. We also compare the performance of agile BNP-HMM, Viterbi algorithm and Maximum A Posterior (MAP) algorithm [36] to predict the membership of each pulse and the lower bound of Theorem 2. The error probability for finite time on their outputs as:

Pet=i𝟙(s^isi,si=t)i𝟙(si=t)P_{e}^{t}=\frac{\sum_{i}\mathds{1}\left(\hat{s}_{i}\neq s_{i},s_{i}=t\right)}{\sum_{i}\mathds{1}\left(s_{i}=t\right)} (32)

Set the true pulses follow φtN(3,σt2)\varphi_{t}\sim N(3,\sigma_{t}^{2}), and the spurious pulses follow φsN(1.5,σs2)\varphi_{s}\sim N(1.5,\sigma_{s}^{2}), and let σt=σs=σ\sigma_{t}=\sigma_{s}=\sigma. We varied the standard deviation from 10310^{-3} to 10110^{-1} and the result is the average of 100 times Monte Carlo simulations. As shown in Fig. 5, the results indicate that the BNP-HMM is closer to the lower bound than the conventional Viterbi and the MAP algorithm.

Refer to caption
Figure 5: The error probabilities in the true pulse, obtained from the theoretical lower bound and the BNP-HMM, Viterbi, and MAP algorithms, were compared.

IV Simulated Performance on Radar Data

Simulations of the PE task and the CPD task are conducted using PRI-defined sequences to examine the effectiveness and robustness of the proposed method. The datasets and evaluation metrics are described in Section IV-A, and simulation results and detailed discussions are presented in Section IV-B to Section IV-C.

IV-A Simulation Design

IV-A1 Simulation Settings

Simulation datasets included PRI sequences with multiple segments generated by the G-HMM described in Section III. Given the modulation type, the transition matrix of the single Work Mode (WM) is randomly sampled, and corresponding parameters are sampled based on the G-HMM sufficient statistics. The modulation types and parameters of each simulation category are given in Table II. Square brackets contain modulation parameters. The three elements in the parentheses of sliding PRI and D&S PRI indicate the minimum and maximum values for sliding PRI, as well as the number of PRI levels within a period. The number of one PRI level of D&S PRI is randomly sampled from 5 to 10. Jittered PRI is represented by parentheses indicating its mean value and variance. Considering the signal propagation error and the measurement error, additive Gaussian measuring noise with zero mean and variance 1 is added.

The first-category of the simulation explored the PE performance of agile BNP-HMM for different agile hyper-parameter κ\kappa values. Each pulse sequence contains pulses from one single work mode with 1000 pulses. The comparison of results and the discussions are given in Section IV-B.

The second and the third categories of simulation examine the CPD performance, including the detection accuracy and timing performance. Each pulse sequence sample contains four work modes, each of which lasts 150 pulses. The work mode change in the Same modulation Type and Variable modulation Parameters (STVP) (D2–D5), and Variable modulation Types and Variable modulation Parameters (VTVP) (D6) are simulated in the second and the third categories, respectively. The results of the STVP, VTVP and different parameter settings are presented in Section IV-C.

Non-ideal conditions are added in each datasets. A length NN pulse sequence with nn% non-ideal conditions is consisted with N×n/2%N\times n/2\% number of randomly generated spurious pulses and N×n/2%N\times n/2\% randomly generated missing pulses, respectively.

Input: initial-batch 𝑷0\boldsymbol{P}^{0}, sequentially arrived pulses {pt}m+1m+n\{p_{t}\}_{m+1}^{m+n}, threshold γp\gamma_{p}, acceptance threshold γu\gamma_{u}.
Output: change point index 𝒅\boldsymbol{d}
1 Initialize statistic of CPD task: Dp=0D_{p}=0;
2 Initialize indicator variable 𝒅\boldsymbol{d};
3 𝝅0,𝑨0,𝚯0\boldsymbol{\pi}^{0},\boldsymbol{A}^{0},\boldsymbol{\Theta}^{0} \leftarrow agile BNP-HMM(𝑷0\boldsymbol{P}^{0});
4 prior \leftarrow (𝝅0,𝑨0,𝚯0\boldsymbol{\pi}^{0},\boldsymbol{A}^{0},\boldsymbol{\Theta}^{0});
5 for tm+1t\leftarrow{m+1} to m+nm+n do
6       𝑷tconcatenate(𝑷t1,pt)\boldsymbol{P}^{t}\leftarrow concatenate(\boldsymbol{P}^{t-1},p_{t});
7       if prior is None then
8             𝝅0,𝑨0,𝚯0\boldsymbol{\pi}^{0},\boldsymbol{A}^{0},\boldsymbol{\Theta}^{0}\leftarrowagile BNP-HMM(𝑷t)(\boldsymbol{P}^{t});
9            
10      else
11             𝝅,𝑨,𝚯\boldsymbol{\pi},\boldsymbol{A},\boldsymbol{\Theta}\leftarrowagile BNP-HMM(𝑷t,prior(\boldsymbol{P}^{t},prior);
12            
13       end if
14      Delete the useless hidden states according to 𝔼[𝒂j]<γu\mathbb{E}[\boldsymbol{a}_{j}]<\gamma_{u};
15       Update the statistic DpD_{p} according to (26);
16      
17      if DpγpD_{p}\geq\gamma_{p} then
18             𝒅t1;priorNone\boldsymbol{d}_{t}\leftarrow 1;prior\leftarrow None;
19            
20      else
21             𝝅0,𝑨0,𝚯0𝝅,𝑨,𝚯;priorposterior\boldsymbol{\pi}^{0},\boldsymbol{A}^{0},\boldsymbol{\Theta}^{0}\leftarrow\boldsymbol{\pi},\boldsymbol{A},\boldsymbol{\Theta};prior\leftarrow posterior;
22            
23       end if
24      
25 end for
26return 𝒅\boldsymbol{d};
Algorithm 2 Change point detection based on the χ2\chi^{2}-CUSUM strategy and online Bayesian updating
TABLE II: Information on the Six Simulation Datasets
Simulation category Dataset Modulation type Modulation parameters (μs\mu s)
PE task D1 Agile WM = [100,110,120,130,140]
Staggered WM = [100,110,120,130,140]
Sliding WM = (100, 140, 5)
Jittered WM = (125,5)
D&S WM = (100, 140, 5)
CPD task (STVP) D2 Staggered WM1 = [100,110,115]
WM2 = [60,80,100,110]
WM3 = [70,75,88]
WM4 = [20,30,80]
D3 Sliding WM1 = (50, 110, 8)
WM2 = (50, 110, 6)
WM3 = (50, 80, 4)
WM4 = (50, 110, 3)
D4 Agile WM1 = [100,120,130]
WM2 = [60,80,100,110]
WM3 = [30,75,100]
WM4 = [50,60,70]
D5 Jittered WM1 = (100, 5)
WM2 = (150,5)
WM3 = (180,5)
WM4 = (200,5)
CPD task (VTVP) D6 Staggered WM1 = [100,120,130,150,160]
Sliding WM2 = (50, 150, 4)
Agile WM3 = [100,120,130,150,160]
Jittered WM4 = (125, 5)

IV-A2 Evaluation Metrics

The annotation error and Hamming distance are used to evaluate the parameter estimation performance.

Annotation Error ΔK\Delta K: The annotation error reflects the ability of the algorithm to estimate the hidden states number:

ΔK=K^K\Delta K=\hat{K}-K (33)

wherein K^\hat{K} and KK are the estimated and the true number of hidden states, respectively. “ΔK\Delta K close to zero” implied the algorithm achieved accurate estimations of hidden state numbers.

Hamming Distance: This metric indicates the ability to estimate an underlying state sequence, and the smaller its value is, the higher the estimation accuracy is. The Munkres algorithm [41] is used to map randomly selected indices of the estimated state sequence to the set of indices that maximized the overlap with the true sequence.

In the change point detection task, the performance is evaluated by following five metrics: F1 score, MDD, MT2FA, FAR, and MR.

F1 Score: The F1 score is given in [42], which reflects the detection accuracy.

F1=TPTP+0.5(FP+FN)F1=\frac{TP}{TP+0.5(FP+FN)} (34)

Mean Detection Delay (MDD) and Mean Time to False Alarm (MT2FA): The MDD and MT2FA are introduced by Lordon[35], and they are respectively expressed by (5) and (6).

False Alarm Rate (FAR) and Missing Rate (MR): False alarm rate and missing rate are two typical metrics that represent the probability of incorrect detection [43].

IV-A3 Baseline Methods

Four change point detection methods are used as baseline methods in this study:

  1. 1.

    Agile BNP-HMM-FSS is implemented with the combination of the proposed parameter estimation method (agile BNP-HMM) and the sequential change point strategy of χ2\chi^{2}-Fixed-Size-Sample (χ2\chi^{2}-FSS)[32]. The stopping time of χ2\chi^{2}-FSS is calculated by:

    N=inf{mj:dj=1};dj={1,if|χ(j1)m+1jm|h0,if|χ(j1)m+1jm|<hN=\inf\{mj:d_{j}=1\};\ d_{j}=\begin{cases}1,\ $if$~{}|\chi_{(j-1)m+1}^{jm}|\geq h\\ 0,\ $if$~{}|\chi_{(j-1)m+1}^{jm}|<h\end{cases} (35)

    wherein χ(j1)m+1jm\chi_{(j-1)m+1}^{jm} is given by (27), mm is the fixed-size and hh is the threshold.

  2. 2.

    U-FSS[44] has been used in our previous work on the MFR work mode online change point detection. It combines the generalized likelihood ratio test for the PE task and the original FSS algorithm[45] for the CPD task.

  3. 3.

    U-CUSUM is proposed in [44] to fulfill the requirements of the MFR work mode online change point detection task. It combines the generalized likelihood ratio test for the PE task and the original CUSUM algorithm[45] for the CPD task.

  4. 4.

    ChangeFinder is a unifying framework for detecting outliers and change points from time series [46]. It combines the auto-regressive model for the PE task and the logarithmic loss for the CPD task. It is used for the comparison under the non-ideal observations in this paper.

For the simplicity of representation, in the following, ABHC is short for Agile BNP-HMM-CUSUM, ABHF is short for Agile BNP-HMM-FSS, and CF is short for ChangeFinder.

IV-B Functional Validation of Parameter Estimation

Two functionality of the PE task are evaluated in this section. Metrics are computed on a per-dataset basis and averaged over 100 Monte Carlo simulations. The hyper-parameters of the original BNP-HMM in the simulations are as follows: απ=1,αA=1,a0=1,b0=0.01,ξ0=0\alpha_{\pi}=1,\alpha_{A}=1,a_{0}=1,b_{0}=0.01,\xi_{0}=0, and λ0=1\lambda_{0}=1. γu\gamma_{u} is set as 0.1 for all datasets. To isolate the effects of the agile hyper-parameter setting, the same architecture and prior distributions are used for the subsequent model. In the results, some metrics are equal to zero and for presentation purpose these zeros results are assigned a minor positive value (0.005 in this study). Note that in the subsequent representation, the agile hyper-parameter are normalized so that κ[0,1]\kappa\in[0,1].

IV-B1 Hidden State Number Estimation

The first simulation examines the influence of parameter κ\kappa settings for both agile and non-agile inter-pulse modulation types. Agile BNP-HMM with κ=0,0.5,1.0\kappa=0,0.5,1.0 is used for five modulation types on D1. The estimated results of the hidden state number under different κ\kappa settings are presented in Fig. 6. In the simulations, the BNP-HMM with hyper-parameter κ=0.5,1\kappa=0.5,1 outperform that with κ=0\kappa=0 on the agile inter-pulse modulation types. Noted that this study focuses on the parameter estimation for agile inter-pulse modulation types. In subsequently reported simulations, the agile BNP-HMM with κ=0.5\kappa=0.5 is used on agile inter-pulse modulation types, and that with κ=0\kappa=0 was used for comparison.

Refer to caption
Figure 6: ΔK\Delta K of each modulation type estimated by the agile BNP-HMM with different κ\kappa values.

The performance under the non-ideal observations is presented in Fig. 7 (a) and 7 (b). The agile BNP-HMM performs better with κ=0.5\kappa=0.5 than κ=0\kappa=0. The ΔK\Delta K is close to zero when κ=0.5\kappa=0.5 under various non-ideal settings. Note that in Fig. 7 (a), the agile BNP-HMM with κ=0\kappa=0 tends to underestimate the number of hidden states (the yy-axis denotes ΔK-\Delta K), meanwhile the presence of more non-ideal pulses provides a more accurate hidden states assignments (the ΔK\Delta K is close to zero when non-ideal ratio increase), which is the advantage of this method.

Refer to caption
Figure 7: ΔK\Delta K performance versus the non-ideal ratio. Agile BNP-HMM results for D1 at: (a) κ=0\kappa=0 and (b) κ=0.5\kappa=0.5.

To analyze the reason of the phenomena, the PE task results of the non-ideal ratio values of 1% and 10% are shown in Fig. 8. The hidden state labels inferred by the agile BNP-HMM are indicated by stars of different colors. The black stars represent ΔTOA\Delta TOA values caused by missing and spurious pulses. The blue lines indicate the temporal relationship between different real PRI values and ΔTOA\Delta TOA values. Theoretically, the original Dirichlet prior (κ=0)(\kappa=0) encourages hidden states to have similar transition distributions 𝔼[ajk|αA]\mathbb{E}[a_{jk}|\alpha_{A}]. A relatively high self-transition probability indicates that each PRI value belongs to a mutual hidden state, as shown in the left part of Fig. 8. However, as shown in the right part of Fig. 8, the difference between the ΔTOA\Delta TOA values and real PRI values are large, thus the ΔTOA\Delta TOA values could be easily identified as a new external hidden state with extremely low self-transition probability. Since outliers are randomly encountered and would violate the similar state transition assumption. When the detector encounters a ΔTOA\Delta TOA value, the algorithm are more likely to move to another hidden state or create a new hidden state. By accumulating the transition tendency, more hidden states will be created. In the middle part, the detail of estimated hidden states from a pulse segment under 1% and 10% non-ideal ratio are shown. Only one hidden state is inferred under 1% non-ideal ratio, and four hidden states are inferred under 10% non-ideal ratio.

Refer to caption
Figure 8: The PE task results for different non-ideal ratios at κ=0\kappa=0.

IV-B2 Underlying State Sequence Estimation Performance

The second category of simulation is performed to evaluate the results of temporal relationship prediction. The normalized Hamming distance is calculated for the three typical agile inter-pulse modulation types at different non-ideal ratios. As shown in Fig. 9 (a), with the increase in the non-ideal observation ratio, the agile BNP-HMM achieves better performance. The explanation is the same for the results in Fig. 8.

Refer to caption
Figure 9: Normalized Hamming distance with the non-ideal pulses in the scenario of agile modulation type. Agile BNP-HMM result for D1 at: (a) κ=0\kappa=0 and (b) κ=0.5\kappa=0.5

From Fig. 9 (a), the proposed model at κ=0.5\kappa=0.5 has a smaller normalized Hamming distance than the model at κ=0\kappa=0. There are two conclusions that can be drawn based on the results presented in Fig. 9 (b). Qualitatively, the agile BNP-HMM at κ=0.5\kappa=0.5 is robust to the non-ideal situation with the increase in the non-ideal ratio, and the normalized Hamming distance remains close to zero. The variance of agile PRI is larger than the other two modulation types. The hidden state transition distribution of agile PRI follows a uniform distribution, resulting in some miss-assignments. Quantitatively, the values of normalized Hamming distance are between 0.005 and 0.01, implying that out of 1,000 pulses in the dataset. Five to ten pulses are assigned to wrong hidden states. The normalized Hamming distance is getting lower with the increase in the non-ideal ratio.

Generally, we recommend setting the κ\kappa to 0.5 when estimating the parameter of agile MFRs, and setting κ\kappa to 0 when estimating the parameter of non-agile MFRs. In practical systems, we can not always obtain the ground truth to calculate ΔK\Delta K and Hamming distance, thus we propose to perform the PE task on two branches with κ\kappa values of 0.5 and 0. By calculating these branches in parallel, we can select the estimated value from the branch with the higher likelihood.

IV-C Change Point Detection Performance Evaluation

In change point detection tasks, datasets D2 to D6 are used for evaluation. In each simulation the initial-batch size was set to 20. The DPMM was initiated with the concentration parameter of α=1\alpha=1 and the same concentration parameter as that used in [39].

IV-C1 Basic Function Validation of Change Point Detection

This section evaluates the performance of the proposed method and baselines under the optimal parameter settings. The parameters of the change detector are optimized based on the F1 score. As shown in Table III, the proposed ABHC method generally outperforms other baseline methods.

TABLE III: Quality Metrics of Different Change Point Detection Methods on Radar Data; \uparrow Indicates Metrics We want to Maximize; \downarrow Indicates Metrics We want to Minimize; Best Values are Highlighted in Bold Font
Method MDD (samples)\downarrow FAR (%)\downarrow MR (%)\downarrow F1 \uparrow MT2FA (samples)\uparrow
Only Staggered PRI/D2
ABHC 1.02 0.02 0.04 0.96 \boldsymbol{\infty}
ABHF 10.05 0.01 0.07 0.96 80.0
CF 2.22 0.45 0.07 0.67 41.48
U-FSS 6.77 0.303 0.232 0.722 55.26
U-CUSUM 5.43 0.48 0.39 0.54 127.42
Only Sliding PRI/D3
ABHC 1.05 0.05 0.05 0.708 130.5
ABHF 15.92 0.05 0.27 0.86 \boldsymbol{\infty}
CF 3.35 0.71 0.53 0.31 114.83
U-FSS 6.34 0.50 0.31 0.55 21.19
U-CUSUM 8.22 0.4 0.2 0.67 113.77
Only Agile PRI/D4
ABHC 1.07 0.09 0.06 0.94 110.30
ABHF 12.71 0.14 0.29 0.79 104.10
CF 1.23 0.78 0.46 0.27 84.47
U-FSS 6.6 0.48 0.40 0.53 94.83
U-CUSUM 8.43 0.50 0.17 0.60 68.79
Only Jittered PRI/D5
ABHC 0.75 0.00 0.00 1.00 \boldsymbol{\infty}
ABHF 11.7 0.00 0.08 0.96 \boldsymbol{\infty}
CF 0.06 0.21 0.00 0.88 53.31
U-FSS 9.25 0.00 0.00 1.00 \boldsymbol{\infty}
U-CUSUM 1.57 0.00 0.00 1.00 \boldsymbol{\infty}
Mixed modulation type/D6
ABHC 1.94 0.02 0.02 0.96 \boldsymbol{\infty}
ABHF 20.31 0.04 0.22 0.88 72.35
CF 1.12 0.33 0.54 0.57 11.00
U-FSS 4.62 0.4 0.23 0.59 58.66
U-CUSUM 7.17 0.51 0.53 0.48 128.6

The results validate the robustness of the proposed framework. As discussed in Section IV-B, the agile BNP-HMM with κ=0.5\kappa=0.5 achieves slightly inferior results in estimating the true number of hidden states and hamming distance for non-agile inter-pulse modulation types (such as Jittered PRI). In the change point detection, either the ABHC or the ABHF has an superior performance. Although the agile BNP-HMM may not always accurately identify all hidden states, it can successfully abstract the time series dynamics of different radar work modes, thus the performance of the CPD task is not degraded facing the non-agile work mode.

In practical applications, we have considered two scenarios. In the first scenario, there are some pre-accumulated pulse sequences with change point information analyzed and recorded by experts. Due to the existence of electronic intelligence these datasets are generally available. In this scenario, the “optimal” parameters can be optimized by some pre-defined objectives, such as the F1 score. These parameters are then used for subsequent pulse sequences. In the second scenario, there is no available dataset like in the first scenario. For instance, the MFR is an unknown MFR or a known MFR with unknown or software defined signals. In this case the corresponding radar signals may not be recorded by interceptor. In this scenario, parameters are directly defined and used for all change point detection tasks.

IV-C2 Performance under Various Thresholds

In this section, a detection scatter plot, as shown in Fig. 10, is designed to present the trade-off between MDD and MT2FA by tuning the change detector parameters. The xx-axis represents the MT2FA, and the yy-axis denotes the MDD. The feature of a scatter can be represented by a tuple (𝒯,𝒮)(\mathcal{T},\mathcal{S}), wherein 𝒯\mathcal{T} and 𝒮\mathcal{S} represent the transparency and the size of a scatter, respectively. Since U-FSS and U-CUSUM is lack of interpretation, they are not simulated in the subsequent simulations. Fig. 10 illustrates the influence of the thresholds selection on the quality metrics of the change point detection approaches. The parameters and their mapping on tuples were defined:

(𝒯,𝒮)={(r,k),ifChangeFinder(m,h),ifagile BNP-HMM-FSS(None,γp),ifagile BNP-HMM-CUSUM(\mathcal{T},\mathcal{S})=\begin{cases}(r,k),&$if$\ \rm$ChangeFinder$\\ (m,h),&$if$\ \rm$agile\ BNP-HMM-FSS$\\ (None,\gamma_{p}),&$if$\ \rm$agile\ BNP-HMM-CUSUM$\end{cases} (36)

wherein (r,k)(r,k) represents the decay and lagging factors of the CF; (m,h)(m,h) is the fixed-size and the threshold of the ABHF; and γp\gamma_{p} represents the threshold of the ABHC. We first define the parameter range (𝒯min,𝒯max),(𝒮min,𝒮max)(\mathcal{T}_{min},\mathcal{T}_{max}),(\mathcal{S}_{min},\mathcal{S}_{max}). The candidate parameters are generated using equidistant sampling.

Refer to caption
(a) D2
Refer to caption
(b) D3
Refer to caption
(c) D4
Refer to caption
(d) D5
Refer to caption
(e) D6
Figure 10: The MT2FA versus MDD detection scatter of the change point detection methods on different datasets: (a) D2; (b) D3; (c) D4; (d) D5; (e) D6. For the simplicity of representation, the case without any false alarm was assigned as MT2FA = 150. However, the maximum value of MT2FA was not 150.

From the perspective of the scatter location, the major scatters of CF (green) are located at the bottom left of every sub-figure of Fig. 10, which implies a high false alarm rate. Meanwhile, most scatters of the ABHC framework (red) are located at the bottom right of the each sub-figure of Fig. 10, which demonstrates better timing performances. As for the ABHF framework, the specific design of the parameter estimation task ensures better performance at MT2FA. In some cases (see Fig. 10 (a), 10 (b), and 10 (d)), the MT2FA value reaches 150, which indicated the zero false alarm rate on these data samples. The FSS strategy uses the data window for data points accumulation and decides whether there is a change point at the end of the data window (see (35)), resulting in longer detection delays. The CUSUM strategy makes decisions for each incoming data point (see (25)), resulting in smaller detection delay.

From the perspective of parameter settings, the ABHC framework is more suitable for practical applications than the baseline methods. As shown in Fig. 10 (e), the CF reconstructs the data via Auto-Regressive (AR) model, which is commonly used for modeling the stationary time series, causing the un-interpretable pattern for agile inter-pulse modulation. For ABHF, the scatters can be divided into five groups in terms of MDD as five mm were set in the simulations, reflecting the trade-off between the MDD and MT2FA. The transparency of each group from the bottom to the top decreased. The higher the fixed-size mm was set, the higher MT2FA and MDD were, achieving a trade-off between them. The size of each scatter increases in terms of the MT2FA value, indicating that a higher threshold hh would result in a higher MT2FA value. For ABHC framework, there is only one threshold parameter to be tuned, and the MT2FA increases (the false alarm rate decreased) with the scatter size increases (i.e., by setting a higher threshold). Varying the parameters would result in a stable MDD at a relatively low level, and the concentration of the ABHC scatters are much higher than in other methods.

V Experimental Performance on real-life Data

The proposed method has the potential to other problems of detecting change points in highly structured time series, especially for the case wherein the pre- and post-change distribution can be well modeled by state space models. We evaluate the performance of our method on other two real-life signal processing benchmark datasets described below:
HASC-2011: It is a dataset of HASC challenge 2011 dataset [47]. It monitors human activity data via three-axis accelerometers. Six activities carried out are staying, walking, jogging, skipping, taking stairs up, and taking stairs down. The three-dimensional data was converted to one-dimensional data via l2l^{2} norm, and then we quantify the sampled data so that the time series has discrete and finite values. Human activity recognition data is commonly used in CPD literature [48].
Well log: It is a dataset of nuclear magnetic resonance measurements taken from a drill while drilling a well [49]. It can be seen as a mean-shift Gaussian with outliers time series since the change in the rock stratification will produce the change in the mean of a time series. Change point detection algorithms applied to this dataset include [48, 50].

The experimental results of the real-life benchmark data can be found in Table IV. In HASC-2011, the ABHC method can capture the temporal feature of each motion and achieves the best FAR and MDR while maintaining the highest F1 score. The results of U-FSS, U-CUSUM, and CF methods are relatively poor because the change point detection method is not designed for time-varying series. The pre- and post-change distribution in well log dataset, can be modeled as a mean-shifted Gaussian time series with outliers. The ABHC method achieves better performance than the ABHF method on F1 score, as ABHC can learn the pattern from the beginning of the time series. The ABHF only learns from partial data (the data window). The U-FSS and U-CUSUM algorithm is sensitive to outliers and achieves worse results. The CF method also achieves better results as it can detect outliers and change point at the same time.

TABLE IV: Quality metrics of different Change point detection methods on Real-life Data. \uparrow Indicates Metrics We want to Maximize; \downarrow Indicates Metrics We want to Minimize; Best Values are Highlighted in Bold Font
Method MDD (samples)\downarrow FAR (%)\downarrow MR (%)\downarrow F1 \uparrow MT2FA (samples)\uparrow
HASC-2011
ABHC 88 0.38 0.08 0.70 \boldsymbol{\infty}
ABHF 102 0.61 0.17 0.53 30
CF 45 0.93 0.23 0.12 25.64
U-FSS 51 0.8 0.83 0.125 85.26
U-CUSUM 5.43 0.93 0.01 0.47 49.6
Well log
ABHC 100 0.2 0.0 0.94 \boldsymbol{\infty}
ABHF 130 0.3 0.17 0.6 \boldsymbol{\infty}
CF 64 0.0 0.08 0.9 114.83
U-FSS 126 0.9 0.25 0.55 126
U-CUSUM 176 0.0 0.1 0.85 150

VI Conclusion

In this paper, a novel Bayesian non-parametric parameter-based framework for parameter estimation and change point detection of MFR work modes is proposed. Firstly, a fully conjugate generative model is designed, which enables highly efficient variational inference. Secondly, the Dirichlet process with an agile feature is designed, and a stick-breaking construction is proposed to control the tendency of Markov Chain self-transitioning. Thirdly, the variational iteration function and the error probability lower bound of the PE task is derived. The proposed parameter estimation method is further combined with streaming Bayesian updating to reduce the computational redundancy. Finally, the optimal sequential strategy χ2\chi^{2}-CUSUM with agile BNP-HMM is designed for better change point detection performance.

The resulting framework do not require prior information, free of window setting dilemmas, easy to set parameters, and robust to non-ideal observations. Results showed that the proposed framework is highly competitive compared to other four methods on either simulated PRI datasets or real-life benchmark datasets.

There are some future works: 1) First-order Markov property is assumed in this study, which may limit the model representation ability; 2) The changes in either modulation type or parameters for modern MFR and cognitive radar is driven by higher level mission objectives. The results of our proposed method can support the inverse construction of the MFR and cognitive radars’ objective functions in the future.

Acknowledgments

The authors appreciate the editors and anonymous referees for their efforts and constructive comments to improve the quality of this paper.

References

  • [1] A. Wang and V. Krishnamurthy, “Signal interpretation of multifunction radars: Modeling and statistical signal processing with stochastic context free grammar,” IEEE Trans. Signal Process., vol. 56, no. 3, pp. 1106–1119, 2008.
  • [2] N. Visnevski, V. Krishnamurthy, A. Wang, and S. Haykin, “Syntactic modeling and signal processing of multifunction radars: A stochastic context-free grammar approach,” Proc. IEEE, vol. 95, no. 5, pp. 1000–1025, 2007.
  • [3] N. A. Visnevski, “Syntactic modeling of multi-function radars,” Ph.D. dissertation, 2005.
  • [4] K. Haigh and J. Andrusenko, Cognitive Electronic Warfare: An Artificial Intelligence Approach.   Artech House, 2021.
  • [5] R. Wiley, ELINT: The interception and analysis of radar signals.   Artech House, 2006.
  • [6] A. Wang and V. Krishnamurthy, “Threat estimation of multifunction radars: Modeling and statistical signal processing of stochastic context free grammars,” in IEEE Int. Conf. Acoust. Speech Signal Process., vol. 3, 2007, pp. III–793.
  • [7] I. Arasaratnam, S. Haykin, T. Kirubarajan, and F. A. Dilkes, “Tracking the mode of operation of multi-function radars,” in IEEE Conf. Radar., 2006, pp. 6–pp. –.
  • [8] S. Apfeld, A. Charlish, and G. Ascheid, “Modelling, Learning and Prediction of Complex Radar Emitter Behaviour,” in Proc. Int. Conf. Mach. Learn. App.   IEEE, 2019, pp. 305–310.
  • [9] Y. Li, M. Zhu, Y. Ma, and J. Yang, “Work modes recognition and boundary identification of mfr pulse sequences with a hierarchical seq2seq lstm,” IET Radar Sonar Navig., vol. 14, no. 9, pp. 1343–1353, 2020.
  • [10] Xueqiong, Li, Zhitao, Huang, Fenghua, Wang, Xiang, Wang, Tianrui, and Liu, “Toward Convolutional Neural Networks on Pulse Repetition Interval Modulation Recognition,” IEEE Commun. Lett., vol. 22, no. 11, pp. 2286–2289, 2018.
  • [11] Z. M. Liu and P. S. Yu, “Classification, Denoising, and Deinterleaving of Pulse Streams With Recurrent Neural Networks,” IEEE Trans. Aerosp. Electron. Syst., vol. 55, no. 4, pp. 1624–1639, 2019.
  • [12] T. Huang, Y. Liu, X. Xu, Y. C. Eldar, and X. Wang, “Analysis of Frequency Agile Radar via Compressed Sensing,” IEEE Trans. Signal Process., vol. 66, no. 23, pp. 6228–6240, 2018.
  • [13] Y. Li, T. Huang, X. Xu, Y. Liu, L. Wang, and Y. Eldar, “Phase Transitions in Frequency Agile Radar Using Compressed Sensing,” IEEE Trans. Signal Process., vol. 69, pp. 4801–4818, 2021.
  • [14] M. Zhu, Y. Li, and S. Wang, “Model-Based Time Series Clustering and Interpulse Modulation Parameter Estimation of Multifunction Radar Pulse Sequences,” IEEE Trans. Aerosp. Electron. Syst., vol. 57, no. 6, pp. 3673–3690, 2021.
  • [15] A. Tartakovsky, I. Nikiforov, and M. Basseville, Sequential analysis: Hypothesis testing and changepoint detection.   CRC press, 2014.
  • [16] M. Scherreik and B. Rigling, “Online Estimation of Radar Emitter Cardinality via Bayesian Nonparametric Clustering,” IEEE Trans. Aerosp. Electron. Syst., vol. 57, no. 6, pp. 3791–3800, 2021.
  • [17] G. Revillon, A. Mohammad-Djafari, and C. Enderli, “Radar emitters classification and clustering with a scale mixture of normal distributions,” IET Radar Sonar Navig., vol. 13, no. 1, pp. 128–138, 2019.
  • [18] N. Ding and Z. Ou, “Variational nonparametric Bayesian Hidden Markov Model,” in IEEE Int. Conf. Acoust. Speech Signal Process., 2010, pp. 2098–2101.
  • [19] Y. W. Teh, M. I. Jordan, M. J. Beal, and D. M. Blei, “Hierarchical Dirichlet Processes,” J. Am. Stat. Assoc., vol. 101, no. 476, pp. 1566–1581, 2006.
  • [20] M. Beal, Z. Ghahramani, and C. Rasmussen, “The Infinite Hidden Markov Model,” in Adv. Neural Inf. Process. Syst., vol. 14, 2001.
  • [21] E. B. Fox, E. B. Sudderth, M. I. Jordan, and A. S. Willsky, “A sticky HDP-HMM with application to speaker diarization,” Ann. Appl. Stat., pp. 1020–1056, 2011.
  • [22] L. Du, P. Wang, H. Liu, M. Pan, F. Chen, and Z. Bao, “Bayesian spatiotemporal multitask learning for radar hrrp target recognition,” IEEE Trans. Signal Process., vol. 59, no. 7, pp. 3182–3196, 2011.
  • [23] W. Chen, B. Chen, X. Peng, J. Liu, Y. Yang, H. Zhang, and H. Liu, “Tensor rnn with bayesian nonparametric mixture for radar hrrp modeling and target recognition,” IEEE Trans. Signal Process., vol. 69, pp. 1995–2009, 2021.
  • [24] E. B. Fox, M. C. Hughes, E. B. Sudderth, and M. I. Jordan, “Joint modeling of multiple time series via the beta process with application to motion capture segmentation,” Ann. Appl. Stat., vol. 8, no. 3, pp. 1281–1313, 2014.
  • [25] A. G. Tartakovsky, “Asymptotic Optimality of Mixture Rules for Detecting Changes in General Stochastic Models,” IEEE Trans. Inf. Theory, vol. 65, no. 3, pp. 1413–1429, 2019.
  • [26] C.-D. Fuh and A. G. Tartakovsky, “Asymptotic Bayesian Theory of Quickest Change Detection for Hidden Markov Models,” IEEE Trans. Inf. Theory, vol. 65, no. 1, pp. 511–529, 2019.
  • [27] C.-D. Fuh, “Asymptotically Optimal Change Point Detection for Composite Hypothesis in State Space Models,” IEEE Trans. Inf. Theory, vol. 67, no. 1, pp. 485–505, 2021.
  • [28] ——, “SPRT and CUSUM in hidden Markov models,” Ann. Stat., vol. 31, no. 3, 2003.
  • [29] C.-D. Fuh and Y. Mei, “Quickest Change Detection and Kullback-Leibler Divergence for Two-State Hidden Markov Models,” IEEE Trans. Signal Process., vol. 63, no. 18, pp. 4866–4878, 2015.
  • [30] J. Sethuraman, “A constructive definition of dirichlet priors,” Stat. Sinica, pp. 639–650, 1994.
  • [31] T. Broderick, N. Boyd, A. Wibisono, A. C. Wilson, and M. I. Jordan, “Streaming Variational Bayes,” in Adv. Neural Inf. Process. Syst., vol. 26, 2013.
  • [32] I. V. Nikiforov, “Quadratic tests for detection of abrupt changes in multivariate signals,” IEEE Trans. Signal Process., vol. 47, no. 9, pp. 2534–2538, 1999.
  • [33] D. Hallac, S. Vare, S. Boyd, and J. Leskovec, “Toeplitz inverse covariance-based clustering of multivariate time series data,” in ACM SIGKDD Int. Conf. Knowl. Discov. Data Min., 2017, pp. 215–223.
  • [34] M. Basseville, I. V. Nikiforov et al., Detection of abrupt changes: theory and application.   prentice Hall Englewood Cliffs, 1993, vol. 104.
  • [35] G. Lorden, “Procedures for Reacting to a Change in Distribution,” Ann. Appl. Stat., vol. 42, no. 6, pp. 1897–1908, 1971.
  • [36] C. M. Bishop, Pattern recognition and machine learning, ser. Information science and statistics.   New York: Springer, 2006.
  • [37] Z. Ghahramani and M. Jordan, “Factorial hidden markov models,” vol. 8, 1995.
  • [38] D. M. Blei, A. Kucukelbir, and J. D. McAuliffe, “Variational Inference: A Review for Statisticians,” J. Am. Stat. Assoc., vol. 112, no. 518, pp. 859–877, 2017.
  • [39] D. M. Blei and M. I. Jordan, “Variational inference for Dirichlet process mixtures,” Bayesian Anal., vol. 1, no. 1, pp. 121–143, 2006.
  • [40] J. Young, A. Høst-Madsen, and E.-M. Nosal, “Deinterleaving of mixtures of renewal processes,” IEEE Trans. Signal Process., vol. 67, no. 4, pp. 885–898, 2018.
  • [41] J. Munkres, “Algorithms for the assignment and transportation problems,” J. Soc. Ind. Appl. Math., vol. 5, no. 1, pp. 32–38, 1957.
  • [42] E. Romanenkova, A. Stepikin, M. Morozov, and A. Zaytsev, “InDiD: Instant Disorder Detection via Representation Learning,” arXiv, 2022.
  • [43] S. M. Kay, Fundamentals of statistical signal processing: estimation theory.   Prentice-Hall, Inc., 1993.
  • [44] J. Bao, Y. Li, M. Zhu, and W. Zhang, “Online Detection Method of Multi-Function Radar Work Mode Changepoints Non-ideal Observations,” Acta Electron. Sinica, vol. 50, no. 6, pp. 1291–1300, 2022.
  • [45] I. V. Nikiforov, “Two strategies in the problem of change detection and isolation,” IEEE Trans. Inf. Theory, vol. 43, no. 2, pp. 770–776, 1997.
  • [46] J.-i. Takeuchi and K. Yamanishi, “A unifying framework for detecting outliers and change points from time series,” IEEE Trans. Knowl. Data Eng., vol. 18, no. 4, pp. 482–492, 2006.
  • [47] N. Kawaguchi, Y. Yang, T. Yang, N. Ogawa, Y. Iwasaki, K. Kaji, T. Terada, K. Murao, S. Inoue, Y. Kawahara et al., “Hasc2011corpus: towards the common ground of human activity recognition,” in Int. Conf. Ubiquitous Comput., 2011, pp. 571–572.
  • [48] R. Giordano, R. Liu, M. I. Jordan, and T. Broderick, “Evaluating Sensitivity to the Stick-Breaking Prior in Bayesian Nonparametrics,” Bayesian Anal., vol. 18, no. 1, pp. 287–366, 2023.
  • [49] J. O. Ruanaidh, W. J. Fitzgerald, and K. J. Pope, “Recursive bayesian location of a discontinuity in time series,” in IEEE Int. Conf. Acoust. Speech Signal Process., vol. 4, 1994, pp. IV–513.
  • [50] J. Knoblauch, J. E. Jewson, and T. Damoulas, “Doubly robust bayesian inference for non-stationary streaming data with beta-divergences,” in Adv. Neural Inf. Process. Syst., vol. 31, 2018.