3 ms·

With N parameters for N data points I have far, far too many degrees of freedom and have grossly overfit my training set. The only way to guarantee good general

With N parameters for N data points I have far, far too many degrees of freedom and have grossly overfit my training set. The only way to guarantee good generalization outside one's training set is to have a lot of data compared to the number of degrees of freedom in the model. To avoid this, we use bias/prior/regularization which reduces the effective number of degrees of freedom. For example, fitting a quadratic polynomial to some data, we have 3 degrees of freedom including the constant term. If I add a regularization term \lambda*||a|| where a is the vector of coefficients, I can alleviate overfitting. We can determine an optimal value for \lambda using validation or cross-validation. For \lambda=0, we have 3 parameters. As \lambda->infinity, we force the answer closer and closer to the constant 0 polynomial ie. no degrees of freedom. In other words, regularization avoids overfitting by reducing the dimension of the model. I am not worried about the amount of data I have to carry around; rather, it was a way of thinking about the dimension of parameter-space. Don't big alarm bells go off in your head when you hear N parameters for N data points?

glial 11y ago
> Don't big alarm bells go off in your head when you hear N parameters for N data points? Gaussian process models typically also have hyperparameters that control things like the smoothness of the learned surface. My hand-wavey sense of how GPs work is that you have a prior distribution over functions (think curves) and a hyperparameter controlling the smoothness/length-scale of those functions. You observe data, then find the posterior distribution over functions that make your data most likely - i.e. of all these possible functions, which ones have the best chance of actually generating the data you're observing? The shape of that posterior distribution depends on the set of N points you observe, and it will be different if you have different data. In that sense, then, the data are parameters, since the posterior depends exactly on the set of data. The analogy to traditional regression comes by having the hyperparameters (controlling the covariance function IIRC, i.e. the smoothness of the posterior curves), which allows the resulting posterior distribution to explain the data perfectly (overfitting, sharp curves) or not (generalizability, smooth curves). See for example slides 23-24 of this slide deck: https://www.cs.toronto.edu/~hinton/csc2515/notes/gp_slides_fall08.pdf https://www.cs.toronto.edu/~hinton/csc2515/notes/gp_slides_f... Rasmussen has some useful video tutorials of all this. It's been a few years since I've watched them but if you're interested I'd recommend them.
mccourt 11y ago
Well, this is the difference in phrasing between the traditional statistical modeling setting and the terminology used in numerical analysis; perhaps this is why GPs are sometimes referred to as a nonparametric model. Also, I think you're oversimplifying the role of regularization, but that's more of a semantic than salient point. You are correct that you should not use "N parameters for N data points", but the role that covariance kernels play is not the same as the role played by (as you suggest) polynomials. Covariance kernels have some sort of localized behavior which limits the degree to which they interact with the data. Not to limit the discussion to things I'm comfortable with, but I wrote some of this up at a very high level here http://blog.sigopt.com/post/131498069303/sigopt-fundamentals-intuition-behind-covariance http://blog.sigopt.com/post/131498069303/sigopt-fundamentals.... As a result, I think one could argue that the compactness of their domain (practical compactness, regardless of their potentially infinite support) produces the actual dimension of the parameter space. As such, different locations in the domain may have different dimensionality, though most of the time the swift decay of kernels away from their center will lead to a much lower "effective dimensionality" than N. Maybe a good way to think of this is the following: Why are you using a quadratic polynomial to fit your (presumably, if you have only 3 parameters) 1D data? Probably just because you feel like it - which is as good a reason as any, short of some rigorous statistical testing. I use kernels because I like their theoretical properties, not because "the data demands it" or some more rigorous reason. But suppose you actually thought of the biggest polynomial you could use: an N-1 degree polynomial: s(x) = a_1 + a_2x + a_3x^2 + a_4x^3 + ... + a_Nx^{N-1} That's the biggest (unique) polynomial you could use to fit your data. You feel, probably correctly, that N terms is too many, so you zero out some of these terms by manually setting most of the coefficients equal to 0 and solving (somehow) for the rest: s(x) = a_1 + a_2x + a_3x^2 + 0x^3 + ... + 0x^{N-1} This is one, very common and very useful way, to fit data, and it is the first thing I teach when I introduce people to approximation theory. But think about the main drawback behind this method: this is the same function everywhere that you want to make approximations. You have no ability to do anything different in different regions of your domain. You could have a problem for which this is true, but I think a lot of problems have some degree of spatial variability/locality, and this is where kernel methods shine. Kernel methods propose that you fit a model that looks like s(x) = a_1K(x,x_1) + a_2K(x,x_2) + a_3K(x,x_3) + a_4K(x,x_4) + ... + a_NK(x,x_N) Now, does this require you to invert an NxN matrix - absolutely. But because there is some locality in these K functions, different kernels will end up being 0 in different locations. Suppose that x_4 through x_N are very far from x_1; your interpolation in that setting looks like: s(x) = a_1K(x,x_1) + a_2K(x,x_2) + a_3K(x,x_3) + a_4 0 + ... + a_N 0 , for x close to x_1 Notice I use the term "close" here; the decision of what close means is the hyperparameter solution that this blog post was trying to allude to, and that this other post http://blog.sigopt.com/post/134931028143/sigopt-in-depth-profile-likelihood-vs-kriging http://blog.sigopt.com/post/134931028143/sigopt-in-depth-pro... addresses more thoroughly. These summation values are probably not identically 0 (although it could be, if you like the Wendland or Wu kernels) but it may be close enough to think of it as 0. Suppose, instead, that you are over near x_N and that only x_4 is close to x_N: s(x) = a_1 0 + a_2 0 + a_3 0 + a_4 K(x,x_4) + ... + a_N K(x,x_N) , for x close to x_N Notice that both the polynomial and kernel methods have less than N terms which are nonzero, but only the kernel method has the ability to deal with regional differences within your problem. That's the benefit for kernel methods over polynomials; they more intelligently zero out a bunch of the terms in the summation. Incidentally, this is also the outcome of using support vector machines/regression, although that problem is phrased in a different way and chooses which pieces of data are worth considering, not which basis functions should be considered. But, I digress ... You are absolutely correct to be worried about overfitting: it is the bane of all people who do any sort of statistical modeling and it will cause problems if you are not wary. But kernels are not inherently problematic on this front. First off, they offer a locality that can have a similar effect as polynomial fitting, but with the benefit of acting locally rather than globally. Perhaps the best point to be made though is that you can combine a polynomial method (for global action) with a kernel method (for local action). That's sometimes called universal kriging, and is basically just GPs with a nonzero (polynomial) mean. My book has an example of this in chapter 17.3, and Rasmussen and Williams talks about this in chapter 2.7 (http://www.gaussianprocess.org/gpml/chapters/RW2.pdf http://www.gaussianprocess.org/gpml/chapters/RW2.pdf). I would also mention that regularization is something that can be done in the GP framework. I described the impact in http://blog.sigopt.com/post/132959177928/sigopt-fundamentals-approximation-of-data http://blog.sigopt.com/post/132959177928/sigopt-fundamentals... at a high level, but you can read more about it in chapter 15.1 of my book, or under the name smoothing spline (https://en.wikipedia.org/wiki/Smoothing_spline https://en.wikipedia.org/wiki/Smoothing_spline, though not the best writeup), or in RBF networks. If you really want to get fancy, you could even make the argument that interpolation with reproducing kernels has some built-in regularization because the interpolant is the minimum norm interpolating function in the Hilbert space; I don't have an easily accessible reference for that but you can see the derivation worked out here http://math.iit.edu/~fass/590/notes/Notes590_Ch8Print.pdf http://math.iit.edu/~fass/590/notes/Notes590_Ch8Print.pdf. That's not the same norm that you are referring to above, but I mention it simply to note that people in the kernel community are as worried about this situation as you are and we have some results that help inform of how to deal with potential overfitting. Thanks for your interest. I really appreciate the opportunity to go in depth with this.

glial 11y ago

> Don't big alarm bells go off in your head when you hear N parameters for N data points? Gaussian process models typically also have hyperparameters that control things like the smoothness of the learned surface. My hand-wavey sense of how GPs work is that you have a prior distribution over functions (think curves) and a hyperparameter controlling the smoothness/length-scale of those functions. You observe data, then find the posterior distribution over functions that make your data most likely - i.e. of all these possible functions, which ones have the best chance of actually generating the data you're observing? The shape of that posterior distribution depends on the set of N points you observe, and it will be different if you have different data. In that sense, then, the data are parameters, since the posterior depends exactly on the set of data. The analogy to traditional regression comes by having the hyperparameters (controlling the covariance function IIRC, i.e. the smoothness of the posterior curves), which allows the resulting posterior distribution to explain the data perfectly (overfitting, sharp curves) or not (generalizability, smooth curves). See for example slides 23-24 of this slide deck: https://www.cs.toronto.edu/~hinton/csc2515/notes/gp_slides_fall08.pdf https://www.cs.toronto.edu/~hinton/csc2515/notes/gp_slides_f... Rasmussen has some useful video tutorials of all this. It's been a few years since I've watched them but if you're interested I'd recommend them.

mccourt 11y ago

Well, this is the difference in phrasing between the traditional statistical modeling setting and the terminology used in numerical analysis; perhaps this is why GPs are sometimes referred to as a nonparametric model. Also, I think you're oversimplifying the role of regularization, but that's more of a semantic than salient point. You are correct that you should not use "N parameters for N data points", but the role that covariance kernels play is not the same as the role played by (as you suggest) polynomials. Covariance kernels have some sort of localized behavior which limits the degree to which they interact with the data. Not to limit the discussion to things I'm comfortable with, but I wrote some of this up at a very high level here http://blog.sigopt.com/post/131498069303/sigopt-fundamentals-intuition-behind-covariance http://blog.sigopt.com/post/131498069303/sigopt-fundamentals.... As a result, I think one could argue that the compactness of their domain (practical compactness, regardless of their potentially infinite support) produces the actual dimension of the parameter space. As such, different locations in the domain may have different dimensionality, though most of the time the swift decay of kernels away from their center will lead to a much lower "effective dimensionality" than N. Maybe a good way to think of this is the following: Why are you using a quadratic polynomial to fit your (presumably, if you have only 3 parameters) 1D data? Probably just because you feel like it - which is as good a reason as any, short of some rigorous statistical testing. I use kernels because I like their theoretical properties, not because "the data demands it" or some more rigorous reason. But suppose you actually thought of the biggest polynomial you could use: an N-1 degree polynomial: s(x) = a_1 + a_2x + a_3x^2 + a_4x^3 + ... + a_Nx^{N-1} That's the biggest (unique) polynomial you could use to fit your data. You feel, probably correctly, that N terms is too many, so you zero out some of these terms by manually setting most of the coefficients equal to 0 and solving (somehow) for the rest: s(x) = a_1 + a_2x + a_3x^2 + 0x^3 + ... + 0x^{N-1} This is one, very common and very useful way, to fit data, and it is the first thing I teach when I introduce people to approximation theory. But think about the main drawback behind this method: this is the same function everywhere that you want to make approximations. You have no ability to do anything different in different regions of your domain. You could have a problem for which this is true, but I think a lot of problems have some degree of spatial variability/locality, and this is where kernel methods shine. Kernel methods propose that you fit a model that looks like s(x) = a_1K(x,x_1) + a_2K(x,x_2) + a_3K(x,x_3) + a_4K(x,x_4) + ... + a_NK(x,x_N) Now, does this require you to invert an NxN matrix - absolutely. But because there is some locality in these K functions, different kernels will end up being 0 in different locations. Suppose that x_4 through x_N are very far from x_1; your interpolation in that setting looks like: s(x) = a_1K(x,x_1) + a_2K(x,x_2) + a_3K(x,x_3) + a_4 0 + ... + a_N 0 , for x close to x_1 Notice I use the term "close" here; the decision of what close means is the hyperparameter solution that this blog post was trying to allude to, and that this other post http://blog.sigopt.com/post/134931028143/sigopt-in-depth-profile-likelihood-vs-kriging http://blog.sigopt.com/post/134931028143/sigopt-in-depth-pro... addresses more thoroughly. These summation values are probably not identically 0 (although it could be, if you like the Wendland or Wu kernels) but it may be close enough to think of it as 0. Suppose, instead, that you are over near x_N and that only x_4 is close to x_N: s(x) = a_1 0 + a_2 0 + a_3 0 + a_4 K(x,x_4) + ... + a_N K(x,x_N) , for x close to x_N Notice that both the polynomial and kernel methods have less than N terms which are nonzero, but only the kernel method has the ability to deal with regional differences within your problem. That's the benefit for kernel methods over polynomials; they more intelligently zero out a bunch of the terms in the summation. Incidentally, this is also the outcome of using support vector machines/regression, although that problem is phrased in a different way and chooses which pieces of data are worth considering, not which basis functions should be considered. But, I digress ... You are absolutely correct to be worried about overfitting: it is the bane of all people who do any sort of statistical modeling and it will cause problems if you are not wary. But kernels are not inherently problematic on this front. First off, they offer a locality that can have a similar effect as polynomial fitting, but with the benefit of acting locally rather than globally. Perhaps the best point to be made though is that you can combine a polynomial method (for global action) with a kernel method (for local action). That's sometimes called universal kriging, and is basically just GPs with a nonzero (polynomial) mean. My book has an example of this in chapter 17.3, and Rasmussen and Williams talks about this in chapter 2.7 (http://www.gaussianprocess.org/gpml/chapters/RW2.pdf http://www.gaussianprocess.org/gpml/chapters/RW2.pdf). I would also mention that regularization is something that can be done in the GP framework. I described the impact in http://blog.sigopt.com/post/132959177928/sigopt-fundamentals-approximation-of-data http://blog.sigopt.com/post/132959177928/sigopt-fundamentals... at a high level, but you can read more about it in chapter 15.1 of my book, or under the name smoothing spline (https://en.wikipedia.org/wiki/Smoothing_spline https://en.wikipedia.org/wiki/Smoothing_spline, though not the best writeup), or in RBF networks. If you really want to get fancy, you could even make the argument that interpolation with reproducing kernels has some built-in regularization because the interpolant is the minimum norm interpolating function in the Hilbert space; I don't have an easily accessible reference for that but you can see the derivation worked out here http://math.iit.edu/~fass/590/notes/Notes590_Ch8Print.pdf http://math.iit.edu/~fass/590/notes/Notes590_Ch8Print.pdf. That's not the same norm that you are referring to above, but I mention it simply to note that people in the kernel community are as worried about this situation as you are and we have some results that help inform of how to deal with potential overfitting. Thanks for your interest. I really appreciate the opportunity to go in depth with this.