How to measure dissimilarity between two classes in terms of a feature?

Question

I have a data set in which each data point has a label y and a feature vector $X=(x_0, x_1, ...)'$.

What I need is: given two classes, a and b, and a feature $x_i$, how much do members of the two classes differ in terms of $x_i$. The measure should give large values if knowing the value of $x_i$ for a given data point allows one to predict the class with certainty. Conversely, it should give low values of the feature provides no information on the class.

What would be a good way to approach this? I've mainly considered two methods:

• If I knew the underlying probability distributions over the feature for each class, I could just use some measure like the Jensen-Shannon divergence. However, I only have a finite number of data points. However, one might infer the distribution using KDE, or by using the data to update a prior distribution.
• Another approach might be to train a classifier to predict class membership, and get the feature importances from that.

I realize this question is a bit vague but would greatly appreciate recommendations.

Answer 1

The measure should give large values if knowing the value of $𝑥_i$ for a given data point allows one to predict the class with certainty. Conversely, it should give low values of the feature provides no information on the class.

This sounds like a few related things would work for you:$ \DeclareMathOperator{\E}{\mathbb{E}} \DeclareMathOperator{\HH}{H} \DeclareMathOperator{\MI}{MI} \newcommand{\ud}{\mathrm{d}} $

Mutual information

The mutual information between $X_i$ and the label $Y$: $$\MI(X_i, Y) = \HH[Y] - \HH[Y \mid X_i] = h(\Pr(Y = 1)) - \E_{X_i}[ h(\Pr(Y = 1 \mid X_i) ],$$ where $h(p) = - p \log p - (1-p) \log(1-p)$ is the entropy of a Bernoulli distribution. If you train a probabilistic classifier for $Y$ given $X_i$, this gives you a reasonable score. There are also various more direct mutual information estimators, or entropy estimators, but since $Y$ is so simple I think the classification approach makes sense. Incidentally, this is closely related to the Jensen-Shannon distance that you suggested.

Distances between distributions

You can also consider a direct notion of distance between the distributions $X_i \mid Y = 0$ and $X_i \mid Y = 1$.

$f$-divergences

Something like the Jensen-Shannon as you mentioned, or the total variation, would be fine (assuming everything has a density, or at least one divergence is absolutely continuous wrt the other). These are $f$-divergences.

The distances themselves correspond roughly to how directly distinguishable the distributions are by a perfect classifier: if $Y$ is exactly the seventeenth-order bit of $X_i$, no ML method that looks at the $X_i$ as a continuous value is ever going to recognize that, but the total variation will still be maximal.

So, estimating them can be arbitrarily hard if you don't assume anything about the distributions. But if everything has relatively smooth densities and you have a reasonable number of samples, since you're in one dimension there should be no serious challenges. Options include, as you mentioned, a plug-in estimator based on the KDE or similar, corrections to that estimator, estimators based on $k$-NN density estimators, estimators based on convex optimization (related to training classifiers), and many more.

Integral probability metrics

There are also other options for distance metrics, where the metrics themselves are more constrained and hence easier to estimate. One nice class is called integral probability metrics: $$\mathcal D_{\mathcal F}(P, Q) = \sup_{f \in \mathcal F} \E_{X \sim P} f(X) - \E_{Y \sim Q} f(Y).$$ These are defined by the choice of test functions $\mathcal F$. If you pick $\mathcal F$ to be the set of functions with outputs bounded in $[-1, 1]$, you get the total variation.

In 1d, one particularly nice option is the Wasserstein distance (aka earth mover's, Kantorovich-Rubenstein, Mallows, ...); it has a simple closed-form estimator in 1d, and corresponds to how well your distributions can be distinguished with Lipschitz functions.

Another option that's particularly nice in higher dimensions, though it also works well here, is the maximum mean discrepancy, based on the kernel trick. Statisticians might be more familiar with the energy distance, which is a special case of the MMD. Its square has a simple unbiased, asymptotically normal estimator. For many choices of kernel, the distance will be zero if and only if the distributions are the same. But its notion of "more similar" is fundamentally connected to the choice of kernel, in a way that is also of course analogously true for any estimator you might use of any distance, but is more explicit here.

Answer 2

From the comments to the question, it has become clear that the goal is to assess the discriminating power of the features. The second suggestion in the question is also known as a wrapper approach, because it is a sequential selection scheme wrapped around the performance (e.g. leave-one-out) of some classifier. This has the disadvantage that it depends on the specific classifier used as a subroutine.

There are different measures that are directly computed from the class distribution in feature space. Typically they are based on a decomposition of the scatter matrix (the covariance matrix) $S$ into a within scatter matrix $S_w$ and a between scatter matrix $S_b$, e.g. $$J_1=\frac{\det(S_b)}{\det(S_w)}=\det(S_b S_w^{-1})\quad\mbox{or}\quad J_2=\mbox{trace}(S_b S_w^{-1})$$ These criteria can then be used for sequential feature selection to determine the features with the most discriminatory power. Beware however, that the above measures $J_i$ can fail if the distributions are not unimodal.

When you assess each feature seperately (as you suggested), you can use Fisher's discriminant ratio $$FDR=\frac{(\mu_1-\mu_2)^2}{\sigma_1^2+\sigma_2^2}$$ Or the area under the ROC curve (AUC) that is obtained when you vary the classification threshold (note that 1D classification can be simply done by thresholding). The greater AUC, the greater is the discriminating power of the feature.

Addendum: The FDR is just a special case of the scatter matrices for one dimension and thus also fails for multimodal distributions. If nothing is known about the distributions, a wrapper approach based on a kNN classifier is easy to implement and runs quickly (as it does not require training). Just measure the leave-one-out rate of a 1NN or 3NN classifier for each feature. If you use it for sequential feature selection, beware to normalize the features beforehand because otherwise the distance will be dominated by the feature with the greatest variance.