An example of a good measure of class separability in linear discriminant learners is Fisher's linear discriminant ratio. Are there other useful metrics to determine if feature sets provide good class separation between target variables? In particular, I'm interested in finding good multivariate input attributes for maximizing target class separation and it would be nice to have a non-linear/non-parametric measure to quickly determine if they provide good separability.
Variable Importance Measures (VIMs) from Random Forests might be what you are looking for. A brief overview over two of these is given in a paper Overview of Random Forest Methodology and Practical Guidance with Emphasis on Computational Biology and Bioinformatics by Boulesteix et al.
The idea for the Gini VIM is that you get some statistics of how often a random forest has made use of a certain attribute as the splitting criterion. Informative features are chosen more often here.
The permutation VIM is based on the idea that the error-estimates of the RF-classifier are compared between
- the original dataset and
- an artificial dataset where values for ONE attribute have been permuted.
The resulting error-estimate-difference will be big for important features.
As far as I remember, VIMs can also be used to discover dependencies between features.
Finding an optimal features set can be quite computationally expensive. The main categories of available solutions can be grouped in two sets: either bind to a specific classifier (Wrappers) or simple ranking of features based on some criterion (Filter methods).
Based on your requirements (quick/non-parametric/non-linear) probably you need candidates from the Filter methods. There are quite a few examples of those described in literature. For example Information Gain - that evaluates the worth of an attribute by measuring the information gain with respect to the class; or Correlation that evaluates the worth of an attribute based on the correlation between the attribute and the class.
The wrapper methods are bind to a classifier and may end up to a better set of features for the classifier of interest. Due to their nature (full training/testing in each iteration) they can not considered quick or non-parametric, however they can deal with non-linear relations of features (your 3rd requirement). An example would be Recursive Feature Elimination that is based on SVMs, thus targets on maximising the margin between the classes and can deal with non-linear relations of features (using a non-linear kernel).