Is Gaussian process functional regression a Bayesian method (over again)?

Question

That’s a sequel to my previous question Does Gaussian process functional regression fulfill the consistency condition?

The conclusion was that:

• Gaussian process regression with i.i.d. Gaussian noise returns the same posterior Gaussian process for any partition of the data;
• ... but with completely different calculations/algorithms. In particular, GP regression with full $n-$update (i.e. the trivial partition) has $O\left( {{n^3}} \right)$ generic computational complexity but GP regression with $n$ sequential $1-$updates (i.e. the atomic partition) has exponential computational complexity in $n$. That’s the reason why we never do $n$ sequential $1-$updates but a $(n-1)-$update followed by a $1-$ update in sequential/online learning, see e.g. Using Gaussian Processes to learn a function online.

Now, consider a Bayesian problem with data $D = \left( {{d_1},...,{d_n}} \right)$ and parameters $\Theta $:

$p\left( {\left. \Theta \right|D} \right) \propto p\left( {\left. D \right|\Theta } \right)p\left( \Theta \right)$

Proposition $1$: if the likelihood factorizes $p\left( {\left. D \right|\Theta } \right) = \prod\limits_{i = 1}^n {p\left( {\left. {{d_i}} \right|\Theta } \right)} $ and $\Theta$ is fixed once and for all

then the posterior calculations are exactly the same for any partition $D = \bigcup\limits_{j = 1}^p {{D_j}} $ of the data and any of its $p!$ permutations.

Proof: we have

$p\left( {\left. \Theta \right|D} \right) \propto p\left( {\left. D \right|\Theta } \right)p\left( \Theta \right) = \left( {p\left( {\left. {{D_p}} \right|\Theta } \right)...\underbrace {\left( {p\left( {\left. {{D_2}} \right|\Theta } \right)\underbrace {\left( {p\left( {\left. {{D_1}} \right|\Theta } \right)p\left( \Theta \right)} \right)}_{ \propto p\left( {\left. \Theta \right|{D_1}} \right)}} \right)}_{ \propto p\left( {\left. \Theta \right|{D_1},{D_2}} \right)}...} \right)$

Therefore, the only difference from one partition to another and from one permutation to another are the parentheses and the order of the products that are totally useless by the associative and commutative properties of the product. QED.

Proposition 1 just says that the likelihood $\prod\limits_{i = 1}^n {p\left( {\left. {{d_i}} \right|\Theta } \right)} $ and the full posterior remain the same regardless of how the data are grouped together and of their order of arrival.

Corollary $1$: GP regression with i.i.d. Gaussian noise is not a Bayesian method.

Proof: We have ${d_i} = \left( {{x_i},{y_i}} \right)$ and for i.i.d. Gaussian noise the likelihood factorizes

$p\left( {\left. D \right|\Theta } \right) = \prod\limits_{i = 1}^n {p\left( {\left. {{x_i},{y_i}} \right|f,\sigma } \right) = } \prod\limits_{i = 1}^n {p\left( {\left. {{y_i}} \right|{x_i},f,\sigma } \right)p\left( {\left. {{x_i}} \right|f,\sigma } \right)} \propto \prod\limits_{i = 1}^n {p\left( {\left. {{y_i}} \right|{x_i},f,\sigma } \right)} \propto {\sigma ^{ - n}}\prod\limits_{i = 1}^n {{e^{ - \frac{{{{\left( {{y_i} - f\left( {{x_i}} \right)} \right)}^2}}}{{2{\sigma ^2}}}}}} $

Moreover, $\Theta$ is fixed once and for all: $\Theta = \left( {f,\sigma ,m,k,{\rm M},{\rm K}} \right)$, see Is Gaussian process functional regression a truly Bayesian method (again)?

But the posterior calculations are not exactly the same from one partition/update scheme to another. QED.

In the same way, we have

Proposition $2$: if the likelihood factorizes and $\Theta$ is fixed once and for all, then Bayesian inference has $O(n)$ computational complexity.

Proof: Computing the prior $p\left( \Theta \right)$ has $O(1)$ computational complexity because it does not depend on $n$. Computing the likelihood $p\left( {\left. D \right|\Theta } \right) = \prod\limits_{i = 1}^n {p\left( {\left. {{d_i}} \right|\Theta } \right)} $ has $O(n)$ computational complexity. Computing the normalization constant $p\left( D \right) = \int {p\left( {\left. D \right|\Theta } \right)p\left( \Theta \right){\text{d}}\Theta } $ has $O(1)$ complexity because that's a $|\Theta|-$ dimensional integral that has nothing to do with $n$ (moreover, we don't need to compute it, it cancels out by Leibniz rule/Feynman trick). Therefore, computing the full posterior $p\left( {\left. \Theta \right|D} \right)$ has $O(n)$ computation complexity. Finally, drawing posterior inferences, taking Bayes estimators and computing credible intervals has $O(1)$ computational complexity because it involves $\left| \Theta \right|-$dimensional integrals whose complexity basically does not depend on $n$ (we just integrate different functions that depend on $n$ but the complexity of those integrals basically does not depend on $n$). All in all, Bayesian inference has $O(n)$ computational complexity. QED.

For one example of such truly Bayesian $O(n)$ functional regression algorithm, see Bayesian interpolation and deconvolution.

Corollary $2$: again, GP regression with i.i.d. Gaussian noise is not a Bayesian method.

Proof: GP regression does not have $O(n)$ computational complexity.

Is that correct please?

Answer 1

Computational complexity has nothing to do with being a Bayesian model. Bayes theorem is a mathematical concept, it has no computational complexity whatsoever. There are different Bayesian models, where some have closed-form solutions so can be solved "instantly", some would need you to take complicated integrals. For the latter, we have many algorithms for finding the, usually approximate, solutions, where each of the algorithms has different computational complexity.

As you can learn from Who Are The Bayesians? there is no clear definition of "Bayesianism" but one of the key concepts is the subjectivist interpretation of probability. The Bayesian model is the one defined in terms of priors and likelihood and using Bayes theorem, which is clearly the case of Gaussian processes. Notice however that there are generalizations of the Bayesian approach that would be considered by many still as Bayesian approaches, e.g. ABC (see approximate-bayesian-computation) that do not even try to directly calculate the Bayes theorem and consider scenarios where this is not possible.

Finally, you seem to be sticking to the idea of Bayesian updating but notice that for some Bayesian models, it would not be possible in practice to do such an update at all. For example, if you are using Markov Chain Monte Carlo for sampling from the posterior distribution to get an approximation of it, there is no simple way of using those samples as a prior for another model.

Answer 2

Your Proposition 1 is wrong, because calculating the posterior can require an increasing number of computations for every additional data point.

A simple example that demonstrates it is a mixture distribution: suppose that $$ x \sim pf_1(x|\theta) + (1-p)f_2(x|\varphi).$$

Namely, $x$ comes from a mixture distribution with two components that are parametrized by $\theta$ and $\varphi$, on which you have some prior $\pi(\theta,\varphi)$. The posterior distribution after observing the first sample $x_1$ will become also a mixture distribution with two components:

$$P(\theta,\varphi|x_1) \propto pf_1(x_1|\theta)\pi(\theta,\varphi) + (1-p)f_2(x_1|\varphi)\pi(\theta,\varphi)$$

The posterior distribution after observing the second sample $x_2$ will then become a mixture distribution with four components :

$$P(\theta,\varphi|x_1,x_2) \propto (pf_1(x_1|\theta)\pi(\theta,\varphi) + (1-p)f_2(x_1|\varphi)) \times (pf_1(x_1|\theta)\pi(\theta,\varphi) + (1-p)f_2(x_1|\varphi)\pi(\theta,\varphi))$$

And so on. After observing $n$ samples the posterior will be a mixture of $2^n$ components, so the amount of calculations requires grows exponentioaly.

Since this proposition is wrong, everything else that follows from it is clearly also wrong.