ILP is now a well-established research area where machine learning meets logic programming [18], which has shown the potential to address many real world problems [6]. Description Logics (DLs) are a family of languages representing domain knowledge as descriptions of concepts, roles and individuals. DLs can be considered as fragments of First Order Logic (FOL). Because of their well-defined semantics and powerful inference tools, DL have been the representation of choice for ontologies, including applications, such as the Semantic Web. ILP algorithms using DL representation have the potential to be applied to large volumes of linked open data and to benefit from the tools available for such data, e.g. IDEs, such as Protégé, triplestores, providing efficient storage and retrieval, and reasoners, which can test the data for consistency and infer additional knowledge. DLs are subsets of FOL, and the representation they use has a variable-free syntax. This is claimed to make the knowledge base statements easier to read than the corresponding FOL formulae [2]. Traditionally, ILP algorithms use the Closed World Assumption (CWA), while DLs operate under the Open World Assumption (OWA). Existing attempts to apply ILP to DL data have explored both possibilities, as shown in Section 3.1.

The chosen application area of Preference Learning (PL) aims to induce predictive preference models from empirical data, e.g. by assigning an absolute rank to the choices available [8]. Online vendors already employ methods, such as collaborative filtering, which allow to produce selective lists of the most popular products among users with similar tastes [16].

The automation of PL has now become essential in many e-commerce applications following the current call for customer personalisation. The method of pairwise comparisons, which we focus on, is relatively new in preference learning, although there are exceptions [3,10,20,19,14]. Balakrishnan and Chopra [3] published a research study on pairwise preferences by using a Bayesian framework. Qian et al. [19] published a similar idea, proposing an approach to learn user preferences by using pairwise comparisons to explore each attribute in turn through "orthogonal queries" and then applying linear SVM to approximate the preferences. Similarly, Jensen et al. [10] apply a Gaussian Process regression model for comparisons between music tracks. Another similar work was performed by Rokach and Kisilevich [20] which uses lazy decision trees with pairwise comparisons at each node.

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 [14], which proposes a framework for learning weak constraints in Answer Set Programming (ASP). We build on previous work combining ILP and DL, namely, the DL-Learner [15], which aims to find a correct class description in a specific ontology from a set of positive and negative examples of individuals. It builds a hypothesis in the form of a class description, which can contain conjunction, disjunction and existential quantification. DL-Learner itself develops previous work on systems, such as YinYang [9] and DL-FOIL [5]. Kietz's [12] and Konstantopoulos' [13] work is also relevant in this context. While DL-Learner can only learn class definitions, we aim to learn definitions of relations. Here we focus on the binary relation of order, and in particular, strict order, a relation that is transitive, anti-reflexive and anti-symmetric. Our aim is to learn each user's individual preferences using a DL-based representation, and an algorithm inspired by the Progol/Aleph family of ILP tools. We evaluate our algorithm on two datasets, one on car preferences [1], the second on sushi preferences [11]. Both datasets provide pairwise preference choices of multiple users.

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.

DLs represent the world in terms of concepts, objects and roles. Concepts can be seen as a formal definition of classes in the application domain, e.g. one can define 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 finite 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 first 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 data 2The preference learning problem is defined 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 first individual is preferred over (strictly better than) the second, Find: a disjunction of axioms defining 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 considering their attributes. We then use these labels to search for a definition 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-reflexive (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 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.

The aim of ILP is to find 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 definitions, 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)).

Our algorithm represents background knowledge through classes and their membership, as shown in the example below (

In our algorithm, the set of positive examples is defined 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).

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 [7] and RDF4J API5 to handle DL. The algorithm is shown in Algorithm 1. We follow the four basic steps used in the Progol/Aleph greedy learning approach:

1. Select a positive example. Each instance of the relation can be seen as a pair of object IDs.

2. Build the bottom clause. The bottom clause is constructed from the conjunction of all non-disjoint classes of which each individual in the pair is a member.

Search. This step is to find all generalisations of the bottom clause of the same, lowest possible, length that are consistent with the data.

We use a top-down approach similar to the one in Progol/Aleph starting from the shortest clause possible. Note that for the specific class of problems, namely, learning strict order, the most general, unconstrained definition stating that for any pair of objects, the first is better than the second, is true in exactly 50% of the cases for every pair x, y , x = y, as where this is true, the relation will not hold for the pair y, x . It will also always be false for pairs of type x, x . 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 refinement 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 first 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 classified as positive. 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 difference between the two algorithms and a possible explanation for any observed difference in their performance.

If a consistent clause has not been found yet, the algorithm continues to refine the current candidate by adding one literal to constrain either object in the relation. Similarly to Aleph, when APARELL cannot find 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 difference 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. for all end if 30: end while 31: Return T 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 first (modulo the choice of a training sample). The resulting coverage is therefore almost identical to the one of the CWA hypothesis.

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 refinement search, as SmallCar EconomyCar 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 EconomyCar is {car1,car8}, which is the same as the membership of SmallCar itself.

Search. The search begins from the shortest clause length considered (2 literals) as shown below:

Car betterthan Manual 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.:

EconomyCar and FamilyCar betterthan Car EconomyCar and FamilyCar betterthan Manual ... 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 finish while Aleph performs faster in just 88 ms.

We use two publicly available preference datasets [1,11]. Both the sushi and the car datasets have 10 items to rank which leads to 45 preference pairs per user. We take 60 users from each dataset and perform 10-fold cross 1. Despite the difference in the number of attributes in the two datasets, we found that the maximum clause length of 4 (in Aleph and in our algorithm) is sufficient to produce consistent hypotheses.

The second dataset used in the experiments is about sushi preferences6 which has been published by Kamishima [11]. The dataset contains user individual preferences about 10 different sushi types. The users asked to sort the sushis according to their preferences in an ascending order. For the experiment, we generate the pairs order from each set of individual preferences. Similar to the previously mentioned car dataset, 45 pairs of sushi preferences are produced for 10 types of sushi (which represents all possible pairs). In this dataset, there were 5000 users involved in the survey. The sushi preference dataset is quite large when compared to the car preference dataset as it has 7 attributes describing each type of sushi. With a dataset of such size, we can test the performance of our algorithm and evaluate how it grows.

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 significantly differ.

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. Accuracy on 60 users.

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 classification algorithm, which is used in many domains. Previous work of pairwise preference learning was performed by Qian et al. [19] showing that SVM can also be used to learn in this domain. Both DT and Aleph are learners expressing their models in logic, where the former uses propositional logic and the latter -(a subset of) First Order Logic (namely, Horn clauses). 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 significant difference 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 find which algorithms are significantly different by using Fisher's Least Significant Difference (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 unaffected (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 first experiment, we have already evaluated the mean difference 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 differences in a large dataset can be problematical as p-value As mentioned in [2], by using DL representation, which is variable-free syntax, our algorithm can produce a set of solutions which are more readable compared to the First Order Logic representation. An example of a consistent hypothesis found by our algorithm is shown below:

(Manual) betterthan (Sedan) (Automatic and Hybrid) betterthan (MediumCar and Suv)

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 first 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.

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 significantly 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 significant (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 final 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 refinement operator by allowing the use of different operators (e.g. union or negation) with the aim of improving the accuracy.