Elamur Research⌕
☰
home / papers / 2001 / A Statistical Model for Domain-Independent Text Segmentation

A Statistical Model for Domain-Independent Text Segmentation

Paper · 2001 · Masao Utiyama and Hitoshi Isahara

Summary

Utiyama and Isahara address text segmentation, the task of splitting a document into topically coherent parts. They target settings with no labelled data, such as summarizing documents or speeches. Earlier unsupervised methods relied on lexical cohesion heuristics like cosine similarity or word repetition. This paper instead treats segmentation as a probabilistic search problem. Each segment is modelled as its own word distribution, estimated only from the text being segmented and smoothed with Laplace's law. A prior over segmentations comes from a minimum-description-length argument: the cost of transmitting the segment lengths. Together these give a cost for every candidate segment. Finding the best segmentation then reduces to a minimum-cost path through a graph of inter-word positions, solved with dynamic programming. The method also picks the number of segments automatically. On Choi's artificial benchmark, the system matched or beat Choi's (2000) state-of-the-art segmenter, with statistically significant gains. This matters because it offers a principled, training-free segmenter that works in any domain and can later absorb supervised features.

Key points

  • The model assumes topics are statistically independent and words are independent given their topic. Word probabilities within a segment use Laplace's law, so no external training corpus is needed.
  • The prior is uninformative, based on description length. Each segment length costs log n bits for a text of n words, giving k·log n bits for k segments. This term counterbalances the likelihood, which on its own would over-segment.
  • Segments correspond to edges in a graph of word-gap positions. The best segmentation is a minimum-cost path found by DP, with boundaries restricted here to sentence ends. A fixed number of segments can be enforced by limiting the number of edges in the path.
  • The number of segments grows only slowly with text length. A ~27-sentence editorial yields roughly 4–6 segments, while a text of over 1000 sentences yields about 10–20.
  • On 700 samples from Choi's artificial corpus, with the segment count given beforehand, the overall error was about 9% versus 11% for Choi's system (one-sided t-test, p ≈ 6.8E-9). The proposed system was better on every data subset reported. The implementation was publicly released by CRL.

Interesting ideas

  • I1. Segmentation as shortest path over word gaps. If segment scores are additive, any segmentation-style problem becomes a DP over a position graph. This could apply to sentence chunking, dialogue turn grouping, or splitting long Ukrainian documents for retrieval.
  • I2. MDL as a free prior. Charging bits for encoding each segment length provides a parameter-free penalty against too many segments. This trick is reusable wherever a model needs an automatic stopping criterion without tuning.
  • I3. Estimating from the input itself. Fitting smoothed per-segment word distributions on the document alone makes the method language- and domain-agnostic. It is attractive for low-resource languages or niche domains like trade documents, where annotated data is scarce.
  • I4. Pluggable segment-level priors. Because whole segments are scored directly, features of a segment can be added as extra cost terms. The authors show one example: a normal-distribution prior on segment length. This is easier than in HMM topic-tagging approaches, which only model transitions.
  • I5. By-product word densities. The per-segment word probabilities could help locate passages where a term is discussed in depth. This might support glossary extraction or term-definition mining.

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

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 9,086 worksArtificial Intelligence · 8,889 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 worksComputer Vision and Pattern Recognition · 1,282 works

Cite

Cite as Masao Utiyama and Hitoshi Isahara. 2001. A Statistical Model for Domain-Independent Text Segmentation. Proceedings of the 39th Annual Meeting of the Association for Computational Linguistics.

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

@inproceedings{utiyama2001statistical,
  title = {{A Statistical Model for Domain-Independent Text Segmentation}},
  author = {Masao Utiyama and Hitoshi Isahara},
  booktitle = {Proceedings of the 39th Annual Meeting of the Association for Computational Linguistics},
  year = {2001},
  doi = {10.3115/1073012.1073076},
  url = {https://doi.org/10.3115/1073012.1073076}
}

References

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

  1. James Allan, Jaime Carbonell, George Doddington, Jonathan Yamron, and Yiming Yang. 1998. Topic detection and tracking pilot study final report. In Proc. of the DARPA Broadcast News Transcription and Understanding Workshop. find
  2. Doug Beeferman, Adam Berger, and John Lafferty. 1999. Statistical models for text segmentation. Machine Learning, 34(1-3):177–210. find
  3. Freddy Y. Y. Choi. 2000. Advances in domain independent linear text segmentation. In Proc. of NAACL-2000.
  4. Marti A. Hearst and Christian Plaunt. 1993. Subtopic structuring for full-length document access. In Proc. of the Sixteenth Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 59–68. find
  5. Marti A. Hearst. 1994. Multi-paragraph segmentation of expository text. In Proc. of ACL’94. find
  6. Oskari Heinonen. 1998. Optimal multi-paragraph text segmentation by dynamic programming. In Proc. of COLING-ACL’98. find
  7. Min-Yen Kan, Judith L. Klavans, and Kathleen R. McKeown. 1998. Linear segmentation and segment significance. In Proc. of WVLC-6, pages 197– 205. find
  8. Judith L. Klavans, Kathleen R. McKeown, Min-Yen Kan, and Susan Lee. 1998. Resources for the evaluation of summarization techniques. In Proceedings of the 1st International Conference on Language Resources and Evaluation (LREC), pages 899–902. find
  9. Hideki Kozima. 1993. Text segmentation based on similarity between words. In Proc. of ACL’93. find
  10. Sadao Kurohashi, Nobuyuki Shiraki, and Makoto Nagao. 1997. A method for detecting important descriptions of a word based on its density distribution in text (in Japanese). IPSJ (Information Processing Society of Japan) Journal, 38(4):845–854. find
  11. Kikuo Maekawa and Hanae Koiso. 2000. Design of spontaneous speech corpus for Japanese. In Proc of International Symposium: Toward the Realization of Spontaneous Speech Engineering, pages 70–77. find
  12. Christopher D. Manning and Hinrich Schütze. 1999. Foundations of Statistical Natural Language Processing. The MIT Press. find
  13. Masaaki Nagata. 1994. A stochastic Japanese morphological analyzer using a forward-DP backward-A n-best search algorithm. In Proc. of COL-ING’94, pages 201–207. ì Yoshio Nakao. 2000. An algorithm for one-page summarization of a long text based on thematic hierarchy detection. In Proc. of ACL’2000, p… find
  14. Manabu Okumura and Takeo Honda. 1994. Word sense disambiguation and text segmentation based on lexical cohesion. In Proc. of COLING-94. find
  15. Jay M. Ponte and W. Bruce Croft. 1997. Text segmentation by topic. In Proc. of the First European Conference on Research and Advanced Technology for Digital Libraries, pages 120–129. find
  16. Jeffrey C. Reynar. 1994. An automatic method of finding topic boundaries. In Proc. of ACL-94. find
  17. Jeffrey C. Reynar. 1998. Topic segmentation: Algorithms and applications. Ph.D. thesis, Computer and Information Science, University of Pennsylvania. find
  18. Jeffrey C. Reynar. 1999. Statistical models for topic segmentation. In Proc. of ACL-99, pages 357–364. find
  19. Gerard Salton, Amit Singhal, Chris Buckley, and Mandar Mitra. 1996. Automatic text decomposition using text segments and text themes. In Proc. of Hypertext’96. find
  20. Andreas Stolcke and Stephen M. Omohundro. 1994. Best-first model merging for hidden Markov model induction. Technical Report TR-94-003, ICSI, Berkeley, CA. find
  21. Yaakov Yaari. 1997. Segmentation of expository texts by hierarchical agglomerative clustering. In Proc. of the Recent Advances in Natural Language Processing. find
  22. J. P. Yamron, I. Carp, S. Lowe, and P. van Mulbregt. 1998. A hidden Markov model approach to text segmentation and event tracking. In Proc. of ICASSP-98. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/utiyama-2001-statistical-model-domain-independent-text/