Information extraction meets the Semantic Web: A survey

The goal of EEL is to extract and link entity mentions in a text with entity identifiers in a KB; some tools may additionally detect and propose identifiers for emerging entities that are not yet found in the KB [231,238,247]. In both cases, the first step is to mark entity mentions in the text that can be linked (or proposed as an addition) to the KB. Thus traditional NER tools – discussed in Appendix A.1 – can be used. However, in the context of EEL where a target KB is given as input, there can be key differences between a typical EEL recognition phase and traditional NER:

In this section, we thus begin by discussing the preparation of a dictionary and methods used for recognizing entities in the context of EEL.

We assume that a list of candidate identifiers has now been retrieved from the KB for each mention of interest using the techniques previously described. However, some KB labels in the dictionary may be ambiguous and may refer to multiple candidate identifiers. Likewise, the mentions in the text may not exactly match any single label in the dictionary. Thus an individual mention may be associated with multiple initial candidates from the KB, where a distinguishing feature of EEL systems is the disambiguation phase, whose goal is to decide which KB identifiers best match which mentions in the text. To achieve this, the disambiguation phase will typically involve various forms of filtering and scoring of the initial candidate identifiers, considering both the candidates for individual entity mentions, as well as (collectively) considering candidates proposed for entity mentions in a region of the text. Disambiguation may thus result in:

In some systems, phases of pruning and scoring may interleave, while in others, scoring is applied first and pruning is applied (strictly) thereafter.

A wide variety of approaches to disambiguation can be found in the EEL literature. Our goal, in this survey, is thus to organize and discuss the main approaches used thus far. Along these lines, we will first discuss some of the low-level features that can be used to help with the disambiguation process. Thereafter we discuss how these features can be combined to select a final set of mentions and candidates and/or to compute a support for each candidate identifier of a mention.

Table 3 provides an overview of how the EEL techniques discussed in this section are used by highlighted systems that: deal with a resource (e.g., a KB) using one of the Semantic Web standards; deal with EEL over plain text; have a publication offering system details; and are standalone systems. Based on these criteria, we exclude systems discussed previously that deal only with Wikipedia (since they do not directly relate to the Semantic Web). In this table, Year indicates the year of publication, KB denotes the primary Knowledge Base used for evaluation, Matching corresponds to the manner in which raw mentions are detected and matched with KB entities (Keyword refers to keyword search, Substring refers to methods such as prefix matching, LSH refers to Locality Sensitive Hashing), Indexing refers to the manner in which KB meta-data are indexed, Context refers to external sources used to enrich the description of entities, Recognition indicates how raw mentions are extracted from the text, and Disambiguation indicates the high-level strategies used to pair each mention with its most suitable KB identifier (if any). Regarding the latter dimension, Table 4 further details the features used by each system based on the categorization given in Section 2.2.1.

With respect to the EEL task, given the breadth of approaches now available for this task, a challenging question is then: which EEL approach should I choose for application X? Different options are associated with different strengths and weaknesses, where we can highlight the following key considerations in terms of application requirements:

In summary, no one EEL system fits all and EEL remains an active area of research. In order to exploit the inherent strengths and weaknesses of different EEL systems, a variety of ensemble approaches have been proposed. Furthermore, a wide variety of benchmarks and datasets have been proposed for evaluating and comparing such systems. We discuss ensemble systems and EEL evaluation in the following sections.

As previously discussed, different EEL systems may be associated with different strengths and weaknesses. A natural idea is then to combine the results of multiple EEL systems in an ensemble approach (as seen elsewhere, for example, in Machine Learning algorithms [80]). The main goal of ensemble methods is to thus try to compare and exploit complementary aspects of the underlying systems such that the results obtained are better than possible using any single such system. Five such ensemble systems are: NERD (2012) [ 263 ]

(Named Entity Recognition and Disambiguation) uses an ontology to integrate the input and output of ten NER and EEL tools, namely AlchemyAPI, DBpedia Spotlight, Evri, Extractiv, Lupedia, OpenCalais, Saplo, Wikimeta, Yahoo! Content Extractor, and Zemanta. Later works proposed classifier-based methods (Naive Bayes, k-NN, SVM) for combining results [265].

2.5. Evaluation

EEL involves two high-level tasks: recognition and disambiguation. Thus, evaluation may consider the recognition phase separately, or the disambiguation phase separately, or the entire EEL process as a whole. Given that the evaluation of recognition is well-covered by the traditional NER literature, here we focus on evaluations that consider whether or not the recognized mentions are deemed correct and whether or not the assigned KB identifier is deemed correct.

Given the wide range of EEL approaches proposed in the literature, we do not discuss details of the evaluations of individual tools conducted by the authors themselves. Rather we will discuss some of the most commonly used evaluation datasets and then discuss evaluations conducted by third parties to compare various selections of EEL systems.

Datasets: A variety of datasets have been used to evaluate the EEL process in different settings and under different assumptions. Here we enumerate some datasets that have been used to evaluate multiple tools:

Aside from being used for evaluation, we note that such datasets – particular larger ones like AIDA-CoNLL – can be (and are) used for training purposes. Moreover, although varied gold standard datasets have been proposed for EEL, Jha et al. [152] stated some issues regarding such datasets, for example, data consensus (there is a lack of consensus on standard rules for annotating entities), updates (KB links change over time), and annotation quality (regarding the number and expertise of evaluations and judges of the dataset). Thus, Jha et al. [152] propose the Eaglet system for detecting such issues over existing datasets.

Metrics Traditional metrics such as Precision, Recall, and F-measure are applied to evaluate EEL systems. Moreover, micro and macro variants are also applied in systems such as AIDA [321], DoSeR [336] and frameworks such as BAT [62] and GERBIL [303]; taking Precision as an example, macro-Precision considers the average Precision over individual documents or sentences, while micro-Precision considers the entire gold standard as one test without distinguishing the individual documents or sentences. Other systems and frameworks may use measures that distinguish the type of entity or the type of mention, where, for example, the GERBIL framework distinguishes results for KB entities from emerging entities.

Third-party comparisons: A number of third-party evaluations have been conducted in order to compare various EEL tools. Note that we focus on evaluations that include a disambiguation step, and thus exclude studies that focus only on NER (e.g., [135]).

As previously discussed, Rizzo and Troncy [264] proposed the NERD approach to integrate various Entity Linking tools with online APIs. They also provided some comparative results for these tools, namely Alchemy, DBpedia Spotlight, Evri, OpenCalais and Zemanta [263]. More specifically, they compared the number of entities detected by each tool from 1,000 New York Times articles, considering six entity types: person, organization, country, city, time and number. These results show that while the commercial black box tools managed to detect thousands of entities, DBpedia Spotlight only detected 16 entities in total; to the best of our knowledge, the quality of the entities extracted was not evaluated. However, in follow-up work by Rizzo et al. [265], the authors use the AIDA–CoNLL dataset and a Twitter dataset to compare the linking precision, recall and F-measure of Alchemy, DataTXT, DBpedia Spotlight, Lupedia, TextRazor, THD, Yahoo! and Zemanta. In these experiments, Alchemy generally had the highest recall, DataTXT or TextRazor the highest precision, while TextRazor had the best F-measure for both datasets.

Gangemi [112] presented an evaluation of tools for Knowledge Extraction on the Semantic Web (or tools trivially adaptable to such a setting). Using a sample text obtained from an extract of an online article of The New York Times30

Cornolti et al. [62] presented an evaluation framework for Entity Linking systems, called the BAT-framework.31

Trani et al. [40] and Usbeck et al. [303] later provided evaluation frameworks based on the BAT-framework. First, Trani et al. proposed the DEXTER-EVAL, which allows to quickly load and run evaluations following the BAT framework.32

Derczynski et al. [79] focused on a variety of tasks over tweets, including NER/EL, which has unique challenges in terms of having to process short texts with little context, heavy use of abbreviated mentions, lax capitalization and grammar, etc., but also has unique opportunities for incorporating novel features, such as user or location modeling, tags, followers, and so forth. While a variety of approaches are evaluated for NER, with respect to EEL, the authors evaluated four systems – DBpedia Spotlight, TextRazor, YODIE and Zemanta – over two Twitter datasets – a custom dataset (where entity mentions are given to the system for disambiguation) and the Meij dataset (where the raw tweet is given). In general, the systems struggled in both experiments. YODIE – a system with adaptations for Twitter – performed best in the first disambiguation task (note that TextRazor was not tested). In the second task, DBpedia had the best recall (0.48), TextRazor had the highest precision (0.65) while Zemanta had the best F-measure (0.41) (note that YODIE was not run in this second test).

Challenge events: A variety of EEL-related challenge events have been co-located with conferences and workshops, providing a variety of standardized tasks and calling for participants to apply their techniques to the tasks in question and submit their results. These challenge events thus offer an interesting format for empirical comparison of different tools in this space. Amongst such events considering an EEL-related task, we can mention:

We highlight the diversity of conferences at which such events have been hosted – covering Linguistics, the Semantic Web, Natural Language Processing, Information Retrieval, and the Web – indicating the broad interest in topics relating to EEL.

Many EEL approaches have been proposed in the past 15 years or so – in a variety of communities – for matching entity mentions in a text with entity identifiers in a KB; we also notice that the popularity of such works increased immensely with the availability of Wikipedia and related KBs. Despite the diversity in proposed approaches, the EEL process is comprised of two conceptual steps: recognition and disambiguation.

In the recognition phase, entity mentions in the text are identified. In EEL scenarios, the dictionary will often play a central role in this phase, indexing the labels of entities in the KB as well as contextual information. Subsequently, mentions in the text referring to the dictionary can be identified using string-, token- or NER-based approaches, generating candidate links to KB identifiers. In the disambiguation phase, candidates are scored and/or selected for each mention; here, a wide range of features can be considered, relying on information extracted about the mention, the keywords in the context of the mentions and the candidates, the graph induced by the similarity and/or relatedness of mentions and candidates, the categories of an external reference corpus, or the linguistic dependencies in the input text. These features can then be combined by various means – thresholds, objective functions, classifiers, etc. – to produce a final candidate for each mention or a support for each candidate.

2.7. Open questions

While the EEL task has been widely studied in recent years, many important research questions remain open, where our survey suggests the following:

Defining “Entity”: A foundational question that remains open is to rigorously define what is an “entity” in the context of EEL [152,180,270]. The traditional definition from the NER community considers mentions of entities from fixed classes, such as Person, Place, or Organization. However, EEL is often conducted with respect to KBs that contain entities from potentially hundreds of classes. Hence some tools and datasets choose to adopt a more relaxed notion of “entity”; for example, the KORE dataset contains the element dbr:Rock_music that might be considered by some as a concept and not an entity (and hence the subject of word sense disambiguation [216,224] rather than EEL). There is also a lack of consistency regarding how emerging entities not in the KB, overlapping entities, coreferences, etc., should be handled [180,270]. Thus, a key open question relates to finding an agreement on what entities may, should and/or must be extracted and linked as part of the EEL process.

We consider a term to be a textual mention of a domain-specific concept, such as “cancer”. Terms may also be composed of more than one word and indeed by relatively complex phrases, such as “inner planets of the solar system”. Terminology then refers more generically to the collection of terms or specialized vocabulary pertinent to a particular domain. In the context of TE, terms/terminology are typically understood as describing a domain, while in the context of KE, keyphrases are typically understood as describing a particular document. However, the extraction process of TE and KE are similar; hence we proceed by generically discussing the extraction of terms.

In fact, approaches to extract raw candidate terms follow a similar line to that for extracting raw entity mentions in the context of EEL. Generic preprocessing methods such as stop-word removal, stemming and/or lemmatization are often applied, along with tokenization. Some term extraction methods then rely on window-based methods, extracting n-grams up to a predefined length [100]. Other term extractors apply POS-tagging and then define shallow syntactic patterns to capture, for example, noun phrases (“solar system”), noun phrases prefixed by adjectives (“inner planets”), and so forth [60,85,220]. Other systems use an ensemble of methods to extract a broad selection of terms that are subsequently filtered [60].

There are, however, subtle differences when compared with extracting entities, particularly when considering traditional NER scenarios looking for names of people, organizations, places, etc.; when extracting terms, for example, capitalization becomes less useful as a signal, and syntactic patterns may need to be more complex to identify concepts such as “inner planets of [the] solar system”. Furthermore, the features considered when filtering term candidates change significantly when compared with those for filtering entity mentions (as we will discuss presently). For these reasons, various systems have been proposed specifically for extracting terms, including KEA [315], TExSIS [185], TermeX [76] and YaTeA [9] (here taking a selection reused by the highlighted systems). Such systems differ from EEL particularly in terms of the filtering process, discussed presently.

3.2. Filtering

Once a set of candidate terms have been identified, a range of features can be used for either automatic or semi-automatic filtering. These features can be broadly categorized as being linguistic or statistical; however, other contextual features can be used, which will be described presently. Furthermore, filtering can be applied with respect to a domain-specific dictionary of terms as taken from a reference KB or ontology.

Linguistic features relate to lexical or syntactic aspects of the term itself, where the most basic such feature would be the number of words forming the term (more words indicating more specific terms and vice-versa). Other linguistic features can likewise include generic aspects such as POS tags [73,123,173,215,220], shallow syntactic patterns [60,85,119,215], etc.; such features may be used in the initial extraction of terms or as a post-filtering step. Furthermore, terms may be filtered or selected based on appearing in a particular hierarchical branch of terminology, such as terms relating to forms of cancer; these techniques will be discussed in the next subsection.

As explained in Appendix x, producing and maintaining linguistic patterns/rules is a time consuming task, which in turn results in incomplete rules. Statistical measures look more broadly at the usage of a particular term in a corpus. In terms of such measures, two key properties of terms are often analyzed in this context [60]: unithood and termhood.

Unithood refers to the cohesiveness of the term as referring to a single concept, which is often assessed through analysis of collocations: expressions where the meaning of each individual word may vary widely from their meaning in the expression such that the meaning of the word depends directly on the expression; an example collocation might be “mean squared error” where, in particular, the individual words “mean” and “squared” taken in isolation have meanings unrelated to the expression, where the phrase “mean squared error” thus has high unithood. There are then a variety of measures to detect collocations, most based on the idea of comparing the expected number of times the collocation would be found if occurrences of the individual words were independent versus the amount of times the collocation actually appears [90]. As an example, Lossio-Ventura et al. [308] use Web search engines to determine collocations, where they estimate the unithood of a candidate term as the ratio of search results returned for the exact phrase (“mean squared error”), versus the number of results returned for all three terms (mean AND squared AND error). Unithood thus addresses a particular challenge – similar to that of overlapping entities in EEL (recalling “New York City”) – where extraction of partial mentions (such as “squared error”) may lose meaning, particularly if linkable to the KB.

The second form of statistical measure, called termhood, refers to the relevance of the term to the domain in question. To measure termhood, variations on the theme of the TF–IDF measure are commonly used [60,85,100,123,173,308], where, for example, terms that appear often in a (domain) specific text (high TF) but appear less often in a general corpus (high IDF) indicate higher termhood. Note that termhood relates closely to Topic Modeling measures, where the context of terms is used to find topically-related terms; such approaches will be discussed later.

Other features can rather be contextual, looking at the position of terms in the text [252]; such features are particularly important in the context of identifying keyphrases/terms that capture the domain or topic of a given document. The first such feature is known as the phrase depth, which measures how early in the document is the first appearance of the term: phrases that appear early on (e.g., in the title or first paragraph) are deemed to be most relevant to the document or the domain it describes. Likewise, terms that appear throughout the entire document are considered more relevant: hence the phrase lifespan – the ratio of the document lying between the first and last occurrence of the term – is also considered as an important feature [252].

A KB can also be used to filter terms through a linking process. The most simple such procedure is to filter terms that cannot be linked to the KB [162]. Other proposed methods rather apply a graph-based filtering, where terms are first linked to the KB and then the sub-graph of the KB induced by the terms is extracted; subsequently, terms in the graph that are disconnected [46] or exhibiting low centrality [144] can be filtered. This process will be described in more detail later.

3.3. Hierarchy induction

Often the extracted terms will refer to concepts with some semantic relations that are themselves useful to model as part of the process. The semantic relations most often considered are synonymy (e.g., “heart attack” and “myocardial infarction” being synonyms) and hypernymy/hyponymy (e.g., “migraine” is a hyponym of “headache” with the former being a more specific form of the latter, while conversely “headache” is a hypernym of “migraine”). While synonymy induces groups of terms with (almost exactly) the same meaning, hypernymy/hyponymy induces a hierarchical structure over the terms. Such relations and structures can be extracted either by analysis of the text itself and/or through the information gained from some reference source. These relations can then be used to filter relevant terminology, or to induce an initial semantic structure that can be formalized as a taxonomy (e.g., expressed in the SKOS standard [207]), or as a formal ontology (e.g., expressed in the OWL standard [136]), and so forth. As such, this topic relates heavily to the area of ontology learning, where we refer to the textbook by Cimiano [49] and the more recent survey of Wong et al. [316] for details; here our goal is to capture the main ideas.

In terms of detecting hypernymy from the text itself, a key method relies on distinguishing the head term, which signifies the more general hypernym in a (potentially) multi-word term; from modifier terms, which then specialize the hypernym [7,32,153,227,306]. For example, the head term of “metastatic breast cancer” is “cancer”, while “breast” and “metastatic” are modifiers that specialize the head term and successively create hyponyms. As a more complex example, the head term of “inner planets of the solar system” would be “planets”, while “inner” and “of the solar system” are modifying phrases. Analysis of the head/modifier terms thus allows for automatic extraction of hypernymic relations, starting with the most general head term, such as “cancer”, and then subsequently extending to hyponyms by successively adding modifiers appearing in a given multi-word term, such as “breast cancer”, “metastatic breast cancer”, and so forth.

Of course, analyzing head/modifier terms will miss hypernyms not involving modifiers, and synonyms; for example, the hyponym “carcinoma” of “cancer” is unlikely to be revealed by such analysis. An alternative approach is to rely on lexico-syntactic patterns to detect synonymy or hypernymy. A common set of patterns to detect hypernymy are Hearst patterns [130], which look for certain connectives between noun phrases. As an example, such patterns may detect from the phrase “cancers, such as carcinomas, …” that “carcinoma” is a hyponym of “cancer”. Hearst-like patterns are then used by a variety of systems (e.g., [7,55,119,153,162,192]). While such patterns can capture additional hypernyms with high precision [130], Buitelaar et al. [31] note that finding such patterns in practice is rare and that the approach tends to offer low recall. Hence, approaches have been proposed to use the vast textual information of the Web to find instances of such patterns using, for example, Web search engines such as Google [50], the abstracts of Wikipedia articles [298], amongst other Web sources.

Another approach that potentially offers higher recall is to use statistical analyses of large corpora of text. Many such approaches (e.g., [6,51,52,58]) are based, for example, on distributional semantics, which aggregates the context (surrounding terms) in which a given term appears in a large corpus. The distributional hypothesis then considers that terms with similar contexts are semantically related. Within this grouping of approaches, one can then find more specific strategies based on various forms of clustering [51], Formal Concept Analysis [52], LDA [58], embeddings [6], etc., to find and induce a hierarchy from terms based on their context. These can then be used as the basis to detect synonyms; or more often to induce a hierarchy of hypernyms, possibly adding hidden concepts – fresh hypernyms of cohyponyms – to create a connected tree of more/less specific domain terms.

Of course, reference resources that already contain semantic relations between terms can be used to aid in this process. One important such resource is WordNet [208], which, for a given term, provides a set of possible semantic senses in terms of what it might mean (homonymy/polysemy [304]), as well as a set of synonyms called synsets. Those synsets are then related by various semantic relations, including hypernymy, meronymy (part of), etc. WordNet is thus a useful reference for understanding the semantic relations between concepts, used by a variety of systems (e.g., [55,153,225,325], etc.). Other systems rather rely on, for example, Wikipedia categorizations [6,7,197] in combination with reference KBs. A core challenge, however, when using such approaches is the problem of word sense disambiguation [224] (sometimes called the semantic interpretation problem [225]): given a term, determine the correct sense in which it is used. We refer to the survey by Navigli [225] for discussion.

An alternative to extracting semantic relations between terms in the text is to instead rely on the existing relations in a given KB [6,46,144,305]. That is to say, if the terms (or indeed simply entities) can be linked to a suitable existing KB, then semantic relations can be extracted from the KB itself rather than the text. This approach is often applied by tools described in the following section (e.g., [46,144,305]), whose goal is to understand the domain of a document rather than attempting to model a domain from text.

3.4. Topic modeling

While the previous methods are mostly concerned with extracting a terminology from a corpus that describes a given domain (e.g., for the purposes of building a domain-specific ontology), other works are concerned with modeling and potentially identifying the domain to which the documents in a given corpus pertain (e.g., for the purposes of classifying documents). We refer to these latter approaches generically as Topic Modeling approaches [177,198]. Such approaches are based on analysis of terms (or sometimes entities) extracted from the text over which Topic Modeling approaches can be applied to cluster and analyze thematically related terms (e.g., “carcinoma”, “malignant tumor”, “chemotherapy”). Thereafter, topic labeling [5,144] can be (optionally) applied to assign such groupings of terms a suitable KB identifier referring to the topic in question (e.g., dbr:Cancer). Application areas for such techniques include Information Retrieval [241], Recommender Systems [155], Text Classification [143], Cognitive Science [244], and Social Network Analysis [259], to name but a few.

For applying Topic Modeling, one can of course first consider directly applying the traditional methods proposed in the literature: LSA, pLSA and/or LDA (see Appendix x for discussion). However, these approaches have a number of drawbacks. First, such approaches typically work on individual words and not multi-word terms (though extensions have been proposed to consider multi-word terms). Second, topics are considered as latent variables associated with a probability of generating words, and thus are not directly “labeled”, making them difficult to explain or externalize (though, again, labeled extensions have also been proposed, for example for LDA). Third, words are never semantically interpreted in such models, but are rather considered as symbolic references over which statistical/probabilistic inference can be applied. Hence a number of approaches have emerged that propose to use the structured information available in KBs and/or ontologies to enhance the modeling of topics in text. The starting point for all such approaches is to extract some terms from the text, using approaches previously outlined: some rely simply on token- or POS-based methods to extract terms, which can be filtered by frequency or TF–IDF variants to capture domain relevance [5,149,150], whereas others rather prefer entity recognition tools (which are subsequently mapped to higher-level topics through relations in the KB, as we describe later) [46,170,298].

With extracted terms in hand, the next step for many approaches – departing from traditional Topic Modeling – is to link those terms to a given KB, where the semantic relations of the KB can be exploited to generate more meaningful topics. The most straightforward such approach is to assume an ontology that offers a concept/class hierarchy to which extracted terms from the document are mapped. Thus the ontology can be seen as guiding the Topic Modeling process, and in fact can be used to select a label for the topic. One such approach is to apply a statistical analysis over the term-to-concept mapping. For example, in such a setting, Jain and Pareek [149] propose the following: for each concept in the ontology, count the ratio of extracted terms mapped to it or its (transitive) sub-concepts, and take that ratio as an indication of the relevance of the concept in terms of representing a high-level topic of the document. Another approach is to consider the spanning tree(s) induced by the linked terms in the hierarchy, taking the lowest common ancestor(s) as a high-level topic [144]. However, as noted by Hulpuş et al. [144], such approaches relying on class hierarchies tend to elect very generic topic labels, where they give the example of “Barack Obama” being captured under the generic concept person, rather than a more interesting concept such as U.S. President. To tackle this problem, a number of approaches have proposed to link terms – including entity mentions – to Wikipedia’s categories, from which more fine-grained topic labels can be selected for a given text [64,147,276].

Other approaches apply traditional Topic Modeling methods (typically pLSA or LDA) in conjunction with information extracted from the KB. Some approaches propose to apply Topic Modeling in an initial phase directly over the text; for example, Canopy [144] applies LDA over the input documents to group words into topics and then subsequently links those words with DBpedia for labeling each topic (described later). On the other hand, other approaches apply Topic Modeling after initially linking terms to the KB; for example, Todor et al. [298] first link terms to DBpedia in order to enrich the text with annotations of types, categories, hypernyms, etc., where the enriched text is then passed through an LDA process. Some recent approaches rather extend traditional topic models to consider information from the KB during the inference of topic-related distributions. Along these lines, for example, Allahyari [5] propose an LDA variant, called “OntoLDA”, which introduces a latent variable for concepts (taken from DBpedia and linked with the text), which sits between words and topics: a document is then considered to contain a distribution of (latent) topics, which contains a distribution of (latent) concepts, which contains a distribution of (observable) words. Another such hybrid model, but rather based on pLSA, is proposed by Chen et al. [46] where the probability of a concept mention (or a specific entity mention42

The result of these previous methods – applying Topic Modeling in conjunction with a KB-linking phase – is a set of topics associated with a set of terms that are in turn linked with concepts/entities in the KB. Interestingly, the links to the KB then facilitate labeling each topic by selecting one (or few) core term(s) that help capture or explain the topic. More specifically, a number of graph-based approaches have recently been proposed to choose topic labels [5,144,150], which typically begin by selecting, for each topic, the nodes in the KB that are linked by terms under that topic, and then extracting a sub-graph of the KB in the neighborhood of those nodes, where typically the largest connected component is considered to be the topical/thematic graph [5,150]. The goal, thereafter, is to select the “label node(s)” that best summarize(s) the topic, for which a number of approaches apply centrality measures on the topical graph: Janik and Kochut [150] investigate use of a closeness centrality measure, Allahyari and Kochut [5] propose to use the authority score of HITS (later mapping central nodes to DBpedia categories), while Hulpuş et al. [144] investigate various centrality measures, including closeness, betweenness, information and random-walk variants, as well as “focused” centrality measures that assign special weights to nodes in the topic (not just in the neighborhood). On the other hand, Varga et al. [305] propose to extract a KB sub-graph (from DBpedia or Freebase) describing entities linked from the text (containing information about classes, properties and categories), over which weighting schemes are applied to derive input features for a machine learning model (SVM) that classifies the topics of microposts.

Domain knowledge extracted through the previous processes may be represented using a variety of Semantic Web formats. In the ontology building process, induced concepts may be exported to RDFS/OWL [136] for further reasoning tasks or ontology refinement and development. However, RDFS/OWL makes a distinction between concepts and individuals that may be inappropriate for certain modeling requirements; for example, while a term such as “US Presidents” could be considered as a sub-topic of “US Politics” since any document about the former could be considered also as part of the latter, the former is neither a sub-concept nor an instance of the latter in the set-theoretic setting of OWL.43

Aside from these Semantic Web standards, a number of other representational formats have been proposed in the literature. The Lexicon Model for Ontologies, aka. LEMON [53], was proposed as a format to associate ontological concepts with richer linguistic information, which, on a high level, can be seen as a model that bridges between the world of formal ontologies to the world of natural language (written, spoken, etc.); the core LEMON concept is a lexical entry, which can be a word, affix or phrase (e.g., “cancer”); each lexical entry can have different forms (e.g., “cancers”, “cancerous”), and can have multiple senses (e.g., “ex:cancer_sense1” for medicine, “ex:cancer_sense2” for astrology, etc.); both lexical entries and senses can then be linked to their corresponding ontological concepts (or individuals).

Along related lines, Hellmann et al. [131] propose the NLP Interchange Format (NIF), whose goal is to enhance the interoperability of NLP tools by using an ontology to describe common terms and concepts; the format can provide Linked Data as output for further data reuse. Other proposals have also been made in terms of publishing linguistic resources as Linked Data. Cimiano et al. [54] propose such an approach for publishing and linking terminological resources following the Linked Data principles, combining the LEMON, SKOS, and PROV-O vocabularies in their core model; OnLit was proposed by Klimek et al. [166] as a Linked Data version of the LiDo Glossary of Linguistic Terms; etc. For further information, we refer the reader to the editorial by McCrae et al. [195], which offers an overview of terminological/linguistic resources published as Linked Data.

Based on the previously discussed techniques, in Table 5, we provide an overview of highlighted CEL systems that deal with the Semantic Web in a direct way, and that have a publication offering details; a legend is provided in the caption of the table. Note that in the Recognition and Filtering column, some systems delegate these tasks to external recognition tools – such as DBpedia Spotlight [200], KEA [315], OpenCalais,44

The approaches reviewed in this section might be applied for diverse and heterogeneous cases. Thus, comparing CEL approaches is not a trivial task; however, we can mention some general aspects and considerations when choosing a particular CEL approach.

We can conclude that comparing CEL approaches is complicated not only by the diversity of methods proposed and the goals targeted, but also by a lack of standardized, comparative evaluation frameworks; we will discuss this issue in the following subsection.

Given the diversity of approaches gathered together in this section, we remark that the evaluation strategies employed are likewise equally diverse. In particular, evaluation varies depending on the particular task considered (be it TE, KE, TM or some combination thereof) and the particular application in mind (be it ontology building, text classification, etc.). Evaluation in such contexts is often further complicated by the potentially subjective nature of the goal of such approaches. When assessing the quality of the output, some questions may be straightforward to answer, such as: Is this phrase a cohesive term (unithood/precision)? On the other hand, evaluation must somehow deal with more subjective domain-related questions, such as: Is this a domain-relevant term (termhood/precision)? Have we captured all domain-relevant terms appearing in the text (recall)? Is this taxonomy of terms correct (precision)? Does this label represent the terms forming this topic (precision)? Does this document have these topics (precision)? Are all topics of the document captured (recall)? And so forth. Such questions are inherently subjective, may raise disagreement amongst human evaluators [173], and may require expertise in the given domain to answer adequately.

Datasets: For evaluating CEL approaches, notably there are many Web-based corpora that have been pre-classified with topics or keywords, often annotated by human experts – such as users, moderators or curators of a particular site – through, for example, tagging systems. These can be reused for evaluation of domain extraction tools, in particular to see if automated approaches can recreate the high-quality classifications or topic models inherent in such corpora. Some such corpora that have been used include: BBC News46

Rather than employing a pre-annotated gold standard, an alternative strategy is to apply the approach under evaluation to a non-annotated corpus and thereafter seek human judgment on the output, typically in comparison with baseline approaches from the literature. Such an approach is employed in the context of TE by Nédellec et al. [227], Kim and Tuan [162], and Dolby et al. [85]; or in the context of KE by Muñoz-García et al. [220]; or in the context of TM by Hulpuş et al. [144] and Lauscher et al. [170]; and so forth. In such evaluations, TM approaches are often compared against traditional approaches such as LDA [5], PLSA [46], hierarchical clustering [127], etc.

Metrics: The most commonly used metrics for evaluating CEL approaches are precision, recall, and F 1 measure. When comparing with baseline approaches over a priori non-annotated corpora, recall can be a manually-costly aspect to assess; hence comparative rather than absolute measures such as relative recall are sometimes used [162]. In cases where results are ranked, precision@k measures may be used to assess the quality of the top-k terms extracted [308].

Particular tasks may be associated with specialized measures. Evaluations in the area of Topic Modeling may also consider perplexity (the log-likelihood of a held-out test set) and/or coherence [266], where a topic is considered coherent if it covers a high ratio of the words/terms appearing in the textual context from which it was extracted (measured by metrics such as Pointwise Mutual Information (PMI) [60], Normalized Mutual Information (NMI), etc.). On the other hand, for Terminology Extraction approaches with hierarchy induction, measures such as Semantic Cotopy [52] and Taxonomic Overlap [52] may be used to compare the output hierarchy with that of a gold-standard ontology.

In cases where a fixed number of users/judges are in charge of developing a gold-standard dataset or assessing the output of systems in an a posteriori manner, the agreement among them is expressed as Cohen’s or Fleiss’ κ-measure. In this sense, Randolph [254] provides a typical description (and usage examples) of the κ-measure, where the considered aspects are the number of cases or instances to evaluate, the number of human judges, the number of categories, and the number of judges who assigned the case to the same category.

Third-party comparisons: To the best of our knowledge, there has been little work on third-party evaluations for comparing CEL approaches, perhaps because of the diversity of goals and methods applied, the aforementioned challenges associated with evaluating CEL systems, etc. Among the available results, Gangemi [112] compared three commercial tools – Alchemy, OpenCalais and PoolParty – for Topic Extraction, where Alchemy had the highest F-measure. In a separate evaluation for Terminology Extraction – comparing Alchemy, CiceroLite, FOX [288], FRED [113] and Wikimeta – Gangemi [112] reported that FRED [113] had the highest F-measure.55

In this section, we gather together three approaches for extracting domain-related concepts from a text: Terminology Extraction (TE), Keyphrase Extraction (KE), and Topic Modeling (TM). While the first task is typically concerned with applications involving ontology building, or otherwise extracting a domain-specific terminology from an appropriate corpus, the latter two tasks are typically concerned with understanding the domain of a given text. As we have seen in this section, all tasks relate in important aspects, particularly in the identification of domain-relevant concepts; indeed, TE and TM further share the goal of extracting relationships between the extracted terms, be it to induce a hierarchy of hypernyms, to find synonyms, or to find thematic clusters of terms.

While all of the discussed approaches rely – to varying degrees – on techniques proposed in the traditional IE/NLP literature for such tasks, the use of reference ontologies and/or KBs has proven useful for a number of technical aspects inherent to these tasks:

On the other hand, such processes are also often used to create or otherwise enrich Semantic Web resources, such as for ontology building applications, where TE can be used to extract a set of domain-relevant concepts – and possibly some semantic relations between them – to either seed or enhance the creation of a domain-specific ontology [49,51,55,225,306,316].

3.9. Open questions

Although the tasks involved in CEL are used in varied applications and domains, some general open questions can be abstracted from the previous discussion, where we highlight the following:

Interrelation of Tasks: Under the heading of CEL, in this survey we have grouped three main tasks: Terminology Extraction (TE), Keyphrase Extraction (KE) and Topic Modeling (TM). These tasks are often considered in isolation – sometimes by different communities and for different applications – but as per our discussion, they also share clear overlaps. An important open question is thus with respect to how these tasks can be generalized, how approaches to each task can potentially complement each other or, conversely, where the objectives of such tasks necessarily diverge and require distinct techniques to solve.

The first step of REL often consists of identifying entity mentions in the text. Here we distinguish three strategies, where, in general, many works follow the EEL techniques previously discussed in Section 2, particularly those adopting the first two strategies.

In summary, entities may be extracted and linked before or after relations are extracted. Processing entities before relations can help to filter sentences that do not involve relationships between known entities, to find examples of sentences expressing known relations in the KB for training purposes, etc. On the other hand, processing entities after relations allows direct use of traditional RE and OpenIE tools, and may help to extract more complex (e.g., n-ary) relations involving entities that are not supported by a particular EEL approach (e.g., emerging entities), etc. These issues will be discussed further in the sections that follow.

In the context of REL, when extracting and linking entities, Coreference Resolution (CR) plays a very important role. While other EEL applications may not require capturing every coreference in a text – e.g., it may be sufficient to capture that the entity is mentioned at least one in a document for semantic search or annotation tasks – in the context of REL, not capturing coreferences will potentially lose many relations. Consider again Listing 3, where the second sentence begins “ He is known for ...”; CR is necessary to understand that “ He ” refers to “Bryan Lee Cranston”, to extract that he portrays “Walter White”, and so forth. In Listing 3, the portrays relation is connected (indirectly) to the node identifying “Bryan Lee Cranston”; this is possible because FRED uses Stanford CoreNLP’s CR methods. A number of other REL systems [97,116] likewise apply CR to improve recall of relations extracted.

4.2. Parsing relations

The next phase of REL systems often involves parsing structured descriptions from relation mentions in the text. The complexity of such structures can vary widely depending on the nature of the relation mention, the particular theory by which the mention is parsed, the use of pronouns, and so forth. In particular, while some tools rather extract simple binary relations of the form p ( s , o ) with a designated subject–predicate–object, others may apply a more abstract semantic representation of n-ary relations with various dependent terms playing various roles.

In terms of parsing more simple binary relations, as mentioned previously, a number of tools use existing OpenIE systems, which apply a recursive extraction of relations from webpages, where extracted relations are used to guide the process of extracting further relations. In this setting, for example, Dutta et al. [93] use NELL [214] and ReVerb [99], Liu et al. [182] use PATTY [223], while Soderland and Mandhani [285] use TextRunner [16] to extract relations; these relations will later be linked with an ontology or KB.

In terms of parsing potentially more complex n-ary relations, a variety of methods can be applied. A popular method is to begin with a dependency-based parse of the relation mention. For example, Grafia [109] uses a Stanford PCFG parser to extract dependencies in a relation mention, over which CR and EEL are subsequently applied. Likewise, other approaches using a dependency parser to extract an initial syntactic structure from relation mentions include DeepDive [233], PATTY [223], Refractive [98] and works by Mintz et al. [213], Nguyen and Moschitti [232], etc.

Other works rather apply higher-level theories of language understanding to the problem of modeling relations. One such theory is that of frame semantics [103], which considers that people understand sentences by recalling familiar structures evoked by a particular word; a common example is that of the term “revenge”, which evokes a structure involving various constituents, including the avenger, the retribution, the target of revenge, the original victim being avenged, and the original offense. These structures are then formally encoded as frames, categorized by the word senses that evoke the frame, encapsulating the constituents as frame elements. Various collections of frames have then been defined – with FrameNet [14] being a prominent example – to help identify frames and annotate frame elements in text. Such frames can be used to parse n-ary relations, as used for example by Refractive [98], PIKES [61] or Fact Extractor [106].

A related theory used to parse complex n-ary relations is that of Discourse Representation Theory (DRT) [156], which offers a more logic-based perspective for reasoning about language. In particular, DRT is based on the idea of Discourse Representation Structures (DRS), which offer a first-order-logic (FOL) style representation of the claims made in language, incorporating n-ary relations, and even allowing negation, disjunction, equalities, and implication. The core idea is to build up a formal encoding of the claims made in a discourse spanning multiple sentences where the equality operator, in particular, is used to model coreference across sentences. These FOL style formulae are contextualized as boxes that indicate conjunction.

Tools such as Boxer [28] then allow for extracting such DRS “boxes” following a neo-Davidsonian representation, which at its core involves describing events. Consider the example sentence “Barack Obama met Raul Castro in Cuba”; we could consider representing this as meet ( BO , RC , CU ) with BO denoting “Barack Obama”, etc.58

There are a number of significant practical shortcomings of using resources such as FrameNet, VerbNet, and PropBank to extract relations. First, being manually-crafted, they are not necessarily complete for all possible relations and syntactic patterns that one might consider and, indeed, are often only available in English. Second, the parsing method involved may be quite costly to run over all sentences in a very large corpus. Third, the relations extracted are complex and may not conform to the typically binary relations in the KB; creating a posteriori mappings may be non-trivial.

An alternative data-driven method for extracting relations – based on distant supervision61

The first step for distant supervision methods is to find sentences containing mentions of two entities that have a known binary relation in the KB. This step essentially relies on the EEL process described earlier and can draw on techniques from Section 2. Note that examples may be drawn from external documents, where, for example, Sar-graphs [167] proposes to use Bing’s Web search to find documents containing both entities in an effort to build a large collection of example mentions for known KB relations. In particular, being able to draw from more examples allows for increasing the precision and recall of the REL process by finding better quality examples for training [233].

Once a list of sentences containing pairs of entities is extracted, these sentences need to be analyzed to extract patterns and/or features that can be applied to other sentences. For example, as a set of lexical features, Mintz et al. [213] propose to use the sequence of words between the two entities, to the left of the first entity and to the right of the second entity; a flag to denote which entity came first; and a set of POS tags. Other features proposed in the literature include matching the label of the KB property (e.g., dbo:birthPlace – “Birth Place”) and the relation mention for the associated pair of entities (e.g., “was born in”) [182]; the number of words between the two entity mentions [117]; the frequency of n-grams appearing in the text window surrounding both entities, where more frequent n-grams (e.g., “was born in”) are indicative of general patterns rather than specific details for the relation of a particular pair of entities (e.g., “prematurely in a taxi”) [223], etc.

Aside from shallow lexical features, systems often parse the example relations to extract syntactic dependencies between the entities. A common method, again proposed by Mintz et al. [213] in the context of supervision, is to consider dependency paths, which are (shortest) paths in the dependency parse tree between the two entities; they also propose to include window nodes – terms on either side of the dependency path – as a syntactic feature to capture more context. Both the lexical and syntactic features proposed by Mintz et al. were then reused in a variety of subsequent related works using distant supervision, including Knowledge Vault [86], DeepDive [233], and many more besides.

Once a set of features is extracted from the relation mentions for pairs of entities with a known KB relation, the next step is to generalize and apply those features for other sentences in the text. Mintz et al. [213] originally proposed to use a multi-class logistic regression classifier: for training, the approach extracts all features for a given entity pair (with a known KB relation) across all sentences in which that pair appears together, which are used to train the classifier for the original KB relation; for classification, all entities are identified by Stanford NER, and for each pair of entities appearing together in some sentence, the same features are extracted from all such sentences and passed to the classifier to predict a KB relation between them.

A variety of works followed up on and further refined this idea. For example, Riedel et al. [257] note that many sentences containing the entity pair will not express the KB relation and that a significant percentage of entity pairs will have multiple KB relations; hence combining features for all sentences containing the entity pair produces noise. To address this issue, they propose an inference model based on the assumption that, for a given KB relation between two entities, at least one sentence (rather than all) will constitute a true mention of the relation; this is realized by introducing a set of binary latent variables for each such sentence to predict whether or not that sentence expresses the relation. Subsequently, for the MultiR system, Hoffman et al. [141] proposed a model further taking into consideration that relation mentions may overlap, meaning that a given mention may simultaneously refer to multiple KB relations; this idea was later refined by Surdeanu et al. [292], who proposed a similar multi-instance multi-label (MIML-RE) model capturing the idea that a pair of entities may have multiple relations (labels) in the KB and may be associated with multiple relation mentions (instances) in the text.

Another complication arising in learning through distant supervision is that of negative examples, where Semantic Web KBs like Freebase, DBpedia, YAGO, are necessarily incomplete and thus should be interpreted under an Open World Assumption (OWA): just because a relation is not in a KB, it does not mean that it is not true. Likewise, for a relation mention involving a pair of entities, if that pair does not have a given relation in the KB, it should not be considered as a negative example for training. Hence, to generate useful negative examples for training, the approach by Surdeanu et al. [292], Knowledge Vault [86], the approach by Min et al. [211], etc., propose a heuristic called (in [86]) a Local Closed World Assumption (LCWA), which assumes that if a relation p ( s , o ) exists in the KB, then any relation p ( s , o ′ ) not in the KB is a negative example; e.g., if born ( BO , US ) exists in the KB, then born ( BO , X ) should be considered a negative example assuming it is not in the KB. While obviously this is far from infallible – working well for functional-esque properties like capital but less well for often multi-valued properties like child  – it has proven useful in practice [86,211,292]; even if it produces false negative examples, it will produce far fewer than considering any relation not in the KB as false, and the benefit of having true negative examples amortizes the cost of potentially producing false negatives.

A further complication in distant supervision is with respect to noise in automatically labeled relation mentions caused, for example, by incorrect EEL results where entity mentions are linked to an incorrect KB identifier. To tackle this issue, a number of DS-based approaches include a seed selection process to try to select high-quality examples and reduce noise in labels. Along these lines, for example, Augenstein et al. [11] propose to filter DS-labeled examples involving ambiguous entities; for example, the relation mention “New York is a state in the U.S.” may be discarded since “New York” could be mistakenly linked to the KB identifier for the city, which may lead to a noisy example for a KB property such as has-city.

Other approaches based on distant supervision rather propose to extract generalized patterns from relation mentions for known KB relations. Such systems include BOA [117] and PATTY [223], which extract sequences of tokens between entity pairs with a known KB relation, replacing the entity pairs with (typed) variables to create generalized patterns associated with that relation, extracting features used to filter low-quality patterns; an example pattern in the case of PATTY would be “<Person> is the lead-singer of <MusicBand>” as a pattern for dbo:bandMember where, e.g., MusicBand indicates the expected type of the entity replacing that variable.

We also highlight a more recent trend towards alternative distant supervision methods based on embeddings (e.g., [179,312,324]). Such approaches have the benefit of not relying on NLP-based parsing tools, but rather relying on distributional representations of words, entities and/or relations in a fixed-dimensional vector space that, rather than producing a discrete parse-tree structure, provides a semantic representation of text in a (continuous) numeric space. Approaches such as proposed by Lin et al. [179] go one step further: rather than computing embeddings only over the text, such approaches also compute embeddings for the structured KB, in particular, the KB entities and their associated properties; these KB embeddings can be combined with textual embeddings to compute, for example, similarity between relation mentions in the text and relations in the KB.

We remark that tens of other DS-based approaches have recently been published using Semantic Web KBs in the linguistic community, most often using Freebase as a reference KB, taking an evaluation corpus from the New York Times (originally compiled by Riedel et al. [257]). While strictly speaking such works would fall within the scope of this survey, upon inspection, many do not provide any novel use of the KB itself, but rather propose refinements to the machine learning methods used. Hence we consider further discussion of such approaches as veering away from the core scope of this survey, particularly given their number. Herein, rather than enumerating all works, we have instead captured the seminal works and themes in the area of distant supervision for REL; for further details on distant supervision for REL in a Semantic Web setting, we can instead refer the interested reader to the Ph.D. dissertation of Augenstein [10].

Relation mentions extracted from the text may refer to the same KB relation using different terms, or may imply the existence of a KB relation through hypernymy/sub-property relations. For example, mentions of the form “X is married to Y”, “X is the spouse of Y”, etc., can be considered as referring to the same KB property (e.g., dbo:spouse), while a mention of the form “X is the husband of Y” can likewise be considered as referring to that KB property, though in an implied form through hypernymy. Some REL approaches thus apply an analysis of such semantic relations – typically synonymy or hypernymy – to cluster textual mentions, where external resources – such as WordNet, FrameNet, VerbNet, PropBank, etc., – are often used for such purposes. These clustering techniques can then be used to extend the set of mentions/patterns that map to a particular KB relation.

An early approach applying such clustering was Artequakt [4], which leverages WordNet knowledge – specifically synonyms and hypernyms – to detect which pairs of relations can be considered equivalent or more specific than one another. A more recent version of such an approach is proposed by Gerber et al. [116] in the context of their RdfLiveNews system, where they define a similarity measure between relation patterns composed of a string similarity measure and a WordNet-based similarity measure, as well as the domain(s) and range(s) of the target KB property associated with the pattern; thereafter, a graph-based clustering method is applied to group similar patterns, where within each group, a similarity-based voting mechanism is used to select a single pattern deemed to represent that group. A similar approach was employed by Liu et al. [182] for clustering mentions, combining a string similarity measure and a WordNet-based measure; however they note that WordNet is not suitable for capturing similarity between terms with different grammatical roles (e.g., “spouse”, “married”), where they propose to combine WordNet with a distributional-style analysis of Wikipedia to improve the similarity measure. Such a technique is also used by Dutta et al. [93] for clustering relation mentions using a Jaccard-based similarity measure for keywords and a WordNet-based similarity measure for synonyms; these measures are used to create a graph over which Markov clustering is run.

An alternative clustering approach for generalized relation patterns is to instead consider the sets of entity pairs that each such pattern considers. Soderland and Mandhani [285] propose a clustering of patterns based on such an idea: if one pattern captures a (near) subset of the entity pairs that another pattern captures, they consider the former pattern to be subsumed by the latter and consider the former pattern to infer relations pertaining to the latter. A similar approach is proposed by Nakashole et al. [223] in the context of their PATTY system, where subsumption of relation patterns is likewise computed based on the sets of entity pairs that they capture; to enable scalable computation, the authors propose an implementation based on the MapReduce framework. Another approach along these lines – proposed by Riedel et al. [258] – is to construct what the authors call a universal schema, which involves creating a matrix that maps pairs of entities to KB relations and relation patterns associated with them (be it from training or test data); over this matrix, various models are proposed to predict the probability that a given relation holds between a pair of entities given the other KB relations and patterns the pair has been (probabilistically) assigned in the matrix.

4.5. RDF representation

In order to populate Semantic Web KBs, it is necessary for the REL process to represent output relations as RDF triples. In the case of those systems that produce binary relations, each such relation will typically be represented as an RDF triple unless additional annotations about the relation – such as its provenance – are also captured. In the case of systems that perform EEL and a DS-style approach, it is furthermore the case that new IRIs typically will not need to be minted since the EEL process provides subject/object IRIs while the DS labeling process provides the predicate IRI from the KB. This process has the benefit of also directly producing RDF triples under the native identifier scheme of the KB. However, for systems that produce n-ary relations – e.g., according to frames, DRT, etc. – in order to populate the KB, an RDF representation must be defined. Some systems go further and provide RDFS/OWL axioms that enrich the output with well-defined semantics for the terms used [113].

The first step towards generating an RDF representation is to mint new IRIs for the entities and relations extracted. The BOA [117] framework proposes to first apply Entity Linking using a DS-style approach (where predicate IRIs are already provided), where for emerging entities not found in the KB, IRIs are minted based on the mention text. The FRED system [113] likewise begins by minting IRIs to represent all of the elements, roles, etc., produced by the Boxer DRT-based parser, thus skolemizing the events: grounding the existential variables used to denote such events with a constant (more specifically, an IRI).

Next, an RDF representation must be applied to structure the relations into RDF graphs. In cases where binary relations are not simply represented as triples, existing mechanisms for RDF reification – namely RDF n-ary relations, RDF reification, singleton properties, named graphs, etc. (see [134,272] for examples and more detailed discussion) – can, in theory, be adopted. In general, however, most systems define bespoke representations (most similar to RDF n-ary relations). Among these, Freitas et al. [109] propose a bespoke RDF-based discourse representation format that they call Structured Discourse Graphs capturing the subject, predicate and object of the relation, as well as (general) reification and temporal annotations; LODifier [12] maps Boxer output to RDF by mapping unary relations to rdf:type triples and binary relations to triples with a custom predicate, using RDF reification to represent the disjunction, negation, etc., present in the DRS output; FRED [113] applies an n-ary–relation-style representation of the DRS-based relations extracted by Boxer, likewise mapping unary relations to rdf:type triples and binary relations to triples with a custom predicate (see Listing 4); etc.

Rather than creating a bespoke RDF representation, other systems rather try to map or project extracted relations directly to the native identifier scheme and data model of the reference KB. Likewise, those systems that first create a bespoke RDF representation may apply an a posteriori mapping to the KB/ontology. Such methods for performing mappings are now discussed.

4.6. Relation mapping

While in a distant supervision approach, the patterns and features extracted from textual relation mentions are directly associated with a particular (typically binary) KB property, REL systems based on other extraction methods – such as parsing according to legacy OpenIE systems, or frames/DRS theory – are still left to align the extracted relations with a given KB.

A common approach – similar to distant supervision – is to map pairs of entities in the parsed relation mentions to the KB to identify what known relations correspond to a given relation pattern.62

In the case of systems that natively extract n-ary relations – e.g., those systems based on frames or DRS – the process of mapping such relations to a binary KB relation – sometimes known as projection of n-ary relations [167] – is considerably more complex. Rather than trying to project a binary relation from an n-ary relation, some approaches thus rather focus on mapping elements of n-ary relations to classes in the KB. Such an approach is adopted by Gerber et al. [116] for mapping elements of binary relations extracted via learned patterns to DBpedia entities and classes. The FRED system [113] likewise provides mappings of its DRS-based relations to various ontologies and KBs, including WordNet and DOLCE ontologies (using WSD) and the DBpedia KB (using EEL).

On the other hand, other systems do propose techniques for projecting binary relations from n-ary relations and linking them with KB properties; such a process must not only identify the pertinent KB property (or properties), but also the subject and object entities for the given n-ary relation; furthermore, for DRS-style relations, care must be taken since the statement may be negated or may be part of a disjunction. Along those lines, Exner and Nugues [97] initially proposed to generate triples from DRS relations by means of a combinatorial approach, filtering relations expressed with negation. In follow-up work on the Refractive system, Exner and Nugues [98] later propose a method to map n-ary relations extracted using PropBank to DBpedia properties: existing relations in the KB are matched to extracted PropBank roles such that more matches indicate a better property match; thereafter, the subject and object of the KB relation are generalized to their KB class (used to identify subject/object in extracted relations), and the relevant KB property is proposed as a candidate for other instances of the same role (without a KB relation) and pairs of entities matching the given types. Legalo [251] proposes a method for mapping FRED results to binary KB relations by concatenating the labels of nodes on paths in the FRED output between elements identified as (potential) subject/object pairs, where these concatenated path labels are then mapped to binary KB properties to project new RDF triples. Rouces et al. [272], on the other hand, propose a rule-based approach to project binary relations from FrameNet patterns, where dereification rules are constructed to map suitable frames to binary triples by mapping frame elements to subject and object positions, creating a new predicate from appropriate conjugate verbs, further filtering passive verb forms with no clear binary relation.

Based on the previously discussed techniques, an overview of the highlighted REL systems is provided in Table 6, with a column legend provided in the caption. As before, we highlight approaches that are directly related with the Semantic Web and that offer a peer-reviewed publication with novel technical details regarding REL. With respect to the Entity Recognition column, note that many approaches delegate this task to external tools and systems – such as DBpedia Spotlight [200], GATE [68], Stanford CoreNLP [187], TagMe [101], Wikifier [255], etc. – which are mentioned in the respective column.

Choosing an RE strategy for a particular application scenario can be complex given that every approach has pros and cons regarding the application at hand. However, we can identify some key considerations that should be taken into account:

Of course, a key consideration when choosing an REL approach is the quality of output produced by that approach, which can be assessed using the evaluation protocols discussed in the following section.

REL is a challenging task, where evaluation is likewise complicated by a number of fundamental factors. In general, human judgment is often required to assess the quality of the output of systems performing such a task, but such assessments can often be subjective. Creating a gold-standard dataset can likewise be complicated, particularly for those systems producing n-ary relations, requiring an expert informed on the particular theory by which such relations are extracted; likewise, in DS-related scenarios, the expert must label the data according to the available KB relations, which may be a tedious task requiring in-depth knowledge of the KB. Rather than creating a gold-standard dataset, another approach is to apply a posteriori assessment of the output by human judges, i.e., run the process over unlabeled text, generate relations, and have the output validated by human judges; while this would appear more reasonable for systems based on frames or DRS – where creating a gold-standard for such complex relations would be arduous at best – there are still problems in assessing, for example, recall.63

In summary, then, approaches for evaluating REL are quite diverse and in many cases there are no standard criteria for assessing the adequacy of a particular evaluation method. Here we discuss some of the main themes for evaluation, broken down by datasets used, how evaluators are employed to judge the output, how automated evaluation can be conducted, and what are the typical metrics considered.

Datasets: Most approaches consider REL applied to general-domain corpora, such as Wikipedia articles, Newspaper articles, or even webpages. However, to simplify evaluation, many approaches may restrict REL to consider a domain-specific subset of such corpora, a fixed subset of KB properties or classes, and so forth. For example, Fossati et al. [106] focus their REL efforts on the Wikipedia articles about Italian soccer players using a selection of relevant frames; Augenstein et al. [11] apply evaluation for relations pertaining to entities in seven Freebase classes for which relatively complete information is available, using the Google Search API to find relevant documents for each such entity; and so forth.

A number of standard evaluation datasets have, however, emerged, particularly for approaches based on distant supervision. A widely reused gold-standard dataset, for example, was that initially proposed by Riedel et al. [257] for evaluating their system, where they select Freebase relations pertaining to people, businesses and locations (corresponding also to NER types) and then link them with New York Times articles, first using Stanford NER to find entities, then linking those entities to Freebase, and finally selecting the appropriate relation (if any) to label pairs of entities in the same sentence with; this dataset was later reused by a number of works [141,258,292]. Other such evaluation resources have since emerged. Google Research64

Note that all prior evaluation datasets relate to binary relations of the form subject–predicate–object. Creating gold standard datasets for n-ary relations is complicated by the heterogeneity of representations that can be employed in terms of frames, DRS or other theories used. To address this issue, Gangemi et al. [114] proposed the construction of RDF graphs by means of logical patterns known as motifs that are extracted by the FRED tool and thereafter manually corrected and curated by evaluators to follow best Semantic Web practices; the result is a corpus annotated by instances of such motifs that can be reused for evaluation of REL tools producing similar such relations.

Evaluators: In scenarios for which a gold standard dataset is not available – or not feasible to create – the results of the REL process are often directly evaluated by humans. Many papers assign experts to evaluate the results, typically (we assume) authors of the papers, though often little detail on the exact evaluation process is given, aside from a rater agreement expressed as Cohen’s or Fleiss’ κ-measure for a fixed number of evaluators (as discussed in Section 3.7).

Aside from expert evaluation, some works leverage crowdsourcing platforms for labeling training and test datasets, where a broad range of users contribute judgments for a relatively low price. Amongst such works, we can mention Mintz et al. [213] using Amazon’s Mechanical Turk67

Automated evaluation: Some works have proposed methods for performing automated evaluation of REL processes, in particular for testing DS-based methods. A common approach is to perform held-out experiments, where KB relations are (typically randomly) omitted from the training/DS phase and then metrics are defined to see how many KB relations are returned by the process, giving an indicator of recall; the intuition of such approaches is that REL is often used for completing an incomplete KB, and thus by holding back KB triples, one can test the process to see how many such triples the process can reinstate. Such an approach avoids expensive manual labeling but is not very suitable for precision since the KB is incomplete, and likewise assumes that held-out KB relations are both correct and mentioned in the text. On the other hand, such experiments can help gain insights at larger scales for a more diverse range of properties, and can be used to assess a relative notion of precision (e.g., to tune parameters), and have thus been used by Mintz et al. [213], Takamatsu et al. [293], Knowledge Vault [86], Lin et al. [179], etc. On the other hand, as mentioned previously, some works – including Knowledge Vault [86] – adopt a partial Closed World Assumption as a heuristic to generate negative examples taking into account the incompleteness of the KB; more specifically, extracted triples of the form ( s , p , o ′ ) are labeled incorrect if (and only if) a triple ( s , p , o ) is present in the KB but ( s , p , o ′ ) is not.

Metrics: Standard evaluation measures are typically applied, including precision, recall, F-measure, accuracy, Area-Under-Curve (AUC–ROC), and so forth. However, given that relations may be extracted for multiple properties, sometimes macro-measures such as Mean Average Precision (MAP) are applied to summarize precision across all such properties rather than taking a micro precision measure [92,213,293]. Given the subjectivity inherent in evaluating REL, Fossati et al. [106] use a strict and lenient version of precision/recall/F-measure, where the former requires the relation to be exact and complete, while the latter also considers relations that are partially correct; relating to the same theme, the Legalo system includes confidence as a measure indicating the level of agreement and trust in crowdsourced evaluators for a given experiment. Some systems produce confidence or supports for relations, where P@k measures are sometimes used to measure the precision for the top-k results [179,182,213,257]. Finally, given that REL is inherently composed of several phases, some works present metrics for various parts of the task; as an example, for extracted triples, Dutta [93] considers a property precision (is the mapped property correct?), instance precision (are the mapped subjects/objects correct?), triple precision (is the extracted triple correct?), amongst other measures to, for example, indicate the ratio of extracted triples new to the KB.

Third-party comparisons: While some REL papers include prior state-of-the-art approaches in their evaluations for comparison purposes, we are not aware of a third-party study providing evaluation results of REL systems. Although Gangemi [112] provides a comparative evaluation of Alchemy, CiceroLite, FRED and ReVerb – all with public APIs available – for extracting relations from a paragraph of text on the Syrian war, he does not publish results for a linking phase; FRED is the only REL tool tested that outputs RDF.

Despite a lack of third-party evaluation results, some comparative metrics can be gleaned from the use of standard datasets over several papers relating to distant supervision; we stress, however, that these are often published in the context of evaluating a particular system (and hence are not strictly third-party comparisons69

This section presented the task of Relation Extraction and Linking in the context of the Semantic Web. The applications for such a task include KB Population, Structured Discourse Representation, Machine Reading, Question Answering, Fact Verification, amongst a variety of others. We discussed relevant papers following a high-level process consisting of: entity extraction (and coreference resolution), relation parsing, distant supervision, relation clustering, RDF representation, relation mapping, and evaluation. It is worth noting, however, that not all systems follow these steps in the presented order and not all systems apply (or even require) all such steps. For example, entity extraction may be conducted during relation parsing (where particular arguments can be considered as extracted entities), distant supervision does not require a formal representation nor relation-mapping phase, and so forth. Hence the presented flow of techniques should be considered illustrative, not prescriptive.

In general, we can distinguish two types of REL systems: those that produce binary relations, and those that produce n-ary relations (although binary relations can subsequently be projected from the latter tools [251,272]). With respect to binary relations, distant supervision has become a dominating theme in recent approaches, where KB relations are used, in combination with EEL and often CR, to find example mentions of binary KB relations, generalizing patterns and features that can be used to extract further mentions and, ultimately, novel KB triples; such approaches are enabled by the existence of modern Semantic Web KBs with rich factual information about a broad range of entities of general interest. Other approaches for extracting binary relations rather rely on mapping the results of existing OpenIE systems to KBs/ontologies. With respect to extracting n-ary relations, such approaches rely on more traditional linguistic techniques and resources to extract structures according to frame semantics or Discourse Representation Theory; the challenge thereafter is to represent the results as RDF and, in particular, to map the results to an existing KB, ontology, or collection thereof.

4.10. Open questions

REL is a very important task for populating the Semantic Web. Several techniques have been proposed for this task in order to cover the extraction of binary and n-ary relations from text. However, some aspects could still be improved or developed further:

Relation types: Unlike EEL where particular types of entities are commonly extracted, in REL it is not easy to define the types of relations to be extracted and linked to the Semantic Web. Previous studies, such as the one presented by Storey [290], provide an organization of relations – identified from disciplines such as linguistics, logic, and cognitive psychology – that can be incorporated into traditional database management systems to capture the semantics of real world information. However, to the best of our knowledge, a thorough categorization of semantic relationships on the Semantic Web has not been presented, which in turn, could be useful for defining requirements of information representation, standards, rules, etc., and their representation in existing standards (RDF, RDFS, OWL).

The content of the Web has traditionally been structured according to the HyperText Markup Language (HTML), which lays out a document structure for webpages to follow. While this structure is primarily perceived as a way to format, display and offer navigational links between webpages, it can also be – and has been – leveraged in the context of Information Extraction. Such structure includes, for example, the presence of hyperlinks, title tags, paths in the HTML parse tree, etc. Other Web content – such as Wikis – may be formatted in markup other than HTML, where we include frameworks for such formats here. We provide an overview of these works in Table 7. Given that all such approaches implement diverse methods that depend on the markup structure leveraged, we will not discuss techniques in detail. However, we will provide more detailed discussion for IE techniques that have been proposed for HTML tables in a following section.

It is interesting to note that KBs such as DBpedia [171] and YAGO2 [139] – used in so many of the previous IE works discussed throughout the survey – are themselves the result of IE processes, particularly over Wikipedia. This highlights something of a “snowball effect”, where as IE methods improve, new KBs arise, and as new KBs arise, IE methods improve.70

Tabular data are common on the Web, where HTML tables embedded in webpages are plentiful and often contain rich, semi-structured, factual information [35,65]. Hence, extracting information from such tables is indeed a tempting prospect. However, web tables are primarily designed with human readability in mind rather than machine readability. Web tables, while numerous, can thus be highly heterogeneous and idiosyncratic: even tables describing similar content can vary widely in terms of structuring that content [65]. More specifically, the following complications arise when trying to extract information from such tables:

There have thus been numerous works on extracting information from tables, sometimes referred to as table interpretation, table annotation, etc. (e.g., [35,45,65,245,307,318], to name some prominent works). The goal of such works is to interpret the implicit structure of tables so as to categorize them for search; or to integrate the information they contain and enable performing joins over them, be it to extend tables with information from other tables, or extracting the information to an external unified representation that can be queried.

More recently, a variety of approaches have emerged using Semantic Web KBs as references to help with extracting information from tables (sometimes referred to as semantic table interpretation, semantic table annotation, etc.). We discuss such approaches herein.

Process: While proposed approaches vary significantly, more generally, given a table and a KB, such works aim to link tables/columns to KB classes, link columns or tuples of columns to KB properties, and link individual cells to KB entities. The aim can then be to annotate the table with respect to the KB (useful for, e.g., later integrating or retrieving tables), and indeed to extract novel entities or relations from the table to further populate the KB. Hence we consider this an IE scenario. While methods discussed previously for IE over unstructured sources can be leveraged for tables, the presence of a tabular structure does suggest the applicability of novel features for the IE process. For example, one might expect in some tables to find that elements of the same column pertain to the same type, or pairs of entities on the same row to have a similar relation as analogous pairs on other rows. On the other hand, cells in a table have a different textual context, which may be the caption, the text referring to the table, etc., rather than the surrounding text; hence, for example, distributional approaches intended for text may not be directly applicable for tables.

Example: Consider an HTML table embedded in a webpage about the actor Bryan Cranston as follows:

We see that the table contains various entities, and that entities in the same column tend to correspond to a particular type. We also see that entities on each row often have implicit relations between them, organized by column; for example, on each row, there are binary relations between the elements of the Character and Series columns, the Series and Networks columns, and (more arguably in the case that multiple actors play the same character) between the Character and Ep. columns. Furthermore, we note that some relations exist from Bryan Cranston – the subject of the webpage – to the elements of various columns of the table.71

The approaches we enumerate here attempt to identify entities in table cells, assign types to columns, extract binary KB relations across columns, and so forth.

However, we also see some complications in the table structure, where some values span multiple cells. While this particular issue is relatively trivial to deal with – where simply duplicating values into each spanned cell is effective [245] – a real-world collection of (HTML) tables may exhibit further such complications; here we gave a relatively clean example.

Systems: We now discuss works that aim to extract entities, concepts or relations from tables, using Semantic Web KBs. We also provide an overview of these works in Table 8.72

Summary: Hence we see that exploring custom IE processes dedicating to tabular input formats using Semantic Web KBs is a burgeoning but still relatively recent area of research; techniques combine a mix of traditional IE methods as described previously, as well as novel low-level table-specific features and high-level global inference models that capture the dependencies in linking between different columns of the same table, different cells of the same column or row, etc.

Also, approaches vary in what they annotate. For example, while Zwicklbauer et al. [335] focus on typing columns, and AIDA [140] and TabEL [21] focus on annotating entities, most works annotate various aspects of the table, in particular for the purposes of extracting relations. Amongst those approaches extracting relations, we can identify an important distinction: those that begin by identifying a subject column to which all other relations extend [172,262,327], and those that rather extract relations between any pair of columns in the table [30,86,176,218,219]. All approaches that we found for Relation Extraction, however, rely on extracting a set of features and then applying machine learning methods to classify likely-correct relations; similarly, almost all approaches rely on a “distant supervision” style algorithm, where seed relations in the KB appearing in rows of the table are used as a feature to identify candidate relations between column pairs. In terms of other annotations, we note that DRETa [219] extracts the protagonist of a table as the main entity about which the containing webpage is about (considered an entity with possible relations to entities in the table), while Ritze and Bizer [262] extract a type for each table that is based on the type(s) of entities in the subject column.

Information Extraction has also been applied to various other formats in conjunction with Semantic Web KBs and/or ontologies. Amongst these, a number of works have proposed specialized EEL techniques for multimedia formats, including approaches for performing EEL with respect to images [17], audio (speech) [19,253], and video [175,204,310]. Other works have focused on IE techniques in the context of social platforms, such as for Twitter [79,320,322], tagging systems [160,287], or for other user-generated content, such as keyword search logs [63], etc.

Techniques inspired by IE have also been applied to structured input formats, including Semantic Web KBs themselves. For example, a variety of approaches have been recently proposed to model topics for Semantic Web KBs themselves, either to identify the main topics within a KB, or to identify related KBs [25,240,267,283]. Given that such methods apply to structured input formats, these works veer away from pure Information Extraction and head more towards the related areas of Data Mining and Knowledge Discovery – as discussed already in a recent survey by Ristoski and Paulheim [261] – where the goal is to extract high-level patterns from data for applications including KB refinement, recommendation tasks, clustering, etc. We thus consider such works as outside the current scope.