Can any continuous function on [a, b], where a and b are real numbers, be approximated or arbitrarily close to the function (in some norm) by Gaussian Processes (Regression)?
$\begingroup$
$\endgroup$
13
-
1$\begingroup$ Be more specific! $\endgroup$– Henry.LCommented Mar 19, 2017 at 13:05
-
1$\begingroup$ yes! Well, actually, it depends on the covariance function, but for some of them they do. Dustin Tran et al. also proved an universal approximation theorem in the Bayesian framework for the Variational Gaussian Process, which is a more complex model because of the warping functions, but it's very closely related. I'll write an answer if the question gets reopened. PS note that universal approximation, as for Neural Networks, only holds over a compact set, not over all of $\mathbb{R}^p$. $\endgroup$– DeltaIVCommented Mar 19, 2017 at 15:40
-
3$\begingroup$ The statement of "universal approximation" in this question appears to have little or nothing to do with the statement in the referenced Wikipedia article. Indeed, it isn't even clear how one might approximate a function with a process. Could you elaborate on what you're trying to ask? $\endgroup$– whuber ♦Commented Mar 19, 2017 at 17:28
-
6$\begingroup$ @whuber Though the technicalities may be a little bit loose, I think the question essentially means "For an input function $f$, is there a realization of a particular GP which is arbitrarily close to $f$ (in some norm)?" Or perhaps, "As we observe infinitely many sample points from a function $f$, and perform standard GP inference with that data, does the learned posterior mean function approach the true function $f$ (in some sense)?" These two are of course different properties, but I'd consider them close enough to be answerable (and hence cast the fifth reopen vote). $\endgroup$– DanicaCommented Mar 20, 2017 at 17:11
-
1$\begingroup$ Maybe, you want to prove convergence instead of approximation. Otherwise, the proof is simple: you can take the function as prior for the mean. It is not much more than $x=x$, but it works. $\endgroup$– Karel MacekCommented Mar 20, 2017 at 20:59
|
Show 8 more comments
1 Answer
$\begingroup$
$\endgroup$
1
As @Dougal notes, there are two different ways in which your question may be interpreted. They are closely related, even if it may not seem so.
The first interpretation is: let $X$ be a compact subset of $\mathbb{R}^d$ (compactness is fundamental for all of the following!!!), let $k(\mathbf{x},\mathbf{x})$ be a continuous covariance function (or kernel) defined on $X\times X$, and denote with $C(X)$ the normed space of continuous functions on $X$, equipped with the maximum norm $||\cdot||_{\infty}$. For any function $f\in C(X)$, can $f$ be approximated to a prespecified tolerance $\epsilon$ by a function in the RKHS (Reproducing Kernel Hilbert Space) associated to $k$? You may well wonder what an RKHS is, an what all this has to do with Gaussian Process Regression. An RKHS $K(X)$ is the closure of the vector space formed by all possible finite linear combinations of all possible functions $f_\mathbf{y}(\mathbf{x})=k(\mathbf{x},\mathbf{y})$ where $\mathbf{y}\in X$. This is very strictly related to Gaussian process regression, because given a Gaussian process prior $GP(0,k(\mathbf{x},\mathbf{x}))$ on the space $C(X)$, then the (closure of the) space of all possible posterior means which can be generated by Gaussian Process Regression is exactly the RKHS. As a matter of fact, all possible posterior means are of the form
$$f(\mathbf{x}) =\sum_{i=1}^n c_i k(\mathbf{x},\mathbf{x}_i)$$
i.e., they are finite linear combinations of functions $f_\mathbf{x_i}(\mathbf{x})=k(\mathbf{x},\mathbf{x_i})$. Thus, we're effectively asking if, given a Gaussian Process prior $GP(0,k(\mathbf{x},\mathbf{x}))$ on $C(X)$, for any function $f\in C(X)$ there is always a function $f^*$ in the (closure of the) space of all functions which can be generated by GPR, which is as close as desired to $f$.
The answer, for some particular kernels (including the classic Squared Exponential kernel, but not including the polynomial kernel), is yes. It can be proved that for such kernels $K(X)$ is dense in $C(X)$, i.e., for any $f\in C(X)$ and for any tolerance $\epsilon$, there is an $f^*$ in $K(X)$ such that $||f-f^*||_{\infty}<\epsilon$. Note the assumptions: $X$ is compact, $f$ is continuous and $k$ is a continuous kernel having the so-called universal approximation property. See here for a full proof in a more general (thus complicated) context.
This result is much less powerful than it looks at first sight. Even if $f^*$ is in the (closure of the) space of the posterior means which can be generated by GPR, we haven't proved that it is the particular posterior mean returned by GPR, for a training set large enough, where of course the training set consists of noisy observations of $f$ at points $\mathbf{x}_1,\dots,\mathbf{x}_n$. We haven't even proved that the posterior mean returned by GPR converges at all, for $n \to \infty$! This is actually the second interpretation suggested by @Dougal. The answer to this question depends on the answer to the first question: if there isn't any function $f^*$ in the RKHS which is a "good approximation" to $f$, of course we cannot hope that the posterior mean returned by GPR converges to it. However, it's a different question. If you would like to have an answer to this question too, please ask a new question.
-
$\begingroup$ great answer! was the follow-up question ever asked? $\endgroup$ Commented Apr 26, 2022 at 4:54