Combining Logic and Probability

Combining logic and probability is one of the long standing problems of Artificial Intelligence. Logic is very useful for describing domains with many different entities connected by complex relationships, while probability theory deals very well with the uncertainty that is associated to the data we collect from the world.

One of the aims of Artificial Intelligence is to develop machines that can reason on knowledge of the real world and derive information implied by it.

However, describing the real world is difficult because it usually includes many entities connected by a wide variety of relationships and the information we collect is often uncertain and incomplete.

To deal with the complexity of real world domains, AI researchers have developed powerful methods based on logic, while to deal with uncertainty they have devised clever techniques based on probability theory and statistics.

Until recently these two lines of research advanced independently because of the difficulties in combining them. The last twenty years have seen the fast growth of the field of Statistical Relational Artificial Intelligence (StarAI) which aims at overcoming these difficulties.

Researchers of DMCS are actively involved in StarAI by developing methods that combine logic programming with probability theory. They developed algorithm for drawing conclusions from probabilistic logic programs (inference) and algorithms that are able to autonomously build descriptions of the world from data (learning).

They developed the web application

http://cplint.ml.unife.it/

where all the algorithms developed by the group can be tried online, even on datasets supplied by the users.

Probabilistic Logic Programming (PLP) is a powerful tool that has a large number of applications, from medicine to marketing, social networks, natural language processing, games, biology and genetics.

In medicine, it can be used to perform causal reasoning and rigorously identify the effects of treatments, avoiding pitfalls such as the Simpson Paradox, see http://cplint.ml.unife.it/example/inference/simpson.swinb

In marketing and social networks, we can predict with PLP whether a marketing action such as sending promotional material regarding a product to a number of clients can have a viral effect on the social network of all clients, see

http://cplint.ml.unife.it/example/inference/viral.swinb


In social networks, as well as in other kind of graphs such as biological or telecommunication networks, we can compute the probability of a connection between two nodes, a problem knwon as “path reliability”, see http://cplint.ml.unife.it/example/inference/path.swinb

Or, we can compute the probability of the existence of a link between two individuals

 

 

 

 

 

 

http://cplint.ml.unife.it/example/inference/uwcse.pl

In games, we can exploit PLP for endowing games with intelligence and variation. For example, we can use it to randomly generate 2D maps as in

http://cplint.ml.unife.it/example/inference/tile_map.swinb









Tiles from https://github.com/silveira/openpixels

In biology, it can be used to predict whether a molecule can cause cancer by looking at the chemical structure of the formula. The predictive model is automatically constructed from the descriptions of molecules for which the cancerogenic or mutagenic effect has been determined in the laboratory, see http://cplint.ml.unife.it/example/learning/muta.pl





Image from https://www.doc.ic.ac.uk/~shm/mutagenesis.html

In genetics, it is possible to predict the genotype of an individual knowing the genotype of (some of) its ancestors using Mendel’s laws of inheritance, see http://cplint.ml.unife.it/example/inference/mendel.pl and http://cplint.ml.unife.it/example/inference/bloodtype.pl







CC BY-SA 3.0, Madeleine Price Ball

The power of PLP can also be illustrated by its ability of solving puzzles, such as the Monty Hall puzzle (http://cplint.ml.unife.it/example/inference/monty.swinb), the truel, or duel among three opponents (http://cplint.ml.unife.it/example/inference/truel.swinb), the coupon collector problem (http://cplint.ml.unife.it/example/inference/coupon.swinb) or the three-prisoners puzzle (http://cplint.ml.unife.it/example/inference/jail.swinb).

Humans have difficulty in providing the correct answer for these problems

while PLP can compute the correct solution very quickly.

Publications:

  • Fabrizio Riguzzi, Elena Bellodi, Evelina Lamma, Riccardo Zese, and Giuseppe Cota. Probabilistic logic programming on the web. Software: Practice and Experience, 46(10):1381-1396, © Wiley, October 2016. [ bib | DOI | .pdf ]

  • Fabrizio Riguzzi. The distribution semantics for normal programs with function symbols. International Journal of Approximate Reasoning, 77:1 - 19, © Elsevier, October 2016. [ bib | DOI | .pdf | http ]

  • Nicola Di Mauro, Elena Bellodi, and Fabrizio Riguzzi. Bandit-based Monte-Carlo structure learning of probabilistic logic programs. Machine Learning, 100(1):127-156, © Springer International Publishing, July 2015. The original publication is available at http://link.springer.com. [ bib | DOI | .pdf ]

  • Elena Bellodi and Fabrizio Riguzzi. Structure learning of probabilistic logic programs by searching the clause space. Theory and Practice of Logic Programming, 15(2):169-212, © Cambridge University Press, 2015. [ DOI | http ]

  • Fabrizio Riguzzi and Terrance Swift. Well-definedness and efficient inference for probabilistic logic programming under the distribution semantics. Theory and Practice of Logic Programming, 13(Special Issue 02 - 25th Annual GULP Conference):279-302, © Cambridge University Press, March 2013. [ bib | DOI | http ]

  • Fabrizio Riguzzi and Terrance Swift. The PITA system: Tabling and answer subsumption for reasoning under uncertainty. Theory and Practice of Logic Programming, 27th International Conference on Logic Programming (ICLP'11) Special Issue, Lexington, Kentucky 6-10 July 2011, 11(4-5):433-449, © Cambridge University Press, 2011. [ DOI http ]

 

Contact:

Prof. Dr. Fabrizio Riguzzi

Dipartimento di Matematica e Informatica, Università di Ferrara

Blocco B, Polo Scientifico Tecnologico

Via Saragat 1, 44122, Ferrara, Italy

Tel: +39 0532 97 4792 Web E-Mail

Filed under: