【免费】序列蒙特卡洛算法（粒子滤波）OnsequentialMonteCarlosamplingmethodsforBayesianfiltering资源-CSDN文库

粒子滤波

序列蒙特卡洛

5星 · 超过95%的资源需积分: 0 60 浏览量 2010-03-11 11:45:31 上传评论 1 收藏 141KB PDF 举报

资源详情

资源评论

Statistics and Computing (2000) 10, 197–208

On sequential Monte Carlo sampling

methods for Bayesian ﬁltering

ARNAUD DOUCET, SIMON GODSILL and CHRISTOPHE ANDRIEU

Signal Processing Group, Department of Engineering, University of Cambridge,

Trumpington Street, CB2 1PZ Cambridge, UK

ad2@eng.cam.ac.uk, sjg@eng.cam.ac.uk, ca226@eng.cam.ac.uk

Received July 1998 and accepted August 1999

In this article, we present an overview of methods for sequential simulation from posterior distribu-

tions. These methods are of particular interest in Bayesian ﬁltering for discrete time dynamic models

that are typically nonlinear and non-Gaussian. A general importance sampling framework is devel-

oped that uniﬁes many of the methods which have been proposed over the last few decades in several

different scientiﬁc disciplines. Novel extensions to the existing methods are also proposed. We show in

particular how to incorporate local linearisation methods similar to those which have previously been

employed in the deterministic ﬁltering literature; these lead to very effective importance distributions.

Furthermore we describe a method which uses Rao-Blackwellisation in order to take advantage of

the analytic structure present in some important classes of state-space models. In a ﬁnal section we

develop algorithms for prediction, smoothing and evaluation of the likelihood in dynamic models.

Keywords: Bayesian ﬁltering, nonlinear non-Gaussian state space models, sequential Monte Carlo

methods, particle ﬁltering, importance sampling, Rao-Blackwellised estimates

I. Introduction

Many problems in applied statistics, statistical signal process-

ing, time series analysis and econometrics can be stated in a

state space form as follows. A transition equation describes the

prior distribution of a hidden Markov process {x

; k ∈N}, the

so-called hidden state process, and an observation equation de-

scribes the likelihood of the observations {y

; k ∈N}, k being a

discrete time index. Within a Bayesian framework, all relevant

information about {x

, x

,...,x

}given observations up to and

including time k can be obtained from the posterior distribu-

tion p(x

, x

,...,x

,...,y

). In many applications we

are interested in estimating recursively in time this distribution,

and particularly one of its marginals, the so-called ﬁltering dis-

tribution p(x

, y

,...,y

). Given the ﬁltering distribution

one can then routinely proceed to ﬁltered point estimates such

as the posterior mode or mean of the state. This problem is

known as the Bayesian ﬁltering problem or the optimal ﬁltering

problem. Practical applications include target tracking (Gordon,

Salmond and Smith 1993), blind deconvolution of digital com-

munications channels (Clapp and Godsill 1999, Liu and Chen

1995), estimation of stochastic volatility (Pitt and Shephard

1999) and digital enhancement of speech and audio signals

(Godsill and Rayner 1998).

Except in a few special cases, including linear Gaussian

state space models (Kalman ﬁlter) and hidden ﬁnite-state space

Markov chains, it is impossible to evaluate these distributions

analytically. From the mid 1960’s, a great deal of attention has

been devoted to approximating these ﬁltering distributions, see

for example Jazwinski (1970). The most popular algorithms,

the extended Kalman ﬁlter and the Gaussian sum ﬁlter, rely on

analytical approximations (Anderson and Moore 1979). Inter-

esting work in the automatic control ﬁeld was carried out during

the 1960’s and 70’s using sequential Monte Carlo (MC) inte-

gration methods, see Akashi and Kumamoto (1975), Handschin

and Mayne (1969), Handschin (1970), and Zaritskii, Svetnik and

Shimelevich (1975). Possibly owing to the severe computational

limitations of the time, these Monte Carlo algorithms have been

largely neglected until recent years. In the late 80’s, massive

increases in computational power allowed the rebirth of numeri-

cal integration methods for Bayesian ﬁltering (Kitagawa 1987).

Current research has now focused on MC integration methods,

which have the great advantage of not being subject to the as-

sumption of linearity or Gaussianity in the model, and relevant

0960-3174

2000 Kluwer Academic Publishers

198 Doucet, Godsill and Andrieu

work includes M¨uller (1992), West (1993), Gordon, Salmond

and Smith (1993), Kong, Liu and Wong (1994) and Liu and

Chen (1998).

The main objective of this article is to include in a uniﬁed

framework many old and more recent algorithms proposed in-

dependently in a number of applied science areas. Both Liu

and Chen (1998) and Doucet (1997, 1998) underline the central

rˆole of sequential importance sampling in Bayesian ﬁltering.

However, contrary to Liu and Chen (1998) which emphasizes

the use of hybrid schemes combining elements of importance

sampling with Markov Chain Monte Carlo (MCMC), we focus

here on computationally cheaper alternatives. We describe also

how it is possible to improve current existing methods via Rao-

Blackwellisation for a useful class of dynamic models. Finally,

we show how to extend these methods to compute the predic-

tion and ﬁxed-interval smoothing distributions as well as the

likelihood.

The paper is organised as follows. In Section 2, we brieﬂy re-

view the Bayesian ﬁltering problem and classical Bayesian im-

portance sampling is proposed for its solution. We then present

a sequential version of this method which allows us to obtain a

general recursive MC ﬁlter: the sequential importance sampling

(SIS) ﬁlter. Under a criterion of minimum conditional variance of

the importance weights, we obtain the optimal importance func-

tion for this method. Unfortunately, for most models of applied

interest the optimal importance function leads to non-analytic

importance weights, and hence we propose several suboptimal

distributions and show how to obtain as special cases many of

the algorithms presented in the literature. Firstly we consider

local linearisation methods of either the state space model or

the optimal importance function, giving some important exam-

ples. These linearisation methods seem to be a very promising

way to proceed in problems of this type. Secondly we consider

some simple importance functions which lead to algorithms cur-

rently known in the literature. In Section 3, a resampling scheme

is used to limit practically the degeneracy of the algorithm. In

Section 4, we apply the Rao-Blackwellisation method to SIS

and obtain efﬁcient hybrid analytical/MC ﬁlters. In Section 5,

we show how to use the MC ﬁlter to compute the prediction and

ﬁxed-interval smoothing distributions as well as the likelihood.

Finally, simulations are presented in Section 6.

II. Filtering via Sequential

Importance Sampling

A. Preliminaries: Filtering for the state space model

The state sequence {x

; k ∈N}, x

∈R

, is assumed to be an

unobserved (hidden) Markov process with initial distribution

p(x

) (which we subsequently denote as p(x

−1

) for no-

tational convenience) and transition distribution p(x

k−1

where n

is the dimension of the state vector. The observa-

tions {y

; k ∈N}, y

∈R

, are conditionally independent given

the process {x

; k ∈N} with distribution p(y

) and n

is the

dimension of the observation vector. To sum up, the model is a

hidden Markov (or state space) model (HMM) described by

p (x

| x

k−1

) for k ≥ 0 (1)

p (y

| x

) for k ≥ 0 (2)

We denote by x

0:n

={x

,...,x

}and y

0:n

={y

,...,y

}, re-

spectively, the state sequence and the observations up to time n.

Our aim is to estimate recursively in time the distribution

p(x

0:n

| y

0:n

) and its associated features including p(x

| y

0:n

)

and expectations of the form

I ( f

) =

0:n

)p(x

0:n

| y

0:n

) dx

0:n

(3)

for any p(x

0:n

| y

0:n

)-integrable f

: R

(n +1) ×n

→R. A recur-

sive formula for p(x

0:n

| y

0:n

)isgivenby:

p(x

0:n+1

| y

0:n+1

) = p(x

0:n

| y

0:n

)

p(y

n+1

| x

n+1

)p(x

n+1

| x

)

p(y

n+1

| y

0:n

)

(4)

The denominator of this expression cannot typically be com-

puted analytically, thus rendering an analytic approach infeasi-

ble except in the special cases mentioned above. It will later be

assumed that samples can easily be drawn from p(x

| x

k−1

) and

that we can evaluate p(x

| x

k−1

) and p(y

| x

) pointwise.

B. Bayesian Sequential Importance Sampling (SIS)

Since it is generally impossible to sample from the state pos-

terior p(x

0:n

) directly, we adopt an importance sampling

(IS) approach. Suppose that samples {x

(i)

0:n

; i =1,...,N} are

drawn independently from a normalised importance function

π(x

0:n

| y

0:n

) which has a support including that of the state

posterior. Then an estimate

( f

) of the posterior expectation

I ( f

) is obtained using Bayesian IS (Geweke 1989):

( f

) =

i=1

(i)

0:n

˜w

(i)

, ˜w

(i)

∗(i)

j=1

∗( j )

(5)

where w

∗(i)

= p(y

0:n

| x

0:n

)p(x

0:n

)/π(x

0:n

| y

0:n

) is the unnor-

malised importance weight. Under weak assumptions

( f

)

converges to I ( f

), see for example Geweke (1989). However,

this method is not recursive. We now show how to obtain a

sequential MC ﬁlter using Bayesian IS.

Suppose one chooses an importance function of the form

π(x

0:n

| y

0:n

) = π(x

)

k=1

π(x

| x

0:k−1

, y

0:k

) (6)

Such an importance function allows recursive evaluation in time

of the importance weights as successive observations y

become

On sequential Monte Carlo sampling methods 199

available. We obtain directly the sequential importance sampling

ﬁlter.

Sequential Importance Sampling (SIS)

For times k =0, 1, 2,...

•

For i = 1,...,N, sample x

(i)

∼π(x

(i)

0:k−1

, y

0:k

) and set

(i)

0:k

=(x

(i)

0:k−1

, x

(i)

) .

•

For i =1,...,N, evaluate the importance weights up to a

normalising constant:

∗(i)

= w

∗(i)

k−1

(i)

k−1

(i)

0:k−1

, y

0:k

(7)

•

For i = 1,...,N, normalise the importance weights:

˜w

(i)

∗(i)

j=1

∗( j )

(8)

A special case of this algorithm was introduced in 1969 by

Handschin and Mayne (1969) and Handschin (1970). Many of

the other algorithms proposed in the literature are later shown

also to be special cases of this general (and simple) algorithm.

Choice of importance function is of course crucial and one ob-

tains poor performance when the importance function is not well

chosen. This issue forms the topic of the following subsection.

C. Degeneracy of the algorithm

If Bayesian IS is interpreted as a Monte Carlo sampling method

rather than as a Monte Carlo integration method, the best possible

choice of importance function is of course the posterior distri-

bution itself, p(x

0:k

). We would ideally like to be close to

this case. However, for importance functions of the form (6), the

variance of the importance weights can only increase (stochas-

tically) over time.

Proposition 1. The unconditional variance of the importance

weights, i.e. with the observations y

0:k

being interpreted as ran-

dom variables, increases over time.

The proof of this proposition is a straightforward extension of

a Kong-Liu-Wong theorem (Kong, Liu and Wong 1994) to the

case of an importance function of the form (6). Thus, it is impos-

sible to avoid a degeneracy phenomenon. In practice, after a few

iterations of the algorithm, all but one of the normalised impor-

tance weights are very close to zero and a large computational

effort is devoted to updating trajectories whose contribution to

the ﬁnal estimate is almost zero.

D. Selection of the importance function

To limit degeneracy of the algorithm, a natural strategy consists

of selecting the importance function which minimises the vari-

ance of the importance weights conditional upon the simulated

trajectory x

(i)

0:k−1

and the observations y

0:k

Proposition 2. π (x

(i)

0:k−1

, y

0:k

) = p(x

(i)

k−1

, y

) is the im-

portance function which minimises the variance of the impor-

tance weight w

∗(i)

conditional upon x

(i)

0:k−1

and y

0:k

Proof: Straightforward calculations yield

var

π(x

(i)

0:k−1

0:k

)

∗(i)

k−1

p(y

| x

(i)

k−1

¢¢

| x

(i)

0:k−1

, y

0:k

− p

| x

(i)

k−1

This variance is zero for π(x

| x

(i)

0:k−1

, y

0:k

) = p(x

| x

(i)

k−1

, y

1. Optimal importance function

The optimal importance function p(x

(i)

k−1

, y

) was intro-

duced by Zaritskii, Svetnik and Shimelevich (1975) then by

Akashi and Kumamoto (1977) for a particular case. More

recently, this importance function has been used in Chen

and Liu (1996), Kong, Liu and Wong (1994) and Liu and

Chen (1995). For this distribution, we obtain from (7) the

importance weight w

∗(i)

k−1

p(y

(i)

k−1

). The optimal im-

portance function suffers from two major drawbacks. It re-

quires the ability to sample from p(x

(i)

k−1

, y

) and to eva-

luate p(y

(i)

k−1

) =

p(y

)p(x

| x

(i)

k−1

) dx

. This integral

will have no analytic form in the general case. Nevertheless,

analytic evaluation is possible for the important class of models

presented below, the Gaussian state space model with non-linear

transition equation.

Example 3. Nonlinear Gaussian State Space Models. Let us

consider the following model:

= f (x

k−1

) + v

, v

∼ N

×1

, Σ

(9)

= Cx

+ w

, w

∼ N

×1

, Σ

(10)

where f : R

→ R

is a real-valued non-linear function,

C ∈R

×n

is an observation matrix, and v

and w

are mu-

tually independent i.i.d. Gaussian sequences with Σ

> 0 and

> 0; C, Σ

and Σ

are assumed known. Deﬁning

−1

= Σ

−1

+ C

−1

C (11)

= Σ

−1

f (x

k−1

) + C

−1

(12)

one obtains

| (x

k−1

, y

) ∼ N (m

, Σ) (13)

剩余11页未读，继续阅读

评论收藏

内容反馈

sxhouxh

2012-03-02

算法很详细，但学习时要有耐心。

序列蒙特卡洛算法（粒子滤波）On sequential Monte Carlo sampling methods for Bay...

评论3

最新资源

序列蒙特卡洛算法（粒子滤波）On sequential Monte Carlo sampling methods for Bay...

评论3

最新资源

相关推荐

序列蒙特卡罗算法

Sequential Monte Carlo Methods for Bayesian Computation

A sequential Monte Carlo filtering approach to fault detection and isolation in nonlinear systems

粒子过滤器：Sequential Monte Carlo-matlab开发

序列蒙特卡洛（Sequential Monte Carlo）的介绍（英文论文）

Sequential Monte Carlo in C++

RaoBlackwellisedParticleFilteringforDynamicBayesia_Bayesian_Rao

upf_demos.zip_Monte Carlo_particle filter_particle filtering_upf

Monte Carlo方法

demo3.zip_Monte Carlo_filter_particle filter_particle filtering

基于粒子滤波和SPRT的小电流单相接地选线方法

序贯滤波（sequential Kalman filter）+ MATLAB程序（简化版sins与gnss融合）

sequential-monte-carlo

随机集理论下的多目标跟踪

demorbpfdbn.zip_Bayesian_RAO_particle filter_particle filtering

demo_rbpf_gauss.zip_DEMO_RBPF_Sequential Gauss_particle filter_p

ISO 39511：2018 Sequential sampling plans for inspection by varia

ISO 28591：2017 Sequential sampling plans for inspection by attri

rjMCMCsa.rar_As One_Bayesian_de Freitas_neural matlab _rjMCMCsa

Qt 5实现串口调试助手 （源工程文件、0积分下载）

【SystemVerilog】路科验证V2学习笔记（全600页）.pdf

AutoSAR标准协议4.2.2

光伏-储能并网系统仿真.rar

NPPJSONViewer.zip

GD32替换STM32注意事项.pdf

XCP协议的规范文档

VS2015安装证书，JavaScript_ProjectSystem.msi，JavaScript_LanguageService.msi

CANoe通过CAPL脚本实现自动测试

蓝牙BLE协议中文版.pdf

Qt 5实现串口调试助手（源工程文件、0积分下载）