Umberto Straccia

Franco Alberto Cardillo, Franca Debole, Umberto Straccia

OWL ontologies are a quite popular way to describe structured knowledge in terms of classes, relations among classes and class instances. In this paper, given a target class T of an OWL ontology, with a focus on ontologies with real- and boolean-valued data properties, we address the problem of learning graded fuzzy concept inclusion axioms with the aim of describing enough conditions for being an individual classified as instance of the class T. To do so, we present PN-OWL that is a two-stage learning algorithm made of a P-stage and an N-stage. Roughly, in the P-stage the algorithm tries to cover as many positive examples as possible (increase recall), without compromising too much precision, while in the N-stage, the algorithm tries to rule out as many false positives, covered by the P-stage, as possible. PN-OWL then aggregates the fuzzy inclusion axioms learnt at the P-stage and the N-stage by combining them via aggregation functions to allow for a final decision whether an individual is instance of T or not. We also illustrate its effectiveness by means of an experimentation. An interesting feature is that fuzzy datatypes are built automatically, the learnt fuzzy concept inclusions can be represented directly into Fuzzy OWL 2 and, thus, any Fuzzy OWL 2 reasoner can then be used to automatically determine/classify (and to which degree) whether an individual belongs to the target class T or not.

Franco Alberto Cardillo, Hamza Khyari, Umberto Straccia

We proposes a novel method that enables Graph Neural Networks (GNNs) to solve SAT problems by leveraging a technique developed for applying GNNs to Mixed Integer Linear Programming (MILP). Specifically, k-CNF formulae are mapped into MILP problems, which are then encoded as weighted bipartite graphs and subsequently fed into a GNN for training and testing. From a theoretical perspective: (i) we establish permutation and equivalence invariance results, demonstrating that the method produces outputs that are stable under reordering of clauses and variables; (ii) we identify a theoretical limitation, showing that for a class of formulae called foldable formulae, standard GNNs cannot always distinguish satisfiable from unsatisfiable instances; (iii) we prove a universal approximation theorem, establishing that with Random Node Initialization (RNI), the method can approximate SAT solving to arbitrary precision on finite datasets, that is, the GNN becomes approximately sound and complete on such datasets. Furthermore, we show that for unfoldable formulae, the same approximation guarantee can be achieved without the need for RNI. Finally, we conduct an experimental evaluation of our approach, which show that, despite the simplicity of the neural architecture, the method achieves promising results.

Umberto Straccia, Giovanni Casini

Knowledge Measures (KMs) aim at quantifying the amount of knowledge/information that a knowledge base carries. On the other hand, Belief Change (BC) is the process of changing beliefs (in our case, in terms of contraction, expansion and revision) taking into account a new piece of knowledge, which possibly may be in contradiction with the current belief. We propose a new quantitative BC framework that is based on KMs by defining belief change operators that try to minimise, from an information-theoretic point of view, the surprise that the changed belief carries. To this end, we introduce the principle of minimal surprise. In particular, our contributions are (i) a general information-theoretic approach to KMs for which [1] is a special case; (ii) KM-based BC operators that satisfy the so-called AGM postulates; and (iii) a characterisation of any BC operator that satisfies the AGM postulates as a KM-based BC operator, i.e., any BC operator satisfying the AGM postulates can be encoded within our quantitative BC framework. We also introduce quantitative measures that account for the information loss of contraction, information gain of expansion and information change of revision. We also give a succinct look into the problem of iterated revision, which deals with the application of a sequence of revision operations in our framework, and also illustrate how one may build from our KM-based contraction operator also one not satisfying the (in)famous recovery postulate, by focusing on the so-called severe withdrawal model as an illustrative example.

Giovanni Casini, Umberto Straccia

We introduce and investigate here a formalisation for conditionals that allows the definition of a broad class of reasoning systems. This framework covers the most popular kinds of conditional reasoning in logic-based KR: the semantics we propose is appropriate for a structural analysis of those conditionals that do not satisfy closure properties associated to classical logics.

Umberto Straccia, Giovanni Casini

The triple language RDFS is designed to represent and reason with \emph{positive} statements only (e.g."antipyretics are drugs"). In this paper we show how to extend RDFS to express and reason with various forms of negative statements under the Open World Assumption (OWA). To do so, we start from $ρdf$, a minimal, but significant RDFS fragment that covers all essential features of RDFS, and then extend it to $ρdf_\bot^\neg$, allowing express also statements such as "radio therapies are non drug treatments", "Ebola has no treatment", or "opioids and antipyretics are disjoint classes". The main and, to the best of our knowledge, unique features of our proposal are: (i) $ρdf_\bot^\neg$ remains syntactically a triple language by extending $ρdf$ with new symbols with specific semantics and there is no need to revert to the reification method to represent negative triples; (ii) the logic is defined in such a way that any RDFS reasoner/store may handle the new predicates as ordinary terms if it does not want to take account of the extra capabilities; (iii) despite negated statements, every $ρdf_\bot^\neg$ knowledge base is satisfiable; (iv) the $ρdf_\bot^\neg$ entailment decision procedure is obtained from $ρdf$ via additional inference rules favouring a potential implementation; and (v) deciding entailment in $ρdf_\bot^\neg$ ranges from P to NP.

Giovanni Casini, Umberto Straccia

Lehmann and Magidor's rational closure is acknowledged as a landmark in the field of non-monotonic logics and it has also been re-formulated in the context of Description Logics (DLs). We show here how to model a rational form of entailment for expressive DLs, such as SROIQ, providing a novel reasoning procedure that compiles a non-monotone DL knowledge base into a description logic program (dl-program).

Franco Alberto Cardillo, Umberto Straccia

OWL ontologies are nowadays a quite popular way to describe structured knowledge in terms of classes, relations among classes and class instances. In this paper, given a target class T of an OWL ontology, we address the problem of learning fuzzy concept inclusion axioms that describe sufficient conditions for being an individual instance of T. To do so, we present Fuzzy OWL-BOOST that relies on the Real AdaBoost boosting algorithm adapted to the (fuzzy) OWL case. We illustrate its effectiveness by means of an experimentation. An interesting feature is that the learned rules can be represented directly into Fuzzy OWL 2. As a consequence, any Fuzzy OWL 2 reasoner can then be used to automatically determine/classify (and to which degree) whether an individual belongs to the target class T.

Giovanni Casini, Umberto Straccia

In the field of non-monotonic logics, the notion of Rational Closure (RC) is acknowledged as a prominent approach. In recent years, RC has gained even more popularity in the context of Description Logics (DLs), the logic underpinning the semantic web standard ontology language OWL 2, whose main ingredients are classes and roles. In this work, we show how to integrate RC within the triple language RDFS, which together with OWL2 are the two major standard semantic web ontology languages. To do so, we start from $ρdf$, which is the logic behind RDFS, and then extend it to $ρdf_\bot$, allowing to state that two entities are incompatible. Eventually, we propose defeasible $ρdf_\bot$ via a typical RC construction. The main features of our approach are: (i) unlike most other approaches that add an extra non-monotone rule layer on top of monotone RDFS, defeasible $ρdf_\bot$ remains syntactically a triple language and is a simple extension of $ρdf_\bot$ by introducing some new predicate symbols with specific semantics. In particular, any RDFS reasoner/store may handle them as ordinary terms if it does not want to take account for the extra semantics of the new predicate symbols; (ii) the defeasible $ρdf_\bot$ entailment decision procedure is build on top of the $ρdf_\bot$ entailment decision procedure, which in turn is an extension of the one for $ρdf$ via some additional inference rules favouring an potential implementation; and (iii) defeasible $ρdf_\bot$ entailment can be decided in polynomial time.

Faranak Sobhani, Umberto Straccia

The detection and representation of events is a critical element in automated surveillance systems. We present here an ontology for representing complex semantic events to assist video surveillance-based vandalism detection. The ontology contains the definition of a rich and articulated event vocabulary that is aimed at aiding forensic analysis to objectively identify and represent complex events. Our ontology has then been applied in the context of London Riots, which took place in 2011. We report also on the experiments conducted to support the classification of complex criminal events from video data.

Umberto Straccia

We present the state of the art in representing and reasoning with fuzzy knowledge in Semantic Web Languages such as triple languages RDF/RDFS, conceptual languages of the OWL 2 family and rule languages. We further show how one may generalise them to so-called annotation domains, that cover also e.g. temporal and provenance extensions.

Giovanni Casini, Umberto Straccia, Thomas Meyer

Description Logics (DLs) under Rational Closure (RC) is a well-known framework for non-monotonic reasoning in DLs. In this paper, we address the concept subsumption decision problem under RC for nominal safe $\mathcal{ELO}_\bot$, a notable and practically important DL representative of the OWL 2 profile OWL 2 EL. Our contribution here is to define a polynomial time subsumption procedure for nominal safe $\mathcal{ELO}_\bot$ under RC that relies entirely on a series of classical, monotonic $\mathcal{EL}_\bot$ subsumption tests. Therefore, any existing classical monotonic $\mathcal{EL}_\bot$ reasoner can be used as a black box to implement our method. We then also adapt the method to one of the known extensions of RC for DLs, namely Defeasible Inheritance-based DLs without losing the computational tractability.

Umberto Straccia

We present a fuzzy version of description logics with concrete domains. Main features are: (i) concept constructors are based on t-norm, t-conorm, negation and implication; (ii) concrete domains are fuzzy sets; (iii) fuzzy modifiers are allowed; and (iv) the reasoning algorithm is based on a mixture of completion rules and bounded mixed integer programming.