A fast and scalable computational framework for large-scale and high-dimensional Bayesian optimal experimental design

Keyi Wu, Peng Chen, Omar GhattasarXiv 2020 · OpenReview

TL;DR

This paper introduces a novel computational framework for designing optimal experiments in complex, high-dimensional systems governed by partial differential equations (PDEs). By cleverly exploiting the structure of the problem and employing an offline-online decomposition, they significantly speed up the process of determining the best sensor locations for Bayesian inference, making it scalable to thousands of parameters and data points.

What Problem Does This Paper Address?

Designing optimal experiments, particularly for inferring parameters in complex models like those described by PDEs, is a computationally intensive task. The goal is to strategically place sensors to gather the most informative data, thereby reducing uncertainty in our understanding of the system. This is often framed as maximizing the "expected information gain" (EIG). However, this problem becomes incredibly challenging when:

  • High-dimensional parameters: The system's behavior depends on a vast number of unknown parameters (e.g., material properties across a large domain).
  • Large-scale PDEs: Simulating the system requires solving computationally expensive PDEs.
  • Curse of dimensionality: The number of possible sensor configurations grows exponentially with the number of potential locations, making exhaustive search infeasible.

Existing methods often struggle with these challenges, requiring an prohibitive number of PDE solves for each potential experimental design.

Methods

The authors propose a framework that tackles these challenges through several key innovations:

  • Offline-Online Decomposition: This is a central theme. The computationally expensive parts, which depend on the underlying physics (PDEs) but not on the specific sensor placement, are done offline. This includes calculating quantities related to the parameter-to-observable map and its Jacobian. The online stage then uses these pre-computed results to optimize sensor placement without needing to solve any PDEs.
  • Low-Rank Approximation of the Hessian: They exploit the fact that for many high-dimensional inverse problems, the information gained from data is concentrated in a low-dimensional subspace. This allows them to approximate the Hessian of the problem using a low-rank representation, significantly reducing computational cost. This is achieved using a randomized SVD algorithm.
  • Swapping Greedy Algorithm: For the online sensor placement optimization, they introduce a "swapping greedy" algorithm. Instead of simply adding sensors one by one (standard greedy), this algorithm starts with an initial set of sensors (chosen based on "leverage scores" derived from the low-rank approximation) and then iteratively swaps sensors to improve the EIG. This is more robust than a purely additive approach.
  • Approximations for Nonlinear Problems: For nonlinear inverse problems, they introduce further approximations like Laplace approximation, fixed MAP point approximation, and prior sample point approximation to make the EIG evaluation computationally tractable.

Datasets

The paper uses synthetic data generated from simulated physical models for evaluation. Specifically:

  • Linear Inverse Problem: An advection-diffusion equation with an unknown initial condition.
  • Nonlinear Inverse Problem: A log-normal diffusion equation with an unknown diffusion coefficient.

No new benchmark datasets are introduced; rather, the authors demonstrate their method on well-defined PDE-governed inverse problems.

Key Insights and Ideas

  • The "Data-Informed Subspace" is Key: The core idea is that in high-dimensional inverse problems, only a small subspace of the parameters is actually informed by the data. Identifying and exploiting this subspace is crucial for scalability.
  • Offline Precomputation Pays Off: By separating the physics-driven computations (offline) from the sensor placement optimization (online), the framework drastically reduces the cost of evaluating different sensor configurations.
  • Swapping is Better Than Just Adding: The swapping greedy algorithm, by allowing for the removal and replacement of sensors, offers a more refined optimization than simple greedy addition, leading to better or comparable results.
  • Leverage Scores as a Smart Starting Point: Using leverage scores to initialize the greedy algorithm provides a good initial guess, likely capturing informative sensor locations early on.

Key Results

The paper demonstrates significant improvements in efficiency and scalability:

  • Efficiency: The proposed framework requires a limited number of PDE solves, making it orders of magnitude faster than traditional methods for large-scale problems.
  • Scalability: The computational complexity is shown to be largely independent of the parameter and data dimensions, allowing for problems with thousands of parameters and sensor locations.
  • Performance: In numerical experiments, both linear and nonlinear inverse problems were solved efficiently. The swapping greedy algorithm consistently found optimal or near-optimal sensor placements, outperforming random choices and often matching or exceeding the standard greedy approach. For instance, in one case, the swapping greedy algorithm achieved results comparable to the optimal design, while random designs led to a 7-53% increase in averaged variance.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • Gaussian Assumptions: The framework relies on Gaussian prior distributions and Gaussian additive noise. Extending it to non-Gaussian scenarios would be valuable.
  • Approximations for Nonlinear Problems: While effective, the approximations used for nonlinear problems (Laplace, fixed MAP, prior sample) are still approximations. Their accuracy might be limited in cases where Laplace approximation is not suitable (e.g., Helmholtz equations).
  • Theoretical Guarantees: While the greedy algorithm has theoretical guarantees for submodular functions, further theoretical analysis for the non-submodular cases encountered here would be beneficial.
  • Adaptive Sensor Selection: The current work assumes a fixed number of sensors. Future work could involve adaptively determining the optimal number of sensors needed.

Summary updated

Abstract

We develop a fast and scalable computational framework to solve large-scale and high-dimensional Bayesian optimal experimental design problems. In particular, we consider the problem of optimal observation sensor placement for Bayesian inference of high-dimensional parameters governed by partial differential equations (PDEs), which is formulated as an optimization problem that seeks to maximize an expected information gain (EIG). Such optimization problems are particularly challenging due to the curse of dimensionality for high-dimensional parameters and the expensive solution of large-scale PDEs. To address these challenges, we exploit two essential properties of such problems: the low-rank structure of the Jacobian of the parameter-to-observable map to extract the intrinsically low-dimensional data-informed subspace, and the high correlation of the approximate EIGs by a series of approximations to reduce the number of PDE solves. We propose an efficient offline-online decomposition for the optimization problem: an offline stage of computing all the quantities that require a limited number of PDE solves independent of parameter and data dimensions, and an online stage of optimizing sensor placement that does not require any PDE solve. For the online optimization, we propose a swapping greedy algorithm that first construct an initial set of sensors using leverage scores and then swap the chosen sensors with other candidates until certain convergence criteria are met. We demonstrate the efficiency and scalability of the proposed computational framework by a linear inverse problem of inferring the initial condition for an advection-diffusion equation, and a nonlinear inverse problem of inferring the diffusion coefficient of a log-normal diffusion equation, with both the parameter and data dimensions ranging from a few tens to a few thousands.
BibTeX
@misc{wu2020fast,
  author = {Keyi Wu and Peng Chen and Omar Ghattas},
  title = {{A fast and scalable computational framework for large-scale and high-dimensional Bayesian optimal experimental design}},
  year = {2020},
  eprint = {2010.15196},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2010.15196},
}
Figure