Probabilistic logic programming: Difference between revisions

Revision as of 13:05, 2 February 2024

Revision as of 14:08, 3 February 2024

Line 1:

'''Probabilistic logic programming''' is a [[programming paradigm]] that combines [[logic programming]] with probabilities.

Most approaches to probabilistic logic programming are based on the distribution semantics,<ref>{{Citation |last=Riguzzi |first=Fabrizio |title=A survey of probabilistic logic programming |date=2018-09-01 |url=http://dx.doi.org/10.1145/3191315.3191319 |work=Declarative Logic Programming: Theory, Systems, and Applications |pages=185–228 |access-date=2023-10-25 |publisher=ACM |last2=Swift |first2=Theresa}}</ref> with the main exception of [[stochastic logic programs]].

== Distribution semantics ==

Most approaches to probabilistic logic programming are based on the ''distribution semantics,''.<ref>{{Citation |last=Riguzzi |first=Fabrizio |title=A survey of probabilistic logic programming |date=2018-09-01 |url=http://dx.doi.org/10.1145/3191315.3191319 |work=Declarative Logic Programming: Theory, Systems, and Applications |pages=185–228 |url=http://dx.doi.org/10.1145/3191315.3191319 |access-date=2023-10-25 |publisher=ACM |last2=Swift |first2=Theresa}}</ref> with the main exception of [[stochastic logic programs]].

The distribution semantics gives meaning to a probabilistic logic program as a probability distribution over possible worlds.

TheUnder the distribution semantics, a probabilistic logic program defines a probability distribution over [[Interpretation (logic)|interpretations]] of its predicates on its [[Herbrand Universe|Herbrand universe]]. The probability of a [[Ground expression|ground]] query ''Q'' is then obtained from the [[Joint probability distribution|joint distribution]] of the query and the worlds: it is the sum of the probability of the worlds where the query is true.<ref name=":0" /><ref>{{Cite journal |last=Poole |first=David |date=1993 |title=Probabilistic Horn abduction and Bayesian networks |url=http://dx.doi.org/10.1016/0004-3702(93)90061-f |journal=Artificial Intelligence |volume=64 |issue=1 |pages=81–129 |doi=10.1016/0004-3702(93)90061-f |issn=0004-3702}}</ref><ref>{{Citation |title=A Statistical Learning Method for Logic Programs with Distribution Semantics |date=1995 |work=Proceedings of the 12th International Conference on Logic Programming |url=http://dx.doi.org/10.7551/mitpress/4298.003.0069 |work=Proceedings of the 12th International Conference on Logic Programming|access-date=2023-10-25 |publisher=The MIT Press}}</ref> gives meaning to probabilistic logic programs that consist of an ordinary [[logic program]] and a set of probabilistic facts, which are logical facts annotated with a probability.

== Languages ==

The distribution semantics underlies many languages such as Probabilistic Horn Abduction, PRISM, Independent Choice Logic , probabilistic [[Datalog]], Logic Programs with Annotated Disjunctions (Vennekens et al., 2004), [[ProbLog]], P-log, and CP-logic. While the number of languages is large, all share a common approach so that there are transformations with linear complexity that can translate one language into another.<ref name=":0">{{Cite journal |last=Riguzzi |first=Fabrizio |last2=Bellodi |first2=Elena |last3=Zese |first3=Riccardo |date=2014 |title=A History of Probabilistic Inductive Logic Programming |url=https://www.frontiersin.org/articles/10.3389/frobt.2014.00006 |journal=Frontiers in Robotics and AI |volume=1 |doi=10.3389/frobt.2014.00006/full |issn=2296-9144}}</ref>

== InferenceRecursion and negation ==

=== Stratified programs ===

=== Answer set programs ===

== Inference ==

The problem of computing the probability of queries is called ''(marginal) inference''. Solving it by computing all the worlds and then identifying those that entail the query is impractical as the number of possible worlds is exponential in the number of ground probabilistic facts.<ref name=":0" /> In fact, already for acyclic programs and [[Atomic formula|atomic]] queries, computing the conditional probability of a query given a conjunction of atoms as evidence is [[♯P|#P]]-complete.

=== Exact inference ===

Usually, exact inference is performed by resorting to [[knowledge compilation]]: according to this, a [[Propositional calculus|propositional]] theory and a query are [[Compiler|compiled]] into a “target language”, which is then used to answer queries in [[polynomial time]]. The compilation becomes the main computational bottleneck, but considerable effort has been devoted to the development of efficient compilers. The compilation methods differ in the compactness of the target language and the class of queries and transformations that they support in polynomial time.<ref name=":0" />

=== Approximate inference ===

Since the cost of inference may be very high, approximate algorithms have been developed. They either compute subsets of possibly incomplete explanations or use random sampling. In the first approach, a subset of the explanations provides a lower bound and the set of partially expanded explanations provides an upper bound. In the second approach, the truth of the query is repeatedly checked in an ordinary [[logic program]] sampled from the probabilistic program. The probability of the query is then given by the fraction of the successes.<ref name=":0" /><ref>{{Cite journal |last=Kimmig |first=Angelika |last2=Demoen |first2=Bart |last3=Raedt |first3=Luc De |last4=Costa |first4=Vítor Santos |last5=Rocha |first5=Ricardo |date=2011 |title=On the implementation of the probabilistic logic programming language ProbLog |url=https://www.cambridge.org/core/journals/theory-and-practice-of-logic-programming/article/abs/on-the-implementation-of-the-probabilistic-logic-programming-language-problog/21037609B99F5DC8033DDF56D07BF839 |journal=Theory and Practice of Logic Programming |language=en |volume=11 |issue=2-3 |pages=235–262 |doi=10.1017/S1471068410000566 |issn=1475-3081}}</ref>

== Learning ==

{{main|Probabilistic inductive logic programming}}

[[Probabilistic inductive logic programming]] aims to learn probabilistic logic programs from data. This includes parameter learning, which estimates the probability annotations of a program while the clauses themselves are given by the user, and structure learning, in which the clauses themselves are induced by the probabilistic inductive logic programming system.<ref name=":0" />

Common approaches to parameter learning are based on [[Expectation–maximization algorithm|expectation–maximization]] or [[gradient descent]], while structure learning van beperformed by searching the space of possible clauses under a variety of heuristics.<ref name=":0" />

== Applications ==

Line 20 ⟶ 39:

== References ==

{{reflist}}

{{dual|date=3 February 2024|source={{Cite journal |last=Riguzzi |first=Fabrizio |last2=Bellodi |first2=Elena |last3=Zese |first3=Riccardo |date=2014 |title=A History of Probabilistic Inductive Logic Programming |journal=Frontiers in Robotics and AI |volume=1}}|sourcepath=https://www.frontiersin.org/articles/10.3389/frobt.2014.00006}}

{{Programming paradigms navbox}}