3
$\begingroup$

Motivation

Let $(Z(x))_{x\in \mathbb{R}^n}$ be a random function (also known as random field, or random process), i.e. a collection of random variables, but also $Z\in C(\mathbb{R}^n)$ almost surely. The construction of this is not completely trivial, but let us take this as a given.

Now if one were to simulate such a random function at a discrete number of points $x_1,\dots, x_n$, one is interested in the marginal distribution, i.e. we want to know $$ \mathbb{E}[f(Z(x_1), \dots, Z(x_n))] $$ for all $f$. What now happens in Bayesian Optimization, is that we sample our random function at some point $x_0$, i.e. we obtain $Z(x_0)$, then we want to know the conditional distribution of $Z(x)$ given $Z(x_0)$. I.e. $$ \mathbb{E}[f(Z(x))\mid Z(x_0)] $$ This is not a huge problem if we assume $Z$ is a Guassian random function (Gaussian process) with known covariance function. But using this conditional distribution, we tend to select our next evaluation point $X_1$. I.e. $X_1$ is a random variable which is $\sigma(Z(x_0))$ measurable. If we now want to know the distribution of $$ \mathbb{E}[f(Z(x))\mid Z(X_1), Z(x_0)] $$ things become much more tricky, as $Z(X_1)$ is a much more complicated object than $Z(x_0)$. My hypothesis is that $$ \mathbb{E}[f(Z(x))\mid Z(X_1), Z(x_0)] = \bigl(y\mapsto \mathbb{E}[f(Z(x))\mid Z(y), Z(x_0)]\bigr)(X_1) $$ as $X_1$ is completely measurable with regards to $\sigma(Z(x_0)$.

Hypothesis

More generally I expect for a random function in $Z \in C(\mathbb{R}^n)$ $$ \mathbb{E}[f(Z(x))\mid Z(X_n),\dots, Z(X_1),Z(x_0)] = \bigl((y_n,\dots, y_1)\mapsto \mathbb{E}[f(Z(x))\mid Z(y_n),\dots, Z(y_1),Z(x_0)]\bigr)(X_n,\dots,X_1) $$ for $X_n$ measurable with regards to $$ \mathcal{F}_{n-1} = \sigma(Z(x_0),Z(X_1)\dots, Z(X_{n-1})). $$

Progress

I have been able to prove the claim:

Let $Z$ be an almost surely random function, $X$ be $\mathcal{F}$ measurable, then $$ \mathbb{E}[f(Z(X))\mid \mathcal{F}] = \Bigl(y\mapsto \mathbb{E}[f(Z(y))\mid \mathcal{F}]\Bigr)(X) $$

using the fact that the evaluation function $e(z,y) = z(y)$ is continuous and therefore measurable for continuous functions, and regular conditional distributions (I can post a proof if requested).

Now if we were not in the continuous case, we could do the following $$ \begin{aligned} &\mathbb{P}(Z(x) = z \mid Z(X_1) = z_1, Z(x_0) = z_0)\\ &\overset{\text{Bayes}}= \frac{\mathbb{P}(Z(X_1)=z_1 \mid Z(x)=z, Z(x_0)=z_0)\mathbb{P}(Z(x)=z, Z(x_0)=z_0)}{\mathbb{P}(Z(X_1)=z_1\mid Z(x)=z)\mathbb{P}(Z(x)=z)} \end{aligned} $$ and then apply the proven statement above since $X_1$ is $\sigma(Z(x), Z(x_0))$ measurable as it is already $\sigma(Z(x_0))$ measurable. Afterwards we simply use Bayes backwards to get $$ \begin{aligned} &\mathbb{P}(Z(x) = z \mid Z(X_1) = z_1, Z(x_0) = z_0)\\ &=\Bigl(y\mapsto \frac{\mathbb{P}(Z(y)=z_1 \mid Z(x)=z, Z(x_0)=z_0)\mathbb{P}(Z(x)=z, Z(x_0)=z_0)}{\mathbb{P}(Z(y)=z_1\mid Z(x)=z)\mathbb{P}(Z(x)=z)}\Bigr)(X_1)\\ &= \bigl(y \mapsto \mathbb{P}(Z(x) = z \mid Z(y) = z_1, Z(x_0) = z_0)\bigr)(X_1) \end{aligned} $$ Unfortunately, it is not quite so easy to translate this to the continuous case. $Z(x_0)\in A$ does not work, since we need to know its precise value to know $X_1$. Well, since we have that $Z$ is continuous, it might work like this. But I am unsure. Such approximating arguments seem to be very troublesome (cf. Borel-Kolmogorov Pradox)

Does anyone already know the solution to this problem, or has any idea how to approach this? Since this is related to a common practical usecase, it seems like this should be something someone has already looked at.

$\endgroup$

1 Answer 1

0
$\begingroup$

The following is a proof for the absolutely continuous case (covering Gaussian random functions)

Lemma: Partial integration

Let $X,Z$ be random variables on polish spaces $(E_x, \mathcal{E}_x), (E_z,\mathcal{E}_z)$, $$ f:E_z\times E_x\to \mathbb{R} $$ a measurable function. Let $X$ be $\mathcal{F}$ measurable, $\kappa_{Z\mid \mathcal{F}}$ the regular conditional distribution, then we have for $\Pr$ almost all $\omega$ $$ \mathbb{E}[f(Z,X) \mid \mathcal{F}](\omega) = \int f(z, X(\omega)) \kappa_{Z\mid \mathcal{F}}(\omega, dz) $$ in the case $\sigma(\tilde{X})=\mathcal{F}$ this simplifies to $$ \mathbb{E}[f(Z,X) \mid \tilde{X}] = \int f(z, X) \kappa_{Z\mid \tilde{X}}(\tilde{X}, dz) $$

Proof

left to the reader (the usual argument starting with $f=\mathbf{1}_{A\times B}$)

Corollary: Conditional Sampling I

Let $Z$ be an almost surely random function, $X$ be $\mathcal{F}$ measurable, then $$ \mathbb{E}[f(Z(X))\mid \mathcal{F}] = (y\mapsto \mathbb{E}[f(Z(y))\mid \mathcal{F}])(X) $$

Proof

The evaluation function $$ e(z,x) = z(x) $$ is continuous on the space of continuous functions, and therefore measurable. $f\circ e$ is then also measurable. The application of [Lemma: Partial Integration] results in $$\begin{aligned} \mathbb{E}[f(Z(X))\mid \mathcal{F}](\omega) &=\mathbb{E}[f \circ e (Z, X) \mid \mathcal{F}](\omega)\\ &= \int f\circ e(z, X(\omega)) \kappa_{Z\mid \mathcal{F}}(\omega, dz)\\ &\overset{\text{Lem.}}= \Bigl(y\mapsto\int f\circ e(z, y) \kappa_{Z\mid \mathcal{F}}(\omega, dz)\Bigr)(X(\omega))\\ &= (y\mapsto \mathbb{E}[f(Z(y))\mid \mathcal{F}])(X)(\omega) \end{aligned}$$ Where we use Klenke (2014, Thm. 8.38) for the last equation and all equalities are true for almost all $\omega$.

Conditional sampling Lemma

Let $Z$ be a random function from $\mathbb{R}^d$ to $\mathbb{R}^m$. Assume that for all $\lambda$ we have that $Y, \tilde{X}, X, Z(\lambda)$ are random variables with joint densities on $\mathbb{R},\mathbb{R}^n, \mathbb{R}^d, \mathbb{R}$ such that $X$ is $\sigma(\tilde{X})$ measurable. Then we have $$ \Pr(Y\in A \mid Z(X), \tilde{X}) = \Bigl(\lambda \mapsto \Pr(Y\in A \mid Z(\lambda), \tilde{X})\Bigr)(X) $$ and $Y, \tilde{X}, Z(X)$ have joint density.

Proof

First we want to prove that $Z(X)$ also has a joint density with the other variables. For this we use the regular conditional distribution to get $$ \Pr(Z(X) \in A, (Y, \tilde{X})) = \int_B \underbrace{ \Pr(Z(X) \in A \mid (Y, \tilde{X}) = (y,x)) }_{=\mathbb{E}[\mathbf{1}_A(Z(X))\mid (Y, \tilde{X}) = (y,x)]} \Pr_{Y,\tilde{X}}(dy, dx) $$ which we can now apply the Corollary to get $$ \underbrace{\mathbb{E}[\mathbf{1}_A(Z(X)) \mid Y, \tilde{X}]}_{=: h(Y, \tilde{X})} = \Bigl( \lambda \mapsto \underbrace{ \mathbb{E}[\mathbf{1}_A(Z(\lambda))\mid Y, \tilde{X}] }_{=:h_\lambda(Y,\tilde{X})} \Bigr)(\underbrace{X}_{=:g(\tilde{X})}) = h_{g(\tilde{X})}(Y, \tilde{X}) $$ where we use the Doob-Dynkin factorization lemma repeatedly and the fact that $X$ is $\tilde{X}$ measurable. We therefore have for $(Y,\tilde{X})$ almost all $y,x$ $$\begin{aligned} h(y,x) &= h_{g(x)}(y,x) \\ &= \mathbb{E}[\mathbf{1}_A(Z(g(x)))\mid Y,\tilde{X} = (y,x)] \\ &= \int_A \varphi_{Z(g(x))\mid Y, \tilde{X}}(z\mid y,x) dz \end{aligned}$$ Putting things together we have $$ \Pr(Z(X) \in A, (Y, \tilde{X})) = \int_B \int_A \varphi_{Z(g(x))\mid Y, \tilde{X}}(z\mid y,x)dz \varphi_{Y,\tilde{X}}(y,x) dy dx. $$ This proves we have the joint density $$ \varphi_{Z(X), Y, \tilde{X}}(z,y,x) = \varphi_{Z(g(x))\mid Y, \tilde{X}}(z\mid y,x) \varphi_{Y,\tilde{X}}(y,x). $$ And thus the conditional density is also well defined and given by $$ \varphi_{Z(X)\mid Y, \tilde{X}}(z\mid y, x) = \frac{\varphi_{Z(X), Y, \tilde{X}}(z,y,x)}{\varphi_{Y,\tilde{X}}(y,x)} = \varphi_{Z(g(x))\mid Y, \tilde{X}}(z\mid y,x) $$ We now use this fact to reason with Bayes arguments, that $$\begin{aligned} \varphi_{Y\mid Z(X), \tilde{X}}(y\mid z, x) &= \frac{\varphi_{Y, Z(X), \tilde{X}}(y, z, x)}{\varphi_{Z(X), \tilde{X}}(z,x)} \\ &= \frac{ \varphi_{Z(X) \mid Y, \tilde{X}}(z \mid y, x)\varphi_{Y,X}(y,x) }{\varphi_{Z(X)\mid \tilde{X}}(z\mid x)\varphi_{\tilde{X}}(x)} \\ &= \frac{ \varphi_{Z(g(x)) \mid Y, \tilde{X}}(z \mid y, x)\varphi_{Y,X}(y,x) }{\varphi_{Z(g(x))\mid \tilde{X}}(z\mid x)\varphi_{\tilde{X}}(x)} \\ &=\varphi_{Y\mid Z(g(x)), \tilde{X}}(y\mid z, x) \end{aligned}$$ Which finally implies our claim $$\begin{aligned} \Pr(Y\in A \mid Z(X), \tilde{X} = (z,x)) &= \int_A \varphi_{Y\mid Z(X), \tilde{X}}(y\mid z, x) dy \\ &= \int_A \varphi_{Y\mid Z(g(x)), \tilde{X}}(y\mid z, x) dy \\ &= \Bigl(\lambda \mapsto \int_A \varphi_{Y\mid Z(\lambda), \tilde{X}}(y\mid z, x) dy\Bigr) (g(x)) \\ &= \Bigl(\lambda \mapsto \Pr(Y\in A \mid Z(\lambda), \tilde{X}=(z,x))\Bigr)(g(x)), \end{aligned}$$ i.e. $$ \Pr(Y\in A \mid Z(X), \tilde{X}) = \Bigl( \lambda \mapsto \Pr(Y\in A \mid Z(\lambda), \tilde{X}) \Bigr)(\underbrace{g(\tilde{X})}_{=X}). $$

Conditional Sampling Theorem

Let $Z$ be a random function from $\mathbb{R}^d$ to $\mathbb{R}^m$ with an existing density function. Let $x_1\in \mathbb{R}^d$ and define $$ \mathcal{F}_n = \sigma(Z(X_i): i\le n) $$ where $X_1=x_1$ and $X_{n+1}$ is $\mathcal{F}_n$ measurable. Then we have for measurable functions $f$ $$\begin{aligned} &\mathbb{E}[f(Z(X_{n+1}))\mid \mathcal{F}_n] \\ &= \Bigl( (y_1,\dots,y_{n+1})\mapsto \mathbb{E}[f(Z(y_{n+1})) \mid Z(y_1), \dots, Z(y_n)] \Bigr)(X_1,\dots, X_{n+1}) \end{aligned}$$ and for any $m\in \mathbb{N}$ the joint density of $Z(X_1),\dots, Z(X_{n+1}), Z(\lambda_1),\dots, Z(\lambda_m)$ exists for any $\lambda_i\in\mathbb{R}^d$.

Proof

Let us first address the density problem. By induction we have that $$ \underbrace{Z(X_1),\dots, Z(X_n), Z(\lambda_1),\dots, Z(\lambda_{m-1})}_{=:\tilde{X}}Z(\lambda_m) $$ has joint density. Then by the conditional sampling Lemma, $\tilde{X}, Z(X_{n+1})$ have joint density, as $X_{n+1}$ is $\sigma(\tilde{X})$ measurable. So we have $$ Z(X_1),\dots, Z(X_{n+1}), Z(\lambda_1),\dots, Z(\lambda_{m-1}) $$ have joint density. As $m\in \mathbb{N}$ was arbitrary, we have this for any $m-1$.

Now to the actual statement: As $X_{n+1}$ is $\mathcal{F}_n$ measurable, we first remove it using the Corollary, resulting in $$ \mathbb{E}[f(Z(X_{n+1}))\mid \mathcal{F}_n] = (y_{n+1}\mapsto \underbrace{\mathbb{E}[f(Z(y_{n+1}))\mid \mathcal{F}_n]}_{(*)})(X_{n+1}) $$ we now look at $(*)$ and define $Y:=f(Z(y_{n+1}))$ and $\tilde{X} = (Z(X_1), \dots, Z(X_{n-1}))$, we know that everything has joint density so by the conditional sampling Lemma $$ \mathbb{E}[Y\mid Z(X_n), \tilde{X}] = (y_n\mapsto \mathbb{E}[Y\mid Z(y_n), \tilde{X}])(X_n) $$ The remaining $X_i$ can be moved out with the same argument using $$ \tilde{X}= (Z(X_1),\dots Z(X_{i-1}),Z(y_{i+1}),\dots,Z(y_n)). $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.