# Why are Gaussian process models called non-parametric?

I am a bit confused. Why are Gaussian processes called non parametric models?

They do assume that the functional values, or a subset of them, have a Gaussian prior with mean 0 and covariance function given as the kernel function. These kernel functions themselves have some parameters (i.e., hyperparameters).

So why are they called non parametric models?

-
I know of several definitions of "Gaussian processes," so it's not apparent what your question is really asking about. But as you consider how to clarify it, ask yourself this: exactly how would you parametrize the Gaussian process you have in mind? If you cannot do it in a natural way with a finite number of real parameters, then it should be considered nonparametric. – whuber Dec 27 '12 at 16:15
@whuber. AFAIK, the main parameters of gaussian processes are the mean and the covariance functions. But as we keep on adding data points, they keep on increasing. So it keeps on increasing. Is that why gaussian processes are termed as non parametric? – user34790 Dec 27 '12 at 17:04
@whuber If I have millions of training data points, then my GP f ~ N(m,k) will be a million dimensional multivariate gaussian distribution. Isn't that too big? I mean as new training data comes it gets bigger and bigger. Doesn't it give rise to computational issue? – user34790 Dec 27 '12 at 17:06
"Parametric" versus "non-parametric" are terms that do not apply to particular processes: they apply to the entire family of processes that could be fit to data. Although I still do not know what family you have in mind, it sounds like although the number of parameters may be finite in any circumstance, there is no limit to the number of parameters that may appear among members of the family: ergo, the problem is non-parametric. – whuber Dec 27 '12 at 17:35

I'll preface this by saying that it isn't always clear what one means by "nonparametric" or "semiparametric" etc. In the comments, it seems likely that whuber has some formal definition in mind (maybe something like choosing a model $M_\theta$ from some family $\{M_\theta: \theta \in \Theta\}$ where $\Theta$ is infinite dimensional), but I'm going to be pretty informal. Some might argue that a nonparametric method is one where the effective number of parameters you use increases with the data. I think there is a video on videolectures.net where (I think) Peter Orbanz gives four or five different takes on how we can define "nonparametric."

Since I think I know what sorts of things you have in mind, for simplicity I'll assume that you are talking about using Gaussian processes for regression, in a typical way: we have training data $(Y_i, X_i), i = 1, ..., n$ and we are interested in modeling the conditional mean $E(Y|X = x) := f(x)$. We write $$Y_i = f(X_i) + \epsilon_i$$ and perhaps we are so bold as to assume that the $\epsilon_i$ are iid and normally distributed, $\epsilon_i \sim N(0, \sigma^2)$. $X_i$ will be one dimensional, but everything carries over to higher dimensions.

If our $X_i$ can take values in a continuum then $f(\cdot)$ can be thought of as a parameter of (uncountably) infinite dimension. So, in the sense that we are estimating a parameter of infinite dimension, our problem is a nonparametric one. It is true that the Bayesian approach has some parameters floating about here and there. But really, it is called nonparametric because we are estimating something of infinite dimension. The GP priors we use assign mass to every neighborhood of every continuous function, so they can estimate any continuous function arbitrarily well.

The things in the covariance function are playing a role similar to the smoothing parameters in the usual frequentist estimators - in order for the problem to not be absolutely hopeless we have to assume that there is some structure that we expect to see $f$ exhibit. Bayesians accomplish this by using a prior on the space of continuous functions in the form of a Gaussian process. From a Bayesian perspective, we are encoding beliefs about $f$ by assuming $f$ is drawn from a GP with such-and-such covariance function. The prior effectively penalizes estimates of $f$ for being too complicated.

Edit for computational issues

Most (all?) of this stuff is in the Gaussian Process book by Rasmussen and Williams.

Computational issues are tricky for GPs. If we proceed niavely we will need $O(N^2)$ size memory just to hold the covariance matrix and (it turns out) $O(N^3)$ operations to invert it. There are a few things we can do to make things more feasible. One option is to note that guy that we really need is $v$, the solution to $(K + \sigma^2 I)v = Y$ where $K$ is the covariance matrix. The method of conjugate gradients solves this exactly in $O(N^3)$ computations, but if we satisfy ourselves with an approximate solution we could terminate the conjugate gradient algorithm after $k$ steps and do it in $O(kN^2)$ computations. We also don't necessarily need to store the whole matrix $K$ at once.

So we've moved from $O(N^3)$ to $O(kN^2)$, but this still scales quadratically in $N$, so we might not be happy. The next best thing is to work instead with a subset of the data, say of size $m$ where inverting and storing an $m \times m$ matrix isn't so bad. Of course, we don't want to just throw away the remaining data. The subset of regressors approach notes that we can derive the posterior mean of our GP as a regression of our data $Y$ on $N$ data-dependent basis functions determined by our covariance function; so we throw all but $m$ of these away and we are down to $O(m^2 N)$ computations.

A couple of other potential options exist. We could construct a low-rank approximation to $K$, and set $K = QQ^T$ where $Q$ is $n \times q$ and of rank $q$; it turns inverting $K + \sigma^2 I$ in this case can be done by instead inverting $Q^TQ + \sigma^2 I$. Another option is to choose the covariance function to be sparse and use conjugate gradient methods - if the covariance matrix is very sparse then this can speed up computations substantially.

-

Generally speaking, the "nonparametric" in Bayesian nonparametrics refers to models with an infinite number of (potential) parameters. There are a lot of really nice tutorials and lectures on the subject on videolectures.net (like this one) which give nice overviews of this class of models.

Specifically, the Gaussian Process (GP) is considered nonparametric because a GP represents a function (i.e. an infinite dimensional vector). As the number of data points increases ((x, f(x)) pairs), so do the number of model 'parameters' (restricting the shape of the function). Unlike a parametric model, where the number of parameters stay fixed with respect to the size of the data, in nonparametric models, the number of parameters grows with the number of data points.

-
This is exactly what I was assuming. So my assumption is right I guess. But my question is if I have million points(observed data). Then my f will also be of million dimension. So wouldn't I have computational issues. Further my covariance matrix will also be of size 1millionx1million. So what should I do in this case? – user34790 Dec 27 '12 at 22:07
@user34790 yes, you would have computational issues. Computational challenges are quite big deal for GPs. Rasmussen and Williams have a book on GPs with an entire chapter dedicated to this, and if you google hard enough you can find it online for free. See my updated post for some minimal details. – guy Dec 28 '12 at 4:29