labman2.tex

一本关于dsp的原著教材

\documentclass[twoside,a4paper,titlepage]{article}
\usepackage{array,amsmath,amssymb,rotating,epsfig,fancyheadings}


\newcommand{\mat}[1]{{\tt >> #1} \\}
\newcommand{\com}[1]{{\tt #1}}
\newcommand{\expl}[1]{%
\begin{turn}{180}%
\parbox{\textwidth}{\em #1}%
\end{turn}%
}
\newcommand{\tit}[1]{{\noindent \bf #1 \\}}
\newcommand{\tab}{\hspace{1em}}

\newcommand{\PBS}[1]{\let\temp=\\#1\let\\=\temp}
\newcommand{\RR}{\PBS\raggedright\hspace{0pt}}
\newcommand{\RL}{\PBS\raggedleft\hspace{0pt}}
\newcommand{\CC}{\PBS\centering\hspace{0pt}}

\setlength{\hoffset}{-1in}
\setlength{\voffset}{-1in}

\setlength{\topskip}{0cm}
\setlength{\headheight}{0cm}
\setlength{\headsep}{0cm}

\setlength{\textwidth}{16cm}
\setlength{\evensidemargin}{2.5cm}
\setlength{\oddsidemargin}{2.5cm}

\setlength{\textheight}{24.7cm}
\setlength{\topmargin}{1.5cm}
\setlength{\headheight}{0.5cm}
\setlength{\headsep}{0.5cm}

\pagestyle{fancyplain}

\begin{document}

\begin{titlepage}
\setcounter{page}{-1}

\centerline{Ecole Polytechnique F\'ed\'erale de Lausanne}

\vspace{5cm}

\begin{center}
\huge
Lab session 2\,: \\
Introduction to Hidden Markov Models
\end{center}

\vfill

\centerline{\includegraphics[width=7cm]{hmmcover.eps.gz}}

\vfill

\noindent
\begin{tabular}{lll}
Course\,: & Speech processing and speech recognition & \\
& & \\
Teacher\,: & Prof. Herv\'e Bourlard \hspace{1cm} & {\tt [e-mail]} \\
& & \\
Assistants\,: & Sacha Krstulovi\'c & {\tt [e-mail]}\\
 & Mathew Magimai-Doss & {\tt [e-mail]} 
\end{tabular}

\end{titlepage}

\thispagestyle{empty}
%%%%%%%%%
%%%%%%%%%
\section*{Guidelines}
%%%%%%%%%
%%%%%%%%%
The following lab manual is structured as follows\,:
\begin{itemize}
\item each section corresponds to a theme
\item each subsection corresponds to a separate experiment.
\end{itemize}
The subsections begin with useful formulas and definitions that will be put
in practice during the experiments. These are followed by the description
of the experiment and by an example of how to realize it in {\sc Matlab}.

If you follow the examples literally, you will be able to progress into the
lab session without worrying about the experimental implementation
details. If you have ideas for better {\sc Matlab} implementations, you are
welcome to put them in practice provided you don't loose too much time\,:
remember that a lab session is no more than 3 hours long.

The subsections also contain questions that you should think about.
Corresponding answers are given right after, in case of problem. You can
read them right after the question, {\em but}\,: the purpose of this lab is
to make you

\medskip
\centerline{\LARGE \bf Think !}
\medskip

If you get lost with some of the questions or some of the explanations, DO
ASK the assistants or the teacher for help\,: they are here to make the course
understood. There is no such thing as a stupid question, and the only
obstacle to knowledge is laziness.

\bigskip
Have a nice lab;

\hfill Teacher \& Assistants \hspace{2cm}


\vfill
%%%%%%%%%
%%%%%%%%%
\section*{Before you begin...}
%%%%%%%%%
%%%%%%%%%
If this lab manual has been handed to you as a hardcopy\,:
\begin{enumerate}
\item get the lab package from \\
	\hspace{2cm}{\tt ftp.idiap.ch/pub/sacha/labs/Session2.tgz}
\item un-archive the package\,: \\
	{\tt \% gunzip Session2.tgz \\
	\% tar xvf Session2.tar}
\item change directory\,: \\
	{\tt \% cd session2}
\item start {\sc Matlab}\,: \\
	{\tt \% matlab }
\end{enumerate}
Then go on with the experiments...


\vspace{1cm}

{\scriptsize
\noindent
This document was created by\,: Sacha Krstulovi\'c ({\tt [e-mail]}).

\noindent
This document is currently maintained by\,: Sacha Krstulovi\'c ({\tt [e-mail]}). Last modification on \today.

\noindent
This document is part of the package {\tt Session2.tgz} available by ftp as\,: {\tt ftp.idiap.ch/pub/sacha/labs/Session2.tgz} .
}

\clearpage

\tableofcontents

\bigskip
%\clearpage
%%%%%%%%%
%%%%%%%%%
\section{Preamble}
%%%%%%%%%
%%%%%%%%%
\subsubsection*{Useful formulas and definitions\,:}
\begin{itemize}
%
\item[-] a {\em Markov chain} or {\em process} is a sequence of events,
usually called {\em states}, the probability of each of which is dependent
only on the event immediately preceding it.
%
\item[-] a {\em Hidden Markov Model} (HMM) represents stochastic sequences
as Markov chains where the states are not directly observed, but are
associated with a probability density function (pdf). The generation of a
random sequence is then the result of a random walk in the chain (i.e. the
browsing of a random sequence of states $Q=\{q_1,\cdots q_K\}$) and of a
draw (called an {\em emission}) at each visit of a state.

The sequence of states, which is the quantity of interest in speech
recognition and in most of the other pattern recognition problems, can be
observed only {\em through} the stochastic processes defined into each
state (i.e. you must know the parameters of the pdfs of each state before
being able to associate a sequence of states $Q=\{q_1,\cdots q_K\}$ to a
sequence of observations $X=\{x_1,\cdots x_K\}$). The true sequence of
states is therefore {\em hidden} by a first layer of stochastic processes.

HMMs are {\em dynamic models}, in the sense that they are specifically
designed to account for some macroscopic structure of the random
sequences. In the previous lab, concerned with {\em Gaussian Statistics and
Statistical Pattern Recognition}, random sequences of observations were
considered as the result of a series of {\em independent} draws in one or
several Gaussian densities. To this simple statistical modeling scheme,
HMMs add the specification of some {\em statistical dependence} between the
(Gaussian) densities from which the observations are drawn.

\item[-] {\em HMM terminology} \,:
\begin{itemize}
\item the {\em emission probabilities} are the pdfs that characterize each
state $q_i$, i.e. $p(x|q_i)$. To simplify the notations, they will be
denoted $b_i(x)$. For practical reasons, they are usually Gaussian or
combinations of Gaussians, but the states could be parameterized in terms
of any other kind of pdf (including discrete probabilities and artificial
neural networks).
\item the {\em transition probabilities} are the probability to go from a
state $i$ to a state $j$, i.e. $P(q_j|q_i)$. They are stored in matrices
where each term $a_{ij}$ denotes a probability $P(q_j|q_i)$.
\item {\em non-emitting initial and final states}\,: if a random sequence
$X=\{x_1,\cdots x_K\}$ has a finite length $K$, the fact that the sequence
begins or ends has to be modeled as two additional discrete events. In
HMMs, this corresponds to the addition of two {\em non-emitting states},
the initial state and the final state. Since their role is just to model
the ``start'' or ``end'' events, they are not associated with some emission
probabilities.

The transitions starting from the initial state correspond to the modeling
of an {\em initial state distribution} $P(I|q_j)$, which indicates the
probability to start the state sequence with the emitting state $q_j$.

The final state usually has only one non-null transition that loops onto
itself with a probability of $1$ (it is an {\em absorbent state}), so that
the state sequence gets ``trapped'' into it when it is reached.

\item {\em ergodic versus left-right HMMs}\,: a HMM allowing for
transitions from any emitting state to any other emitting state is called
an {\em ergodic HMM}. Alternately, an HMM where the transitions only go
from one state to itself or to a unique follower is called a {\em
left-right HMM}.
\end{itemize}
\end{itemize}

\subsubsection*{Values used throughout the experiments\,:}

The following 2-dimensional Gaussian densities will be used to model
simulated vowel observations, where the considered features are the two
first formants\,:

\begin{tabular}{>{\CC}m{10em}>{\CC}m{12em}>{\CC}m{12em}}
Density ${\cal N}_{/a/}$\,: &
\[ \mu_{/a/} = \left[\begin{array}{r} 730 \\ 1090 \end{array}\right] \] &
\[ \Sigma_{/a/} = \left[\begin{array}{rr} 1625 & 5300 \\ 5300 & 53300 \end{array}\right] \] \\
Density ${\cal N}_{/e/}$\,: &
\[ \mu_{/e/} = \left[\begin{array}{r} 530 \\ 1840 \end{array}\right] \] &
\[ \Sigma_{/e/} = \left[\begin{array}{rr} 15025 & 7750 \\ 7750 & 36725 \end{array}\right] \] \\
Density ${\cal N}_{/i/}$\,: &
\[ \mu_{/i/} = \left[\begin{array}{r} 270 \\ 2290 \end{array}\right] \] &
\[ \Sigma_{/i/} = \left[\begin{array}{rr} 2525 & 1200 \\ 1200 & 36125 \end{array}\right] \] \\
Density ${\cal N}_{/o/}$\,: &
\[ \mu_{/o/} = \left[\begin{array}{r} 570 \\ 840 \end{array}\right] \] &
\[ \Sigma_{/o/} = \left[\begin{array}{rr} 2000 & 3600 \\ 3600 & 20000 \end{array}\right] \] \\
Density ${\cal N}_{/y/}$\,: &
\[ \mu_{/y/} = \left[\begin{array}{r} 440 \\ 1020 \end{array}\right] \] &
\[ \Sigma_{/y/} = \left[\begin{array}{rr} 8000 & 8400 \\ 8400 & 18500 \end{array}\right] \] \\
\end{tabular}

\noindent (Those densities have been used in the previous lab session.)
They will be combined into Markov Models that will be used to model some
observation sequences. The resulting HMMs are described in
table~\ref{tab:models}.

\begin{table}[p]
\vspace{-3mm}
\setlength{\arraycolsep}{2pt}
\renewcommand{\arraystretch}{1.5}
\begin{tabular}{>{\CC}m{0.25\textwidth}>{\CC\scriptsize}m{0.26\textwidth}>{\CC}m{0.45\textwidth}}
	\bf Emission probabilities &
	{\normalsize \bf Transition matrix} &
	\bf Sketch of the model \vspace{2mm} \\
	\begin{tabular}{>{\hspace{-2em}}l}
{\bf HMM1}\,: \\
$\bullet$ state 1: initial state \\
$\bullet$ state 2: Gaussian ${\cal N}_{/a/}$ \\
$\bullet$ state 3: Gaussian ${\cal N}_{/i/}$ \\
$\bullet$ state 4: Gaussian ${\cal N}_{/y/}$ \\
$\bullet$ state 5: final state
	\end{tabular}
	&
	\[ \left[\begin{array}{lllll} 
			0.0 & \bf 1.0 & 0.0 & 0.0 & 0.0 \\
			0.0 & \bf 0.4 & \bf 0.3 & \bf 0.3 & 0.0 \\
			0.0 & \bf 0.3 & \bf 0.4 & \bf 0.3 & 0.0 \\
			0.0 & \bf 0.3 & \bf 0.3 & \bf 0.3 & \bf 0.1 \\
			0.0 & 0.0 & 0.0 & 0.0 & \bf 1.0
	               \end{array}\right]
	\]
	&
	\input{hmm1.pstex_t} \\
	%
	\begin{tabular}{>{\hspace{-2em}}l}
{\bf HMM2}\,: \\
$\bullet$ state 1: initial state \\
$\bullet$ state 2: Gaussian ${\cal N}_{/a/}$ \\
$\bullet$ state 3: Gaussian ${\cal N}_{/i/}$ \\
$\bullet$ state 4: Gaussian ${\cal N}_{/y/}$ \\
$\bullet$ state 5: final state
	\end{tabular}
	&
	\[ \left[\begin{array}{lllll} 
			0.0 & \bf 1.0   & 0.0   & 0.0   & 0.0  \\
			0.0 & \bf 0.95  & \bf 0.025 & \bf 0.025 & 0.0  \\
			0.0 & \bf 0.025 & \bf 0.95  & \bf 0.025 & 0.0  \\
			0.0 & \bf 0.02  & \bf 0.02  & \bf 0.95  & \bf 0.01 \\
			0.0 & 0.0   & 0.0   & 0.0   & \bf 1.0
	               \end{array}\right]
	\]
	&
	\input{hmm2.pstex_t} \\
	%
	\begin{tabular}{>{\hspace{-2em}}l}
{\bf HMM3}\,: \\
$\bullet$ state 1: initial state \\
$\bullet$ state 2: Gaussian ${\cal N}_{/a/}$ \\