Fitting Feature-Dependent Markov Chains

S. Barratt and S. Boyd

Journal of Global Optimization, 87(2–4):329–346, November 2023.

We describe a method for fitting a Markov chain, with a state transition matrix that depends on a feature vector, to data that can include missing values. Our model consists of a separate logistic regressions for each row of the transition matrix. We fit the parameters in the model by maximizing the log-likelihood of the data minus a regularizer. When there are missing values, the log-likelihood becomes intractable, and we resort to the expectation-maximization (EM) heuristic. We illustrate the method on several examples, and describe our efficient Python open-source implementation.