Model a sequence

Status

What other tools call it

Meridian's classification; an independent blind rating agreed on 86.2% of 312 rows (exact class, version 2).

Background

When to use it

In an HMM, the hidden process cannot be observed directly, so the goal is to learn about its state by observing the process whose outcomes depend on it.^[1] Asking for the distribution over hidden states at the end of an observed sequence is called filtering, and asking it of a point in the middle is called smoothing.^[1] Asking for the entire most likely sequence of hidden states suits problems such as part-of-speech tagging, where the hidden states are the parts of speech behind an observed sequence of words.^[1] Decide which question you are asking before choosing an algorithm: the state now, the state at some earlier point, or the whole path of states. (Meridian's view)

In an HMM, the hidden state at time t depends only on the hidden state at time t − 1, and the values at t − 2 and before have no influence, which is called the Markov property.^[1]

No tractable algorithm is known for finding the maximum likelihood estimate of an HMM's parameters exactly, but a local maximum can be derived efficiently with the Baum–Welch algorithm.^[1] In the hmmlearn library, training an HMM by the expectation–maximisation (EM) algorithm will generally get stuck in local optima.^[3] Train from several starting points and keep the model that scores best, rather than trusting a single run. (Meridian's view) In hmmlearn, a model fitted to a sequence drawn from another HMM can number its hidden states in a different order from the model that drew it.^[3]

RL is particularly well suited to problems that include a long-term versus short-term reward trade-off.^[2] In large environments, RL can be used where a model of the environment is known but no analytic solution is available, where only a simulation model is given, or where interacting is the only way to collect information.^[2] In RL, poorly designed reward functions can lead to unintended behaviours.^[2]

The method

The parameters of an HMM are of two types: transition probabilities, which govern how the hidden state at time t is chosen given the state at t − 1, and emission probabilities.^[1] In the standard HMM the hidden states are discrete, while the observations can be discrete, typically from a categorical distribution, or continuous, typically from a Gaussian distribution.^[1] The hmmlearn library provides HMMs with categorical, Gaussian, Gaussian mixture, multinomial and Poisson emissions.^[3]

The probability of an observed sequence is a sum over all possible hidden state sequences, and dynamic programming computes it efficiently with the forward algorithm.^[1] The Viterbi algorithm is a dynamic programming algorithm that finds the most likely sequence of hidden events that would explain a sequence of observed events.^[4] Andrew Viterbi proposed the Viterbi algorithm in 1967 as a decoding algorithm for convolutional codes over noisy digital communication links.^[4] The forward-backward algorithm is a good method for computing the smoothed values for all hidden state variables.^[1] In hmmlearn, the predict method decodes hidden states with either the Viterbi algorithm or maximum a posteriori estimation.^[3] In mlpack, mlpack_hmm_viterbi uses the Viterbi algorithm to return the most probable hidden state sequence of an observation sequence under a trained HMM.^[5]

The Baum–Welch algorithm is a special case of the EM algorithm used to find the unknown parameters of an HMM, and uses the forward-backward algorithm to compute the statistics for the expectation step.^[6] The Baum–Welch algorithm is named after its inventors, Leonard E. Baum and Lloyd R. Welch.^[6] HMMs and the Baum–Welch algorithm were first described in a series of articles by Baum and his peers at the IDA Center for Communications Research, Princeton, in the late 1960s and early 1970s.^[6] The Baum–Welch algorithm starts from random initial conditions, or from prior information about the parameters where it is available, which can speed it up and steer it toward the desired local maximum.^[6] The Baum–Welch forward procedure numerically underflows for longer sequences, which a modified algorithm avoids by scaling the forward and backward quantities.^[6] In mlpack, mlpack_hmm_train trains an HMM with the Baum–Welch algorithm if no labels are provided, and accepts an optional file of hidden states for labelled training.^[5]

Basic RL is modelled as a Markov decision process (MDP): a set of states, a set of actions, the probability of moving between states under each action, and the immediate reward after each transition.^[2] The goal of an RL agent is to learn a policy, giving the probability of taking each action in each state, that maximises the expected cumulative reward.^[2] An RL agent chooses between trying new actions to learn more about the environment, called exploration, and using current knowledge to take the best action, called exploitation.^[2] Q-learning is an RL algorithm that trains an agent to assign values to its possible actions based on its current state, without requiring a model of the environment.^[7] Q-learning was introduced by Chris Watkins in 1989, and a convergence proof was presented by Watkins and Peter Dayan in 1992.^[7] In mlpack, an RL agent requires a policy to choose actions and a replay method to sample previous experiences.^[8] In mlpack's random replay, the interactions between agent and environment are saved to a memory buffer at each time step, and previous experiences are sampled from it to train the agent.^[8]

Compared with the alternatives

Unlike classical dynamic programming, RL algorithms do not assume knowledge of an exact mathematical model of the MDP, and they target large MDPs where exact methods become infeasible.^[2]

HMMs can be generalised to continuous state spaces, and where the hidden process is a linear dynamical system with Gaussian variables, exact inference is tractable with the Kalman filter.^[1] In general, exact inference in HMMs with continuous latent variables is infeasible, and approximate methods such as the extended Kalman filter or the particle filter must be used.^[1] For time series prediction with HMMs, Bayesian inference methods such as Markov chain Monte Carlo (MCMC) sampling have been shown to be favourable over a single maximum likelihood model in accuracy and stability.^[1] MCMC imposes a significant computational burden, and variational approximations to Bayesian inference offer computational efficiency comparable to EM.^[1]

Sources

1. [1]Hidden Markov modelsecondary source
2. [2]Reinforcement learningsecondary source
3. [3]Tutorialdocumentation
4. [4]Viterbi algorithmsecondary source
5. [5]mlpack CLI binding documentationdocumentation
6. [6]Baum–Welch algorithmsecondary source
7. [7]Q-learningsecondary source
8. [8]Reinforcement Learning Tutorialdocumentation