\documentclass[12pt, titlepage]{report} \usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{txfonts}
\usepackage[english]{babel}
\usepackage{graphicx}
\usepackage[a4paper]{geometry}
\usepackage{epsfig}
\usepackage{graphicx}
\usepackage{subfig}
\usepackage{verbatim}
\usepackage{array}
\usepackage{subfig}
\usepackage{float}
\usepackage{diagbox}
\usepackage{makecell}

\makeatletter
\newcommand{\thickhline}{%
    \noalign {\ifnum 0=`}\fi \hrule height 1.5pt
    \futurelet \reserved@a \@xhline
}
\newcolumntype{"}{@{\hskip\tabcolsep\vrule width 1.5pt\hskip\tabcolsep}}
\makeatother

\begin{document}

\section*{The Baum-Welch Algorithm}

Given a set of sequences $X = x^1, \dots, x^n$ generated by a hidden Markov model with fixed structure, our goal is to estimate the emission probabilities for each state as well as the transition probabilities between the states.   To solve this problem, we employ an expectation-maximization algorithm known as the \textbf{Baum-Welch algorithm}. 
\\\\
Like all expectation-maximization strategies, we first define the observed data, hidden data, and parameters for the model:

\begin{itemize}
\item Observed data: $X = \{x^1, \dots, x^n\}$ the set of observed sequences
\item Hidden data: $Z = \{ \pi^1, \dots \pi^n \}$ the paths through the HMM that generated $X$
\item Parameters: $\theta$ = the set of emission and transition probabilities
\end{itemize}

\noindent
The idea is that the algorithm alternates between calculating the expected number of times each transition and emission is used to generate $X$.  These expected counts are used to re-estimate the emission and transition probabilities (i.e. the parameters).  These parameters are then used again for computing the expected counts of the emissions and transitions. The algorithm then converges on a local maxima of the likelihood surface for the observed sequences $X$.

\subsection*{Description}

Since the Baum-Welch algorithm is an implementation of the EM algorithm, we break it down into the E (expectation) and M (maximization) steps:

\subsubsection*{E-Step}

For each sequence, we run the forward and backward algorithms on $x^j$.  This gives all forward values $f^j_k(i)$ and backward values $b^j_k(i)$.
\\\\
We then use these values to calculate the expected number of times each transition $a_{kl}$ was used for each sequence.  To do this, we first note that the probability that $a_{kl}$ was used at position $i$ in sequence $x$ is calculated as:

\begin{align*}
P(\pi_i = k, \pi_{i+1} = l, x \mid \theta) & = P(\pi_i = k, \pi_{i+1} = l, \mid x, \theta) \ P(x) \\\\
&= f_k(i) \ a_{kl} \ e_l(x_{i+1}) \ b_l(i+1)
\end{align*} 

\noindent
Therefore,

\begin{align*}
P(\pi_i = k, \pi_{i+1} = l, x \mid \theta) &= \frac{f_k(i) \ a_{kl} \ e_l(x_{i+1} \ b_l(i+1)}{P(x)} \\\\
& = \frac{f_k(i) \ a_{kl} \ e_l(x_{i+1}) \ b_l(i+1)}{f_N(L)}
\end{align*}  


\end{document}