Vecchia approximation

Vecchia approximation is a Gaussian processes approximation technique originally developed by Aldo Vecchia, a statistician at United States Geological Survey. It is one of the earliest attempts to use Gaussian processes in high-dimensional settings. It has since been extensively generalized giving rise to many contemporary approximations.

Vecchia approximation is a Gaussian processes approximation technique originally developed by Aldo Vecchia, a statistician at United States Geological Survey. It is one of the earliest attempts to use Gaussian processes in high-dimensional settings. It has since been extensively generalized giving rise to many contemporary approximations. P(A,B,C) = P(A) P(B | A) P(C | A,B) Vecchia's approximation takes the form, for example, P(A,B,C) \approx P(A) P(B | A) P(C | A ) and is accurate when events B and C are close to conditionally independent given knowledge of A . Of course one could have alternatively chosen the approximation P(A,B,C) \approx P(A) P(B|A) P(C | B) and so use of the approximation requires some knowledge of which events are close to conditionally independent given others. Moreover, we could have chosen a different ordering, for example P(A,B,C) \approx P(C) P(C|A) P(B|A). Fortunately, in many cases there are good heuristics making decisions about how to construct the approximation. More technically, general versions of the approximation lead to a sparse Cholesky factor of the precision matrix. Using the standard Cholesky factorization produces entries which can be interpreted as conditional correlations with zeros indicating no dependence (since the model is Gaussian). These independence relations can be alternatively expressed using graphical models and there exist theorems linking graph structure and vertex ordering with zeros in the Cholesky factor. In particular, it is known that independencies that are encoded in a moral graph lead to Cholesky factors of the precision matrix that have no fill-in. Let x be a Gaussian process indexed by \mathcal{S} with mean function \mu and covariance function K . Assume that S = \{s_1, \dots, s_n\} \subset \mathcal{S} is a finite subset of \mathcal{S} and \mathbf{x} = (x_1, \dots, x_n) is a vector of values of x evaluated at S , i.e. x_i = x(s_i) for i=1, \dots, n . Assume further, that one observes \mathbf{y} = (y_1, \dots, y_n) where y_i = x_i + \varepsilon_i with \varepsilon_i \overset{\text{i.i.d.}}{\sim} \mathcal{N}(0, \sigma^2) . In this context the two most common inference tasks include evaluating the likelihood \mathcal{L}(\mathbf{y}) = \int f(\mathbf{y}, \mathbf{x}) \, d\mathbf{x}, or making predictions of values of x for s^* \in \mathcal{S} and s \not\in S , i.e. calculating f(x(s^*)\mid y_1, \dots, y_n). The original Vecchia method starts with the observation that the joint density of observations f(\mathbf{y}) = \left(y_1, \dots, y_n\right) can be written as a product of conditional distributions f(\mathbf{y}) = f(y_1)\prod_{i=2}^n f(y_i\mid y_{i-1}, \dots, y_1). Vecchia approximation assumes instead that for some k \ll n \hat{f}(\mathbf{y}) = f(y_1)\prod_{i=2}^n f(y_i\mid y_{i-1}, \dots, y_{\max(i-k,1)} ). Vecchia also suggested that the above approximation be applied to observations that are reordered lexicographically using their spatial coordinates. While his simple method has many weaknesses, it reduced the computational complexity to \mathcal{O}(nk^3) . Many of its deficiencies were addressed by the subsequent generalizations. To describe extensions of the Vecchia method in its most general form, define z_i = (x_i, y_i) and notice that for \mathbf{z} = (z_1, \dots, z_n) it holds that like in the previous section f(\mathbf{z}) = f(x_1, y_1) \left( \prod_{i=2}^n f(x_i\mid z_{1:i-1}) \right) \left( \prod_{i=2}^n f(y_i\mid x_i) \right) because given x_i all other variables are independent of y_i . \hat{f}(\mathbf{z}) = f(x_1, y_1) \left( \prod_{i=2}^n f(x_i\mid z_{q(i)}) \right) \left( \prod_{i=2}^n f(y_i\mid x_i) \right), where q(i) \subset \left\{1, \dots, i-1\right\} . Since y_i \perp x_{-i}, y_{-i} \mid x_i it follows that f(x_i\mid z_{q(i)}) = f(x_i\mid x_q(i), y_q(i)) = f(x_i\mid x_q(i)) since suggesting that the terms f(x_i\mid z_{q(i)}) be replaced with f(x_i\mid x_{q(i)}) . It turns out, however, that sometimes conditioning on some of the observations z_i increases sparsity of the Cholesky factor of the precision matrix of (\mathbf{x}, \mathbf{y}) . Therefore, one might instead consider sets q_y(i) and q_x(i) such that q(i) = q_y(i) \cup q_x(i) and express \hat{f} as \hat{f}(\mathbf{z}) = f(x_1, y_1) \left( \prod_{i=2}^n f(x_i\mid x_{q_x(i)}, y_{q_y(i)}) \right) \left( \prod_{i=2}^n f(y_i\mid x_i) \right). Multiple methods of choosing q_y(i) and q_x(i) have been proposed, most notably the nearest-neighbour Gaussian process (NNGP), meshed Gaussian process and multi-resolution approximation (MRA) approaches using q(i) = q_x(i) , standard Vecchia using q(i) = q_y(i) and Sparse General Vecchia where both q_y(i) and q_x(i) are non-empty.

Notes

Text derived from https://en.wikipedia.org/w/index.php?oldid=1362795859 under CC BY-SA 4.0; modifications have been made.