Mathieu Acher

Patrick Heymans

Philippe Collet
email: collet@i3s.unice.fr

Clément Quinton
email: clement.quinton@inria.fr

Philippe Lahire
email: lahire@i3s.unice.fr

Philippe Merle
email: philippe.merle@inria.fr

à la diffusion de documents scientifiques de niveau

Keywords: Feature Models, Model Differences, Model Management

recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Software product line (SPL) engineering aims at generating software variants tailored to the needs of particular customers or market segments [START_REF] Pohl | Software Product Line Engineering: Foundations, Principles and Techniques[END_REF]. SPL principles, formalisms and techniques are gaining more and more attention in different application domains to efficiently produce and maintain multiple similar software products. Central to SPL engineering is the modeling and management of variability: exploiting what variants have in common and managing what varies among them. In this context, feature models (FMs) are widely used to model the variability of a system in terms of mandatory, optional and exclusive features as well as propositional constraints over the features [START_REF] Schobbens | Generic semantics of feature diagrams[END_REF][START_REF] Thüm | Reasoning about edits to feature models[END_REF]. The primary purpose and semantics of FMs is to characterize the combinations of features (called configurations) supported by a system. A number of formalizations (e.g., [START_REF] Schobbens | Generic semantics of feature diagrams[END_REF][START_REF] Czarnecki | Feature diagrams and logics: There and back again[END_REF]), automated reasoning operations [START_REF] Benavides | Automated analysis of feature models 20 years later: A literature review[END_REF] and tools (e.g., [START_REF] Mendonca | Efficient compilation techniques for large scale feature models[END_REF][START_REF] Acher | A Domain-Specific Language for Managing Feature Models[END_REF][START_REF] She | Reverse engineering feature models[END_REF]) have been developed to address this issue. The formalism of FMs is now at the core of many generative or model-based approaches [START_REF] Czarnecki | Generative Programming: Methods, Tools, and Applications[END_REF][START_REF] Pohl | Software Product Line Engineering: Foundations, Principles and Techniques[END_REF][START_REF] Pleuss | Modeldriven support for product line evolution on feature level[END_REF][START_REF] Dhungana | Structuring the modeling space and supporting evolution in software product line engineering[END_REF].

When managing the variability of an SPL, reasoning about the differences of two FMs is a prime concern: for instance, when an SPL, and therefore its FM, evolve over time. Even small edits to an FM, like moving a feature from one branch to another, can unintentionally change the set of valid feature combinations. Understanding the impact of the evolution of an FM, and thus the differences between two versions, is known to be impractical to determine manually [START_REF] Thüm | Reasoning about edits to feature models[END_REF]. Consequently tool support is required to assist practitioners in computing and understanding FM differences. In practice, the need to support FM differences has been observed in different domains and for different purposes.

Evolution of an FM. In [START_REF] Dhungana | Structuring the modeling space and supporting evolution in software product line engineering[END_REF][START_REF] Pleuss | Modeldriven support for product line evolution on feature level[END_REF], the authors report that evolution support becomes particularly important for engineering SPLs and other variability-intensive systems. They propose model-driven support at the feature level, using FM concepts [START_REF] Pleuss | Modeldriven support for product line evolution on feature level[END_REF]. Lotufo et al. study the evolution of the Linux kernel variability model [START_REF] Lotufo | Evolution of the linux kernel variability model[END_REF]. They identify edit operations applied in practice and new automation challenges, including the detection of edits that break existing configurations. Differencing techniques are thus needed, for example, to identify what are the added and removed configurations. In [START_REF] Acher | Reverse Engineering Architectural Feature Models[END_REF], we developed an automated procedure to extract the FM of FraSCAti, a large component and plugin-based system. The handling of FM differences was needed to compare the automatically extracted FM with one that was elaborated manually by the main developer of FraSCAti. It is also needed to understand and validate the evolution of the FMs for different versions of FraSCAti.

Management of a product line (PL) offering. Two kinds of variability are usually distinguished in SPL engineering [START_REF] Pohl | Software Product Line Engineering: Foundations, Principles and Techniques[END_REF][START_REF] Metzger | Disambiguating the documentation of variability in software product lines: A separation of concerns, formalization and automated analysis[END_REF]: software variability, hidden from customers, as opposed to PL variability, visible to them. An important property of an SPL is realizability, that is, whether the set of products that the PL management decides to offer is fully covered by the set of products that the software platform allows to build. Symmetrically, the usefulness property is interesting for a product manager to identify unused flexibility of the software platform. In this case, product managers and software engineers need to precisely understand what are the products supported by the platform but not offered to customers (it can be on purpose and justified by future market extensions). The differencing information is then exploited by product managers and software engineers to validate or evolve the FMs documenting the two kinds of variability. In the development of a video surveillance SPL and medical imaging workflows, we observed similar differentiation needs [START_REF] Acher | Composing Multiple Variability Artifacts to Assemble Coherent Workflows[END_REF].

Until now, the problem of FM differences has neither been recognized nor comprehensively addressed by existing approaches. Model-based approaches mostly rely on syntactic mechanisms, basing their heuristics on the names and structure of model elements [START_REF]Bibliography on Comparison and Versioning of Software Models[END_REF]. While showing some success, there are serious limitations. Models that are syntactically very similar may actually have very different semantics (intended meaning), and vice versa, models that describe the same system may have very different syntactic representations [START_REF] Maoz | A manifesto for semantic model differencing[END_REF][START_REF] Maoz | Addiff: semantic differencing for activity diagrams[END_REF][START_REF] Fahrenberg | Vision paper: Make a difference! (semantically)[END_REF]. This observation also applies to FMs [START_REF] She | Reverse engineering feature models[END_REF]. As a result, a list of syntactic differences, although accurate and useful, may not be able to reveal the real and meaning-ful implications these differences have on the models involved. Some voices are calling for more semantic differencing [START_REF] Maoz | A manifesto for semantic model differencing[END_REF][START_REF] Fahrenberg | Vision paper: Make a difference! (semantically)[END_REF] and such techniques have recently emerged for specific modeling formalisms [START_REF] Maoz | Addiff: semantic differencing for activity diagrams[END_REF][START_REF] Maoz | Cddiff: semantic differencing for class diagrams[END_REF]. In the feature modeling community, Benavides et al. do not report any differencing support in their survey, despite the impressive research effort on FM automations [START_REF] Benavides | Automated analysis of feature models 20 years later: A literature review[END_REF]. Only a few recent works have specifically considered the problem of FM differences at the syntactic [START_REF] Segura | Automated merging of feature models using graph transformations[END_REF] or at the semantic level [START_REF] Thüm | Reasoning about edits to feature models[END_REF][START_REF] Fahrenberg | Vision paper: Make a difference! (semantically)[END_REF] but have limitations to compute and present exploitable differences. In previous work, we developed a set of semantic techniques for FMs [START_REF] Acher | Comparing Approaches to Implement Feature Model Composition[END_REF][START_REF] Acher | Reverse Engineering Architectural Feature Models[END_REF][START_REF] Acher | A Domain-Specific Language for Managing Feature Models[END_REF][START_REF] Acher | Composing Multiple Variability Artifacts to Assemble Coherent Workflows[END_REF] but not yet for differences.

In this paper we first present and illustrate the problem of FM differences (Section 2). We develop a set of syntactic and semantic techniques to compute, reason about and present differences (Section 3). Thanks to these techniques, a practitioner can understand differences in a fine-grained way, visualize and manage a model of differences, augment an existing FM with the differences or compute the differences only on some parts of the two FMs. The techniques are automated using satisfiability algorithms and come with a dedicated language (Section 3.4). We also report on a practical usage and evaluation of the differencing techniques through a case study (Section 4). We discuss related work (Section 5) and conclude the paper (Section 6).

The Problem of Feature Model Differences

Background

FMs hierarchically structure application features into multiple levels of increasing detail. When decomposing a feature into subfeatures, the subfeatures may be optional or mandatory or may form Xor-or Or-groups (see Figure 1(a) for a visual representation of an FM). The terms FM and feature diagram are employed in the literature, usually to denote the same concept. In this paper, we consider that a feature diagram (see Definition 1) includes a feature hierarchy (tree), a set of feature groups, as well as human readable constraints (implies, excludes). The formalism of FMs considered is among the most popular in use.

Definition 1 (Feature Diagram) A feature diagram F D = G, E M AN D , G XOR , G OR , I, EX is defined as follows:
-G = (F, E, r) is a rooted, labeled tree where F is a finite set of features, E ⊆ F × F is a finite set of edges and r ∈ F is the root feature ; -E M AN D ⊆ E is a set of edges that define mandatory features with their parents ; -G XOR ⊆ P(F) × F and G OR ⊆ P(F) × F define feature groups and are sets of pairs of child features together with their common parent feature ; a set of implies constraints I whose form is A ⇒ B, a set of excludes constraints EX whose form is A ⇒ ¬B (A ∈ F and B ∈ F).

Features that are neither mandatory features nor involved in a feature group are optional features. A parent feature can have several feature groups but a feature must belong to only one feature group. It should be noted that a feature diagram, as defined above, is not expressively complete with respect to propositional logics. Similar to [START_REF] She | Reverse engineering feature models[END_REF], we thus consider that an FM is composed of a feature diagram plus a propositional formula ψ cst (see Definition 2).

Definition 2 (Feature Model) An FM is a tuple F D, ψ cst where F D is a feature diagram and ψ cst is a propositional formula over the set of features F.

Not all combinations of features (configurations) are authorized by an FM. A valid (or legal) configuration is obtained by selecting features in a manner that respects the following rules: i) If a feature is selected, its parent must also be selected; ii) If a parent is selected, the following features must also be selected -all the mandatory subfeatures, exactly one subfeature in each of its Alternative groups, and at least one of its subfeatures in each of its Or groups; iii) propositional constraints must hold. An FM thus defines a set of valid feature configurations (see Definition 3). Definition 3 (Configuration Semantics) A configuration of an FM f m 1 is defined as a set of selected features. f m 1 denotes the set of valid configurations of f m 1 and is a set of sets of features.

An FM is usually encoded as a propositional formula, denoted φ, and defined over a set of Boolean variables, where each variable corresponds to a feature [START_REF] Czarnecki | Feature diagrams and logics: There and back again[END_REF]. The translation to propositional logic is well known and off-the-shelf SAT solvers or binary decisions diagrams (BDDs) can be used to automatically reason about properties of an FM and its configurations [START_REF] Benavides | Automated analysis of feature models 20 years later: A literature review[END_REF][START_REF] Schobbens | Generic semantics of feature diagrams[END_REF][START_REF] Czarnecki | Feature diagrams and logics: There and back again[END_REF].

Diff: A Running Example

We now illustrate with a simple example, extracted from [START_REF] Fahrenberg | Vision paper: Make a difference! (semantically)[END_REF], the problem of FM differences. Let us consider applet 1 (see Figure 1(a)) and applet 2 (see Figure 1(b)). Obviously, the two FMs differ, for example, feature init is a child feature of mustOverride in applet 1 whereas feature init is a child feature of the root feature applet in applet 2 . This difference may occur in many scenarios already described in the introduction: the FM applet 1 has evolved over time, leading to applet 2 ; the two FMs have been reverse engineered from two existing frameworks ; applet 1 is a requirements model specified by a customer whereas applet 2 is the actual implementation model supported by an application programming interface, etc. A few questions arise: How do these two FMs, applet 1 and applet 2 , differ? Are they equivalent? If not, what is the actual difference? Several applications of FM differences are conceivable. First, the difference may serve as a debugging information. For example, the four configurations satisfying applet 1 but not applet 2 {{applet, destroy, init, mustOverride, stop}, {applet, init, mustOverride, stop}, {applet, init, mustOverride}, Fig. 1. Two example FMs extracted from [START_REF] Fahrenberg | Vision paper: Make a difference! (semantically)[END_REF] {applet, destroy, init, mustOverride}} can be considered as a specification error. Second, examples of configurations allowed by applet 1 but not in applet 2 might be used to expand configurations of applet 2 . Based on the analysis of differences, a practitioner may correct the error previously identified and relax some variability constraints and edit applet 2 (e.g., features paint and start become optional features and are no longer forming an Or-group). The example shows that a crucial issue for a practitioner, being modeler, product line manager, software engineer or architect, is to precisely understand and reason about differences of two FMs. Based on this information, a practitioner can validate the differences and/or evolve the FMs.

3 Set of Operators for Differencing of Feature Models

Let f m 1 = F D 1 , ψ cst1 with F D 1 = G 1 = (F 1 , E 1 , r 1 ), E M AN D1 , G XOR1 , G OR1 , I 1 , EX 1 and f m 2 = F D 2 , ψ cst2 with F D 2 = G 2 = (F 2 , E 2 , r 2 ), E M AN D2 , G XOR2 , G OR2 , I 2
, EX 2 be two FMs. In the reminder of this section, we consider the difference (diff for short) between f m 1 and f m 2 -in this particular order. We will use the example of Figure 1 to illustrate our contributions (i.e., f m 1 = applet 1 and f m 2 = applet 2 ). Rationale and overview. Several techniques for the diff of FMs can be considered. Roughly, the diff between f m 1 and f m 2 is the set of elements in f m 1 but not in f m 2 . From a syntactical perspective, the elements to be considered in the diff may be features, feature hierarchies, feature groups or implies / excludes. We present syntactic differencing techniques in Section 3.1. Though the syntactic diff might be useful, we believe that a semantic diff for FMs should also be developed and possibly be combined with syntactic differencing. Many researchers share this vision (e.g., see [START_REF] Thüm | Reasoning about edits to feature models[END_REF][START_REF] Maoz | A manifesto for semantic model differencing[END_REF][START_REF] Fahrenberg | Vision paper: Make a difference! (semantically)[END_REF]) and semantic differences have already been developed specifically for other kinds of models (class diagrams [START_REF] Maoz | Addiff: semantic differencing for activity diagrams[END_REF] and activity diagrams [START_REF] Maoz | Cddiff: semantic differencing for class diagrams[END_REF]). We present semantic differencing techniques in Section 3.2. Rather than directly computing and reasoning about differences, it can be useful to focus on the common parts of two FMs. Another developed technique is to provide the means to focus on a specific part, typically smaller, of the two FMs in order to facilitate the understanding of their differences. We describe a set of syntactic and semantic composition and decomposition techniques in Section 3.3 that comes in complement to the differencing techniques.

Syntactic Diff

A general approach to model differencing is to concentrate on matching between model elements using different heuristics related to their names and structure and on finding and presenting differences at a concrete or abstract syntactic level. Matching algorithms are out of the scope of this paper, surveys of different approaches can be found in [START_REF] Euzenat | Ontology matching[END_REF][START_REF] Kolovos | Different models for model matching: An analysis of approaches to support model differencing[END_REF]. We assume that features are identified by an unique label (i.e., name) in an FM and that two features of two FMs match if and only if they have the same name 4 .

In terms of feature modeling, elements of interest are features, variability information (mandatory features, feature groups, and propositional constraints) and feature hierarchy (see Definition 1 and 2). We thus consider the diff of these model elements.

Diff of features.

F dif f is the set of features that are in f m 1 but not in f m 2 , i.e., F dif f = F 1 \ F 2 . In the example of Figure 1, F dif f = ∅.
Diff of feature hierarchies. Several techniques can be considered (e.g., tree edit distance [START_REF] Bille | A survey on tree edit distance and related problems[END_REF]), including the computation of E dif f the set of edges modeling parent-child relationships in f m 1 but not in f m 2 . Formally:

E dif f = E 1 \ E 2 . In the example of Figure 1, E dif f = {{mustOverride, init}, {applet, destroy}, {applet, stop}}.
Diff of mandatory features. A syntactic diff of mandatory features produces

E M AN D dif f = E M AN D1 \ E M AN D2 .
In the example of Figure 1, EMAND dif f = {{applet, mustOverride}}, showing that the feature mustOverride is mandatory in f m 1 , which is not the case in f m 2 .

Diff of feature groups. It is useful to determine feature groups (Xor and Or) that are in

f m 1 but not in f m 2 , including G XOR dif f = G XOR1 \ G XOR2 and G OR dif f = G OR1 \ G OR2 .
We consider that two feature groups are equal if and only if their parent features match and their child features match. In the example of Figure 1,

GXOR dif f = ∅ and GOR dif f = {{{init, start, paint}, mustOverride}}
Diff of implies and excludes. A syntactic diff of implies (resp. excludes) constraints produces

I dif f (resp. EX dif f ) so that I dif f = I 1 \ I 2 (resp. EX dif f = EX 1 \EX 2 ). In Figure 1, I dif f = {{destroy ⇒ init}, {stop ⇒ init}} and EX dif f = ∅.
It should be noted that I dif f is not semantically correct in this example: the features destroy and stop do imply the feature init in f m 2 , owing to the parentchild relationships in f m 2 .

Semantic Diff

Syntactic differences are useful for the example of Figure 1. Using the list of differences, a modeler can identify that the feature init has been moved or that the feature mustOverride becomes a mandatory feature in f m 2 . However, a practitioner rather wants to understand the difference between the two FMs in terms of configuration semantics (i.e., in terms of sets of configurations). For this purpose, the list of syntactic differences fails to produce some differences, among others: i) the four configurations authorized by f m 1 but not by f m 2 are not identified ; ii) I dif f does not report that stop ⇒ mustOverride holds in f m 1 but not in f m 2 . With this information, a practitioner could learn that the feature stop does not imply the selection of the feature mustOverride in f m 2 whereas it is the case in f m 1 .

To raise the limits of a syntactic diff, we address semantically the list of differences. We translate f m 1 and f m 2 into two formula φ 1 and φ 2 . Nevertheless, performing at the level of abstraction of Boolean variables may produce unexploitable results. Stated differently, a practitioner wants to understand differences in terms of feature modeling concepts rather than in terms of a propositional formula. As a result, we take care of producing meaningful information based on the analysis of the two formula.

Diff of information extracted from the two formula. A first general strategy consists in analyzing separately each formula and then performs the differences of the information produced.

Diff of binary implication (resp. exclusion) graphs. We consider a binary implication graph of an FM and its propositional formula φ as a directed graph BIG = (V imp , E imp ) formally defined as follows:

V imp = F E imp = {(f i , f j ) | φ ∧ f i ⇒ f j } (1)
Each binary, directed edge from feature f i to feature f j represents a binary implication. Based on the analysis of φ 1 and φ 2 , we can produce BIG 1 and BIG 2 and then compute

BIG dif f = BIG 1 \ BIG 2 .
It is then straightforward to compute the set of binary implications expressed in f m 1 but not in f m 2 . In the example of Figure 1, E impl dif f = {{destroy ⇒ mustOverride}, {applet ⇒ mustOverride}, {stop ⇒ mustOverride}, {init ⇒ mustOverride}}. As we support arbitrary propositional constraints in an FM, it should be noted that BIG dif f cannot be produced syntactically in the general case. Furthermore, the binary implication graph structure, reified from the propositional formula, has the advantage of exposing an information than can be directly translated in terms of feature modeling (i.e., either as a binary implication between a child feature and a parent feature or simply as an implies constraint). As a more general and powerful technique, the computation of BIG dif f should be used in favour of the syntactic diff of implies constraints. Diff of binary exclusion graphs. Similarly, we can compute the set of binary exclusions expressed in f m 1 but not in f m 2 . We consider a binary exclusion graph of an FM and its formula φ as an undirected graph, denoted BEG, consisting of vertices being features and edges denoting a mutual exclusion between two features f i and f j such that its formula φ entails f i ⇒ ¬f j . Then, BEG dif f = BEG 1 \ BEG 2 . In the example of Figure 1, the set of edges of BEG dif f is empty.

Diff of cliques in implication and exclusion graphs. We extend the previous technique to n-ary bi-implications and n-ary mutual exclusions. A n-ary bi-implication involves n features such that f i ⇒ f j for any i, j = 1 . . . n. It can be obtained by computing cliques in BIG. (A clique in the implication graph is a subgraph in which any two vertices are connected by an edge). A n-ary mutual exclusion involves n features f 1 , . . . , f n and is detected if there exists a clique between f 1 , . . . , f n in BEG. (A clique in the exclusion graph requires each member to have an exclusion to every other member.) For the purpose of conciseness (no set of features is subsumed by other), we compute maximal cliques in BIG and BEG. In the example of Figure 1, we detect that features applet and mustOverride are bi-implied. We do not learn additional difference for this specific example as a syntactic technique already produces such information. Nevertheless the semantic technique is particularly suitable when there are complex cross-tree constraints in an FM.

Semantic diff of feature groups. Reasoning techniques can be performed on φ to detect candidate feature groups (Xor and Or-groups). It is based on an important property: several FMs can represent the same set of configurations while having different hierarchies and feature groups. As a result some feature groups are not syntactically restituted in a feature diagram 5 . For example, in f m 1 , there are two candidate Or-groups {{{init, start, paint}, mustOverride}, {{init, start, paint}, applet}}, but only {{init, start, paint}, applet} is included in GOR 1 . To compute candidate feature groups, we rely on techniques exposed in [START_REF] Czarnecki | Feature diagrams and logics: There and back again[END_REF][START_REF] She | Reverse engineering feature models[END_REF] that perform over a propositional formula.

Reasoning about the two formula. A second general strategy consists in producing relevant information based on the logical combinations of the two formula. We first describe two existing techniques [START_REF] Thüm | Reasoning about edits to feature models[END_REF][START_REF] Fahrenberg | Vision paper: Make a difference! (semantically)[END_REF] relevant for FM differences.

Relationship between two FMs. Thüm et al. [START_REF] Thüm | Reasoning about edits to feature models[END_REF] reason on the nature of FM edits, for example, when f m 1 is edited (e.g., some features are moved, added, or removed), giving f m 2 . They provide a classification (see Definition 4) and an efficient algorithm to compute the kind of relationship between two FMs. In case the relationship is not a refactoring, the authors propose a technique to generate an example of configuration authorized in one but not in another.

Definition 4 (Edits

) f m 1 is a specialization of f m 2 if f m 1 ⊂ f m 2 ; f m 1 is a generalization of f m 2 if f m 1 ⊂ f m 2 ; f m 1 is a refactoring of f m 2 if f m 1 = f m 2 ; f m 1 is an arbitrary edit of f m 2 in other cases.
Quotient. In [START_REF] Fahrenberg | Vision paper: Make a difference! (semantically)[END_REF], an algorithm is presented that takes as input two formula φ 1 and φ 2 in conjunctive normal form (CNF) -FMs are easily converted to 5 In f m2, the features applet, mustOverride and init are semantically forming an Orgroup. This is not syntactically restituted in the feature diagram (see Figure 1(b)) and is considered as an anomaly in the literature [START_REF] Benavides | Automated analysis of feature models 20 years later: A literature review[END_REF]. This example, extracted from [START_REF] Fahrenberg | Vision paper: Make a difference! (semantically)[END_REF], can be seen as an additional argument in favour of a diff performing at the semantic level.

CNF. The algorithm finds for the quotient (i.e., difference) all clauses in φ 1 which are not entailed by φ 2 through the satisfiability checks of φ 2 ∧ ¬c (c being a clause of φ 1 ). As recognized, this is clearly an over-approximation of the difference, but might fail at maximality. In the example of Figure 1, the quotient is {{init ⇒ mustOverride}, {applet ⇒ mustOverride}} Diff of Formula. The two previous techniques fail to comprehensively represent the difference of the two configuration sets. To raise the limitations, we develop a diff operator, noted ⊕ \ , that takes as input two FMs and produces a diff FM (i.e., 2(a). The following defines the semantics of this operator:

f m dif f = f m 1 ⊕ \ f m 2 ). f m dif f is depicted in Figure
f m 1 \ f m 2 = {x ∈ f m 1 | x / ∈ f m 2 } = f m dif f (M 1 )
Computing the diff formula that f m dif f is as follows:

φ dif f = (φ 1 ∧ not(F 2 \ F 1 )) ∧ ¬(φ 2 ∧ not(F 1 \ F 2 ))
not is a function that, given a non-empty set of features, returns the Boolean conjunction of all negated variables corresponding to features:

not({f 1 , f 2 , ..., f n }) = i=1..n ¬f i
The presence of negated variables is needed since we need to emulate the deselection of features that are in f m 1 (resp. f m 2 ) but not in f m 2 (resp. f m 1 ). Otherwise, two features, say f 1 ∈ F 1 and f 2 ∈ F 2 such that f 1 = f 2 (i.e., f 1 does not match f 2 ), can be combined to form a configuration, thereby violating the configuration semantics of Definition M 1 . An important property of φ dif f is that each valid assignment (true/false values assigned to variables) corresponds to a valid configuration of f m dif f . With regards to maximality, it thus outperforms the quotient technique.

The connection between the characterization of edits (see Definition 4) and the diff operator is expressed by Lemma 1 (according to set theory,

f m 1 ⊆ f m 2 is equivalent to f m 1 \ f m 2 = ∅).
Lemma 1 (Diff and Specialization/Refactoring) f m 1 is a specialization or a refactoring of f m 2 if (f m 1 ⊕ \ f m 2 ) characterizes no valid configurations.

As a result, the satisfiability of φ dif f can be checked to determine the kind of relationship between f m 1 and f m 2 . In the example of Figure 1,f

m 1 is an arbitrary edit of f m 2 since f m 1 \ f m 2 = ∅ and f m 2 \ f m 1 = ∅.
From formula to an FM. Though the diff formula is useful for reasoning, we cannot render the formula "as is". Producing a complete FM (including the feature hierarchy, feature groups, etc.) is needed typically when an FM is visualized, serialized to a given format or when syntactic differencing techniques are applied. In this case, we need to transform the diff formula φ dif f as an FM. As stated above, several FMs can represent the same set of configurations [START_REF] Thüm | Reasoning about edits to feature models[END_REF][START_REF] Benavides | Automated analysis of feature models 20 years later: A literature review[END_REF][START_REF] She | Reverse engineering feature models[END_REF]. Intuitively, we want to maximize the parent-child relations that occur in the two input FMs. Furthermore not all feature hierarchies can be chosen (e.g., a hierarchy with start as a parent feature of mustOverride is too logically restrictive). The problem of choosing a hierarchy from amongst a set of hierarchies can be formulated as a minimum spanning tree problem over the binary implication graph of φ dif f . Based on the formula and the hierarchy, propositional logic techniques are applied to synthesize a complete FM (see [START_REF] Acher | A Domain-Specific Language for Managing Feature Models[END_REF]).

Composition and Decomposition of FMs

Computing the commonality and the union. It is interesting for a practitioner to determine the common properties of two FMs (rather than the differences). Syntactical techniques can be naturally applied (e.g., to determine common features). In previous work [START_REF] Acher | Comparing Approaches to Implement Feature Model Composition[END_REF], we propose a semantic operator, called merge, that computes an FM whose set of configurations is the intersection of the two sets of configurations. Using the merged FM, a practitioner can enumerate or count the common set of configurations or simply visualize it (see below for more details).

In the example of Figure 1, there are 15 common configurations. Another variant of the merge operator, denoted ⊕ ∪ , can compute an FM representing the union of the two sets of configurations. Complementing FMs. The need to complement an existing FM, say f m 2 , typically occurs when f m 2 is an underapproximation of f m 1 whereas it should not be the case. Therefore the differencing techniques are not only useful to detect an underapproximation but also to compute it and then integrate it in another model. Interestingly, we can combine the diff operator and the merge operators (in intersection or union mode). A possible application is, for instance, to compute an FM representing both configurations included in f m 2 but not in f m 1 and configurations included in f m 1 but not in f m 2 . It can be formalized in set theory and therefore automated using the techniques previously described:

f m 12comp = (f m 2 ⊕ \ f m 1 ) ⊕ ∪ (f m 1 ⊕ \ f m 2 )
. Such an FM can be used by practitioners to develop products not yet supported by existing solutions (i.e., neither by f m 1 not f m 2 ). f m 12comp is depicted in Figure 2(b).

Decomposing the problem of FM differences. Understanding and managing FM differences is a manual process and can quickly become difficult for a practitioner when a large number of features and constraints are involved. We thus propose to decompose the problem into subproblems. Intuitively, it is easier to focus on some parts of the two FMs rather than considering the two FMs in their entire form. In [START_REF] Acher | Slicing Feature Models[END_REF], we propose a semantic operator, called slice, that produces a projection of a FM (a slice) with respect to a set of selected features (slicing criterion). We define slicing as a unary operation on FM, denoted Π F slice (f m) where F slice = {f t 1 , f t 2 , ..., f t n } ⊆ F. The result of the slicing operation is a new FM, f m slice , semantically defined in terms of configuration set: f m slice = { x ∩ F slice | x ∈ f m } (called the projected set of configurations). In the context of FM differences, the slice operator can be applied on f m 1 and f m 2 using the same slicing criterion. For example, we apply the slice on f m 1 (the resulting FM is depicted in Figure 2(c)) and on f m 2 (the resulting FM is depicted in Figure 2(d)) using the slicing criterion F f oo = {applet, mustOverride, start, paint}. The two slice FMs can then be analyzed using the differencing techniques exposed throughout the section.

Tool Support: Language and Environment

We rely on FAMILIAR (for FeAture Model scrIpt Language for manIpulation and Automatic Reasoning) a domain-specific language for FMs [START_REF] Acher | A Domain-Specific Language for Managing Feature Models[END_REF]. The language already includes facilities for composing/decomposing FMs, editing FMs (e.g., renaming and removal of features), reasoning about FMs (e.g., validity, comparison of FMs) and their configurations (e.g., counting or enumerating the configurations in an FM). FMs and other types (configuration, set, etc.) are manipulated using variables. Compared to [START_REF] Acher | A Domain-Specific Language for Managing Feature Models[END_REF], we extend the language and integrate the differencing techniques developed in the paper through the form of operations over FMs (quotient, computation of candidate feature groups and implication / exclusion graphs, etc.). Basic operators to perform the union, intersection or difference of variables are also provided. Two reasoning back-ends (SAT solvers using SAT4J and BDDs using JavaBDD) are internally used and perform over propositional formula to implement the semantic operators. An important property of the language is that operations can be sequentially executed while properties of the variables can be observed. Hence, complex management scenarios can be applied using FAMILIAR environment. A practitioner can decompose the two FMs, then apply some techniques to understand local differences, edit the FMs, and reiterate the process. At the end, the FMs including their differences can be serialized in different formats and be used to pilot configuration or a generative approach.

Evaluation

Complexity

Performing differences at the semantic level, though more powerful, has a cost. The computation of BIG and BEG heavily depends on satisfiability checks of implications and exclusions. In practice, the computation of BIG and BEG scales for thousands of features and can be realized using SAT solvers or BDDs [START_REF] Czarnecki | Feature diagrams and logics: There and back again[END_REF][START_REF] She | Reverse engineering feature models[END_REF]. Due to transitivity of implication, maximal cliques (see Section 3.2) are actually strongly connected components in BIG, which can be found efficiently by graph traversal. Furthermore, the computation of cliques and Xor-groups scales for thousands of features [START_REF] She | Reverse engineering feature models[END_REF]. To the best of our knowledge, the computation of Or-groups has only been implemented using BDDs. We rely on BDDs to synthesize a complete FM from a formula. (SAT solvers can be used but in this case we do not restitute Or-groups). The cost of feature diagram construction is polynomial regarding the size of the BDD [START_REF] Czarnecki | Feature diagrams and logics: There and back again[END_REF]. We reuse the heuristics developed in [START_REF] Mendonca | Efficient compilation techniques for large scale feature models[END_REF] to reduce the size of the BDD -they scale up to 2000 features.

SAT solvers require a formula to be in CNF. Converting φ dif f into CNF requires φ 2 to be negated (see Equation M 1 ). As argued in [START_REF] Thüm | Reasoning about edits to feature models[END_REF], an exponential explosion of clauses occurs when φ 2 is negated, even for a small number of features. To avoid explosion, we rely on BDDs for computing and reasoning about φ dif f , since computing the disjunction, conjunction and negation of BDDs can be performed in at most polynomial time with respect to their sizes.

Applying differencing techniques: co-evolution of FMs

Case study. In [START_REF] Acher | Reverse Engineering Architectural Feature Models[END_REF], we presented a process for reverse engineering the FM of FraSCAti, a large and highly configurable component and plugin-based system. The overall challenge is to derive an FM so that its scope is not too large (otherwise some unsafe compositions are authorized) or too narrow (otherwise it is a symptom of unused flexibility). On the one hand, the FM produced by an automated procedure may not be an accurate representation, typically when FraSCAti artefacts do not correctly document the variability of the system. On the other hand, a software architect, while manually elaborating an intentional variability model of FraSCAti, may forget to specify some features or constraints. In order to manage (e.g., understand) the differences between the two FMs, we applied the techniques presented in the paper and the tool support.

Results and lessons learned. We now report what techniques have been used and how they helped to manage differences between the FMs. Further details and material (e.g., FAMILIAR scripts) about the case study are available in [1].

Implications. We first observed that the FMs involved have the following properties: an average of ≈ 50 features and ≈ 10 6 configurations per FMs, and a large number of cross-tree constraints (implies). Therefore we made an extensive use of the diff between binary implication graphs. It allowed one to identify dozens of implies constraints expressed in one FM but not in another (and vice-versa). Implies constraints are very important in the FraSCAti case study. First, the software architect elaborates the FM and specifies an important number of binary implications. Second, the extraction procedure combines different sources of information, including plugin dependencies. These dependencies are essentially expressed through implies constraints. The diff between binary implication graphs has the merit of reifying the differences of the two FMs in terms of implies constraints. It is then easier for a software architect to understand the impact of the difference: it is either an implication unintentionally not specified or an implication not documented by plugin dependencies. Compared to a syntactic diff, the major advantage of the structure of binary implication graph is the ability to derive transitive implications. The method of quotient produces some disjunctive clauses that can be transformed into implications. Nevertheless, we observed many times that the method suffers from a lack of completeness regarding the diff of implies constraints.

Or-groups vs Optional. We use a syntactic diff for computing feature groups expressed in one FM but not in another. A semantic diff for computing candidate feature groups, though more powerful in theory, does not produce additional information in this specific case study. The difference between feature groups concerns Or-groups. Indeed some features were modeled as optional features in the FM of the software architect whereas corresponding features formed an Orgroup in the FM produced by the automated procedure. This difference, though subtle, occurs for three Or-Groups and has to be identified and managed (since in one case it is possible to not select any feature).

Decomposition. The compared FMs did not necessary have the same set of features (e.g., some features are added when a new version of FraSCAti is released). The features included in one FM but not in another disturb the management of differences. Intuitively, such features produce new configurations but we were mostly interested by the evolution of the common subset. Therefore we made an extensive use of the decomposition operator (i.e., slice, see Section 3.3) by focusing only on features commonly shared by the two FMs. We then applied the differencing techniques on the decomposed FMs. In particular, it made possible to determine if the common subset has correctly evolved and that no configuration has been broken (i.e., the refactoring or generalization property holds, see Definition 4).

Interactive process. Managing differences is not a simple one step-process. Once differences have been identified and understood, we edited FMs accordingly and reiterated the process until having satisfying FMs. Therefore the process is rather incremental and interactive. Automation and reproducibility of the operations are indeed crucial.

Opportunities for future work. The extracted FM and the FM elaborated by the software architect use different names for features that are actually similar. To avoid unexploitable differencing results, some predirectives were needed and consist in manually renaming features. More automated support seems desirable and matching techniques already integrated in model-based tools (e.g., see [START_REF] Euzenat | Ontology matching[END_REF][START_REF] Kolovos | Different models for model matching: An analysis of approaches to support model differencing[END_REF]) are good candidates. At the current state of the research, it is difficult to assess the significance of the FM matching problem in practice. Many techniques exposed in this paper can be combined on demand to manage differences. We observed that some information produced are sometimes redundant (e.g., the method of quotient detects a binary implication, already detected by the diff of binary implication graphs). To reduce the cognitive process of a practitioner, an interesting perspective is to summarize the differences (by aggregating informa-tion produced by the differencing techniques so that there is no redundancy). We leave it as future work. Another direction for future work is to provide guidelines and a methodological proposal that could help non-experts to apply all these operators in practice. The usability of the approach (e.g., whether the produced information is understandable enough) should be evaluated accordingly using other case studies.

Related Work

Model differencing has attracted research efforts in recent years, including the development of tools (e.g., see [START_REF]Bibliography on Comparison and Versioning of Software Models[END_REF][START_REF] Kolovos | Different models for model matching: An analysis of approaches to support model differencing[END_REF][START_REF] Maoz | A manifesto for semantic model differencing[END_REF][START_REF] Maoz | A manifesto for semantic model differencing[END_REF][START_REF] Maoz | Addiff: semantic differencing for activity diagrams[END_REF][START_REF] Maoz | Cddiff: semantic differencing for class diagrams[END_REF]). The bibliography [START_REF]Bibliography on Comparison and Versioning of Software Models[END_REF] compiles about 300 publications in this field. Existing approaches mainly focus on syntactical differences. As argued in [START_REF] Maoz | A manifesto for semantic model differencing[END_REF][START_REF] Fahrenberg | Vision paper: Make a difference! (semantically)[END_REF], models (e.g., FMs) that are syntactically very similar may induce very different semantics and a list of differences should be best addressed semantically. Maoz et al. define a semantic diff as an operator that takes as input two models and outputs a set of diff witnesses, i.e., instances of one model that are not instances of the other [START_REF] Maoz | A manifesto for semantic model differencing[END_REF]. In our context, instances are configurations and the set of witnesses is finite and can be enumerated if needs be. Fahrenberg et al. propose an alternative definition of a semantic diff and argue that a difference between models should be a model [START_REF] Fahrenberg | Vision paper: Make a difference! (semantically)[END_REF]. One contribution of our work is precisely to compute a diff FM.

Recently, Maoz et al. tackled the problem of semantic model differencing, specifically for class and activity diagrams [START_REF] Maoz | Addiff: semantic differencing for activity diagrams[END_REF][START_REF] Maoz | Cddiff: semantic differencing for class diagrams[END_REF]. They defined and implemented two versions of semantic diff operator, cddiff and addiff. The cddiff operator [START_REF] Maoz | Cddiff: semantic differencing for class diagrams[END_REF] takes as inputs two class diagrams and computes diff witnesses using Alloy Analyzer, a solver for first-order logic. For the addiff operator, they presented algorithms that take as input activity diagrams [START_REF] Maoz | Addiff: semantic differencing for activity diagrams[END_REF]. These two contributions, as ours, are specific to a given formalism and its associated semantics. A few works consider semantic diff between programs, e.g., Jackson and Ladd summarize the semantic diff between two procedures in terms of observable input-output behaviors [START_REF] Jackson | Semantic diff: A tool for summarizing the effects of modifications[END_REF]. We focus on model comparison and not on program comparison.

In the field of feature modeling, Benavides et al. [START_REF] Benavides | Automated analysis of feature models 20 years later: A literature review[END_REF] survey a set of operations and techniques proposed for automated analysis of FMs. No automated techniques have been reported to reason about or compute differences. A notable exception is the algorithm described in [START_REF] Thüm | Reasoning about edits to feature models[END_REF], which classifies the evolution of an FM via modifications (see Section 3.2). The algorithm can be used in the context of FM differences but have two limitations. First, the kind of relationship between two FMs does not help to precisely understand the impact of a change, e.g., what implies or excludes constraints have been removed and added. Second, the technique does not compute all added and removed configurations. In [START_REF] Fahrenberg | Vision paper: Make a difference! (semantically)[END_REF], the authors illustrate their vision and theory of semantic model differences using FMs. They propose an algorithm to compute the quotient (see Section 3.2). As recognized in [START_REF] Fahrenberg | Vision paper: Make a difference! (semantically)[END_REF], the quotient is an approximation of the differences between two FMs whereas the diff FM is not. Another limitation is that the quotient is a set of disjunctive clauses that are difficult to understand for a practitioner (see Section 4.2). In practice, an additional step seems necessary to transform these clauses into a more readable and manageable information, closer to FM constructs. Segura et al. propose a catalog of rules for merging FMs (union and intersection) [START_REF] Segura | Automated merging of feature models using graph transformations[END_REF]. They present syntactic mechanisms (see a comparison in [START_REF] Acher | Comparing Approaches to Implement Feature Model Composition[END_REF]) and no diff operator is considered. The works exposed in [START_REF] Pleuss | Modeldriven support for product line evolution on feature level[END_REF][START_REF] Dhungana | Structuring the modeling space and supporting evolution in software product line engineering[END_REF] developed a set of operators to make evolve FMs but no differencing technique is proposed to control the evolution of the FMs.

Conclusion

Feature models (FMs) are widely used to compactly represent the valid combinations of features (i.e., configurations) supported by a given system. In several application domains and contexts (e.g., software evolution), differences between two FMs should be managed, for example, to identify what are the configurations of an FM that are not included in another. We presented a set of techniques to understand, compute and reason about such differences. The techniques perform at the semantic level (i.e., in terms of sets of configurations) and present relevant information reified from the analysis of propositional formula. A practitioner can detect a difference (e.g., for the purpose of debugging), compute the differences as an FM and then integrate the differences into an existing FM. The tool-supported techniques overcome limitations of earlier attempts and are proved to be essential in a case study.

As future work, we plan to evaluate further the practicality and usefulness of the proposed solution. We hope these insights can contribute to a methodology that guide practitioners in managing FM differences.

Fig. 2 .

 2 Fig. 2. Diff FM, merge in union mode of two FMs, two slice FMs

This assumption is shared by[START_REF] Segura | Automated merging of feature models using graph transformations[END_REF][START_REF] Thüm | Reasoning about edits to feature models[END_REF][START_REF] Fahrenberg | Vision paper: Make a difference! (semantically)[END_REF] and holds for all the case studies presented in the introduction. The problem of FM matching is discussed in Section 4.2

Acknowledgement. This work was supported by the FNRS, the University of Namur, the FP7 Marie-Curie COFUND program, the Interuniversity Attraction Poles Programme, Belgian Science Policy (MoVES), the BNP, the french ANR SALTY project (https://salty.unice.fr) under contract ANR-09-SEGI-012, and the French Ministry of Higher Education and Research, Nord-Pas de Calais Regional Council and FEDER through the CPER-CIA 2007-2013.


Gaurav Sharma

Frédéric Jurie

Cordelia Schmid

Discriminative Spatial Saliency for Image Classification

In many visual classification tasks the spatial distribution of discriminative information is (i) non uniform e.g. person 'reading' can be distinguished from 'taking a photo' based on the area around the arms i.e. ignoring the legs and (ii) has intra class variations e.g. different readers may hold the books differently. Motivated by these observations, we propose to learn the discriminative spatial saliency of images while simultaneously learning a max margin classifier for a given visual classification task. Using the saliency maps to weight the corresponding visual features improves the discriminative power of the image representation. We treat the saliency maps as latent variables and allow them to adapt to the image content to maximize the classification score, while regularizing the change in the saliency maps. Our experimental results on three challenging datasets, for (i) human action classification, (ii) fine grained classification and (iii) scene classification, demonstrate the effectiveness and wide applicability of the method.

Introduction

The human visual system is capable of analyzing images quickly by rapidly changing the points of visual fixation. Estimating the distribution of such points i.e. the visual saliency is an important problem in computer vision [START_REF] Itti | A model of saliency-based visual attention for rapid scene analysis[END_REF][START_REF] Koch | Shifts in selective visual attention: Towards underlying neural circuitry[END_REF][START_REF] Murray | Saliency estimation using a non-parametric low level vision model[END_REF][START_REF] Wang | Image saliency: From intrinsic to extrinsic context[END_REF]. Initial works on visual saliency detection addressed generic saliency, highlighting (generally interesting) properties such as edges, contours, color, texture etc., building on the feature integration theory [START_REF] Koch | Shifts in selective visual attention: Towards underlying neural circuitry[END_REF][START_REF] Treisman | A feature-integration theory of attention[END_REF]. For visual discrimination, generic visual saliency should be adapted to include task specific information. Many works [START_REF] Gao | Discriminant saliency for visual recognition form cluttered scenes[END_REF][START_REF] Gao | Integrated learning of saliency, complex features and object detectors from cluttered scenes[END_REF][START_REF] Moosmann | Learning saliency maps for object categorization[END_REF], thus, define and compute saliency based on the discriminative power of local features i.e. how much does a feature contribute towards separating the classes. Such feature based discriminative saliency has been shown to be important in automatic visual analysis.

Furthermore, in many visual classification tasks there is a spatial bias which complements global feature saliency Figure 1. Example images and their spatial saliency maps obtained with our algorithm for 'interacting with computer', 'taking photo', 'playing music', 'walking' and 'ridinghorse' action classes (higher values are brighter). e.g. for the 'coast' class in scene classification, sky-like regions are salient, not everywhere but in the upper part of an image. Thus, we argue that given a class, visual saliency is attributed to different local regions based on their appearance and their spatial location in an image i.e. a task specific spatial saliency is associated with each image.

In the present paper, we (i) extend the notion of discriminative visual saliency by including discriminative spatial information and (ii) learn it, together with the classifier, to obtain a more discriminative image representation for visual classification. Contrary to previous works [START_REF] Gao | Discriminant saliency for visual recognition form cluttered scenes[END_REF][START_REF] Gao | Integrated learning of saliency, complex features and object detectors from cluttered scenes[END_REF][START_REF] Itti | A model of saliency-based visual attention for rapid scene analysis[END_REF][START_REF] Khan | Top-down color attention for object recognition[END_REF][START_REF] Koch | Shifts in selective visual attention: Towards underlying neural circuitry[END_REF][START_REF] Moosmann | Learning saliency maps for object categorization[END_REF] that use saliency of features, irrespective of their positions, we work with saliency of regions in space i.e. for the 'ridinghorse' class instead of saying 'look for horse like features' we say 'look for horse like features in the lower part of the image'. Fig. 2 illustrates this point and Fig. 1 shows saliency maps obtained by our method.

Our definition of saliency is closely coupled with learning the classifier, unlike previous work which learn the saliency map and the classifier separately [START_REF] Gao | Discriminant saliency for visual recognition form cluttered scenes[END_REF][START_REF] Gao | Integrated learning of saliency, complex features and object detectors from cluttered scenes[END_REF][START_REF] Parikh | Determining patch saliency using low-level context[END_REF]. We learn the classifier while simultaneously modeling saliency in an integrated max margin learning framework. We formulate saliency in terms of local regions, and the learning based on a latent SVM framework adapted to incorporate the saliency model. We show that our saliency model improves results on three challenging datasets for (i) human action classification in images [START_REF] Delaitre | Learning person-object interactions for action recognition in still images[END_REF], (ii) fined grained classification i.e. persons playing vs. holding musical instruments [START_REF] Yao | Combining randomization and discrimination for fine-grained image categorization[END_REF] and (iii) scene classification [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF].

Related work

Visual saliency has been investigated in the computer vision literature in many different ways. Salient local regions have been detected using interest points (e.g. [START_REF] Lowe | Distinctive image features form scale-invariant keypoints[END_REF]19]) which can be made invariant to image transformations (e.g. rotation, scale, affine) and, thus, can be detected reliably and repeatably. They have been very successful for matching images under different transformations [START_REF] Lowe | Distinctive image features form scale-invariant keypoints[END_REF]19]. Such regions were also used to sample small sets of salient patches from images for classification with bag-of-features representations [3], but dense (regular or random) sampling has been shown to perform better [START_REF] Nowak | Sampling strategies for bag-of-features image classification[END_REF] and is currently the state-of-the-art [START_REF] Everingham | The PASCAL Visual Object Classes Challenge[END_REF].

Biologically inspired saliency, based on the feature integration theory [START_REF] Treisman | A feature-integration theory of attention[END_REF], motivated another line of work. Regions were marked as salient depending on the difference with their surrounding area [START_REF] Itti | A model of saliency-based visual attention for rapid scene analysis[END_REF][START_REF] Koch | Shifts in selective visual attention: Towards underlying neural circuitry[END_REF], measured using low level features e.g. edges, texture, contours. Such generic saliency was further adapted to discriminative saliency [START_REF] Gao | Discriminant saliency for visual recognition form cluttered scenes[END_REF][START_REF] Gao | Integrated learning of saliency, complex features and object detectors from cluttered scenes[END_REF][START_REF] Khan | Top-down color attention for object recognition[END_REF][START_REF] Moosmann | Learning saliency maps for object categorization[END_REF], where, given a visual classification task, saliency was defined by the capability of the features to separate the classes.

Moosmann et al. [START_REF] Moosmann | Learning saliency maps for object categorization[END_REF] learn saliency maps for visual search to improve object categorization. Gao and Vasconscelos [START_REF] Gao | Discriminant saliency for visual recognition form cluttered scenes[END_REF] formulate discriminative saliency and determine it based on feature selection in the context of object detection [START_REF] Gao | Integrated learning of saliency, complex features and object detectors from cluttered scenes[END_REF]. Parikh et al. [START_REF] Parikh | Determining patch saliency using low-level context[END_REF] learn saliency in an unsupervised manner based on how well a patch can predict the locations of others. Khan et al. [START_REF] Khan | Top-down color attention for object recognition[END_REF] model color based saliency to weight features. Harada et al. [START_REF] Harada | Discriminative spatial pyramid[END_REF] learn weights on regions for classification. However, they learn the weights per class i.e. the weights are the same for all images. Yao et al. [START_REF] Yao | Combining randomization and discrimination for fine-grained image categorization[END_REF] learn a classifier with random forests.

They mine salient patches, for the decision trees, by randomly sampling patches and selecting the most discriminative ones.

We model saliency based on the contribution of regions to classification i.e. our saliency is discriminative. We do not discard features, but weight them using the saliency map, which differs from e.g. [START_REF] Gao | Integrated learning of saliency, complex features and object detectors from cluttered scenes[END_REF][START_REF] Nowak | Sampling strategies for bag-of-features image classification[END_REF][START_REF] Parikh | Determining patch saliency using low-level context[END_REF]. Our model incorporates saliency modeling into the learning of separating hyperplane in a max margin framework. Hence, our saliency is more tightly coupled with the visual discrimination task unlike many previous works where learning saliency and classifiers are separate steps e.g. [START_REF] Gao | Discriminant saliency for visual recognition form cluttered scenes[END_REF][START_REF] Gao | Integrated learning of saliency, complex features and object detectors from cluttered scenes[END_REF][START_REF] Khan | Top-down color attention for object recognition[END_REF][START_REF] Parikh | Determining patch saliency using low-level context[END_REF].

Recently, latent support vector machine (LSVM) classifiers have shown promise in many visual tasks. Felzenszwalb et al.

[8] use LSVM for part based object detection which has become a standard component in state-of-the-art systems [START_REF] Everingham | The PASCAL Visual Object Classes Challenge[END_REF]. Bilen et al. [START_REF] Bilen | Object and action classification with latent variables[END_REF] model the position and size of the objects using LSVM for image classification. We adapt the LSVM formulation to incorporate saliency modeling. In our model the image saliency maps are latent variables and are thus integrated with learning the classifier.

Approach

We define image saliency as a mapping s : G → R, where G is a spatial partition of the image, c ∈ G is a region of the image and s(c) gives the saliency of the region. Our method is general and can work with any spatial partition of the images e.g. G can be the set of all image pixels, as in traditional saliency, or a set of user specified regions. We choose G to be the set of cells obtained with a spatial pyramid like uniform grid [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF]. This is motivated by two reasons. First, we have a variable corresponding to every element of G for every image and, since contemporary visual discrimination datasets [START_REF] Delaitre | Recognizing human actions in still images: A study of bag-of-features and partbased representations[END_REF][START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF][START_REF] Yao | Grouplet: A structured image representation for recognizing human and object interactions[END_REF] have limited number of training images, using very fine regions e.g. pixels would make the number of variables very large compared to the training data. Second, the spatial pyramid, despite of its simplicity, is competitive with methods using more complex spatial models [START_REF] Everingham | The PASCAL Visual Object Classes Challenge[END_REF]. Given our choice of G, we can equivalently write a saliency map as an ordered list of real values i.e. s = {s c |c ∈ G} where we use the row major order of the grid cells (Fig. 3a).

We work in a supervised binary classification scenario with given training images I i ∈ I and corresponding class labels y i ∈ {-1, 1}. Our model consists of three components, (i) the separating hyperplane w, (ii) the image saliency maps s i for images I i ∈ I and (iii) a generic saliency map s for regularizing the image saliency maps. The saliency map of an image maximizes the classification score while penalizing its deviation from the generic saliency map. Our full model is obtained by solving a maxmargin optimization problem with the image saliency maps as latent variables. We present our model in the following sections.

Maximum margin formulation

Given a saliency map s i = {s i c |c ∈ G} for the i th image, we represent the image with the saliency map weighted concatenation of bag-of-features (BoF) histograms for the grid cells (Fig. 3a), i.e.

x i = [s i 1 h i 1 . . . s i c h i c . . .], (1)
where h c is the BoF histogram for cell c ∈ G with appropriate normalization. As noted in [27], normalization plays an important role, and we discuss this in more detail later.

We cast the problem in a maximum margin latent SVM framework with the image saliency maps {s i |I i ∈ I} as latent variables. The optimization with hinge loss becomes

min w 1 2 ||w|| 2 + C i max(0, 1 -y i f (x i , w)), ( 2
)
where f is the scoring function (Sec. 2.2, Eq. 3). Latent SVMs have been very popular recently in the computer vision community [START_REF] Bilen | Object and action classification with latent variables[END_REF]8]. They lead to a semiconvex optimization i.e. the objective function is convex if the latent variables for the positive examples are fixed.

Image score

We score a given image as f (x, w) = max s w T x (omitting superscript i for brevity) i.e. we allow the saliency map of the image to change to maximize its score w.r.t. the separating hyperplane. However, this leads to the trivial solution of selecting the highest scoring cell. To avoid this, we introduce a new variable, a generic saliency map, s. We penalize the score proportional to the deviation of the image saliency map from s. This regularizes the image saliency maps and gives smoother maps. The final score is thus obtained as

f (x, w) = max s w T x -λ(s -s) T (s -s), ( 3
)
where λ is the parameter controlling the trade off between maximizing the score by varying the saliency map and deviation of the image saliency map from s. We rewrite the first term of the score as

w T x = |G| c=1 s c K k=1 w (c-1)•K+k h ck = s T D w H T , ( 4
)
where K is the size of BoF codebook,

H T = [h T 1 . . . h T |G| ]
(concatenation of cell BoF histograms with appropriate normalization) and

D w =    w 1 . . . w K 0 . . . 0 w (|G|-1)•K+1 . . . w |G|K    .
Normalization of the BoFs. As noted by Vedaldi et al. [27], in the context of linear classifiers, unnormalized histograms favor (assign relatively larger scores to) larger regions, L1 normalization favors smaller regions while L2 normalization is neutral and thus ideal. In our experiments, the images are of different size and the grids, specified in terms of fractional multiples of image width and height, results in different sized regions which makes normalization important. Harzallah et al. [START_REF] Harzallah | Combining efficient object localization and image classification[END_REF] had also previously noted that normalizing each cell separately instead of globally normalizing the whole descriptor gives slightly better results. Our preliminary experiments resulted in similar conclusions and in our final implementation we work with per-cell L2 normalized vectors i.e. each of the h c are L2 normalized independently. The optimization problem in Eq. 3, after rewriting the first term using Eq. 4, takes a closed form solution (for s) involving matrix operations and is very fast to compute.

Regularized formulation

By introducing s into the formulation we have introduced another source of scaling. Everything else fixed, by scaling Algorithm 1 Stochastic gradient descent for w (s fixed) Calculate the saliency map s i iff y i = -1 5:

if y i f (x i , w) ≥ 1 then 6:
w ← w -l w t w 7:

else 8: w ← w -l w t (w -CN y i x i ) 9:
end if 10: end while Algorithm 2 Stochastic gradient descent for s (w fixed)

if y i f (x i , w) ≥ 1 then 6: s ← s -l s t γ(s -1) 7: else 8: s ← s -l s t (γ(s -1) + 2CN y i λ(s -s i )) 9:
end if 10: end while the magnitude of s we can change the image scores (as the saliency maps are multipliers in the score function). Thus, we can decrease the objective value without making any generalizable progress. To control such scaling we augment the objective function with a regularization term for s, which penalizes deviation from a uniform map which assigns unit weight to each cell similar to the (individual levels of) standard spatial pyramid, as

L(w, s) = 1 2 ||w|| 2 + γ 2 ||s-1|| 2 +C i max(0, 1-y i f (x i )).
(5) We now have one more parameter, γ > 0, to control the regularization of s. As the scales of s and w are different we can not expect similar regularization w.r.t. loss, i.e. parameter C to work for both. Thus the model has three parameters for controlling different regularizations γ, C, λ.

The parameter C (cf. the standard SVM parameter) and γ control the relative trade-offs between constraint violation, margin maximization and regularization of s. The parameter λ controls the regularization of the saliency map for each image. To gain some more intuition about the parameter λ, consider the two limiting cases. In the first limiting case, when λ → ∞, we have a highly smoothed model which forces all saliency maps to be the same as the generic saliency. In the other limiting case, when λ is zero, we have no smoothing and the saliency maps put all the weight on the best scoring cell per image.

Solving the optimization problem

We solve the problem with a block coordinate descent algorithm. We treat w and s as two blocks of variables and alternately optimize on one while keeping the other fixed. Fig. 3b illustrates the learning process. In each of the inner iterations we optimize using stochastic gradient descent as detailed in Algorithms 1 and 2, where we use (the stochastic approximations of) the sub-gradient w.r.t. w,

∇ w L = w + C i g w (x i ) (6)
g w (x i ) = 0 if y i F (x i ) ≥ 1 -y i x i otherwise, (7)
and sub-gradient w.r.t. s,

∇ sL = γ(s -1) + C i g s(x i ) (8) g s(x i ) = 0 if y i F (x i ) ≥ 1 2y i λ(s -s i ) otherwise. ( 9
)
While keeping s fixed we get a semi convex LSVM-like optimization [8] for w. Unfortunately, that is not the case for the optimization of s as, with w fixed, the hinge loss for each example is concave w.r.t. s (the coefficient of sT s is -λ < 0). Thus, the total hinge loss (being the maximum over one convex i.e. zero function, and multiple concave functions i.e. per example hinge losses) is, in general, non convex and the algorithm will converge to a local minimum for s. To make sure that it does not end up in a very bad local minimum, we initialize w with a perturbed version of that learned using the baseline SVM (same optimization with all components of s and {s i |I i ∈ I} fixed to 1). Since we are directly minimizing the primal we can expect approximations to generalize reasonably [START_REF] Chapelle | Training a support vector machine in the primal[END_REF]. In practice, we find that the models computed by our implementation perform well.

Parameters. We find initial learning rates l w 0 and l s 0 by performing preliminary experiments on a subset of the full data and then we decrease the learning rates every iteration by dividing by the iteration number i.e. l t = l 0 /t (as is common with stochastic gradient methods). We fix C = 1 for all experiments (this gives similar results on average as with C obtained by cross validation) and select λ and γ by cross validation on the training data.

Nonlinearizing using a feature map. Recent progress in explicitly computing the feature maps [START_REF] Vedaldi | Efficient additive kernels using explicit feature maps[END_REF] induced by different non linear kernels allows us to address non linearity. The approach is to apply the non linear map to compute the feature vectors explicitly, and work with linear algorithms in the feature space.

We transform the histograms by taking their elementwise square roots i.e. φ(h) = √ h. It is known [START_REF] Vedaldi | Efficient additive kernels using explicit feature maps[END_REF] that the product of the resulting vectors is equal to the Bhattacharyya kernel between the original histograms. Hence, using the feature map is equivalent to working with the non linear Bhattacharyya kernel, which has been shown to give better results than the linear kernel. We L1 normalize the original histograms so that the feature mapped vectors are L2 normalized.

Experimental results

We evaluate our method on three challenging datasets for (i) human action classification in still images [START_REF] Delaitre | Learning person-object interactions for action recognition in still images[END_REF], (ii) fine grained classification of humans playing musical instruments vs. holding them [START_REF] Yao | Combining randomization and discrimination for fine-grained image categorization[END_REF] and (iii) scene classification [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF]. We first give the details of our implementation and baselines and then proceed to present and discuss the results on the three datasets.

Bag-of-features. Like previous works [START_REF] Delaitre | Recognizing human actions in still images: A study of bag-of-features and partbased representations[END_REF][START_REF] Yao | Combining randomization and discrimination for fine-grained image categorization[END_REF] we densely sample grayscale SIFT features at multiple scales. We use a fixed step size of 4 pixels and use square patch sizes at 7 scales ranging from 8 to 40 pixels. We learn a vocabulary of size 1000 using k-means and assign the SIFT features to the nearest codebook vector (hard assignment). We use the VLFeat library [START_REF] Vedaldi | VLFeat: An open and portable library of computer vision algorithms[END_REF] for SIFT and k-means computation.

Spatial pyramid (SP and overlapping SP).

We use a four level spatial pyramid but instead of the usual non overlapping cells with uniform grids we expand the cells by 50% and let them overlap i.e. 2 × 2 cells are 3/4 of the height (width) instead of 1/2. We found that doing so provides better statistics (less sparse histograms) for finer cells and improves performance. This is inspired by the idea of 'non sparsification' of vectors [START_REF] Perronnin | Improving the Fisher kernel for large-scale image classification[END_REF]. We discuss this more in Sec. 3.4. Our initial experiments gave similar results with classifiers trained on the full pyramid descriptor and the weighted sum of descriptors from each level. We train classifiers for each level separately and combine levels, for the baselines as well as our method, by the weighted sum of classifier scores. The weights sum to one over all levels and are higher for finer resolution levels similar to previous work [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF].

Baselines. We use SP and overlapping SP, as baselines, with linear SVM trained without our saliency model i.e. we fix all the saliency maps to be uniform in the optimization reducing it to standard linear SVM with spatial BoF. The baseline results are obtained with the liblinear [7] library.

Performance measure. The performance is evaluated based on average precision (AP) for each class and the mean average precision (mAP) over all classes.

Willow actions

Willow actions1 [START_REF] Delaitre | Recognizing human actions in still images: A study of bag-of-features and partbased representations[END_REF] is a challenging database for action classification on unconstrained consumer images downloaded from the internet. It has 7 classes of common human actions e.g. 'ridingbike', 'running'. It has at least 108 images per class of which 70 images are used for training and validation and rest are used for testing. The task is to predict the action being performed given the human bounding box. Like previous work [START_REF] Delaitre | Learning person-object interactions for action recognition in still images[END_REF], we expand the given person bounding boxes by 50% to include some contextual information. Fig. 5a shows example images and their saliency maps obtained with our model and Tab. 1 gives quantitative results on the Willow actions dataset. Our implementation of the baseline spatial pyramid [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF] achieves an mAP of 62.6% while that of a spatial pyramid with overlapping cells improves by 2%. Our model obtains 65.9% which is the stateof-the art result on this dataset. To compare with previous works, Delaitre et al. [START_REF] Delaitre | Learning person-object interactions for action recognition in still images[END_REF] obtain an mAP of 64.1% with a method modeling person-object interactions. Note that they model complex interactions between objects and body parts while using external data to train the several object and body part detectors.

Our method gives best results for four out of seven categories. The most significant improvement is obtained on the 'ridinghorse' class which has a strong spatial bias for horse and grass in the bottom part of the image. The saliency map modeling effectively exploits this (Fig. 5a). The drop on 'ridingbike' class can be explained by the limitation of the method to improve performance if the classifier is able to separate the training data almost perfectly and if there is not enough training data (Sec. 3.4).

People playing musical instruments

People playing musical instruments (PPMI)2 [START_REF] Yao | Combining randomization and discrimination for fine-grained image categorization[END_REF] is a dataset emphasizing subtle difference in interactions between humans and objects (fine grained classification). It contains classes with humans interacting with i.e. either There are two tasks for this dataset (i) 24 class classification with each class being the human playing and holding the 12 instruments and (ii) 12 binary classifications for human playing vs. holding the instruments. Fig. 5b shows some example images and their saliency maps and Tab. 2 shows our results on the PPMI datasets for 24 class multi-class classification (Task 1) and 12 binary classification problems (Task 2) respectively. For Task 1 the spatial pyramid baseline achieves 45.3% and the overlapping spatial pyramid achieves 46.6% improving by 1.3%. Our method achieves a mAP of 49.4% which is state of the art for the dataset. In comparison to previous methods, we improve by 12.7% compared to Yao et al.'s Grouplet [START_REF] Yao | Grouplet: A structured image representation for recognizing human and object interactions[END_REF] and by 2.4% compared to their Random Forest classifier [START_REF] Yao | Combining randomization and discrimination for fine-grained image categorization[END_REF]. For Task 2 the baselines are at 89.2% and 90.3% while our method achieves 91.2% compared to 85.1% of Grouplet [START_REF] Yao | Grouplet: A structured image representation for recognizing human and object interactions[END_REF] and 92.1% of Random Forest classifier [START_REF] Yao | Combining randomization and discrimination for fine-grained image categorization[END_REF]. The Grouplet method uses patches at only one scale which can perhaps explain its lower performance. Note that the Random Forest classifier has a much higher complexity than our approach, as it uses 100 decision trees. At each node of the tree they evaluate a linear SVM decision thus effectively performing 100s of vector dot products, whereas our approach only has one such computation. We perform slightly worse that the state of the art in Task 2 due to performance saturation, see Sec. 3.4 for a discussion.

Scene 15

Scene 15 3 [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF] is a dataset containing 15 scene categories, e.g. 'beach', 'office', with 4485 images. The task is multi-class classification with the dataset split into 100 3 http://www-cvr.ai.uiuc.edu/ponce grp/data/ random images per class for training and the rest for testing. Like previous works, we repeat the experiment 10 times and report the mean and standard deviation.

Fig. 5c shows some example images and their saliency maps and Tab. 3 show our results on the scene 15 dataset for 15 binary one-vs-rest classification problems. Our traditional and overlapping spatial pyramid baselines achieve a performance of 81.8% and 82.6% resp. for 3 levels. Our method achieves 85.5% improving the better baseline by 2.9%. It is interesting to note that our method at a low pyramid level of 2 already beats the best baseline obtained at a higher pyramid level of 3, which indicates a coarse spatial bias in the dataset. The state-of-the-art method on this dataset [START_REF] Xiao | Sun database: Large scale scene recognition from abbey to zoo[END_REF] achieves 88.1% (mean class accuracy). However, they combine 14 different low level features. Our best result is comparable to Krapac et al. [START_REF] Krapac | Learning tree-structured descriptor quantizers for image categorization[END_REF], who used a similar setup as ours and achieved mAP of 85.6%. Note that they quantized features using discriminatively trained decision trees outperforming k-means based quantization. In the current paper, we have used k-means and arguably our results would improve further using similar stronger quantization instead.

Overlapping cells and training saturation

We use overlapping cells for the spatial pyramid decomposition. As noted by Perronnin et al. [START_REF] Perronnin | Improving the Fisher kernel for large-scale image classification[END_REF], when sparseness of the vectors increases, the performance of linear SVM decreases. This is because the more robust distance with sparse vectors is L1 while linear SVM corresponds to the L2 distance. To decrease the effect of sparsity we take overlapping cells in the spatial pyramid partition by increasing the sizes of the cells by 50%. Fig. 4 (left) shows the performances for different codebook sizes on the Willow actions dataset. We notice that for larger codebook sizes of 500 and 1000 the overlapping SP performs better than the non overlapping one but the difference is not significant for a codebook size of 100. As the codebook size increases, but the number of features stays the same, the sparsity of the histogram increases. Thus, pooling more features by increasing the size of the cells performs better, as the sparsity of the histograms is decreased.

We can also observe that our approach does not gain much when the training data is well separated i.e. the baseline SVM is saturated. This can occur when there is not enough training data or the task is relatively easy. In saturated cases the number of vectors within the margin-which effectively contribute towards refining the hyperplane-is small (< 100) and the saliency model is not able to derive additional information from so few examples. Fig. 4 (right) shows the performance for the different pyramid combinations for the Willow actions dataset. We observe that as the pyramid level increases, the gap between the baselines and the proposed method decreases due to increase in train- ing saturation. The trend is similar for increasing codebook size, Fig. 4 (left). This also explains why we get little or no improvement for the 'ridingbike' class (Tab. 1) and the Task 2 of PPMI dataset (Tab. 2b).

Qualitative results

Fig. 5 shows example images from two classes for each of the three datasets together with their saliency maps. We can observe that the saliency maps focus on those parts of the images which we expect to be discriminative. For example, in the action class 'ridinghorse' the saliency maps give high weights to the lower regions which are expected to be salient as they contain the horse and grassy texture which are highly correlated with the class. The person (in the typical riding pose) is not weighted highly, because it might be confused with 'ridingbike', stressing the discriminative nature of the maps.

Furthermore, per image adaptation can be seen in all the examples. In the 'playingmusic' class the maps follow the hands and the musical instruments and differ for every image. A similar observation holds for 'tallbuilding' class where the middle part of the buildings seems to be more discriminative probably because of predominant sky in the upper part of many images.

The correlation between the locality of the task and the peaks in the maps is also clearly visible. A strong contrast is apparent between the 'playingmusic' class of the Willow actions dataset and the similar 'violin' and 'erhu' classes of PPMI dataset. In the actions dataset the discrimination is against more general actions ('running', 'photographing' etc.) and hence the maps capture the instrument, the pose of the hands etc. and have relatively spread out maxima. In contrast, for 'violin' and 'erhu' classes the maps have sharp peaks as the task is to differentiate between holding vs. playing instruments. The maps here quite accurately focus on the region of discriminative interaction between the person and the instrument.

Conclusion

We have presented a method for learning discriminative spatial saliency for images to improve the image representation and, thus, the classification performance. The method has wide applicability as was demonstrated with experiments on three challenging datasets. The method adapts saliency per image and focuses on regions which are salient for the given task. It improves over a baseline without spatial saliency and achieves better or comparable results w.r.t. the state of the art.

We plan to investigate fusing multiple discriminative spatial saliency maps obtained from various low level feature channels corresponding to different cues e.g. shape, color, texture or even high level concepts and attributes, appropriate for the classes.

Aknowledgement. This work was funded by the ANR, grant reference ANR-08-SECU-008-01/SCARFACE.

Figure 2 .

 2 Figure 2. Illustrating the importance of spatial saliency. A horse is salient for the 'ridinghorse' class. However, it is salient if it appears in the lower part of the image (e.g. left image), but not if it appears in some other part of the image (e.g. right image).

w

  Figure 3. (a) The images are represented by concatenation of cell bag-of-features weighted by the image saliency maps. (b) We propose to use a block coordinate descent algorithm for learning our model (Sec. 2.4). As in a latent SVM, we optimize in one step the hyperplane vector w keeping the saliency maps of the positive images fixed and in the other step we optimize the saliency keeping w fixed.

Figure 4 .Figure 5 .

 45 Figure 4. (Left) Evaluation (mAP) of the impact of the codebook size for a full pyramid representation. (Right) Evaluation (mAP) of the impact of the pyramid levels for a codebook size of 1000. The dataset is the Willow Actions [4].

1 :

 1 while t = 1 . . . T do

	2: 3:	Specify learning rate l w t for iteration t Choose a random training image I i
	4:

1 :

 1 while t = 1 . . . T do

	2: 3:	Specify learning rate l s t for iteration t Choose a random training image I i
	4:	Calculate the saliency map s i
	5:

Table 1 .

 1 Results (AP) on actions dataset (Sec. 3.1)

		Per-obj	Baselines
		inter. [5] SP [17] ov. SP Ours
	inter. w/ comp.	56.6	49.4	57.8	59.7
	photographing	37.5	41.3	39.3	42.6
	playingmusic	72.0	74.3	73.8	74.6
	ridingbike	90.4	87.8	88.4	87.8
	ridinghorse	75.0	73.6	80.8	84.2
	running	59.7	53.3	55.8	56.1
	walking	57.6	58.3	56.3	56.5
	mAP	64.1	62.6	64.6	65.9

Table 2 .

 2 Results (mAP) on PPMI dataset (Sec. 3.2)

	(a) Task 1: 24 class multi-class classification task
	Grouplet Rn. forest	Baselines
	[31]	[32]	SP [17] ov. SP Ours
	36.7	47.0	45.3	46.6	49.4
	(b) Task 2: 12 binary classification tasks
	Grouplet Rn. forest	Baselines
	[31]	[32]	SP [17] ov. SP Ours
	85.1	92.1	89.2	90.3	91.2
	Table 3. Results (mAP) on Scene 15 dataset (Sec. 3.3)
	Pyramid	Baselines
	level comb.	SP [17]	ov. SP	Ours
	1	74.9 ± 0.5 74.9 ± 0.5	-
	1+2	77.9 ± 0.4 78.8 ± 0.5 85.1 ± 1.2
	1+2+3	81.8 ± 0.6 82.6 ± 0.4 85.5 ± 0.6
	1+2+3+4	81.9 ± 0.5 81.9 ± 0.3 84.6 ± 0.7
	playing or just holding, 12 different musical instruments.

http://www.di.ens.fr/willow/research/stillactions/

http://ai.stanford.edu/∼bangpeng/ppmi.html