Journal of Robotics, Networking and Artificial Life, Vol. 1, No. 1 (June 2014), 54-59

Model Introduced SPRT for Structural Change Detection of Time Series (I) -- Formulation -Yoshihide Koyama, Tetsuo Hattori

Graduate School of Engineering, Kagawa University, 2217-20 Hayashi
Takamatsu City, Kagawa 761-0396, Japan
E-mail: hattori@eng.kagawa-u.ac.jp
Hiromichi Kawano

NTT Advanced Technology, 19-18, Nakamachi
Musashino-shi, Tokyo 180-0006, Japan

Abstract

Previously, we have proposed a method applying Sequential Probability Ratio Test (SPRT) to the structural change
detection problem of ongoing time series data. In this paper, we introduce a structural change model with Poissonprocess into a system that outputs a set of ongoing time series data, moment by moment. The model can be considered asa kind of Hidden Markov Model. According to the model, we formulate a method to find out the structural change, bydefining a New Sequential Probability Ratio (NSPR), which can be calculated from the joint occurrence probability ofthe observing event with the event H0 (the structural change is not occurred) and H1 (the change is occurred). And also,we show the simple recurrence equation of the NSPR.
Keywords: Time series, Change detection, SPRT (Sequential Probability Ratio Test), Hidden Markov Model

1.

Introduction

To make a prediction of ongoing time series data, wehave three stages in general.1, 2 First; we have to find aprediction model that adequately represents thecharacteristics of the early time series data. Second, we
have to detect the structural change of the time series
data, as quickly and correctly as possible, when theestimated prediction model does not meet the data any
more as shown in Fig.1.3, 4 Third, we have to reconstruct
the next prediction model as soon as possible after thechange detection.
For the second problem, we have already proposed an
application of SPRT (sequential probability ratio test)
that has been mainly used in the field of quality

control.5, 6 And we presented the experimental results incomparison with Chow Test that is well-known standard
method for such structural change detection of timeseries data.6, 7
However, in the SPRT method that we previously
proposed for the structural change detection problem,the probability of structural change occurrence is notknown beforehand. In addition, in the method, only theratio of the conditional probability is used. Then, theformulation of SPRT includes the notion that thestructure may be able to recover even after the change
occurrence. Then, there is a possibility that error
happens in the change detection using the ratio of theconditional probability and so the threshold of the SPRT

Published by Atlantis Press
Copyright: the authors
54

Y. Koyama, T. Hattori and H. KawanoIf i < C1, then terminate this process with theacceptance of H0.

for the detection is decided based on the error
probability.
In this paper, we introduce a Hidden Markov Modelwith Poisson process on the structural change one andpropose a new probability ratio method for the change
detection problem.

y  2 x1  3x 2  10  

yC1 y  3x1  3 x 2  10  

180change point tc = 70160


1 , C2 
1

(2)

where  means type I error (reject a true null
hypothesis), and  means type II error (accept a null
hypothesis as true one when it is actually false).
2.2. Procedure of SPRT8140

The concrete procedure of applying the SPRT method tothe structural change detection problem is describedusing the notation of Fig. 2 as follows.

12010080604020t00102030405060

7080

90100Fig. 1. Example of time series data where the true change
point tc=70.

2. SPRT
2.1. SPRT8The Sequential Probability Ratio Test (SPRT) is usedfor testing a null hypothesis H0 (e.g. the quality is underpre-specified limit 1%) against hypothesis H1 (e.g. thequality is over pre-specified limit 1%). And it is defined
as follows:
Let Z1, Z2, …Zi be respectively observed time series
data at each stage of successive events, the probability
ratio i is computed as follows.

λi P ( Z 1 | H1 )  P ( Z 2 | H 1 )    P ( Z i | H1 )(1)
P ( Z1 | H 0 )  P ( Z 2 | H 0 )    P ( Z i | H 0 )where P(Z | H0) denotes the distribution of Z if H0 istrue, and similarly, P(Z | H1) denotes the distribution ofZ if H1 is true.
Two positive constants C1 and C2 (C1 < C2) are chosen.
If C1 < i < C2, the experiment is continued by taking anadditional observation. If C2 < i, the process isterminated with the rejection of H0 (acceptance of H1).

Fig. 2. Example of time series data and single regression line,
where the true change point tc =70.6

Step 1: Make a prediction expression and set the tolerance
band (a) (e.g. a=2s) that means permissible error
margin between the predicted data and the observed
one. (s denotes a standard deviation in learning
sample data at early stage.)
Step 2: Set up the null hypothesis H0 and alternative
hypothesis H1.
H0：Change has not occurred yet.
H1：Change has occurred.
Set the values ,  and compute C1 and C2,
according to Eq. (2). Initialize i = 0, 0 = 1.

Published by Atlantis Press
Copyright: the authors55

Model Introduced SPRTStep 3: Incrementing i (i = i+1), observe the following datayi. Evaluate the error | i | between the data yi andthe predicted value from the aforementionedprediction expression.
Step 4: Judge as to whether the data yi goes in the tolerance
band or not, i.e., the i is less than (or equal to) thepermissible error margin or not. If it is Yes, then set
i = 1 and return to Step3. Otherwise, advance toStep5.
Step 5: Calculate the probability ratioi, using
following Eq. (3) that is equivalent to Eq. (1).

i  i 1

P ( i | H1 )P ( i | H 0 )thethis model, once the change has occurred during theobserving period, the structure does not go back to theprevious one. The reason why we set such a model isthat we focus on the detection of the first structuralchange in the sequential processing. The concept of thestructural change model is shown in Fig.3. Then, weintroduce the detailed model. Let R be the probability ofthe prediction failure that the data value goes out thetolerance zone when the structure is unchanged. Let Rc
be the probability of the failure when the structurechange occurred. We can consider that Rc is greaterthan R, i.e., Rc > R. The detailed model is illustrated asa probabilistic finite state automaton in Fig.4.

(3)where, if the data yi goes out the tolerance band,( P(i |H0 ), P(i |H1 ) )= ( θ0, θ1 ), otherwise,( P(i |H0 ), P(i |H1 ) )= ( (1-θ0), (1-θ1) ).

1- S0

Step 6: Execution of testing.
(i) If the ratio i is greater than C2 (= (1-)/ ),dismiss the null hypothesis H0, and adopt thealternative hypothesis H1, and then End.
(ii) Otherwise, if the ratio i is less than C1 (= /(1) ), adopt the null hypothesis H0, and dismiss
the alternative hypothesis H1, and then set i =1 and return to Step3.
(iii) Otherwise (in the case where C1  i  C2 ),advance to Step7.
Step 7: Observe the following data yi incrementing i.
Evaluate the error | i | and judge whether the data
yi goes in the tolerance band, or not. Then, return toStep5 (calculation of the ratio i).

3.

Structural Change Model
Introduced

3.1. Hidden Markov Model
We present a Hidden Markov Model where thestructural change is Poisson occurrence of average . In

1.0
S1

S0 : State that the structure is unchanged.
S1 : State that the structural change has occurred.
 : Probability of the structural change occurrence.
(Poisson Process.)
Fig. 3. Structural change model.

3.2. New sequential probability ratio
Let a1a 2 ,, ai , an ai  {IN, OUT} be a string (orsymbol sequence) obtained from the observed data.
~Let θi and θi be the conditional probability that
outputs the observed data (or above symbol sequence,Cn  a1a 2  a n in the state S0 and S1, respectively. That~is, it means that θi {R, 1  R} and θi {Rc , 1  Rc } ,respectively.
And let P(a1…an, H0) and P(a1…an, H1) be the joint
probability of the symbol sequence Cn that happen withthe event H0 (the structural change is not occurred) andH1 (the change is occurred), respectively.
Then, the following equations hold.

Published by Atlantis Press
Copyright: the authors
56

Y. Koyama, T. Hattori and H. Kawano

1

1.0

S01-R

S11-Rc

RRc
Rc

RIN

OUTOUTIN

1-Rc

1-R

R : Probability of prediction failure (OUT) when the structure is unchanged.
Rc : Probability of prediction failure (OUT) when the structural change has been occurred.
IN : The state that observed data goes into the tolerance zone.
OUT: The state that observed data goes out of the tolerance zone.

Fig.4. Proposed Hidden Markov Model.

P( a1  a n , H 0 )  P (Cn , H 0 ) (1 γ) θ1 θn  (1 γ)
nnn

Πθ(4)

P(H1 | a1 an )  P(H1 | Cn ) ii 1P ( a1  a n , H 1 )  P (C n , H 1 )n~θi  ((1 γ)θ1 )(γγn(7)~ii 2n~θ)   ((1 γ) 2θ1θ2 )(γii 3n

k 1n



( (1 γ) k 1･k 1~θ)θj )(γj 0Using these equations, the New Sequential Probability
Ratio (NSPR) that we propose can be represented asfollows.

iik(5)P(H 0 | a1 an )  P(H 0 | Cn ) P(Cn , H1 )P(Cn , H1 )P(Cn )
P(Cn , H 0 )  P(Cn , H1 )θ)i 1

P(H1 | Cn )･ P(Cn )P(Cn )

P(H 0 | Cn )･ P(Cn )P(Cn )

P(Cn , H 0 )P(Cn , H 0 )(6)P(Cn )
P(Cn , H 0 )  P(Cn , H1 )NSPR 

P(H 1 | a1 a n ) P(H 1 | Cn ) P(Cn , H 1 )P(H 0 | a1  a n ) P(H 0 | Cn ) P(Cn , H 0 )nk 1k 1j 0(1 γ) n~θ)θj )(γi knΠθii 1

Published by Atlantis Press
Copyright: the authors57n

((1 γ) k 1･i(8)Model Introduced SPRTWhen the NSPR is greater than 1.0, we can regard thatthe structural change has been occurred before thepresent time.
In the similar way to the case of SPRT (see Eq.(3)), thedefinition of NSPR can also be described in a recursion
formula.

Λ3 ~~ ~~~~γ123  (1 γ)1γ23  (1 γ)212γ3(1 γ)3123

~1(Λ2 γ)( 3 )31 γ(12)Let Λn be the value of NSPR defined by Eq.(8).
nΛn  ( (1  γ)k 1k 1k 1n θ )(γ･jj0(1  γ) n

Therefore, by inductive inference, we have thefollowing simple recurrence equation.

~θi )

ikn

Πθ

ii 1~

where  0  1,  0  1(9)~1nΛn (Λn 1 γ)(  )
n
1 γ

(13)

where Λ0  0 .

Accordingly, we have the followings.

~γ1Λ1 (1 γ)14.

(10)~~~γ  1 2  (1  γ) 1γ  2
Λ2 (1  γ) 2  1 2~~
1 γ  1  (1  γ) 1γ  2()( )1 γ(1  γ) 1
2~~1γ 1(1  γ) 1γ  2()( )
1  γ (1  γ) 1(1  γ) 1  2~1
(Λ1  γ)( 2 )1 γ
2(11)

Conclusion

We have presented a Hidden Markov Model for thestructural change detection problem, and haveformulated a New Sequential Probability Ratio (NSPR)
for solving the problem of the detection, using theoccurrence probability based on the proposed model.
Moreover, we have shown that the definition of NSPR
can also be described in a simple recurrence equation.
We consider that this formulation based on ourproposed model will be more promising than the SPRT
one that we previously applied it to the change detection
problem.
At another opportunity, we will describe the nature ofNSPR in the details and analyze the difference between
NSPR and the conventional SPRT, and also show theeffectiveness of the NSPR by experimentation.

Similarly, we have

Published by Atlantis Press
Copyright: the authors
58

Y. Koyama, T. Hattori and H. KawanoReferences
1. C. G. E. P. Box and G. M. Jenkins, Time Series Analysis:Forecasting and Control (Prentice Hall, 1976).
2. Peter J. Brockwell and Richard A. Davis, Introduction toTime Series and Forecasting, 2nd edn. (Springer; 2003)
3. C. Han, P. K. Willet and D. A. Abraham, Some methods
to evaluate the performance of Page's test as used todetect transient signals, IEEE Trans. Signal processing.
47(8) (1999) 2112-2127.
4. S. D. Blostein, Quickest detection of a time-varying
change in distribution, IEEE Trans. Information Theory.
37(4) (1991) 1116-1122.
5. A. Wald, Sequential Analysis (John Wiley & Sons,1947).
6. H. Kawano, T. Hattori, and K. Nishimatsu, Structural
Change Point Detection Method of Time Series Using
Sequential Probability Ratio Test -Comparison withChow Test in the ability of early detection- (in Japanese),
IEEJ Trans. EIS. 128(4) (2008) 583-592.
7. G. C. Chow, Tests of Equality Between Sets ofCoefficients in Two Linear Regressions, Econometrica.
28(3) (1960) 591-605.
8. K. Takeda, T. Hattori, T. Izumi and H. Kawano,Extended SPRT for Structural Change Detection of Time
Series Based on Multiple Regression Mode, inProceedings of the 15th International Symposium onArtificial Life and Robotics, (Oita, Japan, Feb. 2010),
ISBN: 978-4-9902880-4-4, pp.755-758.
9. K. Takeda, T. Hattori, Tetsuya Izumi and H. Kawano,
Extended SPRT for Structural Change Detection of TimeSeries Based on Multiple Regression Model,International Journal of Artificial Life and Robotics
Springer, ISSN: 1433-5298, 15(4), (2010) 417-420.
10. T. Hattori and H. Kawano, Change Detection Method ofTime Series as an Optimal Stopping Problem -Constructive Proof of Optimal Solution Theorem --, inProc. of 2011 International Conference on Biometrics
and Kansei Engineering, (Kagawa, Japan, 2011), IEEE
Computer Society, ISBN: 978-0-7695-4512-7, pp.100105.

Published by Atlantis Press
Copyright: the authors
59