An Inference Model for Semantic Entailment in Natural Language
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 1678-1678.
© 2005 International Joint Conferences on Artificial Intelligence
Abstract
Semantic entailment is the problem of determining if the meaning of a given sentence entails that of another. This is a fundamental problem in natural language understanding that provides a broad framework for studying language variability and has a large number of applications. We present a principled approach to this problem that builds on inducing re-representations of text snippets into a hierarchical knowledge representation along with a sound inferential mechanism that makes use of it to prove semantic entailment.
- [Dagan and Glickman, 2004] I. Dagan and O. Glickman. Probabilistic textual entailment: Generic applied model- ing of language variability. In Learning Methods for Text Understanding and Mining, Grenoble, France, 2004.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
Semantic entailment is the task of determining, for example, that the sentence: "WalMart defended itself in court today against claims that its female employees were kept out of jobs in management because they are women" entails that "WalMart was sued for sexual discrimination".
Determining whether the meaning of a given text snippet entails that of another or whether they have the same meaning is a fundamental problem in natural language understanding that requires the ability to abstract over the inherent syntactic and semantic variability in natural language [Dagan and Glickman, 2004]. This challenge is at the heart of many high level natural language processing tasks including Question Answering, Information Retrieval and Extraction, Machine Translation and others that attempt to reason about and capture the meaning of linguistic expressions.
Research in natural language processing in the last few years has concentrated on developing resources that provide multiple levels of text analysis (both syntactic and semantic), resolve various context sensitive ambiguities, and identify abstractions (from syntactic categories like POS tags to semantic ones like named entities), and the text relational structures.
Indeed, several decades of research in natural language processing and related fields have made clear that the use of deep structural, relational and semantic properties of text is a necessary step towards supporting higher level tasks. However, beyond these resources, in order to support fundamental tasks such as inferring semantic entailment between two texts snippets, there needs to be a unified knowledge representation of the text that (1) provides a hierarchical encoding of the structural, relational and semantic properties of the given text, (2) is integrated with learning mechanisms that can be used to induce such information from raw text, and (3) is equipped with an inferential mechanism that can be used to support inferences with respect to such representations.
Just resorting to general purpose knowledge representations - FOL based representations, probabilistic representations or hybrids - along with their corresponding general purpose inference algorithms is not sufficient.
We have developed an integrated approach that provides solutions to all challenges mentioned above. We formally define the problem of semantic entailment for Natural Language and present a computational approach to solving it, that consists of a hierarchical knowledge representation language into which we induce appropriate representations of the given text and required background knowledge, along with a sound inferential mechanism that makes use of the induced representation to determine entailment. Our inference approach is formalized as an optimization algorithm that we model as an integer linear programming problem. The preliminary evaluation of our approach is very encouraging and illustrates the significance of some of the key contributions of this approach.
1.1 General Description of Our Approach
Given two text snippets S (source) and T (target) (typically, but not necessarily, S consists of a short paragraph and T, a sentence) we want to determine if S|=T, which we read as "S entails T" and, informally, understand to mean that most people would agree that the meaning of S implies that of T. Somewhat more formally, we say that S entails T when some representation of T can be "matched" (modulo some meaning-preserving transformations to be defined below) with some (or part of a) representation of S, at some level of granularity and abstraction.
The approach consists of the following components:
KR: A Description Logic based hierarchical knowledge representation, EFDL, into which we re-represent the surface level text representations, augmented with induced syntactic and semantic parses and word and phrase level abstractions.
KB: A knowledge base consisting of syntactic and semantic rewrite rules, written in EFDL.
Subsumption: An extended subsumption algorithm which determines subsumption between EFDL expressions (representing text snippets or rewrite rules). "Extended" here means that the basic unification operator is extended to support several word level and phrase level abstractions.
First a set of machine learning based resources are used to induce the representation for S and T. The entailment algorithm then proceeds in two phases: (1) it incrementally generates re-representations of the original representation of the source text S and (2) it makes use of an (extended) subsumption algorithm to check whether any of the alternative representations of the source entails the representation of the target T. The subsumption algorithm mentioned above is used in both phases in slightly different ways.

Figure 1 provides a graphical example of the representation of two text snippets, along with an sketch of the extended subsumption approach to decide the entailment.
Along with the formal definition developed here of semantic entailment, our knowledge representation and algorithmic approach provide a novel solution that addresses some of the key issues the natural language research community needs to address in order to move forward towards higher level tasks of this sort. Namely, we provide ways to represent knowledge, either external or induced, at multiple levels of abstractions and granularity, and reason with it at the appropriate level.
2 Experimental Evaluation
Data. We tested our approach on the PASCAL challenge data set (http://www.pascal-network.org/Challenges/RTE/). As the system was designed to test for semantic entailment, the PASCAL data set is ideally suited, being composed of 276 source - target sentence pairs, indicating whether the source logically entails the target. The set is split into various tasks: CD (Comparable Documents), IE (Information Extraction), MT (Machine Translation), PP (Prepositional Paraphrases), QA (Question Answering), and RC (Reading Comprehension).
In Table 1 we show the system's performance. The baseline is a lexical-level matching based on bag-of-words representation with lemmatization and normalization (LLM).
| Perform. | Overall [%] | Task [%] | ||||||
|---|---|---|---|---|---|---|---|---|
| CD | IE | IR | MT | PP | QA | RC | ||
| System | 64.8 | 74.0 | 35.0 | 62.0 | 87.5 | 63.8 | 84.0 | 49.0 |
| LLM | 54.7 | 64.0 | 50.0 | 50.0 | 75.0 | 55.2 | 50.0 | 52.9 |
Acknowledgement
We thank Dash Optimization for the free academic use of their Xpress-MP software. This work was supported by the Advanced Research and Development Activity (ARDA)'s Advanced Question Answering for Intelligence (AQUAINT) Program, NSF grant ITR-IIS-0085980, and ONR's TRECC and NCASSR programs.
@inproceedings{ijcai2005p350,
title = {An Inference Model for Semantic Entailment in Natural Language},
author = {Braz, Rodrigo de Salvo and Girju, Roxana and Punyakanok, Vasin and Roth, Dan and Sammons, Mark},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Leslie Pack Kaelbling and Alessandro Saffiotti},
pages = {1678--1678},
year = {2005},
url = {https://ijcai.org/proceedings/2005/350},
}
TY - CPAPER TI - An Inference Model for Semantic Entailment in Natural Language AU - Braz, Rodrigo de Salvo AU - Girju, Roxana AU - Punyakanok, Vasin AU - Roth, Dan AU - Sammons, Mark T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 1678 EP - 1678 UR - https://ijcai.org/proceedings/2005/350 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: