Here we describe a Description Logic (DL) based Inductive Logic Programming (ILP) algorithm for learning relations of order. We test our algorithm on the task of learning user preferences from pairwise comparisons. The results have implications for the development of customised recommender systems for e-commerce, and more broadly, wherever DL-based representations of knowledge, such as OWL ontologies, are used. The use of DL makes for easy integration with such data, and produces hypotheses that are easy to interpret by novice users. The proposed algorithm outperforms SVM, Decision Trees and Aleph on data from two domains.
Copyright c by the paper's authors. Copying permitted for private and academic purposes.
In: Nicolas Lachiche, Christel Vrain (eds.): Late Breaking Papers of ILP 2017, Orleans, France, September 4-6, 2017, published at
http://ceur-ws.org
preference learning, although there are exceptions [
Most studies on pairwise preference learning use statistical machine learning approaches while in this paper,
we propose a logic-based approach. There is one other attempt at using ILP for preference learning [
The rest of the paper is organized as follows: in Section 2 we explain the learning task in terms of both logic programming and DL to make the problem clearer to readers from either background. We then propose an algorithm based on ILP in Section 3 and provide the analysis of the evaluation in Section 4. Finally, we conclude our work and provide our plan for further work in Section 5. 2
DLs represent the world in terms of concepts, objects and roles. Concepts can be seen as a formal de nition of classes in the application domain, e.g. one can de ne a father as a man who has at least one child. Concepts have two functions: (1) to describe a collection of objects and (2) to describe the properties that a class should hold. Objects are the entities that belong to one concept or another. Roles represent binary relationships between objects, e.g. John is Anna's father. These can also be used to describe object properties, e.g. John's age is 42. In FOL terminology, objects correspond to unique constants (i.e. ground terms), concepts correspond to unary predicates, and roles correspond to binary predicates. All this information is stored in the form of a knowledge base which comprises of two components, an assertional part (ABox ) and a terminological part (TBox ).The TBox is a nite set of General Concept Inclusions (GCI) and role inclusions. It corresponds to the notion of a schema in a relational database. The assertional set in the knowledge base is called the ABox. It is used to state properties of individuals. In a relational database, this is the actual data, while in the FOL it corresponds to facts (aka ground terms).
The knowledge representation in DL can be expressed using the Resource Description Framework (RDF), which is one of the most powerful general-purpose knowledge representation languages. The syntax of RDF is based on triples in the form of subject-predicate-object expressions. An RDF triple is a statement expressing a relation (\predicate") between the object in its rst argument, and the object or literal in its third argument (e.g. \Anna-has father-John"). In this section, we use Turtle1 syntax to describe RDF data2 The preference learning problem is de ned as follows:
Given: a set of individuals, a class hierarchy, a mapping from individuals to classes, and a set of preferences represented as pairs of individuals, where the rst individual is preferred over (strictly better than) the second, Find: a disjunction of axioms de ning the domain and range of the relation betterthan (where each axiom is expressed as a conjunction of classes) that is complete and consistent with the given preferences. This is a supervised learning problem as the user assigns one of two possible labels for each pair of items after 1https://www.w3.org/TR/turtle/ 2Turtle stands for Terse RDF Triple Language. considering their attributes. We then use these labels to search for a de nition of the Domain and Range class memberships that render the relation true.
We propose an approach to learn relations and apply the resulting system to learn strict order (i.e. better than). The properties of strict order relation are anti-symmetric, which means that if item A is better than item B, then in any case item B cannot be better than item A, unless A=B. That special case is then excluded by the additional assumption of betterthan being anti-re exive (i.e. X cannot be seen as better than itself). It is also transitive, which means whenever item A is better than item B, and item B is better than item C, then item A is better than item C. The ontology reasoner can always be used to extract all pairs of items satisfying the (b) The user annotation is translated into the object property \betterthan". (a) A simple car class hierarchy preference relation as a result of applying its transitivity property. We add these inferred examples to the set of positive examples so that the complete closure is used by the learning algorithm. We also use the anti-symmetry property to produce all negative examples as a `mirror image' of the positive (after completing their transitive closure), i.e., all pairs derived from a positive example through the swap of the rst and second element in the pair.
The representation of a sample preference learning problem in DL is shown in Figure 1. The class hierarchy is given to the system as an input. We evaluate our algorithm using a simple class hierarchy as shown in Figure 1a in order to make the solutions comparable to the Aleph representation. 2.1
The aim of ILP is to nd a theory that is complete (it covers all the given positive examples) and consistent (it covers no negative examples). In our algorithm learning from RDF data, we build a hypothesis for an object property we want to learn, as in the case of the property betterthan. The fact that betterthan is an object property is described in Turtle as shown below:
myontology:betterthan rdf:type owl:ObjectProperty.
Each of the possible hypotheses about this relation is then described as a pair of class de nitions, which specify the membership of the domain D and the range R of the relation. The same hypothesis language can be described in Aleph notation as the following mode declarations: :- modeh(1,betterthan(+car,+car)). :- modeb(1,hasbodytype(+car,#bodytype)). :- modeb(1,hasfuelcons(+car,#fuelconsumption)). :- modeb(1,hasbodytype(+car,#bodytype)). :- modeb(1,hastransmission(+car,#transmission)). :- modeb(1,hasenginesize(+car,#enginesize)). 2.2
Our algorithm represents background knowledge through classes and their membership, as shown in the example below (which uses Turtle syntax): myontology:Sedan rdf:type owl:Class ; rdfs:subClassOf myontology:Car ; owl:disjointWith myontology:Suv . myontology:car1 rdf:type owl:NamedIndividual , myontology:Car , myontology:Manual , myontology:NonHybrid , myontology:SmallCar , myontology:Suv .
The same background knowledge can be spelt out in Aleph as follows: car(car1). %type predicate bodytype(sedan). %type predicate hasbodytype(car1,suv). %bk hasfuelcons(car1,nonhybrid). %bk hastransmission(car1,manual). %bk hasenginesize(car1, small). %bk
In our algorithm, the set of positive examples is de ned by the user's preferences, and the following pre-processing step that computes the transitive closure of these preferences, which are then negated to produce all negative examples. The following Turtle code expresses that car1 is better than car3, car4, car5, and car10: myontology:car1 myontology:betterthan myontology:car3 , myontology:car4 , myontology:car5 , myontology:car10 .
In traditional ILP syntax, the same examples are represented as ground facts of the predicate betterthan/2, where the arguments are of type car. So, the positive examples in Aleph are written as: betterthan(car1,car3), and the negative, obtained by their reversal, as :-betterthan(car3,car1). 3
We propose an algorithm called APARELL (Active3 Pairwise Relation Learner) which learns the relation of
strict order in DL. We implement our algorithm in Java using the OWL API4 [
We use a top-down approach similar to the one in Progol/Aleph starting from the shortest clause possible. Note that for the speci c class of problems, namely, learning strict order, the most general, unconstrained de nition stating that for any pair of objects, the rst is better than the second, is true in exactly 50% of the cases for every pair hx; yi; x 6= y, as where this is true, the relation will not hold for the pair hy; xi. It will also always be false for pairs of type hx; xi. This is why the algorithm proceeds by considering an increasing, and strictly positive number of properties (literals) constraining either object in the relation. The bottom clause contains the conjunction of n constraints (of type class membership) on the Domain side and the same number of constraints again on the Range side of the relation. We evaluate all combinations of constraints, except the ones that imply the same class membership of both arguments (i.e. X is better than Y because they both share the same property/class membership) or those that have already been considered. An example of the re nement operator steps starting from a positive example car1 is better than car3 is illustrated in Figure 2 (please see Section 4.1 for a description of the dataset of car preferences).
We express the coverage of a clause through P and N , where P { the number of positive examples covered, and N { the number of negative examples covered. In the case that the solution has the same score as another alternative, Aleph will only return the rst solution found. In our algorithm, we consider all new clauses that cover at least two positive examples and none of the negatives. (This is done to ensure consistency, and that at least a minimum level of generalisation takes place.) The search will not stop until all the possible combinations at each level have been considered. The resulting theory is a disjunction of clauses. Therefore, any test example covered by one of them is classi ed as positive.
(Thing) betterthan (Thing)
(Car) betterthan (Car) (Manual) betterthan (MediumCar) (Manual) betterthan (NonHybrid)
Our algorithm retains all consistent clauses generalised from a given positive example, rather than just one of them, as Aleph would have done. (At the same time, both algorithms discard the positive example from the training set after this generalisation step in a greedy learning manner.) This is the most important di erence between the two algorithms and a possible explanation for any observed di erence in their performance.
If a consistent clause has not been found yet, the algorithm continues to re ne the current candidate by adding one literal to constrain either object in the relation. Similarly to Aleph, when APARELL cannot nd a consistent generalisation, it adds the bottom clause itself to the theory.
We implement our algorithm using the Closed World Assumption (CWA). For the problem of learning strict order, it makes virtually no di erence whether our system operates under the CWA or OWA. Under the OWA, we learn two hypotheses: one as mentioned before, the other with the positive and negative examples swapped. Algorithm 1 APARELL 1: Input : background knowledge B, a set of positive examples E+ = fhe1; e2i; : : : ; hen; emig, a set of negative examples E = fhe2; e1i; : : : ; hem; enig, maximum number of literals (depth limit ) l a relation name r = betterthan 2: Output : A theory T represented as a set of clauses, each de ning a pair of concepts specifying the relation's domain and range 3: set T = ; /* initialization*/ 4: set x1 = ; /* the list of constraints on Domain */ 5: set x2 = ; /* the list of constraints on Range */ 6: set f lag = false /* whether a consistent generalisation of the bottom clause has been found */ 7: while E+ is not empty do 8: set clause size = 2 /* initial value for jx1j + jx2j */ 9: set x1 = ;, x2 = ;, f lag=false /* reset in every loop*/ 10: select e+ 2 E+ to be generalised, and de ne he1; e2i = e+ 11: /* build the bottom clause hx1; x2i for e+ as follows: */ 12: set x1 = fC1; : : : ; Cmg 8Ci such that e1 2 Ci 13: set x2 = fD1; : : : ; Dng 8Di such that e2 2 Di 14: while f lag==false and clause size < l do
/* search (top-down) through all generalisations of the bottom clause */ 15: for all x01 x1; x02 x2; jx01j + jx02j == clause size do 16: if x01 betterthan x02 is consistent and more general than e+ then 17: add the clause to T 18: set f lag = true 19: end if 20: end for 21: if f lag==false and clause size < l then 22: set clause size = clause size + 1 /* increment clause size */ 23: else if f lag==false and clause size == l then 24: add e+ to T and remove e+ from E+ 25: end if 26: end while 27: if ag==true then 28: remove covered positive examples from E+ 29: end if 30: end while 31: Return T For the given domain (of learning strict order), the second hypothesis (i.e. the one that being swapped between the negative and positive examples) is almost the exact negation of the rst (modulo the choice of a training sample). The resulting coverage is therefore almost identical to the one of the CWA hypothesis. 3.2
In the case of a more complex class hierarchy that consists of more than one level, we consider the hypothesis search over all the inferred class memberships of each individual. For example, if the class hierarchy and its membership in Figure 3 are given to the system, the algorithm progresses as follows: 1. Select a positive example. As an example, we choose car 1 is better than car 3 to be generalised. Please see Table 1 for the properties of the cars. 2. Build the bottom clause. In this step, we use the reasoner to infer all the classes which include car 1 and car 3 as their direct and indirect membership. The bottom class of the above example is shown as follows: (Car and EconomyCar and FamilyCar and Manual and
NonHybrid and SmallCar and Suv) betterthan (Car and Manual and MediumCar and NonHybrid and Sedan) The above bottom clause is only used to guide the re nement search, as SmallCar v EconomyCar v Car. We do not consider clauses referring to the membership of the intersection between a class and its superclass, as this will be the same as the membership of the class itself. For example, the membership of SmallCar u EconomyCar is fcar1,car8g, which is the same as the membership of SmallCar itself. 3. Search. The search begins from the shortest clause length considered (2 literals) as shown below:
Car betterthan MediumCar Car betterthan NonHybrid Car betterthan Sedan EconomyCar betterthan Car EconomyCar betterthan Manual ...
In the case that we have not found any consistent hypothesis of length 2, this parameter is increased to 3, etc.:
It should be noted that the algorithm skips the evaluation of the same value comparisons like: Car betterthan Car to speed up the search. 4. Remove covered positive examples. We count the coverage for each hypothesis we build and remove the covered positive examples from the training dataset. 3.3
Our algorithm can handle a multi-level class hierarchy, but, in order to limit the search, we only allow conjunctions of literals in the clauses, e ectively limiting the language to EL description logic. With this limitation, we can still produce accurate models for our test cases, and a result in a form that is easy to interpret. The most expensive process is checking the class membership (by using the ontology reasoner) for every possible hypothesis. This is used for scoring the hypothesis coverage. The search in our algorithm follows breadth- rst search with limited depth (speci ed as the l parameter).
Another property of our proposed algorithm is that, unlike Aleph, we do not provide a single consistent clause covering a given positive example, but add to the resulting theory all such clauses of the minimal possible length. While this can produce a more accurate result, the learning process takes longer than in Aleph. For example, given 45 training examples in which each item has 4 attributes, our algorithm takes 409 ms to nish while Aleph performs faster in just 88 ms. 4 4.1
We use two publicly available preference datasets [
The second dataset used in the experiments is about sushi preferences6 which has been published by
Kamishima [
The goal of this evaluation is to assess the accuracy of the predictive power of our algorithm to solve the preference learning problem. To do this, we set up four experiments as below: 1. Assess the accuracy of our algorithm compared to the three baseline algorithms, SVM, Aleph and DT, on 60 users in car dataset and sushi dataset. Here, we also perform an ANOVA test and a post-hoc test to assess which algorithms signi cantly di er. 2. Assess the accuracy and the performance of our algorithm on a larger dataset by conducting an experiment on 5000 users of the sushi dataset. 3. Assess the potential of our algorithm to learn relations from a more complex class hierarchy by using the car dataset. 4. Assess the accuracy of our algorithm on training examples of di erent size, and compare it to the three baseline algorithms.
We compare our algorithm with three other machine learning algorithms: SVM, the Matlab CART Decision
Tree (DT) learner, and Aleph. SVM is a very common statistical classi cation algorithm, which is used in many
domains. Previous work of pairwise preference learning was performed by Qian et al. [
We build a simple class hierarchy as explained in Section 2 for each dataset. We learn from each set of individual preferences and evaluate the model by using 10-fold cross validation. We repeat the same test for all users then calculate the average accuracy. The result is shown in Table 2. In this experiment, the search stopped at a maximum length of 4 literals (this is the same as Aleph's default clause length of 4). According to the ANOVA test with = 0:05, the result shows that there is a signi cant di erence amongst the algorithms with a p-value of 1:14 10 21 for the car dataset and 2:97 10 3 for the sushi dataset. ANOVA is conceptually similar to multiple two-sample t-tests, but is more conservative (results in less type I error). After performing the ANOVA test, we nd which algorithms are signi cantly di erent by using Fisher's Least Signi cant Di erence (LSD). The result of this post-hoc test is shown in Table 3. Please note that the result of this 10-fold cross validation may have introduced a bias in terms of absolute performance levels due to the fact that the use of transitivity chains (closures) may have created an overlap between training and test data. However, the same training and test data have been used to compare all algorithms, so the results for their comparison remain una ected (are not biased).
In this experiment, our algorithm is still showing the highest accuracy amongst the other three baseline algorithms. The average accuracy on individual preferences from 5000 sushi dataset users is shown in Table 4. In the rst experiment, we have already evaluated the mean di erence amongst the algorithms using ANOVA and a post-hoc test. In here, the p-value of ANOVA ( =0.05) test is 0. This is a common case in large datasets. Performing statistical test to analyze the mean di erences in a large dataset can be problematical as p-value tends to drop quickly to zero. From the result shown in Table 4, the low standard deviation rate can be a good indication that the accuracy of our algorithm is excellent in any case.
As an additional experiment, we evaluate the car dataset with the complex class hierarchy (see Figure 3) using literal depth limit=4. The accuracy of our algorithm is performed using 10-fold cross validation. The result of the experiment with the complex class hierarchy is a mean of 0.8409 and standard deviation of 0.1405. The accuracy result shows no di erence between using a simple class hierarchy and a complex class hierarchy.
We perform several experiments with the algorithms by varying the proportion of training examples and test it on 10% of examples. For a more robust result, we validate each cycle with 10-fold cross validation. The result of these experiments is shown in Figure 4. We show that our algorithm still works better even with the smallest number of training examples.
We run another test to see the algorithm performance by di erent clause length settings (see Table 5). The evaluation is performed on both datasets by using a 90:10% training-test split. We also record the algorithm execution times of 60 users 90% of examples (2,382 total examples in car dataset and 2400 total examples in sushi dataset, please note that some of the positive examples are removed during the search). The algorithm was executed on Java 8 Eclipse IDE with 8 GB Memory 1867 MHz DDR3 and 2.9 GHz Processor Intel Core i5 machine. The result shows there is no signi cant accuracy improvement after 4 literals. Surprisingly, the algorithm runs very slow at 2 literals for the car dataset (where the achieved accuracy is the lowest for all tested clause lengths). The reason is in Step 4 i.e. the removal of covered positive examples (see Section 3). If we cannot nd any consistent hypothesis when generalising a positive example, we add an exception and only remove one example. But when the algorithm can nd consistent hypotheses, it removes more than one example which results in much fewer positive examples thus speeding up the search. This anomaly does not occur in the sushi dataset due to the larger number of attributes so that the possibility to nd a consistent hypothesis for clause length 2 is higher.
As mentioned in [
The above rules simply say that: \Manual car is better than sedan car OR automatic hybrid car is better than medium size SUV car." In comparison, Aleph produces rules, such as: betterthan(A,B) :- hasenginesize(B,large), hasenginesize(A,small). betterthan(A,B) :- hasfuelcons(B,nonhybrid), hasbodytype(B,sedan).
The rst Aleph's rule states that: \car A is better than car B if car B has a large engine size and car A has a small engine size." In the second rule, it says:\car A is better than car B if car B is a non hybrid car and sedan." In other words, if the car has characteristics as a non-hybrid sedan car, it will not be better than any other car. 5
In this paper, we have shown that the implementation of ILP in DL can be useful to learn a user's preference from pairwise comparisons. In fact, the proposed algorithm has proven statistically signi cantly better than all tested alternatives in all but one case. The exception in question is when compared to SVM on the car dataset, where our algorithm achieves a seemingly higher mean accuracy, but the result is not statistically signi cant (in other words, it is a draw).
We are currently working to address some of the limitations of the algorithm. In terms of accuracy, we show that our algorithm outperformed the other algorithms. However, to produce the nal theory, our algorithm takes much longer than each of the three baseline algorithms. Currently, the only way to restrict the search complexity is by limiting its depth. We need to work on the improvement of this aspect without reducing the accuracy performance. The possible alternatives include the use of heuristic functions to predict the cost of expanding a node (i.e. informed search). We are also working on expanding the re nement operator by allowing the use of di erent operators (e.g. union or negation) with the aim of improving the accuracy.