Bayesian measurement design and information gain

Let $D$ be a finite set of design indices, let $(\mathrm{\Theta },\mathcal{T})$ and $(\mathsf{Y},\mathcal{Y})$ be measurable spaces, let ${\mu }_0$ be a probability measure on $(\mathrm{\Theta },\mathcal{T})$, and let $\nu$ be a sigma-finite measure on $(\mathsf{Y},\mathcal{Y})$. For each $d\in D$, let $Q_d$ be a probability kernel from $\mathrm{\Theta }$ to $\mathsf{Y}$ with a specified nonnegative jointly measurable density $p_d(y\mid \theta )$ relative to $\nu$, so $Q_d(\theta ,B)={\int }_B{p}_d(y\mid \theta )\nu (dy)(\theta \in \mathrm{\Theta },B\in \mathcal{Y})\mathrm{.}$ Define the prior-predictive density $p_d(y)={\int }_{\mathrm{\Theta }}{p}_d(y\mid \theta ){\mu }_0(d\theta )$. For each datum $y$ with $0<p_d(y)<\mathrm{\infty }$, define the posterior probability measure ${\mu }_d^y(A)=\frac{{\int }_A{p}_d(y\mid \theta ){\mu }_0(d\theta )}{p_d(y)}(A\in \mathcal{T})\mathrm{.}$ The dominated-kernel Bayes formula makes $p_{d}d\nu$ the observation law and identifies ${\mu }_d^y$ as a posterior version on these positive finite evidence fibers. No posterior formula is assigned on fibers with zero or infinite evidence; their prior-predictive probability is zero.

A finite set has a finite cardinality.

A measurable space consists of a set and a sigma-algebra.

A probability measure has total mass one.

Sigma-finiteness is witnessed by a countable cover with finite measure.

A probability kernel has measurable evaluations and probability-measure rows.

Joint measurability is with respect to the product sigma-algebra.

A measurable function has measurable preimages.

A specified dominated sampling density yields the predictive density and the posterior kernel on positive finite evidence fibers.

A posterior is a regular conditional law of the parameter given the observations.

Chaloner and Verdinelli, §1.2

MacKay, §2

Assume the Axiom of Choice for the library's Kullback–Leibler divergence convention. For a design $d$ in a design-indexed dominated inverse experiment, let $G_d=\{y:0<p_d(y)<\mathrm{\infty }\}$ be its positive finite evidence fibers. The expected information gain is $\mathrm{EIG}(d):={\int }_{G_d}D({\mu }_d^y\mathrm{\parallel }{\mu }_0)p_d(y)\nu (dy)\in [0,+\mathrm{\infty }],$ where the integrand is defined to be zero outside $G_d$. Here $D(P\mathrm{\parallel }Q)$ is the directional Kullback–Leibler divergence of probability measures, with natural logarithms.

This integrand is measurable. Tonelli's theorem makes $p_d$ measurable, so $G_d$ is measurable. On $G_d$, the likelihood ratio $r_d(\theta ,y)=p_d(y\mid \theta )\mathrm{/}{p}_d(y)$ is the ${\mu }_0$-density of ${\mu }_d^y$. Set $r_d=0$ off $G_d$ and wherever $p_d(y\mid \theta )=+\mathrm{\infty }$; the latter set is ${\mu }_0$-null on each $y\in G_d$ because its integral is the finite value $p_d(y)$. Thus $r_d$ is a finite-valued product-measurable function. With $\psi (0)=0$ and $\psi (t)=t\log t$ for $t>0$, the KL definition gives $D({\mu }_d^y\mathrm{\parallel }{\mu }_0)=\int \psi (r_d(\theta ,y)){\mu }_0(d\theta )$. Tonelli makes the section integrals of $\psi (r_d{)}^{+}$ and $\psi (r_d{)}^{-}$ measurable; the negative integral is finite by the KL definition. Their difference is therefore measurable and extended-valued, and KL nonnegativity makes it $[0,+\mathrm{\infty }]$-valued. Setting it to zero off $G_d$ preserves measurability, so the displayed EIG integral is well-defined.

The predictive density and posterior probability measure on positive finite evidence fibers.

The directional relative entropy is an extended integral with a finite negative part.

The general Radon–Nikodym convention used by the library KL definition assumes AC.

KL divergence between probability measures is nonnegative.

Tonelli makes the predictive density and the posterior KL integrand's section integrals measurable.

Chaloner and Verdinelli, §2.2

MacKay, §2

The value $+\mathrm{\infty }$ is permitted. Before finite numerical optimization, either use the extended objective without subtracting entropies or impose and verify integrability for every design being compared. In particular, do not form a difference of two infinite prior and posterior entropies.

The library KL definition controls the negative part and defines its extended integral without an $\mathrm{\infty }-\mathrm{\infty }$ ambiguity.

Assume the Axiom of Choice. Fix a design $d$ in a design-indexed dominated inverse experiment, with prior ${\mu }_0$, likelihood density $p_d(y\mid \theta )$ relative to the common sigma-finite measure $\nu$, predictive density $p_d(y)$, and posterior ${\mu }_d^y$ on $G_d=\{y:0<p_d(y)<\mathrm{\infty }\}$. Let $P_d$ be the joint law of $(\theta ,Y)$, so on measurable rectangles $P_d(A\times B)={\int }_B{\int }_A{p}_d(y\mid \theta ){\mu }_0(d\theta )\nu (dy),$ let $P_{Y\mid d}(B)={\int }_B{p}_d(y)\nu (dy)$, and let $Q_d={\mu }_0\otimes P_{Y\mid d}$. Then $\mathrm{EIG}(d)=D(P_d\mathrm{\parallel }{Q}_d)\in [0,+\mathrm{\infty }]\mathrm{.}$ On $G_d$, the Radon–Nikodym density $d{P}_d\mathrm{/}d{Q}_d$ is $p_d(y\mid \theta )\mathrm{/}{p}_d(y)$ almost everywhere. The identity is valid as an extended integral: its negative part is finite, its positive part may be infinite, and no subtraction of two infinite entropies occurs.

The common proper prior, dominated likelihood, predictive density, and posterior on positive finite evidence fibers.

EIG is the prior-predictive expectation of posterior-to-prior KL divergence.

KL is the directional RN log-density integral with a finite negative part.

The predictive density and posterior kernel identities hold on positive finite evidence fibers, and exceptional fibers have zero predictive mass.

Chaloner and Verdinelli, §2.2

MacKay, §2

Assume the Axiom of Choice. Let $n,m\ge 1$, let $m_0\in {\mathbb{R}}^n$, let $C\in {\mathbb{R}}^{n\times n}$ be symmetric positive semidefinite, let $A\in {\mathbb{R}}^{m\times n}$, and let $\mathrm{\Gamma }\in {\mathbb{R}}^{m\times m}$ be symmetric positive definite. Suppose $\theta \sim N_n(m_0,C)$ and $\eta \sim N_m(0,\mathrm{\Gamma })$ are independent, and observe $Y=A\theta +\eta$. With $S=AC{A}^T+\mathrm{\Gamma }$, the expected information gain of this experiment is $\mathrm{EIG}=\frac{1}{2}\log \det \text{\hspace{0.17em}⁣}(I_m+{\mathrm{\Gamma }}^{-1\mathrm{/}2}AC{A}^T{\mathrm{\Gamma }}^{-1\mathrm{/}2})\mathrm{.}$ Here ${\mathrm{\Gamma }}^{-1\mathrm{/}2}$ is the inverse of the unique symmetric positive-definite square root of $\mathrm{\Gamma }$, and $\log$ is the natural logarithm. The matrix inside the log determinant is positive definite. This formula permits singular $C$ and never uses differential entropy of $\theta$; the mean $m_0$ cancels. Noise depending on $\theta$ is outside the hypotheses and need not satisfy the formula.

Expected information gain is the joint KL divergence of parameter and observation from the product of their marginals.

For singular prior covariance and positive-definite observation noise, the finite linear Gaussian posterior exists and only the observation covariance is inverted.

A finite multivariate Gaussian law may have singular covariance.

Positive-definite Gaussian covariance gives the stated Lebesgue density.

Logarithms use the natural logarithm.

Chaloner and Verdinelli, §2.2

MacKay, §3.1

Rasmussen and Williams, Chapter 2

Assume AC for the library KL/EIG convention. Input a prior covariance $C\in {\mathbb{R}}^{n\times n}$ with $n\ge 1$ symmetric positive semidefinite, a finite ordered list of raw candidate records $(A_d,{\mathrm{\Gamma }}_d,c_d{)}_{d=1}^N$, and a real budget $B$. Each stored $A_d$ and ${\mathrm{\Gamma }}_d$ is a finite real matrix, with its dimensions part of the input, and each declared cost $c_d$ is finite and real. A candidate is dimension-valid when $A_d$ has at least one row and exactly $n$ columns and ${\mathrm{\Gamma }}_d$ is a symmetric square matrix whose dimension equals the row count of $A_d$; for a dimension-valid candidate write that common positive dimension as $m_d$. The prior mean is immaterial to the score.

Interpret each admissible candidate $d$ (dimension-valid with ${\mathrm{\Gamma }}_d$ positive definite) as a separate singleton-design dominated inverse experiment with prior $\theta \sim N_n(m_0,C)$ for any $m_0\in {\mathbb{R}}^n$, observation space ${\mathbb{R}}^{m_d}$ with Lebesgue measure, and observation $Y_d=A_d\theta +{\eta }_d$, where ${\eta }_d\sim N_{m_d}(0,{\mathrm{\Gamma }}_d)$ is independent of $\theta$. Here $\mathrm{EIG}(d)$ is the expected information gain from the preceding definition for that singleton experiment. Different candidates may have different $m_d$ because each is evaluated on its own observation space. The score is independent of $m_0$.

In exact-real arithmetic, process the list in order. Mark a candidate inadmissible if it is not dimension-valid or if its noise covariance ${\mathrm{\Gamma }}_d$ is not positive definite. For each remaining candidate with $c_d\le B$, compute the Cholesky factor ${\mathrm{\Gamma }}_d=L_d{L}_d^T$ with positive diagonal, solve $L_d{V}_d=A_d$ by forward substitution, and form the symmetric positive-semidefinite matrix $Z_d=V_{d}C{V}_d^T$. Set $H_d=I_{m_d}+Z_d$ and compute its Cholesky factor $H_d=R_d{R}_d^T$. Assign the utility $U_d={\sum }_{j=1}^{m_d}\log (R_d{)}_{jj}-c_d=\frac{1}{2}\log \det (H_d)-c_d\mathrm{.}$ Initialize the stored best candidate as unset. For each admissible candidate meeting the budget, set it if unset; otherwise replace it exactly when the new utility is strictly greater than the stored utility. After the scan, return the stored candidate. This update rule preserves the first index in any tie. If every candidate is inadmissible, return all-inadmissible; if at least one candidate is admissible but none meets the budget, return budget-exhausted.

In floating-point mode, treat each finite stored floating-point matrix entry, cost, budget, and tolerance as the exact real number represented by that value; no uncertainty in these input data is included. Use failure-aware Cholesky and triangular-solve procedures, and take a certificate provider as part of the floating-point input. Each provider result is a finite, independently checkable certificate; if the provider cannot certify a required fact, it returns unresolved.

Process the candidates in list order. Test dimensions and symmetry exactly, marking a dimension-invalid candidate inadmissible. For each dimension-valid noise matrix ${\mathrm{\Gamma }}_d$, call CertifyPositiveDefiniteness(\Gamma_d). It returns positive-definite only with a checkable positive-definiteness certificate, not-positive-definite only with a checkable certificate, or unresolved. For example, an exact factorization ${\mathrm{\Gamma }}_d=L{L}^T$ with $L$ lower triangular and positive diagonal certifies positive definiteness, while a nonzero vector $v$ with $v^T{\mathrm{\Gamma }}_{d}v\le 0$ certifies that it is not positive definite. A failed rounded Cholesky factorization is not a certificate of non-positive-definiteness. If any required status is unresolved, return numerically-unresolved. After all statuses are certified, return all-inadmissible if none is admissible. Compare each admissible stored cost to the stored budget exactly; if none meets it, return budget-exhausted.

For each feasible candidate $d$ in inherited order, call CertifyScore(d). It first runs failure-aware rounded Cholesky on ${\mathrm{\Gamma }}_d$ and, on success, failure-aware forward substitution on each column of $A_d$ in order; any operation failure or unmet range hypothesis returns unresolved. After forming a certified positive-semidefinite ${\widehat{Z}}_d$, it forms a stored matrix ${\widehat{H}}_d$ and certifies both that ${\widehat{H}}_d$ is symmetric positive definite and that $\mathrm{\parallel }{\widehat{H}}_d-(I_{m_d}+{\widehat{Z}}_d){\mathrm{\parallel }}_2\le {\sigma }_d$ for a rational bound ${\sigma }_d\ge 0$. It then runs failure-aware rounded Cholesky on ${\widehat{H}}_d$; a failed definiteness check, factorization, or formation bound returns unresolved. The call then returns either certified with finite stored values ${\widehat{U}}_d$, ${\widehat{Z}}_d$, and ${\widehat{R}}_d$, nonnegative rational upper bounds ${\delta }_d,{\rho }_d,{\lambda }_d$, and certificates for all of the following, or unresolved:

• ${\widehat{Z}}_d$ is symmetric positive semidefinite and $\mathrm{\parallel }{\widehat{Z}}_d-Z_d{\mathrm{\parallel }}_2\le {\delta }_d$, where $Z_d$ uses the exact Cholesky factor of the represented ${\mathrm{\Gamma }}_d$. This bound includes rounding in forming the Cholesky factor and triangular solve for ${\mathrm{\Gamma }}_d$, the covariance square root, and the matrix products.
• ${\widehat{R}}_d$ is a successful lower-triangular Cholesky factor with positive diagonal. If ${\tilde{\rho }}_d$ is a certified upper bound for $\mathrm{\parallel }{\widehat{R}}_d{\widehat{R}}_d^T-{\widehat{H}}_d{\mathrm{\parallel }}_2$, choose a rational ${\rho }_d\ge {\tilde{\rho }}_d+{\sigma }_d$ with ${\rho }_d<1$; then $\mathrm{\parallel }{\widehat{R}}_d{\widehat{R}}_d^T-(I_{m_d}+{\widehat{Z}}_d){\mathrm{\parallel }}_2\le {\rho }_d$.
• $\mid {\widehat{U}}_d-(\frac{1}{2}\log \det ({\widehat{R}}_d{\widehat{R}}_d^T)-c_d)\mid \le {\lambda }_d$. Evaluate the exact expression as ${\sum }_j\log (({\widehat{R}}_d{)}_{jj})-c_d$ using the triangular determinant identity; ${\lambda }_d$ covers rounded logarithms, their summation, and cost evaluation.

If any CertifyScore call returns unresolved, return numerically-unresolved immediately, without a candidate or optimum claim. Continue to interval comparisons only when every feasible candidate has a certified result.

The matrix radius may be certified by the published information-matrix perturbation bound in its single-design, unit-weight $W=I_n$ case. Factor $C$ as $C^{1\mathrm{/}2}{C}^{1\mathrm{/}2}$ and set $J_d=C^{1\mathrm{/}2}{V}_d^T$; for a computed solve ${\widehat{V}}_d$, set ${\widehat{J}}_d=C^{1\mathrm{/}2}{\widehat{V}}_d^T$. Then $Z_d=J_d^T{J}_d$ and ${\widehat{Z}}_d={\widehat{J}}_d^T{\widehat{J}}_d$. The lemma's finite-design hypotheses hold for the one-point sensitivity maps $z\mapsto J_{d}z$ and $z\mapsto {\widehat{J}}_{d}z$ from ${\mathbb{R}}^{m_d}$ to ${\mathbb{R}}^n$, with weight $W=I_n$ and design weight $1$. If $\mathrm{\parallel }{J}_d{\mathrm{\parallel }}_2\le K_d$ and $\mathrm{\parallel }{\widehat{J}}_d-J_d{\mathrm{\parallel }}_2\le {\eta }_d$, then ${\delta }_d$ may be any verified bound at least $2K_d{\eta }_d+{\eta }_d^2$, enlarged by any separate matrix-formation residual. A rounded triangular-substitution bound may be used only after checking its $(m_d+3)u<1$ and normal-range, finite-operation hypotheses for every right-hand side. Convert its backward-error bound to the required forward matrix bound using verified conditioning; a solve backward-error bound alone does not certify ${\eta }_d$. For the published rounded-Cholesky normwise bound, verify success and its operationwise model, put $q=20m_d+20$ and $g=qu\mathrm{/}(1-qu)$, and check $qu<1\mathrm{/}5$ before using $100g\mathrm{\parallel }{\widehat{R}}_d{\mathrm{\parallel }}_F^2$ as a residual bound; if using its relative bound, also check $100\sqrt{m_d}g\le 1\mathrm{/}2$. The log-determinant perturbation bound is applied on the two symmetric matrix segments with eigenvalue floors $1$ and $1-{\rho }_d$. A missing or failed certificate returns numerically-unresolved and no optimum claim.

Set ${\epsilon }_d=\frac{m_d}{2}({\delta }_d+\frac{{\rho }_d}{1-{\rho }_d})+{\lambda }_d$ and form the exact rational interval $[{\widehat{U}}_d-{\epsilon }_d,{\widehat{U}}_d+{\epsilon }_d]$. Given a finite nonnegative stored tolerance $\tau$, compute $M={\max }_{d\text{ feasible}}{\widehat{U}}_d$ and return the first feasible candidate with ${\widehat{U}}_d\ge M-\tau$. Certify the comparisons exactly on the represented floating-point values and rational bounds; if any comparison needed for this branch or for its interval certificate is undecided, return numerically-unresolved. The returned candidate's true utility gap is at most $\tau +2{\max }_d{\epsilon }_d$. If its lower interval endpoint exceeds every earlier candidate's upper endpoint and is at least every later candidate's upper endpoint, certify it as the first exact maximizer. The algorithm makes no bit-complexity claim for exact-real comparisons.

The exact linear-Gaussian EIG is a log determinant, including singular state covariance.

Each candidate's Gaussian model is a singleton design in the dominated-experiment convention.

EIG is the extended prior-predictive posterior-to-prior KL integral.

A positive-semidefinite prior covariance has a positive-semidefinite square root for the Gram representation.

Cholesky factors are lower triangular with positive diagonal.

Every symmetric positive-definite matrix has a unique positive-diagonal Cholesky factor.

Cholesky triangular solves evaluate positive-definite systems without forming an inverse.

The determinant of a triangular matrix is the product of its diagonal entries.

The log-determinant score uses the usual determinant of a finite square matrix.

The logarithm in the score is the natural logarithm.

The floating-point factorization reports success or its first pivot/operation failure.

Successful rounded triangular solves have the stated componentwise backward error.

Successful rounded Cholesky gives the stated factorization residual bounds.

Uniform factor and solve errors imply the stated information-matrix perturbation bound.

A one-point approximate design with a linear sensitivity map and weight matrix $W=I$ satisfies the finite-design setting.

A positive eigenvalue floor controls log-determinant perturbation.

Rasmussen and Williams, Chapter 2, Algorithm 2.1 and equation (2.30)

Chaloner and Verdinelli, §2.2

This procedure is for the specified finite linear-Gaussian candidates. A Monte Carlo estimate of nonlinear EIG is a different procedure and inherits no exact finite optimum guarantee from this algorithm.

Any solve-error certificate must convert triangular-solve backward error to the required matrix error using a verified conditioning bound. Backward error alone is not a forward-error bound.

The exact log-determinant formula applies to the linear-Gaussian model stated there.

A rounded triangular-solve certificate is a backward-error statement and requires conditioning to produce a forward bound.

MacKay, §6.1, model-correctness caveat

Assume AC for the library KL/EIG convention.

Assume the finite-candidate algorithm's hypotheses. A candidate is admissible when it is dimension-valid and its symmetric noise covariance is positive definite; let $\mathcal{V}$ be the ordered list of admissible candidates and let $\mathcal{F}=(d\in \mathcal{V}:c_d\le B)$ in the inherited order. For each $d\in \mathcal{F}$, let $U_d=\mathrm{EIG}(d)-c_d$ be its exact utility. In exact-real mode, if $\mathcal{F}$ is nonempty, the algorithm returns the first index in $\mathcal{F}$ attaining ${\max }_{d\in \mathcal{F}}{U}_d$; if $\mathcal{V}$ is empty it returns all-inadmissible, and if $\mathcal{V}$ is nonempty but $\mathcal{F}$ is empty it returns budget-exhausted.

For the floating-point mode, suppose each $d\in \mathcal{F}$ has a computed score ${\widehat{U}}_d$, a symmetric positive-semidefinite matrix ${\widehat{Z}}_d$, a successful factor ${\widehat{R}}_d$, and certified radii ${\delta }_d\ge 0$, $0\le {\rho }_d<1$, and ${\lambda }_d\ge 0$ such that $\mathrm{\parallel }{\widehat{Z}}_d-Z_d{\mathrm{\parallel }}_2\le {\delta }_d,\mathrm{\parallel }{\widehat{R}}_d{\widehat{R}}_d^T-(I_{m_d}+{\widehat{Z}}_d){\mathrm{\parallel }}_2\le {\rho }_d,$ where $Z_d$ is the exact Cholesky-whitened matrix in the algorithm's Definition, and $\mid {\widehat{U}}_d-(\frac{1}{2}\log \det ({\widehat{R}}_d{\widehat{R}}_d^T)-c_d)\mid \le {\lambda }_d\mathrm{.}$ For example, the matrix-radius component can use the information-matrix perturbation result in its single-design, unit-weight $W=I$ specialization: if $Z_d=J_d^T{J}_d$, ${\widehat{Z}}_d={\widehat{J}}_d^T{\widehat{J}}_d$, $\mathrm{\parallel }{J}_d{\mathrm{\parallel }}_2\le K_d$, and $\mathrm{\parallel }{\widehat{J}}_d-J_d{\mathrm{\parallel }}_2\le {\eta }_d$, then ${\delta }_d\ge 2K_d{\eta }_d+{\eta }_d^2$ is sufficient, with any separate formation residual added. A rounded triangular-solve backward-error bound must be converted to the needed forward matrix error using a verified conditioning bound. The rounded-Cholesky residual must follow from a successful factorization under its stated floating-point assumptions; in particular, the cited bound assumes $mu<1\mathrm{/}5$, where $m=20m_d+20$ and $u$ is unit roundoff. The value ${\lambda }_d$ must bound the rounded logarithms, their summation, and cost evaluation. Set ${\epsilon }_d=\frac{m_d}{2}({\delta }_d+\frac{{\rho }_d}{1-{\rho }_d})+{\lambda }_d$. If the algorithm returns a candidate $\widehat{d}$ with ${\widehat{U}}_{\widehat{d}}\ge {\max }_{d\in \mathcal{F}}{\widehat{U}}_d-\tau$, then ${\max }_{d\in \mathcal{F}}{U}_d-U_{\widehat{d}}\le \tau +{\epsilon }_{d^{\ast }}+{\epsilon }_{\widehat{d}}\le \tau +2{\max }_{d\in \mathcal{F}}{\epsilon }_d,$ where $d^{\ast }$ is any exact maximizer. If the certified score intervals show that the selected candidate's lower endpoint exceeds every earlier candidate's upper endpoint and is at least every later candidate's upper endpoint, it is the first exact maximizer. The matrix and factor radii must be certified under the published solve, information-matrix, rounded-Cholesky, and log-determinant error hypotheses; ${\lambda }_d$ must additionally cover rounded logarithm, summation, and cost evaluation.

The exact scan, feasible set, tie rule, and floating-point certificate interface.

Uniform sensitivity errors control the weighted information-matrix error.

A one-point design with the linear sensitivity maps and unit weight instantiates the finite-design perturbation setting.

A common positive eigenvalue floor controls log-determinant error.

A successful rounded Cholesky factorization supplies a residual bound under its operationwise hypotheses.

The natural logarithm turns positive products into sums.