Hidden Markov model (HMM): model parameter estimation

It is estimated that HMM Model parameters , According to whether the observation sequence corresponds to the state sequence , It can be divided into supervised learning algorithm and unsupervised learning algorithm .

1. Supervised learning estimation HMM Model parameters

Suppose the given training data contains $n$ Observation sequence and corresponding state sequence （ The length of different observation sequences can be the same , It can be different ）$\{(X_1,Y_1),(X_2,Y_2),\cdots ,(X_n,Y_n)\}$, When the state and hang test sequence are known , The model parameter values on each sample can be obtained by direct statistics according to the definition of model parameters , Then the estimation of model parameters can be obtained by calculating the expectation on all samples of the whole training data set .

1.1 Transfer probability $a_{ij}$ Estimation

Set the first $k$ Among samples ,$t$ Always in the State $s_i$、$t+1$ Always in the State $s_j$ The frequency of is $A_{ij}$, So the state transition probability $a_{ij}$ My estimate is ：
$${\hat{a}}_{ij}=\frac{{\sum }_{k=1}^n{A}_{ij}}{{\sum }_{k=1}^n{\sum }_{j=1}^N{A}_{ij}},i=1,2,\cdots ,N;j=1,2,\cdots ,N\text{\hspace{1em}(1.1)}$$

1.2 Observed probability of occurrence $b_j(v_l)$ Estimation

Set the first $k$ Among samples , Status as $s_j$ And the observation is $o_l$ The frequency of this is $B_{jl}$, Then the observed probability of occurrence $b_j(v_l)$ My estimate is ：
$${\hat{b}}_j(o_l)=\frac{{\sum }_{k=1}^n{B}_{jl}}{{\sum }_{k=1}^n{\sum }_{l=1}^M{B}_{jl}},i=1,2,\cdots ,N;l=1,2,\cdots ,M\text{\hspace{1em}(1.2)}$$

1.3 Initial state probability ${\pi }_i$ Estimation

Initial state probability ${\pi }_i$ My estimate is $n$ Among samples , The frequency of the corresponding state ：
$${\hat{\pi }}_i=\frac{1}{n}\sum _{k=1}^{n}if(y_1=s_i,1,0),i=1,2,\cdots ,N\text{\hspace{1em}(1.3)}$$

2. Unsupervised learning estimation HMM Model parameters

Because the cost of status tagging is high , So only the observation sequence data is given 、 Request estimate HMM Model parameters are more common . Assume that the training data only contains a length of $T$ The sequence of observations $X$ And there's no corresponding state sequence $Y$, The goal is to estimate the parameters of hidden Markov model $\lambda =(A,B,\pi )$. In this case , Sequence of States $Y$ Is an unobservable hidden variable （hidden variable）,HHM The model is a probability model with hidden variables ：

$$P(X|\lambda )=\sum _{Y}P(X,Y|\lambda )=\sum _{Y}P(X|Y,\lambda )P(Y|\lambda )\text{\hspace{1em}(2.1)}$$ according to EM Algorithm ,HHM The maximum likelihood estimation of model parameters is ¹：
$$\hat{\lambda }=\underset{\lambda }{\mathrm{argmax}}Q(\lambda ,\bar{\lambda })\text{\hspace{1em}(2.2)}$$$$Q(\lambda ,\bar{\lambda })=\sum _{Y}P(X,Y|\bar{\lambda })\cdot logP(X,Y|\lambda )\text{\hspace{1em}(2.3)}$$

according to $Q$ Function definition ,$type(2.3)$ Omitted $\lambda$ The constant factor of $1/P(X|\lambda )$.

Because by definition ,HMM In the model
$$P(X,Y|\lambda )={\pi }_{i_1}{b}_{i_1}(x_1)\cdot a_{i_1{i}_2}{b}_{i_2}(x_2)\cdots a_{i_{T-1}{i}_T}{b}_{i_T}(x_T)$$

So the algorithm based on logarithm , The subitems involved in each parameter of the model in parameter estimation can be disassembled and collected ,$type(2.3)$ It can be rewritten as follows ：
$$Q(\lambda ,\bar{\lambda })=\sum _{Y}log({\pi }_{i_1})\cdot P(X,Y|\bar{\lambda })+\sum _Y[\sum _{t=1}^{T-1}log(a_{i_t{i}_{t+1}})]\cdot P(X,Y|\bar{\lambda })+\sum _Y[\sum _{t=1}^{T}log(b_{i_t}(x_t))]\cdot P(X,Y|\bar{\lambda })$$
therefore , Find the model parameters $\lambda$ Maximum likelihood estimation of , It can be converted to separate calculation Maximum likelihood estimation of each parameter of the model ：
$${\hat{\pi }}_i=\underset{{\pi }_i}{\mathrm{argmax}}\sum _{Y}log({\pi }_{i_1})\cdot P(X,Y|\bar{\lambda })\text{\hspace{1em}(2.4)}$$$${\hat{a}}_{ij}=\underset{{\pi }_i}{\mathrm{argmax}}\sum _Y[\sum _{t=1}^{T-1}log(a_{i_t{i}_{t+1}})]\cdot P(X,Y|\bar{\lambda })\text{\hspace{1em}(2.5)}$$$${\hat{b}}_j(k)=\underset{{\pi }_i}{\mathrm{argmax}}\sum _Y[\sum _{t=1}^{T}log(b_{i_t}(x_t))]\cdot P(X,Y|\bar{\lambda })\text{\hspace{1em}(2.6)}$$

2.1 Initial state probability ${\pi }_i$ Estimation

$${\hat{\pi }}_i=\underset{{\pi }_i}{\mathrm{argmax}}\sum _{Y}log({\pi }_{i_1})\cdot P(X,Y|\bar{\lambda })\text{\hspace{1em}(2.4)}$$$${\hat{\pi }}_i=\underset{{\pi }_i}{\mathrm{argmax}}\sum _{i=1}^{N}log({\pi }_i)\cdot P(X,y1=s_i|\bar{\lambda })\text{\hspace{1em}(2.1.1)}$$

be aware ${\pi }_i$ Meet the constraints ${\sum }_{i=1}^N{\pi }_i=1$, Write $type(2.1.1)$ Lagrange function of ：

$$\sum _{i=1}^{N}log({\pi }_i)\cdot P(X,y1=s_i|\bar{\lambda })+\gamma (\sum _{i=1}^N{\pi }_i-1)\text{\hspace{1em}(2.1.2)}$$

Yes $type(2.1.2)$ About ${\pi }_i$ And make the result equal to 0, have to ：

$$\frac{P(X,y1=s_i|\bar{\lambda })}{{\pi }_i}+\gamma =0$$$$P(X,y1=s_i|\bar{\lambda })+\gamma {\pi }_i=0\text{\hspace{1em}(2.1.3)}$$

Yes $type(2.1.3)$ All in $i$ Sum of possible situations , obtain ：

$$\sum _{i=1}^N[P(X,y1=s_i|\bar{\lambda })+\gamma {\pi }_i]=0$$$$\sum _{i=1}^{N}P(X,y1=s_i|\bar{\lambda })+\gamma \sum _{i=1}^N{\pi }_i=0\text{\hspace{1em}(2.1.4)}$$ because
$$\{\begin{array}{l}{\sum }_{i=1}^{N}P(X,y1=s_i|\bar{\lambda })=P(X|\bar{\lambda })\\ \\ {\sum }_{i=1}^N{\pi }_i=1\end{array}$$ therefore
$$\gamma =-P(X|\bar{\lambda })\text{\hspace{1em}(2.1.5)}$$

So bring it into $type(2.1.3)$ after , Get parameters ${\pi }_i$ Maximum likelihood estimation of ：

$${\hat{\pi }}_i=\frac{P(X,y1=s_i|\bar{\lambda })}{P(X|\bar{\lambda })}\text{\hspace{1em}(2.1.6)}$$

2.2 Transfer probability $a_{ij}$ Estimation

$${\hat{a}}_{ij}=\underset{{\pi }_i}{\mathrm{argmax}}\sum _Y[\sum _{t=1}^{T-1}log(a_{i_t{i}_{t+1}})]\cdot P(X,Y|\bar{\lambda })\text{\hspace{1em}(2.5)}$$$${\hat{a}}_{ij}=\underset{{\pi }_i}{\mathrm{argmax}}\sum _{i=1}^N\sum _{j=1}^N\sum _{t=1}^{T-1}log(a_{ij})\cdot P(X,y_t=s_i,y_{t+1}=s_j|\bar{\lambda })\text{\hspace{1em}(2.2.1)}$$
Empathy , The application has constraints ${\sum }_{j=1}^N{a}_{ij}=1$ Lagrange multiplier method , We can work out $a_{ij}$ Maximum likelihood estimation of ：

$${\hat{a}}_{ij}=\frac{{\sum }_{t=1}^{T-1}P(X,y_t=s_i,y_{t+1}=s_j|\bar{\lambda })}{{\sum }_{t=1}^{T-1}P(X,y_t=s_i|\bar{\lambda })}\text{\hspace{1em}(2.2.2)}$$

2.3 Observed probability of occurrence $b_j(v_l)$ Estimation

$${\hat{b}}_j(k)=\underset{{\pi }_i}{\mathrm{argmax}}\sum _Y[\sum _{t=1}^{T}log(b_{i_t}(x_t))]\cdot P(X,Y|\bar{\lambda })\text{\hspace{1em}(2.6)}$$$${\hat{b}}_j(k)=\underset{{\pi }_i}{\mathrm{argmax}}\sum _{j=1}^N[\sum _{t=1}^{T}log(b_j(x_t))]\cdot P(X,y_t=s_j|\bar{\lambda })\text{\hspace{1em}(2.3.1)}$$
The Lagrange multiplier method is also applied , The constraint is ${\sum }_{k=1}^M{b}_j(k)=1$. Be careful , Only in $x_t=o_k$ when $b_j(x_t)$ Yes $b_j(k)$ The partial derivative of is not always 0, Get $b_j(k)$ Maximum likelihood estimation of ：

$${\hat{b}}_j(k)=\frac{{\sum }_{t=1}^{T}P(X\cap {\bar{x}}_t,x_t=o_k,y_t=s_j|\bar{\lambda })}{{\sum }_{t=1}^T{\sum }_{k=1}^{M}P(X\cap {\bar{x}}_t,x_t=o_k,y_t=s_j|\bar{\lambda })}$$

2.4 Baum-Welch Algorithm implementation

Input ： Observation sequence of random process
Output ： Maximum likelihood estimation of hidden Markov model parameters .

（1） initialization
about $n=0$, Select any that meets the defined range $a_{ij}^{(0)},b_j(k{)}^{(0)},{\pi }_i^{(0)}$, Get the initial value of model parameters ${\lambda }^{(0)}=(A^{(0)},B^{(0)},{\pi }^{(0)})$;

（2） Iterative training
$$a_{ij}^{(n+1)}=\frac{{\sum }_{t=1}^{T-1}{\xi }_t(i,j|X,{\lambda }^{(n)})}{{\sum }_{t=1}^{T-1}{\gamma }_t(i|X,{\lambda }^{(n)})}$$
$$b_j(k{)}^{(n+1)}=\frac{{\sum }_{t=1,x_t=o_k}^{T-1}{\gamma }_t(j|X,{\lambda }^{(n)})}{{\sum }_{t=1}^{T-1}{\gamma }_t(j|X,{\lambda }^{(n)})}$$
$${\pi }_i^{(n+1)}={\gamma }_1(i|X,{\lambda }^{(n)})$$
In style ${\xi }_t(i,j)$ and ${\gamma }_t(i)$ from HMM Forward algorithm and backward algorithm of the model are introduced , Please refer to the author's article for the specific derivation process ： The hidden Markov model （HMM）： Calculate the probability of occurrence of the observation sequence No 4 Section .

（3） End
When ${\lambda }^{(n+1)}$ Almost no longer changes or changes are less than a given threshold （ That is, it has converged ） when , Stop iterative training . Get the maximum likelihood estimation of the model parameters ：
$$\{\begin{array}{l}{\hat{a}}_{ij}=a_{ij}^{(n+1)}\\ \\ {\hat{b}}_j(k)=b_j(k{)}^{(n+1)}\\ \\ {\hat{\pi }}_i={\pi }_i^{(n+1)}\end{array}$$

---

1. Derivation process , See the author's article ：EM Algorithm （expectation maximization algorithm） Maximum likelihood estimation method of parameters of probability model with hidden variables ︎