Due to its expressiveness and intuitiveness, Probabilistic logic programming (PLP) is a useful tool for reasoning in relational domains with uncertainty. However, both inference and learning are expensive tasks. In this paper we present various approaches for speeding up learning. We rst consider a restriction of PLP called Liftable PLP (LPLP) in which clauses in the program share the same predicate (the target). Then we extend this restriction in Hierarchical PLP (HPLP) where predicates and clauses are hierarchically organized and can be translated into Deep Neural Networks or Arithmetic Circuits. For LPLP, we propose two parameter learning algorithms, Expectation Maximization (EM) and Limited memory BFGS (LBFGS), and a discriminative structure learning. We also propose and implement an algorithm, called Parameter learning for HIerarchical probabilistic Logic program (PHIL) 3 that learns the parameter of HPLP using EM and gradient method.
Probabilistic logic programming (PLP) under the distribution semantics [
The paper is organized as follows: Sections 2 and 3 present Liftable PLP and Hierarchical PLP. Section 4 presents parameter learning of LPLP and HPLP and structure learning for LPLP. Finally Section 5 concludes and presents future work. 2
In order to improve inference in LPADs, we restrict the language of LPADs by
allowing only clauses of the form Ci = hi : i : bi1; : : : ; biui in the program
where all the clauses share the same predicate for the single atom in the head, let
us call this predicate r=a with a the arity. The literals in the body have predicates
other than r=a and are de ned by facts and rules that are certain, i.e., they have
a single atom in the head with probability 1. The predicate r=a is called target
and the others input predicates. A program containing n probabilistic clauses of
the form above is called liftable PLP. The probability of a query q being true
can be compute at liftable level with P (q) = 1 Qin=1(1 i)mi as described
[
student(A); prof essor(B); project(C; A); project(C; B): advisedby(A; B) : 0:6 :
student(A); prof essor(B); ta(C; A); taughtby(C; B): 3
HPLP extends LPLP by adding more layers of rules. In fact, a program in HPLP contains a set of rules that de ne the target predicate r using a number of input and hidden predicates. Hidden predicates are disjoint from input and target predicates. Each rule in the program has a single head atom annotated with a probability. The program is hierarchically de ned so that it can be divided into layers. Each layer contains a set of hidden predicates that are de ned in terms of predicates of the layer immediately below or in terms of input predicates.
A generic clauses C is of the form C = p(X) : : (X; Y ); b1(X; Y ); : : : ; bm(X; Y ) (1) where (X; Y ) is a conjunction of literals for the input predicates using variables X; Y . The literals bi(X; Y ) for i = 1; : : : ; m are built on a hidden predicate. Y is a possibly empty vector of variables. They are existentially quanti ed with scope the body. Only literals for input predicates can introduce new variables into the clause and all literals for hidden predicates must use the whole set of variables X; Y . Moreover, we require that the predicate of each bi(X; Y ) does not appear elsewhere in the body of C or in the body of any other clause. We call hierarchical PLP the language that admits only programs of this form. An example of HPLP is shown in the following program:
C1 = advisedby(A; B) : 0:3 : student(A); prof essor(B); project(C; A); project(C; B); r11(A; B; C): C2 = advisedby(A; B) : 0:6 :
student(A); prof essor(B); ta(C; A); taughtby(C; B): C111 = r11(A; B; C) : 0:2 :
publication(D; A; C); publication(D; B; C): where r11=3 is a hidden predicate.
The grounding of an HPLP can be generated and translated into Arithmetic Circuits (ACs) sharing parameters. In the AC we de ne 2 operators: the operator that computes the joint probability of its arguments ( literals in the body of a clause) and the operator that computes the probability of the disjunction of n independent random variables associated with individual clauses. 4
The parameter learning algorithm can be expressed as follows: Given a LPLP or an HPLP T with parameters , an interpretation I de ning input predicates and a set of positive and negative examples E = fe1; : : : ; eM ; not eM+1; : : : ; not eN g where each ei is a ground atom for the target predicate r, nd the values of that maximize the (log) likelihood (LL):
M arg max X log P (ei) + i=1
N
X log(1 i=M+1
P (ei)) (2) or that minimize the sum of cross entropy errors, erri = yi log(pi) (1 yi) log(1 pi), for all the examples (the two formulations are equivalent). We propose an EM and a gradient method algorithm for each language.
EM nds the maximun likelihood estimates of parameters in models with hidden variables by alternating between an Expectation and a Maximization step. Gradient method instead computes the partial derivatives of the (log) likelihood w.r.t each parameter in order to move the parameters in the direction that minimize the (log) likelihood. Let Xij be the random variable associated with a grounding Ci j of clause Ci. To perform EM we need to compute the distribution of the hidden variables given the observed ones, that are P (Xij = 1je) and P (Xij = 1j:e). For a single example e, the Expectation step computes E[ci0je] and E[ci1je] for all rules Ci where cix is the number of times a variable Xij takes value x for x 2 f0; 1g and for all j 2 g(i) i.e
E[cixje] = X P (Xij = xje)
j2g(i) where g(i) = fjj j is a substitution grounding Cig. These values are aggregated over all examples obtaining E[ci0] = Pe2E Pj2g(i) P (Xij = 0je) and E[ci1] = Pe2E Pj2g(i) P (Xij = 1je).
Then the Maximization computes i =
E[ci1]
E[ci0] + E[ci1]
For LPLP, see [
P (Xij = 1je) = 1 Qin=1(1 i)mi
i P (Xij = 1j:e) = 0 where mi is the number of instanciation of Ci whose head is e and i the parameter associate with Ci.
In HPLP, P (Xij = 1je) is computed by performing two steps over the factor
graph associated with the AC as described in [
We also propose a gradient method algorithm for LPLP and HPLP.
In LPLP, we present a gradient-based method using LBFGS ([
For HPLP, the algorithm, called DPHIL [
node i) if n= (Wi) pan = not(n) (3) (4) where pan is the parent of node n and i = (Wi) = 1+e1 Wi . Parameters are updated using Adam the optimizer. These actions are repeatedly performed until a maximum number of steps is reached or until certain conditions are satis ed.
For LPLP we present a discriminative structure learning called LIFTCOVER
[
In this paper we presented two restrictions of the language of Logic Program with Annotated Disjunction called Liftable and Hierarchical Probabilistic Logic Programming (LPLP and HPLP) that allow fast inference. We also presented an Expectation Maximization and a gradient method algorithm for learning the parameters of both languages. Finally we presented, LIFTCOVER, an algorithm for learning the structure of LPLP. In our future work, we plan to design an implement an algorithm for learning both the parameters and the structure of HPLP. We also plan to learn programs with continuous random variables for HPLP in order to deal with continuous data such as images.