Elamur Research⌕
☰
home / papers / 2006 / Automatic Evaluation of Information Ordering: Kendall's Tau

Automatic Evaluation of Information Ordering: Kendall's Tau

Paper · 2006 · Mirella Lapata

Summary

Information ordering means arranging preselected content units, such as sentences, propositions, database facts or discourse trees, into a coherent sequence. It is a core step in concept-to-text generation and multidocument summarization. Several studies already used Kendall's τ, a rank correlation statistic, to compare system orders with a human reference, but no one had tested whether it reflects human perception. Lapata addresses this gap.

She first argues for τ. It is computed from the minimum number of adjacent swaps between two orders, and it ignores how the items are represented. It penalizes reversals. For small samples it also beats Spearman's coefficient: it is unbiased, approaches normality faster and keeps Type I errors under control.

She then runs two behavioural studies:

  • a judgment elicitation experiment, in which participants rated differently ordered versions of texts;
  • an online reading experiment, which measured processing time.

τ correlates with both the ratings and the reading times. It is therefore a cheap, domain-independent proxy for development-time evaluation and possibly for direct optimization. It complements human assessment rather than replacing it.

Key points

  • Definition: τ = 1 − 2S(π,σ) / (N(N−1)/2), where S is the minimum number of adjacent transpositions. Values range from −1 (reversed order) to 1 (identical order).

  • In a 10-item example, one system scores τ = 0.82 against the reference. A second system that only swaps the first and last items scores just 0.24, reflecting how badly swapping the opening and closing parts harms coherence.

  • In the reading study, τ correlated with reading times at r = −0.48 (p < 0.01). Human ratings correlated with reading times at r = −0.47. The negative sign means texts that are better ordered are read faster.

  • All evaluations used a single reference text. For future work, the paper proposes averaging τ over multiple references or weighting transpositions by how consistently the references agree.

  • The paper contrasts τ with three alternatives:

    • exact-match accuracy (Barzilay and Lee 2004; Barzilay and Lapata 2005);
    • the rank of the reference among all N! permutations;
    • domain-specific alignment (Duboue and McKeown 2002).

    Unlike these, τ gives partial credit to orders that are close but not identical to the reference.

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

🎓University of EdinburghEdinburgh · United Kingdom255 works · 68,771 citations

📚 Shelves 5The 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 worksInformation Systems · 523 works

🧭 Topics 1Research subjects and languages the work is about.Evaluation & benchmarks · 685 works

Cite

Cite as Mirella Lapata. 2006. Automatic Evaluation of Information Ordering: Kendall's Tau. Computational Linguistics.

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

@article{lapata2006automatic,
  title = {{Automatic Evaluation of Information Ordering: Kendall's Tau}},
  author = {Mirella Lapata},
  journal = {Computational Linguistics},
  year = {2006},
  doi = {10.1162/coli.2006.32.4.471},
  url = {https://doi.org/10.1162/coli.2006.32.4.471}
}

References

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

  1. Arndt, Stephan, Carolyn Turvey, and Nancy C. Andreasen. 1999. Correlating and predicting psychiatric symptom ratings: Spearman’s r versus Kendall’s tau correlation. Journal of Psychiatric Research, 33:97–104. find
  2. Baayen, Harald R. 2004. Statistics in psycholinguistics: A critique of some current gold standards. In Mental Lexicon Working Papers 1. University of Alberta, Edmonton, pages 1–45. find
  3. Bangalore, Srinivas, Owen Rambow, and Steven Whittaker. 2000. Evaluation metrics for generation. In Proceedings of the INLG, pages 1–8, Mitzpe Ramon, Israel. find
  4. Barzilay, Regina. 2003. Information Fusion for Multi-Document Summarization: Paraphrasing and Generation. Ph.D. thesis, Columbia University. find
  5. 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
  6. Barzilay, Regina and Mirella Lapata. 2005. Modeling local coherence: An entity-based approach. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics, pages 141–148, Ann Arbor. find
  7. Barzilay, Regina and Lillian Lee. 2004. Catching the drift: Probabilistic content models, with applications to generation and summarization. In Proceedings of the 2nd Human Language Technology Conference and Annual Meeting of the North American Chapter of the Association for Computational Linguistic…
  8. Britton, Bruce K. 1991. Using Kintsch’s computational model to improve instructional text: Effects of repairing inference calls on recall and cognitive structures. Journal of Educational Psychology, 83(3):329–345. find
  9. Callison-Burch, Chris, Miles Osborne, and Philipp Koehn. 2006. Re-evaluating the role of B LEU in machine translation research. In Proceedings of the 11th Conference of the European Chapter of the Association of Computational Linguistics, pages 249–256, Trento, Italy. find
  10. Coughlin, Deborah. 2003. Correlating automated and human assessments of machine translation quality. In Proceedings of MT Summit IX, pages 63–70, New Orleans. find
  11. Dimitromanolaki, Aggeliki and Ion Androutsopoulos. 2003. Learning to order facts for discourse planning in natural language generation. In Proceedings of the 9th European Workshop on Natural Language Generation, pages 113–120, Budapest, Hungary. find
  12. Doddington, George. 2002. Automatic evaluation of machine translation quality using n-gram cooccurrence statistics. In Human Language Technology: Notebook Proceedings, pages 128–132, San Diego. find
  13. Duboue, Pablo and Kathleen R. McKeown. 2002. Content planner construction via evolutionary algorithms and a corpus-based fitness function. In Proceedings of INLG 2002, pages 89–96, New York. find
  14. Duboue, Pablo A. and Kathleen R. McKeown. 2001. Empirically estimating order constraints for content planning in generation. In Proceedings of the 39th Annual Meeting of the Association for Computational Linguistics, pages 172–179, Toulouse, France. find
  15. Hays, William L. 1994. Statistics. Harcourt Brace College Publishers, New York, 3rd edition. find
  16. Hovy, Eduard and Chin-Yew Lin. 2003. Automatic evaluation of summaries using N-gram co-occurrence statistics. In Proceedings of the 1st Human Language Technology Conference and Annual Meeting of the North American Chapter of the Association for Computational Linguistics, pages 71–78, Edmonton, Canad…
  17. Karamanis, Nikiforos. 2003. Entity Coherence for Descriptive Text Structuring. Ph.D. thesis, University of Edinburgh. find
  18. Karamanis, Nikiforos and Hisar Maruli Manurung. 2002. Stochastic text structuring using the principle of continuity. In Proceedings of the 2nd International Conference on Natural Language Generation, pages 81–88, New York. find
  19. Karamanis, Nikiforos and Chris Mellish. 2005. Using a corpus of sentence orderings defined by many experts to evaluate metrics of coherence for text structuring. In Proceedings of the 10th European Workshop on Natural Language Generation, pages 174–179, Aberdeen, Scotland. find
  20. Kendall, Maurice G. 1938. A new measure of rank correlation. Biometrika, 30:81–93. find
  21. Kendall, Maurice G. and Jean Dickinson Gibbons. 1990. Rank Correlation Methods. Oxford University Press, New York. find
  22. Kerridge, D. 1975. The interpretation of rank correlations. Applied Statistics, 24(2):257–258. find
  23. Lapata, Maria and Alex Lascarides. 2003. A probabilistic account of logical metonymy. Computational Linguistics, 29(2):263–317.
  24. Lapata, Mirella. 2003. Probabilistic text structuring: Experiments with sentence ordering. In Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics, pages 545–552, Sapporo, Japan.
  25. Lebanon, Guy and John Lafferty. 2002. Combining rankings using conditional probability models on permutations. In Proceedings of the 19th International Conference on Machine Learning. San Francisco, CA: Morgan Kaufmann Publishers, pages 363–370. find
  26. Lorch, Robert F. and Jerome L. Myers. 1990. Regression analyses of repeated measures data in cognitive research. Journal of Experimental Psychology: Learning, Memory, and Cognition, 16(1):149–157. find
  27. Mani, Inderjeet. 2001. Automatic Summarization. John Benjamins Pub Co., Amsterdam; Philadelphia. find
  28. McKoon, Gail and Roger Ratcliff. 1992. Inference during reading. Psychological Review, 99(3):440–446. find
  29. Mellish, Chris, Alistair Knott, Jon Oberlander, and Mick O’ Donnell. 1998. Experiments using stochastic search for text planning. In Proceedings of the 9th International Workshop on Natural Language Generation, pages 98–107, Ontario, Canada. find
  30. Nenkova, Ani. 2005. Automatic text summarization of newswire: Lessons learned from the document understanding conference. In Proceedings of the 20th National Conference on Artificial Intelligence, pages 1436–1441, Pittsburgh, PA. find
  31. Och, Franz Joseph. 2003. Minimum error rate training in statistical machine translation. In Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics, pages 160–167, Sapporo, Japan. find
  32. Okazaki, Naoaki, Yutaka Matsuo, and Mitsuru Ishizuka. 2004. Improving chronological sentence ordering by precedence relation. In Proceedings of the 20th International Conference on Computational Linguistics, Geneva, Switzerland, pages 750–756. find
  33. Papineni, Kishore, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002. B LEU : A method for automatic evaluation of machine translation. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, pages 311–318, Philadelphia, PA. find
  34. Radev, Dragomir and Kathleen R. McKeown. 1998. Generating natural language summaries from multiple on-line sources. Computational Linguistics, 24(3):469–500. find
  35. Resnik, Philip. 1999. Semantic similarity in a taxonomy: An information-based measure and its application to problems of ambiguity in natural language. Journal of Artificial Intelligence Research, pages 95–130. find
  36. Resnik, Philip and Mona Diab. 2000. Measuring verb similarity. In Proceedings of the 22nd Annual Conference of the Cognitive Science Society. Lawrence Erlbaum Associates, Mahwah, NJ, pages 399–404. find
  37. Siegel, Sidney and N. John Castellan. 1988. Non Parametric Statistics for the Behavioral Sciences. McGraw-Hill, New York. find
  38. Teufel, Simone and Hans van Halteren. 2004. Evaluating information content by factoid analysis: Human annotation and stability. In Dekang Lin and Dekai Wu, editors, Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 419–426, Barcelona. find
  39. Weiss, Sholom M. and Casimir A. Kulikowski. 1991. Computer Systems that Learn: Classification and Prediction Methods from Statistics, Neural Nets, Machine Learning, and Expert Systems. Morgan Kaufmann, San Mateo, CA. find
  40. White, John S. and T. O’Connell. 1994. The ARPA MT evaluation methodologies: Evolution, lessons, and future approaches. In Proceedings of the First Conference of the Association for Machine Translation in the Americas, pages 193–205, Columbia, MD.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/lapata-2006-automatic-evaluation-information-ordering-kendall/