Efficient Graph Kernels for Textual Entailment Recognition

• Autorzy: Zanzotto F. M. , Dell'Arciprete L. , Moschitti A.
• Języki publikacji: EN

Abstrakty

EN

One of the most important research area in Natural Language Processing concerns the modeling of semantics expressed in text. Since foundational work in Natural Language Understanding has shown that a deep semantic approach is still not feasible, current research is focused on shallow methods combining linguistic models and machine learning techniques. The latter aim at learning semantic models, like those that can detect the entailment between the meaning of two text fragments, by means of training examples described by specific features. These are rather difficult to design since there is no linguistic model that can effectively encode the lexico-syntactic level of a sentence and its corresponding semantic models. Thus, the adopted solution consists in exhaustively describing training examples by means of all possible combinations of sentence words and syntactic information. The latter, typically expressed as parse trees of text fragments, is often encoded in the learning process using graph algorithms. In this paper, we propose a class of graphs, the tripartite directed acyclic graphs (tDAGs), which can be efficiently used to design algorithms for graph kernels for semantic natural language tasks involving sentence pairs. These model the matching between two pairs of syntactic trees in terms of all possible graph fragments. Interestingly, since tDAGs encode the association between identical or similar words (i.e. variables), it can be used to represent and learn first-order rules, i.e. rules describable by first-order logic. We prove that our matching function is a valid kernel and we empirically show that, although its evaluation is still exponential in the worst case, it is extremely efficient and more accurate than the previously proposed kernels.

Słowa kluczowe

EN

supervised machine learning; Kernels; natural language processing; efficient algorithm

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 107, nr 2/3
• Strony: 199--222
• Opis fizyczny: Bibliogr. 49 poz., wykr.

Twórcy

autor

Zanzotto F. M.

autor

Dell'Arciprete L.

autor

Moschitti A.

• University of Rome "Tor Vergata" Via del Politecnico 1, 00133 Roma, Italy,

Bibliografia

• [1] Aizerman, A., Braverman, E. M., Rozoner, L. I.: Theoretical foundations of the potential function method in pattern recognition learning, Automation and Remote Control, 25, 1964, 821-837.
• [2] Bar-Haim, R., Dagan, I., Dolan, B., Ferro, L., Giampiccolo, D., Magnini, Bernardo Szpektor, I.: The Second PASCAL Recognising Textual Entailment Challenge, in: Proceedings of the Second PASCAL Challenges Workshop on Recognising Textual Entailment, Venice, Italy, 2006.
• [3] Carpenter, B.: The Logic of Typed Feature Structures, Cambridge University Press, Cambridge, England, 1992.
• [4] Charniak, E.: A Maximum-Entropy-Inspired Parser, Proc. of the 1st NAACL, Seattle, Washington, 2000.
• [5] Chierchia, G., McConnell-Ginet, S.: Meaning and Grammar: An introduction to Semantics, MIT press, Cambridge,MA, 2001.
• [6] Chomsky, N.: Aspect of Syntax Theory, MIT Press, Cambridge,Massachussetts, 1957.
• [7] Collins, M.: Head-Driven Statistical Models for Natural Language Parsing, Comput. Linguist., 29(4), 2003, 589-637, ISSN 0891-2017.
• [8] Collins, M., Duffy, N.: New Ranking Algorithms for Parsing and Tagging: Kernels over Discrete Structures, and the Voted Perceptron, in: Proceedings of ACL02, 2002.
• [9] Corley, C., Mihalcea, R.: Measuring the Semantic Similarity of Texts, in: Proc. of the ACL Workshop on Empirical Modeling of Semantic Equivalence and Entailment, Association for Computational Linguistics, Ann Arbor, Michigan, June 2005, 13-18.
• [10] Cortes, C., Vapnik, V.: Support Vector Networks, Machine Learning, 20, 1995, 1-25.
• [11] Cristianini, N., Shawe-Taylor, J.: An Introduction to Support Vector Machines and Other Kernel-based Learning Methods, Cambridge University Press, March 2000, ISBN 0521780195.
• [12] Dagan, I., Glickman, O.: Probabilistic Textual Entailment: Generic Applied Modeling of Language Variability, Proceedings of the Workshop on Learning Methods for Text Understanding and Mining, Grenoble, France, 2004.
• [13] Dagan, I., Glickman, O.,Magnini, B.: The PASCAL Recognising Textual Entailment Challenge, LNAI 3944: MLCW 2005 (Q.-C. et al., Ed.), Springer-Verlag,Milan, Italy, 2006.
• [14] Dang, H. T.: Overview of DUC 2005, Proceedings of the 2005 Document Understanding Workshop, 2005.
• [15] Eisner, J.: LearningNon-IsomorphicTreeMappings forMachine Translation, Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics (ACL), Companion Volume, Sapporo, July 2003.
• [16] Gärtner, T.: A Survey of Kernels for Structured Data, SIGKDD Explorations, 2003.
• [17] Gildea, D., Jurafsky, D.: Automatic Labeling of Semantic Roles, Computational Linguistics, 28(3), 2002, 245-288.
• [18] Grinberg, D., Lafferty, J., Sleator, D.: A robust parsing algorithm for link grammar, 4th International workshop on parsing tecnologies, Prague, 1996.
• [19] Haghighi, A. D., Ng, A. Y., Manning, C. D.: Robust textual inference via graph matching, HLT '05: Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, Association for Computational Linguistics, Morristown, NJ, USA, 2005.
• [20] Harabagiu, S., Hickl, A.: Methods for Using Textual Entailment in Open-Domain Question Answering, Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, Association for Computational Linguistics, Sydney,Australia, July 2006.
• [21] Harabagiu, S., Hickl, A., Lacatusu, F.: Satisfying information needs with multi-document summaries, Information Processing & Management, 43(6), 2007, 1619 - 1642, ISSN 0306-4573, Text Summarization.
• [22] Hickl, A.,Williams, J., Bensley, J., Roberts, K., Rink, B., Shi, Y.: Recognizing Textual Entailmentwith LCCs GROUNDHOG System, Proceedings of the Second PASCAL Recognizing Textual Entailment Challenge (B. Magnini, I. Dagan, Eds.), Springer-Verlag, Venice, Italy, 2006.
• [23] Jiang, J. J., Conrath, D. W.: Semantic similarity based on corpus statistics and lexical taxonomy, in: Proc. Of the 10th ROCLING, Tapei, Taiwan, 1997, 132-139.
• [24] Köbler, J., Schöning, U., Torán, J.: The graph isomorphism problem: its structural complexity, Birkhauser Verlag, Basel, Switzerland, Switzerland, 1993, ISBN 0-8176-3680-3.
• [25] Lin, D., Pantel, P.: DIRT: discovery of inference rules from text, Knowledge Discovery and Data Mining, 2001.
• [26] Marcus, M. P., Santorini, B., Marcinkiewicz, M. A.: Building a Large Annotated Corpus of English: The Penn Treebank, Computational Linguistics, 19, 1993, 313-330.
• [27] de Marneffe,M.-C., MacCartney, B., Grenager, T., Cer, D., Rafferty, A., D. Manning, C.: Learning to distinguish valid textual entailments, Proceedings of the Second PASCAL Challenges Workshop on Recognising Textual Entailment, Venice, Italy, 2006.
• [28] Minnen, G., Carroll, J., Pearce, D.: Applied morphological processing of English, Natural Language Engineering, 7(3), 2001, 207-223.
• [29] Moschitti, A.: A study on Convolution Kernels for Shallow Semantic Parsing, proceedings of the ACL, Barcelona, Spain, 2004.
• [30] Moschitti, A., Pighin, D., Basili, R.: Tree Kernels for Semantic Role Labeling, Computational Linguistics, 34(2), 2008, 193-224.
• [31] Moschitti, A., Zanzotto, F. M.: Fast and Effective Kernels for Relational Learning from Texts, in: Proceedings of the International Conference of Machine Learning (ICML), Corvallis, Oregon, 2007.
• [32] MUC-7: Proceedings of the SeventhMessage Understanding Conference (MUC-7), Columbia,MD, Morgan Kaufmann, 1997.
• [33] Nivre, J., Hall, J., Kübler, S., McDonald, R., Nilsson, J., Riedel, S., Yuret, D.: The CoNLL 2007 Shared Task on Dependency Parsing, in: Proceedings of the CoNLL Shared Task Session of EMNLP-CoNLL 2007, Association for Computational Linguistics, Prague, Czech Republic, June 2007, 915-932.
• [34] Pantel, p., Pennacchiotti, M.: Espresso: A Bootstrapping Algorithm for AutomaticallyHarvesting Semantic Relations, Proceedings of the 21st Coling and 44th ACL, Sydney, Australia, July 2006.
• [35] Peas, A., lvaro Rodrigo, Verdejo, F.: Overview of the Answer Validation Exercise 2007., CLEF (C. Peters, V. Jijkoun, T. Mandl, H. Mller, D. W. Oard, A. Peas, V. Petras, D. Santos, Eds.), 5152, Springer, 2007, ISBN 978-3-540-85759-4.
• [36] Pedersen, T., Patwardhan, S., Michelizzi, J.: WordNet::Similarity - Measuring the Relatedness of Concepts, in: Proc. of 5th NAACL, Boston, MA, 2004.
• [37] Pollard, C., Sag, I.: Head-driven Phrase Structured Grammar, Chicago CSLI, Stanford, 1994.
• [38] Quinlan, J.: C4:5:programs for Machine Learning, Morgan Kaufmann, San Mateo, 1993.
• [39] Raina, R., Haghighi, A., Cox, C., Finkel, J., Michels, J., Toutanova, K., MacCartney, B., de Marneffe,M.-C., Christopher,M., Ng, A. Y.: Robust Textual Inference Using Diverse Knowledge Sources, Proceedings of the 1st Pascal Challenge Workshop, Southampton, UK, 2005.
• [40] Ramon, J., Gärtner, T.: Expressivity versus Efficiency of Graph Kernels, First International Workshop on Mining Graphs, Trees and Sequences, 2003.
• [41] Suzuki, J., Hirao, T., Sasaki, Y., Maeda, E.: Hierarchical Directed Acyclic Graph Kernel: Methods for Structured Natural Language Data, In Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics, 2003.
• [42] Tesniere, L.: Elements de syntaxe structural, Klincksiek, Paris, France, 1959.
• [43] Voorhees, E. M.: The TREC question answering track, Nat. Lang. Eng., 7(4), 2001, 361-378, ISSN 1351-3249.
• [44] Wang, J.: Average-case computational complexity theory, 1997, 295-328.
• [45] Wang, R., Neumann, G.: Recognizing Textual Entailment Using a Subsequence KernelMethod, Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence (AAAI-07), July 22-26, Vancouver, Canada, 2007.
• [46] Zanzotto, F. M., Moschitti, A.: Automatic Learning of Textual Entailments with Cross-Pair Similarities, in: Proceedings of the 21st Coling and 44th ACL, Sydney, Australia, July 2006, 401-408.
• [47] Zanzotto, F.M.,Moschitti, A.: Experimenting a "General Purpose" Textual Entailment Learner in AVE, vol. 4730, Springer, DEU, 2007, ISBN 978-3-540-74998-1, 510-517.
• [48] Zanzotto, F. M., Pennacchiotti, M., Moschitti, A.: A Machine Learning Approach to Textual Entailment Recognition, NATURAL LANGUAGE ENGINEERING, 15-04, 2009, 551-582, ISSN 1351-3249.
• [49] Zanzotto, F. M., Pennacchiotti, M., Pazienza, M. T.: Discovering asymmetric entailment relations between verbs using selectional preferences, Proceedings of the 21st Coling and 44th ACL, Sydney, Australia, July 2006.