Content deleted Content added
→Recursion and negation: Retitle |
→Stratified programs: Reorganise and expand |
||
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,'' which splits a program into a set of probabilistic facts and a logic program. It defines a probability distribution on interpretations of the [[Herbrand structure|Herbrand universe]] of the program.
Under 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 |last=Sato |first=Taisuke |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 |access-date=2023-10-25 |publisher=The MIT Press}}</ref>▼
== Languages ==
== Semantics ==
Under the distribution semantics, a probabilistic logic program is interpreted as a set of independent probabilistic facts ([[Ground expression|ground]] [[Atomic formula|atomic formulas]] annotated with a probability) and a [[logic program]] which can use the probabilistic facts in the bodies of its clauses. The probability of any assignment of truth values to the groundings of the formulas associated with probabilistic facts is given by the product of their probabilities; this is equivalent to assuming the choices of probabilistic facts to be [[independent random variables]].
=== Stratified programs ===
Important subclasses of stratified programs are positive programs, which do not use negation, but may be recursive, and acyclic programs, which may use negation but have no recursive dependencies.
Line 24 ⟶ 21:
== Inference ==
▲Under 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 |last=Sato |first=Taisuke |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 |access-date=2023-10-25 |publisher=The MIT Press}}</ref>
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.<ref>{{Cite book |last=Riguzzi |first=Fabrizio |title=Foundations of probabilistic logic programming: Languages, semantics, inference and learning |publisher=[[River Publishers]] |year=2023 |isbn=978-87-7022-719-3 |edition=2nd |___location=Gistrup, Denmark |pages=180}}</ref>
| |||