Post-hoc explanation aims at defining a simple local surrogate model to shed light on a prediction produced by a complex, generally black-box, model. In the general context of classification, it has been shown that local surrogates may not be able to always capture a local explanation, i.e. for a specific instance prediction, but rather traduce more of a general behavior of the black-box. This problem is even more complex in a recommendation scenario where classes and decision boundaries are not explicitly defined and where data are very sparse by nature. We show in this paper that it is possible to tackle these problems with an eficient sampling around the recommendation instance to explain, to finally learn a proper local surrogate model. Our experiments show that our method is as accurate or better than the methods of the literature while retrieving more meaningful explainable features locally.
Explainable AI (XAI) [26, 34] aims at understanding the rationale about the factors driving the decision process in complex machine learning models and how their prediction can be altered by changing their input [8]. In this context, post-hoc or model-agnostic explanations have gained some attention in the past years, as they are produced by explanation methods that are agnostic of the internals of the model to explain, and thus need not balance accuracy of the model to explain with the quality of the explanation [26].
The definition of surrogate models is a well-accepted approach
in XAI [14], that builds upon the successful LIME algorithm.
Figure 1 illustrates the main steps of LIME to define simpler,
interpretable models trained to locally mimic the behavior of more
complex, possibly black-box, models [13]. Defining such
surrogate models involves: (
In this paper, we consider the specific case of recommender systems [18], that are notoriously complex prediction systems and for which computing explanation raises new challenges [43].
In this context, we propose to extend recommender systems explanations by reproducing and adapting LIME principles. This task is challenging for two main reasons.
First, because transposing LIME principles to the recommender systems paradigm is not straightforward, as the traditional instances / features data is replaced by a sparse and possibly very large user-item matrix of ratings. In this new context, one needs to redefine what is an instance to explain as the features and class label are not clearly identified, what are the interpretable features, what is a perturbation, and then, when perturbations are generated in the interpretable space, how to project them back to the original space to predict their ratings with the blackbox so as to build a training set? Indeed, determining an out-ofsample prediction for new user-items configurations can be a complex task depending on the nature of the recommendation mechanism.
Second, LIME relies heavily on an estimation of locality around an explanation instance to ensure the quality of its prediction. However, surrogate models as proposed by LIME are not robust, in the sense that they sometimes fail to estimate correctly the explanation model around a specific instance, therefore producing a too general explanation model that accounts for a broader range of input instances [4].
We argue in this paper, that these problems are related to: (
To tackle the aforementioned challenges, we propose a new local surrogate model dedicated to recommender systems, named LIRE - Local and Interpretable Recommendations Explanations that improves over the reference in the literature, the LIME-RS model [29] that is a direct port of LIME, in terms of quality of the explanation by better estimating the locality of an instance to explain, and while still maintaining consistent recommendation fidelity to the original recommender system.
As such our contributions are: the definition of a new representation of a user-item instance to explain, the introduction of a real valued interpretable feature space instead of a binary interpretable space paired with an out-of-sample prediction mechanism to project perturbed instance back to the original space for the specific case of matrix factorization recommender systems. Most importantly, we propose a new definition of locality to better tackle the notion of decision boundary in recommender system decision space by coupling a new gradual perturbation mechanism, with of-the-shelves clustering algorithm and dimensionality reduction techniques such as UMAP [25] so that all users are represented in a low-dimension space where classical metric distance applies efectively. Finally, extensive comparative experiments on the MovieLens benchmark show that our new local surrogate approach is comparable in terms of prediction accuracy if not better than LIME-RS, while proposing more relevant set of interpretable features as explanations.
This paper is organized as follows: Section 2 presents the problem formulation and Section 3 details our main contributions. Section 4 presents our experiments and Section 5 presents a discussion about the problematic in the field of explainable AI before Section 6 concludes and opens future works. 2
In what follows, we consider a (black-box) recommendation system as a function : × → R+ where is the set of users, is the set of items and R+ is the definition domain of the ratings. 2.1
We call an explanation instance the 3-tuple ⟨, , (, )⟩ where ∈ , ∈ and (, ) ∈ R+ denotes a prediction that we want to explain and produced by the (black-box) recommender system for the user and item . Importantly, our objective is not to explain the process by which the black-box recommender system works, but instead to highlight the main interpretable features that explain a specific prediction (, ).
In [29, 33], interpretable feature relates to feature names that represent directly understandable and actionable pieces of domain knowledge. The representation of an (explanation) instance in the interpretable space is thus a set of interpretable feature names, technically represented by a binary feature name vector.
In our work, we denote by interpretable features the set of items names = {1, . . . , }, each associated with a domain of value (1), . . . , () = R. We call a feature vector over + a n-tuple of values = ⟨1, . . . , ⟩ where ∈ R. Equivalently, + and whenever this is convenient, we view the tuple as a function of signature → ∪ ( ), denoting ( ) the value and |′ the restriction of to the subset ′ ⊆ . Consequently, ( ) = |{ } .
Following the previous notation, for an explanation instance ⟨, , (, )⟩, the list of interpretable features is formalized as the tuple , i.e. the restriction of to the subset of items |∪≠ { } ≠ ∈ for a specific user ∈ . Noticeably, and contrary to previous works, this representation of an explanation instance is not binary but associates a real value to each feature name (in fact, the score of the item for this user ). This allows to express more complex perturbation mechanisms as presented in Section 3 and to better preserve locality as shown in experiments in Section 4.
Finally, in our case, and similarly to [29, 33], an explanation is a set of interpretable feature names, technically represented by a real-valued feature name vector, where each interpretable feature name is associated with a real weight representing the importance of the feature for the explanation instance. 2.2
lows: Traditionally, explaining a recommendation boils down to determining the top- [29] or minimal [33] subset of interpretable features that maximizes the fidelity of the surrogate model to the original model. As in [33], we restrict our work to the class of linear explanation models (z) = w · z, where z denotes the vector of values attached to the set of interpretable features.
Consider that tu is the vector of values attached to interpretable
features of user to explain instance ⟨, , (, )⟩, constructed
from . The explanation model (, ) is defined as
fol|∪≠ { }
(, ) = argminw∈R L ( (, ), w · tu) + Ω(w)
(
As a conclusion, our problem reduces to determining the most appropriate interpretable features weights vector ∈ R. Our hypothesis in this paper is that it is possible to improve the quality and the relevance of by introducing locality in the sampling process to generate the training set to learn . 3
As mentioned in the previous sections, our proposal is to
introduce locality during the sampling of instances to train our
linear surrogate model following two complementary directions:
(
This first two objectives raise secondary questions.
Noticeably, (
3.1.1 Perturbation of user instance. Given our definition of explanation instance and its representation as a real valued vector attached to feature names (see Section 2), we define perturbations as a random modification of the values of tuple |∪≠ based on some Gaussian distribution N (0, ). The value of for each item ≠ ∈ is computed as the average observed deviation of all ratings in the training sample.
Then, we model as a Bernoulli process of probability the chance to modify each element of . For simplicity sake, |∪≠ as in the context of an we will note interchangeably
|∪≠ explanation instance ⟨, , (, )⟩ and in this case, will denote a perturbation of .
3.1.2 Out-Of-Sample prediction. In terms of LIME methodology, Out-Of-Sample prediction plays the role of the surjective function −1 between interpretable feature space and original space as well, as the prediction (−1 (′)) attached to this new instance ′ (following notations in Equation 10). The role of this function is, given an interpretable feature description of a perturbed user , to find a representation in the original space for this perturbation, and most importantly, as this user is totally new to the recommender system, to predict his/her rating for the item ∈ .
In our proposal, where we generate never-seen-before useritems signatures, determining a prediction for these new instances can be challenging. Indeed, the dificulty to implement such OOS procedure depends heavily on the recommender system: in case of k-nearest neighbor or baseline approach, it is trivial to implement a recommendation for a new user. The same holds for deep embedded recommender systems [41] which, by design, can produce prediction for any new input. In our work as in [29] however, we consider the special case of Singular Value Decomposition recommender system [5, 32], a Matrix factorization method that expresses the user-item matrix:
R = WΣVt with R a × real valued user-item matrix, and where Σ can be reduced to a diagonal matrix Σkk of size × ( < and < ) containing only the largest singular values of R. In this context, the ratings for an out-of-sample user are determined as follows:
R(, .) = rvΣ where rv represents the 1 × vector representing user in user latent space. In this context, producing an OOS prediction accounts for determining the latent representation rv for OOS user .
To this aim, we formulate the search of latent representation
rv as a least square optimization of the residual sum of square
(RSS) defined as:
= ( − rvΣ ) ( − rvΣ )
(
Finally, the ground truth rating for item ∈ is obtained by re-injecting the optimal rv into Equation 3. 3.2
Ideally, our locality definition should also be coherent with existing decision boundaries. In the context of recommender systems, such decision boundaries are not explicit. Our contribution concerns the determination of such explicit decision boundaries via the definition of natural neighborhood for each explanation instance. In our context, determining the neighborhood reduces to a clustering problem of the tuples = { } ∈ . We mean by “natural”, a grouping of tuples such that a traditional clustering quality criterion is met, for example minimizing the intra-cluster variance as in k-means clustering [16, 24] or ensuring that there exists a transitive density relation between connected neighbors as in DBSCAN algorithm [10, 35].
However, following our previous definitions of an explanation instance, an input ∈ representing a user in an interpretable feature space can still have several thousands of features as in our case, this relates to the set of items. This makes clustering useless because of the loss in discrimination attached to the metric used to perform the clustering, what is known as curse of dimensionality.
Several solutions exist in the literature to solve this dimensionality problem. The first solution is to perform a feature selection or weighting process on the instances in prior to the clustering. This research domain has been extensively studied in the past years as attested by numerous publications [3, 6, 20, 22]. The dificulty lies in the definition of an objective to drive the feature selection process (as, contrary to supervised classification, there is no ground truth). An other solution would be to deifne clusters and their respective set of features at the same time with subspace clustering methods [2, 19, 30]. However, these approaches are generally complex and will not scale with the size of datasets in the recommender systems world.
Moreover, as our final objective is not to build a clustering per se, but to build neighborhoods as clusters from which we estimate a local explanation, we do not want to remove beforehand any information that could explain a local behavior.
For these reasons, we consider in this paper dimensionality reduction techniques such as t-SNE [40] or the more recent UMAP [25]. UMAP builds a relationship graph in high dimensionality by growing around each instance a radius that denotes the strength of the relationship with neighbors. Similar to t-SNE this high dimensional graph is then reproduced in a lower dimension space. Interestingly, UMAP provides parameters to balance the importance of respecting the local relationship versus the global structure of a data set.
In this paper, we use UMAP in conjunction with a k-means clustering. Sensitivity of our approach to these choices is not reported here for the sake of readability and, as illustrated in experiments in Section 4, will need further discussions that are left as future work. 3.3
Previous sections details how locality is introduced in the sampling of instances to build a proper training set for our surrogate model. We now present the diferent variants of our approach LIRE depending on how the training set is constructed from perturbed points and cluster neighbors. Finally, the last subsection describes how the linear weights ∈ R of our local surrogate model are learned.
3.3.1 Building the training set for the surrogate model. In our proposal we consider three diferent scenarios to define the training set of the explanation instance , each one related to a locality definition.
First, in the LIRE-C approach, we consider randomly picked users from the same cluster as the user for which the explanation is to be computed. These neighbors represents observed examples of users in the close vicinity of . Their rating for the item ∈ can be estimated by the black-box directly, that serves as ground truth. This approach is expected to be faster as there is no Out-Of-Sample prediction involved. If the cluster is smaller than the number of training instances, instances are duplicated.
Second, we consider in the LIRE-P approach only perturbations as presented in the previous Section 3.1.1 following the LIME principles. This approach is supposedly the most accurate as it allows to generate numerous training examples in the close vicinity of an explanation instance and by modifying gradually the importance of each interpretable feature.
Finally, the last approach LIRE-M considers a mixed situation where half training instances originates from perturbations and the other half is generated from the cluster neighbors.
3.3.2 Explanation as a weighted regression with L1 regularization. In our context, learning the best explanation amounts to determining the weights of the most appropriate interpretable features. We formalize this problem as a simple regression problem between a training set T of instances expressed on interpretable features composed of either perturbations or cluster neighbors of user and their respective predictions Y either obtained by direct prediction of the black-box or by our OOS prediction. We further want to achieve the simplest explanation by only retaining the most interesting features.
To do so, we consider a LASSO regression model [38]
introducing a penalty term ∥w∥1 similar to Ω(w) in Equation 1. In
the end, our explanation can be optimized following:
dif = Y − wT
(, ) = argminw∈R {dif · dif + ∥w∥1}
(
This section describes the experiments conducted to assess the
interest of our approach and the way it deals with locality to
provide explanations. To do so, we have set up several experiments
reported hereafter that aims more specifically at answering the
following questions:
(
Datasets. Two well-known datasets from the movie recommendation service MovieLens have been used. Each describes 5-star rating and free-text tagging activity from MovieLens. We limit our main tests to the 100 MovieLens dataset [15] with 610 users and 9.724 items, as answering our research questions involves multiple runs with diferent parameters that would be too time consuming on larger datasets. Then, a first evaluation on the MovieLens 20M entries dataset is provided as a testimonial that our approach can scale to larger volume of data. This dataset contains 20.000.263 ratings generated by 138.493 users for 27.278 movies.
Black-boxes. we consider 2 diferent types of black-boxes
algorithms. Similar to [29] we first implement a simple matrix
factorization method. The interest of such approach lies in its ability
to produce meaningful recommendation from a latent space of
users and items even in the context of very sparse data. The
dififculty for post-hoc explanation approaches such as LIME [ 33],
that relies on perturbed points to train a surrogate model, is
that it is not trivial to produce an Out-Of-Sample (OOS)
prediction for these perturbed instances. In our contribution, and
contrary to previous works that avoid this situation by
considering only pre-existing user-items recommendations as training,
we propose a proper method to perform the OOS prediction as
introduced in Section 3.1.2. The second "black-box" is the
linear white-box that we use to determine the quality of our
explanation (see research questions (
Evaluation metrics. We consider several evaluation metrics to assess the quality of our post-hoc explanation approach: • the accuracy to the black-box model is classically computed as a Mean Absolute Error (MAE) between the prediction of the black-box and the prediction of the surrogate model in the interpretable space; • the computation time is estimated in seconds for one run of an approach. Here we only measure the computation time of our LIRE approach to observe the impact of OOS prediction computation versus clustering; • the relevance of our interpretable model is expressed as the ratio of features from the white-box model that are discovered by (i.e. features whose weights exceed 0 in the model ). Let F be the set of features of a model, this ratio can be expressed as follows: ( , ) = F ( ) ∩ F ()
F ( ) (7) • the feature ranking quality is more discriminant than the previous relevance metric since it takes into account the rank of the relevant features and not only their presence / absence in the set of retrieved features. Ranks of interpretable features are provided by their weights, either set randomly in the white-box model, or learned by the surrogate model. To measure the quality of the agreement between the expected and the learned ranking, we use the traditional Normalized Discounted Cumulative Gain (NDCG) measure at rank (NDCG@) for values of ∈ {3, 5, 10}. 4.2
This section reports our comparative experiments between LIMERS and our three approaches LIRE-P (only perturbed training instance), LIRE-C (only cluster training instance), LIRE-M (mixed training instances) when explaining recommendations instances from a matrix factorization black-box model.
Protocol. For each method, we report evaluation metrics averaged over 50 explanation instances ⟨, , (, )⟩. In the random scenario, these instances are generated by picking at random a user and an item from the Movie Lens 100K dataset and by predicting the rating for ⟨, ⟩ based on the black-box function . In the top and flop scenarios, only the user is picked at random, then the black-box is used to determine items with the highest and lowest scores for user and their respective scores as ground truth. Following the parameters of LIME-RS, the training set size of the surrogate for each explanation instance is set to 1000. In LIRE-P, 1000 perturbed points are generated with a probability = 0.1 in the Bernouilli process with a perturbation range following the estimated overall variance set to 1.04 on the nonzero ratings. In LIRE-C, 1000 neighbors from the same cluster are considered. This is a huge constraint in our clustering model since this size of training set may not allow for a finer clustering algorithm that captures small tendencies in the dataset. As a compromise, in case the cluster is too small, we propose to replicate its data, which allows to use a k-means clustering algorithm set with 75 clusters to preserve small clusters and locality. Clustering is applied on top of a UMAP dimensionality reduction as implemented in Python umap package with 30 neighbors and a minimum projection distance of 0.01. The linear regression is based on LARS implementation and uses default parameters as presented in its sklearn version. All code is written in Python and is available as a Git project 1. All tests on MovieLens 100K were run on a laptop with an Intel Core i7 CPU at 2.50GHz and 8 GB of RAM.
Out-Of-Sample Prediction. The OOS predictors run for 120 epochs of gradient descent using the optim package of pytorch. More specifically, within this package we use the Adagrad optimiser using its defaults parameters, exception made of the learning rate set to 0.1.
Comparative accuracy. Table 1 presents the results of our first comparative study based on MAE accuracy measure between the black-box and our surrogate models. In order to assess our results validity, significance t-tests have been conducted. It can be observed that on the Random scenario, LIME-RS, LIRE-P and LIRE-M have comparable results (p-value of 0.41 > 0.05 between LIME-RS and LIRE-P for example), and all 3 approaches manage to estimate correctly the prediction of the black-box. Interestingly, standard deviation values are very high which shows that, even if for most of the cases the accuracy is very good (MAE close to 0), there still exists some cases that should be investigated in the future, where the methods fail to estimate correctly. This is the case with LIRE-C that relies exclusively on cluster neighbors to train the surrogate model and that is less accurate. This is certainly due to the inadequacy of discovered clusters to represent correctly the locality either being to small and too local or being too large and thus providing a surrogate model that is too general. We leave as future work an in-depth study of the most eficient clustering for sampling. Interestingly though, mixing perturbed instances and clusters do not deteriorate the results.
In the T op scenario, diferences are significant between LIREP and LIME-RS (p-value = 8 ∗ 10−5), and between LIRE-M and LIME-RS (p-value = 0.02) which shows that our approach is more eficient when dealing with the best scored items, i.e. those that will be preferentially presented to the user. This is mainly due to the internal behavior of LIME-RS that builds the "locality" around an instance by mostly exchanging items to be scored. As a consequence, training instances will most likely consider lower scored items and in turns will not be able to capture accurately the behavior for the top instances. On the contrary, our perturbed instances paired with our OOS prediction allows for a smoother estimation of the model around the top instances. Interestingly, our approaches do not perform as well as in the Random scenario, as it is more dificult to build a representative training set: in the case of LIRE-P, perturbations are limited to the 0 to 5 range of ratings and in the case of LIRE-C, top scores may not have many neighbors to compare with, because of the generally Zipfian distribution of ratings. The same conclusion applies in the following Flop scenario.
Finally, in the Flop scenario, similar to what is observed for the Random scenario, there is no significant diference between the results (p-value = 0.10 > 0.05 when comparing LIRE-P and LIMERS for example). Interestingly, when mixing perturbed points
27.00 ± 1.98 0.57 ± 0.08 12.85 ± 2.08 1.60 ± 0.36 and cluster neighbors it seems to improve on our sample test the performances of LIRE (not significantly though).
Computation times. During all the experiments, we have also monitored the computation times of the diferent variants of LIRE as reported in Table 2. Only Random scenario is reported as the other scenarios are exactly as intensive in terms of computation. Noticeably, LIRE-C based on cluster neighbors is the fastest approach and LIRE-P is the slowest of the batch. This was expected since LIRE-C does not require the computation of the OOS prediction in LIRE-P. The latter is very costly when considering matrix factorization black-box. Interestingly, LIREM provides a good speed-up over LIRE-P without degrading the accuracy in Top and Flop scenarios. Future work should investigate more this results as a LIRE-P with only 500 training instances may have the same performance and the same computation time as LIRE-M depending on the quality of the clustering used to define the neighborhood. Noticeably, our clustering may not be as eficient as expected because in many real world situations, the size of clusters follows a Zipf law with one very large cluster and many very small clusters. As a consequence, we set up our clustering parameters so as to perform a compromise between the ability to capture small trends in the data as well as more general tendencies. In the case where a cluster is too small to contain 1000 points to produce an equivalent training sample as the other approaches, we use an oversampling technique that may bias the convergence of the surrogate model, hence the performance. We leave these research questions as future work. 4.3
Table 3 contains for each method the evaluation of its ability to identify correctly the interpretable features used to generate the white-box model. Relevance does not consider the relative importance of each interpretable feature while NDCG score takes into account the ranking of the most important interpretable features of the white-box model.
This is a very dificult test as it boils down to identifying 10 features out of 9724. These features may be correlated and so in this case our surrogate has to determine which one of the correlated features to pick to explain the general behavior of the white-box. Finally, the dificulty of the task is also related to the number of items that were scored by the user for which the explanation is produced. Indeed, even when limiting the exploration of interpretable features to the set of scored items, this resolves to a possibly large search space: on average each user of the dataset scored around 614 ± 642 items. This shows that the search space may be very small or very large depending on the selected user.
First, it is interesting to notice that in this experiment, LIMERS is not able to identify any correct interpretable feature from the set of 9724 candidates. This is due to the internal behaviour of the approach as we use in this experiment the “item mode” from the original code that is emphasized in the original paper [29]. In this mode, the sampling to train the surrogate model only varies, for a specific fixed user, the items that are considered. As a consequence, because of the nature of the white-box that is a linear combination of fixed items, the output for all training instances is the same. As a consequence, LIME-RS has no real information to decide from all features locally and tries to minimize the prediction error but on the basis of uninteresting features that are certainly correlated to some extent to the one used in the white-box (hence the good accuracy score).
Second, the baseline random approach chooses from the set of scored items for the user. This constraints greatly helps to find more easily some relevant features (but otherwise this baseline would have been pointless since it would have had 10 chances out of 9724 to find a correct feature), but does not favor the discovery of a proper ranking of the important interpretable features as illustrated by the very low NDCG scores.
Finally, LIRE in general, and more specifically LIRE-P manages to better embrace the local behavior of the white-box and identify a ratio of 0.212 features over which its model is constructed. This is clearly due to the perturbation mechanism that will slightly afect the scores of items to explore the neighborhood of an explanation instance gradually and thus can better evaluate the relative importance and correlation between features. 4.4
The double white-box experiment aims at showing to which extent each surrogate model learns locally the black-box model and to which extent it performs well doing so, based on the previous quality measure of an explanation (see Section 4.3). For each explanation instance generated randomly, we define a decision threshold that is set as the distance to the ℎ nearest neighbors or as the distance to the farthest point in the same cluster, if there are less than instances in the cluster.
Table 4 presents the results obtained when comparing all the methods based on an adapted relevance metric: “Relevance In” indicates the ratio of features from the first model (the one applied inside the neighborhood delimited by the decision threshold) that are identified by the surrogate model, while “Relevance Out” designates the ratio of features from the out-of-neighborhood model. A surrogate model that better approximate a local behavior is likely to have a better “Relevance In” score.
First, it can be seen in Table 4 that LIRE-P approach performs the best for the “Relevance In” score with 0.328, followed by LIRE-M and the random baseline. This shows that LIRE-P is the most efective locally to capture the important features of the inneighborhood white-box model. This is due to its gradual perturbation mechanism that stays in the vicinity of the explanation instance, contrary to the binary perturbation of LIME-RS that does not guarantee that a perturbed instance stays in a close neighborhood. Second, concerning LIRE-M and LIRE-P, it can be observed that adding training instances from the cluster decreases the quality of the explanation. Indeed, LIRE-C has very poor results which tend to show that clusters are generally much larger than the radius defined by the decision threshold and that, in this case, training instances are often labelled by the out-ofneighborhood white-box model prediction. Finally, LIME-RS obtains very poor results with 0.036 in “Relevance In”. In fact, this is due to the setting of the approach for this test, where we have changed the item mode of the previous test (that would not have performed correctly for the same reasons as previously, see Section 4.3) to the user-item mode, present in the original code from [29] but not detailed much in the paper. In this mode, training set is constructed by picking at random (user, item) pairs and their associated black-box predictions, which, as the locality is by definition smaller than the whole explanation instances space, leads to favor the out-of-neighborhood white-box to label its predictions. However, even in the case of the “Relevance Out” score, LIME-RS does not perform well because of the binary perturbation that does not ensure locality correctly. NDCG scores conifrm that LIRE-P also manages to discover more of the main features coming from one or the other white-box model and better respects their ranking with a good score of 0.355 for NDCG@3. 4.5
Table 5 finally reports the comparative results of our 3 methods on the larger 20M entries dataset proposed by MovieLens. All tests were conducted on a AMD Ryzen 3700X with 32 GB of memory, and as such, computation times with previous experiments cannot be compared, but are on the same order of magnitude. First, it should be observed that our approach runs on 20M entries while the code provided for LIME-RS [29] is not able to run on the full dataset. Second, it can be seen that LIRE-M has better results compared to the test on MovieLens 100K and has similar performances in terms of MAE than LIRE-P. Indeed, differences are not significant when considering a bilateral t-test with a p-value equals to 0.18. This is interesting as it may indicate that in this very large dataset scenario, the clustering could help improving the results of the perturbation mechanism. This should be investigated more in future work. However, the cluster neighbors only training set is too dependent on the quality of the clustering algorithm to be eficient on average as shown with LIRE-C results. Finally, and similarly to our experiments on MovieLens 100K, LIRE-C is the fastest approach as it does not involve the OOS prediction mechanism. 5
Explainable recommendations refers to personalized recommendation algorithms that not only provide the user with recommendations, but also make the user aware why such items are recommended [42]. Gedikli et al. [12] evaluate diferent explanation types and propose a set of guidelines for designing and selecting suitable explanations for recommender systems. Indeed, state-of-the-art recommender systems [18] are notoriously complex prediction systems for which computing explanation raises new challenges [43]. Model-intrinsic explanations correspond to recommender systems whose decision process is simple enough to be clear for the users or that embed mechanisms to provide users with an explanation [1]. However as pointed out in [23], this kind of explanations sufer from a trade-of between transparency and accuracy of the model. Indeed, adding internal mechanisms to explain a process or a result may slow down this process or bias this result as the sole focus of the recommender system is no more the accuracy of item scores prediction but to produce a justification for these scores as well.
Methods
LIME-RS Baseline Random
Lire-P Lire-M Lire-C
On the contrary post-hoc or model-agnostic explanations do not require to access or to adapt the internals of the recommender system and thus do not decrease their accuracy [26].
Many of those post-hoc approaches have been proposed such as [31] for Matrix Factorization or similar approaches that relies on the elicitation of latent factors to perform recommendation [11, 31, 37, 44]. The inherent dificulty facing these methods is to determine an eficient way to relate the latent model to explicit interpretable features that make sense for the user. [37] integrate regression trees to guide the learning and further explain latent space while [11] introduce a framework based on deep multi-view learning to model an explanation as multi-level features template. Finally, [44] propose an Explicit Factor Model that builds an alignment between interpretable features and the latent space while [31] search for association rules expressed on features. All these explanation approaches however are tightly related to only one specific recommendation system. More recently, [39] introduces GLIDER, a system that provides an interpretation for any black-box recommender system based on features interactions rather than features significance as in the original LIME algorithm. In our work, we are interested in model agnostic local explanations as provided by LIME, in other words, models that can provide explanations as a set of feature weights, for any recommender system, given an input instance.
In this respect, the LIME-RS approach [29] provides a model agnostic explanation system, that can be applied on any blackbox recommender system and that outputs a set of interpretable features and their relative importance. LIME-RS builds upon the well-known LIME approach [33] to explain recommendation by retrieving the top-n binary interpretable features as computed by LIME.
An explanation produced by LIME for an input instance ∈ X, and a prediction model is as follows [33] ( ) = argmin∈ L ( , , ) + Ω() (8) where L is a fidelity function to the original (black-box) model and ∈ is one explanation model among all possible explainable models . The most common explanation model is a linear prediction model and in this case an explanation corresponds to the weights of the most significant interpretable features whose combination minimize the deviation to the black-box model. Interestingly, is a locality measure around instance ∈ X and is introduced to balance the perturbations introduced in the training set. Finally, Ω() measures the complexity of explanation model . LIME assumes (i) an interpretable feature space Z to learn a surrogate model of and (ii) at least a surjective function from X to Z.
The fidelity function L is expressed as a quadratic error between the predictions ( ′), for instances ′ ∈ X and the surrogate prediction (′) for their interpretable counterparts ′ ∈ Z: ∑ ′ ∈X,′ ∈Z L ( , , ) = ( ′) ( ( ′) − (′))2 (9) where the locality measure = (− (, ′)2/2) crucially weighs the importance of training instances ′ based on their distance (, ′) with instance . This locality importance is better illustrated when reformulating Equation 9 with the surjective function : X → Z, where −1 is to be determined and relates the generated perturbed instances ′ ∈ Z to their L ( , , , ) = antecedent ′ ∈ X as follows: ∑
( (−1 (′)) (−1 (′)) − (′) )2 (10) ′ ∈Z Equation 10 clearly shows that, as −1 does not guarantee that neighbors in Z are still neighbors in the antecedent space X, we need a mechanism to counterweight these uninteresting training samples. Earlier works [29, 33] consider binary explanation spaces, and perturbations are uniform random changes in the binary signature of the explanations. As noted before, a binary change may have a drastic impact on potential expression of the antecedents in X, which, again, exemplifies the role of in LIME-like systems. For this reason, we discuss in this paper new ways to deal with locality around and explanation instance by introducing a more gradual interpretable space and perturbation mechanism as well as a strict locality as defined by an adapted clustering algorithm.
Further properties are discussed to create its own LIME explanation algorithm in [36]. Noticeably, [36] discusses one of the key hypothesis of LIME that consists in knowing by advance the relationship between the interpretable space and original space and indicates that, whenever possible, bijective functions should be considered to limit errors when projecting from the interpretable space to the original one. This hypothesis is very strong and explains the simplifying choices that are made by [29] not to perturb instances outside already existing instances, to avoid the definition of a proper Out-Of-Sample (OOS) process that we implement in this paper. Tightly related to this problem of OOS prediction is the ability of the explanation instance representation chosen in LIME-RS to efectively capture locality via the perturbation mechanism. Indeed, one drawback of LIME-like approaches is that they sometimes fail to estimate a proper local surrogate model [21] and rather produce a model not solely focused on the explanation instance but influenced by more general trends in the data as well.
In our proposal, we want to achieve the same flexibility as
LIME-RS by extending the principle of LIME algorithm [33] and
to circumvent the locality problem with the introduction of two
mechanisms: (
Our paper also raises the question of the evaluation of an explanation, as reflected by the experiments and metrics that we use. This question has been raised in [7] where they define a continuum of evaluation methods from “Function-based” that relies on benchmarks and formalized evaluation metrics with low validity and cost of explanation, to “Cognition-based” where the objective is to quantify the driving factors of features that are related to the task and finally to “Application-based” that relies on experts from the domain to evaluate in a real-use case the validity of an explanation that have high validity and cost.
In [27], the authors are interested in the type of explanations that humans are able to understand and define a set of userstudies to evaluate the cost for human to understand the rationale of an explanation based on input, output of prediction model and its explanation.
In our tests, we focus on accuracy of the surrogate model (fidelity to the black-box) and relevance of the interpretable features. Other quantitative quality measures have been proposed in the literature. For example, [29] describes a fidelity measure that does not rely on an absolute rating prediction error, but rather on diferences in top-k item ratings between the blackbox and its surrogate model. In this paper we also compare rankings but focus on interpretable features which is more local to an explanation instance and more related to the quality and interpretability of the explanation while [29] focus on the ability of the surrogate model to mimic the black-box behavior.
Several other quantitative metrics for explanation evaluation could be considered in the context of recommender systems. Noticeably, the robustness of an explanation following the principle of locally Lipschitz continuity in the classification context seems to be a promising idea [4] that we plan to adapt to the recommendation context in the near future.
Finally, in [26] the author describes several properties of an explanation and what would make an explanation human-friendly. These concepts and ideas should be borrowed and adapted to the context of recommender systems. 6
This paper introduces new implementations of locality in
posthoc explanation approach for recommender systems. Our two
main contributions are: (
Stud. 72, 4 (2014), 367–382. [13] Guidotti, R., Monreale, A., Ruggieri, S., Turini, F., Giannotti, F., and Pedreschi, D. A survey of methods for explaining black box models. ACM Comput. Surv. 51, 5 (2019), 93:1–93:42. [14] Hara, S., and Hayashi, K. Making tree ensembles interpretable: A bayesian model selection approach. In International Conference on Artificial Intelligence and Statistics, AISTATS 2018, 9-11 April 2018, Playa Blanca, Lanzarote, Canary Islands, Spain (2018), pp. 77–85. [15] Harper, F. M., and Konstan, J. A. The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst. 5, 4 (Dec. 2015). [16] Jain, A. K. Data clustering: 50 years beyond k-means. Pattern Recognit. Lett.
31, 8 (2010), 651–666. [17] Järvelin, K., and Kekäläinen, J. Cumulated gain-based evaluation of IR techniques. ACM Trans. Inf. Syst. 20, 4 (2002), 422–446. [18] Koren, Y., Bell, R. M., and Volinsky, C. Matrix factorization techniques for recommender systems. IEEE Computer 42, 8 (2009), 30–37. [19] Kriegel, H.-P., and Zimek, A. Subspace clustering, ensemble clustering, alternative clustering, multiview clustering: what can we learn from each other.
In Proc. ACM SIGKDD Workshop MultiClust (2010). [20] Kumar, V., and Minz, S. Feature selection: A literature review. Smart CR 4, 3 (2014), 211–229. [21] Laugel, T., Renard, X., Lesot, M., Marsala, C., and Detyniecki, M. Defining locality for surrogates in post-hoc interpretablity. CoRR abs/1806.07498 (2018). [22] Li, Y., Dong, M., and Hua, J. Localized feature selection for clustering. Pattern
Recognition Letters 29, 1 (2008), 10–18. [23] Lipton, Z. C. The mythos of model interpretability. Commun. ACM 61, 10 (2018), 36–43. [24] MacQueen, J. B. Some methods for classification and analysis of multivariate observations. In Proc. of the fifth Berkeley Symposium on Mathematical Statistics and Probability (1967), L. M. L. Cam and J. Neyman, Eds., vol. 1, University of California Press, pp. 281–297. [25] McInnes, L., and Healy, J. UMAP: uniform manifold approximation and projection for dimension reduction. CoRR abs/1802.03426 (2018). [26] Molnar, C. Interpretable Machine Learning. 2019. https://christophm.github.
io/interpretable-ml-book/. [27] Narayanan, M., Chen, E., He, J., Kim, B., Gershman, S., and Doshi-Velez, F. How do humans understand explanations from machine learning systems? an evaluation of the human-interpretability of explanation. CoRR abs/1802.00682 (2018). [28] Nguyen, P., Dines, J., and Krasnodebski, J. A multi-objective learning to re-rank approach to optimize online marketplaces for multiple stakeholders.
CoRR abs/1708.00651 (2017). [29] Nóbrega, C., and Marinho, L. B. Towards explaining recommendations through local surrogate models. In Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing, SAC 2019, Limassol, Cyprus, April 8-12, 2019 (2019), pp. 1671–1678. [30] Parsons, L., Haqe, E., and Liu, H. Subspace clustering for high dimensional data: A review. SIGKDD Explor. Newsl. 6, 1 (June 2004), 90–105. [31] Peake, G., and Wang, J. Explanation mining: Post hoc interpretability of latent factor models for recommendation systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018 (2018), pp. 2060–2069. [32] Rendle, S. Factorization machines. In ICDM 2010, The 10th IEEE International Conference on Data Mining, Sydney, Australia, 14-17 December 2010 (2010), pp. 995–1000. [33] Ribeiro, M. T., Singh, S., and Guestrin, C. 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 (New York, NY, USA, 2016), KDD 16, Association for Computing Machinery, p. 11351144. [34] Samek, W., Montavon, G., Vedaldi, A., Hansen, L. K., and Müller, K.R. Explainable AI: interpreting, explaining and visualizing deep learning, vol. 11700. Springer Nature, 2019. [35] Schubert, E., Sander, J., Ester, M., Kriegel, H., and Xu, X. DBSCAN revisited, revisited: Why and how you should (still) use DBSCAN. ACM Trans.