Abductive Matchmaking using Description Logics

Tommaso Di Noia, Eugenio Di Sciascio, Francesco M. Donini, Marina MongielloIJCAI 2003

Introduction

Traditional matchmaking in electronic marketplaces often struggles with the rigidity of keyword matching or the fuzziness of vector-based information retrieval. Logic-based approaches using Description Logics (DL) offer precision but typically rely on strict subsumption—checking if a supply ($S$) satisfies every constraint of a demand ($D$). This binary 'yes/no' logic fails to account for 'near-misses' or potential matches that are compatible but incomplete. This paper proposes a framework using Concept Abduction to rank these imperfect matches based on their semantic distance from the user's requirements.

Methodology: Concept Abduction

The authors utilize the $\mathcal{ALN}$ logic to implement a more nuanced matchmaking process. The core innovation is the application of the Concept Abduction Problem (CAP): given a demand $D$ and a supply $S$, if $S$ does not imply $D$, the system identifies a 'missing' concept $H$ (the hypothesis) such that $S \sqcap H \sqsubseteq D$.

Formal representation of a demand (D) and two supplies (S1, S2) using sets of concepts.

By seeking irreducible solutions for $H$, the system follows the principle of Occam’s Razor to find the simplest set of features that would satisfy the demand. Matches are then ranked by the 'size' of $H$; a smaller $H$ indicates a higher-quality match. This approach operates under an 'Open-World Assumption', treating unmentioned features as unknown rather than absent, which is essential for analyzing brief classified advertisements.

Empirical Evaluation and Results

To validate the framework, the authors conducted a study using real-world apartment rental advertisements. They compared the system's rankings against a 'gold standard' of human judgment provided by 20 volunteers who ranked sets of eight supplies against specific demands.

Comparison of system-generated rankings against averaged human user rankings for eight supply-demand pairs.

The system's rankings demonstrated high alignment with human intuition, with an average deviation from the human mean of only 8.3%. The algorithm successfully distinguished between supplies that were fundamentally inconsistent with the demand and those that were merely incomplete potential matches. As shown in the results table, the system's ranking closely mirrors the averaged human rankings, even when dealing with complex multi-feature demands.

Discussion and Insights

Abduction serves as a powerful tool for semantic gap analysis, quantifying exactly what a user must 'give up' or 'assume' to accept an offer. This process is inherently non-symmetric, reflecting the differing priorities of buyers and sellers. Furthermore, because the system identifies the specific missing concept $H$, it can provide transparent, human-readable explanations for its rankings (e.g., explaining that a match is ranked lower because it lacks a requested garden).

While effective, the system's success depends on a robust domain ontology and the expressivity of the underlying logic. Future work may explore ranking conflicting matches and extending the framework to more complex Description Logics used in the Semantic Web.

Summary updated

BibTeX
@inproceedings{noia2003abductive,
  author = {Tommaso Di Noia and Eugenio Di Sciascio and Francesco M. Donini and Marina Mongiello},
  title = {{Abductive Matchmaking using Description Logics}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2003},
}
Figure