Abstract In this paper, we address the problem of giving names to predicates in logic rules using Large Language Models (LLMs). In the context of Inductive Logic Programming, various rule generation methods produce rules containing unnamed predicates, with Predicate Invention being a key example. This hinders the readability, interpretability, and reusability of the logic theory. Leveraging recent advancements in LLMs development, we explore their ability to process natural language and code to provide semantically meaningful suggestions for giving a name to unnamed predicates. The evaluation of our approach on some hand-crafted logic rules indicates that LLMs hold potential for this task.

Maximum-a-Posteriori (MAP) inference is a crucial problem in Artificial Intelligence, which requires both marginalization and maximization, and asks for the most probable value for a given set of variables such that an evidence holds. Several languages within the Statistical Relational Artificial Intelligence landscape support the encoding of MAP. Here, we focus on Probabilistic Answer Set Programming, consider the credal and smProbLog semantics, and introduce a three-level algebraic model counting representation for MAP. We implemented our approach on top of a state-of-the-art solver and compared it with existing solutions, showing the competitive performance of our proposal, even against less general tools.

Most Probable Explanation (MPE) is a fundamental problem in statistical relational artificial intelligence. In the context of Probabilistic Answer Set Programming (PASP), solving MPE is still an open research problem. In this paper, we present three novel approaches for solving the MPE task in PASP that are based on: i) Algebraic Model Counting, ii) Answer Set Programming (ASP), and iii) ASP with quantifiers (ASP(Q)). These approaches are implemented and evaluated against existing solvers across different datasets and configurations. Empirical results demonstrate that the novel solutions consistently outperform existing alternatives for non-stratified programs.

Probabilistic logic-based languages offer an expressive framework for encoding uncertain information in a human-interpretable way. Among existing formalisms, Probabilistic Answer Set Programming (PASP) stands out for its ease of modeling complex scenarios. The current definition of PASP is limited to programs consisting of disjunctive rules and probabilistic facts only. To enhance the expressivity of the framework, we introduce Optimal Probabilistic Answer Set Programming, which extends the language by allowing the inclusion of weak constraints within PASP specifications. We motivate this extension through some real-world application scenarios and present a detailed computational complexity analysis for both the inference and Most Probable Explanation (MPE) tasks.

Hybrid Knowledge Bases (HKBs) successfully integrate Logic Programming (LP) and Description Logics (DL) under the Minimal Knowledge with Negation as Failure semantics. Both world closure assumptions (open and closed) can be used in the same HKB, a feature required in many domains, such as the legal and health-care ones. In previous work, we proposed (function-free) Probabilistic HKBs, whose semantics applied Sato's distribution semantics approach to the well-founded HKB semantics proposed by Knorr et al. and Lyu and You. This semantics relied on the fact that the grounding of a function-free Probabilistic HKB (PHKB) is finite. In this article, we extend the PHKB language to allow function symbols, obtaining PHKBFS. Because the grounding of a PHKBFS can be infinite, we propose a novel semantics which does not require the PHKBFS's grounding to be finite. We show that the proposed semantics extends the previously proposed semantics and that, for a large class of PHKBFS, every query can be assigned a probability.

Current data-driven AI approaches in Network Intrusion Detection System (NIDS) face challenges related to high resource consumption, high computational demands, and limited interpretability. Moreover, they often struggle to detect unknown and rapidly evolving cyber threats. This survey explores the integration of Neurosymbolic AI (NeSy AI) into NIDS, combining the data-driven capabilities of Deep Learning (DL) with the structured reasoning of symbolic AI to address emerging cybersecurity threats. The integration of NeSy AI into NIDS demonstrates significant improvements in both the detection and interpretation of complex network threats by exploiting the advanced pattern recognition typical of neural processing and the interpretive capabilities of symbolic reasoning. In this survey, we categorise the analysed NeSy AI approaches applied to NIDS into logic-based and graph-based representations. Logic-based approaches emphasise symbolic reasoning and rule-based inference. On the other hand, graph-based representations capture the relational and structural aspects of network traffic. We examine various NeSy systems applied to NIDS, highlighting their potential and main challenges. Furthermore, we discuss the most relevant issues in the field of NIDS and the contribution NeSy can offer. We present a comparison between the main XAI techniques applied to NIDS in the literature and the increased explainability offered by NeSy systems.

The necessity to manage inconsistency in Description Logics Knowledge Bases (KBs) has come to the fore with the increasing importance gained by the Semantic Web, where information comes from different sources that constantly change their content and may contain contradictory descriptions when considered either alone or together. Classical reasoning algorithms do not handle inconsistent KBs, forcing the debugging of the KB in order to remove the inconsistency. In this paper, we exploit an existing probabilistic semantics called DISPONTE to overcome this problem and allow queries also in case of inconsistent KBs. We implemented our approach in the reasoners TRILL and BUNDLE and empirically tested the validity of our proposal. Moreover, we formally compare the presented approach to that of the repair semantics, one of the most established semantics when considering DL reasoning tasks.

Abstract Solving a decision theory problem usually involves finding the actions, among a set of possible ones, which optimize the expected reward, while possibly accounting for the uncertainty of the environment. In this paper, we introduce the possibility to encode decision theory problems with Probabilistic Answer Set Programming under the credal semantics via decision atoms and utility attributes. To solve the task, we propose an algorithm based on three layers of Algebraic Model Counting, that we test on several synthetic datasets against an algorithm that adopts answer set enumeration. Empirical results show that our algorithm can manage non-trivial instances of programs in a reasonable amount of time.

Abstract Probabilistic Answer Set Programming under the credal semantics extends Answer Set Programming with probabilistic facts that represent uncertain information. The probabilistic facts are discrete with Bernoulli distributions. However, several real-world scenarios require a combination of both discrete and continuous random variables. In this paper, we extend the PASP framework to support continuous random variables and propose Hybrid Probabilistic Answer Set Programming. Moreover, we discuss, implement, and assess the performance of two exact algorithms based on projected answer set enumeration and knowledge compilation and two approximate algorithms based on sampling. Empirical results, also in line with known theoretical results, show that exact inference is feasible only for small instances, but knowledge compilation has a huge positive impact on performance. Sampling allows handling larger instances but sometimes requires an increasing amount of memory.

Abstract Probabilistic Logic Programming (PLP) under the distribution semantics is a leading approach to practical reasoning under uncertainty. An advantage of the distribution semantics is its suitability for implementation as a Prolog or Python library, available through two well-maintained implementations, namely ProbLog and cplint/PITA. However, current formulations of the distribution semantics use point-probabilities, making it difficult to express epistemic uncertainty, such as arises from, for example, hierarchical classifications from computer vision models. Belief functions generalize probability measures as non-additive capacities and address epistemic uncertainty via interval probabilities. This paper introduces interval-based Capacity Logic Programs based on an extension of the distribution semantics to include belief functions and describes properties of the new framework that make it amenable to practical applications.

Ever-changing cyber threats require strong and flexible network security solutions. This paper suggests a new method to improve the performance of detecting both known and unknown attacks using a neuro-symbolic artificial intelligence (NSAI) network intrusion detection system (NIDS). Deep neural networks (DNN) learn complex network data patterns, which create a detailed overview of cyber-attack characteristics. Symbolic logic integration into the DNN allows for model training guidance by applying penalties when the DNN fails to differentiate between malicious and benign network traffic. This improves our model’s adaptability to new attacks and overcomes traditional signature-based NIDS limitations. By testing our NSAI NIDS on a large cyber dataset that includes novel attack scenarios, we show that it delivers an improvement in how accurately it detects attacks compared to traditional DNN methods. While our system maintains its high accuracy in recognizing known attacks, it outperforms conventional NIDS in discovering unknown attacks. This work improves cybersecurity by introducing a new way to detect both known and unknown network intrusions by combining DNNs with symbolic logic.

Probabilistic answer set programming has recently been extended to manage imprecise probabilities by means of credal probabilistic facts and credal annotated disjunctions. This increases the expressivity of the language but, at the same time, the cost of inference. In this paper, we cast inference in probabilistic answer set programs with credal probabilistic facts and credal annotated disjunctions as a constrained nonlinear optimization problem where the function to optimize is obtained via knowledge compilation. Empirical results on different datasets with multiple configurations shows the effectiveness of our approach.

Abstract Parameter learning is a crucial task in the field of Statistical Relational Artificial Intelligence: given a probabilistic logic program and a set of observations in the form of interpretations, the goal is to learn the probabilities of the facts in the program such that the probabilities of the interpretations are maximized. In this paper, we propose two algorithms to solve such a task within the formalism of Probabilistic Answer Set Programming, both based on the extraction of symbolic equations representing the probabilities of the interpretations. The first solves the task using an off-the-shelf constrained optimization solver while the second is based on an implementation of the Expectation Maximization algorithm. Empirical results show that our proposals often outperform existing approaches based on projected answer set enumeration in terms of quality of the solution and in terms of execution time.

Abstract When we want to compute the probability of a query from a probabilistic answer set program, some parts of a program may not influence the probability of a query, but they impact on the size of the grounding. Identifying and removing them is crucial to speed up the computation. Algorithms for SLG resolution offer the possibility of returning the residual program which can be used for computing answer sets for normal programs that do have a total well-founded model. The residual program does not contain the parts of the program that do not influence the probability. In this paper, we propose to exploit the residual program for performing inference. Empirical results on graph datasets show that the approach leads to significantly faster inference. The paper has been accepted at the ICLP2024 conference and under consideration in Theory and Practice of Logic Programming (TPLP).

Abstract Probabilistic Logic Programming combines uncertainty and logic-based languages. Liftable Probabilistic Logic Programs have been recently proposed to perform inference in a lifted way. LIFTCOVER is an algorithm used to perform parameter and structure learning of liftable probabilistic logic programs. In particular, it performs parameter learning via Expectation Maximization and LBFGS. In this paper, we present an updated version of LIFTCOVER, called LIFTCOVER+, in which regularization was added to improve the quality of the solutions and LBFGS was replaced by gradient descent. We tested LIFTCOVER+ on the same 12 datasets on which LIFTCOVER was tested and compared the performances in terms of AUC-ROC, AUC-PR, and execution times. Results show that in most cases Expectation Maximization with regularization improves the quality of the solutions.

In 1990, Halpern proposed the distinction between Type 1 and Type 2 statements: the former express statistical information about a domain of interest while the latter define a degree of belief. An example of Type 1 statement is “30% of the elements of a domain share the same property” while an example of Type 2 statement is “the element x has the property y with probability p”. Recently, Type 1 statements were given an interpretation in terms of probabilistic answer set programs under the credal semantics in the PASTA framework. The algorithm proposed for inference requires the enumeration of all the answer sets of a given program, and so it is impractical for domains of not trivial size. The field of lifted inference aims to identify programs where inference can be computed without grounding the program. In this paper, we identify some classes of PASTA programs for which we apply lifted inference and develop compact formulas to compute the probability bounds of a query without the need to generate all the possible answer sets.

Abstract Automatic differentiation (AD) is a range of algorithms to compute the numeric value of a function’s (partial) derivative, where the function is typically given as a computer program or abstract syntax tree. AD has become immensely popular as part of many learning algorithms, notably for neural networks. This paper uses Prolog to systematically derive gradient-based forward- and reverse-mode AD variants from a simple executable specification: evaluation of the symbolic derivative. Along the way we demonstrate that several Prolog features (DCGs, co-routines) contribute to the succinct formulation of the algorithm. We also discuss two applications in probabilistic programming that are enabled by our Prolog algorithms. The first is parameter learning for the Sum-Product Loop Language and the second consists of both parameter learning and variational inference for probabilistic logic programming.

Abstract Probabilistic logic programming (PLP) combines logic programs and probabilities. Due to its expressiveness and simplicity, it has been considered as a powerful tool for learning and reasoning in relational domains characterized by uncertainty. Still, learning the parameter and the structure of general PLP is computationally expensive due to the inference cost. We have recently proposed a restriction of the general PLP language called hierarchical PLP (HPLP) in which clauses and predicates are hierarchically organized. HPLPs can be converted into arithmetic circuits or deep neural networks and inference is much cheaper than for general PLP. In this paper we present algorithms for learning both the parameters and the structure of HPLPs from data. We first present an algorithm, called parameter learning for hierarchical probabilistic logic programs (PHIL) which performs parameter estimation of HPLPs using gradient descent and expectation maximization. We also propose structure learning of hierarchical probabilistic logic programming (SLEAHP), that learns both the structure and the parameters of HPLPs from data. Experiments were performed comparing PHIL and SLEAHP with PLP and Markov Logic Networks state-of-the art systems for parameter and structure learning respectively. PHIL was compared with EMBLEM, ProbLog2 and Tuffy and SLEAHP with SLIPCOVER, PROBFOIL+, MLB-BC, MLN-BT and RDN-B. The experiments on five well known datasets show that our algorithms achieve similar and often better accuracies but in a shorter time.

Abstract Probabilistic logical models deal effectively with uncertain relations and entities typical of many real world domains. In the field of probabilistic logic programming usually the aim is to learn these kinds of models to predict specific atoms or predicates of the domain, called target atoms/predicates. However, it might also be useful to learn classifiers for interpretations as a whole: to this end, we consider the models produced by the inductive constraint logic system, represented by sets ofintegrity constraints, and we propose a probabilistic version of them. Each integrity constraint is annotated with a probability, and the resulting probabilistic logical constraint model assigns a probability of being positive to interpretations. To learn both the structure and the parameters of such probabilistic models we propose the system PASCAL for “probabilistic inductive constraint logic”. Parameter learning can be performed using gradient descent or L-BFGS. PASCAL has been tested on 11 datasets and compared with a few statistical relational systems and a system that builds relational decision trees (TILDE): we demonstrate that this system achieves better or comparable results in terms of area under the precision–recall and receiver operating characteristic curves, in a comparable execution time.

Abstract Probabilistic logic programming is an effective formalism for encoding problems characterized by uncertainty. Some of these problems may require the optimization of probability values subject to constraints among probability distributions of random variables. Here, we introduce a new class of probabilistic logic programs, namely probabilisticoptimizablelogic programs, and we provide an effective algorithm to find the best assignment to probabilities of random variables, such that a set of constraints is satisfied and an objective function is optimized.

Abstract Uncertain information is being taken into account in an increasing number of application fields. In the meantime, abduction has been proved a powerful tool for handling hypothetical reasoning and incomplete knowledge. Probabilistic logical models are a suitable framework to handle uncertain information, and in the last decade many probabilistic logical languages have been proposed, as well as inference and learning systems for them. In the realm of Abductive Logic Programming (ALP), a variety of proof procedures have been defined as well. In this paper, we consider a richer logic language, coping with probabilistic abduction with variables. In particular, we consider an ALP program enriched with integrity constraints à la IFF, possibly annotated with a probability value. We first present the overall abductive language and its semantics according to the Distribution Semantics. We then introduce a proof procedure, obtained by extending one previously presented, and prove its soundness and completeness.

In Weighted Model Counting (WMC) we assign weights to Boolean literals and we want to compute the sum of the weights of the models of a Boolean function where the weight of a model is the product of the weights of its literals.WMC was shown to be particularly effective for performing inference in graphical models, with a complexity of O(n2 w ) where n is the number of variables and w is the treewidth.In this paper, we propose a quantum algorithm for performing WMC, Quantum WMC (QWMC), that modifies the quantum model counting algorithm to take into account the weights.In turn, the model counting algorithm uses the algorithms of quantum search, phase estimation and Fourier transform.In the black box model of computation, where we can only query an oracle for evaluating the Boolean function given an assignment, QWMC solves the problem approximately with a complexity of Θ(2 n 2 ) oracle calls while classically the best complexity is Θ(2 n ), thus achieving a quadratic speedup.

Abductive Logic Programming (ALP) has been proven very effective for formalizing societies of agents, commitments and norms, in particular by mapping the most common deontic operators (obligation, prohibition, permission) to abductive expectations. In our previous works, we have shown that ALP is a suitable framework for representing norms. Normative reasoning and query answering were accommodated by the same abductive proof procedure, named 𝒮CIFF. In this work, we introduce a defeasible flavour in this framework, in order to possibly discharge obligations in some scenarios. Abductive expectations can also be qualified as dischargeable, in the new, extended syntax. Both declarative and operational semantics are improved accordingly, and proof of soundness is given under syntax allowedness conditions Moreover, the dischargement itself might be proved invalid, or incoherent with the rules, due to new knowledge provided later on. In such a case, a discharged expectation might be reinstated and hold again after some evidence is given. We extend the notion of dischargement to take into consideration also the reinstatement of expectations. The expressiveness and power of the extended framework, named 𝒮CIFF𝒟, is shown by modeling and reasoning upon a fragment of the Japanese Civil Code. In particular, we consider a case study concerning manifestations of intention and their rescission (Section II of the Japanese Civil Code).

Abstract In Probabilistic Logic Programming (PLP) the most commonly studied inference task is to compute the marginal probability of a query given a program. In this paper, we consider two other important tasks in the PLP setting: the Maximum-A-Posteriori (MAP) inference task, which determines the most likely values for a subset of the random variables given evidence on other variables, and the Most Probable Explanation (MPE) task, the instance of MAP where the query variables are the complement of the evidence variables. We present a novel algorithm, included in the PITA reasoner, which tackles these tasks by representing each problem as a Binary Decision Diagram and applying a dynamic programming procedure on it. We compare our algorithm with the version of ProbLog that admits annotated disjunctions and can perform MAP and MPE inference. Experiments on several synthetic datasets show that PITA outperforms ProbLog in many cases.

Abstract Programming environments have evolved from purely text based to using graphical user interfaces, and now we see a move toward web-based interfaces, such as Jupyter. Web-based interfaces allow for the creation of interactive documents that consist of text and programs, as well as their output. The output can be rendered using web technology as, for example, text, tables, charts, or graphs. This approach is particularly suitable for capturing data analysis workflows and creating interactive educational material. This article describes SWISH, a web front-end for Prolog that consists of a web server implemented in SWI-Prolog and a client web application written in JavaScript. SWISH provides a web server where multiple users can manipulate and run the same material, and it can be adapted to support Prolog extensions. In this article we describe the architecture of SWISH, and describe two case studies of extensions of Prolog, namely Probabilistic Logic Programming and Logic Production System, which have used SWISH to provide tutorial sites.

Abstract When modeling real-world domains, we have to deal with information that is incomplete or that comes from sources with different trust levels. This motivates the need for managing uncertainty in the Semantic Web. To this purpose, we introduced a probabilistic semantics, named DISPONTE, in order to combine description logics (DLs) with probability theory. The probability of a query can be then computed from the set of its explanations by building a Binary Decision Diagram (BDD). The set of explanations can be found using thetableau algorithm, which has to handle non-determinism. Prolog, with its efficient handling of non-determinism, is suitable for implementing the tableau algorithm. TRILL and TRILLPare systems offering a Prolog implementation of the tableau algorithm. TRILLPbuilds apinpointing formulathat compactly represents the set of explanations and can be directly translated into a BDD. Both reasoners were shown to outperform state-of-the-art DL reasoners. In this paper, we present an improvement of TRILLP, named TORNADO, in which the BDD is directly built during the construction of the tableau, further speeding up the overall inference process. An experimental comparison shows the effectiveness of TORNADO. All systems can be tried online in the TRILL on SWISH web application at http://trill.ml.unife.it/ .

Ontologies form the basis of the Semantic Web. Description Logics (DLs) are often the languages of choice for modeling ontologies. Integration of DLs with rules and rule-based reasoning is crucial in the so-called Semantic Web stack vision - a complete stack of recommendations and languages each ba sed on and/or exploiting the underlying layers - which adds new features to the standards used in theWeb. The growing importance of the integration between DLs and rules is proved by the definition of the profile OWL 2 RL1 and the definition of languages such as RIF2 and SWRL3. Datalog± is an extension of Datalog which can be used for representing lightweight ontologies and expressing some languages of the DL-Lite family, with tractable query answering under certain language restrictions. In particular, it is able to express the DL-Lite version defined in OWL. In this work, we show that Abductive Logic Programming (ALP) can be used to represent Datalog± ontologies, supporting query answering through an abductive proof procedure, and smoothly achieving the integration of ontologies and rule-based reasoning. Often, reasoning with DLs means finding explanations for the truth of queries, that are useful when debugging ontologies and to understand answers given by the reasoning process. We show that reasoning under existential rules can be expressed by ALP languages and we present a solving system, which is experimentally proved to be competitive with DL reasoning systems. In particular, we consider an ALP framework named 𝒮CIFF derived from the IFF abductive framework. Forward and backward reasoning is naturally supported in this ALP framework. The 𝒮CIFF language smoothly supports the integration of rules, expressed in a Logic Programming language, with Datalog± ontologies, mapped into 𝒮CIFF (forward) integrity constraints. The main advantage is that this integration is achieved within a single language, grounded on abduction in computational logic, and able to model existential rules.

We present the web application Tableau Reasoner for descrIption Logics in proLog on SWI-Prolog for SHaring (TRILL on SWISH) which allows the user to write probabilistic description logic (DL) theories and compute the probability of queries with just a web browser. Various probabilistic extensions of DLs have been proposed in the recent past, because uncertainty is a fundamental component of the Semantic Web. We consider probabilistic DL theories following our distribution semantics for probabilistic ontologies (DISPONTE) semantics. Axioms of a DISPONTE knowledge base can be annotated with a probability, and the probability of queries can be computed with inference algorithms. TRILL is a probabilistic reasoner for DISPONTE knowledge base that is implemented in Prolog and exploits its backtracking facilities for handling the non-determinism of the tableau algorithm. TRILL on SWISH is based on SWISH, a recently proposed web framework for logic programming, based on various features and packages of SWI-Prolog (e.g., a web server and a library for creating remote Prolog engines and posing queries to them). TRILL on SWISH also allows users to cooperate in writing a probabilistic DL theory. It is free, open, and accessible on the Web at the url: http://trill.lamping.unife.it; it includes a number of examples that cover a wide range of domains and provide interesting Probabilistic Semantic Web applications. By building a web-based system, we allow users to experiment with probabilistic DLs without the need to install a complex software stack. In this way, we aim to reach out to a wider audience and popularize the Probabilistic Semantic Web. Copyright © 2016 John Wiley & Sons, Ltd.

Probabilistic Logic Programming is a promising formalism for dealing with uncertainty. Learning probabilistic logic programs has been receiving an increasing attention in Inductive Logic Programming: for instancethe system SLIPCOVER learns high quality theories in a variety of domains. HoweverSLIPCOVER is computationally expensivewith a running time of the order of hours. In order to apply SLIPCOVER to Big Data, we present SEMPRE, for “Structure lEarning by MaPREduce”, that scales SLIPCOVER by following a MapReduce strategy, directly implemented with the Message Passing Interface.

The management of business processes can support efficiency improvements in organizations. One of the most interesting problems is the mining and representation of process models in a declarative language. Various recently proposed knowledge-based languages showed advantages over graph-based proced ural notations. Moreover, rapid changes of the environment require organizations to check how compliant are new process instances with the deployed models. We present a Statistical Relational Learning approach to Workflow Mining that takes into account both flexibility and uncertainty in real environments. It performs automatic discovery of process models expressed in a probabilistic logic. It uses the existing DPML algorithm for extracting first-order logic constraints from process logs. The constraints are then translated into Markov Logic to learn their weights. Inference on the resulting Markov Logic model allows a probabilistic classification of test traces, by assigning them the probability of being compliant to the model. We applied this approach to three datasets and compared it with DPML alone, five Petri net- and EPC-based process mining algorithms and Tilde. The technique is able to better classify new execution traces, showing higher accuracy and areas under the PR/ROC curves in most cases.

Summary We present the web application ‘cplinton SWI‐Prolog for SHaring that allows the user to write (SWISH)' Probabilistic Logic Programs and submit the computation of the probability of queries with a web browser. The application is based on SWISH, a web framework for Logic Programming. SWISH is based on various features and packages of SWI‐Prolog, in particular, its web server and its Pengine library, that allow to create remote Prolog engines and to pose queries to them. In order to develop the web application, we started from the PITA system, which is included incplint, a suite of programs for reasoning over Logic Programs with Annotated Disjunctions, by porting PITA to SWI‐Prolog. Moreover, we modified the PITA library so that it can be executed in a multi‐threading environment. Developing ‘cplinton SWISH’ also required modification of the JavaScript SWISH code that creates and queries Pengines. ‘cplinton SWISH’ includes a number of examples that cover a wide range of domains and provide interesting applications of Probabilistic Logic Programming. By providing a web interface tocplint, we allow users to experiment with Probabilistic Logic Programming without the need to install a system, a procedure that is often complex, error prone, and limited mainly to the Linux platform. In this way, we aim to reach out to a wider audience and popularize Probabilistic Logic Programming. Copyright © 2015 John Wiley & Sons, Ltd.

Abstract Learning probabilistic logic programming languages is receiving an increasing attention, and systems are available for learning the parameters (PRISM, LeProbLog, LFI-ProbLog and EMBLEM) or both structure and parameters (SEM-CP-logic and SLIPCASE) of these languages. In this paper we present the algorithm SLIPCOVER for “Structure LearnIng of Probabilistic logic programs by searChing OVER the clause space.” It performs a beam search in the space of probabilistic clauses and a greedy search in the space of theories using the log likelihood of the data as the guiding heuristics. To estimate the log likelihood, SLIPCOVER performs Expectation Maximization with EMBLEM. The algorithm has been tested on five real world datasets and compared with SLIPCASE, SEM-CP-logic, Aleph and two algorithms for learning Markov Logic Networks (Learning using Structural Motifs (LSM) and ALEPH++ExactL1). SLIPCOVER achieves higher areas under the precision-recall and receiver operating characteristic curves in most cases.

Probabilistic Logic Programming (PLP) allows one to represent domains containing many entities connected by uncertain relations and has many applications in particular in Machine Learning. PITA is a PLP algorithm for computing the probability of queries, which exploits tabling, answer subsumption and Binary Decision Diagrams (BDDs). PITA does not impose any restriction on the programs. Other algorithms, such as PRISM, reduce computation time by imposing restrictions on the program, namely that subgoals are independent and that clause bodies are mutually exclusive. Another assumption that simplifies inference is that clause bodies are independent. In this paper, we present the algorithms PITA(IND,IND) and PITA(OPT). PITA(IND,IND) assumes that subgoals and clause bodies are independent. PITA(OPT) instead first checks whether these assumptions hold for subprograms and subgoals: if they do, PITA(OPT) uses a simplified calculation, otherwise it resorts to BDDs. Experiments on a number of benchmark datasets show that PITA(IND,IND) is the fastest on datasets respecting the assumptions, while PITA(OPT) is a good option when nothing is known about a dataset.

As evaluation methods for logic programs have become more sophisticated, the classes of programs for which termination can be guaranteed have expanded. From the perspective of ar set programs that include function symbols, recent work has identified classes for which grounding routines can terminate either on the entire program [Calimeri et al. 2008] or on suitable queries [Baselice et al. 2009]. From the perspective of tabling, it has long been known that a tabling technique called subgoal abstraction provides good termination properties for definite programs [Tamaki and Sato 1986], and this result was recently extended to stratified programs via the class of bounded term-size programs [Riguzzi and Swift 2013]. In this article, we provide a formal definition of tabling with subgoal abstraction resulting in the SLG SA algorithm. Moreover, we discuss a declarative characterization of the queries and programs for which SLG SA terminates. We call this class strongly bounded term-size programs and show its equivalence to programs with finite well-founded models. For normal programs, strongly bounded term-size programs strictly includes the finitely ground programs of Calimeri et al. [2008]. SLG SA has an asymptotic complexity on strongly bounded term-size programs equal to the best known and produces a residual program that can be sent to an answer set programming system. Finally, we describe the implementation of subgoal abstraction within the SLG-WAM of XSB and provide performance results.

Abstract Lifted inference has been proposed for various probabilistic logical frameworks in order to compute the probability of queries in a time that depends on the size of the domains of the random variables rather than the number of instances. Even if various authors have underlined its importance for probabilistic logic programming (PLP), lifted inference has been applied up to now only to relational languages outside of logic programming. In this paper we adapt Generalized Counting First Order Variable Elimination (GC-FOVE) to the problem of computing the probability of queries to probabilistic logic programs under the distribution semantics. In particular, we extend the Prolog Factor Language (PFL) to include two new types of factors that are needed for representing ProbLog programs. These factors take into account the existing causal independence relationships among random variables and are managed by the extension to variable elimination proposed by Zhang and Poole for dealing with convergent variables and heterogeneous factors. Two new operators are added to GC-FOVE for treating heterogeneous factors. The resulting algorithm, called LP2for Lifted Probabilistic Logic Programming, has been implemented by modifying the PFL implementation of GC-FOVE and tested on three benchmarks for lifted inference. A comparison with PITA and ProbLog2 shows the potential of the approach.

Probabilistic Logic Programming is receiving an increasing attention for its ability to model domains with complex and uncertain relations among entities. In this paper we concentrate on the problem of approximate inference in probabilistic logic programming languages based on the distribution semantics. A successful approximate approach is based on Monte Carlo sampling, that consists in verifying the truth of the query in a normal program sampled from the probabilistic program. The ProbLog system includes such an algorithm and so does the cplint suite. In this paper we propose an approach for Monte Carlo inference that is based on a program transformation that translates a probabilistic program into a normal program to which the query can be posed. The current sample is stored in the internal database of the Yap Prolog engine. The resulting system, called MCINTYRE for Monte Carlo INference wiTh Yap REcord, is evaluated on various problems: biological networks, artificial datasets and a hidden Markov model. MCINTYRE is compared with the Monte Carlo algorithms of ProbLog and cplint and with the exact inference of the PITA system. The results show that MCINTYRE is faster than the other Monte Carlo systems.

Recently much work in Machine Learning has concentrated on using expressive representation languages that combine aspects of logic and probability. A whole field has emerged, called Statistical Relational Learning, rich of successful applications in a variety of domains. In this paper we present a Machine Learning technique targeted to Probabilistic Logic Programs, a family of formalisms where uncertainty is represented using Logic Programming tools. Among various proposals for Probabilistic Logic Programming, the one based on the distribution semantics is gaining popularity and is the basis for languages such as ICL, PRISM, ProbLog and Logic Programs with Annotated Disjunctions. This paper proposes a technique for learning parameters of these languages. Since their equivalent Bayesian networks contain hidden variables, an Expectation Maximization (EM) algorithm is adopted. In order to speed the computation up, expectations are computed directly on the Binary Decision Diagrams that are built for inference. The resulting system, called EMBLEM for “EM over Bdds for probabilistic Logic programs Efficient Mining”, has been applied to a number of datasets and showed good performances both in terms of speed and memory usage. In particular its speed allows the execution of a high number of restarts, resulting in good quality of the solutions.

Abstract Distribution semantics is one of the most prominent approaches for the combination of logic programming and probability theory. Many languages follow this semantics, such as Independent Choice Logic, PRISM, pD, Logic Programs with Annotated Disjunctions (LPADs), and ProbLog. When a program contains functions symbols, the distribution semantics is well–defined only if the set of explanations for a query is finite and so is each explanation. Well–definedness is usually either explicitly imposed or is achieved by severely limiting the class of allowed programs. In this paper, we identify a larger class of programs for which the semantics is well–defined together with an efficient procedure for computing the probability of queries. Since Logic Programs with Annotated Disjunctions offer the most general syntax, we present our results for them, but our results are applicable to all languages under the distribution semantics. We present the algorithm “Probabilistic Inference with Tabling and Answer subsumption” (PITA) that computes the probability of queries by transforming a probabilistic program into a normal program and then applying SLG resolution with answer subsumption. PITA has been implemented in XSB and tested on six domains: two with function symbols and four without. The execution times are compared with those of ProbLog,cplint, and CVE. PITA was almost always able to solve larger problems in a shorter time, on domains with and without function symbols.

Abstract Many real world domains require the representation of a measure of uncertainty. The most common such representation is probability, and the combination of probability with logic programs has given rise to the field of Probabilistic Logic Programming (PLP), leading to languages such as the Independent Choice Logic, Logic Programs with Annotated Disjunctions (LPADs), Problog, PRISM, and others. These languages share a similar distribution semantics, and methods have been devised to translate programs between these languages. The complexity of computing the probability of queries to these general PLP programs is very high due to the need to combine the probabilities of explanations that may not be exclusive. As one alternative, the PRISM system reduces the complexity of query answering by restricting the form of programs it can evaluate. As an entirely different alternative, Possibilistic Logic Programs adopt a simpler metric of uncertainty than probability. Each of these approaches—general PLP, restricted PLP, and Possibilistic Logic Programming—can be useful in different domains depending on the form of uncertainty to be represented, on the form of programs needed to model problems, and on the scale of the problems to be solved. In this paper, we show how the PITA system, which originally supported the general PLP language of LPADs, can also efficiently support restricted PLP and Possibilistic Logic Programs. PITA relies on tabling with answer subsumption and consists of a transformation along with an API for library functions that interface with answer subsumption. We show that, by adapting its transformation and library functions, PITA can be parameterized to PITA(IND, EXC) which supports the restricted PLP of PRISM, including optimizations that reduce non-discriminating arguments and the computation of Viterbi paths. Furthermore, we show PITA to be competitive with PRISM for complex queries to Hidden Markov Model examples, and sometimes much faster. We further show how PITA can be parameterized to PITA(COUNT) which computes the number of different explanations for a subgoal, and to PITA(POSS) which scalably implements Possibilistic Logic Programming. PITA is a supported package in version 3.3 of XSB.

This special issue of Fundamenta Informaticae contains the revised, extended versions of selected \npapers presented at the Italian Conference on Computational Logic (Convegno Italiano di Logica Com- \nputazionale, CILC’09) which was held at the Engineering Department of the University of Ferrara, Italy.

Logic Programs with Annotated Disjunctions (LPADs) allow to express probabilistic information in logic programming. The semantics of an LPAD is given in terms of the well-founded models of the normal logic programs obtained by selecting one disjunct from each ground LPAD clause. Inference on LPADs can be performed using either the system Ailog2, that was developed for the Independent Choice Logic, or SLDNFAD, an algorithm based on SLDNF. However, both of these algorithms run the risk of going into infinite loops and of performing redundant computations. In order to avoid these problems, we present SLGAD resolution that computes the (conditional) probability of a ground query from a range-restricted LPAD and is based on SLG resolution for normal logic programs. As SLG, it uses tabling to avoid some infinite loops and to avoid redundant computations. The performances of SLGAD are evaluated on classical benchmarks for normal logic programs under the well-founded semantics, namely a 2-person game and the ancestor relation, and on games of dice. SLGAD is compared with Ailog2 and SLDNFAD on the problems in which they do not go into infinite loops, namely those that are described by a modularly acyclic program. The results show that SLGAD is sometimes slower than Ailog2 and SLDNFAD but, if the program requires the repeated computations of the same goals, as for the dice games, then SLGAD is faster than both.

Abstract Strategic Environmental Assessment is a procedure aimed at introducing systematic assessment of the environmental effects of plans and programs. This procedure is based on the so-called coaxial matrices that define dependencies between plan activities (infrastructures, plants, resource extractions, buildings, etc.) and positive and negative environmental impacts, and dependencies between these impacts and environmental receptors. Up to now, this procedure is manually implemented by environmental experts for checking the environmental effects of a given plan or program, but it is never applied during the plan/program construction. A decision support system, based on a clear logic semantics, would be an invaluable tool not only in assessing a single, already defined plan, but also during the planning process in order to produce an optimized, environmentally assessed plan and to study possible alternative scenarios. We propose two logic-based approaches to the problem, one based on Constraint Logic Programming and one on Probabilistic Logic Programming that could be, in the future, conveniently merged to exploit the advantages of both. We test the proposed approaches on a real energy plan and we discuss their limitations and advantages.

In data mining, association and correlation rules are inferred from data in order to highlight statistical dependencies among attributes. The metrics defined for evaluating these rules can be exploited to score relationships between attributes in Bayesian network learning. In this paper, we propos e two novel methods for learning Bayesian networks from data that are based on the K2 learning algorithm and that improve it by exploiting parameters normally defined for association and correlation rules. In particular, we propose the algorithms K2-Lift and K2-X2, that exploit the lift metric and the X2 metric respectively. We compare K2-Lift, K2-X2 with K2 on artificial data and on three test Bayesian networks. The experiments show that both our algorithms improve K2 with respect to the quality of the learned network. Moreover, a comparison of K2-Lift and K2-X2 with a genetic algorithm approach on two benchmark networks show superior results on one network and comparable results on the other.

The monitoring and detection of nosocomial infections is a very important problem arising in hospitals. A hospital-acquired or nosocomial infection is a disease that develops after admission into the hospital and it is the consequence of a treatment, not necessarily a surgical one, performed by the medical staff. Nosocomial infections are dangerous because they are caused by bacteria which have dangerous (critical) resistance to antibiotics. This problem is very serious all over the world. In Italy, almost 5-8% of the patients admitted into hospitals develop this kind of infection. In order to reduce this figure, policies for controlling infections should be adopted by medical practitioners. In order to support them in this complex task, we have developed a system, called MERCURIO, capable of managing different aspects of the problem. The objectives of this system are the validation of microbiological data and the creation of a real time epidemiological information system. The system is useful for laboratory physicians, because it supports them in the execution of the microbiological analyses; for clinicians, because it supports them in the definition of the prophylaxis, of the most suitable antibi-otic therapy and in monitoring patients' infections; and for epidemiologists, because it allows them to identify outbreaks and to study infection dynamics. In order to achieve these objectives, we have adopted expert system and data mining techniques. We have also integrated a statistical module that monitors the diffusion of nosocomial infections over time in the hospital, and that strictly interacts with the knowledge based module. Data mining techniques have been used for improving the system knowledge base. The knowledge discovery process is not antithetic, but complementary to the one based on manual knowledge elicitation. In order to verify the reliability of the tasks performed by MERCURIO and the usefulness of the knowledge discovery approach, we performed a test based on a dataset of real infection events. In the validation task MERCURIO achieved an accuracy of 98.5%, a sensitivity of 98.5% and a specificity of 99%. In the therapy suggestion task, MERCURIO achieved very high accuracy and specificity as well. The executed test provided many insights to experts, too (we discovered some of their mistakes). The knowledge discovery approach was very effective in validating part of the MERCURIO knowledge base, and also in extending it with new validation rules, confirmed by interviewed microbiologists and specific to the hospital laboratory under consideration.

We present a tool for measuring the Function Point (FP) software metric from the specification of a software system expressed in the form of an Entity Relationship (ER) diagram plus a Data Flow Diagram (DFD). First, the informal and general FP counting rules are translated into rigorous rules expressing properties of the ER–DFD. Then, the rigorous rules are translated into Prolog. The measures given by the system on a number of case studies are in accordance with those of human experts.

We describe a knowledge based system for microbiological laboratory data validation and \nbacteria infections monitoring. The knowledge base has been obtained from international \nstandard guidelines for microbiological laboratory practice, from experts’ suggestions and \nfrom data mining. In this work, we evaluate the system in terms of accuracy on a test dataset.