Schema induction from incomplete semantic data

Abstract

With the development of the Semantic Web, more and more semantic data including many useful knowledge bases has been published on the Web. Such knowledge bases always lack expressive schema information, especially disjointness axioms and subclass axioms. This makes it difficult to perform many critical Semantic Web tasks like ontology reasoning, inconsistency handling and ontology mapping. To deal with this problem, a few approaches have been proposed to generate terminology axioms. However, they often adopt the closed world assumption which is opposite to the assumption adopted by the semantic data. This may lead to a lot of noisy negative examples so that existing learning approaches fail to perform well on such incomplete data. In this paper, a novel framework is proposed to automatically obtain disjointness axioms and subclass axioms from incomplete semantic data. This framework first obtains probabilistic type assertions by exploiting a type inference algorithm. Then a mining approach based on association rule mining is proposed to learn high-quality schema information. To address the incompleteness problem of semantic data, the mining model introduces novel definitions to compute the support and confidence for pruning false axioms. Our experimental evaluation shows promising results over several real-life incomplete knowledge bases like DBpedia and LUBM by comparing with existing relevant approaches.

Keywords

Ontology learning knowledge bases open world assumption association rule mining semantic web

1. Introduction

With the development of the Semantic Web [1], especially the promotion of Linked Open Data project[2]1

¹
http://linkeddata.org/.

and the development of those never-ending knowledge base constructors like NELL [3] and DeepDive [4], more and more semantic data has been published on the Web. The semantic data contains many useful knowledge bases (KBs) like DBpedia [5], Yago [6] and Probase [7]. Such KBs often contain quite a lot of facts but lack expressive schema information, especially disjointness axioms (The disjointness axioms means two concepts cannot have any common instances) and subclass axioms (The subclass axioms means the instances of sub-concept must belong to its parent concept). In the semantic web, ontology reasoning is a critical task in the semantic web to infer implicit information from the explicit information. If an ontology contain logical contradictions, the standard reasoning may lose its meaningfulness. To facilitate ontology reasoning and logical contradiction detection, expressive schema information is urgently required [8, 9, 10, 11]. Furthermore, ontology mapping and object reconciliation, the tasks to deal with the heterogenous problem of the semantic data, also need expressive schema information to improve the quality of the mapping algorithms [12, 13, 14]. Therefore, producing expressive schema information to enrich existing knowledge bases becomes an important and meaningful task. In this paper, we focus on mining disjointness axioms and subclass axioms.

Existing approaches to generate disjointness axioms and subclass axioms can be divided into two categories. One category is to obtain such axioms by labeling relations between two concepts manually. For instance, the work in [15] manually generate disjointness axioms. Obviously, it would be very tedious and even impossible when dealing with large-scale KBs. The other category is to learn terminology axioms automatically. Lehmann and his colleagues have developed a tool called DL-Learner [16] to learn possible candidate concept expressions which are scored by positive examples and negative examples [17]. For the approaches proposed in [10, 11], the confidence is measured by the number of the positive examples and negative examples [18]. This may lead to incorrect terminology axioms learned with a high confidence. The work in [19, 9] consider missing information as negative examples and their work has implemented systems BelNet ${}^{+}$ and GoldMiner respectively. These learning approaches often adopt Closed World Assumption (CWA) which is opposite to the assumption adopted by the semantic data (i.e., Open World Assumption, OWA).2

CWA assumes the truth value of the specified and derivable statements is true, and false otherwise. The main difference between CWA and OWA is that the latter makes the assumption that the truth value of an underivable statement is unknown (i.e., neither true nor false).

Due to the incompleteness of the semantic data, a lot of noisy negative examples may be generated so that existing learning approaches usually fail to perform very well. Therefore, learning high-quality disjointness axioms and subclass axioms from the semantic data still remains challenging.

In this paper, we propose a novel framework which aims on Semantic Induction From Semantic data (SIFS) based on association rules to automatically generate disjointness axioms and subclass axioms for addressing the problem of incomplete semantic data under OWA. This framework consists of two phases. The first phase generates negative examples by a type inference algorithm [20]. The algorithm computes a set of type assertions by assigning a probability $p\in[0,1]$ to indicate how much degree the instance belongs to the concept in such an assertion $C(i)$ . In this way, the negative examples could be obtained by setting a threshold. In the second phase, novel definitions of support and confidence are given and specific association rule mining algorithms are proposed to generate disjointness axioms and subclass axioms. This is because that the value of a cell in a transaction table is no longer 0 or 1 with the probabilities of $C(i)$ and $\neg C(i)$ such that the traditional association rule mining algorithms cannot be applied directly.

The main contributions in this paper are listed as follows:

•

A novel schema induction approach based on association rule mining techniques is proposed to automatically generate high-quality disjointness axioms and subclass axioms from incomplete KBs. This approach exploits type inference to deal with the incompleteness of the semantic data under OWA.

•

To improve the quality of learning results, new definitions of support and confidence are given by using negative examples as constraints. Based on the definitions, specific algorithms to generate disjointness axioms and subclass axioms are described.

•

Our experiments are conducted on several real-life KBs. An exhaustive analysis of the experimental results is provided by comparing our approach with existing relevant ones.

The rest of this paper is organized as follows. Section 2 introduces the background knowledge. The overall process of SIFS is described in Section 3 and more details about the proposed mining approach are presented in Section 4 separately. Section 5 provides the details of our experimental settings like data sets and evaluation measures. In Section 6, the experimental results are analysed thoroughly by comparing our approach with existing ones. The related work is given in Section 7 and Section 8 concludes the paper.

2. Preliminaries

In this section, we first introduce the background knowledge about knowledge base, association rule mining and type inference.

2.1 Knowledge base

In this paper, we focus on those knowledge bases expressed with RDF statements. Each RDF statement is a triple in the the form $<s,p,o>$ , where $s$ , $p$ and $o$ indicate a subject, a property (or predicate) and an object respectively. For convenience, $o(s)$ is used if $p$ indicates “rdf:type” which describes that the individual $s$ belongs to concept $o$ , and $p(s,o)$ is used otherwise.

Usually, a KB consists of an ABox and a TBox. The ABox includes a set of facts describing instances and their relations. The TBox defines the schema information like the relations between classes, domains and ranges of properties. Our task of this paper is to mine TBox information from an ABox. It is noted that, we use the terms knowledge base and ontology interchangeable.

2.2 Association rule mining

Association rule mining[21] is a rule-based method for discovering relations between variables in large databases by constructing transaction tables. Let $\mathcal{I}=\{I_{1},I_{2},\ldots,I_{m}\}$ be a set of items. A set of items that contain $k$ items is called a $k$ -itemset. Each transaction $T$ is a nonempty set of items such that $T\subseteq\mathcal{I}$ . For a set $A$ satisfying $A\subseteq T$ , the transaction $T$ is said to contain $A$ . An association rule is an implication of the form $A\rightarrow B$ , where $A\subset\mathcal{I}$ , $B\subset\mathcal{I}$ , $A\cap B=\emptyset$ , $A$ and $B$ are nonempty.

To decide whether an association rule $A\rightarrow B$ holds or not, the measures of support and confidence are widely adopted.

$\displaystyle\textit{support}(A\rightarrow B)=P(A\cup B),$ $\displaystyle\textit{confidence}(A\rightarrow B)=P(B|A)=\frac{\textit{support}% (A\cup B)}{\textit{support(A)}}.$

Usually, the support of $A\rightarrow B$ is an absolute support which considers the occurrence frequency of the itemset $\{A,B\}$ as its value. Sometimes, it is also defined as a relative support which is the ratio of the absolute support and the number of all transactions in the transaction table. Confidence of $A\rightarrow B$ is the percentage of transactions containing $A$ that also contain $B$ according to the transaction table. This is taken to be the conditional probability.

From the equations we can see that, the problem of mining association rules can be reduced to that of mining frequent itemsets.

2.3 Type inference

A RDF KB contains million facts, but it is still an incomplete KB in most cases. [20] is an statistic method to learn missing type assertions from a noisy RDF KB. For each property in a RDF KB, there is a characteristic distribution of types for both the subject and the object. For example the property dbpedia-owl:location is used in 247,601 triples in DBpedia. Eighty-seven percent objects of these triples are belong to dbpedia-owl:Place. Furthermore, it uses statistic method to assign a certain weigh for each each property, which reflects its capability of predicting the type. Finally, the missing type can be inferred by the weight. because each inferred type assertion have a probability, in this paper, the inferred type assertions are named probabilistic type assertions (namely PTA).

Figure 1.

The overall process of schema induction from incomplete semantic data.

3. The overall process of SIFS

In this section, we show the overall process to mine disjointness axioms and subclass axioms from incomplete semantic data. Figure 1 illustrates the process consisting of four steps: terminology acquisition, type inference, transaction table construction and axiom generation. More details about each step are provided as follows.

3.1 Terminology acquisition

The process of SIFS starts with obtaining terminology information required by our type inference algorithm. The terminology information includes the type assertions which indicates a instance belongs to a concept and those relations between a pair of individuals. We store the downloaded KB in a KB persistence tool, the required terminology information could be obtained directly by a SPARQL endpoint. In such cases, two SPARQL queries are used to obtain the terminology.

3.2 PTA computation

Based on the obtained semantic data, the type inference algorithm given in [20] can be applied to enrich an existing knowledge base $K$ . The algorithm computes a set of probabilistic type assertions (PTA for short) in the form of $(C(i),p)$ . Here, $p\in[0,1]$ is the probability of type assertion $C(i)$ and indicates that the instance $i$ has the probability $p$ to belong to concept $C$ .

Because KB does not includes negative examples, in order to obtain them we use a threshold to measure a instance $i$ is belong to concept $C$ or not. Given a threshold $t$ that will guarantees the accuracy of the positive example is the highest, instance $i$ is taken as a positive example means $i$ belong to $C$ ( $C(i)$ ) if $p\geqslant t$ and a negative example of concept $C$ otherwise $\neg C(i)$ . That is, for concept $C$ ,

$\displaystyle i\ \textit{is}\left\{\begin{array}[]{ll}\textit{postive example}% &\ \ {p\geqslant t}\\ \textit{negative example}&\ \ \textit{otherwise}.\end{array}\right.$

If $i$ is a positive example of concept $C$ , the probability of $\neg C(i)$ is set to be $0$ . Otherwise, if $i$ is a negative example of concept $C$ , then the probability of $\neg C(i)$ is $1-p$ and the probability of $C(i)$ is 0. That is,

$\displaystyle P(C(i))=p$ $\displaystyle P(\neg C(i))=1-p$

Here, $P(s)$ indicates the probability of assertion $s$ .

.

Suppose we obtain the following triples by a SPARQL endpoint:

$\displaystyle\textsf{(La\_Fontaine, Born, Chateau-Thierry)},\ \textsf{(La\_% Fontaine, Died, Paris)},$ $\displaystyle\textsf{(La\_Fontaine, Occupation, poet)}.$

After applying the type inference algorithm, the following PTAs can be obtained:

$\displaystyle\textsf{(Person(La\_Fontaine)},0.8),\ (\textsf{Place(La\_Fontaine% )},0.1).$

Assume the threshold is set to be 0.5 (see Section 5 for more details about how to select a threshold). Then the instance La_Fontaine is taken as a negative example of concept Place and a positive example of concept Person. According to this, the following PTAs can be generated for constructing the transaction table:

$\displaystyle(\textsf{Person}(\textsf{La\_Fontaine}),0.8),\ (\textsf{Place}(% \textsf{La\_Fontaine}),0),$ $\displaystyle(\neg\textsf{Person(La\_Fontaine)},0),\ (\neg\textsf{Place(La\_% Fontaine)},0.9).$

Note that, Person(La_Fontaine) is considered as a new type assertion and will be added to the original knowledge base.

3.3 Transaction table construction

Table 1
Transaction table in SIFS

InstanceConcept	Person	Chef	$\neg\textit{Person}$	$\neg\textit{Chef}$
Robert_Kranenborg	0.87	1	0	0
Artyom_Yankovskiy	1	0	0	0.95
Harlene_Wood	0.80	0	0	0.95
Don_Penny	0.81	Unknown	0	Unknown
Adam_Feeney	0.82	0	0	0.95
Lake_Davos	0	0	0.95	0.67

With the generated PTAs, a transaction table can be constructed (take Table 1 as an example). In the table, each column (namely an item) presents a concept defined in the original KB or its negation and each row (namely a transaction) corresponds to one individual. Each cell in the table is a value between 0 and 1, which indicates the probability of a type assertion or a probabilistic type assertion. The association rules to be mined are of the form $C_{1}\rightarrow\neg C_{2}$ or $C_{1}\rightarrow C_{2}$ . The first rule, used for generating disjointness axioms, means that the instances of $C_{1}$ cannot belong to $C_{2}$ . The second rule, used for generating subclass axioms, indicates that the instances of $C_{1}$ must belong to $C_{2}$ . Note that, the value of a cell is marked as “unknown” if a type assertion is neither stated in the original knowledge base nor inferred by the type inference algorithm.

This is quite different from a traditional transaction table used in association rule mining techniques whose value of a cell is either 0 or 1. Also, in the approach given in the work to learn disjointness axioms [8], the value of a cell is 1 when the corresponding type assertion explicitly stated in the original knowledge base and 0 otherwise.

.

Assume the following type assertions are explicitly stated in an original knowledge base $K$ :

$\displaystyle\textsf{Person(Artyom\_Yankovskiy)},\ \textsf{Chef(Robert\_% Kranenborg)}.$

Besides, the following type assertions are inferred from $K$ by the type inference algorithm:

$\displaystyle(\textsf{Person(Robert\_Kranenborg)},0.87),\ (\textsf{Chef(Artyom% \_Yankovskiy)},0.05),$ $\displaystyle\quad(\textsf{Person(Don\_Penny)},0.81)$ $\displaystyle(\textsf{Person(Harlene\_Wood)},0.8),\ (\textsf{Chef(Harlene\_% Wood)},0.05),$ $\displaystyle\quad(\textsf{Person(Adam\_Feeney)},0.82),$ $\displaystyle(\textsf{Chef(Adam\_Feeney)},0.05),\ (\textsf{Person(Lake\_Davos)% },0.05),\ (\textsf{Chef(Lake\_Davos)},0.33).$

Based on these assertions, Table 1 can be constructed by setting the threshold be 0.5 to judge whether an instance is positive or not. For instance, Lake_Davos is a negative example of Person since $P(\textsf{Person}(\textsf{Lake\_Davos}))=$ 0.05. Thus, $P(\neg\textsf{Person(Lake\_Davos)})$ is 1–0.05 and $P(\textsf{Person(Lake\_Davos)})$ is then set to be 0.

Table 2 presents the transaction table constructed in a traditional way according to $K$ .

Table 2

Transaction table in CWA

InstanceConcept	Person	Chef	$\neg\textit{Chef}$
Robert_Kranenborg	0	1	0
Artyom_Yankovskiy	1	0	1
Harlene_Wood	0	0	1
Don_Penny	0	0	1
Adam_Feeney	0	0	1
Lake_Davos	0	0	1

3.4 Axiom generation

For mining rules from a transaction table in SIFS, the traditional association rule mining algorithms cannot be applied directly due to the difference between the tables in SIFS and those in CWA. To deal with this problem, novel association rule mining algorithms need to be proposed. It is well known that, the support and confidence are two commonly used measures of rule strength in the field of data mining. Therefore, novel definitions of support and confidence (see Section 4 for details) need to be given before proposing new association rule mining algorithms.

Inspired by the work given in [9], the rules in the form of $C_{i}\rightarrow C_{j}$ and $C_{i}\rightarrow\neg C_{j}$ are considered to mine subclass axioms and disjointness axioms respectively, where $C_{i}$ and $C_{j}$ are concepts. A rule like $C_{i}\rightarrow C_{j}$ can be translated to a subclass axiom $C_{i}\sqsubseteq C_{j}$ directly. A rule like $C_{i}\rightarrow\neg C_{j}$ corresponds to a disjointness axiom $C_{i}\sqsubseteq\neg C_{j}$ .

4. Association rule mining in SIFS

To generate axioms from a transaction table in SIFS, support and confidence have to be redefined. In the following, we present the novel definitions of support and confidence respectively. Then specific algorithms are proposed to mine those rules that are used for generating disjointness axioms and subclass axioms.

4.1 Definition of support

In SIFS, the support of 1-itemset needs to be calculated first, which indicates how many instances belong to a concept. The support of 1-itemset can be defined as below according to the absolute support of an itemset.

$\displaystyle\textit{support}(\{C_{i}\})=\sum_{k=1}^{n}(a_{ki})$ (1)

In the equation, $a_{ki}$ is the value in the $k$ th row and $i$ th column of a transaction table and $n$ is the number of rows. This equation shows that the support of a rule is the sum of all values in the column of $C_{i}$ in a transaction table. For example, according to the transaction table given in Table 1, the support of 1-itemset $\{\textsf{Person}\}$ is the sum of 0.87, 1, 0.80, 0.81, 0.82 and 0 (namely 4.3).

In order to keep downward closure property of association rule mining, the support must decrease monotonically if more concepts are added into a rule. Thus, the support of a rule like $C_{i}\rightarrow C_{j}$ or $C_{i}\rightarrow\neg C_{j}$ can be defined as below.

$\displaystyle\textit{support}(C_{i}\rightarrow C_{j})=P(\{C_{i},C_{j}\})=\sum_% {k=1}^{n}(\min(a_{ki},a_{kj}))$ (2)

In the equation, $n$ indicates the number of rows in a transaction table. Besides, $a_{ki}$ indicates the value in the $k$ th row and $i$ th column, and $a_{kj}$ is the value in the $k$ th row and $j$ th column. That is, for a rule like $C_{i}\rightarrow C_{j}$ or $C_{i}\rightarrow\neg C_{j}$ , its support sums the minimal values of $a_{ki}$ and $a_{kj}$ in each row $k$ . For example, according to the transaction table given in Table 1, the support of $\textsf{Person}\rightarrow\neg\textsf{Chef}$ is the sum of 0, 0.95, 0.80, 0.82 and 0. Note that, the row with respect to the instance Don_Penny is ignored since the probability of $\neg\textsf{Chef(Don\_Penny)}$ is unknown.

Right now, the support of a rule in SIFS is still an absolute value. This means that a user who assigns a threshold for support has to know the absolute size of the original knowledge base. To deal with this problem, we give a definition of the proportional support. In a naive way, the absolute value of the support of a 1-itemset could be used (see Definition 2) as a denominator.

$\displaystyle ps(C_{i}\rightarrow C_{j})=\frac{\textit{support}(C_{i}% \rightarrow C_{j})}{\textit{support}(C_{i})}$ (3)

It is noted that, a concept may not have many (probabilistic) type assertions due to the incompleteness of the original knowledge base. For such concepts, we prefer to ignore them which is a commonly used strategy in association rule mining. This will speed up the mining process in SIFS since the searching space could be largely reduced.

4.2 Definition of confidence

In the context of closed world assumption, the influence of missing data cannot be ignored when defining the confidence of a rule. It is because not considering mising data may make the confidence become larger than the actual one (see the definition of confidence given in Section 2). Thus, wrong rules could be obtained according to those confidences. Take the transaction table given in Table 2 as an example. The confidence of the rule $\textsf{Person}\rightarrow\neg\textsf{Chef}$ is 1 because Artyom_Yankovskiy is an instance of Person but not an instance of Chef. From this rule, we can obtain the disjointness axiom $\textsf{Person}\sqsubseteq\neg\textsf{Chef}$ which is obviously wrong.

To deal with this problem, we define the following negative rules which can be used to compute how many (probabilistic) type assertions violate those rules to be mined:

$\displaystyle\text{For the rule}\ C_{i}\rightarrow C_{j},\text{its negative % rule is}\ C_{i}\rightarrow\neg C_{j}.$ $\displaystyle\text{For the rule}\ C_{i}\rightarrow\neg C_{j},\text{its % negative rule is}\ C_{i}\rightarrow C_{j}.$

It is reasonable to use these negative rules since it is unknown whether a missing instance violates the rules to be mined or not. The proportional support can imply the possibility of the negative rules.

When defining confidence of a rule, it is required to combine the support of the rule and that of its negative rule. The support of a negative rule serves as the constraint to reduce the confidence. For the rule to generate subclass axioms, Eqs (4) and (5) are given. Since a disjointness axiom is symmetric, the support of the rule to generate disjointness axioms should be different with that of the rule to generate subclass axioms. We use the operator $\max$ to reflect symmetric. The support of the rule to be mined is given in Eq. (6) and the support of the corresponding negative rule can be seen in Eq. (7). For example, if the rule $C_{i}\rightarrow\neg C_{j}$ is true or false, the inverse rule has same semantic by the symmetric of the disjointness axioms. In order to get the same support of $C_{i}\rightarrow\neg C_{j}$ and its inverse rule we will calculate the maximum support between $C_{i}\rightarrow\neg C_{j}$ and its inverse rule.

$\displaystyle\textit{True}(C_{i}\!\rightarrow\!C_{j})=ps(C_{i}\!\rightarrow\!C% _{j})$ (4) $\displaystyle\textit{False}(C_{i}\!\rightarrow\!C_{j})=ps(C_{i}\!\rightarrow\!% \neg C_{j})$ (5) $\displaystyle\textit{True}(C_{i}\!\rightarrow\!\neg C_{j})=\max(ps(C_{i}\!% \rightarrow\!\neg C_{j}),ps(C_{j}\!\rightarrow\!\neg C_{i}))$ (6) $\displaystyle\textit{False}(C_{i}\!\rightarrow\!\neg C_{j})=\max(ps(C_{i}\!% \rightarrow\!C_{j}),ps(C_{j}\!\rightarrow\!C_{i}))$ (7)

It is noted that, $\textit{True}(C_{i}\!\rightarrow\!\neg C_{j})$ and $\textit{True}(C_{j}\!\rightarrow\!\neg C_{i})$ are same for the rule to generate disjointness axioms.

Based on the equations from Eqs (4) to (7), the confidence of a rule $r$ can be defined as below:

$\displaystyle\textit{Confidence(r)}=\frac{\textit{True(r)}}{\textit{True(r)}+% \textit{False(r)}}$ (8)

In the equation, $r$ indicates a rule in the form of $C_{i}\!\rightarrow\!C_{j}$ or $C_{i}\!\rightarrow\!\neg C_{j}$ . This equation normalizes the confidence not by the entire set of facts, but by the facts that support the rule $r$ together with those that violate $r$ according to what we have know.

InputInput OutputOutput A transaction table $T$ and the thresholds $t_{sup}$ , $t_{ps}$ and $t_{\textit{conf}}$ Axioms to be generated axioms = candidate_rules = $\{\}$

column $i$ in $T$ $\textit{support}(\{C_{i}\})=\Sigma^{n}_{k=1}{a_{ki}}$ row $k$ in T concept pair $(C_{i},C_{j})(i\neq j)$ in $T$ $\textit{support}(\{C_{i}\})>t_{sup}$ and $\textit{support}(\{C_{j}\})>t_{1}$ $\textit{support}(\{C_{i},C_{j}\})+=\min(a_{ki},a_{kj})$ concept pair $(C_{i},C_{j})(i\neq j)$ in $T$ $ps(C_{i}\rightarrow C_{j})={\textit{support}(\{C_{i},C_{j}\})}/{\textit{% support}(\{C_{i}\})}$ $ps(C_{i}\rightarrow C_{j})>t_{ps}$ candidate_rules.add( $C_{i}\rightarrow C_{j}$ , $ps(C_{i}\rightarrow C_{j})$ $r\in$ candidate_rules $r==C_{i}\rightarrow C_{j}$ & $C_{i}$ and $C_{j}$ are atomic concepts $\textit{True}={\textit{support}(C_{i},C_{j})}/{\textit{support}(C_{i})}$ $\textit{False}={\textit{support}(C_{i},\neg C_{j})}/{\textit{support}(C_{i})}$ $r==C_{i}\rightarrow\neg C_{j}$ & $C_{i}$ and $C_{j}$ are atomic concepts $\textit{True}=\max(ps(C_{i}\rightarrow\neg C_{j}),ps(C_{j}\rightarrow\neg C_{i% }))$ $\textit{False}=\max(ps(C_{i}\rightarrow C_{j}),ps(C_{j}\rightarrow C_{i}))$ $\textit{Confidence}={\textit{True}}/(\textit{True}+\textit{False})$ $\textit{Confidence}>t_{\textit{conf}}$ axioms.add(transRule2Axiom( $r$ )) axioms end Axioms Mining Algorithm

4.3 Rule mining algorithms

Our goal is to mine disjointness axioms and subclass axioms from an incomplete KB under OWA. The mining algorithm (see Algorithm 4.2) takes a transaction table $T$ and three thresholds, where $t_{\textit{sup}}$ and $t_{ps}$ are used to filter out those rules with low standard and proportional supports respectively and $t_{\textit{conf}}$ is to prune candidate rules. The function transRule2Axiom translates an association rule to the corresponding axiom. This algorithm can be easily extended to generate other type of axioms. In Algorithm 4.2 $N_{c}$ is a set of concept names which is acquired in terminology acquisition step, all the concept in $N_{c}$ are atomic concepts.

Algorithm 4.2 first computes the absolute support for all 1-itemsets in the input transaction table (see lines 3 and 4). From line 5 to line 8, the algorithm calculates the absolute support for those 2-itemsets whose 1-itemsets own the support greater than the threshold $t_{\textit{sup}}$ . For each obtained 2-itemset, the proportional support of the corresponding rule is computed (see line 10). If the proportional support is greater than $t_{ps}$ , the rule will be considered as a candidate one (see lines 11 and 12). The selection of candidate rules could reduce the search space and speed up the algorithm. After obtaining the candidate rules, the confidence of each rule needs to be calculated for further filtering (see lines 13–22). For each rule $r$ , it is required to check which kind of axiom the rule is suitable for generating. Lines 14 and 17 check if $r$ is in the form to generate subclass axioms or or disjointness axioms respectively. If true, the corresponding probabilities of $r$ to be true and false are computed (see lines 15 and 16 and lines 18 and 19). With the obtained probabilities, the confidence value can be obtained (see line 20). If the confidence value is greater than the threshold $t_{\textit{conf}}$ , rule $r$ needs to be translated to the corresponding axiom which is taken as a new generated axiom (see lines 21 and 22).

5. Experimental settings

The dbpedia is larger than 20 GB and to accelerate computing speed, we do all the calculating in memory. Our experiments are performed on a server with Intel Xeon E5-2670 CPU and 128 GB of RAM using 64 bit operating system Ubuntu 14.04. The maximal heap space is set to be 60 GB. In the following, we introduce the data sets, evaluation measures and the strategies to select thresholds in detail.

5.1 Data sets

Table 3
The statistics of the gold standards

Gold standards	Number of concepts		Number of axioms
	All	No instances	Subclass	Disjointness	Euqivalent
DBpedia	256	16	257	59,914	0
NTN	19	16	52	6	0
University	43	16	36	17	0
Family	49	4	6	17	14

The KBs used in the experiments include DBpedia,3

http://wiki.dbpedia.org/Downloads351.

NTN,4

⁴

http://www.semanticbible.com/.

LUBM5

⁵

http://swat.cse.lehigh.edu/projects/lubm/.

and Family.6

⁶

https://github.com/fresheye/belnet/blob/master/ontology/family_background.owl.

DBpedia is one of the central knowledge bases in linked open data cloud and constructed by extracting structured information from the well-known Wikipedia which is constantly updated and maintained by thousands of contributors. This dataset contains a huge number of facts and relatively small schema information. We use DBpedia 3.5.1 in English. NTN indicates New Testament Names and is a part of Semantic Bible knowledge base. NTN describes people, places and other classes, and their attributes and relationships. University is Lehigh University Benchmark which is developed to facilitate the evaluation of Semantic Web repositories in a standard and systematic way. A university domain ontology and customizable and repeatable synthetic data are included. Family is a KB to describe the concepts like Brother and Sister and relationships like hasSibling and married in a family domain.

For these KBs, we manually constructed gold standards based on their ontologies. To be specific, a set of disjointness axioms are added to each ontology by assuming the siblings are disjoint. The statistics of the gold standards can be seen in Table 3. This table presents he number of all concepts and those that have no type assertions explicitly declared in the corresponding ABox in the original KB. It also shows the number of subclass axioms, disjointness axioms and equivalent axioms. From the table we can observe that NTN is the most sparse KB since 84% concepts have no instances in the gold standard. The performance of SIFS could be better reflected over such a highly incomplete KB.

5.2 Evaluation measures

In order to measure the performance of the implemented systems to generate schema information, the traditional precision and recall are used. Precision is used to measure how many selected items are relevant and recall is to measure how many relevant items are retrieved. See below for the definitions of these measures in the context of generating schema information.

$\displaystyle p=\frac{\textit{Number of axioms that are correctly generated}}{% \textit{Number of all axioms generated by a system}}$ (9) $\displaystyle r=\frac{\textit{Number of axioms that are correctly generated}}{% \textit{Number of axioms in gold standard}}$ (10)

In the equations, precision is the fraction of generated axioms that are correct according to the corresponding gold standard and recall is the fraction of correct axioms that are generated.

5.3 Parameter setting

In this section, the parameter setting depends on the experiment and do not need any domain knowledge. A threshold is an important factor in finding negative examples (see Section 3.2) and may effect the performance of SIFS. In order to obtain the most suitable threshold, we randomly selected 500 instances whose types are unknown and manually checked the correctness of the results. Figure 2 demonstrates more information. From the figure we can observe that, 0.5 should be the best threshold to differentiate positive examples from negative ones.

Table 4
Precision and recall of SIFS-S and SIFS-P with different thresholds

$t_{\textit{conf}}$	Precision-subclass		Recall-subclass		Precision-disjoint		Recall-disjoint
	SIFS-S	SIFS-P	SIFS-S	SIFS-P	SIFS-S	SIFS-P	SIFS-S	SIFS-P
0.7	0.950	0.950	0.995	0.982	0.912	0.981	0.706	0.712
0.8	0.970	0.970	0.983	0.973	0.912	0.982	0.706	0.712
0.9	0.990	0.990	0.973	0.961	0.923	0.991	0.700	0.702

Figure 2.

Experimental results of threshold value.

For SIFS, the default threshold of support 0.7 is used to choose the candidate association rules. That is, if the proportional support of a rule generated by SIFS exceeds 0.7, it would be regarded as a candidate rule. This threshold corresponds to $t_{ps}$ in Algorithm 4.2. Note that, the threshold $t_{\textit{sup}}$ in Algorithm 4.2 is set to be 0 for our experiments to obtain association rules as many as possible. In this way, a relatively higher recall may be reached. Other thresholds could be used to obtain a relatively higher precision.

When deciding a suitable threshold for filtering rules according to their confidences, three possible values are used. The threshold corresponds to $t_{\textit{conf}}$ in Algorithm 4.2. For SIFS, the values of 0.7, 0.8 and 0.9 are tested. Conversely, in BelNet ${}^{+}$ , the lower the confidence of a rule is, the larger the probability to be a correct rule is. Thus, we choose 0.1, 0.2 and 0.3 to further filter out candidate rules according to the confidence. To obtain the stable results in BelNet ${}^{+}$ for a fair comparison, the maximum of the parent node is set to be 5 and the maximum number of iterations is set to be 100.

6. Experimental results

The evaluation of our algorithm to generate axioms can be divided into four experiments. The first experiment tests the influence of standard support and proportional one to SIFS. The second experiment compares SIFS with GoldMiner to see their performance when adopting different world assumptions. The third experiment compares SIFS with BelNet ${}^{+}$ which learns schema knowledge from incomplete KBs. The last experiment shows the usefulness of the generated axioms when detecting logical inconsistencies in DBpedia.

It is noted that, we use SIFS-S and SIFS-P to indicate our system using standard support and that using proportional support separately. SIFS-P can be seen as an implementation of Algorithm 4.2. SIFS-S is actually the implementation of Algorithm 4.2 by ignoring the computation of proportional support in line 10 and modifying the threshold and proportional support in lines 11–12 and 18–19 for adapting to the change.

6.1 SIFS-S vs. SIFS-P

In this section, we compare SIFS-S with SIFS-P by using different thresholds to filter candidate association rules. Table 4 presents precision and recall of both systems to generate subclass axioms and disjointness axioms respectively. This experiment is conducted over DBpedia which is the most challenging KB in our dataset due to its huge number of facts.

From the precision and recall to generate subclass axioms we can observe that, both systems perform similarly. When generating disjointness axioms, SIFS-P performs better than SIFS-S. For example, when $t_{\textit{conf}}$ is 0.8, the precisions of SIFS-S and SIFS-P are 0.912 and 0.982 respectively. At the same time, the recall of SIFS-P is slightly better than SIFS-S. According to this we know that, although SIFS-P produces less disjointness axioms, more correct axioms are contained.

The reason why SIFS-S could find more disjointness axioms but obtain lower precision and recall is that, SIFS-S always omits the big difference between the number of instances of the concepts in a candidate rule (or axiom). Take the disjointness axiom $\textsf{Person}\sqsubseteq\neg\textsf{Chef}$ as an example. When using absolute support, the confidence of the axiom is 0.92. In DBpedia, Person contains 649,644 instances and Chef just contains 470 instances. This huge difference causes the fact that 517,672 instances of Person are regarded as the negative examples of Chef. In this way, very high confidences could be reached for such false disjointness axioms. If proportional support is used, the confidence of the axiom is 0.5. Obviously, the propositional support could improve the quality of the learned disjointness axioms. In the following experiments, we only compare SIFS-P with other systems.

Figure 3.

Precision (left) and recall (right) of systems to generate subclass axioms.

Figure 4.

Precision (left) and recall (right) of systems to generate disjointness axioms.

6.2 SIFS-P vs. GoldMiner

In this section, we compare the systems SIFS-P and GoldMiner. Both systems adopt association rule mining to generate axioms while the difference is the fact that GoldMiner uses different world assumptions to generate negative examples. The precision and recall of the systems to generate subclass and disjointness axioms can be seen in Figs 3 and 4 respectively. In these figures, 0.7, 0.8 and 0.9 in the horizontal axis indicate the thresholds to filter those rules with lower confidences.

This reflects the advantage of using type inference. That is, more type assertions recommended by type inference can increase the support of a rule and thus more correct subclass axioms could be generated. Besides, comparing with the precision and recall of systems to generate disjointness axioms, those to generate subclass axioms are higher, especially with respect to recall (see the left figures in Figs 3 and 4). Because lacking negative examples generating disjointness axioms is much more challenging than generating subclass axioms.

When mining disjointness axioms, the advantage of using type inference becomes more obvious, especially for DBpedia. When the recalls of SIFS-P and GoldMiner are quite similar, the precisions of SIFS-P are much better. For example, from Fig. 4 about DBpedia we can observe that, the difference between the precisions of both systems at any threshold is about 0.1 when their recalls are quite similar. This means that SIFS-P has found less disjointness axioms while containing similar number of correct disjointness axioms. In the case of threshold 0.7 for DBpedia, SIFS-P found about 4000 axioms less than GoldMiner.

SIFS-P performs better than GoldMiner on recall for subclass, and precision on DBPedia for disjointness when generating disjointness axioms. The reason are in such two aspects: (1) One aspect is that more noisy negative examples may be introduced when adopting CWA due to the imbalance of the number of instances of different concepts. For example, the confidence of $\textsf{WebSite}\rightarrow\neg\textsf{Work}$ computed by GoldMiner is 1, which means no instances are shared by concepts WebSite and Work. In DBpedia, Website has 1,852 instances, but instances have not been explicitly stated to belong to Work. In such a case, each instance of Website is regarded as a negative example of Work under CWA. Therefore, the confidence 1 is obtained and WebSite and Work are considered as disjoint by GoldMiner. While for SIFS-P, it uses type inference to generate more type assertions for remedying the imbalance problem. After the type inference algorithm is used, some instances of Website have very high probability to belong to Work. Thus, SIFS-P could infer that WebSite and Work are not disjoint but have the subclass relation. (2) The other aspect is that proportional support could make up for the disadvantage of using absolute values. Like SIFS-S, GoldMiner uses standard support and association rule mining techniques. The main difference is that SIFS-S adopts type inference for generating negative examples. Thus, the comparison of SIFS-S with SIFS-P is similar to that of SIFS-P with GoldMiner with respect to the versions of support. Specific examples can be found in Section 6.1.

6.3 SIFS-P vs. BelNet ${}^{+}$

In this section, SIFS-P is compared with BelNet ${}^{+}$ [18] which transfers the TBox learning into the inference problem in the extension of Bayesian Description Logic Network. Both of them generate schema information under OWA. Since BelNet ${}^{+}$ fails to deal with large data like DBpedia, the comparison is conducted over other three KBs (see Figs 3 and 4).

Obviously, the precisions of BelNet ${}^{+}$ are more than 0.9, but 72% experiments of its recalls are no more than 0.6. For SIFS-P, the precisions are similar to those of BelNet ${}^{+}$ . This shows that BelNet ${}^{+}$ generates much less disjointness axioms than SIFS-P. BelNet ${}^{+}$ depends on the joint probability to learn disjointness axioms. In the training stage, the number of individuals belonging to the pair of concepts is not large enough, which causes that many disjointness axioms are discarded when constructing the network. The experimental results show again that SIFS-P could learn more disjointness axioms whose quality is also high due to the adoption of type inference.

6.4 Application to detect inconsistencies

In this section, the experiment is conducted to verify the usefulness of our algorithm for detecting logical inconsistencies in DBpedia. For each learned disjointness axiom of the form $C_{i}\sqsubseteq\neg C_{j}$ , we use a SPARQL query to retrieve all instances that belong to both $C_{i}$ and $C_{j}$ .

Table 5 presents the experimental result of detected inconsistencies. From the table we can see that, many logical inconsistencies have been found in DBpedia 3.5.1 by our algorithm. In particular, 99 pairs of disjoint concepts share only 1 to 9 common instances and 4 pairs of disjoint concepts share no less than 10 but less than 50 instances. For example, we can find two type assertions Person(Nuri) and Place(Nuri) from DBpedia. And we check the data from dbpedia, the description of Person(Nuri) is same as Place(Nuri). In dbpedia, Nuri is an same instance of both concept Person and Place which are obviously mutually disjoint. Thus, a logical inconsistency is caused. Before learning disjointness axioms, such inconsistencies cannot be detected due to the incompleteness of schema information.

Table 5
The statistics of the inconsistencies

Number of common instances	Pairs of disjoint concepts
[1–10)	99
[10–50)	4
[50–100)	0
[100–1000)	0
[1000– $\infty$ )	0

6.5 Summary of experimental results

Based on the analysis of the above experiments, we obtain the following main observations:

•
The adoption of type inference provides a promising solution to deal with the imbalance problem and also generates higher quality of negative examples than those generated under CWA.
•
The proportional support remedies the disadvantage of using absolute values and improves the quality of learning results.
•
SIFS-P perform better than the existing systems to learn schema information from incomplete data in most cases.
•
High-quality disjointness axioms could help a reasoner to automatically find more contradictions in KBs.

7. Related work

The most relevant work to ours is the approach given in [9] which uses association rule mining to mine schema information including disjointness and subclass axioms. Their algorithms have been implemented in the system GoldMiner. This approach is extended in [8] by considering naïve negative association rule mining to learn disjointness axioms. Our systems SIFS-S and SIFS-P can be seen as an extension of GoldMiner by considering type inference and proportional support. However, as our experiments have shown, GoldMiner has difficulties to deal with the incompleteness problem and the standard support used by GoldMiner may filter out those concepts with few instances.

Another relevant work is given in [18] which proposes an ontology learning approach by integrating the probabilistic inference capability of Bayesian Networks with the logical formalism of Description Logics. The approach considers the incompleteness of KBs and uses inference in a Bayesian network that leverages the structure in the data to solve the noisy issue brought by CWA. This work considers the schema learning as instance classification. To be consistent with OWA of the data in the semantic web, the traditional confusion matrix is extended for considering unknown results. The corresponding algorithms have been implemented in BelNet ${}^{+}$ , which depends on the joint probability to learn axioms. According to the comparison in Section 6, BelNet ${}^{+}$ fails to deal with those cases that the number of instances belonging to the pair of concepts is not large enough.

Our approach is inspired by the rule mining model given in [22], which conforms to the OWA. This work introduces novel definitions of support and confidence. In order to acquire the unknown facts, the notion of functionality is applied to acquire negative examples of a binary relation. Since the goal of this approach is to mine horn logical rules and a type assertion is not functional, it is not suitable to generate axioms from an incomplete KB.

Inductive logic programming (ILP), which marries machine learning and data mining, is often used to learn schema information. In order to induce concept definition axioms from existing instances, Lehmann and his colleagues propose an approach in [23] to generate candidate concept descriptions by a downward refinement operator. Later on, this approach is extended to deal with very large dataset in [24]. All the relevant algorithms have been implemented in the tool DL-Learner [16]. However, noisy negative examples will influence the performance of such approaches.

There are also other works to generate schema information. In [10], all concepts are mapped to vectors with the same dimension. If the similarity of two concepts is lower than a threshold, their work is regarded as disjoint. The authors of [12] proposes an appropriate heuristic rule for learning disjointness axioms. This heuristic rule assumes that all sibling concepts are disjoint. A light-weight approach to enrich knowledge is presented in [25], which uses SPARQL queries to learn axioms. However, it needs an artificial process to optimize the quality of disjointness axioms. The approach given in [26] is a supervised learning approach, whose training set needs to be constructed manually. It uses various kinds of external resources like ontology, texts, and other softwares (e.g., the label of Del.icio.us, WordNet [27] and OntoClean [28]).

8. Conclusion

In this paper, we proposed a novel approach to learning disjointness and subclass axioms from incomplete semantic data under OWA. We first applied the type inference algorithm to generate new probabilistic type assertions, which provides a promising solution to deal with the incompleteness or imbalance problem. We then introduced a mining model consisting of novel definitions of support and confidence using negative examples as constraints. We conducted extensive experiments to compare proportional support with standard support, and our system with existing systems. The experimental results showed that the proportional support performs better than the standard one and SIFS-P outperforms GoldMiner and BelNet ${}^{+}$ with respect to precision and recall in most cases. The experimental results also showed that the learned disjointness axioms are quite useful to detect logical inconsistencies.

In the future, we plan to extend the SIFS-P to learn more kinds of axioms such as the axioms with existential restriction, universal restriction and the limited extensional quantification. Besides, more datasets will be considered to test the performance of SIFS-P.

References

Berners-Lee

Hendler

Lassila

et al., The semantic web, Scientific American 284(5) (2001), 28–37.

Bizer

Heath

and Berners-Lee

, Linked data – the story so far, Int. J. Semantic Web Inf. Syst. 5(3) (2009), 1–22.

Mitchell

T.M.

Cohen

W.W.

Hruschka

E.R.

, Jr., et al., NMever-ending learning, in: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25–30, 2015, Austin, Texas, USA., 2015, pp. 2302–2310.

C.D.

Ratner

Ré

Shin

Wang

and Zhang

, Incremental knowledge base construction using deepdive, VLDB J. 26(1) (2017), 81–105.

Lehmann

Isele

Jakob

Jentzsch

Kontokostas

Mendes

P.N.

Hellmann

Morsey

van Kleef

Auer

and Bizer

, Dbpedia – A large-scale, multilingual knowledge base extracted from wikipedia, Semantic Web 6(2) (2015), 167–195.

Suchanek

F.M.

Kasneci

and Weikum

, Yago: A core of semantic knowledge, in: Proceedings of WWW 2007, 2007, pp. 697–706.

Wang

and Zhu

K.Q.

, Probase: a probabilistic taxonomy for text understanding, in: Proceedings of SIGMOD 2012, 2012, 481–492.

Fleischhacker

and Völker

, Inductive learning of disjointness axioms, in: Proceedings of OTM 2011, 2011, pp. 680–697.

Völker

and Niepert

, Statistical schema induction, in: Proceedings of ESWC 2011, 2011, pp. 124–138.

10.

Töpper

Knuth

and Sack

, Dbpedia ontology enrichment for inconsistency detection, in: Proceedings of I-SEMANTICS 2012, 2012, pp. 33–40.

11.

Völker

Fleischhacker

and Stuckenschmidt

, Automatic acquisition of class disjointness, J. Web Sem. 35 (2015), 124–139.

12.

Meilicke

Völker

and Stuckenschmidt

, Learning disjointness for debugging mappings between lightweight ontologies, in: Proceedings of EKAW 2008, 2008, pp. 93–108.

13.

Noessner

Niepert

Meilicke

and Stuckenschmidt

, Leveraging terminological structure for object reconciliation, in: The Semantic Web: Research and Applications, 7th Extended Semantic Web Conference, ESWC 2010, Heraklion, Crete, Greece, May 30–June 3, 2010, Proceedings, Part II, 2010, pp. 334–348.

14.

Nolle

Meilicke

Chekol

M.W.

Nemirovski

and Stuckenschmidt

, Schema-based debugging of federated data sources, in: ECAI2016 – 22nd European Conference on Artificial Intelligence, 29 August-2 September 2016, The Hague, The Netherlands – Including Prestigious Applications of Artificial Intelligence (PAIS 2016), 2016, pp. 381–389.

15.

Wang

and Zhuang

, Approximating model-based abox revision in dl-lite: Theory and practice, in: Proceedings of AAAI 2015, 2015, pp. 254–260.

16.

Bühmann

Lehmann

and Westphal

, Dl-learner – A framework for inductive learning on the semantic web, J. Web Sem. 39 (2016), 15–24.

17.

Fanizzi

d’Amato

and Esposito

, DL-FOIL concept learning in description logics, in: Proceedings of ILP 2008, 2008, pp. 107–121.

18.

Zhu

Gao

Pan

J.Z.

Zhao

and Quan

, Tbox learning from incomplete data by inference in belnet+, Knowledge-Based Systems 75(5) (2015), 30–40.

19.

Zhu

Gao

Pan

Zhao

and Quan

, Ontology learning from incomplete semantic web data by belnet, in: Proceedings of ICTAI 2013, 2013, pp. 761–768.

20.

Paulheim

and Bizer

, Type inference on noisy RDF data, in: Proceedings of ISWC 2013, 2013, pp. 510–525.

21.

Han

Kamber

and Pei

, Data Mining: Concepts and Techniques, Morgan Kaufmann, 2012.

22.

Galárraga

L.A.

Teflioudi

Hose

and Suchanek

, AMIE: Association rule mining under incomplete evidence in ontological knowledge bases, in: Proceedings of WWW 2013, 2013, pp. 413–422.

23.

Lehmann

Hitzler

, Concept learning in description logics using refinement operators, Machine Learning 1–2(78) (2010) 203–250.

24.

Hellmann

Lehmann

and Auer

, Learning of owl class expressions on very large knowledge bases and its applications, Interoperability Semantic Services and Web Applications (2011) 104–130.

25.

Bühmann

and Lehmann

, Universal OWL axiom enrichment for large knowledge bases, in: Proceedings of EKAW 2012, 2012, pp. 57–71.

26.

Völker

Vrandečić

Sure

and Hotho

, Learning disjointness, in: Proceedings of ESWC 2007, 2007, pp. 175–189.

27.

Miller

G.A.

, Wordnet: A lexical database for english, Commun, ACM 38(11) (1995), 39–41.

28.

Guarino

and Welty

C.A.

, A formal ontology of properties, in: Proceedings of EKAW 2000, 2000, pp. 97–112.

Schema induction from incomplete semantic data

Abstract

Keywords

1. Introduction

1 http://linkeddata.org/.

2.1 Knowledge base

2.2 Association rule mining

2.3 Type inference

3.1 Terminology acquisition

3.2 PTA computation

.

3.3 Transaction table construction

Table 1 Transaction table in SIFS

.

4. Association rule mining in SIFS

4.1 Definition of support

5. Experimental settings

5.1 Data sets

Table 3 The statistics of the gold standards

Table 4 Precision and recall of SIFS-S and SIFS-P with different thresholds

6.1 SIFS-S vs. SIFS-P

6.3 SIFS-P vs. BelNet +

6.4 Application to detect inconsistencies

Table 5 The statistics of the inconsistencies

8. Conclusion

References

¹
http://linkeddata.org/.

Table 1
Transaction table in SIFS

Table 3
The statistics of the gold standards

Table 4
Precision and recall of SIFS-S and SIFS-P with different thresholds

6.3 SIFS-P vs. BelNet ${}^{+}$

Table 5
The statistics of the inconsistencies