This is a tutorial paper for Hidden Markov Model (HMM). First, we brieﬂy review the background on Expectation Maximization (EM), Lagrange multiplier, factor graph, the sum-product algo- rithm, the max-product algorithm, and belief propagation by the forward-backward procedure. Then, we introduce probabilistic graphical mod- els including Markov random ﬁeld and Bayesian network. Markov property and Discrete Time Markov Chain (DTMC) are also introduced. We, then, explain likelihood estimation and EM in HMM in technical details. We explain evalua- tion in HMM where direct calculation and the forward-backward belief propagation are both explained. Afterwards, estimation in HMM is covered where both the greedy approach and the Viterbi algorithm are detailed. Then, we explain how to train HMM using EM and the Baum- Welch algorithm. We also explain how to use HMM in some applications such as speech and action recognition. 1. Introduction Assume we have a time series of hidden random variables. We name the hidden random variables as states (Ghahra- mani, 2001). Every hidden random variable can generate (emit) an observation symbol or output. Therefore, we have a set of states and a set of observation symbols. A Hidden Markov Model (HMM) has some hidden states and someemitted observation symbols (Rabiner, 1989). HMM mod- els the the probability density of a sequence of observed symbols (Roweis, 2003). This paper is a technical tutorial for evaluation, estima- tion, and training in HMM. We also explain some applica- tions for HMM. There exist many different applications for HMM. One of the most famous applications is in speech recognition (Rabiner, 1989; Gales et al., 2008) where an HMM is trained for every word in the speech (Rabiner & Juang, 1986). Another application of HMM is in action recognition (Yamato et al., 1992) because an action can be seen as a sequence or times series of poses (Ghojogh et al., 2017; Mokari et al., 2018). An interesting applica- tion of HMM, which is not trivial in the ﬁrst glance, is in face recognition (Samaria, 1994). The face can be seen as a sequence of organs being modeled by HMM (Neﬁan & Hayes, 1998). Usage of HMM in DNA analysis is another application of HMM (Eddy, 2004). The remainder of paper is as follows. In Section 2, we re- view some necessary background for the paper. Section 3 introduces probabilistic graphical models. Expectation maximization in HMM is explained in Section 4. after- wards, evaluation, estimation, and training in HMM are explain in Sections 5, 6, and 7, respectively. Some applica- tions are introduced in more details in Section 8. Finally, Section 9 concludes the paper. 2. Background Some background required for better understanding of the HMM algorithms is mentioned in this Section. 2.1. Expectation Maximization This section is taken from our previous paper (Ghojogh et al., 2019). Sometimes, the data are not fully observ- Hidden Markov Model: Tutorial 2 able. For example, the data are known to be whether zero or greater than zero. As an illustration, assume the data are collected for a particular disease but for convenience of the patients participated in the survey, the severity of the dis- ease is not recorded but only the existence or non-existence of the disease is reported. So, the data are not giving us complete information as Xi>0is not obvious whether is Xi= 2orXi= 1000 . In this case, MLE cannot be directly applied as we do not have access to complete information and some data are missing. In this case, Expectation Maximization (EM) (Moon, 1996) is useful. The main idea of EM can be sum- marized in this short friendly conversation: – What shall we do? The data are missing! The log- likelihood is not known completely so MLE cannot be used. – Mmm, probably we can replace the missing data with something... – Aha! Let us replace it with its mean. – You are right! We can take the mean of log-likelihood over the possible values of the missing data. Then every- thing in the log-likelihood will be known, and then... – And then we can do MLE! AssumeD(obs)andD(miss )denote the observed data ( Xi’s = 0in the above example) and the missing data ( Xi’s>0 in the above example). The EM algorithm includes two main steps, i.e., E-step and M-step. Letbe the parameter which is the variable for likelihood estimation. In the E-step, the log-likelihood `(), is taken expectation with respect to the missing data D(miss )in or- der to have a mean estimation of it. Let Q()denote the expectation of the likelihood with respect to D(miss ): Q() := ED(miss )jD(obs);[`()]: (1) Note that in the above expectation, the D(obs)andare conditioned on, so they are treated as constants and not ran- dom variables. In the M-step, the MLE approach is used where the log- likelihood is replaced with its expectation, i.e., Q(); therefore: b = arg max Q(): (2) These two steps are iteratively repeated until convergence of the estimated parameters b. 2.2. Lagrange Multiplier Suppose we have a multi-variate function Q(1;:::; K) (called “objective function”) and we want to maximize (or minimize) it. However, this optimization is constrained and its constraint is equality P(1;:::; K) =cwherecis a constant. So, the constrained optimization problem is: maximize 1;:::;KQ(1;:::; K); subject to P(1;:::; K) =c:(3) Figure 1. (a) An example factor graph, and (b) its representation as a bipartite graph. For solving this problem, we can introduce a new variable which is called “Lagrange multiplier”. Also, a new func- tionL(1;:::; K;), called “Lagrangian” is introduced: L(1;:::; K;) =Q(1;:::; K)  P(1;:::; K)c :(4) Maximizing (or minimizing) this Lagrangian function gives us the solution to the optimization problem (Boyd & Vandenberghe, 2004): r1;:::;K;Lset= 0; (5) which gives us: r1;:::;KLset= 0 =) r 1;:::;KQ=r1;:::;KP; rLset= 0 =)P(1;:::; K) =c: 2.3. Factor Graph, The Sum-Product and Max-Product Algorithms, and The Forward-Backward Procedure 2.3.1. F ACTOR GRAPH A factor graph is a bipartite graph where the two partitions of graph include functions (or factors) fj;8jand the vari- ablesxi;8i(Kschischang et al., 2001; Loeliger, 2004). Ev- ery factor is a function of two or more variables. The vari- ables of a factor are connected by edges to it. Hence, we have a bipartite graph. Figure 1 shows an example factor graphs where the factor and variable nodes are represented by circles and squares, respectively. 2.3.2. T HESUM-PRODUCT ALGORITHM Assume we have a factor graph with some variable nodes and factor nodes. For this, one of the nodes is considered as Hidden Markov Model: Tutorial 3 the root of tree. The result of algorithm does not depend on which node to be taken as the root (Bishop, 2006). Usually, the ﬁrst variable or the last one are considered as the root. Then, some messages from the leaf (or leaves) are sent up on the tree to the root (Bishop, 2006). The messages can be initialized to any ﬁxed constant values (see Eq. (8)). The message from the variable node xito its neighbor factor nodefjis: mxi!fj=Y f2N(xi)nfjmf!xi; (6) wheref2N(xi)nfjmeans all the neighbor factor nodes to the variable xiexceptfj. Also,mxi!fjandmf!xi denote the message from the variable xito the factor fj and the message from the factor fto the variable xi, re- spectively. The message from a the factor node fjto its neighbor variable xiis: mfj!xi=X values ofx2N(fj)nxifjY x2N(fj)nximx!fj:(7) The Eq. (6) includes both sum and product. This is why this procedure is named the sum-product algorithm (Kschischang et al., 2001; Bishop, 2006). In the factor graph, if the variable xihas degree one, the message is: mxi!fj= [1;1;:::; 1]>2Rk; (8) wherekis the number of possible values that the variables can get. Moreover, if the variable xihas degree two con- nected tofjandf`, the message is: mxi!fj=mf`!xi: (9) A good example for better understanding of Eqs. (6) and (7) exists in chapter 8 in (Bishop, 2006). For the exact convergence (and inference) of belief prop- agation, the graph should be a tree, i.e., should be cycle- free (Kschischang et al., 2001). If the factor graph has cycles, the inference is approximate where the algorithm is stopped after a while manually. The belief propagation in such graphs is called loopy belief propagation (Murphy et al., 1999; Bishop, 2006). Note that Markov chains are cycle-free so the exact belief propagation can be applied for them. It is also noteworthy that as every variable which is con- nected to only two factor nodes merely passes the message through (see Eq. (9)), a new graphical model, named nor- mal graph (Forney, 2001), was proposed which states every variable as an edge rather than a node (vertex). More details about factor graph and sum-product algorithm can be found in