Inductive Entity Typing Alignment

Abstract

Aligning named entity taxonomies for comparing or combining di↵ erent named entity extraction systems is a di cult task. Often taxonomies are mapped manually onto each other or onto a standardized ontology but at the loss of subtleties between di↵ erent class extensions and domain specific uses of the taxonomy. In this paper, we present an approach and experiments for learning customized taxonomy alignments between di↵ erent entity extractors for di↵ erent domains. Our inductive data-driven approach recasts the alignment problem as a classification problem. We present experiments on two named entity recognition benchmark datasets, namely the CoNLL2003 newswire dataset and the MSM2013 microposts dataset. Our results show that the automatically induced mappings outperform manual alignments and are agnostic to changes in the extractor taxonomies, implying that alignments are highly contextual.

1 Introduction

Named recognition and classification is an important task in providing more fine-grained access to textual resources than simple keyword search can o↵ er. In recent years, many named entity recognition and classification tools have become available such as DBpedia Spotlight [ 8 ] and OpenCalais4. Each of these tools has a slightly di↵ erent goal and di↵ erent inner workings. Often, the entity schemas that these systems use internally are di↵ erent, requiring prior alignment of the schemas in order to compare these systems. In previous work, we have manually mapped the taxonomies of 12 of these systems to a single ontology, namely the NERD ontology [ 12 ]. However, as these taxonomies evolve over time, mappings may need to be updated, which is an iterative and time consuming task. Furthermore, a single, static mapping to another taxonomy may result in loss of subtleties between di↵ erent class extensions and domain specific uses of the taxonomy.

In this paper we show that it is possible to inductively learn mappings of entity types between various extractors available in the NERD framework and gold standard benchmark classes for well-defined entity classes such as person, 4 http://www.opencalais.com organization and location. Bin-classes such as ‘miscellaneous’ are more di cult to learn, but inspection of our mappings shows that the extractors uncover inconsistencies in the gold standard datasets that are being used. To assess the feasibility of the inductive approach, we use the learned mappings as input of the NER experiments reported in [ 11 ], and we observe improvements with respect to the baseline (computed using the manual mappings). The increase in performance is dependent on the used dataset, showing that this approach is better performing with the MSM2013 one.

The proposed approach enables us to create general conclusions based on the observation of individual cases. This is what is observed in the domain of the Natural Language Processing (NLP), in particular for the entity recognition, where the taxonomy is generally encoded implicitly in the data. The learning algorithms, after observing the distributions of tokens and types, train the classifier. Quite recently, with the introduction of the entity extractors, that together with the entity recognition also perform entity linking, the problem of using a rich upper level schema (the majority as advances proposed in the Linked Data movement) of the data has been exploited. Nowadays, the DBpedia Ontology, Freebase, and Schema.org (to name few) are schemas largely used by a plethora of commercial and research entity extractors. Most of these extractors can be used as o↵ -the-shelf extractors, hence there is no chance to feed in a data schema that is di↵ erent from the one internally modeled.

The remainder of this paper is organized as follows. In Section 2, we describe background and related work. In Section 3, we describe the datasets, the set of extractors together with their settings, and the data processing stage. In Section 4, we statistically motivate our approach and we provide two complementary approaches for learning inductively the alignments. In Section 5, we present the experiments and results, followed by a discussion in Section 6. We finish with conclusions and pointers for future work in Section 7. 2

Background and Related work

Matching di↵ erent schemas for generating correspondences between elements is an extensively explored task. Schema matching is a critical step in many domains such as e-business, data warehouses and databases [ 3 ]. With the advent of the Semantic Web, schema matching has taken a central role in managing highly structured knowledge bases, such as DBpedia and YAGO. Several matching tools have been evaluated but typically under di↵ erent conditions and for smaller match problems [ 2 ]. The OAEI yearly organizes shared tasks which include large ontologies, such as medical and library schemas. All these schemas come with a host of additional metadata, that is generally exploited by the matching tools. For instance, Cupid [ 7 ] combines a number of techniques such as linguistic matching, structure-based matching, constraint-based matching, and context-based matching at the schema element level and related metadata. A peculiarity of our work is its aim to be resilient to the schemas’ heterogeneity, in terms of number of classes, number of hierarchical layers, and absence of metadata, conditions with which the discussed ontology matching approaches have di culties.

Recently, the OAEI has introduced the Instance Matching challenge, which aims to evaluate tools able to identify similar instances, belonging to even di↵ erent schemas among di↵ erent RDF and OWL datasets. This notion grounds on the data interlinking movement, that has largely investigated the problem of detecting instances co-referring to the same real-world object is positively important in data integration. [ 15 ] and [ 10 ] propose a multi-layer approach for deciding whether or not two individuals are similar, based on contextual and semantic metadata. In particular, [ 15 ] proposes a tailored instance pipeline for RDF datasets composed of four stages ranging from data cleansing, unique subject matching, one-left object matching, and score matching. The scores, computed on the instances filtered by the previous stages working on the exact match, are weighted on the similarity of the metadata that surround them. [ 10 ] uses a twostage approach composed of candidate generation and instance matching. The first phase clusters similar instances, to reduce the number of pairs. The second determines the equivalence of the individuals, measuring the TF-IDF cosine similarity at triple level for strings, inverted disparity for digits, and exact match for dates. The matching is independent from the initial schemas. Our work narrows down the instance matching task as a mere exact match of the same tokens (that occur in the same document, and at the same o↵ set) potentially labeled using di↵ erent schemas. We investigate the type distributions of the dataset labeled with the gold standard types and the one labeled with extractor types. 3

Experimental Setup

In our experiments, we use two entity classification benchmark datasets, namely CoNLL2003 and MSM2013. The corpora are annotated using o↵ -the-self extractors that use di↵ erent ontologies for classifying the entities, with some of the extractors using more than one ontology. Basic stats of the two datasets are shown in Table 1. 3.1

Datasets

One of the most prominent datasets in NER is the corpus that was created for the CoNLL2003 Language-Independent Named Entity Recognition shared task [ 14 ]. There is fairly little overlap of named entities between the training and test datasets: only 2.9% of the named entities that occur in the training data also occur in the test data.

The MSM2013 corpus was created for the Making Sense of Microposts Challenge 2013 [ 1 ] and consists of microposts collected from the end of 2010 to the beginning of 2011. Similarly as for CoNLL2003, the MSM2013 has 8.1% overlap of named entities between the training and test data. 3.2

Extractors

The commercial and research tools that we evaluate via their Web APIs are AlchemyAPI,5 dataTXT,6 DBpedia Spotlight, Lupedia,7 OpenCalais, TextRazor,8 and Zemanta,9. For brevity, we refer to these using the uncapitalized spelling, and we shorten DBpedia Spotlight to dbspotlight. These extractors are selected for our experiments because they either utilize the DBpedia Ontology v3.8,10 or the Freebase ontology11 enabling us to more easily compare these extractors than the extractors that use a custom ontology. Furthermore, the DBpedia Ontology can be freely downloaded and browsed which enables us to perform experiments learning mappings at di↵ erent levels in the taxonomic hierarchy (see Section 4).

The annotation results vary in terms of the schema used for classifying the phrases. For instance, the entity Barack Obama may be classified (depending on the context) as “Person” from alchemyapi, or as “O ceHolder” by dbspotlight. This example shows at a first glance the subtle di↵ erences that exist while harmonizing di↵ erent classification schemes. Zemanta o cially claims it uses a sample of the Freebase types,12 but in our experiments we observe that it uses a larger set of Freebase and DBpedia types.

We query these extractors by using the NERD framework [ 12 ] that acts as proxy as it harmonizes the retrieval of the annotations. 3.3

Data Preprocessing

We split each set into documents (CoNLL2003) and microposts (MSM2013). We then query the extractor e using the NERD framework, with the settings 5 http://www.alchemyapi.com 6 https://dandelion.eu/products/datatxt 7 http://lupedia.ontotext.com 8 http://www.textrazor.com 9 http://www.zemanta.com 10 http://wiki.dbpedia.org/Ontology 11 http://www.freebase.com 12 http://developer.zemanta.com/docs/entity_type/ last access on April 29th, 2014. described above. The retrieved output is parsed and converted in the CoNLL format, where the last column is dedicated to list the types T returned by e. Per each extractor, we generate one CoNLL file to list the TNERD (NERD types), and one to list the native (source) types TS returned by the extractor. 4

Inductive Typing Alignment

Let E denote the entity list, T the entity type list, S the source extractor types, and GS the types observed in the gold standard. (E, T )S indicates the ordered list of entities and types given by the source extractor, while OS is the schema used by the source extractor to type the entities. We then define A : TS ! TGS as the set of alignments given to which we apply a transformation from the TS to the TGS. Inspired by [ 13 ], we model the proposed inductive typing alignment as shown in Figure 1. Inputs are the ontology depth, the text token, and settings for the machine learning stage.

The initial requirement for an inductive typing alignment is to rely on reasonable answers of a set of systems when performing on specific constraints and defined use cases. By the law of large numbers it is possible to infer the value range of a statistical parameter with a bounded high probability (usually from 95% to 99%) from independent random samples. Therefore, relying on a large number of observations, we can draw upon relations from di↵ erent entity types. We split the inductive typing alignment into two separate tasks, the first a purely statistical approach, in which we extrapolate the evidence by observing the highest number of matches, and, the second, a machine learning approach, where a classification algorithm is trained using a set of mappings in order to infer the correct mapping for the test case. Generally, by looking at the entity type distributions of a gold standard we can narrow down coarse-grained considerations of the dataset. Let us consider the gold standard schema as the central schema, and the extractor schemas as the

OS. The entity surface forms work as matchers, so that we can cross the entity type distributions from the gold standard and the ones observed in the datasets described by OS. Therefore, applying a frequency induction we imply alignments based on the peak of the distributions. 4.2

Machine Learning Induction

In our machine learning induction approach, we aim to learn which entity types as assigned by the extractor outputs correspond to which entity classes in the gold standard. We use Weka [ 6 ] v3.6.11 in our experiments. In all experiments we use separate training and test sets. We have experimented with various algorithms, but k -Nearest Neighbour (k -NN) [ 4 ] and Naive Bayes (NB) [ 9 ] are the best performing for our approach, and thus only results using these algorithms are reported.

For each extractor, we performed the following series of experiments for both k -NN with k set to 1 (called IB1 in Weka) and Naive Bayes.

NERDType we try to learn the mapping between the types assigned by the NERD ontology and the types in the gold standard dataset. This serves as a baseline to check whether the manually created mappings distribution in NERD for each extractor follows the same implicit patterns as the class distribution in the gold standard datasets.

URIType in these experiments, we try to learn the mapping between the entity type as given by the extractor and the gold standard type.

URIType First in these experiments, we try to learn the mapping between the superclass of the entity type as given by the extractor and the gold standard type.

URIType Second in these experiments, we go up one level in the extractor type ontology and try to learn the mapping between the super-super-class of the entity type as given by the extractor and the gold standard type URIType Third in these experiments, we try to learn the mapping between the super-super-super class of the entity type as given by the extractor and the gold standard type.

It must be noted that the schemas for alchemyapi and opencalais are released in a textual format, hence we extrapolated them and created the OWLs.13 Given the reduced depth (flat schema for opencalais, and 2 level hierarchy for alchemyapi) we could not perform experiments in which we traverse the hierarchy. Similarly, the unavailability of a machine readable Freebase schema obliged to consider the Freebase types as sequences of subtypes, separated by the terminator slash. This introduces a bias when the domain type corresponds to the identifier (for instance /person/person).

Figures 2 and 3 show the results of the mappings learnt for each extractor for the CoNLL2003 and MSM2013 datasets respectively.14 For both datasets, 13 https://github.com/NERD-project/nerd-ontology 14 For reasons of space we only present the F-measures here, for an overview of the precision and recall see https://github.com/giusepperizzo/nerd-inductive.

Fig. 2: F-scores of mapping experiments on the CoNLL2003 dataset on the person (PER), location (LOC), organisation (ORG), miscellaneous (MISC) and overall (Overall).

Fig. 3: Results of mapping experiments on the MSM2013 dataset on the person (PER), location (LOC), organisation (ORG), miscellaneous (MISC) and overall (Overall). we see that the person class can be mapped to the di↵ erent extractor schemas most easily. This is not surprising as this class is the least ambiguous. For the organization and location classes, the results drop, but this is mostly due to the recall of the extractors being quite low (see the recall statistics in Figures 3 and 4 of [ 11 ]). The miscellaneous class su↵ ers from being a broad and underspecified class in both datasets, which a↵ ects both the recognition results as well as the typing and thus also the mapping. In the CoNLL specification for example, the miscellaneous class includes named sports events, whereas many of the extractors also annotate more generic event types such as basketball championship.

For both datasets, we find that for the extractors that use the DBpedia Ontology (datatxt, dbspotlight, lupedia and textrazor), the automatically learned mappings most often outperform the manual mappings of the NERD ontology, with the exception of the results for dbspotlight. This e↵ ect is more pronounced in the CoNLL2003 dataset than in the MSM2013 dataset. Another interesting thing to note is that the lupedia mappings can best be learnt using the IB1 algorithms, whereas the dbspotlight and datatxt mappings perform best when using the NaiveBayes classifier. 5

Evaluation and Results

Table 2a shows the results we achieve on applying the inductive approach on [ 11 ] for the extraction and classification of the CoNLL2003 corpus entities. As baseline, we report the results achieved by the same chain, but only using manual mappings. Results are computed using the conlleval script.15 We observe that the C4.5 classifier is the best performing classifier for combining the linguistic features, the output of the Conditional Random Fields (CRF) [ 5 ], and the induced mappings from the investigated seven extractors (for both statically induction and machine learning induction), and hence for predicting the correct type. In this paper, the model used results less rich (with a reduced number of extractors) than our baseline approach.

The most striking finding from these experiments is that for the CoNLL2003 dataset, based on the recall the best mappings are obtained by using a simple frequency based statistical induction, where we choose the most frequently occurring type. This provides us with an increase of 0.45% in recall from the baseline. For the MSM2013 dataset however, the machine learning induction leads to the best results, with an increase in F1 of 0.68%, and an increase in recall of 8.59%. For both datasets, the figures report that the induction is generally promising for the bin classes, such as MISC. This is explained by the fact that the induction fills the gap left by the low number of examples used by the entity recognizer algorithm to build a model on top of that. The top mappings for the MISC class obtained by the datatxt Naive Bayes experiments are shown in Table 3.16 Here we see the breadth of the MISC class and the di↵ erences in 15 http://www.cnts.ua.ac.be/conll2002/ner/bin/conlleval.txt 16 The complete mappings per extractor can be found at https://github.com/ giusepperizzo/nerd-inductive. the type of entities that fall within this class in the two datasets, supporting our case for customized mappings. It also shows the potential usefulness of having a more fine-grained class than MISC. The proposed approach inherits some limitations of the extractors used in this work. The annotations collected from the extractors are imperfect. The machine learning approach aims to compensate the system errors by remapping them to the correct types. Another source of bias is the entity position, that is given by the majority of the extractors, while alchemyapi and opencalais leave the client to compute it. NERD attempts to reduce this ambiguity, recomputing the position just applying a rule-based logic. Four of the extractors potentially use more than one schema for the classification. Although this gives more information to the client, it a↵ ects the interpretation of the entity and, hence, introducing ambiguity in performing the further operations by intelligent systems plugged on. It is also unclear how some of the extractors exploit the taxonomies they use internally, which may cause suboptimal alignments. However, as some of these extractors are black boxes we can only infer how they operate by looking at the results.

Furthermore, the evaluation datasets used may not be optimal for evaluating these extractors. As mentioned in Subsection 4.2, the gold standard dataset is more conservative in its annotations, resulting in a lower precision for the extractors as they assume broader categories of entities. However, as creating gold standard benchmark datasets is a time consuming and complex task, there are not many around. Modeling choices influence the fit of the dataset for di↵ erent tasks and it is inevitable that errors creep in, despite data often being annotated by multiple annotators. Minor errors may creep in, such as ‘Keirin’ being annotated as a location in the CoNLL dataset, whereas it should be a sport. In the same dataset, we also encounter rugby, tennis and soccer as usually not being annotated as an entity, but in some cases they are. Most of the extractors seem to tag these concepts. This presents us a with a mismatch between the dataset and the task the extractors were created for. 7

Conclusions and Future Work

We have shown an approach and experiments for learning customized taxonomy alignments between di↵ erent entity extractors for di↵ erent domains. We experimented with a statistical data-driven alignment, and a machine learning data-driven alignment on two NLP datasets, namely CoNLL2003 and MSM2013. We used the computed alignments as input of [ 11 ] and compared the overall results with the ones obtained just using a manual mapping. Results are encouraging and show the potentiality of the inductive approach, that remains strictly dependent on the used dataset. This validates the hypothesis that there is no one-size-fits-all approach to align di↵ erent taxonomies. Part of our ongoing work is to improve the NER results to get closer to the theoretical limit presented in our previous work. In the ensemble learning domain, we plan to study the feature selection process further, and to estimate the influence of the size of the training corpus for building the classification model. We also plan to experiment with diverse datasets, covering other domains such as TV. A selection of further plots, not reported in this paper, together with the source code of our experiments, are available at https://github.com/giusepperizzo/nerd-inductive. The research leading to this paper was partially supported by the European Union’s 7th Framework Programme via the projects LinkedTV (GA 287911) and NewsReader (ICT-316404).

References

1. Basave , A.E.C. , Varga , A. , Rowe , M. , Stankovic , M. , Dadzie , A.S. : Making Sense of Microposts (#MSM2013) Concept Extraction Challenge . In: Making Sense of Microposts (#MSM2013) Concept Extraction Challenge ( 2013 )

2. Bellahsene , Z. , Bonifati , A. , Duchateau , F. , Velegrakis , Y. : On Evaluating Schema Matching and Mapping . In: Schema Matching and Mapping. Data-Centric Systems and Applications ( 2011 )

3. Bernstein , P.A. , Madhavan , J. , Rahm , E.: Generic Schema Matching, Ten Years Later. PVLDB 4 ( 11 ), 695 - 701 ( 2011 )

4. Cover , T.M. , Hart , P.E. : Nearest neighbor pattern classification . Institute of Electrical and Electronics Engineers Transactions on Information Theory 13 ( 1 ), 21 - 27 ( 1967 )

5. Finkel , J.R. , Grenager , T. , Manning , C. : Incorporating Non-local Information into Information Extraction Systems by Gibbs Sampling . In: 43rd Annual Meeting on Association for Computational Linguistics (ACL '05) ( 2005 )

6. Hall , M. , Frank , E. , Holmes , G. , Pfahringer , B. , Reutemann , P. , Witten , I.H. : The WEKA Data Mining Software: An Update. SIGKDD Explorations 11 ( 1 ) ( 2009 )

7. Madhavan , J. , Bernstein , P.A. , Rahm , E.: Generic Schema Matching with Cupid . In: 7th International Conference on Very Large Data Bases (VLDB'01) ( 2001 )

8. Mendes , P.N. , Jakob , M. , Garcia-Silva , A. , Bizer , C. : Dbpedia spotlight: Shedding light on the web of documents . In: 7th International Conference on Semantic Systems (I-Semantics'11) ( 2011 )

9. Mitchell, T.M. : Generative and discriminative classifiers: Naive bayes and logistic regression ( October 2005 ), rough draft chapter intended for possible inclusion in a possible second edition of Machine Learning , T. M. Mitchell, McGraw Hill .

10. Nguyen , K. , Ichise , R.: SLINT+ results for OAEI 2013 instance matching . In: 8th International Workshop on Ontology Matching (OM-13) ( 2013 )

11. Rizzo , G., van Erp, M. , Troncy , R.: Benchmarking the Extraction and Disambiguation of Named Entities on the Semantic Web . In: 9th International Conference on Language Resources and Evaluation (LREC'14) ( 2014 )

12. Rizzo , G. , Troncy , R.: NERD: A Framework for Unifying Named Entity Recognition and Disambiguation Extraction Tools . In: 13th Conference of the European Chapter of the Association for computational Linguistics (EACL'12) ( 2012 )

13. Shvaiko , P. , Euzenat , J.: Ontology Matching: State of the Art and Future Challenges . IEEE Transactions on Knowledge and Data Engineering 25 ( 1 ) ( 2013 )

14. Tjong Kim Sang , E.F. , Meulder , F.D. : Introduction to the CoNLL-2003 Shared Task: Language-Independent Named Entity Recognition . In: 17th Conference on Computational Natural Language Learning (CoNLL'03) ( 2003 )

15. Zheng , Q. , Shao , C. , Li , J. , Wang , Z. , Hu , L. : RiMOM2013 results for OAEI 2013 . In: 8th International Workshop on Ontology Matching (OM-13) ( 2013 )