Elamur Research⌕
☰
home / papers / 2007 / What is the Jeopardy Model? A Quasi-Synchronous Grammar for QA

What is the Jeopardy Model? A Quasi-Synchronous Grammar for QA

Summary

The paper addresses answer-sentence selection for short-answer (factoid) questions: choosing, from candidates returned by retrieval, the sentence that actually answers a question. Bag-of-words matching struggles with lexical substitutions (leader vs. president) and syntactic shifts (leader of France vs. French president). The authors therefore treat the question as if it were generated from the answer sentence through loose syntactic and semantic transformations. They implement this as the "Jeopardy model," a probabilistic quasi-synchronous dependency grammar adapted from D. Smith and Eisner's (2006) machine translation work. The model mixes a robust non-lexical syntax/alignment component with an optional log-linear component that uses WordNet features. Word alignments between the dependency trees are hidden and summed out, and the model is trained with conditional maximum likelihood. On TREC QA data, it clearly beats reimplemented versions of two prior systems, Cui et al. (2005) and Punyakanok et al. (2004), even when WordNet is added to those baselines. The work shows that explicitly modeling soft tree-to-tree transformations helps QA, where earlier attempts to add syntactic features had often failed.

Key points

  • Task setup:
    • Candidate answers are fixed at sentence granularity.
    • Dependency parses come from a McDonald et al. parser.
    • The prior p(a) over candidates is assumed uniform.
    • Training uses manually judged answers for TREC 8–12 questions 1–100.
  • Main result (test set):
    • The full Jeopardy model reaches MAP 0.6029 and MRR 0.6852.
    • The best baseline, Cui et al., gets MAP 0.4350 and MRR 0.5569.
    • The Jeopardy base model alone (without the lexical-semantics component) gets MAP 0.4828 and MRR 0.5571.
  • Baselines:
    • TreeMatch is a reimplementation of Punyakanok et al. (2004), based on tree edit distance and requiring no training.
    • Cui et al. (2005) relies on dependency-path similarity.
    • Both were also extended with WordNet ("+WN").
  • Noisy training data:
    • Questions 101–2,393 were labeled automatically. A candidate counted as correct if it shared at least three non-stop word types with the question and matched the answer pattern.
    • This hurt every trained method. The Jeopardy model degraded less (test MAP 0.5655) than Cui et al. (0.2833; 0.3811 with +WN).
  • Summing vs. maximizing over alignments:
    • Summing in both training and decoding works best (test MAP 0.6029).
    • Using the max during training is worse (0.5559–0.5571).
    • Significance was tested with a two-tailed paired t-test (p < 0.03).

Interesting ideas

  • I1. Reversed generative story: Imagine the question being produced from the answer, as a noisy-channel "translation." This makes scoring a QA pair a tree-to-tree alignment problem. The same framing could apply to paraphrase detection, textual entailment, or matching queries to documents.
  • I2. Loose grammar instead of strict synchronous structure: Quasi-synchronous grammar lets one tree be generated by a grammar inspired by the other tree. It allows a menu of local alignment configurations instead of demanding isomorphism. This suits "free" correspondences such as morphologically rich or loosely translated text.
  • I3. Alignment as a latent variable that is summed out: The model never commits to one word correspondence. It marginalizes over all of them, and the experiments show this beats picking the single best alignment, especially during training. This is useful wherever alignments are uncertain and gold alignments are unavailable.
  • I4. Mixing a smoothed base model with an optional log-linear component: The multinomial base model provides robustness and smoothing. The log-linear part can absorb arbitrary task-specific features (e.g., WordNet relations) without normalizing over huge sets. The pattern suits low-resource settings, where lexical resources may be sparse but still helpful.
  • I5. Cheap noisy labeling as a stress test: Automatically labeled data (keyword overlap plus answer pattern) is used both to expand training and to measure how gracefully each method degrades under label noise. This is a reusable evaluation trick when manual annotation is expensive.

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: Machine translation · Natural language processing

Topics: Dependency parsing

Cited by

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

Cite

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

@inproceedings{wang2007what,
  title = {{What is the Jeopardy Model? A Quasi-Synchronous Grammar for QA}},
  author = {Wang, Mengqiu and Smith, Noah A. and Mitamura, Teruko},
  booktitle = {Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL)},
  year = {2007},
  url = {https://aclanthology.org/D07-1003/}
}

References

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

  1. Giuseppe Attardi, Antonio Cisternino, Francesco Formica, Maria Simi, Alessandro Tommasi, Ellen M. Voorhees, and D. K. Harman. 2001. Selectively using relations to improve precision in question answering. In Proceedings of the 10th Text REtrieval Conference (TREC-10), Gaithersburg, MD, USA. find
  2. Leonard E. Baum, Ted Petrie, George Soules, and Norman Weiss. 1970. A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains. The Annals of Mathematical Statistics, 41(1):164–171. ↗
  3. Daniel M. Bikel, Richard Schwartz, and Ralph M. Weischedel. 1999. An algorithm that learns whatś in a name. Machine Learning, 34(1-3):211–231. ↗
  4. Peter F. Brown, John Cocke, Stephen A. Della Pietra, Vincent J. Della Pietra, Frederick Jelinek, John D. Lafferty, Robert L. Mercer, and Paul S. Roossin. 1990. A statistical approach to machine translation. Computational Linguistics, 16(2):79–85. ↗
  5. Peter F. Brown, Stephen A. Della Pietra, Vincent J. Della Pietra, and Robert L. Mercer. 1993. The mathematics of statistical machine translation: Parameter estimation. Computational Linguistics, 19(2):263–311. find
  6. Hang Cui, Renxu Sun, Keya Li, Min-Yen Kan, and Tat-Seng Chua. 2005. Question answering passage retrieval using dependency relations. In Proceedings of the 28th ACM-SIGIR International Conference on Research and Development in Information Retrieval, Salvador, Brazil. find
  7. Arthur Dempster, Nan Laird, and Donald Rubin. 1977. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, 39(1):1–38. ↗
  8. Yuan Ding and Martha Palmer. 2005. Machine translation using probabilistic synchronous dependency insertion grammars. In Proceedings of the 43st Annual Meeting of the Association for Computational Linguistics (ACL), Ann Arbor, MI, USA. find our card
  9. Abdessamad Echihabi and Daniel Marcu. 2003. A noisy-channel approach to question answering. In Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics (ACL), Sapporo, Japan. find
  10. Jason Eisner. 2003. Learning non-isomorphic tree mappings for machine translation. In Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics (ACL), Sapporo, Japan. find our card
  11. Michel Galley, Jonathan Graehl, Kevin Knight, Daniel Marcu, Steve DeNeefe, Wei Wang, and Ignacio Thayer. 2006. Scalable inference and training of context-rich syntactic translation models. In Proceedings of the 21st International Conference on Computational Linguistics and the 44st Annual Meeting of the Association for Computational Linguistics (COLING-ACL), Sydney, Australia. find our card
  12. Daniel Gildea. 2003. Loosely tree-based alignment for machine translation. In Proceedings of the 41st Annual Meeting on Association for Computational Linguistics (ACL), Sapporo, Japan. find our card
  13. Sanda Harabagiu and Andrew Hickl. 2006. Methods for using textual entailment in open-domain question answering. In Proceedings of the 21st International Conference on Computational Linguistics and the 44th Annual Meeting of the Association for Computational Linguistics (COLING-ACL), Sydney, Australia. find
  14. Abraham Ittycheriah, Martin Franz, and Salim Roukos. 2001. IBM’s statistical question answering system— TREC-10. In Proceedings of the 10th Text REtrieval Conference (TREC-10), Gaithersburg, MD, USA. find
  15. Tony Jebara and Alex Pentland. 1999. Maximum conditional likelihood via bound maximization and the CEM algorithm. In Proceedings of the 1998 Conference on Advances in Neural Information Processing Systems II (NIPS), pages 494–500, Denver, CO, USA. find
  16. Boris Katz and Jimmy Lin. 2003. Selectively using relations to improve precision in question answering. In Proceedings of the EACL-2003 Workshop on Natural Language Processing for Question Answering, Gaithersburg, MD, USA. find
  17. Jinxi Xu Ana Licuanan and Ralph Weischedel. 2003. Trec2003 qa at bbn: Answering definitional questions. In Proceedings of the 12th Text REtrieval Conference (TREC-12), Gaithersburg, MD, USA. find
  18. Kenneth C. Litkowski. 1999. Question-answering using semantic relation triples. In Proceedings of the 8th Text REtrieval Conference (TREC-8), Gaithersburg, MD, USA. find
  19. Dong C. Liu and Jorge Nocedal. 1989. On the limited memory BFGS method for large scale optimization. Math. Programming, 45:503–528. ↗
  20. Bill MacCartney, Trond Grenager, Marie-Catherine de Marneffe, Daniel Cer, and Christopher D. Manning. 2006. Learning to recognize features of valid textual entailments. In Proceedings of the Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics (HLT-NAACL), New York, NY, USA. find
  21. Mitchell P. Marcus, Mary Ann Marcinkiewicz, and Beatrice Santorini. 1993. Building a large annotated corpus of english: the penn treebank. Computational Linguistics, 19(2):313–330. ↗ our card
  22. Ryan McDonald, Koby Crammer, and Fernado Pereira. 2005. Online large-margin training of dependency parsers. In Proceedings of the 43st Annual Meeting of the Association for Computational Linguistics (ACL), Ann Arbor, MI, USA. find our card
  23. I. Dan Melamed. 2004. Algorithms for syntax-aware statistical machine translation. In Proceedings of the Conference on Theoretical and Methodological Issues in Machine Translation (TMI), Baltimore, MD, USA. find
  24. Xiao-Li Meng and Donald B. Rubin. 1993. Maximum likelihood estimation via the ECM algorithm: A general framework. Biometrika, 80:267–278. ↗
  25. George A. Miller, Richard Beckwith, Christiane Fellbaum, Derek Gross, and Katherine J. Miller. 1990. WordNet: an on-line lexical database. International Journal of Lexicography, 3(4). find
  26. Vanessa Murdock and W. Bruce Croft. 2005. A translation model for sentence retrieval. In Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing (HLT-EMNLP), Vancouver, BC, USA. find
  27. Vasin Punyakanok, Dan Roth, and Wen-Tau Yih. 2004. Mapping dependencies trees: An application to question answering. In Proceedings of the 8th International Symposium on Artificial Intelligence and Mathematics, Fort Lauderdale, FL, USA. find
  28. Chris Quirk, Chris Brockett, and William Dolan. 2004. Monolingual machine translation for paraphrase generation. In Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing (EMNLP), Barcelona, Spain. find our card
  29. Chris Quirk, Arul Menezes, and Colin Cherry. 2005. Dependency treelet translation: Syntactically informed phrasal SMT. In Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics (ACL), Ann Arbor, MI, USA. find our card
  30. Adwait Ratnaparkhi. 1996. A maximum entropy part-of-speech tagger. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), Philadelphia, PA, USA. find
  31. Deepak Ravichandran, Abharam Ittycheriah, and Salim Roukos. 2003. Automatic derivation of surface text patterns for a maximum entropy based question answering system. In Proceedings of the Human Language Technology Conference and North American Chapter of the Association for Computational Linguistics (HLT-NAACL), Edmonton, Canada. find
  32. Dan Shen and Dietrich Klakow. 2006. Exploring correlation of dependency relation paths for answer extraction. In Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics (COLING-ACL), Sydney, Australia. find
  33. Dan Shen, Geert-Jan M. Kruijff, and Dietrich Klakow. 2005. Exploring syntactic relation patterns for question answering. In Proceedings of the Second International Joint Conference on Natural Language Processing (IJCNLP), Jeju Island, Republic of Korea. find
  34. Hideki Shima, Mengqiu Wang, Frank Lin, and Teruko Mitamura. 2006. Modular approach to error analysis and evaluation for multilingual question answering. In Proceedings of the Fifth International Conference on Language Resources and Evaluation (LREC), Genoa, Italy. find
  35. David A. Smith and Jason Eisner. 2006. Quasi-synchronous grammars: Alignment by soft projection of syntactic dependencies. In Proceedings of the HLT-NAACL Workshop on Statistical Machine Translation, New York, NY, USA. find our card
  36. Martin M. Soubbotin and Sergei M. Soubbotin. 2001. Patterns for potential answer expressions as clues to the right answers. In Proceedings of the 10th Text REtrieval Conference (TREC-10), Gaithersburg, MD, USA. find
  37. Dekai Wu and Hongsing Wong. 1998. Machine translation with a stochastic grammatical channel. In Proceedings of the 17th International Conference on Computational Linguistics (COLING), Montreal, Canada. find
  38. Dekai Wu. 2005. Recognizing paraphrases and textual entailment using inversion transduction grammars. In Proceedings of the ACL Workshop on Empirical Modeling of Semantic Equivalence and Entailment, Ann Arbor, MI, USA. find
  39. Kenji Yamada and Kevin Knight. 2001. A syntax-based statistical translation model. In Proceedings of the 39th Annual Meeting of the Association for Computational Linguistics (ACL), Toulouse, France. find our card

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/papers/wang-2007-what-is-jeopardy-model-quasi/