Genshiro Kitagawa. Introduction to Time Series Modeling (Введение в моделирование временных рядов)
Подождите немного. Документ загружается.
Append ix A
Algorithms for No n l i near
Optimiza tion
In this appendix, we briefly discu ss algorithms for nonlinear optimiza-
tion. For simplicity, w e consider the case wher e the objective fun c tion
f (x) is ap proximated by its Taylor series expansion up to the second
order:
f (x) = f (x
∗
) + (x −x
∗
)
T
g(x
∗
) +
1
2
(x −x
∗
)
T
H(x −x
∗
), (A.1)
where x = (x
1
,.. ., x
m
)
T
and
g(x) =
∂
f (x)
∂
x
1
.
.
.
∂
f (x)
∂
x
m
, H =
∂
2
f
∂
x
1
∂
x
1
···
∂
2
f
∂
x
1
∂
x
m
.
.
.
.
.
.
.
.
.
∂
2
f
∂
x
m
∂
x
1
···
∂
2
f
∂
x
m
∂
x
m
. (A.2)
From (A.1), we have
g(x) = g (x
∗
) + H(x −x
∗
) (A.3)
and if x
∗
is assumed to minimize the obje ctive function f (x), g(x
∗
) = 0
holds and we have
g(x) = H(x −x
∗
). (A.4)
Therefore, if the current approximation is x, by computing H and g(x),
the solution x
∗
is obtained as
x
∗
= x −H
−1
g(x). (A.5)
In actu al problems, the objective function f (x) is rarely expressible as a
quadra tic form such as that of (A.1) and the so lution x
∗
is not obtained
by a pplying (A. 5) only once. Moreover, because the matrix H is not
usually constan t but changes d epending on x, it is necessary to repeat th e
recursion
x
k
= x
k−1
−H
−1
k−1
g(x
k−1
), (A.6)
249
250 ALGORITHMS FOR NONLINEAR OPTIMI ZATION
using an app ropriately determined initial value x
0
.
This p rocedure is called the Newton-Raphson method. H owever,
since the likelihood f unction of the time serie s model is usually a very
complex function of the paramete rs and it is sometimes difficult to ob-
tain H
k
analytically, the following algorithm, known as the quasi-Newton
method, is used (Nocedal and Wright ( 2006)).
1. Put k = 1 and choose an initial value x
0
and H
−1
0
suitably. As a default
value, we may put H
0
= I.
2. Calculate the gradient vector g(x
k−1
).
3. Obtain the direction vector by h
k
= H
−1
k−1
g(x
k−1
).
4. Put x
k
= x
k−1
−
λ
k
h
k
and find
λ
k
, which minimizes f (x
k
) by a linear
search.
5. Obtain an estima te of H
−1
k
using eith er the DFP formula or the BFGS
formu la that follow.
[DFP formula] (Fletcher ( 1980))
H
−1
k
= H
−1
k−1
+
∆x
k
∆x
T
k
∆x
T
k
∆g
k
−
H
−1
k−1
∆g
k
∆g
T
k
H
−1
k−1
∆g
T
k
H
−1
k−1
∆g
k
, (A.7)
[BFGS formula] (Broyden (1970))
H
−1
k
=
I −
∆g
k
∆x
T
k
∆g
T
k
∆x
k
T
H
−1
k−1
I −
∆g
k
∆x
T
k
∆g
T
k
∆x
k
+
∆x
k
∆x
T
k
∆x
T
k
∆g
k
, (A.8)
where ∆x
k
= x
k
−x
k−1
and ∆g
k
= G(x
k
) −g(x
k−1
).
6. If the convergence condition is not satisfied, go back to step 2 af ter
setting k = k + 1.
This quasi-Newton method has the following two advantages. Firstly,
it is not necessary to compute the Hessian matrix H
k
and its inverse H
−1
k
directly. Sec ondly, it can usually find the minimum even w hen the objec-
tive fun c tion is far from being a quadratic function, since it a utomatically
adjusts the step width
λ
k
by a linear search. BFGS formula has an a d-
vantage the it does not require precise linear search.
Append ix B
Derivation of Levinson’s Algorithm
In this appendix, we derive the Levinson’s alg orithm (Levinson (1 947))
for estimating the AR co e fficients for univariate time series model ef-
fectively. Whittle (1963) showed an exten sio n of an algorithm for multi-
variate time series. However, since for multi-variate time series, the co-
efficients of the backward AR model are different from those of the for-
ward AR model, the algorithm needs to treat twice as many numbe r of
recursions as the univariate c ase.
Assume that the autocovariance function C
k
, k = 0,1,··· is given and
that the Yule-Walker estimates of the AR model of order m −1 have
already been obtained . In the following, since we consider AR mode ls
with different orders, the AR coefficients, the prediction error and the
prediction error variance of the AR model of ord er m −1 are denoted
by ˆa
m−1
1
,.. ., ˆa
m−1
m−1
, v
m−1
n
and
ˆ
σ
2
m−1
, r e spectively. Next, we c onsider a
method of efficiently obtaining Yule-Walker estimates ˆa
m
1
,.. ., ˆa
m
m
and
ˆ
σ
2
m
for the parameters of the AR model of or der m using the estimates for
the AR model of order m −1.
Since the coefficients ˆa
m−1
1
,.. ., ˆa
m−1
m−1
satisfy the fo llowing Yule-
Walker equation of order m −1, we have that
C
k
=
m−1
∑
j=1
ˆa
m−1
j
C
j−k
, k = 1,.. .,m −1. (B.1)
This means that v
m−1
n
satisfies
E
v
m−1
n
y
n−k
= E
y
n
−
m−1
∑
j=1
ˆa
m−1
j
y
n−j
y
n−k
= 0, (B.2)
for k = 1,. .., m −1. Her e , we consider a backward AR model of order
m −1 tha t represents the present value of the time ser ie s y
n
with future
values y
n+1
,.. ., y
n+m−1
,
y
n
=
m−1
∑
i=1
a
j
y
n+i
+ w
m−1
n
. (B.3)
251
252 DERIVATION OF LEVINSON’S ALGORITHM
Then, since C
−k
= C
k
holds for a univariate time series, this backward
AR model also satisfies the same Yule-Wa lker equatio n (B.1). Therefore,
the backward prediction error w
m−1
n
satisfies
E
n
w
m−1
n−m
y
n−k
o
= E
y
n−m
−
m−1
∑
j=1
ˆa
m−1
j
y
n−m+ j
y
n−k
= 0, (B.4)
for k = 1, ... ,m −1. Here, we define the weig hted sum of the forward
prediction error v
m−1
n
and the backward prediction error w
m−1
n−m
by
z
n
≡ v
m−1
n
−
β
w
m−1
n−m
≡ y
n
−
m−1
∑
j=1
ˆa
m−1
j
y
n−j
−
β
y
n−m
−
m−1
∑
j=1
ˆa
m−1
j
y
n−m+ j
= y
n
−
m−1
∑
j=1
ˆa
m−1
j
−
β
ˆa
m−1
m−j
y
n−j
−
β
y
n−m
. (B.5)
z
n
is a linear combination of y
n
, y
n−1
,.. ., y
n−m
and from (B.2) and (B.4),
it follows that
E{z
n
y
n−k
} = 0 (B.6)
for k = 1, ... ,m −1. Therefore, if the value of
β
is determined so that
E(z
n
y
n−m
) = 0 holds for k = m, the Yule-Walker equation of order m
will be satisfied. For that purpose, fro m
E(z
n
y
n−m
)
= E
y
n
−
m−1
∑
j=1
ˆa
m−1
j
y
n−j
−
β
y
n−m
−
m−1
∑
j=1
ˆa
m−1
j
y
n−m+ j
y
n−m
= C
m
−
m−1
∑
j=1
ˆa
m−1
j
C
m−j
−
β
C
0
−
m−1
∑
j=1
ˆa
m−1
j
C
j
= 0, (B.7)
β
is determined as
β
=
C
0
−
m−1
∑
j=1
ˆa
m−1
j
C
j
−1
C
m
−
m−1
∑
j=1
ˆa
m−1
j
C
m−j
=
σ
2
m−1
−1
C
m
−
m−1
∑
j=1
ˆa
m−1
j
C
m−j
. (B.8)
Therefore, if we denote th is
β
as ˆa
m
m
and define a
m
j
by
ˆa
m
j
≡ ˆa
m−1
j
− ˆa
m
m
ˆa
m−1
m−j
, (B.9)
253
then from (B.5) – (B.7), we have
E
y
n
−
m
∑
j=1
ˆa
m
j
y
n−j
y
n−k
= C
k
−
m
∑
j=1
ˆa
m
j
C
k−j
= 0 (B.10)
for k = 1,. .., m.
In addition, the innovation variance of the AR model with order m
can be expressed as
ˆ
σ
2
m
= C
0
−
m
∑
j=1
ˆa
m
j
C
j
= C
0
−
m−1
∑
j=1
ˆa
m−1
j
− ˆa
m
m
ˆa
m−1
m−j
C
j
− ˆa
m
m
C
m
= C
0
−
m−1
∑
j=1
ˆa
m−1
j
C
j
− ˆa
m
m
C
m
−
m−1
∑
j=1
ˆa
m−1
m−j
C
j
=
ˆ
σ
2
m−1
− ˆa
m
m
C
m
−
m−1
∑
j=1
ˆa
m−1
m−j
C
j
. (B.11 )
Using (B.8) , it follows that C
m
−
m−1
∑
j=1
ˆa
m−1
m−j
C
j
= ˆa
m
m
ˆ
σ
2
m−1
and then
ˆ
σ
2
m
is
obtained as follows:
ˆ
σ
2
m
=
ˆ
σ
2
m−1
1 −( ˆa
m
m
)
2
. (B.12)
Append ix C
Derivation of the Kalman Filter
and Smoother Algorit h ms
In this appendix, a brief derivation of the Kalman filter (Kalman (1960))
and the fixed interval smoothing algorithm (Bierm a n (1977)) are given.
C.1 Kalman Filter
[ One-Step-Ahead Prediction ]
From x
n
= F
n
x
n−1
+ G
n
v
n
, we obtain
x
n|n−1
= E (x
n
|Y
n−1
)
= E (F
n
x
n−1
+ G
n
v
n
|Y
n−1
)
= F
n
E (x
n−1
|Y
n−1
)
= F
n
x
n−1|n−1
, (C.1)
V
n|n−1
= E (x
n
−x
n|n−1
)
2
= E (F
n
(x
n−1
−x
n−1|n−1
) + G
n
v
n
)
2
= F
n
E (x
n−1
−x
n−1|n−1
)
2
F
T
n
+ G
n
E (v
2
n
)G
T
n
= F
n
V
n−1|n−1
F
T
n
+ G
n
Q
n
G
T
n
, (C.2)
where for simplicity of notation, xx
T
is abbreviated a s x
2
.
[ Filter ]
Denote the prediction error of y
n
by
ε
n
; then from y
n
= H
n
x
n
+ w
n
, it
can be expressed as
ε
n
≡ y
n
−E (y
n
|Y
n−1
)
= H
n
x
n
+ w
n
−E (H
n
x
n
+ w
n
|Y
n−1
)
= H
n
x
n
+ w
n
−H
n
E (x
n
|Y
n−1
)
= H
n
(x
n
−x
n|n−1
) + w
n
. ( C.3)
255
256 DERIVATION OF THE KALMAN FILTER AND SMOOTHER
Therefore, we have
Var(
ε
n
) = H
n
V
n|n−1
H
T
n
+ R
n
, (C.4)
Cov(x
n
,
ε
n
) = Cov(x
n
,H
n
(x
n
−x
n|n−1
) + w
n
)
= Var(x
n
−x
n|n−1
)H
T
n
= V
n|n−1
H
T
n
. (C.5)
Using th e facts that Y
n
= {Y
n−1
,y
n
} = Y
n−1
⊕
ε
n
and that in the case
of the normal distribution, the conditional expectation of x
n
given Y
n
is
expressible by orthogonal projection, it follows that
x
n|n
= E(x
n
|Y
n
) = Proj(x
n
|Y
n
)
= Proj(x
n
|Y
n−1
,
ε
n
)
= Proj(x
n
|Y
n−1
) + Proj(x
n
|
ε
n
). (C.6)
Because Proj(x
n
|
ε
n
) is obtained by regressing x
n
on
ε
n
, from (C.4) and
(C.5),
Proj(x
n
|
ε
n
) = Cov(x
n
,
ε
n
)Var (
ε
n
)
−1
ε
n
= V
n|n−1
H
T
n
(H
n
V
n|n−1
H
T
n
+ R
n
)
−1
ε
n
≡ K
n
ε
n
. (C.7)
Therefore, we have
x
n|n
= x
n|n−1
+ K
n
ε
n
. (C.8)
In addition, from
V
n|n−1
= E(x
n
−x
n|n−1
)
2
= E(x
n
−x
n|n
+ K
n
ε
n
)
2
= V
n|n
+ K
n
Var(
ε
n
)K
T
n
, (C.9)
we have
V
n|n
= V
n|n−1
−K
n
H
n
V
n|n−1
= (I −K
n
H
n
)V
n|n−1
. (C.10)
C.2 Smoothing
δ
n+1
≡x
n+1
−x
n+1|n
is assumed to be the prediction error of x
n+1
.
Define Z
n
by
Z
n
≡Y
n
⊕
δ
n+1
⊕{v
n+1
,.. ., v
N
,w
n+1
,.. .,w
N
}.
SMOOTHING 257
Then, we have the decomposition
z
n
≡ Proj(x
n
|Z
n
)
= Proj(x
n
|Y
n
) + Proj(x
n
|
δ
n+1
)
+ Proj(x
n
|v
n+1
,.. ., v
N
,w
n+1
,.. .,w
N
), (C.11)
and it follows th at
Proj(x
n
|Y
n
) = x
n|n
Proj(x
n
|
δ
n+1
) = Cov(x
n
,
δ
n+1
)Var (
δ
n+1
)
−1
δ
n+1
(C.12)
Proj(x
n
|v
n+1
,.. ., v
N
,w
n+1
,.. ., w
N
) = 0.
In addition, we have
Var(
δ
n+1
) = V
n+1|n
, (C.13)
Cov(x
n
,
δ
n+1
) = Cov(x
n
,F
n+1
(x
n
−x
n|n
) + G
n+1
v
n+1
)
= E (x
n
−x
n|n
)
2
F
T
n+1
= V
n|n
F
T
n+1
. (C.14)
Therefore, by putting A
n
= V
n|n
F
T
n+1
V
−1
n+1|n
, we have
z
n
= x
n|n
+ A
n
(x
n+1
−x
n+1|n
). (C.15)
Here, considering that Z
N
generates Y
N
, we obtain
x
n|N
= Proj(x
n
|Y
N
)
= Proj(Proj(x
n
|Z
N
)|Y
N
)
= Proj(z
n
|Y
N
)
= x
n|n
+ A
n
(x
n+1|N
−x
n+1|n
). (C.16)
Further, using
x
n
−x
n|N
+ A
n
x
n+1|N
= x
n
−x
n|n
+ A
n
x
n+1|n
, (C.17)
and E
n
(x
n
−x
n|N
)x
T
n+1|N
o
= E
n
(x
n
−x
n|n
)x
T
n+1|n
o
= 0, we obtain
V
n|N
+ A
n
E
n
x
n+1|N
x
T
n+1|N
o
A
T
n
= V
n|n
+ A
n
E
n
x
n+1|n
x
T
n+1|n
o
A
T
n
.
(C.18)
258 DERIVATION OF THE KALMAN FILTER AND SMOOTHER
Here, using
E
n
(x
n+1
−x
n+1|N
)x
T
n+1|N
o
= 0
E
n
(x
n
−x
n|n
)x
T
n+1|n
o
= 0,
we obtain
E
n
x
n+1|N
x
T
n+1|N
o
= E
(x
n+1|N
−x
n+1
+ x
n+1
)(x
n+1|N
−x
n+1
+ x
n+1
)
T
= V
n+1|N
+ E
x
n+1
x
T
n+1
+ 2E
(x
n+1|N
−x
n+1
)x
T
n+1
= V
n+1|N
+ E
x
n+1
x
T
n+1
−2E
(x
n+1|N
−x
n+1
)(x
n+1|N
−x
n+1
)
T
= E
x
n+1
x
T
n+1
−V
n+1|N
, (C.19)
and
E
n
x
n+1|n
x
T
n+1|n
o
= E
x
n+1
x
T
n+1
−V
n+1|n
. (C.20)
Substituting this into (C.18) yie lds
V
n|N
= V
n|n
+ A
n
(V
n+1|N
−V
n+1|n
)A
T
n
. (C.21)