2.1 Typical system architecture

Figure 1 shows the main components of a general architecture for a knowledge mining system. The knowledge mining component is shown as a shaded box with a list of main functions. Its main purpose is mining for KB entries, such as entities, relations and events. These elements are extracted from possibly multiple data sources and matched with the ontology in order to consistently place them in the KB (the arrow from knowledge mining to the knowledge base). These tasks are typically performed by a processing pipeline consisting of text pre-processing, machine learning/data mining methods such as clustering and categorisation, and NLP methods.

Figure 1

Knowledge mining system architecture

NLP methods used for entity extraction include NER and NED techniques. This process is often supported by an external KB and bootstrapping dictionaries, such as a paraphrase dictionary, particularly useful for tweets. The Paraphrase Database (PPDB)Footnote ² is an example of such a dictionary. Entity disambiguation can be facilitated by comparing synchronised information from multiple data sources and, importantly, may utilise a partially built KB in an iterative process (the arrow from the knowledge base to knowledge mining). This creates a major challenge for such ‘bootstrapping’ of knowledge mining systems because for the KB to be used effectively in knowledge mining, the extracted knowledge must be sufficiently reliable. Thus, some form of human input is typically incorporated into the process. Human input typically provides background knowledge in the form of curation rules to improve the quality of the KB, and human-labelled examples to improve supervised machine learning processes. At the application level, user feedback may confirm the credibility of specific pieces of information, which in turn may serve as training data for machine learning algorithms or be used for KB curation.

A significant question is the purpose to which the KB is to be put. If there is no specific purpose, that is, the aim is to extract as much knowledge as possible, the reliability of the knowledge mining process and the consistency and correctness of the resulting KB is a major issue, especially as such KBs soon grow beyond the capacity of people to validate them. On the other hand, if there is a specific intended application, the knowledge mining process is more constrained, so presumably more reliable, however, the accuracy and completeness of the knowledge extracted remains an issue. In general, evaluation of such complex knowledge mining processes and of the resulting KBs is difficult, and mostly absent for the exemplar systems described below. Research on KB applications so far has concentrated on question answering and event extraction, whereas applications to general data mining and text summarisation may become future trends. For these specific applications, there is of course much evaluation of methods on small-scale data sets.

2.2 Existing knowledge mining systems

In this section, we describe representative examples of knowledge mining systems that attempt to capture general human knowledge rather than apply to any specific domain. These systems are to be taken as research prototypes undergoing constant evolution and ongoing development, thus what is most important are the broad approaches, which we show with reference to the general architecture in Figure 1, rather than the specific details, of which some are only sketchily given and thus cannot be described in depth in this article. The diagrams included in this section show our reconstruction of those architectures from the information presented in the cited papers, in order to identify similarities and differences between the approaches.

2.2.2 Stanford DeepDive

DeepDive (Shin et al., Reference Shin, Wu, Wang, Sa, Zhang and Ré2015) is an open-source system for KB construction. It takes a variety of data sources: unstructured (text documents), semi-structured (Wikipedia) and structured (Freebase) and creates KB entries. Figure 2 identifies the knowledge mining stage from Figure 1, with the KB as the final product. Results from all stages of processing are stored in an RDBMS and most processes in DeepDive are based on SQL statements. The knowledge mining stage consists of a number of steps. In the first step, a combination of SQL queries, NLP methods and user-defined functions perform feature extraction, producing sets of candidate entities, relations and ‘mentions’. Candidates are selected in the second step by classifying each element as true or false using a combination of hand labelling and distant supervision. In the third step of knowledge mining, denoted ‘learning and inference’, a factor graph is created that connects evidence with candidate facts. In this step, statistical learning and inference is used to resolve inconsistencies between candidate facts and to produce the marginal probability associated with each KB entry. For example, the relation HasSpouse(Barack Obama, Michelle Obama) would be expected to have high probability. Human assessors are involved in this stage to learn common errors and correct them, again using SQL statements, before entries are accepted into the KB.

Figure 2

DeepDive system architecture

Scalable relational technology allows avoiding bottlenecks, especially in the grounding and statistical inference stage (Ré et al., 2014). The use of RBDMS allows applying incremental view maintenance, a technique known in database technology (Gupta et al., Reference Gupta, Mumick and Subrahmanian1993) for incrementally modifying the view with the change of underlying input data. The main difference with the Kosmix system is that DeepDive does not create a general purpose KB, but can be used for domain-specific KBs, such as geology and pharmacology. Therefore Figure 2 does not show the applications box.

Examples provided in Shin et al. (Reference Shin, Wu, Wang, Sa, Zhang and Ré2015) suggest that DeepDive works better with richer and structured documents, as opposed to loosely structured tweets. According to the DeepDive website, the system achieved ‘winning performance in entity relation extraction competitions’, referring to the TAC 2014 slot filling competition (Angeli et al., Reference Angeli, Gupta, Premkumar, Manning, Ré, Tibshirani, Wu, Wu and Zhang2014). The comparison to other systems in that competition, however, is not published. We noted, however, based on the above system description, that much human intervention is required to produce these results for the competition.

2.2.3 CMU Never-Ending Language Learning

Never-Ending Language Learning (NELL)Footnote ⁴ (Mitchell et al., Reference Mitchell, Cohen, Hruschka, Talukdar, Betteridge, Carlson, Dalvi, Gardner, Kisiel, Krishnamurthy, Lao, Mazaitis, Mohamed, Nakashole, Platanios, Ritter, Samadi, Settles, Wang, Wijaya, Gupta, Chen, Saparov, Greaves and Welling2015) is a semantic learning system that autonomously reads information from web pages and incrementally builds a general KB. At a high level (Figure 3), NELL performs two main tasks: (1) extracting information from the Web to generate candidate entries for the KB (what we call knowledge mining), and (2) using machine learning and human input to improve and correct KB entries (knowledge base with user input and iteration loops). This structure is our reconstruction of the architecture presented in various papers, roughly conforming to the diagram in Figure 1.

Figure 3

Never-Ending Language Learning architecture

The knowledge mining part of the system contains the knowledge learner, running a number of extraction tasks. Figure 3 lists only the categories of these tasks under the knowledge learner label. Each category contains many such tasks, each dedicated to a specific context, feature or extraction method. These numerous tasks have some mutual dependencies, hence the coupling constraints module within the knowledge miner executes constraints and monitors their satisfaction. The extraction task extracts two types of information: entities for each pre-defined category of entities and a pair of entities for each pre-defined category of relationship. The ontology extension module finds new relations for entities already in the KB.

The NELL KB architecture depends fundamentally on modelling belief with provenance (source path) information and the use of confidence levels. A key objective is that an accurate and consistent KB can be constructed from large amounts of data with relatively little human input. To achieve this, KB population and learning is designed as an iterative process, using an approach similar to expectation maximisation in the following way. Knowledge mining produces candidate beliefs that can be promoted to full KB beliefs by the knowledge integrator, which also processes deletion requests to particular beliefs. In the next iteration, the partially built KB is used to retrain the models produced by the knowledge learner.

Given the lack of labelled data relative to the massive amounts unlabelled data on the Web, NELL relies on a paradigm called ‘coupled learning’. Without going into detail, the key idea is that although individual functions may be hard to learn separately, by learning thousands of functions together the problem becomes more constrained and hence easier. This generalises semi-supervised learning (Section 3.1), and relies on coupling constraints (Figure 3) which can be user supplied or learned. A further key aspect is that learning and KB expansion happens in a staged fashion as more data are gathered and the KB and ontologies grow, thus providing more constraints for subsequent learning iterations.

Two kinds of human input are provided to NELL: (1) human-labelled training examples for each entity and relation category, and (2) user feedback through NELL’s website, where users can vote each belief up or down. These corrections are turned into further training examples (although it is not clear exactly how this is done). It seems that this feedback contributes significantly to improving the accuracy of system knowledge. Empirical evaluation of NELL has been limited: some papers confirm an improvement in accuracy of the KB over time, however, we are not aware of any publication evaluating NELL in an external application. This highlights a serious problem, not confined to NELL, which is that such a highly complex and mainly automated process involving numerous tightly coupled modules is in some sense an autonomous discovery system, and hence hard to evaluate objectively. Thus, analysing the knowledge mining process and evaluating any improvements in the accuracy of the resulting KB is extremely difficult, at least given the current state of the project.

3.1 Overview of data mining techniques

There are numerous data mining techniques currently in use which are covered in a number of introductory texts, such as Han et al. (Reference Han, Kamber and Pei2011) and Witten et al. (Reference Witten, Frank and Hall2011). Two main categories of data mining are clustering and categorisation. Clustering is useful in topic and trend mining, while categorisation can be used for extracting and classifying entities and relations into relevant KB categories. Some methods, such as k-Nearest Neighbour and Naïve Bayes, are very efficient in online stream mining, whereas others, for example support vector machine (SVM), work better in offline settings. Decision tree based categorisation techniques combined with probabilistic methods are worth mentioning as they are very efficient and facilitate decision transparency (a way to explain the classification decision). Well-known methods are VFDT (Very Fast Decision Tree, based on the popular C4.5 algorithm) and Concept-adapting Very Fast Decision Tree learner, a VFDT extension to handle streaming data (Hulten et al., Reference Hulten, Spencer and Domingos2001).

Supervised classification algorithms require correctly labelled examples, which are often difficult to obtain. Some methods give acceptable results with only partial labellings or in a semi-supervised mode (Carlson et al., Reference Carlson, Betteridge, Kisiel, Settles, Hruschka and Mitchell2010; Liu et al., Reference Liu, Zhang, Wei and Zhou2011, Reference Li, Wang, Han, Han, Roth and Yan2013). Semi-supervised learning relies on very large collections of web documents and information redundancy. This is based on combining a small amount of data on known concepts or relations with a much larger amount of data where this information is unknown. The known information is then used to seed predictions, which are reinforced if multiple independent sources of information can be used to make the same prediction with a learning algorithm. In this way, confidence in that prediction should be increased. Another option to overcome the scarcity of annotated training examples is the use of external or built-in-progress KBs. This method, called distant supervision (Mintz et al., Reference Mintz, Bills, Snow and Jurafsky2009; Hoffmann et al., Reference Hoffmann, Zhang, Ling, Zettlemoyer and Weld2011), has been used for example by Roth et al. (Reference Roth, Barth, Wiegand, Singh and Klakow2013) for predicting relations in the TAC competition.

Another common problem in text mining, relevant to entity matching in KB construction, is the selection of methods for comparing texts. A wide range of methods are used (Han et al., Reference Han, Kamber and Pei2011), starting from Jaccard and cosine similarity for a ‘bag-of-words’ approach, where keywords are treated as vector features, disregarding their semantic relationship. Some semantic features are captured in the n-gram approach, where word counts are made over windows of n keywords for a large number of documents and the resulting counts used as features for comparing documents. Probabilistic Soft Logic (Bröcheler et al., Reference Bröcheler, Mihalkova and Getoor2010) can be used for a deeper semantic similarity calculation (Beltagy et al., Reference Beltagy, Erk and Mooney2014), combining logical and distributional information. Generally, better results are obtained when using semantic features (Ji et al., Reference Ji, Grishman, Dang, Griffitt and Ellis2010; Ji & Grishman, Reference Ji and Grishman2011; Guo et al., Reference Guo, Li, Ji and Diab2013; Beltagy et al., Reference Beltagy, Erk and Mooney2014; Gao et al., Reference Gao, Li, Zhang and Ouyang2014).

The use of rules has been recognised as providing effectiveness and transparency. In particular, ripple-down rules (RDR) (Compton & Jansen, Reference Compton and Jansen1990), an incremental knowledge acquisition method capable of handling large numbers of rules, has been applied to text classification tasks for news and e-mail (Ho et al., Reference Ho, Wobcke and Compton2003; Park et al., Reference Park, Kim and Kang2004; Wobcke et al., Reference Wobcke, Krzywicki and Chan2008) and information extraction (Pham & Hoffmann, Reference Pham and Hoffmann2005; Kim & Compton, Reference Kim and Compton2012a). These methods can be extended to the above-mentioned text matching problem and for KB construction. Suganthan et al. (Reference Suganthan, Sun, Krishna Gayatri, Zhang, Yang, Rampalli, Prasad, Arcaute, Krishnan, Deep, Raghavendra and Doan2015) similarly use hand-crafted rules for product classification in a recently developed system called Chimera used at WalmartLabs. They argue that, in practice, it is often both necessary for achieving sufficiently high accuracy, and also much easier, to define classification rules than to capture relevant knowledge automatically, for example ‘if a product description has an ISBN then it is a book’. Part of the Chimera system is the generation of new rules from labelled data using a variation of the Apriori Algorithm (Agrawal & Srikant, Reference Agrawal and Srikant1995): the rules are then validated by system designers. Rules are also extensively used for KB maintenance and curation to correct gaps in automatic knowledge mining, for example in Kosmix (Deshpande et al., Reference Deshpande, Lamba, Tourn, Das, Subramaniam, Rajaraman, Harinarayan and Doan2013).

In our view, the high volume of data makes stream mining (Gama, Reference Gama2012) more suitable than collecting, storing and analysing data in a batch mode fashion. By a data stream, we mean a (theoretically infinite) temporal sequence of data, which can be numerical data (such as stock prices) or multimedia documents (including text, audio, image and video, or a mixture of them) as seen from a particular point of reference, for example tweets can be viewed from many points of reference: topic, sender, recipient, etc.

Streaming sources are characterised by an abundance of data whose properties change over time. Therefore, stream mining techniques generally have a lower accuracy than batch methods (where all data are available in advance) because typically only a small number of data items can be stored, and items in a stream are processed one by one in sequence. To some degree of compensation, stream mining algorithms may have a large number of training examples and may exploit information implicit in the temporal ordering of the stream to improve accuracy. Thus, stream mining algorithms attempt to strike the right balance between speed, accuracy and the computing resources required to store, process and derive conclusions from data.

As the data stream is virtually infinite, the data mining model usually changes over time. This change, called concept drift, can be detected and incorporated into a model if needed (Gama et al., Reference Gama, Žliobaitė, Bifet, Pechenizkiy and Bouchachia2014). Commonly, such methods rely on detection of concept drift (Baena-García et al., Reference Baena-García, del Campo-Ávila, Fidalgo, Bifet, Gavaldà and Morales-Bueno2004; Gama et al., Reference Gama, Medas, Castillo and Rodrigues2004) or adaptation to change by gradual forgetting (Koychev, Reference Koychev2000) or windowing (Widmer, Reference Widmer1997). Another adaptation approach is to maximally utilise periods of time when the concept is stable, called concept clumping in our previous work (Krzywicki & Wobcke, Reference Krzywicki and Wobcke2010, Reference Krzywicki and Wobcke2011).

When dealing with fast streams, windowing and automatic adaptation techniques (e.g. Bifet & Gavaldà, Reference Bifet and Gavaldà2006), are more useful than sampling as the latter may miss the detection of important events, for example short bursts of tweets related to a particular topic. This is especially important in security applications, where infrequent and anomalous patterns need to be detected.

3.2 Entity extraction

Entity extraction refers to finding ‘entities’, such as people, places and dates, in data sources. This is a non-trivial task as, apart from standard entity tagging, which can be performed by NLP software, there is also a need to establish which of the different entities mentioned in different streams or documents are, in fact, the same entity (the problem of entity resolution). Entity resolution cannot usually be done with NLP techniques alone, and requires more specialised algorithms, often based on dictionaries or KBs. Even the seemingly simple task of entity tagging can be difficult for some data sources, such as Twitter, where non-standard vocabulary is used and messages often form ill-structured sequences. For example, the word ‘tomorrow’ is used in over 50 different lexical variations (Ritter et al., Reference Ritter, Clark, Mausam and Etzioni2011). These difficulties are commonly alleviated by using dictionaries, gazetteers and KBs.

The results of entity resolution need to be ranked based on the probability of matching. This often leads to the situation where entity tagging, extraction and resolution tasks are hard to separate and are built as an iterative process. Some examples of research reviewed in this section support this view. One such example is the research of Davis et al. (Reference Davis, Veloso, da Silva, Meira and Laender2012), which gives a fast, incremental algorithm based on the expectation maximisation framework. The lazy association classifier (Veloso et al., Reference Veloso, Meira and Zaki2006) is used to perform fast, incremental learning. Starting to learn from a few positive examples for each entity, the algorithm turns some negative into positive labels (or vice versa) in the validation phase. The classifier is updated partially after each label transition and is able to determine the set of rules that need to be updated. The process is repeated approximating the true positive–negative distribution. The method is more accurate and much faster when compared with retrained SVM (Cortes & Vapnik, Reference Cortes and Vapnik1995).

The above approach involves shallow learning from large amounts of data and is typical of many streaming algorithms. Another fast, but much more complex method, designed for the Kosmix system to work with the Twitter firehose, is presented by Gattani et al. (Reference Gattani, Lamba, Garera, Tiwari, Chai, Das, Subramaniam, Rajaraman, Harinarayan and Doan2013). This method combines entity extraction, linking it to a Wikipedia KB entry, classification into a pre-defined topic and assigning KB concept names as tags to tweets. Entities are not only people and locations, but also products, music albums, songs, books, TV shows, sports events, cars and movies. The whole process integrates all these steps together and uses web context for tweets and social context for users to enrich information in tweets. Mentions of entities are scored by their similarity to the contents of links from tweets, tweet tag and KB. Filtering, scoring and tagging is done again as more features are extracted about mentions. Finally, editorial rules are applied to improve accuracy. The method was evaluated using a small ground truth sample of 99 tweets processed manually, and results were compared with Stanford NER and OpenCalais.

Liu et al. (Reference Liu, Zhang, Wei and Zhou2011) use k-Nearest Neighbourhood (k-NN) to pre-label words across tweets, and then conditional random fields (CRF) (Lafferty et al., Reference Lafferty, McCallum and Pereira2001), is applied for fine-grained, tweet-level NER. CRF uses extra information from gazetteers covering common names, countries, locations, temporal expressions, etc. Here gazetteers play the role of a very simple KB. The k-NN and CRF models are retrained after a pre-defined number of tweets are processed. For evaluation, 12 000 manually annotated tweets are used, and precision, recall and F1 (harmonic mean of precision and recall) metrics used as performance measures. Results were compared with two baseline methods: gazetteers dictionary lookup and the target system, but without using k-NN and semi-supervised learning. Recall and F1 were higher on all types of tested entities, while the precision was lower than the baselines. The algorithm can process tweets in a stream-like fashion, but the execution time is not provided.

While the above methods are geared towards fast, online processing, it is possible to perform entity resolution offline as long as the process can be updated and fast enough to catch up with new entities arriving from the stream. The next two methods belong to this category. Both of them use a version of Latent Dirichlet Allocation (LDA) (Blei et al., Reference Blei, Ng and Jordan2003) for labelling, and a KB to constrain the disambiguation. Ritter et al. (Reference Ritter, Clark, Mausam and Etzioni2011) propose an NER method comprising a number of components: part of speech tagging, parsing and NER. Clustering and CRF are used to perform these tasks. A separate SVM model is used to determine if word capitalisation in tweets is informative. Freebase is used for 70% of entities, and the other 30% are labelled using Labeled LDA. The evaluation section reports an improvement over Stanford NER using manually annotated tweets. Most of the components were trained using annotated tweets, which is not a sustainable solution for continuous data streams with concept drift.

Li et al. (Reference Li, Wang, Han, Han, Roth and Yan2013) developed a method for Twitter entity resolution by supplementing KBs with extra evidence from internal documents in the KB and external corpora. Related names to a given entity are first extracted from the KB and then relevant documents are searched for the extra evidence. These other documents are labelled using LDA with labels related to the entity in question and are used to disambiguate the entity. The process of gathering extra evidence can be run offline and used by any disambiguation algorithm. Results compare favourably with Wikifier (mapping entities from given text to Wikipedia) and AIDA (an NED system making use of a weighted mention-entity graph to find the best joint mention-entity mapping). We note, however, that these two methods were not designed or tested on Twitter text by their original authors, therefore the comparison is less reliable.

Although Twitter entity resolution presents a main challenge, there are a number of methods designed to work with other types of documents, such as news and blogs. Li et al. (Reference Li, Wang and Chen2011) proposed person identity matching in databases, based on both personal features (name, date of birth, social security number, etc.) and social features (participation records in social events or crimes, and their roles in these events, e.g. suspect, victim). For matching personal features in the form of strings, a normalised Levenshtein edit distance (Levenshtein, Reference Levenshtein1966) was used, which is the number of edits, deletions and substitutions to transform one string into the other, divided by the longer string size. Social features are compared using a number of similarity measures, such as Jaccard coefficient. Similarity measures are weighted for the contribution to the final similarity decision and weights are learned using Naïve Bayes. The evaluation data set was real police records and the gold standard was created for individuals with the same last name and date of birth. Pre-clustering was used to avoid comparing all pairs. However, adding social features improved the accuracy of the method by only about a couple of per cent.

In Kotov et al. (Reference Kotov, Zhai and Sproat2011), named entities are extracted from correlated bursts of mentions in multiple streams of news articles. The process consists of two stages. In the first stage, bursts of entity mentions are discovered in streams and modelled with a Markov-modulated Poisson process (MMPP) to estimate the temporal coefficients of bursts. In the second stage, these coefficients are used in a dynamic programming algorithm to discover all pairs of streams with temporally correlated bursts. Apart from correlating entities, the process is able to transliterate entity names between different languages. The baseline chosen for comparison is the binning-based normalisation method, which is a simplified MMPP. Results show higher recall values of the method described over the baseline.

An interesting method for NER is presented by Kim and Compton (Reference Kim and Compton2012b), where Stanford NER is combined with RDR to deal with the informality of web documents such as tweets. The approach is not intended as an alternative to Stanford NER or other general entity recognisers, but to improve their performance in a specific domain. The RDR KB is built incrementally while the system is in use; therefore it is able to update the KB as needed. This paper shows examples of errors commonly made by Stanford NER and corrected with RDR and presents a comparison of RDR with Stanford NER on the MIL (Multiple Instance Learning) data set, which is a sample of sentences typically used on the Web. On all types of entities, RDR is able to improve the performance of Stanford NER. Additionally, it requires a smaller number of documents compared with other NER methods based on machine learning.

Geo-locations are important features, for example in security and marketing applications, but if not provided directly, identifying them in streaming data is challenging and requires contextual understanding of messages. Often multiple locations are reported, such as the location of the incident and the location of the reporter. In the EMBERS system (Ramakrishnan et al., Reference Ramakrishnan, Butler, Muthiah, Self, Khandpur, Saraf, Wang, Cadena, Vullikanti, Korkmaz, Kuhlman, Marathe, Zhao, Hua, Chen, Lu, Huang, Srinivasan, Trinh, Getoor, Katz, Doyle, Ackermann, Zavorin, Ford, Summers, Fayed, Arredondo, Gupta and Mares2014) location (city, state and country) is detected using Probabilistic Soft Logic (Bröcheler et al., Reference Bröcheler, Mihalkova and Getoor2010) with a model that combines and weighs different evidence types, such as location tokens, and organisation and person names. In tweets, geo-location features are sparse and an explicit location is rarely given. Cheng et al. (Reference Cheng, Caverlee and Lee2010) developed a method for identifying a city-level location for tweets, even in the absence of location tokens. The method is based on the observation that specific keywords have high local focus, and when taken together, can provide a probabilistic identification of a place. The challenge is the selection of appropriate keywords. For this purpose a set of keywords was analysed and selected with satisfactory geo focus and dispersion. In testing, the method was able to identify 30% of users within 10 miles. This may not be sufficient for many applications, but it gives an idea of the difficulty of the problem. Better results are obtained by Li et al. (Reference Li, Wang and Chen2011), who explore two kinds of relationships: the probability of following a given distance and the probability of using venue names given the user distance to the venue. The method places around 50% of users within 10 miles.

In summary, NER and NED methods for entity extraction rely on a KB or multiple streams of documents. Common problems found in the methods are the need for prior training on fixed, annotated documents, which hinders their application in streams, and poor data set and baseline selection for evaluation and comparison.

3.3 Relation extraction

The focus of this section is on extracting relations that connect entities in a KB. Zhu et al. (Reference Zhu, Nie, Liu, Zhang and Wen2009) extend the Snowball method of Agichtein and Gravano (Reference Agichtein and Gravano2000) to start with a handful of examples (bootstrapping) and iteratively generate new extraction patterns together with their weights using a Markov logic network (MLN). Patterns are selected using ℓ1-norm regularised maximum likelihood estimation. Their KB system called StatSnowball can extract pre-defined relations as in Snowball or a general type of relation. General patterns are built using shallow NLP: at the entity level these patterns are part of speech tag sequences between entities selected using the MLN. At the sentence level, relations are extracted taking into account tokens surrounding the entities. Evaluation shows that StatSnowball performs better than CRF on all tested entity types except verbs.

Bootstrapping is a popular technique to find high probability relations as seeds and then use them as training examples to find more relations. Bootstrapping dictionaries can be built manually or learned, starting with a handful of seeding examples for a semantic category (Riloff & Jones, Reference Riloff and Jones1999). Etzioni et al. (Reference Etzioni, Cafarella, Downey, Popescu, Shaked, Soderland, Weld and Yates2005) start with automatically created general extraction patterns from well-known relations, for example ‘such as’, then create extraction rules that help to extract more patterns. A common problem with automatic extraction, however, is semantic drift, where the meaning of subsequently extracted patterns drifts from the original seeds. Curran et al. (Reference Curran, Murphy and Scholz2007) present a method to reduce drift using mutual exclusion bootstrapping. Entities are divided into a number of semantic classes under the assumption that they are mutually exclusive (do not contain the same entity names) to prevent entities from crossing class boundaries. Despite the automated extraction process, the method requires a substantial amount of human knowledge (semantic classes, stop classes, filtering rules). Another drawback is that all n-grams need to be in memory at processing time. In summary, bootstrapping starts with well-known relations, using them as training examples, then proceeds to extract more relations while controlling semantic drift.

The Kosmix KB (Deshpande et al., Reference Deshpande, Lamba, Tourn, Das, Subramaniam, Rajaraman, Harinarayan and Doan2013) is constructed from Wikipedia and other data sources. Relations for the KB are extracted in a variety of ways from Wikipedia info boxes, templates and the article text. Each source of relations is associated with certain relation categories by extraction rules. A small number of extraction rules can be used to extract a large number of relationships. Synonyms are captured from redirection pages and homonyms from disambiguation pages as well as additional properties, such as Twitter id, Web URL and co-occurring concepts.

Roth et al. (Reference Roth, Barth, Wiegand, Singh and Klakow2013) present the TAC 2013 winning algorithm in the slot filling competition. The task is to find relations for entities given in queries. Query expansion, entity retrieval and candidate matching are required as first steps. Each type of relation is modelled by training a distantly supervised SVM classifier. The distant supervision training set is obtained from Freebase relations and from hand-crafted seed patterns. Prediction is done for each pair of entities and a candidate sentence which could contain the relation.

An important conclusion to draw from the above review is that extracting entities and relations cannot be done using one well-defined method and rather requires an integrated approach guided by human judgement.

3.4 Event detection and tracking

Event detection and tracking in data streams is important in many domains, such as national security, for a number of reasons. First, predicting events, such as civil unrest, allows for resource planning and deployment for preventive action. Second, detected events can be linked with particular individuals and places, which helps in building a summary of interesting events related to an entity or location.

Before reviewing state-of-the-art work in this area, we first look at the definitions of events, and in particular, how to distinguish events from non-events. It is remarkable that, despite a rich literature in Computer Science on event detection, the notion of an event is rarely defined and often the definition can only be inferred from the method description. This is the case for Schrodt et al. (Reference Schrodt, Davis and Weddle1994), which is the earliest work on automatic event detection. A sentence defines an event if the sentence structure is subject–verb–object and the verb is in a dictionary of pre-defined event verbs (thus a class of events is defined by stipulation). In research by Huang and Riloff (Reference Huang and Riloff2013), event recognition is also based on a dictionary, which serves as a bootstrap for learning event agents and phrases. Fung et al. (Reference Fung, Yu, Yu and Lu2005) defines an event as a minimal set of ‘bursty’ features occurring in a time window over a maximal set of documents (which clearly could also cover non-events). SARSFootnote ⁵ is given as an example of an event, however, the main problem with this definition is that bursty features may refer to both events and topics. One could argue that SARS, the disease, is a topic rather than event. Becker et al. (Reference Becker, Naaman and Gravano2011) define an event in the context of Twitter as an occurrence associated with a time period and discussed in a set of messages (which again seems too general). Yang et al. (Reference Yang, Carbonell, Brown, Pierce, Archibald and Liu1999) list document features specific to an event: time proximity, bursty numbers of documents, change in vocabulary and a relatively brief time window of occurrence.

While the above Computer Science definitions are focussed on how events are identified, the psychological approach to events takes a different perspective (Zacks & Tversky, Reference Zacks and Tversky2001). According to this definition, events are perceived as objects bounded in space and time. For example, SARS is an event as long as associated messages talk about a particular SARS outbreak in a particular place, and are not about treating SARS, etc. The main difference between events and topics is that, unlike objects, single particular events can be experienced only once.

In our view, the basic property of events which distinguishes an event from a topic is that an event involves a change of state, that is states are conceptually prior to events, and events are defined by state changes. In the above example, a SARS outbreak in a particular place and time causes a change in the number of sick people, etc. From a linguistic perspective, Monahan and Brunson (Reference Monahan and Brunson2014) recently discuss a number of such qualities of ‘eventiveness’ of event descriptions: occurrence (signalling a change in state), spatio-temporal grounding, lexical aspect (time boundedness and duration), agency (degree of actor control over an event), affectedness (degree of affect on event participants), actuality (modality of an event description, relating to possibility or uncertainty) and specificity (generic, habitual or specific). The idea of eventiveness may be useful in the context of event mining, insofar as this involves the analysis of documents containing event descriptions.

As with other applications of data stream mining, detecting events in streams presents additional problems in terms of memory and stream catch up time. Yang et al. (Reference Yang, Carbonell, Brown, Pierce, Archibald and Liu1999) extract events from news documents using two clustering algorithms: group-average multi-pass hierarchical (GAC) and single-pass non-hierarchical clustering (INCR). Terms are weighted by tf-idf (term frequency, inverse document frequency) and the distance measure is standard cosine similarity. The INCR method simply clusters documents using a pre-defined distance threshold and uses a linear decay factor in a fixed window for down-weighting older documents. Event tracking is treated as a separate fast learning task for which k-Nearest Neighbour and Decision Tree classifiers were selected. A non-C4.5 Decision Tree was specially constructed for fast incremental learning and achieved the best results in event tracking as measured by the micro-F1 metric. For the event detection task, as expected, GAC achieved better results, but we believe with worse time efficiency, not reported in this paper. Another problem is the sensitivity of the INCR method to the threshold, which needs to be selected manually. A threshold that is too small may pick up noisy events, while one too large may cluster a number of different events together.

The work of Fung et al. (Reference Fung, Yu, Yu and Lu2005) mentioned above detects events based on the probability of features in a binomial distribution. Then the minimal number of bursty features is determined to make a bursty event by maximising the probability of the set of bursty features in a document stream. Experiments conducted on 66 300 news documents confirmed that events can be detected, but quantitative measures are not provided, that is precision, recall, F1, etc. The algorithm is an offline processing method, although an incremental extension may be possible by running bursty feature identification and event detection in parallel.

Becker et al. (Reference Becker, Naaman and Gravano2011) attempt to construct an online method for event detection in the Twitter stream with the main goal of distinguishing events from non-events. The procedure adopted is to first cluster tweets and then eliminate non-event clusters. The clustering method is similar to INCR (Yang et al., Reference Yang, Carbonell, Brown, Pierce, Archibald and Liu1999), with the threshold parameter tuned during the training phase. Weka classifiers (Witten et al., Reference Witten, Frank and Hall2011) were used for determining event clusters trained on a set of temporal, social, topical and Twitter-centric features. Evaluation was performed on 374 annotated clusters used for training and 300 clusters for testing. Results measured as F1 are only compared with the standard Naïve Bayes algorithm showing the superiority of their approach. Despite using an online clustering technique, very simple in fact, nothing else suggests that the whole process can be used for real stream event detection and it was not evaluated as such. It is not known how the threshold was set during the training phase. Use of a fixed threshold would certainly not work as well in a data stream scenario with concept drift. The authors admitted that this problem is not the focus of this paper but the subject of future research. The second problem for real online implementation is the two-stage clustering and classification process. This can possibly be resolved as two independent processes running in parallel with some implications on stream catch up time.

Becker et al. (Reference Becker, Iter, Naaman and Gravano2012) focus on retrieving documents from social media about an event identified by title, description, date/time and venue in typical event sites, such as Last.fm, Eventbrite and Facebook events. The process consists of two steps: (1) a precision-oriented query to first retrieve, perhaps a small number, of documents highly relevant to the event, and (2) a recall-oriented step to expand the query using terms from the first step. The method was trained on 329 event records and tested on 393 events. In the precision step, documents related to the event were retrieved and scored by the number of queries returning a particular document. In the recall step, n-gram joint probabilities were used, returned by the Microsoft Bing search engine. Queries were generated and ranked using a number of n-gram and temporal techniques. Queries and retrieved documents for a random set of 60 events were manually annotated and compared with machine results using the Jaccard coefficient. The most similar results to annotated documents were obtained from Twitter using the Microsoft n-gram score. Interestingly, combining Twitter documents with Flickr and YouTube tags did not improve overall results, indicating a low accuracy of tags. Although the whole method described in this paper is offline in nature, it may be interesting from the point of view of enriching online information for use in constructing event summaries.

The research of Huang and Riloff (Reference Huang and Riloff2013) introduced above uses a seeding dictionary as a bootstrapping technique to recursively harvest more event expressions and identify events. Results obtained on a small sample are successfully compared with SVM. The method, although interesting, is not suitable for online implementation as it requires multiple scans of documents. Silva and Riloff (Reference Silva and Riloff2014) found that pre-classifying users into user types helps with event recognition.

Finally, in specific domains, users may not be interested in all events but only in some class of events. For example, a football match may not normally be an interesting event, but may be of interest if a threat is involved. Interestingness measures (McGarry, Reference McGarry2005; Geng & Hamilton, Reference Geng and Hamilton2006) may need to be developed or extended for events in further research, and potentially applied to all the above methods. In addition, most of the methods discussed above are implemented and tested as offline processing systems; therefore additional research is required to adapt them to data stream processing.

4.1 Knowledge representation for ontologies

A simple knowledge representation scheme at its most basic layer are triples <subject, predicate, object>, for example <‘Tom’, ‘has son’, ‘Charlie’>. The next layer expresses types and classes of concepts and relations and is represented by an ontology language. The most popular languages for representing ontologies are Resource Description Framework (RDF) (Pan, Reference Pan2009) and Web Ontology Language (OWL) (Antoniou & van Harmelen, Reference Antoniou and van Harmelen2009), both based on XML. These languages provide common portable formats for exporting, storing and importing ontologies in files. RDF is the W3C recommendation for semantic annotations in the Semantic Web and provides a formal description of the <subject, predicate, object> triples in the form of XML statements. It is limited to a class and property hierarchy with domain and range definitions for these properties. OWL, in contrast, allows for defining cardinalities of object relations, data-type attributes and the use of logical operators in definitions, for example union of classes. The next level of representing ontologies can be seen as graphs and patterns and are more related and closer to actual sources of knowledge. Some examples of these representations follow.

The Snowball system (Agichtein & Gravano, Reference Agichtein and Gravano2000) extracts relational tuples from newspaper documents and stores them in database tables for using in querying and data mining tasks. Tuples are extracted using patterns of pre-defined relations, such as <LOCATION>-based <ORGANISATION>. This requires a small set of seed patterns and document collection to generate high coverage patterns. Similarly, the Knowledge Vault (Dong et al., Reference Dong, Gabrilovich, Heitz, Horn, Lao, Murphy, Strohmann, Sun and Zhang2014) stores information in the form of RDF triples (subject, predicate, object), for example (<person>, born in, <place>).

Kumar et al. (Reference Kumar, Raghavan, Rajagopalan and Tomkins1999) represent an early approach to extracting knowledge from the Web (spread sources of information). Knowledge was represented as a web graph. The technique they used was to extract information from subgraphs based on topic-related web pages. This model identifies cliques as sets of web pages containing links to one another. By measuring links between them and applying filters on these metrics, it was possible to identify and index communities on the Web and create a KB of web communities.

A different technique is used in the Cayley knowledge graphFootnote ⁶, a successor of the Google Knowledge Graph. Instead of storing all entity properties in a database table, each property is represented as a relation (Figure 4), for example person ⇒ height. At first this seems an excessively complex way of representation, but has the advantage of flexibility in accessing, changing and updating the graph.

Figure 4

Cayley graph structure

4.2 Building, maintaining and updating ontologies

Building, maintaining and updating ontologies generally refers to a two-stage process: (1) finding entities and their relations, and (2) matching them with existing entries in an ontology to expand or update its contents. The generation of ontologies has been extensively investigated and implemented with a number of different techniques. Figure 5 shows a basic classification of methods.

Figure 5

Classification of methods for ontology building and maintenance

The first group of methods to build ontologies are manually based, with Freebase (Bollacker et al., Reference Bollacker, Tufts, Pierce and Cook2007) and DBpedia (Mendes et al., Reference Mendes, Jakob and Bizer2012) being the most representative examples. In Freebase, the most remarkable achievement is scalability and collaboration. The platform allows people around the world to collaborate in the construction of the ontology. The ontology is stored in a graph-based structure to allow easy storing and updating of entities and its relations. DBpedia is another example of the crowdsourcing generation of ontology. The main difference is that the former works with the English language, the latter is being constructed from several languages.

On the other hand, automated methods have been recently designed to tackle the main problems of a purely manually maintained ontology. There are different approaches to automated and semi-automated generation of ontologies. Bottom-up techniques address the generation problem from instances, collapsing entities into related groups or categories. These are represented as hierarchical models (e.g. Van Dyke Parunak et al., Reference Van Dyke Parunak, Rohwer, Belding and Brueckner2007). Top-down methodologies begin from a general concept and spread the conceptualisation to more specific concepts. XTREEM and TRUCKS are examples of such techniques (Brunzel, Reference Brunzel2008; Maynard et al., Reference Maynard, Li and Peters2008).

Unsupervised learners, such as KnowitALL (Etzioni et al., Reference Etzioni, Cafarella, Downey, Popescu, Shaked, Soderland, Weld and Yates2005), are based on pattern recognition extraction rules that identify classes and subclasses across the Web. An unsupervised mechanism allows automating the lengthy manual process of generating the basic categories of knowledge in a structured way. The main problem of unsupervised techniques is managing ambiguity. The Kosmix KB (Deshpande et al., Reference Deshpande, Lamba, Tourn, Das, Subramaniam, Rajaraman, Harinarayan and Doan2013) is constructed by processing a Wikipedia XML dump, treating pages as nodes and links as edges. This does not create a taxonomy automatically, as there are cyclic dependencies to be removed and top categories to be fixed. The top categories are pre-defined and placed below the root of the tree. The main problem is that automated generation of a KB is noisy, resulting in inaccurate ‘facts’ and rules that have to be curated and checked for consistency.

Semi-supervised methods such as Dynamo (Ottens et al., Reference Ottens, Aussenac-Gilles, Gleizes and Camps2007) and expert-based ontology generation like Protégé (Tudorache et al., Reference Tudorache, Noy, Tu and Musen2008) face the high cost of manual disambiguation using expert knowledge when curating and maintaining the KB. The main problem for supervised and semi-supervised methods is the lack of training data. Some large annotated data sets, such as Gigaword (Napoles et al., Reference Napoles, Gormley and Van Durme2012), Linguistic Data Consortium data sets or the Multi-Perspective Question Answering corpora, may be available for training.

Ontology generation from scratch and ontology update with new entries may use similar methods, though with different considerations. Large KBs require two intervening steps: regular updates (re-building from scratch or incrementally) and maintenance (curation and consistency checking). These two tasks may interfere with each other and different approaches are needed to make them work together. In the Kosmix KB (Deshpande et al., Reference Deshpande, Lamba, Tourn, Das, Subramaniam, Rajaraman, Harinarayan and Doan2013), the solution is to capture most of the human curation rules as commands, then apply these commands again when the KB is refreshed, once each day. Refreshing the KB is done by re-running the entire KB generation method from scratch. An alternative is to maintain the consistency of the ontology at update time by checking the consistency of all axiomatic rules, removing rules with the lowest confidence value until inconsistencies are eliminated (Volker et al., Reference Volker, Haase and Hitzler2008).

Probabilistic KBs are becoming increasingly popular due to their power to express uncertainty in human knowledge. In practical terms, they can usefully rank the correctness of knowledge extraction with a confidence factor calculated by probabilistic methods. Chen and Wang (Reference Chen and Wang2014) use an MLN to represent uncertain facts and rules in the KB called ProbKB. An MLN is a set of weighted first-order logic expressions, where weights indicate the degree of truth of the formula. Constraining rules are learned in the form of Horn clauses from web text. Inference on entities, relations and rules is done using a relational massively parallel processing database. A number of techniques were used for curating ProbKB, including functional and semantic constraints, and rule ranking (taking only the top significant rules). Results show much faster runtime compared with a similar probabilistic, relational KB. MLNs are also used in StatSnowball (Zhu et al., Reference Zhu, Nie, Liu, Zhang and Wen2009), as described above.

Another very large probabilistic KB, Google’s Knowledge Vault (Dong et al., Reference Dong, Gabrilovich, Heitz, Horn, Lao, Murphy, Strohmann, Sun and Zhang2014) assigns a probability of correctness to each triple (subject, predicate, object). Supervised machine learning is used for fusing prior knowledge from existing KBs (Freebase, YAGO, DeepDive, TAC competition methods) with extraction from the Web. The probability of correctness for each triple is calculated based on agreement between different extractors and priors.

4.3 Evaluating knowledge base construction

This section compares techniques for KB population and discusses the important issue of evaluating the techniques and measuring the quality of the resulting KBs.

A common way to evaluate the KB population ‘task’ is to compare results with a gold standard. While this method enables comparison of various techniques on the same footing, it suffers from two major drawbacks: the huge amount of human work required to prepare gold standard data sets and unavoidable bias (Biemann, Reference Biemann2005). Ontology learning is difficult to evaluate and human annotators tend to disagree with one another, which then requires many annotators to complete the same task in order to apply agreement measures (Dellschaft & Staab, Reference Dellschaft and Staab2006).

The evaluation of both steps in KB population, extracting entities and relations, and fitting them into the ontology graph structure, can be made using common metrics from information retrieval. As pointed out by Maynard et al. (Reference Maynard, Li and Peters2008), however, precision, recall and F1 are not really sufficient for evaluation, as these metrics are based on a binary classification of results (counts of true or false). In ontology classification, credit should be given for a partial match, for example Researcher to Lecturer. Given a key and a response, Maynard and Peters propose a balance distance metric (BDM) that combines various counts from the ontology hierarchy, such as the distance from the most specific common parent to the root, the length of the shortest path to the common parent and the average chain length of all chains in the ontology containing key, response, and both key and response. Augmented metrics use BDM as a weight to define a weighted measure of precision, recall and F1. Experiments show that the augmented metrics give better differentiation of results when comparing learning algorithms.

Next, we present the comparison of results from the TAC competitions held in 2010, 2011 and 2013Footnote ⁷, comparing successful approaches to KB population in two categories: entity linking and slot filling. The conclusions drawn from these results are useful for comparing different methods, therefore we devote more attention to these reviews.

The task of entity linking requires matching a textual ‘mention’ of a named entity with a corresponding entry in the KB, or determining that such an entry does not exist (Ji et al., Reference Ji, Grishman, Dang, Griffitt and Ellis2010). Micro-average accuracy was used to measure task performance. All competing systems performed best on person entities and worst on geo-political entities. Most of the top 10 algorithms used supervised learning-based lexical levels and name tagging features, but the top two methods used non-supervised learners. Using semantic features improved the task performance by a few percentage points on average. Many methods used Wikipedia structured information (links, boxes) and reported improved performance.

The goal of slot filling is to provide missing attributes in a KB from a set of documents by giving the best matching document for each missing attribute. A reference KB was constructed from a Wikipedia snapshot. Results from this task were categorised by human assessors as correct, inexact, redundant or wrong. Summarising the results for 2010 based on Ji et al. (Reference Ji, Grishman, Dang, Griffitt and Ellis2010), the first thing to notice is that one of the methods (cortex) used an additional two million extensively annotated documents and achieved more than twice better performance compared with the second best. A variety of techniques were used by the successful methods, including distant learning, bootstrapping, question answering and rules. Most of the systems used a single technique, though one successful system, CUNY, adopted a hybrid approach. About 24% of slots required inference from multiple sentences, therefore required combining existing information retrieval approaches with distant learning and reasoning. Some slot filling methods used an external KB, such as Freebase, DBpedia and YAGO, but this did not improve their results much, as these KBs covered only a portion of entities used in the competition.

In the TAC 2011 competition (Ji et al., Reference Ji, Grishman and Dang2011), a number of new trends emerged. First, more statistical methods were used, for matching name variants (statistical classification) and extracting topic features with topic modelling using LDA. Second, new learning algorithms, such as Random Forest and ListNet were introduced for ranking candidates, along with existing SVM for Ranking (SVMRank) and maximum entropy (MaxEnt). According to Chen and Ji (Reference Chen and Ji2011), ListNet achieves the best performance compared with SVMRank, MaxEnt and other algorithms using the same features and resources. Results obtained by one of the 2011 systems indicate that entity context and profile-based features can significantly improve the performance of person and organisation entity extraction, but decrease the performance of geo-political entity extraction, because global, not local, features are dominant in these entities. Another successful method for entity linking, similar to the integrated approach mentioned in Section 2.3, explored the idea of extracting and disambiguating multiple entities from many documents at the same time, expanding the KB and iterating this process.

Two other methods from the same TAC 2011 competition are worth mentioning. Monahan et al. (Reference Monahan, Lehmann, Nyberg, Plymale and Jung2011) present entity linking using cross-document co-reference in a number of stages: (1) clustering mentions with identical normalised strings, (2) grouping mentions in each cluster from step 1 using a distance calculated with logistic regression, which resolves polysemy of mentions (mentions with different meaning would be more distant), (3) finding synonym mentions if they can be linked to the same KB or Wikipedia entry or embedded in a common phrase, and (4) linking of each cluster from stage 3 to a KB entry by voting of mentions in the cluster for a KB entry. Of significance due to the limited amount of work in this area on non-English languages, this paper evaluates two methods of linking multilingual mentions: translate and link to a KB and link to a native KB without translation. Interestingly, though as expected, linking native entities gives better performance. Zhang et al. (Reference Zhang, Su, Chen, Wang, Toh, Sim, Cao, Lin and Tan2011) also combine a number of techniques for entity linking: acronym expansion, instance selection and topic modelling (with LDA). In the first step, acronyms are expanded to full names using SVM trained on matching entities. Next, for each KB entry, name variants are produced from Wikipedia pages. Finally, generated candidates are ranked by an algorithm using a learning to rank technique and SVM.

TAC 2013 (Surdeanu, Reference Surdeanu2013) required that provenance information was included for both entity linking and slot filling. This is a reasonable requirement, as in many domains decisions have to be justified by giving the reason for a particular result. For English slot filling, the top results were achieved by Roth et al. (Reference Roth, Barth, Wiegand, Singh and Klakow2013), mentioned in Section 3.3. The distant supervision used in this and other methods in recent years is a characteristic trend in data mining supported by KBs. The second top method, called RPI-BLENDER (Yu et al., Reference Yu, Li, Cassidy, Li, Huang, Chen, Ji, Zhang and Roth2013), used multiple sources for truth verification and a knowledge graph for the best path resolution from discovered elements to slot filler nodes. It is interesting to notice that the F1 score for these methods, although higher than in previous years, is still relatively low (around 40%), indicating the difficulty of the task of automatic identification of missing parameters in KBs.

5.1 Entity linking

Entity linking is a main step in both KB population and usage. In the KB population task, entity linking allows identification of related entries in the KB and expansion of the KB with new candidate entities. For KB usage, such as query answering or summarisation, related entities from the KB are used to build a response. In Section 4.3, we referred to entity linking in the context of KB evaluation. Those methods, however, were designed and optimised specifically for the TAC competition. In this section, we describe a few more techniques used for entity linking that may be suitable for more general practical applications.

Stoyanov et al. (Reference Stoyanov, Xu, Oard, Lawrie and Finin2012) use context documents for both mentions and KB entities. Given a document with entities to be linked, a set of context documents is produced, extended by Wikipedia documents (for news) or e-mail addresses (for e-mails). The entities from this set of documents are then matched with a similar set of pre-selected entities from the KBs by a resolver. The entities are then fused and the process is repeated until a desired confidence (or number of iterations) is reached. Details of the methods used for matching entities with the KB are not provided.

Twitter is an important source of information in many applications, because it brings the most up-to-date information in a streaming fashion, but processing tweets is a challenge due to their brevity and the language used. Recognising and matching concepts in tweets with KB entries facilitates querying and summarisation. Liu et al. (Reference Liu, Li, Wu, Zhou, Wei and Lu2013) use context to match entities from tweets with KB entries (Wikipedia is treated as a KB). Tweet entities are extracted by a named entity recogniser, and a paraphrase (name variations) dictionary is used to resolve spelling errors and abbreviations. The idea is to resolve a collection of entities simultaneously with matching KB entities using context. Similarity between entities and mentions is calculated using a feature vector comprising features such as edit distance between mention and entity, occurrence of the entity in the title of a Wikipedia entry, similarity between tweets (cosine similarity, same or different Twitter account, containing the same hashtag, etc.). The results were favourably compared with two baseline methods that use Wikipedia for linking and disambiguation.

Other research on matching tweets with Wikipedia (called ‘wikification’) is described by Huang et al. (Reference Huang, Cao, Huang, Ji and Lin2014). Graph-based semi-supervised learning algorithms are used for the task. To extract meaningful mentions from tweets, information from multiple tweets is used for collective inference for both mention identification and disambiguation. All related mentions and their corresponding Wikipedia concepts connected by weights form a relational graph. Weights are calculated as a linear combination of scores from different types of relations. The method is evaluated on a small human-annotated data set of 502 tweets. Two further examples of linking tweets to news are as follows. In Guo et al. (Reference Guo, Li, Ji and Diab2013), hashtags from tweets are compared with entities in news using a graph-based latent variable model. The performance of the method, however, is only a few per cent better than plain information retrieval. A more complex method presented in Hua et al. (Reference Hua, Wang, Wang, Zheng and Zhou2015) is built combining text segmentation and entity disambiguation with prior knowledge from Probase. Obtained accuracy results show significant improvement over disambiguation methods based on similar instances.

5.2 Question answering

The question answering task involves complex matching of semantic structures (entities and relations) with that of a KB. Once the matching is established, sub-concepts and super-concepts can be used for query answering.

In the Kosmix system (Deshpande et al., Reference Deshpande, Lamba, Tourn, Das, Subramaniam, Rajaraman, Harinarayan and Doan2013), query understanding starts with information extraction from the query using the KB as a dictionary. After resolving potential homonyms, the task returns a set of concepts from the KB mentioned in the query as the understanding of that query. Deep Web search works in similar way, except that the query refers to the web information sources linked with the KB. Mentions from the query are matched with these links and the resulting sources are combined to form the answer returned to the user.

Wang et al. (Reference Wang, Zhao, Wang, Meng and Wen2015) treat queries as short texts and describes a method for short text understanding using KBs. This problem is similar to query answering in that the query needs to be understood (parsed semantically and linked to related concepts) before answering. Unlike news articles or other longer documents, short texts such as tweets do not contain sufficient information to perform semantic parsing or topic modelling separately. The approach taken in this paper is to organise terms, concepts and all relevant signals into a graph, and use an iterative random walk approach to arrive at an understanding of a text. Probase concepts are clustered into 5000 clusters, each of which is referred to as a concept itself. Non-instance words in the text, such as verbs and adjectives, are linked to concepts by a probabilistic bridging of these words to concepts in a large set of web documents. These elements are used in a semantic network, in which edges express the strength of relationships between elements. This enables a probabilistic mapping of terms from the query to concepts in the graph to be made by performing multiple rounds of random walk. The results show an advantage of the method over a number of approaches, such as Bayesian analysis for conceptual similarity, LDA for co-occurrence relationships with Probase and random walk.

Yao and Van Durme (Reference Yao and Van Durme2014) implemented a query answering mechanism based on information extraction combined with a web-scale corpus. In addition, NLP techniques like ReVerb are used in order to deal with the informality of queries. The system splits a query into entities, topics and question words. The topic words are used to match with the nodes of Freebase. All triples (arg1, predicate, arg2) related to the topic are extracted as a subset or a subgraph of the KB. The extraction task is defined as maximising the probability P(R|Q) of a relation R, given question Q as a word vector, using a Naïve Bayes assumption. Results show an improvement in performance of 34% in F-measure (48 against 31%) against another Freebase semantic parser of Berant et al. (Reference Berant, Chou, Frostig and Liang2013).

QALD (Question Answering over Linked Data), an initiative to compare question answering methods over knowledge graphs, is an open research challenge run for the last few years. The task is to answer a question, which is given in natural English or another language. We briefly discuss the top methods from 2013 and 2014, starting with QALD 2013. The squall2sparql system proposed by Ferré (Reference Ferré2013) translates a query from a controlled natural language for English, called SQUALL, to an intermediate logic representation and then to SPARQLFootnote ⁸. The produced query can then be used with a SPARQL endpoint of a KB, returning results. The quall2sparql system achieves the best performance due to the fact that the original queries in natural language are manually translated into SQUALL, thus removing many ambiguities.

CASIA (He et al., Reference He, Liu, Chen, Zhou, Liu and Zhao2013) performs a transformation from natural language queries to SPARQL queries in order to improve matching to the DBpedia KB. The system first generates a set of query triples in the form <subject, predicate, object> and converts them to ontology triples. These triples are then converted into SPARQL queries and used to query a KB. Returned answers are scored and combined for the same score. Although precision and recall on the gold standard were low (35 and 36% on the test data set), the research shaped a baseline for later work. Other top performing systems such as Scalewelis, RTV and Intui2 (Cimiano et al., Reference Cimiano, Lopez, Unger, Cabrio, Ngomo and Walter2013) used syntactic patterns and statistical approaches, including hidden Markov models and tree parsing engines.

The QALD 2014 challenge included three tasks: multilingual question answering, biomedical question answering over interlinked data and hybrid question answering from both structured and raw text from DBpedia. A discussion of results is presented by Unger et al. (Reference Unger, Forascu, Lopez, Ngomo, Cabrio, Cimiano and Walter2014). All submissions for the first task were in the English language only. The third task did not have any submissions. The best performer in the first task was the Xser system with a precision of 72%. Phrases are labelled with categories corresponding to KB entries, that is entity, relation or category, using a trained perceptron. The query intention represented as dependency between phrases is modelled as a directed acyclic graph, where nodes are phrases and edges are relationships. This builds a KB-independent structure which is then mapped to a concrete KB. The Xser system can be further improved by removing the need for human-created training examples and avoiding downstream error propagation.

The second best system in the question answering task was gAnswer, proposed by Zou et al. (Reference Zou, Huang, Wang, Yu, He and Zhao2014). Similar to Xser, it uses a semantic query graph to model the intention of the question. This graph is matched with subgraphs of the KB, assuming they are in RDF format. Disambiguation of matching is done at the query evaluation stage, which is easier and saves on processing time. Therefore, this system achieves good runtime performance with about 1 second per query.

An alternative approach that does not make use of a general KB of facts to directly answer questions is exemplified by the IBM Watson system (Ferrucci, Reference Ferrucci2012). The approach taken is to dynamically search a large number of data sources in order to find an answer to a given question. The aim of the system is to efficiently extract and evaluate candidate answers in order to find the most likely answer, using learned models to weigh competing evidence. Watson uses a ‘knowledge base’ called PRISMATIC, organised as a bag of frames, that contains domain-specific linguistic knowledge to assist in finding answers in these data sources (Fan et al., Reference Fan, Kalyanpur, Gondek and Ferrucci2012), for example that presidents win elections, countries annex regions, etc. This approach is feasible when answers to questions can be found without using extensive inference, but rather from direct matches between query expressions and text snippets in the data sources where the answers are contained.

There are a number of conclusions that can be drawn from this section. First, there is no simple technique that can address both entity matching and text understanding. Most successful methods use a holistic approach with iterated running of many stages of processing. Many successful solutions with different techniques achieve similar results. Second (and related to the first), including context always helps. The context comes in different forms: processing many entities at the same time, or using a large set of web documents or an external large KB. Therefore, the choice of methods for a particular problem depends on the availability of data sources, ease of implementation and other requirements such as runtime. Finally, a system should be able to be rapidly adapted to incorporate new data sources and new types of knowledge.

5.3 Summarisation

In this brief section we consider the use of KBs for automatic summarisation of text, for example news articles. We cannot locate any research methods that explicitly use KBs for article summarisation, but looking at many existing summarisation techniques, we believe that such use could be beneficial. This is because summarisation often relies on additional context (Aggarwal & Zhai, Reference Aggarwal and Zhai2012: Ch. 3), such as links to other information or contents of user queries. A KB could provide such context. Other summarisation methods, such as sentence scoring (Nenkova & McKeown, 2012), clustering and topic models also have the potential to improve when using a KB. These hypotheses, however, need to be tested in future research.

A related problem is entity summarisation where information, including a timeline, is provided for a given entity, such as a person or organisation. Such summaries can be generated automatically or combining manual and automatic generation. The work of Althoff et al. (Reference Althoff, Dong, Murphy, Alai, Dang and Zhang2015) is an example of the latter approach, focussing specifically on generating a timeline for a given entity of interest using a KB with timestamped facts, such as Freebase. In the first step, candidate events for the entity are extracted from the KB by exploring related entities. In the second step, events are selected from these candidates using entity and date relevance measures. Events with the same entity and timestamp are merged to form compound events. Event descriptions are created in part manually by defining 100 frequent templates, and for the rest by concatenating the English names of the corresponding predicates and entities.

5.4 Event extraction and prediction

In Section 3.4, we discussed the general issue of event detection and tracking. In this section, we describe two event detection methods that use KBs.

Rusu et al. (Reference Rusu, Hodson and Kimball2014) implement a method for extracting events from news articles with the use of the BabelNet KB. They use an unsupervised information extraction technique to discover events, in contrast to supervised classification of events into pre-defined types. Verbs identified as event triggers and their arguments are extracted from a dependency tree produced by ZPar, the dependency parserFootnote ⁹. WordNet super-senses, BabelNet senses and hypernyms are used for event argument disambiguation. Events are clustered using the Chinese Whispers algorithm and a distance measure based on word counts in the sentence and super-senses from WordNet to obtain a generalised representation of events. Evaluation is performed by manually assessing a number of extracted events for completeness.

Asr et al. (Reference Asr, Sonntag, Grishina and Stede2014) apply an ontology for event co-reference. The task is to cluster events in various news articles that are referred to together. The ontology consists of three layers: event classes, for example killing, earthquake; event instances; and event mentions in news. Each class of events has its own set of specific attributes. The ultimate goal is to match mentions from news with the class and instance of event. Class identification is performed with the help of WordNet synsets. Instance identification within the class is done by matching event attributes against the news. It would be useful to compare the results of event clustering with and without the use of an ontology, however, results are not provided in this paper.