Andriy Nikolov
email: andriy.nikolov@insight-centre.org

Mathieu D'aquin
email: mathieu.daquin@insight-centre.org

Uncovering Semantic Bias in Neural Network Models Using a Knowledge Graph

Keywords: Computing methodologies → Neural networks, Rule learning, Natural language processing, • Information systems → neural networks, explanation, knowledge graphs, rule mining

While neural networks models have shown impressive performance in many NLP tasks, lack of interpretability is often seen as a disadvantage. Individual relevance scores assigned by post-hoc explanation methods are not sufficient to show deeper systematic preferences and potential biases of the model that apply consistently across examples. In this paper we apply rule mining using knowledge graphs in combination with neural network explanation methods to uncover such systematic preferences of trained neural models and capture them in the form of conjunctive rules. We test our approach in the context of text classification tasks and show that such rules are able to explain a substantial part of the model behaviour as well as indicate potential causes of misclassifications when the model is applied outside of the initial training context.

INTRODUCTION

Recent years have seen rapid advances in research on neural machine learning models and their application to different NLP tasks. However, although demonstrating impressive gains in accuracy, intransparency of these models remains a disadvantage [START_REF] Samek | Explainable Artificial Intelligence: Understanding, Visualizing and Interpreting Deep Learning Models[END_REF]: it is not always clear what caused the model to make a decision. A common problem is a "Clever Hans"-type behaviour [START_REF] Lapuschkin | Unmasking Clever Hans predictors and assessing what machines really learn[END_REF], when the model "cheats" by exploiting shortcut correlations in the training data, * Author currently works at AstraZeneca, UK (email: andriy.nikolov@astrazeneca.com).

which results in high reported accuracy during training, but can lead to problems when deployed in the real world. For example, a publicly available LSTM network [START_REF] Rao | Actionable and Political Text Classification using Word Embeddings and LSTM[END_REF] was trained to classify tweets by political leaning (pro-democrat vs pro-republican) and achieved about 90% performance on the test dataset. However, when trying this model with two examples having opposite meaning "I hate @realDonaldTrump" and "I love @realDonaldTrump", the model classifies them both as pro-republican with very high confidence (0.994 and 0.991 respectively): i.e., it relies on who is referenced in a tweet rather than what the tweet actually says.

Existing generic neural network explanation methods such as [START_REF] Arras | Explaining Recurrent Neural Network Predictions in Sentiment Analysis[END_REF][START_REF] Shrikumar | Learning Important Features Through Propagating Activation Differences[END_REF], and [START_REF] Scott | A Unified Approach to Interpreting Model Predictions[END_REF] are focusing on post-hoc interpretability [START_REF] Lipton | The Mythos of Model Interpretability[END_REF], i.e., explaining the reasons for the model's decision on a single example by assigning different relevance scores to atomic tokens in the input text. Such explanations, however, are not sufficient to verify the whole model or to give clues about directions of improvement. To achieve model interpretability, we need to (a) make transparent systematic preferences of the model and possible spurious biases, which apply consistently across many cases, as well as (b) express these preferences in a human-understandable form.

A neural NLP model is able to take into account different kinds of textual features: from low-level syntactic patterns, stylistic elements, and sentiment to the actual factual information expressed about the domain. In this paper we focus on the latter and aim at capturing semantic preferences of the model dealing with domain knowledge. Our paper therefore makes the following contributions:

• We propose a novel method for discovering semantic preferences of neural text processing models. The method combines decision explanation using relevance scores with association rule mining over the knowledge graph to capture explanation rules stating which categories of domain entities are likely to shift the model decision in a certain way. • We report evaluation experiments with our method on four test scenarios demonstrating that (a) mined rules are able to explain model decisions to a large extent and (b) preferences they capture are generic and hold when the model is applied outside of the original training context. The rest of this paper is structured as follows. Section 2 presents a motivational example and briefly outlines the steps of our approach. In section 3, we provide an overview of existing solutions for deep learning explanation methods as well as rule mining approaches. Section 4 describes the process of extracting influential features from a set of input examples and linking them to knowledge graph entities. Section 5 focuses on mining the rules from selected entities. Section 6 describes the evaluation experiments. Finally, section 7 concludes the paper and discusses directions for future work.

MOTIVATION

Let us consider a convolutional network for binary text classification that takes a short biography of a painter and predicts whether his/her paintings are likely to be present in a major European art museum, such as Louvre, Prado, or Uffizi. When we give this model the following snapshot of Titian's biography, it gets misclassified, i.e. the model gives a confidence of only 0.24, which corresponds to the answer "No".

Tiziano Vecelli (+0.04) (1488/1490 -27 August 1576), known in English as Titian, was an Italian (-0.03) painter, the most important member of the 16th-century Venetian school (+0.01). He was born in Pieve di Cadore (-0.03), near Belluno (-0.01), in Veneto (-0.01) (Republic of Venice (-0.01)). His painting methods would profoundly influence future generations of Western Art (+0.001). The text itself does not contain any obvious indication of why Titian would not be represented in a major museum, so, to get an idea about the reasons for misclassification, we can analyze the decision using an explanation tool such as SHAP/DeepExplainer [START_REF] Scott | A Unified Approach to Interpreting Model Predictions[END_REF], which assigns relevance scores to all tokens in the text. Looking at the scores (in brackets), we can see that the toponyms such as "Pieve di Cadore" and "Veneto" push the decision in the negative direction. Indeed, simply reducing the abstract to Tiziano Vecelli (1488/1490 -27 August 1576), known in English as Titian, was an Italian painter, the most important member of the 16th-century Venetian school. His painting methods would profoundly influence future generations of Western Art. is enough to switch the model's prediction to "positive" with a high score of 0.74. This isolated case hints at some non-intuitive preference within the model, but does not reveal it: e.g., is there a bias against the token "Pieve di Cadore", any Italian-originated word, any Italian toponym, all toponyms in general, or is there in fact no consistent bias and the decision was caused by some specific co-occurrence of tokens? In order to understand the model better, we need to be able to generalize from individual examples and capture such preferences at the semantic level: i.e., discover clusters of tokens that consistently influence the model in the same way and represent meaningful categories from the human point of view, for example:

"If the text mentions an Italian toponym, this usually shifts the model's decision to negative" Such rules can be used (a) to analyze the reasons for misclassifications when the model is deployed in the real world or (b) to improve the model by resampling the training data, removing the undesired correlations, and retraining.

To move from analyzing individual relevance scores to reasoning over domain categories, we propose an algorithm consisting of three stages (Figure 1):

• Discovering important input features influencing the model's decision using an existing post-hoc explanation method. • Mapping discovered influential features to a knowledge graph which categorizes them and describes them with facts. • Applying association rule mining [START_REF] Hipp | Algorithms for Association Rule Mining -A General Survey and Comparison[END_REF] to capture the model's learned preferences in the form of predictive explanation rules over knowledge graph concepts and properties.

BACKGROUND AND RELATED WORK

Our work builds on results from two research directions, which, to our knowledge, have not been applied in combination so far: explaining neural network models and association rule mining.

Explaining neural network models

Unlike other machine learning algorithms (e.g., linear regression or decision trees), non-linear neural network models are not inherently intelligible [START_REF] Weld | The challenge of crafting intelligible intelligence[END_REF]: i.e., they do not allow a human user to understand which input features were important for a given prediction. A posthoc explanation method tries to overcome this by analyzing the network's decision process and assign relevance scores to input features. Let 𝑓 𝑐 (•) denote some prediction function learned by a neural network for each class 𝑐. We denote as X 1 , . . . , X n a set of input examples, each one consisting of a sequence of tokens of length 𝑇 : X j = {𝑥 𝑗,1 , . . . , 𝑥 𝑗,𝑇 }. Each input feature 𝑥 𝑗,𝑘 represents an occurrence of some word 𝑤 𝑖 in the vocabulary V. An explanation represents a set of real-valued scores 𝜙 (𝑐, 𝑡, X) that assign relevance for each class 𝑐 for each position 𝑡 = 1, . . . ,𝑇 of the input text X.

For a binary classification task, we will use the notation 𝜙 (𝑡). Some methods try to provide explanations without analyzing the internals of the model. One group of such black-box algorithms utilizes input perturbations: modifying elements of the input and measuring changes in the output. While originally proposed for image processing [START_REF] Zeiler | Visualizing and Understanding Convolutional Networks[END_REF][START_REF] Zintgraf | Visualizing Deep Neural Network Decisions: Prediction Difference Analysis[END_REF], this approach was later adapted for NLP tasks as well [START_REF] Kádár | Representation of Linguistic Form and Function in Recurrent Neural Networks[END_REF][START_REF] Li | Understanding Neural Networks through Representation Erasure[END_REF]. Another group, represented by the LIME [START_REF] Túlio Ribeiro | Explaining the Predictions of Any Classifier[END_REF] algorithm tries to approximate the behaviour of a neural network classifier in the neighbourhood of the input 𝑋 with an interpretable (e.g., linear) model. While being generic, such black-box methods (a) can be inefficient due to the need for multiple input perturbations and sampling and (b) do not give interpretable information about model's internal parameters.

Another class of methods tries to assign relevance scores by back-propagating through the model, e.g. by calculating the output's gradient with respect to the input [START_REF] Simonyan | Deep Inside Convolutional Networks: Visualising Image Classification Models and Saliency Maps[END_REF][START_REF] Sundararajan | Axiomatic Attribution for Deep Networks[END_REF]. This, however, highlights such input features to whose change the model is the most sensitive, which are not necessarily the ones that contributed the most to the decision [START_REF] Montavon | Methods for Interpreting and Understanding Deep Neural Networks[END_REF]. Layer-wise relevance propagation (LRP) [START_REF] Arras | Explaining Recurrent Neural Network Predictions in Sentiment Analysis[END_REF][START_REF] Bach | On Pixel-Wise Explanations for Non-Linear Classifier Decisions by Layer-Wise Relevance Propagation[END_REF] defines back-propagation rules that distribute the output value among the relevance scores of inputs such that 𝑓 𝑐 (X) = 𝑇 1 𝜙 (𝑐, 𝑡, X), thus assigning to each input value a fraction of the output. The DeepLift algorithm proposed by [START_REF] Shrikumar | Learning Important Features Through Propagating Activation Differences[END_REF] instead computes the relevance scores that characterize the positive/negative influence of each input relative to some reference point input: i.e., 𝑓 𝑐 (X) = 𝑓 𝑐 (X 𝑟𝑒 𝑓 ) + 𝑇 1 𝜙 (𝑐, 𝑡, X). This is an advantage in our scenario, since it makes relevance score interpretation independent of its absolute value, which, in turn, makes it easy to aggregate relevance scores across multiple data instances. There exist several implemented variations of DeepLift [START_REF] Ancona | Towards better understanding of gradient-based attribution methods for Deep Neural Networks[END_REF][START_REF] Scott | A Unified Approach to Interpreting Model Predictions[END_REF][START_REF] Shrikumar | Learning Important Features Through Propagating Activation Differences[END_REF], among which we selected to use SHAP/DeepExplainer [START_REF] Scott | A Unified Approach to Interpreting Model Predictions[END_REF] in our experiments for its support for a range of different network architectures.

More recently, the idea of concept-based explanations arose in the image processing domain [START_REF] Ghorbani | Towards Automatic Concept-based Explanations[END_REF][START_REF] Kim | Interpretability Beyond Feature Attribution: Quantitative Testing with Concept Activation Vectors (TCAV)[END_REF], where "concepts" are informally defined as human-understandable image segments (e.g., "wheel" or "police logo"). While this has some similarities with our general goal, these methods merely consider "concepts" as annotated similarity clusters of image segments, rather than ontological concepts formally defined in a knowledge graph, which enable rule mining. The Semantic Web research community also started exploring the possibilities of bringing in domain ontologies to complement machine learning models and make them more transparent [START_REF] Hitzler | Neural-symbolic integration and the Semantic Web[END_REF][START_REF] Lécué | On the role of knowledge graphs in explainable AI[END_REF][START_REF] Seeliger | Semantic Web Technologies for Explainable Machine Learning Models: A Literature Review[END_REF].

Besides dedicated explanation methods, certain elements of network architectures are often used for interpretation, in particular, convolution filters [START_REF] Jacovi | Understanding Convolutional Neural Networks for Text Classification[END_REF] and learned attention weights [START_REF] Bahdanau | Neural Machine Translation by Jointly Learning to Align and Translate[END_REF][START_REF] Li | Understanding Neural Networks through Representation Erasure[END_REF]. However, these can only be exploited for certain architectures and tasks and it can be non-trivial to interpret them to make judgements about feature significance across multiple examples. Moreover, the validity of interpretations is often dubious [START_REF] Jain | Attention is not Explanation[END_REF][START_REF] Serrano | Is Attention Interpretable?[END_REF].

Mining association rules over knowledge graphs

Association Rule Mining (ARM) was originally proposed to discover relations between products in transaction databases [START_REF] Rakesh Agrawal | Mining Association Rules between Sets of Items in Large Databases[END_REF]. The classical Apriori algorithm [START_REF] Agrawal | Fast Algorithms for Mining Association Rules in Large Databases[END_REF] established the typical two-stage procedure including (i) mining frequent itemsets and (ii) generating rules from these itemsets. Later algorithms followed the same procedure, but further optimized these stages [START_REF] Bayardo | Efficiently Mining Long Patterns from Databases[END_REF][START_REF] Pasquier | Efficient Mining of Association Rules Using Closed Itemset Lattices[END_REF]. While the most popular measures used for selecting valid rules are support and confidence, a number of alternative "interestingness" metrics were proposed [START_REF] Lenca | On selecting interestingness measures for association rules: User oriented description and multiple criteria decision aid[END_REF] with different advantages depending on the context. One potential issue of ARM is the large number of rules produced by the Apriori algorithm and its modifications. This can make the resulting rules difficult to interpret by human users. To deal with this problem, various post-processing methods have been proposed to reorganize and filter the mined rule sets. For example, one approach involves grouping and reorganizing the mined rule set with the help of metarules [START_REF] Berrado | Using metarules to organize and group discovered association rules[END_REF] which capture the interdependencies between the rules themseleves. In [START_REF] Marinica | Post-Processing of Discovered Association Rules Using Ontologies[END_REF], post-processing is based on the use of the domain ontology: an approach which produces well-defined and meaningful groupings, but requires additional manual modelling effort. A range of pruning techniques is based on the notion of rule covers [START_REF] Toivonen | Pruning and grouping discovered association rules[END_REF]: a rule can be considered redundant if all objects it covers are also covered by other rules. In [START_REF] Liu | Post-processing of associative classification rules using closed sets[END_REF] this approach was taken further in application to associative classification rules (rules where consequents represent class label attributes), which also makes it relevant for our explanation rules use case (Section 5).

The growth of structured RDF data triggered research on inductive rule mining in the context of knowledge graphs/ontologies. Various Inductive Logic Programming (ILP) methods [START_REF] Muggleton | ILP turns 20 -Biography and future challenges[END_REF] were adopted to deal with different degrees of expressivity of the output. For example, AMIE [START_REF] Galárraga | Fast rule mining in ontological knowledge bases with AMIE+[END_REF][START_REF] Antonio Galárraga | AMIE: association rule mining under incomplete evidence in ontological knowledge bases[END_REF] focuses on mining Horn rules involving multiple variables: a task, for which classical ARM algorithms were found inefficient. Another direction involves learning description logic expressions to enrich the ontology [START_REF] Lorenz Bühmann | DL-Learner -A framework for inductive learning on the Semantic Web[END_REF][START_REF] Potoniec | Swift Linked Data Miner: Mining OWL 2 EL class expressions directly from online RDF datasets[END_REF]. Our algorithm, however, involves mining Horn rules over a single variable and bears more similarities with the standard ARM scenario. For this reason, we adopt a modified the Apriori algorithm for our rule mining procedure in Section 5.

EXTRACTING RELEVANT ENTITIES

The first step of our method involves utilizing individual relevance scores produced by SHAP/DeepExplainer as evidence to discover influential domain entities. To this end, we aggregate and analyze the relevance scores over the whole set of available training instances.

Computing and aggregating relevance scores

SHAP assigns to each input feature a positive/negative weight that characterizes the impact of the feature relative to some reference point input. Thus, the sum of relevance scores for all input text tokens would be equal to the difference in prediction scores between the chosen example and the reference point, i.e. 𝑓 𝑐 (X) = 𝑓 𝑐 (X 𝑟𝑒 𝑓 ) + 𝑇 1 𝜙 (𝑐, 𝑡, X). SHAP/DeepExplainer adapts the DeepLift algorithm to calculate approximate relevance scores by back-propagating DeepLift multipliers through the network layers (Figure 2). For a given input neuron with an input 𝑥 and an output 𝑓 (𝑥), the multiplier 𝑚 𝑥 𝑓 is defined as:

𝑚 𝑥 𝑓 = 𝜙 (𝑓 (𝑥)) Δ𝑥 = 𝜙 (𝑓 (𝑥)) 𝑥 -𝑥 𝑟𝑒 𝑓
Thus, the multiplier 𝑚 𝑥 𝑓 is the contribution of Δ𝑥 to Δ𝑓 (𝑥) divided by Δ𝑥. The multipliers in this way are similar in spirit to partial derivatives (but are defined over finite differences) and are recursively passed back through the network as shown in Figure 2 [START_REF] Scott | A Unified Approach to Interpreting Model Predictions[END_REF].

∀ 𝑗 ∈ {1,2} 𝑚 ℎ 𝑗 𝑓 2 = 𝜙 𝑖 (𝑓 2 (ℎ)) ℎ 𝑗 -ℎ 𝑗,𝑟𝑒 𝑓 ∀ 𝑗 ∈ {1,2} 𝑚 𝑥 𝑖 𝑓 1𝑗 = 𝜙 𝑖 (𝑓 1𝑗 (𝑥)) 𝑥 𝑖 -𝑥 𝑖,𝑟𝑒 𝑓 𝑚 𝑥 𝑖 𝑓 2 = 2 𝑗=1 𝑚 𝑥 𝑖 𝑓 1𝑗 𝑚 ℎ 𝑗 𝑓 2 𝜙 𝑖 (𝑓 (𝑥)) ≈ 𝑚 𝑥 𝑖 𝑓 2 (𝑥 𝑖 -𝑥 𝑖,𝑟𝑒 𝑓
) Back-propagation of the multipliers using the chain rule to pass through layers and rescaling to handle non-linearities allows approximating relevance in an efficient way. A common strategy for selecting an appropriate reference point is to compute the influence weights relative to a large set of reference examples and compute an average value, instead of trying to select a single input example. The relevance scores calculated for all training examples in this way serve as input of our algorithm.

At the first step of the algorithm we use aggregated influence weights for each input token to select the tokens that consistently "push" the model decision in the same direction: in the simplest case of a binary classification task, consistently "positive" or "negative" decision. Aggregating over multiple predictions helps to overcome the known fragility of neural network interpretations [START_REF] Shi Feng | Pathologies of Neural Models Make Interpretation Difficult[END_REF][START_REF] Ghorbani | Interpretation of Neural Networks Is Fragile[END_REF].

Thus, for a specific token 𝑤 𝑖 in the vocabulary, we select all its mentions in the set of input examples 𝑋 1 , . . . , 𝑋 𝑁 , 𝑀 (𝑤 𝑖 ) = 𝑗=1,...,𝑁 {𝑥 𝑗,𝑘 |𝑥 𝑗,𝑘 = 𝑤 𝑖 }. After applying the explanation algorithm over the whole set of examples X 1 , . . . , X n , we can get for each reference of any token in the vocabulary a set of relevance scores Φ(𝑐, 𝑤 𝑖 ) = {𝜙 (𝑐, 𝑘, X j )|𝑥 𝑗,𝑘 ∈ 𝑀 (𝑤 𝑖 )}. Within this set, we separate the occurrences into positive, where the token drives the model to increase the decision score in favour of the given class:

Φ + (𝑐,𝑤 𝑖 )={𝜙 (𝑐,𝑘,X j ) |𝑥 𝑗,𝑘 =𝑤 𝑖 ,𝜙 (𝑐,𝑘,X j ) >0}
and, similarly, negative ones Φ -(𝑐, 𝑤 𝑖 ) where 𝜙 (𝑐, 𝑘, X j ) < 0: e.g., the city of Belluno from our example is mentioned 4 times in the training corpus and only in 1 case with 𝜙 > 0, so |Φ + (𝑐, "𝐵𝑒𝑙𝑙𝑢𝑛𝑜")| = 1 and |Φ -(𝑐, "𝐵𝑒𝑙𝑙𝑢𝑛𝑜")| = 3.

Selecting influential tokens

Once each occurrence of each token has been assigned a relevance score, the next step involves distinguishing the "influential" tokens which consistently impact the network in the same way, from nonsignificant ones, whose influence varies greatly between different occurrences and heavily depends on the context. For this, we introduce the influence function 𝐹 𝑖𝑛𝑓 (𝑑 𝑖 ), which would return a measure of influence for each token.

We tested several alternative strategies for determining such significant tokens, in particular:

• Token classification: selecting influential tokens based on the ratio of positive/negative occurrences:

𝑟 ± (𝑐, 𝑤 𝑖 ) = |Φ ± (𝑐,𝑤 𝑖 ) | |Φ(𝑐,𝑤 𝑖 ) |
and comparing it with a threshold 𝜃 . Thus, a token 𝑤 𝑖 will be considered positive (𝐹 𝑖𝑛𝑓 (𝑤 𝑖 ) = 1) if 𝑟 + (𝑐, 𝑤 𝑖 ) > 𝜃 , negative (𝐹 𝑖𝑛𝑓 (𝑤 𝑖 ) = -1) if 𝑟 + (𝑐, 𝑤 𝑖 ) < 1 -𝜃 or not significant (𝐹 𝑖𝑛𝑓 (𝑤 𝑖 ) = 0) otherwise. • Token scoring: instead of assigning discrete labels to tokens, each token gets assigned a real-valued score 𝐹 𝑖𝑛𝑓 (𝑤 𝑖 ) = 𝑟 + (𝑐, 𝑤 𝑖 ). • Weighted token scoring: each token gets weighted by the number of positive/negative occurrences 𝐹 + 𝑖𝑛𝑓 (𝑤 𝑖 ) = |Φ + | and 𝐹 - 𝑤 𝑖 = |Φ -| rather than the ratio, so that more frequent tokens are valued higher.

Note that we only take into account the sign of each relevance score 𝜙 rather than its absolute value. Since the values of relevance scores are scaled by the final prediction 𝑓 𝑐 (•), they are not comparable between different examples X j .

Grounding influential tokens with a knowledge graph

After determining the set of influential input tokens, we select only the semantically meaningful ones that reference domain entities represented in a knowledge graph containing relevant domain knowledge. We assume the following definition for a knowledge graph from the Resource Description Framework (RDF): A knowledge graph 𝐺 is a finite set of triples (𝑠, 𝑝, 𝑜) ∈ (𝐸∪𝐵)×𝑅×(𝐸∪𝐵∪𝐿), where 𝐸 is a set of URI resources (entities), 𝐵 denotes blank nodes, 𝑅 is a set of URI relations, and 𝐿 is a set of literals.

Our method therefore requires a mapping between a subset of tokens V G ⊂ V and their representative named entities 𝑒 𝑖 ∈ 𝐸 from 𝐺: e.g., between the token "Belluno" and Wikidata ID "Q6558". If there is no available mapping between text tokens and graph entities, a named entity recognition task has to be performed separately. As a result of this stage, we move from the influence functions of textual tokens 𝐹 𝑖𝑛𝑓 (𝑤 𝑖 ) to influence functions 𝐹 𝑖𝑛𝑓 (𝑒 𝑖 ) for influential domain entities, each one uniquely denoted by a URI.

RULE MINING

At the next stage, our algorithm takes the set of discovered significant domain entities and their associated relevance scores and tries to describe this set in terms of the domain knowledge represented in the knowledge graph. Our use case represents an example of associative classification, which in turn is a special case of the association rule mining (ARM) task where the consequent of an association rule is constrained by class label attributes.

Background

Formally, the data mining context of ARM is represented by a transaction database 𝐷 = (𝑂, 𝐼, 𝑅), where 𝑂 and 𝐼 are finite sets of transactions and items respectively and 𝑅 ⊆ 𝑂 ×𝐼 is a binary relation between 𝑂 and 𝐼 . 𝐷 is arranged as a set of transactions where each transaction 𝑡 ∈ 𝑂 is a set of items 𝑦 ∈ 𝐼 (itemset). Thus, (𝑡, 𝑦) ∈ 𝑅 means that the item 𝑦 occurs in the transaction 𝑡, and a transaction 𝑡 is said to contain an itemset 𝑌 if ∀𝑦 ∈ 𝑌 : (𝑡, 𝑦) ∈ 𝑅. For each itemset 𝑌 ⊆ 𝐼 its support 𝑠𝑢𝑝 (𝑌 ) is the number of transactions in which the itemset occurs, i.e. 𝑠𝑢𝑝 (𝑌 ) = |𝑇 |, where 𝑇 = {𝑡 ∈ 𝑂 |∀𝑦 ∈ 𝑌 : (𝑡, 𝑦) ∈ 𝑅}. The aim of ARM is to discover intrinsic relations between itemsets. An association rule is an implication of the form 𝑋 → 𝑌 , where 𝑋 ⊆ 𝐼 and 𝑌 ⊆ 𝐼 are the antecedent and the consequent of the rule and 𝑋 ∩ 𝑌 = ∅. For 𝑋 → 𝑌 its support 𝑠𝑢𝑝 (𝑋 → 𝑌 ) is defined as 𝑠𝑢𝑝 (𝑋 → 𝑌 ) = |{𝑡 ∈ 𝑂 |𝑋 ⊆ 𝑡, 𝑌 ⊆ 𝑡 }| and confidence is the conditional probability that 𝑌 ⊆ 𝑡 given that 𝑋 ⊆ 𝑡, i.e. 𝑐𝑜𝑛𝑓 (𝑋 → 𝑌 ) = 𝑠𝑢𝑝 (𝑋 →𝑌 ) 𝑠𝑢𝑝 (𝑋 ) . In the case of explanation rules, our set of transactions 𝑂 consists of all IRI instances in the knowledge graph that are referenced in the text I 𝑡𝑒𝑥𝑡 . For each 𝑡 ∈ I 𝑡𝑒𝑥𝑡 , its itemset 𝐼 (𝑡) includes:

• All statements in the knowledge graph 𝐺 containing 𝑡 as a subject or an object: {(𝑠, 𝑝)|(𝑠, 𝑝, 𝑡) ∈ 𝐺 } ∪ {(𝑝, 𝑜)|(𝑡, 𝑝, 𝑜) ∈ 𝐺 }. • A class label 𝐶𝑙𝑠 stating whether 𝑡 has a positive or negative influence. 𝐶𝑙𝑠 (𝑥) can take one of {𝑃𝑜𝑠 (𝑋 ), 𝑁 𝑒𝑔(𝑋 )}. Each explanation rule in our case has the format 𝑌 (𝑥) → 𝑃𝑜𝑠 (𝑥) or 𝑌 (𝑥) → 𝑁 𝑒𝑔(𝑥), holding the class label as a consequent, while the antecedent represents a conjunction 𝑌 (𝑥) = 𝑖 (𝑠 𝑖 , 𝑝 𝑖 , 𝑥) ∧ 𝑗 (𝑥, 𝑝 𝑗 , 𝑜 𝑗 ): e.g., a rule covering Italian toponyms from our example can take the form 𝐶𝑖𝑡𝑦 (𝑥) ∧ 𝑙𝑜𝑐𝑎𝑡𝑒𝑑𝐼𝑛(𝑥, 𝐼𝑡𝑎𝑙𝑦) → 𝑁 𝑒𝑔(𝑥).

Mining classification rules

The classical Apriori algorithm [START_REF] Agrawal | Fast Algorithms for Mining Association Rules in Large Databases[END_REF] for mining rules proceeds in two steps:

• Finding frequent itemsets 𝑌 (𝑥) that pass the minimum support threshold 𝑠𝑢𝑝 (𝑌 (𝑥)) ≥ 𝑠𝑢𝑝 𝑚𝑖𝑛 . Frequent itemsets are constructed iteratively: Frequent itemsets of length 𝑘 + 1 are constructed by adding operands to frequent itemsets of length 𝑘, starting from 𝑘 = 1. • Generating rules 𝑌 (𝑥) → 𝐶𝑙𝑠 (𝑥) from frequent itemsets.

Valid rules are selected based on the minimum confidence threshold 𝑐𝑜𝑛𝑓 (𝑌 (𝑥) → 𝐶𝑙𝑠 (𝑥)) ≥ 𝑐𝑜𝑛𝑓 𝑚𝑖𝑛 . Depending on the influence measurement strategy discussed in Section 4, we used different confidence measures, which generalize from the token significance metrics:

• Token classification (TC): this is a straightforward application of the confidence measure to evaluate a rule using the assigned token classification labels:

𝑐𝑜𝑛𝑓 𝑇𝐶 (𝑌 (𝑥) → 𝑃𝑜𝑠 (𝑥)) = |{𝑑 𝑖 |𝑑 𝑖 ∈ 𝑌 (𝑥), 𝐹 𝑖𝑛𝑓 (𝑑 𝑖 ) = 1}| |{𝑑 𝑖 |𝑑 𝑖 ∈ 𝑌 (𝑥)}|
• Token scoring (TS): here a real-valued function 𝐹 𝑖𝑛𝑓 (𝑑 𝑖 ) is taken into account

𝑐𝑜𝑛𝑓 𝑇 𝑆 (𝑌 (𝑥) → 𝑃𝑜𝑠 (𝑥)) = 𝑌 (𝑥) 𝐹 𝑖𝑛𝑓 (𝑑 𝑖 ) |𝑌 (𝑥)| • Weighted token scoring (WTS): 𝑐𝑜𝑛𝑓 𝑊 𝑇 𝑆 (𝑌 (𝑥) → 𝑃𝑜𝑠 (𝑥)) = 𝑌 (𝑥) 𝐹 + 𝑖𝑛𝑓 (𝑑 𝑖 )
𝑌 (𝑥) (𝐹 + 𝑖𝑛𝑓 (𝑑 𝑖 ) + 𝐹 - 𝑖𝑛𝑓 (𝑑 𝑖 )) Note that these metrics behave differently in cases where tokens within the category vary greatly with respect to their frequency. For example, in the tweet political leaning classification use case, we have a candidate rule (𝑥, 𝑜𝑐𝑐𝑢𝑝𝑎𝑡𝑖𝑜𝑛, 𝑝𝑜𝑙𝑖𝑡𝑖𝑐𝑖𝑎𝑛)∧(𝑥, 𝑐𝑜𝑢𝑛𝑡𝑟𝑦, 𝐶𝑎𝑛𝑎𝑑𝑎) → 𝐷𝑒𝑚𝑜𝑐𝑟𝑎𝑡𝑖𝑐 (𝑥) with 5 items satisfying the antecedent criterion. For 4 of them the assumption holds, i.e., they were mostly referenced in pro-democratic tweets, but the 5th one was Ted Cruz who held double citizenship until 2014 and (a) was referenced in primarily pro-republican tweets and (b) had significantly more mentions in the training set than the other 4 combined. Thus, the rule would be selected as valid by the token classification and token scoring metrics, but with weighted token scoring an opposite rule would be created classifying Canadian politicians as evidence for pro-republican leaning. Interpretation of the rule would be different as well: a newly encountered randomly selected Canadian politician in a tweet would more likely shift the model decision towards pro-Democratic, but a random mention of some Canadian politician in a new tweet would more likely point to a pro-Republican tweet since this would likely be a mention of Ted Cruz. For more robust rules that would be valid under both interpretations, we introduced hybrid metric (H):

𝑐𝑜𝑛𝑓 𝐻 (𝑌 (𝑥) → 𝑃𝑜𝑠 (𝑥)) = 𝑚𝑖𝑛(𝑐𝑜𝑛𝑓 𝑇𝐶 , 𝑐𝑜𝑛𝑓 𝑊 𝑇 𝑆 )

Post-processing mined rules

A well-known issue with rule mining algorithms is the potentially large set of produced rules, which makes it difficult to interpret and utilize by a human user. To deal with this, we adapted the approach described in [START_REF] Liu | Post-processing of associative classification rules using closed sets[END_REF] targeted at classification rules and based on the notion of closed rule sets: closed sets of rules covering the same set of transactions. If for two rules, 𝑟 1 and 𝑟 2 , and their supporting sets of transactions, 𝑇 1 and 𝑇 2 , the relation 𝑇 2 ⊂ 𝑇 1 holds, then 𝑟 1 is called a cover-rule of 𝑟 2 . The rule 𝑟 2 in this situation becomes redundant and can be safely discarded. Each closed rule set can then be replaced by a subset of its cover-rules which jointly cover all its transactions.

EVALUATION AND DISCUSSION

Existing benchmark datasets created to evaluate the neural network explanation methods on NLP tasks [START_REF] Arras | Explaining Recurrent Neural Network Predictions in Sentiment Analysis[END_REF][START_REF] Arras | Evaluating Recurrent Neural Network Explanations[END_REF][START_REF] Pörner | Evaluating neural network explanation methods using hybrid documents and morphosyntactic agreement[END_REF] are not suitable in our case, because they do not reference domain information modelled by a knowledge graph. For this reason, we selected our own evaluation datasets using two criteria: (i) availability of pre-existing mappings with Wikidata (Wikipedia links and Twitter account references) to avoid the need for a named entity recognition step, potentially introducing errors and (ii) non-triviality of prediction: the target variable should not be directly present in the text itself, which otherwise would lead to high performance of the model, but trivial explanation rules. Based on these, we selected the following four benchmarks:

• Wikipedia abstracts: As examples, we selected abstracts of Wikipedia articles describing Wikidata instances of the same type. The Wikipedia links in the text were used to map the tokens in the text to Wikidata and the input word embeddings (word2vec [START_REF] Mikolov | Distributed representations of words and phrases and their compositionality[END_REF]) were trained using the complete Wikipedia corpus with explicit references of Wikidata IRIs. In this way, we obtained a common vector space containing Wikidata IRIs together with common words.

-Painters: The task involves deciding whether painters who died before 1700 are likely to have their paintings in one of -Movie rating: The task involves deciding whether a movie is likely to receive a higher than median rating on IMDB.

The selected dataset contains 8087 abstracts. -Movie popularity: The task uses the same textual data as the previous one, but focuses on deciding whether a movie is likely to receive more than the median number of votes on IMDB. • Political leaning: For this test, we reused a pre-trained LSTM model published by [START_REF] Rao | Actionable and Political Text Classification using Word Embeddings and LSTM[END_REF], which classified tweets based on their political leaning (pro-democratic vs pro-republican), and the publicly available test set of 10,000 tweets. We used the referenced Twitter accounts to map them to corresponding Wikidata entities.

For the three Wikipedia datasets, we trained the models ourselves, splitting the datasets equally into the train and test sets. In order to evaluate the dependency of mined rulesets on the network architecture, for each datasets we trained two models: (i) Bi-LSTM and (b) two-layer CNN. The details of all models are provided in Appendix A.

Accuracy of the learned rules

We evaluated the quality of rules mined in the training set by calculating their prediction accuracy on the test set. We selected all entities covered by the mined rules that satisfied the rules' antecedent and were mentioned in the test set. The first measure, "impact accuracy" (𝐴𝑐𝑐 𝑖𝑚𝑝 ), checked whether for each occurrence of the entity its relevance score corresponded with the rule prediction: i.e., for all occurrences of entities 𝑥 satisfying rules 𝑌 (𝑥) → 𝑃𝑜𝑠 (𝑥) and 𝑌 (𝑥) → 𝑁 𝑒𝑔(𝑥), calculating the ratio of cases where the sign of the relevance score was correctly predicted.

𝐴𝑐𝑐 𝑖𝑚𝑝 = | {𝑡 ∈ 𝑀 + (𝑒 𝑖 )|𝜙 (𝑡) > 0} ∪ {𝑡 ∈ 𝑀 -(𝑒 𝑖 )|𝜙 (𝑡) < 0}| | 𝑀 (𝑒 𝑖 )|
As the second metrics "overall prediction accuracy" (𝐴𝑐𝑐 𝑜𝑣𝑒𝑟𝑎𝑙𝑙 ), we measured the ratio of coincidences with the overall model prediction: i.e., for all entity occurrences covered by rules calculating 1 Louvre, Hermitage, Prado, Uffizi, Vatican, London National Gallery, Rijksmuseum, museums in Vienna, Berlin, and Munich.

the ratio of cases where the model prediction for the whole text coincided with the rule prediction for the mentioned entity.

𝐴𝑐𝑐 𝑜𝑣𝑒𝑟𝑎𝑙𝑙 = | {𝑡 ∈ 𝑀 + (𝑒 𝑖 )|𝑓 (X j ) > 0} ∪ {𝑡 ∈ 𝑀 -(𝑒 𝑖 )|𝑓 (X j ) < 0}| | 𝑀 (𝑒 𝑖 )|
As we can see in Table 1, in all cases a substantial part of the model's behaviour can be explained away with the semantic preferences captured by the mined rules: with the most accurate "hybrid" strategy, for the subset covered by the rules 𝐴𝑐𝑐 𝑜𝑣𝑒𝑟𝑎𝑙𝑙 was usually close to the accuracy of the model itself. In general, the TC and H strategies achieved higher accuracy than both TS and WTS. Accounting for non-influential tokens that receive highly varying influence scores in different instances helps to produce more robust rules.

As expected, most of the mined rules reflected common sense knowledge about the corresponding domains. For instance, in the Painters use case, the Dutch or Flemish origin, professional painter's career, and elements of Christian art were found to be positive factors leading to such rules like ℎ𝑢𝑚𝑎𝑛 (𝑥)∧𝑐𝑖𝑡𝑖𝑧𝑒𝑛 (𝑥,𝑆𝑜𝑢𝑡ℎ𝑒𝑟𝑛𝑁 𝑒𝑡ℎ𝑒𝑟𝑙𝑎𝑛𝑑𝑠)

∧𝑚𝑒𝑚𝑏𝑒𝑟𝑂 𝑓 (𝑥,𝐴𝑛𝑡 𝑤𝑒𝑟𝑝𝐺𝑢𝑖𝑙𝑑𝑜 𝑓 𝑆𝑡𝐿𝑢𝑘𝑒)→𝑃𝑜𝑠 (𝑥) or 𝑝𝑎𝑖𝑛𝑡𝑖𝑛𝑔 (𝑥)∧𝑑𝑒𝑝𝑖𝑐𝑡𝑠 (𝑥,𝑉 𝑖𝑟𝑔𝑖𝑛𝑀𝑎𝑟 𝑦)→𝑃𝑜𝑠 (𝑥)
In turn, non-Western origin (e.g., China, Korea, or Russia) or too early time period (Classical Antiquity) usually had a negative impact (Figure 4).

But some preferences were non-intuitive: e.g., a bias against various Italian toponyms. When analyzing the dataset, two complementing reasons emerged: (i) a large number of Italian artists created frescoes rather than oil paintings, which could be moved to museums, and (ii) many Italian painters from small cities did not join one of the famous communities (e.g., in Florence or Rome) and did not acquire global fame, although their works survived in local museums. Such counter-intuitive biases can be used to resample the training data and fine-tune the model behaviour.

Interestingly, different factors were found to be at play when classifying movies by rating or by popularity. For the rating, the most significant positive factors were various awards, while negative ones included certain genres or character types (e.g., zombie movies or superheroes). For the popularity, on the other hand, the positive factors were generally related to recent cultural trends (e.g., association with the Marvel universe or having Brad Pitt as a cast member), while the negative ones had to do with old age (e.g., black and white colour or Clark Gable as an actor). Finally, for the political use case, the referenced twitter accounts were found to have greater influence than the content of the tweet itself: e.g., referencing a military officer or a Methodist church member usually shifted the decision towards "pro-republican", while mentioning a Hollywood actor or a CNN journalist were signs of "pro-democratic".

Figure 3 shows a trade-off between the precision of the mined set of rules and the coverage (percentage of entities which support at least one rule) achieved with different thresholds. The TC strategy generally results in higher precision rules, while the WTS produces more generic rule sets covering a larger proportion of entities.

Impact of network architecture differences

In order to validate that the method is generic enough to be used in combinations with different network architectures, it is important to verify to which extent its results are adequately capturing correlations existing in the data and learned by the model rather than representing uninformative fluctuations dependent on the choice of the model architecture. For this reason, in the Wikipedia abstracts experiments we tested our method with two different neural network architectures for the same task: the LSTM and the CNN. As shown in Table 2, the rules mined after analyzing the influential tokens for both networks largely reflect the same preferences: the sets of entities covered by rules for both network types are strongly overlapping.

The results also show the effects of highly selective metrics (TC and H): due to high dependency on the separation between influential and non-influential tokens, the results are more sensitive to the specific network architecture, the overlap between corresponding entity sets covered by rules is generally lower, but the positive and negative token sets are well-separated. On the other hand, TS and WTS result in greater correlation between the corresponding entity sets, but the rule sets are so generic that there is high overlap between opposite classes to the degree which makes the rules noninformative. This is corroborated by the lower prediction scores achieved with these metrics (Table 1).

Validity outside of the training context

In practical scenarios, the trained model usually has to be applied to new unseen data instances, which can follow different distributions from the training and test sets, which in turn makes the model more error-prone in comparison with its test set performance. In such cases, mined rules can be valuable for diagnosing misclassifications, but only if they are generic enough to hold outside of the training corpus. To check this, we applied the model to a different set of text examples outside of the intended context of the model, but which would contain internally the semantic preferences captured by the rules. For this test, we selected all positive and negative entities covered by mined rules and applied the model to the Wikipedia abstracts of these entities (excluding those included in the training or test set). The model predictions themselves for such examples are not meaningful (e.g., whether the city of Perugia or the character Virgin Mary would have their paintings in a major gallery if they were painters). However, we would expect that the Wikipedia abstracts of entities predicted to have positive impact would themselves be more likely to be classified positively by the model. As we can see in Table 3, for all datasets this expectation holds, which can be seen as an indication that the semantic preferences captured by the model are sufficiently generic to explain the model's behaviour even outside the original learning context.

Viewing and utilizing mined rules

As said in section 2, the purpose of the mined explanation rules is to help the user understand the underlying preferences of the trained deep learning model. Reducing the set of mined rules and presenting them in a human-readable form makes this task easier for the user. Removing redundant rules using closed rule sets (Section 5.3) helps towards achieving the first goal. Visualizing closed rule sets as a graph (Figure 4) makes it easier to explore the rule sets and identify semantic categories which correspond to influential model parameters that can shift model's decision either way. As said in Section 6.1, majority of mined rules in our experiments are consistent with common-sense domain knowledge. However, two types of rules can be of special interest:

• Counter-intuitive rules that contradict common sense, e.g., like a counter-intuitive rule that Italian origin somehow reduces the value of painters' works. Such rules should motivate further analysis of the training dataset and the learning process. This analysis can point to an impact of the training data sampling (like in the case with Italian art) and, in the worst case, to spurious Clever Hans-type biases. • Rules that make use of undesired input data features, which make the model itself violate the requirements: e.g., relying on race or gender terms.

In both cases, discovering such rules can require modifications in order to improve the model, for instance, resampling the training set to avoid biases or pre-processing the training set to remove undesired features.

CONCLUSION AND FUTURE WORK

We have proposed a method for mining explanation rules to capture consistent semantic preferences of neural NLP models. Our experiments have shown that generalizing from atomic relevance scores using association rule mining creates human-interpretable rules that both explain the model behaviour to a large extent and are robust enough to be useful when the model is used outside of the training context. While these results are promising, they cannot provide a complete understanding of a trained model as many important factors are left out. Based on our observations, we consider two directions for future work:

• Using knowledge graphs and rule mining to improve interpretability of intermediate elements of the model: e.g., attention weights, convolutional filters, and feature embeddings. Mined rules can provide "semantic views" over the corresponding vector spaces, highlighting regions that are significant to the model's decision and on the other hand can be mapped to the semantic space. • Extending the method to capture other types of features significant for the model: e.g., syntactic patterns, elements of style, and sentiment.

Figure 1 :

 1 Figure 1: Capturing explanation in the form of knowledge graph-grounded rules.

Figure 2 :

 2 Figure 2: Approximating relevance scores by backpropagating DeepLift multipliers.

Figure 3 :

 3 Figure 3: Aggregated coverage and precision achieved by mined rules with different metrics.

  (a) predicting the impact of a single entity (positive/negative) and (b) predicting the overall model decision over the whole text and (c) percentage of entities covered by the final ruleset. All metrics were tested with the same 𝑐𝑜𝑛𝑓 𝑚𝑖𝑛 = 0.75, for TC and H the parameter 𝜃 = 1.0 was used.

Figure 4 :

 4 Figure 4: Visualized clusters of positive (left) and negative (right) rules composed for the convolutional network applied to the Painters use case. Rules represent nodes of the graph, while edges reflect overlaps between support sets. Connected components represent closed rule sets.

Table 1 :

 1 Accuracy of learned classification rules in

	Use case	Model		Impact accuracy		Overall prediction accuracy	Coverage	Model
		type		𝐴𝑐𝑐 𝑖𝑚𝑝			𝐴𝑐𝑐 𝑜𝑣𝑒𝑟𝑎𝑙𝑙
			TC	TS	WTS H	TC	TS	WTS H	TC	TS	WTS H	accuracy
	Painters	Conv (all) Conv (unseen)	0.80 0.69 0.73 0.79 0.71 0.51	0.86 0.69 0.49 0.70 0.80 0.72 0.53 0.47	0.75 0.72	0.45 0.96 0.96	0.43 0.71
		LSTM (all) LSTM (unseen) 0.81 0.73 0.74 0.85 0.74 0.77	0.86 0.73 0.55 0.68 0.81 0.70 0.59 0.60	0.74 0.70	0.59 0.97 0.96	0.58 0.71
	Movies (rating)	Conv (all) Conv (unseen)	0.83 0.66 0.67 0.69 0.63 0.63	0.83 0.71 0.46 0.47 0.68 0.55 0.44 0.44	0.71 0.54	0.45 0.98 0.98	0.44 0.68
		LSTM (all) LSTM (unseen) 0.77 0.62 0.62 0.86 0.64 0.66	0.84 0.73 0.46 0.48 0.74 0.61 0.44 0.44	0.71 0.61	0.50 0.99 0.99	0.49 0.68
	Movies (popularity) Conv (unseen) Conv (all)	0.77 0.67 0.66 0.64 0.61 0.56	0.77 0.69 0.54 0.54 0.64 0.57 0.48 0.45	0.69 0.57	0.79 0.86 0.99	0.78 0.79
		LSTM (all) LSTM (unseen) 0.75 0.63 0.58 0.83 0.67 0.67	0.84 0.72 0.52 0.52 0.75 0.66 0.47 0.44	0.73 0.66	0.79 0.99 0.99	0.78 0.79
	Political tweets	LSTM (all) LSTM (unseen) 0.70 0.62 0.51 0.66 0.64 0.73	0.90 0.63 0.61 0.70 0.70 0.65 0.57 0.47	0.86 0.66	0.35 0.38 0.42	0.35 0.90

Table 2 :

 2 Overlap of entities covered by rules created for different network architectures (CNN and LSTM) for the same task. The table shows overlap distances between Ω + 𝐶𝑁 𝑁 and Ω + 𝐿𝑆𝑇 𝑀 , in brackets the overlap distances with the rules of the opposite class are given (Ω + 𝐶𝑁 𝑁 and Ω - 𝐿𝑆𝑇 𝑀 ).

	Use case	Class Avg. score Avg. per-rule score 𝑟 𝑃𝑜𝑠
	Painters	Pos	0.47	0.55	0.47
		Neg	0.10	0.12	0.05
	Movies	Pos	0.68	0.75	0.77
	(rating)	Neg	0.35	0.34	0.23
	Movies	Pos	0.34	0.72	0.31
	(popularity) Neg	0.05	0.08	0.02

Table 3 :

 3 Model predictions on entities covered by rules.

A MODELS USED IN EXPERIMENTS

Experiments described in Section 6 included two parts: tests on Wikipedia abstracts and tweets classification. The Wikipedia abstracts tests involved two datasets: abstracts of painters (3943 abstracts) and movies (8087 abstracts). These datasets were in turn used in three classification tasks: (i) classifying painters represented in a major European museum collection, (ii) detecting movies with higher than the median IMDB rating, and (iii) detecting movies with higher than the median number of IMDB votes. For each of these tasks we employed two types of models: convolutional (CNN) and recurrent bi-directional long short-term memory (Bi-LSTM). These datasets as well as the trained models we used in our experiments are available online 2 . Finally, for the tweets political leaning classification [START_REF] Rao | Actionable and Political Text Classification using Word Embeddings and LSTM[END_REF] we reused a pre-trained LSTM model and a publicly available test dataset of 10000 tweets provided by the authors 3 . All use cases involve binary classification, so the output of all networks constitutes a single neuron. Sigmoid activation is applied to normalize the output and get the final prediction.

A.1 CNN for Wikipedia abstract classification

A.3 LSTM for tweets political leaning classification

This is a pre-trained model described in [START_REF] Rao | Actionable and Political Text Classification using Word Embeddings and LSTM[END_REF], which consists of the following four layers:

•


Mathieu D'aquin

Enrico Motta
email: e.motta@open.ac.uk

Extracting Relevant Questions to an RDF Dataset Using Formal Concept Analysis

Keywords: H.4 [Information Systems Applications]: Miscellaneous Algorithms, Design, Human Factors, Measurement Semantic data, semantic web, RDF, navigation, question, formal concept analysis

With the rise of linked data, more and more semantically described information is being published online according to the principles and technologies of the Semantic Web (especially, RDF and SPARQL). The use of such standard technologies means that this data should be exploitable, integrable and reusable straight away. However, once a potentially interesting dataset has been discovered, significant efforts are currently required in order to understand its schema, its content, the way to query it and what it can answer. In this paper, we propose a method and a tool to automatically discover questions that can be answered by an RDF dataset. We use formal concept analysis to build a hierarchy of meaningful sets of entities from a dataset. These sets of entities represent answers, which common characteristics represent the clauses of the corresponding questions. This hierarchy can then be used as a querying interface, proposing questions of varying levels of granularity and specificity to the user. A major issue is however that thousands of questions can be included in this hierarchy. Based on an empirical analysis and using metrics inspired both from formal concept analysis and from ontology summarisation, we devise an approach for identifying relevant questions to act as a starting point to the navigation in the question hierarchy.

INTRODUCTION

The idea of a Semantic Web is quickly gaining momentum as more and more organisations are exposing their data in structured, semantically described datasets following the principles of linked data [START_REF] Bizer | Linked datathe story so far[END_REF]. When coming across such a dataset, a significant effort is generally required before it can be exploited. A variety of approaches can be envisaged to become familiar with the content and the structure of such a dataset, including inspecting its schema (i.e., the ontology) with an ontology editor (such as Protégé1 or the NeOn Toolkit2 ), using a graph representation, a faceted browser, or sending test queries in a trial and error approach.

To simplify this process, example queries are often used as a way to characterise a dataset (see, e.g., the use of competency questions in ontology engineering [START_REF] Noy | Ontology Development 101: A Guide to Creating Your First Ontology[END_REF]). By providing a simple representation of the kind of answers a dataset can provide, they help in better understanding what is the scope of the dataset, and how it can be used. In addition, as questions can be formulated in a way close to natural language, such an approach has the advantage of supporting users unfamiliar with the underlying technologies (e.g., the RDF 3 and OWL 4 representation languages, and the SPARQL5 query language), providing easy access points to the dataset.

In this paper, we propose an approach based on automatically extracting a set of questions that can be answered by a dataset. We use formal concept analysis (FCA) to identify sets of objects from a dataset that share common properties. Each of these sets represents the answers to a particular question, which is characterised by the properties shared by the elements of the set. One of the advantages of using FCA is that these sets are organised in a hierarchy (a lattice), relating any extracted question with more general and more specific ones. This hierarchy is used to generate a navigational query interface, allowing the user to browse the set of possible questions to a dataset, together with their answers.

However, one of the main drawbacks of this method is that the application of FCA can generate thousands of questions, making browsing the hierarchy cumbersome. We therefore also study a set of measures, inspired both from ontology summarisation and from FCA, to identify the questions which are more likely to be close to the ones of interest to the user.

Through studying questions proposed by human users of three test datasets, we propose a combination of measures which help identifying a reasonable entry point into the generated question hierarchy, and so to the dataset.

FORMAL CONCEPT ANALYSIS

FCA [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF][START_REF] Wille | Concept lattices and conceptual knowledge systems[END_REF] is a formal, generic framework, generally associated with the fields of data mining and knowledge discovery. In broad terms, it is concerned with identifying from raw data, patterns of objects' characteristics that form formal concepts. 6 Such a concept is characterised both by an intent -i.e., a set of attributes, and an extent -i.e., the set of objects in the data that share these attributes.

More formally, FCA relies on the notion of a formal context, which represents the raw data. A formal context C = (G, M, I) is made of a set of objects G, a set of attributes M and a binary relation I ⊆ G × M . In simpler terms, a formal context is a binary matrix where the rows represent objects, and columns represent attributes of these objects. Given O a set of objects of G, we note O the set of attributes of M which are shared by all the objects of O. In the same way, given A ⊆ M , A ⊆ G is the set of objects that share all the attributes in A. The double application of (.) is said to represent the closure of a set of objects or attributes. In other terms, O and A are said to be closed.

A formal concept of a context C = (G, M, I) is characterised by a pair (O, A), where O ⊆ G and A ⊆ M . O is called the extent and represents the objects that share the attributes of A, i.e., O = A . A is called the intent and represents the attributes that are shared by the objects of O, i.e., A = O . Note that this implies that O = O and A = A , i.e., the concept (O, A) is equivalently defined both by its set of objects, and by its set of attributes.

The set of all concepts that can be derived from a formal context form a lattice, relying on the subconcept relation (denoted by ≤). Indeed, we say that a concept (O1, A1) is a subconcept of another concept (O2, A2) -i.e., (O1, A1) ≤ (O2, A2) -if O1 ⊆ O2 and (equivalently) A2 ⊆ A1. This concept lattice has an upper-bound and a lower-bound (which are often the concept with an empty extent and the one with an empty intent respectively).

BUILDING A CONCEPT LATTICE TO IDENTIFY QUESTIONS IN A DATASET

Our goal here is to extract from a dataset, represented in RDF, a set of questions it can answer. We start by introducing simple notations for describing an RDF dataset. We illustrate these notations, as well as most of the other examples in the article, using the FOAF7 profile of Tom Heath on the Knowledge Media Institute website (http: //kmi.open.ac.uk/people/tom/rdf).

In such a dataset, we essentially focus on instances. Instances represent individual objects that are members of classes. For example, tom is an instance of the class Person. This is represented in RDF through the use of the property rdf:type, but we use here the simplified notation Person(tom). 8 Instances such as tom can have properties linking them to other instances (e.g., to represent the fact that Tom knows Enrico Motta) or to literal values (e.g., to represent the fact that Tom's phone number is "+44-(0)1908-653565"). Such assertions are occurrences of binary relations, presented in our simplified notation as knows(tom, enrico-motta) and phone(tom, "+44-(0)1908-653565") respectively.

The classes such as Person and the properties such as knows come from the ontology(ies) used in the dataset, where they are part of a taxonomy: for example, Person can be a subclass of another class Agent and knows can be a subproperty of a property hasMet. We represent this with the notation Person Agent and knows hasMet respectively. Such taxonomic relationships can be either asserted in the dataset, or inferred from the definitions of the classes and properties.

Assumptions and Requirements

We focus here on questions for which the answers are sets of objects, such as "Who does Tom know?". More precisely, we consider questions corresponding to queries to the dataset for which results are set of instances (e.g., all the people that Tom knows). A question itself is characterised by a set of properties that are common to the elements of the answer. In this sense, it can be related to a conjunctive query -e.g.,"Who knows Tom?" corresponds to the query Person(?x) ∧ knows(?x, tom).

In addition, we assume that a significant question to a dataset should have more than one answer, as querying for the common characteristics of a unique object does not appear relevant. Also, questions complying with our requirements should be related with each other in a hierarchy. For example, it is natural to consider that "What are the things that Tom knows?" is more general than "What are the people that Tom knows?' (i.e., "Who does Tom know?"), or that "Who has Tom met?" is more general than "Who does Tom know?". In other words, a question is more general than another if it includes its set of answers.

Building the Formal Context

The basic idea underlying the technique presented here is relatively straightforward: We want to build a concept lattice where each concept represents a question, with the extent being a set of instances from the dataset corresponding to answers, and the intent the common characteristics of these instances, forming the clauses of the question. We therefore need to build a formal context C = (G, M, I) where G is the set of all instances of the dataset, and M corresponds to all the possible characteristics of these instances.

We consider three types of attributes that can be applied to an instance o of the dataset. Attributes of the form Class::C appear if o is an instance of C (i.e., C(o)). Attributes of the form p:-m appear if o is related through the property p to the instance or the literal value m (i.e., p(o, m)). Attributes of the form p-:m are used if the instance m is related to o through the property p (i.e., p(m, o)).

In order to extend this explicit set of attributes with inferred statements, we also generate additional attributes substituting the classes, properties, and individuals in existing ones with all the possible combinations of superclasses, superproperties and types that can be inferred. For example, we extend Class::P erson and knows:-Enrico-Motta with inferred attributes of the form Class::Agent, hasM et:-Enrico-Motta, knows:-P erson and hasM et:-P erson.

Having built the set of all attributes for all the instances of the dataset, we can now build the matrix relating these attributes to these instances/objects, as a formal context for FCA.

Creating the Lattice and Eliminating Redundancies

One parameter of a concept lattice building tool is the minimum support for a concept to be included in the lattice, i.e., the minimum cardinality of its extent. In accordance with our assumptions and requirements (Section 3.1), we used 2 as minimum support.

An example lattice for the dataset http://kmi.open.ac. uk/people/tom/rdf is presented in Figure 1(a). Five concepts are present in the hierarchy, with the top one representing all the objects of the dataset and therefore, all the instances of the class Thing, the class of everything in OWL. It can also be noticed in this example that significant parts of the elements characterising some of the concepts are redundant and therefore not really useful. Indeed, having both the attributes tom-:knows and P erson-:knows, or Class::T hing and Class::P erson is not useful as one of the attributes can be inferred from the other. Checking such a relationship between attributes, we reduce the definition of the intents of concepts to keep only the non-redundant ones as shown in Figure 1(b).

Using the Concept Lattice as a Query Interface

As mentioned before, the basic idea of our approach is that each concept of the concept lattice represents a question, with its intent being the components of the question, and its extent the answers. The goal is to use this lattice as the basis for a navigational interface to query the underlying dataset. The first step is therefore to provide a simple representation for each concept/question, which would be reasonably readable by a human user. We derive such a representation from the (non redundant) intent of a concept as a 'question' in pseudo-natural language, following the template:

What are the (C1, ..., Cn) that (p1 m1, ...pm mm) and that (n1 q1, ..., nt qt) where {C1, ...Cn} are extracted from attributes of the form Class::C1, ..., Class::Cn, {p1 m1, ...pm mm} are extracted from attributes of the form {p1:-m1, ...pm:-mm} and {n1 q1, ..., nt qt} are extracted from attributes of the form {q1-:n1, ..., qt-:nt}. We also adapt this general structure depending on whether or not one of the attribute sets is empty and the names of classes, properties and individuals are reduced to the local fragment of their URI, or to the label of the entity if available. For example, the concept at the bottom left of the lattice in Figure 1 Interpreting concepts as questions in this way means that the obtained lattice represents a complete hierarchy of questions that can be presented to the user as a query interface to the considered dataset (see the example Figure 2 where the question "What are the (Person)?" has been selected, showing the sub-questions, the super-questions, alternative questions about Tom's projects and interests, as well as the answers to the selected question).

However, while on our toy example the results are simple and easy to navigate, on a bigger dataset, this process can result in thousands of questions being generated. In the next section, we therefore investigate measures that can be used to identify a set of questions more likely to be of interest to a user, as a way to generate a reasonable entry point into a large question hierarchy.

MEASURING THE RELEVANCE AND IN-TERESTINGNESS OF A QUESTION

In order to identify approaches to find a set of questions more likely to be of interest to a user, we take inspiration from the works prominent in two areas: ontology summarisation and concept lattice simplification.

Measures Inspired from Ontology Summarisation

In [START_REF] Peroni | Identifying key concepts in an ontology through the integration of cognitive principles with statistical and topological measures[END_REF], we presented a work on extracting the key classes of a (possibly populated) ontology, based on a variety of different metrics taking into account in particular the "topology" of the ontology, its structure, and external elements such as the popularity of a concept. We look at three of these criteria which appear specially relevant:

Coverage. In ontology summarisation, this criterion intends to take into account the fact that a good summary should contain elements from all the significant parts of the ontology. This also appears important here, as we would expect any point of the lattice to be reachable from the identified questions, acting as entry points to the hierarchy. We define the set of questions reachable from another question using the notions of filter and ideal from FCA (or more generally, from lattice theory [START_REF] Birkhoff | Lattice Theory[END_REF]). The ideal of a concept is the set of all its direct or indirect subconcepts, or in other terms, all the concepts linked through the transitive closure of the ≤ relation. Similarly, the filter of a concept corresponds to the set of concepts that are reachable through the superconcept relation. We define the coverage of a question in our question hierarchy as the union of the filter and ideal of the corresponding concept, and indicate that a set of questions covers the dataset when the union of the coverages of its elements correspond to the entire lattice.

Level. To extract key classes from an ontology, one of the ideas is that key classes are never too general or too specific, but can be found in the middle layer of the hierarchy. A similar idea can be applied here, as a we can expect very general or very specific questions not to be the most useful to the user. We use a measure of the level of the question/concept of the hierarchy as the distance between the question/concept and the root concept.

Density. In ontology summarisation, one of the assumptions is that the richer the representation of a class is (i.e., the denser it is in terms of the properties attached to it) the more likely it is to be important. Here, the situation is slightly different, as the related notion of density (i.e., the number of attributes in the intent of the concept) is closely related to the one of level (the more specific a concept is, the more likely it is to have a large number of attributes). Therefore, we cannot assume density to be used as criterion to maximise, but rather as a metric which should be not too high (useful questions are probably not the most complex ones), but also not too low (useful questions should be sufficiently well defined).

Measures Inspired from FCA

There are only a few metrics that have been devised in FCA to try to identify the most "interesting" concepts. The most common one is the support, but a notion of stability, applicable both to the intent and the extent of a concept, has been recently discussed as a way to reduce a concept lattice, providing a possible measure to be applied to our problem.

Support. As already mentioned, the support of a concept is the cardinality of its extent, i.e., the number of objects it represents (and so the number of answers to the question). As noticed in [START_REF] Kuznetsov | Reducing the representation complexity of lattice-based taxonomies[END_REF] to motivate the stability measure, there are many scenarios where the most interesting concepts might not be the ones representing the largest number of objects. Here as well, an interesting question might be one with few answers, while questions with a large number of answers might be meaningless.

Intensional Stability. Intensional stability as described in [START_REF] Kuznetsov | Reducing the representation complexity of lattice-based taxonomies[END_REF] intends to define a stable concept as one whose "intent does not depend much on each particular object of the extent". Given a concept (O, A) where O is the extent and A is the intent, the degree of intensional stability σ i is defined by

σ i (O, A) = |{C⊆O|C =A}| 2 |A|
. However, as explained in [START_REF] Kuznetsov | Reducing the representation complexity of lattice-based taxonomies[END_REF], computing such a measure is complex. We therefore use an approximation, which corresponds to the ratio between the cardinality of the concept's extent and the one of the smallest of its direct super-concepts, i.e., σ i ap (O, A) = |O| min n∈N (|n|) , where N is the set of extents of the direct superconcepts of (O, A) in the lattice.

Extensional Stability. In a similar way as for intensional stability, extensional stability can be defined at the level to which the extent of a concept depends on a particular attribute of the intent. It is defined as

σ e (O, A) = |{C⊆A|C =O}| 2 |O|
and we use the following approximation: σ e ap (O, A) = |A| min b∈B (|b|) where B is the set of intents of the direct subconcepts of (O, A) in the lattice.

EXPERIMENT

While the previous section discusses measures that can be used to assess the potential "interestingness" of a question generated using our FCA-based method, we present here a user-based experiment to find out which of these measures are the most relevant and how to parametrize them. We asked 12 users with various degrees of familiarity with semantic technologies to inspect a reasonably large dataset and express up to 5 questions they believed to be interesting on this dataset.

Datasets

We used 4 different datasets as testbeds for our experiment. Three of them, called geography, jobs and restaurants were created by the University of Texas, Austin [START_REF] Tang | Using multiple clause constructors in inductive logic programming for semantic parsing[END_REF], and later transformed into OWL/RDF [START_REF] Kaufmann | Talking to the semantic web -natural language query interfaces for casual end-users[END_REF] for the purpose of evaluating a query answering system. The other one (drama) concerns modern productions of classical greek drama and was built locally for the needs of a project in the domain of Arts. Two of the evaluators for this dataset are actually domain experts involved with the data, with no background in semantic technologies. For each of the datasets, we constructed the concept lattice as explained earlier in this paper. Information about each dataset and the corresponding lattices is given in Table 1.

Results

Out of the 44 valid questions we obtained, 9 we tested that 27 (61%) matched the format of questions produced by our method, and therefore corresponded to questions/concepts in the generated lattices. In the questions that could not be represented we found several reasons why they diverged from our model, which could be considered as possible extensions in the future, including for example the use of disjunctive clauses (e.g., "Which Greek plays have been performed in Kenneth McLeish's translations or versions?") or of numerical manipulations/tests on values (e.g., "What are the restaurants that have ratings higher than 2.5?").

The resulting set of user-generated questions represent a useful sample to analyse the range of values taken by the different measures to be considered. Coverage is not evaluated here as it cannot be assessed at the level of an individual question. Since our goal is to obtain a set of questions as an entry points to the hierarchy, we consider coverage as a fundamental criterion to be enforced while generating the initial question set.

Level. Amongst all the valid and representable questions given by evaluators, the average level of a question in its lattice is 4.46. This is slightly higher than the average level of all the concepts in the lattices and it is also worth mentioning that none of the questions were at a level lower than 3 or higher than 7. This validates our hypothesis that questions of interest are generally not the most general, or the most specific, but are located within a small range around the "centre" of the lattice, which corresponds to the average level. We therefore define a normalised metric m l for a concept of our question hierarchy which is computed as the distance between the concept's level and the average level in the lattice.

Density. In the case of the density measure, our initial hypothesis was also verified that interesting questions tend to be defined simply, but with sufficient elements to represent a distinct set of answers. Indeed the average density of the valid, representable questions is 2.14, and the measure is always included in the range [1..3] (most of the questions being of density 2, such as "What are the restaurants in San Francisco?"). We can argue that there is a strong relationship between the level of a concept and the density of the question. However, this highly depends on the structure of the original dataset, as for example, "What are the restaurants in a city?" is more general than the previous question, while also being of density 2. We therefore define the normalised metric m d based on the difference between the density of a given concept and 2, which seems to be the "standard" for simple, but sufficiently defined questions.

Support. Depending on the dataset, the support of the provided questions can vary a lot. For example, questions in the jobs dataset tend to have a lot of answers (up top 3402), while in the drama dataset, they are generally smaller (from 2 to 38).

Intensional Stability. The expectation related to intensional stability is that the more stable a concept is, the more it is supposed to represent a significant and distinct set of individuals. However from our experiment, there does not seem to be any correlation between a question being identified by evaluators as interesting, and its intensional stability. Values can vary from very low (0.0008) to high (0.82) even for questions provided by a single user, regarding a single dataset.

Extensional Stability. Surprisingly, contrary to intensional stability, the values of extensional stability appear very stable, especially within one dataset, and always high (between 0.75 and 1.0), in particular if compared with the average in the dataset (around 0.4 for all of them). Indeed, it appears that the definition of the question as being a significant subset of the elements of more specific questions is an important criterion to identify interesting questions. Considering the results discussed above, we define an aggregated metric to rank questions in a question hierarchy as the linear combination of the 3 metrics m l , m d and σ e ap on concepts:

m(O, A) = w1.m l (O, A) + w2.m d (O, A) + w3.σ e ap (O, A)
What constitutes an interesting question to a dataset is very dependent on the user and the context in which the answer would be used, but based on the results obtained above, we expect such a metric to be adequate in supporting the identification of reasonable entry points to the question hierarchy.

IMPLEMENTATION AND VALIDATION

The overall method presented here can be divided in two separate processes: 1-the creation of the non-redundant hierarchy of question, and 2-the generation of the user interface based on this hierarchy and using the metric defined above. For the first process, we developed a program that generates a formal context in the input format of the lattice generation tool from a SPARQL endpoint, according to the method described in Section 3.2. We use the OWLIM triple store, 10 which partially supports OWL/RDF inferences. We use the implementation of the CHARM algorithm provided by the CORON tool [START_REF] Kaytoue | The Coron System[END_REF] to generate the concept lattice.

We devised a simple algorithm in order to identify in the generated lattice a set of questions that both rank high according to a chosen metric 11 and which, all together, maximally cover the lattice (by choosing questions which are 10 http://www.ontotext.com/owlim/ 11 A special case is considered for the support measure regarding the top -i.e., the root -of the hierarchy. It is indeed always the concept with the highest support, and is therefore excluded from the ranking. not in the same branch as an already chosen question). In order to validate the choice of the aggregated measure defined above, we tested it together with 5 other measures in 2 different datasets. We used as datasets the collection of 614 course descriptions and 1706 video podcasts from http://data.open.ac.uk. We generated the list of entry questions for each of these datasets using each of the following metrics: a random metric, m l (level) alone, m d (density) alone, support, σ e ap (stability) alone and the aggregated measure of level, density and stability, using a naive distribution of weights (i.e., w1 = w2 = w3 = 1

3 ). We then asked six different users to give a score between 1 and 5 to each of the sets of questions (presented in a random order), 5 corresponding to the highest level of interest.

The results are presented in Figure 3. As can be seen, the aggregated measure appears to provide significantly better results than all of the other measures on both datasets, especially compared to the random measure. As expected, the level, density and stability of questions all contribute to identifying interesting questions (to different extents), but are more appropriate when used in combination. More surprisingly, the support (i.e., number of answers) provide better results than could have been expected from our experiment. A possible explanation is that, in datasets where objects are described homogeneously (i.e., they all have more or less the same structure), support is highly correlated with the measures related to the question's level and density.

The application of the querying interface has already been shown in Figure 2 on our toy example. Figure 4 gives another example, based on the restaurant dataset. It is generated from the concept lattice using as initial questions the set computed using the aggregated measure. The value of this measure is represented in the interface by the font size used for the question. The first question is also attached to the questions directly more general and directly more specific. Any question displayed can be selected, and will then be re-displayed at the top of the list, with more general and more specific questions, as well as the set of its answers (for example, in Figure 4, the question "What are the (Restaurant) that (ratingString good)" has been selected).

RELATED WORK

As discussed previously, our approach relates to ontology summarisation, where an abstract summary of a supposedly complex ontology is being produced, for example in the form of a set of important concepts [START_REF] Peroni | Identifying key concepts in an ontology through the integration of cognitive principles with statistical and topological measures[END_REF]. In [START_REF] Zhang | Ontology summarization based on rdf sentence graph[END_REF], the authors propose a technique to extract a sub-graph of an RDF graph to act as a summary. Similar ideas have also been recently applied to large RDF datasets, including for example the ExpLOD tool [START_REF] Khatchadourian | Exploring RDF usage and interlinking in the linked open data cloud using ExpLOD[END_REF] which produces a visual representation of a dataset, clustering (and therefore abstracting) elements together to produce an overview graph of the dataset. As can be seen from these initial works, the idea of summarising datasets and ontologies is only starting to gain attention. While providing example queries is generally seen as an efficient way for somebody to quickly understand a dataset or an ontology, 12 to the best of our knowledge, there have not been any attempt before at summarising a dataset by providing sets of automatically extracted questions.

FCA, and especially concept lattices, have been used in several approaches to support the task of browsing structured datasets. For example, in the context of image search, [START_REF] Ducrou | An intelligent user interface for browsing and searching MPEG-7 images using concept lattices[END_REF] makes use of several lattices, representing different aspects of images (shape, luminance and "semantic content", with the "semantic content" aspect being based on an ontology). In this case, the lattices act as support for browsing the results of a search. In [START_REF] Ferre | Camelis: a logical information system to organize and browse a collection of documents[END_REF], the author develops a similar idea, using a concept lattice built from the metadata attached to documents, but makes use of logical concept analysis, a variant of FCA where the attributes are logical properties, partially ordered by a relation of subsumption. Other works have been devised that generate views on populated ontologies, which correspond to formal concepts that can be visualised as concept lattices, and be defined by users [START_REF] Tane | Query-based multicontexts for knowledge base browsing: An evaluation[END_REF]. A significant difference between these approaches and ours is that we focus on providing an overview of a dataset using the set of questions it can answer, and a navigation mechanism allowing to browse these questions, rather than the data itself. Closer to our work in that sense is the recent paper [START_REF] Ferre | Conceptual navigation in RDF graphs with SPARQL-like queries[END_REF]. Indeed, in this work, the author relies on the principles of FCA to provide a navigation mechanism based on queries to the underlying dataset. While here, we focus on providing a navigation interface to the data (through the questions), targeting users unfamiliar with both the data and the underlying technologies, [START_REF] Ferre | Conceptual navigation in RDF graphs with SPARQL-like queries[END_REF] concentrate on obtaining queries exploiting the high expressivity of the underlying language (close to the SPARQL language). Our approach also includes, as a core mechanism, the ability to identify sets of questions more likely to provide useful entry points to the dataset.

CONCLUSION

In this paper, we have presented an approach to generate a hierarchy of questions that could be asked to a dataset using formal concept analysis, and to derive a navigational query interface to this dataset based on this hierarchy. This approach relies on constructing a concept lattice from the description of the instances of the dataset, creating groups (concepts) of instances having common properties. However, for a large dataset, the number of these concepts (and so of the corresponding questions) can be very large. We also study the measures providing indications of the potential interest and relevance of an extracted question. Our experiment shows that the identified measures provide a good base to select a set of reasonably interesting questions to act as an entry point into the dataset.

One of the most obvious drawbacks of the approach presented here is the complexity of the methods deployed, especially ontological reasoning and concept lattice generation. Since these complex methods only need to be used once per dataset, in an offline process, the few minutes they take on our test datasets cannot be considered a strong limitation. However, some level of approximation and optimisation will have to be applied to use our tools on significantly larger datasets, containing several millions of statements.

There are many extensions that can be considered to the presented approach. Indeed, our experiment also identified some of the most common limitations of our model in terms of the expressiveness of the considered questions. Some of these elements, such as the possibility to add tests on numerical values, could be added to the model. They would however increase significantly the size of the lattice, and therefore the overall complexity of the approach.

Also, while the approach has been shown to provide promising results on self-contained datasets, an interesting future work would be to take into account elements derived from links to external datasets, making it possible to explore the questions that can be answered from integrating multiple sources of data.

  (b) is transformed into the question: What are the (Person) that (tom knows)

Figure 1 :

 1 Figure 1: Concept lattice generated from http://kmi.open.ac.uk/people/tom/rdf (a); with redundancy eliminated (b). In both figures, the bottom concept of the lattice has been omitted.

Figure 2 :

 2 Figure 2: Simple example of the concept lattice-based interface to querying a dataset.

Figure 3 :

 3 Figure 3: Average scores for the six tested measures on the Course and Podcast datasets.

Figure 4 :

 4 Figure 4: Example of application of the lattice-based query interface on the restaurant dataset.

Table 1 :

 1 Summary of the test datasets.

	Dataset	Nb. Instances Nb. Concepts
	geography	715	842
	jobs	4142	66284
	restaurants	9746	6810
	drama	19294	10083

http://protege.stanford.edu/

http://neon-toolkit.org

http://www.w3.org/RDF/

http://www.w3.org/TR/owl-ref/

http://www.w3.org/TR/rdf-sparql-query/

To avoid ambiguities in this paper, we use the term concept to refer to the notion of formal concept in FCA, and the term class to refer to the corresponding entities in ontologies

http://www.foaf-project.org/

In this simplified notation, we use the local ID or label of an entity, instance, property or class, instead of its full URI.

Some of the questions given by users could not be answered by a set of instances in the considered dataset. There was no overlap between the questions proposed by different users.

The system SchemaPedia (http://schemapedia.com/) for example gives manually created example queries for the ontologies it collects.

Acknowledgment

The authors would like to thank Amedeo Napoli, Mehdi Kaytoue-Uberall and Laszlo Szathmary for their help with the use of the CORON system and for the pointers to elements of formal concept analysis. We also thank Vanessa Lopez for telling us about some of the datasets included in our experiments, as well as all the evaluators who responded to our questionnaire.