Markov Assumption (first order): $P(w_t|w_{t-1},w_{t-2},\dots ,w_1)\approx P(w_t|w_{t-1})$

The joint probability of a sequence of observations / events is then: $P(w_1,w_2,\dots ,w_t)={\prod }_{t=1}^{n}P(w_t|w_{t-1})$

Markov Chain

A Markov Chain is a finite set of discrete states, each of which has a probability distribution of how to transition between them.

Link to original

Hidden Markov Model

In a Hidden Markov Model we have a Markov Chain over hidden states:

• we only have access to observations at each time step
• no 1:1 mapping between observations and hidden states

A number of hidden states can be associated with a particular observations, but the association of states and observations is governed by statistical behaviour. We have to infer the sequence of hidden states that correspond to a sequence of observations.

We add special start and end states which are not associated with ‘real’ observations.

Formal definition of Hidden Markov Models

In a Hidden Markov Model, we have:

• $S_e=\{s_1,\dots ,s_N\}$: set of $N$ emitting hidden states
  • $s_0$: special start state
  • $s_t$: special end state
• $K=\{k_1,\dots ,k_M\}$: output alphabet of $M$ observations (‘vocabulary’)
  • $k_0$: special start symbol
  • $k_t$: special end symbol
• $O=O_1\dots O_T$: sequence of $T$ observations, each drawn from $K$
• $X=X_1\dots X_T$: sequence of $T$ states, each drawn from $S_e$

Markov Property

The Markov Property / Markov Assumption (Limited Horizon) is that we do not factor the history of previous states / transitions depend only on current state: $P(X_t|X_1,\dots ,X_{t-1})\approx P(X_t|X_{t-1})$

Link to original

The Output Independence of a HMM is that the probability of an output observation only depends on the current state: $P(O_t|X_1,\dots ,X_t,\dots ,X_T,O_1,\dots ,O_t,\dots ,O_T)\approx P(O_t|X_t)$

$A$ is a state transition probability matrix of size $(N+2)\times (N+2)$.

$$A=\left[\begin{array}{ccccccccc}-& a_{01}& a_{02}& a_{03}& .& .& .& a_{0N}& -\\ -& a_{11}& a_{12}& a_{13}& .& .& .& a_{1N}& a_{1f}\\ -& a_{21}& a_{22}& a_{23}& .& .& .& a_{2N}& a_{2f}\\ -& .& .& .& & & & .& .\\ -& .& .& .& & & & .& .\\ -& .& .& .& & & & .& .\\ -& a_{N1}& a_{N2}& a_{N3}& .& .& .& a_{NN}& a_{Nf}\\ -& -& -& -& -& -& -& -& -\end{array}\right]$$

$a_{ij}$ is the probability of moving from state $s_i$ to state $s_j$:

\forall_i \sum^{N+1}_{j=0} a_{ij} &= 1\end{aligned}$$ The start state $s_0$ and end state $s_f$ have properties that: - They are not associated with 'real' observations - $a_{0i}$ describe transition probabilities out of start state into state $s_i$ - $a_{if}$ describe transition probabilities into the end state - Transitions into start state $(a_{i0})$ and out of end state $(a_{fi})$ are undefined. $B$ is an emission probability matrix of size $(M + 2) \times (N + 2)$.

B = \begin{bmatrix} b_0(k_0) & - & - & - & - & - & - & - & - \

• & b_1(k_1) & b_2(k_1) & b_3(k_1) & . & . & . & b_N(k_1) & - \
• & b_1(k_1) & b_2(k_1) & b_3(k_2) & . & . & . & b_N(k_2) & - \
• & . & . & . & & & & . & - \
• & . & . & . & & & & . & - \
• & . & . & . & & & & . & - \
• & b_1(k_M) & b_2(k_M) & b_3(k_M) & . & . & . & b_N(k_M) & - \
• & - & - & - & - & - & - & - & b_f(k_t) \ \end{bmatrix}

$b_i(k_j)$ is the probability of emitting vocabulary item $k_j$ from state $s_i$:

b_i(k_j) = P(O_t = k_j | X_t = s_i)

We define our HMM by parameters $\mu = (A,B)$. > [!example] Example: Dice HMM > > Imagine a fraudulous croupier in a casino where customers bet on dice outcomes. > > [!failure] Slides 19-22 > [!abstract] Fundamental tasks with HMMs > > > [!failure] Slide 23 ### Estimating parameters of an HMM > [!failure] Slides 25-26 > #### Viterbi Algorithm > [!failure] Slides -58 > > [!abstract] Why is it necessary to keep $N$ states at each time step? > > > [!failure] Slide 59 > [!abstract] >