3
$\begingroup$

I have seen a lot of studies and articles explaining the definition of curse of dimensionality and its effects.

However, I am curious about if is there any learning method that is resistant to the curse of dimensionality? That is, the performance degradation of the learning method is negligible compared to the growth of the dimension of the feature space?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Kernel methods are close to immune. $\endgroup$
    – Marc Claesen
    Commented Feb 16, 2015 at 9:21
  • 2
    $\begingroup$ Some say dimensionality can be a blessing, not necessarily a curse. Check out Breiman "Statistical Modeling: The Two Cultures", Section 10 and comments (search for word "blessing"). It explains that, for example, support vector machines (SVM) thrive on dimensionality, not suffer from it. $\endgroup$
    – Richard Hardy
    Commented Feb 16, 2015 at 9:24
  • 1
    $\begingroup$ If the relevant features are already in your list of features (and you don't know this in advance), adding irrelevant features on top always (at least according to my experience) reduces out of sample performance even when you use regularization. Same applies to Kernel methods (to disagree with above comment). $\endgroup$
    – Cagdas Ozgenc
    Commented Feb 16, 2015 at 11:20
  • $\begingroup$ @CagdasOzgenc You are right. But irrelevant features seem to be beyond the scope of curse of dimensionality. $\endgroup$
    – shihpeng
    Commented Feb 17, 2015 at 8:05
  • 1
    $\begingroup$ @shihpeng, no it is not. Because you don't know which ones are relevant which ones are not. That is the problem. And there will be features that are relevant but their contribution won't be able to beat the statistical variation they create by including them given the sample size. Even if you can trim them using regularization, or other ensemble approaches, not having them in the first place is better as they may be accidentally included in the model when there are too many of them. $\endgroup$
    – Cagdas Ozgenc
    Commented Feb 17, 2015 at 10:59

1 Answer 1

Reset to default
2
$\begingroup$

Performance degradation due to growth of dimensionality comes from the fact that as the number of "visits" in the space of all possible feature sets increases, the probability to find an effect just by chance increases also. Of course, time to traverse all solution space also goes sky-high thus degrading the performance computation time-wise.

Therefore, the only methods that would perform better in the case of many dimensions are the ones that make those "visits" in a smart way. I know two such methods: meta analysis, and smart heuristics such as Monte Carlo Markov Chains.

Meta analysis is used successfully for example, in bioinformatics, where given that number of records (subjects in a study) is usually much less than number of features (say genetic polymorhpisms), any effect gets killed very often by the multiple comparison correction. So a lot of research groups use candidate gene approach, where the candidate genes (predictors) are being selected based on the overall understanding of modern genomics, including already published results by other groups. This reduces the feature space dramatically.

Sampling methods such as MCMC reduce the feature space by traversing it in a smart way: roughly speaking searching for a maximum such as gradient while allowing to jump to a random point to avoid getting stuck in local maxima.

Improve this answer
$\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.