Elamur Research⌕
☰
home / papers / 2003 / Graph-Based Generation of Referring Expressions

Graph-Based Generation of Referring Expressions

Paper · 2003 · Emiel Krahmer, Sebastiaan van Erk and André Verleg

Summary

This paper addresses content determination for referring expressions: choosing which properties and relations of a target object to mention so that a hearer can tell it apart from distractor objects. The authors model a scene (objects, their attributes and the relations between them) as a labeled directed graph. Choosing content then becomes the task of building a subgraph around the target that fits no distractor. A branch and bound search, steered by cost functions, explores candidate subgraphs, and the costs determine which valid description is preferred. Swapping cost functions lets the framework mimic, and in places improve, earlier algorithms such as Dale's full brevity method and Dale and Reiter's incremental algorithm. Because attributes and relations are both just edges, relational descriptions need no special handling, which sidesteps problems in earlier proposals. The approach matters because it links referring-expression generation to established graph theory, puts competing algorithms in one comparable framework, and opens a route to combining rule-based and statistical generation. (The excerpt provided omits the core algorithm and cost-function sections, so their details are not summarized here.)

Key points

  • Published in Computational Linguistics (2003) by Emiel Krahmer, Sebastiaan van Erk and André Verleg (Tilburg University / Eindhoven University of Technology).
  • Running example: four animals (three dogs and one cat) differing in size and colour. Full brevity picks {small, dog} for d1. The incremental algorithm with preference order ⟨type, color, size⟩ picks {dog, brown, small}, where brown ends up redundant.
  • Full brevity yields minimal descriptions but is NP hard. The incremental algorithm runs in polynomial time because it never backtracks.
  • Earlier relational approaches had specific flaws. Dale and Haddock's could recurse endlessly, describing a dog by the doghouse it is in, that doghouse by the dog inside it, and so on without end, which they patched by allowing each property or relation only once. Krahmer and Theune's incremental extension suffers from "forced incrementality" when adding relations.
  • A second scene (two dogs and two doghouses) uses the relations left of, right of, contain and in. It shows a case where only a relation can separate one dog from the other. Surface realization is delegated to standard realizers such as KPML or SURGE.

Interesting ideas

  • I1. Represent everything as graph edges. Encoding one-place properties as looping edges and relations as edges between nodes means one search procedure covers both. This trick could simplify any system that mixes attributes and relations, such as knowledge-graph querying or entity descriptions in geographic data.
  • I2. Cost functions as a pluggable preference layer. Separating the search from the scoring lets one engine reproduce several published algorithms by changing only the costs. This makes formal comparison between methods straightforward and is a useful design for benchmarking alternatives in any generation task.
  • I3. Bridge between rules and statistics. Since preferences live in costs, those costs could be estimated from corpus frequencies rather than set by hand. This offers a clean way to inject data-driven preferences, for example for Ukrainian descriptions, into a symbolic pipeline.
  • I4. Branch and bound over candidate descriptions. Pruning partial subgraphs once they cost more than the best solution found so far keeps the search for the cheapest distinguishing description manageable. The same pattern suits other "smallest distinguishing set" problems, such as choosing features that uniquely identify a record.

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

🎓Tilburg UniversityTilburg · Netherlands40 works · 6,231 citations🎓Eindhoven University of TechnologyEindhoven · Netherlands4 works · 525 citations

📚 Shelves 4The 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 works

🧭 Topics 1Research subjects and languages the work is about.Text generation · 145 works

Cite

Cite as Emiel Krahmer, Sebastiaan van Erk and André Verleg. 2003. Graph-Based Generation of Referring Expressions. Computational Linguistics.

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

@article{krahmer2003graph,
  title = {{Graph-Based Generation of Referring Expressions}},
  author = {Emiel Krahmer, Sebastiaan {van Erk} and André Verleg},
  journal = {Computational Linguistics},
  year = {2003},
  doi = {10.1162/089120103321337430},
  url = {https://doi.org/10.1162/089120103321337430}
}

References

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

  1. Appelt, Douglas E. 1985. Planning English referring expressions. Artificial Intelligence, 26:1–33. find
  2. Bateman, John. 1997. Enabling technology for multilingual natural language generation: The KPML development environment. Natural Language Engineering, 3:15–55. find
  3. Bateman, John. 1999. Using aggregation for selecting content when generating referring expressions. In Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics (ACL’99), University of Maryland. find
  4. Bauckhage, Christian, Jannik Fritsch, Franz Kummert, and Gerhard Sagerer. 1999. Towards a vision system for supervising assembly processes. In Proceedings of the Symposium on Intelligent Robotic Systems (SIRS’99), pages 89–98. find
  5. Berge, Claude. 1985. Graphs. North-Holland, Amsterdam. find
  6. Blackburn, Patrick. 2000. Representation, reasoning, and relational structure: A hybrid logic manifesto. Logic Journal of the IGPL, 8(3):339–365. find
  7. Chartrand, Gary and Ortrud Oellermann. 1993. Applied and Algorithmic Graph Theory. McGraw-Hill, New York. find
  8. Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. 1990. Introduction to Algorithms. MIT Press, Cambridge. find
  9. Dale, Robert. 1992. Generating Referring Expressions: Constructing Descriptions in a Domain of Objects and Processes. MIT Press, Cambridge. find
  10. Dale, Robert and Nicholas Haddock. 1991. Generating referring expressions involving relations. In Proceedings of the Fifth Conference of the European Chapter of the Association for Computational Linguistics (EACL’91), pages 161–166, Berlin. find
  11. Dale, Robert and Ehud Reiter. 1995. Computational interpretations of the Gricean maxims in the generation of referring expressions. Cognitive Science, 18:233–263.
  12. Elhaded, Michael and Jacques Robin. 1997. SURGE : A comprehensive plug-in syntactic realization component for text generation. Technical Report 96-03, Computer Science Department, Ben-Gurion University, Beer Sheva, Israel. find
  13. Eppstein, David. 1999. Subgraph isomorphism in planar graphs and related problems. Journal of Graph Algorithms and Applications, 3(3):1–27. find
  14. Faugeras, Olivier. 1993. Three-Dimensional Computer Vision. MIT Press, Cambridge. find
  15. Garey, Michael R. and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York. find
  16. Gibbons, Alan M. 1985. Algorithmic Graph Theory. Cambridge University Press, Cambridge. find
  17. Grosz, Barbara J., Aravind K. Joshi, and Scott Weinstein. 1995. Centering: A framework for modeling the local coherence of discourse. Computational Linguistics, 21(2):203–225.
  18. Hajic̆ová, Eva. 1993. Issues of Sentence Structure and Discourse Patterns. Charles University, Prague. find
  19. Hopcroft, John E. and Robert Tarjan. 1974. Efficient planarity testing. Journal of the Association for Computing Machinery, 21:549–568. find
  20. Horacek, Helmut. 1997. An algorithm for generating referential descriptions with flexible interfaces. In Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics (ACL’97), pages 206–213, Madrid. find
  21. Krahmer, Emiel and Mariët Theune. 1998. Context sensitive generation of descriptions. In Proceedings of the Fifth International Conference on Spoken Language Processing (ICSLP’98), pages 1151–1154, Sydney. find
  22. Krahmer, Emiel and Mariët Theune. 2002. Efficient context-sensitive generation of descriptions. In Kees van Deemter and Rodger Kibble, editors, Information Sharing: Givenness and Newness in Language Processing. CSLI Publications, Stanford, California, pages 223–264. find
  23. Krahmer, Emiel, Sebastiaan van Erk, and André Verleg. 2001. A meta-algorithm for the generation of referring expressions. In Proceedings of the Eighth European Workshop on Natural Language Generation (EWNLG’01), Toulouse. find
  24. Langkilde, Irene and Kevin Knight. 1998. The practical value of n-grams in generation. In Proceedings of the Ninth International Workshop on Natural Language Generation (INLG’98), pages 248–255, Niagara-on-the-Lake, Ontario. find
  25. Liebers, Annegret. 2001. Planarizing graphs. Journal of Graph Algorithms and Applications, 5(1):1–74. find
  26. Malouf, Rob. 2000. The order of prenominal adjectives in natural language generation. In Proceedings of the 38th Annual Meeting of the Association for Computational Linguistics (ACL’00), Hong Kong. find
  27. Messmer, Bruno T. and Horst Bunke. 1995. Subgraph isomorphism in polynomial time. Technical Report IAM 95-003, University of Bern, Institute of Computer Science and Applied Mathematics, Bern, Switzerland. find
  28. Messmer, Bruno T. and Horst Bunke. 1998. A new algorithm for error-tolerant subgraph isomorphism detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 20(5):493–504. find
  29. Pechmann, Thomas. 1989. Incremental speech production and referential overspecification. Linguistics, 27:98–110. find
  30. Read, Ronald C. and Derek G. Corneil. 1977. The graph isomorphism disease. Journal of Graph Theory, 1(1):339–363. find
  31. Reiter, Ehud. 1990. The computational complexity of avoiding conversational implicatures. In Proceedings of the 28th Annual Meeting of the Association for Computational Linguistics (ACL’90), pages 97–104.
  32. Rosch, Eleanor. 1978. Principles of categorization. In E. Rosch and B. Lloyd, editors, Cognition and Categorization. Lawrence Erlbaum, Hillsdale, New Jersey, pages 27–48. find
  33. Sedgewick, Robert. 1988. Algorithms. Addison-Wesley, Reading, Massachusetts, second edition. find
  34. Stone, Matthew and Bonnie Webber. 1998. Textual economy through close coupling of syntax and semantics. In Proceedings of the Ninth International Workshop on Natural Language Generation (INLG’98), pages 178–187, Niagara-on-the-Lake, Ontario. find
  35. Tarjan, Robert E. 1972. Depth-first search and linear time algorithms. SIAM Journal on Computing, 1(2):146–160. find
  36. Theune, Mariët. 2000. From Data to Speech: Language Generation in Context. Ph.D. thesis, Eindhoven University of Technology, Eindhoven, The Netherlands. van Deemter, Kees. 2000. Generating vague descriptions. In Proceedings of the First International Natural Language Generation Conference (INLG’00)… find
  37. Wilson, Robin J. 1996. Introduction to Graph Theory. Longman, Harlow, England, fourth edition. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/krahmer-2003-graph-based-generation-referring-expressions/