Scalable Model-Based Clustering with Sequential Monte Carlo

Connie Trojan, Pavel Myshkov, Paul Fearnhead, James Hensman, Tom Minka, Christopher Nemeth
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:3529-3537, 2026.

Abstract

In online clustering problems, there is often a large amount of uncertainty over possible cluster assignments that cannot be resolved until more data are observed. This difficulty is compounded when clusters follow complex distributions, as is the case with text data. Sequential Monte Carlo (SMC) methods give a natural way of representing and updating this uncertainty over time, but have prohibitive memory requirements for large-scale problems. We propose a novel SMC algorithm that decomposes clustering problems into approximately independent subproblems, allowing a more compact representation of the algorithm state. Our approach is motivated by the knowledge base construction problem, and we show that our method is able to accurately and efficiently solve clustering problems in this setting and others where traditional SMC struggles.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-trojan26a, title = { Scalable Model-Based Clustering with Sequential Monte Carlo }, author = {Trojan, Connie and Myshkov, Pavel and Fearnhead, Paul and Hensman, James and Minka, Tom and Nemeth, Christopher}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {3529--3537}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/trojan26a/trojan26a.pdf}, url = {https://proceedings.mlr.press/v300/trojan26a.html}, abstract = { In online clustering problems, there is often a large amount of uncertainty over possible cluster assignments that cannot be resolved until more data are observed. This difficulty is compounded when clusters follow complex distributions, as is the case with text data. Sequential Monte Carlo (SMC) methods give a natural way of representing and updating this uncertainty over time, but have prohibitive memory requirements for large-scale problems. We propose a novel SMC algorithm that decomposes clustering problems into approximately independent subproblems, allowing a more compact representation of the algorithm state. Our approach is motivated by the knowledge base construction problem, and we show that our method is able to accurately and efficiently solve clustering problems in this setting and others where traditional SMC struggles. } }
Endnote
%0 Conference Paper %T Scalable Model-Based Clustering with Sequential Monte Carlo %A Connie Trojan %A Pavel Myshkov %A Paul Fearnhead %A James Hensman %A Tom Minka %A Christopher Nemeth %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-trojan26a %I PMLR %P 3529--3537 %U https://proceedings.mlr.press/v300/trojan26a.html %V 300 %X In online clustering problems, there is often a large amount of uncertainty over possible cluster assignments that cannot be resolved until more data are observed. This difficulty is compounded when clusters follow complex distributions, as is the case with text data. Sequential Monte Carlo (SMC) methods give a natural way of representing and updating this uncertainty over time, but have prohibitive memory requirements for large-scale problems. We propose a novel SMC algorithm that decomposes clustering problems into approximately independent subproblems, allowing a more compact representation of the algorithm state. Our approach is motivated by the knowledge base construction problem, and we show that our method is able to accurately and efficiently solve clustering problems in this setting and others where traditional SMC struggles.
APA
Trojan, C., Myshkov, P., Fearnhead, P., Hensman, J., Minka, T. & Nemeth, C.. (2026). Scalable Model-Based Clustering with Sequential Monte Carlo . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:3529-3537 Available from https://proceedings.mlr.press/v300/trojan26a.html.

Related Material