motiwari

Hmmmm.... not sure exactly what you mean. I believe the setting you're describing is: we have a dataset we're trying to fit with a GMM, we know the number of components k, and we're trying to determine the parameters of the GMM, correct?

I suppose that you could adaptively sample points from the dataset to update your parameters of the GMM, and sample more points for parameters of the GMM that you're less certain about.

(To understand how the parameter estimates would converge to their true values, you'd likely need to use the delta method; see Appendix 3 in https://ar5iv.org/pdf/2212.07473.pdf for an example)

Is that what you had in mind?

Definitely possible, but it would require some extensions to the algorithm. More specifically, as new datapoints enter the stream, they could be compared with the existing medoids to see if swapping them would lower the clustering loss.

This would be a nontrivial engineering effort and I likely won't be able to do it myself (I'm a PhD student about to graduate), but if you or your team is interested in adapting BanditPAM to the streaming setting, please feel free to reach out! My email's motiwari@stanford.edu

Where is this benchmark from? We'd be happy to run BanditPAM on these datasets and report the results

A strength if you're strictly looking to minimize squared L2 loss from each point to its closest mean -- but for a lot of other applications, it's a weakness! As the other poster mentioned, with KMedoids you can use arbitrary loss functions and cluster exotic objects (not restricted to metrics on a vector space)

You got me! As @dang mentioned, once I got feedback from him I was allowed to repost and enter the second-chance pool

(My real first post was submitted too hastily without receiving @dang's feedback)

Hey, thanks! Shout out to Daniel @ HN who gave me a lot of great feedback on how to make this post better.

Thanks for bug report and repro steps! I've filed this issue at https://github.com/motiwari/BanditPAM/issues/244 on our repo.

I suspect that this is because the scikit-learn implementation of KMeans subsamples the data and uses some highly-optimized data structures for larger datasets. I've asked the team to see how we can use some of those techniques in BanditPAM and will update the Github repo as we learn more and improve our implementation.

Right! Though to clarify a few nits: we use successive elimination instead of successive halving. And we talk about the Maximum Inner Product Search problem (very similar to NN problem) in our followup work: https://ar5iv.org/abs/2212.07551

We talk exactly about clustering pictures in our blog post! https://ai.stanford.edu/blog/banditpam/

One thing that's important to note is that k-medoids supports arbitrary distance metrics -- in fact, your dissimilarity measure need not even be a metric (it can be negative, asymmetric, not satisfy the triangle inequality, etc.)

An implication of this is that if you were to do some invertible data transformation and then perform clustering, that's equivalent to doing clustering with a different dissimilarity measure (without the data transformation in the first place). It should be possible to avoid doing the invertible data transformation in the first place if you're willing to engineer your dissimilarity measure.

Without more details, it's hard to say exactly what would happen to the clustering results under custom dissimilarity measures or data transformations -- but our package supports both use cases!

Interesting, thanks for the references! I'm not too familiar with this line of work; let me read up on it and get back to you

The elbow method is pretty common! https://en.wikipedia.org/wiki/Elbow_method_(clustering)

You can also use some regularization criterion (AIC, BIC, or other)

Oh cool, neat trick, thanks!

Thank you for the positive feedback! Will definitely take you up on that coffee next time I visit Ilan :)

To answer your questions:

1. When looking at k-medoids algorithms, we realized that PAM hadn't been improved since the 80s! Other, faster algorithms had been developed but sacrificed solution quality (clustering loss) for speed. Simultaneously, prior work from my coauthors had recognized that the 1-medoid problem could be solved via randomized algorithms/multi-armed bandit -- much faster but returning the same solution. Our key insight was that every stage of PAM could be recast as a multi-armed bandit problem, and that reusing information across different stages would result in further speedups.

2. Actually, the complexity guarantees/theory were pretty easy because we were able to use proof techniques that are common in the multi-armed bandit literature. The hardest part was implementing it in C++ and making it available to both Python and R via bindings. For the original paper we did everything in Python and measured sample complexity, but to make the algorithm valuable for users we had to implement it in a more performant language.

3. To be honest, this project came about from a chance meeting at a conference (ICML 2019). I was randomly introduced to Martin Zhang (ironically I met him first at the conference even though we were both at Stanford). Martin and Ilan had deep expertise in multi-armed bandits/randomized algorithms (and solved the 1-medoid problem), and I got really interested in their work when talking with them, primarily because it seemed like a straightforward win and useful for a lot of people.

Really funny that you mention that! Some of our more recent work focuses on using adaptive sampling techniques in approximate-nearest-neighbor search (actually, the related problem of maximum inner product search: https://ar5iv.org/abs/2212.07551).

We definitely think that our approach could be used to make an index structure for ANN search directly, for example in conjunction with Hierarchical Navigable Small World approaches.

Sorry for the late response. And actually, despite the plethora of clustering algorithms, k-means is still a very commonly-used out-of-the-box technique! (Probably for its simplicity and existing popularity)

Sorry, I don't understand your argument. Could you clarify what you mean by "everything"? Is there another clustering algorithm you're thinking of?

Want something better than k-means? I'm happy to announce our SOTA k-medoids algorithm from NeurIPS 2020, BanditPAM, is now publicly available! `pip install banditpam` or `install.packages("banditpam")` and you're good to go!

Unlike in k-means, the k-medoids problem requires cluster centers to be actual datapoints, which permits greater interpretability of your cluster centers. k-medoids also works better with arbitrary distance metrics, so your clustering can be more robust to outliers if you're using metrics like L1.

Despite these advantages, most people don't use k-medoids because prior algorithms were too slow. In our NeurIPS 2020 paper, BanditPAM, we sped up the best known algorithm from O(n^2) to O(nlogn).

We've released our implementation, which is pip- and CRAN-installable. It's written in C++ for speed, but callable from Python and R. It also supports parallelization and intelligent caching at no extra complexity to end users. Its interface also matches the sklearn.cluster.KMeans interface, so minimal changes are necessary to existing code.

Our previous announcement that went viral: https://www.linkedin.com/posts/motiwari_want-something-bette...

PyPI: https://pypi.org/project/banditpam

CRAN: https://cran.r-project.org/web/packages/banditpam/index.html

Repo: https://github.com/motiwari/BanditPAM

Paper: https://arxiv.org/abs/2006.06856

If you find our work valuable, please consider starring the repo or citing our work. These help us continue development on this project.

I'm Mo Tiwari (https://motiwari.com), a PhD student in Computer Science at Stanford University. A special thanks to my collaborators on this project, Martin Jinye Zhang, James Mayclin, Sebastian Thrun, Chris Piech, and Ilan Shomorony, as well as the author of the R package, Balasubramanian Narasimhan.

(This is my first time posting on HN; I've read the FAQ before posting, but please let me know if I broke any rules)