We propose a learning model for integrating OWL DL ontologies with statistical learning. In contrast to existing learning methods for the Semantic Web and approaches to the use of prior knowledge in machine learning, we allow for a semantically rich and fully formal representation of rules and constraints which enhance and control the learning task. In our implementation, we achieve this by combining a latent relational graphical model with description logic inference in a modular fashion. To demonstrate the feasibility of our approach we provide experiments with real world data accompanied by a set of SHOIN (D) axioms. The results illustrate two practical advancements: First, the probability of unknown roles of individuals can be inductively inferred without violating the constraints and second, known ABox axioms can be analyzed by means of clustering individuals per associated concept.
This paper focuses on the combination of statistical machine learning with OWL DL ontologies and proposes In nite Hidden Semantic Models (IHSM) for this task. The purpose of this is to allow (i) for the completion of the knowledge base with predictions about unknown roles of individuals while considering constraints as background knowledge for the machine learning process and (ii) for the analysis of the known concepts of individuals by means of clustering.
While there is some research on data mining for the Semantic Web (SW), like instance-based learning and classi cation of individuals, considering constraints speci ed in the ontology during this tasks has hardly been tried so far. The same applies to the use of "hard" constraints as opposed to the ubiquitous use of "soft" background knowledge in machine learning.
While we use a social network OWL DL ontology as running example, and settle on relational learning as an apparently natural counterpart for logical constraints, our general approach is in no way restricted to these and could be easily adapted to other formal and learning frameworks.
The remainder of this paper is structured as follows: In Section 2 we specify an ontology in OWL DL that de nes the taxonomy, relational structure and constraints. Next we show how to infer a relational model from the ontology and transfer the relational model into an IHSM (see Section 3). Then, we learn the parameters of this model in an in nite and unsupervised manner while taking the constraints into account (see Section 4). In Section 5 the IHSM is evaluated empirically using a complex dataset from the semantic web. Finally, we discuss related work and conclude in Section 6. 2
We settle on the SHOIN (D) [
C ! Aj:CjC1 u C2jC1 t C2j9R:Cj8R:C nSj nSjfa1; :::; angj nT j
j nT j 9T1; :::; Tn:Dj8T1; :::; Tn:DjD ! djfc1; :::; cng
Here, C denote concepts, A denote atomic concepts, R denote abstract roles or inverse roles of abstract roles (R ), S denote abstract simple roles, the Ti denote concrete roles, d denotes a concrete domain predicate, and the ai / ci denote abstract / concrete individuals.
A SHOIN (D) ontology or knowledge base is then a non-empty, nite set
of TBox axioms and ABox axioms (\facts") C1 v C2 (inclusion of concepts),
T rans(R) (transitivity), R1 v R2, T1 v T2 (role inclusion for abstract
respectively concrete roles), C(a) (concept assertion), R(a; b) (role assertion), a = b
(equality of individuals), and a 6= b (inequality of individuals). Concept equality
is denoted as C1 C2 which is just an abbreviation for mutual inclusion, i.e.,
C1 v C2; C2 v C1. De ning a semantics of SHOIN (D) is not required within
the scope of this work, the canonical semantics which we assume in this work
can be found, e.g., in [
Constraints are actually just knowledge bases (e.g., formal ontologies), and our approach is expected to work with all kinds of logical frameworks which allow for satis ability (or consistency) checks over some given set of formulas. Formally, we de ne a set of constraints C to be the deductive closure (KB ) of a given knowledge base KB , with (KB ) = fcjKB j= cg.
The application-speci c constraint set, that we use as an OWL DL ontology is similar to the well-known Friend-Of-A-Friend (FOAF) social network schema, together with additional constraints which will be introduced later. The following ontology SN comprises only a fragment of the full FOAF-like ontology we have used (with DOB meaning "date of birth" and hasBD meaning "has birthday".).
P erson v Agent knows v knows > v 8knows:P erson 9hasBD:> v P erson
> v 1 hasBD > v 1 hasBD > v 8yearV alue:gY ear > v 1 yearV alue > v 8residence:Location > v 1 residence > v 8attends:School 9hasImage:> v P erson 9knows:> v P erson > v 8hasBD:DOB 9yearV alue:> v DOB 9residence:> v P erson 9attends:> v P erson > v 8hasImage:Image
In addition to these axioms, we provide the machine learning algorithm with an ABox which models an incomplete social network. The later machine learning task consists essentially in a (uncertain) completion of this given network fragment. An example for such additional individuals-governing constraints A: tim : P erson; tina : P erson; tom : P erson (tina; tim) : knows; (tina; tom) : knows
Note that these relationships among persons cannot be weakened or overwritten by the learning process, even if they contradict observed data. They need to be provided manually by the knowledge base engineer. As further constraints, we assume some speci c properties G of the analyzed social network. The following set of axioms expresses that every two persons who know each other must share the same chat account provider in case they have a chat account. We present a fragment of the full set:
P rovA 9 HasP rov:P rovA P rovB 9 HasP rov:P rovB
P rovA v P erson P rovB v P erson F riendP rovA 9 knows:P rovA F riendP rovB 9 knows:P rovB F riendP rovA v P erson F riendP rovB v P erson
P rovF rP rovA 9 IsP rovOf:F riendP rovA
P rovF rP rovB 9 IsP rovOf:F riendP rovB P rovF rP rovA v P rovA P rovF rP rovB v P rovB 9 knows T hing v P erson > v 8 knows:P erson
HasP rov IsP rovOf 9 HasP rov T hing v P erson
> v 8 HasP rov:P rov HasP rov IsP rovOf 9 IsP rovOf T hing v P rov > v 8 IsP rovOf:P erson provA : P rovA provB : P rovB provC : P rovC provD : P rovD
The complete set of constraints in our running example is then C = (SN t A t G). (P rov stands for "chat account provider".) Example Data The set of data used as examples for the learning tasks takes the outer form of restricted SHOIN (D) ABox formulas. But in contrast to the constraints, an example (as a formula) might be wrong, in the sense that it contradicts C. We also do not require the examples to be mutually consistent. In order to maintain compatibility with the expected input format for relational learning, we restrict the syntax of example data to the following two forms: instance : category (instancea; instanceb) : role SHOIN (D) roles correspond to binary predicates in FOL, and - more or less naturally to the relations we would like to induce in the following from observed data. The set of all example data as logical formulas is denoted as D. 3
The proposed In nite Hidden Semantic Model (IHSM) is a machine learning
algorithm from the area of Statistical Relational Learning (SRL) [
In traditional ML prior knowledge is speci ed implicitly by probability distributions, parameters of the learning algorithm or selection of features. In more advanced models prior believes can be speci ed by hyperparameters and by the dependency structure in-between random variables. However, we de ne the relational structure by logical formulas which at the same time impose constraints on the learning.
In this section, we rst show how the ontology from Section 2 de nes a Relational Model (RM). Then we describe how to extend it to an In nite Hidden Relational Model (IHRM) and how to constrain it resulting in the IHSM. 3.1
tim : Person knows knows tom : Person tina : Person residence has
In order to predict unknown instances of roles, we need to create an abstract RM of concepts and roles de ned in our social network ontology, rst. This is done to inform the learning algorithm about which relations to consider. Based on the TBox axioms given by the ontology we can create a simple sociogram as depicted in Fig. 1. A sociogram consists of three di erent elements: Concept individuals (individuals that are instances of a concept (e.g. tim : P erson)), Attribute instances (relations between a concept and a literal (e.g. T im : hasImage)), Role instances (relations between concepts (e.g. (tina; tim) : knows))
Concepts, attributes and roles are those de ned in the TBox. They build the basis of the RM. Note that many TBox elements rst need to be deductively inferred from the ontology, so that all individuals can be assigned to its most speci c concepts. This process is known as Realization in description logic reasoning. Fig. 2 shows the full RM we use for experiments in Section 5. #BlogPosts
knows
posted holds residence attends
located
To obtain a probabilistically sound model based on the RM, random variables as
well as probability distributions and their parameters need to be introduced next.
Following [
Considering the HRM model shown in Fig. 3, information can now propagate via those interconnected hidden variables Z. E.g. if we want to predict whether tom Z31 might know tina Z21 we need to consider a new relationship R3;2. Intuitively, the probability is computed based on (i) the attributes A13 and A11 of the immediately related persons Z31 and Z1; (ii) the known relations associated with 2 the persons of interest, namely the role knows and residence R2;1, R3;1 and R3;2; (iii) higher-order information and constraints transferred via hidden variables Z1 3 and Z1. Given that the hidden variables have discrete probability distributions 2 tim : Person residence
usa : Location knows knows they can be intuitively interpreted as clusters where similar individuals (in our case similar persons, locations, schools,...) are grouped.
Considering the special importance of the hidden variables in the proposed
model their e ectiveness highly depends on the number of components that
can be represented. In nite Hidden Relational Models introduced by [
Finally, we need to de ne the variables, their probability distributions and parameters. The most important parameters of an IHRM are shown in Fig. 4. The state of Zi speci es the cluster assignment of the concept i. K denotes the number of clusters in Z. Z is sampled from a multinomial distribution with parameter vector = ( 1; : : : ; K ), which specify the probability of a concept belonging to a cluster, i.e. P (Zi = k) = k. is referred to as mixing weights, and is drawn according to a stick breaking construction with a hyperparameter 0. 0 is referred to as a concentration parameter in Dirichlet Process (DP) mixture modeling. It determines the tendency of number of states in Z.
Attributes Ac are generated from a Bernoulli distribution For each component, there is an in nite number of mixture components k. Each person inherits the mixture component, thus we have: P (Gi = sjZi = k; ) = k;s. These mixture components are independently drawn from a prior G0. The base distributions Gc0 and Gb0 are conjugated priors with hyperparameters c and b.
Roles Ri;j between two persons (i and j) are a samples drawn from a binomial distribution with parameter k;`, where k and ` denote cluster assignments of the person i and the person j, respectively. bk;` is the correlation mixture component indexed by potentially in nite hidden states k for ci and ` for cj , where ci and cj are indexes of the individuals involved in the relationship class b. Again, Gb0 is the Dirichlet Process base distribution of a role b. If an individual i is assigned to a cluster k, i.e. Zi = k, the person inherits not only k, but also k;`; ` = f1; : : : ; Kg. Attribute
Entity
Relation The (IHSM) is based on the simple idea that formal constraints can be imposed on the hidden variables. This way a user-designed formal ontology with logical rules can be considered during the learning process. As mentioned before, predictions about attributes and roles depend on the hidden variables Z. If probable predictions for an individual belonging to cluster Zi are checked against the ontology, it can be determined if individual i is consistent with this cluster according to the constraints. This way valid cluster assignments can be obtained and invalid cluster assignments are excluded. 4
The key inferential problem in the IHSM is to compute the joint posterior
distribution of unobservable variables given the data. In addition, we need to maintain
consistent cluster assignments during learning. As computation of the joint
posterior is analytically intractable we use Markov chain Monte Carlo (MCMC)
sampling to approximate the posterior distribution. In speci c, we apply the
blocked Gibbs sampling (GS) with truncated stick breaking representation [
Let D be the set of all available observations (observed example data, each represented as a logical formula as de ned in 2.1), and let Agents = AgentI be the set of all instances of category Agent under interpretation I - that is informally, all persons which contribute to the social network. At each iteration, we rst update the hidden variables conditioned on the parameters sampled in the last iteration, and then update the parameters conditioned on the hidden variables. So, for each entity class 1. Update hidden variable Zic for each ec i (a) Constrain to satis able cluster assignments:
For entity cluster k, let Fekxt = F k \ f(em; en) : rjem; en 2 Agents; r 2 R; m 6= ng be the set of those logical formulas in the example data set which represent some relation (\role") r between two di erent individuals (persons) em and en where person em is assigned to cluster k already and en is assigned to a cluster other than cluster k. To keep the notation compact, we spell out role instances (e1; e2) : r only asymmetrically (i.e., we omit (e2; e1) : r if we have covered the case (e1; e2) : r). Let Fk D be the set of all example formulas which have already been used to learn cluster k so far, that is, the subset of the data D which has been used for forming that cluster until now. Let furthermore (e; D) be the set of all sampled formulas in D where the person e appears, i.e., f 2 (e; D) i f 2 D ^ (f e : c _ f (e; ex) : r for some c 2 C, ex 2 Agents and r 2 R. We use (e; j) to express that a certain entity e has already been assigned to a certain cluster j. The following steps are now used in order to check whether cluster k is usable w.r.t. the given set of logical constraints C: i. Identify the largest subset Fcklean of formulas within Fekxt which is c consistent with C and the set of example data about person ei : Fcklean
2Fekxt ; 9 I; I j= Fcklean [ (eic; D) [ C; 8F 2Fekxt ; 9 I; I j= F [ (eic; D) [ C : F
Fcklean (I being an interpretation). ii. Verify whether Fcklean, the formulas which have been used to learn \related" other clusters, (eic; D) and the constraints are consistent in sum if we replace in Fcklean the names of all persons which are assigned to clusters other than k with the name of person eic. Let Fukpd = f(eic; em) : rj(en; em) : r 2 Fekxtg be the latter set of formulas. Furthermore, let Frkel = Sj6=k; (em;k);(em;en):r2F j F j be the set of all formulas in all other clusters than k which \relate" to cluster k using role formulas. The overall consistency check for cluster k yields a positive result i
9 I; I j= (eic; D) [ Fukpd [ Frkel [ C ^ Fcklean 6= ; (b) Assign to cluster where the consistency check described above yielded a positive result with probability proportional to:
Y Y and set vKc(tc+1) = 1. k(Zic(t+1)) equals to 1 if Zic(t+1) = k and 0 otherwise. Before the next iteration we update the parameters:
k 1 c(t+1) = vc(t+1) Y (1 k k k0=1
vkc(0t+1)); k > 1: c(t+1) k b(t+1) k;`
P ( jAc; Zc(t+1); Gc0);
P ( jRb; Z(t+1); Gb0):
After the GS procedure reaches stationarity the role of interest is approximated by looking at the sampled values. Here, we only mention the simplest case where the predictive distribution of the existence of a relation Ri;j between to known individuals i; j is approximated by ib0;j0 where i0 and j0 denote the cluster assignments of the objects i and j, respectively. 5
There is almost no work on statistical relational learning with formal ontologies in general and SW data in particular. The lack of experiments on large and complex real world ontologies is not only due to the absence of algorithms but also due to missing suitable datasets. In this section we will present both, a large and complex SW dataset and the methodology of how to apply IHSM in practice. Ultimately, we evaluate the feasibility of our approach by presenting rst experimental results with IHSM in this domain. 5.1
As mentioned before our core ontology is based on Friend of a Friend (FOAF) data. The FOAF ontology is de ned using OWL DL/RDF(S) and formally speci ed in the FOAF Vocabulary Speci cation 0.913. Besides that we make use of further concepts and roles that are given in the data. We gathered our FOAF dataset from user pro les of the community website LiveJournal.com4.
All extracted concepts and roles are shown in Fig. 2. Tab. 1 lists the number of individuals and instantiated roles. As expected for a social networks knows is the primary source of information. This real world data set o ers both a su ciently large set of individuals for inductive learning and a formal ontology speci ed in RDFS and OWL. To demonstrate the full potential of IHSM we additionally add constraints that are not given in the original ontology (see Section 2.1).
To implement all features of IHSM we made use of open source software packages: The semantic web framework Jena5 is used to load, store and query 3 http://xmlns.com/foaf/spec/ 4 http://www.livejournal.com/bots/ 5 http://jena.sourceforge.net/ the ontology and Pellet6 provides the OWL DL reasoning capabilities. We implemented IHSM and integrated it into this framework. In our experiments the truncation parameter was set to #Individuals=4 and 0 = 0 = 10. We ran 100 iterations each, where 50 iterations are discarded as the burn-in period. As this is intended to provide a feasibility evaluation rather than a performance benchmark we did not carry out any parameter tuning. We will now report rst results on learning the LJ-FOAF data set. Concerning the computational complexity, the additional consistency check for every individual per iteration is approximately slower by a factor of 6. However, this is partly due to the prototypical implementation of IHSM.
An interesting outcome is the number of clusters per hidden variable after convergence (see Table 1). Considering the di erence between IHRM and IHSM, the larger cluster numbers suggest that concepts a ected by constraints are likely to be found more diverse by IHSM.
Fig. 5 compares the learned parameter knows of IHRM to the one learned by IHSM. This indicates the correlation of P erson clusters with regard to the role knows. IHRM converged to 16 und IHSM to 19 clusters. On top of the clusters we show the number of instances per cluster. A brighter cell indicates stronger relations between two clusters. Note that knows is considered a directed relation, thus this does not result in a symmetric matrix.
Although hard to generalize, a cell with 50% gray might indicate that no signi cant probabilistic dependencies for individuals in this cluster are found in the data. Regarding this, it seems to be surprising that knows-relations of large clusters predominantly show this characteristics. Interestingly, individuals in those large clusters are those user pro les that are just referenced by other persons but not extracted by the web crawler. Besides that, social networks tend to have a few strongly connected users and many less active users with little connections. This may reinforce this e ect.
As mentioned before, IHSM results in more diverse clusters. Most interestingly, there are rows with noticeable darker cells (marked with black arrows) 6 http://pellet.owldl.com/ and those darker cells are symmetric. This suggests that those clusters represent con icting individuals. In fact, all of those cells contained at least one pair of persons that con icted with the ontology. This indicates that one of the main goal of IHSM is achieved, namely the exploitation of constraints provided by the ontology. 6
Very generally speaking, our proposed method aims at combining machine
learning with formal logic. So far, machine learning has been mainly approached either
with statistical methods, or with approaches which aim at the inductive
learning of formal knowledge from examples which are also provided using formal
logic. The most important direction in this respect is Inductive Logic
Programming (ILP). Probabilistic- and Stochastic Logic Programming (e.g., [
XII
Surprisingly there are also hardly any applications of (pure) SRL algorithms
to (SW) ontologies. The few examples, e.g. [
With the presented approach, we hope to open up a new line of future research directions. In general we are curious to see more work on inductive learning with SW ontologies and on the other hand SW ontologies that can be supplemented by uncertain evidence. Concerning IHSM in particular a detailed empirical and theoretical analysis on the e ect of constraining on clusters seems promising. We also expect experimental proof for improved predictive performance when formal ontologies are exploited.