Elamur Research⌕
☰
home / papers / 2024 / Large Language Models Enable Few-Shot Clustering

Large Language Models Enable Few-Shot Clustering

Paper · 2024 · Vijay Viswanathan, Kiril Gashteovski, Carolin Lawrence et al.

Summary

Clustering without supervision is underspecified, because the algorithm cannot know which grouping the user actually wants. Semi-supervised clustering addresses this with expert feedback, but gathering enough feedback becomes costly for large datasets with many clusters. Viswanathan et al. test whether an LLM, given only a few expert examples, can act on the expert's behalf. They try this at three stages of the pipeline. Before clustering, GPT-3.5 writes keyphrases for each document, and their embeddings are appended to the document vector. During clustering, the LLM labels point pairs as must-link or cannot-link for the PCKMeans algorithm. After clustering, the LLM re-checks uncertain assignments. Experiments cover five datasets across entity canonicalization, query intent clustering and tweet topic grouping. Keyphrase expansion outperforms plain K-Means on embeddings for every metric and dataset. LLM-generated constraints also help but require many queries, and post-correction adds little. The work offers a cheap, plug-in way to steer clustering with natural-language guidance.

Key points

  • Keyphrase expansion: Keyphrases come from gpt-3.5-turbo-0301, prompted with an instruction plus four demonstrations.
    • They are encoded with the same encoder as the original text, so the gain reflects LLM knowledge rather than a better encoder.
    • For entity clustering, DistilBERT is used to encode the keyphrases.
  • Pseudo-oracle constraints: The LLM produces 20,000 pairwise constraints from up to 4 demonstrations.
    • These feed PCKMeans (Basu et al., 2004), initialized with k-means++.
    • Candidate pairs are chosen by an adapted Explore-Consolidate procedure, or by nearest pairs in embedding space for entity canonicalization.
  • Post-correction: The method targets the 500 lowest-margin points.
    • The LLM first checks each point's current cluster.
    • If the LLM rejects that cluster, it then considers the 4 next-closest clusters as alternatives.
  • Cost: On OPIEC59k, about $41 of API usage outperforms the same budget spent on human labeling (fewer than 700 human-labeled pairs). True-oracle constraints only begin to help after roughly 2,500 labeled pairs.
  • Other findings:
    • An instruction alone, without demonstrations, already gives a substantial benefit.
    • The approach reaches state-of-the-art results on entity canonicalization.
    • Code and prompts are released at github.com/viswavi/few-shot-clustering.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Carnegie Mellon UniversityPittsburgh · United States365 works · 158,048 citations🎓Ss. Cyril and Methodius University in SkopjeSkopje · North Macedonia2 works · 113 citations

Also on the byline: NEC (Germany).

📚 Shelves 6The field of science this work belongs to (OpenAlex fields).Computer Science · 9,085 worksArtificial Intelligence · 8,888 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 worksSocial Sciences · 744 worksGeneral Social Sciences · 87 works

🧭 Topics 1Research subjects and languages the work is about.Language models & pretraining · 1,344 works

Cite

Cite as Vijay Viswanathan, Kiril Gashteovski, Carolin Lawrence, Tongshuang Wu and Graham Neubig. 2024. Large Language Models Enable Few-Shot Clustering. Transactions of the Association for Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1162/tacl_a_00648

@article{viswanathan2024large,
  title = {{Large Language Models Enable Few-Shot Clustering}},
  author = {Vijay Viswanathan, Kiril Gashteovski, Carolin Lawrence, Tongshuang Wu and Graham Neubig},
  journal = {Transactions of the Association for Computational Linguistics},
  year = {2024},
  doi = {10.1162/tacl\_a\_00648},
  url = {https://doi.org/10.1162/tacl_a_00648}
}

References

31 references, 5 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Charu C. Aggarwal and ChengXiang Zhai. 2012. A survey of text clustering algorithms. In ‘‘is point A more similar to point B or point C?’’. find
  2. Iñigo Casanueva, Tadas Temčinas, Daniela Gerz, Matthew Henderson, and Ivan Vulić. 2020. Efficient intent detection with dual sentence encoders. In Proceedings of the 2nd Workshop on Natural Language Processing for Conversational AI, pages 38–45, Online. Association for Computational Linguistics.…
  3. Anni Coden, Marina Danilevsky, Daniel F. Gruhl, Linda Kato, and Meena Nagarajan. 2017. A method to accelerate human in the loop clustering. In Proceedings of the 2017 SIAM International Conference on Data Mining. https://doi.org/10.1137/1 .9781611974973.27 — [doi:10.1137/1](https://doi.org/10.1137/1) find
  4. Jinlan Fu, See-Kiong Ng, Zhengbao Jiang, and Pengfei Liu. 2023. GPTscore: Evaluate as you desire. ArXiv, abs/2302.04166. find
  5. Luis Galárraga, Geremy Heitz, Kevin P. Murphy, and Fabian M. Suchanek. 2014. Canonicalizing open knowledge bases. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management. https://doi.org/10 .1145/2661829.2662073 find
  6. Kiril Gashteovski, Rainer Gemulla, and Luciano Del Corro. 2017. Minie: Minimizing facts in open information extraction. In Conference on Empirical Methods in Natural Language Processing. https://doi.org/10.18653/v1/D17-1278 ↗
  7. Sajib Dasgupta and Vincent Ng. 2010. Which clustering do you want? Inducing your ideal clustering with minimal feedback. Journal of Artificial Intelligence Research, 39:581–632. https://doi.org/10.1613/jair.3003 — [doi:10.1613/jair.3003](https://doi.org/10.1613/jair.3003) ↗
  8. Sarthak Dash, Gaetano Rossiello, Nandana Mihindukulasooriya, Sugato Bagchi, and A. Gliozzo. 2020. Open knowledge graphs canonicalization using variational autoencoders. In Conference on Empirical Methods in Natural Language Processing. https://doi.org/10.18653/v1/2021.emnlp-main.811 ↗
  9. William H. E. Day and Herbert Edelsbrunner. 1984. Efficient algorithms for agglomerative hierarchical clustering methods. Journal of Classification, 1:7–24. https://doi.org/10.1007/BF01890115 — [doi:10.1007/bf01890115](https://doi.org/10.1007/bf01890115) ↗
  10. Kiril Gashteovski, Sebastian Wanner, Sven Hertling, Samuel Broscheit, and Rainer Gemulla. 2019. Opiec: An open information extraction corpus. In Proceedings of the Conference on Automatic Knowledge Base Construction (AKBC). find
  11. Kotaro Hara, Abigail Adams, Kristy Milland, Saiph Savage, Chris Callison-Burch, and Jeffrey P. Bigham. 2017. A data-driven analysis of workers’ earnings on Amazon Mechanical Turk. In Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems. https://doi.org/10.1145 /3173574.317402… find
  12. John J. Horton. 2023. Large language models as simulated economic agents: What can we learn from homo silicus? Working Paper 31122, National Bureau of Economic Research. https://doi.org/10.3386/w31122 — [doi:10.3386/w31122](https://doi.org/10.3386/w31122) ↗
  13. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,…
  14. Harold W. Kuhn. 1955. The Hungarian method for the assignment problem. Naval Research Logistics (NRL), 52. find
  15. Stefan Larson, Anish Mahendran, Joseph J. Peper, Christopher Clarke, Andrew Lee, Parker Hill, Jonathan K. Kummerfeld, Kevin Leach, Michael A. Laurenzano, Lingjia Tang, and Jason Mars. 2019. An evaluation dataset for intent classification and out-of-scope prediction. In Proceedings of the 2019 Confer… find
  16. Hong Kong, China. Association for Computational Linguistics. https://doi.org/10 .18653/v1/D19-1131 find
  17. Shikhar Vashishth, Prince Jain, and Partha Talukdar. 2018. Cesi: Canonicalizing open knowledge bases using embeddings and side information. In Proceedings of the 2018 World Wide Web Conference, pages 1317–1327. https://doi.org/10.1145/3178876 .3186030 ↗
  18. S. Lloyd. 1982. Least squares quantization in pcm. IEEE Transactions on Information Theory, 28(2):129–137. https://doi.org/10.1109/TIT.1982.1056489 — [doi:10.1109/tit.1982.1056489](https://doi.org/10.1109/tit.1982.1056489) ↗
  19. Kiri L. Wagstaff and Claire Cardie. 2000. Clustering with instance-level constraints. In Proceedings of the Seventeenth International Conference on Machine Learning. find
  20. David N. Milne and Ian H. Witten. 2008. Learning to link with wikipedia. In International Conference on Information and Knowledge Management. https://doi.org/10 .1145/1458082.1458150 find
  21. Jianhua Yin and Jianyong Wang. 2016. A model-based approach for text clustering with outlier detection. 2016 IEEE 32nd International Conference on Data Engineering (ICDE), pages 625–636. https://doi.org/10.1109/ICDE.2016.7498276 — [doi:10.1109/icde.2016.7498276](https://doi.org/10.1109/icde.2016.7498276) ↗
  22. Joon Sung Park, Joseph C. O’Brien, Carrie J. Cai, Meredith Ringel Morris, Percy Liang, and Michael S. Bernstein. 2023. Generative agents: Interactive simulacra of human behavior. arXiv preprint arXiv:2304.03442. find
  23. Maarten De Raedt, Fréderic Godin, Thomas Demeester, and Chris Develder. 2023. Idas: Intent discovery with abstractive summarization. ArXiv, abs/2305.19783. https://doi.org/10.18653/v1/2023.nlp4convai-1.7 ↗
  24. Nils Reimers and Iryna Gurevych. 2019. Sentence-bert: Sentence embeddings using siamese bert-networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics. https://doi.org/10.18653/v1/D19-1410 ↗
  25. Dejiao Zhang, Feng Nan, Xiaokai Wei, Shang-Wen Li, Henghui Zhu, Kathleen McKeown, Ramesh Nallapati, Andrew O. Arnold, and Bing Xiang. 2021. Supporting clustering with contrastive learning. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Lingui…
  26. Hongjing Zhang, Sugato Basu, and Ian Davidson. 2019. A framework for deep constrained clustering - algorithms and advances. In ECML/PKDD. https://doi.org/10.1007/978-3-030-46150-8 4 ↗
  27. Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. 2019. Distilbert, a distilled version of bert: Smaller, faster, cheaper and lighter. ArXiv, abs/1910.01108. find
  28. Yuwei Zhang, Zihan Wang, and Jingbo Shang. 2023. Clusterllm: Large language models as a guide for text clustering. ArXiv, abs/2305 .14871. https://doi.org/10.18653/v1/2023.emnlp-main.858 ↗
  29. Wei Shen, Yang Yang, and Yinan Liu. 2022. Multi-view clustering for open knowledge base canonicalization. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD ’22, pages 1578–1588, New York, NY, USA. Association for Computing Machinery. https://doi.org/10.114… — [doi:10.1145/3534678.3539449](https://doi.org/10.1145/3534678.3539449) find
  30. Zhihan Zhou, Dejiao Zhang, Wei Xiao, Nicholas Dingwall, Xiaofei Ma, Andrew Arnold, and Bing Xiang. 2022. Learning dialogue representations from consecutive utterances. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language… find
  31. Hongjin Su, Weijia Shi, Jungo Kasai, Yizhong Wang, Yushi Hu, Mari Ostendorf, Wen-tau Yih, Noah A. Smith, Luke Zettlemoyer, and Tao Yu. 2022. One embedder, any task: Instruction-finetuned text embeddings. In arXiv.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/viswanathan-2024-large-language-models-enable-few/