Chen Wang
email: chen.wang@inria.fr

Jean-Louis Pazat
email: jean-louis.pazat@inria.fr

A Two-Phase Online Prediction Approach for Accurate and Timely Adaptation Decision

Keywords: SBA, adaptation decision, SLA, quality prediction, classification

A Service-Based Application (SBA) is built by defining a workflow that composes and coordinates different Web services available via the Internet. In the context of on-demand SBA execution, suitable services are selected and integrated at runtime to meet different non-functional requirements (such as price and execution time). In such dynamic and distributed environment, an important issue is to guarantee the end-toend Quality of Service (QoS). As a consequence, SBA provider is required to monitor each running SBA instance, analyze its runtime execution states, then identify proper adaptation plans if necessary, and finally apply the relative countermeasures. One of the main challenges is to accurately trigger the adaptation process as early as possible.

In this paper, we present a two-phase decision approach that can accurately analyze the adaptation needs for on-demand SBA execution model. Our approach is based on the online prediction techniques: an adaptation decision is determined by predicting an upcoming end-to-end QoS degradation through two-phase evaluations. Firstly, the end-to-end QoS is estimated at runtime based on monitoring techniques; if a QoS degradation is tent to happen, in the second phase, both static and adaptive strategies are introduced to assess whether it is the best timing to draw the final adaptation decision. Our approach is evaluated and validated by a series of realistic simulations.

I. INTRODUCTION

Service-Oriented Architecture (SOA) is adopted today by many enterprises as a flexible solution for building Service-Based Applications (SBA). An SBA is a dynamic and distributed software system that integrates and coordinates a set of third-party Web services (named as the constituent services) accessible over the Internet. In this scenario, the SBA's endto-end Quality of Service (QoS) is determined by the QoS of all constituent services. For example, the execution time of an SBA instance depends on how fast each constituent service responds. However, in this loosely coupled environment, the execution of SBA may fail, or fail to meet the required quality level: a constituent service may take longer time to respond due to the network congestion; moreover, infrastructure failures can cause a service completely responseless.

In this context, Service Level Agreement (SLA) plays an important role as a guarantee of non-functional quality. SLA is a mutually-agreed contract between service requester and provider, which dictates the expectations as well as obligations in regards to how a service is expected to be provided: on one hand, the expected quality level is formulated by specifying agreed target values for a collection of QoS attributes; on the other hand, some penalty measures are defined in case of failing to meet these quality expectations. SLA violations can lead to some undesirable results, such as reputation degradation and penalty payment. To prevent SLA violation, it is essential for SBA providers to guarantee the end-to-end QoS by taking adaptation countermeasures if needed.

One of the key challenges is to determine the need for adaptation in order to draw accurate adaptation decisions. All existing approaches can be classified into two categories: offline analysis [START_REF] Bodenstaff | Monitoring dependencies for slas: The mode4sla approach[END_REF], [START_REF]Analyzing impact factors on composite services[END_REF], [START_REF] Wetzstein | Monitoring and analyzing influential factors of business process performance[END_REF] and online prediction [START_REF] Leitner | Runtime prediction of service level agreement violations for composite services[END_REF], [START_REF] Leitner | Monitoring, prediction and prevention of sla violations in composite services[END_REF], [START_REF] Schmieders | Preventing performance violations of service compositions using assumption-based run-time verification[END_REF]. Offline approaches can decide when and how to improve the end-to-end quality of SBA by reasoning the causes of the past SLA violations. The adaptation aims at preventing SLA violations for the future executions rather than the ongoing ones. By contrast, online approaches predict an upcoming SLA violation, and thereby decide to trigger preventive adaptation in order to improve the QoS of the running execution instance before the SLA violation really happens.

This paper investigates an online prediction approach for on-demand executions of SBA. In this context, in response to different non-functional preferences and constraints (e.g. price and execution time), each constituent service is selected at runtime from a set of functional-equivalent candidates with different QoS [START_REF] Zeng | Qos-aware middleware for web services composition[END_REF]. As a result, any two distinct executions are instantiated with different configurations, defined as both local and global QoS expectations. Therefore, it is challenging to accurately predict potential SLA violations for all running SBA instances with irrelevant configurations.

In this paper, we introduce a two-phase online prediction approach to decide the best adaptation timing for on-demand executions of SBA. The first phase suspects an SLA violation by predicting an upcoming end-to-end QoS degradation; the prediction is based on the monitoring techniques and the estimation on the future execution. Later in the second phase, both static and adaptive strategies are introduced to predict the reliability of the suspicion in order to decide whether it is necessary to trigger preventive adaptations. Our approach is evaluated by a series of realistic simulations, the results show that our approach can determine both accurate and timely runtime adaptation decisions for on-demand SBA executions.

The rest of paper is organized as follows: Section II provides the background of our problem. In Section III, some of the main existing decision approaches are discussed and our approach is introduced. Later, Section IV and Section V present respectively the two phases of our approach in depth. In Section VI, the performance of our approach is studied based on a set of realistic simulations. Finally, the conclusion and the future work are addressed in Section VII.

II. BACKGROUND

A. Illustrative Example

In this paper, we use a travel agency as an illustrative example to present our approach. As shown in Figure 1, an SBA is implemented to propose traveling plans for its clients. A request composes a set of parameters such as identification information (e.g. email address and password), dates of traveling and the destination. In order to respond to client's requests, a workflow is defined to coordinate a collection of interrelated tasks: firstly, the client's identity is verified by task t 1 and the inputs from the requester are validated and analyzed by task t 2 . Then, the execution is diverged into two parallel execution branches: task t 3 and task t 4 look for the round-trip flight tickets from all airline companies. Concurrently, task t 5 searches available hotels in the destination city, and the weather information is provided by task t 6 . Both branches converge before task t 7 , which generates all propositions of traveling plans based on the client's criterion, such as total budget. Finally, task t 8 sorts all the propositions according to the client's preferences and returns the results.

The SBA requires service collaboration across enterprise boundaries: each task can be bound to either an internal service (e.g. task t 1 , t 2 , t 7 , t 8 ) or an external one provided by the thirdparty enterprises (e.g. task t 3 , t 4 , t 5 , t 6 ). Constituent services are on demand selected at runtime: as an example, for premium clients, fast services are selected and bound in order to return the propositions of traveling plans as quickly as possible; on the other side, for normal clients, cheaper and slower services are used and the execution may take respectively longer time.

B. Global and Local SLA

As introduced, the SLA defines both aspects of expected QoS and penalty measures. First of all, the definition and execution of penalty is beyond the interests of this paper. Furthermore, we assume that a set of QoS attributes can be considered as deterministic: their values cannot be changed at runtime once negotiated (e.g. price). Accordingly, the SLA violation can be only caused by non-deterministic QoS attributes, whose real values are affected by the distributed and The SBA plays the roles of service provider as well as consumer. For both roles, it negotiates an SLA with each of its counterparts, as shown in Figure 1: the SLA between the SBA and each constituent service is defined as local SLA, and the one negotiated with the SBA requester is defined as global SLA. A local SLA reflects the expected time consumption for executing the corresponding task t i , denoted as lsla(t i )=<q t (t i )>, whereas the global SLA dictates the expected end-to-end execution time of SBA, denoted as gsla=<gc t >. Obviously, the definition of the global SLA depends on the local ones. As an example, Table I lists the expected execution time defined in both global and local SLAs for an instance of the illustrative example shown in Figure 1.

C. Prevention of Global SLA Violation

In order to enhance the reputation and to avoid penalties, it is mandatory for service providers to prevent global SLA violation for every running execution instance. The general solution for runtime prevention of SLA violation is to implement the MAPE control-feedback loop (Monitor-Analyze-Plan-Execute) [START_REF] Kephart | The vision of autonomic computing[END_REF], as depicted in Figure 2: 1) Monitor: firstly, each execution instance of SBA is monitored by intercepting communication messages in order to collect a series of events; 2) Analyze: these events are used to evaluate the quality state of a running execution instance and to analyze the need for adaptation; 3) Plan: once an adaptation decision is determined, a suitable adaptation plan (e.g. a list of actions to improve the end-to-end quality) is identified; 4) Execute: finally the relative countermeasures are applied to the ongoing SBA instance.

D. Problem Definition

One of the key challenges to efficiently implement the MAPE loop is to accurately draw adaptation decision (Analyze step). Our research work studies an online prediction approach to analyze the need for adaptation by forecasting whether the SLA is tent to be violated in the future. An eligible online prediction approach has to meet the following requirements (challenges): 1) Effectiveness. An effective approach can successfully predict as many SLA violations as possible. 2) Precision. An effective approach might not be precise due to many false predictions, which will lead to unnecessary adaptations and thereby bring additional cost and complexity: on one hand, runtime adaptation is costly since more resources are required to identify and to execute an adaptation plan; on the other hand, the time consumption of a runtime adaptation process may potentially delay the execution of SBA. 3) Timing. It is desirable to decide as early as possible: late decisions are usually precise but less useful, since the best adaptation opportunities might be missed, and the benefit of preventive adaptation is diminished. 4) Efficiency. The decision algorithm must be efficient (fast decision) in order to meet the critical time constraint at runtime.

III. RELATED WORK AND MOTIVATION

A. Related Work

The existing online prediction approaches in the literature can forecast SLA violations caused by either functional failures or non-functional deviations. In the former case, the recovery from functional failures requires extra execution time and additional cost, which can lead to global SLA violations. Some research work use online testing techniques to test all constituent services in parallel to the execution of an SBA instance. By this means, an upcoming functional failure can be forecasted before its real occurrence. [START_REF] Hielscher | A framework for proactive self-adaptation of service-based applications based on online testing[END_REF] presents the PROSA framework, which defines key activities to initiate online testing either on the binding level or on the service composition level, and thereby proactively triggers the adaptation process. [START_REF] Dranidis | Enabling proactive adaptation through just-in-time testing of conversational services[END_REF] investigates how to guarantee functional correctness of conversational services. The authors propose a novel approach to enables proactive adaptations through just-in-time testing. Online testing approach is helpful to detect potential functional failures but it can hardly be aware of the deviation of the endto-end QoS. Furthermore, it requires each consistent service to provide a test mode (e.g. free interfaces for testing).

Our research work belongs to the latter case, which predicts SLA violation by asserting non-functional deviations that might happen at the end of the execution (e.g. delay). Some research work use runtime verification techniques to determine the necessity of adaptation and to trigger preventive adaptation. In [START_REF] Schmieders | Preventing performance violations of service compositions using assumption-based run-time verification[END_REF], the authors introduce SPADE approach: after the execution of each task, if the local SLA is violated, SPADE uses both monitored data and the assumptions to verify whether the global SLA can be still satisfied. If it reveals that the global SLA is tent to be violated, the adaptation is accordingly triggered. However, early verifications are largely based on the assumptions rather than monitored data, thus they are inaccurate and can lead to many unnecessary adaptations.

Other research work use machine learning techniques in order to provide precise predictions and avoid unnecessary adaptations. In [START_REF] Leitner | Runtime prediction of service level agreement violations for composite services[END_REF], a set of concrete points are defined in the workflow as checkpoints. Each checkpoint is associated with a predictor, which is implemented by a regression classifier. When the execution of the workflow reaches to a checkpoint, the corresponding predictor is activated and uses the knowledge learned from past executions to predict whether the global SLA will be violated. This work is extended in [START_REF] Leitner | Monitoring, prediction and prevention of sla violations in composite services[END_REF] by proposing the PREvent framework, which integrates eventbased monitoring, runtime prediction of SLA violations and Fig. 3. 2-Phase Online Prediction Approach automated runtime adaptations. Such checkpoint-based prediction approach has some limitations: firstly, some misbehavior (e.g. huge delay) between two checkpoints cannot be handled in time. In the meantime, the best adaptation opportunity might be lost. Furthermore, poorly selected checkpoint(s) may lead to undesirable results, such as unnecessary adaptations. But the selection of optimal checkpoints is complicated and challenging, especially for complex workflows.

B. Our Approach: Two-Phase Decision Approach

In order to provide both accurate and timely predictions of SLA violation, we propose a two-phase online prediction approach. As shown in Figure 3, an adaptation decision is determined through the following steps: 1) listen to the events emitted from the Monitor component (refer to Figure 2), once the execution of a task t i is completed, go to step 2. 2) If the execution of workflow has not yet been finished, go to step 3; otherwise, the algorithm is terminated with the state silence, which means that during the entire execution, no SLA violation has been predicted (no adaptation decision has been made). 3) Estimate the values of QoS attributes defined in the global SLA (e.g. execution time) based on the monitored data and the estimation of the execution in the future. 4) Compare the estimated value with the target value defined in the global SLA, if a violation is tent to happen, a suspicion of SLA violation is reported and go to step 5; otherwise, return to step 1. 5) Evaluate the trustworthy level of the suspicion in order to decide whether to accept or to neglect this suspicion. 6) If the suspicion is accepted, our approach terminates with the state warning by predicting an upcoming SLA violation and drawing the adaptation decision; otherwise, the suspicion is neglected and go back to step 1.

The core of our approach is two-phase evaluations: the estimation phase (step 3, 4) evaluates whether the global SLA is tent to be violated and the decision phase (step 5, 6) evaluates how likely the suspected violation will really happen. An additional evaluation can bring more precise adaptation decisions since all inaccurate early suspicions can be neglected in the decision phase. Additionally, without the limitation of the predefined checkpoints, it is possible to react to any misbehavior in time. In the following, Section IV and Section V will use the execution time as an example to highlight respectively these two phases.

IV. ESTIMATION PHASE

To estimate the end-to-end execution time of a running SBA instance, two kinds of information are required: 1) the measured execution time of the tasks whose executions have already been completed; 2) the probable time consumption of uncompleted tasks, including the tasks that are being executed as well as the ones whose executions have not been started yet. Based on the monitoring techniques [START_REF] Leitner | Monitoring, prediction and prevention of sla violations in composite services[END_REF], we assume that the former information is known at the time of estimation, which is accessible from an internal database. In this section, we firstly highlight how to estimate local execution time for uncompleted tasks, and then we introduce an efficient tool for rapid estimation of the global execution time.

A. Estimation of Local Execution Time

The local execution time of a task t i depends on how fast the corresponding constituent service S B (t i ) responds. As a result, some research work [START_REF] Leitner | Monitoring, prediction and prevention of sla violations in composite services[END_REF] propose to use arithmetic mean value of the last n measured response time of S B (t i ) as the estimation of the local execution time for t i , denoted as q E (t i ). However, the performance of this method is affected by the outliers. Suppose that the last 10 measures of response time are: 940ms, 1,020ms, 1,050ms, 1,000ms, 970ms, 1,100ms, 1,020ms, 24,060ms, 960ms, 980ms. The arithmetic mean is 3,310ms, which cannot properly reflect the probable response time of S B (t i ). In addition, this method cannot be used when there is no (sufficient) historical information. For example, in the context of on-demand SBA execution, a task may bind to a service that has never been invoked before.

We provide both dynamic and static methods for local estimation. To estimate the response time of S B (t i ), SBA provider is required to record the response time of all constituent services that have been invoked before. Dynamic methods look into the past records for the information about S B (t i ). If enough historical information is found, the approaches presented in [START_REF] Hodge | A survey of outlier detection methodologies[END_REF] can be used to firstly detect and remove the outliers before computing the arithmetic mean. A more efficient alternative solution is to directly use the median value of the last n measures. In the previous example, the median value is 1 000ms: five measures are less or equal to it and five are greater, including the outlier. In case of no (sufficient) historical information about S B (t i ), the static method is automatically activated, which uses the target value defined in the local SLA as the estimation (q E (t i ) = q t (t i )). In this case, it is straightforward to trust the service provider.

B. Estimation of Global Execution Time

Having the runtime knowledge on the local execution time of each task t i , defined as q L (t i ), the global execution time of a running SBA instance can be estimated by using aggregation functions [START_REF] Jaeger | Qos aggregation for web service composition using workflow patterns[END_REF] (q L (t i ) equals to the measured execution time for completed tasks and equals to q E (t i ) for uncompleted ones). However, runtime aggregation is costly and time-consuming, especially for complex and unstructured workflows. We introduce the Program Evaluation and Review Technique (PERT) [START_REF] Cook | Program Evaluation and Review Technique-Applications in Education[END_REF] as an efficient tool for rapid runtime estimation of global execution time. PERT was originally developed for planning, monitoring and managing the progress of complex projects. In our approach, PERT is used to manage the workflow execution and to facilitate decision making. It maintains some additional information for each task t i : • The Latest Finish Time (LFT): T L (t i ). This is the latest time by which the task t i can finish without causing the delay of the ongoing execution instance.

T L (t i ) = min{T L (t k ) -q L (t k )|t k is the direct successor of t i }.
For the last task (end) t n , T E (t n ) = gc t , which is the target value defined in the global SLA.

• The slack time: S(t i ). This is the maximum delay for executing the task

t i . S(t i ) = T L (t i ) -T E (t i ) -q L (t i ).
• The critical path CP . A path is a sequential execution of tasks from the beginning to the end of a workflow. CP is a path with all tasks having the least slack time. The PERT chart is initially constructed based on both global and local SLAs (q L (t i )=q t (t i )), all the information is then presented on an X-Y chart. As an example, for the execution instance of the illustrative example with all local and global SLAs given in Table I, the corresponding PERT chart is computed and depicted in Figure 4. The X-axis represents the accumulated execution time, while the Y-axis is the list of tasks that are composed in the workflow. Each task t i is represented by a single horizontal bar which starts from T E (t i ) and ends with T L (t i ). The length of the bar corresponds to the maximum acceptable duration for executing a task, under the assumption that all the other tasks complete on schedule. A bar is composed of two parts, the solid part represents q L (t i ) and the hollow part reflects S(t i ). Finally, the tasks on the critical path is marked by a star (⋆).

In order to reflect the most up-to-date runtime execution state, the PERT chart can be updated when new local knowledge q L (t i ) is available (e.g. newly measured execution time of a just-completed task). Please note that the PERT chart only needs to be partially reconstructed by recomputing some of the above-mentioned information (e.g. the completed tasks do not need to be recomputed), which can be seen as the adjustments of some bars along the X-axis. The update can be triggered either periodically, or based on checkpoints or events (e.g. after each "invoke" event). Anyhow, the reconstruction of chart can be performed in parallel with the service invocations, thus it will not bring extra time consumption.

By using the PERT chart, the estimation of global execution time is simplified. When a task t i is finished, the real accumulated execution time at this moment can be measured, denoted as AT (t i ). If AT (t i ) > T L (t i ), the global execution time is estimated to be violated by AT (t i ) -T L (t i ), and a global SLA violation is accordingly suspected. A suspicion of violation is represented by a pair, denoted as S=<T D , t i >, which means that after executing task t i , a delay of T D is estimated (T D =AT (t i )-T L (t i )). In this way, instead of running complex aggregation function, the estimation of global SLA requires only one comparison operation.

V. DECISION PHASE

In this section, both static and adaptive decision strategies are introduced to evaluate the trustworthy level of a suspicion in order to identify the need for the preventive adaptation.

A. Weight of a Suspicion

In the context of on-demand SBA execution, two suspicions with the same attributes (T D and t i ) reported by two distinct SBA instances may have different significances. With different configurations, "after task t i " refers to the different degrees on the completion of workflow execution. Using our illustrative example, S 1 and S 2 are both reported after task t 7 with the same estimated delay of 350ms; but for S 1 , 90% of the global expected execution time (gc t ) is consumed after executing t 7 , whereas only 60% for S 2 . Obviously, S 1 is stronger than S 2 since a delay is more likely to happen in the end.

In order to model the significance of a suspicion S for on-demand executions of SBA, we introduce the concept of weight, denoted as τ s . τ s is defined by a decimal between 0 and 1: greater value indicates a stronger suspicion. An earlier suspicion is often less accurate, because it is based more on the estimated values than on the measured values; accordingly it has a lower weight. Along with the execution, since more and more local estimations are updated with measured values, a later suspicion becomes more accurate and has a respectively higher weight. In our approach, the weight of a suspicion S is expressed by the percentage of execution that is supposed to be completed at the moment, defined as τ s (S) = T L (t i )/gc t , remember that T L (t i ) denotes the LFT of task t i and gc t is the expected global execution time defined in the global SLA.

We provide three static strategies and an adaptive strategy to evaluate a suspicion S using the estimated delay T D and its weight τ s (S). Static strategies compute the maximum allowed delay max d with respect to τ s (S) using predefined evaluation functions. If T D is greater than max d , the suspicion is considered as strong enough and an adaptation decision is determined; otherwise, it is neglected. By contrast, adaptive strategy uses machine learning techniques to build a classifier that learns the knowledge from the past suspicions in order to predict whether or not the current suspicion will really happen.

B. Static Decision Strategies 1) Qualitative strategy:

The idea is to neglect all the early suspicions since they are considered as inaccurate. By specifying a weight threshold ρ w , only the suspicions with τ s > ρ w will be accepted to report a warning of violation. Thus, its evaluation function is a step function, as depicted by f 1 in Figure 5: max d equals to +∞ if τ s is smaller than ρ w and equals to 0 otherwise. Figure 5 also gives three sample suspicions with different weights and estimated delays: using qualitative strategy, S 1 will be neglected whereas both S 2 and S 3 will be accepted.

2) Quantitative strategy: The main limitation of qualitative strategy is that the adaptation cannot be triggered until a certain percentage of workflow has been executed, despite the fact that a huge delay may arise at the beginning of the execution (e.g. S 1 ). In order to react to such problem as early as possible, quantitative strategy evaluates a suspicion with the consideration of both τ s (S) and T D . In this case, the SBA provider specifies an evaluation function based on his/her own experience, such as f 2 defined in Figure 5. Using f 2 , S 1 and S 2 will lead to adaptation decisions while S 3 will not.

3) Hybrid strategy: The quantitative strategy may not detect slight delays when the execution is approaching to the end, such as S 3 . In this case, a slight delay might finally lead to a great penalty due to SLA violation. The hybrid strategy is more critical: by specifying ρ w , if τ s (S) is greater than ρ w , the qualitative strategy is applied (S will be absolutely accepted); otherwise, the quantitative strategy is applied. Thus, its evaluation function follows f 2 when τ s < ρ w and follows f 1 (max d = 0) otherwise. By using hybrid strategy, all three suspicions in Figure 5 will be accepted.

C. Adaptive Decision Strategy

Static decision strategies are useful when insufficient historical information is available. However, from the long-run perspective, it has the following limitations: first of all, it is a challenging task for the SBA provider to manually identify a suitable evaluation function based on his/her past experiences: sometimes such experience is hard to be expressed using a regular function. Additionally, once defined, the evaluation function cannot be self-adjusted (can be manually modified by SBA provider) in order to improve the quality of decision.

The adaptive strategy models adaptation decision as a classification problem. The correctness of a suspicion (C S ) can be evaluated when the relative execution terminates (suppose no adaptation action is really executed): if the global SLA is really violated, the suspicion is proved as correct (C S =true); otherwise, it is marked as a false one (C S =false). As a result, at the end of each execution, a set of suspicion records can be created based on all reported suspicions and their correctness. A suspicion record is described by two numeric attributes (estimated delay and its corresponding weight) and a categorical attribute defined as class (can be true or false), 6. The dataset is often depicted as a table, with each row representing a suspicion record. Based on machine learning technique [START_REF] Bramer | Principles of Data Mining[END_REF], a classifier is built to progressively learn the knowledge from past experiences. The knowledge is a specific algorithm that determines the class of a new suspicion based on its attributes. Once a suspicion is reported and it is classified as correct (C S =true), the adaptation decision is accordingly made; otherwise, this suspicion is neglected.

Since the space is limited, we will not provide the details about data cleaning as well as how to learn and represent the knowledge. Interested readers can refer to [START_REF] Bramer | Principles of Data Mining[END_REF], [START_REF] Hall | The weka data mining software: an update[END_REF]. The classifier is required to be retrained to improve the prediction quality. The retraining can be carried out in one of the following ways: 1) after every N predictions, 2) periodically (after a fixed duration), 3) on-demand by the SBA provider.

VI. EXPERIMENTAL RESULTS

A. Experiment Setup

Our approach is evaluated and validated by a set of experiments built on a realistic simulation model, since real implementation is costly, which requires to implement the entire MAPE control loop as well as dealing with some other challenging problems of on-demand SBA execution, such as service selection, or interface mismatches.

1) Realistic simulation model: For each constituent service, we are only interested in how it responds rather than what it responds. Therefore, instead of invoking real-world Web services, each task is bound to a virtual service, which only simulates the non-functional aspects of a service invocation (e.g. response time). In our experiments, 100 virtual services are created based on the realistic QoS datasets provided by [START_REF] Zheng | Distributed qos evaluation for realworld web services[END_REF], which record the non-functional performances (such as response time, throughput, etc.) of a large number of real-world service invocations. A virtual service collects all the invocation records from the same requester to the same Web service. By using these records, each virtual service defines two methods: 1) simulate() randomly selects one of the past records to simulate the non-functional aspects of an invocation; 2) getExpectedRT() determines the expected response time by specifying a percentage threshold φ, which indicates the percentage of past invocations which can respond within the expected value. In our experiments, in order to create a scenario with high violation rate, φ is set to 0.6 (40% possibility of local SLA violations for each virtual service).

2) Simulate an execution of SBA: An execution of SBA is simulated through three stages: in the first stage, an SBA instance is created by binding each task t i to a randomly selected virtual service, denoted as vs(t i ), and the relative local SLA is generated by completing a template with the expected response time of vs(t i ). Then, the global SLA is generated by computing the expected end-to-end execution time using aggregation functions [START_REF] Jaeger | Qos aggregation for web service composition using workflow patterns[END_REF]. Finally, based on both local and global SLAs, a PERT chart is constructed.

The second stage simulates the execution of this SBA instance. First of all, each selected virtual service vs(t i ) simulates the response time as the real execution time of task t i . Then, by running aggregation functions along all execution paths, the real accumulated execution time by which the execution of task t i is completed can be computed, denoted as AT (t i ). Next, a collection of "receive" events are created with the corresponding timestamp, denoted as Recv= <t i , AT (t i )>.

Finally in the third stage, these "receive" events are sorted by the timestamp and then sequentially processed: firstly, if AT (t i ) > T L (t i ), a set of predictors are activated to make adaptation decision based on different strategies. A predictor is a Java object that implements a specific decision strategy. After the prediction, the PERT chart is updated and the static method is used for estimations of local execution time.

B. Evaluation Metrics

Contingency table metrics [START_REF] Salfner | A survey of online failure prediction methods[END_REF] are used to investigate how accurately a decision approach works. An adaptation decision approach can terminate with two possible states: warning or silence (refer to Figure 3). Using the contingency table, as shown in Table II, a warning is defined as a positive decision (P), which asserts that the global SLA will be violated in the near future; by contrast, a silence is formally named as a negative decision (N) which decides that no adaptation was needed for the entire duration of the execution. In order to evaluate the quality of decision, no adaptation plan is really identified and executed. For a positive decision, if a violation is really occurred in the end, it is proved to be a true positive (TP); otherwise, it is a false positive (FP). Similarly, a negative decision can be either a true negative (TN) if no violation really happens at the end of execution, or else a false negative (FN). Based on the contingency table, different evaluation metrics are defined as follows:

• Accuracy (a). It is the ratio of all correct decisions to the number of all decisions: a = T P +T N T P +T N +F P +F N = T P +T N T .

• Precision (p). It is the ratio of all correct warnings to the number of all warnings, p = T P T P +F P . • Effectiveness (e). It is the ratio of all correct silences to the number of all silences: e = T N T N +F N .

C. Experiment 1: Evaluation of the Best Decision Time

In this experiment, the best decision time is evaluated by disabling the decision phase, thereby the adaptation decision is determined once an SLA violation is suspected. The evaluation is based on the illustrative example defined in Figure 1: after each task t i (1 ≤ i ≤ 8), a checkpoint C i is defined as a possible decision time point. 8 predictors are created based on a single checkpoint: predictor P i (1 ≤ i ≤ 8) can decide only when the execution of workflow reaches to checkpoint C i . Please note that the decisions of P 8 must be definitely accurate because it decides after the completion of workflow execution. In addition, two predictors are defined based on multiple checkpoints: P 9 is activated at both C 2 and C 7 while P 10 can decide at either C 4 or C 6 . We run 1000 simulations, Table III summarizes the performance of all predictors.

1) Decisions based on a single checkpoint: The results reveal that, by using a single checkpoint, it is hard to draw both early and accurate adaptation decision. First of all, as we discussed in this paper, early decisions are less accurate: due to the large number of FP and FN decisions, P 1 and P 2 result in lower accuracy, precision as well as effectiveness. By contrast, as the most part of workflow has been executed, P 7 performs largely better but its decisions come too late to carry out effective preventive adaptations. Furthermore, the other four predictors are based on the checkpoints located on two parallel execution branches, and the critical path can be only determined at runtime due to on-demand service selection. If a task (checkpoint) is not on the critical path, it has thus a larger slack time and a longer delay can be tolerated. Therefore, from its local perspective, the execution is considered as running well and no warning will be reported. That explains why P 3 , P 4 , P 5 and P 6 have less FP decisions but a tremendous number of FN decisions, which lead to a poor performance on average.

2) Decisions based on multiple checkpoints: An additional checkpoint brings another chance to report (either true or false) warnings of SLA violations. Take P 9 for example, if a violation is failed to be predicted at C 2 , it still has chance to be alerted at C 7 ; thus, compared to P 2 , the TP number is greatly improved; meanwhile, only several FP decisions are additionally produced. On the other side, compared to P 7 , although P 9 does get some quality degradation, but the decision time is improved by 2 execution steps. This is the same for P 10 , compared to P 4 and P 6 , both accuracy and effectiveness are significantly improved. However, as an extreme case, we assume that a predictor P x can draw adaptation decisions at all possible checkpoints. It is similar to runtime verification techniques introduced in Section III: whenever a deviation is estimated, the adaptation decision is made. In this case, any a predictor from P 1 to P 8 decides, P x will also decide. Thus, P x cannot have less FP numbers than P 1 . Such a high FP number will result in a poor precision. From the above discussion, we can see that it is challenging to determine the best time for drawing both early and accurate adaptations decisions.

D. Experiment 2: Evaluation of Our Approaches

In the second experiment, both static and adaptive decision strategies presented in this paper are evaluated. The qualitative predictor P ql implements qualitative strategy by specifying the weight threshold ρ w to 0.65. The quantitative predictor P qt defines the evaluation function as max d = (1 -τ s ) 3 2 * gc t * p, where τ s is the weight of a suspicion, gc t is the expected execution time of SBA defined in the global SLA, and p is set to 5%. This function can tolerate greater deviation at the beginning of the execution (as f 2 in Figure 5). Additionally, the hybrid predictor P hb invokes P qt when the weight of suspicion is less than 0.65, and uses P ql otherwise. Finally, the adaptive predictor P ad implements a set of classifiers based on WEKA machine learning toolkit [START_REF] Hall | The weka data mining software: an update[END_REF]. All the decisions reported in the first experiment are used to generate a set of suspicion records, which are organized in the dataset file.

During the training phase (Step 1 in Figure 6), all classifiers are used to learn the knowledge from the dataset, and their performances are evaluated by cross-validation. When a new suspicion is reported, the classifier with the best predictive accuracy is then used for the prediction (Step 2 in Figure 6). Each classifier requires at least 300 historical suspicion records (min training size=300); if the dataset contains more than 1000 records, it selects the 1000 most recent items (max training size=1000). The retraining is carried out for every 200 predictions.

Another 1000 executions are simulated to evaluate our approach. As a comparison, the three predictors with the best decision quality in the first experiment, namely P 7 , P 9 and P 10 , are also used. The performance of different predictors is shown in Table IV. First of all, we can see that the quality of all static and adaptive decision strategies can be considered on the same level. Please note that: 1) P ql decides later than the other three strategies, since it can decide only when a certain part of workflow has been executed. 2) As introduced, P hb is more critical than P ql and P qt . Thus it accepts more suspicions, which can result in a lower precision whereas a higher effectiveness. 3) Static strategies can successfully prevent almost all of SLA violations (luckily, in this experiment, no SLA violation has been missed). Meanwhile, adaptive strategy has a low rate of false silence (5%). Secondly, compared to checkpoint-based predictors (singlestep predictions), the results show that our approach can make more accurate adaptation decisions as early as possible. First of all, the decision quality of our approach can be considered on the same level as P 7 . But our approach improves the decision time by more than one execution step. Secondly, P 9 decides a little earlier than our approaches (less than one execution step), but our approach has a remarkable improvement in accuracy (over 10%), effectiveness (5% higher on average) and precision (15% better). Finally, compare to P 10 , our approaches have almost the same decision time but better accuracy (≈10%) as well as higher effectiveness (≈15%).

E. Experiment 3: Evaluations over Different Workflows

In order to evaluate the performance of our approach over different workflows, we create three fictitious workflows without real meanings: 1) a linear workflow with 9 tasks (a single execution path); 2) a medium workflow with 17 tasks and 6 execution paths; 3) a complex workflow with 30 tasks and 9 execution paths. For each workflow, we firstly simulate 300 executions to initiate the dataset of suspicion records, and then 1000 simulations are carried out by using P ql , P qt , P hb and P ad . Table V and Table VI summarize respectively the accuracy and the precision of different predictors. From the experimental results, we have the following observations: 1) our approach is not limited to a specific workflow and it can perform well for different kinds of workflows; 2) adaptive strategy makes decisions based on the knowledge learned from the past executions, thus its performance can always be maintained at a high level when used for different workflows; 3) the performances of static strategies depend on the predefined evaluation function: as the second experiment demonstrates, a suitable evaluation function can perform as well as adaptive strategy; otherwise, it may get a little performance degradation but it is still good (compared to other approaches).

VII. CONCLUSION AND FUTURE WORK

This paper discusses an important problem for preventing SLA violation: how to make correct runtime decision to accurately trigger preventive adaptation for on-demand SBA execution. In this paper, we have presented an online prediction approach which draws adaptation decisions through twophase evaluations. Based on a series of realistic simulations, our approach exhibits the following desirable properties: 1) it is able to draw accurate adaptation decisions for different workflows: almost all violations can be successfully predicted and alerted; meanwhile, only few unnecessary adaptations will be triggered; 2) with the same accuracy level, our approach can decide as early as possible; 3) by using static strategies, our approach can still make accurate and timely adaptation decision when no (sufficient) historical information is available.

Our future work will concentrate on providing more flexible runtime management of SBA. First of all, the PERT technique can be used for runtime optimization of SBA instances. For example, by using PERT charts, it is easy to detect large slack time for a task and thus it can rebind to a slower but cheaper service in order to reduce the cost. Furthermore, we are integrating branch prediction techniques into PERT charts, which can help to further reduce unnecessary adaptations. The re-construction of PERT chart will take into account the paths that are most likely to be executed. Finally, having positive results based on the realistic simulations, we are going to implement and integrate our approach into an existing business process management system and evaluate its performance.

Fig. 1 .

 1 Fig. 1. Illustrative Example: Travel Agency

Fig. 2 .

 2 Fig. 2. MAPE Control-Feedback Loop dynamic runtime environment, such as response time. For the reason of simplicity, an SLA is therefore modeled as a set of target values for only non-deterministic QoS attributes. As a proof on concept, our discussion will only focus on the response time in the remainder of this paper.The SBA plays the roles of service provider as well as consumer. For both roles, it negotiates an SLA with each of its counterparts, as shown in Figure1: the SLA between the SBA and each constituent service is defined as local SLA, and the one negotiated with the SBA requester is defined as global SLA. A local SLA reflects the expected time consumption for executing the corresponding task t i , denoted as lsla(t i )=<q t (t i )>, whereas the global SLA dictates the expected end-to-end execution time of SBA, denoted as gsla=<gc t >. Obviously, the definition of the global SLA depends on the local ones. As an example, Table I lists the expected execution time defined in both global and local SLAs for an instance of the illustrative example shown in Figure1.

Fig. 5 .

 5 Fig. 5. Evaluation Functions of Static Decision Strategies

Fig. 6 .

 6 Fig. 6. Adaptive Decision Strategy denoted as S R =<T D , τ s (S), C S >. All historical suspicion records are organized into a training dataset, as illustrated in Figure6. The dataset is often depicted as a table, with each row representing a suspicion record. Based on machine learning technique[START_REF] Bramer | Principles of Data Mining[END_REF], a classifier is built to progressively learn the knowledge from past experiences. The knowledge is a specific algorithm that determines the class of a new suspicion based on its attributes. Once a suspicion is reported and it is classified as correct (C S =true), the adaptation decision is accordingly made; otherwise, this suspicion is neglected.Since the space is limited, we will not provide the details about data cleaning as well as how to learn and represent the knowledge. Interested readers can refer to[START_REF] Bramer | Principles of Data Mining[END_REF],[START_REF] Hall | The weka data mining software: an update[END_REF]. The classifier is required to be retrained to improve the prediction quality. The retraining can be carried out in one of the following ways: 1) after every N predictions, 2) periodically (after a fixed duration), 3) on-demand by the SBA provider.

  This is the expected time by which the execution of task t i can start. T E (t i ) = max{T E (t j )+q L (t j )|t j is the direct precedent of t i }, For the first task (start) t s , T E (t s ) = 0.

	task	Y
	⋆t1 0 600 800
	⋆t2	600	1400 1600
	⋆t3		1400		2900 3100
	⋆t4				2900	4400 4600
	t5		1400		3200	3600
	t6				3200	4200	4600
	⋆t7					4400	5600 5800
	⋆t8						5600	6600 6800	time(ms)
								X
			1000	2000	3000	4000	5000	6000	7000
					Fig. 4. PERT Chart

• The Expected Start Time (EST): T E (t i ).

TABLE II CONTINGENCYTABLE Real :

 IIReal

		violated	Real: not violated	Sum
	Prediction: violated	True Positive (TP)	False Positive (FP)	Positive
	(warning)	(correct warning)	(false warning)	(P)
	Prediction: not violated	False Negative (FN)	True Negative (TN)	Negative
	(silence)	(false silence)	(correct silence)	(N)
	Sum	Violations (V)	Compliance (C)	Total (T)

•

  Decision Time (dt). Only positive decisions have dt. It is measured by the maximum number of tasks that have already been completed on different execution paths.

ACKNOWLEDGMENT

The research leading to these results has received funding from the European Communitys Seventh Framework Programme [FP7/2007-2013] under grant agreement 215483 (S-CUBE).


Stéphane Gaboreau

Francis Claret

Catherine Crouzet

Eric Giffaut

Christophe Tournassat

Caesium

Caesium uptake by Callovian-Oxfordian clayrock under alkaline perturbation

teaching and research institutions in France or abroad, or from public or private research centers.

Caesium uptake by Callovian-Oxfordian clayrock under alkaline perturbation

S. Gaboreau 1 , F. Claret 1 , C. Crouzet 1 , E. Giffaut 2 , Ch. Tournassat 1

1. BRGM (French Geological Survey), 3, Avenue Claude Guillemin, 45060 Orleans Cedex, France 2. ANDRA, 1-7 Rue Jean Monnet, 92298 Châtenay-Malabry, France

Caesium is one of the main radionuclides present in radioactive waste. 135 Cs has a very long half-life (~2.3 10 6 yr) and Cs is, therefore, one of the main safety relevant elements (Kissane, 2009). For these reasons, Cs is one of the most widely studied radionuclides in environmental sciences. Numerous works have been devoted to developing sorption models enabling the prediction of Cs sorption in clayrich media. These models consider the presence of different exchange sites at clay surfaces having various relative affinities for Cs and other cations present in solution (Bolt et al., 1963;Jackson, 1968;Sposito, 1980;Brouwer et al., 1983;Bradbury and Baeyens, 2000;Steefel et al., 2003;Wang et al., 2011). Illite has been identified as the main mineral responsible for the uptake of Cs due to the high affinity of its surfaces for Cs ions. Caesium sorption on illite surfaces can be successfully modelled by considering up to three different exchange sites denoted as frayed edge sites (FES), planar sites on the basal surfaces and type II sites whose morphological or structural origin is not well defined (Bradbury and Baeyens, 2000). Of these sites, frayed edge sites are responsible for the very high Cs affinity for illite surfaces at low Cs concentrations. Concepts of a radioactive waste repository in deep clay formations take advantage of this Cs retention by the geological barrier. Nevertheless, although many studies have focused on the prediction of Cs sorption and mobility in this context (Poinssot et al., 1999;Bradbury and Baeyens, 2000;Van Loon et al., 2009), few have been dedicated to the study of Cs retention by the clay-rich media under perturbations due to the presence of the repository structure, the engineered barriers and the waste containers. According to the numerous data produced on alkaline perturbation (Gaucher and Blanc, 2006;Fernandez et al., 2009;Dauzeres et al., 2010;Gaboreau et al., 2011), the use of cement materials in the repository design is assumed to alter the confining properties of the clay buffer plug. Over a long time scale, the degradation of the clays could induce a diminution of their physical and chemical properties by the dissolution of the clay minerals at high pH and by the release of competitive cations for Cs retention such as K + , mainly originating from the cement material alkali-rich pore-water. The quantification and the modeling prediction of these effects are important issues in order to attribute a retention performance to the barrier as a function of pertinent markers of the disturbance (changes in mineral phase composition, concentration levels of competing ions).

The potential effect of a near-field alkaline perturbation is therefore explored in the present study. Batch experiments were conducted to measure the Cs sorption in alkaline perturbed conditions. These experiments aimed at mimicking the effect of an alkaline plume intrusion on COx with accompanying changes in pH and other solution parameters such as K concentration. The second system mimic an interface (clayrock/cement materials) during early reaction time and the last system was an assemblage of minerals representative of the concrete/clay interfaces during long reaction time. A predictive sorption model taken from the literature was applied to identify discrepancies between measured and predicted retention properties. The experimental data, for Cs sorption on Callovian-Oxfordian argillaceous rock under short term (one day) alkaline perturbation, shows that K + competition for Cs + sorption on illite FES sites is the main factor affecting Cs retention capacities. This competitive effect related to the intrusion of hydrated cement pore water in the argillaceous rock is well predicted by the model of Bradbury and Baeyens (2000) without considering any corrections/adjustment in the original model. It is thus possible to make reliable prediction of Cs retention level as a function of K + intrusion in the rock. For instance, from coupled geochemistry/transport modeling K + diffusion in the rock after 10 000 years should lead to a K + concentration up to 20 mmol/L ten centimeter after the interface (corresponding Kd ~ 90 L/kg) whereas this concentration increase should be limited to 3 mmol/L at 0.5 m of the interface (corresponding Kd ~ 160 L/kg


David Picard

Nicolas Thome

Matthieu Cord

Alain Rakotomamonjy

Learning geometric combinations of Gaussian kernels with alternating Quasi-Newton algorithm

We propose a novel algorithm for learning a geometric combination of Gaussian kernel jointly with a SVM classifier. This problem is the product counterpart of MKL, with restriction to Gaussian kernels. Our algorithm finds a local solution by alternating a Quasi-Newton gradient descent over the kernels and a classical SVM solver over the instances. We show promising results on well known data sets which suggest the soundness of the approach.

Introduction

Multiple Kernel Learning(MKL) [START_REF] Bach | Multiple kernel learning, conic duality, and the smo algorithm[END_REF] is now widely used in machine learning applications as an alternative method for combining multiple features, thanks to the availability of efficient algorithms [START_REF] Rakotomamonjy | Sim-pleMKL[END_REF][START_REF] Chapelle | Second order optimization of kernel parameters[END_REF]. It is also a very hot topic in Computer Vision community where the visual feature combination problem is very challenging for classification tasks (see for instance the workshop on Kernels and Distances for Computer Vision at ICCV 2011). Different features are obtained by projection of local descriptors on a visual codebook, and MKL strategies used to optimize their combination [START_REF] Vedaldi | Multiple kernels for object detection[END_REF]. More general combinations have been proposed by Varma et al. in [START_REF] Varma | More generality in efficient multiple kernel learning[END_REF] along with a gradient descent based learning algorithm named GMKL, which when considered with a sum combination boils down to the MKL problem. Varma also investigate the use of a weighted product combination of Gaussian kernels and found it to be more powerful than the sum combination.

In this paper, we further analyze the product combination of Gaussian kernels. Our contributions are three fold: (1) For our specific kernel combination, called PKL, we propose a novel optimization scheme, different from the Varma's algorithm. It is based on alternating a quasi-Newton gradient descent for learning the kernel weights and a classical SVM solver for the sample weights; (2) We discuss about convexity for these classes of problems and show that the associated optimization problem is non-convex; (3) we show promising results on well known data sets.

We first define the notations used in this paper. Let {x i ∈ R M } 1≤i≤N be a training set of samples x i , and f a decision function in a RKHS H. H is the combination of M RKHS H m with minor kernels K m (•, •) = e -γmdm(•,•) such that the major kernel K(•, •) = m e -γmdm(•,•) . We denote d m (•, •) the distance on the subspace H m . We propose to obtain the decision function f by solving the following optimization problem:

min γ,f,b,ξ 1 2 ||f || 2 H + C N i=1 ξ i (1)
s.t. y i (f (x i ) + b) ≥ 1 -ξ i , ξ i ≥ 0, ∀i γ m ≥ 0, ∀m
subscript m always denotes the minor kernels and ranges from 1 to M , and subscript i and j always denote the training samples and range from 1 to N . For the sake of clarity, we now omit these ranges in the summation/product symbols.

We name this learning problem Product Kernel Learning (PKL). In [START_REF] Varma | More generality in efficient multiple kernel learning[END_REF], Varma et al. proposed an algorithm for learning any general combination of kernels named GMKL. Our problem is thus a special case of GMKL restricted to a product of Gaussian kernels. However, it can be applied to any product of Gaussian kernels, regardless of the distance used. Following the methodology of [START_REF] Rakotomamonjy | Sim-pleMKL[END_REF], we propose to solve this optimization problem using an alternate strategy :

min γ J(γ) such that γ m ≥ 0, ∀m (2)
with:

J(γ) =    min f,b,ξ 1 2 ||f || 2 H + C i ξ i s.t. y i (f (x i ) + b) ≥ 1 -ξ i , ∀i ξ i ≥ 0, ∀i (3)
We remark that J(γ) is the optimal value of a standard SVM problem and thus it can be expressed using a standard SVM dual formulation:

J(γ) = max α λ(α, γ) s.t. λ(α, γ) = i α i -1 2 i,j α i α j y i y j m e -γmdm(xi,xj ) i α i y i = 0, 0 ≤ α i ≤ C, ∀i (4)
thanks to the strong duality of the SVM problem, we can express the PKL problem using this dual formulation:

min γ max α i α i -1 2 i,j α i α j y i y j m e -γmdm(xi,xj ) (5)
s.t. i α i y i = 0, 0 ≤ α i ≤ C, ∀i
We now want to stress two points about the optimization problem. First of all, one should note that our PKL framework does not implicitly impose any sparsity constraints in the optimization problem, making it rather simple. However, as we shall see in the experimental section, the algorithm still tends to make weights related to irrelevant minor kernels to 0, inducing then sparsity in that sense.

Another point that we make clear in this paper is the non-convexity of the problem. Although, there exists a general intuitive agreement that the problem ( 5) is not convex [START_REF] Varma | More generality in efficient multiple kernel learning[END_REF], we provide in the sequel a clear proof of this statement. Finally, similarities can be seen with model selection problems for ARD Kernel like in [START_REF] Glasmachers | Maximum likelihood model selection for 1-norm soft margin svms with multiple parameters[END_REF]. However, algorithms in this category usually optimize their criteria on a validation set, whereas our optimization problem is defined on a single training set.

QN-PKL optimization scheme

In [START_REF] Varma | More generality in efficient multiple kernel learning[END_REF], the authors propose an alternating procedure between α and γ subproblems, where the γ step is performed using a simple gradient descent. We propose to improve this step by using a Quasi-Newton descent. The overall optimization scheme is shown in algorithm 1, where Γ is the vector of γ m parameters and A the vector of α i y i parameters.

In the inner loop, we obtain the α ⋆ solution of equation ( 4) by the use of a very fast and efficient SVM solver (in our case LaSVM [START_REF] Bordes | Fast kernel classifiers with online and active learning[END_REF]). We approximate the inverse Hessian matrix by a diagonal matrix B inspired by successful Quasi-Newton procedure used in large scale linear SVM [START_REF] Bordes | Sgd-qn: Careful quasi-newton stochastic gradient descent[END_REF]. Consequently, we named the algorithm QN-PKL. At each iteration t, we search for an improvement of the objective value in the descent direction p t-1 (opposite of gradient direction), weighted by B t-1 and a step size δ. The step size δ is decimate exponentially until an improvement is found or δ < ε. After the possible objective function improvement, the descent direction p t is updated according to the following equation:

p t ← - 1 2 A ⊤ (D m • K)A m (6)
With • being the Hadamard product between matrices. B is updated according to the following diagonal discrete approximation:

B t ← Γ t [m] -Γ t-1 [m] p t [m] -p t-1 [m] m (7)
4 Convexity

In the hereby section, we prove the PKL problem to be non convex. The proof is based on showing that λ(α, γ) is non convex with respects to γ, making thus the full problem (5) non-convex. Let us compute the Hessian H γ of λ over γ :

H γ = ∂ 2 λ ∂γ k ∂γ l = - 1 2 i,j α i α j y i y j d k (x i x j )d l (x i , x j ) m e -γmdm(xi,xj ) (8) = - 1 2 A ⊤ (D k • D l • K)A (9) Algorithm 1 QN-PKL Input: training set A = {xi, yi}, parameters Γ1 = {γm} inited to 1 M , threshold ε, initial learning rate b1 (A, o) ←SVMSolve(A, Γ) // initial alpha coefficients, initial cost o p1 ← -1 2 A ⊤ (Dm • K)A m , B1 ← [b1] m // init descent
t ← t + 1 // increase iterations Γt ← Γ ′ // store new Γ pt ← -1 2 A ⊤ (Dm • K)A m // update descent direction Bt ← Γ t [m]-Γ t-1 [m] p t [m]-p t-1 [m] m // update direction scale g ← o-r
o , o ← r // compute objective gap and store old value end while with A being the vector of αy, D k the distance matrix relative to component k, and K the Gram matrix of kernel K(•, •).

Suppose H γ is positive semi-definite, then all its diagonal values are positive or null for any A coefficients:

∀A, ∀k, - 1 2 A ⊤ (D •2 k • K)A ≥ 0 ( 10
)
which means that the matrix C = -1 2 D •2 k • K is itself positive semi-definite. Let us denote Λ the vector of eigenvalues of C. We remark that:

tr(C) = Λ ⊤ 1 = 0 (11)
However, all eigenvalues of C are positive or null since C is positive semidefinite, thus Λ = 0 and consequently C = 0. This result is absurd since neither D k nor K are null (outside the trivial case were all samples x i are the same vector). This means that C is not positive semi-definite, and consequently H γ is not positive semi-definite.

The same reciprocal reasoning can be done with negative semi-definite property, which in turns means that H γ is indefinite. The direct consequence is that the complete Hessian H with respects to all primal variables is indefinite and thus PKL optimization is not convex.

Experiments

We carried out experiments comparing our QN-PKL with MKL and SVM on 3 standard UCI data sets. We used the same setup as in [START_REF] Varma | More generality in efficient multiple kernel learning[END_REF] (i.e. one Gaussian kernel per component as minor kernels, SVM using a product combination with uniform weights). For fairness of the MKL time evaluation, we use our own Java implementation of SimpleMKL [START_REF] Rakotomamonjy | Sim-pleMKL[END_REF] with the same internal SVM solver 1 .

In table 1, we present a comparison of mean accuracies on sonar, ionosphere, and pima data sets. We can see that the PKL performs better on all three data-sets. This can be explained by the fact that the generalized Gaussian kernel is more powerful than a sum of axis-wise Gaussian kernels, even with PKL converging to a local optimum.

We also report results from [START_REF] Varma | More generality in efficient multiple kernel learning[END_REF] on these datasets. We obtain better performances on larger dimensional data-sets, and similar performances on lower dimensional data-sets. It is worth noting that GMKL uses a ℓ 2 regularization penalty on low dimensional data-set (e.g. pima) which leads to less sparse combination and better results, whereas QN-PKL doesn't use any regularization constraint at all.

We plot kernel weights (normalized to 1) of both algorithms for the Sonar data set on Fig. 1. We can see that QN-PKL outputs less uniform combinations than MKL, even though there is no sparse regulization constraint in our algo-1 software is available at http://perso-etis.ensea.fr/~picard rithm. We explain this natural sparse behavior by the product of kernels which acts as an 'AND' gate. Regarding computational time, QN-PKL seems between 5 and 10 times faster than SimpleMKL on a 3GHz Intel Core2 Duo laptop.

To investigate the sparsity of QN-PKL, we then added 25 random features sampled from the Normal distribution at the end of each input vectors. In table 2, we present accuracies for these noisy data sets. We also compute the ratio R = M m=1 γ m / M +25 m=1 γ m of the relevant weights over the total weights. Using this measure, we can see that QN-PKL is much more efficient at zeroing noisy kernels than MKL, even without any sparsity constraint.

Conclusion

This paper presents a fast Quasi-Newton algorithm for learning a product of Gaussian kernels, named QN-PKL. We prove the related problem to be nonconvex. QN-PKL finds a local solution by alternating a standard SVM optimization loop for learning sample weights, and a approximate second order descent for the kernel weights. Experiments show our algorithm to be as effective as SimpleMKL while being significantly faster. Moreover, QN-PKL seems to be naturally more efficient at discarding irrelevant features than MKL.

  Weights of QN-PKL.

Fig. 1 :

 1 Fig. 1: Comparison of obtained weights for the Sonar data set.

Table 1 :

 1 Classification accuracies for SimpleMKL and QN-PKL on UCI data sets. M is the number of features.

	Data	M MKL (%) time QNPKL (%) time	GMKL[5]	SVM
	Sonar 60 77.9 ±5.5	6.2s	86.6 ±3.4	1.0s	82.3 ±4.8	81.3 ±3.9
	Iono	34 91.3 ±2.3	7.1s	94.1 ±1.5	0.6s	93.0 ±2.1	90.1 ±2.3
	Pima	8	71.4 ±4.1	4.4s	76.4 ±1.9	2.8s	77.2 ±2.1 75.4 ±2.3

Table 2 :

 2 Classification accuracies for SimpleMKL and QN-PKL on Noisy UCI data sets.

	Data set	MKL (%)	R	QN-PKL (%)	R
	Sonar	72.2 ± 3.5 84.9	80.8 ± 6.3	97.7
	Inonosphere 91.2 ± 2.6 67.2	93.3 ± 2.4	99.9
	Pima	71.5 ± 3.4 61.1	74.8 ± 3.0	89.9


Hugo Jacquin

Frédéric Van Wijland

Field theoretic formulation of a mode-coupling equation for colloids

The only available quantitative description of the slowing down of the dynamics upon approaching the glass transition has been, so far, the mode-coupling theory, developed in the 80's by Götze and collaborators. The standard derivation of this theory does not result from a systematic expansion. We present a field theoretic formulation that arrives at very similar mode-coupling equation but which is based on a variational principle and on a controlled expansion in a small dimensioneless parameter. Our approach applies to such physical systems as colloids interacting via a mildly repulsive potential. It can in principle, with moderate efforts, be extended to higher orders and to multipoint correlation functions.

When a suspension of polymer particles is cooled or compressed, a rapid slowing down of the dynamics occurs, and the suspension gradually becomes solid on experimental time scales, without any apparent change in structure [1]. This colloidal glass transition is reminiscent of the phenomenology of molecular glasses. However colloids are conceptually simpler to analyze: the interaction potential often has a simple repulsive character (instead of a Lennard-Jones form) and their effective dynamics is Brownian (instead of Newtonian). They are also experimentally simpler to probe, since colloids are much larger than molecules in simple liquids. An important class of colloids are those who interact via a bounded, repulsive potential. These, due to the existence of a finite energy scale in the potential, exhibit a re-entrant behaviour at high density -the glass melts upon increasing the density-and the non-interacting liquid is recovered in the limit of infinite density [2][3][4]. All particles evolve in a thermal bath (the solution) and thus undergo individual Brownian motions, while also interacting via a given pair-potential v. To make our approach explicit, we chose to study the harmonic spheres model, where the pair-potential v is taken to be of the form:

v(r) = ε 1 -r σ 2 θ 1 -r
σ , but most of the reasoning will be carried out for an arbitrary, sufficiently well-behaved fonction v. This model was introduced by Durian [5] in the context of foam mechanics, where v(r) plays the role of an effective interaction potential that arises from a coarse-graining procedure, but experimental realizations in colloids [6,7] exist, and it became a model system to study glassy structure and dynamics [8].

The position r i (t) of each of the N particles composing the colloidal suspension evolve under Brownian dynamics, encoded in the following Langevin equations:

d r i dt (t) = - j =i ∇ ri v ( r i (t) -r j (t)) + ξ i (t), (1)
where ξ i is a Gaussian white noise with variance 2T (T is the bath temperature). It is our goal to obtain quantitative predictions for the dynamics of the dense liquid phase of such colloidal suspensions upon approaching the glass transition. The only successful first-principles theory to this day is the Mode-Coupling Theory (MCT) developped by Götze and collaborators [9,10]. This is a closed, self-consistent equation of evolution for the relaxation of density fluctuations in equilibrium supercooled liquids which was initially applied to particles evolving under Hamiltonian dynamics, but was later extended by Szamel and Löwen [11] to interacting Brownian particles.

No significant difference between these descriptions [12] emerges, at least within the MCT approximation. In both frameworks MCT predicts a strict dynamical arrest: below a critical temperature, density fluctuations are prevented from relaxing at long times, and ergodicity is spontaneously broken. While successes and failures of MCT are now well documented [13], a systematic way of improving this approximation scheme to overcome the listed pitfalls is still lacking, since the original kinetic formulation of MCT involves physically motivated, but mathematically ill controlled approximations bearing on high-order correlation functions, and it contains no a priori small parameter. The purpose of this letter is to present a new derivation of an MCT equation that bypasses several known pitfalls at the same time: non-interacting particles (v = 0) are exactly dealt with, there exists a small dimensionless parameter, the strength of the potential ε/T , it follows from a well defined variational principle, it can easily be extrapolated to higher-orders, and calculations for fourpoint quantities as well as for sheared systems can simply be implemented.

In order to gain insight into what could be a second order MCT, the idea of resorting to a field theoretic formulation is very appealing, since one can then exploit the standard toolbox of diagrammatic expansions and approximations developped in hard condensed matter and particle physics. Several crucial steps have been made over the past ten years in this direction. Preliminary works [13,14] have soon been shown to be inconsistent with micro-reversibility, a property which is not automatically conserved by standard approximations in field theory. MCT predicts an ergodic-nonergodic transition and one must make sure it does not result from a symmetry breaking approximation. Further attempts [15][16][17] have considerably progressed into the conservation of micro-reversibility, but technical difficulties led to either a non closed equation for density correlations, or to non physical behavior of the solutions to the equations.

In recent years, Kawasaki and Kim [18] obtained a result consistent with reversibility, which led to the same equation as that of the original MCT, but this result stems from a very cumbersome calculation, giving little hope of extending this result to higher orders. In the present letter, we suggest to further exploit the manybody theory tools used in condensed matter, by formally treating our classical particles as bosons. We will see that this approach automatically solves several of the problems encountered in previous attempts of the formulation of a field-theoretic MCT, and provides a transparent way to carry the approximations to next order, or to extend the calculation to different quantities, such as four-point correlators, or to non equilibrium settings, such as in sheared systems. We now proceed with a step-by-step presentation of our approach.

The N coupled Langevin equations Eq. ( 1) can be described by a Fokker-Planck equation governing the evolution of the probability P ({ r i }, t) of finding each particle i at a given position r i at a time t. As a consequence of micro-reversibility, the Fokker-Planck equation converges towards a Gibbsian equilibrium distribution P ({ r i }, t → ∞) = e -i<j v( ri-rj)/T . A standard result [START_REF] Van Kampen | Stochastic Processes in physics and chemistry[END_REF] shows that the knowledge of the equilibrium distribution allows one to render the Fokker-Planck operator Hermitian in the proper basis (this is often called the Darboux or supersymmetry transformation). Hermiticity allows one to interpret this new Fokker-Planck equation as a quantum mechanical problem for interacting bosons. From there we use standard methods of quantum field theory [START_REF] Negele | Quantum many-particle systems[END_REF] to describe the dynamics of the system, which is encoded in the following action:

S[a, a] = t, x a ∂ t a + ∇a • ∇a + V eff [aa]/T. (2)
which is expressed in terms of a pair of complex and conjugate fields a and a. The kinetic term reflects the free diffusion of particles, and the two-body interactions with potential v are expressed, in the quantum formulation, by the effective potential that now contains not only two but also three-body interactions as follows:

V eff [ρ] = 1 4T t, x, y, z ρ( x) ∇ y v ( x -y) ρ( y) • ∇ z v ( x -z) ρ( z) - 1 2 t, x, y ρ( x)∆ x v ( x -y) ρ( y), (3)
where ρ = aa is the physical density and v is the pair potential between the colloids.

It is important to notice that the symmetrization corresponds to a change of basis, so that this field theory does not represent directly the physical problem anymore. It was shown long ago [START_REF] Janssen | [END_REF]22] that the micro-reversibility of usual dynamical field-theories obtained from the regular Fokker-Planck equation is represented by a complicated, non linear transformation, making it very difficult to preserve when performing mode-coupling approximations [16]. In the symmetrized theory, micro-reversibility is simply encoded in the hermiticity of the symmetrized operator, which is a symmetry easy to check and conserve even when performing approximations. Furthermore, setting the pair-potential to 0 cancels the effective potential in Eq. ( 3) and one recovers, without approximation, the free diffusion of colloids. Even if the dynamics described by the action Eq. ( 2) is only related to the real dynamics by a change of basis, careful analysis of the theory shows that far from initial and final conditions (in the "bulk" of the time window), the difference between the modified dynamics and the real dynamics vanishes. Finally, keeping in mind that the pair potential v(r) has an energy scale ε, we see that this approach gives a satisfactory basis for a perturbation expansion in powers of the dimensionless parameter ε/T . Our approach yields a theory that is expressed with ladder operators a and a that do not directly represent the physical density ρ = aa. Introducing it by hand via a Lagrange multiplier, a field λ, we arrive at a field theory involving four independent fields, that we group into a single vector φ = (a, a, λ, ρ). To conclude the layout for the diagrammatic expansion to come, we prefer working with fields defined by deviations around the saddle of the action, which describe a homogeneous and isotropic liquid state of mean density ρ 0 . Thus we set φ = ( √ ρ 0 , √ ρ 0 , 0, ρ 0 ) + (Ψ, Ψ, λ, δρ), and obtain a four field field theory characterized by the following propagator:

G -1 0 (k, ω) =     0 iω + k 2 - √ ρ 0 0 -iω + k 2 0 - √ ρ 0 0 - √ ρ 0 - √ ρ 0 0 1 0 0 1 u(k)     , (4)
where

u(k) = k 2 2ρ0 (1 + ρ 0 v(k)/T ) 2 -1 .
The interaction part of the action is made of two cubic terms, one is

* γ(k 1 , k 2 , k 3 )δρ(k 1 )δρ(k 2 )δρ(k 3 ) and the other is * λ(k 1 )Ψ(k 2 )Ψ(k 3 ). where γ(k 1 , k 2 , k 3 ) = 1 2T 2 [k 1 • k 2 v(k 1 )v(k 2 ) + perms.],
and the symbol * stands for k1,k2,k3 δ(k 1 + k 2 + k 3 ). We now turn to the procedure allowing us to determine the correlations of our fields.

The physical quantity that we are ultimately interested in is the matrix element of the two point correlator of the theory G that describes density-density correlations. Since our theory contains four fields, G is a 4 × 4 matrix, with 10 independent entries. Our goal is to obtain a closed equation bearing on the δρ-δρ element only. Per-forming a double Legendre transform of the dynamical partition function, one obtains a functional of the correlator G, called the 2PI or the Luttinger-Ward functional, Φ [G]. A careful analysis of this functional, which can be found in modern field theory textbooks [START_REF] Cini | Topics and methods in condensed matter theory[END_REF][START_REF] Calzetta | Non-equilibrium quantum field theory[END_REF], shows that it has several remarkable properties. It not only provides a variational principle to obtain the correlator G (the functional attains its maximum when evaluated at the true correlator) but also gives access to the inverse of the correlator, since it is obtained as the functional derivative of Φ[G] with respect to G. Diagrammatically, it is composed of all two particle irreducible diagrams (2PI), allowing for simple truncations of the complete expression of Φ.Finally, any truncation of Φ can be shown to preserve the symmetries of the action, which we use to conserve micro-reversibility when performing approximations. To obtain a self-consistent approximation for the two point correlator, one constructs an approximation for the 2PI functional by selecting a certain subclass of diagrams that contribute to it. For example, the two simplest diagrams that contribute have the following topology:

Φ[G] = + + . . . (5)
Then an expression for the vertex function Σ (the inverse of the correlator) is obtained by functionally differentiating with respect to G. Finally, a self consistent equation is obtained by exploiting the relationship that exists between Σ and G (sometimes referred to as the Schwinger-Dyson equation):

G -1 0 -Σ[G] G = 1.
This variational approach can be seen as the dynamical counterpart to the density functional theory of liquids.

So far, all these considerations are in principle exact. We now present the simplest self-consistent approximation that can be obtained within this formalism, and we will see that we obtain an equation that has the exact same structure as that of the Mode-Coupling equation. We now exploit that our theory contains a small parameter, namely the strength of the potential, to select the lowest order beyond mean-field. We have two vertices in the theory, one of order 4 in ε, and one of order 0. We want to stay to the lowest non-trivial order, so we can neglect the former.

We only retain the simplest diagram in the expression of the 2PI functional Eq. ( 5), and will justify this a posteriori. We obtain an expression for the vertex function that can be inserted in the Schwinger-Dyson equation to yield:

G -1 0 G( k, τ )= t ′ , q Γ( k, q)G( k -q, τ -t ′ )G( q, τ -t ′ )G( k, t ′ ) (6)
This is a matrix equation in which all correlators appear. Note that Eq. ( 6) in itself already has the structure of the mode-coupling equation, in which the memory kernel is a quadratic functional of the correlators, except that it applies to a matrix instead of a scalar. In order to write down an equation that involves the density-density correlator only, we must express all other correlators in terms of C( k, t-t ′ ) = δρ(-k, t ′ )δρ( k, t) . At the meanfield level, all correlators are proportional; we use these proportionality relations and insert them into Eq. ( 6).

The proportionality coefficients involve various powers of ε/T , and one then verifies that, when inserting the proportionality relations into the expression of the 2PI functional, all contributions coming from the diagrams that we neglected are indeed of higher order in ε/T . In Eq.( 5) only the topology of the diagrams is represented, but one has to draw all possible diagrams from the vertices of the theory. Even for the simplest watermelon diagram, this involves 11 independent diagrams. Fortunately, to lowest order (order 2 in ε/T ) only one diagram survives, and the final evolution equation for C is:

0 = -∂ 2 τ C( k, τ ) + Ω(k) 2 C( k, τ ) (7)
+ 1 2ρ 0 t ′ , q M( k, q)C( q, τ -t ′ )C( k -q, τ -t ′ )∂ t ′ C( k, t ′ ),
where the memory kernel has the following expression:

M( k, q) = q 2 c( q) + ( k -q) 2 c( k -q) 2 (8)
Note that, as usual in field theoretic formulations, one has had to resort to a further approximation, i.e. setting -v( k)/T = c(k). This results from our treating the statics and the dynamics on equal footing. At this order of approximation, this replacement is correct, as can be seen with a perturbation analysis of the equilibrium liquid, and allows for direct comparison with the regular MCT result. The statics of equation ( 8) is closely similar to the original mode-coupling equation, apart from the slightly different wave-vector dependence that the original mode-coupling approach predicts, in which the factors q 2 and ( k -q) 2 in the rhs of ( 8) are replaced with k • q and k • ( k -q), respectively. Assuming that the density density correlation function does not decay to zero at large times, one makes the usual ansatz:

lim t→∞ C( k, t) = ρ 0 S( k)f ( k)
, where S(k) is the static structure factor related to the direct correlation function by S(k) = 1/(1 -ρ 0 c(k)), and seek an equation for the non-ergodicity parameter f ( k). By Laplace transform methods one easily obtains:

f (k) 1 -f (k) = ρ 0 S(k) 8π 2 k 4 q M( k, q)S( q)S( k -q)f ( q)f ( k -q) (9)
We then numerically solve this equation with an iterative procedure. The only input is c(k) for the equilibrium liquid, than can be calculated e.g. within the Hyper-Netted Chain approximation. Exactly as in the case of standard MCT, one finds that there exists a transition line T MCT (ρ) above which f (k) = 0 is the only solution, whereas below T MCT (ρ), a nonzero f (k) is found where ergodicity is spontaneously broken. A posteriori, we are inclined to view the MCT equation as a high-temperature expansion. In Fig. 1 behavior is very similar, except for the limit k → 0, where Eq. ( 9)) is found to give f (k) ∼ k→0 1. The modification of the kernel implies that the absolute value of the transition temperature is slightly modified. For example at the packing fraction 0.53, the regular MCT transitionis located approximately at T MCT ≈ 10 -4 , whereas our rough numerical estimate is T MCT ≈ 8.10 -4 .

In this letter we have presented a comprehensive approach to write down mode-coupling equations based on a variational principle. In the example of bounded interactions, we have shown that when the strength of the interaction is taken as an expansion parameter, it is possible to write down, to lowest-order, a mode-coupling equation similar to the regular MCT equation. Our strategy can be extended in a variety of directions. The most obvious one is retaining higher orders in the expansion parameter ε/T . The resulting equation for the 7-dimensional order parameter G will pick up a G 5 contribution to its memory kernel. Retaining, after appropriate substitutions based on the leading order expansion (6), the next order in ǫ/T seems a tedious yet quite accessible task. It would also be of interest to examine whether qualitative differences show up if the full set of ten equations (6) were solved. On our to-do list we also have more pressing wishes like implementing the so-called "thermodynamic of histories" formalism [START_REF] Merolle | Proc. Nat. Acad. Sc[END_REF][START_REF] Garrahan | [END_REF] and probing the relationships between ergodicity breaking and dynamic phase transitions. It would be interesting to investigate sheared systems and compare our approach with existing extensions of MCT [27]. The fate of ergodicity breaking and dynamic phase transitions under shear also belongs to our open questions.

FIG. 1 :

 1 FIG.1: Non-ergodicity parameter f (k) calculated with the regular MCT kernel (full line) and within our modified kernel (dotted line), at packing fraction 0.53 and temperature 10 -4 .

We warmly acknowledge the advice and/or comments of G. Biroli, N. Dupuis, R.L. Jack, J.Kurchan, V. Lecomte, K. Miyazaki, G. Szamel and F. Zamponi. H. Jacquin acknowledges financial support from Capital Fund Management (CFM) foundation.