Re: Questions about subsumption relationships for matchmaking

On May 12, David Martin writes:
> Hi Ian -
> 
> Thanks for your response.  My comments are all the way at the bottom - and I
> do solicit further discussion on this important topic.
> 
> Ian Horrocks wrote:
> 
> > On April 29, David Martin writes:
> > > Hello Lei and Ian -
> > >
> > > As you know, we had some brief discussion at the SWSI F2F meeting in
> > > Miami, having to do with effective matchmaking using advertisements and
> > > queries expressed in description logic (in particular, expressed using
> > > the DAML-S Profile Ontology).  Some concerns have been raised about
> > > possible cases where an advertisement contains too much information, so
> > > that it precludes a DL reasoner from finding a subsumption relationship.
> > >
> > > This is a very central topic, it seems to me, for the successful use of
> > > DAML-S (and the soon to be released OWL-S) profiles.  The DAML-S
> > > coalition members are very keen to understand this issue.  So I'd like
> > > to get the ball rolling with a brief request for clarification.
> > >
> > > I've read your recent paper, "A software framework for matchmaking based
> > > on Semantic Web technology", available here:
> > >
> > > http://www.cs.man.ac.uk/~horrocks/Publications/download/2003/p815-li.pdf
> > >
> > > The point is made there that there may be "too much information inside
> > > the service profile, and this makes it difficult to use automated
> > > reasoning techniques to compute Semantic matches between service
> > > descriptions".  (For those who haven't seen the paper, I should say this
> > > is just one relatively minor point in a broad and interesting paper.)
> > >
> > > Anyway, I'm afraid I'm not convinced of the difficulty yet.  This may be
> > > because I've never studied DL subsumption thoroughly.  So the purpose
> > > here is just to get clarification of the problem.
> > >
> > > Here is a simplified version of your example:
> > >
> > > Advert1 =
> > >   ServiceProfile ^
> > >   (Sales ^
> > >    forall[providedBy].(Actor ^ forall[hasName].Georgia) ^
> > >    ...)
> > >
> > > Query1 =
> > >   ServiceProfile ^
> > >   (Sales ^
> > >    forall[providedBy].(Actor ^ hasCreditLevel >= 5) ^
> > >    ...)
> > >
> > > Now, it seems clear to me, as the paper states, that Query1 is *not*
> > > subsumed by Advert1, because the {set of actors with credit level >= 5},
> > > specified in Query1, may certainly include actors that aren't named
> > > Georgia.  And thus, Query1 may well have values of providedBy that
> > > Advert1 doesn't have, and so Advert1 can't subsume Query1.
> > >
> > > But, it seems to me that simply by modifying Query1 as follows, it would
> > > then be subsumed by Advert1:
> > >
> > > Query1A =
> > >   ServiceProfile ^
> > >   (Sales ^ forall[providedBy].(Actor ^ forall[hasName].BOTTOM ^
> > >                                        hasCreditLevel >= 5) ^
> > >    ...)
> > >
> > > It seems to me that adding forall[hasName].BOTTOM means that Query1A is
> > > subsumed by Advert1.  (If you'd like me to justify this statement before
> > > you respond, just let me know, but in the interest of brevity I won't do
> > > so now.)
> > >
> > > If it's true that Query1A is subsumed by Advert1, that suggests to me
> > > that it could be quite easy in practice to avoid the problem that's been
> > > raised.  I could explain further, but I'd rather not get ahead of
> > > myself.  Could I first just ask you to confirm whether or not Query1A is
> > > subsumed by Advert1?  (And of course feel free to make any other
> > > clarifying remarks you'd like.)
> >
> > It is certainly true that forall[hasName].BOTTOM is subsumed by
> > forall[hasName].C for any class C (including Georgia, which is this
> > context probably should have been written {Georgia}, meaning "the
> > class whose only instance is Georgia"). This isn't really a general
> > solution to the problem though:
> >
> > 1. Adding forall[hasName].BOTTOM would rule out subsumption
> > relationships that might otherwise have held w.r.t. advertisements
> > that simply do not specify the name of the provider.
> >
> > 2. There may be lots of additional information, as in the case of
> > Advert1, (more specific forms of) which would also need to be added to
> > the query. In some cases this may not be appropriate (you may end up
> > getting spurious matches).
> >
> > Regarding this 2nd point, I have to say that the example is not well
> > chosen as an illustration of the point about "providedBy", because
> > Advert1 and Query1 specify 2 different PC features (memory and
> > processor) which mean that they would not be in a subsumption
> > relationship even if neither mentioned the provider. If, however, the
> > PC specification in a query was identical or more general than that in
> > an advertisement, then one would like to find an exact or subsume
> > match respectively. This would not happen if forall[hasName].BOTTOM
> > were added to the query.
> >
> > Our "solution" was to separate parts of the service profile that are
> > almost certainly not of interest in the matching phase so they could
> > be ignored by the subsumption based matcher. This does not, however,
> > address the wider problem that is illustrated by the example - the
> > fact that it may very often be the case that, even after discarding
> > these "irrelevant" parts of the descriptions", advertisements and
> > queries will not be in subsumption relationships, but satisfy only the
> > very weak "intersection" matching condition (i.e., their intersection
> > is not a contradiction). This is because advertisers and queriers may
> > choose to be more specific about different aspects of the description
> > (memory and processor in this example).
> >
> > Regards, Ian
> 
> Yes, this is a good restatement of the point you brought up in Miami.
> 
> But it still doesn't seem clear to me that this is a significant problem.
> That is, it seems to me there's a perfectly reasonable, natural way of using
> DL to perform matchmaking that avoids this problem.  I think it just requires
> the following conventions:
> 
> (1) An advertiser expresses a class of services using an expression that's as
> *general* as possible.
> 
> (2) A requester expresses a query for a service desired using an expression
> that's as *specific* as possible.

Well, these two conditions might be seen as a rather severe
restriction on the matchmaking service. The first places a heavy
burden on advertisers to decide how general is "as general as
possible", and it may make the service less useful to clients by
discouraging advertisers from providing information that would enable
clients to make a more informed choice of service. The second requires
clients to know a lot of detail about the service they require. This
may be OK in some use cases, but not in others - what if a client
prefers, or is only able, to vaguely describe the required service,
and would like to "browse" more specific advertisements for
information about the kinds of service that are available?


> (3) When a requester doesn't care about how a particular property is
> restricted, his query expresses "don't care" for that property, using
>     forall[property].BOTTOM
> as in my proposed reformulation of the example query.

This doesn't really work. An advertisement offering Dell laptops might
include "laptop ^ exists[manufacturer].Dell". This does not subsume
"laptop ^ forall[manufacturer].BOTTOM". 

Is it supposed to be the case that adding "exists[manufacturer].Dell"
is too specific? If so, then the matchmaking service would be
seriously weakened. E.g., if I requested a laptop not manufactured by
Dell, then I would still be offered this service. As an advertiser I
might worry that even laptop is too specific - should I just say
computer, or maybe even consumer-electronics.


> It seems to me these conventions add up to a very natural approach to
> knowledge representation for service matchmaking -- at least for the most
> normal, familiar kind of matchmaking.  That is, an advertiser normally
> advertises his services in the most general way possible (think of the Yellow
> Pages), and a service-seeker normally describes what he wants to accomplish,
> in a particular use of a service, in the most specific way possible.  A
> matchmaker that's tailored to answer whether queries meeting convention (2)
> above are subsumed by advertisements meeting convention (1) may not support
> every conceivable kind of matchmaking, but it seems to me an extremely useful
> approach that supports the most mainstream kind.

But isn't yellow pages exactly the kind of matchmaking we *don't* want?
- i.e., a flat list of services where the client simply chooses the
required service from the list and is presented with an
undistinguished list of matches. I agree that a matchmaker of this
kind may satisfy some requirements, but its functionality is rather
restricted, and there are associated problems such as the ones I
mentioned above.


> Under these conventions, one is primarily interested in identifying the set of
> advertisements that subsumes a given query.  Those are the advertisements that
> most effectively identify the candidate service providers.   But one can still
> test for cases in which an advertisement and query are merely compatible, and
> for cases in which the query subsumes the advertisement - and if such cases
> are identified, one can use that knowledge to make reasonable choices about
> whether and how to use those cases.

This assumes a lot about the matchmaking process. E.g., in my laptop
purchase scenario I might request "laptop" and still be interested in
advertisements from sites selling only a given manufacturers
laptops. If, however, I specified a price constraint, and the
advertisement did not, then my request wouldn't subsume the
advertisement either. Compatible is so weak as to be relatively
useless - my request may be compatible with a *very* large number of
advertisements. (This last point could be mitigated to some extent by
ensuring that the ontology constraints disjointness axioms w.r.t. all
incompatible sibling categories.)


> 
> I've been going around telling people that service matchmaking *is*, in fact,
> a very natural application of DL subsumption, so I'm very keen to know if I've
> been lying or not :-).  I'd certainly like to get your comments (as well as
> others') about whether the use of DL under conventions (1) - (3) will work
> well for (what seems to me) the most normal, mainstream kind of matchmaking.
> At the moment I don't see why it wouldn't!

Of course I believe that DL reasoning is also very natural for
matchmaking. There do, however, seem to be some potential problems, as
outlined above, with the use of simple subsumption
reasoning. Hopefully we can iron these out. One possibility might be to
use more sophisticated reasoning tasks such as query answering.

Regards, Ian


> 
> Regards,
> David
>

Received on Monday, 19 May 2003 04:06:11 UTC