We suggest a logical-ontological approach to the coreference resolution in the process of text analysis and information extraction. Our approach solves the problem of comparing objects found in the text - instances of ontology classes - using the evaluation of the similarity of attributes and relations of objects. In object comparison, we take into account the discourse factors associated with the text and the extra-textual characteristics presented in the ontology of the subject domain. Particularly, we consider polyadic relations which may represent the situations found in the text (events, processes, actions). We propose the ontological interpretation of polyadic relations as classes with singlevalued object properties. For coreference resolution we use information about objects and their relations. We propose the corresponding measures for evaluating the semantic similarity of the participant objects in the relations.
Identification of referential relations in discourse is one of the most vital but difficult for modeling problems of automatic text analysis. Reference is a relation between some text unit (language expression) and non-linguistic object, which is called a referent. Correct interpretation of an utterance in the text under analysis involves identification of the object mention referent, i.e. reference resolution. There is a range of language means to mention certain referent in the text, and a speaker (text author) makes choice between two opposite types of language expressions: full noun phrases (proper names and descriptions) and reduced means of reference (pronouns and anaphoric zeroes). Processing expressions of the first type requires direct comparison of extracted objects. In the second case, an anaphoric relation of the reduced expression to antecedent expression is detected with respect to a number of text-structure, syntactic, semantic and pragmatic conditions.
The anaphora and coreference resolution is an important task within the framework of automatic discourse analysis: machine translation, text summarization and information extraction. The latter can be performed by natural language processing in which certain types of information must be recognized and extracted from the text (named entities recognition and fact extraction tasks, in particular). We consider the coreference resolution within the framework of information extraction for ontology population. In this framework, an ontology is used to represent the results of information extraction, and knowledge presented in the ontology helps to solve specific information extraction tasks.
Solving the task of automatic ontology population involves addition of information
to the ontology repository. In [
In Section 2 we give a brief review of modern trends in the coreference problem definition and the present research. In Section 3 we describe our basic approach to ontology-based information extraction with formal definitions of and ontology and polyadic relations. Section 4 presents ontological factors relevant for coreference resolution illustrated by text examples and revises the similarity measure of objects. In Section 5 we consider features of experiments in our approach. We conclude with the base characteristics and advantages of the proposed approach and outline the directions for future research. 2
We observe several classification aspects of problems related to the reference
identification.
─ First aspect is the way of presenting references in the text: full lexical expressions
(noun phrases – proper names, descriptions, descriptions combined with proper
names) or reduced expressions using anaphoric means (pronouns, determiners) or
anaphoric zero. In the first case, for noun phrases based on proper names, the
problem is detecting identical references to named entities. In the second case, the
problem is identification of the antecedent, i.e. anaphora resolution [
The traditional problem of anaphora and coreference resolution within a coherent
text remains to be relevant. Many early and modern researches solve the problem
using linguistic methods based on rules and methods of machine learning. R. Mitkov's
reviews [
Theories of discourse analysis distinguish several types of discourse connectivity:
referential (identity of participants), spatial, temporal and event-triggered ones [
We consider the problem of information extraction as a task of detecting all references to objects of a given domain: entities and situations (events, states, actions, processes). In the ontology population task, the found objects should be represented as instances of concepts and relations of the ontology. It is necessary to establish referential relations between all instances found in the process of text analysis and instances of the ontology information content (which does not exclude the possibility of adding new instances to the ontology). 3
Consider the environment in which our approach to coreference resolution is being developed. Fig. 1 shows the general scheme of the information extraction system (IEsystem) with the emphasized module of coreference resolution.
The input of our IE-system comprises: the ontology of a subject domain, the ontology population rules and the results of preliminary text processing including the terminological, thematic, and segment coverings of an input text.
A terminological covering is the result of lexical text analysis which extracts terms of a subject domain from a text and forms lexical objects using semantic vocabularies. A segment text covering is a division of the text into formal fragments (clauses, sentences, paragraphs, headlines, etc.) and genre fragments (document title, annotation, glossary, etc.). A thematic covering selects text fragments of a particular topic. A construction of a thematic covering is based on the thematic classification methods.
The module of information extraction constructs objects representing instances of
concepts and relations of the domain ontology from the lexical objects [
The coreference resolution module [
The result of the work of our IE-system is the population of ontology content by instances of concepts and relations of the subject domain found in the input text.
An ontology O of a subject domain includes the following elements: ─ a finite nonempty set CO of classes for representing the concepts of the subject domain, ─ a finite set DO of data domains, and ─ a finite set of attributes with names in AtrO = DatO∪RelO, each of which has values in some data domain from DO (data attributes or datatype properties in DatO) or has values as instances of some classes (object attributes or object properties in RelO, which model binary relations).
Each class c ∈ CO is defined by the set of its attributes: c = (Datc, Relc), where every data attribute α ∈ Datc ⊆ DatO has the domain dα ∈ DO with values in Vd and every object attribute ρ ∈ Relc ⊆ RelO has values from the subset Cρ ⊆ CO. The set of all class attributes is denoted by Atrc = Datc ∪ Relc. We consider an ontology without data and class synonyms, i.e. ∀ α1, α2 ∈ DatO: dα1 ≠ dα2 and ∀ c1, c2 ∈ CO : Atrc1 ≠ Atrc2.
We denote the class of an attribute γ by cγ and the set of its values by Dγ. A set of attributes of every class must include the nonempty set of key attributes Atr K . The c key attributes can either be data or object attributes. These attributes guarantee unambiguous definition and uniqueness of the class instances.
A tuple a = (ca, Data, Rela) is an instance of the class ca (Datca , Relca ) (a ∈ ca) with the values V iff every data attribute a Data has a name Datca and every object attribute a Rela has a name Relc a with the values V from Vd
as a a instances of the classes from Cρ.
We use the standard class inheritance relation: the class c2 is a subclass of the class c1 (c1 < c2) iff ∀ a ∈ c2: a ∈ c1.
The information content ICO of the ontology O is a set of instances of the classes from O. The ontology population problem is to compute information content for a given ontology from the given input data. 3.2
The notion of polyadic relation is not considered in the classical ontology theory. For example, the OWL – the standard ontology description language – has no language constructions for polyadic relations, only binary relations (Object Property) are available. On the other hand, polyadic relations frequently arise in the tasks of extracting information from texts, because they can describe the propositional content of a statement that represents an extra-linguistic situation, or state of affairs (event, action, process, etc.).
To overcome these shortcomings, we model polyadic relations (or just relations) by ontology classes with constraints on the set of attributes. First, relations classes have to include at least two object properties. Second, every object property of a relation has to be a key attribute. A polyadic relation may also contain datatype properties without special constraints.
Due to this definition, a polyadic relation is naturally represented by the set of binary relations. And vice versa, a binary relation can be represented by the polyadic relation with two object properties as a special case of polyadic relations.
In text processing, we consider polyadic relations correspond to descriptions of situations (actions, processes) and other objects with complex structure. The following Table 1 gives some examples of polyadic relations extracted from texts.
These examples relate to the automated control systems subject domain that includes such relation classes as Action, Process, Function, Control, Movement, Change_of_state, etc. Object properties of relation classes correspond to the hierarchy of semantic roles. The semantic role is a generalization of the functions of a participant in a range of situations denoted by a group of predicates, and hence the types of corresponding situations. The information content of a text consists of a set of instances of ontology classes and relations found in the text, which are provided with additional information.
We define a set A of information-text objects (i-objects) retrieved from input data and corresponding to ontology instances. Every i-object a∈A has the form (ca, Data, Rela, Ga, Pa), where ─ ca∈ CO is the ontology class; ─ Data is the set of data attributes a ( ,Va ) , where
Datca is the attribute name, and Va is the set of values v ∈ dα; ─ Rela is the set of object attributes a ( ,V ) , where a is the attribute name, and V Relca a is the set of i-objects of a class c a C a ; ─ Ga is the grammar information (morphological and syntactic features based on grammar features of lexical object); ─ Pa is the structural information (a set of positions in the input data and the formal segments). The attribute γ
of-obtjheect ai is filled if V a . We denote by Atra = Data ∪ Rela the set of all attributes. Each i-object corresponds to some ontology instance in a natural way as follows. Let a = (ca, Data, Rela, Ga, Pa) be an i-object, then its corresponding ontology instance is a′ = (ca, Data′, Rela′), and every α ∈ Data′ has value(s) in V and every ρ∈ Rela′ has values in V a .
We assume that i-objects a and b are possible coreferents a ≈ b (candidates for coreference) iff their classes are transitively related by the class inheritance relation and the set of values of all filled key attributes of one i-object is included in the set of values of the corresponding key attributes of the other i-object.
The coreference resolution problem is to detect if given candidates for coreference
correspond to the same ontology instance.
4
In previous papers [
In our approach, we distinguish logical-ontological factors for considering a set of associated relations between objects. For these factors we use the properties of relations specified in the ontology.
All these factors are used to evaluate similarity of objects mentioned in the text. For each factor, we define a similarity measure. This measure corresponds to the degree of strength of the coreferent relation between the i-objects a and b with respect to the factor, without taking into account other factors. 4.1
We define coreferential conflict as a case when two non-coreferent i-objects a and b are possible coreferents of the third i-object c: a ↭c b (a ≈ c) (b ≈ c) (a ≈ b).
To determine which of these i-objects are actually coreferent, we use the measure of coreference similarity of i-objects. This measure for i-objects a and b is denoted as cs(a,b). If the non-coreferential i-objects a and b are possible coreferents for the iobject c, we say that the coreferential conflict is resolved to a iff cs(a,c) > cs (b,c), i.e. the i-object a is more similar to i-object c, then i-object b.
The integral measure of similarity cs(a,b) is calculated as an Euclidean measure of similarity based on four measures – semantic S(a,b), context C(a,b), position P(a,b) and grammar G(a,b). (1 S (a, b))2 (1 C(a, b))2 (1 P(a, b))2 (1 G(a, b))2 The context similarity measure C(a,b) takes into account the information connectivity of i-objects in a given text. This measure depends on the number of i-objects which directly or indirectly use a) attribute values from both a and b, and b) attribute values borrowed by a from b, and by b from a, for the evaluation of their own attributes.
The position similarity measure P(a,b) takes into account variants of location of iobjects in an input text. This measure depends on the number of segments, number of possible candidates in the conflict, and number of lexemes placed between the positions of a and b.
The grammar similarity measure G(a,b) is based on the standard linguistic features such as gender, number, person, etc.
The semantic similarity measure S(a,b) determines the degree of proximity of the corresponding attribute sets Atra and Atrb. Comparing these two sets takes into account both the similarity of the values of their constituent elements and additional characteristics based on the ontological properties of attributes, including the inheritance of classes and data attributes, intersection, union, composition, refinement, inversion, inclusion, closure, transitivity and symmetry.
In [
S (a, b) 1
sim( a , b ) | Simba | ( a , b )Simba Here, under the sign of the sum, all kinds of similarities of the attributes of the objects a and b are collected. Practical considerations and experimental data revealed particular cases in which basic formula (2) is inexact and instable with respect to adding new attribute comparison characteristics: i-objects that have a large set of comparable but actually not similar attributes can turn out to be close with each other due to just taking into account that the similarity of attributes that is greater than zero. It is worth noting that such cases are very rare due to the definition of coreference and the formulation of the problem of extracting i-objects. The second disadvantage of formula (2) is expressed by the fact that adding new terms to the sum can decrease the total value. But one should expect that positive additional information about the proximity of attributes have to always increase the similarity of the corresponding i-objects. These additional characteristics are based on the ontological properties of attributes, including, in particular, composition, transitivity, refinement, etc., and specials properties of polyadic relations described below. In view of the above, it was proposed to convert formula (2) to a formula of the following form:
S (a, b) S EQ (1 S EQ ) S The value SEQ[0;1] corresponds to the similarity of the values of the corresponding attributes of the objects a and b without taking into account the additional characteristics, and S[0;1) — the additional information provided by these characteristics. (2) (3)
SEQ is calculated by formula (4), similar to formula (2), where the set of pairs of
similar attributes Simba is replaced by the set of pairs of comparable attributes
Compba {( a , b ) | a Atra , b Atrb , }.
(4)
(5)
(6)
Only measures of standard similarity of attributes by values stand under the sign of
the sum in the formula (4) [
Let the total amount of additional information about the attributes of objects a and b be Here the symbol denotes additional properties of attributes, such as transitivity, composition, etc. It is obvious that I can take any positive values. Hence, in order to get the value of S varying from 0 to 1, we need a monotonic transformation defined everywhere on the positive semi-axis. Using I, we evaluate the additional similarity of the i-objects a and b. Really, we determine the value of the probability of this similarity S:
1 S EQ
sim( a , b ) | Compba | ( a ,b )Compba I
sim ( a , b ) aAttra , bAttrb
S
I 1 I We can see from formulas (3), (5) and (6) that ─ S(a,b) = 1 SEQ = 1, ─ S [0;1), and ─ S(a,b) > SEQ SEQ < 1 S > 0.
In other words, when objects have incomplete similarity in the values of comparable attributes, and the additional information is available, the degree of similarity S is always greater than SEQ, but full match is achieved only under the condition that the values of all comparable attributes are the same taking coreference into account. 4.2
For evaluating similarity we consider polyadic relations in the following two aspects.
First, comparing polyadic relation instances for identification coreference between them.
Example 1. When the bottle reaches a certain position, (the sensorX communicates with the conveyor Y)S1 to inform it that it should stop. For this purpose (the sensorX sends a signal StopZ to the receiving device of the conveyorY)S2
In this example, we can distinguish two possible coreferent instances of polyadic relations S1 and S2: S1: Contact (Originator: X, Recipient: Y) S2: Information_transfer (Originator: X, Recipient: Y, Content: Z) These instances are similar because their Originator and Recipient attributes have coreferent values.
Second, using information about polyadic relations for identification coreference between i-objects participating in these relations. For this purpose, pairs of relations are considered that contain similar values (besides the objects themselves being compared). Change the example from the previous version.
Example 2. (The sensorX1 transmits a messageZ to the conveyorY)S1 to inform it that the bottle has reached a certain position. So, (itX2 controls the operation of the conveyorY)S2.
In this example polyadic relations are represented by the following instances: S1: Information_transfer (Originator: X1, Recipient: Y, Content: Z) S2: Control (Controller: X2, Patent: Y) We consider the instances X1 and X2 are similar because S1 and S2 have a similar value Y. Note that in the last example the relations of different classes with different sets of object attributes are compared because we allow the comparison of arbitrary relations.
We define the following formal ontological properties for object attributes. They are used for definition of object similarity measures that take into account polyadic relations. We borrow some concepts of relational algebra. We denote the set of all polyadic relations of the ontology O by SO.
Definition 1. Let ρ, ρ′, ρ′′ ∈ RelO. ─ The attributes ρ, ρ′ are in the projection ρr=elatρio′n iffCρ, Cρ’ ⊆ SO and ∃ γ1,…, mγ , ′ γ′1,…, mγ)′:∀ a∈ c∈ Cρ ∃ a′ ∈ Cρ’: π a ′ a′ π, iγ.iea.= VVγ′ia′ (i∈[1..m]), and vice versa, ∀ a′∈ c′∈ Cρ′ ∃ a ∈ Cρ: π′ a′ (a), i.eπ. the values of the attributes that are in the projection relation are instances of the polyadic relations that contain equal values. ─ The attributes ρ, ρ′ andρ′′ are in the natural joinρ= ρre′⋈laρti′o′ n ifCfρ, Cρ′, Cρ′′⊆ SO and ∀ a′∈ c′∈ Cρ′, ∃ a ∈ c ∈ Cρ, A ⊆ Atra: πtra′ a′ πA(a), ∀ a′′∈ c′′∈ Cρ′′ ∃ a ∈ c ∈ Cρ, A ⊆ Atra: πtra′′ a′′ A(a), anπd ∀ a∈ c∈ Cρ,b∈ Atra : (∃ a′∈ c′∈ Cρ′, b∈’ Atra′ : b= b′ ∨ (∃ a′′∈ c′′∈ Cρ′′, b∈′′ Atra′′ : b b′′ , i.e. the instances that are the of the object attributes ρ′ и ρ′′ are complementary different views projections the values of the attribute ρ.
Thus, the projection describes a subset of the common elements of the relation instances. In Example 1, the common projection of instances of the relations S1 and S2 is {X, Y}. In Example 2, the corresponding projection is the set {Y, X1, X2}. The natural join takes into account the presence of a third relation when comparing a pair of relation instances. This relation includes the join of the attributes of these relations. values on The presence of such a third relation is an evidence of the information included in the first two ones.
The example of the ontological natural join relation is ontological description of the modules of a technological complex that execute the similar tasks. Each module is represented by a relation, including instances of the tasks: SMi (w1, …, wn). The complex performs the whole set of tasks, which is the result of the natural join of the tasks executed by the modules: ∪ wij, wij SMi.
For those cases when properties of attributes in Definition 1 cannot be derived from the ontology description, there is a need to check the necessary conditions of the presence of the properties. The following proposition formulates these conditions in a constructive way. We denote the necessary condition of a property x by x.
─ ρ= ρ′ ⇒ = (Cρ∩iCρ’ ≠ ∅); ─ ρ=ρ′⋈ρ′′ ⇒ ⋈ = (Cρ′⋃ i Cρ′′⊆ i Cρ).
Here, the superscript i in the set operations means that we make the operation over the elements of the sets and over their parental classes and subclasses in the class hierarchy. The proof follows from Definition 1.
Taking into account Definition 1, we define the projection and natural join based similarities of the attributes. We also define the class similarity. In the following definition, the superscript r in comparison operations and calculation of the power of sets means that the operations consider the elements of the sets and their possible coreferents.
Definition 2. For i-objects a and b with a ≈ b and ca ≤ cb, we compute the power of the class similarity as simc(ca, cb) = |cb|/|ca|, where |cx| is the number of subclasses of the class x including x itself.
Definition 3. For i-objects a and b, we consider object relation ρ∈ Rela and ξ ∈ Relb with ρ, ξ∈ SO is ─ projectionally similar ρ∼ ξ, iff=ρξ∨ and Sπ=∪x∈Vρa {X⊆ Atrx | ∃ y∈Vξb, Y⊆ Atry : Xπ(x)= r πY y }∅. ≠The power of the projection similarity is simπ ρ, ξ ½|Sπ|( c(Vρa)-1 + c(Vξb)-1), where c(Vμ z∈ Vμ∑∑γ ∈ Atrz |Vγ |r. ─ joinly similar ρ∼⋈ ξ, if∃f μ: μ ⋈ξ ρ∨ ⋈ and S⋈ = {(x, y) | x∈Vρa, y∈Vξb, ∃ z∈ Cμ, Zx⊆ Atrz, Zy⊆ Atrz: Atrz ⊆ Zx∪ Zy, Aπtrx(x)= r πZx z aAntrdy(y)π= r πZx z }∅. ≠ The power of the join similarity is sim⋈ ρ, ξ ⋈|((|V½ρ|aS|r)-1+(|Vξb|r)-1). Thus, we can take into account the power of simc, simπ and sim⋈ of the projection and join similarity in the semantic similarity measure along with the other factors in formula (5). This allows us to take the context into account more accurately, improving the quality of information extraction. 5
The proposed approach to resolving coreference is based on the properties of the domain concepts presented formally. Testing its implementation requires for a formally presented ontology of a subject domain, as well as text corpus annotated in accordance with the ontology. Typed coreferential relations also have to be annotated.
There exist coreferentially annotated corpora for English (MUC) and a number of
other languages (Catalan, Dutch, English, German, Italian, Spanish, Czech, Chinese
and Arabic). The first open corpus for Russian is RuCor (available at
http://rucoref.maimbava.net/) that represents anaphorical and coreferential relations
and morphological annotation. RuCor contains about 200 texts of different genres
(primarily news, essays, and fiction) that do not correspond to any special subject
domain [
Hence, for evaluation of our approach we form a corpus of examples with a complex type of coreference, which can be resolved on the basis of ontology. Several examples are selected for each type of ontological relation. The total volume of the corpus is about 50 text fragments taken from texts of technical documentation and encyclopedias. These fragments represent specifications of requirements from the subject domain of automated control systems. Each example is annotated by coreference relations with types based on ontological properties.
We consider such annotation of coreference information necessary for further linguistic research. Extending the capabilities of automatic analyzers with computational similarity models based on ontological properties improves the quality of coreference resolution. Thus, for the examples found, the use of logical-ontological measures allows to increase the measure of similarity of the “correct”-0.1va(r5ia-nt 10%). 6
In the papers on the topic of coreference resolution, we proposed a formal statement of the problem and mathematically-strict definitions of the notions of coreference, coreferential conflict and ontological properties used to resolve the coreference. This is an important contribution to ensure the correct operation and improve the quality of the coreference resolution algorithms.
The main features of the proposed approach to coreference resolution are: 1. shift of the emphasis from discourse factors to the subject knowledge, primarily to the ontology of the subject domain to be populated through information extraction, disambiguation, and coreference resolution; 2. integration of computational and linguistic models and techniques of text analysis at the phase of semantic processing. Thus, weighted coreferential relations between objects are used for coreference resolution. In this process, the hypothetic coreferential relations are generated by the linguistic model, and the resolution (choice of the best hypothesis) is based on the statistical data; 3. scalability of the solution. Our approach can be enriched with new information extraction rules and referential factors. by The corpus with annotated coreference is necessary for studying different cases of repeated mentions of events that need ontological information about polyadic relations to correctly resolve coreferences. Our future research will focus on general classification of such cases. We plan to develop special case-oriented coreference resolution techniques, particularly, by considering the relevance of ontological properties for the evaluation of similarity of possible coreferents. Taking this into account, we are faced with the problem of defining ontology formal properties that provide a better solution to the tasks of extracting information from the text and, in particular, the resolution of the coreference.
Acknowledgement. The study was supported by the Russian Foundation for Basic Research, project 17-07-01600.
Resolution.
Vasilyeva,
M., 681