4 ms·

I am familiar with basic regression theory and numerical optimization; I have a qualitative understanding of VC bound. Given this background: What is the numbe

I am familiar with basic regression theory and numerical optimization; I have a qualitative understanding of VC bound. Given this background: What is the number of parameters in a GP model? A parametric regression/classification model has some number of parameters, and having estimated them I only need to carry them around. If a model has more parameters, it is less parsimonious and less desirable than a model with fewer parameters that achieves the same error. If I add regularization/bias/prior to a model, it reduces the dimension of parameter-space. In a GP model I need to hold on to my entire training set. But clearly the number of parameters I'm fitting is much smaller. So how do I quantify that? To be clear, I'm not talking about the hyperparameters of the covariance function.

mccourt 11y ago
I am not exactly sure what you are asking here, but I think that is more a terminology disconnect than anything. I haven't even heard someone say Vapnik-Chervonenkis dimension in a long time, so we may be coming at this from two different standpoints. But I'll try to answer as best I can. When you say parametric regression model, do you mean something like s(x) = a + bx where the parameters here are a and b? If that's the case then I might say that a GP model has N parameters, where there are N pieces of data. You could argue (and I think Rasmussen does) that GPs are nonparametric, since there are N parameters and N pieces of data, but I don't usually use that term about GPs. As you point out, you do not need to carry around the data after you have fit something like a s(x) = a + bx model ... you only need a and b to make predictions. This is not true for GPs, where you will always need the {x_1, ..., x_N} points in order to make predictions. The benefit to using these kernels as your basis s(x) = c_1K(x, x_1) + ... + c_NK(x, x_N) instead of s(x) = a + bx + cy + dx^2 + ... is that there is a guaranteed unique interpolant to your data. It would depend on how you define "error" (and this is a constant issue in any sort of real-world setting) but if you are defining error by how well your model fits the data then a GP model would perfectly fit any data. I'm not saying that is really what you want (I talk in http://blog.sigopt.com/post/132959177928/sigopt-fundamentals-approximation-of-data http://blog.sigopt.com/post/132959177928/sigopt-fundamentals... about why that is a bad idea at times), but I am suggesting that there are certain properties that GPs satisfy very nicely. I would need to understand why you are saying that the number of parameters you are fitting is much smaller. I don't immediately know how you can guarantee that just by looking at a bunch of x and y values. If there is a specific reason you think your data came from a very simple function, then that would make sense, but if you can't make that assumption I don't know why it would immediately be preferable to use one model over another. Given that, if you do think that your data came from a relatively low parameter source (to put it in tangible terms, suppose you have 20000 pieces of data and you think you should only need 50 components in your s function) then you can create a 50 term model using reproducing kernels instead of polynomials (or whatever else). This is often called an RBF network (or kernel network). You can find a great reference online (http://www.eng.buffalo.edu/~psingla/Teaching/MAE502/ReadingPapers/IntroductionRBF.pdf http://www.eng.buffalo.edu/~psingla/Teaching/MAE502/ReadingP...) or a decent reference in chapter 18 of my book (kernel-based approximation methods in Matlab). If you choose to use this strategy you would be creating a model where you would only have to carry around 50 parameters, instead of the 20000 that you would have to use in the GP setting. The benefit over polynomials would be flexibility and locality, the benefit over GPs would be cost (50<<20000 so predictions are cheaper). There are also Support Vector Machines/Regression which do this stuff in a sparse framework (less that 20000 basis functions) using reproducing kernels. Basically, I would totally agree with you that simpler is better. A the end of the day, I think of GPs as a useful tool for identifying local behavior, but I try not to use them globally (although in this paper I looked at the global limit, http://epubs.siam.org/doi/abs/10.1137/110824784 http://epubs.siam.org/doi/abs/10.1137/110824784). Probably the best strategy, if you believe that your data comes from a low complexity function and should only need a few parameters to fit it well is to explicitly define a nonzero mean for your GP; see (Chapter 2.7 in http://www.gaussianprocess.org/gpml/chapters/RW2.pdf http://www.gaussianprocess.org/gpml/chapters/RW2.pdf) or Chapter 17.3 in my book. This lets the low parameter model handle most of the heavy lifting and the GP handles the final touches. You still have to carry around the N pieces of data (sorry) but you get closer to that parsimonious result that you wanted. Incidentally, if you're just worried about carrying around more data than you want to, or that the cost of making predictions is too high, there are computational techniques to deal with this. Two good friends of mine, Lei Wang with tree codes (http://epubs.siam.org/doi/abs/10.1137/120903002 http://epubs.siam.org/doi/abs/10.1137/120903002) and Jie Chen with H-matrices/semiseparable/recursive rank (http://www.mcs.anl.gov/papers/P5112-0314.pdf http://www.mcs.anl.gov/papers/P5112-0314.pdf), worked on something like this for massive problems (I think Jie Chen was in the billions while we were at Argonne together). So there are options out there even for those extreme cases, depending on what your situation/goal is. Hope that helped. Thanks for reading.
- kshitijl 11y ago
  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

I am not exactly sure what you are asking here, but I think that is more a terminology disconnect than anything. I haven't even heard someone say Vapnik-Chervonenkis dimension in a long time, so we may be coming at this from two different standpoints. But I'll try to answer as best I can. When you say parametric regression model, do you mean something like s(x) = a + bx where the parameters here are a and b? If that's the case then I might say that a GP model has N parameters, where there are N pieces of data. You could argue (and I think Rasmussen does) that GPs are nonparametric, since there are N parameters and N pieces of data, but I don't usually use that term about GPs. As you point out, you do not need to carry around the data after you have fit something like a s(x) = a + bx model ... you only need a and b to make predictions. This is not true for GPs, where you will always need the {x_1, ..., x_N} points in order to make predictions. The benefit to using these kernels as your basis s(x) = c_1K(x, x_1) + ... + c_NK(x, x_N) instead of s(x) = a + bx + cy + dx^2 + ... is that there is a guaranteed unique interpolant to your data. It would depend on how you define "error" (and this is a constant issue in any sort of real-world setting) but if you are defining error by how well your model fits the data then a GP model would perfectly fit any data. I'm not saying that is really what you want (I talk in http://blog.sigopt.com/post/132959177928/sigopt-fundamentals-approximation-of-data http://blog.sigopt.com/post/132959177928/sigopt-fundamentals... about why that is a bad idea at times), but I am suggesting that there are certain properties that GPs satisfy very nicely. I would need to understand why you are saying that the number of parameters you are fitting is much smaller. I don't immediately know how you can guarantee that just by looking at a bunch of x and y values. If there is a specific reason you think your data came from a very simple function, then that would make sense, but if you can't make that assumption I don't know why it would immediately be preferable to use one model over another. Given that, if you do think that your data came from a relatively low parameter source (to put it in tangible terms, suppose you have 20000 pieces of data and you think you should only need 50 components in your s function) then you can create a 50 term model using reproducing kernels instead of polynomials (or whatever else). This is often called an RBF network (or kernel network). You can find a great reference online (http://www.eng.buffalo.edu/~psingla/Teaching/MAE502/ReadingPapers/IntroductionRBF.pdf http://www.eng.buffalo.edu/~psingla/Teaching/MAE502/ReadingP...) or a decent reference in chapter 18 of my book (kernel-based approximation methods in Matlab). If you choose to use this strategy you would be creating a model where you would only have to carry around 50 parameters, instead of the 20000 that you would have to use in the GP setting. The benefit over polynomials would be flexibility and locality, the benefit over GPs would be cost (50<<20000 so predictions are cheaper). There are also Support Vector Machines/Regression which do this stuff in a sparse framework (less that 20000 basis functions) using reproducing kernels. Basically, I would totally agree with you that simpler is better. A the end of the day, I think of GPs as a useful tool for identifying local behavior, but I try not to use them globally (although in this paper I looked at the global limit, http://epubs.siam.org/doi/abs/10.1137/110824784 http://epubs.siam.org/doi/abs/10.1137/110824784). Probably the best strategy, if you believe that your data comes from a low complexity function and should only need a few parameters to fit it well is to explicitly define a nonzero mean for your GP; see (Chapter 2.7 in http://www.gaussianprocess.org/gpml/chapters/RW2.pdf http://www.gaussianprocess.org/gpml/chapters/RW2.pdf) or Chapter 17.3 in my book. This lets the low parameter model handle most of the heavy lifting and the GP handles the final touches. You still have to carry around the N pieces of data (sorry) but you get closer to that parsimonious result that you wanted. Incidentally, if you're just worried about carrying around more data than you want to, or that the cost of making predictions is too high, there are computational techniques to deal with this. Two good friends of mine, Lei Wang with tree codes (http://epubs.siam.org/doi/abs/10.1137/120903002 http://epubs.siam.org/doi/abs/10.1137/120903002) and Jie Chen with H-matrices/semiseparable/recursive rank (http://www.mcs.anl.gov/papers/P5112-0314.pdf http://www.mcs.anl.gov/papers/P5112-0314.pdf), worked on something like this for massive problems (I think Jie Chen was in the billions while we were at Argonne together). So there are options out there even for those extreme cases, depending on what your situation/goal is. Hope that helped. Thanks for reading.

kshitijl 11y ago
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.