Understanding the in uences between components of dynamical systems such as biological networks, cellular automata or social networks provides insights to their dynamics. In uences of such dynamical systems can be represented by logic programs with delays. Logical methods that learn logic programs from observations have been developed, but their practical use is limited since they cannot handle noisy input and need a huge amount of data to give accurate results. In this paper, we present a method that learns to distinguish di erent dynamical systems with delays based on Recurrent Neural Network (RNN). This method relies on Long Short-Term Memory (LSTM) to extract and encode features from input sequences of time series data. We show that the produced high dimensional encoding can be used to distinguish di erent dynamical systems and reproduce their speci c behaviors.
Being able to learn the dynamics of an environment purely by observing has many applications. For example, in multi-agent systems where learning other agents' behavior without direct access to their internal state can be crucial for decision making [10]. In system biology, learning the interaction between genes can greatly help in the creation of drugs to treat sicknesses [17].
In: Nicolas Lachiche, Christel Vrain (eds.): Late Breaking Papers of ILP 2017, Oeans, France, September 4-6, 2017, published at http://ceur-ws.org
Several learning algorithms have been proposed, that learn rules for a system, provided that the observations given cover every case that can happen within the system. However, most real world systems, particularly in system biology, obtaining data for even a short amount of time is di cult, time consuming and expensive. Therefore most current learning algorithms, while complete, are not practical in the biology setting. In addition to that, most real world observations that can be obtained are often full of random noise. Therefore, dealing with noise is also an integral part in solving this problem. The focus of this paper is therefore on being able to learn the rules despite some of the rules not having manifested in the observation. We also consider the setting in which actions from past states are able to have a delayed in uence on the current state. In addition, our proposed model can also deal with noise within the data, that no previous approaches dealt with, as shown in the experiments section. 1.2
In this paper, we propose an approach to this problem utilizing Recurrent Neural Networks (RNN) to learn a logic program representation from a series of boolean state transitions. Our method is based on a framework called Learning from Interpretation Transition (LFIT) [9]. LFIT is an unsupervised learning algorithm, that can learn logic programs describing fully the dynamics of the system, purely by observing state transitions. In our approach, we construct two neural networks, one for encoding the observed state transitions, and another one of which to produce the logic program representation for the system. The idea behind this is that given a series of state transitions with a large enough length, it should be possible to uniquely identify the system. Therefore we can transform this into a classi cation problem, in which we attempt to classify which logic program a speci c series of state transition belongs to. Neural networks are known to be good at performing classi cation, which makes them suitable tools for our proposed approach.
Our proposed approach works well even with a limited amount of data. This is possible because the neural network used in our model is not trained to model the dynamical system itself, but rather to output a classi cation of di erent systems. Therefore, it can be trained on arti cial data prior to being applied to real data. Thus it is easy to see that the amount of data obtained has no direct relation with the performance of our model.
The rest of the paper is organized as follows. We cover some of the prior researches in Section 2, following by introducing the logical and neural network background required in Section 3. Then we present the RNN-LFIT approach in Section 4. We pursue by presenting an experimental evaluation demonstrating the validity of an approach in Section 5 before concluding the paper in Section 6. 2 2.1
One way of implementing the LFIT algorithm is by relying on a purely logical method. In [9], such an algorithm is introduced. It constructs an NLP by doing bottom-up generalization for all the positive examples provided in the input state transition. An improved version of this algorithm, utilizing binary decision diagrams as internal data structures, was introduced in [15]. These methods, while proven to be theoritically correct, generate rules from every positive examples. The resulting NLP has been proven to be non-minimal, and thus not very humanfriendly. To allow practical use of the resulting NLP, a method for learning minimal NLP was introduced in [14]. In [16], an algorithm that learns delayed in uences, that is cause/e ect relationship that may be dependent on the previous k time steps, is introduced. Another recent development in the prolongation of the logical approach to LFIT is the introduction of an algorithm which deals with continuous values [18].
This class of algorithms that utilizes logical methods, are proven to be complete and sound, however a huge disadvantage with these methods is that the resulting NLP is only representable of the observations that have been fed to the algorithm thus far. Any observations that did not appear in the input, will be predicted as either to be always true or always false depending on the algorithm used. 2.2
To deal with the shortcomings stated in the previous paragraph, an algorithm that utilizes neural networks (NN)
was proposed [
There are also several other approaches attempting to tie NNs with logic programming [
In [11], the authors proposed a method for constructing models of dynamical systems using RNNs. However,
this approach su ers from its important need of training data, which increases exponentially as the number of
variables grow. This is a well-known computational problem called the curse of dimensionality [
In contrast to these methods, the method proposed in this paper does not assume there exists a direct relation between the trained RNN model and the observed system. Our model aims at classifying a series of state transition to the system that generated it, whereas each of the NN based approaches listed above aims to train a NN model that predicts the next state of the observed system. 3 3.1
The main goal of LFIT is to learn a normal logic program (NLP) describing the dynamics of the observed system. NLP is a set of rules of the form
A
A1 ^ A2 ^ Am ^ :Am+1 ^ ^ :An where A and Ai are propositional atoms, n m 0. : and ^ are the symbols for logical negation and conjunction. For any rule R of the form 1, the atom A is called the head of R and is denoted as h(R). The conjunction to the right of is called the body of R. We represent the set of literals in the body of R as b(R) = fA1; : : : ; Am; :Am+1; : : : ; :Ang. The set of all propositional atoms that appear in a particular Boolean system is denoted as the Herbrand base B.
An Herbrand interpretation I is a subset of B. For a logic program P and an Herbrand interpretation I, the immediate consequence operator (or TP operator) is the mapping TP : 2B ! 2B:
TP (I) = fh(R) j R 2 P; b+(R)
I; b (R) \ I = ;g: Given a set of Herbrand interpretations E and fTP (I) j I 2 Eg, the LFIT algorithm outputs a logic program P which completely represents the dynamics of E.
In the case of Markov(k) systems (i.e. systems with delayed e ects of at most k time steps), we can de ne the timed Herbrand base of a logic program P , denoted by Bk, as follows: k [ i=1 Bk = fvt i j v 2 Bg (1) (2) (3) where t is a constant term which represents the current time step. Given a Markov(k) system S, if all rules R 2 S are such that h(R) 2 B and b(R) 2 Bk, then we represent S as a logic program P with Herbrand base Bk. A trace of execution T of S is a nite sequence of states of S. We can de ne T as T = (x0; : : : ; xn); n 1; xi 2 2B. Thus a k-step interpretation transition is (I; J ) where I Bk; J B. 3.2
A multi-layer perceptron (MLP) is a type of feed-forward neural network. An MLP usually consists of one input layer, one or more hidden layer and an output layer. Each layer is fully connected, and the output layer is activated by a non-linear function. MLPs can be trained using backpropagation by gradient descent.
Fig. 1: An LSTM memory cell
The other neural network that we use to learn the system's dynamics is Long Short-Term Memory (LSTM) [8]. LSTM is a form of RNN that, contrary to earlier RNNs, can learn long term dependencies and do not su er from the vanishing gradient problem. It has been popular in many sequence to sequence mapping application such as machine translation [19]. An LSTM consists of a memory cell for each time step, and each memory cell has an input gate it, an output gate ot and a forget gate ft. When a sequence of nX time steps X = fx1; x2; : : : ; xnX g is given as input, LSTM calculates the following for each time step: 0it 1 0 lt
tanh ct = ft ct 1 + it lt ht = ot ct 1 CC W A ht 1 xt where W is a weight matrix, ht is the output of each memory cell, ct is the hidden state of each memory cell and lt is the input to each memory cell. is the sigmoid function. The input gate decides how much of the input in uences the hidden state. The forget gate decides how much of the past hidden state in uences the current hidden state. The output gate is responsible for deciding how much of the current hidden state in uences the output. A visual illustration of a single LSTM memory cell is shown in Figure 1.
LSTM networks can be trained by performing backpropagation through time (BPTT) [
It can easily be seen that the connections in an LSTM model are complex, and it can be very complicated to attempt to extract or derive relations from the inner architecture of the network. Therefore we forgo the approach of extracting rules from the model, and propose a di erent method which instead utilizes the LSTM to classify the di erent inputs depending on the system that generated them. 4
In this section, we propose an architecture for performing LFIT. It consists of an encoder and decoder for the state transitions, and a neural network for performing LFIT. A visualization of the architecture is shown in Figure 3 and 4. The input for the whole model is the sequence of state transitions obtained from observing the target system. The output of the model is an encoding of an approximation of the logic program representation in ... x1 x2 xt
LSTM matrix form. However, we will be performing evaluation of the performance of the model based on the predicted state.
Given a series of state transitions XT = (x1; x2; : : : ; xT ), where xt 2 [0; 1] represents the state of the system at time t, our goal is to predict xT +1. Note that to be able to deal with noise and continuous values, we are not restricting the domain of xt to Z2. If we obtain a representation of XT in the form of a vector x, we can learn a matrix P, with which we can perform matrix multiplication as Px = xT +1. This can be thought of as performing the TP operator in algebraic space.
The training objective function of the model is de ned as:
n min 1 X(x(Ti+)1 W n i=1 yT(i+)1)2 + kWk22 (4) where W is the set of neural network weights, xT +1 is the prediction of the model, yT +1 is the truth state, kWk22 is the weight decay regularization [12] with hyperparameter .
The input state transition is fed to both the encoder and the LFIT model, as can be seen in the gure. We describe the responsibilities of the three neural network models in the following sections.
LSTM The autoencoder for the input sequences is responsible for encoding discrete time series into a feature vector that can later be manipulated by the neural network. This sequence of vectors is then encoded into one feature vector of dimension 2 ka la, where ka denotes the number of memory cell units in the autoencoder LSTM and la denotes the number of LSTM layers. This amount is doubled because both c and h, which represent the state of the memory cell, are considered. 4.2
This LSTM network can be thought of as performing LFIT. This network takes as input the state transitions and an initial program encoding and outputs a program encoding that is consistent with the observations, which is the same as the de nition of the LFIT algorithm. Although in practice, this network is responsible for classifying the series of state transition to the corresponding logic program representation.
The produced output is the representation of the normal logic program. The observations are the same input sequence as that given to the autoencoder. The dimensions of the matrix output by this network is (2 ll kl; 2 la ka), where kl denotes the number of memory cell units in this network and ll denotes the number of layers.
In this work, the initial program is always set to ; and the LSTM network is trained to produce the complete normal logic program representation. In future work, it could be easily extended so as to accept background knowledge. 4.3
The decoder is responsible for mapping the product of the NLP matrix and the state transition vector into a state vector that represents the predicted following state. The decoder can theoritically be any function that maps a continuous vector into a binary vector. We detail the model used in Section 4.4.
The goal of the architecture is to produce an encoding of past states, and an encoding of a normal logic program, that can then be multiplied together to predict the next state transition. This multiplication is a matrix vector multiplication and produces a vector of Rn where n is the number of features in the logic program representation. This can be thought of as performing the Tp operator within linear geometric space. A MLP then decodes this vector into the desired boolean state vector.
With the encoding of the state transition and an initial program, the LFIT network learns to produce an encoded program based on the observed state transitions. This encoded program can then be used for prediction, and in future work we plan to decode it into a normal logic program thus making it possible to reason with it. 4.4
In our experiment, the autoencoder takes a series of 10 state transitions, where each state is a 10 dimensional vector which represents the state of each variable within the system. The autoencoder LSTM model we trained has 2 layers, each with 512 memory cell units. The produced state representation is then multiplied by a (2 2 512; 128) matrix, to produce a 128 dimension feature vector that represents the series of state transitions.
The LFIT model takes the same input as the encoder model, but the LSTM model has 4 layers, 4 being the dimension of the resulting feature vector for the predicted state, and has 1,024 hidden units which is twice the number of hidden units of the autoencoder model. The produced logic program representation is then transformed into (4; 128) matrix by multiplying it with a (2 4 1024; 4 128) matrix and then reshaping.
The decoder model takes the resulting feature vector for the predicted state, which is a vector of 4 dimensions, and outputs a vector of 10 dimensions with each dimension representing the state of the variables within the system. The decoder model consists of a MLP with 1 hidden layer, and each layer has 8 hidden units. Each hidden layer is activated by ReLU (Recti ed Linear Unit), which is a function that outputs 0 for all input less than 0, and is linear when the input is larger than 0. The nal output layer is activated by a sigmoid function, which is de ned as (x) = 1=(1 + exp( x)). The sigmoid function has a range of [0; 1], which is suitable for our use where we want the MLP to output a boolean vector, with noise. The decoder model is simple, this is to avoid the decoder over tting and thus preventing the LFIT model and the encoder model from learning. 5
We applied our model to learn the dynamics of Boolean networks from continuous time series. The Boolean
network used in this experiment is adapted from Dubrova and Teslenko [
v n RMSE = tuu n1 X(y^i i=1 yi)2 (5) where y^i denotes the predicted value and yi is the actual value.
The initial state vector is generated by giving each of the 10 variables a random value between 0 and 1. Generated states are then mapped back to real values: 0 becomes 0:25 + and 1 becomes 0:75 + , where 2 ( 0:25; 0:25), chosen randomly simulates the measurement noise.
We used the following training parameters for our experiment: { Training steps: 104 { Batch size: 100 { Gradient descent optimizer: Adam, learning rate and various other parameters are left with the defaults for
Tensor ow r1.2
{ Dropout: probability of 0.3 per training step
{ Regularization hyperparameter of 0.2
The model was implemented on Tensor ow r1.2 [
Training data is generated randomly by rst randomly generating logic rules and grouping them together as NLPs. Then the initial state is set as the zero vector, and we continuously perform the TP operator to generate all the consequent states. Variables referring to delays before the initial state is assumed to be 0. In order to assure e ective training of the model, we only train on data that varies a lot. We do so by calculating the standard deviation of all states that are generated from a certain NLP, and only keeping those with standard deviation greater than or equal 0.4. We show some of the accepted NLPs in table 3.
Here, we consider two methods for training the model. One by training the model with data without noise, that is the training data is strictly Z2. Another way of training the model is by training on data with added noise. Each model is trained with 50 acceptable NLPs, generating 500 data points from each NLP, and training for a total of 4 hours. We evaluate each method in the following section. 5.1 In this paper we propose a method for learning a matrix representation of dynamical systems with delays. One of the interesting aspects of this approach is that it produces a logic program representation in matrix form, which when multiplied with a feature vector of the past states, is able to compute a vector that represents the predicted state. This could lead to future works such as reasoning and performing induction purely in the algebraic space.
The main contribution of this work is to devise a method of modeling systems where only limited amounts of data can be collected. Without su cient amount of data, purely logical methods cannot provide useful information, and attempts at training neural networks to model the system will result in over tting. Therefore we speculate that generating arti cial data in order to train a more generalized neural network may be a more successful approach in such cases. We also managed to show that the devised method is resilience to noise, where purely logical methods are not able to deal with.
As future work, we are planning to adapt the current method to take as input a partial program as background knowledge to the network and to decode the NLP representation into logical form to allow humans to reason with. We also hope to evaluate the predictions made by this model with other similar models. 8. Hochreiter, S., Schmidhuber, J.: Long short-term memory. Neural computation 9(8), 1735{1780 (1997) 9. Inoue, K., Ribeiro, T., Sakama, C.: Learning from interpretation transition. Machine Learning 94(1), 51{79 (2014) 10. Jennings, N.R., Sycara, K., Wooldridge, M.: A roadmap of agent research and development. Autonomous Agents and
Multi-Agent Systems 1(1), 7{38 (Jan 1998), https://doi.org/10.1023/A:1010090405266 11. Khan, A., Mandal, S., Pal, R.K., Saha, G.: Construction of gene regulatory networks using recurrent neural networks and swarm intelligence. Scienti ca 2016 (2016) 12. Krogh, A., Hertz, J.A.: A simple weight decay can improve generalization. In: Proceedings of the 4th International Conference on Neural Information Processing Systems. pp. 950{957. NIPS'91, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1991), http://dl.acm.org/citation.cfm?id=2986916.2987033 13. Mart nez, D., Alenya, G., Ribeiro, T., Inoue, K., Torras, C.: Relational reinforcement learning for planning with exogenous e ects. Journal of Machine Learning Research 18(78), 1{44 (2017), http://jmlr.org/papers/v18/16-326.html 14. Ribeiro, T., Inoue, K.: Learning prime implicant conditions from interpretation transition. In: ILP 2015, pp. 108{125.
Springer (2015) 15. Ribeiro, T., Inoue, K., Sakama, C.: A BDD-based algorithm for learning from interpretation transition. In: Proc. ILP 2013, LNAI 8812. pp. 47{63. Springer (2014) 16. Ribeiro, T., Magnin, M., Inoue, K., Sakama, C.: Learning delayed in uences of biological systems. Frontiers in bioengineering and biotechnology 2 (2014) 17. Ribeiro, T., Magnin, M., Inoue, K., Sakama, C.: Learning multi-valued biological models with delayed in uence from time-series observations. In: 14th IEEE International Conference on Machine Learning and Applications, ICMLA 2015, Miami, FL, USA, December 9-11, 2015. pp. 25{31 (2015) 18. Ribeiro, T., Tourret, S., Folschette, M., Magnin, M., Borzacchiello, D., Chinesta, F., Roux, O., Inoue, K.: Inductive learning from state transitions over continuous domains. In: Proceedings of ILP 2017, to appear. Springer (2017) 19. Sutskever, I., Vinyals, O., Le, Q.V.: Sequence to sequence learning with neural networks. In: Advances in neural information processing systems. pp. 3104{3112 (2014) 20. Williams, R.J., Peng, J.: An e cient gradient-based algorithm for on-line training of recurrent network trajectories.
Neural Computation 2, 490{501 (1990) 21. Wold, S., Esbensen, K., Geladi, P.: Principal component analysis. Chemometrics and Intelligent Laboratory Systems 2(1), 37 { 52 (1987), http://www.sciencedirect.com/science/article/pii/0169743987800849, proceedings of the Multivariate Statistical Workshop for Geologists and Geochemists
:ft 2 ^ :ft 3 ^ :ht 4 gt at 2 ^ dt 3 ^ :gt 2 ^ :ct 3 ht :jt 5 ^ :et 4 ^ :gt 5 ^ :ft 1 it :et 4 jt :it 5 Table 3: Example NLPs that are randomly generated and used for training