The -subsumption test is known to be a bottleneck in Inductive Logic Programming. The state-of-the-art learning systems in this eld are hardly scalable. So we introduce a new -subsumption algorithm based on an Actor Model, with the aim of being able to decide subsumption on very large clauses. We use Akka, a powerful tool to build distributed actor systems based on the JVM and the Scala language.
substitution is a nite set fX1=v1; : : : ; Xn=vng where Xi is a variable and vi is a constant. A variable appears only once in a substitution, which is applied to a rst order formula to substitute variables with constants. Two substitutions are not compatible if they assign two distinct values to the same variable, otherwise they are said compatible. Let us introduce an example of -subsumption that will be used throughout this paper: Example 1 C = t(X) D = t(a) p(X; Y; Z) ^ q(Z; T ) ^ r(T; T; U ): p(a; b; c) ^ q(c; e) ^ r(e; e; g) ^ p(a; b; d) ^ q(d; f ) ^ r(f; f; g) ^
r(e; f; g): Example 1 shows that C D both for = fX=a; Y =b; Z=c; T =e; U=gg and = fX=a; Y =b; Z=d; T =f; U=gg. Let us consider the following properties that will be used in our model: Property 1. C -subsumes D if and only if 1) there exists a substitution only referring to the variables of head (C), such that head (C) = head (D) and, 2) there exists a substitution only referring to the variables of body(C) , such that body(C) body(D).
(The proofs of all the properties presented in this paper can be found here : https://lipn.univ-paris13.fr/~leger/ilp2016.html)
Example 1 we have head (C) = head (D) = t(a) with = fX=ag, and body(C) = fp(a; Y; Z); q(Z; T ); r(T; T; U )g. For = fY =b, Z=c, T =e, U=gg we have body(C) body(D). Thus C -subsumes D with = [ . Property 2. Let A = fa1; : : : ; ang be a conjunction of literals and B be a conjunction of ground literals. Then A -subsumes B if and only if there exists a set of compatible substitutions f 1; : : : ; ng such that ai i 2 B (1 i n).
Let us consider A = body(C) and B = body(D) mentioned above. We notice that A B with = 1 [ 2 [ 3 where 1 = fY =b; Z=cg, 2 = fZ=c; T =eg and 3 = fT =e; U=gg. So, according to properties 1 and 2, the subsumption problem of two clauses C and D can be modelled as: 1. seek a substitution only referring the variables of head (C) such that head(C) = head(D), 2. if step1 succeeds: (let body(C) = fa1; ; ang) nd a set of compatible substitutions f 1; ; ng, where i only refers the variables of ai, such that ai i 2 body(D) (1 i n), 3. if step 2 succeeds: output the substitution = [ 1 [ [ n.
Step 1 is very easy to check, so the new model of -subsumption we introduce in the next section focuses on step 2.
-subsumption based on an Actor Model
Given a (usually non-ground) conjunction A = fa1; : : : ; ang and a ground
conjunction B, we seek for a set of compatible substitutions f 1; : : : ; ng such that
i refers only the variables of ai and ai i belongs to B (1 i n). To solve
this problem we introduce an original subsumption procedure based on an
Actor Model. The Actor Model was motivated by the prospect of highly
parallel computing machines communicating via a high-performance communications
network [
Algorithm 1 Building the actors network buildNetwork(A) = A = fa1; : : : ; ang is a conjunction of n literals = begin create the output actor out ; buildTree(out, n) ; = build the tree of join and substitution actors = S = fs1; ; sng leaves(out) ; = get the substitution actors of the tree of root root = create the input actor in ; for i 1 to n do
link si with in ; set ai as internal label of si ; end for return in ; end.
= j: join (or output) actor of the preceding level = buildTree(j, n) begin if n = 1 then create a substitution actor a and store it ; = a new leaf for the tree = else end if link a to j ; end.
create a join actor a ; buildTree(a, n=2 + n mod 2) ; buildTree(a, n=2) ; Let us illustrate how such a network is used to check the subsumption through the network presented in Figure 2 built from the conjunction A = body(C) = fp(a; Y; Z); q(Z; T ); r(T; T; U )g where C is the clause given in Example 1. We also assume that the atoms of B = body(D) = fp(a; b; c), p(a; b; d), q(c; e), q(d; f ), r(e; e; g), r(f; f; g), r(e; f; g)g are sent to the network. Note that all the operations of the actors are made concurrently: { When a ground atom b of B is provided to the input actor, this actor sends b to all substitution actor s associated with the atoms of A built from the same predicate as b. ex) the input actor receives b = p(a; b; c), then it sends p(a; b; c) to the actor p(a; Y; Z). { When a substitution actor associated with an atom ai of A receives a ground atom b it checks if there exists a substitution i such that ai i = b. If i exists the actor sends it to the single join actor with which it is linked. ex) b = p(a; b; c) and ai = p(a; Y; Z) then the substitution i = fY =b; Z=cg is sent to the join actor j1, if b = p(e; b; c) no substitution is sent. The worst case complexity to check if there exists i with ai i = b is O(v:ln(v)) where v is the common arity of ai and b (ln(v) is the worst case complexity to access any argument of ai and b). { When a join actor receives a substitution from its left (right) parent it rst stores it in its left (right) internal memory. Then, it joins with each compatible substitution found in its right (left) memory and sends [ to its single successor. ex) the join actor j1 receives = fY =b; Z=cg from its left parent, then it stores it in its left memory. Assume the right memory of j1 contains the substitutions 1 = fZ=c; T =eg and 2 = fZ=d; T =f g. Thus [ 1 = fY =b; Z=c; T =eg is sent to the successor of j1, while [ 2 = fY =b; Z=c; Z=d; T =f g is not considered because it is not a valid substitution. The complexity to check that and are compatible is O(j j:ln(j )j) (we assume that and have approximately the same size). So the number of operations made by a join actor when it receives a message is in O(m:j j:ln(j j)) where m is the current size of the right (left) memory. { When the output actor receives a substitution it displays as a solution (A B). If we do not want any other solutions, the process terminates, otherwise the actor waits for other substitutions.
We send all the atoms of B to the input actor. To ensure that the activity of the network stops we then send it a speci c end-message. The end message is broadcasted through the network to the output actor which terminates the process if there is no solution. The model is correct and complete: each substitution reaching the output actor is a solution, and every possible solution can be outputed if the user wishes to (see https://lipn.univ-paris13.fr/~leger/ ilp2016.html for proofs). 4
Several programming languages implement the Actor Model. In this work we
use the Akka [
In Figure 3, we can see that the performance of the subsumption test increases along with the number of cores used. In this case the decrease in computation time eventually reaches a plateau, due to the data size. Please keep in mind that the number of actors is directly linked to the number of literals the hypothesis (subsumer) holds. This means that for a bigger clause, the cost-e ciency of parallelism would be higher. 5
We have shown that Actor Modeling is indeed e ective at reducing the running
time of the -subsumption problem. Due to a lack of time we did not compare
the implementation of our model with classical state-of-the-art solutions like
Subsumer [