Information Extraction (IE) is a process of extracting structured data from unstructured sources. It roughly consists of subtasks named entity recognition, relation extraction and coreference resolution. Researchers have primarily focused just on one subtask or their combination in a pipeline. In this paper we introduce an intelligent collective IE system combining all three subtasks by employing conditional random elds. The usage of same learning model enables us to easily communicate between iterations on the y and to correct errors during iterative process execution. In addition to the architecture we introduce novel semantic and collective feature functions. The system's output is labelled according to an ontology and new instances are automatically created during runtime. The ontology as a schema encodes a set of constraints, de nes optional manual rules or patterns and with instances provides semantic gazetteer lists. The proposed framework is being developed during ongoing PhD research. It's main contributions are intelligent iterative interconnection of the selected subtasks, extensive use of context-speci c features and parameterless system that can be guided by an ontology. Some preliminary results combining just two subtasks already show promising results over traditional approaches.
Machine understanding of textual documents has been challenging since early computer-era. Information Extraction (IE) is a sub eld of Information Retrieval that attempts to analyze text and extract its structured semantic contents. Main IE tasks consist of named entity recognition (e.g. extraction of person names, locations, organizations), relation extraction (i.e. identi cation of relations among entities) and coreference resolution (i.e. clustering of mentions to an entity).
Early IE systems were naive and rule-based, then (semi-) automatic
approaches such as wrapper generation, seed expansion and rule induction were
introduced and recently machine learning techniques gained popularity. In
contrast to standard multi-label and regression classi ers, sequence taggers such
as Hidden Markov Models and Conditional Random Fields have become most
successful. Especially latter as they support rich feature function generation.
Ontology-based IE systems have also emerged to assist the development of
Semantic Web [
To further improve IE systems, we propose a Collective Ontology-based IE system that iteratively combines all three main IE subtasks. Those are named entity recognition (NE) - identi cation of entity types (e.g. person names), relation extraction (RE) - identi cation of relation types between entities (e.g. [PERSON] lives in [LOCATION]) and coreference resolution (COREF) - clustering of mentions to the same entity (e.g. to link John and He). We employ linearchain conditional random elds for NE and RE and skip-chain for COREF task. The use of same learning techniques enables us to reuse feature functions across tasks and by machine learning learn the incorporation of intermediate results during iterations. Next to labeling tasks we include entity resolution technique for matching and merging of coreferent mentions during IE process. Furthermore we identify additional semantic and iterative feature functions, taking into account multiple possible labelings in order to build error-robust system. The system is completely parameterless but results can be a ected by ontology manipulation or by runtime as ontology can be automatically populated. Therefore the proposed system is not just a mashup of some already existing techniques, but intelligently interconnects all of the components.
The rest of the paper is structured as follows. Section 2 overviews related work, next in Section 3 we point out motivation for the research and present a toy example showing lack of current methods. Section 4 brie y describes data representation, conditional random elds classi er and then gives an architecture overview of proposed system. Lastly, we discuss current achievements and introduce future work and then conclude the paper in Section 6. 2
There has been a lot of work done for speci c IE subtasks separately [
The term collective IE was to our knowledge rst used by Bunescu and
Mooney [
Conditional random elds (CRF), a sequence modeling framework, were rst
presented by La erty et. al. [
Nowadays applications try to combine data from various sources and apply logic
over it, but there are a number of useful unstructured sources that, due to
complex information extraction systems or low quality results remain unused
(e.g. experiments on automatic software testing using speci cation documents).
There are also many barriers in building IE systems like accuracy, e ciency,
multilinguality or reuse [
We believe best results in IE could be only achieved by using as much data context as possible and jointly work with subtasks of NE, RE and COREF. Apart from input data context and iteration generated context, system should have its own knowledge base and use third party (semi-) structured sources. Many research projects combine the subtasks in linear fashion or just focus on only one of the subtasks by taking others for granted.
The IE system should be easy to use and if possible completely parameterless. There should also be minimal e ort to change system's knowledge domain if needed. It must also be modular in order to inter-change speci c implementation or adapt it to another natural language. Results should be clearly understandable and also presented as a semantic graph according to the underlying ontology. The knowledge base should be automatically populated with labelled data on new documents. User should be able to add additional labelings or repair mislabelings through the system's graphical user interface. Such data would be used as training data at system's classi ers re-learning. These are next to problems of low accuracy performance on general data some ideas that we believe future IE systems should have.
Now we will show an example how to achieve better performance in IE. Let analyze the following toy example: \Dr. Missikof and Kurowski work as researchers. They will give keynote at CAISE in Gdansk." We show possible labeling in Fig. 1. The traditional pipeline approach of NER, RE and COREF employedAs
employedAs researcher JOB_TITLE dr. Kurowski
PER
CAiSE CONF: 0.3 ORG: 0.5
MACHINE: 0.2 hasKeynoteAt
CAiSE
CONF employedAs
hasKeynoteAt dr. Kurowski
PER locatedIn
Gdansk
LOC locatedIn
Gdansk LOC
After iteration 1: dr. Missikoff
PER After iteration 3: dr. Missikoff
PER employedAs researcher
JOB_TITLE would output a result similar to a labeling after rst iteration (see Fig. 1). As we see, the labeling of CAISE may be wrong due to missing additional information. Furthermore They was not yet co-referenced with person type and therefore relation hasKeynotAt was not identi ed. By enabling the system to iterate and take previous labelings into account, we would be able to use pronoun connection They and identify corresponding relation in second iteration. During third iteration CAISE would be successfully classi ed as a conference by using second labeling of corresponding relation and their argument types.
To e ciently solve identi ed problem, we designed a collective architecture which is in more detail de ned in Section 4.3. 4
In this section we present data representation, brie y introduce conditional random elds with feature functions and outline our architecture with training. Data representation presents data labeling that is needed to initially train CRFs and to mutually account intermediate labelings. CRF is a classi er that we have chosen to use for learning labeling models and is therefore crucial part in our architecture. 4.1
The proposed architecture takes a raw natural text as an input and returns semantically annotated text as an output. We treat the tasks of NER, RE and COREF as sequence labeling tasks.
Let xki = fx1ki ; x2ki ; :::; xki
n g denote the sequence of observable tokens. Index ki stands for input words wi or additional attributes such as part-of-speech (lexical category) tags, phrase boundaries, entity cluster identi er or pre-calculated values. Each observable sequence is associated with corresponding labeling sequence yli where li 2 fN E; REL; COREF g is de ned for named entity, relation and coreference label tags.
We use common IOB notation [
Coreference mentions can be represented as clusters, each referencing an entity. We therefore label each mention with corresponding cluster number.
Our problem is now nding the most probable labeling y^l for each of de ned subtasks. 4.2
Conditional random elds (CRF) [
Training CRF means looking for a weight vector w that assigns best possible labeling y^ given x for all training examples: (1) (2) y^ = arg max p(yjx; w);
y using conditional distribution p(yjx; w) = exp(PJ i=1 fj (y; x; i)) j=1 wj Pn
Z(x; w)
(Z(x; w) is a normalization constant over all possible labelings of y). When
distance between two addressing labels yi; yj inside feature functions fk is long,
exact inference is intractable due to exponential number of partial sequences and
thus approximate algorithms must be used. We therefore use feature functions
that depend on single label (yi) and two consecutive labels (yi 1; yi). This type
of CRF is also known as linear chain CRF (LCCRF) which underlying
graphical structure forms a chain and have been rather successfull in IE tasks. Using
LCCRF, training and inference can be easily solved using forward{backward
method and Viterbi algorithm. For COREF task better results are achieved if
a few more distant labels are observed and therefore we use skip-chain CRF
(SCCRF) [
The modeling of feature functions is a crucial part when training CRFs. We divide used feature functions into the following groups: Preprocessed: functions using bootstrap labelings (e.g. parse tree length, consecutive POS tags) String: word shape features (e.g. su x of length 2, upper case word, followed by a special symbol) Semantic: ontology-derived features (e.g. entity type is argument of a relation, word contained as instance in knowledge base, is the same gender constraint) Iteration: features taking into account intermediate labelings of NER, RE and COREF (e.g. relation argument possible types, entity has relation of type X) 4.3
In this section we show proposed system architecture and describe their components. Next, we introduce notion of iterative learning and labeling and de ne classes of used feature functions.
The proposed Collective Ontology-based IE system is presented in Fig. 2. The notion collective is used as all three subtasks iteratively re ne the results and use each other's intermediate outputs. Main components of the system are the following: Input consists of a set of textual documents.
Bootstrapping initially processes input data{i.e. splits it into tokens, sentences, lemmatizes it, performs Part-of-Speech tagging and full dependency parsing. This step initializes data with common labelings and enables the execution of iterative method.
Iterative method includes NER, RE, COREF and Entity merging and
matching algorithms. The iteration continues until results converge or maximum
number of iterations (will be statically de ned by running some
experiments) is reached. At each iteration, classi cations from previous iterations
are used by newly proposed feature functions. The convergence is achieved
when the classi cations over two consecutive iterations remain the same. All
four methods tag data with additional annotations and take previous
labelings into account. Entity matching and merging merges coreferent entities
using relational entity resolution using attribute, relationship and
semantic similarity measures [
Input text
Bootstrapping Data sources
Iterative method
Tokenization, Sentence splitting, Lemmatization, POS tagging, Dependency parsing Named entity recognition
Relation extraction 3rd party sources Ontology Co-reference resolution
Matching and
Merging ETH worksAt
John
Brussels
Output Tom hasSon
drives VW Golf marriedTo livesIn
Irina Output semantic network
Semantically annotated data network 3rd party sources provide access to public services{e.g. phonebook, social network APIs. When extracted data types matches speci c source parameters, extracted data is automatically enriched with response data (e.g. retrieval of twitter feeds if twitter username was extracted). Output consists of semantically annotated data and semantic network according to system's ontology.
We show a high level implementation of training in Algorithm (1). Training for each task's classi er is done separately and in iterative manner to learn weights for intermediate labelings. At beginning of each iteration, feature function values are re-initialized and classi ers are re-learned. As we employ matching and merging technique during training execution, distant labelings from merged clusters become visible locally and therefore there is no need to use arbitrary structured CRF for NE and RE tasks. Labeling is done analogous to training algorithm using already built classi ers.
Algorithm 1 Collective IE Training
Output: classi ers (cNE, cREL, cCOREF) 1: Initialize coreferent clusters as C = ; 2: i 0 3: while i < maxIter and prevScoreDi () < " do 4: Initialize feature functions 5: cNE LCCRF(xk; yNE) 6: cREL LCCRF(xk; yREL) 7: cCOREF SCCRF(xk; yCOREF ) 8: C matchingAndMerging(xk; yl) 9: xI NE cNE.tag(xk) 10: xI REL cREL.tag(xk) 11: xI COREF cCOREF.tag(xk) 12: i i + 1 13: end while 14: return (cNE, cREL, cCOREF)
The iterative algorithm is language independent. To support speci c language, we need to have prebuilt bootstrap algorithms and labeled text corpus, following the representation described in section Section 4.1. 5
At the moment of writing this paper we have already developed matching and
merging algorithm [
The main contribution of the work is intelligent architecture for information extraction. It accepts unstructured text as an input and returns semantically tagged network as a result. Ontology is the only element that the user can change in order to impact the results. Furthermore, the core of the contribution will be the iterative method by new ways to learn and classify with iterative classi ers along with newly introduced feature functions. For Slovene language, the contribution will be the new annotated dataset and evaluation of proposed method on that data. 6 https://bitbucket.org/szitnik/iobie/
Future work will focus on full framework implementation, evaluation on publicly available datasets and support at least one non-english language (e.g. Slovene). 6
In this paper we presented our in-progress PhD research. We proposed an intelligent collective ontology-based information extraction architecture, combining tasks of named entity recognition, relation extraction and coreference resolution.
A new parameterless IE architecture is based on an ontology which also updates at runtime. Main contributions are intelligent interconnection of main IE tasks, iterative training and labeling procedure, new possible feature functions and incorporation of matching and merging techniques into iterative method in order to use faster linear-chain instead of arbitrary CRFs. We also showed an example where proposed system could achieve signi cantly better results, mentioned little preliminary improvements over traditional approach and are continuously update publicly available sources.
Future work will include full implementation and evaluation of proposed iterative system on multi-language data. 7
The work has been supported by the Slovene Research Agency ARRS within the research program P2-0359 and part nanced by the European Union, European Social Fund.