# A Simplified Matrix Formulation for Sensitivity Analysis of Hidden Markov Models
## 2 Background
### Hidden Markov Models
#### 2.1.1 Inference in HMMs  
In temporal models, inference means computing the conditional probability distribution of \(X\) at time \(t\), given the evidence up to and including time \(T\), that is \(p(X^{t}|\mathbf{y_{e}^{1:T}})\). The main inference tasks include _filtering_ for \(T=t\), _prediction_ of a future state for \(t>T\) and _smoothing_, that, is inferring the past for \(t<T\). In an HMM, the _Forward-Backward algorithms_ are used for the inference tasks and training of the model using an iterative procedure called the _Baum-Welch method (Expectation Maximization)_[28; 29; 30]. The _Forward-Backward algorithms_ computes the following probabilities for all hidden states \(i\) at time \(t\leq T\):* forward probability \(F(i,t)=p(x_{i}^{t},\mathbf{y}_{\mathbf{e}}^{1:t})\), and
* backward probability \(B(i,t)=p(\mathbf{y}_{\mathbf{e}}^{t+1:T}|x_{i}^{t})\)  
resulting in  
\[\begin{split} p(x_{i}^{t}|\mathbf{y}_{\mathbf{e}}^{1:T})& =\frac{p(x_{i}^{t},\mathbf{y}_{\mathbf{e}}^{1:T})}{p(\mathbf{y}_{ \mathbf{e}}^{1:T})}=\frac{p(x_{i}^{t},\mathbf{y}_{\mathbf{e}}^{1:T})}{\sum_{j =1}^{n}p(x_{j}^{t},\mathbf{y}_{\mathbf{e}}^{1:T})}=\frac{p(x_{i}^{t},\mathbf{y} _{\mathbf{e}}^{1:t})\cdot p(\mathbf{y}_{\mathbf{e}}^{t+1:T}|x_{i}^{t})}{\sum_{ j=1}^{n}p(x_{j}^{t},\mathbf{y}_{\mathbf{e}}^{1:T})\cdot p(\mathbf{y}_{ \mathbf{e}}^{t+1:T}|x_{j}^{t})}\\ &=\frac{F(i,t)\cdot B(i,t)}{\sum_{j=1}^{n}F(j,t)\cdot B(j,t)} \end{split} \tag{1}\]  
For \(T<t\), the algorithm can be applied by taking \(B(i,t)=1\) and adopting the convention that the configuration of an empty set of observations is TRUE, i.e., \(\mathbf{y}_{\mathbf{e}}^{T+1:t}\equiv TRUE\), giving  
\[F(i,t)=p(x_{i}^{t},\mathbf{y}_{\mathbf{e}}^{1:t})=p(x_{i}^{t},\mathbf{y}_{ \mathbf{e}}^{1:T},TRUE)=p(x_{i}^{t},\mathbf{y}_{\mathbf{e}}^{1:T})\]  
As shown in Equation (1), any conditional probability \(p(x_{i}^{t}|\mathbf{y}_{\mathbf{e}}^{1:T})\) can be calculated from the joint probabilities \(p(x_{i}^{t},\mathbf{y}_{\mathbf{e}}^{1:T})\) for all hidden states \(i\) using [PERSON] theorem. Since our objective is sensitivity analysis of the HMM output probability of interest for parameter variations, in the remainder of this paper our focus will be on the joint probabilities \(p(x_{i}^{t},\mathbf{y}_{\mathbf{e}}^{1:T})\) for all hidden states \(i\).  
The other important inference tasks are the _prediction of future observations_, i.e., \(p(\mathbf{y}_{\mathbf{e}}^{t}|\mathbf{y}_{\mathbf{e}}^{1:T})\) for \(t>T\), finding the most probable explanation, i.e., \(arg\max_{x_{i}^{1:t}}p(x_{i}^{1:t}|\mathbf{y}_{\mathbf{e}}^{1:t})\) using the _Viterbi Algorithm_ and learning the HMM parameters as new observations come in using the _Baum-Welch algorithm_, which can be achieved by the _Forward-Backward algorithms_. The _prediction of future observations_ can be computed as the fraction of the two probabilities \(p(\mathbf{y}_{\mathbf{e}}^{t},\mathbf{y}_{\mathbf{e}}^{1:T})\), \(t>T\), and \(p(\mathbf{y}_{\mathbf{e}}^{1:T})\), which are computed using forward probabilities.  
\[p(\mathbf{y}_{\mathbf{e}}^{1:t})=\sum_{i=1}^{n}p(x_{i}^{t},\mathbf{y}_{ \mathbf{e}}^{1:t})=\sum_{i=1}^{n}F(i,t)\]  
Note that if \(t>T+1\), then \(p(\mathbf{y}_{\mathbf{e}}^{t},\mathbf{y}_{\mathbf{e}}^{1:T})\) can be computed by setting all in-between observations \(\mathbf{y}_{\mathbf{e}}^{k}\), \(t>k>T\), to \(TRUE\) as above.  
Figure 1: (**a**) An example of an HMM representation. (**b**) Its dynamic Bayesian network representation, unrolled for \(T\) time slices.