# Hidden Markov Model @paisley2016bayesianmodel We have a single sequence $(x_1, x_2, \dots, x_T)$ where each $x_t \in \{1, \dots, V\}$ Often the data is in $R^d$. That would require a slightly different modeling approach than what we will discuss below. Incidentally, discrete-valued sequences often arise from what are originally continuous-valued sequences. For example, you can take the original data in $R^d$ and quantize it by first running a [Clustering](clustering.org) algorithm (K-means is the usual one) and then mapping $x_t \in R^d$ to a value $x_t \in \{1, \dots, V \}$ , where the value indicates which of the V clusters the original xt was mapped to. # Parameters - Three Parameters of a K-state HMM ## Hidden State $\pi$: A K-dimensional probability vector used to generate $s_1$ ## Transition Matrix $A$: A K x K Markov transition matrix. $A_{ij}$ is a probability of transitioning to state $j$ given that the current state is $i$. ## Emission Matrix $B$: A K x V emission matrix. $B_{iv}$ is a probability of observing $x = v$ given its corresponding state $s = i$. # Generative Model - Probablistic Model Construction ## Generate State Sequence $ \begin{align*} s_1 &\sim \text{Discrete}(\pi) \\ s_t | s_{t-1} &\sim \text{Discrete}(A_{s_{t-1}, :}) \\ \end{align*} $ ## Generate Observation Sequence $ \begin{align*} x_t | s_t &\sim \text{Discrete}(B_{s_t, :}) \end{align*} $ # Maximum Likelihood Expectation Maximization - Note taken on \[2020-07-24 Fri 23:38\]\ how many of these do I have to compute, is the question here ## Goal: Find a Point Estimate of H = {π, A, B} That Maximizes the Marginal Likelihood $ \begin{align*} \ln(p(x | H)) = \ln\left(\sum_s p(x, s | H)\right) \end{align*} $ - Note that since there are $T$ sequences, the time complexity is O(K^T^). ## Insight of HMM we don't need to compute this marginal distribution. we only need to be able to write out the joint likelihood over x and s ## Writing Out Joint Likelihood $ \begin{align*} p(x, s | H) &= \underbrace{p(x | s, B)}_{\text{emission}} \ \underbrace{p(s | A, \pi)}_{\text{transition}} \end{align*} $ $ \begin{align*} &=\left[\prod_{t=1}^T p(x_t | s_t, B)\right] \left[ p(s_1 | \pi) \prod_{t=2}^T p(s_t | s_{t-1}, A) \right] \end{align*} $ $ \begin{align*} &=\left[ \prod_{t=1}^T \prod_{k=1}^K \prod_{v=1}^V B_{k,v}^{I(s_t = k)I(v_t = v)} \right] \left[ \prod_{k=1}^K \pi_k^{I(s_1 = k)} \right] \left[ \prod_{t=2}^T \prod_{i=1}^K \prod_{j=1}^K A_{i,j}^{I(s_{t-1} = i, s_t = j)} \right] \end{align*} $ # Parameter Estimation ## Estimation of Emission Probability Matrix ## Estimation of Transition Probability Matrix # Expectation-Maximization General method of finding the `maximum-likelihood estimate` of the parameters of an underlying distribution from a given data set when the data is incomplete or has missing values. There are two main applications of the EM algorithm: 1. The first occurs when the data indeed has missing values, due to problems with or limitations of the observation process. 2. The second occurs when optimizing the likelihood function is analytically intractable but when the likelihood function can be simplified by assuming the existence of and values for additional but missing (or hidden) parameters. Assume $x$ is a incomplete data, and that the complete data set $Z=\{x, y\}$ Suppose, $ \begin{align*} P(x, y | \theta) = P(x | \theta) P(y |x, \theta) \end{align*} $ Assume likelihood $ \begin{align*} L(\theta | x, y) \end{align*} $ ## Expectation Construct the conditional expectation $ \begin{align*} Q(\theta, \theta^{i-1}) = E[ \log P(x, y | \theta) | x, \theta^{i - 1} ] = \int_y \log P(x, y | \theta) f(y |x, \theta^{i-1}) dy \end{align*} $ Where $\theta^{i-1}$ are the current parameter estimates at the step $i-1$ θ^i-1^ and x are constants, y is a random variable θ is a normal variable we wish to adjust. (my insight) Weighted average of joint probability, where weight is posterior distribution of y given x and theta. *Issue* is that we don't know the posterior! @paisley2016bayesianmodel ## Maximization $ \begin{align*} \theta^{i} = \text{argmax}_\theta Q(\theta, \theta^{i-1}) \end{align*} $ Goal $ \begin{align*} \text{argmax}_{z_{1:n}} P(x_{1:n} | z_{1:n}) \end{align*} $ Idea $ \begin{align*} P(x_{1:n} | z_{1:n}) \propto P(x_{1:n}, z_{1:n}) \end{align*} $ # Baum-Welch Algorithm @bilmes1998gentle - $Q_t$ is a discrete random variable with $N$ possible values $\{1, ..., N\}$ - $A = \{a_{i,j}\} = P(Q_t = j| Q_{t-1} = i)$ is a transition matrix - $\pi_i = P(Q_1 = i)$ is the initial state distribution - $q = (q_1, ..., q_T)$ where $q_t \in \{1, ..., N\}$ is the state at time $t$ is a particular sequence of states ## Make a Initial Guess $ \begin{align*} P(z_k | z_{k-1}) \\ P(x_k | z_{k}) \\ \end{align*} $ # Forward-Backward Algorithm Goal: Compute $ P(z_k | x_{1:n}) $ Forward $ P(z_k, x_{1:k}) $ Backward $ P(x_{k+1:n} | z_k) $ We can do this because ... (Central Idea) $ \begin{align*} P(z_k | x_{1:n}) \propto P(z_k, x) = \underbrace{P(z_k, x_{1:k})}_{\text{Forward algorithm}} \ \underbrace{P(x_{k+1:n} | z_k)}_{\text{Backward algorithm}} \end{align*} $ ## Motivation - Compare it with a Naive Method The [complexity](20200707123306-complexity.org) of forward algorithm is $o(nm^2)$ whereas complesity of the naive algorithm is $o(m^n)$ ### Proof sequences of length $n$, with $m$ states $ \begin{align*} p(z_k | x) = { p(z_k, x) \over p(x) } \end{align*} $ notice $ \begin{align*} p(z_k, x) = \sum_{z \ne z_k} p(x, z) \end{align*} $ and $ \begin{align*} p(x) = \sum_{z=n}^m \cdots \sum_{z=1}^m p(x, z) \\ \end{align*} $ therefore, the complexity (in [big o notation](20200707121539-big_o_notation.org) ) is $ \begin{align*} o(m^n) \end{align*} $ # Forward Algorithm %% ```dot digraph test { rankdir=LR; "z_{k-2}" -> "z_{k-1}"-> z_k -> "z_{k+1}" -> "z_{k+2}" "z_{k-2}"-> "x_{k-2}" "z_{k-1}"-> "x_{k-1}" z_k -> x_k "z_{k+1}"-> "x_{k+1}" "z_{k+2}"-> "x_{k+2}" "x_k" [style="filled" fillcolor=grey] "x_{k+1}" [style="filled" fillcolor=grey] "x_{k+2}" [style="filled" fillcolor=grey] subgraph cluster1 { style="dashed" "x_{k-2}" [style="filled" fillcolor=grey] "x_{k-1}" [style="filled" fillcolor=grey] } subgraph cluster2 { style="dashed" "z_k" } } ``` %% ![[forward.png]]] $ \begin{align*} \alpha_k(z_k) = P(z_k, x_{1:k}) &= \sum_{z_{k-1} = 1}^m P(z_k, z_{k-1}, x_{1:k}) \\ &= \sum_{z_{k-1} = 1}^m P(x_k | z_k, z_{k-1}, x_{1:k-1}) P(z_k | z_{k-1}, x_{1:k-1}) P(z_{k-1}, x_{1:k-1}) \\ &= \sum_{z_{k-1} = 1}^m P(x_k | z_k) P(z_k | z_{k-1}) P(z_{k-1}, x_{1:k-1}) \\ &= \sum_{z_{k-1} = 1}^m P(x_k | z_k) P(z_k | z_{k-1}) \alpha_{k-1}(z_{k-1})\\ &= \sum_{z_{k-1} = 1}^m \underbrace{P(x_k | z_k)}_{\text{Emission prob.}} \underbrace{P(z_k | z_{k-1})}_{\text{Transition prob.}} \alpha_{k-1}(z_{k-1})\\ \end{align*} $ And $ \begin{align*} \alpha_1(z_1) = P(z_1, x_1) &= P(z_1) P(x_1 | z_1) \end{align*} $ # Backward Algorithm $ P(x_{(k+1):n} | z_k) $ %% ```dot digraph test { rankdir=LR; "z_{k-2}" -> "z_{k-1}"-> z_k -> "z_{k+1}" -> "z_{k+2}" // emission "z_{k-2}"-> "x_{k-2}" "z_{k-1}"-> "x_{k-1}" z_k -> x_k "z_{k+1}"-> "x_{k+1}" "z_{k+2}"-> "x_{k+2}" "x_{k-2}" [style="filled" fillcolor=grey] "x_{k-1}" [style="filled" fillcolor=grey] "x_k" [style="filled" fillcolor=grey] "x_{k+1}" [style="filled" fillcolor=grey] "x_{k+2}" [style="filled" fillcolor=grey] subgraph cluster1 { style="dashed" "x_{k+1}" [style="filled" fillcolor=grey] "x_{k+2}" [style="filled" fillcolor=grey] } subgraph cluster2 { style="dashed" z_k } } ``` %% ![[backward.png]] $ \begin{align} \beta_k(z_k) = P(x_{(k+1):n} | z_k) &= \sum_{z_{k+1}=1}^m P(x_{(k+1):n}, z_{k+1} | z_k ) \\ &= \sum_{z_{k+1}=1}^m P(x_{(k+1):n}, z_{k+1} | z_k ) \\ &= \sum_{z_{k+1}=1}^m P(z_{k+1} | z_k ) P(x_{k+1} | z_{k+1}, z_k ) P(x_{(k+2):n} | z_{k+1}, z_k ) \\ &= \sum_{z_{k+1}=1}^m P(z_{k+1} | z_k ) P(x_{k+1} | z_{k+1}) P(x_{(k+2):n} | z_{k+1}) & \text{(Markov assumption)} \\ &= \sum_{z_{k+1}=1}^m \underbrace{P(z_{k+1} | z_k )}_{\text{Transition prob.}} \underbrace{P(x_{k+1} | z_{k+1})}_{\text{Emission prob.}} \beta_{k+1}(z_{k+1}) \ , \text{for } k=1, \cdots, n-1 \end{align} $ And $ \begin{align*} \beta_n(z_n) = 1 \end{align*} $ # Viterbi Algorithm [Viterbi Algorithm](20200707084341-viterbi_algorithm.org)