# How to classify an arbitrary chain of states(features)?

I'm trying to figure out how to build a classification model based on some states.

I have an arbitrary number of states s1, s2, s3,...,sn that can lead to two outcomes a1, a2 (basically the labels of the classification)

And I can have any number of states that can give a classification. For example:

s1 -> a1
s1,s2 -> a1
s3 -> a2
s1,s3,s7 -> a2
s1,s3,s1,s7,s3 -> a1


I've read about Markov Chains but I don't understand if this would be a good solution or not because in the end I only need the probability of either reaching state a1 or a2

• Can each subject only ever be in one state at any given time? If so, I might look at it in terms of states being applied to the subject, one after another. In which case, it turns into a similar problem to this (posed by me just a few days ago) - my solution was to construct features that encapsulated the chronology of these events, with the aim of using them in a logistic regression (which would bring you one step closer towards your goal of classification) – Ben Mar 8 '18 at 13:22
• @Ben I don't think this is a solution for me as the number of states is very large. – djWann Mar 8 '18 at 13:53

Markov Chains does not look to be a solution. The reason is that MC use the fact that the conditional distribution fitted uses a fixed number of past dependent variables. In it’s simplest form it fits the state at time t given only information about a fixed number of states from t-1 to t-p, together with ergodicity assumption.

In other words it has a short fixed memory. The short memory problem fix was introduced by recurrent neural networks. This was refined with LSTM which introduced the idea of selective forgetness. Finally, I strongly suggest them for your problem, also because they allow variable length inputs.