2
$\begingroup$

Python's Sklearn module provides methods to perform Kernel Density Estimation. One of the challenges in Kernel Density Estimation is the correct choice of the kernel-bandwidth.

I have come across the following python-expression to select a bandwidth:

grid = GridSearchCV(KernelDensity(kernel = 'gaussian'),{'bandwidth': np.linspace(0.1, 0.5, 20)}, cv = 5, iid = True)

Here, GridSearchCV is a method that performs K-Fold Cross-Validation. Here is how I understand it:

We split the data, whose density is to be estimated, into K subsets. We then train the Kernel-Density-Estimation Algorithm with the data points of K-1 subsets. And finally, we evaluate the accuracy of our found parameters on the remaining subset. We repeat the process K times, each time choosing a different subset for testing.

Now, here is my question: In the given python-expression: Which is the algorithm that KernelDensity(kernel = 'gaussian') makes use of? Is it a nearest-neighbor algorithm? Does this mean: We consider a data point and place a Gaussian onto it. We will now have a look at all the data points that fall within this Gaussian. From their values, we estimate the value of the data point that we have placed the Gaussian on.

Does anything that I am saying make sense?

$\endgroup$
6
  • $\begingroup$ Are you interested in knowing how KDE works on its own, given the bandwidth; or, how GridSearchCV decides on the best bandwidth? Your title and body ask different things I suppose. $\endgroup$
    – gunes
    Commented Apr 27, 2019 at 10:52
  • $\begingroup$ @gunes: well, I want to know how KDE works. Or KernelDensity(). But I am also interested in knowing if my understanding of GridSearchCV is correct. Do you ask me to alter my question? $\endgroup$
    – user503842
    Commented Apr 27, 2019 at 11:44
  • $\begingroup$ kde.py does not really do any bandwidth estimation; it uses a default value. The "big thing" it does is having an efficient way of finding the neighbours. Given that we have the proximity of the data-points in question we then place the Gaussian (or whatever kernel) on top. $\endgroup$
    – usεr11852
    Commented Apr 27, 2019 at 11:50
  • $\begingroup$ @usεr11852: Can you explain the idea behind how kde finds its neighbours? $\endgroup$
    – user503842
    Commented Apr 27, 2019 at 11:53
  • $\begingroup$ By default it is the kd_tree algorithm. $\endgroup$
    – usεr11852
    Commented Apr 27, 2019 at 11:56

1 Answer 1

1
$\begingroup$

The grid search CV is sensible because having a PDF estimation with data of $K-1$ folds and testing on the holdout set, by calculating the data log-likelihood, i.e. $\sum \log \hat{p}(x_i)$, you can get an estimate of how good is your KDE.

Normally, for a given query point, KDE uses all the points in the data to estimate its density, i.e. $f_X(x)=\frac{1}{n}\sum K_h(x-x_i)$, when the kernel has infinite support. However, distant points have negligible effect (e.g. adding $10^{-16}$ to $1$ for example), and to be effective/practical some number of neighbours are used, depending on your bandwidth. This can be done efficiently via data structures like ball tree or kd tree as @user11852 also pointed out.

$\endgroup$
7
  • 1
    $\begingroup$ ok, I think I get it now: KernelDensity() is simply estimating the density of the given data. This means: We place a Gaussian on each data point and then sum up all of these Gaussians. When normalizing by the number of data points, this should yield the PDF. Now, GridSearchCV is an algorithm that selects the optimal bandwidth of the Gaussians that KernelDensity() is going to use. To achieve this, GridSearchCV tries out a certain bandwidth and lets KernelDensity() estimate the pdf using K-1 folds. It then tests how good the KDE is on the last fold by computing the log-likelihood (?). $\endgroup$
    – user503842
    Commented Apr 28, 2019 at 8:54
  • $\begingroup$ Exactly. Also GridSearchCV does this K times and averages the likelihood. $\endgroup$
    – gunes
    Commented Apr 28, 2019 at 8:57
  • $\begingroup$ great, thx a lot, man! ... one last question: how is the log-likelihood a measure of how good the estimated pdf is? I mean, the log-likelihood tells me how likely it is to get a certain value within the test-data set. I will still have to compare this value with the actual number of times this value appears within this data set, won't I ? $\endgroup$
    – user503842
    Commented Apr 28, 2019 at 9:14
  • 2
    $\begingroup$ you estimate a pdf from K-1 fold data, and evaluate likelihood of test fold. Do this K times, and average all log-likelihoods. There you get an average estimate of your data likelihood. If you get higher likelihoods for a bandwidth value, this means your data is explained better using it. Think likelihood as probability of event you have your data, the higher it is, the likely the bandwidth is able to explain the data. $\endgroup$
    – gunes
    Commented Apr 28, 2019 at 11:56
  • 1
    $\begingroup$ @user503842: if you find this answer helpful you could consider upvoting it or even accept it if it addresses your question adequately. (It is +1 from me obviously!) $\endgroup$
    – usεr11852
    Commented Apr 28, 2019 at 22:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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