Signal Processing - July 2017 - 66

t=1

0.4

π (x )
q1(x )

0.2
0
-10

-5

0
x

5

t=2

0.2

π (x )
q2(x )

0.1
0
-10

10

-5

0
x

5

10

t=3

0.15

π (x )

0.1

q3(x )

0.05
0
-10

-5

0
x

5

10

FIGURE 3. A proposal adaptation through AIS. The initial proposal q 1 (x)

(too narrow and poorly placed) is iteratively moved toward a better location at some intermediate location between the two modes of the target
pdf and widened to properly cover the effective support of the target.

Hence, the self-normalized AIS estimator is IuKNJ = R Jj = 1
(k)
(k)
R nN= 1 R Kk = 1 wr n, j f (x n, j).

Modern AIS methods
AIS methods got their turn in the spotlight of MC computations after the publication of the population MC (PMC)
sampling method by Cappé et al. in 2004 [19], notwithstanding
the existence of several AIS schemes at that time (see [28]
for a review). The PMC methodology offered a framework to
adapt a population of proposals that was simple, flexible, and
free from the convergence and ergodicity issues of adaptive
MCMC techniques. The original PMC algorithm used a
multinomial resampling stage (note that any of the better
alternative resampling strategies developed for particle filters can also be used [29]) and was unstable due to the use
of the s-MIS weighting strategy of (15). However, the proposed approach raised a considerable interest within the
computational statistics community, and improved PMC
algorithms shortly followed, like the D-kernel PMC [30],
[31] or the mixture PMC (M-PMC) [20]. Furthermore, several authors have recently shown that the performance of
PMC can be improved even more through the use of a nonlinear transformation of the weights [32] or the combination
of the DM weighting scheme of (16) and sophisticated resampling schemes [24].
On the other hand, encouraged by the renewed interest in
AIS methods spurred by the PMC approach, several authors
66

have proposed AIS algorithms that do not fall within the PMC
framework. For instance, the idea of incremental IS mixtures
[originally proposed in (33)] was taken up again by Cornuet
et al. in the adaptive MIS (AMIS) method [21]. AMIS uses
a single proposal per iteration, but applies the DM weighting
scheme of (16) using a mixture composed of the present and
all past proposal pdfs. Much more robust and stable estimators
are thus obtained, but at the expense of a substantial increase in
the computational cost. An alternative to AMIS is the recently
proposed adaptive population IS (APIS) algorithm [22]. APIS
is also based on the DM weighting scheme of (16), but it uses a
mixture with a fixed number of proposals per iteration. In this
way, APIS inherits the robustness and stability of AMIS but
with the benefit of allowing a user-controllable computational
cost that does not increase as the algorithm is iterated. Moreover, gradient information can be incorporated to the APIS
algorithm to improve the performance in high-dimensional
state spaces [34].
Finally, note that the combination of MCMC and AIS techniques has also been considered in several works. For instance,
MCMC steps can be used to accelerate the adaptation of the
AIS technique [22], or the MCMC outputs can be used to build
a proposal distribution for AIS estimation [35]. Sequential MC
samplers have also been suggested as AIS schemes in static
scenarios [36].

Implementation and classification of AIS algorithms
Implementation of AIS algorithms
Many important AIS algorithms have been proposed in the literature in the last two decades. In this section, we describe in
detail some of the most popular AIS algorithms.
■ Standard PMC [19]: In this algorithm, N proposals are
adapted via resampling, which is a well-known mechanism
in MC methodologies that allows us to select the most
promising samples and to eliminate those with low weights
to avoid particle degeneracy [29]. At each iteration, exactly
one sample is drawn from each proposal and weighted
with the standard IS weights calculated by (15). Then, N
multinomial resampling steps (with replacement) are performed within the population of the N drawn samples (one
sample is generated per proposal, i.e., K = 1). The surviving set of particles constitutes the set of location parameters for the next population of proposals.
■ M-PMC [20]: For this method, the proposal used to generate K samples at each iteration is a mixture of N kernels,
where the mixture is adapted to decrease the Kullback-
Leibler (KL) divergence between the mixture and the
target. In its simplest version, the algorithm adapts the
location, scale, and weight of each kernel in the mixture.
■ Nonlinear PMC (N-PMC) [32]: In this algorithm, the
weights are computed in two steps. First, standard impor(k)
tance weights w j are obtained. Then, a nonlinear function is applied to calculate a set of transformed weights
(k)
w{ j . The goal of this transformation is to reduce the variance of the weights and avoid, or at least mitigate, the

IEEE SIGNAL PROCESSING MAGAZINE

|

July 2017

|



Table of Contents for the Digital Edition of Signal Processing - July 2017

Signal Processing - July 2017 - Cover1
Signal Processing - July 2017 - Cover2
Signal Processing - July 2017 - 1
Signal Processing - July 2017 - 2
Signal Processing - July 2017 - 3
Signal Processing - July 2017 - 4
Signal Processing - July 2017 - 5
Signal Processing - July 2017 - 6
Signal Processing - July 2017 - 7
Signal Processing - July 2017 - 8
Signal Processing - July 2017 - 9
Signal Processing - July 2017 - 10
Signal Processing - July 2017 - 11
Signal Processing - July 2017 - 12
Signal Processing - July 2017 - 13
Signal Processing - July 2017 - 14
Signal Processing - July 2017 - 15
Signal Processing - July 2017 - 16
Signal Processing - July 2017 - 17
Signal Processing - July 2017 - 18
Signal Processing - July 2017 - 19
Signal Processing - July 2017 - 20
Signal Processing - July 2017 - 21
Signal Processing - July 2017 - 22
Signal Processing - July 2017 - 23
Signal Processing - July 2017 - 24
Signal Processing - July 2017 - 25
Signal Processing - July 2017 - 26
Signal Processing - July 2017 - 27
Signal Processing - July 2017 - 28
Signal Processing - July 2017 - 29
Signal Processing - July 2017 - 30
Signal Processing - July 2017 - 31
Signal Processing - July 2017 - 32
Signal Processing - July 2017 - 33
Signal Processing - July 2017 - 34
Signal Processing - July 2017 - 35
Signal Processing - July 2017 - 36
Signal Processing - July 2017 - 37
Signal Processing - July 2017 - 38
Signal Processing - July 2017 - 39
Signal Processing - July 2017 - 40
Signal Processing - July 2017 - 41
Signal Processing - July 2017 - 42
Signal Processing - July 2017 - 43
Signal Processing - July 2017 - 44
Signal Processing - July 2017 - 45
Signal Processing - July 2017 - 46
Signal Processing - July 2017 - 47
Signal Processing - July 2017 - 48
Signal Processing - July 2017 - 49
Signal Processing - July 2017 - 50
Signal Processing - July 2017 - 51
Signal Processing - July 2017 - 52
Signal Processing - July 2017 - 53
Signal Processing - July 2017 - 54
Signal Processing - July 2017 - 55
Signal Processing - July 2017 - 56
Signal Processing - July 2017 - 57
Signal Processing - July 2017 - 58
Signal Processing - July 2017 - 59
Signal Processing - July 2017 - 60
Signal Processing - July 2017 - 61
Signal Processing - July 2017 - 62
Signal Processing - July 2017 - 63
Signal Processing - July 2017 - 64
Signal Processing - July 2017 - 65
Signal Processing - July 2017 - 66
Signal Processing - July 2017 - 67
Signal Processing - July 2017 - 68
Signal Processing - July 2017 - 69
Signal Processing - July 2017 - 70
Signal Processing - July 2017 - 71
Signal Processing - July 2017 - 72
Signal Processing - July 2017 - 73
Signal Processing - July 2017 - 74
Signal Processing - July 2017 - 75
Signal Processing - July 2017 - 76
Signal Processing - July 2017 - 77
Signal Processing - July 2017 - 78
Signal Processing - July 2017 - 79
Signal Processing - July 2017 - 80
Signal Processing - July 2017 - 81
Signal Processing - July 2017 - 82
Signal Processing - July 2017 - 83
Signal Processing - July 2017 - 84
Signal Processing - July 2017 - 85
Signal Processing - July 2017 - 86
Signal Processing - July 2017 - 87
Signal Processing - July 2017 - 88
Signal Processing - July 2017 - 89
Signal Processing - July 2017 - 90
Signal Processing - July 2017 - 91
Signal Processing - July 2017 - 92
Signal Processing - July 2017 - 93
Signal Processing - July 2017 - 94
Signal Processing - July 2017 - 95
Signal Processing - July 2017 - 96
Signal Processing - July 2017 - 97
Signal Processing - July 2017 - 98
Signal Processing - July 2017 - 99
Signal Processing - July 2017 - 100
Signal Processing - July 2017 - 101
Signal Processing - July 2017 - 102
Signal Processing - July 2017 - 103
Signal Processing - July 2017 - 104
Signal Processing - July 2017 - 105
Signal Processing - July 2017 - 106
Signal Processing - July 2017 - 107
Signal Processing - July 2017 - 108
Signal Processing - July 2017 - 109
Signal Processing - July 2017 - 110
Signal Processing - July 2017 - 111
Signal Processing - July 2017 - 112
Signal Processing - July 2017 - 113
Signal Processing - July 2017 - 114
Signal Processing - July 2017 - 115
Signal Processing - July 2017 - 116
Signal Processing - July 2017 - 117
Signal Processing - July 2017 - 118
Signal Processing - July 2017 - 119
Signal Processing - July 2017 - 120
Signal Processing - July 2017 - 121
Signal Processing - July 2017 - 122
Signal Processing - July 2017 - 123
Signal Processing - July 2017 - 124
Signal Processing - July 2017 - 125
Signal Processing - July 2017 - 126
Signal Processing - July 2017 - 127
Signal Processing - July 2017 - 128
Signal Processing - July 2017 - 129
Signal Processing - July 2017 - 130
Signal Processing - July 2017 - 131
Signal Processing - July 2017 - 132
Signal Processing - July 2017 - 133
Signal Processing - July 2017 - 134
Signal Processing - July 2017 - 135
Signal Processing - July 2017 - 136
Signal Processing - July 2017 - 137
Signal Processing - July 2017 - 138
Signal Processing - July 2017 - 139
Signal Processing - July 2017 - 140
Signal Processing - July 2017 - 141
Signal Processing - July 2017 - 142
Signal Processing - July 2017 - 143
Signal Processing - July 2017 - 144
Signal Processing - July 2017 - 145
Signal Processing - July 2017 - 146
Signal Processing - July 2017 - 147
Signal Processing - July 2017 - 148
Signal Processing - July 2017 - 149
Signal Processing - July 2017 - 150
Signal Processing - July 2017 - 151
Signal Processing - July 2017 - 152
Signal Processing - July 2017 - 153
Signal Processing - July 2017 - 154
Signal Processing - July 2017 - 155
Signal Processing - July 2017 - 156
Signal Processing - July 2017 - 157
Signal Processing - July 2017 - 158
Signal Processing - July 2017 - 159
Signal Processing - July 2017 - 160
Signal Processing - July 2017 - 161
Signal Processing - July 2017 - 162
Signal Processing - July 2017 - 163
Signal Processing - July 2017 - 164
Signal Processing - July 2017 - 165
Signal Processing - July 2017 - 166
Signal Processing - July 2017 - 167
Signal Processing - July 2017 - 168
Signal Processing - July 2017 - 169
Signal Processing - July 2017 - 170
Signal Processing - July 2017 - 171
Signal Processing - July 2017 - 172
Signal Processing - July 2017 - 173
Signal Processing - July 2017 - 174
Signal Processing - July 2017 - 175
Signal Processing - July 2017 - 176
Signal Processing - July 2017 - 177
Signal Processing - July 2017 - 178
Signal Processing - July 2017 - 179
Signal Processing - July 2017 - 180
Signal Processing - July 2017 - 181
Signal Processing - July 2017 - 182
Signal Processing - July 2017 - 183
Signal Processing - July 2017 - 184
Signal Processing - July 2017 - 185
Signal Processing - July 2017 - 186
Signal Processing - July 2017 - 187
Signal Processing - July 2017 - 188
Signal Processing - July 2017 - 189
Signal Processing - July 2017 - 190
Signal Processing - July 2017 - 191
Signal Processing - July 2017 - 192
Signal Processing - July 2017 - 193
Signal Processing - July 2017 - 194
Signal Processing - July 2017 - 195
Signal Processing - July 2017 - 196
Signal Processing - July 2017 - Cover3
Signal Processing - July 2017 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201809
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201807
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201805
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201803
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201801
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0917
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0717
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0517
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0317
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0916
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0716
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0516
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0316
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0915
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0715
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0515
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0315
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0914
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0714
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0514
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0314
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0913
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0713
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0513
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0313
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0912
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0712
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0512
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0312
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0911
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0711
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0511
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0311
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0910
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0710
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0510
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0310
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0909
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0709
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0509
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0309
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1108
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0908
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0708
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0508
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0308
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0108
https://www.nxtbookmedia.com