How does kernel density estimation work?

Question

There is an inbuilt "adaptive Kernel density" anomaly detection routine provided in a data streaming library (https://docs.microsoft.com/en-us/stream-analytics-query/anomalydetection-spikeanddip-azure-stream-analytics). It returns a p_value for each data point given the history and is designed to detect sudden jumps. I've been trying to find online resources into how it works but can't find good ones. The best resource I've found so far is this paper: https://cis.temple.edu/~latecki/Papers/mldm07.pdf and it suggests some kind of distribution for the observed value is formed based on history and "convolution" with a kernel function which is a multi-dimensional probability density function (Gaussian is most common). Per equation (3) in the paper, it seems very much like this is a mixture of Gaussians.

My question is, how this compares vis-à-vis just doing a one sample t-test for the current observation versus the the history? Seems like the one-sample t-test would be appropriate for gaussian white noise. Does this kernel method improve on that for other kinds of time series? How so?

It certainly seems less efficient since the documentation says that its linear in the number of history points, so surely the added complexity must be providing some advantage.

And is it possible to quantify the advantage (given the generative process for the time series and in terms of statistical power)?

Answer 1

The KDE model, as opposed to (for example) a t-test, does not assume anything about the values distribution.
The resulting distribution is indeed a mixture of Gaussians (given a Gaussian kernel), and if the sample values are far enough from each other (compared to the kernel's 'bandwidth' parameter), the resulting log-likelihood of each new data point will depend almost entirely on the distance from the nearest point in the sample.

The reason for this is that the kernel density (i.e. likelihood function) is the average across data points: $f(y)= \sum_{i}^N K(y-x_i;h)$, where $y$ is the new data point, $x_i$ are the old data points, $K$ is the kernel function and $h$ is the bandwidth parameter.
So, if the new point is close to some old point $x_0$ and relatively far from all the rest, we'll have $f(y) \approx K(y-x_0;h) $ , and the log likelihood will be $log(f(y)) \approx log(K(y-x_0; h))$

Now, if you're looking for anomaly detection, you can expect the KDE to basically single out new points that are far enough from the given ("training") sample.
Keeping that in mind, the Python implementation in SKlearn (link) keeps the data points in a tree structure, which is a bit faster to search through when comparing with new points.

As a side note, we must note that "comparing new values to old values" isn't really utilizing anything temporal in the time-series.

Hope this answers your question to some extent.