Approximate Reasoning with Order-Sorted Feature Logic

Order-Sorted Feature (OSF) logic is a Knowledge Representation and Reasoning (KRR) language originating in Hassan Aït-Kaci's work on designing a calculus of partially ordered type structures. The language was developed to model the notions of subsumption and unification in inheritance-based KRR formalisms, and it has been applied in computational linguistics and implemented in constraint logic programming languages and automated reasoners. The language of OSF logic is based on function-denoting feature symbols and on set-denoting sort symbols ordered in a subsumption (is-a) lattice. Reasoning with OSF logic relies on the unification of set-denoting structures called OSF terms, a process that aims to combine the constraints expressed by two OSF terms into a single term. An advantage of OSF logic is that its unification algorithm takes into account the subsumption ordering between sorts, which may enable a single unification step to replace several inference steps, leading to more efficient computations. This thesis deals with the theoretical development of approximate reasoning within the framework of OSF logic. The first key contribution of the thesis is the definition of fuzzy OSF logic, a fuzzy generalization of the semantics of OSF logic where sorts denote fuzzy sets rather than crisp sets, allowing to represent vague concepts. Moreover, the sorts of fuzzy OSF logic are ordered in a fuzzy subsumption relation (formally a fuzzy lattice) rather than a crisp one, which provides more modeling flexibility by allowing to represent graded subsumption relations. The fuzzy sort subsumption relation is given a special semantics which generalizes Zadeh's definition of inclusion of fuzzy sets. We investigate whether several semantic and computational properties of crisp OSF logic are preserved in the fuzzy setting. For instance, we show that OSF terms are ordered in a fuzzy subsumption relation which extends the fuzzy ordering between sorts, and we prove that the unification of two OSF terms yields their greatest lower bound. We also define procedures to compute the subsumption degree between two sorts or between two OSF terms, and study their computational complexity. The second key contribution of this thesis is the definition of similarity-based reasoning with OSF logic. Approximate reasoning based on fuzzy relations - in particular similarity relations - has been studied extensively in the fuzzy logic programming literature. Several approaches consist in extending the Prolog language with a similarity relation, which enables the definition of flexible notions of unification and SLD resolution, namely weak unification and similarity-based SLD resolution. Along these lines, defining similarity-based reasoning with OSF logic involves the development of a flexible unification procedure for OSF terms that takes into account a similarity relation between sorts. Since the sorts of OSF logic are ordered in a subsumption relation, this procedure should also account for the interactions between the two relations. Our proposed solution consists in a transformation that takes a sort subsumption relation and a sort similarity as inputs, producing a fuzzy sort subsumption relation that intuitively combines the information from both relations and their interactions. The advantage is that, as a consequence of this transformation, the same unification rules of fuzzy OSF logic can be applied to this setting, and a single unification may be able to replace several similarity-based SLD resolution steps. With respect to practical applications of our approach, we discuss logic programming languages based on fuzzy OSF logic and on similarity-based OSF logic, and a similarity-based extension of the CEDAR reasoner, a Semantic Web reasoner based on OSF logic. These applications rely on a fuzzy subsumption relation, or on a sort similarity relation, in order to provide approximate answers to queries posed to a knowledge base.

La logica Order-Sorted Feature (OSF) è un linguaggio di rappresentazione della conoscenza nato dal lavoro di ricerca di Hassan Aït-Kaci su un sistema logico per modellare le nozioni di sussunzione e unificazione nei formalismi basati sull'ereditarietà. La logica OSF è stata applicata alla linguistica computazionale e implementata in linguaggi di constraint logic programming e ragionatori automatici. Il linguaggio della logica OSF si basa su funzioni (attributi, o features), e su tipi (concetti, o sorts) ordinati in una relazione di sussunzione. In questa logica il ragionamento è fondato sull'unificazione di strutture chiamate termini OSF, un processo che mira a combinare i vincoli espressi da due termini OSF in un unico termine. Un vantaggio della logica OSF è che il suo algoritmo di unificazione tiene conto dell'ordinamento di sussunzione tra i tipi, che può consentire a una singola unificazione di sostituire diversi passi di inferenza, portando a calcoli più efficienti. Questa tesi si occupa dello sviluppo teorico del ragionamento approssimato con la logica OSF. Il primo contributo della tesi è la definizione della logica OSF fuzzy, una generalizzazione fuzzy della semantica della logica OSF in cui i tipi denotano insiemi fuzzy, consentendo di rappresentare concetti vaghi. Inoltre, i tipi della logica OSF fuzzy sono ordinati in una relazione di sussunzione fuzzy, fornendo maggiore flessibilità nella modellazione. La relazione di sussunzione fuzzy viene dotata di una semantica che generalizza la definizione di inclusione degli insiemi fuzzy di Zadeh. In questo lavoro indaghiamo se diverse proprietà semantiche e computazionali della logica OSF siano preservate nel contesto fuzzy. Dimostriamo, per esempio, che i termini OSF sono ordinati in un reticolo di sussunzione fuzzy che estende l'ordinamento fuzzy tra i tipi, e dimostriamo che l'unificazione di due termini OSF produce il loro estremo inferiore. Definiamo anche procedure per calcolare il grado di sussunzione tra due tipi o tra due termini OSF e ne studiamo la complessità computazionale. Il secondo contributo di questa tesi è la definizione del ragionamento basato sulla similarità con la logica OSF. Il ragionamento approssimato fondato su relazioni fuzzy è stato ampiamente studiato nella letteratura sulla programmazione logica fuzzy. Diversi approcci consistono nell'estendere Prolog con una relazione di similarità, che consente la definizione di nozioni flessibili di unificazione e di risoluzione SLD. In questa prospettiva, la definizione del ragionamento basato sulla similarità con la logica OSF implica lo sviluppo di una procedura di unificazione flessibile per i termini OSF che tenga conto di una relazione di similarità tra i tipi. Poiché i tipi della logica OSF sono ordinati in una relazione di sussunzione, questa procedura dovrebbe anche considerare le interazioni tra le due relazioni. La nostra soluzione consiste in una trasformazione che, prendendo come input una relazione di sussunzione e una similarità tra i tipi, produce una relazione di sussunzione fuzzy che combina le informazioni di entrambe le relazioni e delle loro interazioni. Come conseguenza di questa trasformazione, le stesse regole di unificazione della logica OSF fuzzy possono essere applicate in questo contesto, e una singola unificazione può sostituire diversi passaggi di risoluzione SLD basata sulla similarità. Per quanto riguarda le applicazioni pratiche del nostro approccio, presentiamo linguaggi di programmazione logica fondati sulla logica OSF fuzzy o sulla logica OSF con una relazione di similarità, e proponiamo un'estensione con una relazione di similarità del ragionatore CEDAR, un ragionatore basato sulla logica OSF per il Semantic Web. Queste applicazioni si avvalgono di una relazione di sussunzione fuzzy o di una relazione di similarità tra i tipi, al fine di fornire risposte approssimate a interrogazioni rivolte a una base di conoscenza.