search

bayesmix-dev / bayesmix

Flexible Bayesian nonparametric mixture models in C++
https://bayesmix.rtfd.io
BSD 3-Clause "New" or "Revised" License
22 stars 18 forks source link

Split and Merge algorithm #116

Closed AleCarminati closed 2 years ago

AleCarminati commented 2 years ago

Good afternoon,

we implemented the Split and Merge algorithm in bayesmix.

We ran tests on galaxy and faithful datasets with the same settings that were used in the master's thesis on bayesmix and with the following parameters for the algorithm:

We obtained interesting results:

We include the density and the cluster estimates we obtained with Split and Merge.

galaxy_cluster galaxy_density

faithful_cluster faithful_density

mberaha commented 2 years ago

I will have a look as soon as possible. In the meantime, what is the ESS per second for all the models? Can you compare that? I would also like to see the ESS/s when varying the parameters of the split-merge algorithm (number of restricted scans, number of metropolis-hastings moves).

AleCarminati commented 2 years ago

I will have a look as soon as possible. In the meantime, what is the ESS per second for all the models? Can you compare that? I would also like to see the ESS/s when varying the parameters of the split-merge algorithm (number of restricted scans, number of metropolis-hastings moves).

As requested, we computed the ESS/s of our algorithm (using the code in commit fec8db5) with different parameters and we compared it with the other marginal algorithms in the library. Here are the results: galaxy_ess_s faithful_ess_s

We saw that, in general, the value of the ESS for Split and Merge is higher than the value for the other algorithms, but the run time is also higher. This makes our algorithm worth using (from the point of view of ESS/s) only with certain combinations of parameters. We analyzed Neal2, which has an ESS/s much higher that all the other algorithms: we found out that this extreme value is due to a very low run time, which compensates the ESS, lower than the one of all the other algorithms.

mberaha commented 2 years ago

As requested, we computed the ESS/s of our algorithm (using the code in commit fec8db5) with different parameters and we compared it with the other marginal algorithms in the library. Here are the results: galaxy_ess_s faithful_ess_s

We saw that, in general, the value of the ESS for Split and Merge is higher than the value for the other algorithms, but the run time is also higher. This makes our algorithm worth using (from the point of view of ESS/s) only with certain combinations of parameters. We analyzed Neal2, which has an ESS/s much higher that all the other algorithms: we found out that this extreme value is due to a very low run time, which compensates the ESS, lower than the one of all the other algorithms.

Can you try with a few other simulated datasets as the dimension increase? For instance you simulate data from a 2 component mixture, the first has mean equal to -3/sqrt(d) and the second one to 3/sqrt(d) (these are d-dimensional vectors with all entries equal) and identity covariance. You could compare the various algorithms for d=2,5,10,25. Set the number of initial clusters to 1. In my experience neal3 should be stuck to always finding only 1 cluster when d>5, while split-merge might find two. This could give a major advantage to split-merge

brunoguindani commented 2 years ago

Hello, I will review this PR soon. In the meantime, could you please mark conversations in this thread as resolved if the proposed changes have already been implemented? Thank you!

AleCarminati commented 2 years ago

With the build test on commit 1b3d1b7 we noted that our fork was not up-to-date with the changes in the signatures of get_mass_new_cluster and get_mass_existing_cluster. Therefore, we fetched upstream our fork and we modified the calls to these functions. Now it should work correctly.

mberaha commented 2 years ago

Way to go! Guys, before merging, I would like to ask you one last thing: create a python notebook in python/notebooks that you call something like "split_merge_benchmarking.ipynb" where you put all the experiments you have and the comparison with Neal2/3/8. You can either use the command line via an executable file to run all the experiments or use the bayesmixpy interface (it's just a wrapper around the command line, nothing fancy about it) and report the plots etc...

Let me know when you have something ready :)

AleCarminati commented 2 years ago

We just added the notebook, as you suggested. It contains the tests that we ran to obtain the numerical values and the graphs for the final presentation and the report. It is composed of two sections: in the first one we test the algorithm on galaxy and faithful, in the second one we test the algorithm with high dimensional synthetic datasets. As you suggested, we tried different combinations of parameters to check if there were some advantages in using Split and Merge. We found a combination (the one that is written in the notebook) in which Split and Merge clearly outclasses Neal3: with dimensions between 6 and 10, Split and Merge recognizes correctly the two clusters, while Neal3 in some cases is not able to find two clusters and in other cases requires thousands of iterations to find them.

mberaha commented 2 years ago

Impressive job guys! I'm really glad to merge this PR to master!

mberaha commented 2 years ago

We need more developers like these ones!!

https://www.youtube.com/watch?v=EMldOiiG1Ko

AleCarminati commented 2 years ago

Thank you for the patience and all the suggestions!