Is the estimation of Shannon's mutual information from data subject to the curse of dimensionality? And if yes why?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Do you have a specific problem in mind? I believe the answer is yes, because estimating the probability distribution of a random variable in high dimensional space is subject to the curse of dimensionality. Does it make sense? $\endgroup$– AndreaLDec 9, 2020 at 13:26
-
$\begingroup$ No. I am just considering the general problem of MI estimation. I know that there are different techniques. Maybe some are not subject to the curse of dimensionality or maybe they all are. But, if they are, it is not clear to me why. $\endgroup$– CesareDec 9, 2020 at 14:09
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
"Simple" approaches would definitively suffer from this problem. For example in this paper: https://arxiv.org/pdf/1910.00365.pdf, they state
One unfortunate consequence of the (KSG) estimator of the first kind is its reliance on the L∞ norm for finding neighbors. [...] Such a choice can lead to problems in regions where the probability varies greatly, which can easily happen in spaces of large dimension. Unless the density of samples increases exponentially with respect to the dimension of the space, the errors in choosing L∞ will compound quickly.
In other words, this estimator suffers from the curse of dimensionality.
So, why are simple approaches subject to the curse of dimensionality? It's because estimating the mutual information involves an estimate of the probability density distribution $P(X, Y)$ and of the marginal distributions $P(X)$ and $P(Y)$.
Estimating these in high dimensions is really hard, precisely because of the curse of dimensionality. In high dimensions, every point is a snowflake, and it's really hard to get a decent density of samples.
As you say, there might be more sophisticated estimators that are more robust to this problem, but I don't know the literature well enough.
