2

I have been reading the Hastie and Tibshirani book again lately, and I noticed in Chapter 9 that the mention the MARS algorithm: Multivariate Adaptive Regression Splines, which is a nonparametric method for fitting a curve to some data.

My question was, how well does this technique work on high-dimensional data? If I remember correctly, one of the key arguments against nonparametric or local regression models was that they did not work very well on high dimensional problems. In high dimensions, the points are already so far away, that you end up creating very wide bins for the data, and this defeats the purpose of local regression or nonparametric methods. This problem was one of the reasons why Tree based methods became so popular.

However, the Hastie and Tibshirani book., Elements of Statistical Learning introduces the MARS algorithm in the same chapter as Tree based methods. So I can't tell if MARS overcomes the problem with dimension that other similar methods have. Does anyone know the answer?

Note that I checked Wikipedia and the HT book itself, but they don't address this question.

krishnab
  • 1,008
  • 7
  • 12

1 Answers1

2

In high dimensions, the points are already so far away, that you end up creating very wide bins for the data, and this defeats the purpose of local regression or nonparametric methods.

This 'curse of dimensionality' mostly occurs when the predictors are considered in tandem; not when variables are considered one-by-one, which is essentially what tree-based methods do, and MARS also. In each of the separate dimensions spanned by the predictors variables, the distance between points does not increase.

I expect MARS can do well in high dimensions, if interaction depth is kept low and probably some sparsity should be enforced. The latter can be done by not allowing the forward pass to select a large number of terms, and/or not allowing the backward pass to retain a large number of terms.

Marjolein Fokkema
  • 1,363
  • 6
  • 22
  • thanks so much for the response. That is very helpful. I was wondering if you could elaborate more on this idea of the "curse of dimensionality" not being a problem when variables are considered one-by-one. If you know of a good reference on this, or perhaps this is explained in some of the tree-based papers? I can google curse of dimensionality and tree methods, but if you know of a good paper or book, please pass it along. The Hastie and Tibshirani book mention it, but did not elaborate. – krishnab Feb 05 '22 at 15:31
  • The SUBiNN method of Elsten & de Rooij (2021; https://doi.org/10.1007/s11634-021-00462-7) provides a nice illustration, I believe: "we built an ensemble method by combining nearest neighbor analyses in one and two-dimensional subspaces, thereby overcoming the curse of dimensionality". Of all (non-)parametric methods, k nearest neighbours is most badly affected by the curse of dimensionality, because it has the greatest flexibility. As you mentioned, with high enough dimensions, all points are very far apart. – Marjolein Fokkema Feb 06 '22 at 11:26
  • E&dR adapted kNN by creating a stacked learner. Base learners are distances in terms of only 1 or 2 possible predictors. The meta learner is lasso regression. The base learners a-priori restrict the predictive function, so that it can only capture main effects and two-way interactions. The meta learner enforces sparsity. Still, when $p$ increases to very high values, curse of dimensionality will kick in: distances between data points will explode at some point, but at (much) higher values of $p$ than with standard kNN where all predictors are considered in tandem and with equal weight. – Marjolein Fokkema Feb 06 '22 at 11:43
  • thanks so much for pointing out these papers. That is very helpful. I will definitely download them. – krishnab Feb 08 '22 at 13:15