Elamur Research
☰
home / papers / 2002 / A Critique and Improvement of an Evaluation Metric for Text Segmentation

A Critique and Improvement of an Evaluation Metric for Text Segmentation

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/J02-1002.pdf

Summary

Text segmentation means finding where topics shift in a stream of text. Fair evaluation is hard because different applications care about different errors. Precision and recall work poorly here: they trade off against each other, and they give no credit to a boundary placed close to, but not exactly at, the true position. The P k metric of Beeferman, Berger, and Lafferty slides a probe of width k across the text. At each step it checks whether the hypothesis and the reference agree that the probe's two ends lie in the same segment. Pevzner and Hearst analyse P k theoretically and find three flaws. It punishes missed boundaries more than spurious ones, it penalizes near misses too harshly, and its scores depend on how segment lengths vary. They propose WindowDiff, which keeps the moving window but counts an error whenever the number of hypothesized boundaries inside it differs from the reference number. Simulations back the analysis and suggest WindowDiff is the better measure. This matters because P k was becoming the default yardstick for comparing segmenters.

Key points

  • In P k, k equals half the mean reference segment length. Disagreements are divided by the number of probe positions, so a perfect segmentation scores 0.
  • A missed boundary (false negative) always costs k penalties. A spurious boundary (false positive) costs fewer when it sits near a segment edge and up to k in mid-segment. With uniform placement it averages about k/2, half the cost of a miss.
  • The three diagnosed flaws are:
    • false negatives are weighted more heavily than false positives;
    • near misses are overpenalized;
    • scores are sensitive to variation in segment size distribution.
  • WindowDiff compares the number of boundaries in each window position between the hypothesis and the reference. This penalizes misses and false alarms more evenly.
  • Context:
    • P k was already used in broadcast-news and topic segmentation work, such as Allan et al. 1998 and Choi 2000.
    • P k was designed so that degenerate outputs (all boundaries or none) score about the same.
    • Evaluating hierarchical segmentations is outside the paper's scope.

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

Fields: Natural language processing

Cited by

154 papers of our library cite it (of the 140673 whose bibliographies we read); 2 of them have a page here, 152 not yet.

Cite

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

@article{pevzner2002critique,
  title = {{A Critique and Improvement of an Evaluation Metric for Text Segmentation}},
  author = {Pevzner, Lev and Hearst, Marti A.},
  journal = {Computational Linguistics},
  year = {2002},
  doi = {10.1162/089120102317341756},
  url = {https://doi.org/10.1162/089120102317341756}
}

References

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

  1. Allan, James, Jaime Carbonell, George Doddington, Jonathan Yamron, and Yiming Yang. 1998. Topic detection and tracking pilot study: Final report. In Proceedings of the DARPA Broadcast News Transcription and Understanding Workshop, pages 194–218, Lansdowne, VA. find
  2. Baeza-Yates, Ricardo and Berthier Ribeiro-Neto. 1999. Modern Information Retrieval. Addison-Wesley Longman. find
  3. Barzilay, Regina and Michael Elhadad. 1997. Using lexical chains for text summarization. In Proceedings of the ACL Intelligent Scalable Text Summarization Workshop (ISTS’97), Madrid, Spain. find
  4. Beeferman, Douglas, Adam Berger, and John Lafferty. 1997. Text segmentation using exponential models. In Proceedings of the 2nd Conference on Empirical Methods in Natural Language Processing, pages 35–46, Providence, RI. find
  5. Beeferman, Douglas, Adam Berger, and John Lafferty. 1999. Statistical models of text segmentation. Machine Learning, 34(1–3):177–210. find
  6. Boguraev, Branimir and Mary Neff. 2000. Discourse segmentation in aid of document summarization. In Proceedings of the 33rd Hawaii International Conference on System Sciences, Maui, HI. find
  7. Box, G. E. P. and M. E. Muller. 1958. A note on the generation of random normal deviates. Annals of Mathematical Statistics, 29:610–611. find
  8. Callan, James P. 1994. Passage-level evidence in document retrieval. In Proceedings of the 17th Annual International ACM/SIGIR Conference, pages 302–310, Dublin, Ireland. find
  9. Choi, Freddy. 2000. Advances in domain independent linear text segmentation. In Proceedings of the 1st Meeting of the North American Chapter of the Association for Computational Linguistics, pages 26–33, Seattle, WA. find
  10. Dharanipragada, S., M. Franz, Jeffrey S. McCarley, S. Roukos, and Todd Ward. 1999. Story segmentation and topic detection in the broadcast news domain. In Proceedings of the DARPA Broadcast News Workshop, Herndon, VA. find
  11. Eichmann, David, Miguel Ruiz, Padmini Srinivasan, Nick Street, Chris Culy, and Filippo Menczer. 1999. A cluster-based approach to tracking, detection and segmentation of broadcast news. In Proceedings of the DARPA Broadcast News Workshop, Herndon, VA. find
  12. Hasnah, Ahmad. 1996. Full Text Processing and Retrieval: Weight Ranking, Text Structuring, and Passage Retrieval for Arabic Documents. Ph.D. thesis, Illinois Institute of Technology. find
  13. Hauptmann, Alexander G. and Michael J. Witbrock. 1998. Story segmentation and detection of commercials in broadcast news video. In Proceedings of the Advances in Digital Libraries Conference, pages 168–179, Santa Barbara, CA. find
  14. Hearst, Marti A. 1993. TextTiling: A quantitative approach to discourse segmentation. Technical Report Sequoia 93/24, Computer Science Division, University of California, Berkeley. find
  15. Hearst, Marti A. 1994. Multi-paragraph segmentation of expository text. In Proceedings of the 32nd Annual Meeting of the Association for Computational Linguistics, pages 9–16, Las Cruces, NM. find
  16. Hearst, Marti A. 1997. TextTiling: Segmenting text into multi-paragraph subtopic passages. Computational Linguistics, 23(1):33–64. find
  17. Hearst, Marti A. and Christian Plaunt. 1993. Subtopic structuring for full-length document access. In Proceedings of the 16th Annual International ACM/SIGIR Conference, pages 59–68, Pittsburgh, PA. find
  18. Heinonen, Oskari. 1998. Optimal multi-paragraph text segmentation by dynamic programming. In Proceedings of the 17th International Conference on Computational Linguistics and the 36th Annual Meeting of the Association for Computational Linguistics (ACL-COLING ’98), pages 1484–1486, Montreal. find
  19. Hirschberg, Julia and Christine H. Nakatani. 1996. A prosodic analysis of discourse segments in direction-giving monologues. In Proceedings of the 34th Annual Meeting of the Association for Computational Linguistics, pages 286–293, Santa Cruz, CA. find
  20. Kan, Min-Yen, Judith L. Klavans, and Kathleen R. McKeown. 1998. Linear segmentation and segment relevance. In Proceedings of the Sixth Workshop on Very Large Corpora (WVLC 6), pages 197–205, Montreal. find
  21. Karlgren, Jussi. 1996. Stylistic variation in an information retrieval experiment. In Proceedings of the 2nd International Conference on New Methods in Language Processing (NeMLaP 2), Ankara, Turkey. find
  22. Kaszkiel, Marcin and Justin Zobel. 1997. Passage retrieval revisited. In Proceedings of the 20th International Conference on Research and Development in Information Access (ACM SIGIR), pages 178–185, Philadelphia, PA. find
  23. Litman, Diane J. and Rebecca J. Passonneau. 1995. Combining multiple knowledge sources for discourse segmentation. In Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics, pages 108–115, Cambridge, MA. find
  24. Mani, Inderjeet, David House, Mark Maybury, and Morgan Green. 1997. Towards content-based browsing of broadcast news video. In Mark Maybury, editor, Intelligent Multimedia Information Retrieval. AAAI/MIT Press, pages 241–258. find
  25. Manning, Christopher D. 1998. Rethinking text segmentation models: An information extraction case study. Technical Report SULTRY-98-07-01, University of Sydney. find
  26. Marcu, Daniel. 2000. The Theory and Practice of Discourse Parsing and Summarization. MIT Press. find
  27. Merlino, Andy, Daryl Morey, and Mark Maybury. 1997. Broadcast news navigation using story segmentation. In Proceedings of the ACM International Multimedia Conference, pages 157–164, Seattle, WA. find
  28. Mittal, Vibhu, Mark Kantrowitz, Jade Goldstein, and Jaime Carbonell. 1999. Selecting text spans for document summaries: Heuristics and metrics. In Proceedings of the 16th Annual Conference on Artificial Intelligence (AAAI ’99), pages 467–473, Orlando, FL. find
  29. Morris, Jane and Graeme Hirst. 1991. Lexical cohesion computed by thesaural relations as an indicator of the structure of text. Computational Linguistics, 17(1):21–48. find our card
  30. Nomoto, Tadashi and Yoshihiko Nitta. 1994. A grammatico-statistical approach to discourse partitioning. In Proceedings of the 15th International Conference on Computational Linguistics (COLING’94), pages 1145–1150, Kyoto, Japan. find
  31. Passonneau, Rebecca J. and Diane J. Litman. 1993. Intention-based segmentation: Human reliability and correlation with linguistic cues. In Proceedings of the 31st Annual Meeting of the Association for Computational Linguistics, pages 148–155, Columbus, OH. find
  32. Ponte, Jay and Bruce Croft. 1997. Text segmentation by topic. In Proceedings of the 1st European Conference on Research and Advanced Technology for Digital Libraries, pages 113–125. find
  33. Reynar, Jeffrey C. 1994. An automatic method of finding topic boundaries. In Proceedings of the Student Session of the 32nd Annual Meeting of the Association for Computational Linguistics, pages 331–333, Las Cruces, NM. find
  34. Richmond, Korin, Andrew Smith, and Einat Amitay. 1997. Detecting subject boundaries within text: A language independent statistical approach. In Proceedings of the Second Conference on Empirical Methods in Natural Language Processing, pages 47–54. Association for Computational Linguistics. find
  35. Salton, Gerard, James Allan, and Chris Buckley. 1993. Approaches to passage retrieval in full text information systems. In Proceedings of the 16th Annual International ACM/SIGIR Conference, pages 49–58, Pittsburgh, PA. find
  36. Salton, Gerard, James Allan, Chris Buckley, and Amit Singhal. 1994. Automatic analysis, theme generation, and summarization of machine-readable texts. Science, 264(5164):1421–1426. van Mulbregt, P., Ira Carp, Larry Gillick, Stephen Lowe, and Jonathan Yamron. 1999. Segmentation of automatically trans… find
  37. Yaari, Yaakov. 1997. Segmentation of expository text by hierarchical agglomerative clustering. In Recent Advances in NLP (RANLP’97), Bulgaria. find