2.1 RTE as a general paradigm for semantic processing

As described above, textual entailment aims at capturing human intuitions about valid common sense reasoning patterns by defining a binary relation between two passages of text T (text) and H (hypothesis) that holds if readers of T ‘would typically infer that H is most likely true’. Following this intuition, the role of textual entailment in applications is generally to deal with the variability of language, that is, the fact that the same state of affairs can be described in a large number of different ways. More specifically, almost all NLP tasks deal with pairs of texts (e.g. queries and answers, or answer candidates and gold answers) whose semantic relationship must be determined in the face of variability. Compare Example (1) above, where T and H₁ are related while T and H₂ are not. At the same time, T and H₁ have a relatively small lexical overlap, a phenomenon named the ‘lexical chasm’ (Berger et al. Reference Berger, Caruana, Cohn, Freitag and Mittal2000). This indicates that the exclusive use of shallow methods can be insufficient, and motivates the use of the more general approach of textual entailment.

Many applications broadly related to search, such as question answering, can employ textual entailment as a verification step. For efficiency reasons, such search tasks generally adopt a retrieval phase that gathers a small set of plausible candidates from large data sets using shallow methods. Textual entailment can then be used to perform a deeper analysis that verifies or rejects these candidates. In question answering, answer candidates are tested for whether they entail the search query reformulated as a statement (Harabagiu and Hickl Reference Harabagiu and Hickl2006; Peñas et al. Reference Peñas, Rodrigo, Sama and Verdejo2008). In information extraction, instance candidates can be compared against templates (Romano et al. Reference Romano, Kouylekov, Szpektor, Dagan and Lavelli2006). A second group of applications use textual entailment as a scoring method that quantifies to what extent one text implies another. Examples include Intelligent Tutoring (Nielsen, Ward and Martin Reference Nielsen, Ward and Martin2009), where good student answers should entail gold standard answers, and Machine Translation (Padó et al. Reference Padó, Cer, Galley, Jurafsky and Manning2009), where system output and manual translation should entail each other. Finally, textual entailment can be used for (hierarchically) structuring sets of texts, for example in multi-document summarization (Harabagiu, Hickl and Lacatusu Reference Harabagiu, Hickl and Lacatusu2007) and information visualization (Berant, Dagan and Goldberger Reference Berant, Dagan and Goldberger2012).

2.2 The state of the art in RTE

A wide variety of NLP methods have been applied to RTE.Footnote ³ Almost all systems first preprocess T and H (e.g. by lemmatization, POS tagging, or parsing) to abstract away from surface variation. The subsequent processing strategies fall into three broad classes: alignment-based, transformation-based, and formal reasoning-based RTE. Note that many implemented systems are hybrid, combining elements of several strategies. Alignment-based RTE constructs an explicit or implicit alignment between the linguistic entities of T and H (e.g. words, phrases, dependency nodes, or semantic structure). Entailment is decided on the basis of alignment quality, generally by assessing the validity of each ‘local’ inference in an aligned T-H pair of entities. Often different aspects of quality are combined to arrive at a final decision using supervised learning methods (Monz and de Rijke Reference Monz and de Rijke2001; MacCartney et al. Reference MacCartney, Grenager, de Marneffe, Cer and Manning2006; Zanzotto, Pennacchiotti and Moschitti Reference Zanzotto, Pennacchiotti and Moschitti2009). Transformation-based RTE aims at validating the entailment relation T⊧H by finding a ‘proof’, i.e. a sequence (T, T ₁, . . ., T_n), such that T_n = H (Bar-Haim, Szpektor and Glickman Reference Bar-Haim, Szpektor and Glickman2005; Harmeling Reference Harmeling2009). The individual transformation steps T_i⊧T _{i + 1} are generally motivated by lexical or lexico-syntactic inference rules such as ‘Y was purchased by X’ ⊧ ‘X paid for Y’. Formal reasoning-based RTE pursues a more traditional approach to inference by constructing meaning representations for T and H in a formal language with formal reasoning procedures, such as predicate or description logics (Tatu and Moldovan Reference Tatu and Moldovan2005; Bos and Markert Reference Bos and Markert2006; Bobrow et al. Reference Bobrow, Condoravdi, Crouch, Paiva, Karttunen, King, Nairn, Price and Zaenen2007). The second distinction can be drawn between knowledge-lean algorithms (Harmeling Reference Harmeling2009) and algorithms that rely on linguistic and world knowledge to decide the validity of inferences. The latter class accounts for the vast majority of approaches. The use of linguistic knowledge (such as lexical inference rules) actually cuts across the three broad classes outlined above: In alignment-based RTE, such rules can be used to score matches between entities; in transformation-based RTE, these can be used as proof steps; and in formal reasoning (logics)-based RTE, these can be formulated as background axioms. Such knowledge is generally drawn from knowledge resources, such as WordNet (Fellbaum Reference Fellbaum1998) or DIRT (Lin and Pantel Reference Lin and Pantel2002), but knowledge gaps remain a key obstacle (Mirkin, Dagan and Shnarch Reference Mirkin, Dagan and Shnarch2009).

2.3 Problems of the state of the art

As we have sketched above, no canonical algorithm, nor even a canonical strategy, has emerged for textual entailment. This situation mirrors the state of semantics as complex area of research that still lacks unified processing approaches that are available for other fields like syntactic analysis or machine translation.

At the same time, the development of a system for recognizing textual entailment represents a substantial development effort. Only in the last two or three years, first publicly available systems for RTE, such as BIUTEE (Stern and Dagan Reference Stern and Dagan2011) and EDITS (Negri et al. Reference Negri, Kouylekov, Magnini, Mehdad and Cabrio2009), have appeared. These systems are however still implementations of particular RTE strategies and not generic platforms. In contrast, in the field of machine translation, researchers can download MOSES (Koehn et al. Reference Koehn, Hoang, Birch, Callison-Burch, Federico, Bertoldi, Cowan, Shen, Moran, Zens, Dyer, Bojar, Constantin and Herbst2007), an open-source toolkit for machine translation, and extend a ready-to-use competitive platform with their own ideas.

The absence of a sufficiently generic system of this type for textual entailment has a number of problematic consequences, both for researchers interested in textual entailment itself and those who want to apply RTE technology to applications.

1. (1) Reusability of algorithms and resources. Researchers who plan to work on textual entailment have a choice: They can either develop a new system from scratch, which involves substantial effort, or use available systems like BIUTEE or EDITS as a basis for further development. If they choose the first option, they need to develop the complete system. Concerning the second option, existing systems are not generally designed to be modular or reusable since there is no standard for packaging RTE methods. The same holds for resources: It is well-established that for most approaches, knowledge resources play a central role in the recognition of textual entailment. Given the absence of a widely used standard for such resources, new systems typically develop their own resources from scratch since they cannot reuse existing resources of other systems. This raises a high bar for new entrants in the field of textual entailment.

2. (2) Generality. If researchers choose the second avenue outlined above, i.e. to use the existing RTE systems, they encounter another problem. Since these systems were not developed as generic platforms, users may be limited by the design decisions taken by its developers, e.g. the overall strategy chosen for RTE (cf. Section 2.2). Only research along the lines of the existing systems can be performed without investing a major development effort. Given the absence of a unified theory of textual inference compared with, for instance, SMT, this stifles the development of novel approaches in the area.

3. (3) Systematic evaluation. Progress in processing-oriented research areas like textual entailment hinges on advances in the understanding of the impact of various factors on output quality. Ideally, experiments would vary factors systematically while keeping the overall system setup constant. However, due to the specialized nature of the publicly available RTE systems mentioned above, comparisons across systems have turned out to be extremely difficult. Some of the RTE workshops (e.g. RTE 2 and 4) have attempted to analyze the system results in terms of knowledge resources utilized, but were not able to establish firm patterns. Thus, the present situation lacks a clear understanding of the systematic influence of design decisions in RTE systems.

4. (4) Multilinguality. To our knowledge, EDITS is the only publicly available system which has been developed with multilinguality in mind; it has been applied to both English and Italian. Applying other systems to new languages involves, in addition to replacing the relevant preprocessing tools, a thorough inspection of the code for details that may be language-specific. This problem seriously impacts the uptake of entailment technology for more languages: after ten years, most textual entailment technology has been applied only to English and Italian, with pilot studies for Spanish (Castillo Reference Castillo2010) and German (Wang and Neumann Reference Wang and Neumann2008b). More recently, there has been interest in cross-lingual textual entailment (2, 010 Reference Mehdad, Negri and Federico2011; Negri et al. Reference Negri, Bentivogli, Mehdad, Giampiccolo and Marchetti2011). Tasks on cross-lingual textual entailment for content synchronization have been carried out at SemEval in 2012Footnote ⁴(Negri et al. Reference Negri, Marchetti, Mehdad, Bentivogli and Giampiccolo2012) and 2013.Footnote ⁵

5. (5) Integration in applications. Integration of RTE technology into NLP applications faces the challenge that existing applications typically have a preexisting processing pipeline that they build on. Integrating an existing RTE system with its own pipeline into the application typically entails that the data are preprocessed again within the RTE system, which is inelegant and may even be impossible for time-critical applications. Consequently, although many NLP tasks have been phrased in terms of entailment (cf. Section 2.1), usage of textual entailment in actual applications is still rare.

4.1 Unstructured information management architecture (UIMA)

We assessed several possible choices for data representation in the LAP. The column-based CoNLL 2009 file format (Hajič et al. Reference Hajič, Ciaramita, Johansson, Kawahara, Martì, Màrquez, Meyers, Nivre, Padó, Štepánek, Stranák, Surdeanu, Xue and Zhang2009) offers a lightweight, general representation, but lacks in extensibility: new layers must be defined ad hoc, variable annotation (such as semantic roles) leads to variable numbers of columns, and there is no declarative support for metadata. More expressive representations, such as LAF and GrAF (Ide and Suderman Reference Ide and Suderman2007), overcome these problems, but are only in the process of being standardized.

We decided to adopt UIMA (Ferrucci and Lally Reference Ferrucci and Lally2004), a general architecture for analysis components that is supported by the Apache Foundation and has healthy communities in both academic and commercial domain. UIMA provides a unified way of constructing linguistic pipelines from analysis components, which are wrapped into the so-called UIMA components.

We concentrate on UIMA's support for storing components’ analysis results in the so-called Common Analysis Structures (CAS).Footnote ⁷ A CAS starts out containing only plain text. As it passes through analysis components, additional annotation layers are stacked onto the text. The input and output of every component are standardized by a type system. CAS also supports the storage of metadata such as language flags. Components can check for the presence of analysis layers to detect incompatibilities (e.g. a parsing component can check that its input is POS-tagged).

The role of the CAS type system in defining the admissible annotations can be understood in analogy to POS tag inventories, but is more powerful in that it defines not only the inventory but also the structures of annotation. Fortunately, there are existing CAS type systems for the NLP domain. We adopted the DKPro type system (Gurevych et al. Reference Gurevych, Mühlhäuser, Müller, Steimle, Weimer and Zesch2007), which was designed with language independence in mind. It provides types for morphological information, POS tags, dependency structure, named entities, coreference, and semantic roles.

We have made two major customizations to use UIMA CAS for textual entailment: one extension is the definition of new type systems for entailment task, and the other one is the representation of entailment problems as single CASes.

First, we needed to represent entailment problems (in the easiest case, a text-hypothesis pair) in terms of UIMA CASes. In general text analysis use cases, one UIMA CAS corresponds to one document; this suggests representing both text and hypothesis as separate CASes. However, we decided to store complete entailment problems as individual CASes. This approach has two major advantages: (i) It enables us to obtain a uniform representation for ‘simple’ entailment problems (one text and one hypothesis) and ‘complex’ entailment problems (one text and multiple hypotheses or vice versa, as in the ‘RTE search’ task (Bentivogli et al. Reference Bentivogli, Magnini, Dagan, Trang Dang and Giampiccolo2009)). (ii) Joint storage in the same CAS enables us to store cross-annotations between texts and hypotheses, notably alignments (cf. Section 2.2).

Second, we needed to extend the DKPro type system with the types necessary to define textual entailment-specific annotation. This involved types for marking stretches of text as texts and hypotheses, respectively, as well as storing correspondence information between texts and hypotheses, pair IDs, gold labels, and some metadata such as language. We also added types for linguistic annotation that are not exclusively entailment-specific, but have found use in RTE and were not covered yet by DKPro. This included annotation for polarity, the reference of temporal expressions, and word and phrase alignments between text and hypothesis.

Figure 2 shows a pictorial example of the CAS data structure for the pair (T, H₁) from the example in Section 1. It contains the two text fragments (‘subject of analysis’ in UIMA terms) and their annotations (here POS and dependencies), as well as global data such as metadata proper (e.g. language) and properties of the entailment pair (e.g. the gold-standard answer). The example shows one T-H pair, but an entailment problem (one CAS) can have multiple pairs with multiple texts or hypotheses.

Fig. 2.

CAS representation of a text-hypothesis pair.

LAP versus EC. We only adopted UIMA for LAP, and not for EC, whose components (EDAs, algorithms, and knowledge components) are ‘normal’ Java components (cf. Figure 1). The reason is that UIMA's strength is defining document-based annotation pipelines: starting out from a ‘raw’ document, components are called sequentially and each one adds its output as a new annotation layer to the document. In contrast, UIMA cannot deal well with situations where there is no underlying document that is enriched, or where there is a more flexible flow of information. This is the case in the EC.

As an example, consider the interaction between an EDA and a lexical knowledge component such as WordNet (cf. Section 6.3 for details). In the typical use case, the input to the lexical knowledge component is a single word (for example, dog), and the output is the set of words lexically entailed by the input word (mammal, animal, object, . . .). The first problem is that each component in a UIMA pipeline must be called a fixed number of times. This order and number of times are defined at the pipeline's building time, which is not appropriate for dynamic situations such as lexical lookup. The second problem is the UIMA CAS format itself. Being optimized for storing documents, it does not provide fast (ideally constant-time) queries and is therefore ill-suited for knowledge storage and access.

Consequently, we have decided to define the EC side of the architecture with Java interfaces and Java data types. These types are described in the following sections.

4.2 Interoperability: achievements and limits

Our adoption of a UIMA-based LAP architecture achieves our goal of decoupling the LAP from the EC on a technical level: the UIMA CASes and their type system serve as the only way to exchange information (cf. Figure 1). However, this situation still leaves room for two broad classes of incompatibility.

First, ‘hard’ incompatibilities arise when dependencies are violated, for example when analysis components for different languages are combined, or when the EC requires some annotation that was not produced by the LAP. We catch such cases by requiring the EC to check for the presence and consistency of all required layers.

The second, more difficult, class consists of ‘soft’ incompatibilities below the level of standardization provided by the type system. These can be broadly characterized as differences in ‘annotation style’. For example, consider a constituent parser that produces flat NP analyses. If it is replaced by another parser which assumes hierarchical analysis of NPs, the difference cannot be detected at the level of the UIMA type system. However, it can clearly degrade the functionality of downstream components, in particular for linguistically informed components which identify particular linguistic structures, e.g. to apply inference rules.

One solution to this problem would be to prescribe one canonical ‘annotation style’ for each analysis level, for example, Stanford dependencies for parsing. This idea however runs counter to our goal of an open platform. Without automatic methods to detect soft incompatibility, our solution is a combination of documentation and policy. On the policy level, we strongly recommend that EDA developers keep the core EDAs as generic as possible, placing annotation's style-specific parts into knowledge components (cf. Section 5). On the documentation level, all EDAs and linguistic knowledge components are to be annotated with information about the analysis tools used for their creation. The price we pay for the openness is that the change of a major LAP component may entail adapting linguistically informed EC components and resources. Nevertheless, we believe that a pluralistic approach is preferable, and support it with a clear methodology and best practice guidelines.

5.1 Decomposition: EDAs versus components

Existing RTE systems can be trivially wrapped as a whole into an EDA. However, our goal is to support the decomposition of existing systems into single EDAs plus a range of subordinate components in order to encourage developers to focus on the reusability of their RTE algorithms and resources. Since there is no unique correct way of decomposition, what is necessary are guidelines that describe as precisely as possible how to split up a given system into EDAs and components.

Our guiding principle is that EDAs should be as minimal and ideally as language-independent as possible, while the following three criteria identify functionalities that should be put into components: (a) functionality that is strongly dependent on particular linguistic structures (cf. Section 4.2); (b) substantial amounts of declarative knowledge (i.e. resources); (c) functionality that is useful for more than one class of EDAs. Following this idea, we have developed a set of four component interfaces (i.e. types) which cover the main classes of reusable functionalities that we identified, discussed in detail in Section 6. Developers are encouraged to use those components. They can add their own types if required, but since this involves additional overhead, we hope that this setup encourages a degree of reusability.

5.2 Result types

At first glance, the result of the EDA should obviously be a binary variable (Entailment versus Non-Entailment), as adopted by the first RTE workshops. However, the task was subsequently extended in various ways. (de Marneffe, Rafferty and Manning Reference de Marneffe, Rafferty and Manning2008) consider a three-way decision that includes Contradiction. Androutsopoulos and Malakasiotis's (Reference Androutsopoulos and Malakasiotis2010) survey argues that techniques for Paraphrase acquisition share many techniques with RTE. (MacCartney and Manning Reference MacCartney and Manning2007) and (Wang Reference Wang2011) also consider more comprehensive sets of semantic relations between texts.

In order to keep the architecture general, but focused on textual entailment, we decided to model the decision type as follows. We define six labels in a hierarchically structured Enum as shown in Figure 3. EDAs can use the upper level for a more coarse-grained task, or can selectively include the lower level for finer-grained distinctions.Footnote ⁸Abstain gives EDAs an option to signal missing coverage. Instead of simply collapsing this type into Unknown, we would like to separate the cases which are truly underspecified from the cases for which the system (or single EDA) cannot make a decision. As also expressed by (Bergmair Reference Bergmair2009), this can be helpful when considering ensembles of RTE systems. If necessary, this type can be extended at the cost of additional effort by the developer.

Fig. 3.

EDA result type hierarchy.

5.3 Efficiency and scalability

The use of textual entailment in practical NLP applications requires very fast or even real-time processing, which is non-trivial for many algorithms. This is especially true for tasks involving large amount of text, like the search task or the summarization task of RTE-6 and 7. We deal with efficiency in two ways. One is the clear separation and serialization of preprocessing, and the other is the support for parallelization.

The separation between LAP and EC helps to reduce the amount of duplicated preprocessing (linguistic annotation). With the CAS serialization format, it is possible to analyze the input data just once while running multiple ECs on the data.

Parallelization can also provide a way to speed up processing. The platform supports two different levels of parallelization. The first level is parallel processing of multiple H/T pairs, which can be assumed to be independent. This capability is integrated via an optional method in the EDA interface that accepts a set of H/T pairs and is implemented by EDAs that are able to concurrently process several H/T pairs.

The second level is parallelization of computations for a single H/T pair within the EDA. While calls to several components can be trivially parallelized with multiple threads, multiple calls to the same component present a bottleneck. This situation arises frequently in the case of knowledge components, e.g. when lexical similarities for a large number of potential word alignments are queried. We therefore require all components to declare whether they are thread-safe or not. If they are, the EDA can call them from different threads similar to the calling of different components; if they are not, the EDA can still choose to initialize several instances of the component, memory permitting.

6.1 Scoring components

Scoring components accept an H/T pair as input, and return a vector of scores for that H/T pair. Technically, the central method of this type gets a Java object mirroring a CAS object (a JCas object) representing the complete H/T pair and returns a vector filled with arbitrary numeric values. Note that a JCas object holds prior annotations, and the scoring component is based on those annotations (for example, tree edit distance scoring relies on parse tree annotations etc). We use JCas as the exchange type to ensure that the scoring components are independent of the internal data structures used in the EDA under the assumption that the LAP-produced CAS objects are available in the EDA.

The semantics of the components’ return values depend on the scoring component. In fact, the interface can be used to extract arbitrary features over the H/T pair, such as modality and polarity match. This functionality follows the criticism by MacCartney et al. (Reference MacCartney, Grenager, de Marneffe, Cer and Manning2006), who have argued that distance on its own is not a good correlate of entailment probability. Components that return such feature vectors can be combined with very simple classifier-based EDAs to build straightforward RTE systems.

Another use of this component is for distance calculation, where the intuition is that the probability of an entailment relation between T and H is related to the distance between them. The platform standardizes the distance calculation modules with the distance component, which is an extended version of the scoring component that can accommodate normalized and unnormalized distance/similarity values along with the scoring vector.

6.2 Annotation components

The second type of component consists of components that add annotation to the text, the hypothesis, or the text/hypothesis pair. Again, the input type for this component is a JCas object to give the component access to the complete T/H pair. However, this time the component also returns the JCas object, extended with additional information.

An example of this type is a component that produces word or phrase alignments between the text and hypothesis. Such alignments form an important part of many RTE algorithms and can, or even should, be separated cleanly from the actual entailment decision (MacCartney et al. Reference MacCartney, Grenager, de Marneffe, Cer and Manning2006). Other examples are annotations of modality or polarity information (Nairn, Condoravdi and Karttunen Reference Nairn, Condoravdi and Karttunen2006).

Note that this definition introduces a certain overlap between the LAP and annotation components, since both can produce annotations. We feel that this situation creates a useful degree of choice: In any evaluation experiment that assesses the impact of some preprocessing step on RTE, there will be a ‘static’ annotation that remains constant during the experiment. This annotation is best produced and serialized in the LAP. In contrast, the ‘dynamic’ annotation that changes with the experimental manipulation can be produced on demand through an annotation component. Also note that cross-annotations like alignment annotations are not natural for LAP annotators, where an annotator is supposed to enrich one subject of analysis.

6.3 Lexical knowledge components

Lexical knowledge describes semantic relationships between words. This type of knowledge is useful for alignment-based approaches to RTE (to distinguish likely from unlikely alignments) as well as for transformation-based approaches (where it provides entailment rules at the lexical level).

We assume that this knowledge can be expressed as directed rules built from two (word, POS) pairs, a Left-Hand Side (LHS) and a Right-Hand Side (RHS). Two rules instances relevant for the example from Section 1 are (Siberia, N) → (Russia, N) and (shooting_star, N) → (meteorite, N). Its interface consists of three queries, which are as follows: (a) list all RHS for a given LHS; (b) list all LHS for a given RHS; and (c) check the existence of an entailment relation when both LHS and RHS are given. The meaning of a rule is usually that the LHS entails the RHS (LHS ⊧ RHS).

This interface can wrap all major lexical knowledge sources currently used in RTE. This includes manually constructed ontologies (e.g. WordNet and VerbOcean (Chklovski and Pantel Reference Chklovski and Pantel2004)), encyclopedic resources (e.g. Wikipedia) as well as automatically constructed thesauri and distributional similarity resources.Footnote ¹⁰ The interface does not impose any constraints on the storage of lexical knowledge. That is, for knowledge sources for which Application Programmer's Interfaces (APIs) are already available (such as WordNet), integration into our platform involves only translation of our interface methods into queries of that API.

The signature of the component is defined by a set of Java interfaces. All lexical knowledge components support the basic interface that provides the above-mentioned querying capability of ‘entailing words’ from LHS to RHS. In addition to that, a lexical knowledge component can choose to support a additional interface that provides resource-specific relations (for example, this additional interface enables WordNet-based implementation to support WordNet-specific queries, or VerbOcean-based implementation to support querying on relations of VerbOcean etc). Both interfaces return a list of lexical rules.

6.4 Syntactic knowledge components

Syntactic knowledge resources capture entailment relationships between syntactic and lexical–syntactic structures. Such rules involve variables that stand for arbitrary material. For example, the structure ‘fall of X’ entails ‘X falls’ (cf. example in Section 1); similarly, ‘X sells Y to Z’ entails ‘Z buys Y from X’. Such relationships are captured insufficiently by purely lexical rules like (sell, V) → (buy, V).

Following Bar-Haim et al. (Reference Bar-Haim, Dagan, Greental and Shnarch2007), we represent lexical–syntactic knowledge as directed rules. Each rule consists of two dependency trees, which may contain variables as nodes (such as X, Y, and Z in the examples) plus a mapping from the variables of the LHS tree to the variables of the RHS tree.Footnote ¹¹

An illustration of a lexical–syntactic rule is given in Figure 4. The left-hand side (shown at the top) is a tree-fragment which represents the syntactic structure of ‘X sells Y to Z’, while the right hand side (in the bottom) represents ‘Z buys Y from X’. The variable names form the mapping, i.e. X in LHS is mapped to X in RHS, Y to Y and Z to Z.

Fig. 4.

Example of a lexical–syntactic rule: ‘X sells Y to Z’ → ‘Z buys Y from X’ (LHS above, RHS below). Mapping indicated by variable names.

The dependencies in the rules’ dependency trees (the LHS and RHS) are Stanford Dependencies (de Marneffe and Manning Reference de Marneffe and Manning2008), which capture relations that are relevant for semantic tasks (e.g. subject, object, types of modifiers, types of new clauses, etc.). We use a small list of POS tags, derived from Penn Treebank POS list. This list was generated by mapping several tags that represent similar POS into a ‘canonical’ tag. For example, VBD, VBG, VBN, VBP, and VBZ are all mapped into ‘Verb’. This process was similarly done for nouns, adjectives, etc.

A rule application is the operation of replacing the rule's LHS by its RHS in a given parse tree, resulting in a new parse tree. For example, when the rule of Figure 4 is applied on the (parse tree that corresponds to the) sentence ‘It happened after Harry sold the car to John’, a new sentence is generated: ‘It happened after John bought the car from Harry’. This application is illustrated in Figure 5.

Fig. 5.

Application of the lexical–syntactic rule from Figure 4 (above: before; below: after). Variable instantiation: X = Harry, Y = car, Z = John.

Syntactic rule formalization can represent knowledge about entailment relationships between predicate–argument structures, as well as about purely syntactic phenomena, like passive–active equivalence of the ‘X Verb Y ↔ Y is Verb[ed] by X’ type. Therefore, it can be used to represent a large variety of resources with (lexical–) syntactic knowledge, such as DIRT (Lin and Pantel Reference Lin and Pantel2002), REVERB (Berant Reference Berant2012), FrameNet-based entailment rules (Ben Aharon, Szpektor and Dagan Reference Aharon, Szpektor and Dagan2010), and many others. Transformation-based systems exploit such knowledge directly by using instantiated rules as proof steps. Alignment-based systems use it to identify semantic equivalence between subtrees of T and H, establishing phrase alignments.

Additional complexity compared with the lexical knowledge resource type arises from the more complex linguistic structures that make up the rules, namely parse trees with variables. These make a sophisticated query mechanism necessary. At the lexical level, we only have a linear number of words which we can query to retrieve all inference rules for a given input. At the syntactic level, however, the number of subtrees of a given parse tree is exponential in the input length. Our solution is to define a method in the component interface that works on the parse tree of the text and returns all matching rules from the current knowledge resource. The efficient identification of these rules, which may differ based on details of the knowledge resource, is left to the resource developer.

7.1 BIUTEE

BIUTEE (Stern and Dagan Reference Stern and Dagan2011) is a system for recognizing textual entailment based on the transformation-based approach outlined in Section 2.2 developed at Bar-Ilan University (BIU), Israel.Footnote ¹² The system derives the Hypothesis (H) from the Text (T) with a sequence of rewrite steps. Since BIUTEE represents H and T as dependency trees, these rewrite steps can either involve just lexical knowledge (node rewrites) or lexico-syntactic knowledge (subtree rewrites). Additional operations (e.g. the insertion of syntactic structure or modification of POS types) ensure the existence for a derivation for any T-H pair. The likelihood that a derivation preserves entailment is finally calculated by a confidence model.

Figure 6 shows the decomposition of BIUTEE in terms of the EXCITEMENT architecture. The LAP provides all required annotations, including parse trees. The EDA encapsulates the ‘top level’ of the algorithm. It consists of three parts: a generation part, where rewrite steps are performed, i.e. entailed trees are generated; a search part, which selects good candidates among the generated derivations; and a classifier. The generation part relies on entailment rules which are stored modularly in (lexico-)syntactic knowledge components and lexical knowledge components. The search part evaluates the set of derived trees and selects good ones. This evaluation is performed based on two criteria: one is the reliability of derivation rules, and the other is the distance between the derived tree T’ and H. The search ends when a derivation from T to H is found, and the final entailment decision is taken based on the confidence of the derivation.

Fig. 6.

System decomposition for the transformation-based BIUTEE system.

Even though the BIUTEE EDA could be decomposed in even more parts (e.g. the search strategies or the classifier could be stored in separate components), this would incur a considerably higher re-engineering effort. The decomposition shown in Figure 6 represents a pragmatic trade-off that involves a feasible porting effort while meeting the main goals formulated in Section 5.1: First, we have identified three modular parts of the BIUTEE system that are stored separately and can be reused in other systems. Second, the BIUTEE EDA becomes largely parser-independent and even language-independent since all annotation style-dependent processing is encapsulated in components.

7.2 EDITS

EDITS (Negri et al. Reference Negri, Kouylekov, Magnini, Mehdad and Cabrio2009) is an alignment-based RTE system developed at Fondazione Bruno Kessler (FBK), Italy.Footnote ¹³ It builds on the assumption that ‘the probability of an entailment relation between a given T-H pair is inversely proportional to the (edit) distance between T and H’ (Negri et al. Reference Negri, Kouylekov, Magnini, Mehdad and Cabrio2009). Thus, entailment recognition in EDITS can be thought of as a sequence of two steps. First, the distance between H and T is determined. EDITS offers a range of distance measures, including string and tree edit distance. Second, these distance measures serve as features in a binary classifier which decides entailment.

Figure 7 shows how EDITS can be decomposed in terms of our architecture. The figure shows that EDITS can reuse the BIUTEE analysis pipeline as LAP. The EDA is minimal: it does not even contain RTE-specific functionality. Rather, it embodies a minimal supervised machine learning setup – it consists of a feature extraction step (which calls various components that measure the distance between T and H) and a binary classifier using these features. This EDA is clearly parser- and language-independent. Footnote ¹⁴

Fig. 7.

System decomposition for the alignment-based EDITS system.

The decomposition of EDITS is fairly uncontroversial. Nevertheless, EDITS illustrates a hierarchical structure that is typical for alignment-based approaches: The EDA does not use linguistic knowledge components directly, but uses distance scoring components, which in turn take advantage of linguistic knowledge. For example, token edit distance can take lexical knowledge into account to reduce the distance for H-T pairs where an H word is entailed by a T word aligned to it. Similarly, syntactic tree edit distance can be enriched with paraphrase knowledge.

7.3 TIE

Textual Inference Engine (or TIE) is an RTE system that has been developed at the German Research Center for Artificial Intelligence (DFKI), Kaiserslautern, GermanyFootnote ¹⁵ (Wang and Neumann Reference Wang and Neumann2008a; Wang and Zhang Reference Wang and Zhang2009; Wang Reference Wang2011) and was not publicly released before. TIE was designed to cover a more general set of semantic relations (cf. Section 5.2). It decomposes ‘classical’ two-class RTE into a two-step task. The first step consists of a set of three independent classification problems corresponding to the presence of three semantic relations: TIE determines (a) whether T and H are related; (b) whether they are mutually consistent; and (c) whether there is an inherent directionality. The second step decides entailment based on the results of the first step, taking into account not only the classifier results but also their confidence values. This strategy has achieved decent performance in RTE challenges (e.g. second place in RTE-5). The multi-step classification setup of TIE is also used by a number of other RTE research prototypes.

The overall architecture of TIE is similar to EDITS, consisting of linguistic analysis components, feature extraction components, and classifier(s). During the linguistic analysis step, the system builds a joint syntactic and semantic dependency graph representation. In the feature extraction step, the system computes various features, including simple bag-of-words similarity scores as well as dependency path comparisons. In the final stage, these features are fed into three classifiers to measure relatedness, consistency, and directionality for each T-H pair, and then fed into the second classifier.

Figure 8 shows how the architecture of TIE can be mapped onto the EXCITEMENT architecture. Again, the EDA consists mainly of machine learning machinery, although this time it involves a total of four classifiers. Note that TIE can cover more classes than just entailment versus non-entailment and thus takes advantages of the flexible result type described in Section 5.2.

Fig. 8.

System decomposition for the multi-stage classification system TIE.

The linguistic knowledge is located in the various scoring components. Two main extensions over EDITS are features that target specifically matches and mismatches (a) between named entities and dates, and (b) on the level of semantic roles. These features are shown in the figures as the ‘NE scoring component’ and ‘semantic scoring component’, which can be reused by other systems.

The most challenging part of mapping TIE onto the EXCITEMENT architecture is the decomposition of the (two-stage) EDA. Ideally, each classifier would be encapsulated to a separate EDA in the spirit of a completely general multi-level classification setup. However, the three first-stage classifiers are not EDAs in their own right since they do not provide complete entailment decisions. For this reason, and to keep the architecture concise, we combine both stages into one EDA.

7.4 Formal reasoning-based textual entailment

The three systems whose mapping we have discussed above represent the majority of current data-driven approaches. However, as mentioned in Section 2.2, some systems approach textual entailment from another angle by translating the input into some kind of formal representation amenable to formal reasoning methods (Bos and Markert Reference Bos and Markert2005; Tatu and Moldovan Reference Tatu and Moldovan2005; Bobrow et al. Reference Bobrow, Condoravdi, Crouch, Paiva, Karttunen, King, Nairn, Price and Zaenen2007). Such a system is currently not included in the EXCITEMENT Open Platform (EOP), and we have not looked at individual systems of this type at the same level of detail as the three systems that we have included.

Nevertheless, we believe that the mapping of such systems onto the EXCITEMENT architecture can take place along roughly the same lines, as shown in Figure 9. The necessary extensions should all be possible within the EXCITEMENT architecture. The main reasoning part maps most straightforwardly onto an EDA as illustrated in the figure. A hybrid system that uses both reasoning and machine learning methods such as (Bos and Markert Reference Bos and Markert2005) might however decide to use a statistical EDA and put the reasoner into an algorithmic component.

Fig. 9.

System decomposition for a formal reasoning TE system.

The most obvious defining property of other reasoning-based approaches is the complete transformation of the natural language input into a formal representation. This raises the question of where the transformation will take place: in the LAP or in the EDA. To promote reusability, we would encourage placing this translation in the LAP, which requires extending the UIMA CAS type system to accommodate the formal representation, be it some sort of description logics, predicate logics, or something else.

The second major question is: what types of knowledge the reasoning process requires. The analysis by (Clark et al. Reference Clark, Harrison, Thompson, Murray, Hobbs and Fellbaum2007) indicates that the lexical and lexico-syntactic knowledge components that form part of EXCITEMENT can cover a significant portion (paraphrases, synonyms, etc.), assuming that a conversion process can be found that translates the output of these components into a formal representation (e.g. a pair of synonymous words into a universal meaning postulate). Another knowledge type that Clark et al. discuss is generic world knowledge such as the so-called core theories that express ‘general, fundamental knowledge (e.g. space, time, plans, goals)’. This type of knowledge raises two challenges: (a) we assume that the existing query interfaces of the lexical and lexical–syntactic components are insufficient; and (b) the data must be exchanged at the level of the formal representation language (or its UIMA type). Therefore, we believe that general world knowledge is best represented as a novel knowledge component type.

8.1 Development and scope of the platform

The first release of the EOP comprises a suite of EDAs, EC components, and LAP components for three languages (English, German, and Italian). The following list gives the most important components.

• LAP: The platform includes one LAP for each language that covers tokenization, POS tagging, lemmatization, and dependency parsing. The English LAP includes a pipeline based on the Stanford NLP tools (Toutanova and Manning Reference Toutanova and Manning2000; Finkel, Grenager and Manning Reference Finkel, Grenager and Manning2005), an easy-first parser (Goldberg and Elhadad Reference Goldberg and Elhadad2010), and the Ark coreference resolver (Haghighi and Klein Reference Haghighi and Klein2009). Another pipeline that is available for English and German is based on TreeTagger (Schmid Reference Schmid1994) and MaltParser (Nivre and Nilsson Reference Nivre and Nilsson2005). The Italian LAP is based on the TextPro package (Pianta, Girardi and Zanoli Reference Pianta, Girardi and Zanoli2008).

• EDAs: The platform covers the three systems whose mappings were outlined in the previous section: a transformation-based EDA (BIUTEE), a single-level classification EDA (EDITS), and a multi-level classification EDA (TIE). These EDAs are language-independent, providing a set of generic basic entailment algorithms.

• Algorithmic components: The platform comes with a set of EC components. It includes distance components for various linguistic levels, components that extract match and mismatch features, and annotator components, e.g. for predicate truth (Lotan, Stern and Dagan Reference Lotan, Stern and Dagan2013). Even though these components were generally implemented for one specific system, we have reviewed the code so that as many components as possible are language-independent (e.g. edit distance), and applicable to multiple EDAs.

• Knowledge components: The platform includes about two dozen lexical and syntactic resources for three languages. Much of these resources are inherited from migrating RTE systems, but now use the same set of interfaces that makes them accessible in a uniform fashion. Since there is still a clear predominance of English resources, the platform includes lexical and syntactic knowledge mining tools to bootstrap resources for other languages or specific domains from corpora.

• Data sets: Finally, the platform includes a number of RTE data sets for all three languages. For English, it covers the well-known RTE workshop test data sets. RTE-3 is also present in translated versions for both Italian and German. Furthermore, we include two task-specific datasets, such as the monolingual English data set prepared for the SemEval-2012 Content Synchronization task (Negri et al. Reference Negri, Marchetti, Mehdad, Bentivogli and Giampiccolo2012), and a German Web search task dataset (Zeller and Padó Reference Zeller and Padó2013).

This first release of the platform is able to demonstrate our original goals:

• • The CAS type systems and the component interfaces form a fundamental layer of the platform that is shared by all three languages and all components. It can be reused by any future components and languages.

• • For each language, we have prepared a single linguistic annotation pipeline. This LAP is reused by all EDAs for that language. For example, all three EDAs for English (EDITS, TIE, and BIUTEE) now share one LAP, whereas each had its own preprocessing toolchain. This separation of LAP from EC worked well with the proposed CAS types. We did not encounter major problems in converting the preprocessing to the UIMA CAS framework.

• • The EDAs are also usable for multiple languages now. For example, we are now able to apply the EDITS EDA to German text, which was not possible earlier.

• • Finally, the generic access methods to knowledge resources provided through the component interfaces mean knowledge resources can now be used by any EDAs. This enables EDAs to use resources that were not used before with virtually no efforts. For example, the adaptation of EDITS to access WordNet through our lexical knowledge interface automatically means that it can use GermaNet when applied to German. With the platform, this would have required dedicated development effort.

8.2 Pilot evaluation

The main aim of the first release is to reduce the future effort of building and improving systems for textual entailment. Thus, the first release is conservative regarding quality and efficiency: The EDA algorithms remain the same as before, and no explicit improvements were made regarding scalability.

Regarding quality, the migrated EDAs should therefore mirror the performance of individual systems. As for efficiency, the integration into the EOP involved some re-implementation as well as some glue code, and the consequences of these changes are not a priori clear.

This section compares three English EDAs (EDITS, BIUTEE, and TIE), as integrated in the platform, with standalone versions of the systems. We evaluate their accuracy and runtime on the test section of the English RTE-3 dataset consisting of 800 T-H pairs. We do not use published numbers of the standalone systems, but configured them so as to correspond as closely as possible to the EDA versions.

Accuracy. The results in Table 1 show that accuracy differences exist between the standalone and platform versions, but they are fairly small. There is almost no change for EDITS (+0.1%). There are small drops in performance in the EDA version of BIUTEE (–0.4%) and TIE (–0.8%). These are presumably due to the refactoring steps that took place during migration and inevitably involved the removal of some representation- and language-specific processing. However, when we assessed the significance of these differences with a bootstrap re-sampling test (Efron and Tibshirani Reference Efron and Tibshirani1993), we found that none of the differences were significant at p = 0.05. We see this as a promising result: We were able to generalize and migrate our systems into the EXCITEMENT platform without a statistically significant loss in performance, and we hope that the same could be done for other systems.

Table 1.

Comparison of accuracy (%) between standalone systems and EXCITEMENT platform versions using specified resources on the English RTE-3 dataset. All differences are not significant at p = 0.05

Efficiency. Table 2 shows the runtimes of the three EDAs, excluding startup time (i.e. the one-time overhead necessary to read resources and input files). The runtimes show a much less uniform picture than the accuracies. For two systems, runtimes have increased (BIUTEE: +38%, EDITS: +31%), while one system has become faster (TIE: –13%). In the case of BIUTEE, where the absolute increase is by far the highest, the reason is that standalone BIUTEE used a POS tag set different from the EOP standard. The developers decided to convert tags dynamically. The resulting performance hit could be avoided by converting all resources to the EOP standard tagsets. More generally, the runtimes are dominated by the overall differences among EDAs, which amount to orders of magnitude. They reflect differences between the processing mechanisms of the EDAs – string edit distance in the case of EDITS versus large-scale lexical–syntactic processing in the case of BIUTEE. In comparison, the impact of importing the EDAs into the EOP is relatively small.

Table 2.

Comparison of runtimes (in ms; excluding startup time) between standalone systems and EXCITEMENT platform versions using specified resources on the English RTE-3 dataset

8.3 Platform usage and use cases

User interface. The components provided by our suite of components are combined into actual ‘inference engines’ through configuration files which contain information to initialize and instantiate a complete inference engine. The user interacts with the platform in the following three steps: (1) write or select a configuration and instantiate the engine; (2) obtain a model by training on new data or loading a previously trained model; and (3) process textual entailment instances.

The platform ships with a set of predefined configuration files covering the shipped components. Each configuration is accompanied by a documentation that describes its characteristics, including efficiency and accuracy. In addition, each separate EDA and component come with documentation on how to configure their functionality.

Use cases. We have two main use cases for the platform in mind. The first one is as a general, self-contained textual entailment engine. This usage is suitable for industrial users, or research users who want to use an already established inference engine as a part of their language processing systems. In this use case, the main benefit of the EXCITEMENT platform is that integration of one platform allows the end user to compare the performance of various RTE systems and configurations in their application. For this use case, the platform can be used as an Apache MavenFootnote ¹⁷ Java module. This enables off-the-shelf usage without knowledge of project internal dependencies.

The second use case is a platform for research in inference. For this group, the most important aspects of the platform are the ability to extend and modify the code base. The EXCITEMENT platform development adopted several policies and principles to make this as easy as possible. Notably, all EXCITEMENT component types introduced in Section 6 support the common behaviors defined in the component type and expose the configurable internal values directly in their class constructor, among other things. Also, the components and their interfaces are documented extensively so that they can be exchanged modularly. Finally, the platform comes with a set of utilities that support development, such as knowledge extraction facilities.

Expectations. We cannot guarantee that the EXCITEMENT platform will find widespread adoption in the textual entailment field. Nevertheless, we believe that it has a good chance of playing a significant role. This judgment is based on the ‘investment versus payback’ trade-off: researchers will adopt the tools that allow them to reach their research goals with the minimal effort necessary. In this respect, the EXCITEMENT platform is an attractive offer: a clean code base for multilingual research that covers several major approaches, can be easily extended and modified, and is accompanied by a layer of research utilities. Naturally, this trade-off differs for each researcher. EXCITEMENT should be interesting for groups who want to enter the field of textual entailment and for whom it can radically lower the initial effort necessary (e.g. developing textual entailment systems for new languages). Meanwhile, established groups with self-developed textual entailment systems naturally have a much smaller incentive to migrate. However, such groups might still be interested in contributing smaller components (e.g. knowledge resources) from their systems to EXCITEMENT to make them available to a broad community. Conversely, if researchers find it helpful to integrate EXCITEMENT components into their own systems, the architecture would still provide a benefit to the community as a standard for exchangeable components, rather than as a complete platform.