Mellouk A., Chebira A. (eds.) Machine Learning

Подождите немного. Документ загружается.

Learning Optimal Web Service Selections in Dynamic Environments when

Many Quality-of-Service Criteria Matter

223

estimates of the aggregated quality score of the policy, and of the average aggregated

quality value until destination; these estimates will be denoted by

(,)

ck i,

()

and

()

Vk . The RRL for an acyclic graph, where the states are ordered in such a way that there is

no edge going backward (i.e., there exists no edge linking a state

to a state

k where

is a successor state of

k ( >

kk ), is as follows (a detailed treatment can be found in

(Achbany et al., 2005)):

1. Initialization phase: Set ()0

, which is the expected cost at the destination state.

2. Computation of the TA policy and the expected cost under exploration constraints: For

=( 1)

kk− to the initial state

k , compute:

(

)

()

exp ( , ) ( )

()= ,

exp ( , ) ( )

()= () (,) ( )for

ki iu

ki '

uUk

ikiiuid

uUk

ck u Vk

Vk u cku Vk k k

∈

⎧

⎡⎤

−+

⎣⎦

⎪

⎡⎤

−+

⎢⎥

⎨

⎣⎦

⎪

≠

⎡⎤

⎪

⎣⎦

⎩

∑

(6)

where

=()

iu k

kfu,

k =()

u and

is set in order to respect the prescribed degree of

entropy at each state (see Eq.4 which can be solved by a simple bisection search).

Various approaches can be applied to update the estimated criterion

r ; e.g., exponential

smoothing leads to:

(1 )

uu u

rr r

←

+− (7)

where

r is the observed value of the criterion for

and ]0,1[

∈

is the smoothing

parameter. Alternatively, various stochastic approximation updating rules could also be

used. The composer updates its estimates of the criterion each time a WS performs a task

and the associated cost is updated accordingly.

5. Simulation results

Experimental setup. Task allocation for the service provision problem diplayed in Fig.3 was

performed. A total of three distinct WS were made available for each distinct task. Each

,ku

is characterized by its actual

r which is an indicator of the WS's performance over the

optimization criterion (see,

§ 4.2). In this simulation, it will simply be the probability of

successfully performing the task (1 -- probability of failure). In total, 42 WS are available to

the Composer for task allocation. For all WS

u ,

r takes its value 0,1]

∈

; for 70% of the WS,

the actual

r is hidden (assuming it is unknown to the Composer) and its initial expected

value,

r , is set, by default, to 0.3 (high probability of failure since the behavior of the WS

has never been observed up to now), while actual

r value is available to the Composer for

the remaining 30% (assuming these WS are well known to the Composer). Actual

r is

randomly assigned from the interval

[0.5,1.0] following a uniform probability distribution.

It has been further assumed that

(, )= ()

iu u

ct w lnr

−

, meaning that it is the product of the

Machine Learning

224

along a path that is optimized (this is a standard measure of the reliability of a system).

After all tasks are allocated, the selected WS execute their allocated tasks according to their

actual

r value (with failure 1

−

). The estimated WS criterion

r is then updated by

exponential smoothing, according to Eq.7. In Eq.7,

r equals 1 if

w is successful at

executing the task it has been allocated, 0 otherwise. Estimated costs are of course updated

in terms of the

r and each time a complete allocation occurs, the probability distributions

of choosing a WS are updated according to Eq.6. 10,000 complete allocations were simulated

for exploration rate 20%.

Fig. 8. Success rate in terms of run number, for an exploration rate of 20%, and for the five

methods (no exploration, actual r known,

-greedy, naive Boltzmann, RRL).

Results. The RRL is compared to two other standard exploration methods,

-greedy and

naive Boltzmann (see (Achbany et al., 2005) for details), while tuning their parameters to

ensure the same exploration level as for RRL. The success rate is defined as the proportion of

services that are successfully completed (i.e., all tasks composing the service are allocated

and executed successfully) and is displayed in Fig. 4 in terms of the run number (one run

corresponding to one complete assignment of tasks, criterion estimation and probability

distribution update). Fig. 4 shows the RRL behaves as expected. Its performance converges

almost to the success rate of the RRL in which all actual

r are known from the outset (i.e.,

need not be estimated)---and indicate that exploration clearly helps by outperforming the

allocation system without exploration (which has a constant 75% success rate). Fig.5

compares the three exploration methods by plotting the average absolute difference

between actual

r and estimated

r criterion values for a 30% exploration rate. Exploration

is therefore clearly helpful when the environment changes with the appearance of new

agents---i.e., exploration is useful for directing Composer behavior in dynamic, changing,

and open architectures, i.e., in the SCA.

Learning Optimal Web Service Selections in Dynamic Environments when

Many Quality-of-Service Criteria Matter

225

Fig. 9. Average absolute difference between actual (

r ) and estimated ( r ) criterion values in

terms of run number, for three exploration methods (

-greedy, naive Boltzmann, RRL).

6. Related work

Various possibilities for representation of web services composition have already been

addressed. Jaeger et al. use composition patterns (sequence, loop, xor, and, or , etc.) to

represent structural elements of the composition. Hamadi (Hamadi & Benatallah, 2003) and

Benetallah and Fu et al. (Fu et al., 2006) approaches refer both to Petri nets for modeling web

services control flow. Rather than using such patterns and their associated aggregation

rules, we choose, as Zeng et al. (Zeng et al., 2003b; Zeng et al., 2004), Benatallah and Dumas

(Benatallah et al., 2002) and Zhang et al. (Zhang et al., 2007), to control services composition

with the help of statecharts.

While statecharts and their associated formal semantic are used to represent the different

tasks entering in the composition, Directed Acyclic Graph (DAG) (Gu & Nahrstedt, 2002) are

used to represent alternative web services allowing to fulfill these tasks. Zeng (Zeng et al.,

2004) proposes to model alternatives with multiple execution paths derived from statecharts

possibilities. We choose to represent our composition possibilities with a Directed Acyclic

Hypergraph (DAH) where nodes represent functional steps of execution and edges are web

services alternatives to fulfill a given task.

Our selection of services that will enter in the services composition is based on their

quality properties, i.e., their QoS. To lead the selection from the requester view, we

provide him a QoS model enabling to specify its expectations about quality behavior. This

behavior is expressed by relationships between characteristics and dimensions, priorities

between quality properties and preferences over values. The preference over values has

already been addressed in other approaches under the form of a direction attribute

indicating if a property has to be maximized or minimized (Jaeger et al., 2004; Liu et al.,

Machine Learning

226

2004; Naumann et al., 1999; Zeng et al., 2004). Our preference structure offers more

information, we allow the user to specify conditions and indifference thresholds. The

priority relationship is defined in some proposals with means of a weight attribute

associated to quality properties (Jaeger et al., 2004; Zeng et al., 2004). Our model

authorizes weights binded to quality properties at different levels and we define a method

to fix adequately these weights.

Most QoS composition approaches aim at summing QoS values of services entering in the

composition rather than computing their individual performance (Cardoso et al., 2004;

Cheng et al., 2006; Jaeger et al., 2005; Yu & Lin, 2004; Yu & Lin, 2005; Zeng et al., 2003b;

Zhang et al., 2007). In our MCRRL proposal, we focus on the individual evaluation of each

web service candidate to the whole composition. Rather than using Reinforcement

Learning computation, Zeng and colleagues (Zeng et al., 2003b) proceed to finding

optimal WS compositions through linear programming techniques. In contrast to RL, their

approach considers each WS composition as a new problem to solve, so that there is no

learning. Canfora and colleagues (Canfora et al., 2004) use genetic algorithms, avoiding

thus the need for a linear objective function and/or linear constraints in the search for the

optimal WS composition (required for the linear programming approach (Zeng et al.,

2003b)). MCRRL improves responsiveness of the system to varying availability and

appearance of new WS because of exploration. MCRRL allows the execution of potentially

complex processes, permits concurrency, while assuming that the set of available WS is

changing. One distinctive characteristic the composer's behavior suggested in the present

paper is that the MCRRL accounts for a vector of criteria when allocating tasks, including

QoS, service provision deadline, provision cost, explicit user preferences, and agent

reputation. Feedback mechanisms are also used by Maximilien and Singh (Maximilien &

Singh, 2005) that propose service selection driven by trust values assigned to individual

services. Trust is extracted from user-generated reports of past service performance (as

usual in reputation systems) over qualities defined by a system-specific QoS ontology.

Level of trust depends on the degree to which reputation and quality levels advertised by

the provider match. Similar approaches have been proposed, yet fail to address service

selection in open, distributed MAS architecture, furthermore without dynamic allocation

so that autonomic requirements are not fulfilled. By basing selection on trust only and

generating levels of trust from advertised and user-observed behavior, Maximilien and

Singh's approach involves learning driven by exploitation of historical information,

without exploration.

7. Conclusions and future work

This paper advocates that WS compositions optimal w.r.t. a set of criteria need to be learned

at runtime and revised as new WS appear and availability of old WS changes, whereby the

learning should be based on observed WS performance, and not the performance values

advertised by the service providers. To enable such learning, a selection procedure is

needed which both exploits the data on observed WS performance in the past, and explores

new composition options to avoid excessive reliance on past data.

As a response, this paper proposes the Multi-Criteria Randomized Reinforcement Learning

(MCRRL) approach to WS composition. MCRRL combines a generic service request and the

Learning Optimal Web Service Selections in Dynamic Environments when

Many Quality-of-Service Criteria Matter

227

Randomized Reinforcement Learning (RRL), a reinforcement learning algorithm. The SR

model describes the process to execute by the WS composition and the criteria and

constraints to meet when executing it. The RRL selects the WS for performing tasks specified

in the service request. The algorithm decides on the WS to select among competing WS

based on multiple criteria, while both exploiting available WS performance data and

exploring new composition options.

MCRRL responds to four common requirements when defining a task allocation

procedure for WS composition. First, the RRL uses both exploitation and undirected

continual exploration in WS composition: exploitation uses available data to ground the

allocation decision in performance observed during the execution of prior compositions,

whereas exploration introduces new allocation options that cannot be identified from past

performance data. Optimal WS compositions are thus identified revised at runtime.

Second, the generic SR model combined with the optimization approach in the RRL allow

many criteria for comparing alternative task allocations. Third, the comparison over

various criteria relies on observed performance over the given criteria, instead of vales

advertised by service providers. Finally, the algorithm can be extended to allow

underterministic outcomes of WS executions (as explained elsewhere (Achbany et al.,

2005)).

Since undirected exploration may be costly in actual applications, future work will

investigate the performance of MCRRL within realistic applications, so that the approach

can be optimized for practical settings.

8. Acknowledgments

We are grateful to Emmanuel Mathot of the European Space Agency, who provided precise

information about the GPOD project and assisted our efforts in describing quality

information of services related to the GPOD project.

9. References

Achbany, Y.; Fouss, F.; Yen, L.; Pirotte, A. & Saerens, M. (2005) Tuning Continual

Exploration in Reinforcement Learning. Technical report,

http://www.isys.ucl.ac.be/staff/francois/Articles/ Achbany2005a.pdf.

Benatallah, B.; Sheng, Q. Z.; Ngu, A. H. & Dumas M. (2002) Declarative Composition and

Peer-to-Peer Provisioning of Dynamic Web Services. Proceedings of the International

Conference on Data Engineering, pages 0297, Los Alamitos, CA, USA.

Bertsekas, D. P. (2000) Dynamic programming and optimal control. Athena sientific.

Canfora, G.; Di Penta, M.; Esposito, R. & Villani, M.-L. (2004) A Lightweight Approach for

QoS-Aware Service Composition. Proceedings of the 2nd International Conference on

Service Oriented Computing (ICSOC'04), pages 36-47.

Cardoso, J.; Sheth, A. P.; Miller, J. A.; Arnold, J. & Kochut, K. (2004) Quality of service for

workflows and web service processes. J. Web Sem., 1(3):281-308.

Chen , Y.P.; Zeng-Zhi, L.; Qin-Xue, J. & Chuang, W. (2006) Study on QoS Driven Web

Services Composition. Frontiers of WWW Research and Development - APWeb 2006,

:702--707.

Machine Learning

228

Christofides, N. (1975) Graph theory: An algorithmic approach. Academic Press.

Cover, T. M. & Thomas, J. A. (1991) Elements of information theory. John Wiley and Sons.

D'Ambrogio, A. (2006) A Model-driven WSDL Extension for Describing the QoS ofWeb

Services. ICWS '06: Proceedings of the IEEE International Conference on Web

Services (ICWS'06), pages 789--796, Washington, DC, USA, 2006, IEEE

Computer Society.

Figueira, J.; Greco, S. & Ehrgott, M. (2005) Multiple Criteria Decision Analysis: State of the Art

Surveys. Springer Verlag, Boston, Dordrecht, London.

Fu, Y.; Zhijiang, D. & Xudong, H. (2006) Modeling, validating and automating composition

of web services. ICWE '06: Proceedings of the 6th international conference on Web

engineering, pages 217--224, New York, NY, USA, 2006. ACM.

Gu, X. & Nahrstedt, K. (2002) A scalable QoS-aware service aggregation model for peer-to-

peer computing grids. Proceedings of the IEEE HPDC-11, 2002.

Hamadi, R. & Benatallah, B. (2003) A Petri net-based model for web service

composition. ADC '03: Proceedings of the 14th Australasian database conference,

pages 191--200, Darlinghurst, Australia, Australia, 2003. Australian Computer

Society, Inc.

Hwang, C.L. & Yoon, K. (1981) Multiple attribute decision making : Methods and applications.

Springer-Verlag, 1981.

Jaeger, M. C.; Rojec-Goldmann, R. & Muhl, G. (2004) QoS Aggregation for Web Service

Composition using Workflow Patterns. edoc, 00:149-159.

Jaeger, M. C.; Rojec-Goldmann, R. & Muhl, G. (2005) QoS Aggregation in Web Service

Compositions. EEE '05: Proceedings of the 2005 IEEE International Conference on e-

Technology, e-Commerce and e-Service (EEE'05), pages 181--185, Washington, DC,

USA, 2005. IEEE Computer Society.

Kapur, J. N. & Kesavan, H. K. (1992) Entropy optimization principles with applications.

Academic Press, 1992.

Keller, A. & Ludwig, H. (2003) The WSLA Framework: Specifying and Monitoring Service

Level Agreements for Web Services. J. Netw. Syst. Manage., 11(1):57--81.

Liu, Y.; Ngu, A. H. & Zeng, L. Z. (2004) QoS Computation and Policing in Dynamic Web

Service Selection. pages 66--73, New York, NY, USA, ACM Press.

Maximilien, E. M. & Singh, M. P. (2005) Multiagent System for Dynamic Web Services

Selection. Proceedings of the Int. Conf. Auton. Agents and Multi-Agent Syst., 2005.

McIlraith, S. A. & Martin, D. L. (2003) Bringing Semantics to Web Services. IEEE Intelligent

Systems, 18(1):90--93.

Menascé, D. A. (2002) QoS Issues in Web Services. IEEE Internet Computing, 6(6):72--75,

2002.

Mitchell, T. M. (1997) Machine learning. McGraw-Hill Compagnies, 1997.

Naumann, F.; Leser, U. & Freytag, J. C. (1999) Quality-driven Integration of Heterogenous

Information Systems. Proceedings of the International Conference on Very Large

Databases (VLDB), pages 447-458, Edinburgh, UK, 1999.

OMG / Business Process Management Initiative. Business Process Modeling Notation

Specification. Final Adopted Specification dtc/06-02-01, 2006.Technical report,

Object Management Group / Business Process Management Initiative., 2006.

Learning Optimal Web Service Selections in Dynamic Environments when

Many Quality-of-Service Criteria Matter

229

OMG. UML Profile for Modeling QoS and Fault Tolerance Characteristics and Mechanisms.

Technical report, Object Management Group, 2006.

OMG. UML Profile for Modeling QoS and Fault Tolerance Characteristics and Mechanisms.

Technical report, Object Management Group, 2006.

Papazoglou, M. P. & Georgakopoulos, D. (2003) Service-oriented computing. Commun.

ACM, 46(10).

Saaty, T.L. (1980) The Analytic Hierarchy Process, Planning, Piority Setting, Resource Allocation.

McGraw-Hill, New york.

Saerens, M.; Souchon, N.; Renders, J. M. & Decaestecker, C. (2004) Decision-making under

uncertainty about the class priors. Submitted for publication.

Sutton, R.S. & Barto, A.G. (1998) Reinforcement Learning: An Introduction. MIT Press,

Cambridge, MA.

Thrun, S. (1992) The Role of Exploration in Learning Control. In D.A. White and D.A. Sofge,

editors, Handbook for Intelligent Control: Neural, Fuzzy and Adaptive Approaches. Van

Nostrand Reinhold, Florence, Kentucky 41022.

Thrun, S.; Burgard, W. & Fox, D. (2005) Probabilistic Robotics. MIT Press.

Thrun, S. (1992) Efficient Exploration In Reinforcement Learning. Technical report,

Pittsburgh, PA, USA.

Urgaonkar, B.; Pacifici, G.; Shenoy, P.; Spreitzer, M. & Tantawi, A. (2005) An analytical

model for multi-tier internet services and its applications. SIGMETRICS Perform.

Eval. Rev., 33(1):291--302.

Verbeeck, K. (2004) Coordinated Exploration in Multi-Agent Reinforcement Learning. PhD

thesis, Vrije Universiteit Brussel, Belgium.

Walsh, A. E. (2002) Uddi, Soap, and Wsdl: The Web Services Specification Reference Book. Prentice

Hall Professional Technical Reference, 2002.

Tao, Y. & Kwei-Jay, L. (2005) Service Selection Algorithms for Composing Complex

Services with Multiple QoS Constraints. Service-Oriented Computing - ICSOC

2005, :130--143.

Tao, Y. & Kwei-Jay, L. (2004) Service Selection Algorithms for Web Services with End-to-

End QoS Constraints. CEC '04: Proceedings of the IEEE International Conference on E-

Commerce Technology (CEC'04), pages 129--136, Washington, DC, USA, 2004. IEEE

Computer Society.

Zacharia, G. & Maes, P. (2000) Trust Management Through Reputation Mechanisms. Applied

Artificial Intelligence, 14:881-907.

Zeng, L.; Benatallah, B.; Dumas, M.; Kalagnanam, J. & Sheng, Q. Z. (2003) Quality Driven

Web Services Composition. Proc. Int. Conf. on World Wide Web (WWW2003), 2003.

Zeng, L.; Benatallah, B.; Ngu, A. H.; Dumas, M.; Kalagnanam, J. & Sheng, H. (2004) QoS-

Aware Middleware for Web Services Composition. IEEE Trans. Softw. Eng.,

30(5):311--327.

Zeng, L; Jeng, J.-J.; Kumaran, S. & Kalagnanam, J. (2003) Reliable Execution Planning and

Exception Handling for Business Process. Technologies for E-Services, pages 119-

130.

Machine Learning

230

Zhang, C.; Chang, R. N.; Perng, C.-S.; So, E.; Tang, C. & Tao, T. (2007) QoS-Aware

Optimization of Composite-Service Fulfillment Policy. Services Computing, 2007.

SCC 2007. IEEE International Conference on, :11--19.

Zhou, C.; Chia, L.-T. & Lee, B.-S. (2004) DAML-QoS Ontology for Web Services. ICWS '04:

Proceedings of the IEEE International Conference on Web Services (ICWS'04), pages 472,

Washington, DC, USA, 2004. IEEE Computer Society.

Model Selection for Ranking SVM Using

Regularization Path

Karina Zapien

, Gilles Gasso

, Thomas Gärtner

and Stéphane Canu

LITIS EA 4108 - INSA de Rouen

Fraunhofer IAIS,

France

Germany

1. Introduction

This chapter deals with supervised learning problems under the ranking framework.

Ranking algorithms are typically introduced as a tool for personalizing the order in which

document recommendations or search results - in the web, for example - are presented. That

is, the more important a result is to the user, the earlier it should be listed. To this end, two

possible settings can be considered :

i. the algorithm tries to interactively rearrange the results of one search such that relevant

results come the closer to the top the more (implicit) feedback the user provides,

ii. the algorithm tries to generalize over several queries and presents the results of one

search in an order depending on the feedback obtained from previous searches.

The first setting deals with an active learning while the second setting deals with a passive

supervised learning. This kind of problems have gain major attention given the nowadays

amount of available informations. This is without doubt a challenging task in the medium

and large scale context.

Several methods have been proposed to solve these problems. For the passive setting, the

Rankboost algorithm (Freund et al. (2003)) is an adaptation from the Adaboost algorithm to

the ranking problem. This is a boosting algorithm which works by iteratively building a

linear combination of several “weak” algorithms to form a more accurate algorithm. The

Pranking algorithm (Crammer & Singer (2001)) is an online version of the weighted

algorithm. The SVRank and RankSVMalgorithms are the adaptation of the Support Vector

machines for classification and regression, respectively, while the MPRank (Cortes et al.

(2007)) is a magnitude-preserving algorithm, which searches not only to keep the relative

position of each sample but also to preserve the distance given by the correct ordering. This

last algorithm has as well the form of a regularization problem as the two previous with a

different cost function.

Later, the Ranking SVM (RankSVM) algorithm was proposed by Herbrich et al. (2000) and

Joachims (2002) as an optimization problem with constraints given by the induced graph of

the ordered queries’ results. This algorithm forms part of the family of kernel algorithms of

the SVM type (Boser et al. (1992); Schölkopf & Smola (2002)).

Kernel methods like the SVM or the ranking SVM solve optimization problems of the form

Machine Learning

232

(1)

where V : H → R

is a loss function,

∈ R

is a regularization parameter, Ω: H → R

is the

regularizer (which allows to enforce some nice properties as smoothness or simplicity of f)

and H represents the hypothesis space. Usually H is chosen as a reproducing kernel Hilbert

space. Although a key bottleneck for applying such algorithms in the real-world is choosing

, research often ignores this. As empirical results, however, strongly depend on the chosen

, runtime intensive repeated cross-validations have to be performed. Hence, in this chapter

we concentrate on speeding up and automating this choice by building on the regularization

path for SVMs (Hastie et al. (2004)).

2. Piecewise linear solutions

This framework is a kind of a more generic regularized optimization problems, already

studied for regularization problems (Rosset & Zhu (2007)) and for parametric quadratic

programming (Markowitz (1959)) for portfolio optimization. We are interested by the

efficient computation of the regularization path. Hence, let us define first this notion.

Definition 2.1 (Regularization path)

The regularization path of Problem (1) is the set of all solutions obtained when varying

over R

i.e.

Path = {f

, with

∈ [0,+∞]}.

As one can see, with this definition, the pursued policy can have a high computational price.

In order to gain in efficiency, the family of piecewise linear solution path is of particular

interest. To highlight this fact, we consider the following definition.

Definition 2.2 (piecewise linear solution path)

The solution path is said to be piecewise linear when there exists a strictly decreasing (or increasing)

sequence

, t = 1, . . . , N such that :

(2)

where h

, t = 1, . . . , N denotes a sequence of functions in H.

With such property, it is easy to efficiently generate the whole path of solution. Indeed, in

such case, one only needs the sequence

and the corresponding h

. Any other functions in-

between can be simply obtained by linear interpolation. Hence, owing to such property, the

computational cost of obtaining the whole path of solution may be of the order of a single

solution computation.

The question induced by this remark is to find which kind of objective functions makes the

solution path piecewise linear. In Rosset and Zhu (2007), the necessary conditions were

given for Problem (1) to admit a linear solution path. The main result is summarized by the

theorem below.

Theorem 1

Assume the loss V(f) and the regularizer Ω(f) are convex functions. If one objective function (either

V(f) or Ω(f)) is piecewise linear and the other one piecewise quadratic then the solution path of the

Problem (1) is piecewise linear.