We address the task of learning a dynamic Boolean network model from data about its state transitions, and constraints regarding the known attractors of the system. To this end, we propose a learning strategy where such prior knowledge is compiled into a first-order theory along with axioms describing the Boolean transitions functions and the language bias for their representation. The learning task is then posed as a model-finding task, in that the Boolean network is obtained as a model of the input first-order theory. With this framework, we support experimentally the hypothesis that attractor constraints reduce the number of state transition examples needed to identify the target model.
Copyright c by the paper’s authors. Copying permitted for private and academic purposes.
In: Nicolas Lachiche, Christel Vrain (eds.): Late Breaking Papers of ILP 2017, Orle´ans, France, September 4-6, 2017, published at http://ceur-ws.org
Our specific goal for this initial exploration is to test the hypothesis that by exploiting prior knowledge about attractors we may reduce significantly the number of transition examples needed to identify the target model. To test this, we need a learning framework capable to interpret constraints such as the model has exactly one periodic attractor of proper length 2. Such a framework is our secondary contribution. In particular, we design a framework in which the learned Boolean network can be obtained as a finite model of a first-order logic theory with equality. The theory consists of common axioms defining the semantics of propositional programs, problem-specific sentences expressing the global attractor constraints, and finally the known ground transitions. 2
We consider propositional variables V = fp1; : : : png. We are given a finite set of assignments (intepretations) I = fIk1 : : : ; Ikm g associated with discrete times ki 2 N , where each Ik : V ! f0; 1g. The model we seek consists of n propositional formulas i formed with variables in V . The formulas define (synchronous) state transitions, that is to say, pi is true at time k + 1 iff i is satisfied under the truth values of all variables at time k. The model thus fits I iff for any Ik; Ik+1 2 I, Ik+1(pi) = 1 iff Ik j= i. Denoting pi(k) Ik(pi), we can express the transitions as pi(k + 1) = i(p1(k) : : : pn(k)), treating i as a Boolean function.
In the rest of the paper we assume that the formulas i are literal conjunctions, and we adhere to the illustrative example
2 from [5], which is as follows
(
In the sequel, we explore how the model (i.e., the three formulas above) can be identified from I and from prior constrains regarding the model’s attractors. The strategy adopted is that the latter two, along with axioms regarding the syntax and semantics of propositional conjunctions are combined in a first-order theory T . The Boolean networks conforming to the said inputs are obtained as finite models of T . We next present two different approaches to such axiomatization. 3
Here, the vocabulary for forming T includes a constant for each propositional variable in V , so for the running example,
the constants are p; q; r. Further, we have a finite number of constants i1; i2; : : : corresponding to interpretations I1; I1; : : :
which we are also going to call states. With the running example, we have up to 8 such constants, depending on the set of
states present as examples in a particular experimental setting. Finally, we have a function symbol s representing the state
succession function. E.g. s(i1) = i2 stipulates that state I2 directly follows state I1. As for predicates, we include pos=2,
neg=2, and true=2 whose meaning we explain through the running example. The meaning of pos=2 is that if for instance
pos(q; p) holds, then q appears as a positive literal in the conjunction for p such as in (
The first axiom in T defines the semantics of conjunctive transitions. In particular, it expresses that if and only if a variable is true in the successor of a state S, then all variables with positive (negative) occurrence in the conjunction must be true (false) in S.
8S; V true(s(S); V ) $
8W (pos(W; V ) ! true(S; W )) ^ (neg(W; V ) ! :true(S; W )) The second axiom encodes the language bias for the propositional models by restricting the pos and neg relations to the constants p; q; r.
8V; W (pos(V; W ) _ neg(V; W )) !
(W = p _ W = q _ W = r) ^ (V = p _ V = q _ V = r)
The remaining formulas in T describe the particular learning instance. Each supplied interpretation Ik is encoded as a set
of ground facts; e.g. true(i1; p) and :true(i1; q) express respectively that p (q) is (not) true in I1. Further facts in the form
s(i2) = s3 postulate the known successions of states. The last group of formulas describe the known facts about attractors.
For example the formula
stipulates, under the presence of (
In general, T has multiple finite models M , M j= T , which all represent a correct solution to the learning problem. M
identifies the target system (
M (p) 0 1 0 M (q) 1 0 0 M (r) 0 1 0 neg(#; !) M (p) M (q) M (r)
M (p) 0 0 1
M (q) 0 0 0
M (r) 0 0 0
Here, M (p) stands for the domain element that p is mapped to by M , and analogically so for q and r. The tables do not
show the Cartesian products for other domain elements as they are all 0 due to axiom (
Our alternative axiomatization uses no predicates except for the special equality predicate. We introduce two constants t, f
representing the true and false Boolean values, and the following axiom making sure the two are different
Conjunctions are modeled through the function conj=9 satisfying the next axiom
(
To model the transitions (
8Ip; Iq; Ir p(Ip; Iq; Ir) = conj(Pp; Pq; Pr; Np; Nq; Nr; Ip; Iq; Ir) The remaining axioms are again specific for a learning instance. The known state transitions are encoded through ground facts such as
p(t; f; t) = f where the arguments stand for the truth values of p; q; r in the source state and the function value corresponds to the truth-value of the indicated variable in the successive state.
The following constraint expresses that there is an attractor state transiting to itself
To encode the existence of higher-order attractors, we proceed in a spirit analogical to the extension of (
Any model found for the theory consisting of the above formulas determines the transition rules by a full instantiation of the p=3; q=3; r=3 functions. The propositional formulas defining the function are determined from the Skolem constants assigned by the model to the existentially quantified variables in (10). ls1000 e d o m t s llae 100 m s f o r e bm 10 u n n a i d em 1 no constraint exactly 1 attractor with length 1 exactly 1 attractor with length 2 exactly 2 diff. attractors, unspec. lenghts exactly 2 attractors with lengths 1 and 2 no constraint eexxaaccttllyy 11 aattttrraaccttoorr wwiitthh lleennggtthh 21 exactly 2 diff. attractors, unspec. lenghts exactly 2 attractors with lengths 1 and 2 ls1000 e d o m t s lle 100 a m s f o r be 10 m u n n a e m 1 2 3
4 5 6 number of known transitions 7 8 2 3
4 5 6 number of known transitions 7 8
All experiments consists of finding finite models of theories T using the model finder Paradox [2], with the aim to identify
the Boolean model (
All experiments with the relational axiomatization include the common axioms (
For each experiment (i.e. each theory T ) multiple finite models are found in general. All resulting models of the functional axiomatization have the same domain size 2. The relational axiomatization produces models of different domain sizes and we discard all models larger than the smallest one.
The resulting model set always contains the model corresponding to (
To interpret the results comparatively, note that the learning approach from [5] needs all 8 observed transitions to identify the model. Complete sets of transitions are also required by other popular approaches to Boolean network learning [1]. 6
Although only with a simple example, we have found empirical support for the hypothesis that by exploiting for prior knowledge on the character of attractors of a Boolean network, such a network can be identified with a smaller number of state-transition examples.
To account for such attractor constraints in the learning process, we formulated a first-order framework for learning propositional formulas. Here, the learned network model is encoded in a finite model of a first-order theory, which specifies the learning instance. Interestingly, this setting contrasts with the well known ILP setting of learning from interpretations, where models represent input data and a first-order theory is searched.
This present framework is strong and allows more complex learning scenarios beyond those exemplified in the preceding sections. Virtually any part of the input theory can be missing (parts of known state transitions, entire transitions, knowledge on state successions, etc.) with the only consequence that the theory will allow a greater number of models. Conversely, any partial knowledge on the structure of the unknown Boolean network (the presence of a certain literal in a rule, entire rule, etc.) can be easily encoded in the input theory. Similar flexibility pertains to the language bias: while our axioms postulated conjunctions, they can be straightforwardly extended to DNF’s or other syntactical structures. Also, more interesting and complex constraints regarding attractors can be specified, which we do not demonstrate here due to limited space.
For this generality, we will likely pay with limited scalability. Although the reported runtimes for the running example used in this study was typically 0s with the Paradox model finder, the perspectives for larger tasks are rather dire, since the 1 These statistics pertain to the functional approach; the relational one exhibited almost identical trends. latter algorithm is based on a reduction to SAT preventing the exploitation of domain-specific heuristics. We thus plan to develop specialized algorithms for Boolean network learning, yet still able to interpret at least the rich attractor constraints.
On the other hand, the first-order axiomatization approach presented here could scale up to a slightly different flavor of Boolean network learning tasks, in which one would not aim at identifying a single ground Boolean model. In particular, using the axiomatization approach we could still reason through lifted inference about the properties of the Boolean network models conforming to prior knowledge (transitions, attractors) without the need to construct specific ground models. Indeed, such reasoning could be implemented by deriving consequences from the input theory through proof finding.