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.
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!
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!
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.
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.
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.
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%.
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.
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
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!
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!
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.
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.
You may enjoy randomised algorithms (https://www.cl.cam.ac.uk/teaching/2425/RandAlgthm/)
The entire field of operations research is essentially founded on the premise that NP hard is just a starting place.
If anything, NP hard problems are usually the ones worth tackling.
I adapted the method to my IVF index (the code-daemon project) and achieved a 146x speedup on the GPU.
That's impressive!
Can someone explain in layman’s terms the contexts this is used?
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.
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 ...
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.
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.
The automatic hyperparameter laws don't seem intuitive to me yet. Do you have any intuition for it?
so the epoch reduction is cool but the hyperparameter laws feel like they were fit post-hoc
Very cool, saving this to play around with later.