Transcript Quickest Detection and Its Applications

Quickest Detection and Its Allications
Zhu Han
Department of Electrical and Computer Engineering
University of Houston, Houston, TX, USA
Outline

Introduction
– Basics
– Markov stopping time

Quickest Detection
– Sequential detection
– Bayesian detection
– CUSUM test

Applications
–
–
–
–
Cognitive radio network
Multiuser detection for memory
Medical applications
Smart grid

Conclusions
Classic Hypothesis Test

Probability Space (Ω, F, P)
– Ω is a set, a sample space
– F is a event
– P is the probability measure assign to the event

Detection: “Spot the Money”
Hypothesis Testing

Let the signal be y(t), model be h(t)
Hypothesis testing:
H0: y(t) = n(t)
(no signal)
H1: y(t) = h(t) + n(t) (signal)

The optimal decision is given by the Likelihood ratio test
(Nieman-Pearson Theorem), g is a threshold.
Select H1 if L(y) = log(P(y|H1)/P(y|H0)) > g;
otherwise select H0.
Signal detection paradigm
Receiver operating characteristic (ROC) curve
Tradeoff between false alarm and detection probability
Basics of Quickest Detection


A technique to detect distribution changes of a sequence of
observations as quick as possible with the constraint of
false alarm or detection probability.
Classification
1.
2.
3.

Sequential detection: determine asap between two known
distributions, starting from time 0.
Bayesian detection: at random time (known distribution),
distribution changes between two known distribution.
CUSUM test: at random time (unknown distribution),
distribution changes to known/unknown distribution.
Applications
1.
2.
3.
4.
Cognitive Radio: Primary user reappear
Multiuser Detection: Memory
Network Monitoring:
Medical Device: Fall or not
Markov Stopping Time

For Markov process: memoriless property

likelihood of a given future state, at any given moment,
depends only on its present state, and not on any past states

Random variable YT: a reward that can be claimed at time T
Optimal stopping time that maximizes the reward

S is finite or infinite.
For finite time S case




backward induction
dynamic programming for Markov Case
For infinite time S case

Define

Stopping time
Outline

Introduction
– Basics
– Markov stopping time

Quickest Detection
– Sequential detection
– Bayesian detection
– CUSUM test

Applications
–
–
–
–
Cognitive radio network
Multiuser detection for memory
Medical applications
Smart grid

Conclusions
Sequential Detection

How to reach a decision between two hypotheses after minimal
average trails?

A real sample sequence, {Zk;K=1,2…} that obey one of two
hypotheses:

Stop the observation as soon as the decision is made
Trade off between probability of error and decision time. More
accurate, more decision time. Quicker decision, less accurate


A sequential decision rule (s.d.r.) as the pair (T,δ), in which T
declares the time to stop sampling and then δ takes the value 0
or 1 declaring which one of H1 , H0
Performance indices of interest

Average cost of errors
– False Alarm
– Missing Probability
– Average cost of errors,  is the probability of event
– c0 and c1 are constants to balance the tradeoff
The cost of sampling
 s.d.r. to solve the optimization problem

Equivalent Rule
Optimal Detection Rule

We can rewrite the problem

Optimal stopping time

Optimal cost
S() and thresholds

An illustration of s(π)

The thresholds are found from s(π)
– One is for false alarm
– The other is for missing prob.
Sequential probability ratio test
Sequential probability ratio test (SPRT) with boundaries
A and B : (SPRT(A, B))
– It exhibit minimal expected stopping time among all
s.d.r.’s having given error probability.
– The stopping time T is equivalently be written as

Example

At the 1st exit of ∧k from (A,B), decides H1 if the exit is to
the right of this interval and H0 if the exit is to the left.
Outline

Introduction
– Basics
– Markov stopping time

Quickest Detection
– Sequential detection
– Bayesian detection
– CUSUM test

Applications
–
–
–
–
Cognitive radio network
Multiuser detection for memory
Medical applications
Smart grid

Conclusions
Baysesian quickest detection





The distribution changes with unknown time (but known
distribution for the changing time). The objective of
observer is to detect such a random change, if one occurs,
as quickly as possible.
The difference from the sequential detection
The design of quickest detection procedures involves the
optimization of a tradeoff between two types of
performance indices: detection delay vs. false alarm.
For example, network from WIFI to Bluetooth
Approaches



Shiryaev’s problem for Bayesian quickest detection
Bojdecki’s quickest detection problem and other constraints
Ritov’s quickest detection problem: Game theory approach
Shiryaev’s problem
for Bayesian quickest detection

Random sequence, {Zk ; k=1,2,…} suppose there is a
change point, t, such that given {Z1 , Z2…, Zt-1} with
marginal distribution Q0 , and {Zt , Zt+1…, ZT} with
marginal distribution Q1

Two performance indices
– The expected detection delay:
– The false alarm probability:

The determination of optimal stopping time, T,
– It was a first posted by Shiryaev. It considers
– C>0, is a constant controlling the balance between 2
indices.
Geometric distribution assumption

To find the optimal stopping time, it need to assume a
specific prior distribution for the change pint, t,
– π and ρ are the constant lying in the interval (0,1)
– π, probability that a change already occurred when
the sequence observation start.
– ρ, the conditional probability that the sequence will
transition to the post-change state at any time, given
that it has not done so prior to that time
Optimal Solution
Example


How to find optimal threshold
Detection vs. time example
Other penalty functions

The penalty parameters act like an optimal constraints (i.e.
penalize combination of false alarms and detection delay)
but the solutions ideally converge to the solution or the
original one.
1. an example is a delay penalty of polynomial type (T-t)p for fixed p>0
2. The exponential penalty. (replace P(T<t) with P(T<t-ε) for fixed ε >0)
3. A alterative delay penalty
Bojdecki’s problem

A different approach to detecting the change point t within
Bayesian framework by maximizing the probability of
selected the right estimator for t based on the observation.

B is an approx. measurable set and XT depends the observed
Zk . If T* is existed, will be called optimal.

Let if maximizing the probability of stopping within m
units of the change point t.

Omit other details
A game theoretic formulation


An alternative approach: Ritov’s gametheoretic quickest detection problem
A game consists two player.
– Player#1: “the statistician” is attempting to quickly
detect a random change point as in the preceding
section
– Player#2: “nature” is attempting to choose the
distribution of the change point and foil the
Player#1.
– Given the probability of the change point
Is allowed to be a function of the past observation
{Z1~Zk-1}, which is selected by “nature”.
Outline

Introduction
– Basics
– Markov stopping time

Quickest Detection
– Sequential detection
– Bayesian detection
– CUSUM test

Applications
–
–
–
–
Cognitive radio network
Multiuser detection for memory
Medical applications
Smart grid

Conclusions
Non-Bayesian quickest detection

Previously, Shiryaev’s problem for Bayesian quickest
detection assumed the change point t, which is a random
variable with given, prior distribution.
– How to solve if the system has no pre-existing
statistical model for occurrence of event, like in
surveillance or inspection system?

Lorden’s problem for non-Bayesian quickest detection
– Problem definition
– Page’s CUSUM test
– Performance of Page’s test

Asymptotic results
– Lorden’s approach

The false-alarm constraints
Lorden’s problem

The detection delay is penalized by its worst case
value :
– Where d(T) is the worst case delay, and dt (T) is the
average delay under Pt
Constraint and Problem Formulation

The rate of false alarms can be quantified by the
mean time between false alarms

The design criterion is then given by:
– is positive, finite constant, and is the stopping time for
minimizing the worst-case delay within lower-bound
constraint in the mean time between the false alarms.
Cusum test (Page, 1966)
Likelihood of composite hypothesis Hn against H 0 :
Hv: sequence has
density f0 before v, and f1 after
max 0£ k£ n (Sn - Sk ) = Sn - min 0£ k£ n Sk ,
where
H0: sequence is
stochastically homogeneous
k
f (x )
S0 = 0; Sk = å log 1 j
f 0 (x j )
j=1
Stopping rule :
N = min{n ³ 1: gn = Sn - min 0£ k£ n Sk ³ b}
gn
for some threshold b
gn can be written in recurrent form
g0 = 0;gn = max(0,gn-1 + log
f1 (x n )
)
f 0 (x n )
This test minimizes the worst-average
detection delay (in an asymptotic sense)
b
Stopping time N
Outline

Introduction
– Basics
– Markov stopping time

Quickest Detection
– Sequential detection
– Bayesian detection
– CUSUM test

Applications
–
–
–
–
Cognitive radio network
Multiuser detection for memory
Medical applications
Smart grid

Conclusions
Example: Cognitive Radio
Lane reserved
for military
Licensed
Spectrum
Or
Primary
Users
Public Traffic
Lane congested!
Unlicensed
Spectrum
Or
Secondary Users
Treated as
Harmful
Interference
Spectrum Sensing

Secondary users must sense the spectrum to
– Detect the presence of the primary user for reducing interference on
primary user
– Detect spectrum holes to be used for transmission

Spectrum sensing is to make a decision between two
hypotheses
– The primary user is present, hypothesis H0
– The primary user is absent, hypothesis H1

Quickest detection for spectrum sensing
– A distribution change in frequency domain is detected in
observations to quit from or join into the licensed frequency band
– There exist unknown parameters after the primary radio emerges
Collaborative Spectrum Sensing

Collaborative spectrum sensing
3- Fusion Center makes
final decision: PU present
or not
Secondary User
Common Secondary
Fusion Center
Primary User
(Licensed user)
2- the SUs send their
Local Sensing bits to a
common fusion center
Secondary User
Secondary User
Secondary User
1- the SUs perform Local
Sensing of PU signal
Collaborative Quickest Spectrum Sensing

The collaborative quickest spectrum sensing without
communication coordination
– An node made own broadcast decision
– The random time-slot selection
– The limited time slots for the secondary users to exchange
information

The key issue is to determine
whether to broadcast based on the
current observation and the local
population of secondary user.
– A threshold broadcast scheme
is proposed
Medical Applications

Patient falling



CUSUM test




Quickest detection to detect as soon as possible to prevent or
report
False alarm limitation
No prior information
How to train the threshold
Need real data
Computation



Bluetooth between sensor and google phone Android
Computation in Android using JAVA
Communication through 3G or WIFI for reporting
Outline

Introduction
– Basics
– Markov stopping time

Quickest Detection
– Sequential detection
– Bayesian detection
– CUSUM test

Applications
–
–
–
–
Cognitive radio network
Multiuser detection for memory
Medical applications
Smart grid

Conclusions
Power System State Estimation Model

Transmitted active power from bus i to bus j
– High reactance over resistance ratio
– Linear approximation for small variance
– State vector
, measure noise e with covariance Ʃe
– Actual power flow measurement for m active power-flow branches
– Define the Jacobian matrix
– We have the linear approximation
– H is known to the power system but not known to the attackers
State Estimation (SE)
•
•
•
z=Hx+e, for n power lines and m measurement, m<n
H: Jacobean Matrix (n×n)
x: State variable (n×1)
z: Measurements (m×1), m<n
e: noise vector (n×1)
Goal of system is to estimate x from z
SE is a key function in building real-time models of
electricity networks in Energy Management Centers (EMC)
Real-time models of the network can be used by
Independent System Operator (ISO) to make optimal
decisions with respect to technical constraints (such as
transmission line congestion, voltage and transient stability)
Bad Data Injection and Detection

Inject Bad data c: z=Hx+c+e

Bad data detection
– Residual vector
– Without attacker
where
– Bad data detection (with threshold )
without attacker:
with attacker:

otherwise
Stealth (unobservable) attack
– Hypothesis test would fail in detecting the attacker, since the
control center believes that the true state is x + x.
QD System Model

Assuming Bayesian framework:
– the state variables are random with

The binary hypothesis test:

The distribution of measurement z under binary hyp: (differ
only in mean)

We want a detector
– False alarm and detection probabilities
Detection Model - NonBayesian

Requiring a non-Bayesian approach due to unknown
prior probability, attacker statistic model

The unknown parameter exists in the post-change
distribution and may changes over the detection
process.
– You do not know how attacker attacks.

Minimizing the worst-case effect via detection delay:
Detection
delay

Detection
time
Actual time of
active attack
We want to detect the intruder as soon as possible
while maintaining PD.
Multi-thread CUSUM Algorithm

CUSUM Statistic:
How about the
unknown?
where Likelihood ratio term of m measurements:

By recursion, CUSUM Statistic St at time t:

Average run length (ARL) for declaring the attack:
Declare the attacker is existing!
Otherwise, continuous to the process.
Linear Solver for the Unknown

Rao test – asymptotically equivalent model of GLRT:

The linear unknown solver for m measurements:
– Omitting the necessity of [J-1]
– Simplifying Quadratic form

solo-parameter envir.
the unknown > 0
Recursive CUSUM Statistic w/ linear unknown
parameter
The unknown
is nosolve:
long
involved
Simulation: Adaptive CUSUM algorithm

2 different detection tests: FAR: 1% and 0.1%

Active attack starts at time 6

Detection of attack at time 7 and 8, for different FARs
Conclusion



Different from the other detection techniques that minimize
error, quickest detection minimizes the decision time.
Trade off between decision time and error probability (false
alarm and error probabilities)
Depending on the different scenarios




Sequential detection
Bayesian detection
Non-Bayesian detection
Applications




Wireless network
Medical applications
Smart grid
Other applications?
Questions?