Stefano Bragaglia and Fabrizio RiguzziCombining logic and probability is a field of research that has received much attention in the last few years. In this vein, many formalisms have been introduced such as Markov Logic Networks, ProbLog and Logic Programs with Annotated Disjunctions (LPADs), that allow to represent probabilistic information in logic. LPADs are particularly interesting because they can express cause–effect relationships among events, possible effects of a cause and the contemporary contribution of more causes to the same effect in a very natural way. From a syntactic point of view, an LPAD consists of a set of disjunctive clauses in which each atom in the head is annotated with a probability value between 0 and 1. The atoms of the head represent the mutually exclusive and exhaustive set of effects of the event represented by the body. The sum of the probabilities associated to the head atoms must be 1. Their semantic is based on the concept of Inference with LPADs can be performed with the
Once all the explanations for the query have been found, a BDD is built that allows to compute the probability by using a dynamic programming algorithm that traverses the diagram. In some domains, exact inference may be impossible. Therefore we considered several approximate algorithms, both deterministic and stochastic. Among these, the approximate deterministic algorithm We considered also a stochastic algorithm based on a Each algorithm has been applied to several datasets, both artificial and real. One of the real world dataset consists of biological graphs sampled from a network with 5220 nodes and 11530 edges that describes the biological entities responsible for Alzheimer’s disease together with their relationships. Since the problem is shaped as a graph where each edge has a probability value that expresses the strength of the connection, the query consists in computing the probability that a path exists between couples of nodes representing genes of Alzheimer’s disease. The results we gathered from experiments on this dataset show that the Monte Carlo algorithm can solve subgraphs almost three times larger than the standard inference (3400 edges instead of 1200). In addition, despite being slower on smaller problems, Monte Carlo algorithm is less demanding in terms of time and memory. Three artificial sets of graphs of increasing complexity have been created to evaluate the effectiveness of the algorithms. Again, the query is to evaluate the probability that a path exists between two given nodes of the graphs. In this case, both algorithms solve almost 50% more problems than the standard inference in less time. Moreover, although Monte Carlo is nearly twice as fast as the other, KBest produces almost no absolute error while the former bears a 10% error in the worst case.
@Inproceedings{BragagliaRiguzzi, |

Workshops > RiCeRcA 2009 >