# semantic matchmaking as non-monotonic reasoning a description logic approach[精选推荐pdf]

Journal of Artificial Intelligence Research 29 2007 269-307ted 8/06; published 7/07Semantic Matchmaking as Non-Monotonic Reasoning A Description Logic ApproachTommaso Di Noiat.dinoiapoliba.it Eugenio Di Sciasciodisciasciopoliba.it SisInfLab - Politecnico di Bari, Bari, ItalyFrancesco M. Doninidoniniunitus.it Universit a della Tuscia, Viterbo, ItalyAbstractMatchmaking arises when supply and demand meet in an electronic marketplace, or when agents search for a web service to per some task, or even when recruiting agenciesmatch curricula and job profiles. In such open environments, the objective of a matchmak-ing process is to discover best available offers to a given request. We address the problem of matchmaking from a knowledge representation perspective, with a alization based on Description Logics. We devise Concept Abduction and Con- cept Contraction as non-monotonic inferences in Description Logics suitable for modeling matchmaking in a logical framework, and prove some related complexity results. We also present reasonable algorithms for semantic matchmaking based on the devised inferences, and prove that they obey to some commonsense properties. Finally, we report on the implementation of the proposed matchmaking framework, which has been used both as a mediator in e-marketplaces and for semantic web services discovery.1. IntroductionThe promise of the Semantic Web initiative is to revolutionize the way ination is coded, stored, and searched on the Internet Berners-Lee, Hendler, but once they are reulated in a comparable way, one is still left withthe basic matchmaking problems given a request, are there compatible offers If there areseveral compatible offers, which, and why, are the most promising ones Matchmaking has been widely studied and several proposals have been made in the past;we report on them in Section 2. Recently, there has been a growing effort aimed at the alization with Description Logics DLs Baader, Calvanese, Mc Guinness, Nardi, Trastour, Bartolini, Sycara, Widoff, Klusch, Di Noia, Di Sciascio, Donini, Li Di Noia, Di Sciascio, Donini, some way to rank most promising ones has to be identified; also some explanation on motivation of such a rank could be appreciated. On the other hand, when there is lack of compatible matches one may accept to turn to incompatible matches that could still be interesting, by revising some of the original requirements presented in the request, as far as one could easily identify them. In other words some is needed to provide a logic-based score for both compatible and incompatible matches and eventually provide a partial/full ordering, allowing a user270Semantic Matchmaking as Non-Monotonic Reasoning A Description Logic Approachor an automated agent to choose most promising counteroffers. Furthermore it should be possible, given a score, to provide logical explanations of the resulting score, thus allowingto understand the rank result and ease further interaction to refine/revise the request. Although this process is quite simple for a human being it is not so in a logic-based fullyautomated framework. We believe there is a need to define non-monotonic reasoning services in a DLs setting, to deal with approximation and ranking, and in this paper we propose the use of Concept Abduction Di Noia et al., 2003a and Concept Contraction Colucci, Di Noia, Di Sciascio, Donini, Concept Abduction as a logical basis for ranking compatible counteroffers to a givenoffer and provide logical explanations of the ranking result; Concept Contraction as a logical basis for ranking incompatible matches, aimed at discovering most promising “near misses”, and provide logical explanations of the ranking result; algorithms implementing the alized inferences for matchmaking purposes and complexity results for a class of matchmaking problems; description of our system implementing semantic matchmaking services, and experi- mental uation.The remaining of the paper is structured as follows next Section reports on backgroundwork on the subject. Then Section 3 we briefly revise Description Logics basics. To make the paper self-contained we recall Section 4 our logic-based framework for matchmaking, pointing out properties that matchmaking algorithms and systems should guarantee. In Sections 5 and 6 we present Concept Abduction and Concept Contraction, the two inferenceservices we devised to compute semantic matchmaking, and present suitable definitions of the problem along with some complexity results. Then in Section 7 we describe our matchmaker, and present Section 7.1 an uation of results computed by the system compared with human users behavior, and with a standard full text retri approach. Conclusions close the paper.2. Related Work on MatchmakingMatchmaking has been investigated in recent years under a number of perspectives and fordifferent purposes, with a renovated interest as the ination overload kept growing with the Web widespreading use. We try here to summarize some of the relevant related work.Vague query answering, proposed by Motro 1988, was an initial effort to overcome limi- tations of relational databases, using weights attributed to several search variables. More recent approaches along these lines aim at extending SQL with ”preference” clauses, in order to softly matchmake data in structured databases Kießling, 2002. Finin, Fritzson, McKay, and McEntire 1994 proposed KQML as an agent communication language ori- ented to matchmaking purposes. Kuokka and Harada 1996 investigated matchmaking271Di Noia, Di Sciascio the approach used KQML, and LOOM as description language. LOOM is also used in the subsumption matching addressed by Gil and Ramachandran 2001. InfoSleuth Jacobs Paolucci, Kawamura, Payne, some DL include also disjunction ⊔ and complement ¬ to close concept expressions under boolean operations. Roles can be combined with concepts using existential role quantificatione.g., Computer ⊓ ∃hasSoftware.WordProcessorwhich describes the set of computers whose software include a word processor, and273Di Noia, Di Sciascio for every inclusion A ⊑ C, replace A with A⊓C in every concept. Clearly, such a process trass every concept into an equivalent one, where the TBox can be forgotten. However, for some TBoxes, unfolding can yield concepts of exponential size w.r.t. the initial concepts. When such an exponential blow-up does not happen, we call the TBox “bushy but not deep” Nebel, 1990. The semantics of axioms is based on set containment and equality an interpretation Isatisfies an inclusion C ⊑ D if CI⊆ DI, and it satisfies a definition C ≡ D when CI DI. A model of a TBox T is an interpretation satisfying all axioms of T . Observe that we make a distinction between equivalence ≡ used in axioms and equality symbols. We use equality to instantiate generic concept symbols with the concepts they stand for, e.g., when we write “... where C A ⊓ ∀R.B...” we mean that the concept symbol C stands for the concept expression A ⊓ ∀R.B in the text.3.3 Reasoning ServicesDL-based systems usually provide two basic reasoning services1. Concept Satisfiability given a TBox T and a concept C, does there exist at least onemodel of T assigning a non-empty extension to C We abbreviate satisfiability of a concept C w.r.t. a TBox T as C 6⊑T⊥.2. Subsumption given a TBox T and two concepts C and D, is CIalways contained in DIfor every model Iof T We abbreviate subsumption between C and D w.r.t. T as C ⊑TD.Since C is satisfiable iffC is not subsumed by ⊥, complexity lower bounds for satisfiability carry over for the complement class to subsumption, and upper bounds for subsumptioncarry over to satisfiability. On the other hand, since C is subsumed by D iffC ⊓ ¬D isunsatisfiable, subsumption is reducible to satisfiability in DLs admitting general concept negation, but not in those DLs in which ¬D is outside the languageas in the DLs of the next Section.3.4 The System ClassicThe system Classic Borgida, Brachman, McGuinness, Borgida Donini, 2003. For simplicity, we only consider a subset of the constructs, namely, conjunction, numberrestrictions, and universal role quantifications, summarized in Table 1. We abbreviate the conjunction ≥ n R ⊓ ≤ n R as n R. We omit constructs ONE-OF·, FILLS·,·that refer to individuals, and construct SAME-AS·,· equating fillers in functional roles.The subset of Classic we refer to is known as ALN Attributive Language with unqualified Number restrictions Donini, Lenzerini, Nardi, Donini et al., 1997b. For more expressive DLs, Concrete Domains Lutz, 1999 should be employed to represent such quantities.4. Semantic Matchmaking Using Description LogicsMatchmaking is a widely used term in a variety of frameworks, comprising severalquitediff erentapproaches. We begin this Section trying to provide a generic and sound defini- tion of matchmaking.Matchmaking is an ination retri task whereby queries a.k.a. de- mands and resources a.k.a. supplies are expressed using semi-structured data in the of advertisements, and task results are ordered ranked lists of thoseresources best fulfilling the query.This simple definition implies thatdifferently from classical unstructured-text Ination Retri systemssome structure in the advertisements is expected in a matchmaking278Semantic Matchmaking as Non-Monotonic Reasoning A Description Logic Approachsystem, and matchmaking does not consider a fixed database-oriented relational structure. Furthermore, usually database systems provide answers to queries that do not include a relevance ranking, which should be instead considered in a matchmaking process.Semantic matchmaking is a matchmaking task whereby queries and resourcesadvertisements are expressed with reference to a shared specification of a con- ceptualization for the knowledge domain at hand, i.e., an ontology.From now on, we concentrate on semantic matchmaking in marketplaces, adopting specific terminology, to ease presentation of the approach. Nevertheless our approach applies to generic matchmaking of semantically annotated resources.We note that all definitions in this Section apply to every DL that can be used to describe a marketplace supplies, demands, background knowledge. We denote by L such a generic DL. We suppose that a common ontology for supplies and demands is established, as a TBox T in L.Now a match between a supply and a demand could be uated according to T . First of all, we remark that a logic-based representation of supplies and demands calls for generally Open-world descriptions, that is, the absence of a characteristic in the descrip- tion of a supply or demand should not be interpreted as a constraint of absence. Instead,it should be considered as a characteristic that could be either refined later, or left openif it is irrelevant for a user. Note that by “generally open” we mean that some specific characteristic might be declared to be closed.However, such a closure should be made piecewise, using some known declarative tool devised in Knowledge Representation for non- monotonic reasoning, such as Defaults in DLs Baader Gonzales- Castillo et al., 2001. full match Sup ⊑TDem, which amounts to the demand being completely fulfilled by the available supply, i.e., Sup has at least all features required by Dem, but not necessarily vice versa, being the matchmaking process not symmetric Di Noia et al., 2003c; this kind of match is also named subsume match by Li and Horrocks 2003. plug-in match Dem ⊑TSup; it corresponds to demand Dem being sub-concept ofsupply Sup,i.e., Dem is more specific than Sup Sycara et al., 2002; Li delete ≤ x R from K; 6.for each concept ∀R.F ∈ Kall if there exist ∀R.E ∈ Dalland either ≥ x R ∈ K♯with x ≥ 17. For readers that are familiar with the concept-centered normal of concepts Baader et al., 2003, we note that ΠAB is a word for UAin the concept-centered normal of B.292Semantic Matchmaking as Non-Monotonic Reasoning A Description Logic Approachor ≥ x R ∈ D♯with x ≥ 1 then let hG′,K′i be the result of findContractF,E in G G ⊓ ∀R.G′; replace ∀R.F in K with ∀R.K′; 7.return hG,Ki; end.Let us comment on the algorithm1. the case in Step 1 cannot occur at the top level, since we assumed C and D be satisfi-able in the definition of CCP. However, ⊥ may occur inside a universal quantificatione.g., C ∀R.⊥hence, the case of Step 1 may apply in a recursive call of findContract, issued from Step 6 of an outer call.2. in Step 2, the conjunction ⊤ ⊓ C is assigned to K in order to leave ⊤ in K if every other concept is removed by the subsequent steps.We denote by hG∅,K∅i solutions for the CCP Q∅ hALN,CNFC,T ,CNFD,T ,∅i. Inthis simplified CCP Q∅, we completely unfold T in both C and D and then forget it.Theorem 4 The pair hG,Ki computed by findContractC,D is a number-restriction- minimal contraction for Q∅ hALN,CNFC,T ,CNFD,T ,∅i.Proof.We first prove that hG,Ki is a solution for Q∅, namely, that i G ⊓ K ≡ C,and that ii K ⊓ D is satisfiable. We prove i by induction. For the base cases, observe that the claim is true in Step 2 by construction, and that in Steps 3–5 when a conjunct is deleted from K, it is also added to G. Hence the claim holds when no recursive call is made. For the inductive case, assume the claim holds for each recursive call in Step 6, that is, G′⊓K′≡ F for every concept ∀R.F ∈ Kall. Let Gn, Knbe the values of variables G,K before the cution of Step 6, and let K−nbe the concept Knwithout ∀R.F. Then, after Step 6 it is G ⊓ K by assigment Gn⊓ ∀R.G′⊓ K−n⊓ ∀R.K′≡by definition of ∀ Gn⊓ K−n⊓ ∀R.G′⊓ K′ ≡by inductive hypothesis Gn⊓ K−n⊓ ∀R.F ≡by definition of K−n Gn⊓ Kn≡since the base case holds before Step 6 C Regarding ii, the proof is again by induction, where the inductive hypothesis is that K′⊓ E is satisfiable. Basically, we construct an interpretation ∆,·I with an element x such that x ∈ K ⊓DI, and show that we can keep constructing I without contradictions, since contradicting concepts have been deleted from K. In the inductive case, we assume the existence of an interpretation ∆′,·J for K′⊓E such that y ∈ ∆′∩K′⊓EJ, and then build a joint interpretation ∆′′,·I′′ by letting ∆′′ ∆U∆′,I′′ I ∪ J ∪ {hx,yi ∈ RI′′}.We now prove that hG,Ki is a number-restriction-minimal solution for Q∅. The proofis by induction on the Quantification Nesting QN of C, defined in Section 3.1. Observethat an at-least restriction is deleted from K only in Step 4 of findContract. For the base caseQNC 0, no recursive callobserve that the role path of a retracted concept293Di Noia, Di Sciascio ALN concepts C, D, both already in CNF output a penalty for the partial match between C and Dwhere zero means that C ⊓ D is satisfiable variables integer n begin 1.if C ⊥ then return |D|