Rendered at 08:21:29 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
jlhawn 11 hours ago [-]
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.
Your website looks incredibly interesting! Very exited to read it when I have time. When you mentioned icosahedral meshes, I immediately thought it would be related to weather/climate modeling :D.
On the topic of these meshes, I'm currently exploring if we can come up with better meshing strategies in data-driven weather models (https://tcumulus.dev/blog/thesis/).
shiandow 9 hours ago [-]
Since it's basically a linear interpolation between Lloyd's algorithm and not moving any points it will be at least as good but gains might be limited without careful tuning.
Edit: in fact you might end up going faster by moving the other way, set alpha = -0.1 and see what happens!
real_faxenoff 12 hours ago [-]
I adapted the method to my IVF index (the code-daemon project) and achieved a 146x speedup on the GPU.
That's impressive!
saagarjha 7 hours ago [-]
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.
oofbey 2 hours ago [-]
Yeah most of these tricks are already well established. And their own ablations show that combining them doesn’t bring any special synergy - it’s just putting together a lot of common techniques. The baselines also are tough to believe fully. Comparing against faiss is fair since many authors are faiss contributors so they know how to run it. But they don’t and should include a comparison to a well tuned mini batch kmeans like the one in scikit.
shiandow 9 hours ago [-]
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.
wood_spirit 12 hours ago [-]
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.
porridgeraisin 12 hours ago [-]
The automatic hyperparameter laws don't seem intuitive to me yet. Do you have any intuition for it?
Thomashuet 32 minutes ago [-]
Their example is terrible, there are clearly 3 clusters and trying to find 200 clusters doesn't make any sense.
They show their algorithm performs better on some degenerate case but what about when there are actually k clusters?
EDIT: actually I see that they have a section about "The k-means problem" and that's where I think they get it wrong. What they describe is not the problem itself but how to solve it. The real problem (for most people at least, they seem to have a different problem) is to find the clusters in a dataset where you already know that there are clusters and how many there are.
hubertzhang 31 minutes ago [-]
what's the common use case for e-means/k-means nowadays?
kingcauchy 5 hours ago [-]
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 4 hours ago [-]
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.
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?
nighthawk454 5 hours ago [-]
The 'Elbow method' [1], yeah. Sweep a bunch of different k values and pick the one where your target metric starts having diminishing returns. There are a lot of heuristics you could use.
There's still not one particularly great way to pick k for this type of clustering. There kind of can't be as clustering is sort of inherently subjective.
Other methods like HDBSCAN can find the number of clusters themselves. There's still a 'one key parameter' you have to pick yourself, but it can be more intuitive and less sensitive for some datasets, when you don't know how many clusters there are / how many you want.
Sometimes, picking k exactly is useful for practical reasons too. Like fixing the size of your codebook. Or partitioning a dataset into k equal-ish pieces, say to spread across a pool of servers of a known/fixed size.
Yeah, I guess you can't really avoid picking k without hierarchical clustering.
nighthawk454 4 hours ago [-]
Yeah, it's not a well-defined problem, so there's no one true solution. Then only question left is "well what do you want?". Always have to pick something.
You could use X-means instead (https://www.cs.cmu.edu/~dpelleg/download/xmeans.pdf). The idea is to use an information criterion that trades the number of parameters against the reduction in within-cluster variance. The approach essentially splits a cluster when the BIC of the split is larger than without. I’d use this to select k and still run normal k-means though.
oofbey 2 hours ago [-]
There isn’t a well defined correct or ideal answer. It depends on what you’re doing with the clusters. Sometimes the raw data are too numerous to properly deal with and you just want a smaller set of points to reason about. In that case pick the number of points that are convenient to reason about. Sometimes you have a fixed budget for the cluster representation and that defines k. Sometimes just pick sqrt(N) so the average cluster size is k.
Luke2642 11 hours ago [-]
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!
hinkley 11 hours ago [-]
The best class of algorithms in this category are those where you know for certain that one answer is impossible and the other is highly probable. Like Bloom Filters, and if you squint, consistent hashing. I wish we had more algorithms of this sort and books about them. If I were a professor I’d be tempted to propose teaching a class.
When I was just starting out, client-server was still a bit of a specialty, mostly reserved for gaming and large institutions. Most of my education was in single task computing. If the university hadn’t offered a class in distributed computing I wouldn’t have gotten much in that direction except in independent study.
In the time since then, we seem to have focused much less on seconds per task and more on tasks per second, which results in more concern about statistical spreads, and queuing mechanisms to manage the variability between a hit and a miss. It would be better if this sort of computation were more organized into a discipline.
Luke2642 11 hours ago [-]
My personal favourite is compressive sensing, sparse signals beat the Nyquist sampling limit, by what seems like an unbounded amount 1000x, 1000000x, etc, because all real world stuff we care about lives on a low dimensional manifold, so unlike the noise.
The entire field of operations research is essentially founded on the premise that NP hard is just a starting place.
ivanjermakov 8 hours ago [-]
If anything, NP hard problems are usually the ones worth tackling.
aaron695 8 hours ago [-]
[dead]
detourdog 8 hours ago [-]
Can someone explain in layman’s terms the contexts this is used?
ttul 8 hours ago [-]
Let's say you have a way of encoding the properties of something using a vector of numbers. But two things might be very similar and yet still produce vectors that are not identical to each other. Indeed, the vectors are nearly guaranteed to always be at least slightly different. Also, assume there are a large number of dimensions.
You want to assign things to a set of clusters so that things that share similar properties are grouped closely together. But, we also want those clusters to be as big as possible. We don't want to leave little islands that only have a few things in them.
Take, for example, classification of email messages. Let's say you have a billion email messages and you want to find a way to cluster them automatically into 10 categories. You don't know what the categories are ahead of time. You just have a way of making sure that an email can be represented by a vector of numbers such that two emails that are close together in their meaning and characteristics will have similar numbers.
K-Means clustering solves that problem but is intractable to calculate for large datasets having high dimensionality (such as the email example). My understanding is that E-Means is away to achieve this spectacularly more efficiently than the best alternative previously known.
pcwalton 5 hours ago [-]
It's clustering. You have a bunch of data points and you want to group them into k clusters such that all the data points in a cluster are similar. Like dividing customers into high/medium/low spenders, or whatever (usually you'd have more dimensions than 1D though).
benjiro29 8 hours ago [-]
Faster vector calculations. What help for example, helps with ivfflat or prism index building. It cut CPU (or GPU) usage, and time needed to build. Seen index build times drop by 50 to 80%, and at the same time CPU usage drop by 50%.
Impressive results ...
akoboldfrying 4 hours ago [-]
I found this unhelpful, sorry. "Faster vector calculations" sounds like a faster way to add or multiply vectors, which TTBOMK k-means doesn't help with at all. There are hundreds of types of things called an "index"; I'm familiar with ordinary RDBMS indices but haven't heard of ivfflat or prism indices. Gemini tells me PostgreSQL uses them to support approximate nearest neighbour queries on geometric data -- e.g., finding the nearest train station to your current position.
bashhq_r 11 hours ago [-]
so the epoch reduction is cool but the hyperparameter laws feel like they were fit post-hoc
robbienukes 7 hours ago [-]
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.
coderenegade 10 hours ago [-]
Very cool, saving this to play around with later.
yksalun 1 hours ago [-]
[flagged]
xiaoliangliang 5 hours ago [-]
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.
boulos 5 hours ago [-]
I feel like they cover that, a bit, with both explicit examples and the quality curves, right?
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
On the topic of these meshes, I'm currently exploring if we can come up with better meshing strategies in data-driven weather models (https://tcumulus.dev/blog/thesis/).
Edit: in fact you might end up going faster by moving the other way, set alpha = -0.1 and see what happens!
That's impressive!
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.
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.
Hope it gets added to scipy - it’s much more available in the envs many use than facebooks own faiss library.
EDIT: actually I see that they have a section about "The k-means problem" and that's where I think they get it wrong. What they describe is not the problem itself but how to solve it. The real problem (for most people at least, they seem to have a different problem) is to find the clusters in a dataset where you already know that there are clusters and how many there are.
https://dyf.io/
There's still not one particularly great way to pick k for this type of clustering. There kind of can't be as clustering is sort of inherently subjective.
Other methods like HDBSCAN can find the number of clusters themselves. There's still a 'one key parameter' you have to pick yourself, but it can be more intuitive and less sensitive for some datasets, when you don't know how many clusters there are / how many you want.
Sometimes, picking k exactly is useful for practical reasons too. Like fixing the size of your codebook. Or partitioning a dataset into k equal-ish pieces, say to spread across a pool of servers of a known/fixed size.
[1] https://en.wikipedia.org/wiki/Elbow_method_(clustering)
https://en.wikipedia.org/wiki/Cluster_analysis#Definition
When I was just starting out, client-server was still a bit of a specialty, mostly reserved for gaming and large institutions. Most of my education was in single task computing. If the university hadn’t offered a class in distributed computing I wouldn’t have gotten much in that direction except in independent study.
In the time since then, we seem to have focused much less on seconds per task and more on tasks per second, which results in more concern about statistical spreads, and queuing mechanisms to manage the variability between a hit and a miss. It would be better if this sort of computation were more organized into a discipline.
You want to assign things to a set of clusters so that things that share similar properties are grouped closely together. But, we also want those clusters to be as big as possible. We don't want to leave little islands that only have a few things in them.
Take, for example, classification of email messages. Let's say you have a billion email messages and you want to find a way to cluster them automatically into 10 categories. You don't know what the categories are ahead of time. You just have a way of making sure that an email can be represented by a vector of numbers such that two emails that are close together in their meaning and characteristics will have similar numbers.
K-Means clustering solves that problem but is intractable to calculate for large datasets having high dimensionality (such as the email example). My understanding is that E-Means is away to achieve this spectacularly more efficiently than the best alternative previously known.
Impressive results ...