Implementing (R-)ALoKDE algorithm for data streams density estimation

Question

I'm trying to implement the (R-)ALoKDE algorithm for the density estimation of the data streams. The algorithm has been published and presented in [1, 2]. Although the algorithm seems simple, I'm struggling to implement it, even in the 1D case. My current (1D) implementation can be found on GitHub [3]. I believe that my problems may be due to my lack of statistical knowledge -- hence I'm looking for some guidance here.

1. Imagine a Kernel Density Estimator (KDE) that's a weighted sum of standard KDEs -- let's name it WS-KDE. I've read that -- to sample from a simple KDE -- one can randomly select one of its kernels and draw a sample from it. Is that also correct for the WS-KDE? Can I select the simple KDE (according to weights) first and then a kernel from the selected KDE? If not, what's the proper way to draw a sample from WS-KDE?

2. ALoKDE algorithm -- as far as I understand -- works in the following way. First, it detects if the concept drift (stream non-stationarity) occurred. If so, then a local estimator $$ \hat{f}^{kde}_t = \frac{1}{m_t +1} \left( \sum^{m_t}_{i=1} \frac{1}{h^d_{D_t}} K \left( \frac{||\textbf{x} - \textbf{x}_t^{(i)}||}{h_{D_t}} \right) + \frac{1}{h^d_{\textbf{x}_t}} K \left(\frac{||\textbf{x} - \textbf{x}_t||}{h_{\textbf{x}_t}} \right) \right) $$ is created. The $h$ parameters are easy to compute, $\textbf{x}_t$ is the new sample from the stream, and $\textbf{x}^{(i)}_t$ are local samples, (see pt. 3). I believe the rest of the symbols are self-explanatory, but I'll edit the post again if needed. At this moment, I should have 2 KDEs -- the KDE from the previous step $\hat{f}_t$ and the local one $\hat{f}_t^{kde}$. I then make a weighted sum of them $$\hat{f}_{t+1}(\textbf{x}) = \lambda_t \hat{f}^{kde}_t(\textbf{x}) + (1 - \lambda_t) \hat{f}_t(\textbf{x})$$ where $\lambda_t$ is the weight computed via the formula $$ \lambda_t = max \left(0, min \left(1, \frac{B_t - C_t}{A_t + B_t - 2C_t} \right) \right) $$ The second problem concerns finding the $\lambda_t$. Here, one has to compute $$ A_t = \int [(E(\hat{f}^{kde}_{t}(\textbf{x}; h_{D_t}, h_{\textbf{x}_t}) - f(\textbf{x}))^2 + Var(\hat{f}^{kde}_{t}(\textbf{x}; h_{D_t}, h_{\textbf{x}_t}))] dx $$

   $$ B_t = \int [(E(\hat{f}_{t}(\textbf{x}) - f(\textbf{x}))^2 + Var(\hat{f}_{t}(\textbf{x}))] dx $$

   $$ C_t = \int [(E(\hat{f}^{kde}_{t}(\textbf{x}; h_{D_t}, h_{\textbf{x}_t}) - f(\textbf{x}))) \cdot (E(\hat{f}_{t}(\textbf{x})) - f(\textbf{x})) + Cov(\hat{f}^{kde}_{t}(\textbf{x}; h_{D_t}, h_{\textbf{x}_t}), \hat{f}_{t}(\textbf{x})] dx $$

   I can see that $A_t$ and $B_t$ are MISE of $\hat{f}^{kde}_t$ and $\hat{f}_t$ respectively, and I know how to compute them. The authors claim that $C_t$ is the covariance between $\hat{f}^{kde}_t$ and $\hat{f}_t$, and this I have no idea how to compute. I've also tried to bypass this problem by finding $\lambda_t$, which minimizes MISE of $\hat{f}^{kde}_{t+1}(\textbf{x})$, but it doesn't work correctly -- it tends to either $\lambda=1$ or $\lambda=0$ depending on MISE of which estimator ($\hat{f}_t$ or $\hat{f}_{t}^{kde}$) is smaller. I believe that one computes the MISE of $\hat{f}_{t+1}$ differently than a weighted sum of simple KDEs MISEs.

3. My additional concern is the local sampling described in the paper (mentioned in point 2). During the update step of the algorithm, one has to draw $m_t$ local samples $\{\textbf{x}_t^{(i)}$ from the current KDE $\hat{f}_t$ that are $\tau$-close (according to some distance measure) to the sample $\textbf{x}_t$ drawn from the stream prior to the update step. Just for the sake of argument, I'll mention that the default is $\tau=1$. Imagine now that $\hat{f}_t$ is a good estimator of $N(0, 1)$. Now, due to concept drift, the stream now draws the data from $N(100, 1)$ so $\textbf{x}_t$ would be a value close to 100. How can I efficiently and numerically draw samples that are so deep into the tail of the distribution?

Currently, I test my implementation on the stationary standard normal distribution $N(0, 1)$.

Solving these two issues will allow me to implement what I need. Any help is greatly appreciated.

[1] https://link.springer.com/article/10.1007/s13042-021-01275-y

[1, free and public] https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8210923/

[2] https://ieeexplore.ieee.org/abstract/document/8621923

[3] https://github.com/Tomev/ALoKDE

Answer 1

I managed to make the algorithm work as intended a few months ago and successfully defended my Ph.D. thesis. Only now have I got some time to answer and close the question, so here goes.

1. As answered by @whuber in the first comment to my question -- yes.

2. The values of $A_t$ and $B_t$ are the $MISE$ of the old and new estimator. I computed them using the standard handbook (eg. Kulczycki's) formulas. As for $C$, the authors claim it's the covariance of the estimators that was problematic for me. Turns out that what they meant was the covariance between the values of the estimators on the whole domain. Knowing that I was able to compute the covariance using the standard covariance formula.

3. Expecting the algorithm to sample from a distribution that is vastly different (with close-to-none overlap) than the current estimator was impossible to obtain numerically. In my case, Python returned (-)infs quite regularly. I managed to overcome this issue with satisfying results by returning the value of the local sample (x) modified ($\pm$) by the $\tau$ parameter (describing local samples' closeness). This way the algorithm behaved reasonably well, although I admit it's not necessarily what the authors intended.

My implementation of 1D AloKDE algorithms is public and can be found under [3] of the original post. If any1 has any ideas as to how to improve it (make it closer to what the authors intended) I'll be glad to read them. As for now, I'm marking this answer as correct. Cheers!