Xem mẫu
- Adaptive Filtering and Change Detection
Fredrik Gustafsson
Copyright © 2000 John Wiley & Sons, Ltd
ISBNs: 0-471-49287-6 (Hardback); 0-470-84161-3 (Electronic)
Part I: Introduction
- Adaptive Filtering and Change Detection
Fredrik Gustafsson
Copyright © 2000 John Wiley & Sons, Ltd
ISBNs: 0-471-49287-6 (Hardback); 0-470-84161-3 (Electronic)
Extended summary
1.1. About the book ....................... 3
1.1.1. Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2. Aim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.3. Background knowledge .................... 6
1.1.4. Outline reading
and advice ................. 7
1.2. Adaptive linearfiltering .................. 8
1.2.1. Signal
estimation ....................... 9
1.2.2. Parameter estimation using adaptive filtering . . . . . . . 11
1.2.3. State estimation using
Kalman filtering . . . . . . . . . . 13
1.3. Change detection ...................... 17
1.3.1. Filters residual
as generators ................ 17
1.3.2. Stoppingrules ........................ 18
1.3.3. One-model approach ..................... 19
1.3.4. Two-model approach ..................... 22
1.3.5. Multi-model approach .................... 23
1.4. Evaluation and formal design ............... 26
1.4.1. Generalconsiderations . . . . . . . . . . . . . . . . . . . . 26
1.4.2. Performance measures .................... 28
1.1. Aboutthebook
1.1.1. Outlook
The areas of adaptive filtering and change (fault) detection are quite active
fields. both in research and applications . Some central keywords of the book
are listed in Table 1.1, and the figures. illustrated in Figure 1.1, give an idea
of the relative activity in the different areas . For comparison. the two related
and well established areas of adaptive control and system identification are
included in the table . Such a search gives a quick idea of the size of the
areas. but there are of course many shortcomings. and the comparison may
be unfair at several instances . Still. it is interesting to see that the theory
has reached many successful applications. whichis directly reflected in the
- 4 Extended summary
Table 1.1. Keywords andnumber of hits (March 2000) in different databases. For Sci-
enceDirect the maximum numberof hits is limited to 2000. On some of the rows, the logical
‘or’ is used for related keywords like ‘adaptive signal processing or adaptive estimation or
adaptive filter’.
Keyword IEL ScienceDirect IBM patent
Adaptive filter/estimation/SP 4661 952 871
Kalman filter 1921 1642 317
Adaptive equalizer (Eq) 479 74 291
Target tracking 890 124 402
Fault diagnosis (FDI) 2413 417 74
Adaptive control (AC) 4563 2000 666
(System) Identification (SI) 8894 2000 317
Total number of items 588683 856692 2582588
I EL ScienceDirect IBM patents
Kalman Kalman
AC AC
Figure 1. l . Relative frequency of keywords in different databases.
number of patents. Browsing the titles also indicates that many journal and
conference publications concern applications. Figure 1.2 reveals the, perhaps
well known, fact that thecommunication industry is more keen to hold patents
(here: equalization). Algorithms aimed at real-time implementation are also,
of course, more often subject to patents, compared to, for instance, system
identification, which is a part of the design process.
Table 1.2 lists a few books in these areas. It is not meant to be compre-
hensive, only to show a few important monographs in the respective areas.
1.1.2. Aim
The aim of the book is to provide theory, algorithms and applications adap-
of
tive filters with or without support from change detection algorithms. Appli-
cations in these areas can be divided into the the following categories:
- 1. l About the book 5
Patents per publication
SI
Adaptive AC
Figure 1.2. Relative ratio of number of patents found in the IBM database compared to
publications in IEL for different keywords.
Table 1.2. Related books.
Keyword Books
Adaptive filters Haykin (1996), Mulgrew and Cowan (1988), Widrow and
Stearns (1985), Cowan and Grant (1985)
Kalman filter Kailath et al. (1998), Minkler and Minkler (1990), Anderson
and Moore (1979), Brown and Hwang (1997), Chui and Chen
(1987)7
Adaptive equalizer Proakis (1995), Haykin (1994), Gardner (1993), Mulgrew and
Cowan (1988)
Target tracking Bar-Shalom and Fortmann (1988), Bar-Shalom and Li (1993),
Blackman (1986)
Fault diagnosis Basseville and Nikiforov (1993), Gertler (1998), Chen and
Patton (1999), Mangoubi (1998)
Adaptive control Wstrom and Wittenmark (1989), Goodwin and Sin (1984)
System identification Ljung (1999), Soderstrom and Stoica (1989), Johansson (1993)
0 Surveillance and parameter tracking. Classical surveillanceproblems
consist in filteringnoisy measurements of physical variables asflows, tem-
peratures, pressures etc, which will be called signal estimation. Model-
based approaches, where (time-varying) parameters in a model of a non-
stationary signal need to be estimated, is a problem of parameter track-
ing. Adaptive control belongs tothisarea.Anotherexample is blind
equalization in digital communication.
0 State estimation. The Kalman filter provides the best linear state es-
timate, and change detection support can be used to speed up the re-
- 6 Extended summary
sponse after disturbances and abrupt state changes. Feedback control
using state feedback, such as Linear Quadratic Gaussian LQG control,
belongs to this area. Navigation and target tracking are two particular
application examples.
0 Fault detection. Faults can occur in almost all systems. Change detec-
tion here has the role of locating the fault occurrence intime and togive
a quick alarm. After the alarm, isolation is often needed to locate the
faulty component. The combined task of detection and isolation is com-
monly referred to as diagnosis. Fault detection can be recast to one of
parameter or state estimation. Faults in actuators and sensors are most
easily detected in a state space context, while system dynamic changes
often require parametric models.
These problems are usually treated separately in literature in the areas of sig-
nal processing,mathematical statistics, automatic control, communication sys-
tems and quality control. However, the tools for solving these problems have
much in common, and the same type of algorithms can be used (C.R. John-
son, 1995). The close links between these areas are clearly under-estimated in
literature.
The main difference of the problem areas above lies in the evaluation cri-
teria. In surveillance the parameter estimate should be as close as possible
to the true value, while in fault detection it is essential to get an alarm from
the change detector as soon as possible after the fault, and at the same time
generating few false alarms. In fault detection, isolation of the fault is also a
main task. The combination of fault detection and isolation is often abbre-
viated to FDI, and the combined task can be referred to as diagnosis. More
terminology used in this area is found in Appendix B.
The design usually consists of the following steps:
1. Modeling the signal or system.
2. Implementing an algorithm.
3. Tuning the algorithm with respect to certain evaluation criteria, either
using real or simulated data.
The main focus is on algorithms and their properties, implementation, tuning
and evaluation. Modeling is covered only briefly, but the numerous examples
should give an idea of the possibilities of model-based signal processing.
1.l .3. Background knowledge
The derivations and analysis can be divided into following areas, and some
the
prior knowledge, or at least orientation, of these is required:
- 1. l About the book 7
0 Statistical theory: maximum likelihood, conditional distributions etc.
0 Calculus: integrations, differentiations, equation solving etc.
0 Matrix algebra: projections, subspaces, matrix factorizations etc.
0 Signal modeling: transfer functions and state space models.
0 Classical filter theory: the use of a low-pass filter for signal conditioning,
poles and zeros etc. Transforms and frequency domain interpretations
occur, but are relatively rare.
To use the methods, it is essential to understand themodel and the statistical
approach. These are explained in each chapter in a section called ‘Basics’.
These sections should provide enough information for understanding and tun-
ing the algorithms. A deeper understanding requires the reader to go through
the calculus and matrix algebra in the derivations. The practitioner who is
mainly interested in what kind of problems can be addressed is advised to
start with the examples and applications sections.
1.l .4. Outline and reading advice
There are certain shortcuts to approaching the book, and advice on how to
read the book is appropriate. Chapter 1 is a summary and overview of the
book, while Chapter 2 overviews possible applications and reviews the ba-
sic mathematical signal models. These first two chapters should serve as an
overview of the field, suitable for those who want to know what can be done
rather than how it is done. Chapters 3, 5 and 8 - the first chapter in each
part are the core chapters of the book, where standard approaches to adap-
~
tive filtering are detailed. These can be used independently of the rest of the
material. The other chapters start with a section called ‘Basics’, which can
also be considered as essential knowledge. Part V is a somewhat abstract pre-
sentation of filter theory in general, without using explicit signal models. It is
advisable to check the content at an early stage, but the reader should in no
way spend too much time trying to digest all of the details. Instead, browse
through and return to the details later. However, the ideas should be familiar
before starting with the other parts. The material can be used as follows:
0 Chapters 1 and 2 are suitable for people from within industry who want
an orientation in what adaptive filtering is, and what change detection
can add to performance. An important goal is to understand what kind
of practical problems can be solved.
0 Chapters 5, 8 and 13 are suitablefor an undergraduatecourse in adaptive
filtering.
- 8 Extended summary
Table 1.3. Organization of the book chapters.
Estimation of
Approach Parameter
Signal
State
Adaptive filtering and whiteness based change Chapter 3 Chapter 5 Chapter 8
detection
Maximum likelihood based change detection Chapter 3 Chapter 6 Chapter 9
Multiple-model based change detection Chapter 4 Chapter 7 Chapter 10
Algebraic (parity space) change detection Chapter 11
0 Chapters 1, 2, 3, 5, 8, 12, 13 andthe ‘Basics’ sectionsin theother
chapters can be included in a graduate course on adaptive filtering with
orientation of change detection, while a more thorough course for stu-
dents specializing in the area would include the whole book.
This matrix organization is illustrated in Table 1.3. Part I1 on signal estima-
tion has many interesting signal processing applications, but it also serves as a
primer on the change detection chapters in Parts I11 and IV. The approach in
Chapter 11 is algebraic rather than statistical, and can be studied separately.
Appendix A overviews the signal models used in the book, and presents the
main notation, while Appendix B summarizes notation used in the literature
on fault detection. The only way in which the book should not be approached
is probably a reading from cover to cover. The theory in the last part is im-
portant to grasp at an early stage, and so are the basics in change detection.
Some of the parts on change detection will appear rather repetitive, since the
basic ideas are quite similar for signal, parameter and state estimation. More
specifically, Part I1 can be seen as a special case (or an illustrative first order
example) of Part 1 1 1.
1.2. Adaptive linearfiltering
Three conceptually different (although algorithmically similar) cases exist:
0 Signal estimation.
0 Parameter estimation in an unknown model.
0 State estimation in a known model.
The following sections will explain the basic ideas of theseproblems, and
introduce one central example to each of them that will be used throughout
the chapter.
- linear 1.2 AdaDtive 9
1.2.1. Signal
estimation
The basic signal estimation problem is to estimate the signal part Ot in the
noisy measurement yt in the model
An example of an adaptive algorithm is
Here At will be referred to as the forgetting fuctor. It is a design parameter
that affects the tracking speed of the algorithm. Aswill become clear from
the examples to follow, it is a trade-off between trackingspeed and noise
attenuation. The archetypical example is to use At = X, when this also has
the interpretation of the pole in a first order low-pass filter. More generally,
any(low-pass)filtercanbe used. If it is known that the signal level has
undergone an abrupt change, as might be indicated by a change detection
algorithm, then there is a possibility to momentarily forget all old information
by setting At = 0 once. This is an example of decision feedback in an adaptive
filter, which will play an important role in change detection. An illustrative
surveillance problem is given below.
Example 7.7 Fuelconsumption
The following application illustrates the use of change detection for im-
proving signal quality. The data consist of measurements of instantaneous
fuel consumption available from the electronic injection system ina Volvo 850
GLT used as a test car. The raw data are pulse lengths of a binary signal,
called t,, which is the control signal from the electronic injection system to
the cylinders. When t , = 1, fuel is injected with roughly constant flow, so the
length of the t , pulses is a measure of fuel consumption. The measured signal
contains a lot of measurement noise and needs some kind of filtering before
being displayed to the driver on the dashboard. Intuitively, the actual fuel
consumption cannot change arbitrarily fast, and the measured signal must be
smoothed by a filter. There are two requirements on the filter:
0 Good attenuation of noise is necessary to be able to tune theaccelerator
during cruising.
0 Goodtracking ability. Tests show that fuel consumption very often
changes abruptly, especially in city traffic.
- 10 Extended summary
25
- Measurement
Y I
- Slow filter
Time [S]
Figure 1.3. Measurements of fuel consumption and two candidate filters. Data collected by
the author in a collaboration with Volvo.
Theserequirements arecontradictory for standard linear filters. The thin
lines in Figure 1.3 show measurements of fuel consumption for a test in city
traffic. The solid lines show the result of (1.2) for two particular values of
the forgetting factor X. The fast filter follows the abrupt changes well, but
attenuates the noise unsatisfactorily, and it is the other way around for the
slow filter. The best compromise is probably somewhere in between these
filters.
The fundamental trade-off between speed and accuracy is inherent in all
linear filters. Change detectors provide a tool to design non-linear filters with
better performance for the type of abruptly changing signal in Figure 1.3.
Figure 1.4 shows the raw data, together witha filter implemented by Volvo
(not exactly the samefilter, but the principal functionality is the same). Volvo
uses a quite fast low-pass filter to get good tracking ability and then quantizes
the result to a multiple of 0.3 to attenuatesome of the noise. To avoid a rapidly
changing value in the monitor, they update the monitored estimate only once
a second. However, the quantization introduces a problem when trying to
minimize fuel consumption manually, and the response time to changes of one
second makes the feedback information to the driver less useful.
- linear 1.2 AdaDtive 11
25
- Measurement
20 - n - Volvo's filter
20 40 60 80 101
Time [S]
Figure 1.4. Measured fuel consumption and a filtered signal similar to Volvo's implemented
filter.
1.2.2. Parameter estimation using adaptive filtering
A quite general parametric model of a linear system is
Here G(q;0) and H ( q ;0) are two filters expressed in the delay operator q
defined by qut = u + . The parameters I9 in the model are assumed to be
tl
time-varying, and are to be estimated recursively. Here and in the sequel u
t
denotes measured inputs to the system, if available, and et is an unknown
input supposed to be modeled as a stochastic noise disturbance.
The generic form of an adaptive algorithm is
et,, = et + KtEt,
Et = Yt - !?to
The outputfrom the estimatedmodel is compared to thesystem, which defines
the residual E t . The adaptive filter acts as a system inverse, as depicted in
Figure 1.5. One common filterthat does this operation for linear in parameter
models is the recursive least squares (RLS) filter. Other well known filters are
Least Mean Square (LMS) (unnormalized or normalized), the Kalman filter
and least squares over sliding window. This book focuses on parametric models
that are linear in the parameters (notnecessarily linear in the measurements).
The reason for this is that the statistical approaches become optimal in this
case. How to obtain sub-optimal algorithms for the general linear filter model
will be discussed.
- 12 Extended summarv
Noise et o u t p u t yt Yt Et M et
W W W
Input ut System Parameter Bt ut Ad. filter 8 6 M Bt
W W
Figure 1.5. The interplay between the parameter estimator and the system.
Example 7.2 Frictionestimation
This example introduces a case study thatwill be studied inSection 5.10.3.
It has been noted (Dieckmann, 1992) that the dependence between the so-
called wheel slip and traction force is related to friction. The slip is defined as
the relative difference of a driven wheel’s circumferential velocity, w,r,, and
its absolute velocity, v:
,
wr, - v
,
S= 7
V,
where r, is the wheel radius. We also define the normalized traction force, p,
(sometimes referred to as the friction coefficient) as the ratio of traction force
( F f ) at the wheel and normal force ( N ) on one driven wheel,
p = - .f
F
N
Here p is computed from measurements, in this case a fuel injection signal,
via an engine model. In the sequel we will consider S and p as measurements.
Define the slip slope k as
The hypothesis is that k is related to friction, and theproblem is to adaptively
estimate it.
The goal is to derive a linear regression model, i.e. a model linear in the
parameters. The slip slope k we want to compute is defined in (1.7), which
for small p reads (including an offset term S)
p = k ( s - S),
where also S is unknown. Although this is a model linear in the parameters,
there are two good reasons for rewriting it as
1
s=p-+S.
k
- linear 1.2 AdaDtive 13
That is, we consider S to be a function of p rather than the otherway around.
The reasons are that S, contains more noise than pm, and that the parameter
S is varying much slower as compared to kS. Both these arguments facilitate
a successful filter design. Note that all quantities in the basic equation (1.9)
are dimensionless.
We will apply a filter where 1/k and S are estimated simultaneously. The
design goals are
0 to get accurate values on k while keeping the possibility to track slow
variations in both k and S, and at the same time
0 to detect abrupt changes in k rapidly.
This case study will be approached by a Kalman filter supplemented by a
change detection algorithm, detailed in Section 5.10.3.
A notationally simplified model that will be used is given by
where 154 = (Oil),
0i2))T is the parameter vector consisting of inverse slope
and the offset, u is the input to the model (the engine torque) and yt is the
t
measured output (the wheel slip).
An example of measurements of yt, ut from a test drive is shown in Figure
1.6(a). The car enters a low friction area at sample 200 where the slope pa-
rameter Oil)increases. Figure 1.6(b) shows a scatter plot of the measurements
together with a least squares fit of straight lines, accordingto the model 1.10,
to the measurements before and after a friction change.
Two adaptive filters were applied, one fast and one slow. Figure 1.7 il-
lustrates the basic limitations of linear filters: the slow filter gives a stable
estimate, but is too slow in tracking the friction change, while the fast filter
gives an output that is too noisy for monitoring purposes. Even the fast filter
has problem in tracking the friction change in this example. reason is poor
The
excitation, as can be seen in Figure 1.6(b). There is only a small variation in
u after the change (circles), compared to the first 200 samples. A thorough
t
discussion on this matter is found in Section 5.10.3.
1.2.3. State estimation using Kalman filtering
For state estimation, we essentially run a model in parallel with the system
and compute the residual as the difference. The model is specified in state
- 14 Extended summary
0.015 0.35
0.01 0.3
-
a
U1
0.005 - 80.25
e
o'2
'
0 O
; lA0 05 - 51 g
8 0.4
e
g 0.3-
S
e 0.2
B
E
0.1
4 0
0 50 150 100 200 250 300 350 "0 0.015
0.005 0.01 0.02
Time [samples] Slip
Figure 1.6. Measurements of yt and ut from a test drive going from dry asphalt to ice (a).
A scatter plot (b) reveals the straight line friction model. The data were collected by the
author in collaboration with Volvo.
0.05
True parameters
0.045 - - Estimated parameters, fast filter
- Estimated parameters, slow filter
0.04 - - -- - - - - - - - - - -
50 250 100
200 150 300
Time [samples]
Figure 1.7. Estimated slope and offset as a function of sample number.
space form:
(1.11)
Here yt is a measured signal, A, B , C,D are known matrices and xt is an un-
known vector (the state). There are three inputs to the system: the observable
(and controllable) ut, the non-observable process noise and the measurement
noise et.
- linear 1.2 AdaDtive 15
Noise e t , wt Output Y t
Yt Et M et
c c c
Input ut System State zt ut Kalman filter 5
% M zt
c c c
Figure 1.8. The interplay between the state estimator and the system.
In a statistical setting, state estimation is achieved via a Kalman $filter,
while inadeterministicsetting, where the noises are neglected, the same
device is called an observer. A generic form of a Kalman filter and an observer
is
(1.12)
where Kt is the filter gainspecifying the algorithm. The Kalmanfilter provides
the equations for mapping the model onto the gain as a function
The noise covariance matrices Q, R are generally considered to have some
degrees of freedom that act as the design parameters. Figure 1.8 illustrates
how the Kalman filter aims at ‘inverting’ the system.
Example 1.3 Target tracking
The typical application of target tracking is to estimate the position of air-
craft. A civil application is air traffic control (ATC) where the traffic surveil-
lance system at each airport wants to get the position and predicted positions
of all aircraft at a certaindistancefromtheairport.Thereareplenty of
military applications where, for several reasons, the position and predicted
position of hostile aircraft are crucial information. There are also a few other
applications where the target is not an aircraft.
As an illustration of Kalman filtering, consider the problemof target track-
ing where a radar measures range R and bearing 8 to an aircraft. The mea-
surements are shown in Figure 1.9 as circles. These are noisy and the purpose
of the Kalman filter is firstly to attenuate the noise and secondly to predict
future positions of the aircraft. This application is described in Section 8.12.2.
One possible model for these tracking applications is the following state
- 16 Extended summary
X 104 Initial filter design
104
3.5
3.5
3
3
2.5
2.5
2
2
> 1.5
1
0.5
0
-0.5
0 1 2 3 4 5 0 1 2 3 4 5
X X
X 104 104
(4
Figure 1.9. Radar measurements (a) and estimates from a Kalman filter (b) for an aircraft
in-flight manoeuvre.
space model
/l 0 T 0)
xt+T = 1 0 0 1 OIXttl T 0 IWt (1.14)
\o 0 0 1)
Yt = + et.
The state vector used here is X = ( ~ 1 ~ ~ 2 , 7 1 1 , 7 1 2 ) ~ ~ xi is the position
where
in 2D, zthe corresponding velocity. The state equation is one example of
i
l
a motion model describing the dynamics of the object to be tracked. More
examples are given in Chapter 8.
The measurements are transformedto this coordinate system andKalman
a
filter is applied. The resulting estimates are marked with stars. We can note
that the tracking is poor, and as will be demonstrated, thefilter can be better
tuned.
To summarize what has been said, conventional adaptive filters have the
following well-known shortcoming:
Fundamental limitation of linear adaptive filters
The adaptation gain in a linear adaptive filter is a compromise
between noise attenuation and tracking ability.
- 1.3 Change detection 17
1.3. Changedetection
Algorithmically, all proposed change detectorscanbeputinto one of the
following three categories:
0 Methods using one filter, where a whiteness test is applied to the resid-
uals from a linear filter.
0 Methods using two filters, one slow and one fast one, in parallel.
0 Methods using multiple filters in parallel, each one matched to certain
assumption on the abrupt changes.
In the following subsections, these will be briefly described. Let us note that
the computational complexity of the algorithm is proportional to how many
filters are used. Before reviewing these methods, we first need to define what
is meant by a residual in this context, and we also need a tool for deciding
whether a result is significant or not - a stopping rule.
1.3.1. Filtersasresidualgenerators
A good understanding of the Kalman and adaptivefilters requires a thorough
reading of Chapters 5 and 8. However, as a shortcut to understanding sta-
tistical change detection, we only need to know the following property, also
illustrated in Figure 1.10.
Residual generation
Under certain model assumptions, the Kalman and adaptive filters
take the measured signals and transform them to a sequence of
residuals that resemble white noise before the change occurs.
From a change detection point of view, it does not matter which filter we
use and the modeling phase can be seen as a standard task. The filters also
computes other statistics that are used by some change detectors, but more
on this later.
4 Filter
Figure 1.10. A whitening filter takes the observed input u and output yt and transforms
t
them to a sequence of residuals E t .
- 18 Extended summary
In aperfect world, the residuals would be zero before a changeand non-zero
afterwards. Since measurement noise and process disturbances are fundamen-
tal problems in the statistical approach to change detection, the actual value
of the residuals cannot be predicted. Instead, we have to rely on their average
behavior.
If there isno change in the system, and the model is correct, then the
residuals are so-called white noise, that is a sequence of independent stochastic
variables with zero mean and known variance.
After the change either the mean or variance or both changes, that is, the
residuals become ‘large’ in some sense. The main problem in statistical change
detection is to decide what ‘large’ is.
Chapter 11 reviews how state space models can be used for filtering (or
residual generation as it will be referred to in this context). The idea is to
find a set of residuals that is sensitive to the faults, such that a particular
fault will excite different combinations of the residuals. The main approach
taken in that chapter is based on parity spaces. The first step is to stack all
variables into vectors. The linear signal model can then be expressed as
where Yt is a vector of outputs, Ut is a vector of inputs, Dt the disturbances
and Ft the faults. The residual is then defined as a projection
With proper design of W , the residual will react to certain faults in specific
patters, making fault isolation possible. A simple example is when the mea-
surement is two-dimensional, and the state disturbance and the fault are both
scalar functions of time. Then, under certain conditions, it is possible to lin-
early transform the measurement to ~t = (dt, f t ) T . A projection that keeps
only the second component can now be used as the residual to detect faults,
and it is said that the disturbance is decoupled.
It should also be noted that the residual is not the only indicator of a
change (that is, it is not a sufficient statistic) inall cases. So even though
residual based change detection as outlined below is applicable in many cases,
there might be improved algorithms. The simplified presentation in this chap-
ter hides the fact that the multi-model approaches below actually use other
statistics, but the residual still plays a very important role.
1.3.2. Stopping rules
Many change detection algorithms, among these algorithms in the classes of
one-model and two-model approaches below, can be recast into the problem
- 1.3 Chanae detection 19
of deciding on the following two hypotheses:
H0 : E(st) = 0,
H1 :E(st) > 0.
A stopping rule is essentially achieved by low-pass filtering st and comparing
this value to a threshold. Below, two such low-pass filters are given:
0 The Cumulative SUM (CUSUM) test of Page (1954):
gt = max(gt-1 + st - v,0), alarm if gt > h.
The drift parameter U influences the low-pass effect, and the threshold h
(and also v ) influences the performance of the detector.
0 The Geometric Moving Average (GMA) test in Roberts (1959)
gt = Xgt-1 + (1- X)st, alarm if gt > h.
Here, the forgetting factor X is used to tune thelow-pass effect, and the
threshold h is used to tune the performance of the detector. Using no
forgetting at all (X = 0), corresponds to thresholding directly, which is
one option.
1.3.3. One-model approach
Statistical whiteness tests can be used to test if the residuals are white noise
as they should be if there is no change.
Figure 1.11 shows the basic structure, where the filter residuals are trans-
formed to a distance measure, that measures the deviation from the no-change
hypothesis. The stopping rule decides whether the deviation is significant or
not. The most natural distance measures are listed below:
0 Change in the mean. The residual itself is used in the stopping rule and
St = Et.
0 Change invariance. The squaredresidual subtracted by a known residual
variance X is used and st = E; - X.
Data
Yt,Ut
c Filter
Et
c Distance meas. -St
Stopping rule
Alarm
k,ta
c
Figure 1.11. Change detection based on a whiteness test from filter residuals.
- 20 Extended summary
0 Change in correlation. The correlation between the residual and past
outputs and/or inputs are used and st = Etyt-k or st = ~ t u t - k for some
k.
0 Change in sign correlation. For instance, one can use the fact that white
residuals should change sign every second sample in theaverage and use
st = sign(etet-l). A variant of this sign test is given in Section 4.5.3.
Example 7.4 Fuelconsumption
To improve on the filter in Example 1.1, the CUSUM test is applied to the
residuals of a slow filter, like that in Figure 1.3. For the design parameters
h = 5 and v = 0.5, the response in Figure 1.12 is obtained. The vertical lines
illustrate the alarm times of the CUSUM algorithm. The lower plot shows how
the test statistic exceeds the threshold level h at each alarm. The adaptive
filter in this example computes mean of the signal fromthe latest alarm to
the
the current time. With a bad tuning of the CUSUM algorithm, we get either
the total mean of the signal if there are no alarms at all, or we get the signal
back as the estimate if the CUSUM test gives an alarm at each time instant.
These are the two extreme points in the design. Note that nothing worse can
happen, so the stability of the filter is not an issue here. To avoid the first
situation where the estimate will converge to theoverall signal mean, a better
30
E
g 20
z
1
I
3 10
U
0
0 100 200 300 400 500
~~
Time [samples]
Figure 1.12. Response of an adaptive filter restarted each time a CUSUM test ( h = 5 ,
v = 0.5), fed with the filter residuals, gives an alarm. The lower plot shows the test statistic
of the CUSUM test.
- 1.3 Chanae detection 21
design is to use a slow adaptive filter of the type illustrated in Figure 1.3. To
avoid the second degenerate case, an alarm can trigger a fast filter instead of
a complete filter restart. That is, the algorithm alternates between slow and
fast forgetting instead of complete or no forgetting.
In contrast to the example above, the next example shows a case where
the user gets important information from the change detector itself.
Example 1.5 frictionestimation
Figure 1.13 shows how a whiteness test, used for restarting the filter, can
improve the filtering result in Example 1.2 quite considerably.
Here the CUSUM test statistics from the residuals is used, and the test
statistics gt are shown in the lower plot in Figure 1.13. Note that the test
statistics start to grow at time 200, but that the conservative threshold level
of 3 is not reached until time 210.
- Estimated parameters
0.04- -- True parameters I
I
I
v--
100
200 150 250 300
41
I
'4
I
"0 50 100 150 200 250 300
Time [samples]
Figure 1.l 3. Estimated friction parameters (upper plot) and test statistics
from the CUSUM
test (lower plot). Note the improved tracking ability compared to Figure 1.7.
In the following example, change detection is a tool for improved tracking,
and the changes themselves do not contain much information for the user.
Example 1.6 Target tracking
This example is a continuation of Example 1.3, and the application of the
CUSUM test is analogous to Example 1.5. Figure 1.14(a) shows the estimated
nguon tai.lieu . vn
