Best strategy to maximize the prediction accuracy when p >> n

Question

I am solving the following classification problem:

• thousands of features, but only 40 samples (i.e. p >> n)
• classes are balanced
• it is not possible to get more data
• the only thing I am interested in is the prediction accuracy on new data
• I also need to estimate the generalization error as accurately as possible

I know that this kind of problem is very hard, but assuming I cannot get more data, what is the best strategy I can do to maximize the prediction accuracy? For example:

• regarding the cross-validation, what is the best CV strategy?
• regarding the choice of supervised algorithm, are there any models that are more suitable for this kind of problem than others? On the other hand, are there any that are totally unsuitable? Are linear or non-linear models better here?
• are there any important settings of ML algorithms that are important here?
• are there any other important things that should be always done here (feature selection, dimensionality reduction, ...)?

For example, I did some experiments, and it seems that trees, and ensembles of trees are not working at all. On the other hand, SVM seems to work. Does it hold in general, or only with my dataset?

I know that each dataset is different and what works with one may not work with another, but there must be some settings that should be followed in this kind of task every time, so I am interested only on them.

Answer 1

• Given you have only 40 observations in total, LOOCV would be the best option.
• Yes, for ex. linear models are not suitable since they cannot be used for p>n problems, unless you apply some sort of regularization, such as LASSO or RIDGE regression (or both ELASTIC NET), ELASTIC NET is probably the best option from linear models. Random forests would be another good option, they should work well on high-dimensional data, in general.
• First of all, they need to be able to deal with high-dimensional data, second some degree of regularization is required.
• Feature selection is very recommended, as most algorithms will work terribly if given too many variables, since they will find mostly noise otherwise. A first pass of feature reduction helps greatly.
• SVM could work, if you find an appropriate kernel to separate your data, not easy in general.