---
# System prepended metadata

title: $Let's\ Talk\ about\ \\ Hidden\ Markov\ Model\ (HMM)$

---

# $Let's\ Talk\ about\ \\ Hidden\ Markov\ Model\ (HMM)$
##### $Kevin\ Kuo$ $5/30/2017$

## $Graphic\ Illustration$
---
![](https://i.imgur.com/t4oPj0a.png =300x200)
##### graphic resource: from wikipedia
- $X$$:observed$ $state$ 
- $Z$$:hidden$ $state$
- $T$$:transition$ $probability$
- $\varepsilon$$:emission$ $probability$ 
---
## $A\ Little\ Example\ with$ $State$$-$$Machine Expression$
![](https://i.imgur.com/Bjoxkyx.png =400x400)
##### graphic resource: from wikipedia 
- $initial\ distribution$ $=$ $arrays\ from\ Start$
- $observed$ $state$ $=$ $Dizzy/Cold/Normal$ 
- $hidden$ $state$ $=$ $Healthy/Fever$
- $transition$ $probability$  $=$ $balck$ $arrays$
- $emission$ $probability$  $=$ $blue/red$ $arrays$

## $Types\ of\ Problem$

- $Prediction\ or\ Smoothing$
  ${\displaystyle P(z(k)\ |\ x(1),\dots ,x(t)),k \leq t}$ 
 $use\ forward$$/$$backward\ algorithm$

 
- $Decoding$ $/$ $Sampling$
 ${\displaystyle P([z(1)\dots z(t)]|[x(1)\dots ,x(t)])\,}$ 
 $use\ Viterbi\ algorithm$

---
### $Introduction$
---
(tutorial resource from youtube channel "mathematicalmonk",there are many resources about machine learning on it)
#### 
![](https://i.imgur.com/1YZxRtz.png)
![](https://i.imgur.com/c2TWsHt.png)
![](https://i.imgur.com/I85Dano.png)
![](https://i.imgur.com/StrxQiK.png)

#### $It\ seems\ like\ flip-flop\ gate\ in\ the\ circuit$
---

### $Forward-Backward\ Algorithm$
---

![](https://i.imgur.com/qxYykjB.png)
![](https://i.imgur.com/2BIhsro.png)
![](https://i.imgur.com/7Z58UQm.png)

![](https://i.imgur.com/kB88ts0.png)
![](https://i.imgur.com/6ZXabWz.png)
![](https://i.imgur.com/KkmDoaU.png)
#### $\sum P(E)P(T)\alpha$ 

![](https://i.imgur.com/zZaAhHV.png)
### $Comparing\ with\ Naive\ Approach:$ 
![](https://i.imgur.com/01R0rd5.png)
#### -$F/B(linear\ scale)\ vs\ Naive(exponential \ scale)$

#### -$Dynamic\ programming\ uses\ earlier\ computation\ \\ to\ reduce\ the\ computation\ complexity$

#### -$Set\ up\ a\ recursion(Luckly\ you\ might\ solve\ the\ problem\ numerically\ \\ without\ checking\  both\ HTTING\ TIME\ and\ \\ MEAN\ RECURRENT\ TIME )$
---
### $Backward\ Algorithm$
---
![](https://i.imgur.com/o5ihrVC.png)
![](https://i.imgur.com/mXyo0dj.png)
![](https://i.imgur.com/XxzQ2RP.png)

---
### [$Solve\ the\ underflow\ problem\ when\ using\ computer\ (skip)$](https://www.youtube.com/watch?v=-RVM21Voo7Q)
- [$related\ page$](https://hackmd.io/KYdgnAJgbBAcCGBaAxhALGRaAMVMCMAzWAJkUMOFgEYwBmbEKbYIA===)

---
### $Viterbi\ Algorithm$

---

![](https://i.imgur.com/ftua3jt.png)
![](https://i.imgur.com/trwMX3j.png)
![](https://i.imgur.com/Vu53MXo.png)
![](https://i.imgur.com/lksv3q9.png)

---
## $Implementation\ in\ Python\ Programming$
### $Use$ [$HMMlearn\ package$](http://hmmlearn.readthedocs.io/en/stable/)

```python=
"""
Sampling from HMM
-----------------

This script shows how to sample points from a Hiden Markov Model (HMM):
we use a 4-components with specified mean and covariance.

The plot show the sequence of observations generated with the transitions
between them. We can see that, as specified by our transition matrix,
there are no transition between component 1 and 3.
"""
print(__doc__)

import numpy as np
import matplotlib.pyplot as plt

from hmmlearn import hmm

##############################################################
# Prepare parameters for a 4-components HMM
# Initial population probability
startprob = np.array([0.6, 0.3, 0.1, 0.0])
# The transition matrix, note that there are no transitions possible
# between component 1 and 3
# i.e. four channel of real number with Gaussian distribution rather than fixed numbers
transmat = np.array([[0.7, 0.2, 0.0, 0.1],
                     [0.3, 0.5, 0.2, 0.0],
                     [0.0, 0.3, 0.5, 0.2],
                     [0.2, 0.0, 0.2, 0.6]])
# The means of each component(emission)
means = np.array([[0.0,  0.0],
                  [0.0, 11.0],
                  [9.0, 10.0],
                  [11.0, -1.0]])
# The covariance of each component
covars = .5 * np.tile(np.identity(2), (4, 1, 1))

# Build an HMM instance and set parameters
model = hmm.GaussianHMM(n_components=4, covariance_type="full")

# Instead of fitting it from the data, we directly set the estimated
# parameters, the means and covariance of the components
model.startprob_ = startprob
model.transmat_ = transmat
model.means_ = means
model.covars_ = covars
###############################################################

# Generate samples
X, Z = model.sample(500)

# Plot the sampled data
plt.plot(X[:, 0], X[:, 1], ".-", label="observations", ms=6,
         mfc="orange", alpha=0.7)

# Indicate the component numbers
for i, m in enumerate(means):
    plt.text(m[0], m[1], 'Component %i' % (i + 1),
             size=17, horizontalalignment='center',
             bbox=dict(alpha=.7, facecolor='w'))
plt.legend(loc='best')
plt.show()

```

### $We\ Derive\ the\ transition\ path\ by\ random\ sampling$
![](https://i.imgur.com/V5NLw83.png)
---

## $Baidu\ Jieba$
---
遇到沒見過的中文單詞，將詞彙視為observed state,詞性視為hidden state

```python=
import jieba

str="小明會維特比演算法 小明好棒棒"
seg=jieba.cut(str)
print(",".join(seg))
```
![](https://i.imgur.com/3WMo7rI.png)




## $This\ is\ all\ for\ today$ $,$ $thank\ you$ $!$