PaperlayerView exact revision on arXiv

Source-linked AI summary

Semantic Matchmaking as Non-Monotonic Reasoning: A Description Logic Approach

T. Di Noia, E. Di Sciascio, F. M. Donini

arXiv:1110.2742v1cs.AI

TL;DR

Finding the best offers for a request is difficult, and matchmaking needs a way to rank compatible and incompatible matches. This paper formalizes matchmaking in Description Logics using Concept Abduction and Concept Contraction; it reports that its approach empirically simulates commonsense human reasoning.

  • Problem

    Matchmaking must identify and rank promising offers, but finding the best matches between parties is difficult.

    Source: §1 · pp. 1–2

  • Method

    The paper formalizes Concept Abduction and Concept Contraction as non-monotonic Description Logic inferences for ranking and explaining matches.

    Source: §1 · p. 3, §8 · p. 32

  • Results

    The authors report that their logically grounded approach empirically simulates commonsense human reasoning.

    Source: §8 · p. 32

  • Takeaways & Limitations

    In e-marketplaces, partial matches can provide a basis for negotiation over negotiable requirements.

    Source: §6 · p. 21

    The authors identify algorithms for more expressive Description Logics and a tableaux-based system as current research directions.

    Source: §8 · p. 33

Abstract

from arXiv · show

Matchmaking arises when supply and demand meet in an electronic marketplace, or when agents search for a web service to perform some task, or even when recruiting agencies match curricula and job profiles. In such open environments, the objective of a matchmaking process is to discover best available offers to a given request. We address the problem of matchmaking from a knowledge representation perspective, with a formalization based on Description Logics. We devise Concept Abduction and Concept 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. Introduction

Automated matchmaking must rank promising offers and explain those rankings, while also addressing incompatible matches that may be negotiable. The paper proposes a Description Logic framework using Concept Abduction and Concept Contraction to support this process.

1. Introduction

  • The paper focuses on automated matchmaking for marketplaces and service discovery, assuming requests and offers have descriptions that can be compared.Its setup assumes a common ontology; heterogeneous descriptions may first be reformulated to be comparable.Source: §1 · pp. 1–2
  • Matchmaking needs logic-based scores and explanations to rank compatible offers and guide users or agents choosing counteroffers.Rank explanations can help users refine or revise requests.Source: §1 · pp. 2–3
  • The paper presents a logical framework for expressing requests and offers as concepts, alongside properties a matchmaking facilitator should satisfy.The paper also reports a system implementation and an evaluation against human behavior and full-text retrieval.Source: §1 · p. 3
  • The framework uses Concept Abduction to rank compatible counteroffers and explain their rankings, and Concept Contraction to rank incompatible near misses.It also specifies algorithms, complexity results, and properties for the matchmaking inferences.Source: §1 · p. 3

2. Related Work on Matchmaking

Prior matchmaking work spans text retrieval, constraint-based systems, and Description Logic approaches. The paper situates its contribution among DL methods for match classification and ranking, as well as fuzzy and hybrid methods.

2. Related Work on Matchmaking

  • Earlier matchmaking approaches included agent-mediated offer matching, syntactic methods, and unstructured-text retrieval such as SHADE, COINS, and GRAPPA.Other work used KQML, databases, or constraint-based systems.Source: §2 · pp. 3–4
  • DL-based work used satisfiability and subsumption for matching, then extended classification and ranking; other proposals used Concept Difference or Concept Contraction and Abduction.The cited approaches include Trastour et al. (2002), Li and Horrocks (2003), and Colucci et al. (2005).Source: §2 · p. 4
  • Fuzzy-DL and hybrid matchmaking approaches address approximation and ranking, but the paper says they do not provide explanation or automated revision services.Examples named are Smart and OWLS-MX.Source: §2 · p. 5
  • The paper distinguishes matchmaking from DL matching, where variable substitution makes one concept expression equivalent to another.It also says concept rewriting in DLs has no direct relation to matchmaking.Source: §2 · p. 5

3. Description Logics Basics

The section introduces Description Logics and the Classic system, including its ALN subset, TBoxes, and core reasoning services. It outlines how concepts are represented and how the system supports reasoning over them.

3.1 Description Logics

  • Description Logics represent knowledge with concepts and roles, combined through constructors such as conjunction and role quantification.Concepts stand for sets of objects, while roles link objects; conjunction is interpreted as set intersection.Source: §3.1 · pp. 5–6

3.2 TBoxes

  • TBoxes collect concept inclusions and definitions; simple TBoxes use acyclic schemas, whose unfolding can cause exponential growth.A simple TBox is an acyclic schema, and unfolding replaces defined names or adds inclusion consequences to concepts.Source: §3.2 · pp. 6–7

3.3 Reasoning Services

  • Concept satisfiability asks whether a concept can have a nonempty extension, while subsumption asks whether one concept is always contained in another.The section relates the two services through unsatisfiability and subsumption reductions, with language-dependent conditions.Source: §3.3 · p. 7

3.4 The System Classic

  • Classic’s ALN subset uses conjunction, number restrictions, and universal role quantification to represent taxonomies, disjoint groups, and role constraints.ALN omits constructs including union and existential role quantification; the paper selects this subset for its ontology and applications.Source: §3.4 · p. 8
  • Classic normal forms precompute a concept’s implications, while embedding a TBox into concepts can make reasoning exponential in the TBox size.With a fixed TBox, the paper states that the resulting CNF has polynomial size in the concept size.Source: §3.4 · pp. 8–9
  • The paper uses a reference ontology for examples and represents memory quantities with number restrictions in ALN.For more expressive DLs, the text says Concrete Domains should be used to represent such quantities.Source: §3.4 · pp. 9–10

4. Semantic Matchmaking Using Description Logics

The section frames semantic matchmaking as ranking offers described against a shared ontology, with open-world descriptions. It proposes penalty requirements and uses non-standard logical reasoning to address ranking and irrelevance.

4. Semantic Matchmaking Using Description Logics

  • Semantic matchmaking ranks resources against queries using ontology-based descriptions, with offers and counteroffers applying whether the issuer is a supplier or a demander.The framework assumes a common ontology and generally open-world descriptions: an omitted characteristic is not treated as absent.Source: §4 · pp. 11–12
  • The framework distinguishes exact, full, plug-in, potential, and partial matches by equivalence, subsumption, and satisfiability relations.Potential matches have no conflicting characteristics; partial matches contain a conflict and may still be recoverable.Source: §4 · pp. 11–12
  • A matchmaking penalty ranks counteroffers for an offer, with lower penalties preferred and zero penalty ranked best.The ranking is intended to help an issuer decide whom to contact first and whom to consider next if a match fails.Source: §4 · p. 12
  • Penalty functions should be non-symmetric and syntax independent, so direction matters and semantically equivalent descriptions receive equal penalties.The section says penalties should not be expected to behave as metric distances.Source: §4 · p. 12
  • For potential matches, greater specificity should not worsen a counteroffer’s ranking; for partial matches, greater specificity should not improve it.The requirements reverse because adding a characteristic to a conflicting offer may worsen or leave unchanged its ranking.Source: §4 · p. 13
  • The paper turns to non-standard logical reasoning frameworks to define penalties declaratively and handle irrelevance as a byproduct.The motivation is that penalties should remain unchanged when irrelevant details are added to a proposal.Source: §4 · pp. 13–14

5. Concept Abduction

Concept Abduction models potential matchmaking by finding hypotheses that complete compatible offers, then uses those hypotheses to rank and explain potential matches. The section develops irreducible solutions and a penalty function, with complexity and ranking properties for the ALN setting.

5. Concept Abduction

  • A CAP seeks a hypothesis H that keeps C ⊓ H consistent and makes C ⊓ H subsumed by D, modeling potential matchmaking in Description Logics.Unlike Concept Difference, this formulation does not require C ⊑T D, so it also applies when neither concept subsumes the other.Source: §5 · p. 14, §5.2 · p. 21
  • Length-minimal and subsumption-maximal solutions can be incomparable or non-unique; both criteria are included among irreducible solutions when the language admits CNF.Length-minimal solutions depend heavily on T.Source: §5 · pp. 15–16

5.1 Irreducible Solutions in ALN-simple TBoxes

  • For ALN with a simple TBox, findIrred constructs a solution and greedily deletes redundant conjuncts to make it irreducible, but the result need not be minimal.The theorem guarantees irreducibility when the returned concept is not ⊥.Source: §5.1 · pp. 16–17
  • For ALN and a simple TBox, finding an irreducible solution takes time polynomial in the sizes of C and D.When T has logarithmic depth in its size, its unfolding and the algorithm are polynomial as well.Source: §5.1 · p. 18

5.2 Abduction-Based Ranking of Potential Matches

  • The potential-match penalty counts hypotheses needed to complete a compatible counteroffer, and the computed concept H can explain the resulting rank.The penalty is the length of findIrred's result on the normalized concepts.Source: §5.2 · p. 18
  • The penalty is non-symmetric, syntax-independent, and monotonic over subsumption; it is zero exactly when C ⊑T D.For increasingly specific compatible counteroffers, penalties do not increase.Source: §5.2 · pp. 18, 20
  • In the example, C1=A2 receives penalty 2 while C2=⊤ receives penalty 3 because C1 contains a characteristic implicitly required by D.The example uses T={A ⊑ A1 ⊓ A2} and D=A.Source: §5.2 · p. 20

6. Concept Contraction

This section models negotiation over inconsistent demand–supply pairs using Description Logic Concept Contraction, including number-restriction-minimal contractions and a penalty for ranking partial matches. It establishes formal properties of contraction-based ranking, including non-symmetry, syntax independence, and antimonotonicity when the first concept becomes more specific.

6. Concept Contraction

  • Concept Contraction finds G and K such that T entails C ≡ G ⊓ K and K ⊓ D is satisfiable, with K retaining requirements and G identifying those given up.C and D must each be satisfiable in T; trivial solutions range from giving up everything to giving up nothing when C ⊓ D is satisfiable.Source: §6 · pp. 21–22
  • Deciding whether a proposed pair solves a Concept Contraction Problem is C-hard whenever concept satisfiability with respect to a TBox is C-hard in a DL containing AL.The proof reduces satisfiability to a CCP solution using universal and unqualified existential role quantification, conjunction, and ⊥.Source: §6 · p. 22

6.1 Number-Restriction Minimal Contractions

  • Number-restriction minimality excludes solutions that give up at-least restrictions merely because of conflicting universal role quantifications.In the example, giving up HomePC leaves requested component specifications vacuously true, so a solution that gives up only part of the monitor specification is more reasonable from the user's perspective.Source: §6.1 · p. 23
  • findContract returns a number-restriction-minimal contraction for its simplified ALN problem with concepts in CNF and no TBox.The method retracts an at-least restriction only when it directly conflicts with an at-most restriction in the demand at the same role path.Source: §6.1 · pp. 23–25

6.2 Contraction-Based Ranking of Partial Matches

  • For Dem1 the penalty is 1, whereas for the more specific Dem2 it is 3, illustrating why the penalty accounts for ⊥ rather than relying on the length of G.The algorithm adds the whole length of D when C = ⊥ because ⊥ conflicts with every concept, while giving up ∀R.⊥ can have zero length.Source: §6.2 · p. 27
  • The partial-match penalty is non-symmetric, syntax independent, and antimonotonic over subsumption.The penalty counts characteristics that must be retracted; the algorithm adds the length of D when C = ⊥ to preserve antimonotonicity.Source: §6.2 · pp. 26–28
  • Contraction penalty is non-symmetric: for the given C and D, p⊥(C, D, ∅) = 2 while p⊥(D, C, ∅) = 1.The example contrasts at-most and at-least restrictions and universal fillers; after giving up the at-least restriction, the universal restriction is compatible.Source: §6.2 · p. 28
  • The contraction formula is syntax-independent because it uses concept normal forms, which are unique up to conjunction order.Fixing an order on conjunctions, such as lexicographic order, removes that variation.Source: §6.2 · p. 28
  • If C′ is subsumed by C, then p⊥(C′, D, T) ≥ p⊥(C, D, T), as shown by induction over concept structure.The basis covers C′ = ⊥, added concept names, and strengthened or added number restrictions.Source: §6.2 · pp. 28–29
  • For universal restrictions, newly quantified roles and more specific fillers cannot decrease the penalty, completing the inductive step.The argument applies the inductive hypothesis to subsumed fillers and shows recursive penalty increments are at least as large.Source: §6.2 · p. 29

7. The Matchmaking System

MaMaS implements Description Logic matchmaking services and was evaluated against human rankings in three scenarios. Its rankings were reported as close to human commonsense behavior and better than unstructured text retrieval.

7. The Matchmaking System

  • MaMaS implements classical Description Logic inference services alongside the paper’s non-standard matchmaking algorithms.Its matchmaking operations include match-type detection, Concept Abduction, Concept Contraction, and ranking scores.Source: §7 · pp. 29–30
  • The system is a multi-user, multi-ontology Java servlet that exposes a DIG-compliant interface extended for matchmaking services.The extended interface includes operations for match-type detection, abduction, contraction, and ranking.Source: §7 · pp. 29–30
  • MaMaS supports only simple-TBox knowledge bases, where each concept axiom has a concept name on its left side.The paper does not detail its marketplace and service-discovery applications in this section.Source: §7 · p. 30

7.1 Experimental Evaluation

  • The evaluation compared unweighted MaMaS rankings with human judgments and a Vector Space Model baseline in apartment rental, dating, and recruiting scenarios.The study used questionnaires containing one request and ten offers, with three groups of ten volunteers ranking advertisements.Source: §7.1 · pp. 30–31
  • MaMaS rankings were close to human commonsense behavior and far better than unstructured text retrieval across the evaluated scenarios.The evaluation reports variability that the authors believe is partly due to ontology design.Source: §7.1 · pp. 30, 32

8. Conclusion

The paper develops Concept Abduction and Concept Contraction as non-monotonic Description Logic inferences for matchmaking, alongside algorithms and commonsense properties. It reports empirical support for its scoring proposal and an implemented facilitator, while noting ontology quality as a condition and identifying further research directions.

8. Conclusion

  • Classical Description Logic services such as satisfiability and subsumption are useful but may not suffice for matchmaking in open environments.The paper also analyzes general commonsense properties that a matchmaker should have.Source: §8 · p. 32
  • Concept Abduction and Contraction model semantic matchmaking as non-monotonic Description Logic inferences, with analyzed minimality criteria and related complexity results.The proposed classification and ranking algorithms use penalty functions and are shown to obey the identified properties.Source: §8 · p. 32
  • The proposal has logical foundations and was empirically shown to simulate commonsense human reasoning well, while relying on well-designed domain ontologies.Source: §8 · p. 32
  • A fully functional facilitator implements the framework for generic e-marketplace advertisements and semantic web-service discovery.The authors describe it as, to their knowledge, the only running system able to handle Concept Abduction and Concept Contraction problems.Source: §8 · p. 32
  • Future work targets algorithms for more expressive Description Logics and a tableaux-based system for the proposed inference services.Source: §8 · p. 33

Appendix A. Rules for Normal Form

The appendix gives rules for repeatedly transforming concepts into normal form, including rules involving subconcepts and the TBox. It states equivalence and complexity properties of the resulting concepts.

Appendix A. Rules for Normal Form

  • Apply the normal-form rules repeatedly until none applies at any nesting level inside ∀R.C.Source: Appendix A · p. 33

A.1 Rules Involving Subconcepts

  • Treat ⊓ on the left-hand side of the rules as associative and commutative, so matching conjuncts may occur in any order.Source: §A.1 · p. 33

A.2 Rules Involving the Concept and the TBox

  • When disj(A, B1, ..., Bk) belongs to T, the rule expands A by conjoining ¬B1 through ¬Bk.Source: §A.2 · p. 34
  • The concept produced by these rules is called an expansion or unfolding of a TBox.Source: §A.2 · p. 34

A.3 Properties of the Normal Form

  • For a concept C and a rule-derived C′, the appendix states a time bound when C′ is polynomially bounded in C.Under that condition, C′ can be computed in time O(|C|^2).Source: §A.3 · p. 34
  • Every concept resulting from the rules is equivalent to C with respect to models of the TBox.Source: §A.3 · p. 34
  • C is unsatisfiable exactly when its normal form is ⊥; under the polynomial-size condition, unsatisfiability is decidable in polynomial time.The text relates polynomially bounded expansions to TBoxes that are “bushy but not deep.”Source: §A.3 · p. 34
Loading 1110.2742v1…