W3C home > Mailing lists > Public > www-ws@w3.org > May 2003

[Fwd: Re: Questions about subsumption relationships for matchmaking]

From: David Martin <martin@ai.sri.com>
Date: Wed, 21 May 2003 23:55:51 -0700
Message-ID: <3ECC7477.B6CD3AA4@ai.sri.com>
To: www-ws@w3.org

Hi again Ian -

And thanks again for your comments, which have been very helpful.  more
below ...

Ian Horrocks wrote:

> 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.

I see your point, but at the same time I don't really see this
requirement as a heavy burden.  Sure, for any knowledge
representation/reasoning scheme to work well, the people who instantiate
the knowledge have to do a reasonably good job.  That goes for any style
of KR, from a desktop Rolodex to a PocketPC calendar thru relational
databases and on up.  But, given a particular ontology with
well-defined, well understood domain-specific properties, I don't think
it's so tricky to describe a service "as generally as possible", while
still remaining accurate.  Maybe advertisers ultimately would need some
guidance to do this well - I don't know- but I don't think it would be a
heavy burden.  As far as discouraging advertisers from providing
information ..., I also think that could be dealt with effectively.  But
all this is, at least for my interests, apart from the main point.

I guess my main concern is to understand how best to employ DL
subsumption for matchmaking purposes.  And my claim (stated somewhat
more carefully than before), is this:

If you want to use subsumption for matchmaking, a promising (and to me
at least, intuitive) conceptual approach can be based on the idea that
each advertiser describes the general space of services that he
provides, and a service seeker describes the particular service instance
(or set of instances) he needs, and the matchmaker finds the
advertisements that subsume the seeker's query.

I'm putting this forward merely as a conceptual starting point, and I
agree that there are difficulties to be addressed, such as you have been
pointing out.  Addressing these needs might ultimately lead to a hybrid
approach.   Also, I'm not claiming that such an approach would
necessarily solve all of the world's matchmaking needs :-).  So I think
we are actually in substantial agreement.  I just want to understand the
difficulties better.  And I don't want to see the baby thrown out with
the bathwater.  (That is, I don't want to see people discarding the idea
that DL subsumption is a good technology for matchmaking, because we can
come up with problematic use cases.)

> 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?

Good points; certainly one would want a matchmaker to support these
situations.  But to my mind, the basic intuition is still valid.  That
is, before the service seeker is done browsing and choosing, he will
have arrived at a query that is subsumed by one or more advertisements
(at least in principle).

>
>
> > (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".

Very good point and example; thanks.  I was just trying to get at some
way by which a query could indicate "don't care" for any given
property.  Clearly my initial idea to use forall[property].BOTTOM
doesn't cut it.

> 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.

I agree.

> 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.

Well, I see your point, but I think that an advertiser who only sells
laptops should - and would have an incentive to - specify "laptop" as
his product category.  Otherwise, he'd wind up having to handle a lot of
inquiries regarding computers that he doesn't offer.  In any case, I
suspect *any* approach to advertising products or services will probably
raise these kinds of issues, and be subject to abuse by advertisers who
are looking for ways to "beat the system".

>
>
> > 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.

Yes, right.  But I didn't mean all of that when I mentioned Yellow
Pages.  I was just pointing out that (seems to me) Yellow Pages
advertisers by and large do follow  my proposed guidelines - they
advertise their Services in the most general way possible, while still
being accurate.

> 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.)

OK, again, no disagreement.  I mainly mentioned the possibility of these
additional modes of matching (query subsumes advertisement and query
compatible with advertisement) mainly because they are mentioned in your
paper, as well as one or two other papers I've read about DL-based
matchmaking :-).

>
>
> >
> > 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.

OK, good summary of the discussion to date!

Regards,
David
Received on Thursday, 22 May 2003 02:55:58 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 3 July 2007 12:25:42 GMT