Robert Mahl

Katarzyna Wegrzyn-Wolska

Keywords: Natural Language Processing, Textual Entailment, Recognizing Textual En- Similarity, Informative Asymmetric Measure, Asymmetric

Each person who goes in our life goes alone; it is because each person is unique and no one replacing the other.

Each person who goes in our life passes us alone and not only because each person leaves a bit of himself and takes a bit of us. (…)"

Charles Chaplin At all stages of our lives we cross paths with people who contribute directly or indirectly to our success, people who by their importance, became forever in the history of our lives, in our history. Though only my name appears on the cover of this dissertation, many people have contributed to and helped me to bring it up and in its production. I owe my sincere gratitude to all those people who have made this thesis possible and because of whom such experience has been one that I will cherish forever.

I have been fortunate to have an adviser who gave me the freedom, courage and confidence to explore this path on my own, and at the same time the helpful guidance to recover when my steps failed. During all these years of working together, Gaël Dias taught me how to be precise, organized and focused. His support even during the last stages of my thesis and his management and coordination skills have been valuable lessons that I'm sincerely grateful for. "

If I could reach this stage of my life, this PhD, the writing of this thesis, it is owing to the force that you give me, and to the new meaning that you give to my life, my wife and my daughter. To you I dedicate this thesis. You are responsible for this work, this new victory. I am forever grateful.

iii

Extended Abstract

"If you can't explain it simply, you don't understand it well enough."

Albert Einstein

Textual Entaiment (TE) aims to capture major semantic inference needs across applications in Natural Language Processing (NLP). Since 2005, in the TE recognition (RTE) task, systems are asked to automatically judge whether the meaning of a portion of text, the Text -T, entails the meaning of another text, the Hypothesis -H. A number of novel approaches, and improvements in TE technologies demonstrated in recent Recognizing Textual Entaiment (RTE) Challenges are signaling of renewed interest towards a deeper and better understanding of the core phenomena involved in TE.

In line with this direction, in this thesis we focus on a particular case of entailment, entailment by generality. For us, there are various types of implication, range of different levels of entailment reasoning, based on lexical, syntactic, logical and world knowledge at different levels of difficulty. We introduce the paradigm of TE by Generality, which can be defined as the entailment from a specific sentence towards a more general sentence. In this context, the Text T entails the Hypothesis H, because H is more general than T.

We propose an unsupervised and language-independent method to recognize TE by Generality given a case of Text -Hypothesis or T -H where entailment relation holds. To this end, we introduce an Informative Asymmetric Measure (IAM) called Simplified Asymmetric InfoSimba, which we combine with different Asymmetric Association Measures (AAM).

To evaluate the performance of our proposal, we did three experiments: To do the experiment with pairs T-> H, where we know the entailment between T and H is for generality, it was necessary us create a corpus of pairs Text-> Hypothesis with Entailment by Generality. This corpus was annotated using the CrowdFlower 2 system, a cheap and fast way to collect annotations from a broad base of paid non-expert contributors over the Web. The corpus is composed of pairs of Text -Hypothesis, collected for RTE-1 through RTE-5 challenges. Only positive pairs of TE were submitted to CrowdFlower for annotation, together with a small set of carefully selected cases of known categorization that are used to train the participating annotators and to exercise quality control.

In this work we hypothesize the existence of a special mode of TE, namely Textual Entailment by Generality. Thus, the main contribution of our study is to highlight the importance of this inference mechanism. Consequently, the new annotation data seems to be a valuable recourse for the community.

QA

Question Answering.

RAIS

Recursive Asymmetric InfoSimba Similarity. Also here we introduce our objective in this work -identifying entailment by generality in pairs of sentences.

RC

Natural Language Processing

We can not imagine a world without communication. Every living being must communicate to survive.

For us, human beings, language is a fundamental aspect and it is a crucial component of our life.

In written form it serves as a long-term record of knowledge from one generation to the next. In spoken form it serves as our primary means of coordinating our day-to-day behavior with others.

Thus, producing language is above all a social activity.

NLP is a field of computer science and linguistics concerned with the interactions between computers and humans by means of natural language. In theory, NLP is a very attractive method of humancomputer interaction. Natural Language (NL) understanding is sometimes referred to as an Artificial Intelligence (AI) complete problem, because NL recognition seems to require extensive knowledge about the outside world and the ability to manipulate it. NLP has significant overlap with the field of computational linguistics, and is often considered a sub-field of artificial intelligence.

Modern NLP algorithms are grounded in Machine Learning (ML), especially statistical ML. Research into modern statistical NLP algorithms requires understanding of a number of fields, including linguistics, computer science, statistics (particularly Bayesian Statistics), linear algebra and optimization theory.

Historical Review

Work in the NLP field has concentrated first on one problem, then on another, sometimes because solving problem X depends on solving problem Y but sometimes just because problem Y seems more tractable than problem X, or because there is market interest in a solution to Y. There has been very substantial progress, both in understanding how to do NLP and in actually doing it, since work in the field took off in the 1950s. In the last twenty-five years in particular, advances in computing technology have made it possible to implement ideas that could only be adumbrated before, to consolidate research, and to carry speech and language processing into the ordinary world. Sometimes the scientific advance in NLP, or the computational linguistics underlying it, is less than the onward rush of information technology field evident in the fifty-year period reviewed here.

Sometimes innovation is only old ideas reappearing in new guises, like lexical list approaches to NLP, or shallow parsing. But the new costumes are better made, of better materials, as well as more becoming: so the research is not so much going round in circles as ascending a spiral.

The work of the late 1940s to late 1960s, was focused on Machine Translation (MT). Following a few early birds, including Booth and Richens' investigations and Weaver's influential memorandum on translation of 1949, research on NLP began in earnest in the 1950s. Automatic translation from Russian to English, in a very rudimentary form and limited experiment, was exhibited in the IBM-Georgetown Demonstration of 1954 (Hutchins et al., 1955). The journal Mechanical Translation, the ancestor of Computational Linguistics, also began publication in 1954. The first international conference on Mechanical Translation was held in 1952, the second in 1956 (the year of the first AI conference); at the important Washington International Conference on Scientific Information of 1958 language processing was linked with information retrieval, for example in the use of a thesaurus, Minsky drew attention to AI, and Luhn provided auto-abstracts (actually extracts) for one session's papers. The Teddington International Conference on Machine Translation of Language and Applied Language Analysis in 1961 was perphars the high point of this phase: it reported work done in many countries on many aspects of NLP including morphology, syntax and semantics, in interpretation and generation, and ranging from formal theory to hardware.

Some notably successful NLP systems developed in the 1960s were SHRDLU1 -"SHRDLU was primarily a language parser that allowed user interaction using English terms. The user instructed SHRDLU to move various objects around in a "blocks world" containing various basic objects: blocks, cones, balls, etc. What made SHRDLU unique was the combination of four simple ideas that added up to make the simulation of "understanding" far more convincing." 2 -a natural language system working in restricted "blocks worlds" with restricted vocabularies, and ELIZA (Weizenbaum, 1966), a simulation of a Rogerian psychotherapist, written by Joseph Weizenbaum 3 between 1964 to 1966.

Using almost no information about human thought or emotion, ELIZA sometimes provided a startlingly 1.1 Natural Language Processing human-like interaction. When the "patient" exceeded the very small knowledge base, ELIZA might provide a generic response, for example, responding to "My head hurts" with "Why do you say your head hurts?".

In 1969 Roger Schank 1 introduced the conceptual dependency theory for natural language understanding (Schank & Tesler, 1969).

In 1970, William A. Woods introduced the Augmented Transition Network (ATN) to represent natural language input (Woods, 1970). Instead of phrase structure rules ATN used an equivalent set of finite state automata that were called recursively. ATN and their more general format called "generalized ATN" continued to be used for a number of years. During the 70's many programmers began to write "conceptual ontologies", which structured real-world information into computerunderstandable data.

Up to the 1980s, most NLP systems were based on complex sets of hand-written rules. Starting in the late 1980s, however, there was a revolution in NLP with the introduction of machine learning algorithms for language processing. This was due both to the steady increase in computational power resulting from Moore's Law 2 and the gradual lessening of the dominance of Chomskyan 3 theories of linguistics (e.g. transformational grammar), whose theoretical underpinnings discouraged the sort of corpus linguistics that underlies the machine-learning approach to language processing. Some of the early machine learning algorithms, such as decision trees, produced systems of hard if-then rules similar to existing hand-written rules. Increasingly, however, research has focused on statistical models, which make soft, probabilistic decisions based on attaching real-valued weights to the features making up the input data. The cache language models upon which many speech recognition systems now rely are examples of such statistical models. Such models are generally more robust when given unfamiliar input, especially input that contains errors (as is very common for real-world data), and produce more reliable results when integrated into a larger system comprising multiple subtasks.

Many of the notable early successes occurred in the field of MT, due especially to work at IBM Research, where successively more complicated statistical models were developed. These systems were able to take advantage of existing multilingual textual corpora that had been produced by the Parliament of Canada 4 and the European Union 5 as a result of laws calling for the translation of all governmental proceedings into all official languages of the corresponding governmental systems.

However, most other systems depended on corpora developed for specific task, which was (and often continues to be) a major obstacle to the success of these systems. As a result, a great deal of research has gone into methods of more effectively learning from limited amounts of data.

algorithms. Such algorithms are able to learn from data that has not been hand-annotated with the desired answers, or using a combination of annotated and raw data. Generally, this task is much more difficult than supervised learning, and typically produces less accurate results for a given amount of input data. However, there is an enormous amount of non-annotated data available (including, among other things, the entire content of the World Wide Web (WWW)), which can often make up for the inferior results.

Applications of Natural Language Processing

NLP is an interdisciplinary research area at the border between linguistics and AI aiming at developing computer programs capable of human-like activities related to understanding or producing texts or speech in a natural language, such as English or Chinese.

The most important applications of NLP include Information Retrieval (IR) and information organization, MT, and natural language interfaces, Information Extraction (IE), Summarization (SUM), search engine, among others. However, as in any science, the activities of the researchers are mostly concentrated on its internal art and craft, that is, on the solution of the problems arising in analysis or generation of natural language text or speech, such as syntactic and semantic analysis, disambiguation, or compilation of dictionaries and grammars necessary for such analysis.

Motivation and Rationale

Natural Language (NL) allows the same meaning to be expressed in many different ways, making automatic understanding particularly challenging. Almost all computational linguistics tasks such as IR, Question Answering (QA), IE, SUM and MT have to cope with this phenomenon.

Inference is generally perceived as the process by which new knowledge is inferred from given information. For example, the Merriam-Webster online dictionary1 defines the first sense of infer as "to derive as a conclusion from facts or premises". Somewhat more technically, inference is defined as "the act of passing from one proposition, statement, or judgment considered as true to another whose truth is believed to follow from that of the former".

Moving to the realm of NLP, we can analogically perceive inference over information stated in human language. Such inference can be defined as the process of concluding the truth of a textual statement based on (the truth of) another given piece of text. This language-oriented view on inference was captured by the textual entailment paradigm, originally proposed by Dagan & Glickman (2004) and subsequently established through the series of benchmarks known as the PASCAL Recognising

Textual Entailment (RTE) Challenges.

While capturing a generic notion of inference over texts, the introduction of entailment recognition as a computational task was particularly motivated by its overarching potential for NLP applications.

Motivation and Rationale

For example, consider a QA scenario, addressing the question "Who painted 'The Scream'?". In order

to provide the answer "Edvard Munch", based on the text snippet "Norway's most famous painting, 'The Scream' by Edvard Munch,…", the QA system needs to validate that the hypothesized answer statement "Edvard Munch painted 'The Scream'." is indeed entailed (inferred) by the given text.

Entailment is widely used in many aspects of the human life. Assume that someone is seeking for something and he or she searches for the answer from books, friends, or the Web. In most cases, the information gathered or retrieved is not the exact answer, although the (information) seeker may have one in his or her mind. Instead, the consequences of the original goal may be detected, so the entailment plays a role and confirms or denies the original information being sought (Dagan et al., 2013).

For example, John wants to know whether the Amazon river is the longest river in the world. Naturally, he can find the exact lengths of the Amazon and other rivers he knows of, and then compare them. But once he sees "Egypt is one of the countries along the longest river on earth", he can already infer that Amazon is not the longest river, since Egypt and the Amazon river are not on the same continent. Similarly, assuming that Albert is not sure who is the current president of the U.S., Bush or Obama, since both "president Bush" and "president Obama" are retrieved. If he performs an inference based on one of the retrieved documents containing "George Bush in retirement", the answer is obvious. In short, finding out the exact information is not always trivial, but inference can help a lot. In both cases, the retrieved information entails the answer instead of being the precise answer.

Entailment also occurs frequently in our daily communication, with respect to language understanding and generation. Usually we do not literally interpret each other's utterances, nor express ourselves in a straight way. For example:

• Tom: Have you seen my iPad?

• Robin: Oh, nice! I'd like to have one too.

• Tom: You have to get one.

The dialogue seems to be incoherent, if we literally and individually interpret each sentence. Firstly, Tom asks a yes-no question, but Robin does not directly give the answer. Instead, Robin implies that he has not seen it before the conversation by showing his compliment to it ("Oh, nice!"). Probably

Tom is showing his iPad to Robin during the conversation. Robin's second sentence also implies that he does not have an iPad till then, and therefore Tom's response is a suggestion for him to get one.

If we literally interpret the conversation, it sounds a bit awkward. Here is one possibility:

• Tom: Here is my iPad.

• Robin: I haven't seen it before. It is nice. I don't have one, but I'd like to have one.

• Tom: I suggest you get one.

Although the interpreted version may be easier for the computers to process human dialogues, the original conversation occurs more naturally in our daily life. Each utterance in the interpreted version is actually implied or entailed by the utterances in the original conversation. Consequently, if we want to build a dialogue system, dealing with this kind of implication or entailment is one of the key challenges. Let alone there is common sense knowledge which does not appear in the dialogue but is nevertheless acknowledged by both speakers, e.g., what an iPad is.

RTE was proposed by Dagan & Glickman (2004) as a generic NLP task in order to overcome the problem of lexical, syntactic and semantic variability in natural languages. In 2005, the RTE Challenge has been launched by Dagan et al. (2005), defining TE as a task for automatic systems.

Given a text T and a hypothesis H, the task consists of deciding whether the meaning of H can be inferred from the meaning of T.

The following examples show T -H pairs for which the entailment relation holds (Example 1) or not (Example 2):

• Example 1 T: Euro-Scandinavian media cheer Denmark vs Sweden draw.

H: Denmark and Sweden tie.

Entailment: YES

• Example 2 T: Oracle had fought to keep the forms from being released.

H: Oracle released a confidential document.

Entailment: NO

In the many evaluation campaigns that in recent years addressed the TE recognition problem, complex definitions of the task have been proposed. The released datasets reflect the long-term objective of creating more natural evaluation settings. These include the formulation of TE as a search task1 (i.e. finding all the sentences in a set of documents that entail a given hypothesis), the use of TE to approach the Answer Validation Exercise 2 (emulate human assessment of QA responses and decide whether an answer to a question is correct or not according to a given text), and the very recent effort to explore multi-directional TE recognition 3 (moving from YES/NO to directional entailment judgements such as Forward, Backward and Bidirectional). Consequently, a large number

Motivation and Rationale

of methods and resources for TE has been published or released.

As for the NLP perspective, RTE can be viewed as a generic semantic processing module, which serves for other tasks. For instance, it has already been successfully used for question answering (Harabagiu & Hickl, 2006), including answer validation (Peñas et al., 2008;Rodrigo et al., 2009), information extraction (Roth et al., 2009), and MT evaluation (Padó et al., 2009a). In the long term, RTE can also play an important role in understanding conversation dialogues (Zhang & Chai, 2010), metaphors (Agerri, 2008), and even human-robot communication (Bos & Oka, 2007).

Given the multiple applicability that Textual Entailment can have, we understand that there are several types of implications, where each type of implication stems or suits specific task. Proof of this is the diversity of methodologies and results presented in the RTE challenges. It is accepted that textual entailment is not an exact science and we believe that there is still much to be investigated in this area.

In this thesis we introduce a new concept, Entailment by Generality. This new paradigm can be defined as the relation that holds between a specific statement that implies a more general one, for example, strawberry (specific) implies fruit (general), because strawberry is really a fruit, but fruit does not necessarily imply strawberry, because, fruit can be strawberry but can also be orange, banana, or other fruit.

Also in this thesis we present our methodology -unsupervised, language-independent and threshold free -for learning to identify entailment by generality between two sentences. This technology is enabling Ephemeral Clusters Summarization of Web Pages (Dias et al., 2011), useful for optimized Search Engine results visualization.

In the context of Ephemeral Clustering of Web Pages, it can be interesting to label each cluster with a small summary instead of just a label. Thus we are interested to find the best web snippet, which

summarizes and subsumes all the other web snippets within an ephemeral cluster. This summary can be defined as a general entailment from a specific information characteristic of the cluster.

Although, Ephemeral Clustering has been studied for more than a decade, it has received low user acceptance. According to us, there are two main reasons for this situation. First, state-of-the-art systems tend to generate an excessive number of clusters. As a consequence, browsing through a high number of clusters is mostly similar to searching through a high number of Web pages. Second, improved user interfaces can only be achieved through high quality cluster labeling. In the optimal case, the labels of the clusters should clearly evidence their overall contents. However, very little has been proposed in the community to overcome the latter obstacle. The only exception is certainly (de Buenaga et al., 2008) who propose to increase the expressiveness of cluster labels with a summary obtained by classical Multi-document Summarization techniques. However, their solution is fulltext based and can not be applied in real-time real-world applications. As a consequence, we propose to increase cluster expressiveness based on finding the web snippet within the ephemeral cluster, which best summarizes and subsumes all the other web snippets present in the cluster. For that purpose, we propose a different methodology based on TE by Generality.

Linguistic Notion of Entailment

The application-oriented notion of textual entailment is related, of course, to a classical logic-based notion of entailment in linguistics. A common definition of entailment in formal semantics specifies that a Text T entails another text H (hypothesis, in our terminology) if H is true in every circumstance (possible world) in which T is true. However, the TE definition allows for cases in which the truth of the hypothesis is highly plausible ("most likely true"), for most practical purposes, rather than certain.

In propositional and predicate logic, entailment (or logical implication) describes a relation between one sentence or a set of sentences -the entailing expressions -represented as formulae of a formal language, and another sentence that is entailed. Formally, given a set of formulae Γ = A 1 , .

Variants of the Entailment

As already mentioned in this thesis, we argue that there are several types of entailment, for example in the study done in (Pazienza et al., 2005),they present three types of entailment can be defined:

1. Semantic Subsumption -T and H express the same fact, but the situation described in T is more specific than the situation in H. The specificity of T is expressed through one or more semantic operations. For example in the sentential pair:

• H: The cat eats the mouse.

• T: The cat devours the mouse.

T is more specific than H, as eat is a semantic generalization of devour.

2. Syntactic Subsumption -T and H express the same fact, but the situation described in T is more specific than the situation in H.

The specificity of T is

Linguistic Notion of Entailment

expressed through one or more syntactic operations. For example in the pair:

• H: The cat eats the mouse.

• T: The cat eats the mouse in the garden.

T contains a specializing prepositional phrase.

3. Direct Implication -H expresses a fact that is implied by a fact in T. For example:

• H:The cat killed the mouse.

• T: The cat devours the mouse.

H is implied by T, as it is supposed that killed is a precondition for devour. In (Dagan & Glickman, 2004) syntactic subsumption roughly corresponds to the restrictive extension rule, while direct implication and semantic subsumption to the axiom rule.

In (Pazienza et al., 2005) despite the two types of subsumption entailment, direct implication underlies deeper semantic and discourse analysis. In most cases, as implication concerns two distinct facts in T and H, and as facts are usually expressed through verbs, it follows that the implication phenomenon is strictly tied to the relationship among the T and H verbs. In particular, it is interesting to notice the temporal relation between T and H verbs, as described in (Miller, 1995). The two verbs are said to be in temporal inclusion when the action of one verb is temporally included in the action of the other (e.g. snore -> sleep). Backward-presupposition stands when the H verb happens before the T verb (win entails play). In causation a stative verb in H necessarily follows a verb of change in T (e.g. give -> have). In this case, the temporal relation is thus inverted with respect to backward-presupposition. Such considerations leave space to the application of temporal and verb analysis techniques both in the acquisition and recognition tasks.

Ultimately, we want to regard entailment by generality as a relation between utterances (that is, sentences in context), where the context is relevant to understand the meaning. Then, considering study in (Pazienza et al., 2005), we understand that the relation entailment by generality can be compared with one of three relations:

• Semantic Subsumption;

• Syntactic Subsumption;

• Or a combination -Semantic Subsumption + Syntactic Subsumption;

For us, in the most common definition, Entailment by Generality can be defined as the entailment from specific sentence towards a more general sentence. (Dias et al., 2011;Pais et al., 2011).

. . . Entailment: S1 entails S2

. . .

S1

.

John is from Osnabrueck . . .

S2

.

John is from Germany . . .

S1 entails S2 iff [[S1]] ⊆ [[S2]]
.

[[S1]]

.

[[S2]]

. .

Set

Context of Textual Entailment

Natural languages allow to express the same meaning in many possible ways, making automatic understanding particulary challenging. Almost all computational linguistics tasks such as IR, QA, IE, text summarization and MT have to cope with this phenomenon.

Within TE framework, a text T is said to entail a textual hypothesis H if the truth of H can be inferred from T. This means that most people would agree that the meaning of T implies that of H.

Somewhat more formally, we say that T entails H when some representation of H can be "matched"

with some (or part of a) representation of T, at some level of granularity and abstraction.

Dagan & Glickman (2004) define TE as a relationship between a coherent textual fragment T and a language expression, which is considered as a hypothesis H. Entailment holds (i. e. T → H) if the meaning of H can be inferred from the meaning of T, as interpreted by a typical language user. This relationship is directional and asymmetric, since the meaning of one expression may usually entail the other, while entailment in the other direction is less certain.

This definition of textual entailment captures quite broadly the reasoning about language variability needed by different applications aimed at natural language understanding and processing (Androutsopoulos & Malakasiotis, 2010;Dagan et al., 2009). For instance, a QA system has to identify texts that entail the expected answer. Given the question "Who painted the Mona Lisa?", the text "Among the works created by Leonardo da Vinci in the 16th century is the small portrait known as the Mona Lisa or la 'Gioconda'", entails the expected answer "Leonardo da Vinci painted the Mona Lisa".

Similarly, in IR relevant documents should entail the combination of semantic concepts and relations denoted by the query. In IE, entailment holds between different text variants expressing the same target relation (Romano et al., 2006). In text summarization, an important processing stage is sentence extraction, which identifies the most important sentences of the texts to be summarized;

especially when generating a single summary from several documents (Barzilay & McKeown, 2005), it is important to avoid selecting sentences that convey the same information as other sentences that have already been selected (i.e. that entail such sentences). Also in MT, an entailment relation should hold:

Context of Textual Entailment

1. among machine-generated translations and human-authored ones that may use different phrasings in the evaluation phase (Padó et al., 2009b), or 2. in the translation phase, between source language words and longer phrases that have not been encountered in training corpora (Mirkin et al., 2009).

Other applications that could benefit from such inference model are reading comprehension systems (Nielsen et al., 2009).

Below, we give a few variants of informal definitions for textual entailment.

Probabilistic Textual Entailment

In many intuitive cases, the textual entailment recognition task may be perceived as being deterministic (Glickman & Dagan, 2005). For example, given the hypothesis h 1 = "Harry was born in Iowa" and a candidate text t 1 that includes the sentence "Harry's birthplace is Iowa", it is clear that t 1 does (deterministically) entail h 1 , and humans are likely to have high agreement regarding this decision. In many other texts, though, entailment inference is uncertain and has a probabilistic nature. For example, a text t 2 that includes the sentence "Harry is returning to his Iowa hometown to get married." does not deterministically entail the above h 1 since Harry might have moved to Iowa as a child. Yet, it is clear that t 2 does add substantial information about the correctness of h 1 .

In other words, the probability that h 1 is indeed true given the text t 2 ought to be significantly higher than the prior probability of h 1 being true. More specifically, we might say that the probability p of h 1 being true should be estimated based on the percentage of cases in which someone's reported hometown is indeed his/her birthplace. Accordingly, we wouldn't accept t 2 as a definite assessment for the truth of h 1 . However, in the absence of other definite information, t 2 may partly satisfy our information need for an assessment of the probable truth of h 1 , with p providing a confidence probability for this inference. From this applied empirical perspective, textual entailment represents therefore an uncertain -but highly plausible -relation, that has a probabilistic nature.

Recognizing Textual Entailment

The RTE task, as defined by Dagan et al. (2005), and established in the RTE Challenges, is formulated as follows:

Textual entailment is defined as a directional relationship between pairs of text expressions, denoted by T (the entailing "Text") and H (the entailed "Hypothesis"). We say that

T entails H if humans reading T would typically infer that H is most likely true.

Basically, RTE is the task of deciding, given two text fragments, whether the meaning of one

Our Proposal for RTE by Generality

of the texts is entailed (can be inferred) from the other text.

As noted by Dagan et al. (2005), this definition is based on common human understanding of language, much like the definition of any other language understanding task. Accordingly, it enables the creation of gold-standard evaluation data sets for the task, where humans can judge whether the entailment relation holds for given Text-Hypothesis pairs. This setting is analogous to the creation of gold standards for other text understanding applications like QA and IE, where human annotators are asked to judge whether the target answer or relation can indeed be inferred from a candidate text. The distinguishing characteristic of the textual entailment task is that it captures textual inference in a generic, application-independent manner. This allows research to focus on core inference issues, while making the results applicable across application areas.

Similar to other semantic annotation tasks, such as those mentioned above, the RTE judgment criterion has some fuzziness with respect to "what a person would typically infer", particularly in boundary cases. However, the various RTE annotation efforts have shown that sufficiently consistent human judgments can be obtained, allowing research progress on this task (Dagan et al., 2013).

Also, this task captures generically a broad range of inferences that are relevant for multiple applications. For example, QA system has to identify texts that entail the expected answer. Given the question "Who is John Lennon's widow?" the text "Yoko Ono unveiled a bronze statue of her late husband, John Lennon, to complete the official renaming of England's Liverpool Airport as Liverpool John Lennon Airport" entails the expected answer "Yoko Ono is John Lennon's widow".

Similarly, semantic inference needs of other text-understanding applications such as IR, IE and MT evaluation can be cast as entailment recognition (Candela et al., 2006). A necessary step in transforming textual entailment from a theoretical idea into an active empirical research field was the introduction of benchmarks and an evaluation forum for entailment systems.

Our Proposal for RTE by Generality

We introduce the paradigm of TE by Generality, which can be defined as the entailment from a specific sentence towards a more general sentence. For example, from sentences (1) and (2)

extracted from RTE-1, we would easily state that (1) → (2) as their meaning is roughly the same although sentence (2) is more general than sentence (1).

• (1) Mexico City has a very bad pollution problem because the mountains around the city act as walls and block in dust and smog.

• (2) Poor air circulation out of the mountain-walled Mexico City aggravates pollution. et al., 2005;Glickman & Dagan, 2005;Perez et al., 2005).

Finally, we propose to avoid the definition of a "hard" threshold and study exhaustively asymmetry in language i.e. not just by the conditional probability as done in Glickman & Dagan (2005). For that purpose, we propose a new IAM called the AIS combined with different Association Measures.

Structure of the Thesis

The Thesis is structured as follows:

• Chapter 2 gives an overview of the research in TE, in particular, it focuses on the first five RTE Challenges (datasets and annotations, and relevant resources and tools).

• Chapter 3 describes the methodology for the creation of the corpus of pairs T-> H, to learn RTE by Generality, taking advantage of crowdsourcing. This corpus was created with the help of the CrowdFlower service1 which provides a crowdsourcing interface to MTurk 2 for non-US citizens.

• Chapter 4, the core of our work -our methodology, this chapter presents an IAM called the Simplified Asymmetric InfoSimba Similarity (AISs), which we combine with different AAM to recognize the specific case of TE by Generality. The AISs provides an unsupervised, languageindependent and threshold free solution.

• Chapter 5 reports extensively several experiments and respective results on three datasets. In this experiments, we extract MWU with SENTA and used the Stop Words lists.

• Chapter 6 concludes the Thesis drawing final remarks and suggesting directions for future improvements.

Structure of the Thesis

• Appendix A show Stop Words list in English 1 and show other Stop Words list in Portuguese 2 .

• Appendix B show two lists the MWU, in English and Portuguese, prepared for the first five RTE Challenges.

• Appendix C illustrates the submitted form to "Turkers" in CrowdFlower.

• Appendix D presents the Web frequencies for the calculations in the pair T -H in the section 4.5.

R W

"Never regard study as a duty, but as the enviable opportunity to learn to know the liberating influence of beauty in the realm of the spirit for your own personal joy and to the profit of the community to which your later work belongs."

Albert Einstein

This chapter presents the state of the art of the research in TE. Given the significant number of publications on this topic, we focus on a set of relevant works that are unsupervised and languageindependent.

Overview of the First Five RTE Challenges

The first three RTE competitions -RTE-1 relation holds:

• T: In the end, defeated, Antony committed suicide and so did Cleopatra, according to legend, by putting an asp to her breast.

• H: Cleopatra committed suicide.

At present, TE is considered an interesting and challenging topic within the NLP community, due to its many potential applications. The PASCAL Network promoted a generic evaluation framework covering semantic-oriented inferences for several NLP applications, which led to launch the RTE Challenge. Many research areas such as IE, QA, IE, text summarization and MT have to cope with different kinds of inference mechanisms, closely related to the entailment notion. In this direction, some works attempted to apply textual entailment to various NLP tasks in order to benefit from a semantic inference framework, and to potentially improve their performances (Glickman, 2009).

Datasets and Annotations

RTE-1

The set of Text -Hypothesis pairs used in the first RTE challenge was collected by human annotators. • TextMap Question Answering online demo, from the Information Sciences Institute 2 ;

It

• Relation Recognition dataset, from University of Illinois at Urbana-Champaign 3 ;

• DIRT paraphrase database (online demo), from the University of Southern California 4 ;

• The output of the TEASE system for extracting entailment relations and paraphrases (Szpektor et al., 2004);

Overview of the First Five RTE Challenges

• Corpus of aligned sentences extracted from monolingual comparable corpora, Columbia University1 .

A fraction of the examples were collected from the Web, focusing on the general news domain. In all cases the decision as to which example pairs to be included was made by the annotators. The annotators were guided to obtain a reasonable balance of different types of entailment phenomena and of levels of difficulty. Since many T -H pairs tend to be quite difficult to recognize, the annotators were biased to limit the proportion of difficult cases, but on the other hand to try avoiding high correlation between entailment and simple word overlap. It is interesting to note that more negative examples than positive ones were produced in the cases where T and H have a very high degree of lexical overlap (Dagan et al., 2005). Bellow are listed the specific routines followed for each application area.

• Collecting Information Retrieval (IR) pairs: Annotators generated hypotheses H that may correspond to meaningful IR queries that express some concrete semantic relations. These queries are typically longer and more specific than a standard keyword query. The queries were selected by examining prominent sentences in news stories, and then submitted to a web search engine. Candidate texts T were selected from the search engine's retrieved documents, picking candidate texts that either do or do not entail the hypothesis;

• Collecting Comparable Documents (CD) pairs: Annotators identified T -H pairs by examining a cluster of comparable news articles that cover a common story. They examined pairs of aligned sentences that overlap lexically, in which semantic entailment may or may not hold.

Some pairs were identified on the web using Google News 2 and others were taken from a corpus of aligned sentences. The motivation for this setting is the common use of lexical overlap as a hint for semantic overlap in comparable documents, e.g. for multi-document summarization;

• Collecting Reading Comprehension (RC) pairs: This task corresponds to a typical reading comprehension exercise in human language teaching, where students are asked to judge whether a particular statement can be inferred from a given text story. Annotators were asked to create such T -H pairs, that constitute an adequate reading comprehension test for high school students;

• Collecting Question Answering (QA) pairs: The TextMap Web Based Question Answering system, available online, was queried with questions taken from CLEF-QA and TREC, also the annotators were allowed to construct their own questions. For a given question, the annotators chose first a relevant text snippet T that was suggested by the system as including the correct answer. They then turned the question into an affirmative sentence with the hypothesized answer "plugged in" to form the hypothesis H.

RTE-2

The RTE-2 dataset consists of 1600 T -H pairs, divided into a development set and a test set, each containing 800 pairs. The texts T consist of 1 or 2 sentences, while the hypotheses H are usually made of a single short sentence. The focus here was on four out of the seven applications presented in RTE-1, namely IR, IE, QA, and multi-document summarization (equivalent to the CD task in RTE-1).

Within each application setting the annotators selected 100 of both positive entailment examples, where T does entail H, as well as negative examples, where entailment does not hold for total of 200 pairs. Each pair was annotated with its related task (IE/IR/QA/SUM) and entailment judgment.

A sample of the development set is given in Table 2.2. The examples in the dataset are based mostly on outputs (both correct and incorrect) of Web-based systems, while most of the input was sampled from existing application-specific benchmarks. Thus, the examples give some sense of how existing systems could benefit from an entailment engine postprocessing their output. This dataset was collected with regard to the following text processing applications:

• Collecting IE pairs: This task adapts the IE (and Relation Extraction) application settings to pairs of texts in contrast to text and a structured template. The pairs were generated using four different approaches. In the first approach, ACE-20041 relations were taken as templates for hypotheses. Relevant news articles were collected as texts T and then given to actual IE systems. The system outputs were used as hypotheses, generating both positive examples (from correct outputs) and negative examples (from incorrect outputs). In the second approach, the output of IE systems on a dataset of the MUC-4 2 was similarly used to create entailment pairs. the third subset consists of entailment pairs that were manually generated from the annotated MUC-4 dataset and news articles collected for the ACE relations. For example, given the ACE relation "X work for Y" and the text "An Afghan interpreter, employed by the United States, was also wounded.", a hypothesis "An interpreter worked for Afghanistan." is created, producing a non-entailing pair. In the forth approach, hypotheses which correspond to types of semantic relations not found in the ACE and MUC datasets were manually generated for sentences from the collected news articles. These relations were taken from various topic, such as sports, entertainment and science. All these processes simulate the need of IE systems to recognize that the given text indeed entails the semantic relation that is expected to hold between the candidate template slot fillers;

• Collecting IR pairs: In this application setting, the hypotheses are IR queries, which specify some statement, e.g. "Alzheimer's disease is treated using drugs". The hypotheses were adapted and simplified from standard IR evaluation datasets. For each hypothesis H several texts T that do or do not entail the hypothesis were selected from documents retrieved by different search engines (e.g. Google, Yahoo and MSN). In this application setting it is assumed that relevant documents should entail the given hypothesis;

• Collecting QA pairs: Annotators were given questions, taken from TRECQA 3 and QA@CLEF 4 datasets and the corresponding answers extracted from the Web by QA systems. Their task was to transform the question-answer pairs into text-hypothesis pairs following a two-stage routine:

First, the annotators picked from the answer passage an answer term, either a correct or an incorrect one. Then, the annotators turned the question into an affirmative sentence including the answer term. These affirmative sentences serve as the hypotheses H, and the original answer passage serves as the text T. For example, given the question "How many inhabitants does Slovenia have?" and an answer text "In other words, with its 2 million inhabitants, Slovenia has only 5.5 thousand professional soldiers" T, the annotators picked "2 million inhabitants"

as the correct answer term, which was used to turn the question into the statement "Slovenia In a cross-annotation process of the collected pairs each pair was judged by at least two annotators.

The average agreement on the test set, was 89.2%, which is an upper boundary of what could be expected from an entailment detection system. About 18% of the pairs were removed from the test set due to disagreement. The following situations often caused disagreement:

A number of reasons caused disagreement and bellow are listed some of the most permeative ones:

• T gives approximate numbers and H gives exact numbers;

• T states an asserted claim made by some entity, and the H drops the assertion and just states the claim. For example: T: "Scientists say that global warming is made worse by human beings.", H: "Global warming is made worse by human beings.";

• T makes a weak statement, and H makes a slightly stronger statement about the same thing.

Additional filtering was done which discarded pairs that seemed controversial, too difficult, or redundant. In this phase, about 256% of the original pairs were removed from the test set and minimal correction of texts was performed, e.g. fixing spelling and punctuation. et al., 2006) As in the previous challenges, the RTE-3 dataset consisted of 1600 text-hypothesis pairs, equally divided into a development set and a test set. While the length of the hypotheses H was the same as in the past datasets, a certain number of texts T were longer than in previous datasets.

ID

The longer texts were marked as L, after being selected automatically when exceeding 270 bytes.

In the test set they were about 17% of the total.

As in RTE-2, four applications -namely IE, IR, QA and SUM -were considered as settings or contexts for the pairs generation. 200 pairs were selected for each application in each dataset. Although the datasets were supposed to be perfectly balanced, the number of negative examples were slightly higher in both development and test sets (51.50% and 51.25% respectively; this was unintentional).

Positive entailment examples, where T entailed H, were annotated YES; the negative ones, where entailment did not hold, NO. Each pair was annotated with its related task (IE/IR/QA/SUM) and entailment judgment (YES/NO, obviously released only in the development set). Table 2.3 shows some examples taken from the development set.

As in RTE-2, human annotators generated T -H pairs within four application settings, following exactly the same process as used in RTE-2.

Each pair of the dataset was judged by three annotators. As in previous challenges, pairs on which the annotators disagreed were filtered-out. On the test set, the average agreement between each pair of annotators who shared at least 100 examples was 87.8%, with an average Kappa level of 0.75, regarded as substantial agreement according to Landis & Koch (1977).

19.2% of the pairs in the dataset were removed from the test set due to disagreement. The disagreement was generally due to the fact that the H was more specific than the T, for example because it contained more information, or made an absolute assertion where T proposed only a personal opinion. In addition, 9.4% of the remaining pairs were discarded, as they seemed controversial, too difficult, or too similar when compared to other pairs.

As far as the texts extracted from the web are concerned, spelling and punctuation errors were sometimes fixed by the annotators, but no major change was allowed, so that the language could be grammatically and stylistically imperfect. The hypotheses were finally double-checked by a native English speaker.

RTE-4

In RTE-4, in participating systems were assigned the task of RTE in a set of 1000 T -H pairs; i.e., they were required to decide, given a set of text pairs, called T and H, whether T entailed H or not.

Unlike the previous challenges, the main RTE-4 task asked the systems to make a three-way decision, further distinguishing, in case there was no entailment between T and H, whether the truth of H was contradicted by T, or remained unknown on the basis of the information contained in T.

In other words, the participating systems had to decided whether:

• T entailed H -in which case the pair was marked as ENTAILMENT;

• T contradicted H -in which case the pair was marked as CONTRADICTION;

• The truth of H could not be determined on the basis of T -in which case the pair was marked as UNKNOWN.

The classic two-way RTE task was also offered, in which the pairs where T entailed H were marked as ENTAILMENT, and those where the entailment did not hold were marked as NO ENTAILMENT. No development set was provided this challenges, as the pairs proposed were very similar to the ones contained in previous challenges development and test sets, which could therefore be used to train the systems.

Four application -namely IE, IR, QA and SUM -were considered as settings or contexts for the pairs generation. The length of the H ′ s was the same as in the past datasets; however, the T's were generally longer, following the decision taken last year of moving towards real cases where more discourse analysis is required. A major difference with respect to previous campaigns was that the RTE-4 dataset consisted of 1000 T -H pairs, instead of 800. This was due to the fact that while 200 pairs were selected for QA and SUM, 300 were chosen for IE and IR, as these two settings proved somewhat more difficult in the previous challenges. The distribution according to the 3 way annotation, both in the individual settings and in the overall test set, was as follows: 50%

ENTAILMENT, 35% UNKNOWN and 15% CONTRADICTION.

Overview of the First Five RTE Challenges

As usual, human annotators generated T -H pairs within the four aforementioned application settings, following exactly the same process as used in RTE-3.

As in previous challenges, each pair of the dataset was judged by three annotators. Pairs on which the annotators disagreed were discarded. The disagreement between annotators was often due to the fact that one annotator did not consider that some extra information was contained in the H, making it more specific than the T. In other cases, the disagreement was about whether the information in H was contradictory with respect to the content of T, or simply not sufficient to determine a judgment, especially in some ambiguous cases. Some pairs were also discarded because they were too similar to others, or their content was otherwise inappropriate.

Both texts and hypotheses were revised by native English speakers to eliminate the major spelling and grammar mistakes frequently present in texts taken from the web. No major changes were otherwise made, in order to keep the exercise realistic.

RTE-5

The RTE-5 was kept very similar to that proposed in RTE-4, in order to facilitate the comparison between the performances of systems which had participated in the previous challenges and encourage new participants to take part in an exercise not too different from last year's task. Nevertheless, some changes were introduced in order to move towards a more realistic exercise, stimulating researchers who had already participated in other RTE challenges to further test their systems against more challenging data sets.

First of all, while the length of the H ′ s was the same as in the past data sets (around 8 words), in the RTE-5 data set T ′ s were longer, up to 100 words, whereas in RTE-4 the average length was about 40 words. This length was meant to represent the average portion of the source document that a reader would naturally select, such as a paragraph or a group of related sentences. On the other hand, longer texts introduced in the exercise discourse phenomena, such as coreference, which were not present in the previous data sets. Moreover, texts, taken from a variety of freely available sources to avoid copyright problems, were not edited from their source documents. In this way, systems were asked to handle real text that may include typographical errors and ungrammatical sentences. For the rest, the basic structure of the challenge remained unchanged. Like in the previous RTE-4 challenge, both the classic two-way task and the three-way task were offered. In the traditional two-way task the pairs where T entails H are marked as ENTAILMENT, and those where the entailment does not hold are marked as NO ENTAILMENT.

The three-way task requires to further distinguish, in case there is no entailment between T and H, whether the truth of H is contradicted by T, or remains unknown on the basis of the information contained in T. In other words, the systems participating in the three-way task have to decide Volvo is a car manufacturer from Finland.

CONTRADICTION

Overview of the First Five RTE Challenges

The settings from which the pairs were manually created by human annotators were IE, IR, QA.

SUM was not considered in this challenge, as the Pilot Search data sets were entirely based on the Summarization setting. As in the previous challenges, the overall process of data set creation requires the generation of large amounts of T -H pairs, which are subsequently filtered to retain only those (i) featuring full agreement among three annotators in terms of the assigned entailment judgment, and (ii) compliant with the RTE guidelines for the creation of entailment pairs. The effort required to create the pairs varies a lot depending on the application scenario (being the QA pairs the most difficult to create and the IR pairs the easiest ones), and the type of entailment pair to be created (entailment, unknown, contradiction).

On average, six pairs per hour are created and annotated for the first time by an expert annotator.

The subsequent entailment annotation of the existing pairs is much less time-consuming, as forty pairs per hour can be annotated.

As regards the RTE-5 data set, around 25% of the pairs originally created were discarded due to disagreement, and another 20% because they were unsuitable according to the guidelines (e.g. T ′ s too short or too long, ENTAILMENT pairs with the elements relevant to the entailment judgment repeated verbatim, or UNKNOWN pairs with T and H completely unrelated).

Summary

From its beginning in 2005, the task of RTE has evolved significantly, although its basic structure has been maintained in the years. In the first three challenges the task consisted of assigning a two-way entailment judgment (YES/NO) to a set of T -H pairs. In RTE-4 and RTE-5 an additional 3-way judgment task was proposed together with the original one. In this task, in case of no entailment between T and H, systems have to specify whether T contradicts H (CONTRADICTION judgment), or the truth of H cannot be determined on the basis of T (UNKNOWN judgment).

In all the editions of the Challenge, the T -H pairs were created by expert annotators from a number of NLP application settings. In the first challenge the applications considered were IR, CD, RC,QA, IE, MT and PP. In the following three challenges they were limited to IE, IR, QA, and SUM. In RTE-5 only IE, IR and QA were considered.

Table 2.6 shows how the composition of the data sets evolved over the years, in terms of number of pairs, T and H length, and word overlap between T and H. As far as the length of T and H is concerned, while H ′ s length remained constant over the years, the length of T ′ s substantially increased, passing from an average of 24.78 words in the RTE-1 Development set to around 100 words in the RTE-5 data sets. This gradual change to longer texts allowed for the introduction of discourse phenomena in the data set, which represented a first step towards the more realistic scenario proposed in the RTE-5 Search Pilot Task, where TE was performed against a real corpus.

Table 2.6 also shows data about the average word overlap between T and H, which is calculated counting all the words shared by T and H, and normalizing the results by the length of H. Overlap rates are grouped on the basis of the entailment judgment (YES/NO) assigned to the pairs. In general, it can be seen that positive examples (entailment=YES) show a higher word overlap with respect to the negative ones. Moreover, it is interesting to analyze the difference in word overlap between positive and negative pairs. This difference steadily increased over the years, reaching its highest value in the RTE-3 data sets, where the average overlap for positive pairs amounts to 71% whereas for negative pairs it amounts to 54%. This suggests that, for systems taking word overlap into account, the RTE-3 data set is potentially easier to process.

RTE

Relevant Resources and Tools

Evaluation Measures

The evaluation of all runs submitted was automatic, the judgments returned by the system being compared to the Gold Standard compiled by the human assessors. The main evaluation measure was accuracy, i.e., the fraction of correct answers. For the two-way task, a judgment of "NO ENTAIL-MENT" in a submitted run was considered to match either "CONTRADICTION" or "UNKNOWN" in the Gold Standard.

As a second measure, an Average Precision score was computed for systems that provided as output a confidence-ranked list of all test examples. Average Precision is a common evaluation measure for system rankings, and is computed as the average of the system's precision values at all points in the ranked list in which recall increases, that is at all points in the ranked list for which the gold standard annotation is ENTAILMENT. In other words, this measure evaluates the ability of systems to rank all the T -H pairs in the test set according to their entailment confidence (in decreasing order from the most certain entailment to the least certain). More formally, it can be written as follows:

1

R n ∑ i=1 E(i) × ♯EntailmentU pT pPair(i) i (2.1)
where n is the number of the pairs in the test set, R is the total number of ENTAILMENT pairs in the Gold Standard, E(i) is 1 if the ith pair is marked as ENTAILMENT in the Gold Standard and 0 otherwise, and i ranges over the pairs, ordered by their ranking.

In practice, the more confident the system was that T entailed H, the higher the ranking of the pair was. A perfect ranking would have placed all the positive pairs (for which the entailment holds) before all the negative ones, yielding an average precision value of 1. As average precision is relevant only for a binary annotation, in the case of three-way judgment submissions the pairs tagged as CONTRADICTION and UNKNOWN were conflated an retagged as NO ENTAILMENT.

First Challenge

In an overview of the systems participating in the first RTE challenge In

Second Challenge

In the second edition, of 2006, the main directions were generally the same, only algorithms were more sophisticatedly and also the results were better (average precision grew up from 55.12 % in 2005 to 58.62 % in 2006). New directions are related to semantic role labelling (Hickl et al., 2006), Machine Learning classification, using of background knowledge (Tatu et al., 2006) acquisition of entailment corpora (Hickl et al., 2006). Some groups tried to detect non entailment, by looking for various kinds of mismatch between the text and the hypothesis. Logic inference can be considered as one of the most direct approaches to the entailment problem.

Participants Accuracy

System

Tatu et al. (2006) transformed two text snippets into three-layered semantically-rich logic form representations, generates an abundant set of lexical, syntactic, semantic, and world knowledge axioms and, iteratively, searches for a proof for the entailment between the text T and a possibly relaxed version of the hypothesis H. They could improve the performance of their system using the lexical inference system in combination with their logical approach.

The system described in Zanzotto et al. (2006) defines a cross-pair similarity measure based on the syntactic trees of T and H, and combines such similarity with traditional intra-pair similarities to define a novel semantic kernel function. The intuition behind this approach is that not only intrapair similarity between T and H, but also cross-pair similarity between two pairs can be useful to address the problem. The latter similarity measure along with a set of annotated examples is used by a learning algorithm to automatically derive syntactic and lexical rules to solve complex entailment cases.

Adams et al. (2006) presents a system of TE based primarily on the concept of lexical overlap. The system begins with a bag of words similarity overlap measure, derived from a combination of Word-NetMiller (1995) lexical chains to form a mapping of terms in the hypothesis to the source text. It then looks for negations not found in the mapping, and for the lexical edit distance of the mapping.

These items are then entered into a decision tree to determine the overall entailment.

One of the first efforts to combine shallow NLP methods with a deep semantic analysis was made by Bos (2005). In RTE-2, Bos & Markert (2006) combined two approaches, a shallow method based mainly on word-overlap and a method based on logical inference, using first-order theorem proving and model building techniques. They used a machine learning technique to combine features from both methods.

Third Challenge

In et al., 1999) which provides a large number of world knowledge axioms, event and temporal information provided by the Temporal Awareness and Reasoning Systems for Question Interpretation (TARSQI) 2 toolkit, logic form representations of events, negation, coreference and context, and new improve-ments of lexical chain axiom generation.

(2007) 0,800 X X X X X X Tatu & Moldovan (2007) 0,723 X X X X Iftene & Balahur- Dobrescu (2007) 0,691 X X X Adams et al. (2007) 0,670 X X X X Wang & Neumann (2007) 0,669 X X
In order to boost the similarity scores and extend them to a different level, Iftene & Balahur-Dobrescu ( 2007) compared H ′ s parse tree against subtrees of T ′ s parse tree. They transformed the hypothesis making use of an extensive semantic knowledge from sources like Discovery of Inference Rules from Text (DIRT) (Lin & Pantel, 2001), WordNet, Wikipedia1 and a database of acronyms. Additionally, they took advantage of hand coded complex grammar rules for rephrasing in English.

In Adams et al. (2007), two textual entailment approaches are presented. The first one is based primarily on the concept of lexical overlap, considering a bag-of-words similarity overlap measure to form a mapping of terms in the hypothesis to the source text. The second system is a lexico-semantic matching between the text and the hypothesis that attempts an alignment between chunks in the hypothesis and chunks in the text, and a representation of the text and hypothesis as two dependency graphs. Both approaches employ decision trees as a supervised learning algorithm.

The system presented in Wang & Neumann (2007) has moved from a puristic syntactic approach, in the sense that they only performed dependency parser, to the development of specialized RTEmodules capable of tackling more entailment phenomena. They present a novel approach to RTE that exploits a structure-oriented sentence representation followed by a similarity function. The structural features are automatically acquired from tree skeletons that are extracted and generalized from dependency trees. Their method makes use of a limited size of training data without any external knowledge bases or handcrafted inference rules. For preprocessing, they use a PoS tagger, a dependency parser 2 , and a Named Entity (NE) recognizer 3 in order to annotate the original plain texts. The Precision-Oriented (PO) modules are created to specialize the system in the RTE task.

Fourth Challenge

Inside the different approaches to TE, the use of ML approaches is dominant. This is mainly because both logic and rule-based methods suffer from either limited coverage of hand-crafted rules and lower performance. In ML approaches, a variety of features including lexical, syntactic and semantic The main idea in Iftene ( 2008) is to map every word from hypothesis to one or more words from the text. For that, this system transform the hypothesis making use of extensive semantic knowledge from sources like DIRT, WordNetMiller (1995), VerbOcean 4 , Wikipedia and a database of acronyms.

Overview of the First Five RTE Challenges

After the mapping process, they associate a local fitness value to every word from hypothesis, which The approach proposed in Wang & Neumann ( 2008) is based on constructing structural features from the abstract tree descriptions, which are automatically extracted from syntactic dependency trees of T and H. These features are then applied by a subsequence-kernel-based classifier that learns to decide whether the entailment relation holds between two texts. A divide-and-conquer architecture is then in charge of providing a set of specific RTE methods (namely: temporal anchors, named entities and noun phrase anchors), and then combine them applying a voting scheme in order to maximize the accuracy. In Li et al. (2008), they design different strategies to recognize true entailment and false entailment. The similarity between hypothesis and text is measured to recognize true entailment.

They detect the exact entity and relation mismatch to recognize the false entailment.

The RTE system presented in Balahur et al. (2008) tackles the entailment phenomenon from two different points of view. First, they build the system's core by means of several lexical measures and further on, they add some semantic constraints that they think are appropriated for the entailment recognition. The reason for creating this core was given by (i) the fact that the integration of more complex semantic knowledge is a delicate task and it would be easier if they had a solid base system; and (ii) although the proposed core needs some language dependent tools (e.g. lemmatizer, stemmer), it could be easily ported to other languages.

Fifth Challenge

In this challenge the best result for two way is Iftene & Moruz ( 2009), the main idea of they system is to map every word in the hypothesis to one or more words in the text. For that, they transform the hypothesis, using extensive semantic knowledge from sources (as previous RTE). The main improvement this challenge was related to the pre-processing part, the texts were obtained from a variety of sources and were not edited from their source documents, they focused on this part.

Thus, they identify and eliminate special characters that occur frequently on web pages. This choice is based on the fact that with or without these characters the meaning of the text is the same, but the quality of the tools output is improved. Additionally, they process the LingPipe1 output with GATE Cunningham et al. (2002) in order to identify some named entities categories unidentified by LingPipe such as nationality, language, and job.

In Wang et al. (2009) propose a joint syntactic-semantic representation to better capture the key information shared by the pair, and also apply a co-reference resolver to group cross-sentential mentionings of the same entities together.

In First, for several values of n (typically from 1 to 4), they calculate the percentage of n-grams from the text T, which appear in the hypothesis H. The frequency of each n-gram is limited to the maximum frequency with which it appears in any text T. Then, they combine the marks obtained for each value of n, as a weighted linear average and finally apply a brevity factor to penalize short texts T. The output of BLEU is then taken as the confidence score. Finally, they perform an optimization procedure to choose the best threshold according to the percentage of success of correctly recognized entailments. The value obtained was 0.157. Thus, if the BLEU output is higher than 0.157, the entailment is marked as true, otherwise as false. This procedure achieves 0, 495 of accuracy in recognizing TE.

In Bayer et al. (2005) the entailment data is treated as an aligned translation corpus. In particular, they use the GIZA++ toolkit (Och & Ney, 2003) to induce alignment models. However, the alignment scores alone were next to useless for the RTE-1 development data, predicting entailment correctly only slightly above chance. As a consequence, they introduced a combination of metrics intended to measure translation quality. Finally, they combined all the alignment information and string metrics with the classical K -NN classifier to choose, for each test pair, the dominant truth value among the five nearest neighbors in the development set. This method achieves 0, 586 of accuracy.

The most interesting work is certainly the one described in Glickman & Dagan (2005) who propose a general probabilistic setting that formalizes the notion of TE. Here, they focus on identifying when the lexical elements of a textual hypothesis H are inferred from a given text T. The probability of lexical entailment is derived from Equation 2.2 where hits(., .) is a function that returns the number of documents, which contain its arguments.

2.2 Unsupervised Language-Independent Methodologies for RTE

P(H|T) = ∏ u∈H max v∈T hits(u, v) hits(v) (2.2)
The text and hypothesis of all pairs in the development and test sets were tokenized and stop words were removed to empirically tune a decision threshold, λ. Thus, for a pair T -H, they tagged an example as true (i.e. entailment holds) if P(H|T) > λ, and as false otherwise. The threshold was empirically set to 0.005. With this method accuracy of 0, 586 is achieved. The best results from these three approaches are obtained by Glickman & Dagan (2005), who introduce the notion of asymmetry within their model without clearly mentioning it. The underlying idea is based on the fact that for each word in H, the best asymmetrically co-occurring word in T is chosen to evaluate P(H|T). Although all three approaches show interesting properties, they all depend on tuned thresholds, which can not reliably be reproduced and need to be changed for each new application.

Moreover, they need training data, which may not be available. Our idea aims at generalizing the hypothesis made by Glickman & Dagan (2005). Indeed, their methodology is only based on one pair (u, v), ∀u and does not take into account the fact that many pairs i.e. (u, v), ∃v∀u may help the decision process. Moreover, they do not propose a solution for the case where the ratio hits(u,v) hits(v) is null. Finally, we propose to avoid the definition of a "hard" threshold and study exhaustively asymmetry in language i.e. not just by the conditional probability as done in Glickman & Dagan (2005).

For that purpose, we propose a new IAM called the AIS combined with different Association Measures. But when I believe I can, then I acquire the ability to do it even if I didn't have it in the beginning."

Mahatma Gandhi

In this chapter we detail our methodology for building a specialized corpus needed to evaluate our approach to identify entailment by generality in pairs of sentences. For this task, we use the technique of crowdsourcing, through the CrowdFlower service, which appears to be an excellent medium for large scale manual annotation.

Crowdsourcing

Large scale annotation projects such as TreeBank (Marcus et al., 1993), PropBank (Palmer et al., 2005), TimeBank (Pustejovsky et al., 2003), FrameNet (Baker et al., 1998), SemCor (Miller et al., 1993), and others play an important role in NLP research, encouraging the development of novel ideas, tasks, and algorithms. The construction of these datasets, however, is extremely expensive in both annotator-hours and financial cost. Since the performance of many NLP tasks is limited by the amount and quality of data available to them (Banko & Brill, 2001), one promising alternative for some tasks is the collection of non-expert annotations.

The availability and the increasing popularity of crowdsourcing services have been considered as an interesting opportunity to meet the aforementioned needs and design criteria.

One of the most popular crowdsourcing services is MTurk 1 , "[…] a crowdsourcing Internet marketplace that enables computer programmers (known as Requesters) to co-ordinate the use of human intelligence to perform tasks which computers are unable to do […] The Requesters are able to pose tasks known as HITs (Human Intelligence Tasks) […] Workers [also known as "Turkers"] can then browse among existing tasks and complete them for a monetary payment set by the Requester. To place HITs, the requesting programs use an open Application Programming Interface […] Requesters

can ask that Workers fulfill Qualifications before engaging a task, and they can set up a test in order to verify the Qualification. They can also accept or reject the result sent by the Worker, which reflects on the Worker's reputation" 1 .

Crowdsourcing services have been recently used with success for a variety of NLP applications (Callison-Burch & Dredze, 2010). Although MTurk is directly accessible only to US citizens, the CrowdFlower service 2 provides a crowdsourcing interface to MTurk for non-US citizens.

The main idea in using crowdsourcing to create NLP resources is that the acquisition and annotation of large datasets, needed to train and evaluate NLP tools and applications, can be carried out in a cost-effective manner by defining simple Human Intelligence Tasks (HITs) routed to a crowd of non-expert workers, called "Turkers", hired through on-line marketplaces. Figure 3.1 illustrates the MTurk process 3 .

Quality Control of Crowdsourced Data

The design of a data acquisition HITs has to take into account several factors, each having a considerable impact on the difficulty of instructing the workers, the quality and quantity of the collected data, the time and overall costs of the acquisition. In our particular case, Turkers are presented with the task of labeling input data referring to a fixed set of possible values (i.e. making a choice between multiple alternatives).

For annotation jobs, quality control mechanisms can be easily set up by calculating Turkers agreement, by applying voting schemes, or by adding hidden gold units (or test questions) to the data to be annotated. CrowdFlower provides means to check workers reliability, and weed out untrusted ones without money waste. This is achieved by adding hidden gold standard units in the 1 Taken from http://en.wikipedia.org/wiki/Amazon_Mechanical_Turk [Last access: 14 th December, 2013] 2 http://crowdflower.com/ [Last access: 14 th December, 2013] 3 Source: https://requestersandbox.mturk.com/tour/how_it_works [Last access: 14 th December, 2013]

Building Methodology

data to be annotated. For that purpose, we annotated 260 pairs that constitute our gold units1 .

As regards textual entailment, the first work exploring the use of crowdsourcing services for data annotation is Snow et al. (2008), which shows high agreement between non-expert annotations of the RTE-1 dataset and existing gold standard labels assigned by expert annotators.

Building Methodology

Our approach builds on a pipeline of HITs routed to MTurk workforce through the CrowdFlower interface. The objective is to collect T -H pairs where entailment by generality holds.

Our building methodology has several stages, first we select the positive pairs of TE from the first five RTE challenges. These pairs are then submitted to CrowdFlower through a job that we have built online (see Appendix C), to be evaluated by "Turkers" 2 . In CrowdFlower each T -H pair is a unit.

The "Turkers" are asked to select either one of "Entailment by Generality", "Entailment, but not Generality" or "Other" whichever is most appropriate for the T -H pair under consideration (see Appendix C).

In the end we built our form, we calibrate and parametrize our job (sample, see figure 3.2). We define the following parameters 3 :

• "Gold Units"

• "Data Settings" -Make Your Data Public -"This data may be used by the public for research purposes. By checking this box, you agree to the Terms of Service."

• "Skill Requirements" -Bronze -"Bronze contributors are trusted contributors within our system. There are approximately 20,000 contributors in this group. Among other qualifying criteria, all Bronze contributors have seen at least 100 Gold units, and have achieved at least 80% accuracy on these units."

• "Task Settings" -Judgments per unit -"This is the number of trusted judgments we will collect for each of your units.Gold units will receive a higher number of judgments." -Units per page -"This is the number of units that contributors will see on each page."

• "Contributor Pay" -Seconds per unit -"This is the number of seconds you think it will take the average contributor to complete a single unit on a page. This is only used to estimate how much contributors can earn per hour on this task. (They will not see this estimate.)" -Payment per page (cents) Once calibrated and parameterized, we add money to our account of CrowdFlower, to submit our job for evaluation.

Quantitative Analysis

When the Turkers provide the required number of trusted judgments and therefore finish the job, there is available a list of reports, Figure 3.4, to be further analyzed. T -H pair was the most favored one, where each pair can be classified as either "Entailment by Generality", "Entailment, but not Generality" or "Other" and respectively level of inter-annotator agreement. It is this report from which we build our corpus of "Entailment by Generality" T -H pairs.

Quantitative Analysis

Table 3.1 summarizes the work involved in the annotation of the entailment cases of RTE-1 through RTE-5 datasets with "Entailment by Generality", "Entailment, but not Generality" and "Other" labels. We uploaded 20001 T -H pairs known to be in entailment relation. Of those, 1740 were submitted for evaluation and 260 were "Gold" pairs.

O M RTE G

"What ever the mind of man can conceive and believe, it can achieve. "

Napoleon Hill

This chapter describes our approach to the problem of recognizing textual entailment by generality.

In this, we treat a sentence as a string of lexical units or tokens. It turns out that there are different ways to tokenize and below we describe few of them. We will see in the following chapter that they possess interesting properties in the context of this work.

Contextual Word Similarity

A prerequisite of any language-independent NLP methodology is the capability to extract implicit and explicit knowledge from raw natural language texts as the basic textual information.

Two different types of knowledge can be acquired depending on the basic textual unit under study.

On the one hand, analyzing word similarities evidences intrinsic knowledge about the language (i.e.

information about the language which is not explicitly encoded in texts). Traditional examples are collocations and word semantic relations such as hypernymy/hyponymy, meronymy/holonymy, synonymy or antonymy, which must be mined from texts. On the other hand, explicit knowledge about the language (i.e. information about the message conveyed by the texts) can be extracted from the evaluation of sentence, passage and text similarities1 . There are obviously some exceptions. In particular, analyzing sentence similarities in the context of topic segmentation is likely to identify intrinsic knowledge about discourse structure (Dias et al., 2007).

Identifying different types of similarities between words has been an important goal in NLP. Usually it is achieved through some statistical approach for computing the degree of similarity between unit representation in an appropriate feature space. In this approach a word is represented by a word co-occurrence vector in which each entry corresponds to another word in the lexicon. The value of an entry specifies the frequency of joint occurrence of the two words in the corpus, that is, the frequency with which they co-occur within some particular relationships in the text. The degree of similarity between a pair of words is then computed by some similarity or distance measure that is applied to the corresponding pair of vectors.

Applications of Word Similarity

The concept of word similarity was traditionally captured within thesauri. A thesaurus is a lexicographic resource that specifies semantic relationships between words, listing for each word related words such as synonyms, hyponyms and hypernyms. Thesauri have been used to assist writers in selecting appropriate words and terms and in enriching the vocabulary of a text. To this end, modern word processors provide a thesaurus as a built in tool.

The area of IR has provided a new application for word similarity in the framework of query expansion. Good free-text retrieval queries are difficult to formulate since the same concept may be denoted in the text by different words and terms. Query expansion is a technique in which a query is expanded with terms that are related to the original terms that were given by the user, in order to improve the quality of the query. Various query expansion methods have been implemented, both by researchers and in commercial systems, that rely on manually crafted thesauri or on statistical measures for word similarity.

Word similarity may also be useful for disambiguation and language modeling in the area of NLP and speech processing. Many disambiguation methods and language models rely on word co-occurrence statistics that are used to estimate the likelihood of alternative interpretations of a natural language utterance (in speech or text). Due to data sparseness, though, the likelihood of many word co-occurrences cannot be estimated reliably from a corpus, in which case statistics about similar words may be helpful.

Consider for example the following utterances, which may be misinterpreted by a speech recognizer.

• a. The bear ran away.

• b. The pear ran away.

A typical language model may prefer the first utterance if the word co-occurrence bear ran was encountered in a training corpus while the alternative co-occurrence pear ran was not. However, due to data sparseness it is quite likely that neither of the two alternative interpretations was encountered in the training corpus. In such cases information about word similarity may be helpful.

Knowing that bear is similar to other animals may help us collect statistics to support the hypothesis that animal names can precede the verb ran. On the other hand, the names of other fruits, which are known to be similar to the word pear, are not likely to precede this verb in any training corpus.

This type of reasoning was attempted in various disambiguation methods, where the source of word

Contextual Word Similarity

similarity was either statistical (Dagan et al., 1993;Essen & Steinbiss, 1992;Grishman & Sterling, 1993;Grishman et al., 1986;Karov & Edelman, 1996;Lin, 1997;Schütze, 1992Schütze, , 1993) ) or a manually crafted thesaurus (Jiang & Conrath, 1997;Resnik, 1995).

It should be noted that while all the applications mentioned above are based on some notion of "word similarity" the appropriate type of similarity relationship might vary. A thesaurus intended for writing assistance should identify words that resemble each other in their meaning, like aircraft and airplane, which may be substituted for each other.

For query expansion, on the other hand, it is also useful to identify contextually related words, like aircraft and airline, which may both appear in relevant target documents. Co-occurrence-based disambiguation methods would benefit from identifying words that have similar co-occurrence patterns. These might be words that resemble each other in their meaning, but may also have opposite meanings, like increase and decrease.

Co-occurrence relations

In the corpus-based framework a word is represented by data about its joint co-occurrence with other words in the corpus. Different types of co-occurrence relationships have been examined in the literature, for computing word similarity as well as for other applications. These relationships may be classified into two general types: grammatical relations, which refer to the co-occurrence of words within specified syntactic relations, and non-grammatical relations, which refer to the cooccurrence of words within a certain distance (window) in the text. As will be discussed below, the types of relations used in a particular word similarity system will affect the types of similarity that will be identified.

Non-grammatical relations

Non-grammatical co-occurrence relations refer to the joint occurrence of words within a certain distance (window) in the text. This broad definition captures several sub-types of co-occurrence relations such as n-grams, directional and non-directional co-occurrence within small windows, and co-occurrence within large windows or within a document.

An n-gram is a sequence of n words that appear consecutively in the text. N-gram models are used extensively in language modeling for automatic speech recognition systems, as well as in other recognition and disambiguation tasks. In an n-gram model the probability of an occurrence of a word in a sentence is approximated by its probability of occurrence within a short sequence of n words. Typically sequences of two or three words (bigrams or trigrams) are used, and their probabilities are estimated from a large corpus. These probabilities are combined to estimate the a priori probability of alternative acoustic interpretations of the utterance in order to select the most probable interpretation.

The information captured by n-grams is, to a large extent, only an indirect reflection of lexical, syntactic and semantic relationships in the language. This is because the production of consecutive sequences of words is a result of more complex linguistic structures. However, n-grams have been shown to have practical advantages for several reasons: it is easy to formulate probabilistic models for them, they are very easy to extract from a corpus, and, above all, they have proved to provide useful probability estimations for alternative readings of the input.

Word similarity methods that are based on bigram relationships were tried for addressing the data sparseness problem in n-gram language modeling (Dagan et al., 1994;Essen & Steinbiss, 1992).

Word-similarities that are obtained by n-gram data may reflect a mixture of syntactic, semantic, and contextual similarities, as these are the types of relationships represented by n-grams. Such similarities are suitable for improving an n-gram language model, which, by itself, mixes these types of information.

A co-occurrence of words within a relatively large window in the text suggests that both words are related to the general topic discussed in the text. This hypothesis will usually hold for frequent co-occurrences, that is, for pairs of words that often co-occur in the same text. A special case for this type of relationship is co-occurrence within the entire document, which corresponds to a maximal window size.

Co-occurrence within large windows was used in the work of Gale et al. (1992) on word-sense disambiguation. In this work co-occurrence within a maximal distance of 50 words in each direction was considered. A window of this size captures context words that identify the topic of discourse. Word co-occurrence within a wide context was used also for language modeling in speech recognition,

where the occurrence of a word affects the probability of other words in the larger context. In the context of computing word similarity, co-occurrence within a large window may yield topical similarities between words that tend to appear in similar contexts.

Co-occurrence of words within a small window captures a mixture of grammatical relations and topical co-occurrences. Typically, only co-occurrence of content words is considered since these words carry most semantic information. Smadja (1993) used co-occurrence within a small window as an approximation for identifying significant grammatical relations without using a parser. His proposal relies on an earlier observation that 98% of the occurrences of syntactic relations relate words that are separated by at most five words within a single sentence (Martin et al., 1983). Smadja (1993) used this fact to extract lexical collocations, and applied the extracted data to language generation and information retrieval. Dagan et al. (1993) use this type of data as a practical approximation for extracting syntactic relationships. To improve the quality of the approximation, the direction of co-occurrence is considered, distinguishing between co-occurrences with words that appear to the left or to the right of the given word. The extracted data is used to compute word similarities, which capture both semantic similarities, as when using grammatical relations, but also some topical similarities, as when using co-occurrence within a larger context.

Another variant of co-occurrence within a small window appears in the work of Brown et al. (1991).

They use a part-of-speech tagger to identify relations such as "the first verb to the right" or "the

Contextual Word Similarity

first noun to the left", and then use these relations for word-sense disambiguation in MT. This type of relationship provides a better approximation for syntactically motivated relations while relying only on a part of speech tagger, which is a simpler resource compared to syntactic parsers.

Asymmetric Word Similarities

New trends have recently emerged with the study of asymmetric measures (Michelbacher et al., 2007). The idea of an Asymmetric Association Measures (AAM) is inspired by the fact that within the human mind, association between two words or concepts is not always symmetric. For pairs like fruit and apple, one would agree that there is a strong mutual association between the two. When thinking of fruit, it is not very far-fetched to think of apple as well and vice versa. There are other pairs, however, that do not exhibit this kind of strong association in both directions. Think of the pair fruit and mango, for example. Mango is probably not the first thing that comes to one's mind when hearing the word fruit. On the other hand, mango is strongly associated with the concept of a

fruit. An example from Michelbacher et al. (2007) reads: "there is a tendency for a strong forward association from a specific term like adenocarcinoma to the more general term cancer, whereas the association from cancer to adenocarcinoma is weak". According to Michelbacher et al. (2007), this idea bears some resemblance to the prototype theory (Rosch, 1973), where objects are regarded as members of different categories. Some members of the same category are more central than others making them more prototypical of the category they belong to. For instance, cancer would be more central than adenocarcinoma. However, we deeply believe that the main background for the direction of association lies in the notion of specific and general terms. Indeed, it is clear that there exists a tendency for a strong forward association from a specific term to the more general term but the backwards association is weaker. Within this scope, several recent works have proposed the use of asymmetric similarity measures. We believe that this idea has the potential to bring about significant improvements in the acquisition of word semantic relations.

Asymmetric Association Measures

Pattern-based measures can embody asymmetry as they were initially defined to discover the hypernymy/hyponymy relation. But, Ohshima & Tanaka ( 2009) is certainly the approach that makes the most of asymmetric patterns. Indeed, instantiating and sending to a search engine a number of patterns filled only with one possible candidate may guarantee the extraction of hypernymy/hyponymy or meronymy/holonymy relations if asymmetric patterns exist. However, we know that pattern-based measures are sensitive to word polysemy and pattern ambiguity. Moreover, they are language-dependent techniques which are difficult to replicate for different languages.

In order to stay within the domain of language-independent and unsupervised methodologies a number of asymmetric association measures have been proposed (Pecina & Schlesinger, 2006;Tan et al., 2004) (2007) propose two different measures to model the notion of asymmetric association. Their intent is to determine to what extent these two measures of directed association can be used as a model for directed psychological association in the human mind. These two measures are the plain conditional probability and the ranking measure R(.∥.) based on the Pearson's χ 2 test. In particular, let t i , i = 1 . . . n be the list of all terms which co-occur with term t ordered with respect to the value χ 2 (t, t i ). Then R(t i ∥t) is the rank of term t i in this list. The results were evaluated against a large number of free association norms, collected from human subjects, and they found that the measures were able to distinguish between highly symmetric and highly asymmetric pairs to some extent, but the overall accuracy in predicting the degree of asymmetry was low.

In the specific domain of word order discovery, Dias et al. (2008) propose a methodology based on directed graphs and the TextRank algorithm (Mihalcea & Tarau, 2004) to automatically induce a general-specific word order for a given vocabulary based on Web corpora frequency counts. A directed graph is obtained by keeping the edge, which corresponds to the maximum value of the asymmetric association measure between two words. Then, the TextRank is applied and produces an ordered list of nouns, on a continuous scale, from the most general to the most specific. Eight of the AAM used in that work will be evaluated in the context of asymmetric similarity between sentences: the Added Value (Equation 4.2), the Braun-Blanket (Equation 4.3), the Certainty Factor (Equation 4.4), the Conviction (Equation 4.5), the Gini Index (Equation 4.6), the J-measure (Equation 4.7), the Laplace (Equation 4.8) and the Conditional Probability (Equation 4.1).

Contextual Word Similarity

AV(x∥y) = P(x|y) -P(x).

(4.2)

BB(x∥y) = f (x, y) f (x, y) + f ( x, y)
. (4.7)

LP(x∥y) = N × P(x, y) + 1 N × P(y) + 2 .
(4.8)

Asymmetric Attributional Word Similarities

In Dias (2010) it was noted that it is unjustified from linguistic point of view to assume all the dimensions of a vector space model to be orthogonal to each other. Since each dimension typically corresponds to a context word, this is equivalent to the assumption that every two words denote disparate meanings. Apparently, such a vector space model fails to account adequately for contexts that are similar in meaning or synonymous.

The InfoSimba Similarity (IS) aims to measure the correlations between all the pairs of words in two word context vectors instead of just relying on their exact match as with the cosine similarity measure (Equation 4.9). Further, IS guarantees to catch similarity between pairs of words, even when they do not share contexts, due to data sparseness for example, nevertheless they have similar contexts. It is defined in Equation 4.10 where S(., .) is any symmetric similarity measure and each W ij corresponds to the attribute word at the j th position in the vector X i , p is the length of the vector X i .

cos(X i , X j ) = ∑ p k=1 X ik × X jk √ ∑ p k=1 X 2 ik × √ ∑ p k=1 X 2 jk .
(4.9)

IS(X i , X j ) = ∑ p k=1 ∑ p l=1 X ik × X jl × S(W ik , W jl )      ∑ p k=1 ∑ p l=1 X ik × X il × S(W ik , W il )+ ∑ p k=1 ∑ p l=1 X jk × X jk × S(W jk , W jl )- ∑ p k=1 ∑ p l=1 X ik × X jl × S(W ik , W jl )      . (4.10)
In the context of asymmetric attributional word similarities research (Freitag et al., 2005;Lund et al., 1995) the directions of co-occurrences is noted and exploited, but there does not exist an in-depth study neither a theoretical account of this phenomenon. The efforts are directed towards developing asymmetric distributional similarity measures such as the Kullback-Leibler divergence (Kullback & Leibler, 1951) defined in Equation 4.11 where A = {⟨z, r⟩|∃(x, z, r) ∧ ⟨z, r⟩|∃(y, z, r)}, which has been regularly set apart from the Jensen-Shannon divergence (Menéndez et al., 1997), its symmetric counterpart. We can also point at the cross entropy described in Pecina & Schlesinger (2006). (2008). Indeed, they generally capture the direction of association between two words based on document contexts and only take into account a loose semantic proximity between words. For example, it is highly probable to find that Apple is more general than iPad, which can not be assimilated to an hypernymy/hyponymy or meronymy/holonymy relation. On the other hand, asymmetric attributional word similarities only take into account common contexts to assess the degree of asymmetric relatedness between two words. To leverage these issues, in AIS measure, which underlying idea is to say that one word x is semantically related to word y and x is more general than y, if x and y share as many relevant related words as possible and each context word of x is likely to be more general than most of the context words of y. The AIS is defined in Equation 4.12, where AS(.∥.) is any asymmetric similarity measure, likewise for the IS in Equation AISs(.∥.) in 4.13.

AIS(X i ∥X j ) = ∑ p k=1 ∑ p l=1 X ik × X jl × AS(W ik ∥W jl )      ∑ p k=1 ∑ p l=1 X ik × X il × AS(W ik ∥W il )+ ∑ p k=1 ∑ p l=1 X jk × X jk × AS(W jk ∥W jl )- ∑ p k=1 ∑ p l=1 X ik × X jl × AS(W ik ∥W jl )      . (4.12) AISs(X i ∥X j ) = 1 p 2 p ∑ k=1 p ∑ l=1 X ik × X jl × AS(W ik ∥W jl ) ↔ W ik ̸ = W jl .
(4.13)

Bellow we give a sample calculation of the simplified AIS, Equation 4.13, with Added Value measure, for the following pair of sentences:

• X i : Rumen studies in Paris.

• X j : Rumen studies in France.

Frequency W i W j W i ∩ W j W j ∩ W i
Paris studies 154000000 166000000

Paris in 132000000 132000000

Paris France 318000000 315000000

AISs(X i ∥X j ) = = 1 4 × 4           ((1 × 1 × AV(Rumen∥studies)) + (1 × 1 × AV(Rumen∥in)) + (1 × 1 × AV(Rumen∥France)))× ((1 × 1 × AV(studies∥Rumen)) + (1 × 1 × AV(studies∥in)) + (1 × 1 × AV(studies∥France)))× ((1 × 1 × AV(in∥Rumen)) + (1 × 1 × AV(in∥studies)) + (1 × 1 × AV(in∥France)))× ((1 × 1 × AV(Paris∥Rumen)) + (1 × 1 × AV(Paris∥studies))+ (1 × 1 × AV(Paris∥in)) + (1 × 1 × AV(Paris∥France)))           = 1 4 × 4   (0.
AISs(X j ∥X i ) = = 1 4 × 4           ((1 × 1 × AV(Rumen∥studies)) + (1 × 1 × AV(Rumen∥in)) + (1 × 1 × AV(Rumen∥Paris)))× ((1 × 1 × AV(studies∥Rumen)) + (1 × 1 × AV(studies∥in)) + (1 × 1 × AV(studies∥Paris)))× ((1 × 1 × AV(in∥Rumen)) + (1 × 1 × AV(in∥studies)) + (1 × 1 × AV(in∥Paris)))× ((1 × 1 × AV(France∥Rumen)) + (1 × 1 × AV(France∥studies))+ (1 × 1 × AV(France∥in)) + (1 × 1 × AV(France∥Paris)))           = 1 4 × 4   (0.

Asymmetry between Words

Most of the metrics, which evaluate the degree of similarity between words are symmetric (Pecina & Schlesinger, 2006;Tan et al., 2004), except perhaps pattern-based similarities Caraballo (1999);

Asymmetry between Sentences

Hearst (1992). Patterns can be helpful to learn knowledge from texts that can possibly be expressed by constructions known in advance and surely embody the easiest way to induce this knowledge.

Most of the works in this area have been dealing with the identification of the hypernymy/hyponymy relation although some other word semantic relations such as synonymy and meronymy/holonymy have been tackled.

In order to extract hypernymy/hyponymy relations, Hearst (1992) The idea of an asymmetric measure is inspired by the fact that within the human mind, the association between two words or concepts is not always symmetric. For example, as stated in Michelbacher et al. (2007), "there is a tendency for a strong forward association from a specific term like adenocarcinoma to the more general term cancer, whereas the association from cancer to adenocarcinoma is weak". For instance, cancer would be more central than adenocarcinoma. Within this scope, seldom new researches have been emerging over the past few years, which propose the use of asymmetric similarity measures, which we believe can lead to great improvements in the acquisition of word semantic relations as shown in Cleuziou et al. (2011).

We present the eight asymmetric association measures used in this work that will be evaluated in the context of asymmetry between sentences: the Added Value (Equation 4.2), the Braun-Blanket (Equation 4.3), the Certainty Factor (Equation 4.4), the Conviction (Equation 4.5), the Gini Index (Equation 4.6), the J-measure (Equation 4.7), the Laplace (Equation 4.8), and the Conditional Probability (Equation 4.1).

Asymmetry between Sentences

There are a number of ways to compute the similarity between two sentences. Most similarity measures determine the distance between two vectors associated to two sentences (i.e. the vector space model). However, when applying the classical similarity measures between two sentences, only the identical indexes of the row vector X i and X j are taken into account, which may lead to miscalculated similarities. To deal with this problem, different methodologies have been proposed, but the most promising one is certainly the one proposed by Dias et al. (2007), the InfoSimba informative similarity measure, expressed in Equation 4.10.

Although there are many asymmetric similarity measures between words, there does not exist any attributional similarity measure capable to assess whether a sentence is more specific/general than another one. To overcome this issue, we introduce the asymmetric InfoSimba similarity measure (AIS), which underlying idea is to say that a sentence T is semantically related to sentence H and H is more general than T (i.e. T → H), if H and T share as many relevant related words as possible between contexts and each context word of H is likely to be more general than most of the context words of T. The AIS is defined in Equation 4.12.

As computation of the AIS may be hard due to orders of complexity, we also define its simplified version AISs(.∥.) in Equation 4.13, which we will specifically use in our experiments.

As a consequence, an entailment (T → H) will hold if and only if AISs(T∥H) < AISs(H∥T). Otherwise, the entailment will not hold. This way, contrarily to existing methodologies, we do not need to define or tune thresholds. Indeed, due to its asymmetric definition, the asymmetric InfoSimba similarity measure allows to compare both sides of entailments.

Three Levels of Pre-Processing

In our work, we experienced three approaches for selecting the words for the calculation of the asymmetry between sentences.Thus we can assess which approach best performance to identify entailment by generality.In a first approach, we chose to do the calculations without restrictions, ie, do the calculations with all the words (see Figure 4.1).

The next approach was to use a list of stop words (for English1 and for Portuguese 2 ). Sometimes, some extremely common words which would appear to be of little value in helping select documents matching a user need are excluded from the vocabulary entirely. These words are called stop words.

In computer search engines, a stop word is a commonly used word (such as "the") that a search engine has been programmed to ignore, both when indexing entries for searching and when retrieving them as the result of a search query. When building the index, most engines are programmed to remove certain words from any index entry. The list of words that are not to be added is called a stop word list (see table A.1). Stop words are deemed irrelevant for searching purposes because they occur frequently in the language for which the indexing engine has been tuned. In order to save both space and time, these words are dropped at indexing time and then ignored at search time. In the 4.4 Three Levels of Pre-Processing context of our work, in this approach, the calculations are made with restrictions, ie, the words that are on the list of stop words are ignored (see Table A.1), are not considered in the calculations.(see Figure 4.2).

Finally, in this last approach, we introduce the concept of MWU (the next chapter explains in this concept), identified the MWU in sentences (see Table B.1) for the calculation of the asymmetry (see Figure 4.3).

In summary, our experiments are based on three approaches to the calculations, all words, using list of the Stop Words and finally using MWU. In the Chapter 5, we evaluate the performances of these approaches to identify which one best identifies entailment by generality.

Multiword Units Identification

ME( S) = n × P( S) 2 ∑ 2 i 1 =1 • • • ∑ n i (n-1
) =i (n-2) +1 P(p i1 i 1 w i 1 p i 1 i 2 w i 2 . . . p i 1 i (n-1) w i (n-1) )

.

(4.16)

Algorithm 1 The GenLocalMaxs algorithm.

∀W n-1 ∈ Ω n-1 , ∀W n+1 ∈ Ω n+1 if size(W) = 2 ∧ assoc(W) > assoc(W n+1 ) then return MWU else if size(W) ̸ = 2 ∧ assoc(W) ≥ assoc(W n-1 ) ∧ assoc(W) > assoc(W n+1 ) then return MWU else return NO-MWU end if end if

Sample of Calculation for Identify Entailment by Generality

In this chapter we present our methodology to identify entailment by generality between two sentences, we now apply our methodology on a pair of T -H extracted from RTE-3 test set:

"<pair id="217" entailment="YES" task="IR" length="short" > <t>Pierre Beregovoy, apparently left no message when he shot himself with a borrowed gun.</t> <h>Pierre Beregovoy commits suicide.</h> </pair>"

The AAM, we use in this demonstration is the Conditional Probability (Equation 4.1), for the calculations of the three approaches,the terms and their web frequencies are in the Appendix D. For the calculations used the Google API 1 to calculate all joint and marginal frequencies, so, instead of relying on a closed corpus and exact frequencies, we based our analysis on the Web and Web hits i.

e. estimated number of documents where words appear -each pair needs approximately 17 minutes to get all the frequencies used in the respective AAM. A total of 5790669 queries derived from pairs of the first five RTE Challenges, which are submitted to Google API to know its frequency.

The following figures show the links between the terms in the three approaches.

Sample of Calculation for Identify Entailment by Generality

The next figure illustrates the links between sentence, when the calculations are made with all terms -All Words that compose theses sentences.

. . In this case, AISs(T∥H) = 0.26 and AISs(H∥T) = 0.20, then AISs(T∥H) = 0.26 > AISs(H∥T) = 0.20, so we conclude that T no entail H.

In the approach we use a list of stop words, in this example,for calculations exclude the T the words: "no", "he", "with" and "a". H not exclude words because none of them are on the list of stop words (see Table A.1 In this case, AISs(T∥H) = 0.17 and AISs(H∥T) = 0.24, then AISs(T∥H) = 0.17 < AISs(H∥T) = 0.24, so we conclude that T entail H -(T-> H).

Through the concept of MWU, gives us the possibility of the links are not only in single words but also in terms, as we see below (Figure 4.3), the example has two MWU -"Pierre Beregovoy" and "with a". In this case, AISs(T∥H) = 0.17 and AISs(H∥T) = 0.22, then AISs(T∥H) = 0.17 < AISs(H∥T) = 0.22, so we conclude that T entail H -(T-> H).

E P M "You may never know what results come of your action,

but if you do nothing there will be no result."

Mahatma Gandhi

In this Chapter we present the results obtained through the calculations of measures for evaluating the performance of our methodology. Analyze and compare the precisions and accuracies calculated.

Evaluation Scheme

With the evaluation the performance of our methodology will help us define what approach -with all words; without stop words; with MWU -and what AAM -the Added Value (Equation 4.2), the Braun-Blanket (Equation 4.3), the Certainty Factor (Equation 4.4), the Conviction (Equation 4.5), the Gini Index (Equation 4.6), the J-measure (Equation 4.7), the Laplace (Equation 4.8), and the Conditional Probability (Equation 4.1), what better way to recognize entailment by generality.

With this new definition, we know how to implement future framework and / or toolkits unsupervised and language-independent, with different objectives in NLP.

Our evaluation is based on analysis of the results obtained through the measures that we present below. The calculation of these measures are based on the Confusion Matrix (CM).

Measures to evaluate the performance

Classification or categorization is the task of assigning objects from a universe to two or more classes or categories. In the field of AI, a CM is a visualization tool typically used in supervised and unsupervised learning. Each column of the matrix represents the instances in a predicted class, while each row represents the instances in an actual class. One benefit of a CM is that it is easy to see if the system is confusing two classes (i.e. commonly mislabeling one as another).

When the dataset is unbalanced (when the number of samples in different classes vary greatly) the error rate of a classifier is not representative of the true performance of the classifier.

The entries in the confusion matrix have the following meaning in the context of our study:

• a is the number of correct predictions that an instance is Entailment,

• b is the number of incorrect predictions that an instance is No Entailment,

• c is the number of incorrect predictions that an instance in Entailment and

• d is the number of correct predictions that an instance is No Entailment.

YES is correct NO is correct

YES was assigned a b

NO was assigned c d The AC is the proportion of the total number of predictions that were correct. It is determined using the equation:

AC = a + d a + b + c + d (5.1)
P is defined as a measure of the proportion of selected items that the system got right:

P = a a + b (5.2)
To evaluate the overall performance of our experiments, we used two types of averaging of the previous measures, calculate the arithmetic average and the calculation of the weighted average1 .

The weighted average formula is used to calculate the average value of a particular set of numbers with different levels of relevance. The relevance of each number is called its weight. The weights should be represented as a percentage of the total relevancy. Therefore, all weights should be equal to 100%, or 1. The most common formula used to determine an average is the arithmetic mean formula. This formula adds all of the numbers and divides by the amount of numbers. For example the average of 1, 2 and 3 would be the sum 1 + 2 + 3 divided by 3, which would return 2. However, and Weighted Average. Similarly, the J-measure achieves 0, 52 in Weighted Average. 5.2 reveals that the results fit a short range between 0, 52 and 0, 55 for the Arithmetic Average and between 0, 52 and 0, 54 for the Weighted Average. Analysis with respect to different challenges shows that globally AAMs perform best on RTE-4 data while RTE-1 data seems to be the most challenging set.

In spite of the low values of Accuracy, in Precision -Entailment for this approach the J-measure stands out with 0, 81 and 0, 73 for Arithmetic Average and Weighted Average, respectively. With respect to the J-measure in Arithmetic Average, we highlight the excellent result achieved on the RTE-2 data set, namely 0, 91. In Precision -Entailment the worst measure is Braun-Blanket with 0, 43 and 0, 44 for Arithmetic Average and Weighted Average, respectively.

The averages that we present in Table 5.3 do not have the same behavior as the averages we presented in Table 5.2. The best result in terms of Precision -Entailment is much higher compared to the second best result. With all words the best result is achieved by the J-measure for RTE-2 set.

All pairs of the Test Set of the first five RTE Challenges

Its worst performance is on the RTE-1 test set. The results for Precision -No Entailment show that the best measure is the Braun-Blanket with significant differences for the second best measure (contrary to what we have seen in table 5.3).

With the bests results in RTE-1 and the worse results in RTE-2, with emphasis on the J-measure that has obtained 0, 09.

Considering the results for All Words, Table 5.2, we can not conclude that our methodology is capable to recognize textual entailment as the best Accuracy, achieved by Braun-Blanket, is as low as 0, 55. On the other side, when we analyze Table 5.3 and Table 5.4 we can conclude that our methodology identifies better Entailment compared to recognition of No Entailment cases with J-measure and Braun-Blanket, respectively.

An interesting pattern to observe is a symmetric behavior with respect to Precision. Thus, the RTE-2 is the challenge that presents the best results for Precision -Entailment, but this is the one that has worst results for Precision -No Entailment, and the RTE-1 is the challenge that has the worst results for Precision -Entailment, but the best results for Precision -No Entailment.

Without Stop Words

As already mentioned, in this approach we have excluded from calculations words that do not add relevant information (stop words) to the sentences that compose the pair. Compared to the previous approach, this one performs fewer calculations, due to the exclusion of about half of the terms.

In this approach, our methodology shows a different behavior. Gini Index and J-Measure reaching as low as 0, 49.

As happened in the approach With all Words, also in this approach for Accuracy, there is no significant difference between the measurements, as we confirmed in the results shown in Table 5.5.

All pairs of the Test Set of the first five RTE Challenges

However, the RTE-4 set allows for relatively better performance compared to RTE-1 and RTE-2 data sets. With respect to Precision -Entailment, the measure with best performance is the J-measure.

On the RTE-2 data set it achieves 0, 89 as evidenced by Table 5.6. The J-measure achieves 0, 75 in Arithmetic Average, while the second best measure, ADDED VALUE, only achieves 0, 65. In Weighted Average, J-measure achieves 0, 66 and the second best measure, ADDED VALUE, achieves 0, 59. On the other hand, in average, the Conviction and Gini Index have the worst performances.

Individually, the AAM's have the best performance on RTE-2 dataset and the worst results are obtained on RTE-1 dataset. The J-measure shows the worst performance in both averages. The best averages are achieved with Braun-Blanket (0, 62 and 0, 7 respectively). The same pattern is observed here with respect to Precision as in the approach With All Words, namely the RTE-2 is the challenge that presents the best results for Precision -Entailment, but this is the one that has worst results for Precision -No Entailment, and the RTE-1 is the challenge that has the worst results for Precision -Entailment, but the best results for Precision -No Entailment.

PRECISION -ENTAILMENT by RTE

In this approach Braun-Blanket achieves the best performance.

In summary, the best Accuracy is achieved by three measures -Braun-Blanket, Certainty Factor and Conditional Probability, while the best Precisions values are achieved by Braun-Blanket, Conviction, Gini Index and J-measure.

With Multiword Units

Due to the use of MWU this approach requires fewer calculations than in the first approach.

Compared to the previous approach, the number of calculations is roughly equivalent.

We expect that the use of MWU would allow for improved results. However, with regard to Accuracy, this is not the case as we have performance figures that are not significantly different from the previous approaches. The measure with best performance is the Braun-Blanket, with values of 0, 54

for Arithmetic Average and 0, 56 for the Weighted Average, also the Laplace obtained 0, 56 for the Weighted Average. For Precision -Entailment, in this approach, the measure that stands out is the Added Value, with a significant difference compared to the second best measures (Braun-Blanket and J-measure). The best result per challenge is obtained with the Added Value on RTE-2, achieving precision of 0, 9.

The worst averages precision (0, 46) is obtained with Certainty Factor.

The behavior of the measures was very similar in all RTE Challenges.

Summary

The purpose of this section is to evaluate our methodology against well known test data used to compare a number of methodologies. Although the obtained results are not excellent, they are promising and encouraging.

An individual analysis of As already mentioned earlier, Accuracy values of our experiments on RTE Challenges span a relatively short range between 0, 50 and 0, 56. (2005). They obtained 0, 586, 0, 586 and 0, 495 of accuracy, respectively. We prove that our methodology has better performance than was possible in previous works. On RTE-1 Challenge With MWU approach, our methodology achieved its best results. Table 5.8 shows that the measures Braun-Blanket and Laplace achieve

Corpus TE by Generality

good results in Weighted Average Accuracy, namely 0, 61.

Corpus TE by Generality

In this section, we present the results of an experiment designed to measure the degree to which our methodology is capable to distinguish TE by Generality. To this end we needed a corpus of entailment instances that were labeled either TE by Generality or TE but not by Generality. This corpus was built following the methodology described in Chapter 3.

Here we again followed the standard procedure to measure performance, namely we filled a confusion matrix with the number of true positive, false positive, false negative and true negative classifications produced by our system. From these we calculated various Accuracy and Precision scores. It is worth noting, that the results on this subset are higher compared to the corresponding results presented in Section 5.2.1. Removing the cases that are not TE and dividing the rest in another pair of classes leads to this situation. A possible conclusion is that our methodology is better in telling TE by Generality from the other cases of TE than in the classification between TE and not an entailment. Similarly to the results in Section 5.2.1 the J-Measure achieves the best performance with respect to Precision -Entailment and also for Precision for "Entailment by Generality".

AAM Accuracy Precision

Without Stop Words

On average, 862 TE by Generality pairs were correctly identified as such and the other 341 were classified as "Entailment but not Generality", i.e., this approach achieved 72% hit rate as Table 5.16 evidences. Analyzing measures individually we see that the measure that correctly classifies the greatest number "Entailment by Generality" pairs is the Braun-Blanket, with 965 correct. J-measure achieves comparable performance, classifying 943 correctly. The behavior of the AAM in Table 5.17 is very different from the behavior presented in Section 5.2.2.

On the corpus TE by Generality, in the approach "With Stop Words", the Braun-Blanket has an excellent performance, the same is not the case for approach "With All Words".

With Multiword Units

In this approach, only considering the subset of TE by Generality pairs, on average over the 8 AAM, 820 T-> H pairs where correctly classified and 383 pairs were missed, i.e., this approach achieves a hit rate of 68%, as shown in Table 5.18. However, in this approach we have two measures that stand out with an excellent performance. These are respectively Added Value and Braun-Blanket.

We find that the best measure continues to be Braun-Blanket. This last measure classifies correctly 1113 "Entailment by Generality" pairs. Table 5.19 shows that for this approach, the best performing AAM is the Braun-Blanket likewise the situation in Table 5.17, but here this measure has a greater emphasis.

In the same line of reasoning, when we look at Table 5.19, we find the excellent behavior that the measure "Braun-Blanket" has. For "Accuracy" we have 0, 85, for "Precision -Entailment by Generality" we have 0, 93, and for "Precision -Entailment, but no Generality" we have 0, 73. This result distinguishes "Braun-Blanket" from the other measures with a significant difference between "Accuracy" and "Precision".

The worst performances figures are obtained by Conviction -0, 54, Laplace -0, 58 and Added

Corpus TE by Generality

Value -0, 49, (respectively "Accuracy", "Precision -Entailment by Generality" and "Precision -Entailment, but no Generality"). These values here are lower compared to to previous approaches. Although Braun-Blanket is the best measure "With MWU" approach on both the general TE set, Section 5.2.3, and on TE by Generality set, here the difference with the second best result is more pronounced.

Summary

In this section we summarize the results of the application of our methodology on the corpus TE by Generality. These are the results we are most interested in, as they concern the problem on which we are focusing our attention, namely identification of entailment by generality.

With respect to Accuracy, as seen in Table 5.20, the best performance, 0, 85, is achieved by the measure Braun-Blanket in conjunction with the approach With MWU. In this approach the second best measure is the Added Value whit 0, 69 of accuracy. We noted the significant difference between these two AAM.

The measure Braun-Blanket also is the best measure in approach "Without Stop Words", with accuracy of 0, 73. In this approach, we have two measures with the second best performance, Gini Index and J-measure, with 0, 64 accuracy.

In "All Words", we have two measures with the best performance, Conviction and J-measure, with 0, 7 and 0, 69 accuracy, respectively.

In Table 5.20, we realize that although Conviction is the best measure with "All Words" with respect to Accuracy, its performance is virtually equivalent to that of a random guesser "Without Stop Words" and "With MWU".

AAM Accuracy

All

Corpus TE by Generality translated into Portuguese

In this section we present the results of an experiment parallel to the one discussed in Section 5.3.

Its original intention is to measure the degree to which our methodology is capable to recognize a specific kind of TE, namely TE by Generality. However, now we aim to study the possibility to adapt the processes to a different language. To this end we randomly selected a subset of 100 T-> H Machine translation is a viable alternative to manual translation due to a combination of two factors.

First, since our intention was to be as much language independent as possible, our methodology does not use morpho-syntactic analysis and language specific word order knowledge. On the other hand, Google Translate is reasonably successful in correct content word substitution. Thus, from the perspective of our bag-of-words approach Google Translate preserves well the important information. This supposition is in line with the fact that our results in Portuguese are comparable to the corresponding results in English language.

All Words

On average over 8 AAMs, out of the 60 positive TE by Generality pairs about 44 were correctly identified as such and the other about 16 were missed, i.e., our approach achieved 73% hit rate.

Analyzing each measure individually, we noticed that the Table 5.22 evidences a similar behavior to the Table 5.14 (even with the difference in the total number of pairs). In this approach, we see that the measure that correctly classifies the greatest number of "Entailment by Generality" pairs is the J-measure, with 51 correct, and the one with worst performance is Braun-Blanket, with 39 correct. Table 5.23 shows that in terms of accuracy, for this approach, the best performing measures are the J-Measure and the Conviction. The J-Measure shows the best performance in Accuracy, 0, 72, and Precision for "Entailment by Generality", 0, 85. The Conviction is the best measure in Precision for "Entailment, but no Generality", 0, 6. As shown in Table 5.15, these measures also achieve good performance in English.

The worst result occur on measure Added Value in Precision for "Entailment, but no Generality", with 0, 4. The measure Conditional Probability has bad performance in terms of Accuracy, 0, 59.

With respect to Precision for "Entailment by Generality" the measure with the worst performance is Braun-Blanket, 0, 65. 5.15 and Table 5.23 we see that the AAMs have a similar behavior in this approach, when compared over the English and Portuguese versions of the corpus. It is even more evident when we analyze the ranking of the measures in Table 5.15 and Table 5.23. That is, the AAM measures with the best performance in English are the same measures that show the best performance in Portuguese. Similarly, the worst measures in English also achieve low results in Portuguese.

Without Stop Words

On average over the 8 AAM measures 43 TE by Generality T-> H pairs were classified correctly and 17 were missed, i.e., this approach achieved a hit rate of about 72% as evidenced by Table 5.24.

When the measures are considered individually, the ones that correctly classify the highest number of "Entailment by Generality" pairs are Added Value and Braun-Blanket with 47 correct, the Gini Index also has a good performance, classifying 45 pairs correctly.

AAM System Response

A B

Gold Standard

Added Value A 47 25 Braun-Blanket is the measure that shows the best performance both in English, Table 5.17, and in Portuguese, Table 5.25, when the corpus for TE by Generality is subjected to stop words removal (cf. Appendix 6.2).

B

With Multiword Units

In this approach, on average over the 8 AAM, 41 out of 60 T-> H pairs of TE by Generality were correctly classified as such and 19 pairs were missed, i.e., this approach achieved a hit rate of 68%, as we confirm in Table 5.26. In this approach we have two measures that stand out with an excellent performance, these are respectively Added Value and Braun-Blanket. The best measure continues to be Braun-Blanket. This last measure classifies correctly 53 pairs of "Entailment by Generality". Table 5.27 shows that for this approach, the AAM with the best performance is Braun-Blanket, the same conclusion was drawn from the analysis of Table 5.19, however here this measure does not show significant advantage over the other measures. In the same line of reasoning, when we look at Table 5.27, we find the excellent behavior of the measure "Braun-Blanket" compared to the other measures, scoring 0, 76 with respect to "Accuracy". "Braun-Blanket" also achieves the best result with respect to "Precision -Entailment by Generality", 0, 88. "Certainty Factor", "Gini Index"

and "Laplace" achieve the highest "Precision -Entailment, but no Generality" value, 0, 68.

This approach achieves the absolute lowest values compared to the previous ones with Conviction, 0, 5, 0, 55 and 0, 43 (respectively "Accuracy", "Precision -Entailment by Generality" and "Precision -Entailment, but no Generality"). Comparing performance between English, Table 5.19, and Portuguese, Table 5.27, we confirm that there is no significant difference between both datasets. On the corpus TE by Generality translated into Portuguese, with the approach "With MWU" the Braun-Blanket has the best performance with respect to "Accuracy" and "Precision -Entailment by Generality" (likewise in Section 5.3.3). For "Precision -Entailment, but no Generality" the best AAMs are "Certainty Factor", "Gini Index"

and "Laplace", unlike the corresponding results in Table 5.19.

In contrast to Section 5.3.3, here there is no a measure with significant advantage over the other measures.

Summary

In this section we summarize the results of the application of our methodology on the corpus TE by Generality translated into Portuguese.

With respect to Accuracy the best performance is achieved with the measure Braun-Blanket in conjunction with the approach With MWU, with result of 0, 76, as evidenced in Table 5.28. In this approach the second best measure is the Added Value whit result of 0, 69. Similarly, Braun-Blanket achieves the best performance in approach "Without Stop Words", with result of 0, 71, followed by Gini Index with 0, 66. With "All Words", the measure with the best Accuracy is J-measure, with 0, 72

From table 5.28, we read the three measures with the lowest Accuracy, namely, Conditional Probability with approach "All Words" and "Without Stop Words" and Conviction "With MWU".

AAM Accuracy

All Considering the Accuracy figures for English and for Portuguese, presented in Table 5.20 and Table 5.28, which show similar scale and variations, we conclude that the performance of our methodology is not significantly influenced by the language.

With respect to "Precision -Entailment by Generality" the measure Braun-Blanket in conjunction with the approach With MWU, presents the best results of 0, 88, followed by the measure J-measure in conjunction with the approach All Words, 0, 85. Both, Accuracy and Precision figures show that whether applied to a corpus in English or in Portuguese language, our methodology provides classification capability significantly better than random guessing baseline and virtually indistinguishable with respect to the language.

Qualitative Analysis

In this chapter we study the behavior of our methodology for recognizing TE by Generality. Also, we provide a thorough comparison to relevant work. This is done taking under account the limitations of a typical language-independent and unsupervised learning techniques. In order to obtain fair comparison we used a well known dataset studied in the RTE Challenge as our test-bed. Further, as we are interested in a special kind of TE, we built a suitable corpus and also translated it into Portuguese language.

In this process we learned that detecting entailment between sentences is not an exact science.

We saw that each new RTE Challenge required different approach to the problem. Thus, we do not provide a measure or an approach that pretends to solve the problem. We can only conclude, based on evidences from Table 5.12 that for some combinations of measure and preprocessing approach our method shows good precision in recognizing TE.

Comparing our results, presented in Section 5.2, with the results of other relevant methodologies, presented in Section 2.2, we prove that our methodology achieves higher performance figures. In RTE-1 Challenge:

• The method described in Bayer et al. (2005), obtained 0, 586 of accuracy;

• The method described in Glickman & Dagan (2005), obtained 0, 586 of accuracy;

• The method described in Perez et al. (2005), obtained 0, 495 of accuracy.

On RTE-1 Challenge data, with approach With MWU, our methodology achieved better results than previous methodologies. Table 5.8 shows that the measures Braun-Blanket and Laplace achieve better results for Weighted Average Accuracy, namely 0, 61.

In the second case, the results are much more significant. As seen in Tables 5.20 and Table 5.21, there is always measure and an approach that stand out, namely Braun-Blanket measure with MWU.

However J-measure and Conviction also have good results:

• J-measure in Precision -Entailment by Generality with All Words, has the second best performance (with 0, 83). In another words J-measure with All Words has a good performance to identify entailment by generality between sentences;

• Conviction ranks second for Accuracy (with 0, 7), and achieves a good result in Precison -Entailment, but no generality or Other, both with approach All Words.

Finally, when executed on the TE by Generality corpus translated in Portuguese, our methodology achieves results comparable to these in English language, although with less significant difference between the best and the following measures. However, in terms of Accuracy, Table 5.28, and

Precision -Entailment by Generality, Table 5.29, the Braun-Blanket achieves the best performance in approach With MWU.

The results in both cases prove that there are several types of entailment (see Section 1.3.1), and evidence, through the corpus TE by Generality and the subset translated into Portuguese, that our method has a good performance in recognizing entailment by generality.

C 6

C F W

"The best way to prepare for the future is to concentrate all the imagination and enthusiasm in executing the perfect job today."

Dale Carnegie

Finally, we present a recapitulation of this thesis and present our perspectives for the future investigation in this field.

Recapitulation

This Thesis presents and discusses the most relevant results of our research on TE by Generality.

We studied the behavior of a specific variation of TE, where the objective is to understand how to identify entailment by generality between two sentences. We contribute a new direction for research in various fields of NLP.

In this thesis, we present an initial study of Entailment (Chapter 1), where we studied its meaning, its context in linguistics as well as its variations. This study contributed to promote a specific variation of Entailment -Entailment by Generality -and define the objective of our work -Recognizing Textual Entailment by Generality.

Still in Chapter 1, we show that there exists a strong relation between the concept of probability and TE. It is this relation that also supports our proposal to identify Entailment by Generality between sentences.

In Chapter 2 we present the study of the works that already exist in the area and survey all the approaches used in the first five RTE Challenges. Most of the participating systems relied on some external knowledge, e.g. linguistic tools (see Chapter 2), supervised approaches (see Chapter 2) and parameterized variables (for example threshold). In contrast, we presented a methodology for recognizing TE by Generality, one that is unsupervised, language-independent and threshold free solution.

In Chapter 2, we report the most important approaches used in RTE Challenges, with the variety of approaches, we realized that recognizing TE between two sentences is not an exact science. The With this corpus at hand, the next task (see Chapter 5) involves testing our methodology and evaluation of its performance in three different environments: i) All pairs of the Test Set of the first five RTE Challenges; ii) corpus of TE by Generality; and iii) a set of 100 T -H pairs randomly taken from the corpus of TE by Generality and translated into Portuguese. To evaluate the performance of our methodology we used two benchmarks -the Accuracy (Equation 5.1) and the Precision (Equation 5.2). The results are very satisfactory and encouraging to further the work on our methodology.

In section 5.5 we looked at the quality of our results. We conclude that with respect to RTE by Generality, the measure Braun-Blanket in English and Portuguese, globally has an excellent performance, especially on approach with MWU. Also in this section, in conjunction with Section 5.2.4, we show that our methodology has better results on RTE-1 Challenge (in approach With MWU, see 5.2.3), than the other unsupervised and language-independent methodologies tested in this challenge (see Chapter 2.2).

With this thesis, we contribute an original proposal to RTE. Our methodology is unsupervised and language-independent, and accounts for the asymmetry of the studied phenomena by means of asymmetric similarity measures. However, we have demonstrated through the results in Chapter 5, that it is necessary to treat differently each type of textual entailment, i.e., through our methodology we got excellent results to identify pairs T -H by generality, while, the result was less impressive when evaluating the data set of the first five RTE Challenges.

Some of the issues addressed in this thesis give raise to interesting questions, problems and future research directions.

Our work does not end with the presentation of this thesis. This thesis is the beginning of our study in TE, more specifically TE by Generality. We will make available the corpus of TE by Generality to the scientific community. We intend to perform a syntactic and semantic analysis of this corpus in near future, in order to learn how many pairs each RTE Challenges contributed to the construction of this corpus, and finally what is the average size of T and H.

Still much work is to be done with the results presented in this thesis. It is necessary to make a more complete qualitative analysis, in order to understand what are the main differences between the various measures and approaches that we used. With the current results, we also want to know the measure and approach with more Statistical Significance ((Demšar, 2006) (Foody, 2004)), independent of their performance. For this we will use the McNemar's Test and ROC analysis (Davis & Goadrich, 2006).

We want to improve our results and it is necessary to reinvent methodologies and improve existing ones, always respecting the idea of unsupervised, language-independent and threshold free solutions.

Thus, we are conducting further studies of the simplified asymmetric InfoSimba informative similarity measure AISs(.∥.) (see Equation 4.13), which showed promising results (see Chapter 5).

In this sense, the next task will be to implement our methodology in a new informative attributional similarity measure. To this end we turned the AIS into a N order similarity measure by proposing its recursive definition as in Equation 6.1, which we call the Recursive Asymmetric In-foSimba Similarity (RAIS), where the initialization is based on the initial version of the AIS i.e.

RAIS 0 (X i ∥X j ) = AIS(X i ∥X j ). We also define its simplified version RAISs N (.∥.) in 6.2 with the following initialization RAISs 0 (X i ∥X j ) = AISs(X i ∥X j ).

RAIS N (X i ∥X j ) = ∑ p k=1 ∑ p l=1 X ik .X jl .RAIS N-1 (W ik ∥W jl )      ∑ p k=1 ∑ p l=1 X ik .X il .RAIS N-1 (W ik ∥W il )+ ∑ p k=1 ∑ p l=1 X jk .X jl .RAIS N-1 (W jk ∥W jl )- ∑ p k=1 ∑ p l=1 X ik .X jl .RAIS N-1 (W ik ∥W jl )      . (6.1) RAISs N (X i ∥X j ) = 1 p 2 p ∑ k=1 p ∑ l=1 X ik .X jl .RAISs N-1 (W ik ∥W jl ). (6.2)
With the wide usage of mobile devices summarizing Web pages "on the fly" is one of the most important applications for NLP. Following this direction, we plan to build a toolkit whose objective is to propose a summary of each generated cluster within the scope of ephemeral clustering (as mentioned in Section 1.2) search engine. Indeed, most of the time, the cluster label is not expressive enough to afford a clear understanding of the cluster content. For that purpose, we proposed an innovative solution, which is based on the discovery of the most expressive and general snippet within

given cluster is the one, which entails all other ones with minimal loss of information. Once a user knows more about a cluster, she may find useful to understand what are the slight differences embodied by each Web page within the cluster. As such, each Web snippet could be highlighted (or ultra-summarized) by its differences and not its commonalities. These issues are very interesting for mobile information retrieval as well as for VIP users, as they may allow fast access to relevant information. Moreover, they can easily be computed in real-time based on our initial ideas.

S W L

A.1 Stop Words List in English "Pierre" "commits" 59200 "Pierre" "suicide" 1560000 "Beregovoy" "commits" 32 "Beregovoy" "suicide" 1220 "apparently" "Pierre" 1460000 "apparently" "Beregovoy" 231 "apparently" "commits" 3320000 "apparently" "suicide" 17300000 "left" "Pierre" 30900000 "left" "Beregovoy" 761 "left" "commits" 21400000 "left" "suicide" 136000000 "no" "Pierre" 75800000 "no" "Beregovoy" 4540 "no" "commits" 37700000 "no" "suicide" 263000000 "message" "Pierre" 15700000 "message" "Beregovoy" 1890 "message" "commits" 5700000 "message" "suicide" 62800000 "when" "Pierre" 83000000 "when" "Beregovoy" 1490 "when" "commits" 37800000 "when" "suicide" 268000000 "he" "Pierre" 57700000 "he" "Beregovoy" 1110 "he" "commits" 34100000 "he" "suicide" 239000000 "shot" "Pierre" 18800000 "shot" "Beregovoy" 271 "shot" "commits" 22200000 "shot" "suicide" 108000000 T ∩ H H ∩ T "when" "commits" 37800000 "when" "suicide" 268000000 "he" "Pierre Beregovoy" 1520 "he" "commits" 34100000 "he" "suicide" 239000000 "shot" "Pierre Beregovoy" 307 "shot" "commits" 22200000 "shot" "suicide" 108000000 "himself" "Pierre Beregovoy" 514 "himself" "commits" 14900000 "himself" "suicide" 58000000

D.1 All Words

"with a" "Pierre Beregovoy" 1160

"with a" "commits" 23400000

"with a" "suicide" 95900000 "borrowed" "Pierre Beregovoy" 37 "borrowed" "commits" 40800 "borrowed" "suicide" 843000 "gun" "Pierre Beregovoy" 220 "gun" "commits" 14000000 "gun" "suicide" 71000000 Index vii,14,55,56,64,33,39,41,56,63,68 SENTA,14,63 similarity,34,[36][37][38][39][40][41][51][52][53][54]35 Stop Words,14,62,63,65,67 Syntactic,35,36 Turkers,[45][46][47]49,50

  1. we tested our methodology on all pairs Text -Hypothesis of the Test Set of the first five RTE Challenges; 2. we tested in pairs Text-> Hypothesis, where we know the entailment between Text and Hypothesis is by generality; 3. finally, we tested our methodology on 100 pairs T-> H which were randomly extracted from set of pairs submitted in CrowdFlower (60 pairs T-> H Entailment vii by Generality and 40 pairs T-> H Entailment, but no Generality) and translated into Portuguese by Google Translate 1 .

"

  Victory is always possible for the person who refuses to stop fighting." Napoleon Hill In this Chapter we introduce the context and the motivations underlying the present research work, we analyze the notion and variants of entailment and consequently Textual Entaiment (TE).

Figure 1 . 1 :

 11 Figure 1.1: Venn diagram of the entailment relation.

Figure 1 . 2 :

 12 Figure 1.2: Example the entailment by generality relation.

  consists of seven subsets, which correspond to typical success and failure settings in other applications. Within each application setting the annotators selected an equal number of both positive entailment examples, where T is judged to entail H, and negative examples, where entailment does not hold. Typically, T consists of one sentence (sometimes two) while H was most often made of a single short sentence. Part of the examples were collected using external sources, such as available datasets or systems as follows: • Document Understanding Conferences (DUC) 2004 MT evaluation data, from the National Institute of Standards and Technology (NIST) 1 ;

2. 1

 1 Overview of the First Five RTE Challenges has 2 million inhabitants" H, producing a positive entailment pair; • Collecting SUM pairs: In this setting T and H are sentences taken from a cluster of news documents, a collection of news articles that describe the same news topic. The annotators considered the output of a multi-document summarization systems, including the document clusters and the summary generated for each cluster. The annotators picked sentence pairs with high lexical overlap, preferably where at least one of the sentences was taken from the summary. Positive examples were constructed by simplifying the hypothesis by removing sentence parts, until it was fully entailed by T. Negative examples were simplified in the same manner. This simulates the summarization process of identification and removal of the redundant information from a text.

  whether: T entails H -ENTAILMENT; T contradicts H -CONTRADICTION; The truth of H cannot be determined on the basis of T -UNKNOWN. Wrath, published exactly 70 years ago, can be seen as a prophetic novel, rooted in the tragedies of the Great Depression, but speaking directly to the harsh realities of 2009, writes Steinbeck scholar Robert De-Mott. Steinbeck's epic novel, which traces harrowing exodus of Tom Joad and his family from blighted Oklahoma (where they are evicted from their farm), across the rugged American south-west via Highway 66, and on to what they mistakenly hope will be a more promising future in California, is considered by many readers to be the quintessential Depression-era story, and an ironic reversal of the rags-toriches tale favoured by many optimistic Amerregistered seven dead children and 4,761 HFMD cases. Shandong has reported five children dead from HFMD and 3,280 cases to deal with. HFMD can start from a variety of viruses of which Enterovirus 71 (EV-71) is the most common, followed by the Coxsackie A virus (Cox A16). There is an Incubation period from time of contact to appearance of symptoms between three to seven days. in Eastern France has confirmed the Swedish car manufacturer Volvo is guilty over the deaths of two schoolchildren aged nine and ten and the serious injury of a third after a brakes failure caused an accident in 1999. The Volvo 850 TDI was being driven by a local teacher when it struck the children, who had been on their way to school. Driver Catherine Kohtz later asserted that the brake pedal had become stiff and the brakes themselves unresponsive as she traveled along the steep road.

  -4 and RTE-5 data sets are different from the previous ones, due to the introduction of the threeway classification of the pairs. If we consider the class of NO-ENTAILMENT pairs, on the one hand we see a large difference in word overlap between UNKNOWN and ENTAILMENT pairs (similar to that present in the RTE-3 data set); on the other hand, CONTRADITION pairs present a high word overlap, very similar to that of ENTAILMENT pairs. This makes the RTE-4 and RTE-5 particularly challenging, as a part of the negative pairs are not distinguishable from the positive pairs by simply considering the word overlap feature.Challenge Data Set Pairs H length 1 T length 2

  Delmonte et al. (2005), the system for semantic evaluation VENSES (Venice Semantic Evaluation System) is organized as a pipeline of two subsystems: the first is a reduced version of GETARUN, our system for Text Understanding. The output of the system is a flat list of head-dependent structures with Grammatical Relations and Semantic Roles labels. The evaluation system is made up of two main modules: the first is a sequence of linguistic rule-based subcalls; the second is a quantitatively based measurement of input structures. VENSES measures semantic similarity which may range from identical linguistic items, to synonymous or just morphologically derivable. Both modules go through General Consistency checks which are targeted to high level semantic attributes like presence of modality, negation, and opacity operators, temporal and spatial location checks.Bayer et al. (2005) intended to exemplify two different ends of the spectrum of possibilities. The first submission is a traditional system based on linguistic analysis and inference, while the second is inspired by alignment approaches from MT.InGlickman & Dagan (2005) proposes a general probabilistic setting that formalizes the notion of TE and describe a model for lexical entailment based on web co-0ccurrence statistic in a bag of words representation.The system described inHerrera et al. (2005), is based on the use of a broad-coverage parser to extract dependency relations and a module which obtains lexical entailment relations from WordNetMiller (1995).The transformation-based entailment method makes use of various types of entailment knowledge to gradually transform T such that it becomes more similar to H, or vice versa.Kouylekov & Magnini (2005) assumed a distance-based framework,where the distance between T and H is 2.1 Overview of the First Five RTE Challenges inversely proportional to the entailment relation in the pair, estimated as the sum of the costs of the edit operations (i.e. insertion, deletion, substitution) on the parse tree, which are necessary to transform T into H. They use different resources to estimate the edit operations cost and to ensure the non-symmetric directionality of the entailment relation.

  the third edition, of 2007, we can notice a move toward deep approaches. The groups were oriented on the approaches based on the syntactic structure of Text and Hypothesis, on semantic understanding of the texts and also on verification of the content and new situations and contexts that meet in the test data. A special attention was given to the named entities, where(Tatu & Moldovan, 2007) had special rules for Person names, and where(Iftene & Balahur-Dobrescu, 2007) had special rules for all named entities. Some form of relation extraction has been introduced: information extracted automatically by a system(Hickl & Bensley, 2007). Also, in comparison to previous editions, now the longer texts need anaphora resolution(Iftene & Balahur-Dobrescu, 2007).

  features can be extracted from training examples, thus can be employed to train a classifier,Bensley & Hickl (2008) focused on collecting deeper semantic features, in using a pipeline of lightweight, largely statistical systems for commitment extraction, lexical alignment, and entailment classification in order to estimate the likelihood that a T includes the linguistic content sufficient to textually entail a H.

C 3 C"

 3 Men often become what they believe themselves to be.If I believe I cannot do something, it makes me incapable of doing it.

Figure 3

 3 Figure 3.1: Mechanical Turk process.

Figure 3

 3 Figure 3.2: Job Calibration Settings in CrowdFlower.

Figure 3

 3 Figure 3.3: Add Funds in CrowdFlower.

Figure 3

 3 Figure 3.4: All Reports in CrowdFlower.

  ) = P(x) × P( ȳ) P(x, ȳ) .

  ) = P(y) × (P(x|y) 2 + P( x|y) 2 ) -P(x) 2 P( ȳ) × (P(x| ȳ) 2 + P( x| ȳ) 2 ) -P( x) 2 .

  KL(x∥y) = ∑ ⟨z,r⟩∈A log P(z|x) × log P(z|x) log P(z|y) .

  many asymmetric similarity measures, they evidence problems that may reduce their utility. On the one hand, asymmetric association measures can only evaluate the generality/specificity relation between words that are known to be in a semantic relation such as inSanderson & Croft (1999) and Dias et al.

Figure 4

 4 Figure 4.1: Sample calc with all words.

Figure 4

 4 Figure 4.2: Sample calc with list of the stop words .

Figure 4

 4 Figure 4.3: Sample calc with Multiword Units.

  pairs from Corpus TE by Generality, preserving the proportion of 60 T-> H pairs of Entailment by Generality and 40 T-> H pairs of Entailment, but no Generality, and translated this subset into Portuguese using Google Translate 1 service.

  datasets of RTE's Challenges consist of T -H pairs with different levels of entailment reasoning, based on lexical, syntactic, logical and world knowledge at different levels of difficulty. Through this chapter we show also the shortage of works that are language independent, unsupervised and threshold free in RTE Challenge.Supported by the findings of the previous works and the results published inPais et al. (2011) andDias et al. (2011), we conclude that to evaluate the performance of our methodology, we could not just use the pairs of positive TE test datasets of the first five RTE Challenges. We needed a corpus of pairs of TE by Generality. Such a corpus did not exist previously.In Chapter 3, we turn to a crowdsourcing platform called CrowdFlower in order to construct a corpus of pairs where TE by Generality relation holds. As a starting point of this exercise we used the set of the positive pairs from the datasets of the first five RTE Challenges. In this manner we obtained a manually annotated corpus, where the relationship between the text T and the hypothesis H of each pair is Entailment by Generality. This new corpus served us to study the behavior of our methodology.

  To understand how Textual Entailment by Generality can be modeled for two sentences, we propose a new paradigm based on a new Informative Asymmetric Measure (IAM), called the Asymmetric In-foSimba Similarity (AIS) measure. Instead of relying on the exact matches of words between texts, we propose that one sentence infers the other one in terms of generality if two constraints hold:(a) if and only if both sentences share many related words and (b) if most of the words of a given sentence are more general than the words of the other sentence. As far as we know, we are the first to propose an unsupervised, language-independent, threshold free methodology in the context of TE by Generality, although the approach from Glickman & Dagan (2005) is based on similar assumptions. This new proposal is exhaustively evaluated against the first five RTE datasets by testing different Asymmetric Association Measures (AAM) in combination with the AIS. In particular, the RTE-1 as it is the only dataset for which there exist comparable results with linguistic-free methodologies (Bayer

.1 Overview of the First Five RTE Challenges particular

  For example, given the question, "Who is application. A sample of this dataset is given in Table2.1.

	Ariel Sharon?" and taking a candidate answer text "Israel's Prime Minister, Ariel Sharon, visited 2ID TEXT Hypothesis TASK ENTAILMENT Prague." as T, the hypothesis H is formed by turning the question into the statement "Ariel Sharon is Israel's Prime Minister.", thus producing a True entailment pair; 1 iTunes software has seen strong sales in Europe. Strong sales for iTunes in Eu-rope. IR True
	• Collecting Information Extraction (IE) pairs: For this task the annotators used an available dataset annotated for the IE relations "kill" and "birth place" produced by University of Illinois at Urbana-Champaign, as well as general news stories in which they identified manually "typi-2 Cavern Club sessions paid the Beatles £15 evenings and £5 lunchtime. The Beatles perform at Cavern Club at lunchtime. IR True
	cal" IE relations. Given an IE relation of interest, annotators choose T candidate among news story sentences in which the relation holds. As a hypothesis they created a straightforward for-mulation of the IE relation. For example, given the information extraction task of identifying killings of civilians, and a text "Guerrillas killed a peasant in the city of Flores.", a hypothesis "Guerrillas killed a civilian." is created, thus producing a True entailment pair; 3 American Airlines began laying off American Airlines will recall hundreds of flight attendants on Tuesday, after a federal judge the job losses. flights it operates. turned aside a union's bid to block hundreds of flight attendants as it steps up the number of PP False
	The two suspects belong to the
	• Collecting Machine Translation (MT) pairs: Two translations of the same text, an automatic 30th Street gang, which became
	translation and a gold standard human translation, were compared and modified in order to embroiled in one of the most no-
	obtain T -H pairs. The automatic translation was alternately taken as either T or H, where a correct translation corresponds to True entailment. The automatic translations were gram-4 torious recent crimes in Mexico: a shootout at the Guadalajara air-Cardinal Juan Jesus Posadas Ocampo died in 1993. QA True
	matically adjusted whenever needed; port in May, 1993, that killed Car-
	• Collecting Paraphrase Acquisition (PP) pairs: PP systems attempt to generate pairs of ex-dinal Juan Jesus Posadas Ocampo
	pressions that convey mostly equivalent or entailing meanings being at the same time as much and six others.
	grammatically correct as possible. Annotators selected a text T from some news story which Table 2.1: Examples of T -H pairs in RTE-1 (Dagan et al., 2005)
	includes a certain relation, for which a paraphrase acquisition system produced a set of para-
	phrases. Correct paraphrases suggested by the system yielded True T -H pairs; otherwise a
	False example was generated.
	In a second phase of this dataset production process the examples produced by one annotator
	were validated by the other annotator who received only the text and hypothesis pair, without
	any additional information from the original context. The annotators agreed in their judgment
	for roughly 80% of the examples, which corresponded to a 0.6 Kappa level (moderate agreement).
	The 20% of the pairs on which the judges disagreed were discarded. A third person reviewed the
	remaining examples and eliminated about additional 13% of the original examples, which seemed
	controversial.
	The final dataset is believed to represent a broad range of naturally occurring entailment factors.
	However, it is unclear whether it corresponds to a particular representative distribution of these
	factors. Thus, results on this dataset may provide useful indications of system capabilities to
	address various aspects of entailment, but do not predict directly the performance figures within a

Table 2

 2

.5: Examples o T -H pair in RTE-5 (Bentivogli et al., 2009)

  Table 2.5 presents some examples of T -H pairs taken from the RTE-5 data set. The RTE-5 data set consisted of 1.200 T -H pairs -400 for each setting -equally divided into a Development Set and a Test Set. The distribution according to the 3 way annotation, both in the individual settings and in the overall data set, was 50% ENTAILMENT, 35% UNKNOWN, 15% CONTRADICTION.

Table 2

 2

.9: Best Results in

RTE-3 (Giampiccolo et al., 2007)

The GROUNDHOG system

(Hickl & Bensley, 2007)

uses a pipeline of lightweight, largely statistical systems for commitment extraction, lexical alignment, and entailment classification in order to estimate the likelihood that T includes sufficient linguistic content to textually entail H.

As in

RTE-2, Tatu & Moldovan (2007)

based in logical inference, first, they summarize our semantic logical-based approach. The novelties include new resources, such as eXtended WordNet 1 (Harabagiu

Table 2

 2 is used to calculate a global fitness value for current fragments of text. The global fitness value is decreased in cases in which a word from hypothesis cannot be map to one word from the text or when we have different forms of negations for mapped verbs. In the end, using thresholds identified in the training step for global fitness values, they decide for every pair from test data if they have entailment or not.

							System Description
	Participants	Accuracy	Lexical Relation, WordNet	n-gram similarity	Syntactic Matching /	Alignment	Semantic Role Labelling /	Framenet / Propbank, Verbnet	Logical Inference	Corpus /	Web-Based Statistics, LSA	ML Classification	Anaphora resolution	Entailment Corpora -DIRT	Background Knowledge
	Bensley & Hickl (2008)	0,746	X	X					X			X	X		X
	Iftene (2008)	0,721	X			X									X
	Wang &
	Neumann	0,706				X						X
	(2008)
	Li et al. (2008)	0,659	X	X								X
	Balahur et al. (2008)	0,608	X	X		X

.10: Best Results in

RTE-4 (Giampiccolo et al., 2008)

1 Overview of the First Five RTE Challenges alignment

  models, each of which leads to a different type of entailment system. They identify desirable properties of alignment, and use this to inform our implementation of an alignment component.

	Challenge Accuracy Average
	RTE-1	0.581
	RTE-2	0.675
	RTE-3	0.711
	RTE-4	0.688
	RTE-5	0.679
	Participants 2.2 Unsupervised Language-Independent Methodologies for RTE System Description Table 2.12: Average the top five results Accuracy Lexical Relation, WordNet n-gram similarity Syntactic Matching / Alignment Semantic Role Labelling / Framenet / Propbank, Verbnet Logical Inference Corpus / Web-Based Statistics, LSA ML Classification Anaphora resolution	Entailment Corpora -DIRT	Background Knowledge
	Sammons et al. (2009) present an approach to textual entailment recognition, in which inference
	is based on a shallow semantic representation of relations (predicates and their arguments) in the
	text and hypothesis of the entailment pair, and in which specialized knowledge is encapsulated
	in modular components with very simple interfaces. They propose an architecture designed to

Li et al. (2009), they propose an interesting method, SEGraph (Semantic Elements based Graph). This method divides the Hypothesis and Text into two types of semantic elements: Entity Semantic Element and Relation Semantic Element. The SEGraph is then constructed, with Entity Elements as nodes, and Relation Elements as edges for both Text and Hypothesis. They recognize the textual entailment based on the SEGraph of Text and SEGraph of Hypothesis. In Mehdad et al. (2009) use of semantic knowledge based on Wikipedia. More specifically, they used it to enrich the similarity measure between pairs of text and hypothesis (i.e. the tree kernel for text and hypothesis pairs), with a lexical similarity (i.e. the similarity between the leaves of the trees. integrate different, unscaled NLP resources, and demonstrate an alignment-based method for combining them. They clarify the purpose of alignment in the RTE task, identifying two distinct 2.Different approaches have been proposed to recognize Textual Entailment: from unsupervised language-independent methodologies Glickman & Dagan (2005), Perez et al. (2005) and Bayer et al.

(2005)

to deep linguistic analysis. We will particularly detail the unsupervised language-independent approaches, to which our work can be directly compared, at least to a certain extent. One of the most simple proposals

(Perez et al., 2005)

explores the BLEU algorithm

Papineni et al. (2002)

.

Table 3 .

 3 1: Summary of RTE by Generality corpus annotation task

		RTE-1 RTE-2 RTE-3 RTE-4 RTE-5
	# Input Pairs 1	400	400	400	500	300
	# Pairs to Launch 2			1740
	# Gold Pairs 3			260
	# Output Pairs 4			1203
	# Discarded Pairs 5			797
	Evaluation Time 6			≈43 days
	# Trusted "Turkers"			2308
	# Trusted Judgments			5220 (1740*3)
	# Untrusted Judgments			60482
	Cost ($)			108,08

In total, 2000 pairs were upload to CrowdFlower. Table

3

.1 evidences that the annotated corpus contains 1203 T -H pairs that are in TE by Generality relation.

6

Each case was evaluated by three "Turkers" for final average inter-annotator agreement of 0, 8.

This task proved to be complicated for the "Turkers", as it is difficult for a human annotators to identify entailment relation and entailment by generality in particular. Proof of this is the time spent to complete the task (Evaluation Time) and the total number of Judgments (Trusted + Untrusted) needed to achieve the final objective. The result of our work is the first large-scale dataset containing a reasonable number of pairs that are in TE by Generality relation. 0 Number of pairs T-> H uploaded 1 Number of pairs T-> H submitted for evaluation 2 Number of "Gold" pairs T-> H 3 Number of pairs T-> H classified as "Entailment by Generality" 4 Number of pairs T-> H classified as "Entailment, but not Generality" or "Other" 5 Time accomplish the task C 4

  and applied to the problems of taxonomy construction(Cleuziou et al., 2010; Sanderson & Croft, 1999), cognitive psycholinguistics(Michelbacher et al., 2007) and general-specific word order induction(Dias et al., 2008).They assume that a term t 2 subsumes a term t 1 if the documents in which t 1 occurs are a subset of the documents in which t 2 occurs constrained by P(t 2 |t 1 ) ≥ 0.8 and P(t 1 |t 2 ) < 1. By gathering all subsumption relations, they build the semantic structure of any domain, which corresponds to a directed acyclic graph. InSanderson & Lawrie (2000), the subsumption relation is relieved to the fol-

	Sanderson & Croft (1999) is certainly one of the first studies to propose the use of the conditional
	probability, Equation 4.1, for taxonomy construction.
	P(x|y) =	P(x, y) P(y)	.	(4.1)

lowing expression P(t 2 |t 1 ) ≥ P(t 1 |t 2 ) and P(t 2 |t 1 ) > t where t is a given threshold and all term pairs found to have a subsumption relationship are passed through a transitivity module, which removes extraneous subsumption relationships in the way that transitivity is preferred over direct pathways, thus leading to a non-triangular directed acyclic graph.

Michelbacher et al.

Table 4

 4

	.1: Web frequencies for calculations with All Words
	W i Frequency	W j Frequency
	Rumen	14700000 Rumen	14700000
	studies 261000000 studies 261000000
	in 505400000	in 505400000
	Paris 437000000 France 838000000
	Table 4.2: Web frequencies for calculations with All Words
			Frequency
	W i	W j	W i ∩ W j	W j ∩ W i
	Rumen studies	2080000	2080000
	Rumen	in	15700000	15600000
	Rumen France	994000	994000
	studies	in	10900000	10900000
	studies France 190000000 190000000
	in France 226000000 226000000
	Paris Rumen	688000	688000

  001 + 0.024 + (-0.006)) × (0.020 + (-0.100) + 0.105)× (0.833 + (-0.194) + 0.034) × ( -0.157 + 0.387 + 0.058 + 0.176)

	 
	=0.063 × (0.019 × 0.024 × 0.673 × 0.464)
	=0.063 × (0.000142)
	=0.0000089	(4.14)

Table 5

 5

.1: Contingency table for evaluating a binary classifier. For example, a is the number of objects in the category of interest that were correctly assigned to the category.

(Manning & Schütze, 1999)

For binary classification, classifiers are typically evaluated using a table of counts like table 5.1. An important measure is classification Accuracy (AC) and Precision (P) which is defined in equation 5.1 and equation 5.2, respectively.

Table 5 .

 5 2: Accuracy Average by RTE Challenges | With All Words

	ACCURACY by RTE Challenges
				Arithmetic Average
	AAM	RTE-1 RTE-2 RTE-3 RTE-4 RTE-5 Average
	ADDED VALUE	0,53	0,52	0,51	0,58	0,55	0,54
	BRAUN-BLANKET	0,53	0,51	0,52	0,59	0,58	0,55
	CERTAINTY FACTOR	0,51	0,52	0,52	0,56	0,56	0,53
	CONDITIONAL PROBABILITY	0,50	0,52	0,51	0,58	0,55	0,53
	CONVICTION	0,48	0,50	0,49	0,57	0,53	0,52
	GINI INDEX	0,48	0,52	0,53	0,58	0,57	0,54
	J-MEASURE	0,52	0,50	0,51	0,60	0,53	0,53
	LAPLACE	0,50	0,52	0,51	0,56	0,55	0,53
				Weighted Average
	AAM	RTE-1 RTE-2 RTE-3 RTE-4 RTE-5 Average
	ADDED VALUE	0,52	-	0,51	0,58	-	0,53
	BRAUN-BLANKET	0,51	-	0,52	0,58	-	0,54
	CERTAINTY FACTOR	0,51	-	0,52	0,55	-	0,53
	CONDITIONAL PROBABILITY	0,50	-	0,51	0,57	-	0,53
	CONVICTION	0,49	-	0,49	0,57	-	0,52
	GINI INDEX	0,48	-	0,53	0,59	-	0,53
	J-MEASURE	0,51	-	0,51	0,61	-	0,54
	LAPLACE	0,50	-	0,51	0,56	-	0,52
	Table

Table 5

 5

	.3: PRECISION -ENTAILMENT Average by RTE Challenges | With All Words
	PRECISION -ENTAILMENT by RTE Challenges
				Arithmetic Average
	AAM	RTE-1 RTE-2 RTE-3 RTE-4 RTE-5 Average
	ADDED VALUE	0,48	0,85	0,63	0,69	0,67	0,66
	BRAUN-BLANKET	0,43	0,62	0,47	0,57	0,57	0,53
	CERTAINTY FACTOR	0,47	0,80	0,58	0,67	0,63	0,63
	CONDITIONAL PROBABILITY	0,44	0,83	0,61	0,67	0,66	0,64
	CONVICTION	0,53	0,58	0,60	0,63	0,64	0,60
	GINI INDEX	0,53	0,81	0,63	0,70	0,69	0,67
	J-MEASURE	0,52	0,91	0,84	0,87	0,89	0,81
	LAPLACE	0,44	0,83	0,61	0,72	0,66	0,65
				Weighted Average
	AAM	RTE-1 RTE-2 RTE-3 RTE-4 RTE-5 Average
	ADDED VALUE	0,49	-	0,64	0,67	-	0,60
	BRAUN-BLANKET	0,44	-	0,48	0,56	-	0,49
	CERTAINTY FACTOR	0,48	-	0,60	0,65	-	0,58
	CONDITIONAL PROBABILITY	0,45	-	0,63	0,65	-	0,58
	CONVICTION	0,54	-	0,59	0,64	-	0,59
	GINI INDEX	0,53	-	0,64	0,70	-	0,62
	J-MEASURE	0,51	-	0,84	0,86	-	0,73
	LAPLACE	0,45	-	0,63	0,71	-	0,59

Table 5

 5

	.4: PRECISION -NO ENTAILMENT Average by RTE Challenges | With All Words
	PRECISION -NO ENTAILMENT by RTE Challenges
				Arithmetic Average
	AAM	RTE-1 RTE-2 RTE-3 RTE-4 RTE-5 Average
	ADDED VALUE	0,57	0,20	0,36	0,47	0,42	0,40
	BRAUN-BLANKET	0,62	0,40	0,56	0,61	0,59	0,56
	CERTAINTY FACTOR	0,55	0,24	0,43	0,44	0,48	0,43
	CONDITIONAL PROBABILITY	0,57	0,22	0,37	0,50	0,43	0,42
	CONVICTION	0,43	0,42	0,40	0,52	0,42	0,44
	GINI INDEX	0,42	0,24	0,40	0,47	0,44	0,39
	J-MEASURE	0,52	0,09	0,17	0,34	0,17	0,26
	LAPLACE	0,56	0,22	0,37	0,40	0,43	0,40
				Weighted Average
	AAM	RTE-1 RTE-2 RTE-3 RTE-4 RTE-5 Average
	ADDED VALUE	0,63	-	0,37	0,49	-	0,49
	BRAUN-BLANKET	0,67	-	0,57	0,61	-	0,62
	CERTAINTY FACTOR	0,61	-	0,44	0,45	-	0,50
	CONDITIONAL PROBABILITY	0,63	-	0,38	0,49	-	0,50
	CONVICTION	0,50	-	0,39	0,49	-	0,46
	GINI INDEX	0,49	-	0,41	0,48	-	0,46
	J-MEASURE	0,58	-	0,17	0,36	-	0,37
	LAPLACE	0,62	-	0,38	0,41	-	0,47

Table 5

 5

	.5: Accuracy Average by RTE Challenges | Without Stop Words
	ACCURACY by RTE Challenges
				Arithmetic Average
	AAM	RTE-1 RTE-2 RTE-3 RTE-4 RTE-5 Average
	ADDED VALUE	0,50	0,52	0,52	0,55	0,54	0,52
	BRAUN-BLANKET	0,52	0,50	0,52	0,54	0,56	0,53
	CERTAINTY FACTOR	0,50	0,51	0,51	0,57	0,54	0,53
	CONDITIONAL PROBABILITY	0,51	0,52	0,52	0,56	0,54	0,53
	CONVICTION	0,51	0,53	0,49	0,50	0,54	0,51
	GINI INDEX	0,51	0,50	0,50	0,55	0,52	0,51
	J-MEASURE	0,50	0,49	0,51	0,53	0,52	0,51
	LAPLACE	0,51	0,52	0,52	0,53	0,55	0,53
				Weighted Average
	AAM	RTE-1 RTE-2 RTE-3 RTE-4 RTE-5 Average
	ADDED VALUE	0,50	-	0,52	0,54	-	0,52
	BRAUN-BLANKET	0,52	-	0,52	0,53	-	0,52
	CERTAINTY FACTOR	0,50	-	0,51	0,57	-	0,53
	CONDITIONAL PROBABILITY	0,51	-	0,52	0,55	-	0,53
	CONVICTION	0,51	-	0,49	0,50	-	0,50
	GINI INDEX	0,51	-	0,50	0,55	-	0,52
	J-MEASURE	0,50	-	0,51	0,53	-	0,51
	LAPLACE	0,51	-	0,52	0,52	-	0,52

Table 5 .

 5 7: PRECISION -NO ENTAILMENT Average by RTE Challenges | Without Stop Words

	PRECISION -NO ENTAILMENT by RTE Challenges
				Arithmetic Average
	AAM	RTE-1 RTE-2 RTE-3 RTE-4 RTE-5 Average
	ADDED VALUE	0,56	0,24	0,36	0,43	0,36	0,39
	BRAUN-BLANKET	0,62	0,28	0,44	0,47	0,48	0,46
	CERTAINTY FACTOR	0,56	0,28	0,41	0,48	0,44	0,44
	CONDITIONAL PROBABILITY	0,60	0,26	0,37	0,44	0,41	0,41
	CONVICTION	0,46	0,51	0,47	0,46	0,54	0,49
	GINI INDEX	0,54	0,38	0,46	0,54	0,47	0,48
	J-MEASURE	0,57	0,09	0,21	0,28	0,21	0,27
	LAPLACE	0,59	0,26	0,37	0,42	0,39	0,41
				Weighted Average
	AAM	RTE-1 RTE-2 RTE-3 RTE-4 RTE-5 Average
	ADDED VALUE	0,64	-	0,37	0,42	-	0,48
	BRAUN-BLANKET	0,70	-	0,45	0,45	-	0,53
	CERTAINTY FACTOR	0,63	-	0,41	0,48	-	0,51
	CONDITIONAL PROBABILITY	0,67	-	0,37	0,43	-	0,49
	CONVICTION	0,53	-	0,47	0,47	-	0,49
	GINI INDEX	0,61	-	0,46	0,53	-	0,53
	J-MEASURE	0,65	-	0,21	0,28	-	0,38
	LAPLACE	0,67	-	0,37	0,41	-	0,48

Table 5

 5

	.8: Accuracy Average by RTE Challenges | With MWU
	ACCURACY by RTE Challenges
				Arithmetic Average
	AAM	RTE-1 RTE-2 RTE-3 RTE-4 RTE-5 Average
	ADDED VALUE	0,50	0,51	0,52	0,57	0,57	0,53
	BRAUN-BLANKET	0,53	0,51	0,53	0,55	0,58	0,54
	CERTAINTY FACTOR	0,52	0,51	0,51	0,54	0,55	0,53
	CONDITIONAL PROBABILITY	0,51	0,51	0,52	0,57	0,55	0,53
	CONVICTION	0,48	0,48	0,51	0,55	0,54	0,51
	GINI INDEX	0,49	0,51	0,52	0,58	0,56	0,53
	J-MEASURE	0,51	0,49	0,51	0,56	0,53	0,52
	LAPLACE	0,52	0,51	0,52	0,56	0,56	0,53
				Weighted Average
	AAM	RTE-1 RTE-2 RTE-3 RTE-4 RTE-5 Average
	ADDED VALUE	0,50	-	0,52	0,57	-	0,53
	BRAUN-BLANKET	0,61	-	0,53	0,55	-	0,56
	CERTAINTY FACTOR	0,51	-	0,51	0,53	-	0,52
	CONDITIONAL PROBABILITY	0,51	-	0,52	0,57	-	0,53
	CONVICTION	0,48	-	0,51	0,55	-	0,51
	GINI INDEX	0,49	-	0,52	0,57	-	0,53
	J-MEASURE	0,50	-	0,51	0,56	-	0,52
	LAPLACE	0,61	-	0,52	0,56	-	0,56
	Weighted Average. In this case, our methodology has better performance compared to the
	methodologies presented in Section 2.2, namely, Bayer et al. (2005), Glickman & Dagan (2005) and
	Perez et al. (2005), as they obtained 0, 586, 0, 586 and 0, 495. The RTE-4 and RTE-5 data sets afford

In particular, these last two measures, Braun-Blanket and Laplace, achieve 0, 61 in RTE-1 for for the best performance in this approach. RTE-1 and RTE-2 data sets, likewise in the previous approaches, exhibit low performance.

Table 5

 5

	.9: PRECISION -ENTAILMENT Average by RTE Challenges | With MWU
	PRECISION -ENTAILMENT by RTE Challenges
				Arithmetic Average
	AAM	RTE-1 RTE-2 RTE-3 RTE-4 RTE-5 Average
	ADDED VALUE	0,78	0,90	0,72	0,73	0,78	0,78
	BRAUN-BLANKET	0,55	0,77	0,57	0,63	0,63	0,63
	CERTAINTY FACTOR	0,49	0,45	0,43	0,46	0,46	0,46
	CONDITIONAL PROBABILITY	0,43	0,44	0,46	0,55	0,49	0,48
	CONVICTION	0,46	0,51	0,56	0,56	0,61	0,54
	GINI INDEX	0,45	0,49	0,55	0,59	0,58	0,53
	J-MEASURE	0,57	0,55	0,67	0,68	0,67	0,63
	LAPLACE	0,44	0,44	0,46	0,52	0,49	0,47
				Weighted Average
	AAM	RTE-1 RTE-2 RTE-3 RTE-4 RTE-5 Average
	ADDED VALUE	0,79	-	0,73	0,71	-	0,74
	BRAUN-BLANKET	0,55	-	0,58	0,61	-	0,58
	CERTAINTY FACTOR	0,49	-	0,44	0,44	-	0,46
	CONDITIONAL PROBABILITY	0,43	-	0,47	0,54	-	0,48
	CONVICTION	0,48	-	0,55	0,57	-	0,53
	GINI INDEX	0,45	-	0,55	0,58	-	0,53
	J-MEASURE	0,56	-	0,67	0,68	-	0,63
	LAPLACE	0,44	-	0,47	0,51	-	0,48
	When we analyze Table 5.10, three measures stand out with good results, namely Certainty Factor,
	Conditional Probability and Laplace, where the latter two achieve a maximum precision of 0, 67.

The worst results are obtained with Added Value (0, 21 and 0, 23 on RTE-1) which, on the other hand, obtained strong results in Precision -Entailment (see Table

5

.9). The RTE-5 data set affords the best performance.

Table 5 .

 5 10: PRECISION -NO ENTAILMENT Average by RTE Challenges | With MWU

	PRECISION -NO ENTAILMENT by RTE Challenges
				Arithmetic Average
	AAM	RTE-1 RTE-2 RTE-3 RTE-4 RTE-5 Average
	ADDED VALUE	0,21	0,11	0,29	0,42	0,36	0,28
	BRAUN-BLANKET	0,50	0,26	0,47	0,47	0,53	0,45
	CERTAINTY FACTOR	0,54	0,58	0,59	0,62	0,63	0,59
	CONDITIONAL PROBABILITY	0,59	0,57	0,57	0,60	0,62	0,59
	CONVICTION	0,49	0,45	0,47	0,53	0,48	0,48
	GINI INDEX	0,52	0,53	0,49	0,56	0,54	0,53
	J-MEASURE	0,45	0,44	0,35	0,45	0,39	0,42
	LAPLACE	0,59	0,57	0,57	0,61	0,63	0,59
				Weighted Average
	AAM	RTE-1 RTE-2 RTE-3 RTE-4 RTE-5 Average
	ADDED VALUE	0,23	-	0,31	0,43	-	0,32
	BRAUN-BLANKET	0,56	-	0,48	0,48	-	0,51
	CERTAINTY FACTOR	0,61	-	0,59	0,62	-	0,60
	CONDITIONAL PROBABILITY	0,67	-	0,57	0,59	-	0,61
	CONVICTION	0,55	-	0,47	0,52	-	0,52
	GINI INDEX	0,61	-	0,49	0,56	-	0,55
	J-MEASURE	0,51	-	0,35	0,44	-	0,43
	LAPLACE	0,67	-	0,57	0,61	-	0,62

2 All pairs of the Test Set of the first five RTE Challenges Precision -No Entailment With Multiword Units approach

  Table 5.2 and Table 5.5, considering per challenge results, we conclude that RTE-4 is associated to improved accuracy for approach All Words and Without Stop Words compared to other data sets. The best accuracy of the approach With MWU is achieved on RTE-4 is achieved on RTE-5 data set. Regarding the Arithmetic Average (Table 5.11), the combination that has the best performance is the Braun-Blanket measure on All Words. Best Weighted Average is achieved on With WMU approach by Braun-Blanket and Laplace measures. Overall, the worst result was obtained with the measure Conviction in approach Without Stop Words.

	and RTE-5 data sets, as evidenced in Table 5.8.
	With respect to Precision -Entailment, Table 5.3, Table 5.6 and Table 5.9, RTE-2 affords best

results with All Words and Without Stop Words approaches, while With Multiword Units approach works best on RTE-5 data set. With respect to Precision -No Entailment, Table 5.4, Table 5.7 and Table 5.10, RTE-1 affords best results with All Words and Without Stop Words. Similarly to Precision -Entailment, the best 5.

Table 5 .

 5 11: Accuracy Averages | Measures versus Approach

Averages ACCURACY by RTE Challenges | Measures versus Approach AAM Arithmetic Average by Approach With All Words Without Stop Words With MWU

	ADDED VALUE	0,54	0,52	0,53
	BRAUN-BLANKET	0,55	0,53	0,54
	CERTAINTY FACTOR	0,53	0,53	0,53
	CONDITIONAL PROBABILITY	0,53	0,53	0,53
	CONVICTION	0,52	0,51	0,51
	GINI INDEX	0,54	0,51	0,53
	J-MEASURE	0,53	0,51	0,52
	LAPLACE	0,53	0,53	0,53
		Weighted Average by Approach
	AAM	With All Words Without Stop Words With MWU
	ADDED VALUE	0,53	0,52	0,53
	BRAUN-BLANKET	0,54	0,52	0,56
	CERTAINTY FACTOR	0,53	0,53	0,52
	CONDITIONAL PROBABILITY	0,53	0,53	0,53
	CONVICTION	0,52	0,50	0,51
	GINI INDEX	0,53	0,52	0,53
	J-MEASURE	0,54	0,51	0,52
	LAPLACE	0,52	0,52	0,56

Table 5 .

 5 11 points out the approach Without Stop Words as the one with worst performance in terms of accuracy, while All Words achieves slightly better accuracy compared to With MWU.

The combination with the best performance on the Arithmetic Average Precision is the measure J-measure with approach All Words. For the Weighted Average Precision, Added Value shows the best result With MWU. The worst result is obtained with measure Conviction With MWU -0, 46.

Table 5 .

 5 12: PRECISION -ENTAILMENT Averages | Measures versus Approach

Average PRECISION -ENTAILMENT by RTE Challenges | Measures versus Approach AAM Arithmetic Average by Approach With All Words Without Stop Words With MWU

  Laplace has the best performance With MWU approach. Note the low results obtained by J-measure and Added Value. In Table5.13 the approach with the best performance is With MWU, and the worst performing approach is Without Stop Words.

	ADDED VALUE	0,66	0,65	0,78
	BRAUN-BLANKET	0,53	0,60	0,63
	CERTAINTY FACTOR	0,63	0,62	0,46
	CONDITIONAL PROBABILITY	0,64	0,64	0,48
	CONVICTION	0,60	0,54	0,54
	GINI INDEX	0,67	0,55	0,53
	J-MEASURE	0,81	0,75	0,63
	LAPLACE	0,65	0,64	0,47
		Weighted Average by Approach
	AAM	With All Words Without Stop Words	With MWU
	ADDED VALUE	0,60	0,59	0,74
	BRAUN-BLANKET	0,49	0,54	0,58
	CERTAINTY FACTOR	0,58	0,57	0,46
	CONDITIONAL PROBABILITY	0,58	0,58	0,48
	CONVICTION	0,59	0,53	0,53
	GINI INDEX	0,62	0,52	0,53
	J-MEASURE	0,73	0,66	0,63
	LAPLACE	0,59	0,57	0,48
	After an exhaustive study and analysis of the results obtained from the application of our method-
	ology, we can compare our results with the results of the methodologies presented in Section 2.2,

With respect to Precision -Entailment criterion, the approach that achieves the best results is With All Words.

In contrast to the results for

Precision -Entailment, our method shows unsatisfactory behavior when considered from the perspective of Precision -No Entailment. For Arithmetic Average the best combination is Certainty Factor, Conditional Probability and Laplace With MWU. For Weighted Average, namely, Bayer et al. (2005), Glickman & Dagan (2005) and Perez et al.

Table 5 .

 5 13: PRECISION -NO ENTAILMENT Averages | Measures versus Approach

	Average PRECISION -NO ENTAILMENT by RTE Challenges | Measures versus Approach
			Arithmetic Average by Approach
	AAM	With All Words Without Stop Words	With MWU
	ADDED VALUE	0,40	0,39	0,28
	BRAUN-BLANKET	0,56	0,46	0,45
	CERTAINTY FACTOR	0,43	0,44	0,59
	CONDITIONAL PROBABILITY	0,42	0,41	0,59
	CONVICTION	0,44	0,49	0,48
	GINI INDEX	0,39	0,48	0,53
	J-MEASURE	0,26	0,27	0,42
	LAPLACE	0,40	0,41	0,59
			Weighted Average by Approach
	AAM	With All Words Without Stop Words	With MWU
	ADDED VALUE	0,49	0,48	0,32
	BRAUN-BLANKET	0,62	0,53	0,51
	CERTAINTY FACTOR	0,50	0,51	0,60
	CONDITIONAL PROBABILITY	0,50	0,49	0,61
	CONVICTION	0,46	0,49	0,52
	GINI INDEX	0,46	0,53	0,55
	J-MEASURE	0,37	0,38	0,43
	LAPLACE	0,47	0,48	0,62

Table 5 .

 5 16: Confusion Matrix for all AAM | Without Stop Words

		System Response
	AAM	A	B

Table 5

 5

	AAM	Accuracy	Precision A B
	ADDED VALUE	0,63	0,74	0,47
	BRAUN-BLANKET	0,73 0,80 0,62
	CERTAINTY FACTOR	0,63	0,67	0,56
	CONDITIONAL PROBABILITY	0,60	0,70	0,44
	CONVICTION	0,59	0,63	0,52
	GINI INDEX	0,64	0,72	0,51
	J-MEASURE	0,64	0,78	0,43
	LAPLACE	0,62	0,69	0,51

.17 shows that likewise the best performing measure in approach "With All Words", in the present approach the best performing measure with respect to Accuracy and Precision -Entailment by Generality is Braun-Blanket. In this case, Conviction and J-measure are the measures with the worst performance.

Table 5

 5

		.18: Confusion Matrix for all AAM | With MWU
				System Response
		AAM		A	B
		Added Value	A B	987 216	408 389
			A 1113	214
		Braun-Blanket	B	90	583
			A	756	265
		Certainty Factor	B	447	532
			A	773	296
	Gold Standard	Conditional Probability Conviction	B A B A	430 674 529 786	501 396 401 233
		Gini Index	B	417	564
			A	765	356
		J-measure	B	438	441
			A	703	296
		Laplace	B	500	501

Table 5

 5

	.19: Accuracy and Precision by AAM | All MWU
	AAM	Accuracy	Precision A B
	ADDED VALUE	0,69	0,82	0,49
	BRAUN-BLANKET	0,85 0,93 0,73
	CERTAINTY FACTOR	0,64	0,63	0,68
	CONDITIONAL PROBABILITY	0,64	0,64	0,63
	CONVICTION	0,54	0,56	0,50
	GINI INDEX	0,68	0,65	0,71
	J-MEASURE	0,60	0,64	0,55
	LAPLACE	0,60	0,58	0,63

Table 5 .

 5 22: Confusion Matrix for all AAM | All Words

		System Response
	AAM	A	B

Table 5 .

 5 23: Accuracy and Precision by AAM | All Words

	AAM	Accuracy	Precision A B
	ADDED VALUE	0,63	0,78	0,4
	BRAUN-BLANKET	0,62	0,65	0,58
	CERTAINTY FACTOR	0,64	0,68	0,58
	CONDITIONAL PROBABILITY	0,59	0,68	0,45
	CONVICTION	0,68	0,73	0,6
	GINI INDEX	0,66	0,72	0,58
	J-MEASURE	0,72 0,85 0,53
	LAPLACE	0,61	0,7	0,48
	From Table

Table 5 .

 5 25 shows that the AAM with the best performance is the Braun-Blanket.

		13	15
		A 47	16
	Braun-Blanket	B 13	24
		A 39	17
	Certainty Factor	B 21	23
		A 39	22
	Conditional Probability	B 21	18
		A 39	19
	Conviction	B 21	21
		A 45	19
	Gini Index	B 15	21
		A 43	25
	J-measure	B 17	15
		A 43	21
	Laplace	B 17	19

With respect to Accuracy and Precision for "Entailment, but no Generality" in the preset approach the best performing measure is Braun-Blanket. With respect to Precision for "Entailment by Generality" the measures Braun-Blanket and Added Value are the best performing measures, however, Added Value is the worst performing measure when Precision for "Entailment, but no Generality" is considered. Conditional Probability is the measure with the worst performance when compared by Accuracy criterion. The worst performers with respect to Precision for "Entailment by Generality" are Certainty Factor, Conditional Probability and Conviction measures.

Table 5 .

 5 26: Confusion Matrix for all AAM | With MWU

		System Response
	AAM	A	B

Table 5 .

 5 27: Accuracy and Precision by AAM | All MWU

	AAM	Accuracy	Precision A B
	ADDED VALUE	0,69	0,85	0,45
	BRAUN-BLANKET	0,76 0,88 0,58
	CERTAINTY FACTOR	0,63	0,6	0,68
	CONDITIONAL PROBABILITY	0,6	0,62	0,58
	CONVICTION	0,5	0,55	0,43
	GINI INDEX	0,68	0,68	0,68
	J-MEASURE	0,6	0,62	0,58
	LAPLACE	0,63	0,6	0,68

  The worst results are achieved in With MWU by

	AAM	Precision for A All Words Without Stop Words With MWU
	ADDED VALUE	0,78	0,78	0,85
	BRAUN-BLANKET	0,65	0,78	0,88
	CERTAINTY FACTOR	0,68	0,65	0,6
	CONDITIONAL PROBABILITY	0,68	0,65	0,62
	CONVICTION	0,73	0,65	0,55
	GINI INDEX	0,72	0,75	0,68
	J-MEASURE	0,85	0,72	0,62
	LAPLACE	0,7	0,72	0,6
	AAM	Precision for B All Words Without Stop Words With MWU
	ADDED VALUE	0,4	0,38	0,45
	BRAUN-BLANKET	0,58	0,6	0,58
	CERTAINTY FACTOR	0,58	0,58	0,68
	CONDITIONAL PROBABILITY	0,45	0,45	0,58
	CONVICTION	0,6	0,52	0,43
	GINI INDEX	0,58	0,53	0,68
	J-MEASURE	0,53	0,38	0,58
	LAPLACE	0,48	0,48	0,68
	Certainty Factor and Laplace, 0, 6.

With respect to "Precision -Entailment, but no Generality" the results are markedly lower. The best results are achieved in With MWU by Certainty Factor, Gini Index and Laplace with value of 0, 68. Moreover, the worst results are achieved by Added Value, 0, 38, in All Words.

Table B .

 B 1: MWU extracted from the first five RTE dataset test.

				B.1 Multiword Units in English B.1 Multiword Units in English B.1 Multiword Units in English B.1 Multiword Units in English B.1 Multiword Units in English B.1 Multiword Units in English B.1 Multiword Units in English B.1 Multiword Units in English
	B.2	Table B.1: (continued) Table B.1: (continued) Table B.1: (continued) Table B.1: (continued) Table B.1: (continued) Table B.1: (continued) Table B.1: (continued) Table B.1: (continued) Table B.1: (continued) Table B.1: (continued) Table B.1: (continued)
		Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency	MWU MWU MWU MWU MWU MWU MWU MWU	MWU MWU MWU MWU MWU MWU MWU MWU
		0.00007995819760 34 0.00004880493361 14 0.00003486066635 8 0.00002728225991 12 0.00002247595512 7 0.00001845564657 12 0.00001743033317 4 0.00001497346329 35 0.00001307274943 3 0.00001120521392 3 0.00000929617727 4 0.00000871516659 2 0.00000820250989 4 0.00000688605769 8 0.00000558664533 5 0.00000361625166 70		human rights Alfredo Cristiani Sharm el-Sheikh interest rates Wolfgang von Foreign Affairs Budleigh Salterton can be Alexandre Berthier Hugo Chávez advisory panel Malcolm Brabant attorney fees growth rate Ryder Cup over the
		0.00007566171553 44 0.00004826861550 12 0.00003486066635 8 0.00002728225991 12 0.00002247595512 7 0.00001845564657 6 0.00001743033317 4 0.00001480157334 25 0.00001297768631 92 0.00001120521392 3 0.00000896417168 12 0.00000871516659 2 0.00000784364966 3 0.00000680872381 5 0.00000537707729 25 0.00000358648822 10		South Africa Wye Plantation Raman Raghav Baptist Church Joseph Wilson vision goggles Borislav Shervinsky does not for a Gilda Flores member states Lindsay Ellis Samir Geagea tropical storm said it three months
		0.00007240292325 18 0.00004826861550 12 0.00003486066635 8 0.00002724220394 124 0.00002241042785 18 0.00001845564657 6 0.00001743033317 4 0.00001452527795 5 0.00001283506390 9 0.00001108490596 103 0.00000896417168 6 0.00000871516659 2 0.00000784364966 3 0.00000664405570 74 0.00000531210162 8 0.00000353019414 8		Romano Prodi Jean Hackett Mo Siegel as a car bomb Princess Diana Aurore Paquiss Margaret Thatcher Air Force to a intensive care Les Combes Jacques Delors of its second round returned home
		0.00007196237857 17 0.00004793341577 11 0.00003486066635 8 0.00002715109622 9 0.00002241042785 6 0.00001845564657 6 0.00001743033317 4 0.00001447458817 91 0.00001267660627 8 0.00001082987637 13 0.00000871516659 4 0.00000871516659 2 0.00000784364966 3 0.00000664012668 4 0.00000508384710 7 0.00000348606659 2	al Qaeda Chen Shui-bian Chadrick Fulks Hurricane Katrina Willy Claes long-term accommodation Andre Agassi with a industrial espionage foreign minister Yitzhak Rabin Kiryat Arba Houston multimillionaire Warner Village heart disease Sue Robbins
		0.00007069162530 318 0.00004751171582 13 0.00003486066635 8 0.00002670178765 12 0.00002241042785 6 0.00001815659743 10 0.00001743033317 4 0.00001426118160 6 0.00001267660627 4 0.00001077239449 24 0.00000871516659 4 0.00000871516659 2 0.00000784364966 3 0.00000664012668 4 0.00000498009513 6 0.00000348606659 2		at the Qin Shi Carrie Tomlinson Stephen Hawking Javier Solana arms embargo Alaattin Cakici Super Bowl Writer Samir three years Ohama Beach Kaspersky Labs hot springs Van Hasselt steel manufacturer Mary Vattimo
		0.00007027052197 278 0.00004694384552 260 0.00003404583185 31 0.00002621812564 76 0.00002241042785 6 0.00001815659743 5 0.00001743033317 4 0.00001426118160 6 0.00001267660627 4 0.00001072635860 4 0.00000871516659 4 0.00000871516659 2 0.00000784364966 3 0.00000664012668 4 0.00000498009513 2 0.00000348606659 2		in a from the carried out that he Father Bátiz Jesse Owens Agua Dulce Mount Graham Sony BMG Valdez Principles minke whales Karl Rove Genghis Khan Channel Tunnel Tennessee Tech Jim Lankes
		0.00006972133269 16 0.00004648088725 12 0.00003401726281 11 0.00002614549885 6 0.00002241042785 6 0.00001743033317 4 0.00001708172567 7 0.00001394426636 4 0.00001267660627 4 0.00001072635860 4 0.00000871516659 4 0.00000871516659 2 0.00000774681484 4 0.00000664012668 4 0.00000498009513 2 0.00000348606659 2		Vladislav Listyev Standard Model Nick Leeson Ulan Bator Crathes castle Zack Urlocker gold medals Vue Cinemas parking garage Moroccan delegation Korkmaz Yigit Jubiz Hazvumb Bosnian Serb ballistic missile Iron Curtain burning backpack
		0.00006972133269 16 0.00004440148041 22 0.00003358244066 17 0.00002614549885 6 0.00002241042785 6 0.00001743033317 4 0.00001708172567 7 0.00001394426636 4 0.00001267660627 4 0.00001072635860 4 0.00000871516659 4 0.00000871516659 2 0.00000774681484 4 0.00000659084481 11 0.00000473047794 80 0.00000348606659 2		Celestial Seasonings Latin America mercy killing Radovan Karadzic Aldrich Hazen Yom Kippur Colin Powell Todd Keys Judith Miller modem connections Klaus Wowereit Henrik Larsson beauty contests war crimes the US Brian Goodell
		0.00006850526552 26 0.00004361355968 34 0.00003295422357 11 0.00002614549885 6 0.00002218406007 42 0.00001743033317 4 0.00001660685302 22 0.00001394426636 4 0.00001267660627 4 0.00001071536917 15 0.00000871516659 4 0.00000871516659 2 0.00000764155902 11 0.00000653637471 3 0.00000466095935 13 0.00000348606659 2		Yasser Arafat oil prices Real Madrid Niel Tupas could be Viroj Laohaphan set up terminally ill Houston Rockets security forces Klaus Pohl Helicobacter pylori six months Fidel Castro 2 million Bob Geldof
		0.00006850526552 26 0.00004357583384 15 0.00003281003956 8 0.00002614549885 6 0.00002178791692 5 0.00001743033317 4 0.00001651294770 6 0.00001394426636 4 0.00001256009273 7 0.00001067607900 7 0.00000871516659 4 0.00000871516659 2 0.00000756014470 12 0.00000647035085 7 0.00000461391164 6 0.00000348606659 2		Nelson Mandela organizing committee Vicente Fox Costa Rica Mabel Normand Trevi Fountain Secret Service Soto Toro Wall Street mobile phones Frank Costello Guillermo Ortiz Mr Putin border dispute King Abdullah Allan Chapman
		Mutual Expectation Frequency 0.00006723128172 18 0.00004357583384 10 0.00003281003956 8 0.00002614549885 6 0.00002178791692 5 0.00001743033317 4 0.00001651294770 6 0.00001394426636 4 0.00001254983999 6 0.00001063322907 121 0.00000871516659 3 0.00000871516659 2 0.00000751307471 5 0.00000642330406 93 0.00000435758329 3 0.00000348606659 2	MWU Li Zhaoxing virtual reality serial killer conscientious objectors Kurt Cobain Tel Aviv Dalai Lama Perez Quiron Katharine Hepburn after the São Paulo Gene Bartow Alfred Hitchcock during the polling stations 221 BCE
		0.00152795552276 1791 0.00006562007911 16 0.00004357583384 10 0.00003281003956 8 0.00002614549885 6 0.00002178791692 5 0.00001743033317 4 0.00001651294770 6 0.00001394426636 4 0.00001237700144 13 0.00001054608401 12 0.00000871516659 3 0.00000871516659 2 0.00000733908746 8 0.00000633830314 4 0.00000435758329 2 0.00000342776184 54		of the Aki Kaurismaki Port Nolloth Moqtada al-Sadr Calista Flockhart Industri Kapital Sosnovyi Bor bomber detonated Pan Am high school news conference negative publicity Forza Italia health care shallow waters Ross Perot of his
		0.00082489388296 1276 0.00006499827577 34 0.00004357583384 10 0.00003281003956 8 0.00002614549885 6 0.00002178791692 5 0.00001743033317 4 0.00001641694143 9 0.00001394426636 4 0.00001226203676 11 0.00001031532793 19 0.00000871516659 2 0.00000871516659 2 0.00000733908746 4 0.00000633830314 4 0.00000435758329 2 0.00000332398781 44		in the Addis Ababa Bill Clinton Charlton Heston bronze bust Buenos Aires Salvatore Gravano auction houses non-manufacturing index Central Bank last week Zeev Bielsky first-time offenders Tikrit my Mahmoud Ahmadi-Nejad Jake Borski to his
		0.00063047156436 184 0.00006420765567 19 0.00004327531133 12 0.00003208765702 9 0.00002614549885 6 0.00002135215800 7 0.00001743033317 4 0.00001640501978 8 0.00001394426636 4 0.00001212544885 8 0.00001028176757 52 0.00000871516659 2 0.00000871516659 2 0.00000733908746 4 0.00000633830314 4 0.00000435758329 2 0.00000316915157 2		United States Salt Lake Satellite Radio Stock Exchange Brandenburg Gate Panchen Lama Roger Federer Tata Steel Mohamed Fulayfel Filipino hostage he was Yevgenia Timoshenko Duane Hanson stores fund Falkland islanders conjugated estrogen replacement therapy
		0.00049295328790 136 0.00006338302774 20 0.00004221582276 39 0.00003198226113 20 0.00002614549885 6 0.00002091639908 6 0.00001743033317 4 0.00001640501978 8 0.00001394426636 4 0.00001210439768 5 0.00001012083885 6 0.00000871516659 2 0.00000871516659 2 0.00000733908746 4 0.00000620589526 28 0.00000434792128 30 0.00000316915157 2		Prime Minister la Cruz United Nations Security Council Anna Politkovskaya Umberto Bossi Reinventing Comics Gerhard Schroeder Kailash Satyarthi Time Warner intelligence agencies Wu Yi diplomacy directives Saint Laurent they are as an precious cargo
		0.00024237485195 181 0.00006197451876 16 0.00004209590043 16 0.00003172712240 18 0.00002614549885 6 0.00002091639908 6 0.00001743033317 4 0.00001631775922 44 0.00001394426636 4 0.00001199506823 16 0.00000996019025 12 0.00000871516659 2 0.00000871516659 2 0.00000733908746 4 0.00000611031555 21 0.00000407876178 32 0.00000316915157 2		have been Fiona Wood Stephen Harper White Sox Alison Hargreaves Sonia Gandhi Quentin Tarantino known as infinite canvas New Zealand opposition parties Verdens Gang Cyprian Gatete poli outbreak should be for its Ian Woosnam
		0.00023694132688 198 0.00005871269968 16 0.00004151313624 62 0.00003137459862 12 0.00002590563236 18 0.00002091639908 6 0.00001743033317 4 0.00001619975774 31 0.00001394426636 4 0.00001190198327 105 0.00000996019025 4 0.00000871516659 2 0.00000871516659 2 0.00000733908746 4 0.00000606272442 4 0.00000407049356 48 0.00000316915157 2		has been Titanic sank would be Eiffel Tower so far Pedro Quintanar Plaid Cymru President Bush Genetic Modification and a Metin Kaplan Uttar Pradesh Contemnit procellas Eugene Shoemaker Nick Berg from a green card
		0.00022077299946 81 0.00005773863813 181 0.00004145746425 54 0.00003137335443 213 0.00002512018546 7 0.00002091639908 6 0.00001743033317 4 0.00001593630441 8 0.00001394426636 4 0.00001162022181 4 0.00000996019025 4 0.00000871516659 2 0.00000871516659 2 0.00000733908746 4 0.00000606272442 4 0.00000387340742 2 0.00000316915157 2		New York to be million people with the Christopher Reeve Alberto Tomba Padraig Pearse William Doyle Ciudad Madero Walter Cronkite Mel Sembler Sylvia Costas Clement VII eighteen books Clark Gable Robin Warren genetic illnesses
		0.00020527825109 86 0.00005693908679 14 0.00004092339077 18 0.00003107488010 216 0.00002490047518 10 0.00002082231549 29 0.00001743033317 4 0.00001591751243 22 0.00001394426636 4 0.00001162022181 4 0.00000996019025 4 0.00000871516659 2 0.00000871516659 2 0.00000733908746 4 0.00000603357694 6 0.00000387340742 2 0.00000316915157 2		took place Oberlin College El Salvador that the Genie Awards less than Nicole Kidman most important Buzz Aldrin Martian meteorite Mel Karmazin Silicon Graphics Chuck Yeager 23 rd natural gas Renzo Piano Christopher Yavelow
		0.00019847218937 47 0.00005693908679 14 0.00004067077680 14 0.00003098725938 8 0.00002425089770 8 0.00002075039629 10 0.00001743033317 4 0.00001588339182 27 0.00001394426636 4 0.00001162022181 4 0.00000996019025 4 0.00000871516659 2 0.00000871516659 2 0.00000713059080 3 0.00000581011091 2 0.00000387340742 2 0.00000306932088 53		Los Angeles Condoleezza Rice pleaded guilty True Path Benjamin Netanyahu rain forest Merrill Lynch do not Berry Gordy Marilyn Manson measuring 6.9 Shapour Bakhtiar Celso Amorim monetary union Virtual Reality Raisani tribe is in
		0.00018817998352 587 0.00005622687968 20 0.00004048335541 12 0.00003098725938 8 0.00002425089770 8 0.00002065817171 8 0.00001743033317 4 0.00001587777479 94 0.00001377558601 7 0.00001162022181 4 0.00000996019025 4 0.00000871516659 2 0.00000871516659 2 0.00000713059080 3 0.00000581011091 2 0.00000387340742 2 0.00000290505545 3		to the Harriet Lane Tony Blair Sierra Leone Andy Roddick joint venture Mein Kampf at a mental illness Larry Page Jurgen Schneider Salvo Lima Camille Pissarro Maurice Strong Robbie Williams Rafael Benitez binge drinking
		0.00018683138478 49 0.00005602607052 15 0.00003961439506 10 0.00003098725938 8 0.00002422075704 75 0.00002065817171 8 0.00001743033317 4 0.00001568729931 6 0.00001366538163 14 0.00001162022181 4 0.00000996019025 4 0.00000871516659 2 0.00000871516659 2 0.00000713059080 3 0.00000581011091 2 0.00000387340742 2 0.00000270470696 3		Saudi Arabia Helmut Kohl Nikos Kourkoulos Gertrude Jekyll said that Corfu Channel Max Purnell Le Boucher postmenopausal women Grand Prix browser bug Sally Struthers Bracamonte Battalion Linux LTS Rick Dinon patent abstract Fair Trade
		0.00016676276573 348 0.00005488655734 51 0.00003921824828 12 0.00003098725938 8 0.00002413430775 12 0.00002063430111 47 0.00001743033317 4 0.00001568729931 6 0.00001361744762 5 0.00001162022181 4 0.00000996019025 4 0.00000871516659 2 0.00000871516659 2 0.00000713059080 3 0.00000581011091 2 0.00000387340742 2 0.00000256328440 5		is a Arnold Schwarzenegger did not Elvis Presley El Nino at least Markus Müller Ice Hockey Dow Jones CBS newsman Ayatollah Ali Ronnie Gilbert Berliner Verlag Don Brash Madhu Mani Miss Universe presidential candidate
		0.00014907041623 99 0.00005460376269 44 0.00003921824828 9 0.00003069254308 9 0.00002413430775 6 0.00001980719753 5 0.00001743033317 4 0.00001568729931 6 0.00001318616614 94 0.00001162022181 4 0.00000990359877 5 0.00000871516659 2 0.00000871516659 2 0.00000697213318 8 0.00000581011091 2 0.00000387340742 2 0.00000253020971 3		more than European Union Valerie Plame Kofi Annan Tansu Ciller Satomi Mitarai Maggie Dempster fishing quotas was a Andrei Kozyrev particle physics Regina Schueller Ben Stiller best picture Judy Sgro Mauricio Pineda maternity leave
		0.00013466177916 52 0.00005455048813 26 0.00003914179979 16 0.00003021579323 83 0.00002413430775 6 0.00001980719753 5 0.00001743033317 4 0.00001556279676 5 0.00001307274943 3 0.00001162022181 4 0.00000988811917 28 0.00000871516659 2 0.00000871516659 2 0.00000697213318 4 0.00000581011091 2 0.00000387340742 2 0.00000245114052 3		Olympic Games Supreme Court per cent that it Sri Lanka RJR Nabisco Lin Piao Aptis Communications Rossville Blvd Andrei Kokoshin may be Olive Madison Beatriz Iero tape containing Jake Peavy Lorenzo brothers tax cuts
		0.00012264038378 443 0.00005424439951 19 0.00003789203038 10 0.00003005229883 10 0.00002413430775 6 0.00001980719753 5 0.00001743033317 4 0.00001549362969 4 0.00001307274943 3 0.00001162022181 4 0.00000988683041 78 0.00000871516659 2 0.00000871516659 2 0.00000697213318 4 0.00000581011091 2 0.00000387340742 2 0.00000230695582 3		is the Franz Liszt Philip Morris Berni Ahern petty thief Edvard Munch Keith Maupin Symbian OS Roh Moo-hyun Achille Occhetto on a Nicol Williamson Baz Luhrman holiday weekend Harnold Lamb Liverpool boss Apple Computer
		0.00010284388554 112 0.00005339418567 22 0.00003766196824 11 0.00002976491305 25 0.00002413430775 6 0.00001980719753 5 0.00001743033317 4 0.00001549362969 4 0.00001307274943 3 0.00001146732484 5 0.00000980456207 6 0.00000871516659 2 0.00000871516659 2 0.00000697213318 2 0.00000581011091 2 0.00000387340742 2		will be Northern Ireland Harry Potter World Cup morning-after pill ARENA assassins Katamari Damacy Steve Price Palos Verdes Rafik Hariri Social Democrats Natwar Singh Barrow Hanley Stefano Falconi Gianni Versace Kristina Miller
		0.00009866995242 44 0.00005338039409 14 0.00003715413186 18 0.00002941368803 9 0.00002413430775 6 0.00001960912414 6 0.00001743033317 4 0.00001549362969 4 0.00001307274943 3 0.00001146732484 5 0.00000980456207 3 0.00000871516659 2 0.00000871516659 2 0.00000697213318 2 0.00000581011091 2 0.00000387340742 2		White House Solar Temple San Francisco Ahmed Qurei Francis Ricciardone shuttle Atlantis Josko Damic Sergey Brin Notre Dame Giulio Andreotti vacuum tubes Muktar Said-Ibrahim Ayrton Senna spaceship launches Ghazi al-Yawar Douglas Hurd
		0.00009571911505 36 0.00005299763507 15 0.00003691129314 12 0.00002935634984 8 0.00002388380744 53 0.00001960912414 6 0.00001743033317 4 0.00001549362969 4 0.00001307274943 3 0.00001146732484 5 0.00000980456207 3 0.00000871516659 2 0.00000871516659 2 0.00000697213318 2 0.00000581011091 2 0.00000387340742 2		prime minister Dick Cheney Nancy Pelosi Gravetye Manor such as Pamplona fiesta Joachim Johansson Sergei Sidorsky MG Rover Dave McCool Soledad Prison Morihiro Hosokawa Angela Merkel haemorrhagic fever fastest swimmer Deutsche Telekom
		0.00009373646026 22 0.00005287018212 281 0.00003599015326 210 0.00002935634984 8 0.00002372868948 18 0.00001960912414 6 0.00001743033317 4 0.00001549362969 4 0.00001307274943 3 0.00001139884171 29 0.00000980456207 3 0.00000871516659 2 0.00000871516659 2 0.00000697213318 2 0.00000581011091 2 0.00000387340742 2		Victor Emmanuel by the of a fiber optic Gulf War Jessica Litman Ivan Getting Jeff Hunt Lleyton Hewitt when he Piazza dei Minnie Driver Andriy Shevchenko Gerald Schatten Doug Arthur crushing debt
		0.00009263328684 376 0.00005229099770 12 0.00003529642345 9 0.00002905055590 10 0.00002348508133 16 0.00001960912414 6 0.00001743033317 4 0.00001549362969 4 0.00001307274943 3 0.00001138781772 14 0.00000980456207 3 0.00000871516659 2 0.00000871516659 2 0.00000697213318 2 0.00000581011091 2 0.00000387340742 2		for the Vasquez Rocks Tommy Thompson scrap metal Winter Olympics Derek Plumbly Irma Goldberg Ibrahim Sofu Hong Kong no longer Federico Fellini Minerva Rigging alter ego genetically modified Bolan Pass bright ideas
		0.00009158848115 34 0.00005161341323 47 0.00003486066635 10 0.00002905055590 10 0.00002343411506 33 0.00001960912414 6 0.00001743033317 4 0.00001549362969 4 0.00001307274943 3 0.00001138594325 9 0.00000980456207 3 0.00000871516659 2 0.00000871516659 2 0.00000697213318 2 0.00000581011091 2 0.00000387121281 28	Salvation Army years ago Silvio Berlusconi Mahmoud Ahmadinejad next year Audrey Seiler Haggits Pillar Cate Blanchett Hector Oqueli unemployment rate en route milepost markers African-American WWE Deng Xiaoping Balinese massage works for
		0.00008472465561 96 0.00005052270353 20 0.00003486066635 10 0.00002846112329 26 0.00002330500138 19 0.00001923347190 8 0.00001743033317 4 0.00001534627154 9 0.00001307274943 3 0.00001138307471 8 0.00000968011955 118 0.00000871516659 2 0.00000869458745 65 0.00000697213318 2 0.00000581011091 2 0.00000385592011 14		were killed Saddam Hussein Jack Ruby South Korea North Korea Vladimir Meciar Goetz Friedrich Green Zone Gustavo Guzman De Klerk as the Midge Ure a new Aurora Borealis Alabama Birmingham when they
		0.00008178089047 349 0.00005037366282 17 0.00003486066635 8 0.00002788853271 8 0.00002324474917 120 0.00001923347190 8 0.00001743033317 4 0.00001531962880 15 0.00001307274943 3 0.00001120521392 3 0.00000953957442 9 0.00000871516659 2 0.00000820250989 4 0.00000697213318 2 0.00000569390886 7 0.00000374342721 8		on the XXIII Olympiade Neil Armstrong Revenue Cutter by a Big Bang floating gardens presidential election Enola Gay Viktor Yanukovych Nobel Prize Michel Camdessus Kofi Anan 800 Chechens both sides officials say
		0.00008129819616 25 0.00004887268369 69 0.00003486066635 8 0.00002788853271 8 0.00002321900502 38 0.00001856709423 7 0.00001743033317 4 0.00001508394234 30 0.00001307274943 3 0.00001120521392 3 0.00000929617727 4 0.00000871516659 2 0.00000820250989 4 0.00000697213318 2 0.00000566687550 53 0.00000363440995 14		Film Festival had been Susan Linn Heydar Aliyev this year lunar landing Clermont Ferrand last year asylum seekers Las Vegas Lawrence Welk Melvyn Percy Financial Times 357 yards and other but also

Multiword Units in Portuguese Table

  B.2: MWU extracted from the first five RTE dataset test, translated into Portuguese.

				B.2 Multiword Units in Portuguese B.2 Multiword Units in Portuguese B.2 Multiword Units in Portuguese B.2 Multiword Units in Portuguese B.2 Multiword Units in Portuguese B.2 Multiword Units in Portuguese B.2 Multiword Units in Portuguese B.2 Multiword Units in Portuguese B.2 Multiword Units in Portuguese B.2 Multiword Units in Portuguese
	A	D	Table B.2: (continued) Table B.2: (continued) Table B.2: (continued) Table B.2: (continued) Table B.2: (continued) Table B.2: (continued) Table B.2: (continued) Table B.2: (continued) Table B.2: (continued) Table B.2: (continued) Table B.2: (continued) Table B.2: (continued) Table B.2: (continued) Table B.2: (continued) Table B.2: (continued) Table B.2: (continued) Table B.2: (continued) Table B.2: (continued) Table B.2: (continued) Table B.2: (continued)
		Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency Mutual Expectation Frequency	MWU MWU MWU MWU MWU MWU MWU MWU MWU MWU MWU	MWU MWU MWU MWU MWU MWU MWU MWU MWU MWU MWU MWU
	Mutual Expectation Frequency 0.00080304709263 242 0.00039809668669 117 0.00005234670243 15 0.00005139494533 18 0.00005065809819 15 0.00003072708932 19 0.00002871590550 12 0.00002840976049 17 0.00002135272189 19 0.00002127104199 8 0.00002115018287 20 0.00001794744094 6 0.00001794744094 6 0.00001794744094 6 0.00001487960617 56 0.00001486949805 7 0.00001486949805 7 0.00001395912113 4 0.00001395912113 4 0.00001395912113 4 0.00001240810707 4 0.00001240810707 4 0.00001240810707 4 0.00001116729618 4 0.00001116729618 4 0.00001116729618 4 0.00001026405971 5 0.00001026405971 5 0.00001015208818 4 0.00000930608076 4 0.00000930608076 4 0.00000930608076 6 0.00000865705169 17 0.00000863379591 50 0.00000859022839 4 0.00000728867826 56 0.00000727656288 7 0.00000727037559 5 0.00000697956057 2 0.00000697956057 2 0.00000697956057 2 0.00000697956057 2 0.00000697956057 2 0.00000697956057 2 0.00000697956057 2 0.00000697956057 3 0.00000695081781 92 0.00000624098266 13 0.00000623175038 5 0.00000623175038 5 0.00000558364809 2 0.00000558364809 2 0.00000558364809 2 0.00000525519818 8 0.00000525437417 60 0.00000523467043 3 0.00000465304038 2 0.00000465304038 2 0.00000465304038 2 0.00000398832026 2 0.00000398832026 2 0.00000398832026 2 0.00000356021337 49 0.00000349998845 60 0.00000348978028 2 0.00000310202677 2 0.00000310202677 2 0.00000310202677 2 0.00000277921527 46 0.00000274435342 57 0.00000271226440 15 W F 0.00035627873149 129 0.00004985400301 20 0.00002791824227 8 0.00002093868170 9 0.00001794744094 6 0.00001486949805 7 0.00001395912113 4 0.00001240810707 4 0.00001116729618 4 0.00001015208818 4 0.00000930608076 4 0.00000859022839 4 0.00000727037559 10 0.00000697956057 3 0.00000697956057 2 0.00000685642453 35 0.00000622234393 63 0.00000558364809 4 0.00000523467043 3 0.00000465304038 2 0.00000398832026 2 0.00000348978028 2 0.00000310202677 2 0.00000267935729 9 0.00025095048477 80 0.00004758791329 15 0.00002776360088 151 0.00002093868170 6 0.00001794744094 6 0.00001486949805 7 0.00001395912113 4 0.00001240810707 4 0.00001116729618 4 0.00001015208818 4 0.00000930608076 4 0.00000858608018 110 0.00000720470734 8 0.00000697956057 2 0.00000697956057 2 0.00000679092363 6 0.00000620405353 4 0.00000558364809 2 0.00000523467043 3 0.00000465304038 2 0.00000398832026 2 0.00000348978028 2 0.00000310202677 2 0.00000256695080 11 Pair T-H extracted from RTE-3 test set. S 0.00020497686637 514 0.00004743390673 70 0.00002684446372 10 0.00002093868170 6 0.00001794744094 6 0.00001482870539 36 0.00001395912113 4 0.00001240810707 4 0.00001116729618 4 0.00001015208818 4 0.00000930608076 4 0.00000858009844 77 0.00000715121223 71 0.00000697956057 2 0.00000697956057 2 0.00000677899834 13 0.00000620405353 4 0.00000558364809 2 0.00000523467043 3 0.00000465304038 2 0.00000398832026 2 0.00000348978028 2 0.00000310202677 2 0.00000253802204 2 0.00019914630684 59 0.00004717220145 14 0.00002661696817 15 0.00002093868170 6 0.00001786767461 8 0.00001478024569 6 0.00001395912113 4 0.00001240810707 4 0.00001116729618 4 0.00001015208818 4 0.00000930608076 4 0.00000847518004 17 0.00000712496785 7 0.00000697956057 2 0.00000697956057 2 0.00000672638134 78 0.00000620405353 4 0.00000558364809 4 0.00000523155995 29 0.00000465304038 2 0.00000398832026 2 0.00000348978028 2 0.00000310202677 2 0.00000253802204 2 <pair id="217" entailment="YES" task="IR" length="short"> Estados Unidos MWU Hong Kong Condoleezza Rice Las Vegas nave espacial White Sox Vladimir Putin Hillary Clinton Vicente Fox Bill Clinton Li Zhaoxing Valentino Rossi Cyril Ferez as pessoas Silvio Berlusconi Time Warner Kadhem Al-Rawi All-Stars Starters Alix McAlister Got Talent Ban Ki-moon Gravetye Manor Jenson Button Bowery Poetry Lulu Xingwana Jacques Delors ursos polares Sergey Brin Jason MacIntyre Toro Rosso Virginia Tech já havia entre os Pete Wilson com as Greater Manchester Margaret Thatcher Zeev Bielsky Abdelaziz Bouteflika Lindsay Ellis Midge Ure Aurore Paquiss Budleigh Salterton Kamal Dahal Lago Kivu e um mil dólares Boston Globe General Motors formato Blu-ray Sony BMG Rafael Benitez bomba explodiu dizem que Sonia Gandhi Mani Tripathi Madhu Mani Olive Madison Todd Chaves Intel Pentium delegação marroquina para se e uma meteorito marciano Wildlife Conservation Hun Sen ciclistas tirou que foram e da C informações sobre Reino Unido realidade virtual Thaksin Shinawatra Mahmoud Ahmadinejad Javier Solana Singapore Airlines Lhadon Tethong Gertrude Jekyll Andrei Kozyrev Land Rover Arthur Virgílio Serra Leoa New Hampshire Samir Geagea lona infinito disse à do presidente Steve Price Grand Prix Front Row Perez Quiron Walter Cronkite Jennifer Watts cinco vezes US $ Negócios Estrangeiros sobre o Celso Amorim Michel Fourniret Chen Shui-bian Mount Prospect Yves Engler caçadores furtivos Rodrigo Avila Sondhi Limthongkul em que crescimento econômico tutela síria Reinventando Comics reformas econômicas Tommy Thompson Sally Struthers Casey Stoner Ben Kinsella Madeleine Albright Korkmaz Yigit Danny Boyle muito tempo Jogos Olímpicos tem sido Arnold Schwarzenegger Ramos Horta Benazir Bhutto deve ser Andre Agassi Sunshine Coast Idi Amin Giampaolo Giuliani Jurgen Schneider para as que ela Sendero Luminoso Markus Mller ataque terrorista Hassan Turabi Kimi Raikkonen sales plan Will Carling Marilyn Monroe London Underground Hudson Valley Post Office para o Second Life El Salvador Datuk Seri telefones móveis Harriet Lane Mo Siegel barbárie medieval Hilda Solis Patrick Doohan Joachim Johansson duas vezes relações sexuais Jubiz Hazvumb Technischen Hochschule para uma Akhmad Kadyrov Evo Morales não vai Zhirun Yuan Alexander Downer Nicole Kidman ambientalmente saudáveis Van Meeteren Los Angeles 0.00019199564122 519 0.00004594009079 21 Nelson Mandela 0.00002644886081 12 carne bovina 0.00002093868170 6 Umberto Bossi 0.00001766596870 46 está sendo 0.00001462297041 49 as autoridades 0.00001395912113 4 serial killer 0.00001240810707 4 Jacqui Smith 0.00001116729618 4 Jade Goody 0.00001015208818 4 All-Star Game 0.00000930608076 4 Modelo Padrão 0.00000845510476 19 logo após 0.00000699360908 74 após o 0.00000697956057 2 Beatriz Iero 0.00000697956057 2 Irma Goldberg 0.00000670585223 7 Bob Denver 0.00000620405353 4 Vladislav Doronin 0.00000558364809 2 Shin Tae-seop 0.00000517084209 41 sobre os 0.00000465304038 2 Sherman Hartley 0.00000398832026 2 Raul Reyes 0.00000348978028 2 concedido anualmente 0.00000310202677 2 Small Heath 0.00000253802204 2 Ingrid Bergman <t>Pierre Beregovoy, apparently left no message when he shot himself with a borrowed gun.</t> para a 0.00018472748343 203 0.00004558844012 205 que os 0.00002561673682 64 mais tarde 0.00002081797174 128 por um 0.00001744890142 5 Sharm el-Sheikh 0.00001456603877 12 República Checa 0.00001395912113 4 Raman Raghav 0.00001240810707 4 Great Yarmouth 0.00001116729618 4 Jalal Talabani 0.00001015208818 4 Preston Burch 0.00000930608076 4 Irene Khan 0.00000837547213 6 Steve Jobs 0.00000697956057 2 Zack Urlocker 0.00000697956057 2 Industri Kapital 0.00000697956057 2 Agua Dulce 0.00000665111065 9 pediu desculpas 0.00000620405353 4 Trenton Duckett 0.00000558364809 2 toques polifônicos 0.00000513202986 5 parque temático 0.00000465304038 2 pole position 0.00000398832026 2 Barry Rogerson 0.00000348978028 2 jatos corporativos 0.00000310202677 2 bacia amazônica 0.00000253802204 2 acessórios digitais <h>Pierre Beregovoy commits suicide.</h> dos EUA 0.00015711436572 46 0.00004536714187 13 Sri Lanka 0.00002536657485 26 New York 0.00002069378388 13 São Paulo 0.00001744890142 5 Andry Rajoelina 0.00001454075118 5 fast food 0.00001395912113 6 Vladislav Listyev 0.00001226900258 28 têm sido 0.00001108518427 9 produtos químicos 0.00001015208818 4 Lord Carnarvon 0.00000930608076 4 Marion Bartoli 0.00000810529582 6 ensino médio 0.00000697956057 2 Viroj Laohaphan 0.00000697956057 2 Barrow Hanley 0.00000697956057 2 Ulan Bator 0.00000665032803 90 a uma 0.00000620405353 4 Carroll Campbell 0.00000558364809 2 Alexandra Holzer 0.00000507604409 4 gripe aviária 0.00000465304038 2 Kirk Kerkorian 0.00000398832026 2 considerada insegura 0.00000348978028 2 Gerald Schatten 0.00000310202677 2 Universal Pictures 0.00000253802204 2 Jorge Lorenzo </pair> Nações Unidas 0.00015202724899 358 0.00004419572724 170 é uma 0.00002481621414 8 Angelina Jolie 0.00002033699457 13 ficaram feridas 0.00001744890142 5 Dobie Gillis 0.00001440941469 16 sistema operacional 0.00001395912113 4 Skip Spence 0.00001215488101 16 of the 0.00001103220802 7 mudanças climáticas 0.00001015208818 4 Roger Federer 0.00000930608076 4 Lycos Europe 0.00000804311276 11 ataques terroristas 0.00000697956057 3 Iyad Allawi 0.00000697956057 2 Yevgenia Timoshenko 0.00000697956057 2 Willy Claes 0.00000662735420 122 de seu 0.00000620405353 4 Zinedine Zidane 0.00000558364809 2 baby boom 0.00000507604409 4 Ian Fleming 0.00000465304038 2 Silicon Graphics 0.00000398832026 2 Lester Piggott 0.00000348978028 2 profeta Maomé 0.00000310202677 2 transtorno bipolar 0.00000253802204 2 Amanda Knox é um 0.00014415156329 72 0.00004364085908 186 para os 0.00002481621414 8 Creative Commons 0.00002032407974 114 do governo 0.00001744890142 5 Helmut Kohl 0.00001424993570 7 insuficiência cardíaca 0.00001395912113 6 Jack Ma 0.00001214496478 71 não é 0.00001092452931 6 Super Bowl 0.00001015208818 4 Doris Lessing 0.00000930608076 4 tigres siberianos 0.00000797664052 4 Gerhard Schroeder 0.00000697956057 6 trabalhadores humanitários 0.00000697956057 2 Helicobacter pylori 0.00000697956057 2 ex-repúblicas soviéticas 0.00000661221520 6 lucro líquido 0.00000620405353 4 Augusto Pinochet 0.00000558364809 2 Adil Kalbani 0.00000507604409 4 lhe dissera 0.00000465304038 2 Nicol Williamson 0.00000398832026 2 Natasha Richardson 0.00000348978028 2 Old Mutual 0.00000310202677 2 wood chips 0.00000253802204 2 Shenzhou V D.1 All Words Nova York 0.00013839868188 443 0.00004222634016 22 Manchester United 0.00002442846198 7 Alfredo Cristiani 0.00002030417636 8 Opera House 0.00001744890142 5 Beni Suef 0.00001413360951 9 Al Qaeda 0.00001395912113 4 Paula Radcliffe 0.00001196496032 6 Alberto Gonzales 0.00001090556270 5 Dave McCool 0.00001015208818 4 Criss Angel 0.00000930608076 4 assessoria jurídica 0.00000797664052 8 Banco Central 0.00000697956057 2 decepcionante 112.000 0.00000697956057 2 Karl Rove 0.00000697956057 2 Plaid Cymru 0.00000661221520 6 Bob Rae 0.00000612372696 48 uma nova 0.00000558364809 2 Tsuyoshi Kusanagi 0.00000507604409 4 Naomi Campbell 0.00000465304038 2 Salvo Lima 0.00000398832026 2 Rita Levi-Montalcini 0.00000348978028 2 Ronnie Gilbert 0.00000303872025 8 Partido Socialista 0.00000253802204 2 Christiaan Huygens que o 0.00013588291768 328 0.00004084039756 32 muitas vezes 0.00002442846198 7 Yigal Amir 0.00002019087151 9 Nicolas Sarkozy 0.00001709992284 7 Porto Nolloth 0.00001397829510 27 este ano 0.00001395912113 4 Christopher Hitchens 0.00001196496032 6 Alberto Tomba 0.00001076430453 93 que se 0.00001015208818 4 Charing Cross 0.00000930608076 4 Salvatore Lo 0.00000797664052 4 Mel Sembler 0.00000697956057 2 Alaattin Çakici 0.00000697956057 2 Muktar Disse-Ibrahim 0.00000697956057 2 RJR Nabisco 0.00000661221520 6 números primos 0.00000603637636 8 alto perfil 0.00000558364809 2 ski run 0.00000507604409 4 General Store 0.00000465304038 2 Ben Stiller 0.00000398832026 2 years ago 0.00000348978028 2 Fernando Alonso 0.00000297574161 24 como eles 0.00000247824960 28 no dia disse que 0.00012119788880 353 com o 0.00011721674673 388 em um 0.00011596808326 36 Casa Branca 0.00011264761997 342 é o 0.00011245389760 48 Barack Obama 0.00009970800602 30 Arábia Saudita 0.00008909270400 319 com a 0.00008661813627 308 em uma 0.00008506343147 361 que a 0.00008297820750 253 que ele 0.00007896460011 460 de um 0.00007609972090 26 Relações Exteriores 0.00006711115566 25 companhia aérea 0.00006578615285 130 por cento 0.00006496359856 22 Brian Mulroney 0.00006482122262 41 0.00005798404163 36 0.00005569440691 56 0.00005565052561 67 0.00005507421156 68 0.00005319786942 25 San Francisco 0.00003072708932 19 Supremo Tribunal 0.00002166327795 158 é a 0.00001799991878 7 tosse convulsa 0.00001488972885 8 Direitos Humanos 0.00001395912113 4 Dietrich Mateschitz 0.00001240810707 4 Moqtada al-Sadr 0.00001116729618 4 Estelle Getty 0.00001026405971 5 Jack Ruby 0.00000930608076 4 Joba Chamberlain 0.00000872445071 5 Star Trek 0.00000739012285 6 iPod nano 0.00000697956057 2 Henrik Larsson 0.00000697956057 2 Andriy Shevchenko 0.00000697956057 2 Mufi Hannemann 0.00000628160433 3 Sergey Orlovskiy 0.00000558364809 2 Keith Maupin 0.00000531776050 4 Barnaby Joyce 0.00000465304038 2 Klaus Wowereit 0.00000405788387 5 pedir desculpas 0.00000356256919 66 que um 0.00000312858106 24 não tem 0.00000279182404 2 Cristiano Ronaldo pelo menos 0.00003136881060 20 seres humanos 0.00002174401561 18 New Line 0.00001799991878 7 Wen Jiabao 0.00001494508069 48 todas as 0.00001395912113 4 Yusuf Kalla 0.00001240810707 4 Elvis Presley 0.00001116729618 4 coleiras elétricas 0.00001033158605 15 Partido Trabalhista 0.00000930608076 6 Oceano Antártico 0.00000872445071 5 Boeing 737 0.00000739012285 6 Kim Beazley 0.00000697956057 2 Regina Schueller 0.00000697956057 2 Kiryat Arba 0.00000697956057 2 Claudio Ranieri 0.00000628160433 3 Baker Children 0.00000558364809 2 Charlton Heston 0.00000531776050 4 Marina Souza 0.00000474021226 72 para um 0.00000409809036 8 pelas forças 0.00000358948819 6 F-16 0.00000314080216 3 companhias aéreas 0.00000279182404 2 substâncias dopantes ter sido 0.00003140802073 9 Bento XVI 0.00002184415098 137 o seu 0.00001799991878 7 Dick Cheney 0.00001512133895 110 o governo 0.00001395912113 4 Guiding Light 0.00001246350075 5 Giles Chichester 0.00001116729618 4 Nicole Wong 0.00001042625718 11 James Bond 0.00000930608076 4 Joseph Dault 0.00000876919148 14 Partido Liberal 0.00000744486442 4 dessas economias 0.00000697956057 2 Les Combes 0.00000697956057 2 alter ego 0.00000697956057 2 credor hipotecário 0.00000628160433 3 Uri Geller 0.00000558364809 2 Vue Cinemas 0.00000531776050 4 Murray Hill 0.00000478387165 29 muito mais 0.00000423902111 23 três anos 0.00000379323933 5 Apple Computer 0.00000316562068 50 e não 0.00000279182404 2 Rebecca MacKinnon 0.00000156255408 37 começou a ano passado 0.00003140802073 12 Torre Eiffel 0.00002192352622 32 nos últimos 0.00001813572089 151 do que 0.00001551013338 10 Walt Disney 0.00001395912113 4 Larisa Trembovler 0.00001246350075 5 Princípios Valdez 0.00001116729618 4 Julia Redd 0.00001046934085 3 Terry McAuliffe 0.00000930608076 4 Elmwood Avenue 0.00000897372047 6 Boston Celtics 0.00000746569185 73 que eles 0.00000697956057 2 Jake Peavy 0.00000697956057 2 Baz Luhrman 0.00000697956057 2 Purnomo Yusgiantoro 0.00000628160433 3 shopping center 0.00000558364809 2 Buzz Aldrin 0.00000531776050 8 Eu estou 0.00000481478401 61 que está 0.00000425871485 6 Igreja Batista 0.00000379628523 51 disseram que 0.00000319065612 4 Al Jazeera 0.00000279182404 2 Suresh Joachim 0.00000170059809 69 e de direitos humanos 0.00003204899986 60 pode ser 0.00002222438889 11 Rainha Elizabeth 0.00001823691491 9 Zona Verde 0.00001554538358 7 Fiona Wood 0.00001395912113 4 Ailin Graef 0.00001246350075 5 Quinta Emenda 0.00001116729618 4 Michelle Steele 0.00001046934085 3 Aer Lingus 0.00000930608076 4 Estrela Alimentos 0.00000897372047 3 NetIP members 0.00000759996556 14 nesta quarta-feira 0.00000697956057 3 Gilda Flores 0.00000697956057 2 Puerto Cabezas 0.00000697956057 2 Prim Palver 0.00000628160433 3 Emile Lahoud 0.00000568026735 54 como uma 0.00000545160265 17 havia sido 0.00000483200347 3 Católica Romana 0.00000432760453 25 seu primeiro 0.00000392049151 34 os seus 0.00000323844597 43 um novo 0.00000279182404 2 Alfred Hitchcock 0.00000172361092 27 tem uma União Europeia 0.00004009382610 316 de uma 0.00003955084321 17 Gordon Brown 0.00003865602775 12 Romano Prodi 0.00003838758130 11 Buenos Aires 0.00003758734601 63 foram mortos 0.00003738382657 100 todos os 0.00003665222539 31 Nova Zelândia 0.00003489780283 15 Oriente Médio 0.00003489780283 10 Meio Ambiente 0.00003489780283 10 Falun Gong 0.00003489780283 10 Aki Kaurismaki 0.00003465712871 12 Sam Brownback 0.00003380602720 51 tinha sido 0.00003371259299 16 Saddam Hussein 0.00003297430158 180 a sua 0.00003248668145 16 Yasser Arafat 0.00002405763189 130 como um 0.00002389926340 140 que as 0.00002380397382 18 ficaram feridos 0.00002359091377 13 Prêmio Nobel 0.00002355601646 9 Força Aérea 0.00002351009789 8 empréstimos ruins 0.00002351009789 8 Andy Roddick 0.00002337341175 12 Harry Potter 0.00002268357093 13 Tony Blair 0.00002251471051 10 Movimento Esquerda-Verde 0.00002251471051 10 Ron Gray 0.00002244378629 39 estão sendo 0.00002233459236 8 Carla Bruni 0.00002233459236 12 Suprema Corte 0.00002229975871 126 um dos 0.00002222438889 11 homicídio culposo 0.00002011755714 7 Scotland Yard 0.00001988475742 43 -year-old 0.00001949463331 9 gripe suína 0.00001942138624 8 Nancy Pelosi 0.00001938766763 10 Red Bull 0.00001932801388 6 Wye Plantation 0.00001932801388 6 Angela Merkel 0.00001932801388 6 Johanna Sigurdardottir 0.00001932801388 6 Garcia Marquez 0.00001932801388 6 Victor Emmanuel 0.00001913980850 111 com uma 0.00001899991366 7 Anna Politkovskaya 0.00001890897693 38 à noite 0.00001886367681 10 la Cruz 0.00001876820716 21 ataque cardíaco 0.00001861216151 8 Motor Company 0.00001709992284 7 Oberlin College 0.00001709992284 7 Yitzhak Rabin 0.00001700284702 119 com um 0.00001675094427 6 Cessna 172 0.00001675094427 6 Jefferson Airplane 0.00001628564132 14 candidato presidencial 0.00001628564132 7 Manmohan Singh 0.00001615269684 9 Real Madrid 0.00001586263716 10 ferimentos graves 0.00001586263716 5 Temperos Celestial 0.00001586263716 5 Nikos Kourkoulos 0.00001586263716 10 Air Canada 0.00001570401037 6 Britney Spears 0.00001570401037 6 Awatef Aboudihaj 0.00001565375896 121 sobre a 0.00001556631832 91 com os 0.00001395912113 4 XXIII Olympiade 0.00001395912113 4 Adis Abeba 0.00001395912113 4 Chadrick Fulks 0.00001395912113 4 joint venture 0.00001395912113 4 Valerie Plame 0.00001395912113 4 Katamari Damacy 0.00001395912113 4 Edouard Balladur 0.00001395912113 4 Dalai Lama 0.00001395912113 4 Yad Vashem 0.00001395912113 4 Nadia Comaneci 0.00001395912113 4 Ocean Drive 0.00001395912113 4 Luciano Bello 0.00001395912113 4 Pita Sharples 0.00001395912113 4 Desejo Tagro 0.00001395912113 4 Vlaams Belang 0.00001395912113 4 Hideki Moronuki 0.00001353611697 8 Leona Lewis 0.00001342223186 5 Ahmed Qorei 0.00001342223186 5 Thabo Mbeki 0.00001342223186 5 Qin Shi 0.00001338622224 89 era um 0.00001325986977 32 pode ter 0.00001322443040 6 Melinda Duckett 0.00001322443040 6 Satellite Radio 0.00001316898215 10 Stephen Harper 0.00001307154616 18 partido político 0.00001292511206 10 aquecimento global 0.00001276262446 8 British Airways 0.00001256320866 6 batatas fritas 0.00001256320866 6 Ramzan Kadyrov 0.00001246350075 5 Berni Ahern 0.00001246350075 5 Benjamin Netanyahu 0.00001196496032 6 Big Brother 0.00001179730043 104 e os 0.00001179305036 14 eleição presidencial 0.00001163260094 5 Associated Press 0.00001163260094 5 Marc Ravalomanana 0.00001159680778 18 duas semanas 0.00001152403456 99 em seu 0.00001142109886 6 Wikimedia Foundation 0.00001126035750 11 América Latina 0.00001116729618 4 Heydar Aliyev 0.00001116729618 4 Radovan Karadzic 0.00001116729618 4 Derek Plumbly 0.00001116729618 4 Aptis Comunicações 0.00001116729618 4 Vaclav Havel 0.00001116729618 4 Maurizio Bevilacqua 0.00001116729618 4 Estrelas Foods 0.00001056365909 28 pessoas morreram 0.00001046934085 3 Calista Flockhart 0.00001046934085 3 Francis Ricciardone 0.00001046934085 3 Hector Oquelí 0.00001046934085 3 Tel Aviv 0.00001046934085 6 Ted Stevens 0.00001046934085 3 Huiyuan Juice 0.00001046934085 3 Société Générale 0.00001046934085 3 Países Baixos 0.00001046934085 3 Piazza dei 0.00001046934085 3 Lleyton Hewitt 0.00001046934085 3 Niel Tupas 0.00001046934085 3 Burkina Faso 0.00001046934085 3 Vantagem Legal 0.00001046934085 3 Learning Summit 0.00001046934085 3 WealthBridge Connect 0.00001005056674 6 Alan Johnston 0.00000980500135 35 seu filho 0.00000974440991 17 seis meses 0.00000969383382 5 Pierre Beregovoy 0.00000969383382 5 Leona Helmsley 0.00000966400694 6 Neil Armstrong 0.00000966400694 6 telefones celulares 0.00000966400694 6 Ilhas Salomão 0.00000963393177 93 como o 0.00000933131378 86 contra o 0.00000930608076 4 JK Rowling 0.00000930608076 4 Colin Powell 0.00000930608076 4 Circuit Court 0.00000930608076 6 horário nobre 0.00000930608076 4 Kofi Annan 0.00000930608076 4 Russell Dunham 0.00000930608076 4 Lo Piccolo 0.00000930608076 4 Alexandre Borovik 0.00000924320193 7 moeda estrangeira 0.00000918363185 5 Lana Clarkson 0.00000918363185 5 Brigham Young 0.00000913687927 12 homens armados 0.00000913365056 91 contra a 0.00000909091796 85 que não 0.00000897372047 3 Audrey Seiler 0.00000897372047 3 Tansu Ciller 0.00000897372047 3 Wolfgang von 0.00000897372047 3 Georgi Markov 0.00000897372047 3 Maurice Strong 0.00000897372047 3 Viktor Yanukovych 0.00000897372047 3 Cate Blanchett 0.00000897372047 3 castelo Crathes 0.00000797664052 4 Ronald Reagan 0.00000797664052 4 Conservação Ambiental 0.00000797664052 4 Ed Stelmach 0.00000797664052 4 Gerald Posner 0.00000797664052 4 Robbie Fowler 0.00000797664052 4 Galvarino Apablaza 0.00000797664052 4 Claire Danes 0.00000793131858 5 instituições financeiras 0.00000793131858 5 Melhor Ator 0.00000789344722 74 diz que 0.00000785200518 3 Sun Microsystems 0.00000785200518 3 Sudeste Asiático 0.00000785200518 3 Pan Am 0.00000785200518 3 Gavin Newsom 0.00000785200518 3 Pai Btiz 0.00000784380154 133 de sua 0.00000697956057 4 Football Club 0.00000697956057 2 Josko Damic 0.00000697956057 2 Quentin Tarantino 0.00000697956057 2 Mein Kampf 0.00000697956057 2 Padraig Pearse 0.00000697956057 2 dolce vita 0.00000697956057 2 Brigadas Vermelhas 0.00000697956057 2 Goetz Friedrich 0.00000697956057 2 Kurt Cobain 0.00000697956057 2 Clermont Ferrand 0.00000697956057 2 Yom Kippur 0.00000697956057 2 Rosinha Matheus 0.00000697956057 2 Borislav Shervinsky 0.00000697956057 2 Oppong Manneh 0.00000697956057 2 Malcolm Brabant 0.00000697956057 2 Camille Pissarro 0.00000697956057 4 Formula One 0.00000697956057 3 Highway Patrol 0.00000697956057 2 Beth Ditto 0.00000697956057 2 Sara Hiom 0.00000697956057 2 Billy Connolly 0.00000697956057 2 Deacon Brodie 0.00000697956057 2 Nikola Gruevski 0.00000697956057 2 Connie Beauchamp 0.00000697956057 2 Yacht Charters 0.00000697956057 2 Liam Neeson 0.00000697956057 2 Humphrey Bogart 0.00000697956057 2 Ratu Josefa 0.00000697956057 2 Slumdog Millionaire 0.00000697956057 2 Yisrael Beiteinu 0.00000697956057 4 Tesla Motors 0.00000697956057 3 Kenneth Branagh 0.00000697956057 2 Sento Shosho 0.00000697956057 2 Bulelani Ngcuka 0.00000697956057 2 Forces Nouvelles 0.00000697956057 2 simbolismo religioso 0.00000697956057 2 Pledge Room 0.00000697956057 2 climate change 0.00000697956057 2 entrepreneurial ecosystem 0.00000697956057 3 Wells Fargo 0.00000697956057 2 Attila Ekici 0.00000697956057 2 Leroy Chiao 0.00000697956057 2 Salizhan Sharipov 0.00000697956057 2 Point Comfort 0.00000697956057 2 Horatiu Nastase 0.00000697956057 2 Jeanna Giese 0.00000697956057 2 Nagashi Furukawa 0.00000697956057 2 Kaew Panjapetchkaew 0.00000657689361 7 floresta tropical 0.00000656899783 4 Mel Gibson 0.00000656899783 4 Raymond Leblanc 0.00000656899783 4 Senador Dunn 0.00000656899783 4 Lori Mitchell 0.00000656899783 4 Flat Top 0.00000656899783 4 Susan Linn 0.00000656899783 4 assistentes sociais 0.00000654542509 14 esta semana 0.00000646255603 5 Philip Morris 0.00000644267129 6 Hyde Park 0.00000642929081 62 por uma 0.00000638131223 24 poderia ser 0.00000635429933 68 depois que 0.00000631366584 16 suas ações 0.00000631277862 27 vai ser 0.00000603637636 8 meu marido 0.00000597591225 73 durante a 0.00000587752447 4 Emerald InTouch 0.00000587752447 8 David Cameron 0.00000587752447 4 Sir Clement 0.00000587752447 4 extremista islâmico 0.00000587752447 4 Morris Iemma 0.00000587752447 4 has been 0.00000587752447 4 envolvendo motociclistas 0.00000571054943 3 monarca jordaniano 0.00000571054943 3 Rolling Stone 0.00000571054943 3 Pedro Quintanar 0.00000571054943 3 party supply 0.00000571054943 3 Il Manifesto 0.00000571054943 3 Glenn Morrison 0.00000570852217 32 as suas 0.00000558364809 2 Kathleen Sebelius 0.00000558364809 2 união monetária 0.00000558364809 2 Jihad Islâmica 0.00000558364809 2 economistas previam 0.00000558364809 2 Maggie Dempster 0.00000558364809 2 Ibrahim Sofu 0.00000558364809 2 Montanhas Azuis 0.00000558364809 2 Symbian OS 0.00000558364809 2 HOT 97 0.00000558364809 2 towards children 0.00000558364809 2 Laurie Garner 0.00000558364809 2 Toni Hoffman 0.00000558364809 2 Isaac Asimov 0.00000558364809 4 Jeopardy ! 0.00000558364809 2 Bosco Ntaganda 0.00000555109546 72 a ser 0.00000495162294 33 não está 0.00000492674826 6 militares indonésios 0.00000486937506 63 e as 0.00000485534656 4 Fundo Global 0.00000485534656 4 motor esquerdo 0.00000485534656 4 Steven Spielberg 0.00000485534656 4 Thunder Bay 0.00000485534656 4 vulcão Ubinas 0.00000485534656 4 Wendy Portillo 0.00000485534656 4 Tata Steel 0.00000485534656 4 Jim Callahan 0.00000485534656 4 Mark Cuban 0.00000485104192 28 as mulheres 0.00000483200347 3 Alpes italianos 0.00000483200347 3 Timor Leste 0.00000483200347 3 criminalidade violenta 0.00000465304038 4 Mahmoud Abbas 0.00000465304038 2 Achille Occhetto 0.00000465304038 2 Ursa Maior 0.00000465304038 2 anglo-holandesa Corus 0.00000465304038 2 Sergei Sidorsky 0.00000465304038 2 Donald Tusk 0.00000465304038 2 Ursos pardos 0.00000465304038 2 toxic chemicals 0.00000465304038 2 Toby Harnden 0.00000465304038 2 Ezer Weizman 0.00000465304038 2 Toby Gascon 0.00000465304038 2 vaso sanitário 0.00000465304038 2 Pablo Neruda 0.00000465304038 2 Gossip Girl 0.00000459181592 5 gravemente ferido 0.00000456973794 16 eles estavam 0.00000398832026 2 esclerose múltipla 0.00000398832026 2 Virgin Atlantic 0.00000398832026 2 galáxia anã 0.00000398832026 2 Max Purnell 0.00000398832026 2 Marilyn Manson 0.00000398832026 2 Metin Kaplan 0.00000398832026 2 Mohamed Fulayfel 0.00000398832026 2 míssil balístico 0.00000398832026 2 Labrador Inuit 0.00000398832026 2 Bairro Francês 0.00000398832026 2 Mona Lisa 0.00000398832026 2 Nadya Suleman 0.00000396565929 25 as forças 0.00000395302550 8 F 1 0.00000394139897 12 nas eleições 0.00000392600259 6 estamos aqui 0.00000348978028 2 119 universidades 0.00000348978028 2 Kia Pride 0.00000348978028 2 alimento básico 0.00000348978028 2 Tyson Gay 0.00000348978028 2 Brendan Fraser 0.00000348978028 2 prisões secretas 0.00000348978028 2 Salvatore Gravano 0.00000348978028 2 Andrei Kokoshin 0.00000348978028 2 cabo Bravo 0.00000348978028 2 Granada Teatro 0.00000348978028 3 will be 0.00000345452986 49 e outros 0.00000332740296 25 entre as 0.00000330610760 3 Albert Reynolds 0.00000330610760 3 Privacy International 0.00000330610760 3 Josh Schwartz 0.00000296740404 34 não foi 0.00000291422134 20 sua vida 0.00000285527472 3 agressão sexual 0.00000279182404 2 Escritor Samir 0.00000279182404 2 Mauricio Pineda 0.00000279182404 2 Marina Petrella 0.00000279182404 2 dieta mediterrânea 0.00000279182404 2 Michel Rocard 0.00000279182404 2 Amanda Mealing 0.00000279182404 2 Carrie Prejean 0.00000279182404 2 Muammar Gaddafi 0.00000279182404 2 Katherine Heigl 0.00000279182404 2 raios X 0.00000279182404 2 JP Losman 0.00000279182404 2 SBC Communications 0.00000279182404 2 Soto Toro 0.00000245331285 31 ele é 0.00000241600173 3 T Frequency H Frequency Fidel Castro 0.00000232652019 3 "Pierre" 61500000 "Pierre" 61500000 sistemas operacionais 0.00000224565179 19 "Beregovoy" 16900 "Beregovoy" 16900 ele tem 0.00000216607054 3 "apparently" 29600000 "commits" 401000000 comissão parlamentar 0.00000213128124 39 "left" 249000000 "suicide" 1880000000 que vai 0.00000210703706 4 "no" 1710000000 novas tecnologias 0.00000208769143 13 "message" 333000000 algumas das 0.00000202632395 3 "when" 802000000 Financial Times 0.00000201011335 6 "he" 402000000 in the 0.00000197524469 33 "shot" 90200000 trabalha para 0.00000195919188 45 "himself" 46500000 que uma 0.00000195917482 4 "with" 1840000000 partidos políticos 0.00000194307722 24 "a" 3750000000 contra os 0.00000193399137 15 "borrowed" 4710000 também são 0.00000179474409 3 setor privado "gun" 59200000

Table D.1: Web frequencies for calculations with All Words

Table D .

 D 2: Web frequencies for calculations with All Words

			Frequency
	T	H	T ∩ H	H ∩ T
	"Pierre" "Beregovoy"	11500

Table D

 D

				D.2 Without Stop Words D.3 With MultiWords Units
		.2: (continued) Table D.4: (continued) Table D.6: (continued)
	Frequency Table D.3: Web frequencies for calculations without Stop Words Frequency Table D.5: Web frequencies for calculations with MultiWords Units Frequency
	T "himself" "himself" "Beregovoy" H "Pierre" "himself" "commits" "himself" "suicide" "with" "Pierre" "with" "Beregovoy" "with" "commits" "with" "suicide" 201000000 293000000 T ∩ H H ∩ T 1960000 2000000 328 329 14900000 7340000 58000000 46000000 101000000 97300000 2900 2920 43800000 50300000 "a" "Pierre" 105000000 98200000 "a" "Beregovoy" 14500 14700 "a" "commits" 44300000 50900000 T Frequency H "Pierre" 61500000 "Pierre" "Beregovoy" 16900 "Beregovoy" "apparently" 29600000 "commits" "left" 249000000 "message" "when" "shot" "himself" "borrowed" "gun" "himself" "suicide" 58000000 "borrowed" 4710000 46000000 59200000 "himself" "commits" 14900000 "with a" 519000000 7340000 4710000 "himself" "Beregovoy" 328 "himself" 46500000 329 46500000 "himself" "Pierre" 1960000 "shot" 90200000 2000000 90200000 "shot" "he" 402000000 "suicide" 108000000 114000000 802000000 "shot" "commits" 22200000 "when" 802000000 19600000 333000000 "shot" "Beregovoy" 271 "message" 333000000 275 "suicide" 1880000000 "shot" "Pierre" 18800000 "no" 1710000000 15800000 401000000 "when" "left" 249000000 "suicide" 1880000000 "suicide" 268000000 172000000 16900 "when" "commits" 37800000 "apparently" 29600000 "commits" 401000000 39900000 61500000 "when" "Beregovoy" 1490 "Pierre Beregovoy" 8300 "Pierre Beregovoy" 8300 1490 Frequency T H T ∩ H H ∩ T T Frequency H Frequency T H
	"a" "borrowed" "gun" 59200000 "suicide" 311000000 294000000 "Pierre" 119000 144000
	"borrowed" Table D.4: Web frequencies for calculations without Stop Words "Pierre" 119000 144000 "borrowed" "Beregovoy" 44 44
	"borrowed" "Beregovoy" "borrowed" "commits" "borrowed" "suicide" "gun" "Pierre" "gun" "Beregovoy" "gun" "commits" "gun" "suicide" "borrowed" "commits" H T ∩ H 14000000 44 40800 843000 1910000 193 71000000 40800 Frequency "borrowed" "suicide" 843000 H ∩ T 11500000 44 40900 717000 4360000 193 40900 717000 "Pierre" "Beregovoy" T "gun" "Pierre" 1910000 4360000 Table D.6: Web frequencies for calculations with MultiWords Units 11500 "Pierre" "commits" 59200 "Pierre" "suicide" 1560000 "Beregovoy" "commits" 32 "gun" "Beregovoy" 193 193 "gun" "commits" 14000000 Frequency 11500000 "gun" "suicide" 71000000 T H T ∩ H H ∩ T 72600000 "Pierre Beregovoy" "commits" 60 72600000 "Beregovoy" "suicide" 1220 "Pierre Beregovoy" "suicide" 2110
	"apparently" "apparently" "Pierre Beregovoy" "Pierre" 1460000	144
	"apparently" "Beregovoy" "apparently" "commits"	231 3320000
	"apparently" "apparently"	"commits" "suicide" 3320000 17300000
	"apparently" "left" "Pierre Beregovoy" "suicide" 17300000	1190
	"left" "left"	"Pierre" "commits" 30900000 21400000
	"left" "Beregovoy" "left" "suicide" 136000000 761
	"left" "no" "Pierre Beregovoy" "commits" 21400000	5850
	"left" "no"	"suicide" 136000000 "commits" 37700000
	"message" "no"	"Pierre" "suicide" 263000000 15700000
	"message" "Beregovoy" "message" "Pierre Beregovoy"	1890	3120
	"message" "message"	"commits" "commits" 5700000 5700000
	"message" "message"'	"suicide" "suicide" 62800000 62800000
	"when" "when" "Pierre Beregovoy" "Pierre" 83000000	1710

http://hci.stanford.edu/~winograd/shrdlu/ [Last access: 14 th December,

2013]2 http://en.wikipedia.org/wiki/SHRDLU [Last access: 14 th December, 2013] 3 http://en.wikipedia.org/wiki/Joseph_Weizenbaum [Last access: 14 thDecember, 2013]

http://www.merriam-webster.com/ [Last access: 14 th December,

2013]

RTE: http://www.nist.gov/tac/2010/RTE/ [Last access: 14 th December,

2013] 2 AVE: http://nlp.uned.es/clef-qa/ [Last access: 14 th December, 2013] 3 NTCIR-9 RITE: http://artigas.lti.cs.cmu.edu/rite/ [Last access: 14 th December, 2013]

http://www.nist.gov/tac/2008/rte/rte.08.guidelines.html [Last access: 14 th December,

2013]

http://crowdflower.com/ [Last access: 14 th December,

2013] 2 http://www.mtruk.com/ [Last access: 14 th December, 2013]

http://duc.nist.gov/duc2004/ [Last access: 14 th December,

2013] 2 http://www.textmap.com/ [Last access: 14 th December, 2013] 3 http://l2r.cs.uiuc.edu/~cogcomp/ [Last access: 14 th December, 2013] 4 http://demo.patrickpantel.com/demos/lexsem/paraphrase.htm [Last access: 14 th December, 2013]

http://www.cs.columbia.edu/~noemie/alignment/ [Last access: 14 th December,

2013] 2 http://news.google.com/ [Last access: 14 th December, 2013]

ACE

information extraction templates, from the NIST -http://www.nist.gov/speech/tests/ace/ [Last access: 14 th December, 2013] 2 Message Understanding Conference, 1992 3 http://trec.nist.gov/data/qa.html [Last access: 14 th December, 2013] 4 http://clef-qa.fbk.eu/ [Last access: 14 th December, 2013]

http://pascallin.ecs.soton.ac.uk/Challenges/RTE/ [Last access: 14 th December,

2013]2 http://wordnet.princeton.edu/ [Last access: 14th December, 2013]

(2006) 0,754 X X X X X X X Tatu et al. (2006) 0,738 X X X Zanzotto et al. (2006) 0,639 X X X X Adams et al. (2006) 0,626 X X Bos & Markert (2006) 0,616 X X XTable 2.8: Best Results in RTE-2 (Ido et al., 2006)InHickl et al. (2006), they introduce a new system for RTE (known as GROUNDHOG) which utilizes a

http://xwn.hlt.utdallas.edu/ [Last access: 14 th December,

2013]2 http://www.timeml.org/site/tarsqi/ [Last access: 14th December, 2013]

http://en.wikipedia.org/ [Last access: 14 th December,

2013]2 The dependency parser used is MINIPAR(Lin, 1998) 3 They used the Stanford NE recognition system(Finkel et al., 2005) 4 http://demo.patrickpantel.com/demos/verbocean/ [Last access: 14th December, 2013]

http://www.alias-i.com/lingpipe/ [Last access: 14 th December,

2013]

Iftene & Moruz (2009) 0,735 X X X X X X Wang et al. (2009) 0,685 X X X Li et al. (2009) 0,670 X X Mehdad et al. (2009) 0,662 X X X Sammons et al. (2009) 0,643 X

http://www.mtruk.com/ [Last access: 14 th December,

2013]

Our Gold Units are available at http://hultig.di.ubi.pt/~sebastiao/ [Last access:

th December, 2013] 2 This dataset is available at http://hultig.di.ubi.pt/~sebastiao/ [Last access: 21 th December, 2013] 3 Source: https://crowdflower.com/resource-library [Last access: 14 th December, 2013]

Input Pairs are available at http://hultig.di.ubi.pt/~sebastiao/ [Last access:

th December, 2013]

The subset of 1203 TE by Generality pairs is available at http://hultig.di.ubi.pt/~sebastiao/ [Last access: 21 th December, 2013]

From now on, we will refer to sentences, passages and texts simply as texts.

Source: http://www.microsoft.com/en-us/download/confirmation.aspx?id=10024 [Last access: 14 th December,

2013]2 Source: http://www.linguateca.pt/chave/stopwords/ [Last access: 14 th December, 2013]

https://code.google.com/apis/console/ [Last access: 14 th December,

2013]

The weighted average is a average where there is some variation in the relative contribution of individual data values to the average. Each data value (X i ) has a weight assigned to it (W i ). Data values with larger weights contribute more to the weighted average and data values with smaller weights contribute less to the weighted average.

https://translate.google.pt/ [Last access:

th December, 2013]

Acknowledgements

Muito Obrigado Por Tudo

List of Abbreviations

AAM Asymmetric Association Measures. X X

Summary

The RTE systems results demonstrate general improvement with time, with overall accuracy levels ranging from 50% to 65% on RTE-1 (17 submissions), from 53% to 75% on RTE-2 (23 submissions), from 49% to 80% on , from 45% to 74% on RTE-4 (26 submissions, three-way task)

and from 43% to 75% on RTE-5 (20 submissions, three-way task). Common approaches used by the submitted systems include ML, logical inference , cross-pair similarity measures between T and H and word alignment.

All pairs of the Test Set of the first five RTE Challenges

the weighted average formula looks at how relevant each number is. Say that 1 only happens 10% of the time while 2 and 3 each happen 45% of the time. The percentages in this example would be the weights. The weighted average would be 2, 35.

More specifically, in our work, we defined following equations -Average Accuracy (Equation 5.3), Average Precision (Equation 5.4) and Weighted Average Accuracy (Equation 5.5), Weighted Average Precision (Equation 5.6).

AC =

∑ n i=1 AC i n

(5.3)

(5.4)

(5.5)

(5.6)

All pairs of the Test Set of the first five RTE Challenges

In this section, we present the performance of our methodology measured in terms Arithmetic Average and Weighted Average of both Accuracy and Precision, as these two metrics are commonly used to assess performance in the RTE field. With the results presented here we can see how our methodology behaves in the RTE task. We detail our results over five sets of T -H pairs used for evaluation in the early RTE challenges. This endeavor provides for a fair comparison of our methodology and the results of other researchers.

All Words

This approach involves more calculations, compared to the other two approaches, since all the words in the texts snippets are considered, as we demonstrate in Section 4.5. More words imply also more search requests to the Google API, consequently longer delay in obtaining results.

In terms of Accuracy the measure that achieves the best results is the Braun-Blanket with Arithmetic Average of 0, 55 and Weighted Average equal to 0, 54. The J-measure in Weighted Average achieves 0, 54. The worst performance is of the Conviction measure with 0, 52 for both Arithmetic Average

All Words

On average over 8 AAMs, out of the 1203 positive TE by Generality pairs about 901 were correctly identified as such and the other about 302 were missed, i.e., our approach achieved 75% hit rate.

Analyzing each measure individually, Table 5.14, we see that the measure that correctly classifies the greatest number "Entailment by Generality" pairs is the J-measure, with 997 correct, and the one with worst performance is Braun-Blanket, with 834 correct.

Instructions

When people talk and write they convey both explicit and implicit information. People are in general capable to infere the implicit part. For example, when one tells that they have stained their white shirt, we can deduce that the white one is not the only one that the speaker has.

We are interested in learning to recognise, given a pair of sentences -the Text T and the Hypothesis H, whether H can be infered provided the T is true. This task is called Recognition of Textual Entailment and is a key task for many natural language processing (NLP) applications.

Thus, Recognizing Textual Entailment consists in determining whether an entailment relation holds between a text T and a hypothesis H. It is said that entailment relation holds between T and H when the meaning of H can be inferred from T.

Informally, T entails H if, typically, a human reading T would infer that H is most likely true based on the truth of T.

In logic deductive reasoning is a kind of inference in which the conclusion is of no greater generality than the premises. This is why we put all cases of TE in two categories -TE but not Generality which is equivalent to deductive reasoning and TE by generality, where the Hypothesis H is in some sense more general than the Text T. For example, from T below one can conclude that Unterweger was not killed as no one has access to him inside the cell, so it was a suicide, but H does not elaborate on the exat means in contrast to T. Thus, the realtion between T -H is TE by Generality.

T: Unterweger was found hanging from his cell roof less than 24 hours after being sentenced to life for a second time.

H: Unterweger committed suicide.

On the other side the following pair T -H is TE but not Generality as H is true given T, but H is no more general with respect to the details it has in common with T.

teemed.

H: Linnaeus was a professor in Uppsala.

All pairs T -H in this job come from RTE1 through RTE5 PASCAL Challenges. H: Tea protects from some diseases.

Choose one

Entailment by Generality

Entailment, but not Generality