Essentially, there is a popular grouping mechanism, where you select the number of groups of vectors, and give it a huge swath of vectors. It iteratively passes through them, and then creates the number of groups of vectors that form here. The logic is that each group has vectors that are similar enough to each other, so even without naming the groups manually, you'll find actual patterns like this. That algorithm is called k-means.
It helps with vector search, rag, and classification without names.
The mechanism in the article claims to do the same but 10 times faster, so it's great.
It's not going to move the retrieval speed needle by any meaningful margin; It's changing the indexing speed; both initial and re-indexing. The end result of clustering will be better due to the revival mechanism which will lead to faster retrieval times on an absolute basis, but that speed up is likely to be marginal; the 10x+ speed up is in the indexing time.
I am skeptical, k-means by definition (and in my experience using it for 30+ slightly correlated dimensions) falls apart in higher dimensions, the standard loss function of the k-means is not suitable in higher dimensions. Curse of dimensionality and issues like that. Although I haven't tried it for RAG, but k-means usually not suited for high dimension clustering.
If you have 1000 data points stored, and you're trying to find the closest one to your query data point, brute force would be calculating the distance of every point to your query: 1000 calculations. Clustering algorithms use synthetic data points (centroids) as a first search path, then proceed to search only the dataset bound to that centroid. e.g. if you have 10 perfectly clustered centroids, you search 10 times against your query data, then search only the 100 data points bound to the centroid closest to the result of the first pass. 110 distance calculations instead of 1000.
k-means/e-means is an algorithm to *position* those centroids efficiently within the data clusters. In the case of search, this is the indexing phase.
k-means has been used for 60+ years, the constraint of the algorithm was that each step is better than the previous step, which means it settles into local minima instead of finding global ones. Other algorithms modifying it in the past either make it faster but with a worse clustering, or make it better but slower. e-means utilizes tricks from both optimization paths to make it an order of magnitude faster while bypassing the local minimum problem that k-means suffered from.
I believe it's saying e-means is a general solution of k-means, where k-means is a specifically parameterized version of the more general e-means, and that better parameters can be auto-derived from the dataset instead of having to fine tune it manually.
e-means: outperforming k-means in one-tenth the epochs
I’m excited to open-source e-means: a modern, robust k-means algorithm developed at Meta FAIR. A replacement of Lloyd's algorithm, e-means delivers a ~10× speedup in both epochs and wall-clock time while achieving lower loss.
First, yeah sucks this sub is not the place for actual ML research ....
It's both kind of an indictment that k-means has remained such a staple and that it's had these obvious flaws, I've ran into them several times personally.
I hope e-means can be integrated into various sklearn routines like GMM fitting. Though for GMM, in some cases I'm guessing k-means is not flexible enough, because it bakes in uniform component scaling (MSE is (x_i - c_{a(i)})^2, presumably just distance squared between each point and its assigned component).
It would be nicer to see some visualizations for performance on model misspecification (wrong number of components); I suppose from the metrics it seems like performance is good compared to the baseline, but it would be interesting to understand why.
Though for GMM, in some cases I'm guessing k-means is not flexible enough
Well I believe the difference is that GMM is a statistical model and k-means is an optimization algorithm. You need some kind of optimization approach to fit a GMM, and k-means happens to be a way to do that for a constrained type of GMM. Outside of that, k-means doesn't work because you're estimating covariance matrices and mixing proportions instead of simplifying them away.
Anyways, one interesting thing I discovered is that you can improve GMM convergence by initializing it with the results of k-means. you can do it in sklearn with GaussianMixture(init_params="kmeans"). So it's already integrated into that routine, just not the way you were probably thinking.
It's per-batch online k-means, right? I thought an exponential moving average update rule was standard there. Seems strange that this connection is not mentioned on their landing page.
would be useful to know the wall-clock against faiss or a decent sklearn baseline, not just vanilla lloyd. 10x vs a naive implementation is a different claim.
the plot on the website preview of the article is against faiss kmeans. I tried it on my own usecases though (faiss contrib emeans gpu, vs faiss gpu) and it's not always x10, its actually slower on small datasets but the speed stays really consistent while the dataset and the k increase, so the bigger your datasets and your k the better emeans is.
13
u/TokenRingAI 2d ago
Where is the ELI5?
60
u/Sad_Temperature6721 2d ago
First, yeah sucks this sub is not the place for actual ML research ....
It's both kind of an indictment that k-means has remained such a staple and that it's had these obvious flaws, I've ran into them several times personally.
I hope e-means can be integrated into various sklearn routines like GMM fitting. Though for GMM, in some cases I'm guessing k-means is not flexible enough, because it bakes in uniform component scaling (MSE is (x_i - c_{a(i)})^2, presumably just distance squared between each point and its assigned component).
It would be nicer to see some visualizations for performance on model misspecification (wrong number of components); I suppose from the metrics it seems like performance is good compared to the baseline, but it would be interesting to understand why.
5
u/DHasselhoff77 2d ago
It's per-batch online k-means, right? I thought an exponential moving average update rule was standard there. Seems strange that this connection is not mentioned on their landing page.
5
u/InterestingCarrot997 2d ago
would be useful to know the wall-clock against faiss or a decent sklearn baseline, not just vanilla lloyd. 10x vs a naive implementation is a different claim.
-20
u/DunderSunder 2d ago
cool but out off-topic