Using Inductive Logic Programming to globally approximate Neural Networks for preference learning: challenges and preliminary results Daniele Fossemò1,∗ , Filippo Mignosi1,2 , Luca Raggioli3 , Matteo Spezialetti1 and Fabio Aurelio D’Asaro4 1 Department of Information Engineering, Computer Science and Mathematics, University of L’Aquila, Italy 3 Department of Computer Science, University of Manchester, United Kingdom 2 ICAR-CNR, Palermo, Italy 4 Ethos Group, Department of Human Sciences, University of Verona, Italy Abstract In this paper we explore the use of Answer Set Programming (ASP), and in particular the state-of-the-art Inductive Logic Programming (ILP) system ILASP, as a method to explain black-box models, e.g. Neural Networks (NN), when they are used to learn user preferences. To this aim, we created a dataset of users preferences over a set of recipes, trained a set of NNs on these data, and performed preliminary experiments that investigate how ILASP can globally approximate these NNs. Since computational time required for training ILASP on high dimensional feature spaces is very high, we focused on the problem of making global approximation more scalable. In particular we experimented with the use of Principal Component Analysis (PCA) to reduce the dimensionality of the dataset while trying to keep our explanations transparent. Keywords Explainable AI, Preference Learning, Answer Set Programming, Inductive Logic Programming, ILASP, PCA 1. Introduction The application of machine learning algorithms in very diverse fields has exponentially increased in the last decade, covering more operational areas, like robotic and drone navigation, as well as the processing of sensitive data, such as in legal reasoning. The use of this category of techniques reached remarkable performance in several complex tasks, in some cases achieving superhuman capabilities (e.g., DeepMind’s AlphaZero/Go winning against the Go and chess world champions). A very relevant issue with many Machine Learning (ML) models, however, is that the internal structure and the processes are exceedingly hard to understand and interpret, even for the developers themselves – for this reasons they are sometimes referred to as black-box BEWARE: Joint BRIO, MEE and AWARE Workshop @ AIxIA 2022, November 28 - December 2, 2022, University of Udine, Udine, Italy ∗ Corresponding author. Envelope-Open daniele.fossemo@student.univaq.it (D. Fossemò); filippo.mignosi@univaq.it (F. Mignosi); luca.raggioli@manchester.ac.uk (L. Raggioli); matteo.spezialetti@univaq.it (M. Spezialetti); fabioaurelio.dasaro@univr.it (F. A. D’Asaro) © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org) (BB) models. This issue is even more pressing and calls for attention in cases where sensible data are involved, and when the model’s reasoning and outputs may have a tangible impact in the real world. In 2016, the General Data Protection Regulation (GDPR)1 was introduced, stressing the need for automated systems’ decisions to be complemented with meaningful explanations of the logic behind its’ decisions, especially when these may potentially affect individuals. This has spotlighted the need for transparent systems that are able to provide the users with human-understandable rationale for their decisions, as well as post-hoc methods, which instead attempt to formulate an explanation from black-boxes outputs (see [1] for a survey of such methods). An advantage of this latter approach is that they do not require to alter the black-box structure, thus not impacting the performance of such models. Transparent systems, on the other hand, often impose a trade-off between accuracy and explainability. In this work, we propose a post-hoc method to explain black-box models for preference learning using Answer Set Programming (ASP) [2] and Inductive Logic Programming framework ILASP [3, 4, 5], extending upon the work presented in [6]. These systems can output logical theories that easily translate into natural language, and therefore can be understood even by non-experts. For this reason, they are easier to check (when compared to non-transparent Machine Learning models) for the presence of biases and artifacts resulting from training on large collections of data (see e.g. [7, 8]). Following [6], we further our exploration of ILASP as a method to analyze and produce theories from target black-boxes, which may prove useful in situations where the data such black-boxes were trained on is not available. This method may help identify systematic biases such as, e.g., decisions influenced by prejudices or unfair principles. In this work we are particularly concerned with preference learning, so it is worth mentioning here that ASP suits well our task as its standard syntax has constructs known as weak con- straints [2] that can be used to naturally express preference relations. In turn, these preferences can be learned by ILASP. Thanks to its ability to generalize from examples, it can process the output of black-box methods to find an appropriate ASP program that mimics its behaviour. However, ILASP is computationally very expensive on highly dimensional data, with long execution times on average. For this reason, we used Principal Component Analysis (PCA) to identify the most relevant features in the data and decrease the size of the feature space, aiming to achieve a good trade-off between transparency and adherence of the output theory to the target black-box. Our target domain is that of gastronomic preferences, which we formalized as a comparison between recipes. More specifically, given a user and a pair of recipes, the model aims to classify them in one of the following three ways: “the user prefers the first recipe of the pair over the second one”, “the user prefers the second recipe of the pair over the first one” and “the user does not have a strong preference of a recipe over the other one”. We created a dataset of recipes retrieved from an Italian cooking website, GialloZafferano 2 . We then surveyed participants about their preferences about recipes in this dataset, and created a dataset of user preferences. We trained fully dense NNs on these user preferences (one for each user), and then trained ILASP on the output of such NNs. Finally, we studied to which extent the output theory of ILASP was able to accurately predict the output of the corresponding NN. The developed 1 https://eur-lex.europa.eu/eli/reg/2016/679/oj 2 https://www.giallozafferano.it/ code during the described work can be found in a public github repository 3 . As it will fully explained at the end of the article, in terms of accuracy, precision and recall, we haven’t obtained very good results in approximating black-box models. That said, the proposed methods involving PCA to approach the problem of the execution time required by ILASP during training phase looks promising. 2. Related Work This paper is a continuation of [6]. In that work, ILASP was applied to local and global approximation of Support Vector Machines (SVMs), a set of simple classical ML models that have often been used to benchmark explainable AI technologies (see e.g. [9]). The present work addresses the need for enlarging the scope of black-boxes taken under consideration to more fashionable (and complex) ML models such as NNs. Our work is not the only one using ILP to approximate black-boxes. For instance, [10, 11] and [12] use the Prolog-based system Aleph [13]. We use ILASP instead, which was shown to outperform Aleph accuracy-wise in some cases respect to the predictions (see e.g. [5]). Furthermore, our focus here is on preference learning tasks, which is a typical application area for ASP (as opposed to Prolog). Obviously, ILP is not the only possible approach to explaining black-box systems – for instance, Exceptional Preferences Mining [14] and LIME [15] are other techniques whose relationship to ILP and ILASP may be the subject of future work. Furthermore, we previously mentioned that our technique is a post-hoc one, namely it applies to any black-box whose training was performed before the explanation procedure takes place. Other powerful techniques can be deployed if we relax this constraint and perform model-specific operations throughout the training phase, as in [16] that is specific to NNs and requires some additional labeling effort. These systems are potentially more accurate than ours – nonetheless, they are not post-hoc and thus are less generally applicable than our approach. 3. Background In this section we give a brief overview of the basics of Answer Set Programming and Inductive Logic Programming, and how one can represent and learn preferences within them. Preference learning [17, 18, 19] aims to develop agents that can profile users, and know how to classify what could be of interest to them. In general, a preference system can be formalized as a (total or partial) ordering among items. More formally, given an instance space X and a set of labels 𝐿 = {𝜆1 , 𝜆2 , ..., 𝜆𝑘 }, an ordering for an instance x can be described as ordering of the labels by means of a relation ≻x such that 𝜆i ≻x 𝜆j indicates that 𝜆i is preferred over 𝜆j by instance x. So the ordering induced by ≻x can be identified by a permutation 𝜋x such that 𝜋x (i) = 𝜋x (𝜆𝑖 ) indicates the position of the label 𝜆𝑖 in the ordering. So, a complete ordering of the lables in L can be described as following: 𝜆𝜋x−1 (1) ≻x 𝜆𝜋x−1 (2) ≻x ... ≻x 𝜆𝜋x−1 (k) (1) 3 https://github.com/DanieleF198/ILASP-as-post-hoc-method-in-a-preference-system where 𝜋x−1 (j) indicates the index of the label which occupates the j-th position in the ordering [19]. In order to find out an accurate ≻x for each instance x and learn to ordering new elements in the future for that instance, the artificial intelligence is trained on a set of labels in which we already know the relationships. An ordering of elements can be decomposed in the form of pairwise comparison. The idea behind this decomposition is that the ordering of a set of element can be structured as a succesion of consecutive question “do you prefer 𝜆i over 𝜆j ?” (with i ≠ j) in which the answers could be either “yes” or “no”. Thus, knowing the position of each element in the order of preferences, we can define all preference relationships in this form by using the following function: 𝜆 ≻ 𝜆 , if 𝜆i preceed 𝜆j in the ordering f(𝜆i , 𝜆j ) = { i x j (2) 𝜆j ≻x 𝜆i , otherwise the number of couples (𝜆i , 𝜆j ), if k indicates the number of elements in the collection, is equal to k(k − 1)/2. This decomposition allow us to decompose the original problem into a set of presumably simpler sub-problems, which is useful from a machine learning point of view [17]. In our work we treat “uncertain” between elements. In fact, in a set of elements is possible that for an instance x is uncertain the preference relationship among some elements. We will treat this concept thanks to the algorithm 1 which we explain during the description of the creation of the dataset. Conceptually we will label couples of element for which we cannot find the preference relationship as uncertain couples, and so we pass from a problem of binary classification to one of ternary classification. Answer Set Programming [2] is a declarative logic programming language based on the stable model semantics, whose output is a model called of the input theory usually called stable model or answer set. We are particularly concerned with a special construct that allows one to represent preferences in ASP, namely the weak constraints, which induces a (partial) ordering over the stable models of a theory. Given n, m ≥ 0, a weak constraint has the form: :~ b1, ..., bn [w@l, t1, ..., tm] where b 1 , … , b n are literals, w is a weight associated with the constraint, l is a priority level, and t 1 , … , t m are used to handle independence among weak constraints4 . Unlike hard constraints, weak constraints do not affect the answer sets of a theory. Instead, they induce a preference relation among them. Intuitively, each answer set satisfying the body of a weak constraint gets a penalty that is proportional to that weak constraint’s weight. To describe the preference relation induced by these weak constraints, we first introduce the notion of cost of an answer set at some priority level l. This is defined as the sum of weights at priority level l for all the weak constraints such that their bodies are satisfied by the answer set. For instance consider the ASP program P consisting of the following axioms and weak constraint: p(a). p(b). p(c). 0{ q(X) }1 :- p(X). :~ q(a). [1@2, a] :~ q(b). [3@1, b] :~ q(c). [-1@2, c] 4 We are not going to discuss this syntax here, but the interested reader can find the full syntax and semantics in [2]. This theory has 8 answer sets, namely: {𝑝(𝑎), 𝑝(𝑏), 𝑝(𝑐)}, {𝑝(𝑎), 𝑝(𝑏), 𝑝(𝑐), 𝑞(𝑏)}, {𝑝(𝑎), 𝑝(𝑏), 𝑝(𝑐), 𝑞(𝑐)}, {𝑝(𝑎), 𝑝(𝑏), 𝑝(𝑐), 𝑞(𝑏), 𝑞(𝑐)}, {𝑝(𝑎), 𝑝(𝑏), 𝑝(𝑐), 𝑞(𝑎)}, {𝑝(𝑎), 𝑝(𝑏), 𝑝(𝑐), 𝑞(𝑎), 𝑞(𝑐)}, {𝑝(𝑎), 𝑝(𝑏), 𝑝(𝑐), 𝑞(𝑎), 𝑞(𝑏)} and {𝑝(𝑎), 𝑝(𝑏), 𝑝(𝑐), 𝑞(𝑎), 𝑞(𝑏), 𝑞(𝑐)}. The answer set {𝑝(𝑎), 𝑝(𝑏), 𝑝(𝑐), 𝑞(𝑎), 𝑞(𝑏), 𝑞(𝑐)} satisfies all the bodies of weak constraints, thus its cost at prior- ity level 2 is 0 (which results from adding the weights of the first and third constraint above), whereas its cost at priority level 1 is 3. We say that an answer set 𝐴 is preferred to an answer set 𝐵 (according to theory 𝑇) if the cost of 𝐴 is strictly smaller than that of 𝐵 at the highest level for which their costs differ. ILASP (inductive language of answer set programs)[3, 4, 5] is an Inductive Logic Programming language mainly used for Explainable AI, which can learn ASP programs. Furthermore, ILASP can learn the preferences represented as weak constraint in ASP. ILASP, given some additional background knowledge (the so-called language bias) required to define the hypothesis space, will find a suitable theory (including weak constraints) covering the examples in the input. Instead, theories that do not cover some of the examples are penalized by ILASP, which then tries to find the theory in the hypothesis space that is minimally penalized. 4. Dataset The domain of choice for this work is user-dependent gastronomic preferences, formalized through pairwise comparison between recipes. To this aim, we built two datasets, to gather recipes’ features and users’ preferences over recipes, respectively. Both are freely available online 5 . More specifically, the two dataset are: • Recipes dataset: a dataset of 100 recipes crawled and processed from Giallo Zafferano website. • Users Preferences: a dataset containing 54 different user answers about preferences on different subsets of recipes and preferences over the features of the recipes dataset. To realize the recipes dataset a crawler was used to send a set of requests to Giallo Zafferano website to get the pages with raw data, allowing us to obtain about 4000 recipes. We chose the first 100 most voted recipes by the website visitors (sweets and pastries excluded). The unprocessed and non-standardized data obtained with the crawler included 277 ingre- dients. In order to improve training efficiency while still maintaining a reasonable level of granularity in the data, we defined three levels of categorization: • All the ingredients are considered as in the raw data. This is the densest level of granular- ity. • The ingredients are divided into 36 classes. This is the intermediate level of granularity. • The 36 classes are grouped into 12 meta-classes. This is the least dense level of granularity. For example, the first ingredient “spaghetti” belongs to the class “dry pasta” which belongs, as well as “fresh pasta”, to the meta-class “pasta”. In the recipes dataset we considered the intermediate level of granularity, because it allows to have a reasonable level of specificity for the 5 https://doi.org/10.5281/zenodo.7265253 Feature Description ID A progressive integer number assigned to the recipe Name The Italian name of the recipe Integer number from 1 to 5, where: 1 → starter 2 → Complete Meal Category 3 → First Course 4 → Second Course 5 → Savory Cake Integer number from 1 to 5, where: 1 → very low 2 → low Cost 3 → medium 4 → high 5 → very high Integer number from 1 to 4, where: 1 → very easy Difficulty 2 → easy 3 → medium 4 → difficult Preparation time integer positive number, expressed in minutes Vector of 36 elements in which if the element i-th has a value: v ≥ 1 → the ingredient class represented by position i is present in the recipe and has v as importance Ingredients in the composition of the recipe v = 0 → the ingredient class represented by position i is not present in the recipe Preparations Vector of 9 elements with same codification of ingredients vector Link string representing the link of the recipe in Giallo Zafferano website Table 1 Recipe Dataset features ingredients, in light of the fact that these will be used to structure the surveys to administer to the users: in the surveys we ask the users to rank all the ingredients in the dataset, and ranking 277 ingredients is, obviously, un-practical. Since ILASP struggles with high-dimensional feature spaces, we performed ILASP experiments with the 12 meta-classes as this makes the training phase computationally feasible in our application. The recipes in the dataset are described by the features in Table 1. As example, the first entry of the dataset has the following representation: 1, Spaghetti alla Carbonara, 3, 2, 2, 25, [0 0 0 0 0 0 2 0 0 0 5 3 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 1 0 0 0 0 0 0], [4 2 0 0 1 0 0 0], https://ricette.giallozafferano.it/Spaghetti-alla-Carbonara. Before any further experimental step, the dataset was preprocessed as follows: • Normalization: for each recipe, the ingredient vector has been divided by its sum, as well as the preparation vector; • Standardization: each numerical feature has been standardized. For the realization of the survey we have considered several criteria, such as the choice of the questions, their structure and, most of all, the choice of how many and which recipes include in the survey. This latter was crucial as we wanted to collect as many user preferences as possible, while avoiding to present the participants with an excessive number of questions (e.g., rank 100 recipes in decreasing order of preference). To solve this problem we created 10 different surveys aiming to be as representative as possible of the distribution of the full set of 100 recipes. We furthermore tried to ensure that each recipe appeared in at least some of the surveys. To do so we used the PCA for dimensionality reduction following the kaiser rule (taking into account components with eigenvalue ≥ 1), reducing the 47 features to 17 Principal Components. Subsequently, we used the the k-means clustering to partition the dataset, considering k = 2, 3, 4, 5, 20. k was finally set to 3 as it allowed to maximize the number of clusters, while minimizing the inter-group variance, excluding results in which we have group with small cardinality. From each of the three partitions, we draw randomly 7 recipes, which are combined together to create a representative subset of 21 recipes. The 10 representative subsets obtained at the end of this process cover the entire recipes dataset. Recipes can be present in multiple representative subsets, but not more than once in the same one. Each representative subset is used to create a survey, in which we collect the following data6 : • Personal data: gender, age range and Italian region of residence. • Recipes evaluation: each recipe presented is rated on a scale from 1 to 10, where 1 means “I would never eat it” and 10 “I like it very much”. • Sorting recipes: where the user have to sort the recipes presented according to her/his personal preferences. • Ingredient classes evaluation: for each ingredient class presented, we ask to rate a generic recipe in which that ingredient class is present. • Ingredient meta classes evaluation: for each ingredient meta class presented, we ask to rate a generic recipe in which that ingredient meta class is present. • Preparations evaluation: for each food preparation, we ask to rate a generic recipe in which that preparation is done. • Generic preferences: generic preferences about cost, difficulty and preparation time. • Ingredient/Preparation combination preferences: we ask the user if there are par- ticular combinations of ingredients (class or meta class) and preparations for which his preferences diverges from the scores assigned to the individual elements (e.g.: the user has given a high score to the fish ingredient meta class and “frying” preparation method, but doesn’t like fried fish). Each combination generated by the user also needs to be rated (as in Recipes evaluation). We limited the each combination to a maximum of 3 items between ingredients and preparations, and we collected for each user a maximum of 4 combinations. It is important to note that the section Sorting recipes is divided in 3 subsections, because in 6 All data are collected in anonymous form, but in case the users were interested in viewing statistics regarding session, there is the possibility of providing their e-mail (which is not included in the dataset for privacy reasons) after the survey is concluded. Microsoft Form7 , the service used to make the surveys, it is not possible to ask to the user to sort more than 10 elements. For this reason the user is asked to sort the 21 recipes presented in the survey, by effectively sorting 10 elements at a time. The subsections are organized in the following structure: • 𝑂1 = [𝐼1(1,2) , 𝐼2(1,2) , 𝐼3(1,2) , 𝐼4( 1,3) , 𝐼5(1,3) , 𝐼6(1,3) , 𝐼7(1) , 𝐼8(1) , 𝐼9(1) , 𝐼10(1) ] • 𝑂2 = [𝐼1(1,2) , 𝐼2(1,2) , 𝐼3(1,2) , 𝐼11(2,3) , 𝐼12(2,3) , 𝐼13(2,3) , 𝐼14(2) , 𝐼15(2) , 𝐼16(2) , 𝐼17(2) ] • 𝑂3 = [𝐼4(1,3) , 𝐼5(1,3) , 𝐼6(1,3) , 𝐼11(2,3) , 𝐼12(2,3) , 𝐼13(2,3) , 𝐼18(3) , 𝐼19(3) , 𝐼20(3) , 𝐼21(3) ] where 𝑂𝑖 represent the 𝑖𝑡ℎ ordering subsection and 𝐼𝑗(𝐿) refers to the 𝑗 𝑡ℎ item that is present in the list of orderings 𝐿. Note that the subsections are organized in three ordering because this allow us to maximize the number of common recipes among the ordering. This would give us as much information as possible about the preferences and uncertainties of the user. Moreover we have created the representative subset exactly to avoid to ask too many questions to the users, and considering also the whole survey by itself, we considered that three orderings should be the best choice (indeed is the minimum number of orderings needed to cover all the 21 recipes). Elements present in more than one subsection allow us to combine the three orderings ranked by the users, and create a list of pairwise comparisons between the 21 recipes, with pairs of recipes that are directly or indirectly in a ordering relation (e.g. 𝑎 > 𝑏 and 𝑏 > 𝑐 → 𝑎 > 𝑐) being included in the list. More specifically, this process is structured as follows (and the pseudo-code is shown in Algorithm 1): • First, the algorithm searches for direct preferences in each ordering (i.e. if item 𝐼𝑖 precede 𝐼𝑗 ) and finds all the uncertainty between the partial orderings resulting from the 3 subsections (i.e. if item 𝐼𝑖 precede 𝐼𝑗 in an ordering but succeeds it in another). In this way an initial set 𝑆 of preference pairs (𝐼𝑖 , 𝐼𝑗 ) are obtained, meaning that 𝐼𝑖 is preferred to 𝐼𝑗 . • Then, the algorithm iteratively applies a transitive rule to the set of preferences: if (𝐼𝑖 , 𝐼𝑗 ), (𝐼𝑗 , 𝐼𝑘 ) ∈ 𝑆 then (𝐼𝑖 , 𝐼𝑘 ) is added to 𝑆. This rule is applied until no more changes are made to 𝑆. • The pairs for which no preference relationships were found in the previous steps, are marked with the uncertain relationship. It’s worth noting that the application of these steps, without further constraints, could cause to two possible issues: • Inconsistency: if more than one transitive rules can be applied in the same iteration to the same pair of items, but with an opposite verse, they could change 𝑆, by adding both (𝐼𝑖 , 𝐼𝑘 ) and (𝐼𝑘 , 𝐼𝑖 ); • Overwriting of existing preferences: to avoid inconsistencies, we should allow the transi- tive rule to remove (𝐼𝑘 , 𝐼𝑖 ), if present, if (𝐼𝑖 , 𝐼𝑘 ) is discovered. Unfortunately, this would lead to the overwriting of pairs discovered in previous iterations, but also, in case of transitive rules of the same iteration acting in an opposite way on the same pair, to an endless loop. 7 Note that we used Microsoft Form after considering different other solution and considering different criteria. Some of these criteria are ease of use, the possibility of exporting the answers via .csv files, the possibility of asking as a question the request to order a set of recipes through a ranking system, and the possibility of link the GialloZafferano recipe web pages directly on questions. We addressed both aspects by introducing a priority level decreasing from the first step through each iteration of the algorithm and by making it “lock”, with that level, pairs and uncertainties discovered at each iteration, so that their cannot be further changed. The rationale behind this choice is that we “trust” more in the first step and in earlier iterations, because they represent a shorter chain of transitive rules. Algorithm 1 Conversion from orderings to pairwise comparison Require: 𝑅 the list of 𝑛 element in the orderings; 𝑂 the list of recipes orderings 1: 𝑀 ← 0𝑛,𝑛 ; ▷ 𝑛 × 𝑛 matrix of zeros used to save preferences 2: 𝐿 ← 0𝑛,𝑛 ; ▷ 𝑛 × 𝑛 matrix of zeros used to keep trace of locked preferences 3: for (𝑟𝑖 , 𝑟𝑗 ) ∈ 𝑅 × 𝑅 do ▷ 𝑖 and 𝑗 are the indices of 𝑟𝑖 and 𝑟𝑗 in R 4: for 𝑜 ∈𝑂 do 5: if 𝑟𝑖 ∈ 𝑜 and 𝑟𝑗 ∈ 𝑜 and position(𝑟1 , 𝑜) < position(𝑟2 , 𝑜) then 6: if 𝐿[𝑖, 𝑗] == 0 then 7: 𝑀[𝑖, 𝑗] ← 1; 𝑀[𝑗, 𝑖] ← −1; 𝐿[𝑖, 𝑗] ← 1; 𝐿[𝑗, 𝑖] ← 1; 8: else if 𝑀[𝑖, 𝑗] == −1 then 9: 𝑀[𝑖, 𝑗] ← 0; 𝑀[𝑗, 𝑖] ← 0; 𝐿[𝑖, 𝑗] ← 1; 𝐿[𝑗, 𝑖] ← 1; 10: end if 11: end if 12: end for 13: end for 14: 15: 𝑐 ← 1; 𝑝 ← 2; 16: while 𝑐 == 1 do 17: 𝑐 ← 0; 18: for (𝑟𝑖 , 𝑟𝑗 , 𝑟𝑘 ) ∈ 𝑅 × 𝑅 × 𝑅 do 19: if 𝑀[𝑖, 𝑗] == 1 and 𝑀[𝑗, 𝑘] == 1 then 20: if 𝐿[𝑖, 𝑘] == 0 then 21: 𝑀[𝑖, 𝑘] ← 1; 𝑀[𝑘, 𝑖] ← −1; 𝐿[𝑖, 𝑘] ← 𝑝; 𝐿[𝑘, 𝑖] ← 𝑝; 22: else if 𝐿[𝑖, 𝑘] == 𝑝 and 𝑀[𝑖, 𝑘] == −1 then 23: 𝑀[𝑖, 𝑘] ← 0; 𝑀[𝑘, 𝑖] ← 0; 𝐿[𝑖, 𝑘] ← 𝑝; 𝐿[𝑘, 𝑖] ← 𝑝; 24: end if 25: end if 26: end for 27: end while 28: return 𝑀 Note that in the case in which we have only one list, then the effect of this algorithm will be simply the decomposition from a ranking problem to a pairwise comparison problem in which is never present the uncertain case. We used a script to redirect to one of the 10 surveys randomly, starting from a unique link that we have successively distributed. The surveys were filled out 48 times. From the third section of the surveys, then, we created the user preferences dataset. For each entry (and so, for each user) there are 210 pairs, in which the element are the ID of the recipes (pairs with elements with same ID were discarded). Each pair has label 1 if the first accuracy precision recall Support Vector Machines 76.54% 77.29% 76.54% K-nearest Neighbors 73.63% 67.49% 73.63% Neural Network 82.72% 83.26% 82.43% Table 2 Results of the considered black-box model Activation function Nodes Input layer tanh 64 Dropout Rate al 10% Hidden layer relu 64 Dropout Rate al 10% batch normalization Hidden layer linear 64 Dropout Rate al 10% Output layer softmax 64 Optimization function SGD learning rate 0,0005 Table 3 Neural network considered during experiments element is preferred over the second, -1 if the second is preferred over the first, 0 in case of uncertain relationship among the two element. 5. ILASP and PCA experiments The next step, after the realization of dataset, was to build a black box model to classify user preferences expressed in the pairwise form. Because we are in a user-dependent domain we aims to develop a model for each users, and so the statistics presented from now on are the mean of all the models results. To do so, we considered several methods, such as Support Vector Machines, K-nearest Neighbors and Neural Networks, tuning the hyper-parameters for each of them. The black box model exhibiting the best performance was a fully connected Neural Network, structured as in Table 3. Therefore we used this network architecture in the experiments with ILASP. Given that we are modeling user preferences, we trained a distinct model for each user. For instance, given the model approximating the preferences of user u, and the input (𝑖1 , 𝑖2 ), the NN outputs a class which should correctly represent the user preference. In order to evaluate the performance of the Neural Network, we averaged the results over the validation of each user’s model. The results are reported with the results obtained with Support Vector Machines and K-nearest Neighbors in table The aim of this work is to approximate the underlying theory of the Neural Network model using ILASP. To do so, there are two main possible approaches, that are using of ILASP as global or local approximator. In this work, we focus on global approximation, in order to extrapolate the general logic that the Neural Network use to make decision. Specifically, we samples N pairs (𝑖1 , 𝑖2 ) at random from the feature space and we label these pairs with the predictions B(𝑖1 , 𝑖2 ) made by the Neural Network; then we train ILASP on these pairs using an appropriate language bias L. For a deeper description of approximation approaches, please refer to D’Asaro et al. 2020 [6], which is the starting point of this work, and that we are trying to extent. During the experimental phase, we focused very thoroughly on preserving the trade-off between the execution time and the complexity of the theory returned by ILASP, which is used in order to approximate the Neural Network. Such a theory is a set of weak constraint labeled with a weight, consisting of different literals, and ordered by priority. Given, for instance, the following theory: :~ value(steaming,V1).[-1@3, V1] :~ value(meat,V1).[V1@2, V1] :~ value(prepTime,V1).[-V1@1, V1] :~ value(oven,V1).[-1@4, V1] :~ category(3), value(boiling,V1).[-V1@5, V1] this means that according to the explanation produced by ILASP over the set of constraints obtained from the NN, the user likes (in order of priority) first course dishes that are boiled, recipes prepared in the oven, recipes with the “steamed” preparation, does not like meat and likes long preparation times. There are different parameters that influence the theory produced by ILASP, as well as the accuracy of approximation of the Neural Network, such as the number of weak constraints and the number of literals allowed for each of them. Other important parameters are the number of sampled pairs and the dimensionality of the space of features, which have a relevant impact on the performance of ILASP. Unfortunately, the time complexity tends to grows exponentially with the increase of these parameters. In Figure 1 we show how the performances and the training time of ILASP are affected by the increase of the number of sampled pairs, the maximum number of weak constraints (maxp) in the theory and the maximum number of literals for each weak constraint (maxv). To handle this problem, we introduced the Principal Component Analysis in the workflow of approximation. The aim is to reduce the dimensionality of the dataset (as well as the execution time of ILASP), with a negligible loss of information.We explored two different approaches to use the PCA, which we refer to as indirect and direct. In the indirect PCA we determine which are the most important features among the first n principal components, so that we can reduce the number of features in the dataset accordingly. Let us consider the first n Principal Components obtained by applying the PCA on the dataset, and the weights 𝑤𝑖𝑗 that the feature i assigns to component j, then we only kept the features such that: 𝑤𝑖𝑗 ≥ 𝜇𝑗 + 2𝜎𝑗 j = 1, ..., n (3) This means that, the features whose weights are greater then the mean of the features’ weights plus two times the standard deviation, among the first n PCs, are those that we keep in the dataset. In the direct approach, we have passed to ILASP the recipes dataset directly after the PCA (so passing the PC as features). The idea behind this approach is to significantly reduce the feature Figure 1: The graphs are divided by row respect to the size of the training set (45, 105 and 210 couples); and by column respect to estimators (accuracy, precision and recall) and execution time. These graphs are about ILASP results on user 3 when it is used as global approximator of the neural network. Note that on the abscissa we have the value of the parameters maxv and maxp, which increase equally. As cab be seen the execution time grows exponentially both with the size of training set and the increas of maxp and maxv space, avoiding the loss of information as much as possible by exploiting the base concept of PCA, that is to make the first PCs as the ones which explain the higher variance of the dataset. Given the theory returned with this technique, which will have a shape like the following: :~ value(pc0,V1).[V1@1, V1] we can understand the feature involved by retro-projecting, from the PC of interest, the features which has higher weight. Of course, the effectiveness of this technique is affected by the choice accuracy precision recall execution time (seconds) Indirect PCA 62.67% 39.52% 39.48% 7122.82 Direct PCA (5PC) 67.10% 37.75% 39.08% 4.86 Direct PCA (10PC) 72.09% 44.84% 49.02% 8.19 Direct PCA (15PC) 66.90% 36.63% 37.21% 30.47 Direct PCA (20PC) 65.52% 35.11% 35.58% 43.57 Table 4 Results in global approximation with indrect and direct PCA approaches over 10 user with training set of 190 couples. Accuracy, precision and recall are about performances reached on the test set, of 105 couples, while execution time refer to the time required from ILASP during the training. of how many feature are retro-projected from the PC. For instance we can extrapolating these features using the equation 3, considering only the PC given by the theory; or considering the feature which has higher value for each PC in the theory, and so on. 6. Preliminary Results In this section we present some preliminary results concerning a subset of 10 users. This is due to the high execution time faced during the ILASP experiments. These users are the ones with the top 10 performances obtained with the neural networks, considering the ones with the most balanced classes distribution. Unfortunately, we have a very unbalanced dataset with respect to uncertain relationship. In fact for each user, in average, the amount of pairs labeled with the uncertain relationship is 17.44% of the total. The results proposed concern the use of PCA with indirect and direct approach for ternary classification, which includes the uncertain relationship class. In the indirect approach, we set n to 8 (due to the execution time limitations) and preserve 15 features from the starting 48. Moreover, as another method to decrease dimensionality, we considered meta-class ingredients. In the direct approach, we tested a variable amount of PCs, namely 5, 10, 15 and 20. Finally, the training and test sets are generated by randomly sampling from the recipes in the space of the feature (avoiding same recipes in train and test set) and using them to build the pairs. Training set has 190 pairs, while the test set has 105 pairs, with the labels being generated from the predictions of the Neural Network. The results are proposed in the table 4. The first thing that can be seen is that there is a huge execution time difference between the indirect PCA and other cases. Furthermore, the best performance are obtained with the direct PCA method using the first 10 PCs. To better comprehend this difference, let us consider the results for the third user in the dataset using the indirect PCA method (in Figure 1) and the direct PCA method (in Figure 2). We can clearly see how in the first case (indirect PCA) the execution time grows exponentially as the parameters maxv and maxp grow, while in the second it grows linearly. Note that, in both cases, the dimensionality of the feature space is set to 15. We believe the main reason behind this behavior is that the PCA, from the starting feature space, creates a new orthonormal basis. Thus, when ILASP is trained in the direct PCA case, it has a simpler feature space compared to the starting one, which is used (reduced to 15 feature) in indirect PCA case. Figure 2: Execution time of ILASP when used as global approximator for user 3 with the use of the direct PCA method on a training set of 190 pairs, considering the number of PC = 5, 10, 15 and 20 accuracy precision recall execution time (seconds) Indirect PCA 73.51% 49.19% 47.60% 10855.21 Direct PCA (5PC) 70.44% 41.16% 36.78% 4.03 Direct PCA (10PC) 72.45% 44.12% 39.78% 16.90 Direct PCA (15PC) 74.36% 44.82% 40.54% 26.72 Direct PCA (20PC) 74.87% 46.74% 41.76% 38.90 Table 5 results of ILASP when used directly on the preference dataset with indrect and direct PCA approaches Another point to consider is that the direct PCA method reaches the best performance with the use of the first 10 PC, decreasing with the 15 and 20 PC cases. This could be a sort of early overfitting caused by the fact that both the feature space and the ground-truth are over- simplified by the combined use of direct PCA method and the use of the predictions of the neural network as labels. This is further supported by the results in Table 5, obtained using ILASP directly on the preferences contained in the dataset, labeled with the answers of the users, rather than with the predictions of the neural networks. The last thing that has to be noted, is the difference that accuracy results has over precision and recall results. Beyond the already mentioned unbalanced dataset, we have observed that ILASP is not good to predict the uncertain relationship cases with the proposed approach. Using the cost concept, ILASP classifies a pair (𝑖1 , 𝑖2 ) as 𝑖1 is preferred to 𝑖2 if, at higher penalty level in which the cost of the two element differs, the cost of 𝑖1 is strictly less than the cost of 𝑖2 , regardless of how much big is this difference. The same applies for the case in which 𝑖2 is preferred to 𝑖1 . This, however, doesn’t hold in the case of uncertain, in which the costs of 𝑖1 and 𝑖2 have to be the same in every penalty level, which is statistically less likely to be observed as compared to the other two cases. Thus, starting from a unbalanced dataset, it is harder for ILASP to produce a theory for the uncertain cases compared to the other two preference relationships. 7. Conclusion and future developments In this work, we present the complete workflow we followed to experiment with the use of ILP to explain black-box preference learning system. In this work doesn’t yet test the accessibility of the output given by ILASP for the non-expert user, but this is one point in which we already give some effort and that we will go in deep in future works. First, similarly to [9], we created a food preference dataset based on a survey where par- ticipants ranked Italian recipes. However, our dataset has a much higher dimensionality, and therefore it is a bigger challenge for logic-based learning algorithms. We asked each surveyed user to provide orderings for three (partially overlapping) sets of recipes. The choice of asking users to provide three such orderings was partly due to technical limitations, since our designated tool for surveys – Microsoft Forms – did not allow users to order more than 10 elements for each survey, and partly because we wanted to study the more complicated case of a partial (rather than a total) ordering with inconsistencies and pairwise indifferent items. Then, to disambiguate, we propose an algorithm to get a full (partial) ordering from the three different orderings. In future work, it may be worth investigating how the number and structure of the surveys may affect the proposed approach. We did not just collect user preferences concerning recipes: in order to validate our approach we collected participants’ opinions on some of the features, asking them questions such as “how do you like parmesan cheese?”. In future work we will be able to use this information as a ground truth to compare our learned theories to. We tested the ILASP framework as global approximator of a fully dense NN model, which is one of the most widely used deep learning methods, trained to classify users’ preferences. Because of high execution times, we integrated PCA in the workflow, both with a indirect and direct approach. Our results were encouraging: we were able to achieve higher accuracy (72.09%) and significantly decreased computation time. In fact, we went from an average execution time of about 2 hours to less than 1 minute. In future work, and following [6], we will use ILASP as local approximation of fully dense NNs, and perform similar experiments as those of the global approximation case. Another point we left behind in this work, but need to be investigated, is how to make the direct PCA approach transparent by showing how it is possible to translate those opaque theories into human understandable ones. We also found out that ILASP does not perform well when it comes to uncertain relationships, so we are considering repeating the experiments as a binary classification task, thus discarding uncertain relationships over the dataset. Acknowledgments The author Fabio Aurelio D’Asaro acknowledges the funding and support of PON “Ricerca e Innovazione” 2014-2020 (PON R&I FSE-REACT EU), Azione IV.6 “Contratti di ricerca su tematiche Green” in the context of the project titled “Il miglioramento dell’algorithmic fairness in ambito assicurativo: Un’analisi concettuale a partire da uno studio di caso”. References [1] R. Guidotti, A. Monreale, S. Ruggieri, F. Turini, F. Giannotti, D. Pedreschi, A survey of methods for explaining black box models, ACM computing surveys (CSUR) 51 (2018) 1–42. [2] F. Calimeri, W. Faber, M. Gebser, G. Ianni, R. Kaminski, T. Krennwallner, N. Leone, M. Maratea, F. Ricca, T. Schaub, ASP-Core-2 input language format, Theory and Practice of Logic Programming 20 (2020) 294–309. [3] M. Law, A. Russo, K. Broda, Inductive learning of answer set programs, in: European Workshop on Logics in Artificial Intelligence, Springer, 2014, pp. 311–325. [4] M. Law, A. Russo, K. Broda, Learning weak constraints in answer set programming, Theory and Practice of Logic Programming 15 (2015) 511–525. [5] M. Law, A. Russo, K. Broda, Inductive learning of answer set programs from noisy examples, arXiv preprint arXiv:1808.08441 (2018). [6] F. A. D’Asaro, M. Spezialetti, L. Raggioli, S. Rossi, Towards an inductive logic program- ming approach for explaining black-box preference learning systems, Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning 17 (2020) 855–859. doi:h t t p s : / / d o i . o r g / 1 0 . 2 4 9 6 3 / k r . 2 0 2 0 / 8 8 . [7] A. Caliskan, J. J. Bryson, A. Narayanan, Semantics derived automatically from language corpora contain human-like biases, Science 356 (2017) 183–186. URL: https://science.sciencemag.org/content/356/6334/183. doi:1 0 . 1 1 2 6 / s c i e n c e . a a l 4 2 3 0 . arXiv:https://science.sciencemag.org/content/356/6334/183.full.pdf. [8] P. Schramowski, C. Turan, S. Jentzsch, C. Rothkopf, K. Kersting, The moral choice machine, Frontiers in Artificial Intelligence 3 (2020) 36. URL: https://www.frontiersin.org/article/10. 3389/frai.2020.00036. doi:1 0 . 3 3 8 9 / f r a i . 2 0 2 0 . 0 0 0 3 6 . [9] T. Kamishima, Nantonac collaborative filtering: recommendation based on order responses, in: Proceedings of the ninth ACM SIGKDD international conference on Knowledge dis- covery and data mining, 2003, pp. 583–588. [10] J. Rabold, M. Siebers, U. Schmid, Explaining black-box classifiers with ILP – empow- ering LIME with Aleph to approximate non-linear decisions with relational rules, in: International Conference on Inductive Logic Programming, Springer, 2018, pp. 105–117. [11] J. Rabold, H. Deininger, M. Siebers, U. Schmid, Enriching visual with verbal explanations for relational concepts – combining lime with aleph, in: P. Cellier, K. Driessens (Eds.), Machine Learning and Knowledge Discovery in Databases, Springer, 2020, pp. 180–192. [12] F. Shakerin, G. Gupta, Induction of non-monotonic logic programs to explain boosted tree models using lime, in: Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, 2019, pp. 3052–3059. [13] A. Srinivasan, The Aleph manual, 2004. URL: http://www.cs.ox.ac.uk/activities/ machinelearning/Aleph/. [14] C. Rebelo de Sá, W. Duivesteijn, C. Soares, A. Knobbe, Exceptional preferences mining, in: T. Calders, M. Ceci, D. Malerba (Eds.), Discovery Science, Springer International Publishing, Cham, 2016, pp. 3–18. [15] M. T. Ribeiro, S. Singh, C. Guestrin, “Why should I trust you?”: explaining the predictions of any classifier, in: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’16, Association for Computing Machinery, New York, NY, USA, 2016, p. 1135–1144. URL: https://doi.org/10.1145/2939672.2939778. doi:1 0 . 1 1 4 5 / 2 9 3 9 6 7 2 . 2 9 3 9 7 7 8 . [16] J. Ferreira, M. de Sousa Ribeiro, R. Gonçalves, J. Leite, Looking inside the black-box: Logic- based explanations for neural networks, in: Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, volume 19, 2022, pp. 432–442. [17] J. Fürnkranz, Preference learning, Springer-Verlag Berlin Heidelberg, 2010. [18] M. Gurrieri, X. Siebert, P. Fortemps, S. Greco, R. Słowiński, Advances on Computational Intelligence, 2012, pp. 613–623. [19] Y. Zhou, Y. Liu, J. Yang, X. He, L. Liu, A taxonomy of label ranking algorithms, Journal of Computers 9 (2014) 557–565.