Can Correlation based feature selection discard features that show no correlation by themselves but are meaningful only if combined? Assuming a feature selection process based on correlation or some other metric, is it possible to overlook input features that by themselves show no actual correlation with the target values, but that combined together are valid?
I tried different approaches at feature selection, all start by judging one feature at a time; I also tried to use a small, single layer neural network with only one input to select features that are good predictors by themselves (this would be the equivalent of a "non-linear" correlation) to later combine them together.
Both the Pearson correlation based method and the small ANN method performed well, and more complex models built with the features selected gave even better results, as expected, but I'm wondering if I missed some other opportunity to get even better results by combining features that were not selected by these approaches.
If I were to "try and combine" the features in couples i would get unreasonable computational times, especially if the analysis were to go on to triples or more...
Is it possible that i overlooked some valid features combinations? If so, are there any feature selection methods that take into consideration multiple features at a time? Can strongly non-linear features show this beauvoir?

$\newcommand{\perpp}{\perp\!\!\!\perp}$
$\newcommand{\nperpp}{\perp\!\!\!\perp\!\!\!\!\!\!\mathbf /\;\:}$
First, note that it is quite unusual to have multiple features $X_i$ that are all independent of $Y$ (in symbols $X_i\perpp Y$), but together create a notable dependence $(X_1,\ldots,X_n)\nperpp Y$. Think e.g. of two independent binary random variables $X_1, X_2$ that are both uniformly distributed over $0$ and $1$, $X_1,X_2\sim U(\{0,1\})$, and a third binary variable $Y=X_1\oplus X_2$, where $\oplus$ is addition modulo $2$. Then
$$\label{eq}\tag{*}
X_1 \perpp Y, \;\;X_2\perpp Y, \qquad\mbox{but}\qquad (X_1, X_2)\nperpp Y.
$$
However, a slight perturbation of this situation, e.g. $X_1$ and $X_2$ not being uniform, would destroy the independencies $X_i\perpp Y$. Thus, the situation $\eqref{eq}$ could, in a sense, be considered singular, and all those methods that only consider one feature at a time are not too bad.
But of course, your concern is justified, especially when taking into account that one has only finite data, and thus scenarios that are close to the singular situation in $\eqref{eq}$, could, among all the noise, actually appear like $\eqref{eq}$.
Generally, there are quite a number of methods that can help you in performing good feature selection with few redundancies and without missing relevant combinations, e.g.:

*

*Feature selection with the feature importance assignment of random forest

*Relevance vector machines

*Spike-and-slab

*many more
Note, however, that the method should fit your problem. E.g., using random forest importance works best as feature selection for the application of random forest.
And if you are interested in getting to know the dependencies of your features in all gory detail, consider having a look at methods for learning the Bayesian network or your features, e.g. with bnlearn.
