Parameter Learning of Logic Programs for Symbolic-Statistical Modeling

By Taisuke Sato, Yoshitaka Kameya. Journal of Artificial Intelligence Research, 2001

297 citations recorded by the source corpus.

We propose a logical/mathematical framework for statistical parameter learning of parameterized logic programs, i.e. definite clause programs containing probabilistic facts with a parameterized distribution. It extends the traditional least Herbrand model semantics in logic programming to distribution semantics, possible world semantics with a probability distribution which is unconditionally applicable to arbitrary logic programs including ones for HMMs, PCFGs and Bayesian networks. We also propose a new EM algorithm, the graphical EM algorithm, that runs for a class of parameterized logic programs representing sequential decision processes where each decision is exclusive and independent. It runs on a new data structure called support graphs describing the logical relationship between observations and their explanations, and learns parameters by computing inside and outside probability generalized for logic programs. The complexity analysis shows that when combined with OLDT search for all explanations for observations, the graphical EM algorithm, despite its generality, has the same time complexity as existing EM algorithms, i.e. the Baum-Welch algorithm for HMMs, the Inside-Outside algorithm for PCFGs, and the one for singly connected Bayesian networks that have been developed independently in each research field. Learning experiments with PCFGs using two corpora of moderate size indicate that the graphical EM algorithm can significantly outperform the Inside-Outside algorithm.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/e33e1bd066c9c62040327c6969a890b9a49b23c0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Parameter Learning in Probabilistic Databases: A Least Squares Approach (2008, background): “Before determining the scoring function and learning setting, it is important to realize that there is also a major difference between probabilistic databases and alternative probabilistic logics, such as PRISM [6] and SLPs [5], even though the probabilistic database semantics seems closely related ”
Probabilistic logic programs: Unifying program trace and possible world semantics (2017, background): “, [18], [19], in which case every possible world admits at most one trace, or through symbolic extensions of traces that restore this property in the presence of non-determinism, e.”
Probabilistic (logic) programming concepts (2015, methodology): “Prominent examples of Prolog-based languages using this semantics include ICL (Poole 2008), PRISM (Sato and Kameya 2001) and ProbLog (De Raedt et al.”
Probabilistic Inductive Logic Programming (2004, methodology): “Nevertheless, this setting has been studied by [5] and by [ 54 ], who solves the parameter estimation problem for stochastic logic programs respectively PRISM programs, and by [39, 41], who presents an approach to structure learning of stochastic logic programs: adding one clause at a time to an exi”
BLOG: Probabilistic Models with Unknown Objects (2005, methodology): “Prologbased languages such as probabilistic Horn abduction [Poole, 1993], PRISM [Sato and Kameya, 2001], and Bayesian logic programs [Kersting and De Raedt, 2001] work with Herbrand models, where the objects are in one-to-one correspondence with the ground terms of the language.”
Probabilistic models with unknown objects (2006, methodology): “This separation can be exploited to obtain efficient algorithms for certain tasks [Sato and Kameya, 2001].”
An Algebraic Prolog for Reasoning about Possible Worlds (2011, unknown): “There is significant interest in probabilistic approaches to logic programming and several probabilistic variants of Prolog have been developed, such as ICL (Poole 2000), Dyna (Eisner, Goldlust, and Smith 2005), PRISM (Sato and Kameya 2001) and ProbLog (De Raedt, Kimmig, and Toivonen 2007).”
Learning Markov Logic Networks via Functional Gradient Boosting (2011, background): “These models range from directed models [2]–[4] to undirected models [5], [6] and sampling-based approaches [7], [8].”
Gradient-based boosting for statistical relational learning: The relational dependency network case (2011, background): “These models range from directed models (Getoor et al. 2001; Kersting and De Raedt 2007; Fierens et al. 2005; Jaeger 1997; Getoor and Grant 2006) to undirected models (Domingos and Lowd 2009; Koller et al. 2002) and sampling-based approaches (Sato and Kameya 2001; De Raedt et al. 2007; Poole 1993).”
Under Consideration for Publication in Theory and Practice of Logic Programming on the Implementation of the Probabilistic Logic Programming Language Problog (unknown): “As proofs are mutually exclusive, the explanation graph directly mirrors the sum-of-products structure of probability calculation (Sato and Kameya 2001).”