Md Rashedur Rahman

Olivier Mesnard

Jérémy Guillemot

Pierre Ternay

Christian Lautier

Julien, Arnaud, Swen, Christopher Charlotte Zheng

Antonio Guterres

Ban Ki- Moon Sasha

Malia Francoise Hollande

Angela Merkel

Hillary Clinton

John Kerry

Barack Obama

Michelle Obama

Sasha Malia

John Kerry Barack

Obama Michelle

Knowledge Base Population based on Entity Graph Analysis

Keywords: 6, 3 Supervised Relation Validation and Knowledge Base Population, xxiii

Knowledge Base Population (KBP) is an important and challenging task specially when it has to be done automatically. The objective of KBP task is to make a collection of facts of the world. A Knowledge Base (KB) contains different entities, relationships among them and various properties of the entities.

Relation extraction (RE) between a pair of entity mentions from text plays a vital role in KBP task. RE is also a challenging task specially for open domain relations. Generally, relations are extracted based on the lexical and syntactical information at the sentence level. However, global information about known entities has not been explored yet for RE task. We propose to extract a graph of entities from the overall corpus and to compute features on this graph that are able to capture some evidence of holding relationships between a pair of entities.

In order to evaluate the relevance of the proposed features, we tested them on a task of relation validation which examines the correctness of relations that are extracted by different RE systems. Experimental results show that the proposed features lead to outperforming the state-of-the-art system.

First and foremost I would like to express many thanks to my supervisors Brigitte Grau and Sophie Rosset. Their insightful guidelines directed me toward a successful PhD candidate. Both of them spent their precious time for many discussion sessions. Their intellectual suggestions helped me to overcome the hurdles during

v Résumé: Le peuplement de base de connaissance (KBP) est une tâche importante qui présente de nombreux défis pour le traitement automatique des langues. L'objectif de cette tâche est d'extraire des connaissances de textes et de les structurer afin de compléter une base de connaissances. Nous nous sommes intéressé à la reconnaissance de relations entre entités.

L'extraction de relations (RE) entre une paire de mentions d'entités est une tâche difficile en particulier pour les relations en domaine ouvert. Généralement, ces relations sont extraites en fonction des informations lexicales et syntaxiques au niveau de la phrase. Cependant, l'exploitation d'informations globales sur les entités n'a pas encore été explorée. Nous proposons d'extraire un graphe d'entités du corpus global et de calculer des caractéristiques sur ce graphe afin de capturer des indices des relations entre paires d'entités.

Pour évaluer la pertinence des fonctionnalités proposées, nous les avons testées sur une tâche de validation de relation dont le but est de décider l'exactitude de relations extraites par différents systèmes.

Les résultats expérimentaux montrent que les caractéristiques proposées conduisent à améliorer les résultats de l'état de l'art. vii

Synthèse en français

Aujourd'hui, à l'ère du World Wide Web (WWW), une énorme quantité d'informations sont disponibles dans des formats lisibles par machine. Le texte est l'un des formats les plus courants de publication de contenus dans différents médias et de communication entre les êtres humains. Dans notre vie quotidienne, nous recherchons différentes informations et attendons qu'elles soient disponibles sur demande. Les sources d'information existantes lisibles par machine sont pour la plupart non structurées (par exemple un portail de nouvelles) et semi-structurées (par exemple Wikipédia). Par conséquent, il devient très difficile de trouver des informations utiles immédiatement. Ce problème peut-être résolu en stockant l'information d'une manière structurée.

Une base de connaissances (KB) est une collection structurée d'informations. Elle représente les faits du monde. Un fait dans un KB se réfère à une relation sémantique binaire entre deux entités du monde réel. Les types d'entités du monde réel sont la personne, l'organisation, la localisation, etc. Une KB nous fournit des informations précises sur différentes entités. Ainsi, il facilite la réponse aux questions [START_REF] Demner-Fushman | Answering clinical questions with knowledge-based and statistical techniques[END_REF][START_REF] Fader | Open question answering over curated and extracted knowledge bases[END_REF] et le service à la clientèle [START_REF] Khodakarami | Exploring the role of customer relationship management (CRM) systems in customer knowledge creation[END_REF][START_REF] Cheung | A multi-perspective knowledge-based system for customer service management[END_REF] dans divers domaines. Ces dernières années, l'extraction d'informations factuelles à partir de textes et leur stockage dans une base de données ont été un sujet de recherche très étudié.

Il existe de nombreux KBs où Freebase, DBpedia, YAGO, Wikidata qui sont très connus. Aucune base de connaissances existante n'est complète. En outre, sur le web, de nombreuses informations sont publiées chaque jour dans des textes. Les faits manquants peuvent être collectés à partir des textes libres. Le peuplement de base de connaissances (KBP) est la tâche de recueillir des informations factuelles à partir de textes. C'est une tâche importante et stimulante surtout quand elle doit être faite automatiquement. L'extraction de relations (RE) entre une paire de mentions d'entité à partir du texte joue un rôle essentiel dans la tâche KBP. L'extraction automatique de relation dansun texte est une tâche difficile. Elle est particulièrement complexe lors de la recherche d'un grand nombre de relations sémantiques qui décrivent des entités dans le domaine ouvert. Les systèmes d'extraction de relation existants génèrent un grand nombre de fausses relations entre différentes entités qui rendent une base de connaissances automatiquement remplie moins précise. Par conséquent, nous avons été motivés pour valider les hypothèses de relation qui sont générées par différents systèmes d'extraction de relation. L'objectif est de rejeter un viii grand nombre de fausses relations sans affecter les bonnes pour que le score global dans la tâche KBP puisse être amélioré.

Dans la littérature sur la caractérisation des relations, des analyses fiables telles que le vote majoritaire [START_REF] Sammons | Overview of UI-CCG systems for event argument extraction, entity discovery and linking, and slot filler validation[END_REF] ont été étudiées spécialement lorsque les hypothèses de relation sont générées par plusieurs systèmes. Le vote à la majorité lui-même ne peut pas atteindre un bon score. Par conséquent, des informations supplémentaires telles que les caractéristiques linguistiques sont prises en compte. Les caractéristiques linguistiques traditionnelles (par exemple, lexicales et syntaxiques) se sont avérées utiles pour la tâche de caractérisation des relations, mais elles n'obtiennent pas un très haut score.

Les informations globales sur les entités, c'est-à-dire la manière dont une entité est associée à d'autres entités dans une ressource partagée, peuvent être efficaces pour trouver des indices permettant de valider une relation entre deux entités. Deux entités apparentées partagent des voisins communs dans leurs activités quotidiennes. Dans les activités d'une entité particulière, les autres entités qui participent à ces activités sont considérées comme les voisins de cette entité particulière. Ainsi, une communauté d'une entité est construite par les entités voisines. Les informations globales sur les entités n'ont pas été utilisées pour la tâche de caractérisation des relations. Nous étudions un graphe d'entités qui nous permet d'explorer les informations globales sur les entités et de fournir des informations utiles si une paire d'entités est dans une vraie relation. Nous proposons de calculer plusieurs caractéristiques telles que la similarité du réseau, la densité du réseau, la centralité du vecteur propre et l'information mutuelle pour valider une relation basée sur l'analyse du graphe d'entité. De plus, nous utilisons certaines caractéristiques de la littérature sur la caractérisation des relations et proposons de nouvelles fonctionnalités basées sur l'analyse linguistique.

Nous considérons la validation de relation comme une tâche de classification binaire. Le but est de déterminer si une hypothèse de relation est vraie ou fausse lorsque on donne une paire d'entités, une phrase justifiant la relation ainsi qu'un graphe d'entités. De plus, nous proposons un modèle pour la tâche KBP basé sur notre modèle de validation de relation.

Afin d'évaluer la pertinence des fonctionnalités proposées, nous les avons testées sur une tâche de validation de relations. Nos résultats expérimentaux montrent que les caractéristiques des graphes proposées améliorent significativement la performance de la validation de la relation lorsqu'elles sont combinées avec certaines caractéristiques linguistiques de base. Dans l'ensemble, nous obtenons un score F plus élevé d'environ 10 points par rapport à une combinaison de quatre caractéristiques ix linguistiques. De plus, notre méthode de validation de relation est utilisée pour remplir une base de connaissances en validant les hypothèses de relation générées par différents systèmes d'une manière globale. Notre système de KBP basé sur la validation des relations améloire le système KBP de référence la plus performante d'environ 1, 27 point spécialement pour certaines relations sémantiques sélectionnées. (Mikolov et al., 2013) . . . . 4.4 Encoding semantic differences in between the vectors [START_REF] Mikolov | Linguistic regularities in continuous space word representations[END_REF] 1.1 Size of some existing knowledge bases [START_REF] Li | IMPROVING KNOWLEDGE BASE POPULATION WITH IN-FORMATION EXTRACTION[END_REF] . . . . . . . . . .

T

Oday, in the age of information technology, an enormous amount of information is available in machine-readable formats. The text is one of the very common formats of publishing information in different media and communicating among human beings. In our daily life, we search for various information and expect them to be available on demand. Therefore, extracting information automatically has become a very important task. Information extraction from texts has been a very interesting topic in Natural Language Processing (NLP) research since the last couple of decades [START_REF] Grishman | Message understanding conference-6: A brief history[END_REF]. The existing machine readable information sources are mostly unstructured (e.g. news portal) and semi-structured (e.g. Wikipedia). Usually, information is extracted automatically from these sources and stored in a structured fashion for further usage. Structured information basically refers to factual information between different types of entities. Such information is very useful in several tasks specially for question answering (Demner-Fushman and [START_REF] Demner-Fushman | Answering clinical questions with knowledge-based and statistical techniques[END_REF][START_REF] Fader | Open question answering over curated and extracted knowledge bases[END_REF] and customer service [START_REF] Khodakarami | Exploring the role of customer relationship management (CRM) systems in customer knowledge creation[END_REF][START_REF] Cheung | A multi-perspective knowledge-based system for customer service management[END_REF] in various domains. In recent years, extracting factual information from texts and storing them in a database have been much studied research topic.

Increasing of huge information on the web in different formats opens various dimensions of research works related to information extraction. In the same context, IRT SystemX1 , an Institute for Technological Research (IRT) comes with a project named Multimedia Multilingual Integration (IMM2 ). IMM project aims at developing tools for monitoring user extracted knowledge from unstructured information sources (specially text and audio) in order to make some reports or decisions. One important part of this project is extracting advanced semantic information such as factual information from raw texts. This research represents a part of IMM project aiming at populating a knowledge base from free texts.

A Knowledge Base (KB) is a special-purpose structured collection of information which is readable and manageable by machine. It provides useful information on demand. Usually, a knowledge base comprises factual information in triplets. A fact is a triple (relation, subject, object) where the subject and object refer to entities and relation refers to the relation name between the subject and object. For example, a triplet of (spouse, Barack Obama, Michelle Obama) indicates spouse relationship between Barack Obama and Michelle Obama. A fact may also represent a property of an entity. For [START_REF] Li | IMPROVING KNOWLEDGE BASE POPULATION WITH IN-FORMATION EXTRACTION[END_REF] In recent years, several knowledge bases have been constructed where DBpedia [START_REF] Auer | Dbpedia: A nucleus for a web of open data[END_REF], Freebase [START_REF] Bollacker | Freebase: a collaboratively created graph database for structuring human knowledge[END_REF], YAGO [START_REF] Hoffart | YAGO2: A spatially and temporally enhanced knowledge base from Wikipedia[END_REF][START_REF] Biega | Inside YAGO2s: A transparent information extraction architecture[END_REF][START_REF] Mahdisoltani | Yago3: A knowledge base from multilingual wikipedias[END_REF], DeepDive [START_REF] Niu | DeepDive: Web-scale Knowledge-base Construction using Statistical Learning and Inference[END_REF], Google Knowledge Graph [START_REF] Singhal | Introducing the knowledge graph: things, not strings[END_REF] etc. are very well-known. These knowledge bases contain millions of facts among different types of entities such as person, organization, location etc. Table 1.1 represents statistics of some existing knowledge bases. Most of the existing knowledge bases represent facts by following the standard of Resource Description Framework (RDF) or similar format. A knowledge base can be represented also graphically where the entities and relation types are denoted by nodes and edges accordingly.

A knowledge base provides us various information that we search for in our daily life. Moreover, knowledge bases are used in the back-end of search engines and some virtual personal assistant applications such as Google Assistant, Apple's Siri, Micorisoft's Cortana, Amazon's Alexa etc.

Knowledge Base Population (KBP) is the task of constructing a knowledge base. KBP has become a highly explored research topic in NLP field since last decade (Auer et al., 2007 Suchanek, Kasneci, and[START_REF] Suchanek | Yago: a core of semantic knowledge[END_REF][START_REF] Bollacker | Freebase: a collaboratively created graph database for structuring human knowledge[END_REF]. In the existing knowledge bases such as DBpedia3 , Freebase4 , YAGO5 etc, different properties of entities and relationships between entities have been collected from structured and semi-structured information sources. Different methods have been used for building these knowledge bases. DBpedia was built by crowd-sourced community. In DBpedia project, structured information has been extracted from Wikipedia infoboxes [START_REF] Lehmann | DBpedia-a large-scale, multilingual knowledge base extracted from Wikipedia[END_REF] automatically. However, these infoboxes followed different templates that prone to error in automatic information extraction. These errors were solved by crowd-sourced mapping. However, in Freebase, the data was mainly composed of its community members. Freebase allowed end-users to edit the existing structured information. It also integrated data from other structured information sources which are: Wikipedia, NNDB6 , FMD7 and MusicBrainz8 . On the other hand, YAGO was built automatically from Wikipedia, GeoNames and WordNet [START_REF] Hoffart | YAGO2: A spatially and temporally enhanced knowledge base from Wikipedia[END_REF]. Several rules were defined for extracting information automatically from Wikipedia articles.

No existing knowledge base is complete. A lot of facts are missing in the existing knowledge bases. Missing facts can be collected from free texts. However, free texts exist in a large volume and it has been increasing day by day. Therefore, populating a knowledge base has to be done automatically or semi-automatically leading to human curation. In order to construct a knowledge base automatically from free texts, extraction of relation is an important component. Relation Extraction (RE) is a kind of information extraction task which extracts related pairs of entities (subject and object) from texts and characterizes semantic types of the relations. It requires natural language understanding (NLU) of pieces of texts. For instance, a relation extraction system should be able to extract six relationships of three semantic types spouse, children and parent among four entities Chelsea Victoria, Bill Clinton, Hillary Clinton and Marc Mezvinsky from the sentence Chelsea Victoria, the daughter of Bill Clinton and Hillary Clinton got married to Marc Mezvinsky. as illustrated in Ex 1.1. The expression of a semantic relation mostly depends on trigger words. A trigger word is a content word which is able to characterize the semantic type of a relation when it takes place between two entities. For example, married is a trigger word for spouse relation.

Automatically extraction of relations from texts is a difficult task. It is particularly complex when searching for a large number of semantic relations that describe United States national institute of standards and technology (NIST9 ) has been conducting text analysis conference (TAC10 ) for evaluating automatic KBP task since 2009. In KBP task, a set of queries is given where each query is defined by a subject entity and a relation name. A KBP system has to extract the object entity of a query relation from raw texts. Additionally, it has to provide a relation justifying text to support the query relation between the pair of entities. KBP systems usually employ relation extraction systems to produce relation hypotheses between entities. Most of the automatic KBP systems obtain a very low score [START_REF] Surdeanu | Overview of the english slot filling track at the tac2014 knowledge base population evaluation[END_REF]. One of the most important reasons for resulting a low score is the poor performance of the relation extraction systems. Relation extraction systems generate a large number of false relationships among different entities that lead KBP systems to result in lower precision [START_REF] Surdeanu | Multi-instance multi-label learning for relation extraction[END_REF].

Research Objective

KBP systems generate many false responses to the given queries. Some sample responses to a query are illustrated in Ex 1.2. The given subject entity and relation name are Barack Obama and spouse accordingly. There are three candidates Michelle Obama, Michelle Robinson and Hillary Clinton to be the object of the query relation (spouse, Barack Obama, ?). According to the justification texts, Michelle Obama (Response 1) is the correct object since the word married expresses the spouse relationship between Barack Obama and Michelle Obama. In Response 2, the text does not justify spouse relationship between them. Moreover, in Response 3, the relation justifying text expresses spouse relationship between Barack Obama and Michelle Obama but not between Barack Obama and Hillary Clinton. In KBP evaluation task, Response 2 and 3 are considered as wrong. As a result, these wrong responses cause a system getting a lower score. The score of a system can be improved by discarding the wrong responses. Moreover, several relation extraction systems can be employed to improve the KBP scores. The objective is to discard a large number of false relations without affecting the correct ones so that overall score in KBP task can be improved. Suppose, we are given a set of queries (Q) and a text corpus (T C) where each of the queries is defined by a subject entity (E q ) and a relation name (R), and different relation extraction systems generate a set of candidate objects {E c 1 , E c 2 ,...,E cn } E c from T C with justifying text excerpts for each of the candidates. We aim at deciding whether a claimed relation (R, E q , E ci ) is correct or wrong for improving KBP scores.

Trustworthy measurements have been introduced for relation validation task when relation hypotheses are generated by multiple systems. As the trustworthy measurements, [START_REF] Sammons | Overview of UI-CCG systems for event argument extraction, entity discovery and linking, and slot filler validation[END_REF] used majority voting and [START_REF] Rodrıguez | University of Florida 2016 Slot Filler Validation system[END_REF] combined several trustworthy signals come from systems, source documents and user beliefs for validating relation in KBP task. However, using such features has not proven to be sufficient.

Linguistic analysis (semantic and syntactic) provides useful information to justify Chapter 1. Introduction either a claimed relation is correct or not. However, in some cases, specially when a relation is expressed in a long or complex sentence, linguistic analyzer fails to capture the useful information. Sometimes, natural language is ambiguous and hence, linguistic analysis cannot identify the semantics of a word. As a consequence, it fails to detect the true relationship between a pair of entity mentions in a sentence.

Relation extraction and relation validation can be considered as the opposite sides of the same coin. In relation validation task, several linguistic features have been inherited from the task of relation extraction. Semantic information such as words between the related pair of entity mentions have been inspected by comparing them to a set of pre-collected trigger words for justifying a claimed relation [START_REF] Yu | The Wisdom of Minority: Unsupervised Slot Filling Validation based on Multi-dimensional Truth-Finding[END_REF]. Syntactic dependency path has been examined as well. Dependency patterns of relation expression can be studied for validating a claimed relation.

Linguistic analysis captures local information for justifying a relation. Apart from linguistic information, global information about entities, i.e. how an entity is associated with other entities in a shared resource can be effective for finding some clues to validate a relationship between two entities. Two related entities share some common entities in their daily life activities. In the activities of a particular entity, other entities which participate in that activities are considered as the neighbors of that particular entity. Thus a community of an entity is built by the neighbor entities. A graph of entities allows us to explore global information about the entities and it can provide some information if they are in a relationship.

We summarize our research objective by two questions from two different perspectives: entity graph and linguistic analysis which are stated below.

• Q1: Can entity graph analysis provide some clues to validate a relationship between two entities?

• Q2: Can some linguistic features be improved to capture useful information for validating a claimed relation?

Contributions

Important and influential nodes in a graph can be identified by measuring node centralities [START_REF] Friedl | A critical review of centrality measures in social networks[END_REF]. Such measurement ranks the nodes in a graph. Graph based ranking Method has been proven effective for validating relation [START_REF] Jain | Factrank: Random walks on a web of facts[END_REF][START_REF] Jean-Louis | Text Segmentation and Graph-based Method for Template Filling in Information Extraction[END_REF][START_REF] Singh-Blom | Prediction and validation of gene-disease associations using methods inspired by social network analyses[END_REF]. These methods mainly employed PageRank [START_REF] Brin | The anatomy of a large-scale hypertextual Web search engine* 1[END_REF] algorithm and Katz measure [START_REF] Katz | A new status index derived from sociometric analysis[END_REF] on a graph for re-ranking the candidates. A graph 1.2. Contributions also facilitates to perform information-theoretic measurements. Such measurement has been successfully used in knowledge discovery task [START_REF] Holzinger | On graph entropy measures for knowledge discovery from publication network data[END_REF].

In order to study the impact of the surroundings of entities, we construct a graph of entities from a given corpus. The link between two entities in a graph indicates that the pair of entities are mentioned in the same sentence so that they are somehow related in the real world. We define a community of an entity by the directly connected neighbors in the graph. Fig. 1.1 shows an example of such type of graph where the communities of Barack Obama, Michelle Obama and Hilary Clinton are denoted by the green rectangle, purple circle and orange ellipse accordingly. We analyze the community graphs of entities for identifying some clues of having a relationship between a pair of entities. We compute network density, network similarity, mutual information between two communities and eigenvector centrality of entity nodes in a community graph. These measurements quantify how two entities are related to each other based on their global association. For instance, network similarity quantifies the similarity between the communities of a query entity and of a candidate object based on the number of community members they share. According to Fig. 1.1, the similarity between the communities of Barack Obama and Michelle Obama is higher than that between the communities of Barack Obama and Hillary Clinton because the pair (Barack Obama, Michelle Obama) share three entities while (Barack Obama, Hillary Clinton) pair has only one entity in common between their communities.

The expression of relation at the sentence level follows some syntactic patterns which can be captured from annotated examples. However, all the patterns of a relation may not be collected due to lack of annotated data. Therefore, we propose to compute edit distance between a dependency pattern under analysis and a list of Chapter 1. Introduction learned dependency patterns for justifying the relation under validation. For characterizing the semantic type of a relation, we depend on some state-of-the-art linguistic features that have been successfully used in semantic relation extraction task.

Inspecting the existence of any trigger word between entity mentions plays an important role in relation validation task. However, it may not be possible to collect all the trigger words of a relation due to lack of annotated positive examples. In order to identify the unknown triggers of a relation, we propose to utilize word embeddings for computing similarity between the vectors of a content word and a known trigger word of a relation. Thus our relation validation model takes into account entity level global information as well as linguistic information.

We consider relation validation as a binary classification task. Therefore, we train a binary classifier with the graph features computed on the community graphs and features based on linguistic analysis. Our experimental results show that the proposed graph features improve the performance of relation validation significantly when they are combined with some baseline linguistic features. Overall we gain around 10 points higher F-score by this combination compared to a baseline of four linguistic features. Furthermore, our relation validation method is employed to populate a knowledge base by validating the relation hypotheses generated by different systems in an ensemble fashion. Our relation validation based ensemble system outperforms the best scoring baseline KBP system by around 1.27 point on triggerdependent relations.

Outline

Relation extraction and relation validation are very active research domain. In particular, different linguistic and graph based methods have been proposed to handle these problems. Therefore, we dedicate Chapter 2 to the literature review on knowledge base population, relation extraction, relation validation.

• In Chapter 3, we present how community graphs can be used for validating relations. Firstly, we focus on the definition of the graph of entities and the graph construction. Then different measurements on the community graphs are described. Finally, we describe how a claimed relation between two entities can be validated based on community graph analysis.

• In Chapter 4, we describe the linguistic aspects of expressing and validating semantic relations. In this chapter, firstly, different syntactic modeling are studied. Then we illustrate the lexical semantics for characterizing the type 1.3. Outline of a relation. We also study the use of word embeddings for analyzing lexical semantics. Finally, different word embeddings are evaluated in a setting of relation validation task.

• In Chapter 5, we describe our relation validation framework. This chapter summarizes all the features that we use for validating relations. We also describe the corpora used in our research and preprocessing of the corpora. Finally, evaluation metrics of relation validation and KBP tasks are defined.

• In Chapter 6, we present different experiments on relation validation and knowledge base population. Firstly, we build some relation validation models and employ them on KBP SFV task. Then we observe the performance and investigate the limitations of the relation validation models and how we improve the models. Finally, this chapter evaluates the performances of the improved models on both relation validation and KBP tasks.

• Finally, in Chapter 7, we present the conclusion and a summary how we answered our research question. Then this chapter concludes with some possible future research directions.

Publications

During this research work, we have published our works in some workshops and conferences. The list of publications are given below:

A

Utomatic knowledge base population (KBP) from texts is a special kind of information extraction (IE) task in the field of NLP research. It requires extracting factual information which refers to a binary relation between two entities. A binary relation is defined by a tuple of three elements: relation name, subject and object. For example, the spouse relationship between Barack Obama and Michelle Obama is referred by (spouse, Barack Obama, Michelle Obama) tuple.

KBP task is simply defined by some slots (or attributes) of different types of entities that have to be filled up by extracting the corresponding values from texts automatically. Slot filling task was first introduced in the 6th Message Understanding Conference (MUC-6) [START_REF] Grishman | Message understanding conference-6: A brief history[END_REF]. A slot is defined by a relation name and the subject of that relation. In slot filling task, the objective is to find the object of that relation. For example, (spouse, Barack Obama, ?) refers to a slot for slot filling task which has to be filled with the correct object value, Michelle Obama. U.S. National Institute of Standards and Technology (NIST) has been conducting a workshop named Text Analysis Conference (TAC) for evaluating KBP task since 2009 [START_REF] Mcnamee | Overview of the TAC 2009 knowledge base population track[END_REF][START_REF] Ji | Overview of the TAC 2010 knowledge base population track[END_REF][START_REF] Surdeanu | Overview of the TAC2013 knowledge base population evaluation: English slot filling and temporal slot filling[END_REF][START_REF] Surdeanu | Overview of the english slot filling track at the tac2014 knowledge base population evaluation[END_REF]. TAC defines slots of person and organization typed entities that count more slots compared to the number of slots defined in MUC-6.

Relation extraction (RE) plays a vital role in slot filling task. RE is the task of identifying the semantic type of relation between the subject and object entities from a text where the entities are mentioned. It can be formally defined as (subject, object, relation?) when a subject-object pair and a text are given. Suppose, given a sentence Barack Obama is married to Michelle Obama and two entities Barack Obama (subject) and Michelle Obama (object), RE task requires to identify the semantic type of the relation between these entities and a RE system should return the relation name, spouse.

A slot filling system employs one or more relation extractors in order to find out the filler values from texts. It is a very challenging task. Performances of the existing slot filling systems are affected by a large number of wrong filler values due to false relation extraction. Therefore, relation validation, a task of validating extracted relations becomes important for improving slot filling scores in KBP task. Relation validation can be defined as a binary classification task to say correct or wrong for provided a relation name, a pair of subject and object and a sentence. For example, given a sentence Barack Obama is married to Michelle Obama and a claimed relation (spouse, Barack Obama, Michelle Obama), a relation validation system has to justify the claimed relation as correct if the sentence really expresses Chapter 2. Literature Review the relation, otherwise wrong.

In this research, we focus on relation validation for improving slot filling scores in KBP task. Slot filling and relation validation tasks are different forms of relation extraction task. Therefore, in this chapter, we present the backgrounds and state-ofthe-arts of slot filling, relation extraction and relation validation tasks. Since relation extraction task requires different kinds of linguistic analysis we study several linguistic features of relation extraction based on syntactic and semantic analysis that can be used for relation validation task. Moreover, we explore global information about entities based on their community graphs for validating relations. Therefore, in this chapter, we also study state-of-the-arts of some graph based relation validation methods and some features computed on a graph. Finally, this chapter is concluded by adopting some features from the related tasks and proposing some new features for relation validation task.

Slot Filling Task

A slot basically refers to an attribute of an entity. For example, the slot per:employee_of denotes an organization where a person works as an employee. In this case, the organization name is the value of the employment attribute of that person.

Slot filling task requires filling the defined slots of different entities in a required format. Usually, the filler type (or types) of a slot is predefined. For example, the filler type of per:employee_of is organization which means per:employee_of has to be filled by the name of an organization or a company.

In MUC-6, the main focus was on information extraction from text messages. There was a special task named scenario template where several templates of different types of objects PERSON, ORGANIZATION, ARTIFACT etc. were defined. PER-SON and ORGANIZATION templates individually counted 5 and 9 slots accordingly as listed in Table 2.1. The objective was to fill up the templates by extracting relevant information from text messages. In most cases (i.e. PER_NAME, ORG_NAME etc), the type of a filler is not a named entity but a string. However, some slots hold values of specific types of named entities. For example, ORG_LOCALE slot required to be filled up by a location name {CITY, PROVINCE, COUNTRY, RE-GION, UNKNOWN}. Detail description of the templates and slots are available on the MUC-6 website1 . In scenario template task, a relation between two entities was encoded as an attribute of a template. To solve this problem, MUC-7 [START_REF] Chinchor | Muc-7 information extraction task definition[END_REF] In TAC KBP-2014 slot filling task [START_REF] Surdeanu | Overview of the english slot filling track at the tac2014 knowledge base population evaluation[END_REF], several slots were defined for PERSON and ORGANIZATION entities. PERSON and ORGANIZATION individually counted 25 and 16 slots accordingly as shown in Table 2.2. In most cases, the filler types are named entities. For example, per:spouse, per:employee_of etc have to be filled by person and organization typed entities accordingly. TAC provides an evaluation corpus and slot filling queries. A query is defined by an entity name, a corresponding document and a slot name as shown in Ex. 2.1. A slot filling system has to respond with the filler values including relation justification texts (from the given corpus). Detail descriptions of the slots, filler types, query and response formats are available in KBP-2014 website 2 . Definition and number of slots of the KBP slot filling task may vary in different years. For example, in KBP-2015 slot filling task, inverse slots (such as gpe:births_in_country is the inverse slot of per:country_of_birth) had been introduced. More details about the inverse slot can Chapter 2. Literature Review Using this information, a system can correctly extract the filler "per:country of birth=United States" for the above query. The provenance for this filler must include elements of the last two sentences, at least: "She was born in Chicago" and "Chicago is the third most populous city in the United States" (which were necessary to perform the inference that generated this slot filler). Importantly, the provenance no longer has to include text that disambiguates ambiguous mentions of entity and filler (although systems will not be penalized if they do). In this particular example, the entity mention is ambiguous in the above provenance ("She"). LDC assessors will manually disambiguate such mentions by reading a few sentences surrounding the provided provenance (this was proved sufficient in the previous evaluations). The human assessor will judge the correctness of the (possibly normalized) slot filler string, and correctness of the provenance offsets. We will report two different scores for this task: (a) ignoring the provenance offsets, and (b) scoring the provenance offsets, i.e., a slot filler will be considered correct only if both its value and its justification are correct. All in all, assuming the first block of text starts at offset 100 in document D1, and the second starts at offset 200 in document D2, a valid encoding for this provenance would be (without the quotes): "D1:209-232,D2:200-260".

Filler Values

Column 5 (if present) contains the canonical string representing the slot filler; the string should be extracted from the filler provenance in Column 6, except that any embedded tabs or newline characters should be converted to a space character and dates must be normalized. Systems have to normalize document text strings to standardized [START_REF] Aguilar | A comparison of the events and relations across ace, ere, tac-kbp, and framenet annotation standards[END_REF]. In ACE, relation extraction task required to detect and characterize the relation type between two entities for a given sentence and a pair of entity mentions. In slot filling task, the goal is to find the object entity or entities for a given relation name and a subject entity where the entity types are predefined. For example, in Ex. 2.1, Nelson Mandela refers to the subject entity and per:spouse indicates the relation name or slot. This slot has to be filled up by a person name who is the spouse of Nelson Mandela. In addition, slot filling requires a system to justify the claimed relation by providing a justification text along with the filler value as discussed in Section 2.1. Traditional evaluation of relation extraction tasks such as ACE and Se-mEval provide annotated training data which makes this task completely supervised. In KBP slot filling task, no annotated training data is provided that makes the task harder compared to the traditional relation extraction task.

Several methods of slot filling have been proposed during the last couple of years where most of them employed distant supervision [START_REF] Craven | Constructing biological knowledge bases by extracting information from text sources[END_REF][START_REF] Bunescu | Learning to extract relations from the web using minimal supervision[END_REF][START_REF] Mintz | Distant supervision for relation extraction without labeled data[END_REF] based relation extraction models [START_REF] Wiegand | Effective slot filling based on shallow distant supervision methods[END_REF][START_REF] Nguyen | New york university 2014 knowledge base population systems[END_REF][START_REF] Roth | Universal schema for slot-filling, cold-start KBP and event argument extraction: UMAss IESL at TAC KBP 2014[END_REF][START_REF] Angeli | Stanford's 2014 slot filling systems[END_REF][START_REF] Angeli | Bootstrapped self training for knowledge base population[END_REF][START_REF] Sterckx | Ghent University-IBCN participation in the TAC KBP 2015 cold start slot filling task[END_REF][START_REF] Adel | Cis at tac cold start 2015: Neural networks and coreference resolution for slot filling[END_REF][START_REF] Zhang | Stanford at TAC KBP 2016: Sealing Pipeline Leaks and Understanding Chinese[END_REF]. A distant supervision method uses an existing knowledge base to collect facts. A fact is a tuple which consists of two entities and a relation name. Any sentence containing the pair of entities is considered as an example of that particular relation. Thus distant supervision facilitates to generate a large number training examples for extracting relations in a supervised fashion. Distant supervision suffers from inappropriate alignment of a sentence to a fact in an existing knowledge base [START_REF] Riedel | Modeling relations and their mentions without labeled text[END_REF] and involving multiple relations between a pair of entities [START_REF] Hoffmann | Knowledge-based weak supervision for information extraction of overlapping relations[END_REF][START_REF] Surdeanu | Multi-instance multi-label learning for relation extraction[END_REF]. Therefore, distant supervision based relation extraction methods are usually trained on noisy data. As a consequence, they generate a large number of false relations which result in lower score in slot filling task.

In addition to the distant supervision, hand-coded patterns have been used by [START_REF] Angeli | Stanford's 2014 slot filling systems[END_REF], [START_REF] Nguyen | New york university 2014 knowledge base population systems[END_REF], [START_REF] Angeli | Bootstrapped self training for knowledge base population[END_REF] and [START_REF] Sterckx | Ghent University-IBCN participation in the TAC KBP 2015 cold start slot filling task[END_REF] for extracting the object of a relation in slot filling task. A rule based inference learning method creates new knowledge from known facts by applying some reasoning. For example, if a person, P lives in a city, C and C is a city of state S, it can be implied that P lives in S. [START_REF] Bentor | University of Texas at Austin KBP 2013 Slot Filling System: Bayesian Logic Programs for Textual Inference[END_REF], [START_REF] Nguyen | New york university 2014 knowledge base population systems[END_REF] [START_REF] Angeli | Bootstrapped self training for knowledge base population[END_REF]. Therefore, [START_REF] Angeli | Bootstrapped self training for knowledge base population[END_REF] proposed bootstrapped self training method for the relation extraction component in their slot filling system. In bootstrapped learning, a system is firstly trained on a small clean dataset and tested on a large noisy dataset. Then it is iteratively trained by the correctly predicted examples. Thus, it takes advantages of distant supervision and pattern based methods. [START_REF] Lin | OpenKN at TAC KBP 2014[END_REF] incorporated a conditional random field (CRF) model with patterns for extracting slot fillers. A multi-dimensional truth finding model (MTM) [START_REF] Yu | RPI-BLENDER TAC-KBP2013 Knowledge Base Population System[END_REF] model has been proposed for slot filling that computes credibilities of the fillers, sources and relation extraction systems which has been continuously achieving a competitive score. This model is extended by a temporality-based clustering mode (TBCM) and active learning [START_REF] Hong | Rpi blender tac-kbp2014 knowledge base population system[END_REF]) in 2014. Yu et al. (2016) proposed a graph based trigger driven slot typing method which closely explored the dependency tree structures and ranked the candidate trigger words by PageRank algorithm for slot filling. A couple of systems [START_REF] Adel | Cis at tac cold start 2015: Neural networks and coreference resolution for slot filling[END_REF][START_REF] Zhang | Stanford at TAC KBP 2016: Sealing Pipeline Leaks and Understanding Chinese[END_REF] employed neural networks for relation extraction module which obtain better scores compared to some others.

However, still all of the KBP slot filling systems suffer from poor F-score [START_REF] Surdeanu | Overview of the TAC2013 knowledge base population evaluation: English slot filling and temporal slot filling[END_REF][START_REF] Surdeanu | Overview of the english slot filling track at the tac2014 knowledge base population evaluation[END_REF]. The performances of some top ranked slot filling systems in recent years are shown in Table 2.3. In 2013 and 2014, the highest F-score was around 37% while it was between 26% and 27% in 2015 and 2016. Slot filling scores of the top ranked systems are decreasing over the years. It might be due to some special requirements added to the evaluation task each year, due to lack of annotated training data and due to the changes in evaluation corpus. All the top ranked slot filling systems fails to achieve a decent score even though by using effective relation extraction models of literature. All these scores indicate that extracting entity level relations for slot filling is still a challenging task in NLP research.

Relation Extraction

Relation extraction module is a very important component of a slot filling system. Relation extraction refers to finding semantic relationships among given arguments (or entities) and characterizing the relation types. A relation between two arguments is called a binary relation. In this section, only binary relation will be studied. A binary semantic relation can be trigger-dependent or trigger-independent. A trigger is a word which strongly represents the semantics of a particular relation. For instance,

Slot Filling System

Relation Extraction Method F-score [START_REF] Wiegand | Effective slot filling based on shallow distant supervision methods[END_REF] In unsupervised methods [START_REF] Rosenfeld | Ures: an unsupervised web relation extraction system[END_REF][START_REF] Banko | Open Information Extraction from the Web[END_REF]Rosenfeld and Feldman, 2007a;[START_REF] Fader | Identifying relations for open information extraction[END_REF], pairs of entities are collected based on their co-occurrences. Then, the pairs of entities are clustered by extracting features at the sentence level automatically. Each cluster represents a relation. Unsupervised methods do not require any prior knowledge about the relation types. Such methods are useful for open relations where the precise semantic type of a relation is not important.

However, in supervised relation extraction, a system learns expression of a relation and characterization of the relation type from an annotated dataset. Usually, Chapter 2. Literature Review the annotated dataset contains sentences of different relation types. Each sentence consists of at least one pair of entities and expresses a particular relation between them.

The expression of a binary relation follows some lexical and structural patterns between two arguments. Such patterns are repeated to mention that relationship between another pair of arguments. Subject-verb-object (SVO) is the simplest pattern of expressing relation. Such pattern was used for extracting events [START_REF] Yangarber | Automatic acquisition of domain knowledge for information extraction[END_REF] and to capture hypernym relations [START_REF] Snow | Learning syntactic patterns for automatic hypernym discovery[END_REF]. Regular expression patterns have been used by [START_REF] Hearst | Automatic acquisition of hyponyms from large text corpora[END_REF] for hyponym relation extraction. Mostly, the pattern based relation extraction methods use POS-tag patterns [START_REF] Fader | Identifying relations for open information extraction[END_REF] and lexico-syntactic patterns [START_REF] Alfonseca | Pattern learning for relation extraction with a hierarchical topic model[END_REF][START_REF] Pershina | Infusion of Labeled Data into Distant Supervision for Relation Extraction[END_REF]. However, in natural language, relations are expressed by many diverse patterns and it is not possible to capture all of them. As a consequence, pattern based methods suffer from low recall even though they achieve very high precision. In order to solve this problem feature based methods have been explored.

In feature based method, relation extraction is considered as relation classification task. Different features are computed on the annotated examples. A feature based method predicts an instance whether it expresses a specific type of relation by one of two possible ways: by computing similarity between the instance and annotated examples [START_REF] Zelenko | Kernel methods for relation extraction[END_REF][START_REF] Culotta | Dependency tree kernels for relation extraction[END_REF][START_REF] Bunescu | A shortest path dependency kernel for relation extraction[END_REF][START_REF] Bunescu | Using Encyclopedic Knowledge for Named entity Disambiguation[END_REF] or by training a classifier model with the feature vectors of annotated examples [START_REF] Kambhatla | Combining lexical, syntactic, and semantic features with maximum entropy models for extracting relations[END_REF][START_REF] Guodong | Exploring various knowledge in relation extraction[END_REF][START_REF] Jiang | A Systematic Exploration of the Feature Space for Relation Extraction[END_REF].

Supervised relation extraction methods require a large number of annotated examples to obtain a decent score. Manual annotations, as being expensive and time consuming, cannot provide sufficient data for training models of diverse relation types. Distant supervision [START_REF] Bunescu | Learning to extract relations from the web using minimal supervision[END_REF][START_REF] Mintz | Distant supervision for relation extraction without labeled data[END_REF] comes into play to solve this problem. However, distant supervision suffers from noisy training data that generates a lot of false relations.

Traditional supervised relation extraction or classification methods require a lot of feature engineering. In recent years, neural network based supervised relation classification methods [START_REF] Zeng | Relation Classification via Convolutional Deep Neural Network[END_REF][START_REF] Xu | Semantic Relation Classification via Convolutional Neural Networks with Simple Negative Sampling[END_REF][START_REF] Vu | Combining Recurrent and Convolutional Neural Networks for Relation Classification[END_REF][START_REF] Zheng | A neural network framework for relation extraction: Learning entity semantic and relation pattern[END_REF][START_REF] Dligach | Neural Temporal Relation Extraction[END_REF] have been popular in that they do not require any feature engineering. Such methods take positive and negative examples of relations as input and use word embeddings [START_REF] Mikolov | Linguistic regularities in continuous space word representations[END_REF][START_REF] Pennington | GloVe: Global Vectors for Word Representation[END_REF] to learn lexical features automatically. Neural network based methods learn also the structural representation of words in a sentence to express a relation.

Linguistic Features for Relation Characterization

Almost, all the feature based relation extraction methods extract different features based on the syntactic and semantic analysis. Basically, these analyses are performed at the sentence level. The syntactic analysis focuses on the grammatical representation of a sentence. On the other hand, semantic analysis emphasizes on understanding the meaning of a sentence.

Syntactic Analysis

Syntactic dependency expresses the grammatical relationship among the words in a sentence. Moreover, syntactic dependency path between two related words indicates the structure of expressing a relation.

Usually, a relation between two entities is expressed in a shorter context. Therefore, shortest dependency path has been proven effective for kernel based relation extraction [START_REF] Bunescu | A shortest path dependency kernel for relation extraction[END_REF][START_REF] Zhang | A composite kernel to extract relations between entities with both flat and structured features[END_REF]. Neural network based relation classification methods [START_REF] Cai | Bidirectional Recurrent Convolutional Neural Network for Relation Classification[END_REF][START_REF] Liu | A Dependency-Based Neural Network for Relation Classification[END_REF] used syntactic dependency labels for capturing features in the shortest path automatically.

Chapter 2. Literature Review However, [START_REF] Zhou | Tree kernel-based relation extraction with contextsensitive structured parse tree information[END_REF] argued that in many cases shortest path trees cannot capture enough information for extracting relations. They proposed a contextsensitive shortest path to include necessary information outside the shortest path. In order to capture useful context, [START_REF] Culotta | Dependency tree kernels for relation extraction[END_REF] proposed smallest common subtree and [START_REF] Chowdhury | A study on dependency tree kernels for automatic extraction of protein-protein interaction[END_REF] proposed minimal subtree for extracting relations.

Consecutive dependency labels in the shortest path between two related entities make a pattern of a relation. Such patterns could be useful for trigger-independent relation extraction. Several patterns have been studied for extracting relation from texts. [START_REF] Pershina | Infusion of Labeled Data into Distant Supervision for Relation Extraction[END_REF] extracted dependency patterns of different relations where maximum pattern length of 3 was found most effective. A SVO pattern has been used by [START_REF] Snow | Learning syntactic patterns for automatic hypernym discovery[END_REF] for extracting hypernym relations.

Expression of a relation often includes a verb between the subject and object. Parts-of-speech (POS) tags provide useful information to identify syntactic roles of the words in a sentence. Therefore, POS-tags have been widely used in pattern based [START_REF] Hearst | Automatic acquisition of hyponyms from large text corpora[END_REF][START_REF] Fader | Identifying relations for open information extraction[END_REF], kernel based [START_REF] Nguyen | Convolution kernels on constituent, dependency and sequential structures for relation extraction[END_REF] and feature based [START_REF] Mintz | Distant supervision for relation extraction without labeled data[END_REF][START_REF] Surdeanu | Multi-instance multi-label learning for relation extraction[END_REF] relation extraction. [START_REF] Mintz | Distant supervision for relation extraction without labeled data[END_REF] used windows of POS-tags between two arguments, before the first argument and after the second argument. Subgraphs of syntactic parse trees with POS-tags have been explored by [START_REF] Jiang | A Systematic Exploration of the Feature Space for Relation Extraction[END_REF] for extracting relation at the sentence level.

The syntactic analysis provides useful information for learning grammatical structures of relation expression. However, in most cases, characterizing the semantic type of a relation is not possible by such information.

Semantic Analysis

Semantic analysis facilitates understanding the meaning of a text. Since a relation is usually expressed in a sentence, semantic analysis is important to interpret what type of relation it mentions.

Words between and around the mentions hold useful information to characterize the relation type specially for trigger-dependent relations. Therefore, such lexical information has been widely used for learning relation types. [START_REF] Kambhatla | Combining lexical, syntactic, and semantic features with maximum entropy models for extracting relations[END_REF], [START_REF] Jiang | A Systematic Exploration of the Feature Space for Relation Extraction[END_REF] and [START_REF] Mintz | Distant supervision for relation extraction without labeled data[END_REF] used words between the arguments of a relation. Moreover, the first word before the first argument and the first word after the second argument have been taken into account in addition to the words between the arguments by [START_REF] Guodong | Exploring various knowledge in relation extraction[END_REF]. [START_REF] Mintz | Distant supervision for relation extraction without labeled data[END_REF] included windows of k-words before the first argument and after the second argument in their distant supervision based relation learning model. Such windows of words have been inherited in some other studies [START_REF] Riedel | Modeling relations and their mentions without labeled text[END_REF][START_REF] Riedel | Modeling relations and their mentions without labeled text[END_REF][START_REF] Hoffmann | Knowledge-based weak supervision for information extraction of overlapping relations[END_REF][START_REF] Surdeanu | Multi-instance multi-label learning for relation extraction[END_REF].

Traditional systems learn which words are useful for identifying the type of a relation. These systems cannot handle unseen and sparse words in the training data. However, neural network based relation classification methods [START_REF] Zeng | Relation Classification via Convolutional Deep Neural Network[END_REF][START_REF] Nguyen | Relation Extraction: Perspective from Convolutional Neural Networks[END_REF] take the sequence of words as input and perform semantic analysis based on word embeddings. Word embeddings facilitate characterizing the semantic type of a relation by computing semantic similarity between words.

Collective and Statistical Analysis for Relation Extraction

Linguistic analysis is important for extracting relation at the sentence level. Relationship between two entities also depends on their co-existence and common resources between them. Such information cannot be explored by linguistic analysis. In relation validation task, corpus level studies e.g. co-occurrences of two entities and their sharing resources can be taken into account which we call collective analysis.

Collection level information has been explored for improving the performance of relation extraction by learning the boundaries of relation arguments (Rosenfeld and Feldman, 2007b). [START_REF] Augenstein | Web Relation Extraction with Distant Supervision[END_REF] has taken into account global information about the object of a relation such as object occurrence, markup link with the object, title of the document containing the object etc. for web relation extraction.

The statistical analysis gets importance for extracting relation in a collective manner. [START_REF] Niu | DeepDive: Web-scale Knowledge-base Construction using Statistical Learning and Inference[END_REF] performed statistical inference on diverse data for learning relation. A probabilistic model of inference has also been explored by [START_REF] Fang | Searching patterns for relation extraction over the web: rediscovering the pattern-relation duality[END_REF]. Such model counts co-occurrences of the subject-object pairs, frequencies of the relational tuples and patterns and their probabilities. Co-occurrence context has also been quantified by measuring mutual information for extracting relation between entities in the web [START_REF] Xu | Mining temporal explicit and implicit semantic relations between entities using web search engines[END_REF]. Different features have been studied in relation extraction task where lexical features such as words between and around entity mentions and POS-tags, and syntactic feature such as dependency labels are used very commonly. Different patterns are also used for extracting relations. Patterns or dependency paths are generally made of syntactic dependency and lexical information. It is difficult to generalize the patterns and capture similarities among them because of syntactic and lexical variations together.

Conclusion

Relation Validation

Slot filling systems generate a large number of false candidate objects for a query relation with given subject. Performance of the slot filling systems can be improved by discarding the false candidates and it can be done by validating the claimed relations.

Relation validation is the task of selecting the correct object(s) of a relation among several candidates which can be generated by single or multiple systems. Basically, the objective is to discard wrong relation hypotheses by performing further investigation on the already extracted relations. Different relation validation methods have been studied in the literature which are described in the following sub-sections.

Ensemble Learning for Relation Validation

The output of a single learning system is affected by statistical, computational and representational problems that can be partly overcome by an ensemble learning [START_REF] Dietterich | Ensemble learning[END_REF]. Therefore, outputs of different relation extraction systems can be aggregated for further processing as an ensemble manner.

Ensemble Method

An ensemble method makes some decisions or generates output by performing some analysis on the outcomes of multiple systems. Ensemble methods have been well studied in machine learning. Bagging [START_REF] Breiman | Bagging predictors[END_REF], stacking [START_REF] Wolpert | Stacked generalization[END_REF], boosting [START_REF] Freund | A desicion-theoretic generalization of on-line learning and an application to boosting[END_REF] etc. are widely used ensemble machine learning algorithms where bagging and boosting basically count majority votes of the outcomes by different learning algorithms trained on different subsets (bootstrapped samples) of the training data. However, in stacking outputs of the first round bootstraptrained algorithms are fed to train an algorithm at the second round to learn the final outcome.

Voting is another kind of ensemble method which takes into account agreements among the outputs of different systems. Such methods have been studied in many decision making tasks [START_REF] Polikar | Ensemble based systems in decision making[END_REF][START_REF] Boroushaki | Using the fuzzy majority approach for GIS-based multicriteria group decision-making[END_REF][START_REF] Morais | Group decision making on water resources based on analysis of individual rankings[END_REF][START_REF] Cao | Voting based extreme learning machine[END_REF] Ensemble methods have been successfully used in many information extraction tasks. [START_REF] Yang | A review of ensemble methods in bioinformatics[END_REF] explored using ensemble methods to solve various bioinformatics problems such as identifying the interaction between genes, predicting regulatory elements from DNA and protein sequences etc and for identifying effective features. In order to recognize spoken emotions, [START_REF] Morrison | Ensemble methods for spoken emotion recognition in call-centres[END_REF] employed both stacking and voting based ensemble methods. Moreover, Jean-Louis, Besançon, and Ferret (2011) performed majority voting on the outputs of three different methods for template filling task. Their voting method obtained better result compared to any individual method.

Slot Filler Validation

In the series of KBP workshop, every year TAC operates several tracks focusing on different problems. Slot filler validation (SFV)4 is one of the tracks which emphasizes on validating relations for improving slot filling scores. Basically, a SFV system examines whether a response of a slot filling system holds any evidence to justify a claimed relation in the response. Thus SFV implies the task of relation validation.

In slot filling task, a system generates outputs regarding some given queries. When multiple systems respond to the same set of queries, the system outputs can be analyzed to select the correct responses by validating them in an ensemble fashion. [START_REF] Viswanathan | Stacked Ensembles of Information Extractors for Knowledge-Base Population[END_REF] used stacking classifier to improve the KBP slot filling performance. They trained the classifier by the offsets and confidence scores of the responses of different slot filling systems. A comparative study of different models for slot filling was done by [START_REF] Adel | Comparing Convolutional Neural Networks to Traditional Models for Slot Filling[END_REF] which found a combination of state-of-the-art and neural network models achieves a higher score than any single model. Therefore, outcomes of different slot filling systems have been taken into account by [START_REF] Wang | JHUAPL TAC-KBP2013 Slot Filler Validation System[END_REF] and [START_REF] Sammons | Overview of UI-CCG systems for event argument extraction, entity discovery and linking, and slot filler validation[END_REF] documents and filler values corresponding to a slot filling query have been taken into account by [START_REF] Yu | The Wisdom of Minority: Unsupervised Slot Filling Validation based on Multi-dimensional Truth-Finding[END_REF]. They employed a multi-dimensional truth finding model to compute the credibility of a system, document and filler value. In their method, some linguistic indications also have been used such as filler type and inspection of trigger words and dependency path length in the responded relation justifying text etc.

A bipartite graph-based consensus maximization (BGCM) method has been proposed by [START_REF] Rodriguez | University of Florida DSR lab system for KBP slot filler validation 2015[END_REF] that combines the outputs of supervised stacked ensemble methods and slot filling runs. This method outperforms all other ensemble methods and the best slot filling run on 2015 KBP slot filling dataset. This method has been extended in [START_REF] Rodrıguez | University of Florida 2016 Slot Filler Validation system[END_REF] where consensus maximization technique is employed over multiple knowledge bases. This two SFV methods did not use any linguistic information but achieved better score compared to the best SF systems.

The performances of some top ranked SFV ensemble systems are shown in Table 2.5. The highest F-score of 61.72 was achieved on KBP-2013 dataset. However, the best SFV F-scores on KBP-2014, KBP-2015 and KBP-2016 datasets were 48.00, 34.83 and 32.42 accordingly. On the other hand, the best F-scores of different SF systems on the same datasets (KBP-2013 to KBP-2016) were 37.28, 36.72, 28.75 and 27.03 accordingly. Although SFV systems are improving the scores over the SF systems, the scores of SFV systems are also decreasing over the years which indicates that SFV is also a very challenging task.

Graph based Methods for Relation Validation

Mentions of entities in a collection of texts can be represented in a graph according to their co-existences in texts and sharing resources between them. Such graph facilitates to explore how the related entities are associated and what common information they share.

Candidate Ranking Model

Several studies explored graph based ranking model to extract keywords and keyphrases for document summarization task [START_REF] Mihalcea | TextRank: Bringing Order into Text[END_REF][START_REF] Litvak | Graph-based keyword extraction for singledocument summarization[END_REF][START_REF] Bougouin | Topicrank: Graphbased topic ranking for keyphrase extraction[END_REF]. These methods basically represented texts in a graph and ranked words and phrases by HITS [START_REF] Kleinberg | Authoritative sources in a hyperlinked environment[END_REF] and PageRank [START_REF] Brin | The anatomy of a large-scale hypertextual Web search engine* 1[END_REF] algorithms.

Ranking graph nodes also plays an important role in entity linking task [START_REF] Shen | Entity linking with a knowledge base: Issues, techniques, and solutions[END_REF]. [START_REF] Hachey | Graph-based named entity linking with wikipedia[END_REF] ranked candidate entities by measuring degree centrality and PageRank scores in a graph constructed from Wikipedia articles. [START_REF] Rao | Entity linking: Finding extracted entities in a knowledge base[END_REF] and [START_REF] Alhelbawy | Graph Ranking for Collective Named Entity Disambiguation[END_REF] took into account popularity of the entity nodes for entity linking task. They ranked the candidates in terms of popularity by using PageRank.

Graph based ranking method has been proven effective when there exist several object candidates for a relation, and the objective is to re-rank the candidates. [START_REF] Jain | Factrank: Random walks on a web of facts[END_REF] and [START_REF] Jean-Louis | Text Segmentation and Graph-based Method for Template Filling in Information Extraction[END_REF] re-ranked the filler values by using PageRank algorithm. Singh-Blom et al. ( 2013) employed Katz [START_REF] Katz | A new status index derived from sociometric analysis[END_REF] measure on a graph for predicting and validating gene-disease relation.

Measurements on a Graph

A graph represents different objects as nodes and a relationship between two nodes can be expressed by a link between them. Such representation facilitates performing different measurements.

Identifying influential nodes in a graph is a similar task to ranking the nodes. Eigenvector centrality [START_REF] Bonacich | Eigenvector-like measures of centrality for asymmetric relations[END_REF] measures the influence of a node in a network. It basically hypothesizes that a node will be even more influential if it is connected to other influential nodes. The concept of eigenvector centrality has been used to rank sentences for text summarization task [START_REF] Erkan | Lexrank: Graph-based lexical centrality as salience in text summarization[END_REF]. [START_REF] Han | Collective entity linking in web text: a graph-based method[END_REF] measured evidence propagation based on semantically related neighbor entities for entity linking task in a collective manner. Such concept of neighbor can be extended to community graphs of entities in the same sentence. These community graphs can be analyzed for characterizing a relation between two entities. [START_REF] Yang | Community-affiliation graph model for overlapping network community detection[END_REF] argued that the density of two overlapping communities would be higher than the density of two non-overlapping communities. Therefore, it could be applied to the communities of two entities in a true relationship.

Chapter 2. Literature Review Information theoretic measurements have been explored in complex networks for knowledge discovery [START_REF] Holzinger | On graph entropy measures for knowledge discovery from publication network data[END_REF] and for detecting community structures [START_REF] Rosvall | An information-theoretic framework for resolving community structure in complex networks[END_REF]. Rosvall and Bergstrom maximized the mutual information between a network and a descriptor to detect a community structure. Thus relatedness between two entities can be quantified by measuring mutual information between their communities.

Summary

Relation validation task refers to justifying a claimed relation. It becomes important for discarding the wrong fillers in KBP slot filling task. In SFV task, slot filling scores have been improved significantly by validating relations. Several methods of relation validation have been studied in the literature specially for KBP task such as ensemble method, constraint optimization, consensus maximization, multi-dimensional truth finding method etc. The linguistic indication such as the existence of trigger word has also been inspected for validating relations. Moreover, graph based methods such as candidate ranking and centrality measurement have been studied for relation validation task. When there exist several candidate objects of a relation, PageRank has been used for selecting the best object. Katz measurement on a graph has been explored for validating gene-disease relations. These graph based studies indicate that a graph holds effective evidence of justifying relation between two entities. Relation validation comes into play for discarding false relations. The objective of a relation validation system is to remove incorrect candidates by keeping correct ones so that the overall score can be improved in KBP task. An ensemble relation validation method takes outcomes of different slot filling systems as input and applies some heuristic model to generate a better output. Such methods have shown performance improvement over individual slot filling systems for KBP task. Existing relation validation methods followed voting [START_REF] Sammons | Overview of UI-CCG systems for event argument extraction, entity discovery and linking, and slot filler validation[END_REF], multidimensional truth finding model [START_REF] Yu | The Wisdom of Minority: Unsupervised Slot Filling Validation based on Multi-dimensional Truth-Finding[END_REF], constraint optimization [START_REF] Wang | JHUAPL TAC-KBP2013 Slot Filler Validation System[END_REF] and consensus maximization [START_REF] Rodriguez | University of Florida DSR lab system for KBP slot filler validation 2015[END_REF] techniques. Moreover, ranking methods [START_REF] Jain | Factrank: Random walks on a web of facts[END_REF][START_REF] Jean-Louis | Text Segmentation and Graph-based Method for Template Filling in Information Extraction[END_REF] have been explored for relation validation task where object candidates of a relation are re-ranked by a graph based ranking algorithm.

Conclusion

Linguistic analysis is also important for validating a relation which is claimed in a sentence. Syntactic and semantic characteristics of relation expression can be inherited from linguistic analysis of relation extraction task. [START_REF] Yu | The Wisdom of Minority: Unsupervised Slot Filling Validation based on Multi-dimensional Truth-Finding[END_REF] inspected linguistic evidence such as the existence of trigger words in the syntactic dependency path for validating relations.

However, few works have explored yet collective analysis for relation extraction task. The collective analysis could be effective for validating relations when the information in a corpus is represented in a graph structure. For example, documents, sentences and entity mentions in a corpus could be denoted as graph nodes and relationship among them could be indicated by edges. A graph structure facilitates to examine the association between related entities based on community analysis and centrality measurements. Moreover, node ranking and information theoretic measurements could be possible on a graph.

In order to validate a claimed relation between two entities, we come with the following propositions:

• We inherit different linguistic indications of expressing and characterizing relation at the sentence level from the literature of relation extraction task. We propose to generalize the dependency patterns of relation expression by computing edit distance. We also propose to employ word embeddings for detecting unknown trigger words of a relation by computing similarity between two word vectors.

• We adopt voting and candidate ranking techniques from the literature of relation validation.

• We compute several new features on the graph of entities based on community analysis, centrality measurement and information theoretic measurement.

We consider relation validation as a binary classification task to decide where the candidate object in a claimed relation is correct or wrong. We adopt two models: supervised and unsupervised regarding this task. As a supervised method, we train a binary classifier with several features computed on the instances of a labeled dataset. In contrast, we employ PageRank algorithm on a graph for raking the candidate objects of a relation to choose the correct ones in an unsupervised fashion.

G

Raph based models for knowledge representation has been popular for the last couple of years. A graph facilitates to represent various objects as nodes and links among the nodes describe how the different objects are related among them. Graph databases are used to store and represent the information about the objects by maintaining the graph structures. Graph based methods have been proven effective for solving a variety of problems such as text summarization [START_REF] Erkan | Lexrank: Graph-based lexical centrality as salience in text summarization[END_REF], community detection [START_REF] Fortunato | Community detection in graphs[END_REF], social network analysis [START_REF] Girvan | Community structure in social and biological networks[END_REF], entity linking [START_REF] Guo | A Graph-based Method for Entity Linking[END_REF] etc.

The mentions of different entities and their co-occurrences in texts can be depicted in a graph. The information and resources which are common between two entities can be observed in such presentation. Thus it can help to analyze the relationship between a pair of entities. Therefore, we explore graph of entities to find out some clues of holding true relationship between a pair of entities by analyzing their communities. This chapter focuses on the theoretical background and construction of a graph. Furthermore, computation of several features based on graph analysis for validating a claimed relation hypothesis between two entities.

Graph Definition

A graph is a structure to represent objects and relationship among them. Formally a graph is defined by a set of vertices and edges. Objects are represented by the vertices (nodes) and edges (links) describe the relationship among the objects. A graph can be directed or undirected where the links of a directed graph indicate the directions of the relations between the pairs of nodes. In contrast, a link in an undirected graph just refers to the existence of a relationship between two nodes. It does not emphasize on the direction of the relation. A graph is called connected when a node is reachable from all other nodes.

An example of a connected undirected graph is shown in Fig. 3.1 which consists of 6 nodes V = {v 1 , v 2 , ..., v 6 } and 9 links E = {e 1 , e 2 , ..., e 9 }. The link e 1 between nodes v 1 and v 2 indicates that these two nodes are in a relationship. This graph constraints that there can be at most one link between a pair of nodes. The properties of the nodes and relationships (e.g. node types and weights of the relations) can be described in the nodes and links accordingly. This graph can be represented as a two dimensional matrix as shown in Eq. 3.1. Here the rows and columns refer to the indices of the nodes and a cell of the index pair (i, j) of G indicates the relationship between the nodes v i and v j . Moreover, an adjacency matrix A (Eq. 3.2) of the graph G represents the connectivity information among the nodes where A(i, j) = 1 means that the nodes v i and v j are connected, and A(i, j) = 0 otherwise. Adjacency matrix can also be constructed by the number of links of each node, weights of the links and so on. Such representation facilitates performing mathematical operations on the graph.

v 1 v 2 v 3 v 4 v 5
G i,j =              v 1 v 2 v 3 v 4 v 5 v 6 v 1 -e 1 -e 3 e 5 - v 2 e 1 -e 2 --- v 3 -e 2 -e 4 -e 8
v 4 e 3e 4e 6 e 7 v 5 e 5 -e 6e 9 v 6 -e 8 e 7 e 9 -

             (3.1) A i,j =              v 1 v 2 v 3 v 4 v 5 v 6 v 1 0 1 0 1 1 0 v 2 1 0 1 0 0 0 v 3 0 1 0 1 0 1 v 4 1 0 1 0 1 1 v 5 1 0 0 1 0 1 v 6 0 0 1 1 1 0              (3.2) 3.2.

Entity Graph and Graph Database

We use the graph structure for representing different types of entities and relationships among them. The node of a graph describes an entity with its properties and a link between two entities refers to the relation and properties of the relationship between them. Fig. 3.2 shows two entity nodes of types person and location and their relationship in term of co-occurrence in text. For example, the entities Barack Obama and USA are found in the same sentence (IN_SAME_SENTENCE) of a document where document id and sentence id are 2 and 3 accordingly. The information about the entities and their relationships extracted from a collection of texts are stored in a graph database that visualizes the information in a graph structure.

Neo4j1 is a schemaless graph database which facilitates storing information in the form of a node, edge and attribute, visualizing in a graph structure and performing different queries and operations on the graph based on different criteria. Cypher Query Language is used to perform queries on this database. A sample Neo4j graph is shown in Fig. 3.3 which consists of three types of entity nodes (person, organization and location) and a document type node. It also contains two types of relational links IN_SAME_SENTENCE and FOUND_IN where IN_SAME_SENTENCE connects two entities that are found in the same sentence and FOUND_IN connects a document node to an entity node.

Graph Construction

The graph of entities or community graph (as shown in Fig. 1.1 on Page 9) is constructed from a graph representing the association among documents, sentences and entity-mentions in a collection of texts (lower part of Fig. 3.5) called association graph. The association graph represents documents, sentences, mentions and entities as nodes and the edges between these nodes represent relationships between these elements. The association graph is generated by applying systems of named entity recognition and sentence splitting. Named entity recognition (NER) is done by Luxid2 , which is able to decompose the entities into components, such as first name and title, and by the Stanford CoreNLP (Manning et al., 2014b). When the two systems disagree, we choose the annotation produced by Luxid that gets better precision. This entity-graph basically contains three types of named entities which are person, geopolitical location and organization. Geopolitical locations are classified into three subtypes: country, region (state/province) and city. Dates are also included in the graph as nodes after normalizing the date string. For example, 7th March 2017 and August 2018 are normalized as 2017-03-07 and 2018-08-XX accordingly.

We assume that two entities mentioned in the same sentence share the common meaning since a sentence as being the basic unit of a language states a complete sense. We hypothesize that the co-occurrences of pairs of entity mentions could provide some evidence of justifying relationships. Therefore, we aim at connecting two entities which co-exist in the same sentence by IN_SAME_SENTENCE relational link.

Multiple mentions of the same entity found in the same document are connected to the same entity node in the association graph, based on the textual similarity of the mentions and their possible components, which corresponds to the first step of entity creation on local criteria. This operation is performed by Luxid. However, an entity can be mentioned in different documents, in the same or different forms (e.g. Barack Obama, President Barack Obama, President Obama etc.) which create redundant nodes in the association graph.

Then, the entities are clustered based on the similarities in their names. We assume that different mentions of an entity can be grouped together by matching their mentioning strings or components of the mentions. However, if two different entities have similar mention, they can be distinguished by their neighbor entities. The task of clustering person type entities is done in two sub-steps. Firstly, we inspect whether the mention of an entity includes three basic components such as title, first name and last name. Then, a pair of entities (i.e. E 1 and E 2 ) are compared in terms of their components. We define a set of constraints (Constraints 3.1) to decide if a pair of entities belongs to the same cluster. When two entities satisfy any one of the constraints (based on conditional OR operation) we keep them in the same cluster. We select a seed entity of a cluster which is mentioned with a comparatively higher However, an organization type entity cannot be splitted into the components like a person type entity. Therefore, we compute cosine similarity between the character tri-grams of a pair of entities for clustering organization type entities. Two entities are considered to belong to the same cluster if the similarity score satisfies a threshold of 0.5. Unlike person and organization type entities, a location type entity maintains almost the same form in its different mentions. Therefore, we do not perform any clustering of the location type entities.

In order to decide if two entities with a similar name in the same cluster truly refer to the same person or organization, we compute the similarity of their neighboring entities by Eq. 3.10 on Page 45. We empirically define two different thresholds for the person and organization type entities which are 0.1 and 0.5 accordingly. If the similarity score satisfies the predefined threshold we merge two entity nodes into a single node.

However, an entity may belong to two or more clusters according to our clustering method. In such case, we select the cluster of that particular entity based on the highest similarity score between the communities of that entity and other entities in the different clusters. When several entities in a cluster refer to the identical person or organization, we merge the corresponding nodes into a single node and choose the name of seed entity for the merged node in the community graph as shown in the upper part of the association graph illustrated in Fig. 3.5. In the association graph, the links between entities and documents are always maintained via their mention nodes. It is thus possible to know the number of mentions of each entity and the number of coexistences of a pair of entities.

We do not either use any existing entity graph such as DBpedia or construct the graph from Wikipedia articles because this database or articles mostly contain information about popular entities. The entities and relations we study in this thesis may not exist there. Therefore, the association graph is built from a given corpus where entities and relations have to be extracted. We store the graph in a Neo4j database which makes it possible to extract the subgraphs linked to an entity by queries as illustrated in Section 3.2.

Measurements on Graph

Several measurements on a graph have been explored for solving different problems like entity linking by measuring the degree of entity nodes [START_REF] Guo | A Graph-based Method for Entity Linking[END_REF], knowledge discovery by measuring entropy in a publication network [START_REF] Holzinger | On graph entropy measures for knowledge discovery from publication network data[END_REF] etc. Centralities of the graph nodes have been computed for finding the most important and influential node and clustering the nodes into several groups. In order to quantify the degree of connectivity among the nodes of a cluster, density is measured. Moreover, the similarity between two clusters can be calculated based on the common members.

Node Centrality

Centrality measurement in a graph or network characterizes the nodes of that particular network. The characterization of the nodes differs based on different measurements of centrality. Here we focus on three centrality measurements related to our task.

Degree Centrality

Degree centrality [START_REF] Freeman | A set of measures of centrality based on betweenness[END_REF] is used to find the highly connected nodes in a network by counting the number of direct neighbors of each node. The popular nodes in a network are highly connected and more information flow through these nodes. Thus degree centrality facilitates to detect important nodes. The degree centrality

C D (v) of a node in a network G:=(V, E) with a set of nodes V = {v 1 , v 1 , ..., v n } and a set of links E = {e 1 , e 1 , ..., e m } is measured by Eq. 3.3. C D (v) = v :v =v e(v, v ) = degree of node v (3.3)
where, e(v, v ) refers to a direct link between v and a neighbor node v .

Betweenness Centrality

Betweenness centrality [START_REF] Freeman | A set of measures of centrality based on betweenness[END_REF] is measured based on the shortest paths between each pair of nodes. In a connected graph, every pair of nodes has at least one shortest path. Betweenness centrality of a node counts the number of shortest paths passing through that particular node. It characterizes a node to become a bridge between two other nodes. Higher betweenness centrality of a node refers to be the bridge among a large number of nodes. The betweenness centrality C B (v) of a node v in a network is computed by the Eq. 3.4.

C B (v) = s =v =t σ st (v) σ st (3.4)
where, σ st refers to the total number of shortest path between nodes s and t, while σ st (v) is the number of those shortest path passing through node v. Edge betweenness [START_REF] Girvan | Community structure in social and biological networks[END_REF] has been studied for community detection in a network which implies the similar concept of betweenness centrality. When a network contains some interconnected communities or groups and these are loosely connected by some edges, the shortest paths among the communities pass through at least one of the loosely connected edges. Thus the edges connecting different communities get high edge betweenness score and the communities can be separated by removing these edges.

Eigenvector Centrality

Eigenvector centrality [START_REF] Bonacich | Eigenvector-like measures of centrality for asymmetric relations[END_REF] measures the influence of a node in a graph. A node will be even more influential if it is connected to other influential nodes. Unlike degree centrality, a node having high eigenvector centrality does not mean the node is highly connected. Moreover, two nodes having the same degree centrality may have different eigenvector centrality. Degree centrality does not account the neighbor nodes at the further levels apart from the first level to compute the importance of a node. However, eigenvector centrality accounts the contribution of the neighbor nodes recursively to compute the centrality of a node that facilitates to find out the nodes having the similar influence in a network.

C E (v) = 1 λ t G a v,t C E (t) (3.5)
where, λ = 0 is a constant and the equation can be expressed in the matrix form: λC E = AC E . Suppose, a network G:=(V,E) and A = (a v,t ) is the adjacency matrix of the network G where a v,t = 1 if node v is linked to node t, and a v,t = 0 otherwise. The eigenvector centrality C E (v) score of a node v can be computed by Eq. 3.5.

Eigenvector centrality can be compared to PageRank [START_REF] Brin | The anatomy of a large-scale hypertextual Web search engine* 1[END_REF] centrality. PageRank vector is also an eigenvector but a damping factor is added in the measurement of PageRank centrality to restrict extending community to a certain level by continuously reducing the weight at each level.

Mutual Information

Information flows in a network node to node through the links. The flow of information differs among different nodes in a network based on their connectivity. Shannon entropy [START_REF] Shannon | The Bell System Technical Journal[END_REF] measures the rate of information flow of a random variable in a transmission medium. It basically counts the number of bits to encode a message or information. Thus the flow of information in a network can be quantified by measuring the entropy of the network based on the degree of connectivity of each node. Suppose, G := (V, E) is a network with vertices V = {v 1 , v 2 , ..., v n } then the Chapter 3. Entity Graph and Measurements for Relation Validation entropy of the network G can be measured by Eq. 3.6.

H(G) = - n i=1 p(v i ) log 2 (p(v i )) (3.6)
where, p(v) = degree of node v total number of links (|E|) in G Mutual information quantifies the amount of information gained by a random variable compared to another one. The mutual information between two random variables X and Y can be measured by Eq. 3.7.

M I(X, Y ) = H(X) + H(Y ) -H(X, Y ) (3.7)
If a network consists of two communities, it is possible to quantify the mutual information between them based on the degree of connectivity of the nodes by using Eq. 3.6 and by modifying Eq. 3.7 a little. Suppose, a network G is composed of two community networks G x and G y . We compute the mutual information between G x and G y by using Eq. 3.8.

M I(G x , G y ) = H(G x ) + H(G y ) -H(G x , G y ) (3.8)
where, H(G x , G y ) = H(G)

Network Density

Network density measures the degree of connectivity in a network. Mathematically it calculates the ratio of the number of existing links to the number of potential links in a network. The density of a network of n nodes and |E| existing links can be calculated by Eq. 3.9 where L refers to the highest number of possible links.

ρ = total number of links (|E|) number of potential links (L ) (3.9)
where, L = n * (n -1) 2

According to this definition the density of the network shown in Fig. 3.1 is 0.60 where the numbers of nodes, existing links and potential links are 6, 9 and 15 accordingly. However, the density of the network presented in Fig. 3.4 is 0.25. These two scores of network density help to realize that the network of Fig. 3.1 on Page 36 is highly interconnected compared to the network of Fig. 3.4 on Page 39. If some nodes in a network are highly interconnected among them these particular nodes can be considered as the members of the same community.

Network Similarity

Network similarity measures how much similar two networks are. Typically it is calculated based on the cosine similarity measurement. The similarity between two networks can be easily measured on the basis of the common nodes shared by both networks. Suppose, V x = {v x1 , v x1 , ..., v xm } and V y = {v y1 , v y1 , ..., v yn } are the node sets of two different networks accordingly. The similarity between these networks can be measured by Eq. 3.10.

network similarity = |V x ∩ V y | |V x ||V y | (3.10)
Network similarity gives a realization similar to the network density. If two networks share a large number of members, the similarity score would be very high. Thus two communities in a network having high similarity score to each other can be considered as a single community by merging them.

Relation validation by Graph Analysis

A relation can be defined between a pair of entities by a tuple as shown in Def. 3.1 where R, E q and E c refer to the relation name, subject entity and object entity accordingly. For the task of relation validation E q and E c become a subject and a candidate object accordingly for the relation (R, E q , ?) and our objective is to predict whether the candidate object (E c ) is correct or not for the claimed relation.

Def 3.1: A relation between two entities (R, E q , E c ) (spouse, Barack Obama, Michelle Obama)

We propose to incorporate graph based analysis (as presented in Section 3.4) for validating a claimed relation between two entities in addition to the linguistic analysis. Such studies on graph analysis were not done before for relation validation task. Basically, we analyze the communities of the subject and object entities of a relation hypothesis to get some clues for validating it. Here, we define a community of an entity by the neighbor entities which are mentioned in the same sentences where that particular entity is mentioned.

A network as shown in Fig. 3.6 constructed based on the co-occurrences of the entities in texts does not hold any semantic evidence of holding a specific type of relationship between two entities but gives some realizations how they are associated to each other and with other entities which are common between the neighbors of this Chapter 3. Entity Graph and Measurements for Relation Validation two particular entities. We compute several features on the networks of two entities in a relationship to realize their relatedness.

E q P B Z G c G q G' c FIGURE 3.6: Community graph for realizing different measurements
Suppose, the communities of a subject entity (E q ) and a candidate object (E c ) are extracted from the constructed network which are G q and G c accordingly. A community can be expanded up to several levels from the entity node under observation. These two communities are analyzed to predict whether R(E q , E c ) is true.

Network similarity: we compute the similarity score (Eq. 3.10) between G q and G c and expect higher similarity score if G c is the community of the correct candidate than the score between G q and the community of an incorrect candidate, G c . In Fig. 3.6, the similarity score between G q and G c is 0.46 while the score between G q and G c is 0.15.

Network density: we merge the community of G q to G c and calculate the density (Eq 3.9) of the merged network. We hypothesize that the density would be higher for a correct candidate than the density of the merged network of G q and G c . The density scores of the merged networks G q + G c and G q + G c are 0.20 and 0.17 accordingly.

Eigenvector centrality: we also compute eigenvector centrality for each node after merging the communities of G q and G c . We expect similar centrality score for the nodes of E q and E c if E c is the correct object because E q and E c should be highly influential to each other. Therefore, we calculate the absolute difference of the eigenvector centrality scores of E q and E c . We hypothesize that

|C E (E q ) - C E (E c )| < |C E (E q )-C E (E c )
| where E c refers to an incorrect candidate. In Fig. 3.6, eigenvector centrality is measured for each node of the full network. The normalized scores of nodes E q , E c and E c are 1.0, 0.78 and 0.74 accordingly where the scores of

|C E (E q ) -C E (E c )| and |C E (E q ) -C E (E c
)| are 0.22 and 0.26 respectively.

Conclusion 47

Mutual information: furthermore, we compute mutual information between G q and G c and expect higher mutual information if G c is the correct candidate than the mutual information measured between G q and G c . The community of an entity is constructed by the neighbors of level one for calculating the network similarity and network density scores. However, the eigenvector centrality and mutual information are computed by expanding the community up to third level to include more information about the entities.

As early mentioned, we consider relation validation as a binary classification task. A feature vector is generated including the four graph based features: network similarity, network density, mutual information and eigenvector centrality.

Conclusion

We expect that the features computed on the network as we discussed so far are able to characterize the existence of a strong relationship between two entities. However they are not able to characterize the semantic type of a relation. Characterization of the type of a semantic relation mostly depends on the linguistic information. Therefore, we incorporate linguistic features to the graph based features which are discussed in this chapter in order to fully represent a relation. In the next chapter, we will focus on the linguistic analysis of expressing relations. The contribution of the proposed features in addition to the linguistic features of validating relations will be discussed in Chapter 6.

T He expression of a relationship between two entities in text follows some linguistic properties. Studies of relation extraction from texts basically focus on syntactic and lexical semantic analysis [START_REF] Kambhatla | Combining lexical, syntactic, and semantic features with maximum entropy models for extracting relations[END_REF][START_REF] Guodong | Exploring various knowledge in relation extraction[END_REF][START_REF] Mintz | Distant supervision for relation extraction without labeled data[END_REF][START_REF] Surdeanu | Multi-instance multi-label learning for relation extraction[END_REF]. Syntactic analysis inspects the grammatical structure of a relation when it is expressed between a pair of entities at the sentence level. However, Semantic type of a relation is characterized by the words between and/or around the entity mentions.

Our objective is to validate already extracted relations. We assume that the tasks of relation extraction and relation validation are the opposite side of the same coin. Similar to the relation extraction, validating a relation requires natural language understanding of pieces of text. Therefore, linguistic analysis comes into play to justify whether a claimed relation between a pair of entities in text is true or false.

In this chapter, we focus on dependency patterns of relations based on syntactic analysis, identifying semantic type of a relation based on trigger words and wordembeddings, and finally make a fusion to take advantages of both syntactic and semantic analysis.

Linguistically Motivated Classification of Relation

Relations are expressed between different types of entities such as person, organization, location etc. Semantic type of a relation depends on the types of the pair or entities and words between and/or around their mentions. For example, a spouse relationship always occurs between two persons while a residence relationship is mentioned between a person and a location. However, the types of the entities do not hold sufficient evidence to explicitly characterize the relations. Because different pairs of entities with similar types may express different relations. For example, the types of the entity pairs (person-person) in both spouse and children relationships (in Ex. 4.1) are the same. Therefore, words around the mentions are analyzed to collect more evidence for identifying the specific type of a relation. The words married and daughter characterize two different relations spouse and children accordingly. children (Julie, Jesi): Julie's daughter Jesi likes to play piano.

residence (John, France): John was in France for three years.

residence (John, France): John is currently living in France.

A content word which is explicitly able to characterize the semantics of a relation between two entities is called a trigger word. For example, married, husband, wife are the trigger words for spouse relation. Semantic relations can be classified into two types based on triggers words: trigger-dependent and trigger-independent [START_REF] Yu | Unsupervised Person Slot Filling based on Graph Mining[END_REF]. A trigger-dependent relation requires at least one trigger word to express the relation between a pair of entities. Spouse, children, bornIn etc. are examples of trigger-dependent relations. In contrast, a trigger-independent relation can be expressed with or without a trigger word. For example, residence, subsidiaries etc are trigger-independent relations. The first sentence in Ex. 4.1 states spouse relationship between John and Julie where the word married explicitly indicates the semantic type of the relationship. The third one expresses residence relationship between John and France where no word explicitly holds the semantic of residence relation. However, the residence relationship in the third sentence is understandable by humans based on the grammatical orientation of the words. In contrast, the word living in the last sentence explicitly refers to the residence relation. Thus validating a relation either trigger-dependent or trigger-independent requires semantic and syntactic analysis. Sometimes validating a trigger-independent relation depends only on the syntactic analysis when it is expressed in a sentence having no trigger word.

We studied annotated sentences of different relations to classify the relations into trigger-dependent and trigger-independent. We collected the words between the subject and object pairs of positive examples of each kind of relation and ranked them by counting their frequencies. We observed that for some relations (i.e. spouse, parents, etc) at least one of the top five words is discriminating (i.e. married) for characterizing the semantics of the relation. We call these relations trigger-dependent relations. In contrast, we notice that for other relations (i.e. city_of_residence, subsidiary etc) top five words are either prepositions or other words that are not able to distinguish any semantic relation. Such relations are called trigger-independent relations. A trigger-independent relation can also be expressed by using a trigger word but it is not mandatory. Table 4.1 shows some trigger-dependent and trigger-independent relation names which have been grouped based on the trigger word analysis. Section 4.3 describes in detail how we collect the trigger words and identify unknown triggers of a relation.

Trigger-dependent

Trigger

Syntactic Modeling

Syntactic analysis facilitates to understand the meaning of a sentence by dividing the words in a sentence into different parts and by characterizing their grammatical relations. The syntactic analysis covers a set of grammatical annotations at the sentence level such as parts-of-speech tagging (POS-tagging), segmentation, dependency parsing etc [START_REF] Jurafsky | Speech and Language Processing. Always learning[END_REF].

POS tagging is a kind of annotation of the words in a sentence based on the parts of speech such as noun, verb, adjective etc. Such annotation indicates the role of a word and formal relationship between the adjacent or related words in a sentence. For example, John and likes in the sentence of Ex. 4.2 refer to a proper noun and a verb accordingly in terms of parts-of-speech. The boundaries of a compound word (two or more consecutive words together expresses a single meaning) and a clause (consists of a subject and a predicate) in a sentence are identified by segmentation. For instance, coffee shop in Ex. 4.2 refers to a place of selling coffee. Moreover, the sentence contains two clauses (purple colored) separated by where which individually expresses a complete sense.

In information extraction and relation extraction related tasks, POS tagging and segmentation play important roles to realize the inter-word relationships in a sentence [START_REF] Fader | Identifying relations for open information extraction[END_REF][START_REF] Li | Extracting Relation Descriptors with Conditional Random Fields[END_REF]. Syntactic dependency parsing gives a better explanation of the relationships among words based on the directed grammatical relations as found in some relation extraction tasks [START_REF] Mintz | Distant supervision for relation extraction without labeled data[END_REF].

Syntactic Dependency Analysis

Syntactic dependency refers to the directed grammatical relation between a pair of words where the relation is defined by two arguments head and dependent [START_REF] Jurafsky | Speech and Language Processing. Always learning[END_REF] The dependency relations between the pairs of words are shown in Ex. 4.3. Here nsubj(likes-2, John-1) indicates the grammatical relationship between the words John and likes where nsubj refers John to be a nominal subject. In addition, dobj(likes-2, shop-5) refers shop to be a direct object. Moreover, compound(shop-5, coffee-4) means coffee and shop together to be a compound word, coffee shop. On the basis of these grammatical relations, it makes possible to detect the clause with the words John likes the coffee shop. Thus syntactic dependency analysis facilitates to identify the related words and the syntactic relationships among them in a sentence.

A graph representation of the syntactic dependencies as shown in Fig. 4.1 incorporates to find the dependency path between two words. For example, the blue colored connections indicate the path between John and Julie. Such path provides some information such as dependency labels (function) and path length to justify if any potential relationship exists between two words.

Dependency Patterns and Edit Distance

Binary relations (i.e. spouse) follow some structures (i.e. X married Y) by placing the words between two arguments (X and Y). Such structures are repeated to mention relationships between different pairs of arguments which are called patterns of relations. Pattern based relation extraction was first studied by [START_REF] Hearst | Automatic acquisition of hyponyms from large text corpora[END_REF]. Pattern based methods usually use POS-tags [START_REF] Fader | Identifying relations for open information extraction[END_REF]) and lexico-syntactic information [START_REF] Alfonseca | Pattern learning for relation extraction with a hierarchical topic model[END_REF][START_REF] Pershina | Infusion of Labeled Data into Distant Supervision for Relation Extraction[END_REF]. Since lexical information is important to characterize the semantic type of a relation, lexical information is added to the POS-tag based patterns to map the open information to semantic relations. However, lexico-syntactic patterns include both lexical and structural information for semantic relation extraction where dependency labels are used for capturing the grammatical structure.

A relation between two arguments in a short or long dependency path can be captured by using syntactic dependency tree. The dependency labels between a pair of words in a relationship make a pattern of that particular relation. Such pattern can be repeated between the same or different pair of words in another sentence.

Chapter 4. Linguistic Characteristics of Expressing and Validating Relations For example, a spouse relationship is mentioned between John and Julie in Fig. 4.2a where the dependency labels (blue colored solid lines) make a pattern (nsub, dobj). Therefore, we have been motivated to define patterns of relations by only syntactic information i.e. dependency labels between a pair of arguments. [nn, nsubj, prep_of]. We simplify the pattern [nn, nsubj, prep_of] to [nsubj, prep_of] by removing leading and following nn. We notice that sometimes the dependency patterns contain consecutive labels like [nsubj, dobj, prep_of, prep_of, poss]. In such cases, we simplify the pattern by substituting the consecutive labels with a single label that means [nsubj, dobj, prep_of, prep_of, poss] is simplified as [nsubj, dobj, prep_of, poss]. This simplification generalizes the dependency patterns.

John

In natural language, a relation can be expressed in several ways and it may not be possible to capture all the patterns of that relation due to lack of positive examples. For example, we obtain 21 different patterns of spouse relation from 37 annotated sentences. The statistics on the collected patterns of some semantic relations is given in Table 4.2. Additionally, some relation expressing snippets with trigger words are shown in Table 4.3. We propose to match the pattern of an unlabeled sentence that claims to hold a specific relation to the existing patterns of that relation by an approximation.

Levenshtein distance or edit distance [START_REF] Levenshtein | Binary codes capable of correcting deletions, insertions, and reversals[END_REF] measures the dissimilarity between two strings by counting the minimum number of operations required to for each pattern q in Q do (nsub, advcl, dobj). We compute the edit distance between (nsub, dobj) and (nsub, advcl, dobj) when the second sentence claims to hold spouse relationship between Kevin and Sarah. The resulted edit distance score between these pair of patterns is 1. We use this score as a feature of binary classification task and a classifier automatically learns whether an unlabeled pattern belongs to the claimed relation.

Thus edit distance calculation facilitates to generalize diverse patterns of the same relation. we use this edit distance feature for validating both trigger-dependent and trigger-independent relations.

Lexical Analysis

Lexis refers to the complete list of words used in a language and word is the basic unit of a sentence. According to the linguistic point of view, semantic analysis refers to understanding the meaning of a word, phrase, sentence etc [START_REF] Jurafsky | Speech and Language Processing. Always learning[END_REF]. Every word has its own meaning and it represents an emotion, concept, object etc. A word may express different meanings based on the context of the text where it takes place. For example, mouse refers to an animal in terms of zoology while it indicates an electric device in terms of computer accessories. In contrast, different words may express the same meaning and they can be used alternatively in texts to express a concept such as dinner and supper both mean the evening meal. Moreover, several words collectively may form a single meaning such as coffee shop refers to a place of serving and drinking coffee. Thus a variety of words are used for expressing different things in natural language.

Ex 4.5: Sentence categorization based on lexical semantics

Julie got married to John and two years later she became a mother.

John started working in a bank as a junior officer.

Different words that are related to the same concept can be grouped together. For example, father, mother, husband, wife, children etc. denote the concept of family. Similarly, a sentence or paragraph can be categorized into a semantic type based on the words in it. For instance, the first sentence in Ex. 4.5 can be cast as the type of family relationship since it contains the words married and mother. However, the words working and officer refer the second to the semantic of employment or profession.

A relation between a pair of entities can be mentioned in a sentence by several words that are specific to characterize the relation. Such words are called trigger words. It requires interpreting the meaning of these words for understanding the mentioned relation and for justifying it linguistically. Thus the semantic type of a relation between two entity mentions in a sentence depends on the words between and/or around them. For example, the first sentence in Ex. 4.5 denotes spouse relationship between Julie and John where the word married and its position characterize the semantic type of the relationship.

Trigger Word Collection

A trigger word holds the semantics of a relation type as defined in section 4.1. Collecting the trigger words of different relations is required for validating a claimed relation hypothesis.

A set of very common trigger words (i.e. husband, wife etc) of a relation (i.e. spouse) can be easily collected as shown in section 4.1. In order to improve the coverage, synonyms and similar words have to be included in the list of trigger words. These words can be found in lexical resources, as WordNet1 for instance. However, for some relations (i.e. shareholders, subsidiaries etc.) it may not be possible to collect all the trigger words, because, these relations can be expressed by using many different words. Highly frequent words (except stop words) between the entity mentions in the annotated sentences of a relation type can be considered as the trigger words of that relation. Therefore, for each type of relation, we extract the words between the pairs of entities in relation. We manually examine which of the frequent words are semantically able to characterize the specific relation and enlist them in the set of trigger words. Table 4.2 represents the statistics on the collected trigger words of some semantic relations.

However, still it is not enough to identify and collect all the trigger words of a relation due to lack of annotated sentences. We need to identify similar words in new sentences. Word embeddings are known for finding semantically similar words. Therefore, we employ word embeddings to recognize the unknown triggers.

Word Embeddings

Word embeddings refers to the vector representation of the words of a corpus where each word is represented by a vector of real numbers [START_REF] Bengio | A neural probabilistic language model[END_REF][START_REF] Schwenk | Continuous space language models for statistical machine translation[END_REF][START_REF] Mikolov | Linguistic regularities in continuous space word representations[END_REF]. Such representation of words basically is done by vector space model where semantically similar words are mapped to nearby points. Vector representation of the words is done based on the co-occurrences of the words in a corpus but the measurement of co-occurrences differs in different embedding models. There are basically two models of learning the vector encoding of the words: count-based and predictive.

In count-based models, a large matrix is constructed where row and column refer to the words and contexts accordingly or vice versa. Co-occurrences of the words are counted according to different contexts. Finally, the high-dimensional vectors of the words are reduced to low-dimensional vectors. An example of count-based vector representation of the words is shown in Ex. 4.6. GloVe (Pennington, Socher,

CBOW

Skip-gram

Figure 1: New model architectures. The CBOW architecture predicts the current word based on the context, and the Skip-gram predicts surrounding words given the current word.

R words from the future of the current word as correct labels. This will require us to do R × 2 word classifications, with the current word as input, and each of the R + R words as output. In the following experiments, we use C = 10.

Results

To compare the quality of different versions of word vectors, previous papers typically use a table

showing example words and their most similar words, and understand them intuitively. Although it is easy to show that word France is similar to Italy and perhaps some other countries, it is much more challenging when subjecting those vectors in a more complex similarity task, as follows. We follow previous observation that there can be many different types of similarities between words, for example, word big is similar to bigger in the same sense that small is similar to smaller. Example of another type of relationship can be word pairs big -biggest and small -smallest [20]. We further denote two pairs of words with the same relationship as a question, as we can ask: "What is the word that is similar to small in the same sense as biggest is similar to big?"

Somewhat surprisingly, these questions can be answered by performing simple algebraic operations with the vector representation of words. To find a word that is similar to small in the same sense as biggest is similar to big, we can simply compute vector X = vector("biggest")vector("big") + vector("small"). Then, we search in the vector space for the word closest to X measured by cosine distance, and use it as the answer to the question (we discard the input question words during this search). When the word vectors are well trained, it is possible to find the correct answer (word smallest) using this method.

Finally, we found that when we train high dimensional word vectors on a large amount of data, the resulting vectors can be used to answer very subtle semantic relationships between words, such as a city and the country it belongs to, e.g. France is to Paris as Germany is to Berlin. Word vectors with such semantic relationships could be used to improve many existing NLP applications, such as machine translation, information retrieval and question answering systems, and may enable other future applications yet to be invented.

FIGURE 4.3:

Predictive models of word embedding [START_REF] Mikolov | Linguistic regularities in continuous space word representations[END_REF] and Manning, 2014) embedding is trained by such model by normalizing the cooccurrence values of the words. Ex 4.6: Count-based vector representation he goes to school by car students go to school by bus there was a car accident a bus accident injured them I drive a car every weekend they travel by bus every weekend drive by a every accident travel school weekend

car 1 1 2 1 1 0 1 1 bus 0 2 1 1 1 1 1 1
In predictive models, either a word is predicted given the surrounding (context) words or the surrounding words are predicted for a given word. The method of training a predictive model for predicting a word based on the context words is called continuous bag-of-words (CBOW) model. In contrast, the method of predicting context words based on a given word called continuous skip-gram model. Concepts of the predictive models are illustrated in Fig. 4.3. The comparison between these two models made by [START_REF] Mikolov | Linguistic regularities in continuous space word representations[END_REF] shows that CBOW is faster than skip-gram for training the model and gets a little higher syntactic accuracy. However, Skip-FIGURE 4.4: Encoding semantic differences in between the vectors [START_REF] Mikolov | Linguistic regularities in continuous space word representations[END_REF] gram model achieves higher semantic accuracy and represents better the rare words compared to CBOW. Word2Vec2 is a widely used implementation to train predictive models based on both skip-gram and CBOW. Word embeddings holds the syntactic and semantic regularities between words that seem to be encoded between the vectors of the words. For example, the differences between two words in terms of gender (male and female) and number (singular and plural) seem to be constant as shown in Fig. 4.4. Thus, two words can be examined whether these represent the same semantic type by calculating the cosine similarity of their vectors. For example, in a word embeddings, it is expected that married and wife would be in the same region of the semantic space. The cosine similarity between the vectors of these words is 0.86 in GloVe embeddings. The score of cosine similarity ranges between 0 and 1 and a higher score means higher similarity. Thus married and wife are close to each other in terms of semantic similarity.

Recognition of Trigger Words

It can be possible to recognize an unknown trigger word of a relation based on a known trigger of that relation by calculating the cosine similarity between the word vectors as illustrated in Alg. 2. Suppose, married, husband, wife are the known trigger words of spouse relation and a sentence There was a big party on wedding anniversary of John and Julie claims to hold spouse relationship between John and Julie. Since the sentence does not contain any known trigger word of spouse relation, we compare each of the content words (except John, Julie and stopwords) in the sentence to the individual known trigger. We take the vectors of a content word and a known trigger from a pre-trained word embeddings. Then cosine similarity is computed between the pair of vectors. for each word X in L do

7: V x ← GetVector(X) 8: d ← CosineSimilarity(V w , V x ) 9: if d > Score then 10: Score ← d 11:
return Score

The best similarity score of 0.61 is resulted between wedding and married. If any word completely matches to one of the known triggers the similarity score becomes 1. High similarity score indicates that it is highly probable to consider the pair of words holding the same semantics. Therefore, we use the best similarity score as a feature for validating a relation hypothesis. A classifier automatically learns the threshold of the score to decide if the word is a trigger or not from the training data. Thus we incorporate word embeddings for recognizing unknown trigger words for relation validation task. The next section describes how we use the trigger words for relation validation task. Then in section 4.5, we will study different word embeddings for this task.

Syntactic-Semantic Fusion

Trigger words are useful for characterizing the types of the relations. It is important to inspect the position of the trigger words in a sentence carefully to validate a relation. For example, a system claims parent relationship between Julie and John in the first sentence of Ex. 4.5 on Page 59 where there is a trigger word mother to support the claimed relation. Though mother is a trigger for parent relation this sentence does not express that relation between Julie and John. Therefore, it requires to combine semantic and syntactic evidence for validating a relation hypothesis.

A sentence can be represented by a sequence of words and a dependency graph. The most common pattern of mentioning a relation is by placing a trigger word between the pair of entity mentions in a sentence as in the first sentence of Ex. 4.5 where married word contributes to express the spouse relation between Julie and John.

However, it cannot be always expected that a claimed relation would be true when a trigger of that relation places in between the entity mentions. For instance, the sentence in Fig. 4.5 contains married between Julie and Tim and a system claims spouse relationship between them. Though there is a trigger word married in between the mentions it does not mean the spouse relationship between them. However, the dependency path Julie → got → 13 → Tim (see Fig. 4.5) between the mentions does not contain any trigger to justify spouse relationship. In contrast, the hypothesis of spouse relationship between Julie and John satisfies the existence of any trigger word for both cases: between the mentions and in the dependency path. Therefore, we examine the existence of any trigger in the sequence of words when they are placed according to the dependency path. For example, in Fig. 4.5, according to the dependency path (nsubj-xcomp-nmod) between Julie and John, the word sequence is got married which contains a trigger married. Moreover, sometimes, the trigger can be found outside the dependency path for justifying a relation. For example, in the sentence John first met Julie three years before their marriage, the trigger word marriage does neither lie between the mentions of John and Julie nor in between the dependency path as shown in Fig. 4.6. In such cases, we check if there is a trigger word in the minimum subtree. A minimum sub tree is a part of a dependency tree which mainly focuses on the target nodes and their direct neighbor nodes. Such trees have been explored by [START_REF] Chowdhury | A study on dependency tree kernels for automatic extraction of protein-protein interaction[END_REF] for biomedical relation extraction. In order to find a trigger word in the minimum subtree, firstly we find out the common root node of the pair of mention nodes. Then we examine the directly connected child nodes of the root. In Fig. 4.6 the common root between John and Julie is met and the child nodes of met are first, years and marriage where marriage is a trigger word for spouse relation. We examine the directly connected child nodes in order to capture the trigger evidence in a shorter context. When the dependency tree of a long sentence contains several levels, including indirectly connected child nodes for inspection may lead to noisy context. We assume that the information in the shorter context is more reliable than in longer context.

In summary, for validating a claimed relation we inspect the existence of any trigger word (i) between the entity mentions (ii) in between the dependency path and (iii) in the minimum subtree of a dependency parse tree.

Evaluation of Word-embeddings

We examine the quality of different word-embeddings in terms of trigger words similarity. In this evaluation, we use three pre-trained word-embeddings which are GloVe3 , GoogleNews-Vectors4 and FastText5 . Moreover, we build two more wordembeddings KBP-WordSG and KBP-CharSG by training the word2vec model with word skip-gram and character skip-gram accordingly on TAC KBP-2014 corpus. Table 4.4 represents the characteristics of these word-embeddings. In the pre-trained GloVe, GoogleNews-Vectors and FastText, each word is represented by a vector of 300 dimension. In contrast, KBP-WordSG and KBP-CharSG represent a word by a vector of 250 dimension. We reduce vector dimension for training the models rapidly. Our study finds that the reduction of vector dimension from 300 to 250 does not degrade the quality a word embeddings.

The trigger words of a relation denote the same semantic. Therefore, we expect that trigger words of the same relation would lie on the same vector space in a good word-embeddings. In order to evaluate the qualities of these word-embeddings, we compute the similarity between every pair of trigger words and standard deviation of the similarity scores. For example, wife, husband, married are trigger words of spouse relation. We compute similarity of (wife, husband), (husband, married) and (wife, married) pairs. We expect that similarity scores of these pairs would also be similar. That means, the standard deviation of these similarity scores would be very low. We perform another experiment which focuses on validating relations as a binary classification task. The objective of this experiment is to evaluate the quality of a word-embeddings on identifying unknown triggers of a relation. In this experiment, we use the three features that inspect the existence of trigger-words (Section 4.4) based on trigger-word similarity scores (Section 4.3.3) measured on a word-embeddings. We expect better classification performance based on the similarity scores measured on a better word-embeddings. The evaluation dataset consists of 3, 945 training instances where positive and negative examples count 1, 443 and 2, 502 instances accordingly. In contrast, the test dataset counts of 8, 423 instances where the number of positive and negative examples are 1, 805 and 6, 618 respectively.

Word-embeddings

# Features Precision Recall F-score Acc. The upper part of Table 4.6 represents the performance of relation validation by individual word-embeddings. We see that the best recall and F-score is obtained by KBP-WordSG. In contrast, KBP-CharSG results in the lowest precision and F-score which are 39.15 and 49.15 accordingly. The F-scores obtained by other embeddings ranges between 49.17 to 50.52. These scores indicate that no individual wordembeddings gets a significantly better score. Therefore, we combine the trigger-word similarity scores resulted by different word-embeddings. This combination method increases the number of features. For example, the combination of KBP-WordSG and KBP-CharSG counts 6 features where each of them counts 3 features by inspecting the existence of trigger words. These features differ in terms of similarity scores measured on two different embeddings. Thus a combination of 4 word-embeddings counts 12 features. The lower part of Table 4.6 shows the performance of relation validation by different combinations of word-embeddings. We observe that two combinations GoogleNews-Vector + KBP-WordSG and KBP-WordSG + KBP-CharSG outperform the best individual embeddings by around 1 point in term of F-score.

Chapter 4. Linguistic Characteristics of Expressing and Validating Relations

These two combinations obtain the F-scores of 52.20 and 52.06 accordingly. Moreover, these combined embeddings perform better than some of the combinations of two embeddings. Interestingly, we notice that each embeddings of these two combinations has been trained by word2vec model. Moreover, they include at least one word-embeddings which is trained on TAC KBP-2014 corpus. However, we achieve the best result by the combination of four embeddings GoogleNews-Vector + FastText + KBP-WordSG + KBP-CharSG in terms of precision, recall and F-score. This combination results in an F-score of 53.73 which beats the best individual embeddings (KBP-WordSG) by around 3 points. Moreover, it outperforms the paired combination (GoogleNews-Vector + KBP-WordSG) by around 1.5 points. These results depict that the combination of word skip-gram and character skip-gram based word2vec models and models trained on TAC KBP-2014 corpus improves the performance of relation validation by identifying the trigger words more precisely.

Conclusion

This chapter discussed on the linguistic aspects for relation validation task. Semantic and syntactic analysis facilitate extracting effective features regarding this task. Lexical semantics is able to characterize the types of trigger dependent relations. On the other hand, syntactic patterns denote grammatical structures of sentences expressing some relations. In this chapter, we focused on the state-of-the-art linguistic features and explored some new aspects for validating a claimed relation. We proposed dependency-pattern-edit-distance to generalize the syntactic patterns of the sentences expressing the same relation. Moreover, we presented a method of identifying unknown trigger words by using the known triggers and word-embeddings.

T

His chapter presents our relation validation system. Here, we firstly focus on our relation validation model with a system overview. Then we describe the evaluation corpus. Finally, the evaluation metrics are defined for relation validation and KBP tasks.

Relation Validation Model

We want to validate a claimed relation whether it is correct or wrong. Given a relation hypothesis, (R, E q , E c ) and a justifying sentence, S, the objective is to predict either the relation hypothesis is correct or wrong by analyzing the community graphs (G q and G c ) of E q and E c and by performing some linguistic analysis on S.

We consider relation validation as a binary classification task. Therefore, a binary classifier is trained with several features which are computed on the positive and negative examples. Then the classifier predicts a relation hypothesis under validation if it is correct or wrong.

Furthermore, we populate a knowledge base after validating the relation hypotheses which are generated by different systems. In KBP task, there are two types of slots, single-valued and multi-valued. A single-valued slot (e.g. per:country_of_birth) has to be filled up by only one filler value. In contrast, a multi-valued slot (e.g. per:country_of_residence) can be filled up by several non-repeating filler values. In order to select the correct filler values of a slot filling query for KBP, we apply the algorithm as shown in Alg. 3. The inputs to the model are a query relation name or slot name (R), subject entity of the query relation (E q ), list of candidate objects (E c ), list of relation justifying sentences (S), a graph of entities (G) and a pre-trained binary classifier (M ). For each candidate (E ci ), a feature vector (V ci ) is generated and then a classifier predicts whether (R, E q , E ci ) is true or false. All the candidates (E c ) classified as true are selected as the filler values of R if it refers to a multi-valued slot. However, if R is a single-valued slot, we take the first element from the list E c .

Relation Validation Features

We first remind the features based on the graph and linguistic analysis for validating relations as discussed in Chapter 3 and Chapter 4. Additionally, we will present some trustworthy features based on the agreements among different system responses. Table 5.1 summarizes the features we used in our model.

for each candidate E ci in E c do 10: H ← (R, E q , E ci ) 11: V ci ← generate feature vector for (R, E q , E ci ) 12: L ← Classify(M, V ci ) 13: if L = T RU E then 14: E c ← E ci 15: if R is a multi-valued slot then 16: return E c 17: else if R is a single-valued slot then 18: return top element from E c (a) Graph Features
We propose four graph features for validating a claimed relation between two entities as described in Section 3.5 on Page 45. Here we briefly remind these features.

(i) Network Similarity: we compute the similarity between the communities of a subject (E q ) and an object (E c ). We hypothesize that the community of a subject entity would be more similar to the community a true candidate than the community a false candidate.

(ii) Network Density: we combine the community networks of a subject (E q ) and an object (E c ) of a relation hypothesis and compute density of the merged network. We assume that the density would be higher for a correct object than a wrong one when the community of an object entity is merged with the community of the subject entity.

(iii) Eigenvector centrality: we hypothesize that a subject of a relation hypothesis would be more influenced by a true candidate object than a false candidate. Eigenvector centrality measures the influence of a node in a network. A node will be even more influential if it is connected to other influential nodes. Therefore, we quantify the influence of a candidate object (E c ) to a subject entity (E q ) by measuring Eigenvector centrality.

Feature Group Feature Name

Graph

Network similarity between the communities of Eq and Ec of a relation hypothesis, (R, Eq, Ec)

Network density by merging the communities of Eq and Ec of a relation hypothesis, (R, Eq, Ec)

Eigenvector centralities of Eq and Ec of a relation hypothesis, (R, Eq, Ec)

Mutual information between the communities of Eq and Ec of a relation hypothesis, (R, Eq, Ec) (iv) Mutual Information: the amount of information shared between two variables can be measured by mutual information. We assume that a subject entity shares more information with a true candidate object than a false one. Therefore, we quantify the shared information between two entities (E q and E c ) by measuring mutual information between them in their communities.

Linguistic

(b) Linguistic Features

Validating a claimed relation requires linguistic information for capturing syntactic patterns of a relation expression and characterizing the semantic type of a relation. Therefore, we use several linguistic features regarding this task.

(i) Dependency Patterns: expression of relations follow some syntactic dependency patterns. Matching these patterns is useful for relation extraction. However, a relation can be expressed by several different patterns. Some of these patterns may be unidentified. Therefore, we propose to calculate edit distance between a pattern under inspection and a set of pre-identified patterns. Moreover, length of the dependency path between a pair of entity-mentions is used as a feature for validating relation.

(ii) Inspection of the Entity Pair in the Same Clause: we hypothesize that the related pair of entities are mentioned in the same clause if the sentence of expressing relation is complex or its length is comparatively long. Therefore, we inspect whether the related pair of entities is mentioned in the same clause.

(iii) Inspection of the Trigger Words: relations are mostly expressed in a sentence by some trigger words. Therefore, we inspect existence of any trigger word between a pair of entity mentions, in the syntactic dependency path and in the minimum dependency tree (see Section 4.4).

(iv) Indication of Relation Type: the existence of trigger word is not mandatory for some relations such as per:city_of_residence. We use a boolean indication of relation type either trigger-dependent or trigger-independent as a feature for validating relation.

(c) Trustworthy Features

We define voting features to observe the trustworthy influence of multiple systems on validating claimed relations. Therefore, we calculate a credibility score (voting) of a candidate object based on all the responses given by different systems for a given subject and relation name.

Suppose, E c = {E c1 , E c2 , E c3 } is the list of candidate objects generated by three systems S = {S 1 , S 2 , S 3 } with respect to a query relation (R, E q , ?) with id Q and D = {D 1 , D 2 , D 3 , D 4 } be the documents where the candidates are mentioned. The relations among the candidates, systems and documents are as follows:

E c1 (S 1 , S 2 , D 1 , D 3 ), E c2 (S 2 , D 2 ), E c3 (S 1 , S 3 , D 1 , D 4 ).
We compute the Filler Credibility of a candidate by using Eq. 5.1.

F iller Credibility(E ci , Q) = # occurrences of a candidate E ci f or query Q # occurrences of all the candidates f or Q (5.1) The Filler Credibility counts the relative votes for a candidate which indicates the degree of agreement by different systems to consider the candidate as correct. Since we can assume that systems already performed some analysis to make the responses, Filler Credibility holds strong evidence for a candidate to be correct. Such measurement has been used by [START_REF] Sammons | Overview of UI-CCG systems for event argument extraction, entity discovery and linking, and slot filler validation[END_REF] where candidate objects have been validated based on the majority voting.

We also compute the Document Credibility of a referenced document in a response to a query relation by Eq. 5.2. The Document Credibility measures the reliability of a source document where a candidate object is mentioned.

Document Credibility(D i , Q) = # occurrences of a document D i f or query Q # occurrences of all the documents f or Q (5.2)
Moreover, the System Credibility is measured to quantify the reliability of a system by counting the number of common candidates among different systems. We build a two-dimensional matrix where the rows and columns refer to the slot filling systems. At first, the matrix is initialized by zero. If two systems respond with the same filler to a query, we increase the credibility of both systems by 1. We repeat this process for all the queries. After completing this process with all the queries, we count total credibility of each system by adding the values of the corresponding row or column. Finally, the credibility values are normalized by the top score. We also include the confidence score of a response (which is given by a system) as a feature for validating relations.

Relation Validation System Overview

We build a system to integrate different components of our relation validation model. This system basically contains three components: input processing, feature extraction and binary classification. Figure 5.1 depicts the different components of the relation validation system. • Binary classification: finally each response is classified as correct or wrong by using a pre-trained classifier.

Corpus and Preprocessing

In our research, we used the corpus of KBP Slot Filling (English) evaluation task in 2014, 2015 and 2016 which have been provided by NIST. This section illustrates these corpora and their preprocessing for constructing a graph of entities.

KBP Slot Filling Corpora

Each of the KBP document corpora consists of newswire and discussion_forum document. The corpus of KBP-2014 includes web data in addition to the newswire and discussion_forum. Each of the document in the corpus is XML formatted and contains an id. The web data are noisier compared to the newswire and discus-sion_forum. Among these three types of data, the increasing order of noisiness is newswire, discussion_forum and web data. A newswire document follows the markup as shown in Ex. 5.1 where the id refers to the unique identifier of the document and type (=story) refers to the type of a document if it is characterized as story. However, the HEADLINE and DATELINE tags are optional and the TEXT content may include <P> ... </P> tags if doc_type_label is story. A discussion_forum data may contain multiple posts as the markup described in Ex. 5.2. There may also be arbitrarily deep nesting of quote elements, and other elements e.g. <a...>...</a> tags in the discussion_forum documents. Furthermore, Ex. 5.3 represents the markup for the web documents where most of the web documents contain <QUOTE ...> tag without having the end tag, </QUOTE>. A portion of text in the discussion_forum and web data may repeat under the tags <quote> and <QUOTE> accordingly when the same topic is shared among different users and comments are made on it. Preprocessing of the corpus was done by the team of IMM project at IRT Sys-temX with the IMM platform [START_REF] Mesnard | Construction automatisée d'une base de connaissances[END_REF]. Firstly, all the documents of these three categories of data were parsed and stored in a MongoDB database. The pipeline of processing the XML formatted source files is shown in Fig. 5.2 that makes the collection of text corpus. The markup tags were removed from the documents to make them clean and for better linguistic preprocessing. Moreover, duplicate instances of texts (according to the <quote> or <QUOTE> tag) were removed. While removing these texts, the original positions of the remaining texts were preserved. Basically, the repeated texts were replaced by blank spaces where the number of blank spaces was equal to the number of characters in a repeated text. IRT SystemX used KBP corpus for developing a slot filling system. If a mention of a relation between two entities is repeated by the same text-segment in the same document, counting more instances of the relation may bias a slot filling system. Therefore, removing the repeated texts was important to avoid the bias factor. Then each of the documents was splitted into sentences by using Stanford CoreNLP (Manning et al., 2014a) and both the original and cleaned documents were stored in MongoDB for further use. We construct two Neo4j graph databases from KBP-2015 and KBP-2016 corpus as described in Section 3.3 on Page 38. Table 5.3 summarizes the statistics of these two graphs. There are 152, 583 and 65, 389 entities (person, organization and location) in the graphs constructed on the KBP-2015 and KBP-2016 corpus accordingly. Moreover, these graphs consist of 805, 216 and 488, 198 IN_SAME_SENTENCE links among different entity mentions respectively. We construct two different graphs because the query entities and the corresponding filler entities are different in the KBP tasks of 2015 and 2016. Thus constructing the two graphs helps to find the information regarding these entities.

KBP Slot Filling Responses and Snippet Assessments

The KBP task defines a set of slot filling queries by the entity name, reference document, offset of the entity mention, entity type and the slot name as depicted in Ex. 5.4.

Ex 5.4: A slot filling query <query id="CSSF_ENG_0e7479c2b6"> <name>Nelson Mandela</name> <docid>a69c5c79caa4c2b2869775fabcbabc7f</docid> <beg>174</beg> <end>187</end> <enttype>per</enttype> <slot>per:spouse</slot> </query> A slot filling system has to respond with the filler value of the query and some additional information according to a predefined format of 8 tab-separated columns as listed in Ex. 5.5. TAC provides the assessments of a subset of the query-responses by different systems after the evaluation. The assessment file contains the queries, responses and assessments of the responses. Each response is assessed based on the filler value and its justification by the relation provenance snippets.

Ex 5.5: Format of a slot filling response column 1: Query Id column 2: Slot Name column 3: A unique run Id of a SF system column 4: Provenance for the relation (doc ID and offsets) column 5: A slot filler column 6: A filler type (PER, ORG, GPE, STRING) column 7: Provenance for the filler value (doc ID and offsets) column 8: Confidence score

The assessment of a relation provenance snippet can be either correct (C), wrong (W), inexact-short (S) or inexact-long (L) where inexact-short means that the snippet does not contain enough information to justify the relation and inexact-long indicates that the snippet is too long having some unnecessary information. There are 8 tabseparated columns in the assessment file as the format is illustrated in Ex. 5.6. from the datasets of three different years. It shows that the number of negative responses is much higher than the number of positive responses in all of the three datasets. Each of the assessed datasets covers 41 types of relations.

Evaluation Metrics

Evaluation is important for determining the performance of a method or a system. It quantifies the merit of a system by calculating some metrics governed by a set of standards. Thus quantitative measurements of the metrics facilitate to compare the performances of different systems that perform the similar task.

The evaluation metrics differ for different tasks. Information extraction related tasks such as Message Understanding Conference (MUC) [START_REF] Grishman | Message understanding conference-6: A brief history[END_REF] and KBP [START_REF] Surdeanu | Overview of the english slot filling track at the tac2014 knowledge base population evaluation[END_REF] are usually evaluated by precision, recall and F-score.

In the classification based tasks such as relation classification [START_REF] Girju | Semeval-2007 task 04: Classification of semantic relations between nominals[END_REF]) precision and recall is calculated based on the confusion matrix [START_REF] Sokolova | A systematic analysis of performance measures for classification tasks[END_REF]. The accuracy also gives a good indication of performance measurement for classification task which calculates the ratio of correctly classified instances to the total number of instances. Fig. 5.4 shows a confusion matrix model of binary classification where the observations come from two classes positive (+) and negative (-). A confusion matrix is described by four terms true positive (TP), false positive (FP), false negative (FN) and true negative (TN) which are defined below:

Terms of the confusion matrix TP counts the number of positive observations predicted as positive. FP counts the number of negative observations predicted as positive. FN counts the number of positive observations predicted as negative. TN counts the number of negative observations predicted as negative.

In the classification task, the precision, recall and accuracy are calculated by the Eq. 5.3, Eq. 5.4 and Eq. 5.5 based on the TP, FP, FN and TN. However, the calculation of F-score remains the same as it is defined for information extraction task in Eq. 5.6.

P recision =

T P T P + F P (5.3)

Recall = T P T P + F N
(5.4)

Accuracy = T P + T N T P + F P + F N + T N
(5.5)

F 1 = 2 * precision * recall precision + recall (5.6)
In both information extraction and classification tasks the objective of a system is to obtain high precision and recall so that a high F-score can also be achieved. Sometimes, high recall is expected at the cost of precision and vice versa to get a high F-score. A high recall is expected when a system has to extract or predict a large number of positive observations. On the other hand, when a system is required to say confidently an extracted information or predicted observation is correct the precision gets more importance. We expect high precision at the cost of the recall to achieve a good F-score for our relation validation task. A high accuracy is desired as well.

A KBP system (slot filling and slot filler validation) is also evaluated by precision, recall and F-score but the definition of precision and recall are a little different than traditional definitions. The precision and recall for KBP task are measured by the Equations 5.7 and 5.8 respectively. For calculating the recall, ground truths of the queries have been defined base on the total number of possible non-redundant correct filler values. precision = number of correct objects number of correct and f alse objects

(5.7) recall = number of correct objects total number of ground truth

(5.8)

Conclusion

This chapter presented our relation validation framework, the different corpus and the evaluation metrics. We consider relation validation as a binary classification task. In Chapter 6

Experiments and Results

T

His chapter illustrates the experiments related to the tasks of relation validation and knowledge base population (KBP). Firstly we build several supervised relation validation models based on different feature combinations and observe their contributions on the slot filler validation (SFV) task. Then we investigate drawbacks of these models and propose some improvements. Finally, we improve our supervised relation validation models and evaluate them on a larger corpus. We also evaluate an unsupervised relation validation model to realize its performance. Moreover, we employ these relation validation models for KBP task and compare KBP scores to different systems.

Participation to TAC KBP-2016 SFV Task

NIST conducts SFV task in the TAC KBP workshop which aims at ensembling the slot filling responses of different systems to construct a more precise knowledge base. We participated in the TAC KBP-2016 SFV ensemble task. NIST provided the assessments of the responses of slot filling queries used in TAC KBP-2014 and KBP-2015 tasks. We used them for learning purpose.

In the assessment of TAC KBP-2015 dataset, the responses of around 4, 400 slot filling queries were assessed. A lot of queries have been answered with only wrong responses. Therefore, we do not take into account these queries for building our training corpus. We select the queries that have been answered with at least one correct and one wrong response. This subset counts total 1, 296 slot filling queries. We have extracted linguistic features for around 55, 276 responses from 68, 076 responses that contain mentions of the subject and object entities of a claimed relation. Our system fails to detect many named entities from texts. Moreover, in many cases, entities are mentioned by pronouns. We do not use any tool of co-reference resolution due to lower performance of the existing tools. Therefore, in many cases, our system cannot detect both the subject and object entities of a relation which are mentioned in the same sentence. As a result, we are not able to extract linguistic and graph features for a large number of responses. Our system extracted both linguistic and graph features for around 4, 321 responses from 260 queries.

Evaluation of Different Feature Groups

Here we observe the relation validation performances of three feature sets based on trustworthy, linguistic and graph analysis. We perform 10-fold cross-validation by Chapter 6. Experiments and Results

Random Forest classifier on both datasets which count 55, 276 and 4, 321 responses accordingly. We use Random Forest classifier because it gives better performance than other classifiers on our data.

Feature Set

Precision Recall F-score Accuracy The upper part of Table 6.1 shows the cross-validation results on the responses having no graph feature. We observe that four trustworthy features collectively performs better than the linguistic features to classify correct and wrong responses. Trustworthy and linguistic features resulted in F-scores of 88.16 and 56.74 accordingly. Interestingly, Filler Credibility, as a single feature, obtains an F-score of 67.88 which is around 11 points higher than the linguistic features. This result indicates that trustworthy features are very effective for validating relations. However, the combination of trustworthy and linguistic features outperforms the trustworthy features by around 5 points. This result signifies the contribution of linguistic analysis for validating relations.

Moreover, the lower part of Table 6.1 depicts the cross-validation results on the responses having graph features. Trustworthy feature set achieves better precision, recall, F-score and accuracy than the scores resulted by linguistic features. However, Filler Credibility and linguistic features obtain similar F-score although their precision and recall are different. Here we also notice better result by combining different feature sets. The combination of trustworthy and linguistic features results in F-score of 90.95 which is around 6.5 points higher than the trustworthy features.

Interestingly, graph features combined with trustworthy and linguistic features significantly improves the performance to classify correct and wrong responses. This combination achieves an F-score of 94.15 which is around 10 and 3 points higher than the score of trustworthy and trustworthy+linguistic features accordingly. These results signify the effectiveness of graph features on validating relations although the experiment is performed on a small dataset.

Relation Validation Models for KBP-2016 SFV Task

We build different classifier models by merging the two datasets and combining different feature sets. The merged dataset counts in total 59, 597 responses. In order to handle the responses having no graph feature, we allow the classifier to assign some values to the graph features. In such cases, Random Forest classifier assigns the median value of a missing feature. Four relation validation models had been built as shown in Table 6.2. Cross-validation evaluation on these models show the performance order (descending) Trustworthy+Linguistic+Graph, Trustworthy+Linguistic, Trustworthy, Linguistic in terms of F-score. These models had been used in TAC KBP-2016 SFV evaluation task. We expected the best result from the model of Trust-worthy+Linguistic+Graph combination because this model obtained the best score in cross-validation as shown in Table 6 The upper part of Table 6.3 shows the official scores in KBP-2016 SFV ensemble task by employing four relation validation models. The relation validation models resulted very low scores in the official evaluation of SFV task. Moreover, Trustwor-thy+Linguistic+Graph did not get the best score among four relation validation models. We obtained the best F-score of 24.79 by Trustworthy+Linguistic model which is around 5 points higher than Trustworthy+Linguistic+Graph model. The model based on trustworthy features resulted in the second highest F-score of 23.90 among four models. However, Linguistic and Trustworthy+Linguistic+Graph models obtained similar F-score which is around 19.50. The lower part of this table presents the official scores obtained by three other participants. The best performance was achieved by Anonymous Participant-3 which scored F-score of 32.42. In contrast, two other Anonymous Participants obtained the F-scores of 27.34 and 28.64 accordingly. Our best model scored F-score 24.79 which is around 8 points lower than the score of Anonymous Participant-3. Our results were very frustrating as they did not meet our expectation.

Relation Validation Model

Precision Recall F-score

System Investigation

Our relation validation models are basically trained on TAC KBP-2015 dataset and evaluated on TAC KBP-2016 SFV task. Since the relation validation models do not perform well, we try to analyze both of the training and evaluation datasets. Moreover, all the features that we use in relation validation task may not be effective for different datasets. Therefore, we also analyze the effectiveness of the features.

Statistical Difference Between TAC KBP Evaluation Datasets in 2015 and 2016

In order to investigate the training and evaluation datasets, we compare these datasets statistically. In statistics, the measurement of p-value quantifies the significance of the difference between two samples. Student's t-test [START_REF] Student | The probable error of a mean[END_REF] facilitates to measure the p-value. p-value ranges between 0 and 1. If the p-value is less than 0.05 in a particular observation, the result of that observation is interpreted as significant.

We measure the p-value of each feature score regarding the instances of training and evaluation datasets used in our relation validation task. Our objective is to observe whether these two datasets are significantly different. In this investigation, we take into account the responses on 9 relations which individually counts at least 50 positive responses. Relations with fewer positive responses may not give us a good realization of the differences between two datasets. Table 6.5 shows the measured p-values of different features where a significant pvalue is indicated with a star (*) mark. We see that almost all the feature values of different relations in the two datasets differ significantly. For example, in 6 relations out of 9, the feature values of column A and B (both are trigger word features as shown in Table 6.4) in the KBP-2015 and KBP-2016 datasets are significantly different. Only two syntactic features (column F and G) have less difference between KBP-2015 and KBP-2016 datasets.

Since there are many negative responses compared to the number of positive ones, we measure p-value by balancing the positive and negative responses with a ratio of around 1 : 2. That means each dataset counts two negative responses for a positive one for each query. According to the Table 6.5 and Table 6.6, in most cases, specially for the trigger word features (A-D) and trustworthy features (I-L) the datasets differ significantly. This difference might be one of the reasons of low score in the official evaluation of slot filler validation task.

Impact of the Trustworthy Features

We investigate the effects of trustworthy features on validating relations when the models are trained and tested on the subsets of KBP-2015 and KBP-2016 datasets accordingly. In this experiment, we balance the number of positive and negative examples of each dataset by a ratio of 1 : 2. Before balancing, we remove the duplicate instances from both datasets. Thus, KBP-2015 dataset counts 24,624 instances (positive = 8,206 and negative = 16,418) and KBP-2016 dataset contains 4,882 instances (positive = 1,627 and negative = 3,255). Table 6.7 shows the performances of different feature combinations when they are trained on the KBP-2015 dataset and tested on the KBP-2016 dataset. The set of four trustworthy features results in the precision, recall and F-score of 52.33, 49.78 and 51.02 accordingly. We notice that Filler Credibility gets better precision, recall and F-score than the combination of all trustworthy features by around 4, 11 and 7 points accordingly. Surprisingly, these two combinations do not exceed the scores obtained by Filler Credibility even though they are combined with linguistic features. The combination of Filler Credibility and linguistic features obtains the precision, recall and F-score of 54.98, 50.58 and 52.69 accordingly which are lower than the scores resulted by Filler Credibility alone. Moreover, the combination of four trustworthy and linguistic features obtains around 11 and 5 points lower recall and F-score than the scores resulted by Filler Credibility. However, this combination achieves the best precision of 58.90 which is around 2.65 points higher than the precision obtained by Filler Credibility.

Feature Combination

Precision Recall F-score However, we noticed different characteristics of the feature combinations by 10fold cross validation on the subset of the KBP-2015 dataset as shown in Table 6.8. Here, the combination of four trustworthy features outperforms the Filler Credibility by around 19, 21 and 20 points in terms of precision, recall and accuracy accordingly. Moreover, Filler Credibility combined linguistic features results better scores than the Filler Credibility itself. The best precision, recall and F-score of 94.36, 94.03 and 94.20 have been achieved by combining all the trustworthy features and linguistic features.

All the scores observed in Table 6.7 and Table 6.8 indicate that the performances of trustworthy features which are dependent on systems and data in different years are not consistent. However, the Filler Credibility, which counts votes of agreement on the responses, seems consistent for validating relations. Table 6.9 represents the statistics of the number of positive responses and number (with percentage) of responses having trigger word (a content word to justify the claimed relation) for several slots in KBP-2015 and KBP-2016 datasets. For example, there are 98 responses for per:children slot in the KBP-2015 dataset where each of them contains at least one trigger anywhere in the relation justifying snippet. We observe that each of the responses of per:children and per:city_of_birth slots in both datasets contains at least one trigger. Only 3 (per:city_of_death, per:parents and org:member_of ) out of 18 slots in KBP-2016 dataset count higher percentage of positive responses having trigger words compared to the KBP-2015 dataset. However, 13 slots in KBP-2016 dataset count less percentage of responses with trigger words compared to the KBP-2015 dataset. For example, per:country_of_birth, per:spouse and per:cities_of_residence count 100%, 86.8% and 73.6% responses having triggers in KBP-2015 dataset while these numbers are 83.3%, 76% and 12.7% in KBP-2016 dataset respectively. These numbers indicate that KBP-2015 and KBP-2016 datasets differ to each other on the basis of trigger words as well.

We split the slot based on the percentage of responses having trigger words. Almost all the slots in the upper part of Table 6.9 individually counts more than 80% responses with trigger words in both datasets. Each of the slots in the lower part individually counts less than 60% responses with trigger words except per:cities_of_residence and per:employee_member_of in the KBP-2015 dataset. We can consider these slots in the lower part of Table 6.9 as trigger-independent. This list of trigger-independent slots slightly differs from the trigger-independent slots defined in Table 4.1 in Chapter 4. In Table 6.9, org:city_of_headquarters and org:country_of_headquarters are considered as trigger-independent while in Table 4.1 they have been considered as trigger-dependent. Moreover, org:member_of was included in the group of triggerdependent relation while here we discover it as a trigger-independent relation. The relations in Table 4.1 were grouped into trigger-dependent and trigger-independent based on the slot filling responses of the KBP-2014 dataset which consisted of a small number of responses compared to KBP-2015 and KBP-2016 datasets. According to the statistics presented in Table 6.9, we assume that it would be better to focus on mostly trigger dependent relations (upper part of this table) for realizing the task of semantic relation validation.

Identifying the Reason of Failure to Compute Graph Features

For computing graph features on the two entities, we retrieve the subject and object entities of a relation hypothesis from the constructed association graph based on the given document id and offsets in a slot filling query and response. Since the construction of an association graph depends on named entity recognition (NER), we do not compute graph features if the association graph does not contain any of the two entities of a claimed relation.

Our system was able to generate graph features for a very small number of responses. We were able to compute graph features for only 1, 326 responses (around 14%) out of 9, 510 potential responses. We suspect that redundant text filtering in preprocessing (see Section 5.2.1 on Page 76) and limitation of NER tool restricted to detect some named entities from texts. We investigate around 1, 350 queries of KBP-2016 whether our system can retrieve the subject entities mentioned in these queries.

Repeated Text Filtering

In the corpus preprocessing step, we filtered out repeated texts in a document. In some queries, the subject entities are mentioned in the text segments which we filtered out. Therefore, because of filtering redundant text, we failed to detect the subject entities of 78 queries which is around 5.8% of the total 1, 350 queries.

The Ambiguity of Entity Type in Slot Filling Query

There are several queries (e.g. gpe:member_of) where the named entity type of the subject is mentioned as GPE (Geo-Political Entity). GPE usually refers to a location typed entity such as city, state/province and country. However, in a query of GPE typed entity, the sub-type is not mentioned. Therefore, a GPE typed entity becomes ambiguous to identify either it is a country name, state name or city name. There are 181 queries out of 1, 350 which mention ambiguous GPE typed entities. Thus, we failed to retrieve around 14% query entities.

Limitation of the NER Tools

Our fusion NER system was able to detect only 690 entities as mentioned in 1, 350 queries. That means our NER system was unable to retrieve around 37% of the query entities. We noticed that in several cases, type of the same entity mention differs in the slot filling query and in the association graph. Therefore, retrieving the entity which was mentioned in a query was not possible. By ignoring the type, our system retrieved additional 178 query entities. Thus, lack of retrieving entities was reduced to around 20.5%. Still, this percentage is high but seems reasonable according the performances of existing NER tools as the highest F-score of entity mention extraction on the KBP-2016 corpus (English) is 76.0 [START_REF] Ji | Overview of TAC-KBP2016 Tri-lingual EDL and its impact on end-to-end Cold-Start KBP[END_REF].

Two Related Entities in the Same Sentence

We constrained to find the subject and object entities of a relation in the same sentence for computing graph features. Therefore, we also investigated how many entity pairs of the relation hypotheses have been mentioned in the same sentence. We found that only 1, 326 entity pairs out of 2, 467 were mentioned in the same sentence. That means, our system was not able to find around 46% of the related entity pairs in the same sentences.

Summary

Our investigation finds that due to redundant text filtering, ambiguous entity (GPE) type and NER limitation we lack to retrieve in total around 40% query entities. We also noticed that only 2, 467 entity pairs out of 9, 510 slot filling responses were retrieved from our association graph which was around 26%. Moreover, due to the constraint of finding the subject and object entities of a relation in the same sentence for computing graph features, we missed around 46% of all the responses. Thus, finally we were able to compute graph features for only around 14% slot filling responses. In order to increase the dataset with graph features, two constraints can be relaxed: (1) relaxing the constraint of retrieving entities from the exact position as mentioned in the queries (2) relaxing the constraint to exist the subject and object entities of a relation in the same sentence.

Conclusion and Plans for Improving the System

In our experiments on the KBP-2015 dataset, graph based features have been proven effective to achieve a very good score for validating relations. However, our system lacked to generate graph features for a large number of relation instances. Moreover, slot filler validation system built on some relation validation models with different feature sets did not obtain a good score in the official evaluation of KBP-2016 slot filler validation task. We investigated different issues such as differences between the training and evaluation datasets, trustworthy features, relations with trigger words and lacking responses having graph features etc.

We want to increase the training and test datasets having graph features by relaxing some constraints and to redesign relation validation models with optimized feature sets. Moreover, we want to focus on mostly trigger-dependent relations because they are easy to understand and they are more suitable to evaluate both linguistic and graph features for relation validation task.

Supervised Relation Validation and Knowledge Base Population

Our objective is to employ the relation validation models for discarding wrong relation hypotheses which are generated by several slot filling systems. We aim at populating a knowledge base of trigger-dependent relations based on our supervised relation validation models. In this study, we select 12 relations where 8 are highly trigger-dependent, 2 are softly trigger-dependent and 2 are trigger-independent according to Table 6.9. The selected relations are listed in Table 6.10. We rebuild several relation validation models which are trained and tested on subsets KBP-2015 andKBP-2016 We select the best feature set based on an empirical analysis which is listed in Table 6.11. The performances of different features for validating relations as a binary classification task are presented in Table 6.12. We observe that the set of linguistic features used in KBP-2016 SFV task obtains an F-score of 37.7. However, a set of selected linguistic features which removes the indications of relation type (triggerdependent or trigger-independent) and related entity pairs in the same clause gets a better F-score of 41.3. Moreover, filler credibility as a single trustworthy feature gets an F-score of 64.2 which outperforms the set of four trustworthy features by around 11 points. The combination of selected linguistic features and filler credibility increases the F-score by around 1 point compared to the score of filler credibility. We achieved the best F-score of 70.1 by combining selected linguistic features, filler credibility and graph features. This combination results in the best precision, recall and accuracy as well.

Impact of Adding More Training Data

We inspect the efficiency of the relaxed constraint of the IN_SAME_SENTENCE link between subject and object entities over hard constraint to improve the classification performance. We expect that the relation validation system would learn and perform better by training with and testing on more data accordingly. Table 6.13 represents the statistics of training and test dataset, F-score (F) and accuracy (Acc.) regarding both hard and relaxed constraints. This table shows the scores obtained by Random Forest classifier which is trained by the best feature combination, i.e. Linguistic + F illerCredibility + Graph. Here we use a single word embeddings, GloVe for computing trigger-word based features since it results in better scores compared to other individual embeddings as described in Section 4.5 on Page 65.

Relaxed constraint significantly increases both training and test instances for all the relations as discussed in Section 6.3.1. The F-score and accuracy are gained over almost all the relations by relaxing the IN_SAME_SENTENCE constraint. In the results of the hard constraint dataset, we notice that several relations do not have any training examples (as per:children or per:country_of_death), or test data (as per:spouse, per:city_of_death, org:member_of ). We see that relaxed constraint results in better F-score for all the relations except per:parents and org:top_members_employees. We obtain overall F-score and accuracy of 51.5 and 78.2 accordingly by hard constraint. In contrast, the relaxed constraint improves these scores by around 12 and 6 points accordingly. We achieve overall F-score and accuracy of 63.3 and 84.8 accordingly by relaxing the constraint. Thus relaxation of the constraint of IN_SAME_SENTENCE relation between subject and object entities facilitates to train a model with more data that significantly improves the performance to classify the correct and wrong relations.

We also observe the impact of multiple word embeddings for relation validation task on the relaxed constraint datasets of 12 relations together. We use the best combination as described in Section 4.5 on Page 65 and include other features such as Filler Credibility, graph and syntactic dependency path length, dependency patterns and dependency pattern edit distance. A Random Forest classifier trained on KBP-2015 dataset and tested on KBP-2016 dataset results the precision, recall, F-score and accuracy of 54.5, 71.3, 61.8 and 83.3 accordingly. By employing multiple word embeddings we get around 1.2 points higher recall but the precision, F-score and accuracy are decreased by around 3, 1.5 and 1.5 points accordingly compared to the results presented in the relaxed constraint part of Table 6.13. Multiple word embeddings improve the recall by identifying trigger words of expressing relations but fails to achieve a better precision. As a consequence, it gets lower F-score and accuracy. However, in Section 4.5, we obtained better score by combining multiple word embeddings. The results would need further exploration to know why multiple wordembeddings provide a different behavior. Since trigger word features computed on GloVe and other features collectively gives better F-score, in the next experiments, we use only GloVe instead of multiple word embeddings.

1. Trigger word between entity mentions 2. Trigger word in the dependency path between entity mentions 3. Trigger word in the minimum subtree between entity mentions 4. Dependency pattern length Table 6.16 presents the classification scores where we observe that the combination of BL and proposed graph features outperforms the BL almost for all the relations except per:country_of_death. We obtain overall F-score of 58.60 by BL+Graph that is around 9 points higher than the BL. The experimental results also show that the combination of BL and dependency pattern edit distance (DPED) improves the overall F-score by 1.79 points over the BL. This combination achieves higher F-score for 7 relations (among 12) which indicates the effectiveness of DPED for relation validation task. Basically, we gain higher precision by allowing a slight drop of recall that results in better F-score over the BL. The best F-score is achieved by the combination of BL, DPED and graph (BL+DPED+Graph). This combination results overall F-score of 59.90 which is around 10 points higher than the BL. We observe that BL+DPED+Graph obtains higher F-score for 11 relations compare to the BL. For only one relation (per:country_of_death) the classification performance remains same as the BL.

We notice in Table 6.16 that BL+Graph and BL+DPED+Graph obtain a very high score for per:country_of_birth over the BL. Both BL+Graph and BL+DPED+Graph achieve an F-score of 88.89 which is around 69 points higher than the BL. The reason behind this result is that we have a very small number of true instances (total 5) for this relation compare to the number of false instances (total 260) (as shown in Table 6.17) and a high precision is resulted by discarding 231 false relations.

We achieve the highest precision almost for all the relations by BL+DPED+Graph. BL+DPED+Graph achieves an overall precision of 66.02 that is around 21 points higher than the BL that indicates the proposed features discard a large number of false relation instances correctly. A little drop of recall is caused by BL+DPED+Graph which is around 1 point lower than the BL. The recall of 55.73 and 54.82 are resulted by the BL and BL+DPED+Graph accordingly. The drop of recall indicates the limitations of graph features to hold the semantic evidence of some relations. Table 6.17 illustrates the confusion matrix resulted by BL and BL+DPED+Graph where we compare the number of true positive (TP), false negative (FN), false positive (FP), true negative (TN) and accuracy (Acc.). We see that the baseline and BL+DPED+Graph methods correctly classify overall 618 and 608 true relation instances accordingly among 1, 109.

Error Analysis

We inspect some relation justifying snippets for error analysis. Table 6.18 presents classification results on some claimed relations from the test data that helps to realize the performance of our RV model. The first and second rows show two correctly classified true claims of spouse and children relation accordingly. Furthermore, a false claim of spouse relation has been detected as wrong as shown in the third row.

In contrast, our system fails to correctly classify a true children relation as shown in the fourth row. However, our system achieves overall decent scores compared to the baseline. All the experimental results on relation validation task show that global information about the entities captured by the community-graph based features are significantly effective for relation extraction task.

Knowledge Base Population by Employing Relation Validation Models

Our objective is to populate a knowledge base by using the outputs of different slot filling systems. Since slot filling systems generate a lot of wrong relation hypotheses, we want to discard the false relations without affecting the true ones. Therefore, we are interested to know whether the validation step allows for building a better knowledge base. Here we employ our relation validation models for KBP task. We use the slot filling model presented in Section 3 on Page 72 regarding this task. For evaluating the KBP task, TAC defines a set of ground truths for all the query slots that contains different correct filler values for each of the queries. A filler value (object) is considered as correct if the excerpt containing the subject and object justifies their relation, otherwise wrong. The KBP system should not repeat an object for the same slot. If the system repeats an object for the same slot only one instance of that object would be considered as correct and others would be wrong.

We measure the KBP performances of different systems on our test dataset for comparison. Here, the results do not indicate the official KBP scores. Since we focus on some selected relations, the results in this study differ from the official scores even though we follow similar scoring method. The upper part of Table 6.19 shows the official scores of the top 3 TAC KBP systems where the best F-score of 26.31 is achieved by System-1. On the other hand, System-2 and System-3 obtain the F-score of 21.53 and 18.06 accordingly. However, these three systems obtain the F-scores of 28.12, 28.03 and 27.35 accordingly on our test dataset for the selected relations (see System-i in the middle part of Table 6.19).

Since different relation extraction systems can be employed for KBP task, we can use the trustworthy filler credibility feature to take advantage of the agreements on the outcomes by several relation extraction systems. Therefore, we built a relation validation model by using a single trustworthy feature. Since the best performance of validating relations is achieved by F iller Credibility + Linguistic + Graph features, we use the relation validation model trained by this feature combination for KBP task.

In the lower part of Table 6.19, we see the voting (Filler Credibility) based KBP system obtains an F-score of 22.83 that indicates the importance of this feature. Interestingly, the F iller Credibility + Linguistic + Graph based KBP system achieves an F-score of 29.61 which is higher than each individual KBP system. We also observe that F iller Credibility + Linguistic + Graph based KBP system achieves the highest precision of 38.51 that is almost 2 points higher than the best KBP system. The precision improvement indicates that this model discards many wrong relations which are resulted by different relation extraction systems. Moreover, F iller Credibility + Linguistic + Graph based KBP system obtains the recall of 24.05 that is around 1.27 point higher than the best relation extraction based KBP system and around 3 points higher than the voting based KBP system. These results justify that our system enables to fill more relations in knowledge base than the existing ones for the trigger-dependent relations.

An Experiment of Unsupervised Relation Validation and Knowledge Base Population

In some cases, unsupervised learning becomes very important, specially if no annotated data is available. We aim at exploring graph algorithm to exploit our graph representation for relation validation and KBP tasks in an unsupervised fashion.

We hypothesize that the graph of entities gives some clues on how two related entities are connected to each other via their common neighbors. A graph of entities facilitates to find such clues. Moreover, it helps to rank the entities by employing a ranking algorithm. We assume that for a query relation (R, E q , ?), a correct candidate-object will get higher ranking score than the score of a wrong one. If multiple correct objects are allowed for a query relation, we expect that the correct ones will get comparatively higher ranks than the wrong ones. Therefore, a threshold of rank has to be defined to choose the correct objects of a query relation.

We use a graph based candidate ranking model as shown in Fig. 6.1. This method takes the subject (E q ) and candidate entities (E c1 , E c2 , ..., E cn ) of a relation hypothesis as the input. Then it models a graph of entities with all the relation hypotheses and ranks the candidates. Finally, top-ranked candidates which satisfy a predefined threshold (th) are considered as the correct objects of that relation. where, W (v) is the weight given to node, v

Graph Modeling

Our objective is to rank the candidate objects of a query relation by using PageRank algorithm. Such method has been successfully used in entity linking task [START_REF] Pershina | Personalized Page Rank for Named Entity Disambiguation[END_REF]. We construct a special graph of entities for the ranking task.

We represent each candidate object as a relation hypothesis with the subject entity as shown in Fig. 6.2. For example, (E q , E c i) refers to a claimed relation hypothesis where E q and E c i indicate the subject and a candidate respectively. The other entities linked to a relation hypothesis denote the community members of the corresponding candidate. For instance, M and N are the community members of candidate E c 2. We make some modifications in this graph which are reflected in Fig. 6.3. For example, any entity (e.g. P ) which is not a community member of any candidate object but connected to the subject entity, is linked to all the candidate entities. In Fig. 6.3, P is connected to the three candidates. Moreover, if there is a link between two candidate objects, the link is removed to avoid the influence of a candidate to another one. Finally, the subject entity is removed from the graph as Fig. 6.3 shows that it does not contain the subject entity and its links to the candidate entities. We finalize this graph by expanding the community of each candidate up to level 3. We take the maximum score among the three options: trigger word between entity mentions, trigger word in the dependency path and trigger word in the minimum subtree (Section 4.4 on Page 63).

W (E c i) = Sc i n i=1 Sc i (6.4)

The weights of the candidate nodes are normalized. For example, E c = {E c1 , E c2 , ..., E cn } is the set of candidate objects of a relation and S = {Sc 1 , Sc 2 , ..., Sc n } refers to the set of linguistic confidence scores of the corresponding candidates. We define the weight, W (E c i) of a candidate, E c i by Eq. 6.4. Moreover, a small weight of 0.01 is assigned to each of the non-candidate nodes in the graph in order to take them into account for scoring the candidates.

Evaluation

We evaluate the unsupervised relation validation model on the responses of 105 queries of trigger-dependent relations from the KBP-2016 dataset. We select these queries because each of the queries has been responded by at least one correct and one wrong objects. If all the responses of a query are wrong, it does not make any sense to rank them.

In total there are 1, 223 correct and 3, 864 wrong responses to these queries by different systems. Firstly, we compute accuracy at N = {1, 2, 3, 4, 5} when the total number of responses to a query is greater than N . For example, A@1 means the percentage of queries that get at least one correct response at the top ranked position when total number of responses is at least 2. Similarly, A@5 counts the percentage of queries get at least one correct response anywhere in the top 5 positions when However, for other relations (e.g. org:member_of, org:city_of_headquarters etc.), many wrong relations have been discarded but a large number of correct relations has not been preserved. As a result, they get very low F-scores. From these results, we observe that even though this unsupervised ranking based relation validation model discards a large number of wrong relations, it fails to preserve many correct ones. Now, we construct a knowledge base (for the selected 12 relations) in an ensemble fashion by using the relations which have been classified as correct by the ranking model. The upper part of Table 6.23 shows the KBP scores resulted for different ranking thresholds. We see that the threshold of 5 achieves the best recall (28.69) and F-score (21.02). The best precision is obtained by the threshold of 2 which results around 3.5 points lower F-score that the best one. We notice that the increasing of ranking threshold results in better recall and F-score but causes to drop of precision. We have noticed similar characteristics in the evaluation of relation validation task (see Table 6.21). In both tasks of relation validation and KBP, the ranking threshold of 5 achieves the best score compared to other threshold values. Although the ranking based ensemble system obtains the F-score of 21.02 (for ranking threshold of 5), still it gets a lower score than the top ranked KBP systems. The top three individual KBP systems obtain the F-score of 28.12, 28.03 and 27.35 (in decreasing order) accordingly (see the lower part of Table 6.23).

However, in our experiment of ranking based relation validation, we used the same threshold value for ranking the candidates of different relations. Different thresholds can be studied regarding different types of relations to observe whether 6.5. Summary 115 they can improve the relation validation performance.

Summary

We explored both supervised and unsupervised methods of relation validation task. Our experimental results show that the supervised model gets better score compared to the unsupervised model. Moreover, the supervised relation validation model contributes to populate a better knowledge base in an ensemble manner that outperforms the top ranked individual KBP systems. However, the ranking based unsupervised relation validation model gets a lower score than the individual KBP systems.

We used different types of features in our supervised relation validation model. Validating a semantic relation at the sentence level mostly depends on linguistic evidence such as the existence of trigger word between entity mention, in the syntactic dependency path, in the minimal subtree, length the syntactic dependency path, similarity of dependency patterns, clausal information, relation type regarding trigger dependency etc.

Trustworthy features such as confidence score, credibilities of the systems, documents and responded filler values collectively obtains a very good score specially when a classifier model trained and tested on the same year dataset (KBP-2015) and the relation hypotheses are generated by different systems. However, a classifier trained and tested on KBP-2015 and KBP-2016 datasets accordingly, does not result in good score by using confidence score and credibilities of the systems and documents as the features of relation validation. Our investigation finds that the KBP-2015 and KBP-2016 evaluation datasets differ significantly. Therefore, some the trustworthy features affect the relation validation performance badly. Moreover, our feature optimization method on a development dataset filters out two linguistic features which are clausal information and relation type regarding trigger dependency.

Trustworthy Filler Credibility as a voting feature obtains a good score for validating relations even though the relation validation model is trained and tested on different datasets. However, in order to be system independent, a relation validation method discards trustworthy filler credibility feature and relies on only linguistic features which are not sufficient to achieve a decent score. Thus, validating entity level relation requires global information at the entity level in addition to the linguistic evidence at the sentence level.

Global information about entities provides some clues how two related entities are associated in a collection when the entities in the collection are represented in a graph. A graph structure facilitates analyzing the communities of different entities. Moreover, it helps to compute several features such as network density, network similarity, mutual information, the influence of a node on another one etc. on the community graphs for validating a relation hypothesis between two entities. Construction of a graph of entities requires NER and computing graph features requires having the IN_SAME_SENTENCE link between two entities under inspection. Our system was unable to generate graph features for a large number of entity pairs. Our investigation suggested relaxing some constraints to increase the dataset with graph features. By relaxing these constraints we significantly increase the training and test datasets with graph features.

Experimental results show that proposed graph features significantly contribute to outperform the baseline model of relation validation when they are combined with some baseline features. Furthermore, a relation validation model with the proposed graph features achieves a better score over the best individual KBP system for some trigger-dependent relations. All the experimental results signify the effectiveness of the proposed graph features in both tasks of relation validation and knowledge base population. rapidly in text format which is readable by both human and machine. However, the huge source of information is mostly unstructured. Collecting important and useful information from the unstructured texts is a challenging and interesting task in NLP research. Knowledge Base Population is a special kind of information extraction task that aims at creating a collection of facts of the world. A Knowledge Base facilitates a user to retrieve necessary information on demand very easily. It also helps both human and machine to learn reasoning among the related facts. Manually populating a knowledge base from a large volume of unstructured information sources is a very difficult and time consuming task. Therefore, automatic knowledge base population comes into play. Automatic KBP task requires extraction of semantic relations from texts. Semantic relations can be classified into two distinct types: trigger-dependent and trigger-independent. In order to express a trigger-dependent relation between two entities in a sentence, there must exist a trigger word between or around the entities. In contrast, the existence of trigger word is not mandatory for expressing a trigger-independent relation. Existing relation extraction systems generate a large number of false relations that lead to a noisy and inaccurate knowledge base. Therefore, filtering false relations gets importance to construct a more accurate knowledge base.

In this research, we focused on validating trigger-dependent relation hypotheses which have been generated by different systems. We considered relation validation as a binary classification task. Several classifier models were trained by different combinations of features to classify a claimed relation as true or false.

We observed that there are some similarities between the tasks of relation validation and relation extraction specially in terms of linguistic analysis. Both the tasks inspect existence of trigger words between or around a pair of entity mentions. Therefore, we inherited a couple of linguistic features from the literature of relation extraction. We analyzed the lexicons, syntactic dependency path and dependency parse tree of the relation justifying text of a claimed relation to validate it. The presence of trigger words had been inspected between the pair of entity mentions, in the shortest dependency path and in the minimum sub-tree. We also took into account length of the shortest dependency path between two entities.

In our primary study, we collected some trigger words of different relations from a small volume of labeled data. Some relations are expressed by a large number of trigger words that cannot be captured from a small dataset. Therefore, we employed a word embeddings to identify the unknown trigger words of a relation. Basically, we computed cosine similarity between the vectors of a known trigger and a word between a pair of entity mentions. A known trigger gets 1 as the similarity score. A high similarity score of a word to a known trigger of a relationship indicates that there is a high chance of that particular word to be a trigger of that particular relation. We defined the features of existence of trigger words by the trigger word similarity scores. We noticed that a classifier model trained with only linguistic features cannot result a good score for entity level relation validation task.

Global association among different entities provides useful information about their relatedness that cannot be captured by linguistic analysis. Two related entities share some common ideas and resources with their neighbors. Therefore, we proposed to explore the communities of two entities which were claimed to be in a relationship. We constructed a graph of entities by extracting different types of named entities from a given text corpus. Entities, documents and sentences were presented by graph nodes. Moreover, the coexistence of a pair of entities in a sentence was denoted by an IN_SAME_SENTENCE relational edge. The associations among the entities, mentions, sentences and documents were maintained by distinct relational edges as well. This graph facilitated us to find the community of an entity based on IN_SAME_SENTENCE relation. We proposed to compute several features on the community graphs which are network density, network similarity, eigenvector centrality and mutual information. These graph based features provided more clues in addition to the linguistic features to decide whether two entities are in a true relationship.

Our experimental results showed that the proposed features significantly improved the performance in relation validation over some baseline linguistic features. Our relation validation model discarded a large number of wrong relations. Furthermore, we employed our relation validation model to populate a knowledge base in an ensemble fashion. Our relation validation based ensemble system outperformed the best slot filling system in KBP task for some trigger-dependent relations.

Future Work

We aimed at discarding a large part of the wrong relation hypotheses by validating the outcomes of different relation extraction systems. Although our relation validation system outperforms some baselines, still it fails to achieve a very high precision. Moreover, we notice that the relation validation model discards some true relations that causes the drop of recall. Still there are many issues to improve our relation validation system that we could not focus due to various shortcomings. Both of linguistic and graph analysis can be further investigated to achieve a better performance.

• Our system learned trigger words and syntactic dependency patterns of various relations from a very small amount of labeled dataset. In supervised learning, a system requires to be trained with a large number of labeled data in order to achieve a very high performance.

• We did not focus on trigger-independent relations. Validating a trigger-independent relation becomes harder due to lack of semantic information. Such relations mostly rely on syntactic patterns. Therefore, syntactic patterns can be explored more for validating trigger-independent relations.

• Some relations such as person and children share common trigger words that cause difficulty in relation validation task. In such cases, learning directionality of relation is very important. We did not focus on this issue in this thesis that can be studied in future.

• A long sentence contains more information compared to a short one. If the distance between two related entity mentions is very long, validation of the relationship is affected by noise. Moreover, many relation expressing sentences are not grammatically correct specially for discussion_forum data. The linguistic analyzer such as dependency parser fails to analyze a long or grammatically incorrect sentences properly. Therefore, it can be investigated how to capture useful information from long and grammatically incorrect sentences.

• Construction of entity graph relies on recognition of named entity recognition from texts. We noticed that existing NER tools fail to detect many named entities. Sometimes, the type of a detected named entity is not correct. Moreover, co-references of the named entities are not resolved during construction of the entity graph. Named entity disambiguation is an important prerequisite for constructing an entity graph. We did not evaluate our entity disambiguation method. These issues can be further studied to construct a more precise and rich graph.

• In our system, time complexity is very high for extracting community of an entity and for computing features on the community graphs. Efficient algorithms can be explored to overcome this limitation.

• In recent years, neural networks have been very effective and popular for solving NLP related problems. Neural network based learning systems do not require explicit feature engineering. In this thesis, we did not use any neural network based technique for validating relations. Therefore, it could be a good idea to explore neural networks for relation validation task.

• We performed only one experiment for unsupervised relation validation. Due to time limitation, we could not explore in depth of unsupervised learning. It can be further studied for relation validation task.

Community graph based features have shown a great positive impact on relation validation task specially when they are combined with some baseline linguistic features. Moreover, these features have contributed to populating a more accurate knowledge base as well. The proposed features can also be used in relation extraction task to achieve a better precision. However, we have addressed some drawbacks that could be improved further to achieve a better performance in both relation validation and knowledge base population tasks.

  the Training and Testing Datasets . . . . . . . . . 6.3.2 Relation Validation Models . . . . . . . . . . . . . . . . . 6.3.3 Knowledge Base Population by Employing Relation Validation Models . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 An Experiment of Unsupervised Relation Validation and Knowledge Base Population . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4.1 PageRank Algorithm . . . . . . . . . . . . . . . . . . . . . 6.4.2 Graph Modeling . . . . . . . . . . . . . . . . . . . . . . . 6.4.3 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . 6.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Conclusion and Future Work 7.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bibliography xvii List of Figures 1.1 Community graph . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 A graph with nodes and links . . . . . . . . . . . . . . . . . . . . . 3.2 A graph with two entity nodes and their relationship . . . . . . . . . 3.3 Neo4j graph with different types of nodes and links . . . . . . . . . 3.4 A subgraph extracted from the Neo4j graph (Fig. 3.3) by performing the query of Ex. 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Association graph (in the bottom part) that enables to build the community graph (in the top part) . . . . . . . . . . . . . . . . . . . . . 3.6 Community graph for realizing different measurements . . . . . . . 4.1 Syntactic dependency graph . . . . . . . . . . . . . . . . . . . . . 4.2 Syntactic dependency graph of two sentences mentioning spouse relationship between two pairs of persons . . . . . . . . . . . . . . . 4.3 Predictive models of word embedding

  . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Finding trigger words in the dependency path . . . . . . . . . . . . 4.6 Finding trigger words in the minimum subtree . . . . . . . . . . . . 5.1 System overview of the relation validation model . . . . . . . . . . 5.2 Pipeline of processing the XML formatted source files . . . . . . . 5.3 Compilation of assessed snippets from the queries, responses, assessments and corpus . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 A model of confusion matrix for binary classification . . . . . . . . 6.1 Unsupervised candidate ranking model . . . . . . . . . . . . . . . . 6.2 Entity graph with relation hypotheses . . . . . . . . . . . . . . . . 6.3 Modified graph for ranking the candidate entities by PageRank . . . xix List of Tables

2. 1

 1 PERSON and ORGANIZATION templates of scenario template task of MUC-6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Slots of PERSON and ORGANIZATION for the task of KBP slot filling in 2014 (Surdeanu and Ji, 2014) . . . . . . . . . . . . . . . . 2.3 TAC official scores of some top ranked slot filling systems in recent years . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Relation extraction performance by different methods on different datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Some top ranked SFV systems in recent years . . . . . . . . . . . . 4.1 Trigger-dependent and trigger-independent relations . . . . . . . . . 4.2 Statistics of the collected dependency patterns and trigger words . . 4.3 Relation expressing snippets with trigger words (words in bold font indicate trigger words) . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Characteristics of different word-embeddings . . . . . . . . . . . . 4.5 Standard deviation of trigger-word similarity scores for different relations measured on different word-embeddings . . . . . . . . . . . 4.6 Performance of relation validation by different word-embeddings (trained on KBP-2015 dataset and tested on KBP-2016 dataset) . . . . . . . 5.1 Relation validation features . . . . . . . . . . . . . . . . . . . . . . 5.2 Number of documents in the KBP corpus of three different years . . 5.3 Statistics of the entities in the two graphs . . . . . . . . . . . . . . 5.4 Statistics of the assessed responses to the queries of the KBP tasks in three different years . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1 Relation validation evaluation by cross validation on KBP-2015 dataset 6.2 Relation validation models (by cross-validation) used in KBP-2016 SFV task . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Official scores in KBP-2016 SFV ensemble task . . . . . . . . . . . 6.4 List of features used for analyzing differences between two datasets xx 6.5 p-values measured on 9 relations including all of their positive and negative examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.6 p-values measured on 9 relations by balancing the number of negative examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.7 Trustworthy feature investigation: models trained on KBP-2015 dataset and tested on on KBP-2016 dataset . . . . . . . . . . . . . . . . . . 6.8 Trustworthy feature investigation: 10-fold cross validation on a subset of KBP-2015 dataset . . . . . . . . . . . . . . . . . . . . . . . 6.9 Comparison of the slot filling responses of KBP-2015 and KBP-2016 datasets in terms of trigger words . . . . . . . . . . . . . . . . . . . 6.10 Selected relations (highly trigger-dependent, softly trigger-dependent and trigger-independent) for knowledge base population . . . . . . 6.11 Best features for relation validation . . . . . . . . . . . . . . . . . . 6.12 Evaluation of relation validation features on development data (trained on a small part of KBP-2015 dataset and tested on a small part of KBP-2016 dataset) . . . . . . . . . . . . . . . . . . . . . . . . . . 6.13 Comparison of relation validation performance between hard and relaxed constraints (in both cases, trained on KBP-2015 dataset and tested on KBP-2016 dataset) . . . . . . . . . . . . . . . . . . . . . 6.14 Relation validation performances by different classifiers on relaxed constraint dataset (trained on KBP-2015 dataset and tested on KBP-2016 dataset) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.15 Baseline linguistic features for evaluating relation validation models 6.16 Classification performances by different feature sets (trained on KBP-2015 dataset and tested on KBP-2016 dataset) . . . . . . . . . . . . 6.17 Comparison of the confusion matrices resulted by BL and BL+DPED+Graph (trained on KBP-2015 dataset and tested on KBP-2016 dataset) . . . 6.18 True positive (TP), true negative (TN) and false negative (FN) examples after validating relations . . . . . . . . . . . . . . . . . . . . . 6.19 KBP performances of different systems and relation validation models on KBP-2016 dataset . . . . . . . . . . . . . . . . . . . . . . . 6.20 Accuracy@N (on KBP-2016 dataset) by ranking the candidate objects of a relation . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.21 Confusion matrix and evaluation scores (on KBP-2016 dataset) after filtering lower ranked candidate objects (TP = true positive, FN = false negative, FP = false positive, TN = true negative, P = precision, R = recall and F = F-score) . . . . . . . . . . . . . . . . . . . . . . xxi 6.22 Evaluation scores relation-by-relation (on KBP-2016 dataset) after filtering lower ranked candidate objects for the ranking threshold of 5 (TP = true positive, FN = false negative, FP = false positive, TN = true negative, P = precision, R = recall and F = F-score) . . . . . . . 113 6.23 KBP performance by the ranking based relation validation model (upper part) and top 3 individual KBP systems (lower part) on KBP-2016 dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 Introduction 1.1 Research Objective . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  entities in the open domain. The semantic relation extraction methods are mostly supervised and a supervised method requires a lot of annotated training examples. Unfortunately, sufficient annotated examples of different types of relations are not available. Moreover, in many cases, relations are expressed in multiple sentences where the entities are mentioned by coreferences. In such cases, resolving coreferences becomes very important. Unfortunately, existing coreference resolution systems do not achieve very high scores and generate a lot of noise. As a consequence, automatic KBP becomes a very challenging task. 6 Chapter 1. Introduction Ex 1.1: Relation extraction from text Chelsea Victoria, the daughter of Bill Clinton and Hillary Clinton got married to Marc Mezvinsky. Relations between the pairs of entities 1. (spouse, Chelsea Victoria, Marc Mezvinsky) 2. (spouse, Bill Clinton, Hillary Clinton) 3. (children, Bill Clinton, Chelsea Victoria) 4. (children, Hillary Clinton, Chelsea Victoria) 5. (parent, Chelsea Victoria, Bill Clinton) 6. (parent, Chelsea Victoria, Hillary Clinton)

  Ex 1.2: Responses to a query of spouse relation relation name: spouse subject entity: Barack Obama Response 1: Michelle Obama Michelle Obama is married to Barack Obama, the 44th president of the United States... Response 2: Michelle Robinson In June 1989, Barack Obama met Michelle Robinson when he was employed as a summer associate... Response 3: Hillary Clinton Barack Obama visited the family of Hillary Clinton with his wife Michelle Obama... Our research focuses on validating relation hypotheses which are generated by different relation extraction systems.

FIGURE

  FIGURE 1.1: Community graph

  Supervised relation extraction systems with manually labeled training data have shown good results. However, in some special kind of relation extraction task, such as slot filling, no annotated data is provided for training a system. In such cases, systems employ distant supervision for training the relation extraction module. Such relation extraction methods cannot result in a sound score. As a consequence, slot filling system becomes harder and suffers to achieve a decent score. Moreover, traditional relation extraction systems focus on the relation between mentions of entities at the Chapter 2. Literature Review sentence level. In contrast, slot filling task for KBP requires extraction of a relation at the entity level with a justification of the relation at the sentence level. This is why slot filling task differs from traditional relation extraction task.

  for SFV task. Sammons et al. simply counted majority voting of the fillers for the same purpose and achieved F-score between 45.70 and 48.0. In contrast, Wang et al. used confidence scores of the responses by different slot filling systems to solve a constraint optimization problem for validating the responses. Moreover, contributions of the systems, referenced Chapter 2

  Slot filling systems for knowledge base population require semantic relation extraction. Supervised relation extraction systems lack sufficient labeled training data. Therefore, existing slot filling systems employ distant supervision for training the relation extraction component. Distant supervision labels sentences based on the facts in an existing knowledge base. Labeling sentences by distant supervision is often erroneous that creates noisy training data. A relation extractor trained with noisy data generates a large number of false relations. As a consequence, slot filling systems suffer to achieve a decent score.

  FIGURE 3.1: A graph with nodes and links

  FIGURE 3.3: Neo4j graph with different types of nodes and links

  FIGURE 3.4: A subgraph extracted from the Neo4j graph (Fig. 3.3) by performing the query of Ex. 3.1

Chapter 4 .

 4 Linguistic Characteristics of Expressing and Validating Relations Ex 4.1: Trigger-dependent and trigger-independent relation spouse (John, Julie):

Chapter 4 .

 4 Linguistic Characteristics of Expressing and Validating Relations Ex 4.2: POS tagging and segmentation of words in a sentence John likes the coffee shop where he first met Julie. NNP$ VBZ DT NN NN WRB PRP RB VBD NNP

  FIGURE 4.2: Syntactic dependency graph of two sentences mentioning spouse relationship between two pairs of persons

  between each pair of[(a,c,b),(a,b,c)],[(a,c,b), (a,c,d)],[(a,c,b),(b,c,d)] and take the minimum edit distance as a feature for relation validation. The algorithmic pseudo code of dependency pattern edit distance shown in Alg. 1. We expect lower edit distance score of a pattern P with reference to the existing patterns P of a relation R if P supports R. For example, in Fig.4.2a, (nsub, dobj) is a known pattern of expressing a spouse relation. Now, another sentence in Fig.4.2b mentions spouse relation between a different pair of words which gives a different pattern

  Calculate trigger word similarity 1: W : a context word from the sentence claiming to hold relation R 2: L : a list of trigger words of R 3: procedure GETTRIGGERWORDSIMILARITY(W, L)

  FIGURE 4.5: Finding trigger words in the dependency path

FIGURE 4 . 6 :

 46 FIGURE 4.6: Finding trigger words in the minimum subtree

Chapter 5 .

 5 Relation Validation FrameworkAlgorithm 3 Slot filling by relation validation 1: R : a query relation name or slot name 2: E q : subject entity of the query relation, R 3: E c = {E c1 , E c2 , ..., E cn } : list of candidate objects of the relation, R 4: S = {S c1 , S c2 , ..., S cn } : list of justifying sentences corresponding to each E ci E c 5: G =: a graph of entities 6: M =: a pre-trained binary claasifier 7: procedure GETSLOTFILLERVALUES(R, E q , E c , S, G, M ) 8:E c ← initialize an empty list 9:

  subject and object entities in the same clause of S Trigger word between entity mentions Trigger word in the dependency path between entity mentions Trigger word in the minimum subtree between entity

  FIGURE 5.3: Compilation of assessed snippets from the queries, responses, assessments and corpus

84

  Chapter 5. Relation Validation Framework the next chapter, we will do the experiments related to the relation validation and KBP tasks.

P

  FIGURE 6.1: Unsupervised candidate ranking model

FIGURE 6 . 2 :

 62 FIGURE 6.2: Entity graph with relation hypotheses

  FIGURE 6.3: Modified graph for ranking the candidate entities by PageRank

  age of World Wide Web (WWW), information is increasing very

  instance,(age, Barack Obama, 56) denotes the age of Barack The facts we are interested in are basically binary relations between two entities where the types of the entities can be person, organization, location etc.

	4			Chapter 1. Introduction
	Obama. Knowledge Base	# Entities # Relation Types Facts
	Wikidata	18 M	1,632	66 M
	YAGO2	9.8 M	114	447 M
	DBpedia	4.6 M	1,367	539 M
	Freebase	40 M	35,000	637 M
	Yahoo! Knowledge Graph 3.4 M	800	1,391 M
	Google Knowledge Graph 570 M	35,000	18,000 M

TABLE 1 .

 1

1: Size of some existing knowledge bases

  introduced template relation task by including LOCATION_OF, EM-PLOYEE_OF, and PRODUCT_OF slots to break out the relations or facts from the

	Object	Slot Name	Filler Description
		PER_NAME	"NAME"
		PER_ALIAS	"ALIAS"
	PERSON	PER_TITLE	"TITLE"
		OBJ_STATUS	{OPTIONAL}
		COMMENT	" "
		ORG_NAME	"NAME"
		ORG_ALIAS	"ALIAS"
		ORG_DESCRIPTOR	"DESCRIPTOR"
		ORG_TYPE	GOVERNMENT, COMPANY, OTHER
	ORGANIZATION	ORG_LOCALE	LOCALE-STRING {LOC_TYPE}
		ORG_COUNTRY	NORMALIZED-COUNTRY
		ORG_NATIONALITY NORMALIZED-COUNTRY-or-REGION
		OBJ_STATUS	{OPTIONAL}
		COMMENT	" "
	TABLE 2.1: PERSON and ORGANIZATION templates of scenario
		template task of MUC-6
	templates. Thus each slot represented a binary relation. A binary relation is defined
	by a tuple (r, arg1, arg2) where r, arg1 and arg2 refer to the relation name, subject
	and object accordingly. For example, (spouse, Barack Obama, Michelle Obama)
	indicates a spouse relationship between two persons Barack Obama and Michelle
	Obama.

Table 1 :

 1 List of slots for TAC KBP 2014 slot filling. The slot types can be: Name, i.e., named entities such as person, organizations, or locations; Value, i.e., numeric entities such as dates or other numbers; and String, which do not fall in any of the previous two categories. The list column indicates if the slot accepts multiple values for a given entity.

	Person Slots per:country of birth Name per:alternate names per:date of birth per:age per:stateorprovince of birth per:city of birth per:origin per:date of death per:country of death per:stateorprovince of death per:city of death per:cause of death per:countries of residence per:statesorprovinces of residence Name Yes Type List? Name Name Yes org:alternate names Organization Slots Value org:political religious affiliation Value org:top members employees Name org:number of employees members Value Type Name Yes List? Name Yes Name Yes Name org:members Name Yes Name org:member of Name Yes Name Yes org:subsidiaries Name Yes Value org:parents Name Yes Name org:founded by Name Yes Name org:date founded Value Name org:date dissolved Value String org:country of headquarters Name Name Yes org:stateorprovince of headquarters Name org:city of headquarters Name per:cities of residence Name Yes org:shareholders Name Yes per:schools attended Name Yes org:website String per:title String Yes per:employee or member of Name Yes per:religion String Yes per:spouse Name Yes per:children Name Yes per:parents Name Yes per:siblings Name Yes per:other family Name Yes per:charges String Yes
	consider the query "per:country of birth" for the
	entity "Michele Obama" and the texts:
	Michelle Obama started her career
	as a corporate lawyer specializing in
	marketing and intellectual property. She
	was born in Chicago.
	...
	Chicago is the third most populous city
	in the United States, after New York City
	and Los Angeles.

TABLE 2

 2 Slot filling task requires extraction of relation between entities. Relation extraction for slot filling differs to traditional relation extraction task like ACE to some extents

	.2: Slots of PERSON and ORGANIZATION for the task of
	KBP slot filling in 2014 (Surdeanu and Ji, 2014)
	be learned from the TAC KBP website 3 .
	In most cases, slots of the KBP slot filling task represent relations between a pair
	of named entities. Therefore, extraction of relation between named entities plays an
	important role in KBP slot filling task.
	Ex 2.1: An example of KBP slot filling query
	<query id="SF_004">
	<name>Nelson Mandela</name>
	<docid>a69c5c79caa4c2b2869775fabcbabc7f</docid>
	<beg>174</beg>
	<end>187</end>
	<enttype>per</enttype>
	<slot>per:spouse</slot>
	</query>

  and Zhang et al.

	Chapter 2. Literature Review
	(2016) employed such method to extract relations implicitly for slot filling task.
	Precision and recall of relation extraction are affected by distant supervision due
	to noisy training data and hand coded patterns accordingly

TABLE 2

 2

.5: Some top ranked SFV systems in recent years

  Graph Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Entity Graph and Graph Database . . . . . . . . . . . . . . . . . . 3.3 Graph Construction . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Measurements on Graph . . . . . . . . . . . . . . . . . . . . . . . Relation validation by Graph Analysis . . . . . . . . . . . . . . . . 3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	Chapter 3
	Entity Graph and Measurements for
	Relation Validation
	3.1

3.4.1 Node Centrality . . . . . . . . . . . . . . . . . . . . . . . . 3.4.2 Mutual Information . . . . . . . . . . . . . . . . . . . . . . 3.4.3 Network Density . . . . . . . . . . . . . . . . . . . . . . . 3.4.4 Network Similarity . . . . . . . . . . . . . . . . . . . . . . 3.5

  Entity Graph and Graph Database

	node id : 1 node type : entity	IN _SAM E_SEN T EN CE	node id : 2 node type : entity
	entity type : person entity : Barack Obama	document id : 2 sentence id : 3	entity type : location entity : U SA
	FIGURE 3.2: A graph with two entity nodes and their relationship

  Chapter 3. Entity Graph and Measurements for Relation Validation

	barack obama	IN_SAME_SENTENCE	michelle obama
	Barack	Obama	Michelle
	name.first	name.last	name.first
		Sentence-1
		Doc-1
	FIGURE 3.5: Association graph (in the bottom part) that enables to
	build the community graph (in the top part)
	number of components.
	Constraints 3.1: Person Type Entity Clustering
	1. Title(E 1 ) == Title(E 2 ) AND FirstName(E 1 ) == FirstName(E 2 ) AND
	LastName(E 1 ) == LastName(E 2 )
	2. Title(E 1 ) == Title(E 2 ) AND NOT HasFirstName(E 2 ) AND LastName(E 1 )
	== LastName(E 2 )
	3. Title(E 1 ) == Title(E 2 ) AND FirstName(E 1 ) == FirstName(E 2 ) AND NOT
	HasLastName(E 2 )
	4. NOT HasTitle(E 2 ) AND FirstName(E 1 ) == FirstName(E 2 ) AND
	LastName(E 1 ) == LastName(E 2 )
	5. NOT HasTitle(E 2 ) AND FirstName(E 1 ) == FirstName(E 2 ) AND NOT
	HasLastName(E 2 )
	6. NOT HasTitle(E 2 ) AND NOT HasFirstName(E 2 ) AND LastName(E 1 ) ==
	LastName(E 2 )

TABLE 4 .

 4 1: Trigger-dependent and trigger-independent relations In order to validate a relation, we inspect the existence of any trigger word of the claimed relation and analyze syntactic dependencies among different words in a relation justifying sentence.

  . A relation between head and dependent indicates a grammatical function such as subject, object etc.

		root	dobj				acl:relcl advmod
				det					nsubj
	nsubj			compound				advmod	dobj
	John NNP$	likes VBZ	the DT	coffee NN	shop NN		where WRB	he PRP	first RB	met VBD	Julie NNP
			FIGURE 4.1: Syntactic dependency graph
	Ex 4.3: Syntactic dependency
	John likes the coffee shop where he first met Julie.
		1	2	3	4	5	6	7	8	9	10
	function(head, dependent)
	nsubj(likes-2, John-1)
	root(ROOT-0, likes-2)
	det(shop-5, the-3)
	compound(shop-5, coffee-4)
	dobj(likes-2, shop-5)
	advmod(met-9, where-6)
	nsubj(met-9, he-7)
	advmod(met-9, first-8)
	acl:relcl(shop-5, met-9)
	dobj(met-9, Julie-10)

  between two words or entity mentions is captured in a sentence that claims R relationship between the words. We calculate Chapter 4. Linguistic Characteristics of Expressing and Validating Relations

	Relation Name Relation Name per:spouse per:spouse per:parents		Relation Expressing Snippet # Patterns # Triggers # Sentences 21 3 Alan Gross' wife, Judy, attended the event 37 Amanda Knox's father, Curt Knox, said he hopes
	per:parents per:children per:children per:country_of_birth per:country_of_death	25 Assaf Ramon, the son of Israel's first astronaut, Col. Ilan Ramon 8 47 16 8 Raul Castro was born on June 3, 1931 in the town of Biran in northern Cuba 19 Vladimir Ladyzhenskiy died late Saturday in southern Finland
	per:country_of_death per:employee_or_member_of per:country_of_birth org:top_members_employees org:member_of	8 Alan Gross was working as a contractor for the U.S. Agency 6 9 4 4 Tim Carpenter, national director of the Progressive Democrats of America 6 Taiwan is a senior member of the Pacific Asia Travel Association
	per:city_of_death org:city_of_headquarters	14 Qatalys, Inc. founded in 1995 and headquartered in Dallas 6 15
	per:city_of_birth per:employee_or_member_of 78 9 TABLE 4.3: Relation expressing snippets with trigger words (words 4 12 40 166 org:top_members_employees 49 20 in bold font indicate trigger words) 155 org:member_of 7 5 7 Algorithm 1 Calculate dependency pattern edit distance
	org:country_of_headquarters	21		6		46
	org:city_of_headquarters		26		6		42
	4: 5:	TABLE 4.2: Statistics of the collected dependency patterns and trig-initializes edit distance score with a large number Score ← 9999
						ger words
	Ex 4.4: Realization of edit distance
		1	2	3	4	5	6	7	8	9	10
		P	H	O	T	O	G	R	A	P	H
			A	U	T	O	G	R	A	P	H
		P	H	O	T	O	G	R	A	P	H

transform one string to another. An example of edit distance calculation is shown in Ex. 4.4 where there are two strings PHOTOGRAPH and AUTOGRAPH with lengths 10 and 9 accordingly. The string AUTOGRAPH can be transformed into PHOTO-GRAPH by minimum three modifications which are (i) inserting P at index 1 (ii) replacing A by H at index 2 (iii) replacing U by O at index 3. Edit distance calculation is widely used for different tasks like automatic spelling correction

[START_REF] Brill | An improved error model for noisy channel spelling correction[END_REF]

, comparing genetic sequences

[START_REF] Kim | TopHat2: accurate alignment of transcriptomes in the presence of insertions, deletions and gene fusions[END_REF]

etc. Since a relation is expressed in different sequences of dependency relations, we can compute the edit distance between a pair of dependency patterns to capture the deviation among different patterns.

Suppose, a list of existing dependency patterns are (a,b,c),

(a,c,d), (b,c,d)

for a relation R and a dependency pattern (a,c,b) 1: P : a dependency pattern claiming to hold relation R 2: Q : a list of pre-annotated patterns of R 3: procedure GETDEPENDENCYPATTERNEDITDISTANCE(P, Q)

66

  Chapter 4. Linguistic Characteristics of Expressing and Validating Relations

	Word-embeddings	Model	Training Corpus (Token Count) Vocabulary Dimension
	GloVe	word co-occurrence statistics	Wikipedia + Gigaword (6 B)	400 K	300
	GoogleNews-Vector word2vec word skip-gram	Google News (3 B)	3M	300
	FastText	word2vec character skip-gram Wikipedia (1.9 B)	2.5 M	300
	KBP-WordSG	word2vec word skip-gram	TAC KBP-2014 (11 B)	3.5 M	250
	KBP-CharSG	word2vec character skip-gram TAC KBP-2014 (11 B)	3.5 M	250
		TABLE 4.4: Characteristics of different word-embeddings

  Table4.5 shows standard deviations of trigger-word similarity scores of 11 trigger-dependent relations measured on different word-embeddings. In most cases, KBP-CharSG results in lower standard deviation compared to other embeddings. It gets the lowest standard deviation for 9 relations out of 11. In contrast, KBP-WordSG obtains the lowest standard deviation for only 2. Word-embeddings trained on TAC KBP-2014 result lower standard deviation compared to pre-trained embeddings on other corpora. An average standard deviation of 0.092 of 11 relations has been scored by KBP-CharSG. On the other hand, GloVe, GoogleNews-Vector, FastText and KBP-WordSG result average standard deviation of 0.120, 0.143, 0.128 and 0.126 respectively. According to these scores, it seems that a word-embeddings trained on TAC KBP-2014 corpus with word2vec character skip-gram model is more effective to find the trigger words of a relation. We can expect better performance from this word-embeddings to identify the unknown triggers of a relation.

	RelationName	GloVe GoogleNews-Vector FastText KBP-WordSG KBP-CharSG
	parents	0.109	0.118	0.106	0.132	0.071
	children	0.109	0.118	0.106	0.132	0.071
	spouse	0.082	0.131	0.081	0.118	0.060
	city_of_birth	0.078	0.131	0.132	0.106	0.107
	country_of_birth	0.078	0.131	0.132	0.106	0.107
	city_of_death	0.139	0.123	0.112	0.131	0.072
	country_of_death	0.139	0.123	0.112	0.131	0.072
	top_members_employees 0.156	0.179	0.149	0.157	0.127
	member_of	0.167	0.223	0.199	0.153	0.110
	city_of_headquarters	0.127	0.150	0.142	0.110	0.106
	country_of_headquarters	0.127	0.150	0.142	0.110	0.106
	Average	0.120	0.143	0.128	0.126	0.092

TABLE 4

 4

	.5: Standard deviation of trigger-word similarity scores for
	different relations measured on different word-embeddings

TABLE 5

 5

.1: Relation validation features

TABLE 5

 5

	.2: Number of documents in the KBP corpus of three dif-
	ferent years

  Table 5.2 shows the statistic of KBP corpus in different years. In KBP-2014 corpus, there are 2, 099, 319 documents in total where newswire, discussion_forum and web individually counts 1, 000, 257, 99, 063 and 999, 999 accordingly. A total of 49, 124 documents are counted in KBP-2015 corpus where 8, 938 are newswire and 40, 186 are discussion_forum data. On the other hand, KBP-2016 corpus consists of 30, 002 documents where both of newswire and discussion_forum individually counts 15, 001.

TABLE 5 .

 5 3: Statistics of the entities in the two graphs

TABLE 5 .

 5 4: Statistics of the assessed responses to the queries of the KBP tasks in three different years different information in 8 tab separated columns. Since the slot filling response and assessment file refer to the relation provenance text by document Id and offset, we collect the text snippets regarding the responses from the document corpus based on the document Id and offsets. A snippet is considered as positive or negative if the relation provenance assessment is C or W accordingly. We do not take into account the snippets that are assessed as S or L because they are either incomplete or contain excess information accordingly.

	Ex 5.7: Format of an assessed snippet
	column 1: Query Id
	column 2: response Id
	column 3: Unique run Id
	column 4: Relation name
	column 5: Query entity
	column 6: Object entity
	column 7: Relation provenance text
	column 8: Assessment of the relation provenance text (C or W)
	Table 5.4 represents the statistics of the compiled assessed queries and responses

  6.1 Participation to TAC KBP-2016 SFV Task . . . . . . . . . . . . . . 6.1.1 Evaluation of Different Feature Groups . . . . . . . . . . . 6.1.2 Relation Validation Models for KBP-2016 SFV Task . . . . 6.1.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 System Investigation . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.1 Statistical Difference Between TAC KBP Evaluation Datasets in 2015 and 2016 . . . . . . . . . . . . . . . . . . . . . . . 6.2.2 Impact of the Trustworthy Features . . . . . . . . . . . . . 6.2.3 Impact of Trigger Words in the Slot Filling Responses . . . 6.2.4 Identifying the Reason of Failure to Compute Graph Features 6.2.5 Conclusion and Plans for Improving the System . . . . . . . 6.3 Supervised Relation Validation and Knowledge Base Population . . 6.3.1 Enlarging the Training and Testing Datasets . . . . . . . . . 6.3.2 Relation Validation Models . . . . . . . . . . . . . . . . . 6.3.3 Knowledge Base Population by Employing Relation Validation Models . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 An Experiment of Unsupervised Relation Validation and Knowledge Base Population . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4.1 PageRank Algorithm . . . . . . . . . . . . . . . . . . . . . 6.4.2 Graph Modeling . . . . . . . . . . . . . . . . . . . . . . . 6.4.3 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . 6.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

TABLE 6

 6

.1: Relation validation evaluation by cross validation on KBP-2015 dataset

  .1.

	Relation Validation Model (Feature Set) Precision Recall F-score
	Trustworthy	83.85	84.41 84.13
	Linguistic	74.76	63.68 68.77
	Trustworthy+Linguistic	90.16	89.22 89.69
	Trustworthy+Linguistic+Graph	90.61	89.17 89.88
	TABLE 6.2: Relation validation models (by cross-validation) used in
	KBP-2016 SFV task

  Relation validation models evaluated by cross-validation and tested on different datasets resulted very different scores. Moreover, the relation validation model with graph features (Trustworthy+Linguistic+Graph) did not achieve the best score among four models. The performance of Trustworthy+Linguistic+Graph model on official evaluation indicated that the training data were not sufficient. Moreover, lower scores in the official evaluation of all the relation validation models (presented in the upper part of Table6.3) required to investigate the datasets and features used for training and evaluating the models.

	Trustworthy	22.02	26.13 23.90
	Linguistic	17.50	21.91 19.46
	Trustworthy+Linguistic	22.56	27.50 24.79
	Trustworthy+Linguistic+Graph	14.48	29.76 19.49
	Anonymous Participant-1	24.19	31.43 27.34
	Anonymous Participant-2	33.08	25.25 28.64
	Anonymous Participant-3	37.78	28.39 32.42
	TABLE 6.3: Official scores in KBP-2016 SFV ensemble task
	6.1.3 Conclusion

TABLE 6

 6

	.4: List of features used for analyzing differences between
	two datasets

  Table 6.6 represents the p-values of balanced datasets. Here

	92						Chapter 6. Experiments and Results
		A	B	C	D	E	F	G	H	I	J	K	L
	per:employee_member_of	0*	0.023 0.081 0.018 0.636 0.816 0.003* 0.024* 0*	0.029* 0*	0*
	org:country_of_HQ	0*	0.441 0.681 0.003* 0.048* 0*	0.002* 0.004* 0*	0.400 0*	0*
	org:top_member_employee 0.846 0*	0*	0.004* 0.436 0.590 0.787 0.043* 0.001* 0*	0*	0.066
	per:parent	0*	0*	0*	0*	0.011* 0.651 0*	0*	0*	0*	0*	0*
	per:countries_of_residence	0.820 0.676 0.118 0*	0.008* 0.094 0.087 0.026* 0*	0.015* 0.685 0*
	per:states_prov._of_residence 0*	0*	0*	0*	0.168 0.558 0.949 0.523 0*	0.033* 0*	0*
	org:state_province_of_HQ	0*	0.093 0.074 0*	0.061 0.092 0.086 0.739 0*	0.001* 0*	0*
	org:subsidiaries	0*	0*	0*	0*	0.011* 0.513 0*	0*	0*	0.170 0*	0*
	org:city_of_HQ	0.592 0*	0*	0*	0.014* 0.080 0.700 0.001* 0.097 0*	0.919 0.884
	count significant (*)	6	6	5	9	5	1	4	7	8	7	7	7
	TABLE 6.5: p-values measured on 9 relations including all of their
			positive and negative examples
	we notice the similar behavior of the two datasets as shown in Table 6.5 in terms of
	p-value measurement.
		A	B	C	D	E	F	G	H	I	J	K	L
	per:employee_member_of	0*	0.140 0.595 0.077 0.340 0.790 0.041* 0.337 0*	0.001* 0*	0*
	org:country_of_HQ	0.041* 0.852 0.265 0.027* 0.235 0*	0.050 0.038* 0*	0.524 0*	0*
	org:top_member_employee 0.219 0*	0*	0*	0.444 0.383 0.490 0.545 0.070 0*	0*	0.034*
	per:parent	0*	0*	0*	0*	0.700 0.053 0.006* 0.010* 0.001* 0.074 0.026* 0.001*
	per:countries_of_residence 0.358 0.437 0.831 0*	0.200 0.394 0.529 0.070 0	0.038* 0.951 0*
	per:states_prov._of_residence 0.013* 0.004* 0.034* 0.279 0.111 0.256 0.792 0.295 0.048* 0.861 0.001* 0.040*
	org:state_province_of_HQ	0*	0.400 0.281 0*	0.614 0.544 0.735 0.942 0*	0.003* 0*	0*
	org:subsidiaries	0*	0*	0*	0*	0.416 0.192 0.082 0*	0*	0.076 0*	0*
	org:city_of_HQ	0.738 0*	0*	0*	0.005* 0.012* 0.420 0.007* 0.176 0*	0.799 0.732
	count significant (*)	6	5	5	7	1	2	3	4	7	5	7	8
	TABLE 6.6: p-values measured on 9 relations by balancing the num-
				ber of negative examples

  Impact of Trigger Words in the Slot Filling ResponsesRelations are mostly expressed by trigger words and we use several features for validating relations based on the existence of any trigger word in a relation justifying sentence. We investigate the slot filling positive responses of KBP-2015 and KBP-2016 datasets whether there is any trigger word in a relation justifying sentence. The objective is to observe how two datasets differ in terms of trigger words. Here, we take into account only those slots that individually counts at least 30 positive responses.

	Feature Combination	Precision Recall F-score
	Trustworthy (All)		89.79	86.60 88.16
	Filler Credibility		70.65	65.32 67.88
	Filler Credibility + Linguistic 86.39	88.12 87.25
	Trustworthy (All) + Linguistic 94.36	94.03 94.20
	TABLE 6.8: Trustworthy feature investigation: 10-fold cross valida-
		tion on a subset of KBP-2015 dataset
	6.2.3 Dataset KBP-2015			Dataset KBP-2016
	Relation Name	# Responses # Resp. with Trigger (%)	# Responses # Resp. with Trigger (%)
	per:children	98	98	100% 85	85	100%
	per:city_of_birth	673	673	100% 163	163	100%
	per:country_of_birth	211	211	100% 30	25	83.3%
	per:country_of_death	120	120	100% 133	91	68.4%
	per:city_of_death	181	172	95.0% 38	38	100%
	org:top_member_employees 582	533	91.6% 228	215	94.3%
	org:founded_by	1,020	921	90.3% 57	47	82.5%
	per:parents	277	244	88.1% 114	114	100%
	per:spouse	243	211	86.8% 75	57	76.0%
	per:cities_of_residence	242	178	73.6% 71	9	12.7%
	per:employee_member_of	2,952	1,995	67.6% 609	316	52.2%
	org:member_of	316	165	52.2% 36	21	58.3%
	org:city_of_headquarters	781	331	42.4% 267	104	39.0%
	org:subsidiaries	232	93	40.1% 257	53	20.6%
	per:countries_of_residence	866	201	23.2% 617	49	7.9%
	org:parents	231	42	18.2% 87	2	2.3%
	org:country_of_headquarters 460	68	14.8% 195	32	16.4%
	org:shareholders	41	2	4.9% 41	0	0%

TABLE 6

 6

	.9: Comparison of the slot filling responses of KBP-2015
	and KBP-2016 datasets in terms of trigger words

  datasets accordingly. Then the best relation validation model is employed to populate a knowledge base.

		Dataset KBP-2015	Dataset KBP-2016
	Relation Name	# Responses with Trigger (%)	# Responses with Trigger (%)
	per:children	100%	100%
	per:city_of_birth	100%	100%
	per:country_of_birth	100%	83.3%
	per:country_of_death	100%	68.4%
	per:city_of_death	95.0%	100%
	org:top_member_employees	91.6%	94.3%
	per:parents	88.1%	100%
	per:spouse	86.8%	76.0%
	per:employee_member_of	67.6%	52.2%
	org:member_of	52.2%	58.3%
	org:city_of_headquarters	42.4%	39.0%
	org:country_of_headquarters	14.8%	16.4%

TABLE 6

 6 Usually, a relation between two entities is expressed when both of the entities are mentioned in the same sentence. Therefore, in our preliminary study, we constrained the system to find an IN_SAME_SENTENCE link (in the association graph of entities) between the subject and object entities of a relationship under observation for computing graph features. Thus we could compute graph features for around 14% of the responses. We obtained 2, 274 (827 positive and 1, 447 negative) instances for training from 130 queries of the 12 selected relations. In this setting, the test dataset counted 3, 429 (262 positive and 1, 167 negative) instances from 63 queries for the same number of relations. The number of training instances (positive and negative) for different relations are very different. Moreover, some relations (i.e. per:spouse, org:member_of ) count very small number of training instances and some (i.e. per:children, country_of_death) have no training example at all. Therefore, in the setting of hard constraint, we include training examples of some other relations (as shown in Table4.1) to the instances of the 12 selected relations. We obtained in total 3, 481 (1, 268 positive and 2, 213 negative) instances from 260 queries of 19 relations. Our experiment on this dataset obtains poor result because of a small number of training examples. Therefore, we defined a strategy for increasing the number of examples.We relax the constraint of having IN_SAME_SENTENCE relation between the subject and object entities of a relation. If the entity pairs are not connected by an IN_SAME_SENTENCE link in the graph we forcefully connect them by creating the link before computing graph features and delete the link after completing the feature computation of the entity pair. We delete this link after computing the graph features because it does not exist in the original graph. We want to keep the original graph unchanged so that a forcefully created link cannot affect other entity pairs during their graph feature computation. Relaxed constraint significantly increases both training and test instances for all the relations as shown in Table6.13. We obtain a training dataset that counts in total 14, 804 (5, 933 positive and 8, 871 negative) instances from 411 queries of the 12 selected relations. In a similar way, our test dataset counts 1, 109 and 4, 827 positive and negative instances accordingly from 223 queries.

	.10: Selected relations (highly trigger-dependent, softly
	trigger-dependent and trigger-independent) for knowledge base popu-
	lation
	6.3.1 Enlarging the Training and Testing Datasets
	Since many entity pairs do not have IN_SAME_SENTENCE relationship between
	them in the association graphs of these datasets, we cannot compute graph features
	for these entity pairs. Our investigation proposed to relax IN_SAME_SENTENCE
	constraint between two entities for computing graph features. In this section, we
	enlarge the training and test datasets by relaxing the IN_SAME_SENTENCE relation
	constraint.

TABLE 6 .

 6 15: Baseline linguistic features for evaluating relation validation models pattern edit distance) and graph features and their combinations. Since Random Forest results in the best score over several classifiers, we observe the performances of different feature sets by this classifier.

			BL			BL + DPED			BL + Graph		BL + DPED + Graph
	Relation Name	P	R	F	P	R	F	P	R	F	P	R	F
	per:parents	37.30 73.40 49.46 40.12 69.15 50.78 51.75 78.72 62.45 45.65 67.02 54.31
	per:children	62.22 75.68 68.29 60.87 75.68 67.47 70.00 75.68 72.73 93.33 75.68 83.58
	per:spouse	36.23 100 53.19 73.53 100 84.75 65.00 52.00 57.78 68.42 52.00 59.09
	per:country_of_death	98.55 94.44 96.45 98.55 94.44 96.45 97.50 54.17 69.64 98.55 94.44 96.45
	per:country_of_birth	11.43 80.00 20.00 12.90 80.00 22.22 100 80.00 88.89 100 80.00 88.89
	per:city_of_death	58.00 96.67 72.50 71.05 90.00 79.41 75.00 90.00 81.82 75.00 90.00 81.82
	per:city_of_birth	97.20 100 98.58 97.18 99.28 98.22 100 99.28 99.64 100 99.28 99.64
	per:employee_or_member_of 20.74 29.27 24.28 20.63 27.53 23.58 34.85 24.04 28.45 32.88 25.09 28.46
	org:top_members_employees 39.39 63.93 48.75 35.78 63.93 45.88 52.38 90.16 66.27 59.14 90.16 71.43
	org:member_of	28.57 44.44 34.78 38.71 44.44 41.38 48.00 44.44 46.15 50.00 44.44 47.06
	org:country_of_headquarters 52.17 25.71 34.45 59.02 25.71 35.82 75.93 29.29 42.27 75.93 29.29 42.27
	org:city_of_headquarters	50.00 44.27 46.96 60.14 43.23 50.30 86.67 47.4 61.28 89.69 45.31 60.21
	All Together	44.75 55.73 49.64 48.55 54.46 51.34 65.09 53.29 58.60 66.02 54.82 59.90

TABLE 6

 6

	.16: Classification performances by different feature sets
	(trained on KBP-2015 dataset and tested on KBP-2016 dataset)

TABLE 6

 6

	.17: Comparison of the confusion matrices resulted by BL
	and BL+DPED+Graph (trained on KBP-2015 dataset and tested on
	KBP-2016 dataset)

  That means BL+DPED+Graph discards 501 true relation instances which is around 1% more than the BL. However, the BL and BL+DPED+Graph correctly discard overall 4, 064 and 4, 514 false relation instances respectively among 4, 827. The rate of discarding false relation instances by BL+DPED+Graph Chapter 6. Experiments and Results Willem-Alexander married Maxima Zorreguieta Cerruti from Argentina and they have three daughters: Princess Catharina-Amalia, Princess Alexia and Princess Ariane. TP children(Margaret Thatcher, Mark)In a statement to the public, Thatcher's son Mark Thatcher said his twin sister Carol and the rest of their family had been overwhelmed by messages of support they had received from around the globe. 9% higher than the BL which contributes to increasing the overall precision and finally achieves a high accuracy. The BL model achieves the overall accuracy of 78.87% while BL+DPED+Graph achieves around 7.42% higher accuracy which is 86.29%. While observing the accuracy relation-by-relation we see a significant improvement achieved by BL+DPED+Graph over the BL for all the relations.

	Claimed Relation	Justification Sentence	RV
	spouse(Willem-Alexander, Maxima Zorreguieta Cerruti)
			TP
	spouse(Willem-Alexander, Alexia) children(Margaret Thatcher, Carol)	Willem-Alexander married Maxima Zorreguieta Cerruti from Argentina and they have three daughters: Princess Catharina-Amalia, Princess Alexia and Princess Ariane. In a statement to the public, Thatcher's son Mark Thatcher said his twin sister Carol and the rest of their family had been overwhelmed by messages of support they had received from around the globe.	TN FN
	TABLE 6.18: True positive (TP), true negative (TN) and false nega-
	tive (FN) examples after validating relations
	is around

TABLE 6 .

 6 23: KBP performance by the ranking based relation validation model (upper part) and top 3 individual KBP systems (lower part) on KBP-2016 dataset

	Ranking Threshold	Precision Recall F-score
	1	18.60	06.75	09.91
	2	20.81	15.91	17.56
	3	15.53	17.30	16.37
	4	17.07	24.05	19.97
	5	16.59	28.69	21.02
	KBP with the selected relations
	System-1	36.73	22.78	28.12
	System-2	32.07	24.89	28.03
	System-3	37.50	21.52	27.35

http://www.irt-systemx.fr/

http://www.irt-systemx.fr/en/project/imm/

http://wiki.dbpedia.org/

https://developers.google.com/freebase/

http://www.yago-knowledge.org/

http://www.nndb.com/

http://www.fashionmodeldirectory.com/

https://musicbrainz.org/

https://www.nist.gov/

https://tac.nist.gov/

http://www.cs.nyu.edu/cs/faculty/grishman/muc6.html

http://surdeanu.info/kbp2014/def.php

https://tac.nist.gov//2016/KBP/ColdStart/guidelines.html

https://tac.nist.gov//2016/KBP/SFValidation/index.html

https://neo4j.com/

http://www.expertsystem.com/fr/

https://wordnet.princeton.edu/

https://code.google.com/archive/p/word2vec/

https://nlp.stanford.edu/projects/glove/

https://github.com/mmihaltz/word2vec-GoogleNews-vectors

https://github.com/facebookresearch/fastText

Acknowledgements

express my gratefulness to IRT SystemX for financing my PhD. For the first two years of my PhD, I worked at SystemX as a team member of IMM project.

Chapter 6. Experiments and Results

Feature Group Feature Name Graph Network similarity between the communities of Eq and Ec of a relation hypothesis, (R, Eq, Ec) Network density by merging the communities of Eq and Ec of a relation hypothesis, (R, Eq, Ec)

Eigenvector centralities of Eq and Ec of a relation hypothesis, (R, Eq, Ec) Mutual information between the communities of Eq and Ec of a relation hypothesis, (R, Eq, Ec) Linguistic Dependency pattern minimum edit distance Dependency pattern length Trigger word between entity mentions Trigger word in the dependency path between entity mentions Trigger word in the minimum subtree between entity mentions

Trustworthy

Filler Credibility TABLE 6.11: Best features for relation validation

Relation Validation Models

In this section, we optimize different features to achieve the best results and we observe the effectiveness of adding more training data on relation validation task. Moreover, we measure the performance of different classifiers for binary classification and impact of the proposed features on validating relations.

Feature Optimization

In order to select the best features for validating the total number of responses is at least 6. Table 6.20 shows the A@N results. We observe that only 25 queries out of 105 get the correct response at the top ranked position. Thus the score of A@1 is 23.81. Similarly, the scores of A@2, A@3 and A@4 are 46.15, 57.84 and 66.67 accordingly. We get the best accuracy at A@5 which is 78.00.

We define different ranking thresholds ranging 1 to 5 (higher to lower) for selecting the correct responses. That means, for ranking threshold 5, if any candidate object gets a rank lower than 5, it would be considered as wrong. Then we observe the confusion matrix (true positive, false negative, false positive and true negative) and evaluation scores (precision, recall, F-score and accuracy) after filtering the lower ranked candidates in Table 6.21.

We want to discard a large number of false relation by keeping the correct ones. Therefore, we are interested in F-score because it makes a trade-off between the precision and recall. We notice that this ranking based relation validation method gets the best recall (63.81) and F-score (48.35) for a ranking threshold 5. This threshold results in a precision of 39.00. The ranking threshold of 2 gives the best precision of 46.24 but obtains F-score of 41.83 which is around 7 points lower than the best one. The ranking threshold of 4 obtains F-score of 47.92 which is almost near to the best one. This threshold results in the precision and recall of 40.84 and 57.98 accordingly.

On the other hand, the ranking threshold of 1 and 3 obtain the F-score of 29.86 and 41.14 accordingly. We compare the confusion matrix resulted by the ranking threshold of 4 and 5 since they achieve similar and higher F-scores. The ranking threshold of 5 discards 2, 647 wrong relations (out of 3, 865) by keeping 778 correct relations (out of 1, 223) successfully. In contrast, the ranking threshold of 4 discards 2, 837 wrong relations which counts 190 more instances than that counted by a threshold of 5. However, this threshold preserves 709 correct relations which counts 69 less instances than that resulted by the threshold of 5.

In Table 6.22 we present the evaluation scores relation by relation for the ranking threshold of 5. In some relations, per:spouse, per:city_of_birth and per:country_of_birth, many wrong relations (13, 52 and 65 accordingly) have been discarded by preserving all the correct ones. For these relations, resulted F-scores are 67.53,89.12 and 19.23 respectively. Moreover, in per:city_of_birth relation, 53 wrong relations (out of 89) have been removed where only one correct relation has been classified as wrong and it obtains the F-score of 61.86. Also in per:city_of_birth relation, many wrong relations have been discarded by losing some correct ones which obtain the F-score of 67.84. In per:country_of_birth relation, even though all the correct relations have been preserved, still the F-score is very low. The reason is that this relation counts We propose to extract a graph of entities from the overall corpus and to compute features on this graph that are able to capture some evidence of holding relationships between a pair of entities. In order to evaluate the relevance of the proposed features, we tested them on a task of relation validation which examines the correctness of relations that are extracted by different RE systems. Experimental results show that the proposed features lead to outperforming the state-of-the-art system.