A Model of User Preferences for Semantic Services Discovery and Ranking

A Model of User Preferences for Semantic Services Discovery and Ranking Jos´eMar´ıa Garc´ıa, David Ruiz, and Antonio Ruiz-Cort´es University of Seville Escuela T´ecnica Superior de Ingenier´ıa Inform´atica Av. Reina Mercedes s/n, 41012 Sevilla, Spain [email protected] Abstract. Current proposals on Semantic Web Services discovery and ranking are based on user preferences descriptions that often come with insufficient expressiveness, consequently making more difficult or even preventing the description of complex user desires. There is a lack of a general and comprehensive preference model, so discovery and ranking proposals have to provide ad hoc preference descriptions whose expressiveness depends on the facilities provided by the corresponding technique, resulting in user preferences that are tightly coupled with the underlying formalism being used by each concrete solution. In order to overcome these problems, in this paper an abstract and sufficiently expressive model for defining preferences is presented, so that they may be described in an intuitively and user-friendly manner. The proposed model is based on a well-known query preference model from database systems, which provides highly expressive constructors to describe and compose user preferences semantically. Furthermore, the presented proposal is independent from the concrete discovery and ranking engines selected, and may be used to extend current Semantic Web Service frameworks, such as wsmo,sawsdl,orowl-s. In this paper, the presented model is also validated against a complex discovery and ranking scenario, and a concrete implementation of the model in wsmo is outlined. Keywords: User Preferences, Ontology Modeling, Semantic Web services, Service Discovery, Service Ranking. 1 Introduction Semantic Web Services (SWS) definition frameworks provide comprehensive tools to describe services and their interactions. However, preferences cannot be described at the same detail level, i.e. users cannot define complex desires for a concrete service request. For instance, wsmo goals [19] only support the description of requirements about a request in the form of capabilities, but preferences to rank services fulfilling these requirements cannot be directly expressed by using a standard wsmo goal definition, which only provides means to define non-functional properties / values pairs. In other words, preferences are not considered first-class citizens in wsmo, in comparison to service capabilities, whose definitions are more expressive. Other frameworks, such as owl-s [16] or sawsdl [5], do not even define a specific model to describe user requests at all. Discovery and ranking proposals try to fill this gap, extending SWS frameworks to support preferences definition, or just providing separate user preferences descriptions. There is a variety of formalisms proposed to define preferences, such as tendencies [4,22,24], relative weights [15,17,18,23], or utility functions [8,13,25]. These formalisms actually determine the level of expressiveness of each proposal, while resulting in a high coupling between user preferences definition and its corresponding discovery and ranking implementations. In order to overcome these limitations, a highly expressive, intuitive model of user preferences is presented in the following. This proposal adapts a well-known model from database systems [12] that allows to define preferences constructively and user-friendly. In this paper, a user preference ontology is described and validated using a discovery scenario from the SWS Challenge1. Additionally, the proposed ontological model is applied to wsmo definitions, extending its goal element in order to allow the specification of preferences using our model. The rest of the paper is structured as follows: Sec. 2 discussed the related work on preference definition. Then, in Sec. 3 our proposal is thoroughly presented and validated against a scenario from the SWS Challenge, along with an implementation in wsmo. Finally, Sec. 4 sums up our work and presents the benefits of our contribution. 2 Related Work Concerning the representation of preferences, there are several approaches in the literature based on different formalisms. Thus, preferences modeled as utility functions have been widely used in economics [6,10] and web systems [1,8,25]. Another formalism based on partial orders were proposed in database systems field [3,12]. The main difference between these two formalisms is that the former constitutes a quantitative approach while the latter is qualitative. Although quantitative approaches are more general because most preference relations can be defined in terms of utility functions, there are some intuitive preferences that cannot be captured by these functions [3]. On the other hand, qualitative approaches have higher expressiveness and are more intuitive and user-friendly, though they are not directly applicable to a SWS scenario because they do not take into account that properties may be expressed using different abstraction levels depending on the stakeholder. Our proposal constitutes a hybrid model, where both qualitative and quantitative preferences can be expressed. Preference queries from database systems can be also applied to the Semantic Web scenario with ease. Thus, Siberski et al. [20] extend SPARQL query language with a preference clause similar to the proposed by Kießling [12], which in turn serves as the foundations for the preference model presented in Sec. 3.1. Applied to SWS discovery and ranking scenario, there are some approaches in the literature [9,14], though their preference model is essentially based on utility functions. 1http://sws-challenge.org Additionally, their model is coupled with their actual implementation of discovery and ranking, consequently limiting their expressiveness. A more comprehensive comparison and overview of these approaches can be found in [7]. Other proposals to model preferences on SWS are more focused on ranking mechanisms, so their preference model are specifically tailored towards their implementations. Toma et al. [22] presents a multi-criteria approach based on logic rules, modeling preferences by including simple annotations to wsmo goals, in a similar fashion as policies defined in Palmonari et al. [17], though they provide more facilities to express relative weights and different offered policies. Garc´ıa et al. [8] provide means to semantically define preferences as utility functions, integrating both logic rules and constraint programming to rank services with respect to those preferences. Finally, a hybrid approach to SWS ranking is proposed by Kerrigan [11], where preferences are described using instances from an ontology, as in our proposal, while distinguishing filtering and ordering preferences that are used at different stages of his solution. 3 Defining an Ontology of User Preferences In the following, an ontology representing our proposed preference model is presented in detail. In order to validate this model, an application to the Logistics Management scenario from the SWS Challenge2is also discussed. Finally, we depict how to extend wsmo framework so that users can define their preferences inside wsmo goals. 3.1 User Preferences Model As discussed before, service descriptions and user preferences should be semantically described at the same detail level. Therefore, there is a need for the definition of an ontological model that leverages preference descriptions as first-class citizens in the discovery and ranking scenario. This model has to provide intuitive and user-friendly facilities to easily define both requirements and preferences, so that service descriptions can be matched with user requests. Furthermore, these facilities have to conform a sufficiently expressive model so that a user can describe any kind of preference, without being limited by a concrete formalism or representation. In order to specify a preference model, firstly we need to establish a clear separation between requirements that have to be met, and preferences that have to be taken into account once requirements have been fulfilled. Typically, requirements are hard constraints that are used to filter service repositories in the discovery process, while preferences are used to rank previously discovered services so that the most appropriate service can be selected after the ranking process. Therefore, preferences define a strict partial order in our model, providing a framework to compare and rank a set of services. 2 The complete scenario description can be found at http://sws-challenge.org/wiki/index.php/Scenario:_Logistics_Management UserRequest Property refersTo RequirementTerm hasRequirements PreferenceTerm 0..1 hasPreference refersTo PropertyValue ofType hasOperands hasOperands Fig. 1. Upper ontology of user preferences Figure 1 shows the upper ontology of our model, which is represented using a UML-based notation for OWL ontologies [2] that is also used throughout the rest of the paper. The root concept in our proposed model is called UserRequest, which consists on the materialization of user desires with respect to a particular service request. These desires are described using RequirementTermsand possibly a PreferenceTerm. Thus, hard requirements are defined by instances of subclasses of RequirementTerm, and the same applies to PreferenceTerm.Both requirements and preferences are related with one or more properties, which are referred inside each term, and with some property values that act as operands for each term specialization. Properties and property values depend on the specific domain being used within each scenario, so instances (or specializations) of Property and PropertyValue classes may be probably described using an external domain ontology. Requirements definition has been widely discussed in the literature, and SWS frameworks provide sufficiently expressive facilities to define them, so in the following we will focus on preference modeling. In Sec. 3.2, requirement terms are simply considered as property / property value pairs, which is sufficient to describe user requests in the validation scenario. Concerning preferences, Fig. 2 presents the middle ontology of our model, where a hierarchy of available preference constructors is introduced. Thus, a preference term can be an AtomicPreference, or a composition of two preference terms by applying one of the sub-classes of CompositePreference.On the one hand, atomic preferences are those which refers to a single property, and can describe either a qualitative or a quantitative preference that users may have with respect to the referred property. On the other hand, composite preferences relate different preferences between them, so that a complex preference can be described. These complex constructors are defined for two preferences in our model, though they can be generalized to a greater number of preferences obviously. Each preference construct from Fig. 2 is defined intuitively in the following, including a motivating example described in natural language from the SWS Challenge scenario used to validate our proposed model in Sec. 3.2, where some of these constructs are applied to describe that scenario goals. A formal definition of the described preference terms can be found at [12], where the foundations of our model are thoroughly discussed. AtomicPreference FavoritesPref QualitativeAtomicPreference QuantitativeAtomicPreference PreferenceTerm CompositePreference 1hasLeftTerm 1hasRightTerm DislikesPref FavoritesDislikesPref FavoritesAlternativePref ExplicitPref AroundPref BetweenPref LowestPref HighestPref ScorePref ParetoPref PrioritizedPref NumericalPref RealFunction 1 hasCombiningFunction 1 hasScoringFunction Fig. 2. Preference terms hierarchy Qualitative atomic preferences. The first group of preferences presented in the following corresponds to the qualitative and atomic constructs, which means that every preference that belongs to this kind refers to a single, non-numerical property. a) Favorites preference - FavoritesPref Afavorites preference defines a finite set of property values that constitute the desired values of the referred service property. Thus, services whose value for that property is a member of the favorite set are preferred to services that provide any other values from the property domain. An instance of this preference constructor has many operands as the cardinality of the favorite values set. Example: I prefer WSs that provide carriageForward as a possible PaymentMethod3. b) Dislikes preference - DislikesPref As opposite to FavoritesPref,adislikes preference define a set of property values that the service should not provide for the referred property in order to be preferred to another service whose property values coincide with any of the values in the associated dislikes set. Example: I prefer WSs that do not offer refundForDamage as an available Insurance option. 3In each example, italics text correspond to property values used as operands, while typewriter text are used to denote properties. c) Favorites or alternative preference - FavoritesAlternativePref Afavorites or alternative preference is an extension of FavoritesPref, where there are two favorite sets. The second set is called alternative set. In this case, services whose property values are in the favorite set are the most preferred. Otherwise their values should be on the alternative set. If this is not the case either, then the corresponding services will be undesirable, because their property values are not member of any of the two sets. In order to differentiate between favorite and alternative set, hasOperands object property has to be specialized to two different object properties, namely hasFavorite and hasAlternative. Example: IpreferWSswhosePaymentMethod is carriagePaid, but if that is infeasible, then it should be carriageForward. d) Favorites or dislikes preference - FavoritesDislikesPref It is also possible to combine FavoritesPref with DislikesPref in the following form: service properties should have a value on the defined favorite set. Otherwise, values should not be from the dislikes set. If none of these two conditions hold, then the service will be less preferred than others fulfilling the first or the second condition. Again, hasOperands is specialized for this preference constructor to hasFavorite and hasDislikes object properties. Example: I prefer WSs that provide refundForLoss as a possible Insurance, but if that is infeasible, then it should not be refundForDamage. e) Explicit preference - ExplicitPref An explicit preference can be used to explicitly represent the strict partial order between a pair of property values. Thus, a better-than graph can be defined using several explicit preferences.Inthiscase,hasOperands is specialized to hasLeftOperand and hasRightOperand, meaning that the left operand value is better than the right operand value, with respect to the referred property. Example: WSs that provide carriageForward as a possible PaymentMethod are more preferred than those that provide carriagePaid. Quantitative atomic preferences. When the referred property of an atomic preference is numerical, the following quantitative constructs may be used to express user preferences on that single property. a) Around preference - AroundPref An around preference determines which property value is better by determining the distance of each values to a concrete value provided as an operand of this preference term. Thus, services which provide exactly that value are preferred to the rest of them. If this is infeasible, services with closer values to the operand are preferred. Example: I prefer WSs that provide a BasePrice closer to 180 Euros. b) Between preference - BetweenPref In this case, a service should have values for the referred property between a range of values that are defined as operands in the preference (hasOperands is specialized to lowBound and upBound). If this is not the case, between preferences prefer services closer to the interval boundaries, computing the distance as in around preferences. Example: I prefer WSs that provide a PaymentDeadline within the interval of [45,60] days. c) Lowest preference - LowestPref Alowest preference does not have any operand, but prefer services whose property values are as low as possible for the referred service property. Example: I prefer WSs that provide a BasePrice as low as possible. d) Highest preference - HighestPref In opposition to the last constructor, a highest preference is used when property values should be as high as possible. Example: I prefer WSs that provide a PaymentDeadline as long as possible. e) Score preference - ScorePref Ascore preference basically defines a scoring function (i.e. a utility function like in [8]) that takes a property value as its argument and returns a real value that can be interpreted in the following form: the higher the value returned by the function is, the more preferred the property value entered as the argument. Note that this kind of preference is not as intuitive as the rest, but it is still useful when a user wants to express complex grades of preference, using for instance a piecewise function depending on the property values. Example: I prefer WSs with the highest score with respect to Price/Kg,where the scoring function is defined as: f(priceP erKg)= −1 50 priceP erKg +1. Composite preferences. The last group of preference constructs are used to compose two different preference terms by stating the preference relationship between each component term, which can be also a composite preference. Composite preferences refersTo property associate the preference with the union of the properties referred by component preferences. a) Pareto preference - ParetoPref Apareto preference P combines two preference terms P1 and P2 using the Pareto-optimality principle, which considers that P1 and P2 are equally important preferences. Thus, a service SWS1is better than another service SWS2with respect to P, if SWS1is better than SWS2with respect to P1 and SWS1is not worse than SWS2with respect to P2, and vice versa.Note that P1 is linked with P using the hasLeftTerm object property, and P2 using the hasRightTerm object property. Intutively, this preference balance the fulfillment of each preference component, so that the composite preference is the average degree of preference taking both components into account. Example: Cf. Fig. 6 for a use case of a pareto preference. b) Prioritized preference - PrioritizedPref In the case of a prioritized preference P that compose two preference terms P1 and P2, P1 is considered more important than P2. Thus, P2 is evaluated only if P1 does not mind (i.e. service property values compared using P1 do not return enough information to rank those services). Example: Cf. Fig. 4 for a use case of a prioritized preference. c) Numerical preference - NumericalPref Finally, a numerical preference is the combination of two score preferences using a function that takes the values returned by the score preferences as its arguments and returns another real number that gives information about the global preference, considering all the properties referred by concrete score preferences. Notice that component preferences must be score preferences in order to properly compose them using a combining function. Example: Provided that f(baseP rice)andg(priceP erKg) are already defined and they range within the interval [0,1], I prefer WSs that have a higher combined score, where the combining function is defined as: combF (baseP rice, priceP erKg)=0.8∗f(baseP rice)+0.4∗g(priceP erKg). 3.2 Validating the Model The proposed preference model has been validated using one of the discovery scenarios from SWS Challenge. Concretely, the chosen one has been the Logistics Management scenario, because of its complexity and the inclusion of preference descriptions. It consists on seven logistics service offers, described in natural language in terms of different properties, such as price, covered geographical areas, operating hours and truck fleets, among others. Additionally, several service requests (i.e. user goals) applicable to this scenario are defined, which contain both hard requirements and user preferences (they are referred as soft constraints in the scenario) that can be used to choose the most appropriate service (i.e. the best one in terms of preferences) among those which fulfill hard requirements. In the chosen scenario, goals B1, C1, D1 and E1 define a variety of preferences against different service properties, in addition to describe how preferences should be combined within each goal. In order to validate our preference model using this scenario, we provide in the following equivalent descriptions for each of these goals using the proposed model. Thus, textual descriptions of goals directly extracted from the scenario description are shown alongside their equivalent representation using the preference ontology presented in Sec. 3.1. For the sake of simplicity, service properties are included as instances inside the same default namespace as the goal, though a domain ontology should be externally defined, covering all the existing properties in the Logistics Management domain. Figure 3 presents the instantiation of the goal B1 from the scenario. The goal as a whole is modeled with an instance of UserRequest, while each term is instantiated depending on its nature. Thus, requirements about pickup, delivery and transported goods are represented at the top of the figure. This representation is shown simplified, because requirements in every goal from the Logistics Management scenario are pairs between domain properties and their values. Consequently, in the following instantiated goals, requirements are omitted from the representation, though they can be easily described using property-value pairs. Concerning the preference modeling, goal B1 states that the user prefers two properties, namely PaymentMethod and Insurance, to contain certain values, GoalB1 : pref::UserRequest RQ1 : pref::RequirementTerm RQ5 : pref::RequirementTerm PickUpDateTime : pref::Property Good : pref::Property 3rdNovemberDateT ime : pr ef::Proper tyValue refersTo hasOperands ofType SC1 : pref::FavoritesPref SC2 : pref::FavoritesPref carriageFor ward : pref::PropertyValue RefundF orDamage : pr ef::Pr opertyValue PaymentMethod : pref::Property Insurance : pref::Property Preference : pref::ParetoPref RomanCandles : pref::PropertyValue ofTyperefersTo hasOperands hasPreference refersTo hasLeftTerm hasRightTerm ofType hasOperands refersTo refersTo hasOperands ofType hasRequirement ... RQ1 - Pickup date&time: 03/09/2008 18 :00 RQ2 - Pickup location: Avinguda Diagonal 338, 08013, Barcelona (Spain) RQ3 - Delivery date&time: 04/09/2008 09:30 RQ4 - Delivery location: Calle del General Ricardos 176 , 28025, Madrid (Spain) RQ5 - Good: Roman candles (70 mm of inner diameter without flash composition ) Preference - I prefer WSs that provide the following properties SC1 - PaymentMethod: carriageForward SC2 - Insurance: RefundForDamage Fig. 3. Goal B1 description excerpt and its representation using our model carriageForward and refundForDamage, respectively. Both of these soft constraints are considered qualitative preferences that define the favorite values for each property. However, the preference description do not explicitly express how to compose those two atomic preferences, so it can be inferred that a pareto preference canbeappliedtorelateeachone,because both atomic preferences can be considered equally important for the user. The next goal used to validate our model is shown in Fig. 4. In this case, the atomic preferences defined in C1 are instantiated as a favorites preference and an around preference. Moreover, the preference description gives more importance to the favorites preference on the PaymentMethod property, taking GoalC1 : pref::UserRequest SC1 : pref::FavoritesPref SC2 : pref::AroundPref carriageFor ward : pr ef::Pr opertyValue 180 : pref::PropertyValue PaymentMethod : pref::Property BasePrice : pref::Property Preference : pref::PrioritizedPref hasPreference refersTo hasLeftTerm hasRightTerm ofType hasOperands refersTo refersTo hasOperands ofType Requirements … Preference - I Prefer WSs that best fit the soft constraint on Payment method . In the case of equal satisfaction degree , I prefer WSs whose Base Price are closer to the value expressed in the soft constraint. Based on the consideration that cheap prices occasionally do imply lower service quality, I explicitly do not ask for the cheapest base price . SC1 - PaymentMethod: carriageForward SC2 - Base Price: close to 180 Euro Fig. 4. Goal C1 description excerpt and its representation using our model