3
$\begingroup$

I want to prove that the variance of a Gaussian Process (GP) is the lowest on any one of its $p$ training data points.

The prior distribution for a zero-mean GP prior, with kernel function $k(x, x')$ is, $$ P\left( \begin{bmatrix} y_{*} \\ Y \end{bmatrix} \right) = \mathcal{N} \left(0, \begin{bmatrix} k(x_{*}, x_{*}) & K(x_{*}, X)\\ K(x_{*}, X)^{T} & K(X, X) \end{bmatrix} \right). \,\, (1) $$ Where,

  1. $x_{*}$ is a new potentially unseen test data point.
  2. $X$ is the prior seen training data set for which corresponding labels/observations $Y$ are available. To be precise X is a matrix with the $i^{th}$ row given by data-point $x_i$.
  3. $K(x_{*}, X)$ is a $p \times 1$ row-vector with $i^{th}$ entry given by $K(x_{*}, x_i)$.
  4. $K(X, X)$ is a $ p \times p$ matrix with the $(i, j)^{th}$ entry being given by $k(x_i, x_j)$.
  5. I am not considering any observation noise in the problem which means that labels and observations are identical and given by $y$.

For the above prior distribution, the covariance of the posterior distribution over the predicted label $y_{*}$ will be, $$ \sigma_{y_{*}} = k(x_{*}, x_{*}) - K(x_{*}, X)K(X, X)^{-1}K(x_{*}, X)^{T}. \,\,(2) $$ Where I have used the formula for the covariance of a conditional multivariate normal (MVN) random variable as is done in [1].

Among other requirements, kernel functions $k$ satisfy, $k(x, x) = 1$ so $\sigma_{y_{*}}$ being minimum for seen points present in $X$ is equivalent to, $$ \arg \max_{x_{*}} K(x_{*}, X)K(X, X)^{-1}K(x_{*}, X)^{T} = x_i \, \, \forall \, i \in [p]. \,\,(3) $$

To try and prove the condition $(3)$, I have tried the following approaches,

  1. The result is clearly true for $p=1$ since then the term in $(3)$ becomes $k(x_{*}, x_1)k(x_{1}, x_{1})^{-1}k(x_{*}, x_1)$ which will be maximum when $x_{*} = x_{1}$. So I tried writing out the product in $(3)$ for the case $p = 2$ to see if I could find a reason for it being maximized on points in $X$. For $p=2$ the expression in $(3)$ was, $$ k(x_{*}, x_1)^{2} + k(x_{*}, x_2)^{2} - 2 k(x_1, x_2) k(x_{*}, x_1) k(x_{*}, x_2). $$ For this $p = 2$ case $X = [x_1^{T} \, x_2^{T}]^{T}$ and I don't see why we'll have maximums at $x_{*} = x_1$ and $x_{*} = x_2$.
  2. Next I tried putting in the RBF/Squared-Exponential kernel $k(x, x') = \exp{\left(-\frac{1}{2 l_{d}^2} (x - x') \right)}$ into the expression for $p=2$ I got above and took the derivative of the expression with respect to $x_{*}$ and set this derivative to 0. While plugging in $x_1$ and $x_2$ does make the derivative evaluate to $0$ it is not clear if those two will be the only solutions to the equation
  3. Since I could see the result holding for $p=1$ I thought of trying an inductive approach where I assume that $(3)$ holds for some $p=m$ and I attempt to extend it to $p=m+1$ by expanding $k(x_{*}, X_{p})$ to $[k(x_{*}, X_{p}) \,\, k(x_{*}, x_{p + 1})]$ and analogously expanding $K_{XX}$; however I don't think optimization problems (or at least this problem) can be fit into an inductive framework.
  4. An argument for the result is that $\sigma_{y_{*}}$ can only be a valid variance if the expression in $(2)$ $\geq 0$. This in turn requires that, $$ K(x_{*}, X)K(X, X)^{-1}K(x_{*}, X)^{T} \leq k(x_{*}, x_{*}) = 1. \,\, (4) $$ Now it easy to show that $\sigma_{y_{*}} = 0$ when $x_{*}$ is a test-point from $X$ so by (4) we get the required result of the variance being minimum and equal to $0$ on test-points. However I am discounting this argument as circular.
$\endgroup$
1
  • $\begingroup$ There is nothing circular about your argument 4: you've shown that a given function is nonnegative, and then you've found a point at which it takes value 0. This point is necessarily a global minimizer; it's a sound argument. Now, it does not imply that there won't be some non-training point that also has zero variance. Actually, this will be the case for certain kernels, notably tensor sum kernels. See e.g. arxiv.org/pdf/1112.4394.pdf. $\endgroup$ Feb 20 at 23:45

1 Answer 1

2
$\begingroup$

For noise free case, when $x_* = x_i$ for some i, then $k(x_*, X)$ is the $i$th column of $K(X,X)$. Thus, you obtain

$K(X,X)^{-1} k(x_i,X)^T = \mathbf{e}_i$ where $\mathbf{e}_i$ denotes a standard basis of $\mathbb{R}^N$

Thus, $\sigma_{y_*} = k(x_i , x_i) - k(x_i, X) \mathbf{e}_i = k(x_i, x_i) - k(x_i, x_i) = 0$ and this is global minimum.

$\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.