A Markov chain is a belief network with random variables in a sequence, where each variable only directly depends on its predecessor in the sequence. Markov chains are used to represent sequences of values, such as the sequence of states in a dynamic system or language model. Each point in the sequence is called a stage.

Figure 9.14 shows a generic Markov chain as a belief network. The network has five stages, but does not have to stop at stage $4$; it can extend indefinitely. The belief network conveys the independence assumption

which is called the Markov assumption.

Often the sequences are in time, and $S_t$ represents the state at time $t$. The state conveys all of the information about the history that could affect the future. The independence assumption of the Markov chain can be seen as “the future is conditionally independent of the past given the state.”

A Markov chain is a stationary model or time-homogenous model if the variables all have the same domain, and the transition probabilities are the same for each stage:

To specify a stationary Markov chain, two conditional probabilities are provided:

• •

  $P(S_0)$ specifies the initial conditions

• •

  $P(S_{i+1}\mid S_i)$ specifies the dynamics, which is the same for each $i\ge 0$.

The sharing of the parameters for the conditional probability is known as parameter sharing or weight tying, as used in convolutional neural networks.

Stationary Markov chains are of interest for the following reasons:

• •

  They provide a simple model that is easy to specify.

• •

  The assumption of stationarity is often the natural model, because the dynamics of the world typically does not change in time. If the dynamics does change in time, it is usually because of some other feature that could also be modeled as part of the state.

• •

  The network extends indefinitely. Specifying a small number of parameters gives an infinite network. You can ask queries or make observations about any arbitrary points in the future or the past.

To determine the probability distribution of state $S_i$, variable elimination can be used to sum out the preceding variables. The variables after $S_i$ are irrelevant to the probability of $S_i$ and need not be considered. To compute $P(S_i\mid S_k)$, where $i>k$, only the variables between $S_i$ and $S_k$ need to be considered, and if , only the variables less than $k$ need to be considered.

A stationary distribution of a Markov chain is a distribution of the states such that if it holds at one time, it holds at the next time. Thus, $P$ is a stationary distribution if for each state $s$, $P(S_{i+1}=s)=P(S_i=s)$. Thus

Every Markov chain with a finite number of states has at least one stationary distribution. The distribution over states encountered in one infinite run (or the limit as the number of steps approaches infinity) is a stationary distribution. Intuitively, if an agent is lost at time $i$, and doesn’t observe anything, it is still lost at time $i+1$. Different runs might result in different parts of the state space being reached, and so result in different stationary distributions. There are some general conditions that result in unique stationary distributions, which are presented below.

A Markov chain is ergodic if, for any two states $s_1$ and $s_2$, there is a nonzero probability of eventually reaching $s_2$ from $s_1$.

A Markov chain is periodic with period $p$ if the difference between the times when it visits the same state is always divisible by $p$. For example, consider a Markov chain where the step is per day, so $S_{i+1}$ is the state on the day after $S_i$, and where the day of the week is part of the state. A state where the day is Monday is followed by a state where the day is Tuesday, etc. The period will be (a multiple of) 7; a state where the day is Monday can only be a multiple of 7 days from a state where the day is also Monday. If the only period of a Markov chain is a period of 1, then the Markov chain is aperiodic.

If a Markov chain is ergodic and aperiodic, then there is a unique stationary distribution, and this is the equilibrium distribution that will be approached from any starting state. Thus, for any distribution over $S_0$, the distribution over $S_i$ will get closer and closer to the equilibrium distribution, as $i$ gets larger.

The box gives an application of Markov chains that formed the basis of Google’s initial search engine.

A hidden Markov model (HMM) is an augmentation of a Markov chain to include observations. A hidden Markov model includes the state transition of the Markov chain, and adds to it observations at each time that depend on the state at the time. These observations can be partial in that different states map to the same observation and noisy in that the same state can map to different observations at different times.

The assumptions behind an HMM are:

• •

  The state at time $t+1$ only directly depends on the state at time $t$ for $t\ge 0$, as in the Markov chain.

• •

  The observation at time $t$ only directly depends on the state at time $t$.

The observations are modeled using the variable $O_t$ for each time $t$ whose domain is the set of possible observations. The belief-network representation of an HMM is depicted in Figure 9.15. Although the belief network is shown for five stages, it extends indefinitely.

A stationary HMM includes the following probability distributions:

• •

  $P(S_0)$ specifies initial conditions

• •

  $P(S_{t+1}\mid S_t)$ specifies the dynamics or the belief state transition function

• •

  $P(O_t\mid S_t)$ specifies the sensor model.

There are a number of tasks that are common for HMMs.

The problem of filtering or belief-state monitoring is to determine the current state based on the current and previous observations, namely to determine

All state and observation variables after $S_i$ are irrelevant because they are not observed and can be ignored when this conditional distribution is computed.

The problem of smoothing is to determine a state based on past and future observations. Suppose an agent has observed up to time $k$ and wants to determine the state at time $i$ for ; the smoothing problem is to determine

All of the variables $S_i$ and $V_i$ for $i>k$ can be ignored.

Standard belief-network algorithms, such as recursive conditioning or variable elimination, can be used to carry out monitoring or smoothing. However, it is possible to take advantage of the fact that time moves forward and that the agent is getting observations in time and is interested in its state at the current time.

In belief monitoring or filtering, an agent computes the probability of the current state given the history of observations. The history can be forgotten. In terms of the HMM of Figure 9.15, for each time $i$, the agent computes $P(S_i\mid o_0,\mathrm{\dots },o_i)$, the distribution over the state at time $i$ given the observation of $o_0,\mathrm{\dots },o_i$. As in exact inference, a variable is introduced and summed out to enable the use of known probabilities:

Suppose the agent has computed the previous belief based on the observations received up until time $i-1$. That is, it has a factor representing $P(S_{i-1}\mid o_0,\mathrm{\dots },o_{i-1})$. This is just a factor on $S_{i-1}$. To compute the next belief, it multiplies this by $P(S_i\mid S_{i-1})$, sums out $S_{i-1}$, multiplies this by the factor $P(o_i\mid S_i)$, and normalizes.

Multiplying a factor on $S_{i-1}$ by the factor $P(S_i\mid S_{i-1})$ and summing out $S_{i-1}$ is an instance of matrix multiplication. Multiplying the result by $P(o_i\mid S_i)$ is the dot product.

Smoothing is the problem of computing the probability distribution of a state variable in an HMM given past and future observations. The use of future observations can make for more accurate predictions. Given a new observation, it is possible to update all previous state estimates with one sweep through the states using variable elimination; see Exercise 9.14.

Recurrent neural networks (RNNs) can be seen as neural network representations of reasoning in a hidden Markov model. An RNN models how $S_i$ depends on $o_i$ and $S_{i-1}$ using a differentiable function. They need to be trained on data for the task being performed, typically smoothing. An HMM is designed to be more modular; learning transition functions and sensor models separately allows for different forms of reasoning, such as smoothing, and the ability to modularly add sensors or modify the dynamics.

The state at a particular time need not be represented as a single variable. It is often more natural to represent the state in terms of features.

A dynamic belief network (DBN) is a discrete time belief network with regular repeated structure. It is like a (hidden) Markov model, but the states and the observations are represented in terms of features. If $F$ is a feature, we write $F_t$ as the random variable that represented the value of variable $F$ at time $t$. A dynamic belief network makes the following assumptions:

• •

  The set of features is the same at each time.

• •

  For any time $t>0$, the parents of variable $F_t$ are variables at time $t$ or time $t-1$, such that the graph for any time is acyclic. The structure does not depend on the value of $t$ (except $t=0$ is a special case).

• •

  The conditional probability distribution of how each variable depends on its parents is the same for every time $t>0$. This is called a stationary model.

Thus, a dynamic belief network specifies a belief network for time $t=0$, and for each variable $F_t$ specifies $P(F_t\mid parents(F_t))$, where the parents of $F_t$ are in the same or previous time steps. As in a belief network, directed cycles are not allowed.

The model for a dynamic belief network is represented as a two-step belief network, which represents the variables at the first two times (times 0 and 1). That is, for each feature $F$ there are two variables, $F_0$ and $F_1$. The set of parents of $F_0$, namely $parents(F_0)$, can only include variables for time 0. The resulting graph must be acyclic. Associated with the network are the probabilities $P(F_0\mid parents(F_0))$ and $P(F_1\mid parents(F_1))$.

The two-step belief network is unfolded into a belief network by replicating the structure for subsequent times. In the unfolded network, $P(F_i\mid parents(F_i))$, for $i>1$, has exactly the same structure and the same conditional probability values as $P(F_1\mid parents(F_1))$.

One of the problems with the definition of an HMM or a dynamic belief network is that the model depends on the time granularity. The time granularity specifies how often a dynamic system transitions from one state to the next. The time granularity could either be fixed, for example each day or each thirtieth of a second, or it could be event based, where a time step occurs when something interesting occurs. If the time granularity were to change, for example from daily to hourly, the conditional probabilities would also change.

One way to model the dynamics independently of the time granularity is to model continuous time, where for each variable and each value for the variable, the following are specified:

• •

  a distribution of how long the variable is expected to keep that value (e.g., an exponential decay) and

• •

  what value it will transition to when its value changes.

Given a discretization of time, where time moves from one state to the next in discrete steps, a dynamic belief network can be constructed from this information. If the discretization of time is fine enough, ignoring multiple value transitions in each time step will result only in small errors.

Markov chains are the basis of simple language models, which have proved to be very useful in various natural language processing tasks in daily use.

Assume that a document is a sequence of sentences, where a sentence is a sequence of words. Consider the sorts of sentences that people may speak to a system or ask as a query to a help system. They may not be grammatical, and often contain words such as “thx” or “zzz”, which may not be typically thought of as words.

In the set-of-words model, a sentence (or a document) is treated as the set of words that appear in the sentence, ignoring the order of the words or whether the words are repeated. For example, the sentence “how can I phone my phone” would be treated as the set $\{$“can”, “how”, “I”, “my”, “phone”$\}$.

To represent the set-of-words model as a belief network, as in Figure 9.22, there is a Boolean random variable for each word. In this figure, the words are independent of each other (but they do not have to be). This belief network requires the probability of each word appearing in a sentence: , , …, . To condition on the sentence “how can I phone my phone”, all of the words in the sentence are assigned true, and all of the other words are assigned false. Words that are not defined in the model are either ignored, or are given a default (small) probability. The probability of sentence $S$ is $\left({\prod }_{w\in S}P(w)\right)\ast \left({\prod }_{w\notin S}(1-P(w))\right)$.

A set-of-words model is not very useful by itself, but is often used as part of a larger model, as in the following example.

In a bag-of-words or unigram model, a sentence is treated as a bag (multi-set) of words, representing the number of times a word is used in a sentence, but not the order of the words. Figure 9.24 shows how to represent a unigram as a belief network. For the sequence of words, there is a variable $W_i$ for each position $i$, with domain of each variable the set of all words, such as . The domain is often augmented with a symbol, “$\perp$”, representing the end of the sentence, and with a symbol “?” representing a word that is not in the model.

To condition on the sentence “how can I phone my phone”, the word $W_1$ is observed to be “how”, the variable $W_2$ is observed to be “can”, etc. Word $W_7$ is assigned $\perp$. Both $W_4$ and $W_6$ are assigned the value “phone”. There are no variables $W_8$ onwards.

The unigram model assumes a stationary distribution, where the prior distribution of $W_i$ is the same for each $i$. The value of $P(W_i=w)$ is the probability that a randomly chosen word is $w$. More common words have a higher probability than less common words.

In a bigram model, the probability of each word depends on the previous word in the sentence. It is called a bigram model because it depends on pairs of words. Figure 9.25 shows the belief-network representation of a bigram model. This needs a specification of $P(W_i\mid W_{i-1})$.

To make $W_1$ not be a special case, introduce a new word $\perp$; intuitively $\perp$ is the “word” between sentences. For example, is the probability that the word “cat” is the first word in a sentence. is the probability that the sentence ends after the word “cat”.

In a trigram model, each triple of words is modeled. This is represented as a belief network in Figure 9.26. This requires $P(W_i\mid W_{i-2},W_{i-1})$; the probability of each word given the previous two words.

In general, in an n-gram model, the probability of each word given the previous $n-1$ words is modeled. This requires considering each sequence of $n$ words, and so the complexity of representing this as a table grows with $w^n$, where $w$ is the number of words. Figure 9.27 shows some common unigram, bigram, and trigram probabilities.

The conditional probabilities are typically not represented as tables, because the tables would be too large, and because it is difficult to assess the probability of a previously unknown word, or the probability of the next word given a previously unknown word or given an uncommon phrase. Instead, one could use context-specific independence, such as, for trigram models, represent the probability of the next word conditioned on some of the pairs of words, and if none of these hold, use $P(W_i\mid W_{i-1})$, as in a bigram model. For example, the phrase “frightfully green” is not common, and so to compute the probability of the next word, , it is typical to use , which is easier to assess and learn.

Transformers, when used in generative language models, are n-gram models, where $n$ – the window size of the transformer – is very large (in GPT-3, $n$ is 2048). A neural network, using attention, gives the probability of the next word given the previous words in the window. Note that a transformer model used in an encoder to find a representation for a text uses the words after, as well as the words before, each word.

Any of these models could be used in the help system of Example 9.36, instead of the set-of-words model used there. These models may be combined to give more sophisticated models, as in the following example.

A topic model predicts the topics of a document from the sentences typed. Knowing the topic of a document helps people find the document or similar documents even if they do not know what words are in the document.

It is possible to mix these patterns, for example by using the current topics to predict the word in a predictive typing model with a topic model.

Models based on n-grams cannot represent all of the subtleties of natural language, as exemplified by the following example.