Most IE methods do not provide easy means for integrating complex prior knowledge that can be provided by human experts. Such knowledge is especially valuable when there are no or little training data. In the paper we elaborate on the extraction ontology paradigm; the distinctive features of our system called Ex are 1) probabilistic reasoning over extractable attribute and instance candidates and 2) combination of the extraction ontology approach with the inductive and (to some degree) wrapper approach. We also discuss the issues related to the deployment and evaluation of applications based on extraction ontologies.
In the last decade, web information extraction (WIE) was dominated by two styles.
One—wrapper-based—is quite reliable but strictly depends on the formatting
regularity of pages. The other—inductive—paradigm assumes the presence of annotated
training data, which is rarely fulfilled in real-world settings, and manual labelling of
training data is often unfeasible. In addition, both approaches usually deliver extracted
information as weakly semantically structured; if WIE is to be used to fuel semantic
web repositories, secondary mapping to ontologies is typically needed, which makes
the process complicated and may introduce additional errors [
There were recently proposals for pushing ontologies towards the actual extraction
process as immediate prior knowledge. Extraction ontologies [
Section 2 of the paper briefly reviews the features of our WIE tool named Ex (see [
Our approach to WIE was originally inspired by that developed by Embley and
colleagues at BYU [
Extraction ontologies in Ex are designed so as to extract occurrences of attributes (such as ‘speaker’ or ‘location’), i.e. standalone named entities or values, and occurrences of whole instances of classes (such as ‘seminar’), as groups of attributes that ‘belong together’, from HTML pages or texts in a domain of interest.
Attributes are identified by their name, equipped with a data type (string, long text, integer or float) and accompanied by various forms of extraction evidence relating to the attribute value or to the context it appears in. Attribute value evidence includes (1) textual value patterns; (2) for integer and float types: min/max values, a numeric value distribution and possibly units of measure; (3) value length in tokens: min/max length constraints or a length distribution; (4) axioms expressing more complex constraints on the value and (5) coreference resolution rules. Attribute context evidence includes (1) textual context patterns and (2) formatting constraints.
Patterns in Ex (for both the value and the context of an attribute or class) are nested regular patterns defined at the level of tokens (words), characters, formatting tags 1 http://www.cs.waikato.ac.nz/ml/weka 2 http://www.medieq.org (HTML) and labels provided by external tools. Patterns may be inlined in the extraction ontology or sourced from (possibly large) external files, and may include e.g. fixed lexical tokens, token wildcards, characterl-evel regexps, formatting tags, labels representing the output of external NLP tools or references to other patterns or attribute candidates. For numeric types, default value patterns for integer/float numbers are provided.
For both attribute and class definitions, axioms can be specified that impose constraints on attribute value(s). For a single attribute, the axiom checks the to-be-extracted value and is either satisfied or not (which may boost or suppress the attribute candidate’s score). For a class, each axiom may refer to all attribute values present in the partially or fully parsed instance. For example, a start time of a seminar must be before the end time. Arbitrarily complex axioms can be authored using JavaScript. Further attributelevel evidence includes formatting constraints (such as not allowing the attribute value to cross an HTML element) and coreference resolution scripts.
Each class definition enumerates the attributes which may belong to it, and for each attribute it defines a cardinality range. Extraction knowledge may address both the content and the context of a class. Class content patterns are analogous to the attribute value patterns, however, they may match parts of an instance and must contain at least one reference to a member attribute. Class content patterns may be used e.g. to describe common wordings used between attributes or just to specify attribute ordering. For each attribute, the engagedness parameter may be specified to estimate the apriori probability of the attribute joining a class instance (as opposed to standalone occurrence). Regarding class context, analogous class context patterns and similar formatting constraints as for attributes are in effect.
In addition, constraints can be specified that hold over the whole sequence of extracted objects. Currently supported are minimal and maximal instance counts to be extracted from a document for each class.
All types of extraction knowledge mentioned above are pieces of evidence indicating the presence (or absence) of a certain attribute or class instance. Every piece of evidence may be equipped with two probability estimates: precision and recall. The precision of evidence states how probable it is for the predicted attribute or class instance to occur given the evidence holds, disregarding the truth values of other evidence. The recall of evidence states how abundant the evidence is among the predicted objects, disregarding whether other evidence holds. 2.3
In order to illustrate most of the above features, we present and explain an example from the seminar announcement extraction task3, in which the speaker name, location and start and end times (stime, etime) are to be extracted. Fig. 1 shows the structure of an extraction ontology for this task. Fig. 2 displays a part of the corresponding code in the XML-based ontology definition language, dealing with the name of the speaker and start time. Note that the extraction ontology defines some extra attributes like date, host and submitter; these are ‘helper’ attributes extracted in order for the system not to confuse them with the remaining attributes. 3 Compiled by A. McCallum, http://www.cs.umass.edu/˜mccallum/code-data.html.
In the global scope of the model, extraction knowledge affecting more than one attribute is defined: an axiom states that in 80% of cases, the duration of a seminar is between 30 minutes and 4 hours. The axiom is conditioned so that it only applies when both stime and etime are specified.
The speaker attribute shows the usage of nested regular patterns defined at the level of both words and characters. The ‘value’ section contains a sample pattern that is assumed to be exhibited by 50% of valid speaker names and its expected precision is 80%: the pattern partially relies on frequent first-name and surname lists. This value-related evidence is combined with contextual evidence stating that at least 10% of speaker names are preceded by indicative word sequences that, when present, identify a subsequent speaker name with 60% precision. A user-defined person-name co-reference resolution script is used to uncover multiple mentions of the same speaker.
Next, a generic time attribute follows which extracts time references from the input text. It contains an axiom that checks the time validity and also a time co-reference rule that identifies when two time entries are the same (like “noon” and “12pm”). Then two specializations of time are defined: the start and end times (only the start time is shown). The system specializes an attribute value when it finds some evidence that indicates the specialization (a context pattern in this sample). All properties of the general attribute are inherited to the child. 2.4
The inputs to the extraction process are the extraction ontology and a set of documents.
The process consists of five phases with feed-back looping; further details are in [
AC lattice is created. – Generation of instance candidates (ICs) for target classes in a bottom-up fashion, via gluing the ACs together; high-level ontological constraints are employed in this phase. The ICs are eventually merged into the AC lattice. – Formatting pattern induction allowing to exploit local mark-up regularities. For example, having a table with the first column listing staff names, if e.g. 90 person names are identified in such column and the table has 100 rows, patterns are induced at runtime that make the remaining 10 entries more likely to get extracted as well. – Attribute and instance parsing, consisting in searching the merged lattice using dynamic programming. The most probable sequence of instances and standalone attributes through the analysed document is returned. 3 3.1
Clearly, the critical aspect of the WIE approach relying on extraction ontologies is the design of such ontologies. So far, in the projects mentioned in section 2, all ontologies were designed manually by experienced knowledge engineers; the time required for the initial design was in the order of several person-weeks. For some attributes it may prove difficult to enter all needed extraction knowledge manually and still achieve acceptable error rates. This can be due to large heterogeneity of the extracted values and due to the complexity or large amounts of the required extraction knowledge, or simply because of lack of the designer’s knowledge (e.g. extraction from different languages). We are working in different directions to alleviate this problem: – Inductive models can be trained to classify selected attributes for which training data are available. The classifier’s decisions are then used within the extraction ontology patterns and can be augmented with further expert knowledge. – When no training data are available, the designer can perform mining over the current extraction results in order to find frequent phrases that occur in different positions wrt. so-far extracted attribute values. The positions include left and right context, prefix, content and suffix, and different types of string overlap. The mined phrases can guide the designer in creating indicative context and content patterns. – An alternative to building complex extraction models is to utilize evidence related to the larger context of data. For example, in the MedIEQ project, the extraction ontologies initially extract generic ‘contact information’ which is then specialized (e.g. to ‘person responsible for medical content’ or to ‘administrative staff’) using post-processing rules relying on page category determined by other tools.
We also investigate possibilities for reducing the amount of work in building the
conceptual structure of the extraction ontology. Our hypothesis, partially confirmed
by experiments described in [
The high-level workflow can be initiated either by adopting (or building) a DO or by directly writing an EO. In the latter case, we however lack a target ontological structure to be populated by extracted data. We thus assume that a DO could be re-engineered from an EO by following the transformation rules backwards (though such ‘deserialisation’ would require more human investment). Even though populating the DO using transformation rules will be a non-trivial process, it is likely to be more transparent compared to IE approaches that do not exploit ontological structures.
Finally, we assume that the EO could also be purely syntactically transformed to a semantic web (i.e. OWL) ontology, let us call it Ex2OWL ontology, that would serve as a DO (at the cost of being skewed towards document-oriented view).
Figure 3 depicts the scheme of prospective high-level workflow around EO-based IE. Solid edges correspond to fully-supported processes (now only the actual Ex-based IE), dashed edges to processes currently subject to intense research (the flow from ontology repository through the target DO to the EO), and dotted5 edges to processes weakly elaborated to date (some of them amounting to mere syntactic transformations). 3.2
Common approaches to IE evaluation, have they been developed at the level of formal
models [
Let us sketch a very simple evaluation model that would allow to compare dissimilar IE methods including the model-building context. Instead of directly comparing the accuracy of different methods, we can declare the minimal accuracy value required for the target application (target accuracy – TA). Then we will calculate the overall cost (in terms of the human power consumed) required by those different methods in order for the TA to be reached. For a purely inductively-trained model, the cost amounts to CI = cannot.nI (1) where cannot is the cost of annotating one elementary unit (such as ontological instance) and nI is the number of annotations needed to learn a model reaching the TA. Similarly, for an extraction ontology that only uses manual extraction evidence, the cost is CO = cinspect.nO + CODesign (2) where cinspect is the cost of merely inspecting (viewing) one elementary unit and nO is the number of units that had to be viewed by the extraction ontology designer to build a model reaching the TA; CODesign then is the cost of designing the actual extraction ontology. It is important to realise that cinspect << cannot (among other, cinspect does not have to deal with exact determination of entity boundaries, which is a well-known problem in creating the ground truth for IE) and most likely also nO < nI ; what now matters is whether this lower cost in CO is/not outweighed by the relatively high cost of CODesign. The model can be arbitrarily extended: e.g. for hybrid approaches (such as that we use in Ex) we could also consider the cost of deciding which attributes are to be extracted using which method—inductive vs. manual.
Let us, eventually, briefly touch another problem, that of cross-validation , which is a standard approach in evaluating inductive IE methods. While in the inductive approach an annotated dataset can be repeatedly partitioned and presented to the learning tool, we cannot do the same with the human designer of the extraction ontology, as s/he is not as ‘oblivious’ as a machine. The only way of simulating cross-validation in this context thus seems to be the inclusion of multiple designers, which is in most cases prohibitive.
As partial illustration of the mentioned concepts, let us tentatively compute the cost
of IE over seminar announcements. The utilized dataset contained 485 annotated
documents, of which 240 were made available to the extraction ontology designer (who
finally only needed to see a subset of these) and the remaining 245 were used for
testing. After about 8 person days of development, the extraction ontology attained, on the
test set, precision/recall values roughly comparable to those reported in literature; with
F-measure reaching 94% for both stime end etime, and 69% and 77% for speaker and
location, respectively. The accuracy for the two latter fields did not reach the best
results7 achieved by inductive algorithms like LP2 [
Thanks to their short development cycle, extraction ontologies are an interesting alternative for WIE when there are no or little training data. State-of-the-art ontological engineering techniques can be employed to ease their development. Fair evaluation of their performance however needs to take into account a larger context of their creation. The research was supported by the EC, FP6-027026, Knowledge space of semantic inference for automatic annotation and retrieval of multimedia content—K-Space.