Ali Aït-Bachir
email: ali.ait-bachir@imag.fr

Marie-Christine Fauvet
email: marie-christine.fauvet@imag.fr

Analysis of incompatibilities between services: diagnosing all and identifying those which are fixable *

This text presents a tool, from its design to its implementation, which detects all incompatibilities between two service interfaces. Among all these incompatibilities, those which can be fixed by a mediator are identified. The tool focuses on behavioural dimension of service interfaces. Unlike prior work, the proposed solution does not simply check whether two services are incompatible or not, it rather provides detailed diagnosis, including the incompatibilities and for each one its location in the service interfaces. A measure of similarity between interfaces which considers outputs from the detection algorithm is proposed too. A visual report of the comparison analysis is also provided which pinpoints a set of incompatibilities that cause a behavioural interface not to simulate another one.

Introduction

Established organisations are discovering new opportunities to conduct business by providing access to their enterprise information systems through web services. This trend has led to a paradigm known as Service-Oriented Computing (SOC) wherein information and computational resources are abstracted as (web) services which are then interconnected using a collection of Internet-based standards (see for example [START_REF] Weerawarana | Web Services Platform Architecture[END_REF]). With this setting, a service is seen as an abstraction of a set of activities offered by existing applications or other services intended to fulfil a class of customer needs or business requirements.

A service interface is defined as the set of messages the service can receive and send, and the inter-dependencies between these messages. Service interfaces can be seen from at least three perspectives: structural, behavioural and non-functional. The structural interface of a service describes the types of messages that the service produces or consumes and the operations underpinning these message exchanges. While the structural interface of a service is most of the time described in WSDL, its behavioural interface, refering to the order in which the service produces or consumes messages, can be described using BPEL, business protocols, or more simply using state machines as discussed in this paper. Finally, the non-functional interface refers to reliability, security and other aspects that are not considered to be part of the functional requirements of a service. The work presented here focuses on behavioural interfaces and is complementary to other work which has studied the problem of structural interface incompatibility [START_REF] Ponnekanti | Interoperability among independently evolving web services[END_REF].

The study described in this text aims at providing a tool which is capable of reporting incompatibilities between two service interfaces. Its main contributions are:

• An algorithm which detects all differences that cause two service interfaces not to be compatible from a behavioural viewpoint. Among all detected differences, the algorithm detects those which are reconciliable using a mediator.

• A measure of similarity between service interfaces which is based on the outputs of the detection algorithm. This measure evaluates the degree of similarity between two interfaces.

• A tool which implements the algorithm and the similarity measure and provides business process designers a visual diagnosis, resulting from the incompatibility detection process applied on two interfaces.

In this paper we make the following assumptions :

(1) We focus on interfaces that expose only externally visible behaviour. In particular, internal actions or timeouts do not appear in the service interface unless they are externalised as messages.

(2) We assume messages with the same structure to be equivalent. The paper is structured as follows. Section 2 frames the problem addressed and introduces an illustrating example. In Section 3 we show how we model service interfaces according to their behavioural dimension. Section 4 presents the principle of the proposed approach while Section 5 details the detection algorithm and discusses implementation details and experiments. Section 6 compares the proposal with related ones, and Section 7 concludes and sketches further work.

Motivation and illustrating example

As a motivating example, we consider services that handle purchase orders processed either online or offline. In Figure 1, behavioural interfaces are described using UML activity diagram notation that captures control-flow dependencies between message exchanges (i.e. activities for sending or receiving messages). We distinguish the provided interface that a service exposes from its required interface as it is expected by its clients or peers. Figure 1a shows the provided interface P of a service S which interacts with a client application C that requires an interface R. We consider the scenario where C wishes to interact with another service S ′ whose interface is P ′ while meeting the same needs then S (see Figure 1b).

In this setting, and considering client applications or peers of the service S, the questions that we address are: (i) do the differences between P and P ′ cause incompatibilities between S ′ and client(s) of S? and if so, (ii) which differences lead to these incompatibilities? (iii) what are those which are fixable? Specifically, we consider two situations:

(1) A sequence of operations1 of the same polarity (i.e. all are related to a message to be sent, or all are related to a message to be received) appears in P in a specific order while it appears in P ′ in a different order. For the sake of simplicity, we call such a sequence a monotony. This is illustrated in Figure 1: according to its interface P , the service S expects to receive the message of type Insurance and before one of type SpecialDelivery (see Figure 1a). These two operations are defined in P ′ , but not with this order: the service S ′ expects to receive first the message of type SpecialDelivery, then the one of type Insurance. This difference between P and P ′ leads to an incompatibility because it causes P ′ not to simulate P . However, such a situation is fixable by a mediator, automatically generated, which would be responsible for receiving messages from clients on the behalf of S ′ , retaining them as long as they are not expected by S ′ , and eventually delivering them to S ′ at the right time (see [START_REF] Yellin | Protocol specifications and component adaptors[END_REF][START_REF] Motahari-Nezhad | Semiautomated adaptation of service interactions[END_REF]).

This situation refers to asynchronous communications. The client C will perform the activities Send Insurance then Send SpecialDelivery without having to wait for a reply from the service S ′ .

(2) The second situation refers to synchronous communications that arise when to perform an activity, a service has to wait for a reception of a message. As depicted in Figure 1, the service C may need information sent in message OfflineInvoice, before it can send the message Transfer. In this case, we distinguish three types of difference: (1) an operation is defined in P while it is not in P ′ , (2) conversely, an operation is defined in P ′ while it is not in P , (3) an operation is defined in P and changed with another one in P ′ . In Figure 1, we observe that the flow which loops from the activity Receive OfflineOrder back to itself in P does not appear in P ′ . In other words, customers of S ′ are not allowed to alter offline orders. This is a source of incompatibility since clients that rely on interface P may attempt to send messages to alter their offline order while the service S ′ does not expect a new order after the first one. On the other hand, message ShipmentTrackingNumber (STN in short) has been replaced in P ′ by message AdvanceShipmentNotice (ASN in short). This difference will certainly cause an incompatibility vis-a-vis of S's clients and peers. Another difference is that paying by bank transfer is offered in service S ′ while it is not in service S. However, this difference does not lead to any incompatibilities since S's clients have not been designed to use this option.

Modelling behavioural dimension of service interfaces

In our approach, the detection of incompatibilities relies on an abstract representation of service interfaces with an emphasis on behavioural aspects. Thus, we consider order dependencies between messages but we do not look into the schema of these messages. Accordingly, we model the behaviour of a web service interface using Finite State Machines (FSM [START_REF] Beyer | Web service interfaces[END_REF][START_REF] Pathak | Modeling web service composition using symbolic transition systems[END_REF]). Our choice of FSMs is motivated by the following reasons:

• It is arguably the simplest and most widely understood model of system behaviour and it has been used in several previous work in the area of behavioural service interface analysis [START_REF] Bordeaux | When are two web services compatible?[END_REF][START_REF] Benatallah | Developing adapters for web services integration[END_REF][START_REF] Nejati | Matching and merging of statecharts specifications[END_REF].

• It is sufficiently powerful to capture most forms of behaviour encountered in service interfaces, including race conditions and interleaved parallelism.

• There exist transformations from other notations for service behaviour modelling to FSMs. In particular several transformations from BPEL to FSMs are implemented in existing tools such as WS-Engineer [START_REF] Foster | WS-Engineer: A tool for model-based verification of web service compositions and choreography[END_REF] and WSAT [START_REF] Fu | WSAT: A tool for formal analysis of web services[END_REF].

Following [START_REF] Beyer | Web service interfaces[END_REF][START_REF] Motahari-Nezhad | Semiautomated adaptation of service interactions[END_REF], we adopt a simple yet effective approach to model service interface behaviour using Finite State Machines (FSMs). In the FSMs we consider, transitions are labelled with operations (i.e. messages to be sent or received). When a message is sent or received, the corresponding transition is fired. Figure 2 depicts FSMs of provided interfaces P and P ′ of the running example presented in Section 2. The operation has polarity < when the corresponding message m is to be sent, otherwise its polarity is > (the corresponding message is to be received). The names given to states do not have any semantics. Each conversation initiated by a client starts an execution of the corresponding FSM. The figure shows also all differences between P and P ′ . How to detect and localise these differences is discussed in the next section.

Definitions and notations :

An FSM is a tuple (S, L, T, s 0 , F ) where: S is a finite set of states, L a set of events (actions), T the transition function (T : S × L -→ S). s 0 is the initial state such as s 0 ∈ S, and F the set of final states such as F ⊂ S. The transition function T associates a source state s 1 ∈ S and an event l 1 ∈ L to a target state s 2 ∈ S.

To check whether or not differences between an interface P (of service S, seen as a reference) and another one P ′ (of service S ′ ) lead to incompatibilities, it is necessary to identify situations when P ′ does not simulate P . Actually, if P ′ simulates P then each interface R required by the clients of S, which are compatible with P remains compatible with P ′ (see [START_REF] Aït-Bachir | Detectioning behavioural incompatibilities between pairs of services[END_REF] for a proof).

Diagnosing differences

To detect differences between P and P ′ , their respective FSMs are traversed synchronously starting from their respective initial states s 0 and s ′ 0 . The traversal seeks for two states s and s ′ (belonging respectively to P and P ′ ) which are such as the sub-automaton starting from s in P and the one starting from s ′ in P ′ are incompatible (details are given in Section 5.1). We first discuss and illustrate the conditions that need to be evaluated in order to identify an incompatibility which could be fixable by a mediator, i.e. a monotony in P which has a permutation in P ′ (see Section 4.1). Then, we detail the situations which lead to incompatibilities which cannot be resolved: one occurs when P has an operation which does not exist in P ′ (for the sake of simplicity we call this situation a deletion, see Section 4.2) and the other one when an operation in P is replaced with another one in P ′ (this is called a modification, see Section 4.3). We do not detail here the situation when P ′ has an operation which does not exist in P as it is transposed from the deletion mentioned above.

Diagnosing fixable incompatibilities

Figure 3 illustrates a situation where a fixable incompatibility can be diagnosed between two interfaces (the figure shows a fragment of P and P ′ interfaces). This situation occurs when all operations which label transitions that belong to the path starting in P with <Z(m) and finishing with <Y(m) have the same polarity and are also enabled in FSM P ′ , but in a different order. In other words, the path in P defined by the sequence of transition labels [<Y(m), <X(m), <Z(m)] is a permutation of the path in P ′ defined by [<X(m), <Z(m), <Y(m)]. As seen before, the incompatibility which is led by this mismatch could be fixed by adding a mediator which retains messages as they arrive, according to interface P and deliver them at the right time, according to interface P ′ . More formally a fixable incompatibility is detected between interfaces P and P ′ at the pair of states s, s ′ (respectively belonging to P and P ′ ), when the following condition holds (the notation is explained further down): ∃p ∈ M onotonies(s), ∃p ′ ∈ M onotonies(s ′ ) :

(1) P olarity(p) = P olarity(p ′ ) ∧ IsP ermutation(p, p ′ ) (

All examples given below are related to FSMs depicted in Figure 2.

-M onotonies(s) is the set of paths starting after the state s, each of which being a monotony with at least 2 transitions (e. In the process of comparing interfaces P and P ′ , the pairs of states to examine next has to be determined. For this purpose, among the paths defined according to the equations given above, we consider only those which are of the maximum length. For instance, comparing interfaces P and P ′ as depicted in Figure 3 As the latters include the formers, the pair of states to visit next is deduced from the target state of their last transition. Thus, the next state to visit in P (resp. in P ′ ) is the target state of the transition labelled by <Y(m) in P (respectively in P ′ ).

Deletion of an operation

Figure 4 depicts two situations where an operation appears in P and not in P ′ . First in Figure 4a, we observe that all operations enabled in state S1 ′ are also enabled in state S1. Moreover, there is an operation (namely >R(m)) enabled in state S that has no match in state S1 ′ . Hence we conclude that, considering the pair of states S1 and S1 ′ , >R(m) is missing in P ′ . Once this difference has been detected, the pairs of states to be examined next in the process of comparing P and P ′ are S2, S2 ′ and S3, S3 ′ : S2 in P and S2 ′ in P ′ are targets of transitions which both labelled by the same operation: >X(m). The same remark applies to S3 and S3 ′ with the operation <Z(m). In Figure 4b we note that first, the operation <Z(m) is enabled in S1 ′ and not in S1, and second the operation >X(m) is enabled in S1 but not in S1 ′ . There are two reasons for this mismatch: either operation >X(m) has been modified and has become <Z(m), or >X(m) has been deleted. In this example, we can discard the former possibility because <Z(m) appears downstream in the FSM of P ′ (it labels an outgoing transition of state S2). Hence, <Z(m) can not be considered as a replacement for >X(m). Thus, we conclude that >X(m) has been deleted in P ′ . Once this difference has been detected, the pair of states to be examined next in the process of comparing P and

P ′ is S2, S1 ′ .
Formally, when comparing two interface FSMs P and P ′ , the fact an operation is defined in P and missing in P ′ is diagnosed in a pair of states s, s ′ (respectively belonging to P and P ) if the following condition holds:

Label (s•) -Label (s ′ •) 1 ∧ Label (s ′ •) -Label (s•) = 0 (3) ∨ ∃t ∈ s•, ∃t ′ ∈ s ′ • : Label (t) ∈ Label (s ′ •) ∧ ExtIn(t ′ , (t•)•) (4)
In the previous equations, the notations given below -Label(t) is the label of t. (e.g. Label( S1, <Z(m), S2 ) = <Z(m)) -X : cardinality of X.

-The • operator (respectively •) is generalised to a set of transitions (respectively states). For example, if

T = n i=1 {t i } then T • = n i=1 {t i •};
where n = T . Similarly, operator Label is generalised to a set of transitions.

A deletion is detected in state pair (s, s ′ ) in two cases. The first one (line 3) is when every outgoing transition of s ′ can be matched to an outgoing transition of s, but on the other hand, there is an outgoing transition of s that can not be matched to a transition of s ′ . A second case is when there exists a pair of outgoing transitions t and t ′ (of states s and s ′ respectively) such that: (i) transition t can not be matched to any outgoing transition of s ′ ; and (ii) the label of t ′ occurs somewhere in the FSM rooted at the target state of t (line 4). 2 This second condition is tested in order to determine whether the non-occurrence of t's label among the outgoing transitions of s ′ should indeed be interpreted as a deletion, as opposed to a modification or an addition. To check if a transition label occurs somewhere in the FSM rooted at the target of a given transition, we use the following recursive Boolean function:

ExtIn(t, T ) ≡ T = ∅ ∧ (Label (t) ∈ Label (T ) ∨ T i=1 ExtIn(t, (T i •)•)).
In other words, ExtIn(t, T ) (where t is a transition and T is a set of transitions) evaluates to true if either the label of transition t label appears among the labels of transitions in T (Label (t) ∈ Label (T )) or, there exists a transition taken in T which has a target state whose set of outgoing transitions (namely T 1) is such that ExtIn(t, T 1) evaluates to true. The way it is defined, this recursive function does not converge if the FSM has cycles, but it can be trivially extended to converge by adding an input parameter to store the set of visited states and to ensure that each state is visited only once.

Modification of an operation

Figure 5 shows a situation where we can diagnose that operation >X(m) has been replaced by operation >Y(m) (i.e. a modification). The reason is that the operation >X(m) is enabled in S1 but not in S1 ′ , and conversely >Y(m) is enabled in S1 ′ but not in S1. Moreover, the transition labelled >X(m) does not match to any transitions t ′ in state S1 ′ such that operation >X(m) occurs downstream along the branch starting with t ′ , and symmetrically, >Y(m) does not match any transitions t of state S1 such that >Y(m) occurs downstream along the branch starting with t. Thus we can not diagnose that >X(m) has been deleted, nor can we diagnose that >Y(m) has been added.

In this case, the pairing of transition >X(m) with transition >Y(m) is arbitrary. If state S1 ′ had a second outgoing transition labelled >Z(m), we would just also diagnose that >X(m) has been replaced by >Z(m). Thus, when we diagnose that >X(m) has been replaced by >Y(m), all we capture is that >X(m) has been replaced by another operation, possibly >Y(m). The output produced by the proposed technique should be interpreted in light of this.

The pair of states to be visited next in the synchronous traversal of P and P ′ is such that both transitions involved in the modification are traversed simultaneously ( S2, S2 ′ in this example). Formally, a modification is diagnosed in state pair (s,s ′ ) if the following condition holds:

∃t1 ∈ s•, ∃t1 ′ ∈ s ′ • : Label (t1) ∈ Label (s ′ •) ∧ Label (t1 ′ ) ∈ Label (s•) (5) ∧¬∃t2 ∈ s• : ExtIn(t1 ′ , (t2•)•)) ∧ ¬∃t2 ′ ∈ s ′ • : ExtIn(t1, (t2 ′ •)•)) (6)
A modification is detected when there exists a label of an outgoing transition t1 (resp. t1 ′ ) of a state s (resp. s ′ ) which does not appear in labels of outgoing transitions of a state s ′ (resp. s) (see line 5), and there exist no outgoing transition t2 (resp. t2 ′ ) of a state s (resp. s ′ ) such that label of t1 ′ (resp. t1) appears downstream the sub-automata of P (resp. P ′ ) rooted at target state of t2 (resp. t2 ′ , see line 6).

Implementation details and experiments

The detection algorithm presented below (see Section 5.1) is implemented in a tool whose main feature is to detect differences between two behavioural interfaces that cause that the second interface does not simulate the behaviour of the first one3 [START_REF] Aït-Bachir | BESERIAL: Behavioural service analyser[END_REF]. Section 5.2 details the complexity of the detection algorithm. A measure of similarity between two service interfaces is introduced in Section 5.3 while Section 5.4 focuses on some experimental results.

Detection algorithm

The algorithm implementing the detection process illustrated in the previous section is detailed in Figure 6. Given two interface FSMs P and P ′ , the algorithm traverses P and P ′ synchronously starting from their respective initial states s 0 and s ′ 0 . At each step, the algorithm visits a state pair consisting of one state from each of the two FSMs. Given a state pair, the algorithm determines if an incompatibility exists and if so, it classifies it as fixable or not fixable. Incompatibilities which are fixable are permutations of monotonies of messages to be received (resp. sent) between pairs of paths of P and P ′ . Incompatibilities which are fixable are ignored as a mediator can automatically be generated to fix them. An incompatibility which is not fixable is detected as an addition, a deletion or a modification. If an addition is detected (e.g. an operation is enabled from s ′ 0 in P ′ and not from s 0 in P ), the algorithm progresses along the transition of the operation in the interface it has been added. Conversely, if the change is a deletion (e.g. an operation is enabled from s 0 in P and not from s ′ 0 in P ′ ), the algorithm progresses along the transition of the deleted operation in. However, if a modification is detected, the algorithm progresses along both FSMs simultaneously. While traversing the two input FSMs, the algorithm accumulates a set of differences represented as tuples of the type Difference defined as below:

type Difference: < State, Transition, State, Transition > /* Let s, t, s ′ , t ′ be of type Difference: s and s ′ are states respectively belonging to FSMs P and P ′ to be compared. t = null ⇐⇒ t ′ = null ∧ t ′ is enabled in P ′ while it is not in

P (t ′ added in P ′ ), t ′ = null ⇐⇒ t = null ∧ t is enabled in P while it is not in P ′ (t is deleted), t = null ∧ t ′ = null ⇐⇒ t in P is modified by t ′ in P ′ . */
For instance, the detection algorithm applied on the illustrating example (see Figure 2) returns the set of tuples { S4, <OfflineOrder, S4', null , S3, null, S3', <Transfer S8, >STN, S8', >ASN } which summarises the differences found when comparing P ′ to P . It is worth noting that comparing P to P ′ returns { S4', null, S4, <OfflineOrder , S3', <Transfer, S3, null S8',>ASN, S8, >STN }.

The algorithm proceeds as a depth-first algorithm over state pairs of the compared FSMs. Three stacks are maintained: one with the visited pairs of states and two others with pairs of states to be visited (see Figure 6, line 5). These pairs of states are such that the first state belongs to the FSM P i while the second one belongs to the FSM P j. The first state pair to be visited is the one containing the initial states of P i and P j (line 6). Once a pair of states is visited it will not be visited again. To ensure this, the algorithm uses the variable visited for this purpose (line 9). In line 10, the function Incompatibilities verifies whether or not the current pair of states si, sj is compatible or not. This function is detailed below: Incompatibilities(P i, P j: FSM; si, sj: State): < isCompatible:Boolean, next:StackOfStatePair> /* Incompatibilities(P i,P j,si,sj) returns a tuple b, n where b is true there exists no incompatibility (false otherwise). n is a set of state pairs to be visited next. Labels in common among those of outgoing transitions of si and those of outgoing transitions of sj are considered as unchanged (no incompatibility to detect). Thus, in n, each pair of states s, s ′ is such that s and s ′ are, in their respective FSM, target states of transitions with the same labels in both FSM. */ If the algorithm detects an incompatibility at the current pair of states, the function F ixableIncomp which finds out incompatibilities that are fixable (line 12). The algorithm of this function is detailed further down.

Incompatibilities which are not fixable are detected (line 13). The algorithm reports all differences between the outgoing transitions of si and the outgoing transitions of sj (line 14). Two set of transition differences are stored in two variables difPiPj (transitions whose labels belongs to Label (si•) but do not belongs to Label (sj•)) an difPjPi (transitions whose labels belong to Label (sj•) but do not belong to Label (si•)). Line 15 calculates all combinations of transitions whose labels do not belong to Label (si•) ∩ Label (sj•).

Lines 16 to 18 are dedicated to detect a deletion when an outgoing transition of si does not match any transition in sj•. The result is a set of tuples of the form of < si, t, sj, null > where t is one of the outgoing transitions of si whose label does not appear in any of sj outgoing transitions. As mentioned in Section 4.2, when an operation is deleted in FSM P j the algorithm progresses in FSM P i, along the branch of the The variable combPiPj contains transition pairs such that the label of the first one ti belongs to Label(si•) but not to Label (sj•) while the label of the second one tj belongs to Label(sj•) but not to Label (si•). For each transition pair satisfying this condition, the algorithm checks the conditions for diagnosing an addition (lines 24 to 26), a deletion (lines 27 to 29) or a modification (lines 30 to 32).

difPiPj ← {ti ∈ si• | Label(ti) ∈ Label(sj•)} difPjPi ← {tj ∈ sj• | Label(tj) ∈ Label(si•)} 15 combPiPj ← difPiPj × difPjPi /*
Finally, the algorithm updates toBeV isited variable with state pairs to be visited next (line 33). The algorithm testing whether incompatibilities are fixable or not is detailed in Figure 7. The result is a tuple b, n where b is true if are fixable and n a set of state pairs to be visited next. While comparing monotonies starting from state si in FSM P i to those starting from state sj in FSM P j, permutations are detected and reported as fixable incompatibilities, otherwise they are reported as unfixable incompatibilities. Lines 6 and 7 build all possible monotonies in P i and P j. This function takes as inputs FSM P i (resp. P j) and state si (resp. sj) to build monotonies. The result is a set of paths each of which has messages of a same polarity. The algorithm finds out all possible paths starting from state si (resp. sj) downstream outgoing transitions. Each resulted path ends either with a transition whose target state has no outgoing transitions or with a transition whose target state has outgoing transitions with different polarity.

Then, for each path pathi in P i monotonies the algorithm checks whether there exist paths pathj in P j monotonies such that each path pathj is a permutation of path pathi (see lines 8 and 9). If there exists no permutation, the incompatibility is reported as unfixable (see lines 10 to 13), otherwise they are reported as fixable (see lines 14 to 17).

Complexity of the detection algorithm

Let P and P ′ be two interface FSMs given as input to the detection algorithm, P (respectively P ′ ) has n (resp. n ′ ) states and m (resp. m ′ ) transitions. Also, let w and w ′ be the number of distinct transition labels appearing in P and P ′ respectively. We observe that the algorithm performs a depth-first search over the space of state pairs s, s ′ such that s is a state of P and s ′ is a state of P ′ . The algorithm visits each state pair at most once, therefore one component of the complexity is O(n * n ′ ). We then observe that for each visited state pair, the algorithm examines transitions pairs t, t ′ such that t is an outgoing transition of s and t ′ is an outgoing transition of s ′ . Also, when a transition t in one FSM can not be matched to a transition in the other FSM, we examine t individually. Overall each transition pair t, t ′ such that t is a transition of P and t ′ is a transition of P ′ is examined at most once. Additionally, each transition t in P and t ′ in P ′ is examined at most once individually. Thus another component of the complexity is O(m * m ′ + m + m ′ ). Since the first term dominates the other two, this can be written as O(m * m ′ ). Thus, the complexity of the traversal is

O(n * n ′ + m * m ′ ).
While visiting each state pair, monotononies in P are compared to other monotonies in P ′ . In the worst case, each path has one transition and the complexity is O(m * m ′ ). Thus, the complexity of the matching monotonies stage is bounded by O(m * m ′ +m+m ′ ). As the first term dominates the other two, this can be written as O(mm ′ ).

For each visited pair t, t ′ of transitions a condition is evaluated. This condition is based on the transition labels and, in some cases, it also involves a "look-ahead" operation. The purpose of this look-ahead is to find, for a given label, whether or not this label appears in the FSM rooted at either the target of t or the target of t ′ . This look-ahead can be avoided as follows. In a pre-processing stage, we traverse each of the two FSMs individually using a breadth-first search algorithm. During this traversal, we construct a look-up table that maps each state s to a list of pairs l, b where l is a transition label and b is a Boolean value indicating whether or not l is the label of a transition reachable from s. For each state s, we calculate the value of b for each label, based on the corresponding values of b for each direct successor of s. This step is linear on the number of labels appearing in the FSM. Thus, the complexity of this pre-processing is O((n + m) * w) for P and O((n ′ + m ′ ) * w ′ ) for P ′ . Since the number of distinct labels in an FSM is bounded by the number of transitions, the complexity of the pre-processing stage is bounded by

O(n * m + (m) 2 + n ′ * m ′ + (m ′ ) 2 ).
Adding up the complexity of the pre-processing, the monotony matching and the detection algorithm, the overall complexity is

O(n * m + (m) 2 + n ′ * m ′ + (m ′ ) 2 + n * n ′ + m * m ′ + m * m ′ ).
Assuming the number of transitions in an FSM is greater than the number of states (which, modulo one transition, holds because the FSMs are connected graphs), the complexity is bounded by O((m + m ′ ) 2 ). Thus the worst-case complexity is quadratic on the total number of transitions in both FSMs.

Measure of similarity

This section presents a measure meant to give a quantitative evaluation of how much an interface is different from another one. This measure relies on a function QuantitativeSimulation (QS in short). QS : VStates → [0..1] where VStates is the set of state pairs visited by the detection algorithm (VStates ⊆ S × S ′ , S being the set of states in P and S ′ the set of those in P ′ ). Given a pair of states s, s ′ ∈ VState, QS( s, s ′ ) measures incompatibilities detected at s, s ′ relatively to the number of transitions in common between s and s ′ . The formulae is (see explanations below):

QS ( s, s ′ ) =    1 if s• = ∅ LC + d∈Diff ( s,s ′ ) Weight(d) LC + Diff ( s, s ′ ) otherwise LC = Label (s•)∩Label (s ′ •)
is the set of labels in common in transitions whose sources are s and s ′ . Diff ( s, s ′ ) is the set of differences pinpointed from the state pair s, s ′ . The function Weight : Difference → [0..1[ is such as Weight(d ) is the penalty associated with d. Penalties are arbitrary chosen and depend on whether the difference is an addition, a deletion or a modification. Fixable incompatibilities are ignored.

When s does not have any outgoing transitions, QS( s, s ′ ) = 1. Otherwise, QS tends toward zero as the weight of incompatibilities, evaluated relatively to the global number of transitions in common, rooted at s and s ′ . For a fixed number of these transitions, more differences are found at s, s ′ higher is the dividend and closer to 0 is QS( s, s ′ ). The divisor, which is meant to keep QS in [0, 1], is never equal to 0: either s has no outgoing transition (QS( s, s ′ ) = 1), or s has at least one outgoing transition and it corresponds to a difference ( Diff ( s, s ′ ) > 0) or not ( LC ≥ 1).

For example, in Figure 2, assuming the penalty for the deletion is set to 0.5, thus: QS ( S3, S3' ) = (1+0.5)/(1+1)=0.75 while QS ( S1, S1' ) = (1+0)/(1+0)=1

Eventually, to quantitatively compare P and P ′ , we propose to calculate the mean of values returned when applying QS on each pair of states visited by the algorithm. This is done by the function Mean Quantitative Simulation (M QS in short). MQS (P, P ′ ) = 1 means that P ′ simulates P .

MQS (P, P

′ ) = p∈VStates QS (p)/ VStates
In the running example, if the penalty values are set to 0.5 then the mean quantitative simulation is: MQS (P, P ′ ) = 0.875.

Experimental results

For validation purposes, we built a test collection of 15 behavioural interfaces derived from the textual description of choreographies expressed in the standard xCBL 4 . The experiment consisted in comparing interfaces to each other.

Table 1 gives a fragment of the results obtained when comparing service interfaces. Each line reports the comparison between the interface seen as a reference and a particular interface given by its id number (see column Interface). In the column MQS is displayed the value returned when applying the function MQS (see above) to the list of differences built by the detection algorithm. The number of items in this list is given in column Nb diff while the column States (resp. Transitions) shows how many states (resp. transitions) where found in the interface to be compared. Each interface has between 3 and 16 transitions. The interface given as a reference has 11 states and 13 transitions. The interface whose id is ♯11 has 10 states and 14 transitions. It has 19 differences with the interface given as the reference. The value returned by M QS is 0.233 which is lower then the one returned when comparing the interface whose id is ♯5. The interface ♯5 has a better score (0.30) then the one which id is ♯11, even thought ♯5 has less differences then ♯11. The interface ♯12 scores 1 and has no difference with the reference, thus it simulates the reference interface.

Interface

Related work

The issues tackled in this paper have been partially addressed before, with various points of view. Web service interactions may fail because of interface incompatibilities according to their structural dimension. In this context, reconciling incompatible interactions leads towards transforming message types (using for instance Xpath, XQuery, XSLT). Issues that arise in this context are similar to those widely studied in the data integration area. A mediation-based approach is proposed in [START_REF] Altenhofen | An execution semantics for mediation patterns[END_REF]. While this approach relies on a mediator (called virtual supplier ) it focuses on structural dimension of interfaces only. Detecting incompatibilities is proceeded manually.

In [START_REF] Motahari-Nezhad | Semiautomated adaptation of service interactions[END_REF], authors introduce a technique to diagnose mismatches of message structure between service interfaces and to fix them with adaptors. An extension of this technique is applied to resolve mismatches between service protocols. The proposed iterative algorithm builds a mismatch tree to help developers to choose the suitable adapter each time an incompatibility is detected. However, this technique only applies to protocols which describe a sequence of operations. More complex flow controls such as iterative or conditional compositions are not taken into consideration. The solution proposed in our algorithm does not have this limitation. Another drawback of this approach is that adaptors have no control logic and can not resolve complicated protocol mismatches, such as extra condition, missing condition, or iteration structure, etc.

Compatibility test of interfaces has been widely studied in the context of web service composition. Most of approaches which focus on the behavioural dimension of interfaces rely on equivalence and similarity calculus to check, at design time, whether or not interfaces described for instance by automata are compatible (see for example [START_REF] Bordeaux | When are two web services compatible?[END_REF][START_REF] Haddad | Modelling web services interoperability[END_REF]). The behavioural interface describes the structured activities of a business process. Checking interface compatibility is thus based on bi-similarity algorithms [START_REF] Martens | Analyzing compatibility of bpel processes[END_REF]. These approaches do not deal with pinpointing exact locations of incompatibilities as ours does. In [START_REF] Wombacher | Matchmaking for business processes based on choreographies[END_REF], authors propose an approach to business process matchmaking based on automata extended with logical expressions associated with states. The proposed algorithm determines if the languages of two automata (which model two business processes) have a non-empty intersection. This technique for detecting differences between two processes returns a binary output. It does not provide any detailed diagnosis. In [START_REF] Deng | Automated synthesis of composite services with correctness guarantee[END_REF], authors define an approach for composing web services and verifying correctness constraints and freeness of deadlocks. Service interfaces are specified at business protocol level using deterministic finite automata. Correctness constraint test is based on L * algorithm introduced in [START_REF] Rivest | Machine Learning: From Theory to Applications[END_REF]. Freeness of deadlock algorithm aims at removing existing deadlocks if and only if there exists a sequence of messages to be received in a given service interface. This sequence of messages can be buffered and sent in a correct order to another service partner of the composition. Nevertheless, these algorithms do not diagnose all incompatibilities. The result is a binary response which states whether interfaces are compatible or not.

Recent research has addressed interface similarity measure issues. In [START_REF] Sokolsky | Simulation-based graph similarity[END_REF], authors present a similarity measure for labelled directed graphs inspired by the simulation and bi-simulation relations on labelled transition systems. The presented algorithm returns a value of a simulation measure but does not give the location of the incompatibilities which have been detected. Its complexity is exponential or factorial to the number of states of the graphs to be compared. According to this theoretical result, our algorithm is more efficient. A similar algorithm with the same limitations and complexity has been used for service discovery purpose as introduced in [START_REF] Corrales | BPEL processes matchmaking for service discovery[END_REF]. More specifically, some algorithms for detecting incompatibilities have been proposed, but they focus only on structural aspect of interfaces and do not address their behavioural dimension [START_REF] Champin | Measuring the similarity of labeled graphs[END_REF]. In [START_REF] Lohmann | Correcting deadlocking service choreographies using a simulation-based graph edit distance[END_REF], the author presents a similarity measure for labelled directed graphs inspired by the simulation and bi-simulation relations on labelled transition systems. The author applies this technique to detect and correct deadlocks. Other algorithms based on graph-edit distances have been applied to service discovery in [START_REF] Corrales | BPEL processes matchmaking for service discovery[END_REF], but do not pinpoint behavioural differences between services.

Change patterns have been introduced in [START_REF] Weber | Change patterns and change support features in process-aware information systems[END_REF] which characterise different types of business process evolution. Each pattern models a set of rules which are used by the designer to decide whether or not to propagate changes on executing instances of the modified process or to abort them. This approach does not apply to web services as web services are used as black boxes.

In [START_REF] Nejati | Matching and merging of statecharts specifications[END_REF], authors propose an operator match which is a similarity function comparing two interfaces for finding correspondences between them. This function is the same as the one introduced in [START_REF] Sokolsky | Simulation-based graph similarity[END_REF] which considers the behavioural semantics. The similarity measure is an heuristic which relies on penalty scores associated with the type of change (addition vs. deletion). However, the result does not pinpoint the exact location of these changes.

Conclusion and further study

In this text we have presented both design and implementation of a tool intended to detect differences of an operation) that give rise to behavioural incompatibilities between two service interfaces (addition, deletion or modification. The main originality of the proposed solution is that the detection algorithm does not stop at the first incompatibility encountered but keeps searching further to identify all incompatibilities leading up to the final state of one of the interfaces to be compared. The tool deals with asynchronous communications as well This extension is achieved by maintaining a buffer of unconsumed messages during the traversal, as it is proposed in [START_REF] Motahari-Nezhad | Semiautomated adaptation of service interactions[END_REF]. Eventually we have proposed a measure of similarity between interfaces. This measure is meant to be used to select, among a set of services, which one has the closest interface to a given service interface.

Ongoing work aims at extending the proposed solution toward two directions: (i) comparing our similarity measures to others and testing detection algorithm on real services; and (ii) assisting business process designers in determining how to address incompatibilities. Also, fixable incompatibilities are currently assumed to be permutation of monotonies. Future work will aim at extending the technique to address other fixable cases. This extension can be achieved by introducing patterns of fixable incompatibilities, as proposed in [START_REF] Taher | Diagnosing incompatibilities in web service interactions for automatic generation of adapters[END_REF].

Figure 1 :

 1 Figure 1: Differences between two service interfaces.

Figure 2 :

 2 Figure 2: FSMs modelling P and P ′ .

Figure 3 :

 3 Figure 3: Diagnosis of fixable incompatibilities

  g. M onotonies(S0) = { [<OfflineOrder, <Insurance], [<OfflineOrder, <Insurance, <SpecialDelivery] } ). -P olarity(p) is the polarity of the path p. If p is not a monotony, P olarity(p) is not applicable. (e.g. P olarity([<OfflineOrder, <Insurance])=<) -IsP ermutation(p, p ′ ) evaluates to true when the path p is a permutation of the path p ′ (IsP ermutation(p, p ′ ) = IsP ermutation(p ′ , p)). (e.g. IsP ermutation ([<OfflineOrder, <Insurance], [<Insurance, <OfflineOrder]) = true, IsP ermutation ([<OfflineOrder, <Insurance, <SpecialDelivery], [<Insurance, <OfflineOrder]) = false)

  will lead to compare the monotony [<X(m), <Z(m)] to the monotony [<Z(m), <X(m)], and also the monotony [<X(m), <Z(m), <Y(m)] to the monotony [<Z(m), <X(m), <Y(m)].

  >R(m) deleted in P ′ >X(m) deleted in P ′

Figure 4 :

 4 Figure 4: Diagnosis of deletions

  apply (examples refer to Figure 4a): s• is the set of outgoing transitions of s (e.g. S1• = { S1, >X(m), S2 , S1, <Z(m), S3 , S1, >R(m), S1 } t• is the target state of the transition t. (e.g. S1, <Z(m), S2 • = S2).

Figure 5 :

 5 Figure 5: Diagnosis of a modification/replacement

Figure 6 :

 6 Figure 6: Detection algorithm

Figure 7 :

 7 Figure 7: Fixable incompatibilities algorithm

1

  Detection (P i: FSM, P j: FSM): {Difference} 2 /* Detection (P i,P j) is the set of differences between P i and P j. */ 3 setRes: { Difference } /* the result */ 4 si, sj: State /* auxiliary variables */ 5 visited, toBeV isited: Stack of type <State, State> /* pairs of states that have been visited / must be visited */

		next: Stack of type <State, State>
	6 toBeV isited.push((initState(P i), initState(P j)))
	7 while notEmpty(toBeV isited)
	8	si, sj ← toBeV isited.pop()
	9	visited.push( si, sj ) /* si, sj is now considered as visited */
	10	isCompatible, next ← Incompatibilities(P i, P j, si, sj)
		/* not isCompatible ⇒ next=∅ */
	11	If not isCompatible then	/* incompatible */
	12	isF ixable, next ← FixableIncomp(P i, P j, si, sj)
	13	If Not isF ixable then	/* incompatible and not fixable */
	14

1

  FixableIncomp(P i,P j: FSM; si,sj: State): < isF ixable: Boolean, next: StackOfStatePair> 2 /* FixableIncomp(P i,P j,si,sj) returns a tuple b, n where b is true if incompatibilities are fixable (false otherwise). n is a set of pairs of states to be visited next. */ 3 isF ix: Boolean ; nxt:StackOfStatePair /* result variables */ 4 PiPaths,PjPaths : {P ath} /* auxiliary variables */ 5 isFixable ← f alse 6 PiPaths ← Monotonies(P i,si) /* Monotonies(P i,si) is a set of paths starting from si such that all transitions have the same polarity. */ 7 PjPaths ← Monotonies(P j,sj)

	10	If isEmpty(mappingPaths)
	11	si ← (Last(pathi))•
	12	nxt.push( si, sj )
	13	Else
	14	isF ix ← true
	15	For each pathj in mappingPaths do
	16	si ← (Last(pathi))•; sj ←(Last(pathj))•
		/* The algorithm progresses synchronously up to the end of each path, in both
		FSMs. */
	17	nxt.push( si, sj )
	18 Return isF ix, nxt

8 For each pathi in P iP aths do 9 mappingPaths ← Permutations(pathi, PjPaths) /* Permutations(pathi, PjPaths returns a subset of P jP aths such that each path is permutation of pathi */

Table 1 :

 1 Fragment of experimental results

		MQS	States Transitions Nb diff
	♯12	1	11	13	0
	♯14	0.977	11	13	1
	♯13	0.875	10	13	3
	♯1	0.43	4	3	11
	♯3	0.37	6	6	16
	♯5	0.30	8	11	21
	♯11	0.233	10	14	19

We use the terms operation and message interchangeably, while noting that strictly speaking, messages are events that initiate or result from operations.

Submitted to BDA'09

By FSM P rooted at s we mean FSM P in which the initial state is set to be s. This means that we ignore any state or transition that is not reachable from s.

See http://mrim.imag.fr/ali.ait-bachir/webServices/webServices.html

Submitted to BDA'09 page 12

Submitted to BDA'09 page 13

XML Common Business Library (http://www.xcbl.org/).

Submitted to BDA'09 page 15

Submitted to BDA'09 page 16

* Work partly funded by the Web Intelligence Project, Rhône-Alpes French Region


Keywords: systèmes de filtrage, démarrage à froid, espaces de communautés filtering systems, recommender systems, cold-start problem, community spaces. Cette recherche

projet #MD-33.

Exploitation des données « disponibles à froid » pour améliorer le démarrage à froid dans les systèmes de filtrage d'information

Une approche expérimentale fondée sur les « espaces de communautés » et la classification par règles An-Te Nguyen, Nathalie Denos, Catherine Berrut Laboratoire CLIPS-IMAG 385, rue de la Bibliothèque BP 53,nathalie.denos,catherine.berrut}@imag.fr RÉSUMÉ. Dans les systèmes de filtrage d'information, les utilisateurs reçoivent des documents que leur recommande le système sur la base de leurs profils et/ou de leurs communautés, mais le problème du « démarrage à froid » conduit à des performances très pauvres pour les nouveaux utilisateurs. Nous améliorons ici les techniques classiques de démarrage à froid en exploitant les données « disponibles à froid » (par exemple âge, profession, lieu de résidence, etc.) afin d'associer automatiquement les meilleures communautés initiales aux nouveaux utilisateurs. Nous nous appuyons sur le modèle existant des « espaces de communautés », et nous utilisons un processus de classification par règles et définissons un processus de recommandations par niveau d'accord. L'évaluation montre que cette approche fournit des recommandations meilleures que celles obtenues suite à un processus de démarrage à froid classique.

ABSTRACT. With information filtering systems, users receive documents recommended on the basis of their profiles and/or communities. New users experience the "cold-start" problem: as their profiles and communities are very poor, the system performs very poorly. In this paper, we improve classical "cold-start" techniques by exploiting the data that are "readily available " (e.g. age, job, city, etc.), in order to automatically associate users with better initial communities. We rely on the existing "community spaces model", and we use a rulebased classification process and define a recommendation process based on the "level of agreement". The experiments lead to better recommendations than those obtained after a classical "cold-start" technique.

Introduction

Problématique. Dans les systèmes de filtrage d'information, les utilisateurs reçoivent des documents que leur recommande le système sur la base de leurs profils et/ou de leurs communautés. Le profil et les communautés d'un utilisateur évoluent au cours du temps grâce aux interactions entre l'utilisateur et le système, notamment grâce aux évaluations produites par cet utilisateur. Lorsqu'il s'inscrit et commence à utiliser le système, le problème du « démarrage à froid » se pose, car son profil est encore très pauvre, voire inexistant, et ses communautés sont encore inconnues. Par conséquent, le système ne peut pas lui fournir des recommandations pertinentes [START_REF] Maltz | Pointing the way: Active collaborative filtering[END_REF].

Selon le type de filtrage d'information (collaboratif, basé sur le contenu, ou encore hybride), les réponses à ce problème varient, mais dans tous les cas, l'utilisateur est mis à contribution, et les tâches qui lui sont demandées sont généralement difficiles, longues et/ou fastidieuses. L'objectif de cet article est d'améliorer ces processus de gestion du démarrage à froid. Pour cela nous proposons d'exploiter les données « disponibles à froid » pour rattacher automatiquement le nouvel utilisateur aux meilleures communautés initiales et à terme pour lui associer un meilleur premier profil.

Les données « disponibles à froid » sont les informations sur l'utilisateur que l'on peut recueillir dès son inscription, et que l'utilisateur peut fournir avec une grande fiabilité, et sans effort particulier : par exemple, son âge, sa profession, son lieu de résidence. Les autres données qui participent au profil de l'utilisateur [START_REF] Bouzghoub | Personnalisation de l'information : Aperçu de l'état de l'art et définition d'un modèle flexible de profils[END_REF] (évaluations des documents présentés, description du contenu des documents intéressants) sont plus difficiles à obtenir des utilisateurs.

Notre approche. Nous pensons qu'utiliser les données disponibles à froid peut permettre de compenser partiellement les données non fournies initialement par les utilisateurs, qui sont utiles dans le positionnement d'utilisateurs au sein des communautés. Notre objectif ici consiste à valider expérimentalement que cette première approche améliore significativement les performances des systèmes.

Ainsi, nous montrons comment positionner un nouvel utilisateur dans les communautés multicritères sans qu'il ait à fournir d'évaluations ou de descriptions. Pour cela, nous nous appuyons sur le modèle des « espaces de communautés » [START_REF] Nguyen | Modèle d'espaces de communautés basé sur la théorie des ensembles d'approximation dans un système de filtrage hybride[END_REF] qui permet de prendre en compte les divers facteurs de pertinence exploitables dans les systèmes de filtrage d'information. Schématiquement, ce modèle permet à un utilisateur d'être membre de multiples communautés : une par espace de communautés, un espace de communautés étant associé à chaque facteur de rapprochement entre utilisateurs.

Les données « disponibles à froid » nous permettent d'attribuer au nouvel utilisateur une communauté pour elles-mêmes (communautés d'âge, de profession etc.) mais également dans l'espace des communautés relatives au contenu, ou relatives aux évaluations passées. Ainsi le système déduit les communautés Contenu et Evaluation par un processus de classification par règles, qui s'appuie sur : a) l'appartenance de l'utilisateur aux communautés relevant des espaces où l'information est bien connue (données disponibles à froid comme Age, Profession, etc.), et b) l'ensemble des données relatives aux utilisateurs déjà intégrés dans le système, données qui révèlent la façon dont les différents attributs sont liés entre eux.

Les performances de cette approche sont évaluées selon leur capacité à fournir, sans effort de la part de l'utilisateur, des recommandations équivalentes à celles obtenues suite à un processus de démarrage à froid classique, qui lui, requiert un effort de l'utilisateur.

Etat de l'art sur le démarrage à froid

Le démarrage à froid est le phénomène qui se produit en début d'utilisation du système, dans des situations critiques où le système manque de données pour procéder à un filtrage personnalisé de bonne qualité. On distingue trois types de problèmes de démarrage à froid [START_REF] Burke | Hybrid recommender systems: Survey and experiments[END_REF] :

-le démarrage à froid pour un nouveau système (« new system ») [START_REF] Middleton | Exploiting Synergy Between Ontologies and Recommender Systems[END_REF], où les performances des systèmes sont très mauvaises en raison de l'absence d'informations sur lesquelles fonder le processus de filtrage personnalisé. Ce problème est généralement traité en exploitant des données externes, données dont on ne dispose pas toujours, selon le cadre applicatif [START_REF] Middleton | Ontological user profiling in recommender systems[END_REF].

-le démarrage à froid pour un nouveau document (« new item ») : c'est un problème spécifique à l'approche collaborative, pour laquelle les objets à recommander ne sont décrits que par les évaluations fournies par les utilisateurs. Ce problème est généralement traité en combinant une approche de filtrage basé sur le contenu avec l'approche collaborative (approche hybride) par exemple utilisant la similarité entre documents [START_REF] Schein | Generative Models for Cold-Start Recommendations[END_REF] ou introduisant des agents intelligents qui évaluent les documents automatiquement [START_REF] Good | Combining collaborative filtering with personal agents for better recommendations[END_REF].

-le démarrage à froid pour un nouvel utilisateur (« new user ») : le profil de l'utilisateur est inexistant et ses communautés sont encore inconnues, ce qui conduit à des recommandations de mauvaise qualité.

Nous nous intéressons ici au démarrage à froid pour un nouvel utilisateur. Selon le type de filtrage, les réponses à ce problème varient. A l'exception des contextes applicatifs où des sources externes d'informations sur les nouveaux utilisateurs existent, l'utilisateur est toujours mis à contribution. Selon les modalités de cette contribution, la tâche est plus ou moins difficile, plus ou moins fastidieuse, et les résultats (profil et communautés résultant du processus de démarrage à froid) sont plus ou moins fiables.

Pour le filtrage collaboratif qui se base sur les communautés formées à partir des évaluations d'utilisateurs [START_REF] Breese | Empirical Analysis of Predictive Algorithms for Collaborative Filtering[END_REF], la technique classique consiste à demander à l'utilisateur d'évaluer un ensemble de documents que le système lui présente, ces documents n'ayant a priori aucun rapport privilégié avec les centres d'intérêt potentiels de l'utilisateur. Cette tâche est simple mais fastidieuse : par exemple, le système de recommandation de films MovieLens1 exige de l'utilisateur au moins 15 évaluations avant de fournir des recommandations, mais les films proposés n'étant pas ciblés pour cet utilisateur, ce dernier peut ne rencontrer que des films qu'il n'aime pas, ou des films qu'il ne sait pas évaluer, comme par exemple des films dont il n'a jamais entendu parler. Ainsi l'utilisateur devra parcourir une liste parfois très longue avant d'atteindre ce nombre de 15 évaluations. Les travaux se consacrant à cette approche ont donc pour objectif de trouver les meilleurs documents à présenter aux nouveaux utilisateurs, et cela indépendamment de l'utilisateur considéré [START_REF] Rashid | Getting to Know You: Learning New User Preferences in Recommender Systems[END_REF].

Pour le filtrage basé sur le contenu et le filtrage hybride [START_REF] Burke | Hybrid recommender systems: Survey and experiments[END_REF], la réponse la plus courante consiste à demander à l'utilisateur de définir ses centres d'intérêt à partir d'une liste de termes et/ou d'exemples décrivant au mieux ses centres d'intérêt [START_REF] Melville | Content-Boosted Collaborative Filtering for Improved Recommendations[END_REF][START_REF] Claypool | Combining Content-Based and Collaborative Filters[END_REF]. L'effort demandé à l'utilisateur est important : il doit procéder à une réflexion pour synthétiser ses centres d'intérêt sous la forme de termes, ou bien rechercher des exemples pertinents de documents. Cette dernière tâche peut être automatisée lorsque le système dispose de données externes sur les utilisateurs, par exemple pour des chercheurs académiques qui sont aussi auteurs de publications [START_REF] Middleton | Exploiting Synergy Between Ontologies and Recommender Systems[END_REF][START_REF] Middleton | Ontological user profiling in recommender systems[END_REF], mais en règle générale on ne dispose pas de telles données. Dans la plupart des cas, le profil résultant est incomplet et bruité.

Enfin, une dernière approche consiste à associer le nouvel utilisateur à un profiltype (« stéréotype ») parmi ceux prédéfinis. Le processus de construction de ces profils-type nécessite un ensemble de données d'apprentissage, puis le processus de démarrage à froid doit confronter à ces profils-type certaines informations relatives au nouvel utilisateur. Le système les obtient généralement en interagissant avec l'utilisateur, par exemple en lui posant une série de questions [START_REF] Krulwich | Lifestyle Finder: Intelligent user profiling using large-scale demographic data[END_REF], mais aussi parfois en exploitant une source d'informations « démographiques » externe comme leurs pages Web personnelles [START_REF] Pazzani | A framework for collaborative, content-based and demographic filtering[END_REF]. Pazzani étudie entre autres les performances de cette approche en la prenant pour unique base d'un système de recommandation « démographique », et nous retenons de son travail que les performances de recommandation via les données démographiques sont certes moins bonnes que celles de systèmes basés contenu ou collaboratifs, mais toutefois acceptables.

Pour conclure, ces processus de démarrage à froid ont tous un coût pour l'utilisateur : d'une part ils requièrent un effort en termes de temps ou d'accomplissement d'une tâche plus ou moins difficile ; d'autre part, le profil et les communautés résultant de ce processus ne peuvent pas donner lieu à des recommandations de qualité. Ils conduisent donc à un rapport coût/bénéfice déficitaire pour les utilisateurs. Suite à ce constat, nous proposons ici d'étudier la qualité obtenue avec une approche où l'on ne demande aucun effort à l'utilisateur (quelques questions « démographiques » dont la réponse est simple, immédiate et sûre), sachant qu'à terme cette approche est destinée à être combinée avec l'une ou l'autre des approches classiques de façon à leur conférer un meilleur rapport coût/bénéfice. Notre approche de démarrage à froid s'apparente donc à celle des profils-type, avec l'optique de limiter au maximum le nombre et la complexité des informations à demander aux utilisateurs.

Approche

Approche par les espaces de communauté

Des travaux antérieurs nous ont conduits à définir le modèle des « espaces de communautés » [START_REF] Nguyen | Modèle d'espaces de communautés basé sur la théorie des ensembles d'approximation dans un système de filtrage hybride[END_REF] comme un cadre pour prendre en compte les divers facteurs de pertinence exploitables dans les systèmes de filtrage d'information. Nous présentons ici les éléments du modèle et les résultats utiles pour la suite.

Un utilisateur est positionné dans divers espaces de communautés, chaque espace Ω a étant associé à un « attribut » a (Age, Profession, Contenu, Evaluation, etc.), et reflétant un facteur possible de rapprochement entre les utilisateurs (même tranche d'âge, même catégorie socio-professionnelle, proximité des thèmes couvrant les centres d'intérêt, similarité dans l'évaluation des documents, etc.). Dans chacun de ces espaces de communautés Ω a , l'utilisateur appartient à une communauté particulière G a . Typiquement, le système de filtrage peut s'appuyer sur chacune de ces communautés pour produire un flux de recommandations (approche collaborative). Etant donné la table de communautés T (voir Figure 1) construite à partir des espaces de communautés, le « vecteur de positionnement » P u = T[u] de l'utilisateur u est composé des positions G a de cet utilisateur dans les divers espaces de communautés Ω a , et chacune de ces positions constitue une source de recommandation potentielle.

A partir d'un vecteur de positionnement incomplet et des données relatives aux autres utilisateurs, nous complétons les valeurs manquantes de ce vecteur et produisons une liste de recommandations pour chacun des espaces de communautés. Ainsi, pour positionner un nouvel utilisateur, nous initialisons d'abord le vecteur de positionnement avec ses données disponibles à froid. Par exemple pour les attributs Profession, Ville, Genre préféré et Evaluation, un nouvel utilisateur u verra son vecteur initialisé ainsi : P u = (Chercheur, Paris, _, _). Nous complétons ensuite ce vecteur de positionnement automatiquement en instanciant les valeurs manquantes, en vue de limiter l'effort de l'utilisateur pour passer le cap du démarrage à froid. Dans la suite, nous décrivons le principe de l'instanciation des valeurs manquantes dans un vecteur de positionnement d'un nouvel utilisateur, qui est faite via un processus de classification par règle, puis le dispositif mis en place pour évaluer l'apport de cette approche.

Principe pour compléter un vecteur de positionnement

Compléter le vecteur de positionnement d'un utilisateur au sein des espaces de communautés se fait en 2 étapes (voir Figure 2). Ce type de méthode commence par une phase d'apprentissage s'appuyant sur les données disponibles pour construire un classificateur qui est un ensemble de règles, X → d où X est un sous ensemble d'attributs et d est l'attribut choisi comme « décision », c'est-à-dire celui pour lequel on veut instancier la valeur manquante. La qualité d'une règle X → d dans le classificateur est généralement mesurée par son support et sa confiance. Le support d'une règle est la proportion d'occurrences de cette règle sur la taille de l'ensemble d'apprentissage, et la confiance est la proportion d'occurrences de cette règle par rapport aux occurrences de la prémisse X.

La méthode se poursuit par une phase de classification, où on cherche une règle applicable X → d dont la prémisse X est satisfaite par les données disponibles de l'utilisateur u considéré. La valeur d de la règle trouvée remplace alors la valeur manquante dans le vecteur de positionnement de u. Pour connaître les détails de ces méthodes, nous conseillons au lecteur de consulter les références suivantes : [START_REF] Quinlan | C4.5 : Programs for Machine Learning[END_REF][START_REF] Liu | Improving an Association Rule Based Classifier[END_REF].

Une fois le vecteur de positionnement complété, il nous faut évaluer sa qualité au niveau de production des recommandations pour l'utilisateur. Dans ce but d'évaluation, nous avons défini de façon ad hoc un processus de recommandation fondé sur le « niveau d'accord » au sein des communautés que nous décrivons cidessous.

Etape 2. Recommandations par « niveau d'accord ». Le principe de cette méthode de production de recommandations est très simple : supposons que le nouvel utilisateur u appartient à la communauté G dans un espace de communautés donné. Alors, le nouvel utilisateur reçoit tous les documents jugés intéressants de façon unanime par la communauté G. Le niveau d'accord au sein de la communauté est alors maximal, puisqu'il y a unanimité.

Ce principe général peut être décliné de diverses manières, par exemple en limitant le « niveau d'accord » à un sous-ensemble de la communauté, comme par exemple aux membres les plus représentatifs de la communauté.

Application au jeu de données MovieLens

Le jeu de données MovieLens2 permet d'appliquer cette approche sur 5 espaces de communautés, à partir desquels nous pouvons générer, entre autres, 3 listes de recommandations : une liste issue de la combinaison des attributs disponibles à froid (Age, Profession, Géographie), et une liste par attribut déduit (Genre préféré et Evaluation).

Jeu de données. Dans la continuité des travaux présentés dans [START_REF] Nguyen | Cartes de communautés pour l'adaptation interactive de profils dans un système de filtrage d'information[END_REF][START_REF] Nguyen | Modèle d'espaces de communautés basé sur la théorie des ensembles d'approximation dans un système de filtrage hybride[END_REF], nous avons utilisé le jeu de données réelles MovieLens qui contient 100 000 évaluations données par 943 utilisateurs sur 1682 films relevant de 19 genres de film. Chaque évaluation contient les identificateurs de film et d'utilisateur, le score et le moment d'évaluation. Nous avons exploité 5 attributs permettant la formation de 5 espaces de communautés : Age, Profession, Géographie, Genre préféré et Evaluation.

Application de l'approche. A partir des 3 attributs disponibles à froid (Age, Profession, Géographie) pour un nouvel utilisateur u 0 , nous pouvons produire divers types de recommandations, présentés dans la Figure 3. R Demog : les recommandations s'appuient directement sur les communautés G Age , G Profession et G Géographie sans passer par l'étape de classification, ici inutile puisque les valeurs du vecteur P u sont déjà connues pour ces attributs. On génère 3 ensembles de recommandations R Age , R Prof , R Géo par niveau d'accord dans chacun des 3 espaces de communautés correspondants, puis on les combine linéairement avec des pondérations égales pour les 3 sources de recommandation. R Genre : les attributs Age, Profession et Géographie sont utilisés en entrée de la classification par règles, qui associe à u 0 une communauté G Genre dans l'espace Ω Genre . Le processus de recommandation par niveau d'accord génère ensuite pour u 0 une liste de recommandations R Genre en rapport avec la position de l'utilisateur dans cette communauté. R Eval : il en est de même pour R Eval où l'espace Ω Evaluation remplace l'espace Ω Genre .

En pratique, voici comment nous avons réalisé la classification et la recommandation.

Méthode de classification par règles.

A l'étape 1 (voir Figure 2), nous instancions les valeurs manquantes via un processus de classification par règles. Après avoir comparé diverses méthodes, nous avons choisi la méthode C5, successeur de la méthode populaire C4.5 [START_REF] Quinlan | C4.5 : Programs for Machine Learning[END_REF].

Recommandation ad hoc par « niveau d'accord ». A l'étape 2 (voir Figure 2), nous produisons les recommandations par « niveau d'accord ». Pour chaque attribut (c'est-à-dire pour chaque espace de communautés), la méthode doit sélectionner les films à recommander parmi ceux qui ont été évalués par la communauté dans laquelle u 0 se situe. On procède à un premier filtre en ne considérant que les films évalués avec un score supérieur ou égal à un seuil S score , puis à un deuxième filtre où on ne conserve que les films qui ont été ainsi évalués par une part suffisante des membres de la communauté, dont la limite est fixée par un autre seuil S accord .

Expérimentation

Nous avons évalué notre approche en comparant ses performances de recommandations à celles d'une approche classique de démarrage à froid obtenue par le recueil de 15 évaluations par utilisateur. Ces performances seront mesurées par rapport à des données de références. Pour cela nous utilisons 3 mesures différentes.

Les données à évaluer et les données de référence

Les listes de recommandations issues de notre approche R Genre , R Eval et R Demog . Nous avons divisé l'ensemble des utilisateurs de MovieLens en deux catégories :

(i) « Nouveaux » utilisateurs (U N ) : 77 utilisateurs qui se sont inscrits au cours du dernier mois (04/1998), et (ii) Utilisateurs « existants » (U E ) : 866 utilisateurs inscrits avant le dernier mois.

Pour les nouveaux utilisateurs (U N ), nous avons calculé les 3 listes de recommandations R Genre , R Eval et R Demog avec les seuils S Score = 4 étoiles et S accord = 25% pour le processus de recommandation par niveau d'accord.

La liste de recommandations R Pearson . Nous nous appuyons sur un exemple de système réel pour calibrer notre base de comparaison, celui du système MovieLens3 pour lequel un nouvel utilisateur doit fournir, outre des informations personnelles, des évaluations sur au moins 15 des films proposés avant de recevoir des recommandations. Pour nous rapprocher de ces conditions, nous extrayons les 15 premières évaluations d'un utilisateur u de U N , qui composent le profil. Nous générons ensuite les recommandations pour ce profil par le processus classique de recommandation selon la corrélation de Pearson [START_REF] Breese | Empirical Analysis of Predictive Algorithms for Collaborative Filtering[END_REF]. On obtient alors R Pearson , une nouvelle liste de recommandations analogue à celles que nous générons par notre approche.

Les données de référence E Réelles . Les évaluations des utilisateurs de U N non utilisées pour générer les listes de recommandations constituent l'ensemble des données de référence : c'est l'ensemble E Réelles . Cet ensemble nous sert de référence dans les calculs de performance.

Mesures d'évaluation

Pour estimer la qualité des listes de recommandations pour un nouvel utilisateur u 0 dans U N , nous utilisons les mesures suivantes.

-Erreur moyenne absolue (MAE -Mean Absolute Error) [START_REF] Rashid | Getting to Know You: Learning New User Preferences in Recommender Systems[END_REF] : cette mesure calcule la différence moyenne entre les prédictions de recommandations du système p j et les scores e j donnés réellement par l'utilisateur dans les évaluations. Dans cet article, nous avons utilisé les deux formules suivantes :

M 1 = - j j j e p E 1 [1] M 2 = - j j j e p R 1 [2]
où E : ensemble des évaluations de référence, R : ensemble des recommandations à analyser (cf. 4.3).

La mesure [1] prend pour référence de normalisation l'ensemble E des évaluations réellement faites par les utilisateurs pour lesquels on produit des recommandations. Mais dans le cas du jeu de données MovieLens, qui provient de l'utilisation réelle d'un système de filtrage collaboratif, rien ne garantit que E Réelles couvre l'ensemble des informations que les utilisateurs auraient évaluées positivement si l'intégralité des documents disponibles leur avait été présentée. Nous complétons donc cette mesure « absolue » par la mesure [2], qui normalise le nombre d'erreurs par le nombre de recommandations produites. Cette mesure diminue l'impact d'un mauvais rappel possible de E Réelles , et offre un bon complément, se prêtant bien à une évaluation comparative entre les différentes approches.

-Corrélation de Pearson [START_REF] Breese | Empirical Analysis of Predictive Algorithms for Collaborative Filtering[END_REF] : cette mesure est souvent utilisée dans le domaine du filtrage collaboratif pour le processus de prédiction de recommandations, mais on peut aussi l'utiliser pour estimer la corrélation entre les recommandations produites et les évaluations réelles :

M 3 = - - - - j j j 2 j 2 j j j ) e

Analyse

De façon générale, la liste de recommandations R Genre domine les autres.

Logiquement, le Tableau 1 et le Tableau 2 donnent les mêmes résultats de comparaison entre les ensembles de recommandations à un facteur de |E Réelles | / |R| près selon l'ensemble de recommandations R en question.

La comparaison des taux d'erreurs entre R Genre et les autres ensembles de recommandations montre l'utilité de notre approche comme une solution personnalisée pour le problème du démarrage à froid dans un système de filtrage. Néanmoins, ces bons résultats ne permettent pas de déterminer quelle part de ces performances sont dues à la production des premières recommandations, puisqu'elles dépendent de plusieurs facteurs comme la performance de la méthode de classification, la qualité du calibrage des paramètres utilisés dans le filtrage collaboratif par niveau d'accord, et l'hybridation du filtrage par des attributs démographiques.

Les résultats du Tableau 3 confirment la qualité de l'ensemble R Genre par rapport à l'ensemble R Pearson et montrent toujours la mauvaise qualité de R Démog . Ils rendent également compte d'une qualité relativement stable en fonction de la taille des ensembles de recommandations.

Par ailleurs, nous avons montré dans [START_REF] Nguyen | Modèle d'espaces de communautés basé sur la théorie des ensembles d'approximation dans un système de filtrage hybride[END_REF], en analysant ces mêmes données, que l'attribut Genre peut être mieux prédit par les autres attributs, que l'attribut Evaluation. Ce résultat est ici confirmé en pratique.

Pour conclure, nous obtenons des résultats meilleurs que la technique classique prise pour base de comparaison, et du fait de l'absence d'intervention de l'utilisateur dans notre approche, nous concluons à un rapport coût/bénéfice bien meilleur.

Conclusion

Nous avons défini une méthode qui s'appuie sur les données disponibles à froid pour offrir à tout nouvel utilisateur un premier vecteur de positionnement complet sans qu'il ait d'effort à fournir.

Nous avons montré que ce vecteur permet de générer des recommandations de meilleure qualité que celles produites suite à un processus de démarrage à froid classique, où l'utilisateur doit fournir un effort important (en l'occurrence des évaluations). Nous obtenons donc un rapport coût/bénéfice bien meilleur que celui de l'approche classique prise pour base de comparaison. Nous suggérons donc d'utiliser cette méthode comme préalable à un processus de démarrage à froid classique, afin de rendre ce dernier plus performant car mieux ciblé.

Cette première approche a validé expérimentalement le principe de correction automatique de vecteurs de positionnement. Bien évidemment, les résultats obtenus nous encouragent à approfondir la méthode, et notamment d'envisager une approche théorique approfondie.

Figure 2 .

 2 Figure 2. Principe pour compléter un vecteur de positionnement.

Figure 3 .

 3 Figure 3. Production de diverses listes de recommandations à partir des données disponibles à froid.

  Les résultats des mesures M 1 , M 2 et M 3 en fonction du nombre de meilleures recommandations (Top_N) à présenter aux utilisateurs sont illustrés dans Tableau 1, Tableau 2 et Tableau 3, où nous comparons chaque liste de recommandations aux données de référence E Réelles . L'approche servant de base de comparaison (R Pearson ) est sur la première ligne, et la meilleure approche est en italique.

	Plus les taux d'erreurs M 1 et M 2 diminuent, plus la qualité de l'ensemble de
	recommandations R augmente. Au contraire, plus M 3 est grand, meilleure est la
	qualité des recommandations.
	4.3. Résultats
	|R|	Top_5 Top_10 Top_15 Top_20 Moyenne
	Approche
	R Pearson	1,76%	2,84%	4,09%	5,30%	3,50%
	R Genre	1,38%	2,48%	4,09%	5,91%	3,47%
	R Eval	3,32%	4,30%	4,95%	4,99%	4,39%
	R Demog	2,59%	4,15%	4,79%	6,51%	4,51%
	Tableau 1. Résultats de la mesure d'erreur moyenne absolue (M 1 ).
	|R|	Top_5 Top_10 Top_15 Top_20 Moyenne
	Approche
	R Pearson	27,97% 24,02% 22,83% 22,45%	24,32%
	R Genre	26,59% 24,96% 23,18% 22,44%	24,29%
	R Eval	43,45% 29,54% 27,59% 27,45%	32,01%
	R Demog	83,32% 83,44% 79,74% 79,83%	81,58%
	Tableau 2. Résultats de la mesure d'erreur moyenne absolue (M 2 ).
	|R|	Top_5 Top_10 Top_15 Top_20 Moyenne
	Approche
	R Pearson R Genre	) 28,95% 25,90% 24,02% 24,97% e e )( p p ( 29,92% 30,99% 31,53% 32,23%	25,96% 31,17%	[3]
	R Eval	e 31,39% 30,40% 32,13% 30,52% ( ) p p (	31,11%
	R Demog	18,08% 19,45% 20,34% 19,20%	19,27%
	où e : moyenne des scores des évaluations faites par l'utilisateur, p : moyenne des scores prédits dans les recommandations. Tableau 3. Résultats de la mesure de corrélation de Pearson (M 3 ).

http://movielens.umn.edu

http://movielens.umn.edu

http://movielens.umn.edu