search

dask / dask-ml

Scalable Machine Learning with Dask
http://ml.dask.org
BSD 3-Clause "New" or "Revised" License
891 stars 255 forks source link

Add GMM #113

Open gmaze opened 6 years ago

gmaze commented 6 years ago

Hi all, Is there any plan to implement a parallel version of GMM (Gaussian Mixture Modelling) ? Thanks g

eg: http://dx.doi.org/10.1109/CSAE.2012.6272849

TomAugspurger commented 6 years ago

That'd certainly be in scope. I likely won't have time to work on this until the end of the month, but may be able to after that.

Do you have any other references for parallel or distributed GMM? That paper doesn't seem to be publicly available.

gmaze commented 6 years ago

The paper is here: Yang_et_al.IEEE2012.pdf But I'm not sure that this is the most relevant implementation for dask-ml, more biblio should be done

TomAugspurger commented 6 years ago

Gave a quick skim of scikit-learn's implementation. A translation of that to use work on dask arrays doesn't look too difficult. Unless I missed something, the fanciest thing was a cholesky decomposition, which is implemented in dask.array.

@gmaze do you have any interest in working on this?

mrocklin commented 6 years ago

I think it would be interesting to see how Dask's cholesky factorization behaves here, but it may be that other algorithms more suited to large distributed datasets exist. A literature search is possibly still warranted here.

On Tue, Jan 9, 2018 at 10:15 AM, Tom Augspurger notifications@github.com wrote:

Gave a quick skim of scikit-learn's implementation. A translation of that to use work on dask arrays doesn't look too difficult. Unless I missed something, the fanciest thing was a cholesky decomposition, which is implemented in dask.array.

@gmaze https://github.com/gmaze do you have any interest in working on this?

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/dask/dask-ml/issues/113#issuecomment-356332208, or mute the thread https://github.com/notifications/unsubscribe-auth/AASszIEBiw3bvMN0aIOrbaMmh1r7P-g-ks5tI5CRgaJpZM4RXCe3 .

TomAugspurger commented 6 years ago

Agreed.

On Tue, Jan 9, 2018 at 10:17 AM, Matthew Rocklin notifications@github.com wrote:

I think it would be interesting to see how Dask's cholesky factorization behaves here, but it may be that other algorithms more suited to large distributed datasets exist. A literature search is possibly still warranted here.

On Tue, Jan 9, 2018 at 10:15 AM, Tom Augspurger notifications@github.com wrote:

Gave a quick skim of scikit-learn's implementation. A translation of that to use work on dask arrays doesn't look too difficult. Unless I missed something, the fanciest thing was a cholesky decomposition, which is implemented in dask.array.

@gmaze https://github.com/gmaze do you have any interest in working on this?

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/dask/dask-ml/issues/113#issuecomment-356332208, or mute the thread https://github.com/notifications/unsubscribe-auth/ AASszIEBiw3bvMN0aIOrbaMmh1r7P-g-ks5tI5CRgaJpZM4RXCe3 .

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/dask/dask-ml/issues/113#issuecomment-356333072, or mute the thread https://github.com/notifications/unsubscribe-auth/ABQHIm_8eKLCGrJzJH4OXghsqhKvNhmWks5tI5EigaJpZM4RXCe3 .

gmaze commented 6 years ago

I would surely have interest in working on this but have no timeline before the end of February and would certainly need a lot of help in order to follow the dask-ml code logic

At this point, I don't quite yet understand where the need for a specific distribution method arises, ie why people publish papers on new GMM algorithm vs distribute the bottleneck operation of the classic EM algorithm for a GMM (which is, as you pointed, the cholesky factorization of the covariance matrices)

The first step, may be to try the benchmark the regular GMM EM algorithm with and without specific dask-ml optimized operators

DaniJonesOcean commented 4 years ago

Hi all. I would like to flag my interest in this project as well. It doesn't look like there has been much activity in this area lately.

Does anyone have plans to work on this issue in the near-term future? I would be interested in contributing, but like gmaze I would need help getting started.

gmaze commented 4 years ago

I didn't get the time to work on this yet because I wanted to focus on releasing a clean version of http://github.com/obidam/pyxpcm , which now implement the choice of 2 stats backend (scikit-learn or dask_ml). Now that it's done, I plan to focus on optimisation, hence this issue of having EM/GMM optmized for dask_ml. But I can't guaranty any timeline

TomAugspurger commented 4 years ago

Thanks for the update @gmaze.

remiadon commented 3 years ago

Hi,

I made a bit of literature search on my side.

IMO the resource mentioned by @gmaze is a good start, but it's basically a re-implementation designed to reduce data exchange on cluster of machines. Quoting page 2

we developed a newframework called Distrim from scratch, aiming to minimize space and communication overheads as much as possible, and to maximize the usage of computational power of multicore clusters as much as possible

I suggest to use a different methodology. One concept that I find particularly interesting is called coreset A coreset is a subset of the original data that gives theoretical guarantees on the shape (the shape of a coreset is close from the shape of the original data)

Coresets have already proven to be useful for large scale modeling of Gaussian Mixture, as well as K-means and K-median clustering

proposed solution

I believe this methodology is compatible with the current philosophy of dask-ml ("re-implement at scale if required, or simply allow sklearn estimators to scale with a different methodology). It can also benefit other methods, not only GMMs

Regards, Rémi

References Scalable Training of Mixture Models via Coresets Coresets for k-Means and k-Median Clustering and their Applications

TomAugspurger commented 3 years ago

Thanks for sharing @remiadon. One API question around your proposed Coreset class.

This would return a subsample of the original dask.array as a numpy.array, along with associated weigths for those points, also as a numpy array

I see the suggestion of a method like coreset(*arrays) that handles all the logic of extracting a coreset from a dask Array. But for an end-user API, I instead think of some kind of meta-estimtaor like

>>> model = Coreset(sklearn.mixture.GaussianMixture())
>>> model.fit(big_X, big_y)  # extracts the coreset, fits the weighted(?) sklearn GMM on the coreset (small, in memory)
>>> model.predict(big_X)  # Dask Array of predictions
remiadon commented 3 years ago

@TomAugspurger, a Coreset meta-estimator would be great !

Another way of achieving an equivalent goal would be to implement a CoresetTransformer that would return the data fully transformed (the set of points, weighted). But as far as I know sklearn prohibits having a different number of rows between intput/output of a transformer ...

Any of those solutions suits me, I can try submitting a PR

TomAugspurger commented 3 years ago

Yes, the Transformer would also work well, but would I think require https://github.com/scikit-learn/enhancement_proposals/pull/15. I haven't read through that in a while, but I don't know how it proposes to deal with weights.

Anyway, I think for now an implementation using a metaestimator would be most welcome. I think the logic of selecting the coreset is likely to be the most difficult part, regardless of the API :)

remiadon commented 3 years ago

I created a PR here https://github.com/dask/dask-ml/pull/799

This is work in progress for now, as most of the sampling methods were designed for KMeans, and usage with Gaussian Mixture is still a bit obscure to me.