  Estimating mutual information (MI) from samples is a fundamental problem in
statistics, machine learning, and data analysis. Recently it was shown that a
popular class of non-parametric MI estimators perform very poorly for strongly
dependent variables and have sample complexity that scales exponentially with
the true MI. This undesired behavior was attributed to the reliance of those
estimators on local uniformity of the underlying (and unknown) probability
density function. Here we present a novel semi-parametric estimator of mutual
information, where at each sample point, densities are {\em locally}
approximated by a Gaussians distribution. We demonstrate that the estimator is
asymptotically unbiased. We also show that the proposed estimator has a
superior performance compared to several baselines, and is able to accurately
measure relationship strengths over many orders of magnitude.
