Hostname: page-component-8448b6f56d-mp689 Total loading time: 0 Render date: 2024-04-20T06:30:56.040Z Has data issue: false hasContentIssue false
  • English
  • Français

Unsupervised acquisition of entailment relations from the Web

Published online by Cambridge University Press:  30 July 2013

IDAN SZPEKTOR ,
HRISTO TANEV ,
IDO DAGAN ,
BONAVENTURA COPPOLA  and
MILEN KOUYLEKOV
IDAN SZPEKTOR
Affiliation:
Yahoo! Research, Haifa, Israel e-mail: idan@yahoo-inc.com
HRISTO TANEV
Affiliation:
JRC, Ispra, Italy e-mail: htanev@gmail.com
IDO DAGAN
Affiliation:
Department of Computer Science, Bar-Ilan University, Ramat Gan, Israel e-mail: dagan@cs.biu.ac.il
BONAVENTURA COPPOLA
Affiliation:
IBM Thomas J. Watson Research Center, Yorktown Heights, NY e-mail: bcoppola@us.ibm.com
MILEN KOUYLEKOV
Affiliation:
CELI s.r.l., Torino, Italy e-mail: kouylekov@celi.it
Get access Rights & Permissions [Opens in a new window]

Abstract

Entailment recognition is a primary generic task in natural language inference, whose focus is to detect whether the meaning of one expression can be inferred from the meaning of the other. Accordingly, many NLP applications would benefit from high coverage knowledgebases of paraphrases and entailment rules. To this end, learning such knowledgebases from the Web is especially appealing due to its huge size as well as its highly heterogeneous content, allowing for a more scalable rule extraction of various domains. However, the scalability of state-of-the-art entailment rule acquisition approaches from the Web is still limited. We present a fully unsupervised learning algorithm for Web-based extraction of entailment relations. We focus on increased scalability and generality with respect to prior work, with the potential of a large-scale Web-based knowledgebase. Our algorithm takes as its input a lexical–syntactic template and searches the Web for syntactic templates that participate in an entailment relation with the input template. Experiments show promising results, achieving performance similar to a state-of-the-art unsupervised algorithm, operating over an offline corpus, but with the benefit of learning rules for different domains with no additional effort.

Type
Articles
Information
Natural Language Engineering , Volume 21 , Issue 1 , January 2015 , pp. 3 - 47
Copyright
Copyright © Cambridge University Press 2013 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Androutsopoulos, I., and Malakasiotis, P., 2010. A survey of paraphrasing and textual entailment methods. Journal of Artificial Intelligence Research 38: 135–87.Google Scholar
Baeza-Yates, R., and Raghavan, P. 2010. Chapter 2: next generation web search. In Ceri, S., and Brambilla, M. (eds.), Search Computing, pp. 11–23. Lecture Notes in Computer Science, vol. 5950. Berlin/Heidelberg: Springer.Google Scholar
Baker, C. F., Fillmore, C. J., and Lowe, J. B. 1998. The berkeley framenet project. In Proceedings of the 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics, Vol. 1(ACL '98), pp. 86–90. Stroudsburg, PA: Association for Computational Linguistics.Google Scholar
Bannard, C. J., and Callison-burch, C. 2005. Paraphrasing with bilingual parallel corpora. In Meeting of the Association for Computational Linguistics, Ann Arbor, Michigan.Google Scholar
Bar-Haim, R., Dagan, I., Dolan, B., Ferro, L., Giampiccolo, D., Magnini, B., and Szpektor, I. 2006. The second PASCAL recognising textual entailment challenge. In Second PASCAL Challenge Workshop for Recognizing Textual Entailment, Venice, Italy.Google Scholar
Bar-haim, R., Dagan, I., Greental, I., and Shnarch, E. 2007. Semantic inference at the lexical-syntactic level. In National Conference on Artificial Intelligence, Vancouver, British Columbia, Canada.Google Scholar
Bar-Haim, R., Szpektor, I., and Glickman, O. 2005. Definition and analysis of intermediate entailment levels. In Proceedings of the ACL Workshop on Empirical Modeling of Semantic Equivalence and Entailment, Ann Arbor, Michigan.Google Scholar
Barzilay, R., and Lee, L. 2003. Learning to paraphrase: an unsupervised approach using multiple-sequence alignment. In North American Chapter of the Association for Computational Linguistics, vol. cs.CL/0304, Stroudsburg, PA, USA.Google Scholar
Barzilay, R., and McKeown, K. R., 2001. Extracting paraphrases from a parallel corpus. In Meeting of the Association for Computational Linguistics, Toulose, France, pp. 50–57.Google Scholar
Ben Aharon, R., Szpektor, I., and Dagan, I. 2010. Generating entailment rules from FrameNet. In Proceedings of the ACL 2010 Conference Short Papers, pp. 241–6. Uppsala, Sweden: Association for Computational Linguistics.Google Scholar
Bentivogli, L., Dagan, I., Dang, H. T., Giampiccolo, D., and Magnini, B. 2009. The fifth PASCAL recognizing textual entailment challenge. In Proceedings of the TAC 2009 Workshop, Gaithersburg, Maryland, USA.Google Scholar
Bentivogli, L., Clark, P., Dagan, I., Dang, H. T., and Giampiccolo 2010. The sixth PASCAL recognizing textual entailment challenge. In Proceedings of the TAC 2010 Workshop, Gaithersburg, Maryland, USA.Google Scholar
Berant, J., Dagan, I., and Goldberger, J., 2012. Learning entailment relations by global graph structure optimization. Computational Linguistics 38 (1): 73–111.Google Scholar
Bergadano, F., and Gunetti, D., 1995. Inductive Logic Programming: From Machine Learning to Software Engineering. Cambridge, MA: MIT Press.Google Scholar
Bhagat, R., Pantel, P., and Hovy, E. H. 2007. LEDIR: an unsupervised algorithm for learning directionality of inference rules. In Empirical Methods in Natural Language Processing, Prague, Czech Republic, pp. 161–70.Google Scholar
Carletta, J., 1996. Assessing agreement on classification tasks: the Kappa statistic. Computational Linguistics 22 (2): 249–54.Google Scholar
Chklovski, T., and Pantel, P. 2004. VerbOcean: mining the web for fine-grained semantic verb relations. In Lin, D. and Wu, D. (eds.), Empirical Methods in Natural Language Processing, Association for Computational Linguistics, Barcelona, Spain, pp. 33–40.Google Scholar
Condoravdi, C., Crouch, D., de Paiva, V., Stolle, R., and Bobrow, D. G. 2003. Entailment, intensionality and text understanding. In Proceedings of the HLT-NAACL 2003 Workshop on Text Meaning, Stroudsburg, PA, USA.Google Scholar
Dagan, I., and Glickman, O. 2004. Probabilistic textual entailment: generic applied modeling of language variability. In PASCAL Workshop on Learning Methods for Text Understanding and Mining, Grenoble, France.Google Scholar
Dagan, I., Glickman, O., and Magnini, B. 2006. The PASCAL recognising textual entailment challenge. In Quiñonero-Candela, J., Dagan, I., Magnini, B., and d'Alché-Buc, F. (eds.), Machine Learning Challenges. Evaluating Predictive Uncertainty, Visual Object Classification, and Recognising Tectual Entailment, Lecture Notes in Computer Science, Vol. 3944, pp. 177–90. Berlin: Springer.Google Scholar
Dolan, B., Quirk, C., and Brockett, C. 2004. Unsupervised construction of large paraphrase corpora: exploiting massively parallel news sources. In International Conference on Computational Linguistics, Stroudsburg, PA, USA.Google Scholar
Duclaye, F., Yvon, F., and Collin, O., 2002. Using the web as a linguistic resource for learning reformulations automatically. In Language Resources and Evaluation, Las Palmas, Spain, pp. 390–96.Google Scholar
Durme, B. Van, Huang, Y., Jupść, A., and Nyberg, E. 2003. Towards light semantic processing for question answering. In Proceedings of HLT/NAACL Workshop on Text Meaning 2003, Stroudsburg, PA, USA.Google Scholar
Erk, K., and Padó, S., 2008. A structured vector space model for word meaning in context. In Empirical Methods in Natural Language Processing, Stroudsburg, PA, USA, pp. 897–906.Google Scholar
Giampiccolo, D., Dang, H. T., Magnini, B., Dagan, I., Cabrio, E., and Dolan, B. 2008. The forth PASCAL recognizing textual entailment challenge. In Proceedings of the TAC 2008 Workshop, Gaithersburg, Maryland, USA.Google Scholar
Giampiccolo, D., Magnini, B., Dagan, I., and Dolan, B. 2007. The third PASCAL recognizing textual entailment challenge. In Proceedings of the ACL-PASCAL Workshop on Textual Entailment and Paraphrasing, Prague, Czech Republic.Google Scholar
Glickman, O., and Dagan, I. 2003. Identifying lexical paraphrases from a single corpus: a case study for verbs. In Recent Advances in Natural Language Processing (RANLP), Borovets, Bulgaria.Google Scholar
Harabagiu, S., and Hickl, A., 2006. Methods for using textual entailment in open-domain question answering. In Meeting of the Association for Computational Linguistics, Sydney, Australia, pp. 905–12.Google Scholar
Hermjakob, U., Echihabi, A., and Marcu, D. 2003. Natural language based reformulation resource and web exploitation. In Voorhees, E. M. and Buckland, L. P. (eds.), Proceedings of the 11th Text Retrieval Conference (TREC 2002). Gaithersburg, MD: NIST.Google Scholar
Ibrahim, A., Katz, B., and Lin, J. 2003. Extracting structural paraphrases from aligned monolingual corpora. In Proceedings of the Second International Workshop on Paraphrasing (IWP-2003), Sapporo, Japan.Google Scholar
Jacquemin, C. 1999. Syntagmatic and paradigmatic representations of term variation. In Meeting of the Association for Computational Linguistics, College Park, Maryland, USA.Google Scholar
Kietz, J.-U., and Lubbe, M. 1994. An efficient subsumption algorithm for inductive logic programming. In ICML, New Brunswick, NJ, USA.Google Scholar
Kipper, K., Dang, H. T., and Palmer, M. S., 2000. Class-based construction of a verb lexicon. In National Conference on Artificial Intelligence, Austin, Texas, USA, pp. 691–6.Google Scholar
Kotlerman, L., Dagan, I., Szpektor, I., and Zhitomirsky-Geffet, M., 2010. Directional distributional similarity for lexical inference. Natural Language Engineering 16 (4): 359–89.Google Scholar
Lin, D. 1998. Dependency-based evaluation of Minipar. In Proceedings of the Workshop on Evaluation of Parsing Systems at LREC 1998, Granada, Spain.Google Scholar
Lin, D., and Pantel, P., 2001. Discovery of inference rules for question answering. Natural Language Engineering 7 (4): 343–60.Google Scholar
Lloret, E., Ferrández, Ó., Muñoz, R., and Palomar, M., 2008. A text summarization approach under the influence of textual entailment. In Natural Language Understanding and Cognitive Science, Barcelona, Spain, pp. 22–31.Google Scholar
Markov, Z., and Pelov, N. 1998. A framework for inductive learning based on subsumption lattices. In Giunchiglia, F. (ed.), Artificial Intelligence: Methodology, Systems, and Applications, Proceedings of the 8th International Conference (AIMSA 98), pp. 341–52. Lecture Notes in Computer Science, vol. 1480. Sozopol, Bulgaria: Springer.Google Scholar
Mausam, M. S., Bart, R., Soderland, S., and Etzioni, O. 2012. Open language learning for information extraction. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning(EMNLP-CoNLL '12), pp. 523–34. Stroudsburg, PA: Association for Computational Linguistics.Google Scholar
Miller, G. A., 1995. WordNet: a lexical database for English. Communications of The ACM 38: 39–41.Google Scholar
Mirkin, S., Dagan, I., and Shnarch, E. 2009. Evaluating the inferential utility of lexical–semantic resources. In Proceedings of the 12th Conference of the European Chapter of the ACL (EACL 2009), pp. 558–566. Athens, Greece: Association for Computational Linguistics.Google Scholar
Moldovan, D., and Rus, V. 2001. Logic form transformation of WordNet and its applicability to Question Answering. In Proceedings of ACL 2001, Toulose, France, pp 394–401.Google Scholar
Monz, C., and de Rijke, M. 2001. Light-weight entailment checking for computational semantics. In Proceedings of the Third Workshop on Inference in Computational Semantics (ICoS-3), Italy.Google Scholar
Nakashole, N., Weikum, G., and Suchanek, F. 2012. Patty: a taxonomy of relational patterns with semantic types. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP–CoNLL’12), pp. 1135–45. Stroudsburg, PA: Association for Computational Linguistics.Google Scholar
Pang, B., Knight, K., and Marcu, D. 2003. Syntax-based alignment of multiple translations: extracting paraphrases and generating new sentences. In North American Chapter of the Association for Computational Linguistics, Edmonton, Canada.Google Scholar
Pantel, P., Bhagat, R., Coppola, B., Chklovski, T., and Hovy, E. 2007. ISP: learning inferential selectional preferences. In Proceedings of North American Association for Computational Linguistics/Human Language Technology Conference (NAACL HLT 07), Rochester, New York.Google Scholar
Pantel, P., and Pennacchiotti, M. 2006. Espresso: leveraging generic patterns for automatically harvesting semantic relations. In Proceedings of the 21st International Conference on Computational Linguistics and the 44th Annual Meeting of the Association for Computational Linguistics, pp. 113–20. Stroudsburg, PA: Association for Computational Linguistics.Google Scholar
Pekar, V. 2006 (June). Acquisition of verb entailment from text. In Proceedings of the Human Language Technology Conference of the NAACL, Main Conference, New York City, USA, pp. 49–56.Google Scholar
Ravichandran, D., and Hovy, E. H., 2002. Learning surface text patterns for a Question Answering system. In Meeting of the Association for Computational Linguistics, Philadelphia, PA, pp. 41–7.Google Scholar
Reynar, J. C., and Ratnaparkhi, A. 1997. A maximum entropy approach to identifying sentence boundaries. In Proceedings of the fifth conference on Applied natural language processing, pp. 16–9. Stroudsburg, PA: Association for Computational Linguistics.Google Scholar
Reynolds, J. C., 1970. Transformational systems and the algebraic structure of atomic formulas. Machine Intelligence 5: 135–51.Google Scholar
Romano, L., Kouylekov, M., Szpektor, I., Dagan, I., and Lavelli, A. 2006. Investigating a generic paraphrase-based approach for relation extraction. In Conference of the European Chapter of the Association for Computational Linguistics, Trento, Italy.Google Scholar
Schoenmackers, S., Etzioni, O., Weld, D. S., and Davis, J. 2010. Learning first-order horn clauses from web text. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing(EMNLP '10), pp. 1088–98. Stroudsburg, PA: Association for Computational Linguistics.Google Scholar
Sekine, S. 2005. Automatic paraphrase discovery based on context and keywords between NE pairs. In The 3rd International Workshop on Paraphrasing, Jeju Island, South Korea.Google Scholar
Shinyama, Y., and Sekine, S. 2006. Preemptive information extraction using unrestricted relation discovery. In North American Chapter of the Association for Computational Linguistics, New York City, USA.Google Scholar
Shinyama, Y., Sekine, S., Sudo, K., and Grishman, R. 2002. Automatic paraphrase acquisition from news articles. In Proceedings of Human Language Technology Conference (HLT 2002), San Diego, CA, USA.Google Scholar
Suchanek, F. M., Ifrim, G., and Weikum, G., 2006. Combining linguistic and statistical analysis to extract relations from web documents. In Knowledge Discovery and Data Mining, Philadelphia, USA, pp. 712–7.Google Scholar
Sudo, K., Sekine, S., and Grishman, R., 2003. An improved extraction pattern representation model for automatic IE pattern acquisition. In Meeting of the Association for Computational Linguistics, Sapporo, Japan, pp. 224–31.Google Scholar
Szpektor, I., and Dagan, I. 2007. Learning canonical forms of entailment rules. In Recent Advances in Natural Language Processing (RANLP), Borovets, Bulgaria.Google Scholar
Szpektor, I., and Dagan, I., 2008. Learning entailment rules for unary templates. In International Conference on Computational Linguistics, Manchester, UK, pp. 849–56.Google Scholar
Szpektor, I., Dagan, I., Bar-Haim, R., and Goldberger, J. 2008 (June). Contextual preferences. In Proceedings of ACL-08: HLT, pp. 683–91. Columbus, OH: Association for Computational Linguistics.Google Scholar
Szpektor, I., Shnarch, E., and Dagan, I. 2007. Instance-based evaluation of entailment rule acquisition. In Meeting of the Association for Computational Linguistics, Prague, Czech Republic.Google Scholar
Szpektor, I., Tanev, H., Dagan, I., and Coppola, B., 2004. Scaling web based acquisition of entailment patterns. In Empirical Methods in Natural Language Processing, Barcelona, Spain, pp. 41–8.Google Scholar
Tanev, H. 2007. Unsupervised learning of social networks from a multiple-source news corpus. In Proceedings of the Workshop Multi-source Multilingual Information Extraction held at RANLP 2007, Borovets, Bulgaria.Google Scholar
Tanev, H., and Magnini, B. 2006. Weakly supervised approaches for ontology population. In Conference of the European Chapter of the Association for Computational Linguistics.Google Scholar
Weisman, H., Berant, J., Szpektor, I., and Dagan, I. 2012. Learning verb inference rules from linguistically-motivated evidence. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, (EMNLP-CoNLL '12), pp. 194–204. Stroudsburg, PA: Association for Computational Linguistics.Google Scholar
Zhao, S., Wang, H., Liu, T., and Li, S., 2008. Pivot approach for extracting paraphrase patterns from bilingual corpora. In Meeting of the Association for Computational Linguistics, Columbus, Ohio, USA, pp. 780–88.Google Scholar