0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you please explain whether you are looking for a single measure for the class separation in feature space (aka "internal clustering validation indices"), or whether you seek a measure per point x in feature space? $\endgroup$ – cdalitz Nov 13 at 9:12
  • $\begingroup$ The former. Given classes A and B, I need a way of measuring the degree to which the i'th feature 'stands out' in class A compared to B. $\endgroup$ – ahura Nov 13 at 9:16
  • $\begingroup$ In other words: you need it for feature selection and are looking for a measure for the dicriminationg power of each individual feature? $\endgroup$ – cdalitz Nov 13 at 9:19
  • $\begingroup$ I don't need it for feature selection. The aim is to help interpret the results from a clustering algorithm i.e. I want a method that can take data points in clusters A and B and determine which features are most characteristic to the difference. I would think this is very similar to feature selection, which was the motivation behind the second approach I suggested (as that is the usual method of recursive feature elimination) $\endgroup$ – ahura Nov 13 at 9:29
  • $\begingroup$ I have deleted my previous answer and added an answer addressing your question as clarified in the recent comments. $\endgroup$ – cdalitz Nov 13 at 10:03
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you. I'm not strong in information theory, so sorry if I'm wrong here, but isn't the mutual information in your first equation MI(Y|X) and not MI(X|Y). I think I'll go with the first approach, as that allows me to piggyback on tried-and-true binary classifiers. $\endgroup$ – ahura Nov 13 at 14:08
  • $\begingroup$ Quick question, considering the first two approaches, would you pick one over the others, especially if the dataset were unbalanced with regards to classes? $\endgroup$ – ahura Nov 13 at 14:20
  • 1
    $\begingroup$ @ahura MI is symmetric - it's "mutual"! I would have to understand your problem a little better to really make a recommendation, but I think the classifier-based mutual information estimator is both reasonable and will be fairly widely understood. You can use something simple like a KDE/kNN-based classifier. $\endgroup$ – Dougal Nov 13 at 15:32
  • $\begingroup$ just to be 100% clear, by h(Pr(Y=1)), you mean simply the max-likelihood distribution over classes, right? So the p in h(p) is just the fraction of the data points where Y=1? $\endgroup$ – ahura Nov 14 at 16:33
  • 1
    $\begingroup$ @ahura Yep, exactly. $\endgroup$ – Dougal Nov 14 at 23:52
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. I did consider using something like the Fisher ratio. However, we want to also be able to notice less straightforward dependencies (for instance, if for feature i, members of class A fall uniformly in [-3:-1] and [1:3] while members of class B fall in [-1:1]. then knowing the value of feature i for a given data point tells you with certainty the class it belongs to, yet the fisher ratio gives 0) $\endgroup$ – ahura Nov 13 at 10:16
  • $\begingroup$ I have extended the answer to suggest something in this case of a multimodal distribution and non-cntoguous decision regions. $\endgroup$ – cdalitz Nov 13 at 10:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.