Elamur Research⌕
☰
home / papers / 2009 / Dialogue Act Prediction Using Stochastic Context-Free Grammar Induction

Dialogue Act Prediction Using Stochastic Context-Free Grammar Induction

Paper · 2009 · Jeroen Geertzen

Summary

The paper asks how a dialogue system could choose its next move using structure learned from data instead of hand-written rules. Geertzen treats dialogue management as dialogue act prediction: given the history, suggest the most plausible next act. Acts follow the DIT taxonomy, where each act pairs a communicative function with a semantic content. Each dialogue becomes a sequence of symbols that encode the speaker and up to three simultaneous functions. A grammatical inference algorithm, the Dialogue Grammars Inducer (DGI), builds on alignment-based learning. It finds interchangeable subsequences and turns them into stochastic context-free grammars whose non-terminals act like "dialogue games." The resulting SCFGs predict next acts in the DIAMOND corpus. They are compared with a heuristic baseline and with n-gram language models. SCFG models clearly beat n-grams when predicting communicative functions. Predicting full acts with semantic content stays hard, though SCFGs still lead. The work matters because hierarchical grammars can capture nested patterns such as clarification sub-dialogues, which flat n-grams handle poorly.

Key points

  • Data: the DIAMOND corpus, about 1,600 functional segments. A 250-utterance development subset alone yielded 45 induced "dialogue games."
  • Symbols are 4-tuples: interlocutor plus up to three dialogue acts. The roughly 0.5% of cases with four simultaneous functions are ignored.
  • DGI uses five phases, including segmentation by silent time gaps, alignment learning, and selection learning via Viterbi beam search.
  • For communicative function prediction, the best n-gram model reached 66.4% accuracy and the best SCFG model 78.9%.
  • With semantic content included, simplifying that content raised the best n-gram from 35.1% to 37.5% and the best SCFG from 42.9% to 46.6%. Only 2-grams, and partly 3-grams, were trainable on this sparse data.

Interesting ideas

  • I1. When several functions co-occur, pack them into one symbol with a fixed canonical order: task functions first, then feedback, then the rest, alphabetically within groups. Symbol identity then becomes trivial to check, and this richer encoding beat main-function-only symbols despite sparser data.
  • I2. Alignment-based learning compares sequences pairwise and treats spans that share surrounding context as interchangeable constituents, inducing hierarchical structure without supervision.
  • I3. A grammar with non-terminals can cluster symbols and capture gapped or nested regularities, such as a question–answer pair wrapped around a clarification, which flat n-grams cannot represent.
  • I4. Reducing semantic content to a simpler form measurably improved prediction by easing sparsity, showing a useful trade-off between symbol detail and learnability.
  • I5. The author notes that scoring against one observed continuation is too strict and that several next acts may be equally valid, so evaluation should use sets of attested continuations from similar contexts.

For Mova

How these ideas could serve Mova, our small open language model — its files, stages and tests:

  • I1 (frames): speech-act annotations in prag could store multifunctional utterances as canonically ordered tuples, so identical act bundles compare equal and remain traceable.
  • I2 (learn): the same alignment trick could propose candidate repair rules or construction patterns from silver parses, using spans that recur in identical contexts.
  • I3 (world): event ordering in dialogue-heavy tales could model nested exchanges as constituents, letting the world track which answer closes which open question.
  • I4 (frames): when learning frame-sequence statistics, back off from full logical forms to predicate-level skeletons so rare arguments do not fragment the counts.
  • I5 (learn): evaluation of generated replies or predicted next events could accept any member of a gold set gathered from comparable contexts, avoiding unfair penalties.

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 CambridgeCambridge · United Kingdom243 works · 121,396 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

🧭 Topics 3Research subjects and languages the work is about.Dialogue systems · 624 worksSyntax & grammar formalisms · 214 worksSpeech act theory · 229 works

Cite

Cite as Jeroen Geertzen. 2009. Dialogue Act Prediction Using Stochastic Context-Free Grammar Induction. Proceedings of the EACL 2009 Workshop on Computational Linguistic Aspects of Grammatical Inference.

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

@inproceedings{geertzen2009dialogue,
  title = {{Dialogue Act Prediction Using Stochastic Context-Free Grammar Induction}},
  author = {Jeroen Geertzen},
  booktitle = {Proceedings of the EACL 2009 Workshop on Computational Linguistic Aspects of Grammatical Inference},
  year = {2009},
  doi = {10.3115/1705475.1705478},
  url = {https://doi.org/10.3115/1705475.1705478}
}

References

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

  1. Jan Alexandersson and Norbert Reithinger. 1997. Learning dialogue structures from a corpus. In Proceedings of Eurospeech 1997, pages 2231–2234, Rhodes, Greece, September. find
  2. Hiyan Alshawi. 1990. Resolving quasi logical forms. Computational Linguistics, 16(3):133–144.
  3. Harry Bunt. 2000. Dialogue pragmatics and context specification. In Harry Bunt and William Black, editors, Abduction, Belief and Context in Dialogue; Studies in Computational Pragmatics, pages 81– 150. John Benjamins, Amsterdam, The Netherlands. ↗
  4. Harry Bunt. 2006. Dimensions in dialogue annotation. In Proceedings of the 5th International Conference on Language Resources and Evaluation (LREC 2006), pages 1444–1449, Genova, Italy, May. find
  5. Jeroen Geertzen and Menno M. van Zaanen. 2004. Grammatical inference using suffix trees. In Proceedings of the 7th International Colloquium on Grammatical Inference (ICGI), pages 163–174, Athens, Greece, October. find
  6. Jeroen Geertzen, Yann Girard, and Roser Morante. 2004. The DIAMOND project. Poster at the 8th Workshop on the Semantics and Pragmatics of Dialogue (CATALOG 2004), Barcelona, Spain, July. find
  7. John Godfrey, Edward Holliman, and Jane McDaniel. 1992. SWITCHBOARD: Telephone speech corpus for research and development. In Proceedings of the ICASSP-92, pages 517–520, San Francisco, USA. find
  8. Jeroen Groenendijk and Martin Stokhof. 1991. Dynamic predicate logic. Linguistics and Philosophy, 14(1):39–100. find
  9. Slava M. Katz. 1987. Estimation of probabilities from sparse data for the language model component of a speech recognizer. IEEE Transactions on Acoustics, Speech, and Signal Processing, 35(3):400–401. ↗
  10. Oliver Lemon, Kallirroi Georgila, and James Henderson. 2006. Evaluating effectiveness and portability of reinforcement learned dialogue strategies with real users: The talk towninfo evaluation. In Spoken Language Technology Workshop, pages 178–181. find
  11. Joan A. Levin and Johanna A. Moore. 1988. Dialogue-games: metacommunication structures for natural language interaction. Distributed Artificial Intelligence, pages 385–397. ↗
  12. Esther Levin, Roberto Pieraccini, and Wieland Eckert. 1998. Using markov decision process for learning dialogue strategies. In Proceedings of the ICASSP’98, pages 201–204, Seattle, WA, USA. find
  13. Lori Levin, Klaus Ries, Ann Thymé-Gobbel, and Alon Lavie. 1999. Tagging of speech acts and dialogue games in spanish call home. In Proceedings of ACL-99 Workshop on Discourse Tagging, College Park, MD, USA. ↗
  14. Masaaki Nagata and Tsuyoshi Morimoto. 1994. First steps towards statistical modeling of dialogue to predict the speech act type of the next utterance. Speech Communication, 15(3-4):193–203. ↗
  15. Tim Paek. 2006. Reinforcement learning for spoken dialogue systems: Comparing strenghts and weaknesses for practical deployment. In Interspeech Workshop on ”Dialogue on Dialogues”. find
  16. Massimo Poesio and Andrei Mikheev. 1998. The predictive power of game structure in dialogue act recognition: Experimental results using maximum entropy estimation. In Proceedings International Conference on Spoken Language Processing (ICSLP-98), Sydney, Australia, December. find
  17. Livia Polanyi and Remko Scha. 1984. A syntactic approach to discourse semantics. In Proceedings of the 10th international conference on Computational linguistics, pages 413–419, Stanford, CA, USA. find
  18. Norbert Reithinger and Elisabeth Maier. 1995. Utilizing statistical dialogue act processing in VERB-MOBIL. In Proceedings of the 33rd annual meeting on the Association for Computational Linguistics (ACL), pages 116–121, Cambridge, Massachusetts. Association for Computational Linguistics (ACL). find
  19. Uwe Reyle. 1993. Dealing with ambiguities by underspecification: Construction, representation and deduction. Journal of Semantics, 10(2):123–179. ↗
  20. Emanuel A. Schegloff. 1968. Sequencing in conversational openings. American Anthropologist, 70:1075–1095. find
  21. Andreas Stolcke, Klaus Ries, Noah Coccaro, Elizabeth Shriberg, Rebecca Bates, Daniel Jurafsky, Paul Taylor, Rachel Martin, Carol Van Ess-Dykema, and Marie Meteer. 2000. Dialogue act modeling for automatic tagging and recognition of conversational speech. Computational Linguistics, 26(3):339–373. ↗
  22. Richard S. Sutton and Andrew G. Barto. 1998. Reinforcement Learning: An Introduction (Adaptive Computation and Machine Learning). MIT Press, March. find
  23. Menno van Zaanen and Pieter W. Adriaans. 2001. Comparing two unsupervised grammar induction systems: Alignment-Based Learning vs. EMILE. Technical Report TR2001.05, University of Leeds, Leeds, UK, March. find
  24. Menno M. van Zaanen. 2002. Bootstrapping Structure into Language: Alignment-Based Learning. Ph.D. thesis, University of Leeds, Leeds, UK, January. ↗
  25. Andrew J. Viterbi. 1967. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Transactions on Information Theory, 13(2):260–269, April. ↗
  26. Marilyn Walker, Candace Kamm, and Diane Litman. 2000. Towards developing general models of usability with paradise. Natural Language Engineering, 6(3-4):363–377. ↗
  27. Ian H. Witten and Timothy C. Bell. 1991. The zero-frequency problem: Estimating the probabilities of novel events in adaptive text compression. IEEE Transactions on Information Theory, 37(4):1085– 1094. ↗
  28. Steve Young. 2002. The statistical approach to the design of spoken dialogue systems. Technical Report CUED/F-INFENG/TR.433, Engineering Department, Cambridge University, UK, September. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/geertzen-2009-dialogue-act-prediction-stochastic-context/