Rakebul Hasan

Fabien Gandon

Summarized Explanations from Linked Justifications

Keywords: Explanation, justification, summarization, Linked Data, Linked Justifications Explication, justification, résumé, web des données liées, web des justifications liées

A user of a Semantic Web application may not trust its results because he may not understand how the application produces its results using distributed data and inferential capabilities. Explanation-aware Semantic Web applications provide explanations of their reasoning -explaining why an application has performed a given step or which information it has used to derive a new piece of information. However, providing too much and irrelevant information in explanations may overwhelm the users, especially the non-expert users. In this paper, we discuss an approach to explain reasoning over Linked Data. We introduce a vocabulary to describe justifications and we discuss how publishing justifications as Linked Data enables explaining reasoning over Linked Data. Finally, we discuss how to summarize explanations with relevant information taking into account user specified explanation filtering criterion.

Introduction

Semantic Web applications use inferential capabilities and distributed data in their reasoning. Users often find it difficult to understand how these applications produce their results. Hence, users often do not trust the results these applications produce. Explanation-aware Semantic Web applications provide explanations of their reasoning -explaining why an application has preformed a given step or which facts it used to derive a new fact. Explanations enable users to better understand reasoning of these application. Users have more details about how an application produce a given result or why it has performed a step in its reasoning. Explanations help users to decide whether to trust a result or an application.

The emergence of Linked Data enables large-scale reasoning over heterogeneous and distributed data. Explaining reasoning over Linked Data requires explaining how these distributed data were produced. Publishing also the explanation related metadata as Linked Data enables such explanations. Justifications are metadata about how a given piece datum is obtained. We introduce the concept of Linked Justification in this paper. We present a vocabulary to describe justifications and guidelines to publish these justifications as Linked Data.

The existing explanation-aware Semantic Web applications inherit explanation features from explanation-aware expert systems. These explanations are targeted to expert users, such as knowledge engineers, with detailed information about all the execution steps of reasoners of these applications. Unlike the expert systems, users of Semantic Web applications have diverse background -from expert knowledge engineers who are interested in every details of the reasoning, to regular users who do not have any background in reasoning, logic, or ontologies. These non-expert users might feel overwhelmed with all the execution details of reasoners. To address this issue, we provide summarized and relevant explanations to users. Users can specify their explanation filtering criterion -types of information they are interested in. We take into consideration the explanation filtering criterion when we present explanations and summarize explanations. We use centrality and similarity matrices to summarize and provide relevant explanations.

This paper is structured as follows: in Section 2, we present two motivating scenarios. We present the concept of Linked Justifications and how to generate explanations from Linked Justifications in Section 3. In Section 4, we present our approach to summarize explanations. In Section 5, we present an evaluation of our explanation summarization approach. Then in Section 6, we present the related work. Finally, we conclude and discuss the future work in Section 7.

Motivating Scenarios

In this section, we present explanation scenarios from two perspectives: (i) in subsection 2.1, need for explanations for expert users such as knowledge engineers(ii) in subsection 2.2, need for explanations for non-expert users such as regular end-users.

Explaining Large-Scale Reasoning over Linked Data

In the recent years, we have seen an increasing growth of publishing Linked Data. We have seen datasets published from community driven efforts, governmental bodies, scientific communities, and corporate bodies [START_REF] Bonatti | Robust and scalable linked data reasoning incorporating provenance and trust annotations[END_REF]. These datasets are interlinked 1 and use RDFS/OWL schemata. This presents opportunities of large-scale data integration and reasoning over cross-domain data. In this scenario, knowledge engineers might need explanations for debugging or understanding ontologies. In addition, performance related explanations can help knowledge engineers to optimize performance (e.g. identifying most frequent failure point in a query). In such a scenario with large ontologies, a knowledge engineer may want to focus on a specific part of an explanation with a lot of details. A knowledge engineer may want a short explanation to have a quick understanding. A real world example of this scenario would be FactForge2 . FactForge integrates data from some of the central datasets and materialize -the process of storing inferred knowledgethe inferred facts with respect to OWL 2 RL3 .

Explaining Smart Applications

Smart applications such as recommendation systems are potentially effective applications of the Semantic Web for end-users. Such an application can use inference and distributed data to produce its results. A users -without sufficient knowledge of ontology or knowledge engineering -of such a smart application may want to know why the application has produced an output or taken an action. The application should explain to justify its action in this scenario. However, providing explanations with too much details may overwhelm such a user. Smart applications should be able to provide easy to understand and concise explanations.

Linked Justifications

In this section, we first discuss how we can explain in in a distributed settings. We introduce the concept of Linked Justification. We present a vocabulary to publish justifications as Linked Data. Finally, we present an algorithm to generate explanations from Linked Justifications.

McGuinness et al. [START_REF] Mcguinness | Explaining answers from the semantic web: the inference web approach[END_REF] discuss the importance of distributed and portable justifications, and subsequently present justifications as user-friendly explanations. With the increasing growth of sharing Semantic Web data as part of the Linked Data [START_REF] Berners-Lee | Linked data. W3C Design Issues[END_REF] initiatives, it is important that data publishers can publish their data with explanation related metadata with ease. Explanation infrastructures should be able to accommodate common data publishing principles. Semantic Web explanation infrastructures should also address heterogeneous and distributed nature of the Web. With regard to diversity of different representation, explanation metadata should be published promoting interoperability. The W3C PROV-DM data model [START_REF] Moreau | PROV-DM: The PROV data model[END_REF] can be used as an interchange data model across different systems in this regard. Different systems can define their explanation metadata model as application-specific and domain-specific extensions of PROV-DM. Applications across the Web can then make sense of explanation metadata in a unified manner. Consumers of these explanation metadata can use explanation presentation and visualization tools according to their needs. Our work [START_REF] Hasan | Linking justifications in the collaborative semantic web applications[END_REF] on applying the Linked Data principles to publish explanation metadata -Linked Justifications -intent to address these issues.

Justifications are metadata about how a given piece of datum is obtained. In Linked Justifications approach, an application can obtain such a piece of datum from other data pieces published as Linked Data. These involved data pieces can be located anywhere in the Web. Publishing justification metadata as Linked Data enables explaining distributed reasoning by following the links between justifications for involved data in a reasoning. We present the Ratio4TA4 vocabulary for describing justifications. Data publishers can use Ratio4TA describe metadata about their data and publish this metadata as Linked Data.

Ratio4TA

Ratio4TA (inter linked justifications for triple assertions) is an OWL ontology for describing justifications. Ratio4TA allows data publishers to describe metadata about their data. For example, applications can describe their reasoning processes and links between their consumed and produced data using Ratio4TA.

Ratio4TA facilitates explanation of reasoning processes in a Web-scale. Applications can publish their data along with justification related metadata as Linked Data using Ratio4TA.

Other applications can consume these data with justification metadata and provide explanations about their consumed data -generated from the justification metadata of the consumed data. In this way, applications can provide explanations of distributed reasoning processes by following the links between justifications.

Ratio4TA extends the W3C PROV Ontology5 (specifically, PROV-O Working Draft 03 May 2012 6 ). This promotes interoperability by enabling data consumers process justification metadata according to W3C PROV standards.

Figure 1 shows the core concepts and relations of Ratio4TA. It allows to describe data, reasoning processes, results, data derivations, rules, and software application. In addition the JustificationAccount class allows to define named graph containers of justification statements. A detailed specification of Ratio4TA with examples is available in its website.

Explanations from Linked Justifications

We generate explanations from Linked Justifications by recursively following the links between involved justifications in a reasoning. Listing 1 shows an algorithm that recursively collects involved justification in for a derived RDF statement dst.

Algorithm 1 Generating explanation for an RDF statement if (depth > maxDepth) then end for 12: end procedure This algorithm crawls through the related justifications and constructs the derivation proof tree for a derived statement. We set a maximum depth limit to traverse by setting the global variable maxDepth. This is to avoid the algorithm falling into loops because of cyclic proof paths, or faulty justification metadata; also to allow generating proof tree with a maximum depth. We initially call procedure GenerateExplanation by setting dst to the derived statement for which we want to generate the proof tree, and by setting depth to 1 to start crawling from the depth one of the proof tree. Also, we initialize the set of justification statements JST = ∅ and the set of knowledge statements KST = ∅. Justification statements for a RDF statements are the justification metadata statements that justify the RDF statement. Knowledge statements for a RDF statement are the statements from which the RDF statement is derived. After the procedure GenerateExplanation finishes executing, the set of justification statements JST will contain all the justification statements in the proof tree for the initial derived statement dst. Similarly,the set of knowledge statements KST will contain all the knowledge statements in the proof tree for the initial derived statement dst. These two variables JST and KST are also global variables in our algorithm.

Line 2 checks the condition if the current depth exceeds the maximum depth and line 3 stops executing the current call of the procedure if the condition on line 2 holds. Line 5 collects all the justification statements for the current derived statement dst by calling GetJustification-MetaStatements and assigns the collected justification statements in the set CJST . The GetJustificationMetaStatements procedure collects the justification statements by following the r4ta:justifiedBy link for dst. Please note that GetJustificationMetaStatements should be made aware of where to find the r4ta:justifiedBy link for a derived RDF statement. This is a design decision for data publishers. As a common practice, data publisher for a dataset can specify inside a provenance container named graph which r4ta:JustificationAccount instance justifies which RDF statement and also publish the provenance container as Linked Data. Line 6 collects all the knowledge statements by calling GetRDFKnowledgeStatements and assigns the collected knowledge statements in the set CKST . The GetRDFKnowledgeStatements procedure collects all the knowledge statements from which the statement dst was derived by following the r4ta:derivedFrom links found in the current justification statements CJST . Line We call the derived RDF statement (dst in our algorithm initialization) that we are explaining, the root statement rs. We call the RDF graph formed by the set of knowledge statements union the root statement, the RDF knowledge graph KG:

KG = RDF Graph(KST ∪ rs)
We provide explanations in natural language for the RDF statements in KG. Our explanations also include the information of proof tree hierarchy. Figure 2 shows an example of our explanation for a derived statement that "Bob is a British Scientist". Each node of our explanation is an RDF knowledge statement. What we present in each node is a natural language representation of the RDF knowledge statement in that node. A node with children means that the RDF knowledge statement in that node is derived from the RDF knowledge statements of its children nodes.

This approach explains derivations of a given RDF statement with all the derivation steps upto a maximum depth in the derivation proof tree. However, explanations with the details of all the steps in a computation process may not be as useful for non-expert users as they are for expert users [START_REF] Angele | Ontology-based query and answering in chemistry: Ontonova project halo[END_REF][START_REF] Costabello | DC proposal: PRISSMA, towards mobile adaptive presentation of the web of data[END_REF][START_REF] Hasan | A Brief Review of Explanation in the Semantic Web[END_REF][START_REF] Mcguinness | Explaining answers from the semantic web: the inference web approach[END_REF]. Explanations should contain information with different degrees of detail taking into account the users' expertise [START_REF] Mcguinness | Explaining answers from the semantic web: the inference web approach[END_REF]. To address this issue, we propose providing summarized explanations with different size to different types of users. In next section, we discuss our approach to summarize explanations.

Summarizing Explanations

The users of Semantic Web applications can have different background, skill level, and knowledge level because of the open nature of the Web. Level of user expertise should be taken into account while providing explanations. The presentations of explanations can change according to user expertise or user scenario context. According to [START_REF] Angele | Ontology-based query and answering in chemistry: Ontonova project halo[END_REF], explanation-aware applications in the Semantic Web should provide explanations with the features of provision of explanation with different degrees of detail and filtering explanation paths. In this paper, we propose summarizing explanations for providing explanations with different degrees of details. Our summarizing approach can also filter information in summarized explanations using filtering criterion. These filtering criterion can be a description of context related information or descriptions of what types of information a user is interested in to consume in explanations. Our explanation summarization approach provides a platform for personalized explanations for different contexts, as discussed in [START_REF] Angele | Ontology-based query and answering in chemistry: Ontonova project halo[END_REF].

Given a RDF knowledge graph KG = (R, T ), where R is the set of resources and literals and T is the set of RDF statements. In addition, given the root statement rs, where KST = T \ rs, and the justification metadata statements JST. We provide summarized explanations by summarizing RDF statements from KST. We also use the term "oriented graph" to refer to KG throughout the paper. Consumers of our explanations can specify what kind information they are interested in. When we summarize an explanation, we take into consideration five aspect: (i) salience of RDF statements, (ii) similarity of RDF statements with respect to users' filtering criterion, (iii) abstract statements. (iv) subtree weight in proof tree -weight with respect to the proof tree, (v) coherence. We first describe the first four aspects below and then we describe how we re-rank our explanation statements by coherence.

Salient RDF Statements

The salience of an RDF statement indicates the importance of the RDF statement. We use degree centrality to compute salience of RDF statements. Degree centrality, C D , of a vertex in a graph is the number of links the vertex has. We use the normalized degree centrality when we compute salience of RDF statements. Normalized degree centrality, C DN , is the degree centrality divided by the maximum possible degree centrality. Given a graph G = (V, E), where V is the set of vertices, E is the set of edges, we compute C D (v) and C DN (v) for a vertex v ∈ V as following:

C D (v) = deg(v) C DN (v) = C D (v) maxC D (V )
Here the graph G = KG with V = R and E = T for computing C D and C DN . For a vertex v ∈ V , deg(v) is the number of links the vertex has. The value of maxC D (V ) is the maximum value from the set of all degree centrality values -i.e. from the set {C D (v): for each v ∈ V }. We compute the salience S SL (i) of an RDF statement i by taking the weighted average of the normalized degree centrality of the subject of the RDF statement and the normalized degree centrality of the object of the RDF statement in KG. We use equal weights for the weighted average. We compute S SL (i) of an RDF statement i ∈ KST as below:

S SL (i) = 0.5 × C DN (subjectOf (i)) + 0.5 × C DN (objectOf (i))
Here subjectOf (i) is the subject resource in RDF statement i, and objectOf (i) is the object resource or literal in RDF statement i. The S SL score gives us a collective importance score of an RDF statement depending on the degree centrality of the nodes, representing the subject and the object, in the oriented graph represented by KG. We did not use the centrality of the predicate of statement while computing S SL because we wanted an importance score representing the importance of the information in a statement but not the importance of the relation between the information.

Relevant RDF Statements

The consumers of our explanations can specify a set of classes, F ilter, as their filtering criterion. Users can select these classes from the union of classes in the schemata used to describe KG. We use SC to refer to this union of all the classes in the used schemata.

F ilter ⊆ SC

When we summarize explanations, we rank the more relevant statements to the concepts given in filtering criterion higher. We use the approximate query solving feature [START_REF] Corby | Ontology-based Approximate Query Processing for Searching the Semantic Web with Corese[END_REF] of Corese Semantic Web Factory 7 to compute similarity. Corese implements a similarity feature, as a SPARQL extension, to compute conceptual similarity between two classes in a schema based on their semantic distance. For a statement i and a set of classes as user filtering criterion F ilter, we compute similarity S SM (i, F ilter), as following:

S SM (i, F ilter) = 1 3 × similarity node (subjectOf (i), F ilter) + 1 3 × similarity node (predicateOf (i), F ilter) + 1 3 × similarity node (objectOf (i), F ilter)
7 http://wimmics.inria.fr/corese

Inria

For a statement i, subjectOf (i) returns the subject of the statement, predicateOf (i) returns the predicate of the statement, and objectOf (i) returns the object of the statement. We compute similarity node (j, F ilter) where j ∈ R ∪ SC as following:

similarity node (j, F ilter) = maxSimilarity type (j, F ilter) : if j ∈ SC similarity node (j, F ilter) = maxSimilarity type (typesOf (j), F ilter) :

if j / ∈ SC but j ∈ R maxSimilarity type (T ypes, F ilter) = max( {similarity type (m, F ilter) :
for each m ∈ T ypes})

similarity type (m, F ilter) = {similarity corese (m, n) : for each n ∈ F ilter}
In the above formalism, typesOf (j) for a resource j ∈ R gives us the set of classes T ypes ∈ SC of which j is an instance. For a class m T ypes and a class n ∈ F ilter, similarity corese (m, n) computes a similarity score between class m and n ranging from 0.0 to 1.0 where 1.0 represent exact match and 0.0 represents completely not similar. The S SM score for a statement with respect to F ilter indicates the similarity of the types of information specified in F ilter. One can also define other similar measures to match a description of a context with explanation information for providing context-aware explanations.

Abstract Statements Our abstraction measure resembles approaches using abstract information for summarizing texts [START_REF] Eduard | Text summarization[END_REF]. We consider a statement that is close to the root, rs, of the proof tree that JST represents is more abstract than a statement that is far from the root rs. A node in the proof tree represents an RDF statement in KG. A link in the proof tree represents a r4ta:derivedFrom link. We define the distance of a node in the proof tree from the root node as the level in which the node belongs. The root node belongs to level one in the proof tree. The root node is derived from the nodes in level two. A node in level two is derived from the linked nodes in level three, and so on. For a statement i ∈ KST , we compute the abstraction score, S AB (i), as following:

S AB (i) = 1 level(i)
The function level(i) gives the the level in which the statement i belongs in the proof tree.

Subtree Weight in Proof Tree

We also consider salience of the statements in KST with respect to their proof tree positions. We take all the subtrees of proof tree with root i ∈ KST . For a subtree with root i, we compute the subtree weight of the statement i by taking the average score of all the statements in that subtree.

S ST (i) = j∈subtree((i) score(j) | subtree((i) |
The subtree(i) function returns the subtree of proof tree with root i. The score(j) for a statement j here can be combinations of S SL (j), S SM (j, F ilter), and S AB (j). We discuss more about score(j) in ranking section.

Ranking

We rank the statements in KST by different combinations of their computed scores. Taking n statements, where n ≤| KST |, will give a summarized list of n statements which can explain rs. We compute the statement score, score(i) where i ∈ KST , by taking weighted average of different combinations of S SL (i), S SM (i, F ilter), and S AB (i) with equal weights .

For the most salient statements, we compute score(i) as following:

score(i) = S SL (i) (1)
We compute score(i) for the most salient and abstract statements as following:

score(i) = 0.5 × S SL (i) + 0.5 × S AB (i) (2)
For the most salient statements taking the user's filtering criterion, F ilter, into account, we compute score(i) as following:

score(i) = 0.5 × S SL (i) + 0.5 × S SM (i, F ilter) (3)
We compute score(i) for the most salient and abstract statements taking the user's filtering criterion, F ilter, into account as following:

score(i) = 1 3 × S SL (i) + 1 3 × S AB (i) + 1 3 × S SM (i, F ilter) (4)
For the most salient statements with respect to the proof tree positions of the statements, we compute score(i) as below:

score(i) = S ST (i) (5)
As we showed before, computation of S ST (i) requires already computed score(i). This score(i) values can be again combinations of S SL (i), S SM (i, F ilter), and S AB (i).

Re-Ranking by Coherence

In text summarization, an ideal summary will include coherent and readable texts [START_REF] Eduard | Text summarization[END_REF]. An ideal ontology summary should also be expressed in a coherent way [START_REF] Zhang | Ontology summarization based on RDF sentence graph[END_REF]. In our case, a RDF statement a is coherent to a RDF statement b if a is directly derived from b. The authors of [START_REF] Zhang | Ontology summarization based on RDF sentence graph[END_REF] discuss that it is not possible to satisfy the coherence requirement during the extraction process of a summary. They suggest re-ranking an ontology summary by coherence measure after the initial extraction process. We follow a similar approach to satisfy our coherence requirement. Let R is a ranked list of RDF statements by their scores; S is a list of already selected RDF statements in the summary; i is the next RDF statement to be selected. i should satisfy that:

i = arg max i∈R\S (0.5 × score(i) + 0.5 × reward(i, S))
In the above formalism, reward(i, S) is the amount of potential contribution value -ranging from 0.0 to 1.0 -of i to the total coherence of the summary of i is added to S. We compute reward(i, S) as following:

reward(i, S) = 1 - coherent(S) coherent(S ∪ i)

Inria

In a set of statements S, coherent(S) is the number of coherent statements. We define coherence of an RDF statement in KST with respect to the positions of the statements in the proof tree that the statements in JST represents. The RDF statements a and b are coherent if the following condition hold:

(name(a) r4ta:derivedFrom name(b)) ∈ JST where a ∈ KST and b ∈ KST Here name(k) is the name of the statement k. As we discuss earlier, we used named graphs to assign unique names to each statements. (name(a) r4ta:derivedFrom name(b)) represents an RDF statement with name(a) as the subject, r4ta:derivedFrom as the predicate, and name(b) as the object of the statement.

Evaluation

Our evaluation methodology builds on ontology summary evaluation [START_REF] Li | Evaluations of user-driven ontology summarization[END_REF] and text summary evaluation methodologies [START_REF] Eduard | Text summarization[END_REF][START_REF] Steinberger | Evaluation measures for text summarization[END_REF]. Generally, evaluating summarizing technologies include measuring the agreement between human-generated summaries -known as "ground truths" -and automatically generated summaries.

In this section, we present the evaluation of our explanation summarization methodology. We preformed a survey to find ground truth summaries of explanations. We then measured the agreement between the automatically generated summarized explanations by our methodology and the ground truth summarized explanations using evaluation measures drawn from the information retrieval and summary evaluation literatures.

Evaluation Context

For the purpose of our study, we selected a subset of geographical locations from GeoNames8 and a subset of artists, events, and places from DBPedia9 , then derived new information from these selected subsets. Our ad-hoc reasoner infers new RDF statements with respect to RDFS type propagation; and owl:sameAs and transitivity of parentFeature property of GeoNames schema. For example, given the statements: geonames :3017382 owl : sameAs dbpedia : France . geonames :2985244 gno : parentFeature geonames :3017382.

The reasoner infers the following statement:

geonames :2985244 gno : parentFeature dbpedia : France .

Assuming the following statements are also given: geonames :6447113 gno : parentFeature geonames :2985244. geonames :6447113 owl : sameAs dbpedia : Carry -le -Rouet .

The reasoner infers:

dbpedia : Carry -le -Rouet gno : parentFeature dbpedia : France . Now, suppose that DBPedia specifies Nina Simone's death place as Carry-le-Rouet: dbpedia : Nina_Simone dbpedia -owl : deathPlace dbpedia : Carry -le -Rouet .

And our reasoner inferred that Carry-le-Rouet is part of France. Therefore, the reasoner can infer that Nina Simone died in France, even though it was not originally specified in our initial data:

dbpedia : Nina_Simone dbpedia -owl : deathPlace dbpedia : France .

In addition to inferring new statements, our reasoner generates justification for each derivation it performs. We generate explanations in natural language from these justifications by using the labels involved classes, instances, and properties.

In a test case, we give the participants a query and the answer for the query with its explanation all in natural language. We ask the participants to rate the effectiveness of each of the statements in the explanation from a range of 1 to 10. As our algorithms can take users' filtering criterion and provide relevant explanations to the concepts provided in filtering criterion, we give the the same query, answer, and the explanation for the answer but this time with a user's filtering criteria class taken from the schemata used in the reasoning process. We ask the participants again to rate the effectiveness of each of the statements in the explanation from a range of 1 to 10.

The rankings of the explanation statements produced by their ratings are the ground truths for our study. We used one test case for this study. We surveyed 9 people from different backgrounds: 4 computer scientists, 1 journalist, 1 psychologist, 1 biologist, and 1 business administrator. 44% of the participants were female and 56% of them were male. 56% had knowledge of RDF and 44% did not have any knowledge of RDF. The ages of the participants range from 22 to 31.

Evaluation Matrices

Cosine Similarity

We use cosine similarity to measure agreements between ratings produced by the survey participants. Cosine similarity, CSM , between two vectors x and y is defined as:

CSM (x, y) = x • y x y
The cosine similarity value ranges from -1 to 1. The value -1 means exactly opposite, the value 1 means exactly the same, and the value 0 indicates independence. We consider a participant's rating scores for all statements in an explanations as a vector. We interpret the cosine similarity between two such rating vectors as the agreement between the two associated ratings.

Compression Ratio

Given an explanation E and the summary S for this explanation. Compression Ration CR is the ratio of the size of the summarized explanation S to the size of original explanation E:

CR = size(S) size(E)
CR represents a normalized size of the summarized explanation. A good summary of an explanation will have a low CR and a high rate of important information of the original explanation where importance is defined by the users [START_REF] Eduard | Text summarization[END_REF]. Below, we discuss a few more measures which allow us to understand this notion of importance with respect to the opinions of users.

Inria

Normalized Discounted Cumulative Gain

The discounted cumulative gain (DCG) [START_REF] Järvelin | Cumulated gain-based evaluation of IR techniques[END_REF][START_REF] Mcsherry | Computing information retrieval performance measures efficiently in the presence of tied scores[END_REF] measures the quality of results of an Information Retrieval (IR) system in a ranked list. DCG assumes that judges have graded each item in a list of results. Using these grades, DCG measures the usefulness, or gain, of a ranked list of results. DCG penalizes high quality results appearing lower in a ranked list of results. Given the grades of items in a list result -rel i representing the grade of the result at position i, DCG at rank p is defined as:

DCG p = rel 1 + p i=2 rel i log 2 (i)
Normalized Discounted Cumulative Gain (nDCG) allows to calculate and compare this measure across multiple lists of results where each of the lists might have different length. nDCG at rank p is computed by dividing DCG p by the maximum possible DCG at rank p -also known as Ideal Discounted Cumulative Gain (IDCG) at rank p:

nDCG p = DCG p IDCG p
nDCG values are in the interval 0.0 to 1.0. For a ranked list, a nDCG p value of 1.0 means that the ranking is perfect at rank p with respect to the ideal ranking produced by ranking the results based on grades. A nDCG p value of 0.0 means that the ranking is completely imperfect p with respect to the ideal ranking. In our evaluation, we convert the normalized size of the summary CR for different summaries to p as below:

p = CR * size(E)
This allows us to compare different summaries with different compression ratios -hence with different p -using nDCG.

Our algorithms produce ranked list of explanation statements. We consider the rating scores by the participants as grades. The average of ratings by all the participants for a statement s gives us the ground truth rating for s. For n survey participants, we compute the ground truth rating rel i for a statement at position i of a ranked list of explanation statements as below:

rel i = n j=1 rating(i, j) n
In the above formalism, rating(i, j) represents the rating for the statement at position i in a ranked list of explanation statements by survey participant j.

Recall, Precision, and F-score

We measure the performance of our summarization algorithms using Recall and P recision composite scores as in text summarization [START_REF] Eduard | Text summarization[END_REF]. Recall and Precision quantify how closely the summarized explanations generated by algorithms correspond to the human produced summarized explanations. For each summary, we let correct = the number of statements selected by the algorithm and the human; wrong = the number of statements selected by the algorithm but not by the human; and missed = the number of statements selected by the human but not by the algorithm. We calculate Recall and P recision scores as below:

Recall = correct correct +

P recision = correct correct + wrong

Recall reflects how many good statements the algorithm missed, and P recision reflects how many of the algorithm's selected statements are good.

F-score is a composite measure of Recall and P recision. We use the basic F-score discussed in [START_REF] Steinberger | Evaluation measures for text summarization[END_REF]:

F = 2 × P recision × Recall P recision + Recall

Analysis of Ground Truths

As we discuss before, our ground truths are the rankings of the explanation statements produced by their ratings. We compute the agreement between two ground truths by computing cosine similarity between their ratings. Table 1 shows the agreement among the survey participants for the two scenarios -without F ilter and with F ilter -we evaluate for a test case. Each entry shows the average agreement between a survey participant to the other survey participants. The rightmost column shows the total average agreement for a scenario. The average agreements for both the scenarios are high. However, with F ilter the participants agree less. In the scenario with F ilter, the participants have to also consider the extra factor of similarity to the concepts provided as user filtering criterion. This contributes to the lower agreement when user filtering criterion are given. From these high agreements, we can conclude that the survey participants highly agree on what is effective as an explanation.

Evaluation of Explanation Summarization Measures

For the two scenarios -without F ilter and with F ilter, we take different combinations of our measures S SL , S ST , and S AB . In the case of with F ilter, we do the filtering using S SM , and therefore S SM is combined with the different combinations of our measures. Finally, we re-rank by coherence the ranked list of explanation statements produced by the different combinations of measures for both without F ilter and with F ilter scenarios. In the figures, re-rank is shown as S CO .

We compute the gold standard ranking of the statements of an explanation by ranking the statements by their average ratings -i.e. the ground truth ratings. As we have two scenarios (without and with F ilter), we have two gold standard rankings. The gold standard rankings reflect the collective opinions of survey participants.

For the case of without F ilter, we also evaluate sentence graph summarization [START_REF] Zhang | Ontology summarization based on RDF sentence graph[END_REF]. As the authors suggest, we use 0.8 as the navigational preference p value. We denote sentence graph summarization as S SG . We do not consider sentence graph summarization for with F ilter scenario because sentence graph summarization does not provide a feature for filtering information based on ontology concepts as filtering criterion.

Figure 3 shows the nDCG values of different combinations of our summarization measures, and the sentence graph summarization for summaries with different sizes for the scenario of without F ilter. In the x-axis, we have compression ratio CR. The y-axis represents nDCG. The measures salience + abstraction + coherence (S SL + S AB + S CO ) and salience + abstraction + subtree weigh + coherence (S SL + S AB + S ST + S CO ) gives the best results for the scenario of without F ilter. This means that the participants consider central (with respect to the oriented graph and the proof tree), abstract, and coherent information as effective information in explanation summaries. The nDCG values in the CR value interval 0.05 to 0.2 are particularly interesting for these two combinations of measures because we have small summaries with very similar rankings to the gold standard rankings. For the CR value interval 0.05 to 0.15, nDCG values are 1.0 for these two combinations, meaning the rankings are perfect rankings with respect to the gold standard rankings. The nDCG for the rest of the CR values for these two combinations are also close to 1.0. This means that for the rest of the CR values, these two combinations produce similar rankings to the gold standard rankings. The sentence graph summarization algorithm performs poorly for summarizing explanations. For a short summary, CR interval 0.05 to 0.2, the best nDCG value as low as 0.52. This shows that our explanation summarization algorithms perform significantly better than sentence graph summarization algorithm when there is no filtering criterion.

Inria

Figure 4 shows the nDCG values of different combinations of our summarization measures with F ilter for summaries with different sizes. We use the S SM measure to filter information similar to concepts in F ilter. For this reason, all the combinations in this case have S SM measure.

For the scenario of with F ilter, the combination salience + similarity + coherence (S SL + S SM +S CO ) performs best. This means that the survey participants consider central (with respect to oriented graph), similar (with respect to the concepts in F ilter), and coherent information as effective information in the summarized explanations. The nDCG values in the CR value interval 0.05 to 0.2 are particularly interesting this combination of measures because in this interval we have small summaries with very similar rankings to the gold standard rankings. For the CR values after this interval, the nDCG values are also high, ranging from 0.8 to 0.95. However, the best performance in the scenario of with F ilter is not as good as the best performance in the scenario of without F ilter. This is again due to the fact that the survey participants had to consider the extra factor of similarity. Similarity is a very broad concept and peoples opinions about similarity vary greatly [START_REF] Euzenat | Ontology matching[END_REF][START_REF] Kiefer | The fundamentals of isparql -a virtual triple approach for similarity-based semantic web tasks[END_REF]. It is hard to develop algorithms with a common understanding of similarity. Therefore, our algorithms perform a little worse in the scenario when they filter information using similarity than the scenario when there is no filtering using similarity.

Evaluation of Summaries of Explanation

We evaluate the quality of summarized explanations by comparing them to gold standard summarized explanations. We generate the gold standard summarized explanation for an explanation by taking statements with ground truth ratings greater than or equals to a threshold value th where the ground truth rating for each statement is scaled to 1.0. We set th to 0.6 for our gold standard summarized explanations. This allows us to get the top statements rated by the survey participants for a given explanations.

We use F-score to measure the quality of summarized explanations. F-score reflects accuracy with respect to the gold standard summary. A desirable situation would a summarized explanation with high F-score value and low CR value. As in the evaluation of measures in subsection 5.4, we have the same scenarios (without and with F ilter) and the same combinations of measures. We have two gold standard summarized explanations generated with th set to 0.6.

Inria

Figure 5 shows compression ratio of summarized explanations against F-score for the scenario without F ilter. Figure 6 shows compression ratio of summarized explanations against F-score for the scenario with F ilter. As Figure 5 shows for the scenario without F ilter, we get the best F-score of 0.83 when CR value is 0.35 by the measure combination salience + abstraction + subtree weight (S SL + S AB + S ST ). However, the F-Score values of 0.75 and 0.80 respectively for CR values 0.15 and 0.25 by the measure combinations salience + abstraction + coherence (S SL + S AB + S CO ) and salience + abstraction + subtree weigh + coherence (S SL + S AB + S ST + S CO ) are more desirable because the size of the summaries are smaller. This again confirms that the participants consider central (with respect to the oriented graph and the proof tree), abstract, and coherent information as effective information in explanation summaries. The sentence graph summarization again performs worst with a best F-score value of 0.25 in the CR interval 0.1 to 0.3. This shows that our summarized explanations are significantly more accurate than the summarized explanations generated by sentence graph summarization algorithm when there is no filtering criterion.

For the scenario with F ilter, the best F-score value 0.6 is lower than the best F-score value 0.83 for the scenario without F ilter. This is again due to the fact that the survey participants had to consider the extra factor of similarity to filter information in the explanations. The measure combination salience + similarity + coherence (S SL + S SM + S CO ) achieves the F-score value 0.6 when the CR value is 0.15. This is a desirable situation because the size of the summary is small. This again confirms that survey participants consider central (with respect to the oriented graph), similar (with respect to the concepts in F ilter), and coherent information as effective information in the summarized explanations.

Related Work

According to our knowledge, there is no comparable published work on summarizing explanations in the Semantic Web. But researchers have studied ontology summarization. RDF Sentence graph based summarization [START_REF] Zhang | Ontology summarization based on RDF sentence graph[END_REF] extracts RDF Sentences based on centrality measures. Our work has a similar approach to sentence graph summarization approach. However, we define new measures for summarizing explanations. Peroni et al. [START_REF] Peroni | Identifying key concepts in an ontology, through the integration of cognitive principles with statistical and topological measures[END_REF] discuss how to identify key concepts in an ontology. They draw summarization criterion from cognitive science (natural categories), network topology (density and coverage), and lexical statistics (term popularity). Alani et al.

Conclusion and Future Work

In this paper, we discuss generating explanations from Linked Justifications. We present an approach to summarize these explanations. We presented five different measures to summarize explanations. We compared different combinations of these measures to evaluate our summarized explanations. The evaluation showed that the combinations of salience, abstraction, and coherence; salience, abstraction, subtree weigh, and coherence; and salience, similarity, and coherence have good performances.

In the future work, we would like to explore how we can effectively present explanations Inria and summarized explanations using different kinds of user interfaces and user interactions. We would like to explore how we can effectively use the summarization rankings while presenting information in personalized and context dependent summarized explanations. In addition, we would are going to evaluate if explanations and summarized explanations are useful for the end-users.

Figure 1 :

 1 Figure 1: The core classes and properties of Ratio4TA.

Inria

1 :

 1 procedure GenerateExplanation(dst, depth) 2:

8 :

 8 KST = KST ∪ CKST 9:for each statement in CKST do 10:GenerateExplanation(statement, depth + 1) 11:

Figure 2 :

 2 Figure 2: Example of a proof tree-based explanation.

Inria

7

  updates JST by a set union with already collected justification statements and CJST . Line 8 updates KST by a set union with already collected knowledge statements and CKST . Line 9 to 11 call the the GenerateExplanation procedure for each knowledge statement found in CKST (i.e. the current set of knowledge statements) by increasing depth by 1.

Figure 3 :

 3 Figure 3: Quality of rankings produced by various combinations summarization measures without F ilter.

Figure 4 :

 4 Figure 4: Quality of rankings produced by various combinations summarization measures with F ilter.

Figure 5 :

 5 Figure 5: Compression ratio (CR) vs F-score without F ilter.

Figure 6 :

 6 Figure 6: Compression ratio (CR) vs F-score with F ilter.

  [START_REF] Alani | Winnowing ontologies based on application use[END_REF] discuss shrinking an ontology by analyzing the usage of the ontology.Alani et al. analyze the query log against an ontology to understand the important parts of the ontology. The work of Peroni et al. and Alani et al. focus on a concept level summarization of ontologies. In contrast, our focus is on statement level.

Table 1 :

 1 Agreements between ground truths measured by cosine similarity.

	missed

RR n°8279

See http://richard.cyganiak.de/2007/10/lod/ for a graph of these datasets and their interlinkage.

http://factforge.net/

http://www.w3.org/TR/owl2-profiles/#OWL_2_RL Inria

http://ns.inria.fr/ratio4ta/

http://www.w3.org/TR/prov-o/

http://www.w3.org/TR/2012/WD-prov-o-20120503/ RR n°8279

http://www.geonames.org/

http://dbpedia.org/ RR n°8279

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Acknowledgements

The work presented in this paper is supported by the CONTINT program of French National Agency for Research (ANR) under the Kolflow project (ANR-2010-CORD-021-02).


M J Fadili

J.-L Starck

J Bobin

Y Moudden

Image decomposition and separation using sparse representations: an overview

Keywords: Sparse representations, image decomposition, blind source separation, morphological component analysis

This paper gives essential insights into the use of sparsity and morphological diversity in image decomposition and source separation by overviewing our recent work in this field. The idea to morphologically decompose a signal into its building blocks is an important problem in signal processing and has far-reaching applications in science and technology. Starck et al. [1], [2] proposed a novel decomposition method -Morphological Component Analysis (MCA) -based on sparse representation of signals. MCA assumes that each (monochannel) signal is the linear mixture of several layers, the so-called Morphological Components, that are morphologically distinct, e.g. sines and bumps. The success of this method relies on two tenets: sparsity and morphological diversity. That is, each morphological component is sparsely represented in a specific transform domain, and the latter is highly inefficient in representing the other content in the mixture. Once such transforms are identified, MCA is an iterative thresholding algorithm that is capable of decoupling the signal content. Sparsity and morphological diversity have also been used as a novel and effective source of diversity for blind source separation (BSS), hence extending the MCA to multichannel data. Building on these ingredients, we will overview the Generalized MCA (GMCA) introduced by the authors in [3], [4] as a fast and efficient BSS method. We will illustrate the application of these algorithms on several real examples. We conclude our tour by briefly describing our software toolboxes made available for download on the Internet for sparse signal and image decomposition and separation.

I. INTRODUCTION

Although Mathematics has it million-dollar problems, in the form of Clay Math Prizes, there are several Billion Dollar problems in signal and image processing. Famous ones include the cocktail party problem (separate a speaker voice from a mixture of other recorded voices and background sounds at a cocktail party).

These signal processing problems seem to be intractable according to orthodox arguments based on rigorous mathematics, and yet they keep cropping up in problem after problem.

One such fundamental problem involves decomposing a signal or image into superposed contributions from different sources; think of symphonic music which may involve superpositions of acoustic signals generated by many different instruments -and imagine the problem of separating these contributions. More abstractly, we can see many forms of media content that are superpositions of contributions from different 'content types', and we can imagine wanting to separate out the contributions from each. We can easily see a fundamental problem; for example an N -pixel image created by superposing K different types offers us N data (the pixel values) but there may be as many as N • K unknowns (the contribution of each content type to each pixel).

Traditional mathematical reasoning, in fact the fundamental theorem of linear algebra, tells us not to attempt this: there are more unknowns than equations. On the other hand, if we have prior information about the underlying object, there are some rigorous results showing that such separation might be possible -using a sparsity prior.

The idea to morphologically decompose a signal into its building blocks is an important problem in signal and image processing. Successful methods for signal or image separation can be applied in a broad range of areas in science and technology including biomedical engineering, medical imaging, speech processing, astronomical imaging, remote sensing, communication systems, etc. An interesting and complicated image content separation problem is the one targeting decomposition of an image to texture and piece-wise-smooth (cartoon) parts. A functional-space characterization of oscillating textures was proposed in [START_REF] Meyer | Oscillating patterns in image processing and in some nonlinear evolution equations[END_REF], and was used for variational cartoon+texture image decomposition [START_REF] Vese | Modeling textures with total variation minimization and oscillating patterns in image processing[END_REF]. Since then, we have witnessed a flurry of research activity in this application field.

In [START_REF] Starck | Image decomposition via the combination of sparse representatntions and variational approach[END_REF], [START_REF]Redundant multiscale transforms and their application for morphological component analysis[END_REF], the authors proposed a novel decomposition method -Morphological Component Analysis (MCA) -based on sparse representation of signals. MCA assumes that each signal is the linear mixture of several layers, the so-called Morphological Components, that are morphologically distinct, e.g. sines and bumps. The success of this method relies on the assumption that for every component behavior to be separated, there exists a dictionary of atoms that enables its construction using a sparse representation. It is then assumed that each morphological component is sparsely represented in a specific transform domain. And when all transforms (each one attached to a morphological component) are amalgamated in one dictionary, each one must lead to sparse representation over the part of the signal it is serving, while being highly inefficient in representing the other content in the mixture. If such dictionaries are identified, the use of a pursuit algorithm searching for the sparsest representation leads to the desired separation. MCA is capable of creating atomic sparse representations containing as a by-product a decoupling of the signal content.

Over the last few years, the development of multi-channel sensors motivated interest in methods for the coherent processing of multivariate data. Consider a situation where there is a collection of signals emitted by some physical sources. These could be, for example, different brain areas emitting electric signals; people speaking in the same room, thus emitting speech signals; or radiation sources emitting their electromagnetic waves. Assume further that there are several sensors or receivers. These sensors are in different positions, so that each records a mixture of the original source signals with different weights. The so-called blind source separation (BSS) problem is to find the original sources or signals from their observed mixtures, without prior knowledge of the mixing weights, and by knowing very little about the original sources. Some specific issues of BSS have already been addressed as testified by the wide literature in this field. In this context, as clearly emphasized by previous work, it is fundamental that the sources to be retrieved present some quantitatively measurable diversity or contrast (e.g. decorrelation, independence, morphological diversity, etc). The seminal work of [START_REF] Zibulevsky | Blind source separation by sparse decomposition[END_REF], [START_REF] Bofill | Underdetermined blind source separation using sparse representations[END_REF] paved the way for the use of sparsity in BSS. Recently, sparsity and morphological diversity have emerged as a novel and effective source of diversity for BSS both for underdetermined and overdetermined BSS; see the comprehensive review in [START_REF] Bobin | Blind source separation : The sparsity revolution[END_REF]. Building on the sparsity and morphological diversity ingredients, the authors proposed the Generalized MCA (GMCA) as a fast and efficient multichannel sparse data decomposition and BSS method [START_REF] Bobin | Sparsity and morphological diversity in blind source separation[END_REF], [START_REF] Bobin | Blind source separation : The sparsity revolution[END_REF], [START_REF] Bobin | Morphological diversity and sparsity for multichannel data restoration[END_REF].

A. Organization of the paper

Our intent in this paper is to overview the recent work in monochannel image decomposition and multichannel source separation based on the concepts of sparsity and morphological diversity. The first part of the paper is devoted to monochannel sparse image decomposition, and the second part to blind sparse source separation.

In this review, our goal is to highlight the essential concepts and issues, and to describe the main algorithms.

Several applications to real data are given in each part to illustrate the capabilities of the proposed algorithms.

We conclude our tour by providing pointers to our software toolboxes that implement our algorithms and reproduce the experiments on sparse signal and image decomposition and source separation.

B. Notations

The ℓ p -norm of a (column or row) vector x is x p := ( i |x[i]| p ) 1/p with the usual adaptation when p = ∞, and x 0 := lim p→0 x p p is the ℓ 0 pseudo-norm, i.e. the number of nonzero components. Bold symbols represent matrices and X T is the transpose of X. The Frobenius norm of X is X F = Trace X T X 1/2 . The k-th entry of y i (resp.

y j ) is y i [k] (resp. y j [k])
, where y i is the i-th row and y j is the j-th column of Y. An atom is an elementary signal-representing template. Examples might include sinusoids, monomials, wavelets,

Gaussians. A dictionary Φ = [φ 1 , • • • , φ L ]
defines a N × L matrix whose columns are unit ℓ 2 -norm atoms φ i . When the dictionary has more columns than rows, it is called overcomplete or redundant. We are mainly interested here in overcomplete dictionaries.

II. MONOCHANNEL SPARSE IMAGE DECOMPOSITION

A. Morphological Component Analysis

Suppose that the N -sample signal or image x is the linear superposition of K morphological components, possibly contaminated with noise

y = K k=1 x k + ε, σ 2 ε = Var[ε] < +∞ .
The MCA framework aims at solving the inverse problem that consists in recovering the components

(x k ) k=1,••• ,K
from their observed linear mixture as illustrated in the top of Fig. 1. MCA assumes that each component x k can be sparsely represented in an associated basis Φ k , i.e.

x k = Φ k α k , k = 1, . . . , K ,
where α k is a sparse coefficient vector (sparse means that only a few coefficients are large and most are negligible). Thus, a dictionary can be built by amalgamating several transforms

(Φ 1 , • • • , Φ K ) such that,
for each k, the representation of x k in Φ k is sparse and not, or at least not as sparse, in other Φ l , l = k.

In other words, the sub-dictionaries (Φ 1 , • • • , Φ K ) must be mutually incoherent. Thus, the dictionary Φ k plays a role of a discriminant between content types, preferring the component x k over the other parts. This is a key observation for the success of the separation algorithm. Owing to recent advances in computational harmonic analysis, many novel representations, including the wavelet transform, curvelet, contourlet, steerable or complex wavelet pyramids, were shown to be very effective in sparsely representing certain kinds of signals and images. Thus, for decomposition purposes, the dictionary will be built by taking the union of one or several (sufficiently incoherent) transforms, generally each corresponding to an orthogonal basis or a tight frame.

However, the augmented dictionary

Φ = [Φ 1 • • • Φ K ] will provide an overcomplete representation of x.
Because there are more unknowns than equations, the system x = Φα is underdetermined. Sparsity can be used to find a unique solution, in some idealized cases; there is an extensive literature on the subject and the interested reader may refer to the comprehensive review paper [START_REF] Bruckstein | From sparse solutions of systems of equations to sparse modeling of signals and images[END_REF].

In [START_REF] Starck | Image decomposition via the combination of sparse representatntions and variational approach[END_REF], [START_REF]Redundant multiscale transforms and their application for morphological component analysis[END_REF], it was proposed to solve this underdetermined system of equations and recover the morphological components (x k ) k=1,••• ,K by solving the following constrained optimization problem: where α p p is the penalty quantifying sparsity (the most interesting regime is for 0 ≤ p ≤ 1), and τ is typically chosen as a constant times √ N σ ǫ . The constraint in this optimization problem accounts for the presence of noise and model imperfection. If there is no noise and the linear superposition model is exact (τ = 0), an equality constraint is substituted for the inequality constraint. This formulation is flexible enough to incorporate external forces that direct the morphological components to better suit their expected content, these forces will fine tune the separation process to achieve its task. As an example for such successful external force, [START_REF] Starck | Image decomposition via the combination of sparse representatntions and variational approach[END_REF] proposed to add a Total Variation (TV) penalty [START_REF] Rudin | Nonlinear total variation noise removal algorithm[END_REF] to the cartoon part in order to direct this component to fit the piecewise-smooth model.

min α1,••• ,αK K k=1 α k p p such that y - K k=1 Φ k α k 2 ≤ τ , (1)

B. MCA algorithm

Problem (1) is not easy to solve in general, especially for p < 1 (for p = 0 it is even NP-hard). Nonetheless, if all components x l = Φ l α l but the k-th are fixed, then it can be proved that the solution α k is given by hard thresholding (for p = 0) or soft thresholding (for p = 1) the marginal residuals r k = yl =k Φ l α l .

These marginal residuals r k are relieved from the other components, and are likely to contain mainly the salient information of x k . This intuition dictates a coordinate relaxation algorithm that cycles through the components at each iteration and applies a thresholding to the marginal residuals. This is what justifies the

= [Φ 1 • • • Φ K ],
number of iterations N iter , stopping threshold λ min , threshold update schedule. Initialization:

• Initial solution x (0) k = 0, ∀k. • Initial residual r (0) = y. • Initial threshold: let k ⋆ = max k Φ T k y ∞ , set λ (0) = max k =k ⋆ Φ T k y ∞ . Main iteration: for t = 1 to N iter do for k = 1 to K do Compute marginal residuals r (t) k = r (t-1) + x k . Update k-th component coefficients by thresholding α (t) k = TH λ (t-1) Φ T k r (t) k . Update k-th component x (t) k = Φ k α (t) k . Update the residuals r (t+1) = y -K k=1 x (t)
k . Update the threshold λ (t) according to the given schedule. if λ (t) ≤ λ min then stop.

Output: Morphological components x (Niter) k k=1,••• ,K .
Beside coordinate relaxation, another important ingredient of MCA is iterative thresholding with varying threshold. Thus, MCA can be viewed as a stagewise hybridization of matching pursuit (MP) [START_REF] Mallat | Matching pursuits with time-frequency dictionaries[END_REF] with blockcoordinate relaxation (BCR) [START_REF] Sardy | Block coordinate relaxation methods for nonparametric wavelet denoising[END_REF] to (approximately) solve [START_REF] Starck | Image decomposition via the combination of sparse representatntions and variational approach[END_REF]. The adjective stagewise is because MCA exploits the fact that the dictionary is structured (union of transforms), and the atoms enter the solution by groups rather than individually unlike MP. As such, MCA is a salient-to-fine process where at each iteration, the most salient content of each morphological component is iteratively computed. These estimates are then progressively refined as the threshold λ decreases towards λ min .

In the noiseless case, a careful analysis of the recovery properties (uniqueness and support recovery) of MCA algorithm and its convergence behavior when all Φ k are orthobases can be found in [START_REF] Bobin | Morphological component analysis: An adaptive thresholding strategy[END_REF], [START_REF] Bobin | Morphological diversity and sparsity for multichannel data restoration[END_REF].

C. Dictionary choice

From a practical point of view, given a signal x, we will need to compute its forward (or analysis) transform by multiplying it by Φ T . We also need to reconstruct any signal from its coefficients α. In fact, the matrix Φ and its adjoint Φ T corresponding to each transform are never explicitly constructed in memory. Rather they are implemented as fast implicit analysis and synthesis operators taking a signal vector x, and returning Φ T x = Tx (analysis side), or taking a coefficient vector α and returning Φα (synthesis side). In the case of a simple orthogonal basis, the inverse of the analysis transform is trivially T -1 = Φ; whereas assuming that Φ is a tight frame implies that the frame operator satisfies ΦΦ T = cI, where c > 0 is the tight frame constant. Hence, T T = Φ is the Moore-Penrose pseudo-inverse transform (corresponding to the minimal dual synthesis frame), up to the constant c. In other words, the pseudo-inverse reconstruction operator T + corresponds to c -1 Φ. It turns out that T + α is the reconstruction operation implemented by most implicit synthesis algorithms.

Choosing an appropriate dictionary is a key step towards a good sparse decomposition. Thus, to represent efficiently isotropic structures, a qualifying choice is the wavelet transform [START_REF] Mallat | A Wavelet Tour of Signal Processing[END_REF], [START_REF] Starck | Image Processing and Data Analysis: The Multiscale Approach[END_REF]. The curvelet system [START_REF] Candès | Fast discrete curvelet transforms[END_REF] is a very good candidate for representing piecewise smooth (C 2 ) images away from C 2 contours. The ridgelet transform [START_REF] Candès | Ridgelets: the key to high dimensional intermittency?[END_REF] has been shown to be very effective for sparsely representing global lines in an image. For locally oscillating textures, one can think of the local DCT (discrete cosine transform) [START_REF] Mallat | A Wavelet Tour of Signal Processing[END_REF], waveatoms [START_REF] Demanet | Wave atoms and sparsity of oscillatory patterns[END_REF] or brushlets [START_REF] Meyer | Brushlets: A tool for directional image analysis and image compression[END_REF]. These transforms are also computationally tractable particularly in large-scale applications, What happens if none of the known fixed transforms can efficiently sparsify a morphological component; e.g. a complex natural texture. In [START_REF] Peyré | Learning adapted dictionaries for geometry and texture separation[END_REF], the authors have extended the MCA algorithm to handle the case where the dictionary attached to each morphological component is not necessarily fixed a priori as above, but learned from a set of exemplars in order to capture complex textural patterns.

D. Thresholding strategy

In practice, hard thresholding leads to better results. Furthermore, in [START_REF] Bobin | Morphological component analysis: An adaptive thresholding strategy[END_REF], we empirically showed that the use of hard thresholding is likely to provide the ℓ 0 -sparsest solution. As far as the thresholding decreasing strategy is concerned, there are several alternatives. For example, in [START_REF] Starck | Image decomposition via the combination of sparse representatntions and variational approach[END_REF], [START_REF]Redundant multiscale transforms and their application for morphological component analysis[END_REF], linear and exponential decrease were advocated. In [START_REF] Bobin | Morphological component analysis: An adaptive thresholding strategy[END_REF], a more elaborated strategy coined MOM (for mean-of-max) was proposed.

E. Handling bounded noise

MCA handles in a natural way data perturbed by additive noise ε with bounded variance σ 2 ε . Indeed, as MCA is a coarse-to-fine iterative procedure, bounded noise can be handled just by stopping iterating when the residual is at the noise level. Assuming that the noise variance σ 2 ε is known, the algorithm may be stopped at iteration t when the ℓ 2 -norm of the residual satisfies r (t) 2 ≤ √ N σ ε . Alternatively, one may use a strategy reminiscent of denoising methods, by taking λ min = τ σ ε where τ is a constant, typically between 3 and 4. the galaxy has been well detected in the wavelet space while the stripping artifact was remarkably captured and removed owing to ridgelets and curvelets.

F. Applications

III. MULTICHANNEL SPARSE SOURCE SEPARATION

A. The blind source separation problem

In the blind source separation (BSS) setting, the instantaneous linear mixture model assumes that we are given m observations (channels) {y 1 , • • • , y m } where each y j is a row-vector of size N ; each channel is the linear mixture of n sources

∀j ∈ {1, • • • , m}, y j = n i=1 a j [i]s i + ε j , (2)
or equivalently in matrix form

Y = AS + E , (3)
where

Y = [y T 1 , • • • , y T m ]
T is the m × N measurement matrix whose rows are the channels

y j 's, S = [s T 1 , • • • , s T n ]
T is the n × N source matrix whose rows are the sources s i , and A is the m × n mixing matrix. A defines the contribution of each source to each channel. An m × N matrix E is added to account for instrumental noise or model imperfections. See Fig. 1.

Source separation techniques aim at recovering the original sources S by taking advantage of some information contained in the way the signals are mixed. In the blind approach, both the mixing matrix A and the sources S are unknown. Source separation is overwhelmingly a question of contrast and diversity.

Indeed, source separation boils down to devising quantitative measures of diversity or contrast to extricate the sources. Typical measures of contrast are statistical criteria such as independence (i.e. ICA [START_REF] Hyvärinen | Independent Component Analysis[END_REF]), or sparsity and morphological diversity, see [START_REF] Zibulevsky | Blind source separation by sparse decomposition[END_REF], [START_REF] Georgiev | Sparse component analysis and blind source separation of underdetermined mixtures[END_REF], [START_REF] Bobin | Morphological diversity and source separation[END_REF], [START_REF] Bobin | Sparsity and morphological diversity in blind source separation[END_REF], [START_REF] Bobin | Blind source separation : The sparsity revolution[END_REF] and references therein.

B. Generalized Morphological Component Analysis

The GMCA framework assumes that the observed data Y is a linear instantaneous mixture of unknown sources S with an unknown mixing matrix A as in [START_REF] Bobin | Sparsity and morphological diversity in blind source separation[END_REF]. For notational convenience, the dictionaries in the multichannel case will be transposed versions of those considered in the single channel case in Section II; each dictionary Φ k now a matrix whose rows are unit-norm atoms. Thus, we let Φ be the concatenation of

K transforms: Φ = Φ T 1 , • • • , Φ T K T .
The GMCA framework assumes a priori that the sources (s i ) i=1,••• ,n are sparse in the dictionary Φ; ∀i s i = α i Φ where α i is sparse (or compressible). More precisely, in the GMCA setting, each source is modeled as the linear combination of K morphological components where each component is sparse in a specific basis

∀i ∈ {1, • • • , n}; s i = K k=1 x ik = K k=1 α ik Φ k . ( 4
)
GMCA seeks an unmixing scheme, through the estimation of A, which leads to the sparsest sources S in the dictionary Φ. This is expressed by the following optimization problem

min A,α n i=1 K k=1 α ik p p such that Y -AαΦ F ≤ σ and a i 2 = 1 ∀i = 1, • • • , n , (5)
where typically p = 0 or a relaxed version with p = 1. But other sparsity regularization terms can be used in ( 5), e.g. mixed-norms [START_REF] Kowalski | Under-determined source separation via mixed-norm regularized minimization[END_REF]. The unit ℓ 2 -norm constraint on the columns of A avoids the classical scale indeterminacy of the product AS in (3). The reader may have noticed that the MCA problem ( 1) is a special case of the GMCA problem [START_REF] Meyer | Oscillating patterns in image processing and in some nonlinear evolution equations[END_REF] when there is only one source n = 1 and one channel m = 1 (no mixing).

Thus GMCA is indeed a multichannel generalization of MCA.

The program ( 5) is a difficult non-convex optimization problem even for convex penalties p ≥ 1. More conveniently, the product AS can be split into n•K multichannel morphological components:

AS = i,k a i x ik = AαΦ = i,k a i α ik Φ k .
Based on this decomposition, GMCA yields an alternating minimization algorithm to estimate iteratively one term at a time. It has been shown in [START_REF] Bobin | Sparsity and morphological diversity in blind source separation[END_REF] that estimating the morphological component

x ik = α ik Φ k assuming A and x {pq} ={ik} can be obtained through iterative thresholding for p = 0 and p = 1.

Now, considering fixed {a p } p =i and S, updating the column a i is then just a least-squares estimate

a i = 1 s i 2 2   Y - p =i a p s p   s T i . (6)
This estimate is then projected onto the unit sphere to meet the unit ℓ 2 -norm constraint in [START_REF] Meyer | Oscillating patterns in image processing and in some nonlinear evolution equations[END_REF].

C. GMCA algorithm

The GMCA algorithm is summarized in Algorithm 2. In the same vein as MCA, GMCA also relies on a salient-to-fine strategy. More precisely, GMCA is an iterative thresholding algorithm such that at each iteration it first computes coarse versions of the morphological components for a fixed source s i . These raw sources are estimated from their most significant coefficients in Φ. Then, the corresponding column a i is estimated from the most significant features of s i . Each source and its corresponding column of A are then alternately and progressively refined as the threshold λ decreases towards λ min . This particular iterative thresholding scheme provides robustness to noise, model imperfections initialization by working first on the most significant features in the data and then progressively incorporating smaller details to finely tune the model parameters. As a multichannel extension of MCA, GMCA is also robust to noise and can be used with either linear or exponential decrease of the threshold [START_REF] Bobin | Sparsity and morphological diversity in blind source separation[END_REF], [START_REF] Bobin | Blind source separation : The sparsity revolution[END_REF]. Moreover, hard thresholding leads to its best practical performance.

Algorithm 2: GMCA BSS algorithm. Task: Blind source separation.

Parameters: Observed channels Y, the dictionary Φ = [Φ T 1 • • • Φ T K ]
T , number of sources n, number of iterations N iter , initial and stopping thresholds λ (0) and λ min , threshold update schedule.

Main iteration: for

t = 1 to N iter do for i = 1 to n do for k = 1 to K do Compute marginal residuals R (t) ik = Y -{p,q} ={i,k} a p (t- 1) x (t-1) pq .
Update (i, k)-th coefficients by thresholding α

(t) ik = TH λ (t-1) a i (t-1) T R (t) ik Φ T k . Update (i, k)-th component by reconstructing from the selected coefficients x (t) ik = α (t) ik Φ k . Update i-th source s (t) i = K k=1 x (t) ik . Update i-th mixing matrix column a i (t) = 1 s (t) i 2 2 Y -n p =i a p (t-1) s (t) p s (t) T i
and normalize to a unit norm. Update the threshold λ (t) according to the given schedule. if λ (t) ≤ λ min then stop.

Output: Sources s (Niter) i i=1,••• ,n
and mixing matrix A (Niter) .

D. Unknown number of sources

In BSS, the number of sources n is assumed to be a fixed known parameter of the problem. This is rather an exception than a rule, and estimating n from the data is a crucial and strenuous problem. Only a few works have attacked this issue. One can think of using model selection criteria such as the minimum description length used in [START_REF] Balan | Estimator for number of sources using minimum description length criterion for blind sparse source mixtures[END_REF]. In [START_REF] Bobin | Blind source separation : The sparsity revolution[END_REF], a sparsity-based method to estimate n within the GMCA framework was proposed.

Roughly speaking, this selection procedure uses GMCA to solve a sequence of problems [START_REF] Meyer | Oscillating patterns in image processing and in some nonlinear evolution equations[END_REF] for each constraint radius σ(q) with increasing q, 1 ≤ q ≤ m. In [START_REF] Bobin | Blind source separation : The sparsity revolution[END_REF], it was argued to set σ(q) to the Frobenius-norm of the error when approximating the data matrix Y with its largest q singular vectors; see [START_REF] Bobin | Blind source separation : The sparsity revolution[END_REF] for further details.

E. Hyperspectral data

In standard BSS, A is often seen as a mixing matrix of small size m × n. On the other hand, there are applications in which one deals with data from instruments with a very large number of channels m which are well organized according to some physically meaningful index. A typical example is hyperspectral data where images are collected in a large number (i.e. hundreds) of contiguous regions of the electromagnetic spectrum. Regardless of other definitions appearing in other scientific communities, the term hyperspectral is used here for multichannel data model [START_REF] Bobin | Sparsity and morphological diversity in blind source separation[END_REF] where the number of channels m is large, and these channels achieve a uniform sampling of some meaningful physical index (e.g. wavelength, space, time) which we refer to as the spectral dimension. For such data, it then makes sense to consider the regularity of the spectral signatures

(a i ) i=1,••• ,n .
For instance these spectral signatures may be known a priori to have a sparse representation in some specified possibly redundant dictionary Ψ of spectral waveforms.

In [START_REF] Bobin | Blind source separation : The sparsity revolution[END_REF], [START_REF] Moudden | Dictionary learning with spatio-spectral sparsity constraints[END_REF], the authors propose a modified GMCA algorithm capable of handling hyperspectral data. This is achieved by assuming that each rank-one matrix X i = a i s i has a sparse representation in the multichannel dictionary Φ ⊗ Ψ [START_REF] Bobin | Morphological diversity and sparsity for multichannel data restoration[END_REF], [START_REF] Gribonval | Beyond sparsity : recovering structured representations by l1-minimization and greedy algorithms: Application to the analysis of sparse underdetermined ica[END_REF] (⊗ is the Kronecker product); i.e. ∀i s i = α i Φ and a i = Ψβ i where α i and β i are both sparse. The separation optimization problem for hyperspectral data is then

min α,β 1 2 Y - n i=1 Ψβ i α i Φ 2 F + n i=1 λ i β i α i 1 , (7)
where a Laplacian prior is imposed on each α i conditionally on β i and vice versa. Remarkably, this joint prior preserves the scale invariance of (3). Problem ( 7) is again a non-convex optimization problem for which no closed-form solution exists. In the line of the GMCA algorithm, thanks to the form of the ℓ 1 -penalty in [START_REF] Zibulevsky | Blind source separation by sparse decomposition[END_REF], a block-relaxation iterative thresholding algorithm was proposed in [START_REF] Bobin | Blind source separation : The sparsity revolution[END_REF], [START_REF] Moudden | Dictionary learning with spatio-spectral sparsity constraints[END_REF] that alternately minimizes [START_REF] Zibulevsky | Blind source separation by sparse decomposition[END_REF] with respect to α and β. It was shown by these authors that the update equations on the coefficient matrices are

α (t+1) = ST η (t) β (t) T β (t) -1 β (t) T Ψ T YΦ T , β (t+1) = ST ζ (t) Ψ T YΦ T α (t) T α (t) α (t) T -1 . (8)
η (t) is a vector of length n and entries η

(t) [i] = λ (t) β i (t) 1 / β i (t) 2 2 , ζ (t) has length m and entries ζ (t) [j] = λ (t) α j (t) 1 / α j (t) 2
2 , and λ (t) is a decreasing threshold. The multichannel soft-thresholding operator ST η acts on each row i with threshold η[i] and ST ζ acts on each column j with threshold ζ[j].

F. Applications BSS:

We first report a simple BSS application. Fig. 3 shows two original sources (left) and the two noisy mixtures SNR=10dB (middle). GMCA was applied with a dictionary containing curvelets and local DCT. As a quantitative performance measure of BSS methods, we use the mixing matrix criterion ∆ A = I n -P Â+ A 1 , where Â+ is the pseudo-inverse of the estimate of the mixing matrix A, and P is a matrix that reduces the scale/permutation indeterminacy of the mixing model. The right panel of Fig. 3 compares GMCA to popular BSS techniques in terms of ∆ A as the SNR increases. We compare GMCA to ICA JADE [START_REF] Cardoso | Blind signal separation: statistical principles[END_REF], Relative Newton Algorithm (RNA) [START_REF] Zibulevski | Blind source separation with relative newton method[END_REF] that accounts for sparsity and EFICA [START_REF] Koldovsky | Efficient variant of algorithm fastica for independent component analysis attaining the cramer-rao lower bound[END_REF]. Both RNA and EFICA were applied after "sparsifying" the data via an orthonormal wavelet transform. It can be seen that JADE performs rather badly, while RNA and EFICA behave quite similarly. GMCA seems to provide much better results especially at high noise level.

Color image denoising: GMCA can be applied to color image denoising. This is illustrated in Fig. 4 where the original RGB image is shown on the left. The middle image shows the RGB image obtained using a classical undecimated wavelet-domain hard thresholding on each color plane independently. GMCA is applied to the RGB color channels using the curvelet dictionary. In the notation of section III-A, we have m = 3 channels (color planes), each color channel is y j , j = 1, 2, 3, n = 3 sources and A plays the role of the color space conversion matrix. Unlike classical color spaces (e.g. YUV, YCC), where the conversion matrix from RGB is fixed, the color space conversion matrix is here estimated by GMCA from the data. As such, GMCA is able to find adaptively the appropriate color space corresponding to the color image at hand. Once A is estimated by GMCA, we applied the same undecimated wavelet-based denoising to the estimated sources. The 4) on the right shows the GMCA-based denoised image. Clearly, denoising in the "GMCA color space" is substantially better than in the RGB space (or other color spaces such as YUV or YCC; see [START_REF] Bobin | Sparsity and morphological diversity in blind source separation[END_REF]).

Hyperspectral data processing: In this experiment, we consider m = 128 mixtures of n = 5 source images. The sources are drawn at random from a set of structured images shown in Fig. 5(a). For the spectra (i.e. columns of A), we randomly generated sparse coefficient vectors β i (i = 1, . . . , n) with independent Gaussian-distributed non-zero entries, and then applied the inverse orthogonal wavelet transform to these sparse vectors to get the spectra. Φ was chosen as the curvelet dictionary. Fig. 5(b) gives four typical noisy observed channels with SNR=20dB. The sources recovered using GMCA (Algorithm 2) and its hyperspectral extension (iteration of section III-E) are shown respectively in Fig. 5(c) and (d). Visual inspection shows that GMCA is outperformed by hyperspectral GMCA which better accounts for both spatial and spectral sparsity.

IV. REPRODUCIBLE RESEARCH SOFTWARE

Following the philosophy of reproducible research, two toolboxes MCALab and GMCALab [START_REF] Fadili | MCALab: Reproducible research in signal and image decomposition and inpainting[END_REF]

V. CONCLUSION

In this paper, we gave an overview of how sparsity and morphological diversity can be used advantageously to regularize image decomposition and blind source separation problems. We also reported several numerical experiments to illustrate the wide applicability of the algorithms described. We believe that this is an exciting field where many interesting problems are still open. Among them, we may cite for instance the theoretical guarantees of the sparsity-regularized BSS problem, and sharper theoretical guarantees for the decomposition problem by exploiting geometry.

Fig. 1 .

 1 Fig. 1. Illustration of the image decomposition (top) and the blind source separation (BSS) problems (bottom) using sparsity and morphological diversity. For the bottom part, each source is itself a mixture of morphological components (see (4)) to be isolated.

Algorithm 1 :

 1 steps of the MCA algorithm summarized in Algorithm 1, where TH λ (α) denotes component-wise thresholding with threshold λ: hard thresholding HT λ (u) = u if |u| > λ and 0 otherwise, or soft-thresholding ST λ (u) = u max(1 -λ/ |u| , 0). MCA decomposition algorithm. Task: Signal/image decomposition. Parameters: The signal/image x, the dictionary Φ

  and as stated above, never explicitly implement Φ and T. The associated implicit fast analysis and synthesis operators have typical complexities of O(N ), with N the number of samples or pixels (e.g. orthogonal or bi-orthogonal wavelet transform) or O(N log N ) (e.g. ridgelets, curvelets and local DCT, waveatoms).

Fig. 2

 2 Fig. 2 shows examples of application of the MCA sparse decomposition algorithm to three real images: Barbara (a)-(c), X-ray riser image (d)-(f) and an astronomical image of the galaxy SBS 0335-052 (g)-(j). The riser in Fig. 2(d) is made of a composite material layer, a layer of steel-made fibers having opposite lay angles, and lead-made markers used as a reference to calibrate the X-ray camera. The observed image is corrupted by noise. The structures of interest are the curvilinear fibers. The astronomical image of Fig. 2(g) is contaminated by noise and a stripping artifact, the galaxy of interest is hardly visible in the original data. The dictionaries used for the three images are respectively: local DCT+curvelets for Barbara to decompose it into cartoon+texture parts; translation invariant wavelets+curvelets for the riser image; ridgelets+curvelets+translation invariant wavelets for the astronomical image. The details of the experimental set-up including the parameters of the dictionaries for each image are detailed in [22]. From Fig. 2(e)-(f), one can clearly see how MCA managed to get rid of the lead-made markers while reconstructing the curvilinear fibers structure. In Fig. 2(j),

Fig. 2 .

 2 Fig. 2. MCA of three real 2D images. Barbara: (a) Original, (b) cartoon component (curvelets), (c) texture (local DCT). X-ray riser image: (d) Observed, (e) isotropic structures and background (wavelets), (f) curvilinear fibers (curvelets). Galaxy SBS 0335-052: (g) Observed, (h) ridgelet component, (i) curvelet component, (j) detected galaxy (wavelets).

Fig. 3 .

 3 Fig. 3. Example of BSS with two sources (left) and two noisy mixtures (middle). The right panel depicts the evolution of the mixing matrix criterion ∆ A with input SNR (solid line : GMCA, dashed line : JADE, (+) : RNA, (⋆) : EFICA).

Fig. 4 .

 4 Fig. 4. Left: Original RGB image image with additive Gaussian noise SNR=15 dB. Middle: Wavelet-based denoising in the RGB space. Right: Wavelet-based denoising in the "GMCA color space".

  denoised data are obtained by coming back to the RGB space via the estimated mixing matrix. Fig.(

  are made available freely for download at the address http://www.morphologicaldiversity.org MCALab and GMCALab have been developed to demonstrate key concepts of MCA and GMCA and make them available to interested researchers and technologists. These toolboxes are libraries of Matlab routines that implement the decomposition and source separation algorithms overviewed in this paper. They contain a variety of scripts to reproduce the figures in our own articles, as well as other exploratory examples not included in the papers.

Fig. 5 .

 5 Fig. 5. (a) Images used as sources. (b) Four noisy mixtures out of m = 128 (SNR=20dB). (c) Recovered sources using GMCA. (d) Recovered sources using hyperspectral GMCA.

June 1, 2009 DRAFT

Acknowledgment: This work is supported by the NatImages ANR grant ANR-08-EMER-009.