Elamur Research⌕
☰
home / papers / 2003 / Probabilistic Text Structuring: Experiments with Sentence Ordering

Probabilistic Text Structuring: Experiments with Sentence Ordering

Summary

Lapata addresses information ordering, which means arranging a given set of sentences into a coherent sequence. This matters for text-to-text generation tasks such as multidocument summarization and question answering, where sentences come from different sources and no tree-like semantic plan is available. The paper proposes an unsupervised probabilistic model trained on the BLLIP corpus of Wall Street Journal stories. Each sentence is described by automatically extracted lexical and syntactic features, such as verbs with their subjects or nouns with their modifiers. The model treats a text as a first-order Markov chain over sentences. It estimates the probability of one sentence following another from pairwise feature co-occurrences across adjacent sentences, with Katz back-off smoothing. A greedy search then builds an acceptable order. Model orders are compared with authored texts and with human orderings using Kendall's τ. The best feature sets perform close to the level of agreement between humans. On the multidocument summaries of Barzilay et al. (2002), the V_D N_D features beat a random baseline. The approach is portable across domains and requires no manual annotation.

Key points

  • Training data: the BLLIP corpus (30M words, WSJ 1987–89), with 98,732 stories averaging 19.2 sentences. About 71.30% of the stories are shorter than 50 sentences.
  • The probability P(S_i|S_{i-1}) is a product over all feature pairs in the Cartesian product of the two sentences. It is normalized by the number of pairs so that sentences with many features are not penalized.
  • Finding an optimal order is NP-complete (Cohen et al., 1999). The paper therefore uses a greedy algorithm with beam width one, which first picks the likeliest opening sentence and then repeatedly picks the likeliest successor.
  • In the experiment with human subjects, N_L and V_D N_D were not significantly different from human–human agreement. The other feature sets did significantly worse.
  • In the summarization experiment (Barzilay et al. data, MULTIGEN-style summaries of 8.8 sentences on average, ten subjects):
    • Average pairwise τ was .60 between humans, .56 for V_D N_D and .48 for N_L.
    • Only V_D N_D significantly outperformed the random baseline B_R.

Interesting ideas

  • I1. Representing sentences as feature bags to fight sparsity. Exact sentences almost never repeat, so the model counts transitions between their parts instead. The same trick can turn any sequence-of-units problem, such as ordering paragraphs or dialogue turns, into something learnable from raw corpora.
  • I2. Taking all cross-sentence feature pairs without choosing in advance. The model accepts some noise in exchange for not having to guess which dependencies matter. Because of this, it can simply be retrained on a new domain or language, which is attractive for low-resource settings such as Ukrainian corpora.
  • I3. Using Kendall's τ against human orderings as an automatic metric. Rank correlation with several human orders gives a cheap proxy for coherence. Inter-human agreement then serves as an upper bound, which is a reusable evaluation design for any ordering or ranking task.
  • I4. Using feature ablation to diagnose the type of coherence. Entity-only features worked for single newswire texts but failed on cross-document event summaries. Comparing feature families can therefore show whether a genre relies more on entity coherence or on event and temporal coherence.
  • I5. Ordering when chronology gives no signal. A learned ordering model offers a fallback for summarization when publication dates are missing or identical, a common situation with scraped or aggregated data.

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

93 papers of our library cite it (of the 140884 whose bibliographies we read); 10 of them have a page here, 83 not yet.

Cite

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

@inproceedings{lapata2003probabilistic,
  title = {{Probabilistic Text Structuring: Experiments with Sentence Ordering}},
  author = {Lapata, Mirella},
  booktitle = {Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics},
  year = {2003},
  doi = {10.3115/1075096.1075165},
  url = {https://doi.org/10.3115/1075096.1075165}
}

References

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

  1. Asher, Nicholas and Alex Lascarides. 2003. Logics of Conversation. Cambridge University Press. find
  2. Barzilay, Regina. 2003. Information Fusion for Multi-Document Summarization: Praphrasing and Generation. Ph.D. thesis, Columbia University. find
  3. Barzilay, Regina, Noemie Elhadad, and Kathleen R. McKeown. 2002. Inferring strategies for sentence ordering in multidocument news summarization. Journal of Artificial Intelligence Research 17:35–55. find
  4. Charniak, Eugene. 2000. A maximum-entropy-inspired parser. In Proceedings of the 1st Conference of the North American Chapter of the Association for Computational Linguistics. Seattle, WA, pages 132–139. find our card
  5. Cohen, William W., Robert E. Schapire, and Yoram Singer. 1999. Learning to order things. Journal of Artificial Intelligence Research 10:243–270. find
  6. Grosz, Barbara, Aravind Joshi, , and Scott Weinstein. 1995. Centering: A framework for modeling the local coherence of discourse. Computational Linguistics 21(2):203–225. find our card
  7. Katz, Slava M. 1987. Estimation of probabilities from sparse data for the language model component of a speech recognizer. IEEE Transactions on Acoustics Speech and Signal Processing 33(3):400–401. find
  8. Kibble, Rodger and Richard Power. 2000. An integrated framework for text planning and pronominalisation. In In Proceedings of the 1st International Conference on Natural Language Generation. Mitzpe Ramon, Israel, pages 77–84. find
  9. Lebanon, Guy and John Lafferty. 2002. Combining rankings using conditional probability models on permutations. In C. Sammut and A. Hoffmann, editors, In Proceedings of the 19th International Conference on Machine Learning. Morgan Kaufmann Publishers, San Francisco, CA. find
  10. Lin, Dekang. 1998. Dependency-based evaluation of MINIPAR. In In Proceedings on of the LREC Workshop on the Evaluation of Parsing Systems. Granada, pages 48–56. find
  11. Marcu, Daniel. 1997. From local to global coherence: A bottom-up approach to text planning. In In Proceedings of the 14th National Conference on Artificial Intelligence. Providence, Rhode Island, pages 629–635. find
  12. Marcus, Mitchell P., Beatrice Santorini, and Mary Ann Marcinkiewicz. 1993. Building a large annotated corpus of english: The penn treebank. Computational Linguistics 19(2):313–330. find our card
  13. McKeown, Kathleen R., Judith L. Klavans, Vasileios Hatzivassiloglou, Regina Barzilay, and Eleazar Eskin. 1999. Towards multidocument summarization by reformulation: Progress and prospects. In Proceedings of the 16th National Conference on Artificial Intelligence. Orlando, FL, pages 453–459. find
  14. Mellish, Chris, Alistair Knott, Jon Oberlander, and Mick O’ Donnell. 1998. Experiments using stochastic search for text planning. In In Proceedings of the 9th International Workshop on Natural Language Generation. Ontario, Canada, pages 98–107. find
  15. Reiter, Ehud and Robert Dale. 2000. Building Natural Language Generation Systems. Cambridge University Press, Cambridge. find
  16. Sampson, Geoffrey. 1996. English for the Computer. Oxford University Press. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/lapata-2003-probabilistic-text-structuring-experiments-sentence/