# Build a quasi Markov chain model using Deep Learning

My problem is similar to Markov Discrete Process, with one little but - it doesn't have true markov property. a probability to move to next state rarely depend only on current state but rather on 3-10 previous states.. these numbers (3-10) are not known and are a guess.

I want an idea on how to approach this using a deep learning machine (RNN perhaps) which will discover most robust patterns (most statistically stable dependencies between the current state and previous states), one state can be part of many patterns simultaneosly.

Then I want the machine to predict next state as a matrix of probabilities for each possible values, that is if there are 5 possible values for each states then I need 5 prob numbers for one predicted state. Similar to markov's transition matrix.

how would you approach this problem from a DL prospective?

P.S. it appears to be a case of continuous unsupervised learning

## 1 Answer

If you have no requirement concerning programming language, it might be easiest to get started with keras.

Roughly you want to approach the problem as follows:

• convert your discrete input sequence into one-hot vectors (i.e. vectors where only one of the dimensions is 1, all the others are 0. The amount of dimensions of a one-hot vector equals the amount of possible values)
• add an embedding layer to your network (an embedding layer converts your sparse vectors into more dense vector representations that contain some semantic information)
• feed the output of that layer into a stateful LSTM layer (important to have a stateful network)
• feed the output of the LSTM layer into a dense timedistributed layer with softmax activation function. The output dimension of this layer is again the amount of possible values such that the weights of this layer give the probabilities for the next value assignment.

If all of this seems confusing, you're going to need to read up on some of these concepts. Perhaps starting here: http://karpathy.github.io/2015/05/21/rnn-effectiveness/

• No its not confusing. I use keras for another task exactly in a way you described. The stateful lstm with batch size 1. I didn't think of one hot encoding though. Why do you think it's better than just feed the actual values (the range in my task is 3000 possible values)?. . However in this particular case my problem with keras that it needs a known sequence length. But this process is continuous unsupervised learning. So I will need an encoder decoder lstm ie seq2seq. And I find it difficult to trust keras in this case. It seems more a as hack to me. any comments? – Boppity Bop Aug 10 '17 at 18:04
• P.s. there are 3 inputs in reality. One us the 3000 values I can do one hot with but the others are real numbers.. I expect the machine to learn patterns using all 3 as there is intrinsic relations between them which I am not able to analyse in mathematical sense.. hence I am asking for a DL solution – Boppity Bop Aug 10 '17 at 18:07
• P.p.s. I asked on keras forum if anyone replicated Karpathy results in Keras but haven't got an answer. – Boppity Bop Aug 10 '17 at 18:08
• One-hot encoding tends to work better for discrete input since networks tend to get confused when using integers to represent discrete values. If your input were words for example, it would make no sense to represent the word 'cat' by 1 and 'ketchup' by 2. One-hot combined with the embedding layer allows to go from discrete to continuous in a sensible way. The fact that you have 3 inputs complicates matters a little bit but I think you could simply add 2 extra dimensions to your one-hot vectors for the other two real numbers. You might want to look into normalizing those extra inputs however. – GR4 Aug 10 '17 at 19:13
• Regarding seq2seq, in my experience it is true that keras is not great with that. I know there are some libraries on github that are supposed to help with that, but don't think they work with variable length (or at least some time ago). If you want to do this with keras you will probably need to add padding, possibly with buckets depending on the variability of your input. – GR4 Aug 10 '17 at 19:15