Identi cation of ontological relations using Formal Concept Analysis ?

Abstract

In this paper we present an approach for the automatic identi cation of relations in ontologies of restricted domain. We use the evidence found in a corpus associated to the same domain of the ontology for determining the validity of the ontological relations. Our approach employs formal concept analysis, a method used for the analysis of data, but in this case used for relations discovery in a corpus of restricted domain. The approach uses two variants for lling the incidence matrix that this method employs. The formal concepts are used for evaluating the ontological relations of the target ontology. The performance obtained was about 96% for taxonomic relations and 100% for non-taxonomic relations.

Keywords

• Formal concept analysis
• ontology evaluation
• ontological relations

-

There is a huge amount of information that is uploaded every day to the World Wide Web, thus arising the need for automatic tools able to understand the meaning of such information. However, one of the central problems of constructing such tools is that this information remains unstructured nowadays, despite the e ort of di erent communities for giving a semantic sense to the World Wide Web. In fact, the Semantic Web research direction attempts to tackle this problem by incorporating semantic to the web data, so that it can be processed directly or indirectly by machines in order to transform it into a data network [ 10 ]. For this purpose, it has been proposed to use knowledge structures such as \ontologies" for giving semantic and structure to unstructured data. An ontology, from the computer science perspective, is \an explicit speci cation of a conceptualization"' [ 3 ]. ? This work has been partially supported by CONACYT and PROMEP grants:

CONACYT 54371, PROMEP/103.5/12/4962 BUAP-792.

Ontologies can be divided into four main categories, according to their generalization levels: generic ontologies, representation ontologies, domain ontologies, and application ontologies. Domain ontologies, or ontologies of restricted domain, specify the knowledge for a particular type of domain, for example: medical, tourism, nance, arti cial intelligence, etc. An ontology typically includes the following components: classes, instances, attributes, relations, constraints, rules, events and axioms.

In this paper we are interested in the process of discovering and evaluating ontological relations, thus, we focus our attention on the following two types: taxonomic relations and/or non-taxonomic relations. The rst type of relations are normally referred as relations of the type \is-a" (hypernym/hyponymy or subsumption).

There are plenty of research works in literature that addresses the problem of automatic construction of ontologies. The major of those works evaluate manually created ontologies by using a gold standard, which in fact, it is supposed to be manufactured by an expert. By using this approach, it is assumed that the expert has created the ontology in a correct way, however, there is not a guarantee of such thing. Thus, we consider very important to investigate a manner to automatically evaluate the quality of this kind of resources, which are continuously been used in the framework of the semantic web.

Our approach attempts to nd evidence of the relations to be evaluated in a reference corpus (associated to the same domain of the ontology) using formal concept analysis. To our knowledge, this topic has nearly been studied from the formal concept analysis point of view. In [ 2 ], for example, it is presented an approach for the automatic acquisition of taxonomies from text in two domains: tourism and nance. They use di erent measures for weighting the contribution of each attribute (such as conditional probability and pointwise mutual information (PMI)).

In [ 6 ] are presented two experiments for building taxonomies automatically. In the rst experiment, the attribute set includes a group of sememes obtained from the HowNet lexicon, whereas in the second the attributes are a basically set of context verbs obtained from a large-scale corpus; all this for building an ontology (taxonomy) of the Information Technology (IT) domain. They use ve experts of IT for evaluating the results of the system, reporting a 43.2% of correct answers for the rst experiment, and 56.2% of correct answers for the second one.

Hele-Mai Haav [ 4 ] presents an approach to semi-automatic ontology extraction and design by usign Formal Concept Analysis combined with a rule-based language, such as Horn clauses, for taxonomic relations. The attributes are nounphrases of a domain-speci c text describing a given entity. The non-taxonomic relations are de ned by means of predicates and rules using Horn clauses.

In [ 13 ] it is presented an approach to derive relevance of \events" from an ontology of the event domain. The ontology of events is constructed using Formal Concept Analysis. The event terms are mapped into objects, and the name entities into attributes. These terms and entities were recovered from an corpus in order to build the incidence matrix.

From the point of view of the evaluation of the ontology, some of the works mentioned above perform an evaluation by means of gold standard ([ 2 ]) in order to determine the level of overlapping between the ontology that has been built automatically and the manually constructed ontology (called gold standard).

Another approach for evaluating ontologies is by means of human experts as it is presented in [ 6 ].

In our approach we used a typed dependency parser for determining the verb of a given sentence, which is associated to the ontological concepts of a triple from which the relation component require to be validated. The ontological concepts together with their associated verbs are introduced, by means of an incidence matrix, to Formal Concept Analysis (FCA) system. The FCA method allow us to nd evidence of the ontological relation to be validated by searching the semantic implicit in the data. In order to validate our approach, we employ a manual evaluation process by means of human experts.

The remaining of this paper is structured as follows: Section 2 describes more into detail the theory of formal concept analysis. In section 3 we present the approach proposed in this paper. Section 4 shows and discusses the results obtained by the presented approach. Finally, in Section 5 the ndings and the future work are given. 2

Formal Concept Analysis

Formal Concept Analysis (FCA) is a method of data analysis that describes relations between a particular set of objects and a particular set of attributes [ 1 ]. It was introduced by Rudolf Wille in 1992 [ 11 ] as an area of research based on a model of set theory to concepts and concept hierarchies. It also allows data analysis methods for the formal representation of conceptual knowledge. FCA produces two kinds of output from the input data: a concept lattice and a collection of attribute implications. The concept lattice is a collection of formal concepts of the data, which are hierarchically ordered by a subconcept-superconcept relation. The attribute implication describes a valid dependency in the data. FCA can be seen as a conceptual clustering technique that provides intentional descriptions for abstract concepts. From a philosophical point of view, a concept is a unit of thoughts made up of two parts: the extension and the intension [ 12 ]. The extension covers all objects or entities beloging to this concept, whereas the intension comprises all the attributes or properties valid for all those objects.

FCA is based in the set theory, and it proposes a formal representation of conceptual knowledge [ 11 ]. FCA begins with the primitive idea of a context de ned as a triple (G; M; I), where G and M are sets, I is a binary relation between G and M (I is the incidence of the context); the elements of G and M are named objects and attributes, respectively.

For A G, A0 = fm 2 M j8g 2 A : (g; m) 2 Ig, and dually, for B M , B0 = fg 2 Gj8m 2 B : (g; m) 2 Ig

A0 is the set of all attributes common to the objects of A, B0 is the set of all objects that have all attributes in B.

A formal concept is de ned as [ 2 ]: A pair (A; B) is a formal concept of (G; M; I) i A G, B M , A0 = B and A = B0.

In other words, (A; B) is a formal concept if the attribute set shared by the objects of A are identical with those of B; and A is the set of all the objects that have all attributes in B. A is the extension, and B is the intension of the formal concept (A; B). The formal concepts of a given context are ordered by the relation of subconcept - superconcept de nided by: (A1; B1) (A2; B2) , A1

A2(, B2

B1)

FCA is a tool applied to various problems such as: hierarchical taxonomies, information retrieval, data mining, etc., [ 1 ]. In this case, we use this tool for identifying ontological relations of restricted domain. 3

Approach for evaluating semantic relations

We employ the theory of FCA to automatically identify ontological relations in a corpus of restricted domain. The approach considers two variants in the selection of properties or attributes for building the incidence matrix that is used by the FCA method for obtaining the formal concepts.

The di erence between the two variants is the type of syntactic dependencies parser used in the preprocessing phase for getting the properties.

The rst variant uses the minipar tagger [ 7 ], whereas the second variant employs the Stanford tagger [ 8 ]. For each variant, we selected manually a set of dependency relations in order to extract verbs from each sentence of the corpus that contains an ontology concept. These verbs are then used as properties or attributes in the incidence matrix.

The Stanford dependencies are triples containing the name of the relation, the governor and the dependent. Examples of these triples are shown in Table 1. For the purpose of our research, from each triple we have selected the governor (p=1), the dependent (p=2) or both (p=1,2) as attributes of the incidence matrix.

In the case of the minipar parser, we use the pattern C:i:V for recovering the verbs of the sentence. The grammatical categories that made up the pattern follows: C is a clause, I is an in ectional phrase, and V is a verb or verbal phrase. Some examples of triples recovered from the sentences are shown in Table 2.

The approach proposed in this paper involves the following three phases: 1. Pre-processing stage. The reference corpus is split into sentences, and all the information (ontology and the sentences) are normalized. In this case, we use the TreeTagger PoS tagger for obtaining the lemmas [ 9 ]. An information retrieval system is employed for ltering those sentences containing information referring to the concepts extracted from the ontology. The ontological relations are also extracted from the ontology1. Thereafter, we apply 1 We used Jena for extracting concepts and ontological relations (http://jena. apache.org/) Relation name p Meaning Example nsubj 1 Nominal subject nsubj(specialized, research) prep 1 Prepositional modi er prep into(divided, sub elds) root 2 Root of the sentence root(ROOT, give) acomp 1 Adjectival complement acomp(considered, feasible) advcl 1,2 Adverbial clause modi er advcl(need, provide) agent 1 Agent complement of a passive verb agent(simulated, machine) aux 1,2 Auxiliar verb aux(talked, can) auxpass 1,2 Passive auxiliar auxpass(used, is) cop 1,2 Copula cop(funded, is) csubj 2 Clausal subject csubj(said, having) csubjpass 1,2 Clausal passive subject csubjpass(activated, assuming) dobj 1 Direct object of a verbal phrase dobj(create, system) expl 1 Expletive expl(are, there) iobj 1 Indirect object iobj(allows, agent) nsubjpass 1 Passive nominal subject nsubjpass(embedded, agent) parataxis 2 Parataxis parataxis(Scientist, said) pcomp 2 Prepositional complement pcomp(allow, make) prepc 1 Prepositional clausal modi er prepc like(learning, clustering) prt 1,2 Phrasal verb particle prt( nd, out) tmod 1 Temporal modi er tmod(take, years) vmod 2 Reduced non- nite verbal modi er vmod(structure, containing) the syntactic dependency parser for each sentence associated to the ontology concepts. In order to extract the verbs from these sentences, we use the patterns shown in Table 3 for each syntactic dependency parser, and each type of ontological relation.

By using this information together with the ontology concepts, we construct the incidence matrix that feed the FCA system. 2. Identi cation of ontological relations. The concepts that made up the triple in which the ontological relation is present are searched in the formal concepts list obtained by the FCA system2 [ 5 ]. The approach assigns a value of 1 (one) if the pair of concepts of the ontological relation exists in the formal concept, otherwise it assigns a zero value. We consider the selection criteria shown in the third column of Table 3 for each type of ontological relation. As can be seen, in the Stanford approach we have tested three di erent selection criteria based on the type of verbs to be used. 3. Evaluation. Our approach provides a score for evaluating the ontology by using the accuracy formulae: Accuracy(ontology) = jS(R)j , where jS(R)j is jRj the total number of relations from which our approach considers that exist evidence in the reference corpus, and jRj is the number of semantic relations in the ontology to be evaluated. For measuring this approach, we compare the results obtained by our approach with respect to the results obtained by human experts. 2 We used the sequential version of FCALGS: http://fcalgs.sourceforge.net/

Experimental results

In this section we present the results obtained in the experiments carried out. Firstly, we present the datasets, the results obtained by the approach aforementioned follow; nally, the discussion of these results are given. 4.1

Dataset We have employed an ontology of the Arti cial Intelligence (AI) domain3 [ 14 ] for the experiments executed. In Table 4 we present the number of concepts (C), taxonomic relations (T R) and non-taxonomic relations (N T ) of the ontology evaluated. The characteristics of its reference corpus are also given in the same Table: number of documents (D), number of tokens (T ), vocabulary dimensionality (V ), and the number of sentences ltered (O) by the information retrieval system (S). As we mentioned above, we validated the ontology relations by means of human expert's judges. This manual evaluation was carried out in order to determine the performance of our approach, and consequently, the quality of the ontology.

Table 5 shows the results obtained by the approach presented in this paper when the AI ontology is evaluated. We used the accuracy criterion for determining the quality of the taxonomic relations. The rst column presents two variants for identifying the taxonomic relations. The last three columns indicate the quality of the system prediction according to three di erent human experts (E1, E2 and E3). The second column shows the quality obtained by the approach for each type of variant.

Table 6 shows the results obtained by the approach when the non-taxonomic relations are evaluated.

The results presented here were obtained with a subset of sentences associated to the ontological relations because of the great e ort needed for manually evaluate their validity. Therefore, in order to have a complete evaluation of the two type of ontological relations, we have calculated their accuracy, but in this case considering all the sentences associated to the relations to be evaluated. Table 7 shows the variantes used for evaluating the ontological relations and the accuracy assigned to each type of relation (Accuracy). 3 The ontology together with its reference corpus can be downloaded from http://azouaq.athabascau.ca/goldstandards.htm

As can be seen, the approach obtained a better accuracy for non-taxonomic relations than for taxonomic ones. This result is obtained because the approach is able to associate the verbs that exist in both, the relation and the domain corpus, by means of the FCA method. Therefore, when non-taxonomic relations are evaluated, the approach has more opportunity to nd evidence of their validity. 5

Conclusions

In this paper we have presented an approach based on FCA for the evaluation of ontological relations. Two types of variants for constructing the incidence matrix were employed. The Stanford variant was more accurate than the minipar one; actually, the minipar variant obtained a good accuracy for the two types of relations evaluated (taxonomic and non-taxonomic), whereas the Stanford variant obtained the best results for the non-taxonomic relations. The minipar variant, on the other hand, is quite fast in comparison with the Stanford one.

According to the results presented above, the approach obtains the global approach presented in this paper obtained an accuracy an accuracy of 96% for taxonomic relations, and 100% for non-taxonomic relations. This result shows, in some way, the quality of the ontology. These results should be seen in terms of the ability of our system for evaluating ontological relations. As future work, we will analyze the reasons for which the approach does not detect all the taxonomic relations.

References

1. Belohlavek , R.: Introduction to formal context analysis . Tech. rep. , Dept of Computer science. Palack y University, Olomouk, Czech Republic. ( 2008 )

2. Cimiano , P. , Hotho , A. , Staab , S. : Learning concept hierarchies from text corpora using formal concept analysis . J. Artif. Int. Res . 24 ( 1 ), 305 {339 (Aug 2005 )

3. Gruber , T.R.: Towards Principles for the Design of Ontologies Used for Knowledge Sharing . In: Guarino, N. , Poli , R . (eds.) Formal Ontology in Conceptual Analysis and Knowledge Representation . Kluwer Academic Publishers, Deventer, The Netherlands ( 1993 )

4. Haav , H.M.: A semi-automatic method to ontology design by using fca . In: Snsel, V. , Belohlvek , R . (eds.) CLA. CEUR Workshop Proceedings , vol. 110 . CEURWS.org ( 2004 )

5. Krajca , P. , Outrata , J. , Vychodil , V. : Parallel recursive algorithm for FCA . In: Proceedings of the Sixth International Conference on Concept Lattices and Their Applications . vol. 433 , pp. 71 { 82 . CEUR-WS.org, Olomouc ( 2008 )

6. Li , S. , Lu , Q. , Li , W. : Experiments of ontology construction with formal concept analysis . In: ren Huang , C. , Calzolari , N. , Gangemi , A. , Lenci , A. , Oltramari , A. , Prevot , L . (eds.) Ontology and the Lexicon , pp. 81 { 97 . Cambridge University Press ( 2010 ), cambridge Books Online

7. Lin , D. : Dependency-based evaluation of minipar . In: Proc. Workshop on the Evaluation of Parsing Systems. Granada ( 1998 )

8. de Marne e, M.C., MacCartney , B. , Manning , C.D.: Generating typed dependency parses from phrase structure trees . In: LREC ( 2006 )

9. Schmid , H.: Probabilistic part-of-speech tagging using decision trees . In: Proceedings of the International Conference on New Methods in Language Processing . Manchester, UK ( 1994 )

10. Sol s, S.: La Web Semantica. Lulu Enterprises Incorporated ( 2007 )

11. Wille , R.: Concept lattices and conceptual knowledge systems . Computers & Mathematics with Applications 23 ( 69 ), 493 { 515 ( 1992 )

12. Wolf , E.K. : A rst course in formal concept analysis . In: SoftStat'93 Advances in Statistical Software 4 . vol. 429 , pp. 429 { 438 . Faulbaumr

13. Xu , W. , Li , W. , Wu , M. , Li , W. , Yuan , C. : Deriving event relevance from the ontology constructed with formal concept analysis . In: Computational Linguistics and Intelligent Text Processing , 7th International Conference, CICLing 2006. Lecture Notes in Computer Science , Springer ( 2006 )

14. Zouaq , A. , Gasevic , D. , Hatala , M. : Linguistic patterns for information extraction in ontocmaps . In: Blomqvist, E. , Gangemi , A. , Hammar , K. , del Carmen SuarezFigueroa , M. (eds.) WOP. CEUR Workshop Proceedings , vol. 929 . CEUR-WS.org ( 2012 )