Problem when the number of sampled Background events comes to 1

[skepsun]

Thanks for your detailed codes about crime prediction!
I tried to implement your code of SEPP on my real Dataset. However, in SEPP, if only one event is sampled as the background event, the Kth nearest neighbor algorithm would fail. The way to determine whether the input coordinates are one-dim makes it hard to determine whether the input coordniates is nx1 (n is the dimension, N is the number of points = 1).
Maybe the form of input coordinates could be changed to [n,1] or [1,N], not [n,] either [N,].

[MatthewDaws]

Thanks for the feedback. I'm afraid this code is still somewhat a work in progress! I'm aware that the SEPP code can fail to converge: as you say, the cause is almost surely due to the Kth nearest neighbour algorithm.

I plan to look at this later this week (currently working on GUI issues). I'll check the code, and hope to fix, then...

[skepsun]

I find that the scaling factors applied to bkernel and tkernel may cause convergence problem in the SEPP code. It could be confusing that how the output lambda is defined. The output lambda has been defined as the estimated intensity of crimes at certatin time-space point. However KDE is used to estimate the probabilistic intensity, instead of actual intensity of number of crimes. To estimate the intensity, I think the scaling factor for tkernel (obtained from KDE, normalized) could be set as No, the scaling factor for bkernel could be set as Nb (1 for nu, Nb for mu). I tried these scaling factors and did not meet the convergence problem. However I am still not sure whether they are suitable in SEPP algorithm, as Mohler's paper does not tell the details on scaling.

[MatthewDaws]

I have changed StocasticDecluster so that if, in an iteration of the fitting algorithm, the number of triggered events falls below 10, then we raise a RuntimeError. I have also added some basic logging.

This seems most appropriate to me: it is pretty much meaningless to try to run a KDE algorithm on only 1 data point!

Of course, it doesn't help with why the algorithm is failing to converge. But you should now see a more meaningful error.

[MatthewDaws]

As for the "scaling factors", I'm afraid I don't fully follow your comments. I think you are referring to the following code, in StocasticDecluster.next_iteration:

    number_background_events = backgrounds.shape[-1]
    number_triggered_events = number_events - number_background_events
    bkernel.set_scale(number_background_events)
    tkernel.set_scale(number_triggered_events / number_events)

I believe that these are correct, and in agreement with Mohler et al. I have tried to explain this in the notebook
https://github.com/QuantCrimAtLeeds/PredictCode/blob/master/examples/Self-exciting%20point%20processes%201.ipynb
See the section "Note on the scaling of the KDEs". Furthermore, this notebook demos the code on two completely synthetic datasets. These datasets are samples from the actual statistical model, with known kernels for the background and "triggering" events. There is good agreement between the the estimated kernels and the expected kernels. (I am here basically re-creating the appendix of Mohler et al.)

Would it be possible for you to make available a Jupyter Notebook (for example) which shows the convergence issues you are having on your dataset? I too find that the performance on a real dataset (e.g. a section of Chicago burglary crime data) is "poor"-- but I have no trouble with convergence, only with that the estimated kernels are not very sensible.

[skepsun]

Thanks for your explanation. Now I think the scale factors are correct in SEPP code.
I made a Jupyter Notebook to show the convergence issues. I will also offer a sample data from the actual dataset. I have slightly modified the SEPP code to print the shapes of background and triggered events matrices.
example.zip

Edit: Well I found the reason why there could be convergence issues. The initialization is critical! The suitable parameters (initial time/space bandwidth) will ensure the convergence. Otherwise, it would not converge.
Additionally, the KNN algorithm would also fail when there are more than k_rest same data in dataset. It is due to the dataset used.

[MatthewDaws]

Thanks for getting back to me. I have changed the notebook slightly, please see attached. I can get it to converge okay, but it is very (very!) unstable. Sometimes it works, and sometimes it doesn't. When it works, the predicted background rate varies quite a bit.

Is the data artificial? It looks like it is from the plots I made.

I'm not really sure what to suggest. From speaking informally to colleagues and other researchers, it seems that there is acceptance that the SEPP method has convergence issues, and sometimes simply doesn't work!

I am currently working on a bit of original research, going back to the formulation of the Expectation-Maximisation algorithm. It'll update if I get anywhere.

demo.ipynb.tar.gz

[skepsun]

Since the initial time/space bandwidth is important for convergence, maybe it is better to add them as tunable arguments to train() in SEPPPredictor.

In open_cp sepp, the code to detect too many background events is a bit confusing:
if triggered.shape[-1] < 10: raise RuntimeError("Estimated only {} background points, which is too few to allow KDE to function".format(backgrounds.shape[-1]))
Maybe 'background' should be 'triggered'？

[MatthewDaws]

Thanks for these ideas.

#6ef33b9 adds the bandwidths as parameters to SEPPPredictor.

#5bec498 fixes the warning message!