E-means: Outperforming k-means in one-tenth the epochs

wood_spirit

This looks awesome. Obvious in hindsight! The viz really explains it well. Hope it gets added to scipy - it’s much more available in the envs many use than facebooks own faiss library.

real_faxenoff

I adapted the method to my IVF index (the code-daemon project) and achieved a 146x speedup on the GPU. That's impressive!

Luke2642

This is a great example of why p=np is sometimes the wrong question. For this np hard problem approximate solutions are good enough, and if you get them 45x faster that's even better!

bashhq_r

so the epoch reduction is cool but the hyperparameter laws feel like they were fit post-hoc

jlhawn

I wonder if this could be used anywhere as an alternative to Lloyd's algorithm. I have a hobby project which uses Lloyd's to "relax" an icosohedral equal area mesh on the surface of a sphere [1]. I'm going to try to swap it out with an adaptation of this and see if it's much better or if I can afford more iterations with this method. Edit: tried it, and it’s definitely not better for this use case. e-means wins by needing fewer passes over a huge dataset, but relaxing a mesh on a sphere has no dataset: each Voronoi cell’s centroid can be computed directly from its geometry. Mini-batches just swap that for a noisy sampled estimate of the same thing. It has the same objective and the same optimum, so at best it matches Lloyd. In practice it was much slower and left the grid noisy, and with small sample budgets it even tangled the mesh. [1] https://webgcm.app/explain/grid#nudging-the-cells-into-shape

coderenegade

Very cool, saving this to play around with later.

shiandow

These kinds of algorithms tend to have equivalent descriptions as expectation maximisation or simulated annealing. I wonder if it's possible to understand their algorithm in that sense. Though I suppose it may be as simple as expectation maximization with a friction term, since Sj = sj - a (sj - Sj). Importantly they note that this update rule keeps the centroid within the convex hull, which is pretty important.

detourdog

Can someone explain in layman’s terms the contexts this is used?

senderista

The one remaining hyperparameter is of course k. I vaguely remember there was some rule of thumb for picking k like the "elbow of a curve", but what is the state of the art now for picking k?

robbienukes

What is most impressive about this excellent work is not just the staggering time savings but the robustness of the technique in its assignment of single centroids where legacy may create two due to artefacting or worse one centroid for two blobs. Their explanation that: mini-batches provide more noisy updates that are more likely to explore the optimization landscape and escape local minima makes perfect sense and just goes to show it is all not settled hash. Incredible work with real world benefits of real marginal utility.

saagarjha

As far as I can tell this isn't particularly new, people have been doing minibatch k-means for a while, including with an EWA update. I assume the contribution here is that they tried to measure how much better it is and provided code? I'm not sure I agree with their claims though, because they didn't really measure the things that matter–sure, it's better than Lloyd's algorithm, but that's a very low bar. If you are claiming that your algorithm is "highly parallelizable" and comes with "wall-clock speedups", then the actual metrics that matter here is not number of steps or even basic wall clock time as your size remains fixed, but how your algorithm scales as more data is present or parallelism is required. This algorithm splits up the minibatch across workers and has them compute local updates, then allreduces it. As the amount of data goes up, the comms become much more expensive (since you have to use a worse transport layer), which means that you're basically locked in a desperate attempt to do more local work before you send your partial update to everyone else. If you attempt this (not explored in the paper) you will find that the improvement in clustering by doing this extra work has diminishing returns–you only reduce the number of updates by a few steps (which is what drives your wall clock time). At scale you end up being heavily comms limited and not super parallel at all.

xiaoliangliang

I'd want to see final cluster quality, not just inertia, before treating "one-tenth the epochs" as a drop-in win. On badly imbalanced or overlapping clusters, Lloyd's often spends early iterations bouncing centroids around. If the interpolation mainly damps that motion, you can look converged on the objective while the partition is still poor. A plot of ARI or NMI versus epoch budget on messy data would make the claim a lot more convincing.

kingcauchy

Played around with changing our hierarchical balanced incremental clustering to this https://github.com/antflydb/antfly/pull/1607 bulk builds of existing indexes that need to be completely reindexed (like a shard split) were 2.5x faster, overall insertion times didn’t change that much because overall clustering incrementally as data is indexed is a small portion of the cpu time.

jdonaldson

Here's one of my own efforts on density-aware locality-sensitive hashing for embeddings. It uses k-means at one stage, I'll give this approach a shot. https://dyf.io/