{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T10:00:46Z","timestamp":1760608846692,"version":"3.41.0"},"reference-count":55,"publisher":"MIT Press","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computational Linguistics"],"published-print":{"date-parts":[[2015,6]]},"abstract":"<jats:p>Entailment rules between predicates are fundamental to many semantic-inference applications. Consequently, learning such rules has been an active field of research in recent years. Methods for learning entailment rules between predicates that take into account dependencies between different rules (e.g., entailment is a transitive relation) have been shown to improve rule quality, but suffer from scalability issues, that is, the number of predicates handled is often quite small. In this article, we present methods for learning transitive graphs that contain tens of thousands of nodes, where nodes represent predicates and edges correspond to entailment rules (termed entailment graphs). Our methods are able to scale to a large number of predicates by exploiting structural properties of entailment graphs such as the fact that they exhibit a \u201ctree-like\u201d property. We apply our methods on two data sets and demonstrate that our methods find high-quality solutions faster than methods proposed in the past, and moreover our methods for the first time scale to large graphs containing 20,000 nodes and more than 100,000 edges.<\/jats:p>","DOI":"10.1162\/coli_a_00220","type":"journal-article","created":{"date-parts":[[2015,4,30]],"date-time":"2015-04-30T12:34:32Z","timestamp":1430397272000},"page":"249-291","source":"Crossref","is-referenced-by-count":3,"title":["Efficient Global Learning of Entailment Graphs"],"prefix":"10.1162","volume":"41","author":[{"given":"Jonathan","family":"Berant","sequence":"first","affiliation":[{"name":"Stanford University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Noga","family":"Alon","sequence":"additional","affiliation":[{"name":"Tel Aviv University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ido","family":"Dagan","sequence":"additional","affiliation":[{"name":"Bar-Ilan University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jacob","family":"Goldberger","sequence":"additional","affiliation":[{"name":"Bar-Ilan University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/0201008"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Angeli, Gabor and Christopher D. Manning. 2014. Naturalli: Natural logic inference for common sense reasoning. In Proceedings of EMNLP, pages 534\u2013545, Doha.","DOI":"10.3115\/v1\/D14-1059"},{"key":"R4","unstructured":"Ben Aharon, Roni, Idan Szpektor, and Ido Dagan. 2010. Generating entailment rules from FrameNet. In Proceedings of ACL, pages 241\u2013246, Uppsala."},{"key":"R5","unstructured":"Berant, Jonathan, Ido Dagan, Meni Adler, and Jacob Goldberger. 2012. Efficient tree-based approximation for entailment graph learning. In Proceedings of ACL, pages 117\u2013125, Jeju Island."},{"key":"R6","unstructured":"Berant, Jonathan, Ido Dagan, and Jacob Goldberger. 2010. Global learning of focused entailment graphs. In Proceedings of ACL, pages 1,220\u20131,229, Uppsala."},{"key":"R7","unstructured":"Berant, Jonathan, Ido Dagan, and Jacob Goldberger. 2011. Global learning of typed entailment rules. In Proceedings of ACL, pages 610\u2013619, Portland, OR."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1162\/COLI_a_00085"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Berant, Jonathan and Percy Liang. 2014. Semantic parsing via paraphrasing. In Proceedings of ACL, pages 1,415\u20131,425, Baltimore, MD.","DOI":"10.3115\/v1\/P14-1133"},{"key":"R10","unstructured":"Bhagat, Rahul, Patrick Pantel, and Eduard Hovy. 2007. LEDIR: An unsupervised algorithm for learning directionality of inference rules. In Proceedings of EMNLP-CoNLL, pages 161\u2013170, Prague."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1162\/jmlr.2003.3.4-5.993"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1162\/coli.2006.32.1.13"},{"key":"R13","unstructured":"Chambers, Nathanael and Dan Jurafsky. 2011. Template-based information extraction without the templates. In Proceedings of ACL, pages 976\u2013986, Portland, OR."},{"key":"R14","unstructured":"Chang, Yin-Wen and Michael Collins. 2011. Exact decoding of phrase-based translation models through Lagrangian relaxation. In Proceedings of EMNLP, pages 26\u201337, Edinburgh."},{"key":"R15","unstructured":"Chklovski, Timothy and Patrick Pantel. 2004. Verb ocean: Mining the web for fine-grained semantic verb relations. In Proceedings of EMNLP, pages 33\u201340, Barcelona."},{"key":"R17","doi-asserted-by":"crossref","unstructured":"Coyne, Bob and Owen Rambow. 2009. Lexpar: A freely available English paraphrase lexicon automatically extracted from FrameNet. In Proceedings of IEEE International Conference on Semantic Computing, pages 53\u201358, Berkeley, CA.","DOI":"10.1109\/ICSC.2009.56"},{"key":"R19","unstructured":"Dinu, Georgiana and Mirella Lapata. 2010. Topic models for meaning similarity in context. In Proceedings of COLING, pages 250\u2013258, Beijing."},{"key":"R20","unstructured":"Do, Quang and Dan Roth. 2010. Constraints based taxonomic relation classification. In Proceedings of EMNLP, pages 1,099\u20131,109, Cambridge, MA."},{"key":"R21","doi-asserted-by":"crossref","unstructured":"Dzeroski, Saso and Ivan Brakto. 1992. Handling noise in inductive logic programming. In Proceedings of the International Workshop on Inductive Logic Programming, pages 48\u201364, Tokyo.","DOI":"10.1007\/978-3-662-04599-2_3"},{"key":"R22","unstructured":"Fader, Anthony, Stephen Soderland, and Oren Etzioni. 2011. Identifying relations for open information extraction. In Proceedings of EMNLP, pages 1,535\u20131,545, Portland, OR."},{"key":"R24","unstructured":"Ganitkevitch, Juri, Benjamin Van Durme, and Chris Callison-Burch. 2013. PPDB: The paraphrase database. In Proceedings of HLT-NAACL, pages 758\u2013764, Atlanta, GA."},{"key":"R26","doi-asserted-by":"crossref","unstructured":"Habash, Nizar and Bonnie Dorr. 2003. A categorial variation database for English. In Proceedings NAACL-HLT, pages 17\u201323, Edmonton.","DOI":"10.21236\/ADA455167"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1080\/00437956.1954.11659520"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"Hearst, Marti. 1992. Automatic acquisition of hyponyms from large text corpora. In Proceedings of COLING, pages 23\u201328, Nantes.","DOI":"10.3115\/992133.992154"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1145\/1102351.1102399"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1137\/0108053"},{"key":"R31","unstructured":"Kipper, Karin, Hoa T. Dang, and Martha Palmer. 2000. Class-based construction of a verb lexicon. In Proceedings of AAAI, pages 691\u2013696, Austin, TX."},{"key":"R32","doi-asserted-by":"crossref","unstructured":"Lin, Dekang. 1998. Automatic retrieval and clustering of similar words. In Proceedings of COLING-ACL, pages 768\u2013774, Montreal.","DOI":"10.3115\/980432.980696"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1017\/S1351324901002765"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"Martins, Andre, Noah Smith, and Eric Xing. 2009. Concise integer linear programming formulations for dependency parsing. In Proceedings of ACL, pages 342\u2013350, Singapore.","DOI":"10.3115\/1687878.1687928"},{"key":"R35","unstructured":"McCreath, Eric and Arun Sharma. 1997. ILP with noise and fixed example size: a Bayesian approach. In Proceedings of IJCAI, pages 1,310\u20131,315, Nagoya."},{"key":"R36","unstructured":"Melamud, Oren, Jonathan Berant, Ido Dagan, Jacob Goldberger, and Idan Szpektor. 2013. A two level model for context sensitive inference rules. In Proceedings of ACL, pages 1,331\u20131,340, Sofia."},{"key":"R37","unstructured":"Meyers, Adam, Ruth Reeves, Catherine Macleod, Rachel Szekeley, Veronika Zielinska, and Brian Young. 2004. The cross-breeding of dictionaries. In Proceedings of LREC, pages 1,095\u20131,098, Lisbon."},{"key":"R38","unstructured":"Nakashole, Ndapandula, Gerhard Weikum, and Fabian M. Suchanek. 2012. Patty: A taxonomy of relational patterns with semantic types. In Proceedings of EMNLP-CoNLL, pages 1,135\u20131,145, Jeju Island."},{"key":"R39","unstructured":"\u00d3S\u00e9aghdha, Diarmuid. 2010. Latent variable models of selectional preference. In Proceedings of ACL, pages 435\u2013444, Uppsala."},{"key":"R40","unstructured":"Pantel, Patrick, Rahul Bhagat, Bonaventura Coppola, Timothy Chklovski, and Eduard H. Hovy. 2007. ISP: Learning inferential selectional preferences. In Proceedings of NAACL-HLT, pages 564\u2013571, Rochester, NY."},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1016\/j.csl.2007.05.001"},{"key":"R42","doi-asserted-by":"crossref","unstructured":"Ravichandran, Deepak and Eduard H. Hovy. 2002. Learning surface text patterns for a question answering system. In Proceedings of ACL, pages 41\u201347, Philadelphia, PA.","DOI":"10.3115\/1073083.1073092"},{"key":"R43","unstructured":"Reichart, Roi and Regina Barzilay. 2012. Multi-event extraction guided by global constraints. In Proceedings of NAACL-HLT, pages 70\u201379, Montreal."},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.3115\/1599081.1599173"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.3115\/1610075.1610095"},{"key":"R46","unstructured":"Ritter, Alan, Mausam, and Oren Etzioni. 2010. A latent Dirichlet allocation method for selectional preferences. In Proceedings of ACL, pages 424\u2013434, Uppsala."},{"key":"R47","unstructured":"Roth, Michael and Anette Frank. 2012. Aligning predicates across monolingual comparable texts using graph-based clustering. In Proceedings of EMNLP-CoNLL, pages 171\u2013182, Jeju Island."},{"key":"R48","unstructured":"Rush, Alexander M., Roi Reichart, Michael Collins, and Amir Globerson. 2012. Improved parsing and POS tagging using inter-sentence consistency constraints. In Proceedings of EMNLP, pages 1434\u20131444, Jeju Island."},{"key":"R49","unstructured":"Schoenmackers, Stefan, Jesse Davis, Oren Etzioni, and Daniel S. Weld. 2010. Learning first-order horn clauses from web text. In Proceedings of EMNLP, pages 1,088\u20131,098, Cambridge, MA."},{"key":"R50","unstructured":"Sekine, Satoshi. 2005. Automatic paraphrase discovery based on context and keywords between NE pairs. In Proceedings of IWP, pages 80\u201387, Jeju Island."},{"key":"R51","doi-asserted-by":"crossref","unstructured":"Shinyama, Yusuke and Satoshi Sekine. 2006. Preemptive information extraction using unrestricted relation discovery. In HLT-NAACL, pages 304\u2013311, New-York, NY.","DOI":"10.3115\/1220835.1220874"},{"key":"R52","doi-asserted-by":"publisher","DOI":"10.3115\/1220175.1220276"},{"key":"R55","doi-asserted-by":"publisher","DOI":"10.3115\/1599081.1599188"},{"key":"R56","doi-asserted-by":"publisher","DOI":"10.3115\/1708141.1708147"},{"key":"R57","unstructured":"Szpektor, Idan, Hristo Tanev, Ido Dagan, and Bonaventura Coppola. 2004. Scaling web-based acquisition of entailment relations. In Proceedings of EMNLP, pages 41\u201348, Barcelona."},{"key":"R58","doi-asserted-by":"crossref","unstructured":"Wang, Mengqiu, Wanxiang Che, and Christopher D. Manning. 2013. Effective bilingual constraints for semi-supervised learning of named entity recognizers. In Proceedings of AAAI, pages 919\u2013925, Bellevue, WA.","DOI":"10.1609\/aaai.v27i1.8617"},{"key":"R59","doi-asserted-by":"crossref","unstructured":"Weeds, Julie and David Weir. 2003. A general framework for distributional similarity. In Proceedings of EMNLP, pages 81\u201388, Sapporo.","DOI":"10.3115\/1119355.1119366"},{"key":"R60","unstructured":"Weisman, Hila, Jonathan Berant, Idan Szpektor, and Ido Dagan. 2012. Learning verb inference rules from linguistically-motivated evidence. In Proceedings of EMNLP, pages 194\u2013204, Jeju Island."},{"key":"R61","doi-asserted-by":"publisher","DOI":"10.1613\/jair.2772"},{"key":"R62","unstructured":"Zeichner, Naomi, Jonathan Berant, and Ido Dagan. 2012. Crowdsourcing inference-rule evaluation. In Proceedings of ACL (short papers), pages 156\u2013160, Jeju Island."}],"container-title":["Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/COLI_a_00220","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,27]],"date-time":"2025-05-27T18:38:49Z","timestamp":1748371129000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/coli\/article\/41\/2\/249-291\/1506"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6]]},"references-count":55,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,6]]}},"alternative-id":["10.1162\/COLI_a_00220"],"URL":"https:\/\/doi.org\/10.1162\/coli_a_00220","relation":{},"ISSN":["0891-2017","1530-9312"],"issn-type":[{"type":"print","value":"0891-2017"},{"type":"electronic","value":"1530-9312"}],"subject":[],"published":{"date-parts":[[2015,6]]}}}