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

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

Diagnosing and measuring incompatibilities between pairs of services ⋆

This text presents a tool, from its design to its implementation, which detects all behavioural incompatibilities between two 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 the location in the service interfaces where these incompatibilities occur. 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

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 nonfunctional. The structural interface of a service describes the types of messages that the service produces or consumes and the operations underpinning these message exchanges. In the case of web services, the structural interface of a service can be described for example in WSDL [START_REF] Weerawarana | Web Services Platform Architecture[END_REF]. The behavioural interface refers to the order in which the service produces or consumes messages. This can be described for example using BPEL ( [START_REF] Weerawarana | Web Services Platform Architecture[END_REF]) 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.

-A measure of similarity between behavioural interfaces of services 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.

The paper is structured as follows. Section 2 frames the problem addressed and introduces a motivating 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

As a motivating example, we consider services that handle purchase orders processed either online or offline. In Figure 1 the 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). The figure distinguishes between the provided interface that a service exposes, and its required interface as it is expected by its clients or peers. Specifically, Figure 1-a shows the provided interface P of a service S. S 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 1-b).

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? Specifically, we consider three situations: (1) an operation1 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 ′ . We argue that other changes can be described in terms of these ones.

In Figure 1, we observe that the flow which loops from 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 Fig. 1. Differences between two service interfaces. 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. In technical terms, a difference between P ′ and P only leads to an incompatibility if it causes P ′ not to simulate P .

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 modelbased verification of web service compositions and choreography[END_REF].

Following [START_REF] Beyer | Web service interfaces[END_REF][START_REF] Motahari-Nezhad | Semi-automated 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 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 Submitted to DEXA'09 page 3

in Section 2. The message m has prefix > (respectively <) when it is sent (respectively received). Each conversation initiated by a client starts an execution of the corresponding FSM. The figure shows also all differences between P and P ′ . This latter will be 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 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 remain compatible with P ′ (see [START_REF] Ait-Bachir | Detection behavioural incompatibilities between pairs of services[END_REF] for a proof).

Assumptions :

(1) Even thought web service communication is not always synchronous, we assume synchronous communication as it provides, to a certain extent, a suitable basis for analysing service behaviour. First of all, synchronous communication is more restrictive than asynchronous communication. Therefore, incompatibilities that arise within the asynchronous case arise in the synchronous case as well. Second, for a relatively large class of interfaces, it has been shown that adopting the synchronous communication model leads to the same analysis results than adopting the asynchronous model [START_REF] Fu | Synchronizability of conversations among web services[END_REF].

(2) 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.

(3) We assume messages with the same structure to be equivalent.

Submitted to DEXA'09 page 4

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 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.1) and when an operation in P is replaced with another one in P ′ (this is called a modification, see Section 4.2). We do not detail here the situation when P ′ has an operation which does not exist in P as it is transposed from the addition mentioned above.

Deletion of an operation

Figure 3 depicts two situations where an operation appears in P and not in P ′ . First in Figure 3-a, 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 both labelled by the same operation: >X(m). The same remark applies to S3 and S3 ′ with the operation <Z(m).

>R(m) <Z(m) <Z(m) >X(m) deletion

Interface P

Interface P'

>X(m) S2 S3 S2' S3' S1' S1 (a) >R(m) deleted in P ′ Interface P S2 S1 S3 Interface P' S3' S2' S1' deletion <Z(m) >R(m) <Z(m) >X(m) (b) >X(m) deleted in P ′

Fig. 3. Diagnosis of deletions

In Figure 3-b 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 l angleS2, 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 (each part of this condition is explained further down).

Label (s•) -Label (s ′ •) 1 ∧ Label (s ′ •) -Label (s•) = 0 (1) ∨ ∃t ∈ s•, ∃t ′ ∈ s ′ • : Label (t) ∈ Label (s ′ •) ∧ ExtIn(t ′ , (t•)•) (2)
In the previous equations, the notations given below apply (examples refer to Figure 3):

-s• is the set of outgoing transitions of s (e.g. S1• = { S1, >X(m), S1 , S1, <Z(m), S3 , S1, >R(m), S2 } -t• is the target state of the transition t. (e.g. S1, <Z(m), S2 • = S2). -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 (respec- tively 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 1) 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 2). 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 transition t's 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 only visited once.

Modification of an operation

Figure 4 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 as well 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 state pair to be visited next in the synchronous traversal of P and P ′ is such that both transitions involved in the modification are traversed simultaneously. In this example, S2, S2 ′ should be visited next.

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•) ∧¬∃t2 ∈ s• : ExtIn(t1 ′ , (t2•)•)) ∧¬∃t2 ′ ∈ s ′ • : ExtIn(t1, (t2 ′ •)•))
5

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] Ait-Bachir | BESERIAL: Behavioural service analyser[END_REF].

Detection algorithm

The algorithm implementing the detection illustrated in the previous section is detailed in Figure 5. 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 an addition, deletion or 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 motivating example (see Figure 2) returns the set of tuples { S2, <OfflineOrder, S2', null , S4, null, S4', <Transfer S6, >STN, S6', >ASN } which summarises the differences found when comparing P ′ to P . It is worth noting that comparing P to P ′ returns { S2',<null, S2, OfflineOrder , S4',<Transfer, S4, null S6',>ASN, S6, >STN }.

The algorithm proceeds as a depth-first algorithm over state pairs of the compared FSMs. Two stacks are maintained: one with the visited state pairs and another with state pairs to be visited (see Figure 5, line 5). These state pairs are such that the first state belongs to the FSM of P i while the second state belongs to the FSM of 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 to memorise the already visited pairs of states (line 10).

Labels in common among those of outgoing transitions of si and labels of outgoing transitions of sj are considered as unchanged (no change to detect). Thus, a set of state pairs is built where states are target states of common labels (line 11). Also, the algorithm reports all differences between the outgoing transitions of si and the outgoing transitions of sj (line 12). The two set differences of transitions are put 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 13 calculates all combinations of transitions whose labels are not in common among Label (si•) and Label (sj•). Lines 14 to 16 are dedicated to detect a deletion when an outgoing transition of si does not match any transition in sj•. The result is returned as set of tuples < si, t, sj, null > where t is one of the outgoing transitions of si whose label does not appear in any of sj's outgoing transitions. As mentioned in Section4.1, when an operation is deleted in P j FSM the algorithm progresses in P i FSM, along the branch of the transition which does not exist in P j, but remains in the same state in P j FSM.

∈ si• × sj• | Label(ti) = Label(tj)} { pairs of matching transitions } 12 difPiPj ← {ti ∈ si• | Label(ti) ∈ Label(sj•)} difPjPi ← {tj ∈ sj• | Label(tj) ∈ Label(si•)} 13 combPiPj ← difPiPj × difPjPi { all
The detection of an addition is quite similar to the detection of a deletion (lines 17 to 20).

The variable combPiPj contains transition pairs such that the label of the first transition ti belongs to si• but does not belong to Label (sj•) while the label of the second transition tj belongs to sj• but not to Label (si•). For each transition pair satisfying this condition, the algorithm checks the conditions for diagnosing an addition (lines 22 to 24), a deletion (lines 25 to 27) or a modification (lines 28 to 30).

Finally, the algorithm also progresses along pairs of matching transitions, i.e. pairs of transitions with identical labels (line 31). In fact, if no incompatibilities are detected in the current state pair, the algorithm will only progress along pairs of transitions that match one another.

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 ′ ).
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 ).
Submitted to DEXA'09 page 10

Adding up the complexity of the pre-processing and the detection algorithm, the overall complexity is

O(n * m + (m) 2 + n ′ * m ′ + (m ′ ) 2 + n * n ′ + 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 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.

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 M QS. 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.

Submitted to DEXA'09 page 11

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.

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 | Semi-automated adaptation of service interactions[END_REF], authors introduced a technique to diagnosis message structure mismatches 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 ad apter each time and incompatibility is detected. However, this technique can only be applied 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 this text 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 our proposition does.

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 in service discovery 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].

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. As web services are used as black boxes, this approach does not apply to web services.

Recent research has addressed interface similarity measures issues. In [START_REF] Lohmann | Correcting deadlocking service choreographies using a simulationbased 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.

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 models. This function is the same as the one introduced in [START_REF] Sokolsky | Simulation-based graph similarity[END_REF] which consider the behavioural semantics. The similarity measure is a heuristic which returns a value which calculated according to changes involved by the addition and by the deletion of an operation. However, the result do not pinpoints the exact location of these changes.

In [START_REF] Wombacher | Matchmaking for business processes based on choreographies[END_REF], the authors propose an approach to business process matchmaking based on automata extended with logical expressions associated to states. Their algorithm determines if the languages of two automata (which model two business processes) have a non-empty intersection. This technique for detecting process differences returns a Boolean output. It does not provide detailed diagnosis.

Conclusion and further study

In this text we have presented both design and implementation of a tool intended to detect differences (addition, deletion or modification of an operation) that give rise to behavioural incompatibilities between two service interfaces. 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. We have introduced 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) detecting complex types of incompatibilities (e.g. the order of two operations is swapped or an entire branch is deleted); and (ii) assisting business process designers in determining how to address an incompatibility. Also, communications are currently assumed to be synchronous. Future work will aim at extending the technique to address the asynchronous case. This extension can be achieved by maintaining a buffer of unconsumed messages during the traversal, as it is proposed in [START_REF] Motahari-Nezhad | Semi-automated adaptation of service interactions[END_REF].

Fig. 2 .

 2 Fig. 2. FSMs modelling P and P ′ .

Fig. 4 .

 4 Fig. 4. Diagnosis of a modification/replacement

Fig. 5 .

 5 Fig. 5. Detection algorithm

  pairs of si and sj uncorresponding outgoing transitions. }

	14	If difPiPj	1 and difPjPi = 0 then	{ deletion }
	15	For each t in difPiPj do setRes.add(< si, t, sj, null>)
	16	If((t•, sj) / ∈ visited) then toBeVisited.push((t•, sj))
	17	If difPjPi	1 and difPiPj = 0 then	{ addition }
	18	For each t in difPjPi do
	19	If (polarity({ addition }
	23	setRes.add(< si, null, sj, tj>)
	24	If ((si, tj•) / ∈ visited) then toBeVisited.push((si, tj•))
	25	If ExtIn(tj, (ti•)• ) then	{ deletion }
	26	setRes.add(< si, ti, sj, null,'deletion'>)
	27	If ((ti•, sj) / ∈ visited) then toBeVisited.push((ti•, sj))
	28	If ( (¬∃tj { modif. }
	29	setRes.add(< si, ti, sj, tj>)
	30	if((ti•, tj•) / ∈ visited) then toBeVisited.push((ti•, tj•))
	31	For each (ti, tj) in combEqual do
		If ((ti•, tj•) / ∈ visited) then toBeVisited.push((ti•, tj•))
	32 Return setRes

t) = 'send') then setRes.add(< si, null, sj, t>) { otherwise this addition does not lead to incompatibility } 20 If ((si, t•) / ∈ visited) then toBeVisited.push((si, t•)) 21 For each (ti, tj) in combPiPj do 22 If ExtIn(ti, (tj•)•) then ′ ∈ sj• : ExtIn(ti, (tj ′ •)•)) ∧(¬∃ti ′ ∈ si• : ExtIn(tj, (ti ′ •)•))) then

Table 1 .

 1 Fragment of experimental results

	Interface 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 DEXA'09 page 5

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 DEXA'09 page 7

Submitted to DEXA'09 page 9

XML Common Business Library (http://www.xcbl.org/). Submitted to DEXA'09 page 12

⋆ This work is partially funded by the Web Intelligence Project, Rhône-Alpes French Region


Stéphane Ayache

Georges Quénot
email: georges.quenot@imag.fr

Laurent Besacier

The LIG Multi-Criteria System for Video Retrieval

Keywords: H.3.3 [Information Storage and Retrieval]: Information Search and Retrieval Algorithms, Experimentation Video retrieval, multi-criteria search

The LIG search system uses a user-controlled combination of six criteria: keywords, phonetic string, similarity to example images, semantic categories, similarity to already identified positive images, and temporal closeness to already identified positive images.

THE LIG VIDEO RETRIEVAL SYSTEM

The LIG search system [START_REF] Ayache | CLIPS-LSR Experiments at TRECVID 2006[END_REF] uses a user-controlled combination of six criteria: keywords, phonetic string (new in 2009), similarity to example images, semantic categories, similarity to already identified positive images, and temporal closeness to already identified positive images (Figure 1). The system outputs an ordered list of relevant shots for each topic after interaction with the user (initial query and multiple relevance feedback). This system was used for TRECVID [START_REF] Smeaton | Evaluation campaigns and TRECVid[END_REF], VideOlympics [START_REF] Cees | VideOlympics: Real-time evaluation of multimedia retrieval systems[END_REF] Relevance is first assigned to speech segments and then projected onto overlapping shots.

Criterion 2: Phonetic string based search. Video documents are transcribed at the phonetic level using a subset of the International Phonetic Alphabet (IPA). Queries are made in the same way and the search is done using a phonetic string spotting algorithm. Combination of search criteria. The user can dynamically define his search strategy according to the topic and/or the looking of the retrieved images. Each search criterion can be independently configured and given a global weight for the search. The per-criterion relevances are linearly combined according to the criteria weights to produce the final key frame relevance.

  and the Star Challenge [4].

Figure 1 :

 1 Figure 1: The LIG video retrieval system

Criterion 3 :

 3 Similarity to image examples. Visual similarity between key frames and image examples is looked for using color and texture characteristics (4×4×4 color histograms and 8×5 Gabor transforms). normalized and the turned into a relevance value for each feature.

Criterion 4 :

 4 Feature based search. Video shots are ranked according to the 36 pre-classified categories used in the TRECVID 2007 high level feature detection task. Criteria 5 and 6: Visual similarity and temporal closeness. Visual similarity and temporal closeness (within the video stream) to already retrieved images can be used for the search. These images have to be marked by the user as positive examples for similarity based search and/or as positive examples for temporal closeness based search (relevance feedback).


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

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

Reconciling Web service failing interactions. Towards an approach based on automatic generation of mediators

Interactions between Web services are based on interfaces which describe Web services on both structural and behavioural perspectives. It can happen that the interface provided by a service does no longer match (for instance, because of an evolution) the interface required by its partners. In this situation, and until the required interfaces are fixed, interactions cannot succeed. To address this issue, and focusing on the behavioural part of interfaces, we propose an approach based on a mediator, automatically generated, which aims to seamlessly resolve incompatibilities during service interactions.

Introduction

As Web service interactions rely on message exchanges, modelling Web service aims at describing messages as well from the structural point of view (types of exchanged messages) as from the behavioural point of view (control flow between message exchanges). With this setting, a Web service's interface is defined as the set of messages it can receive and send, and the inter-dependencies between these messages. We distinguish the provided interface an existing service exposes, from its required interface as it is expected by its clients (i.e. applications).

As a Web service evolves, its interface is more likely to be modified too. This leads to the situation where the provided interface of a service does no longer correspond to the one its partners expect. Two solutions thus apply: (1) modify the service in order to make the interface it provides match the interface required by each client; (2) introduce an adapter that reconciles the provided interface with those required by the partners. The former solution is not satisfying because the same service may interact with many other partners which consider its original interface. The same service has to expose as many provided interfaces as collaborations it is involved in. The latter solution consists in supplying an adapter which is capable of matchmaking each of the required interfaces with the one provided by the service.

A service is generally described according to its structural or behavioural dimensions, or even according to its non-functional dimension. Thus, interface matchmaking must be studied according each of these dimensions. Dealing with structural matchmaking essentially leads towards reconciliation between different message types. This issue has been widely studied (see for example [START_REF] Ponnekanti | Interoperability among independently evolving web services[END_REF][START_REF] Oaks | Guided interaction: A mechanism to enable ad hoc service interaction[END_REF]) and many commercial systems exist (e.g. Microsoft's BizTalk Mapper). Conversely the problem of behavioural matchmaking is still a research topic [START_REF] Peltz | Web services orchestration and choreography[END_REF][START_REF] Altenhofen | An execution semantics for mediation patterns[END_REF][START_REF] Benatallah | Developing adapters for web services integration[END_REF].

The study reported in the paper aims at dealing with this latter issue. Its main contribution is the definition and implementation of an architecture for service providers whose main modules are:

-Mediators (one associated to each service). A mediator is responsible for accepting messages received (on the behalf of the service), detecting incompatibilities, and if necessary, seamlessly reconciling failing interactions. -A generator of mediators. Mediators are implemented by finite state automaton each of which automatically generated. The generation process, according to the previous version of the provided interface and its current one issued by the last modification detects: (1) whether the current version simulates the previous one and if not (2) generates the mediator. As a first stage, the mediator is limited to consider deletion of operations only.

The rest of the text is structured as follows. In Section 2 we frame the problem addressed and discuss related work. In section 3, we describe the main principles of our approach. The processes we propose for incompatibility detection and mediator generation are detailed in Section 4. While Section 5 exposes implementation details, Section 6 concludes and sketches further work.

To illustrate the issues we deal with, we consider a service meant to sell and deliver goods. In Figure 1, an activity diagram (UML) is given which models interactions the service BestBargain is capable to handle, and their inter dependencies. The activity is named according to the type of message being sent or received. As said before, we focus only on the behavioural dimension of interfaces. With this setting, a modification could be either an addition, a deletion, or an update of an activity, or any combination of these modifications. Deletion of an operation is studied according to its nature:

-The operation to be deleted belongs to a sequence of operations. Such an example could be the deletion of the activity Send response from BestBargain's interface. After this modification, clients whose required interface still contains the corresponding operation (an incoming message), will expect the message but never receive it. -The operation to be deleted corresponds to a choice in a conditional composition. For instance, the activity Receive cash is no longer available. Thus, clients whose interfaces still consider this option and which are willing to use it can no longer send it as the service does not expose any more the operation for its reception.

The mediator-based approach proposed in this paper aims at detecting interactions which fail because of incompatibilities between the interface a service provides and the one its clients require. In the first of the situations discussed above, the mediator, to allow the conversation to carry out, sends, when necessary, a message of the same type of Send response, so the client gets an incoming message, as close as possible to what it was expecting. In the second situation, the mediator intercepts the message Receive cash sent by the client, and on the behalf of the service returns a message asking for another choice.

The issues illustrated below have been partially addressed before, with various points of view. Web service interactions may fail because of interface incompatibilities ac-cording 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, as ours, on a mediator (called virtual supplier) it focuses on structural dimension of interfaces only. The virtual supplier is responsible for adapting the structure of exchanged messages.

Conformity 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 interfaces, described for instance by automata, are compatible (see for example [START_REF] Foster | Modelbased verification of web service compositions[END_REF][START_REF] Bordeaux | When are two web services compatible?[END_REF][START_REF] Haddad | Modelling web services interoperability[END_REF]). The behavioral interrface describes the structured activities of a business process. Some studies discuss the translation into automaton, of interfaces described in WSCI1 or BPEL 2 . Petri nets may also be used to formalise interface's behavioural dimension. Checking interface compatibility is thus based on bi-similarity algorithms [START_REF] Djikman | Service-oriented design: A multi-viewpoint approch[END_REF][START_REF] Martens | Analyzing compatibility of bpel processes[END_REF]. These approaches do not deal with reconciliation issues when incompatibilities occur.

Recent research has addressed interface adaptation issues. In [START_REF] Benatallah | Developing adapters for web services integration[END_REF], authors present a framework which relies on identifying mismatch patterns. Other techniques for generating adaptors are defined in [START_REF] Schmidt | Generating adapters for concurrent component protocol synchronisation[END_REF][START_REF] Dumas | Adapt or perish: Algebra and visual notation for service interface adaptation[END_REF]. In [START_REF] Dumas | Adapt or perish: Algebra and visual notation for service interface adaptation[END_REF], authors propose an algebra of interface transformation operators and a visual language based on this algebra. All these studies differ from ours in that they provide means for developers to implement adaptors, while we aim at automatising the generation of mediators.

Preliminaries

In this section we first introduce the mediation principle which is behind our approach, then we show how we model services' behaviour with automata. Eventually, we introduce notations and give definitions necessary for the understanding of our solution.

Mediation principles: the cornerstone of the conversation mediation between two Web services, is that of each message being sent or received by the two partners, pass through a third partner called a mediator [START_REF] Altenhofen | An execution semantics for mediation patterns[END_REF]. For instance, a message sent by a client is intercepted first by the mediator which checks whether the message still conforms to the service's interface. If yes, the message is forwarded to its recipient, otherwise the mediator tries to reconcile the resulting incompatibilities. In our approach, the mediator is automatically generated according to the version of the interface issued by the last evolution and its previous one.

We choose to model the behaviour of a Web service with Labelled Transition Systems (LTS) 3 . A LTS is a directed graph where nodes refer to all possible states of a system and arcs model transitions between states [START_REF] Haddad | Modelling web services interoperability[END_REF]. Each arc is labelled with an event. A guard condition could be associated to transition.

In our context of modelling behavioural dimension of interfaces, transitions are labelled with messages to be exchanged. When a message is sent or received, the corresponding transition is fired (it is so, only when the guard, if any, is evaluated to true). Internal operations, which are not shown in services' interface, are also modelled by transitions. Each state describes a particular step of the business process implemented by the service. Operations on data can also be defined within states (e.g. to update the value of variables associated to the process instance's context).

Figure 2 depicts the LTS modelling the shipment phase of the illustrating example presented in Section 2. In this example, after the information about the payment is sent (by transfer, cheque or cash), the client sends his preference for the shipment (express, the day after, etc.). The operation enacted by this message, sends in turn, a response towards the client. Then, the delivery order is issued by the service and sent to the client.

Figure 2. Shipment mode LTS

The message m is denoted by >m (respectively <m) when it is sent (respectively received) (see Figure 2). Each conversation initiated by a client (identified by c) generates an instance of the corresponding automaton.

Definitions and Notations:

A LTS is a tuple (S, L , T, s 0 , F) where: S is a set of states, L a set of events (actions), T the transition function. 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.

We denote by P ′ the version of the interface issued by the last modification while P denotes the previous one. Both provided interfaces, P and P ′ , are respectively described by the following LTSs: (S, T, s 0 , F, L), and (S ′ , T ′ , s ′ 0 , F ′ , L ′ ).

3 Petri Net-based was another option. We do not discuss this choice here, as it is out of the scope of this paper.

We adopt the following notations [START_REF] Djikman | Service-oriented design: A multi-viewpoint approch[END_REF]. Examples refer to the LTS depicted in Figure 2: s• is the set of outgoing transitions from s (e.g. shipmentMode• = { >c:result(msg)}). -•s is the set of the incoming transitions for the state s (e.g. •responseMode= {>c:result(msg)}). t• is the target state of the transition t (e.g. >c:result(msg)• =responseMode). -•t is the source state of the transition t (e.g. •>c:result(msg)=shipmentMode).

The • operator (respectively •) is generalised to a set of transitions (respectively states). For example, if T is a set of transitions such as:

T = n i=1 {t i } then T • = n i=1 {t i •}.
Compatibility checking between two interfaces relies on simulation calculus [START_REF] Clarke | Model Checking, chapter Equivalences and Preorders between Structures[END_REF]. Communication operations (named distinguishable behaviour, in [START_REF] Bordeaux | When are two web services compatible?[END_REF]) only are considered in this process. To abstract internal operations in an automaton, we use a reduction algorithm which eliminates the ǫtransitions [START_REF] Van Glabbeek | Branching time and abstraction in bisimulation semantics[END_REF]. This algorithm is applied to LTSs whose internal operations are considered as ǫtransitions.

To check whether a mediator is needed, it is necessary to identify situations when the version P ′ does not simulate its previous one P. If P ′ simulates P (denoted P P ′ ) then each interface R required by a client, which is compatible with P (denoted R ∼ P) remains compatible with P ′ as shown below. Let R denotes the opposite interface of R obtained by transforming each message being sent to a message being received and conversely. Given R ∼ P, thus R P [START_REF] Bordeaux | When are two web services compatible?[END_REF]. Due to the transitivity property of the preorder relation of simulation [START_REF] Clarke | Model Checking, chapter Equivalences and Preorders between Structures[END_REF], we have R P ′ (because R P and P P ′ ). Hence, R conforms to P ′ (R ∼ P ′ ). Thus, the detection and the resolution of incompatibilities are relevant only if P ′ does not simulate P.

Detection and Resolution

In the study reported in this text, we focus on incompatibilities due to the deletion of operations (i.e. deletion of messages to be sent or received as specified in the provided interface). Deleting operations is discussed depending on three cases: deleting an operation or a sequence of operations (see Section 4.1). We distinguish the specific case of an acknowledgement (see Section 4.2); the third case we consider consists in the deletion of an option among a conditional composition (see Section 4.3).

To detect incompatibilities, P and P ′ are browsed in parallel from their respective initial states s 0 and s ′ 0 . The search 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. This search is implemented by functions detailed below. Each returns a tuple < t ypeI, s, s ′ > where t ypeI is the type of the incompatibility between the sub-automaton starting respectively from s and s ′ . These functions are called by the algorithm presented in Section 5.

Deleting an operation from a sequence

As illustrated in Section 2, after an operation (or a sequence of operations) has been deleted from the service's provided interface, clients can no longer use it. To reconcile the resulting failing interactions, the mediator simulates the existence of this operation whose corresponding message is not forwarded to the service. The mediators's behaviour is defined in such a way it can handle the reception of such messages as well as those which have to be forwarded to the service because they are exposed in the current version of its interface (see Figure 3).

Figure 3. Mediator's LTS (deletion of an operation)

With respect to our scenario, the version P of the provider contains an operation that permits clients to choose the shipment mode (see Figure 2). The corresponding operation is followed by an other one whose role is to return the shipment mode which will eventually be chosen (it could be different than the one wished by the client). After the evolution which produced the new interface P ′ , this operation is no longer available. The automaton shown in Figure 3, is derived from the one associated to P where the state responseMode and both transitions >c:result(msg) and >c:deliveryOrder(itmList) have been added (see the path in bold, shown in Figure 3). The message associated to >c:result(msg) conforming to its type defined in P is sent to clients which require P, and wait for an answer before they can carry out and accept the message >c:deliveryOrder(itmList).

The detection of this kind of evolution is formalised by the following expression. An operation is defined in P but missing in P ′ , if it exists a pair s and s ′ (respectively in P and P ′ ) which satisfies:

s• = ∅ ∧ (s ′ • = ∅ ∨ (s ′ • = ∅ ∧ s • ∩ s ′ • = ∅ ∧ (((s•)•)•) ⊆ s ′ •))
The deleted operation is detected when s has outgoing transitions (i.e. s is not a final state, expressed by s• = ∅) and s ′ does not have any outgoing transitions (s ′ is a final state, formulated by s ′ • = ∅). An other case of operation deletion is detected when the outgoing transitions of s are not included in the outgoing transitions of s ′ (formulated by s • ∩ s ′ • = ∅). In this case, the outgoing transitions of the subsequent states of s are included in the outgoing transitions of s ′ (formulated by (((s

•)•)•) ⊆ s ′ •).
The expression above can be generalised in order to detect the deletion of a sequence of operations:

s• = ∅ ∧ (s ′ • = ∅ ∨ (s ′ • = ∅ ∧ s • ∩ s ′ • = ∅∧ I ncEt (s•, s ′ •)) where: I ncEt (s•, s ′ •) = s• = ∅ ∧ s• ⊆ s ′ • ∧ (s•)• i=1 I ncEt ((((s•)•) i )•, s ′ •)
The idea is to check whether it exists at least one subsequent state of s whose outgoing transitions are included in the set of outgoing transitions of s ′ . This test is based on the function I ncEt (s•, s ′ •) which implements an extended inclusion. If such incompatibility is detected for a pair < s, s ′ >, a path, containing a sequence of transitions and states, is built starting from s in P and ending in a state whose outgoing transitions are included in s ′ •. The mediator's automaton is first built by the one describing P ′ . Then, this path is added to it, starting from s ′ and ending in states

(s ′ •)•.

Deletion of an Acknowledgement

After deleting an acknowledgement, clients who are unaware of these changes may wait indefinitely for this message that will never come. Therefore, the mediator must be able to act on the behalf of the service, and send a message the client is waiting for. The LTS modelling the mediator is shown in Figure 4. The mediator is first initialised by the LTS of the new version of the interface. Then, between states order and invoice a path is added (with states confirmation and both transitions >c:send acknowledgement and >c:send invoice). This path is only meant to be used in case a client still requires the previous version of the service's interface.

The expression to detect an acknowledgement deletion is based on the conjunction of the two following boolean expressions (s and s ′ are states in P and P ′ respectively):

1 : s • = 1 ∧ Message(•s) = Message(•s ′ ) = {< m} 2 : Message(s•) = {> m} ∧ s• s ′ • ∧ ((s•)•)• ⊆ s ′ •
When a message is received before entering in s and s ′ (which is expressed by Message(

•s) = Message(•s ′ ) = {< m}), the confirmation being sent belongs to s• but it does not in s ′ • (expressed by Message(s•) = {> m} ∧ s• s ′ •).
The confirmation is sent in one of the outgoing transitions of s. Then, the outgoing transitions of the subsequent state of s are included in s ′ • (formulated by

((s•)•)• ⊆ s ′ •).
The resolution of this incompatibility is similar to the one which applies for operation deletion, seen before. Thus, starting from s and s ′ , the mediator interface is such as it has a path containing a transition labelled by the acknowledgement operation followed by the next operation after the acknowledgement. The transition of the acknowledgement operation is added within the outgoing transitions of s ′ and the transition of the operation following the acknowledgement is added within the incoming transitions of the successor state of s ′ (see Figure 4).

Deletion of an option in a switch case

To reconcile the conversations which fail because an option has been deleted from an interface, the mediator intercepts the message that contains the option chosen by the client, but not available any more. Instead of forwarding the message to the service, a reject is returned by the mediator to the client, which can, in turn, choose another option. This leads to a mediator whose behaviour is depicted in Figure 5: clients wishing to pay by cash, will receive a reject until they choose another option. The detection of this incompatibility is formalised by the expression below:

Receivings(s•) 2 ∧ s • -s ′ • ≥ 1 where s • -s ′ • = {t ∈ s • |t / ∈ s ′ •}
The detection of option deletions aims at verifying first, if the set of the outgoing transitions of s contains at least two transitions associated to message receptions (formulated by Receivings(s•) 2), and, if at least one of the outgoing transitions does not exist anymore ( s • -s ′ • ≥ 1). For each option that no longer exists in the new version of the interface, a corresponding path is added in the mediator's LTS. Each of these paths starts from a state modelling the choice of the missing option and loops back to its preceding state. A guard is also added to this path in order to limit the number of fails allowed (see Figure 5).

Algorithm of incompatibility detection

The algorithm implementing the detection is detailed in Figure 6. Given P ′ the new version of the service's interface and P the previous one, the principle of the algorithm is to browse in parallel both LTSs describing P ′ and P. It proceeds so, starting from s 0 and s ′ 0 the initial states of P ′ and P LTSs respectively. The algorithm aims at finding all pairs of states s and s ′ which satisfies one of the three functions O pt, Seq and Ack (each of which associated to each case discussed in the previous section). Each function returns the type of the detected incompatibility (if any) and the pair of states indicating, where in P ′ and P LTSs, the incompatibility occurs (see line 0).

Figure 6. Algorithm of incompatibility detection

The initial call of the algorithm is realised by the expression Detection(s, P, s ′ , P ′ ). Values for the parameters, at each recursive call, are determined according to the type of deletion, as detected by the functions O pt, Seq and Ack. A function named end L T S(P: L T S, S: State): L T S is introduced. Given an LTS P and one of its state S, end L T S(P, S) is the fragment (an LTS) of P starting from the state S.

If each function (O pt, Seq, and Acq) returns a negative result (no incompatibity detected), then the algorithm is recursively applied on each pair end L T S(P, s Suc), and end L ST (P ′ , s Suc ′ ) where, for each t ∈ s•, s Suc = t• (in P), and s Suc ′ = t• (in P ′ ). Each pair of states < s Suc, s Suc ′ > is built by applying the same outgoing transition t respectively on s and s ′ (s• = s ′ •, P and P ′ are compatible). See lines 15, 16 and 17.

If an incompatibility is detected, the pairs of LTSs to consider next depend on which type of incompatibility is returned. In case of a deletion of an option (see lines 6, 7, 8 and 9), the transitions to be applied are those, in both LTSs, starting from s and s ′ (i.e. s • ∩s ′ •). In case an operation has been deleted from a sequence, the algorithm goes a step forward in the LTS of P only. The pair of LTSs to consider next is then end L T S(P, s Suc) and P ′ , such as s Suc• ⊆ s ′ • (see lines 10, 12 and 13). The same process applies in case of the deletion of an acknowledgement.

Conclusion and Future Work

In this paper, we focused on conversations which cannot successfully complete because client and service interfaces do not match due to the evolution of the service interface. In our approach, the mediation is based on LTSs (Labelled Transition Systems) to model the behavioural dimension of services and to reconcile failing conversations. Three cases of incompatibilities are detected and resolved: deletion of an operation from a sequence, deletion of an acknowledgement and deletion of an option in a conditional composition. The detection and the resolution of incompatibilities is relevant only if the new version P ′ of the provided interface does not simulate the previous version P. Starting from the detected incompatibilities, the behavioural interface of mediator is generated according to both automata modelling P and P ′ .

The study reported in this paper raises several research directions. First, we focused on the situation that occurs when a service interface evolves after the substitution of an operation by another new one(adding operation has been addressed in [START_REF] Fauvet | An automaton-based approach for web service mediation[END_REF]). We also plan to study the completeness of our algorithm for the detection. An other important extension is to generalise the proposed approach, limited to two consecutive versions, and to consider a history of any number of versions.

Figure 1 .

 1 Figure 1. BestBargain's provided interface.

  (msg) response mode >c:deliveryOrder(itmList) <c:mode(m) <c:mode(m) <c:mode(m)

Figure 4 .

 4 Figure 4. Mediator's LTS (deletion of an acknowledgement)

Figure 5 .

 5 Figure 5. Mediator's LTS (deletion of an option)

This work has been partially funded by the project Web Intelligence granted by the French Rhône-Alps Region.

Web Service Choreography Interface[START_REF] Peltz | Web services orchestration and choreography[END_REF].

Business Process Execution Language[START_REF] Martens | Analyzing compatibility of bpel processes[END_REF]


Stéphane Ayache

Georges Quénot

Jérôme Gensel

Classifier Fusion for SVM-Based Multimedia Semantic Indexing

Concept indexing in multimedia libraries is very useful for users searching and browsing but it is a very challenging research problem as well. Combining several modalities, features or concepts is one of the key issues for bridging the gap between signal and semantics. In this paper, we present three fusion schemes inspired from the classical early and late fusion schemes. First, we present a kernel-based fusion scheme which takes advantage of the kernel basis of classifiers such as SVMs. Second, we integrate a new normalization process into the early fusion scheme. Third, we present a contextual late fusion scheme to merge classification scores of several concepts. We conducted experiments in the framework of the official TRECVID'06 evaluation campaign and we obtained significant improvements with the proposed fusion schemes relatively to usual fusion schemes.

Introduction

In order to retrieve multimedia documents from huge digital libraries, the needs for concept-based indexing are rapidly growing. Finding concepts in multimedia documents, such as video sequences, is one of the main objectives of the contentbased semantic indexing community. Hence, new issues are arising on the combination (fusion) of several features, modalities and/or intermediate concepts to obtain a better accuracy of concept detection. For instance, an efficient fusion scheme must enhance concept indexing in multimedia documents by merging visual and textual modalities, color and texture modalities, or global and local features. Using a generic framework, usual approaches propose either to merge data on a concatenated vector before achieving classification [START_REF] Ayache | CLIPS-LSR-NII experiments at TRECVID[END_REF][START_REF] Ayache | Using topic concepts for semantic video shots classification[END_REF], or to perform several classification and then to merge confidence scores using a higher level classifier [START_REF] Iyengar | Discriminative model fusion for semantic concept detection and annotation in video[END_REF][START_REF] Naphade | On supervision and statistical learning for semantic multimedia analysis[END_REF] by the means of a stacking technique [START_REF] Wolpert | Stacked generalization[END_REF]. Called "early" and "late" fusion [START_REF] Snoek | Early versus late fusion in semantic video analysis[END_REF], those approaches are easy to implement and provide state of the art performance. However, such fusion schemes are not always able to outperform unimodal classifiers, especially when one of the modalities provide much better accuracy than the others or when one has to handle imbalanced input features. Such situations are particularly frequent in the field of multimedia indexing due to the diversity of concepts with regard to the extracted features.

Using kernel-based classifier, for instance a Support Vector Machine, recent approaches have been proposed to take advantage of some useful kernel properties. They aim to merge features at the kernel level before performing the concept classification. Kernel-based data fusion has been successfully applied in biology to the problem of predicting the function of yeast proteins [START_REF] Lanckriet | Kernel-based data fusion and its application to protein function prediction in yeast[END_REF]. [START_REF] Lanckriet | Kernel-based data fusion and its application to protein function prediction in yeast[END_REF][START_REF] Sonnenburg | A general and efficient multiple kernel learning algorithm[END_REF] propose efficient algorithms to learn simultaneously the parameters of each unimodal kernel and the parameters of the combining function.

In this paper, we study and compare three fusion schemes in the scope of semantic video indexing. The first one takes advantage of some useful kernel properties, we present a simple algorithm which merges unimodal kernels before performing the concept classification using a SVM classifier. In such a way, features are combined at the earliest possible step using a kernel-based classifier. The second fusion scheme is derived from the early fusion scheme. We normalized each individual feature vectors so that their average norm becomes equal in order to reduce the problem of imbalanced input features. The third fusion scheme is a late-like fusion scheme; it performs fusion at the concept level taking into account the classification scores of 39 concepts from visual and textual modalities.

In Section 2, we briefly present Support Vectors Machines and some required knowledge about kernels. In section 3, we describe the proposed fusion schemes and give some background information for formally comparing them with other fusion schemes. In section 4, we describe the experiments conducted using the TRECVID'06 [START_REF] Kraaij | TRECVID 2006 -An Introduction[END_REF] corpus and metrics.

Kernel-based classifier

Kernel-based methods have provided successful tools for solving many recognition problems, such as KFD, KPCA or SVM [START_REF] Shawe-Taylor | Kernel Methods for Pattern Analysis[END_REF]. One of the reasons of this success is the use of kernels which overcome the problem of non-linearly separable data sets by mapping the initial problem into a higher dimensional space. The main idea behind kernel-based classifiers is that the similarity between examples in a data set gives much information about the patterns that may be present in these data.

Support Vector Machines

Support Vector Machines (SVM) have shown their capacities in pattern recognition and have been widely used for classification in CBIR. SVM is formalized as an optimization problem which finds the best hyperplane separating relevant and irrelevant vectors by maximizing the size of the margin between both sets. The use of a kernel allows the algorithm to find the maximum-margin hyperplane in a transformed feature space. The transformation may be non-linear and the transformed space may be of higher dimensionality than the original one. Thus, though the classifier separator is a hyperplane in the high-dimensional feature space it may be non-linear in the original input space. Furthermore, if the kernel used is a Gaussian radial basis function, the corresponding feature space is a Hilbert space of infinite dimension. Maximum margin classifiers are well regularized and the infinite dimension does not spoil the results. In a two-class case, the decision function for a test sample x has the following form:

g(x) = i α i y i K(x i , x) -b
where K(x i , x) is the value of a kernel function for the training sample x i and the test sample x, y i the class label of x i (+1 or -1), α i the learned weight of the training sample x i , and b is a learned threshold parameter. The training samples with weight α i > 0 are usually called "support vectors".

Kernel matrices

A kernel matrix is a similarity matrix where each entry represents a measure of similarity between two sample vectors, and must be positive definite (i.e. satisfy the Mercer's condition) to ensure that the optimization problem is convex. Therefore, a clever choice of the kernel (or similarity) function is essential to obtain a positive definite kernel matrix. Nevertheless, some unproved positive definite kernels such as EMD-based kernels or Log kernels have been successfully used in image recognition [START_REF] Zhang | Local features and kernels for classification of texture and object categories: A comprehensive study. Beyond Patches workshop[END_REF][START_REF] Boughorbel | Conditionally positive definite kernels for SVM based image recognition[END_REF].

Kernel matrices satisfying the Mercer's condition have interesting properties which provide modularity and derivation of kernels from other kernels. If K and K ′ are kernels, then the following are also kernels (not exhaustive):

-aK + bK ′ , for a > 0 and b ≥ 0 -K × K ′ , where × is the entrywise product The most commonly used kernel function with SVM classifier in multimedia indexing is the RBF kernel defined as follow:

K(x, y) = e -x-y 2 2σ 2
where . denotes the L 2 norm, x and y are two sample vectors, and σ the width of the Gaussian kernel, generally determined using cross-validation. RBF kernels have exhibited good generalization properties in many classification problems. However, the use of a simple Euclidian distance implies small variations on the kernel value in high dimensional feature spaces.

Fusion schemes

We present in this section three fusion schemes inspired from the usual early and late fusion schemes. Those schemes use a classifier to learn the relations between modality components at different abstraction levels. Merging all the descriptors into a single flat classifier leads to a fully integrated fusion strategy since the fusion classifier obtains all the information from all sources. The advantage of such a scheme is its capacity to learn the regularities formed by the components independently from the modalities. Also, it is easy to use as it just consists in concatenating the various data in a single vector. The main disadvantage is the use of a unique approach (classifier and/or kernel) to merge different types of information. Assuming a RBF kernel and two sample vectors x and y from sets of features 1 and 2, the classical early fusion scheme leads to the following kernel:

K(x, y) = e -x-y 2 2σ 2 = e -x 1 -y 1 2 + x 2 -y 2 2 2σ 2 = e -x 1 -y 1 2 2σ 2 e -x 2 -y 2 2 2σ 2
This formulation shows that using a SVM classifier with RBF kernels, an early fusion scheme is equivalent to multiply unimodal kernels which share the same σ parameter. The σ parameter is often fixed by cross validation, it is then optimal for the concatenated vectors, but not necessary for each modality A late Fusion is performed on top of several classifiers. It has been presented using different formalisms, such as meta-classification which aims to re-classify the classification results made by other classifiers [START_REF] Lin | Meta-classification of multimedia classifiers[END_REF]. The closest theory to illustrate a late Fusion is the Stacking Ensemble learning [START_REF] Wolpert | Stacked generalization[END_REF] which is part of the ensemble methods [START_REF] Dietterich | Ensemble methods in machine learning[END_REF]. The idea behind Ensemble learning methods (e.g. bagging, boosting, stacking) is to improve the generalization by training more than one model on each problem (e.g. train 10 SVM instead of just one) and then to combine their predictions by averaging, by voting or by other methods. Using staking, the combination is achieved by a final classifier which provides the final result. Hence, in the context of multimedia indexing, the late fusion scheme consists in performing a first classification separately on each modality and then in merging the outputs using a higher level classifier. In such a way, in contrast with the early fusion, one can use different classifier algorithms and different training sets according to the modalities. Furthermore, the late fusion scheme also allows to combine various classifiers for the same modality. However, the significant dimensional reduction induced by the stacked classifiers might be a disadvantage as the fusion classifier cannot fully benefit from the correlation among the sources of information.

Kernel Fusion

Kernel combination is a current active topic in the field of machine learning. It takes benefit of Kernel-based classifier algorithms. Advantages of merging modalities at kernel level are numerous. First, it allows to choose the kernel functions according to the modalities. For instance, histograms of colors can take advantage of specific histogram matching distances. Likewise, textual modality can be categorized using appropriate kernels such as String Kernels [START_REF] Lodhi | Text classification using string kernels[END_REF] or Word-Sequence kernels [START_REF] Cancedda | Word-sequence kernels[END_REF].

Kernel fusion also allows to model the data with more appropriate parameters. Merging modalities using an early fusion scheme leads to model the data using a single kernel function. Consequently, when using a RBF kernel, a single σ parameter is expected to "fit" properly the sample vectors relations, whereas it makes much more sense to train a combined RBF kernel using one σ per modality. Combination of unimodal kernels leads to keep as much information as possible from each modality. A combined RBF kernel has the following form:

K c (x, y) = F (K m (x m , y m ) (1≤m≤M) )
where K c (x, y) is the combined kernel value for samples x and y, (K m ) 1≤m≤M are the considered unimodal RBF kernels, F is the combining function over the M modalities, x m and y m are the sample vectors for modality m. Figure 2 shows the kernel fusion process, the unimodal kernels are merged using a fusion function in order to create the multimodal kernel. Then, learning and classification steps aim to assign a classification score to the video item.

Fig. 2. Kernel Fusion scheme

One of the main issues in the current kernel research is the learning of such combined kernels. Called Multiple Kernels Learning, it aims to learn at the same time the parameters of all the unimodal kernels and the parameters of the combining function [START_REF] Sonnenburg | A general and efficient multiple kernel learning algorithm[END_REF]. In our experiments, we used a very simple strategy to create combined kernels. The following algorithm describes the steps to simply create combined kernels:

1. Construct each unimodal kernels K m , 2. Perform cross-validation on each unimodal kernels to fix their parameters, 3. Construct the combined kernel using the F combining function, 4. Perform cross-validation to optimize the parameters of F . This algorithm assumes that the best parameters of unimodal kernels are suitable enough to allow efficient generalization of the combined kernel.

Combining individual kernels using a product operator is highly comparable to the classic early scheme where feature vectors are just concatenated. The difference is that by performing kernel fusion, each modality m is associated to its own kernel parameters (ie: σ m . Furthermore, due to the product operator, this combination might lead to sparse kernels and provide poor generalization. We used the sum operator instead of the product operator to try to avoid too sparse kernel representations. Summing unimodal kernels should be more suitable for concept detection when extracted features from a single modality are noisy and lead to incorrect detection.

We actually combine unimodal kernels by linear combination (weighted sum). Using RBF unimodal kernels, combined kernels are defined by the following formula:

K c (x, y) = m w m e - xm-ym 2 2σ 2 m
where σ m is the RBF parameter of kernel m and w m is the weight of the associated modality. The w m 's can be fixed a priori or by cross-validation. In the conducted experiments, we optimized the w m 's on the training set.

Normalized Early Fusion

The number of extracted features depends upon the modalities and the type of the features. Hence, an early fusion scheme based on simple vector concatenation is much affected by the vector which has the highest number of inputs. Such fusion should have an impact on the classification, especially with a RBF kernel which is based on Euclidian distance between each training sample.

In traditional SVM implementation, a normalization process is integrated and aims to transform each input in the same range (e.g. [0..1], [-1..1]) in order to unbias the Euclidian distance. But, for the scope of merging features, this normalization doesn't take into account the number of input from the source features. The goal of normalized early fusion scheme is to avoid the problem of imbalanced features inputs by reprocessing each feature vectors before concatenation. We normalized each entry of the concatenated vector so that the average norm of each source vector is about the same. The normalization formula becomes:

x i ′ = x i -min i (max i -min i ) × Card(x i )
where x i is an input of the feature vector x, min i and max i are respectively the minimum and maximum value of the i th input among the training samples and Card(x i ) is the number of dimensions of the source vector of x i .

Contextual-Late Fusion

Usual late fusion scheme first classify each concept using individual modalities and then merge the scores in a second layer of classifier. Here, we generalize this scheme by considering more than a single concept. Contextual information has been widely exploited in multimedia indexing [START_REF] Snoek | The semantic pathfinder for generic news video indexing[END_REF][START_REF] Naphade | On supervision and statistical learning for semantic multimedia analysis[END_REF]. Here, the second layer (stacked) classifier is able to exploit the contextual relation between the different concepts. This proposed scheme merges each unimodal classification score from a set of several concepts, in order to exploit both multimodal and conceptual contexts.

Assume that we have M modalities (e.g. visual, audio and text) and C concepts (e.g. Car, Face, Outdoor, Bus, etc). The stacked classifier merges M scores to classify the C concepts in the classic late fusion scheme. The late context fusion scheme merges M × C classification scores to classify the C concepts.

Experiments

We have evaluated and compared the presented fusion schemes in the framework of the TRECVID'06 evaluation campaign. The objective of the "high level feature extraction task" is to find video shots containing a visual appearance of 39 predefined concepts (high level features). For each concept, an ordered list of 2000 relevant shots should be returned by the competing systems. The Inferred Average Precision (IAP) [START_REF] Yilmaz | Estimating average precision with incomplete and imperfect judgments[END_REF] on the returned lists computed using the trec eval tool is used as the evaluation metric. We compare the three proposed fusion schemes with the commonly used early and late fusion schemes, as well as with unimodal approaches. We have extracted features from visual and textual modalities; we present them in the following section.

Visual and text features

The features used in this evaluation are mid-level semantic features. Visual features are based on the concatenation of several intermediate concept classification scores detected at a patch level. Those visual "local concepts" are automatically extracted in each key frame, which are split into 260 (20 × 13) overlapping patches of 32 × 32 pixels. Local descriptors (low-level features) include: color (9 color momentum in RGB space), texture (8 orientation × 3 scales Gabor filters) and motion vector (extracted by optical flow). An SVM classifier is trained in order to detect a set of 15 visual concepts (eg: vegetation, sky, skin, etc.) selected from the LSCOM ontology. Those intermediate concepts have been selected as they can be extracted at patch level. For each of the 39 concepts, we manually associated a subset of 6 intermediate visual concepts. Thus, visual feature vectors contain 1560 dimensions (6 × 260).

Text features are derived from speech transcription result. We used 100 categories of the TREC Reuters collection to classify each speech segment. The advantages of extracting such concepts from the Reuters collection are that they cover a large panel of news topics like the TRECVID collection and they are obviously human understandable. Thus, they can be used for video search tasks. Examples of such topics are: economics, disasters, sports and weather. The Reuters collection contains about 800000 text news items in the years 1996 and 1997.

We constructed a vector representation for each speech segment by applying stop-list and stemming. Also, in order to avoid noisy classification, we reduced the number of input terms. While the whole collection contains more than 250000 terms, we have experimentally found that considering the top 2500 frequently occurring terms gives the better classification results on Reuters collection. We built a prototype vector of each topic category on Reuters corpora and apply a Rocchio classification on each speech segment. Such granularity is expected to provide robustness in terms of covered concepts as each speaker turn should be related to a single topic. Our assumption is that the statistical distributions of the Reuters corpus and of TRECVID transcriptions are similar enough to obtain relevant results. Finally, the vector of text features has 100 dimensions. More explanation about those features can be found in [START_REF] Ayache | Using topic concepts for semantic video shots classification[END_REF].

Comparison of fusion schemes

The goal of the experiment is to study how imbalanced input features and large difference on the performance of unimodal classifiers are managed by the various fusion schemes. We show the results for unimodal runs and we compare all proposed fusion schemes and the usual early and late schemes. The 20 following concepts have been assessed for the TRECVID'06 evaluation campaign: The results presented in this paper are based on those 20 concepts. We do not study here each individual concepts result due to lack of space. The table 1 shows the Mean Inferred Average Precision (MIAP) obtained from the 20 assessed concepts. The two first entries refer to the unimodal runs, the two following correspond to the state of the art fusion schemes. The three fusion schemes described in this paper are shown in bold. We also show the median MIAP obtained from all of the TRECVID'06 participants.

Unimodal runs :

We observe that the two unimodal runs are very different in terms of accuracy; the visual based classification is almost 7 times higher than text based concept detection. This is probably due to the nature of the assessed concepts, which seems to be hard to detect using text modality. The difficulty to detect concepts from the text modality is also probably due to the poor quality of automatic speech transcription (and translation) in some videos of the collection. This point is actually interesting for the evaluation of the ability of the various fusion schemes to handle such heterogeneous data. The features we want to merge lead to different accuracies and are also imbalanced regarding the number of input features.

Classic Early and Late fusion schemes :

The two classical fusion schemes do not merge unimodal features similarly. While early fusion is able to outperform both unimodal runs, the late fusion scheme achieves poorer accuracy than the visual run. It might be due to the low number of dimensions handled by the stacked classifier. The early fusion scheme exploits context provided by all of the local visual features and the textual features. The gain obtained by such fusion means that those two modalities provide distinct kind of information. The merged features are, somehow, complementary.

Early based fusion schemes :

The gain obtained by the normalized fusion schemes is the most important compared to other fusion schemes. Processing the unimodal features by reequilibrating them according to the number of dimensions is determining factor in order to significantly outperform unimodal runs. In such a way, despite the different number of dimensions, both the visual and textual modalities have the same impact on concept classification. This normalization process leads to a gain of almost 17% (in MIAP) comparing to the classic early fusion scheme, which simply normalizes input in a common range, and 28% comparing to the best unimodal run.

The gain obtained by the kernel fusion scheme is less significant than the gain obtained by the normalized fusion run. However, when comparing to the classic early fusion, it seems that a combination using sum operator leads to better accuracy than multiplying kernels (which is somehow what the classic early fusion do). Furthermore, it is important to notice that the σ parameters are selected first by cross-validation on unimodal kernels and that we optimize the linear combination separately. We can expect that an integrated framework which learns simultaneously σ m and w m parameters should lead to better results.

Contextual-Late fusion scheme :

Contextual-Late fusion is directly comparable with the classical late fusion scheme. This fusion scheme take into account the context from the score of other concepts detected in the same shot. By doing so, the context from other concepts leads to a gain of 26%. Furthermore, we observe that the MIAP obtained using the late contextual fusion scheme is almost the same as the one obtained for the classical early fusion scheme. In order to go further in this study, it could be interesting to evaluate the impact of the number and/or accuracy rate of concepts used in the context.

Fig. 1 .

 1 Fig. 1. Classical Early and Late Fusion schemes

Figure 1

 1 Figure1describes the process of early and late fusion schemes. The feature extraction (FE) process extracts and creates a vector for each modality of the video item. We show the SVM process as two main steps: first, the construction of the Kernel, then the Learning or Classification (L / C) processes aims to assign a classification score to the video item.

  Sports, Weather, Office, Meeting, Desert, Mountain, Waterscape, Corporate Leader, Police / Security, Military, Animal, Computer / TV Screen, US Flag, Airplane, Car, Truck, People Marching, Explosion / Fire, Maps, Chart.

Table 1 .

 1 Mean IAP of the 20 TRECVID'06 concepts

	Visual	0.0634
	Text	0.0080
	Classical Early Fusion	0.0735
	Classical Late Fusion	0.0597
	Normalized Early Fusion	0.0884
	Kernel Fusion	0.0805
	Contextual Late Fusion	0.0753
	Median	0.0680

We notice that both of unimodal runs lead to poorer accuracy than the median of TRECVID'06 participants. This may be due to the basic and not so optimized features used in our experiments. However, the gain induced by the three fusion schemes presented in this paper lead to better accuracy than the median. We think that an optimization in the choice of descriptors for each modality could enhance the accuracy rate of both unimodal and multimodal runs.

Conclusion

We investigated three fusion schemes derived from the classical early and late fusion schemes when using SVM classifier. We have shown that all of the presented strategies perform in average better than the best unimodal run on the concept detection task of TRECVID'06. Furthermore, those fusion schemes outperform the median of TRECVID'06 participants over all of their runs. Kernel fusion schemes make it possible to take advantage of individual modalities, with a set of suitable parameters. Normalized early fusion is a good way to re-equilibrate the influence of individual modalities. Finally, the Contextual-Late fusion allows integration of context information from unimodal classification score of other concepts.

We studied influences of those fusion schemes on a set of 20 concepts, and did not analyzed individual concepts variations. As argued in [START_REF] Snoek | The semantic pathfinder for generic news video indexing[END_REF], it is possible that one strategy performs differently than other depending the nature of the concepts. It could be interesting to go further in this direction. Also, the nature of the combined feature differs depending of the fusion schemes: early fusion is based on low-or intermediate-level features, where late fusion merges unimodal classification scores of high-level features. It could be interesting to merge those two heterogeneous kind of features in an integrated fusion scheme.