Elamur Research⌕
☰
home / papers / 2011 / Global Learning of Typed Entailment Rules

Global Learning of Typed Entailment Rules

Paper · 2011 · Jonathan Berant, Ido Dagan and Jacob Goldberger

Summary

The paper tackles automatic acquisition of predicate entailment rules (e.g., "annex" implies "control") as a knowledge resource for textual inference. Earlier methods mostly scored each rule in isolation and ignored the fact that entailment is transitive. The authors use the typed-predicate data of Schoenmackers et al. (2010): 10,672 predicates whose arguments carry one of 156 types. Predicates that share a pair of argument types form a typed entailment graph. Learning has two stages. First, a local classifier, trained with distant supervision from WordNet, scores each candidate edge from distributional similarity features. Second, an ILP chooses the edge set with the best total score under transitivity and background-knowledge constraints. Exact ILP does not scale well, so the graphs are first split into independent components and then solved with incremental ILP, which still yields optimal solutions. Against Sherlock, DIRT, BInc, SR and the classifier alone, the global method raises F1 by 27% and AUC by 29%. It also produces a released resource of about 30,000 rules with roughly twice Sherlock's recall at similar precision.

Key points

  • Data source: the Sherlock/TextRunner data from Schoenmackers et al.
    • 29M (argument, type) pairs were extracted with Hearst patterns.
    • 1.1M arguments were mapped to 156 types.
    • This produced 10,672 typed predicates, which form 2,303 entailment graphs.
  • Two kinds of graphs:
    • Two-types graphs have different argument types, so argument mapping is unambiguous.
    • Single-type graphs (e.g., team, team) must also record whether each edge maps arguments directly or in reverse.
  • Gold standard: 10 graphs (7–118 nodes) were fully annotated by hand, giving 3,427 edges and 35,585 non-edges (about 9% density).
  • Main results:
    • ILP_scale reaches R/P/F1 of 43.4/42.2/42.8 with AUC 0.22.
    • The local classifier alone (clsf_k) gets F1 33.8.
    • Sherlock_k gets 20.6/43.3/27.9.
  • Effect of the scaling techniques:
    • Unsolvable graphs drop from 9 to 3 in the best setting.
    • This adds about 3,500 rules, a 13% relative recall gain, with comparable precision on sampled rules.
    • The released resource contains 29,732 rules.

Interesting ideas

  • I1. Typing predicates to reduce ambiguity. Constraining argument types (e.g., drug or country) largely prevents the sense mix-ups that break transitivity. This makes global constraints safe to apply. Any graph over ambiguous lexical items could use the same move.
  • I2. Splitting a sparse problem before exact optimization. Breaking the graph into independent components before calling the solver shrinks the largest subproblem a lot (around 75% for the sparsest setting) without losing optimality. This trick suits other sparse transitive relations the authors list, such as taxonomy induction or coreference.
  • I3. Incremental ILP for transitivity constraints. The number of transitivity constraints grows cubically. Adding only the constraints that the current solution violates keeps the problem tractable. This is a general recipe for structured prediction with many constraints.
  • I4. Distant supervision from WordNet. Synonyms and hypernyms serve as positive training pairs, while co-hyponyms, hyponyms and random pairs serve as negatives. This lets a classifier that combines several similarity measures be trained without any manual labels. It is useful for lower-resource languages wherever a WordNet-like resource exists.
  • I5. An edge prior as a density knob. A single prior parameter trades precision against recall across the whole graph. This allows precision-recall curves and lets one choose high-precision or high-recall releases from the same model.

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

🎓Bar-Ilan UniversityRamat Gan · Israel118 works · 21,077 citations🎓Tel Aviv UniversityTel Aviv · Israel67 works · 10,006 citations

📚 Shelves 4 Computer Science · 9,086 works Artificial Intelligence · 8,889 works Arts and Humanities · 9,296 works Language and Linguistics · 9,206 works

Cite

Cite as Jonathan Berant, Ido Dagan and Jacob Goldberger. 2011. Global Learning of Typed Entailment Rules. Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies.

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

@inproceedings{berant2011global,
  title = {{Global Learning of Typed Entailment Rules}},
  author = {Jonathan Berant, Ido Dagan and Jacob Goldberger},
  booktitle = {Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies},
  year = {2011},
  url = {https://aclanthology.org/P11-1062/}
}

References

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

  1. J. Fillmore Baker, C. F. and J. B. Lowe. 1998. The Berkeley framenet project. In Proc. of COLING-ACL. our card
  2. Michele Banko, Michael Cafarella, Stephen Soderland, Matt Broadhead, and Oren Etzioni. 2007. Open information extraction from the web. In Proceedings of IJCAI. our card
  3. Roni Ben Aharon, Idan Szpektor, and Ido Dagan. 2010. Generating entailment rules from framenet. In Proceedings of ACL. our card
  4. Jonathan Berant, Ido Dagan, and Jacob Goldberger. 2010. Global learning of focused entailment graphs. In Proceedings of ACL. find
  5. Rahul Bhagat, Patrick Pantel, and Eduard Hovy. 2007. LEDIR: An unsupervised algorithm for learning directionality of inference rules. In Proceedings of EMNLP-CoNLL. find
  6. James Clarke and Mirella Lapata. 2008. Global inference for sentence compression: An integer linear programming approach. Journal of Artificial Intelligence Research, 31:273–381. find
  7. Ido Dagan, Bill Dolan, Bernardo Magnini, and Dan Roth. 2009. Recognizing textual entailment: Rational, evaluation and approaches. Natural Language Engineering, 15(4):1–17. find
  8. Quang Do and Dan Roth. 2010. Constraints based taxonomic relation classification. In Proceedings of EMNLP. find
  9. Saso Dzeroski and Ivan Brakto. 1992. Handling noise in inductive logic programming. In Proceedings of the International Workshop on Inductive Logic Programming. find
  10. Christiane Fellbaum, editor. 1998. WordNet: An Electronic Lexical Database (Language, Speech, and Communication). The MIT Press. find
  11. Jenny Rose Finkel and Christopher D. Manning. 2008. Enforcing transitivity in coreference resolution. In Proceedings of ACL-08: HLT, Short Papers. our card
  12. Marti Hearst. 1992. Automatic acquisition of hyponyms from large text corpora. In Proceedings of COLING. find
  13. Thorsten Joachims. 2005. A support vector method for multivariate performance measures. In Proceedings of ICML. find
  14. Karin Kipper-Schuler, Hoa Trand Dang, and Martha Palmer. 2000. Class-based construction of verb lexicon. In Proceedings of AAAI/IAAI. find
  15. Dekang Lin and Patrick Pantel. 2001. Discovery of inference rules for question answering. Natural Language Engineering, 7(4):343–360. find
  16. Xiao Ling and Daniel S. Weld. 2010. Temporal information extraction. In Proceedings of AAAI. find
  17. Catherine Macleod, Ralph Grishman, Adam Meyers, Leslie Barrett, and Ruth Reeves. 1998. NOMLEX: A lexicon of nominalizations. In Proceedings of COL-ING. find
  18. Andre Martins, Noah Smith, and Eric Xing. 2009. Concise integer linear programming formulations for dependency parsing. In Proceedings of ACL. find
  19. Eric McCreath and Arun Sharma. 1997. ILP with noise and fixed example size: a bayesian approach. In Proceedings of the Fifteenth international joint conference on artificial intelligence - Volume 2. find
  20. Vladimir Nikulin. 2008. Classification of imbalanced data with random sets and mean-variance filtering. IJDWM, 4(2):63–78. find
  21. Hoifung Poon and Pedro Domingos. 2010. Unsupervised ontology induction from text. In Proceedings of ACL. find
  22. Sebastian Riedel and James Clarke. 2006. Incremental integer linear programming for non-projective dependency parsing. In Proceedings of EMNLP. find
  23. Stefan Schoenmackers, Oren Etzioni Jesse Davis, and Daniel S. Weld. 2010. Learning first-order horn clauses from web text. In Proceedings of EMNLP. find
  24. Satoshi Sekine. 2005. Automatic paraphrase discovery based on context and keywords between ne pairs. In Proceedings of IWP. find
  25. Rion Snow, Daniel Jurafsky, and Andrew Y. Ng. 2006. Semantic taxonomy induction from heterogenous evidence. In Proceedings of ACL. find
  26. Idan Szpektor and Ido Dagan. 2008. Learning entailment rules for unary templates. In Proceedings of COLING. find
  27. Idan Szpektor and Ido Dagan. 2009. Augmenting wordnet-based inference with argument mapping. In Proceedings of TextInfer. find
  28. Idan Szpektor, Hristo Tanev, Ido Dagan, and Bonaventura Coppola. 2004. Scaling web-based acquisition of entailment relations. In Proceedings of EMNLP. our card
  29. Jason Van Hulse, Taghi Khoshgoftaar, and Amri Napolitano. 2007. Experimental perspectives on learning from imbalanced data. In Proceedings of ICML. find
  30. Julie Weeds and David Weir. 2003. A general framework for distributional similarity. In Proceedings of EMNLP. our card
  31. Mihalis Yannakakis. 1978. Node-and edge-deletion NP-complete problems. In STOC ’78: Proceedings of the tenth annual ACM symposium on Theory of computing, pages 253–264, New York, NY, USA. ACM. find
  32. Alexander Yates and Oren Etzioni. 2009. Unsupervised methods for determining object and relation synonyms on the web. Journal of Artificial Intelligence Research, 34:255–296. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/berant-2011-global-learning-typed-entailment-rules/