2.1 Introduction to the ABC method

As explained in Chapter 1, the Bayesian inverse problem aims at updating the a priori information about a set of parameters θ ∈ Θ ⊂ ℝ^d for a parameterised model class M_j, based on the available information from the system response contained in the data D ∈ D ⊂ ℝ^ℓ. This is achieved by Bayes’ theorem which yields the posterior PDF p(θ|D, M_j) of the model specified by θ in the model class M_j. However, in engineering practise, there are situations where the Bayesian inverse problem involves a likelihood function that is not completely known or it is computationally unaffordable, perhaps because it requires the evaluation of an intractable multi-dimensional integral [127]. Approximate Bayesian Computation (ABC) was conceived with the aim of evaluating the posterior PDF in those cases where the likelihood function is intractable [182]. In the Bayesian literature, such a method is also called as a likelihood-free computation algorithm, since it circumvents the explicit evaluation of the likelihood function by using a stochastic simulation approach. In this section, the method ABC is briefly described.

Let x ∈ ℝ^ℓ denote a simulated outcome from p(x|θ,M_j), the stochastic forward model for model class M_j parameterised by θ, formerly explained in Chapter 1, Equation (1.19). ABC aims at evaluating the posterior p(θ|D,M_j) ∝ p(D|θ,M_j)p(θ|M_j) by applying Bayes’ theorem to the pair (θ, x) ∈ Θ × D ⊂ ℝ^{d +ℓ}:

$p\left(\theta ,\text{x}|D\right)\propto p\left(D|x,\theta \right)p\left(x|\theta \right)p\left(\theta \right)$ (2.1)

In the last equation, the conditioning on model class M_j has been omitted for simplicity, given that the ABC theory is valid irrespective of a chosen model class. The basic form of the ABC algorithm to generate samples from the posterior given by Equation (2.1), is a rejection algorithm that consists in jointly generating θ′ ~ p(θ) and x′ ~ p(x|θ′), and accepting them conditional on the equality x′ = D being fulfilled. This is due to the fact that the PDF p(D| x, θ) in Equation (2.1) gives higher density values for the posterior in those regions where x is close to D. Of course, obtaining the sample x′ = D is unlikely in most of the cases, and it is only feasible if D consists of a finite set of values rather than a continuous region in ℝ^ℓ. To address the above difficulty, two main approximations have been conceived in ABC theory [128]: a) replace the equality x = D by the approximation x ≈ D and introduce a tolerance parameter ϵ that accounts for the quality of such approximation through a suitable metric ρ; and b) introduce a low-dimensional vector of summary statistics η(·) that allows a weak comparison of the closeness between x and D. Through this approach, the posterior p(θ, x|D) in Equation (2.1) is approximated by p_ϵ(θ, x|D), which assigns higher probability density to those values of (θ, x) ∈ Θ × D that satisfy the condition ρ(η(x), η(D) ≤ ϵ.

The standard version of the ABC algorithm defines an approximate likelihood function given by p_ϵ(D|θ, x) ≜ P(x ∈ B_ϵ(D)|θ, x) [46], where B_ϵ(D) is a region of the data space D defined as

$B_{ϵ}\left(D\right)=\left\{x\in D:\rho \left(\eta \left(x\right),\eta \left(D\right)\right)\le ϵ\right\}$ (2.2)

In the expression of the approximate likelihood function and also in what follows, p(·) is adopted to denote probability whereas p(·) denotes a PDF. Thus, from Bayes’ theorem, the approximate posterior p_ϵ(θ, x|D) can be obtained as

$p_{ϵ}\left(\theta ,\text{x}|D\right)\propto P\left(x\in {{\rm B}}_{ϵ}\left(D\right)|x,\theta \right)p\left(x|\theta \right)p\left(\theta \right)$ (2.3)

The approximate likelihood can be formulated as P(x ∈ B_ϵ(D)|x, θ) = I_Bϵ(D) (x), with I_Bϵ(D) (x) being an indicator function for the set B_ϵ(D) that assigns the unity when ρ(η(x), η(D)) ≤ ϵ, and 0 otherwise. It follows that the approximate posterior p_ϵ(θ, x|D) can be readily computed as

$p_{ϵ}\left(\theta ,\text{x}|D\right)\propto p\left(x|\theta \right)p\left(x|\theta \right)I{I}_{B_{ϵ\left(D\right)}}\left(x\right)$ (2.4)

Since the ultimate interest of the Bayesian inverse problem is typically the posterior of model parameters p_ϵ(θ|D), it can be obtained by marginalising the approximate posterior PDF in Equation (2.4)

$p_{ϵ}\left(\theta |D\right)\propto p\left(\theta \right){\displaystyle {\int }_{D}p\left(x|\theta \right)I{I}_{B_{ϵ\left(D\right)}}\left(x\right)dx}=P{\left(x\in B_{ϵ}\left(D\right)|\theta \right)}_p\left(\theta \right)$ (2.5)

Note that this integration need not be done explicitly since samples from this marginal PDF are obtained by taking the θ-component of the samples from the joint PDF in Equation (2.4) [151]. A pseudo-code implementation of ABC algorithm is given below as Algorithm 3.

Example 4 Let us consider a 2 [m] length column with 0.4 [m] square cross section, which is loaded with F = 1 [kN] at the top, as illustrated in Figure 2.1. Let also consider that, for some reason, the column is made of a degrading material so that its Young’s modulus decreases at an unknown constant rate ξ from an initial value E₀ = 40 [MPa], such that

$E_n=e^{-\xi }{E}_{n-1}+{\nu }_n$ (2.6)

where E_n is the Young’s modulus at time or instant n ∈ ℕ expressed in weeks, and vn is an unknown model error term, which is assumed to be distributed as a zero-mean Gaussian with uncertain standard deviation, that is, v_n ~ N (0, σ). Next, a sensor is assumed to be placed at the top of the column to register deflections, and the following measurement equation can be considered:

${\delta }_n=f\left(E_n\right)+w_n$ (2.7)

where f : ℝ_≥0 → ℝ_≥0 is a mathematical function that provides the deflection of the column as a function of En. Assuming the linear elasticity theory, this function can be expressed as f = $\frac{F{L}^3}{3E_{n}I},$ where I is the inertia momentum of the cross section. In Equation (2.7), the term w_n is the measurement error, which is assumed to be negligible as compared to the model error term, so that it is subsumed into the error term v_n. In this example, the degradation rate and the standard deviation of the error term are selected as the uncertain model parameters, so that θ = {θ₁, θ₂} = {ξ, σ}, whose prior information can be represented by the uniform piece-wise PDFs p(θ₁) = U [0.0001, 0.02], and p(θ₂) = U[0.01, 2], respectively. The data in this example are given as a recorded time-history of deflections over a period of time T = 200 weeks, that is, D = {δ_n,meas}_n=0²⁰⁰. These data are synthetically generated from Equations (2.6) and (2.7) considering θ_true = (0.005, 0.1), shown in Figure (2.2), panels (a) and (b). The ABC-rejection algorithm is adopted with K = 20, 000 samples to obtain the approximate posterior of θ based on the referred data. The results are shown in Figure 2.2c.

In Figure 2.2, the grey circles represent samples from the prior, whilst the darker-colored circles represent samples from θ distributed according to the approximate posterior PDF p_ϵ(θ|D) (recall Eq. (2.5)), where ϵ = 1100, using a ℓ₁ distance as metric, that is $\rho ={\displaystyle {\sum }_{n=0}^{200}\Vert E_{n,true}-E_n\Vert }.$ A total amount of 5, 000 samples lie within the approximate posterior samples, which populate a region close to the θ_true values. Observe that, in average, the approximate posterior gives us a region of plausible values of θ ≈ θ_true, which in view of Figure 2.2 is relatively large. Hence, better results would be expected if smaller ϵ values are considered, as will be shown further below.

Note that the quality of the posterior approximation in ABC depends on a suitable selection of the metric ρ, the tolerance parameter ϵ and, of special importance, the summary statistic η(·) [65]. The choice of the tolerance parameter ϵ is basically a matter of the amount of computational effort that the modeller is willing to expend. Indeed, for ϵ sufficiently small η(x′) → η(D), and thus all accepted samples simulated according to Equation (2.5) come from the closest approximation to the posterior density p(θ|D), where the exactness is achieved when η(·) is a sufficient statistic. This desirable fact is at the expense of a high computational effort to get η(x′) = η(D) under the stochastic forward model p(x|θ,M_j), usually prohibitive. On the contrary, as ϵ → ∞, all accepted simulations x′ come from the prior density. Hence, the choice of the tolerance parameter ϵ reflects a trade-off between computational cost and accuracy of the ABC posterior approximation.

For that reason, several computational improvements have been proposed in the literature addressing this trade-off. Among them, combining ABC with MCMC methods (commonly called the ABC-MCMC method) has demonstrated to be efficient [128] in those cases where the probability content of the posterior is concentrated over a small region in relation to a diffuse prior. In fact, in ABC-MCMC, a proposal PDF q(θ′ |θ^(ζ)) is used to sample a new parameter θ′ based on a previous accepted one θ^(ζ), targeting the stationary distribution p_ϵ(θ|D). A pseudo-code is provided below as Algorithm 4.

It should be noted that when the likelihood function is approximated as p_ϵ(D| x, θ) = I_Bϵ(D) (x), as in our case, the acceptance probability α (Step 3 in Algorithm 4) can be rewritten as the product of a MCMC acceptance ratio and the indicator function as follows

$\alpha =\min \left\{1,\frac{p\left({\theta }^{\prime }\right)q\left({\theta }^{n-1}\right)|{\theta }^{\prime }}{p\left({\theta }^{\left(n-1\right)}\right)q\left({\theta }^{\prime }|{\theta }^{\left(n-1\right)}\right)}\right\}I{I}_{B_{ϵ\left(D\right)}}\left(x^{\prime }\right)$ (2.8)

where Equation (2.8) clearly shows that the dependence upon ϵ in the indicator function may lead to an inefficient algorithm for a good approximation of the true posterior. In fact, given that α can only be non-zero if I_Bϵ(D) (x′) = 1 (i.e. ρ(η(x′), η(D)) ≤ ϵ), then the Markov chain may persist in distributional tails for long periods of time if ϵ is sufficiently small, due to the acceptance probability being zero in Step 3 of Algorithm 4. Again, despite some attempts to effectively overcome this limitation [28, 169], the desirable fact ϵ → 0 in ABC again implies heavy computation.

For that reason, a branch of computational techniques have emerged in the literature to obtain high accuracy (ϵ → 0) with a feasible computational cost by combining sequential sampling algorithms adapted for ABC [55]. These techniques share a common principle of achieving computational efficiency by learning about intermediate target distributions determined by a decreasing sequence of tolerance levels ϵ₁ > ϵ₂ > ;… > ϵ_m = ϵ, where the last is the desired tolerance ϵ. The reader is referred to [46] for an overview of the main contributions to the literature on this topic. Within the available methods, the so-called ABC-SubSim algorithm published by Chiachío et al. in [46] has demonstrated efficiency as compared with the available ABC algorithms in the literature [188]. The methodological bases of ABC-SubSim algorithm are provided below.

Subset Simulation (SS) [14] is an efficient method for simulation of rare-events in high-dimensional spaces, which makes this method applicable to a broad range of areas of science and engineering [17, 47]. By Subset Simulation, conditional samples can be efficiently generated corresponding to specified levels of a performance function g : Z ⊂ ℝ^d → ℝ in a progressive manner, converting a problem involving rare-event simulation into a sequence of problems involving higher probability events [14]. This method was originally proposed to compute small failure probabilities encountered in reliability analysis of engineering systems (e.g. [16, 47]). For illustration purposes, the Subset Simulation method is presented in this section using its primary aim of small failure probabilities estimation. In the next section, it will be specialised for ABC simulation.

Let us consider that F is a failure region in a z-space, corresponding to the exceedance of the performance function g above some specified threshold value b

$F=\left\{z\in {\rm Z}:\text{g}\left(z\right)>b\right\}$ (2.9)

Let us now assume that F can be defined as the intersection of m regions F = ∩_j=1^m F_j, such that they are arranged as a nested sequence F₁ ⊃ F₂ … ⊃ F_m−1 ⊃ F_m = F, where F_j = {z ∈ Z : g(z) > b_j}, with b_j+1 > b_j, such that p(z_j|F_j) ∝ p(z)IF_j (z), j = 1,…, m. The term p(z) is to denote the probability model for z. When the event F_j holds, then {F_j−1,…,F₁} also hold, henceforth P(F_j|F_j−1,…,F₁) = P(F_j|F_j−1), so that

$P\left(F\right)=P\left({\displaystyle \underset{j=1}{\overset{m}{\cap }}{F}_j}\right)=P\left(F_1\right)={\displaystyle \prod _{j=1}^{m}P\left(F_j|F_{j-1}\right)}$ (2.10)

where, for simpler notation, we use P(F) ≜ P(z ∈ F) and P(F_j|F_j−1) ≜ P(z ∈ F_j | z ∈ F_j−1), with P(z ∈ F_j|z ∈ F_j−1) being the conditional failure probability at the (j−1)^th conditional level. Notice that although the probability P(F) can be relatively small, by choosing the intermediate regions appropriately, the conditional probabilities involved in Equation (2.10) can be made large, thus avoiding the simulation of rare events.

In the last equation, apart from P(F₁) (which can be readily estimated by the standard Monte Carlo method (MC)), the remaining factors cannot be efficiently estimated because of the conditional sampling involved. However, MCMC methods can be used for sampling from the PDF p(z_j−1|F_j−1) when j ≥ 2, although it is at the expense of generating K-dependent samples, giving

$P\left(F_j|F_{j-1}\right)\approx {\overline{P}}_j=\frac{1}{K}{\displaystyle \sum _{k=1}^{K}I{I}_{F_j}\left(z_{j-1}^{\left(k\right)}\right),}{z}_{j-1}^{\left(k\right)}\sim p\left(z_{j-1}|F_{j-1}\right)$ (2.11)

where IF_j(z_j−1^(k)) is the indicator function for the region F_j, j = 1,…, m, that assigns a value 1 when g(z_j−1^(k)) > b_j, and 0 otherwise. Observe that it is possible to obtain Markov chain samples that are generated at the (j −1)th level which lie in F_j, so that they are distributed as p(·|F_j). Hence these samples provide “seeds” for generating more samples according to p(z_j|F_j) by using MCMC sampling. Because of the way the seeds are chosen, Subset Simulation exhibits the benefits of perfect sampling [207, 151] which is an important feature to avoid wasting samples during a burn-in period, in contrast to other MCMC algorithms such as the MH algorithm.

As explained below, F_j is actually chosen adaptively based on the samples {z_j−1^(k), k = 1,…, K} from p(z|F_j−1) in such a way that there are exactly NP₀ of these samples in F_j (so P̄_j = P₀ in Equation (2.11). Next, MCMC is applied to obtain (¹/P_{0 − 1}) samples from p(z_j|F_j) starting at each seed, so that a total of N samples are obtained in F_j. Repeating this process, one can compute the conditional probabilities of the higher-conditional levels until the final region of interest F_m = F has been reached. Note that the intermediate threshold value b_j defining F_j is obtained in an adaptive manner as the [(1 − P₀)K]_th largest value of the sample values g(z_j−1^(k)), k = 1,…, K, in such a way that the sample estimate of P(F_j|F_j−1) in Equation (2.11) is equal to P₀. See Figure 2.3 for an illustrative example of the Subset Simulation method.

In Figure 2.3, panels (a) & (b) represent the initial set of samples of dimension two simulated according to any specified model, and the selection of seeds whereby F₁ is defined, respectively. In panel (c), new samples simulated according to p(z|F₁) are represented along with the seeds for defining the subsequent intermediate failure region, which is represented using samples in panel (d). Panel (e) represents the final step where the whole set of samples arranged through subsets is showed along with the sequence of intermediate threshold levels until the final one (solid line) is reached.

It should be noted that the choice of an adequate P₀ has a significant impact on the efficiency of Subset Simulation. Indeed, a small value for the conditional probability (P₀ → 0) ensures that the distance between consecutive intermediate levels b_j − b_j−1 becomes too large, which leads to a rare-event simulation problem. If, on the contrary, the intermediate threshold values were chosen too close (P₀ → 1), the algorithm would require more simulation levels m (and hence, large computational effort) to progress towards F. In the literature about Subset Simulation, several works have reported about the scaling strategies for P₀. The value P₀ = 0.1 was recommended in the original presentation of Subset Simulation [14], and more recently in [207], the range 0.1 ≤ P₀ ≤ 0.3 was proposed as near optimal range of values after a rigorous sensitivity study of Subset Simulation.

As stated before, to draw samples from the conditional PDF p(z_j|F_j), MCMC methods like Metropolis-Hastings [131] are adequate. In the original version of Subset Simulation [14], the Modified Metropolis Algorithm (MMA) was proposed and it was shown to work well for very high dimensions (e.g. 10³ - 10⁴). In MMA, a univariate proposal PDF is chosen for each component of the parameter vector and each candidate component is accepted or rejected separately, instead of drawing a full parameter vector from a multi-dimensional PDF as in the original algorithm. Later in [16], grouping of the parameters was considered when constructing a proposal PDF to allow for the case where small groups of components in the parameter vector are highly correlated. An appropriate choice for the proposal PDF for ABC-SubSim is introduced in the next section. Further insights for Subset Simulation using MMA as a conditional sampler are provided by Zuev et al. [207] where an exhaustive sensitivity study of MMA is presented along with enhancements for the Subset Simulation method.

2.3 The ABC-SubSim algorithm

The ABC-SubSim algorithm was conceived by combining the ABC principles with the technique of Subset Simulation for efficient rare-event simulation, first developed by Au and Beck [14]. Algorithm 5 provides a pseudo-code implementation of ABC-SubSim that is intended to be sufficient for most applications. The algorithm is implemented such that a maximum allowable number of simulation levels (m) is considered in case the specified ϵ is too small. Recent improvements for adaptive selecting ϵ have appeared in the literature [186, 187]

One of the key aspects of ABC-SubSim is the selection of the ϵ_j values. Indeed, these values are adaptively chosen as in Subset Simulation [14], so that the sample estimate P̄_j of P(Z_j|Z_j−1) satisfies P̄_j = P₀ [46]. By this way, the intermediate tolerance value ϵ_j can be simply obtained as the 100P₀ percentile of the set of distances given by ρ(η(x_j−1^(k), η(D)), k = 1,…, K, arranged in increasing order. Moreover, observe in Algorithm 5 that P₀ is chosen such that KP₀ and ¹/P₀ are integers, and so the size of the subset of samples generated in Z_j−1 that lie in Z_j is known in advance and equal to KP₀, which provides a significant advantage for the implementation. These KP₀ samples in Z_j are used as seeds for KP₀ Markov chains of length $\frac{1}{P_0},$ where the new $\left(\frac{1}{P_0}-1\right)$ samples in Z_j in each chain can be readily generated by MMA [14]. Hence the total number of samples of (θ, x) lying in Z_j is K, but KP₀ of them were generated at the (j −1)^th level. Because of the way the seeds are chosen, ABC-SubSim exhibits the benefits of perfect sampling [207, 151], which is an important feature to avoid wasting samples during a burn-in period, in contrast to ABC-MCMC.

Finally, it is important to remark that the important control parameters to be chosen in ABC-SubSim are P₀ and σ^(j)_q, the standard deviation in the Gaussian proposal PDF in MMA at the j^th level. For P₀, the recommendation is to choose it within the interval [0.1, 0.3], and more specifically P₀ = 0.2 [46]. In regards to the optimal variance of the local proposal PDF for the MMA sampler, the rule is to adaptively choose the standard deviation σ^(j)_q of the j^th intermediate level so that the monitored acceptance rate lies within the interval [0.2, 0.4] based on an initial chain sample of small length (e.g. 10 states). The reader is referred to [186] for a detailed study about adaptive scaling of the ABC-SubSim algorithm, and also to [207], where the optimal scaling is addressed for the general Subset Simulation method.

Example 5 Let us consider again the example of the column given in Example 4. In this case, we want to obtain samples from the posterior θ ~ p_ϵ(θ|D), where ϵ is much smaller than that obtained in Example 4. The ABC-SubSim algorithm is used with K = 5, 000, P₀ = 0.2, and m = 4 simulation levels, so that the final subset produces K = 5, 000 samples distributed according to p_ϵm (θ|D). The results are shown in Figure 2.4. In Figure 2.4c, the intermediate posterior samples are superimposed in increasing gray tones to reveal the uncertainty reduction. The final subset is depicted using darker circles. ABC-SubSim uses 17,000 simulations to generate 5,000 samples representing a final posterior that is better aligned with the values of θ_true. Moreover, to demonstrate the efficacy of the algorithm, the model is evaluated by picking a sample θ̂^ABC-SS from p_ϵ(θ|D). Recall that in both cases, the final posterior has the same amount of samples, namely, 5,000 samples. The results for stiffness and deflections are presented superimposed in Figures 2.4a and 2.4b for better interpretation. Note that the results are very satisfactory in the sense that ABC-SubSim can reconstruct the true structural behaviour with high precision in comparison with the ABC-rejection algorithm with the same computational cost. In fact, in both cases, the computational burden of the algorithms are almost equivalent (indeed, ABC-SubSim uses 17,000 samples to produce a final posterior of 5,000 samples, whilst ABC-rejection needs 20,000), while the accuracy obtained by ABCSubSim is, by far, superior to ABC-rejection, which corroborates the findings originally observed in [46].

2.4 Summary

This chapter has shown that ABC methods are efficient for giving a solution to inverse problems where the likelihood function is unknown or directly computationally intractable. The resulting posterior PDF is obtained for a given tolerance value which provides a measure of how close the simulations are obtained using the posterior samples with respect to the data. The original ABC (rejection) algorithm is shown to be simple to implement but computationally inefficient overall when small tolerance values are adopted. Since the publication of the first ABC methodology, new ABC variants have been proposed to tackle the computational costs when adopting small tolerances, with the ABC-SubSim being a highly efficient one, based on the study published in [46], and further corroborated in works like [186, 188]. The ABC-SubSim algorithm has been explained in this chapter within the context of a structural engineering example based on a cantilever column under a constant lateral load, whose material is subject to a degradation process. The algorithm has been able to infer the damage model parameters with high fidelity with a reasonable computational cost irrespective of the big uncertainty considered. Moreover, the ABC-SubSim algorithm has been compared with the former ABC-rejection algorithm under similar computational cost, showing that ABC-SubSim can obtain a much finer posterior inference. Further research should be focused on investigating ways to adaptively scale the ABC-SubSim meta parameters, which have a strong influence on the posterior quality and the computational cost. Also, another fruitful research would be to explore the use of ABC-SubSim as a surrogate model for the evaluation of complex degradation engineering processes where multidimensional model parameters are involved.