Unsupervised Text Segmentation via Kernel Change-Point Detection on Sentence Embeddings
This addresses the problem of expensive and subjective boundary labels in text segmentation for NLP applications, though it is incremental as it builds on existing change-point detection methods.
The paper tackled unsupervised text segmentation by proposing Embed-KCPD, a training-free method using kernel change-point detection on sentence embeddings, which often outperformed strong unsupervised baselines on standard benchmarks.
Unsupervised text segmentation is crucial because boundary labels are expensive, subjective, and often fail to transfer across domains and granularity choices. We propose Embed-KCPD, a training-free method that represents sentences as embedding vectors and estimates boundaries by minimizing a penalized KCPD objective. Beyond the algorithmic instantiation, we develop, to our knowledge, the first dependence-aware theory for KCPD under $m$-dependent sequences, a finite-memory abstraction of short-range dependence common in language. We prove an oracle inequality for the population penalized risk and a localization guarantee showing that each true change point is recovered within a window that is small relative to segment length. To connect theory to practice, we introduce an LLM-based simulation framework that generates synthetic documents with controlled finite-memory dependence and known boundaries, validating the predicted scaling behavior. Across standard segmentation benchmarks, Embed-KCPD often outperforms strong unsupervised baselines. A case study on Taylor Swift's tweets illustrates that Embed-KCPD combines strong theoretical guarantees, simulated reliability, and practical effectiveness for text segmentation.