We present a new framework for learning disjunctive logic programs from interpretation transitions, called LFDT. It is a nontrivial extension to Inoue, Ribeiro and Sakama's LF1T learning framework, which learns normal logic programs from interpretation transitions. Two resolutions for disjunctive rules are also presented and used in LFDT to simplify learned disjunctive rules.
In machine learning and specifically inductive logic programming [
Since a seminal work on representing Boolean networks by logic programs [
It is well-known that disjunctive logic programs [
Comparing with LF1T framework for learning normal logic programs, a nontrivial work in the paper is to handle with nondeterministic interpretation transitions, i.e., it is possible there are two interpretation transitions hI; J i and hI; J 0i in an observation with J 6= J 0. Combining with two new proposed resolutions for disjunctive rules, we achieve the new framework for learning disjunctive logic programs from interpretation transitions, called LFDT. It is proved being both sound and complete.
We assume a underlying first-order language without proper function symbols L and denote its Herbrand base (the set of all ground atoms) by A. We assume A is finite for our learning purpose.
A (disjunctive) logic program is a finite set of (disjunctive) rules of the form A1 _ _ Ak
B1 ^ ^ Bm ^ :C1 ^ ^ :Cn; (1) where k 1; m 0; n 0 and Ai (1 i k); Bj (1 j m), and Cs (1 s n) are atoms of L.
For a rule r of the form (1), the head of r, written hd(r), is A1 _ _ Ak; the body of r, written bd(r), is the conjunction B1 ^ ^ Bm ^ :C1 ^ ^ :Cn; the atoms occurring in the body of r positively (resp. negatively) is denoted by bd+(r) = fB1; : : : ; Bmg (resp. bd (r) = fC1; : : : ; Cng). If k = 1 then r is normal. A normal logic program is a finite set of normal rules. Given a logic program P , we denote hd(P ) = Sr2P hd(r) and bd(P ) = Sr2P bd(r). For convenience, we also write hd(r) as the set fA1; : : : ; Akg, and bd(r) as the set fB1; : : : ; Bm; :C1; : : : ; :Cng when there is no confusion. In this sense, a rule r of the form (1) can be alternatively written as fA1; : : : ; Akg
fB1; : : : ; Bm; :C1; : : : ; :Cng: is a function from variables to terms, which is written in the fol
A substitution lowing form
fx1=t1; : : : ; xn=tng
where xis (1 i n) are pair-wise distinct variables and tis (1 i n) are terms
(of the language L). The application e of to an expression e is obtained from e by
simultaneously replacing all occurrences of each variable xi in e with the same term
ti, and e is called an instance of e [
ground(r) = fr j r is a ground instance of rg:
For simplicity, we assume logic programs are always ground in the following of the paper, unless explicitly stated otherwise.
Let r1; r2 be two rules. We say that r1 subsumes r2, written r1 r2, if there exists a substitution such that hd(r1) hd(r2) and bd(r1) bd(r2). In this sense, we say that r1 is more (or equally) general than r2, and r2 is less (or equally) general than r1. By r1 r2 we mean r1 subsumes r2 but r2 does not subsume r1. For a logic program P , we denote SR(P ) the logic program obtained from P by removing all rules that are properly subsumed by some other rules in P , i.e., (2) (3) (4) SR(P ) = fr 2 P j6 9r0 2 P s:t : r0 rg: (5)
A (Herbrand) interpretation I is a set of ground atoms. An interpretation I satisfies a ground rule r if I satisfies bd(r) implies I satisfies hd(r). It satisfies a rule r if I satisfies every ground rule in ground(r). It satisfies a logic program P if it satisfies every rule in the logic program P . In this case we call I a model of a (ground) rule (resp., logic program). In the following we use “j=” to denote the satisfaction relation, and “ ” to denote the classical equivalence relation.
A rule r is applicable w.r.t. an interpretation I if I j= bd(r). Let P be a logic program. We denote app(P; I) the set of rules in P that are applicable w.r.t. I. Definition 1. Let P be a disjunctive logic program. The immediate consequence operator TPd : 2A ! 22A is defined as follows, for I A,
TPd (I) = fSjS is a minimal (under set inclusion) model of hd(app(P; I))g: (6)
Please note that the operator TPd is a generalization to the operator TP for normal
logic programs [
To extend the learning algorithm for normal logic programs in [
rule r is disjunctively ground resolvable w.r.t. r0 on a literal l whenever (a) l 2 bd(r) and l 2 bd(r0), (b) bd(r0) n flg bd(r) n flg, and (c) hd(r0) hd(r).
The disjunctive ground resolvent of r w.r.t. r0 on l is the rule hd(r) bd(r) n flg. We denote it by gr(r; r0). In particular, if the above condition (b) is strengthen to bd(r0) n flg = bd(r) n flg (7) then we say that r is disjunctively naive resolvable w.r.t. r0 on l.
The following proposition shows that the disjunctive ground resolution preserves the equivalence of the TPd operator in terms of TPd (I) = TPd0 (I) for every I A where P 0 is obtained from P by adding some disjunctive ground resolvent.
Proposition 1. Let P be a ground logic program containing two disjunctive rules r and r0 such that r is disjunctively ground resolvable w.r.t. r0 on a literal l, and Q = P [ fgr(r; r0)g. Then hd(app(P; I)) hd(app(Q; I)) for every I A. Definition 3 (combined resolution). Let r1; : : : ; rk and r be the following rules: bd+ [ :(bd . .
. rk : hd(rk) r : hd(r) bd+ [ :(bd bd+ [ fbij1 [ fbkg); i kg [ :bd 0 such that – bd \ fbij1 i kg = ;, and – hd(ri) hd(r) for every i (1 i
k).
Then the combined resolvent of r; r1; : : : ; rk, written cr(r; r1; : : : ; rk), is the rule r : hd(r) bd+ [ :(bd [ bd 0): (8) In this case we say that the rules r; r1; : : : ; rk are combined resolvable.
The next proposition shows that, similar to the disjunctive ground resolution, the combined resolution preserves the equivalence of the TPd operator as well. Proposition 2. Let P be a logic program containing rules r; r1; : : : ; rk such that r, r1, : : :, rk are combined resolvable, and Q = P [ fcr(r; r1; : : : ; rk)g. It holds that hd(app(P; I)) hd(app(Q; I)) for any I A. 4
In the section we present our inductive learning task for disjunctive logic programs and its learning algorithm. Properties of the algorithm are investigated as well. 4.1
A background theory is a logic program. An example (or observation) is a state transition (or interpretation transition), i.e., a tuple hI; J i with I A and J A, which means that the state J is a candidate successor of the state I in a Boolean network, or J 2 TPd (I) for a disjunctive logic program P . Let E be a set of examples. We denote Ei = fI j hI; J i 2 Eg, Eo = fJ j hI; J i 2 Sg and E(I) = fJ j hI; J i 2 Eg for I A. The set E is total whenever Ei = 2A.
state transitions is, given a background theory B and a set E of examples (state transitions), to find a hypothesis (a logic program) H such that, for every example hI; J i 2 E, J 2 T d
B[H (I) holds.
The above inductive learning task is written as ILT(B; E). Such a hypothesis H to the inductive learning task is called a solution to ILT(B; E). For our learning purpose, the given examples have to be restricted. For instance, let E = fh;; ;i; h;; fpgig and B = ;. There will be no logic program H satisfying f;; fpgg TBd[H (;), since the sets in the collection T d
B[H (;) are incomparable under set inclusion, while ; and fpg are comparable under set inclusion.
A set E of state transitions is coherent if J and J 0 are incomparable under set inclusion for every hI; J i and hI; J 0i in E, i.e., J and J 0 are all minimal under set inclusion. A set E of state transitions is consistent w.r.t. a logic program P , if for each hI; J i 2 E, I j= bd(r) implies J j= hd(r) holds for every rule r in P .
The following property identifies the sufficient and necessary condition for the existence of a solution to an inductive learning task.
Proposition 3. Given an inductive learning task ILT(B; E) where B is a background theory and E is a set of observations, there exists a solution H to ILT(B; E) if and only if E is coherent and E is consistent w.r.t. B. 4.2
In the following we present a bottom-up method to compute a logic program for our inductive learning tasks. This method generates hypothesis by generalization from the most specific rules until all examples are covered.
Firstly, let q 2 A and I A. We denote rqI the following rule: q
I [ :I (9) which is the most specific normal rule such that q belongs to a candidate successor of the state I. Now the LFDT algorithm is showed in Algorithm 1. Intuitively, this algorithm is to construct the following rules for these examples with the same first state in the state transitions hI; J1i; : : : ; hI; Jmi of E:
H
I [ :I;
H is a minimal hitting set of J1; : : : ; Jm: (10)
The algorithm AddRule, shown in Algorithm 2, adds these rules into the result. It
also simplifies the result by removing being subsumed rules through disjunctive ground
resolution and combined resolution. Since disjunctive ground resolution is a
generalization of ground resolution, this algorithm is also a generalization of the algorithm LF1T
in [
Let P be a logic program, and E be a coherent set of state transitions which is consistent w.r.t. a background theory B. The logic program P is complete for E w.r.t. B if fJ j hI; J i 2 Eg TBd[P (I) for any I 2 Ei, it is sound for E if TBd[P (I) fJ j hI; J i 2 Eg for any I 2 Ei. A learning algorithm is complete (resp. sound) for E w.r.t. B if its output is complete (resp. sound) for E w.r.t. B. In the following we show the correctness of the LFDT algorithm according to its soundness and completeness. Theorem 1. The algorithm LFDT is sound and complete (with disjunctive ground resolution, combined resolution, and/or subsumption reduction). Namely, if E is coherent and B is consistent w.r.t. E then the output P by the algorithm LFDT is sound and complete for E w.r.t. B. In this paper we proposed a new framework LFDT for learning disjunctive programs from interpretation transitions. It is a nontrivial and substantial extension to the LF1T framework. One remaining challenge work is to apply the learning approach to practical domains, such as bio-informatics for which LF1T is successfully applied.
Acknowledgement. We thank reviewers for their helpful comments. This work is partially supported by NSFC under grant 63170161, Stadholder Fund of Guizhou Province under grant (2012)62, Outstanding Young Talent Training Fund of Guizhou Province under grant (2015)01 and Science and Technology Fund of Guizhou Province under grant [2014]76400, Scientific and Technological Research Program of Chongqing Municipal Education Commission under Grant No. KJ1601129.