%%%
%%% bibTeX doesn't understand "\includeonly".
%%%
%%%\includeonly{introduction, algorithms, appendix}
\includeonly{introduction, algorithms, variants, continuous, toys,
real, appendix}
%%%
%%% Note: The following settings will cause many overfull hbox false alarms:
\documentclass[prelim,showlabels]{book}
% \documentclass[dvips,prelim,showlabels,mt2pro]{book}
% \documentclass[dvips,prelim,showlabels,siammathtime]{book}
%\documentclass[dvips,final,mt2pro]{book}
\usepackage[letter,center]{crop}
\crop
\usepackage{graphicx,color}
\usepackage{amsmath, amsfonts}% ToDo: compatible w/siammathtime.sty?
\usepackage{amsthm}% Note: Conflicts with newsiambook
\usepackage{xspace}
\usepackage{bm} % Bold Math
\usepackage{rotating} % for sidewaysfigure
\usepackage{afterpage}
\usepackage{pstricks}
\usepackage{booktabs} % for nicer looking tables
\usepackage{dcolumn} % decimal point aligned columns
\usepackage{url}
%%% Defines the alltt environment which is like the verbatim
%%% environment except that \ and braces have their usual meanings.
%%% Thus, other commands and environments can appear within an alltt
%%% environment.
%%%
%%% Note: This is used in appendix.tex to typeset a code listing.
%%%
\usepackage{alltt}
%\usepackage{makeidx}
\usepackage{index}
\usepackage[norefeq,refpage,nocfg,intoc,noprefix]{nomencl}
%%% This is used to make the description list in the nompreamble
%%% format the same as the one in the nomenclature itself. I (Karl)
%%% took it straight out of the nomencl.sty.
%%%
\newenvironment{symbdescription}{%
\list{}{%
\labelwidth\nomlabelwidth
\leftmargin\labelwidth
\advance\leftmargin\labelsep
\itemsep\nomitemsep
\let\makelabel\nomlabel}}%
{\endlist}
\newtheorem{theorem}{Theorem}
\renewcommand{\th}{^{\text th}}
\newcommand{\field}[1]{\mathbb{#1}}
\newcommand{\INTEGER}{\field{Z}}
\newcommand{\REAL}{\field{R}}
\newcommand{\COMPLEX}{\field{C}}
\newcommand{\EV}{\field{E}}
\newcommand{\y}{\mathbf{y}}
\newcommand{\x}{\mathbf{x}}
\newcommand{\s}{{\bf s}}
\newcommand{\bS}{{\bf S}}
\newcommand{\Y}{{\bf Y}}
\newcommand{\Tsamp}{\tau_s }
%\newcommand{\ColorComment}[3]{{\color{#1}\textbf{#2:} #3}}
\newcommand{\ColorComment}[3]{}
\newcommand{\ReviewerNote}[1]{\ColorComment{Red}{Reviewer}{#1}}
\newcommand{\ToDo}[1]{\ColorComment{NavyBlue}{ToDo}{#1}}
\newcommand{\KarlHeg}[1]{\ColorComment{OrangeRed}{KarlHeg}{#1}}
\newcommand{\argmin}{\operatorname*{argmin}}
\newcommand{\argmax}{\operatorname*{argmax}}
\newcommand{\Normal}{{\mathcal{N}}}
\newcommand{\NormalE}[3]{{\mathcal{N}}\left.\left(#1,#2\right)\right|_{#3}}
\newcommand{\transpose}{^\top}
\newcommand{\ceil}[1]{\lceil#1\rceil}
\newcommand{\bceil}[1]{\left\lceil#1\right\rceil}
\newcommand{\floor}[1]{\lfloor#1\rfloor}
\newcommand{\bfloor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\states}{{\cal S}}
\newcommand{\outputs}{{\cal Y}}
\newcommand{\State}{S}
\newcommand{\Output}{Y}
\newcommand{\parameters}{\theta}
\newcommand{\parametersPrime}{\theta'}% for EM1.gpt
\newcommand{\ti}[2]{{#1}{(#2)}} % Time Index
%%% \newcommand{\ts}[3]{{#1}{(t\=#2,\ldots,#3)}} % Time Sequence
\newcommand{\ts}[3]{#1_{#2}^{#3}} % Time Sequence
%%% \newcommand{\ts}[3]{\left\{ #1(l) \right\}_{l=#2}^{#3}} % Time Sequence
\newcommand{\id}{{\bf I}}
\newcommand{\ie}{i.e.\xspace}
\newcommand{\eg}{e.g.\xspace}
\newcommand{\etal}{et al.\xspace}
\newcommand{\iid}{i.~i.~d.\xspace}
\newcommand{\apost}{\emph{a posteriori}\xspace}
\newcommand{\apri}{\emph{a priori}\xspace}
\newcommand{\plotsize}{\small}
\newcommand{\mlabel}[1]{\label{#1}}
\newcommand{\biburl}[1]{\\\url{#1}} % URL in a "note" gets a line by itself
%%% The following are "rubber directives". See
%%% http://manpages.ubuntu.com/manpages/gutsy/man1/rubber.html
%%% rubber: paper letter
%%% rubber: module graphicx
%%% rubber: module bibtex
%%% rubber: module index
%%% rubber: onchange main.nlo "makeindex main.nlo -s nomencl.ist -o main.nls"
%%% rubber: watch main.nls
%%% rubber: clean main.loa
%%% rubber: clean main.nlo
%%% rubber: clean main.nls
%%% rubber: clean main.out
\makeindex
\author{Andrew M. Fraser}
\title{Hidden Markov Models and Dynamical Systems}
\begin{document}
\frontmatter
\maketitle
% \hspace{1em} \vspace{.4\textheight}\\
% \begin{center}
% For Marguerite
% \end{center}
\chapter*{Preface}
\addcontentsline{toc}{chapter}{Preface}
\label{chap:preface}
This book arose from a pair of symposia on hidden Markov models that
Kevin Vixie organized at the 2001 SIAM Dynamical Systems meeting. At
the end of the first symposium someone asked the speakers for a simple
reference that explains the basic ideas and algorithms for applying
HMMs. We were stumped. A group of the participants suggested writing
this book to answer the question. I have aimed the book at readers
who have backgrounds and interests typical of those who attend that
conference. In my view, HMMs are discrete state - discrete time
stochastic dynamical systems, and they are often used to approximate
dynamical systems with continuous state spaces operating in continuous
time. Thus, by using familiar analogies, it is easy to explain HMMs
to readers who have studied dynamical systems.
The basic techniques were well developed in the 1970's for work on
speech and language processing. Many in speech research learned about
the techniques at a symposium held at the Institute for Defense
Analysis \index{Institute for Defense Analysis} in Princeton. J.\ D.\
Ferguson edited the proceedings\cite{ida80} and copies were given to
the attendees\footnote{The volume is available at a few libraries.}.
The volume was called \emph{the blue book} by workers in the field. I
was not part of that community, but I have a copy of the blue book.
It explains the basic algorithms and illustrates them with simple
concrete examples. I hope \emph{this} book is as simple, useful, and
clear.
Although there are other books and papers that are about HMMs
exclusively or in part, I hope that readers find the following
features of this present volume useful:
\begin{description}
\item[It is introductory.] Sophomore or Junior study in engineering,
mathematics, or science that includes work in probability, linear
algebra, and differential equations provides the prerequisites for
most of the book. The exceptions are ideas from dynamical systems
and information theory. In particular, I use the Gibbs inequality
(Eqn.~\eqref{eq:GibbsIE}) in developing the EM algorithm in Chapter
\ref{chap:algorithms}. Although Chapter \ref{chap:toys} \emph{Toy
Problems and Performance Bounds} deals with Lyapunov exponents and
entropies, it is not a prerequisite for any other chapter.
\item[Algorithms are explained and justified.] I present enough of the
theory behind the basic algorithms in Chapter \ref{chap:algorithms}
so that a reader can use it as a guide to developing his own
variants.
\item[I provide code implementing the algorithms and data for the
examples.] Although algorithms are given in pseudo code in the text,
a working implementation of each of the algorithms that I describe
is available on the web\cite{FraserPhysicsHMM}. I have chosen to
write the programs in the python language\cite{python} because it is
easy to read and the interpreter is free software. I have written
the programs to follow the descriptions and notation in the text. I
provide data and scripts (makefiles, shell scripts, etc.) that make
all of the figures in the text. On a gnu system, issuing ``make
book.pdf'' from a command line compiles the software, runs the
numerical experiments, makes the figures, and formats the entire
book.
\item[It uses analogies to dynamical systems.] For example, I
demonstrate the HMM training algorithm by applying it to data
derived from the Lorenz system. The result, as
Fig.~\ref{fig:Statesintro} illustrates, is that the algorithm
estimates a discrete state generating mechanism that is an
approximation to the state space of the original Lorenz system.
\item[I illustrate with a practical example.] In Chapter \ref{chap:apnea} I
present an application to experimental measurements of
electrocardiograms (ECGs).
\end{description}
\ToDo{ Point to review papers and material (I've collected some of the
kind of stuff I have in mind at
\url{http://fraserphysics.com/~andy/HMMs/} ). Perhaps organize this
stuff under the following topics:
\begin{itemize}
\item MCMC annealing and optimization
\item Other applications
\item Other papers books and web sites
\item Bayes nets
\end{itemize}
}
\section*{Acknowledgments}
\addcontentsline{toc}{section}{Acknowledgments}%
\label{sec:ack}
In writing this book, I have used much that I learned from colleagues
in Portland. In particular, Todd Leen kept me informed about
developments in the machine learning community. I've relied on the
review of the ergodic theory of dynamical systems in Kevin Vixie's
dissertation\cite{vixie02} for Chapter~\ref{chap:toys} of this book.
Shari Matzner and Gerardo Lafferriere helped me understand the
convergence properties of the EM algorithm. Also the following
colleagues have given me constructive comments on drafts of the book:
%
Katherine Backus, %
Patrick Campbell, %
Ralf Juengling, %
Shari Matzner, %
Kary Myers, %
Reid Porter, %
Cosma Shalizi, %
and %
Rudolph Van der Meer. %
I thank the following people and organizations for providing the data
that I used for examples:
\begin{description}
\item[Carl Otto Weiss] For providing Tang's\cite{Tang92} laser data
\item[PhysioNet] For providing Penzel's\cite{Penzel02} ECG data and
George Moody's \emph{wfdb} software \cite{PhysioToolkit}
\item[Project Gutenberg] For digitizing and distributing \emph{A
Book of Prefaces},\\ by H.~L.~Mencken
%%% I hate to put a line break in there like that, but it was hanging
%%% out into the margin without it. -- karlheg
\end{description}
I was fortunate to meet Karl Hegbloom in Portland. Karl contributes
to several free software projects and he helped me with the figures
and software. Ralf Juengling also helped with the software. In
addition to personal help with software, I relied on free software
written by too many contributors to mention. Almost all of the tools
I used are available in the debian\cite{debian} and
ubuntu\cite{ubuntu} distributions.
I acknowledge Portland State University for support of a sabbatical
leave during which I started the book and for a computer on which I
did much of the development. I thank Principal Investigator James
Kamm for arranging to have the Los Alamos National Laboratory LDRD
office support work on Chapter~\ref{chap:apnea} through project \#
20030037DR.
\tableofcontents
\mainmatter
\include{introduction}
\include{algorithms}
\include{variants}
\include{continuous}
\include{toys}
\include{real}
\include{appendix}
%%% \include{pointers}
\backmatter
% Begin ``Notation'' material
\renewcommand{\nomname}{Notation}%
\renewcommand{\pagedeclaration}[1]{\ (page #1)}%
\setlength{\nomlabelwidth}{2.0cm}%
\renewcommand{\nompreamble}{%
Throughout the book I write about random variables and stochastic
processes. I have tried to select notation that is as simple as
possible without being ambiguous. To illustrate the challenge
suppose that I have been talking about gambling and the weather
and that I say ``the probability of 5 is 0.16''. Among the many
things that I could mean are the following:
\begin{equation*}
\mathbf{Prob}(\text{top face of die}=5) = 0.16
\end{equation*}
\begin{equation*}
\lim_{\epsilon \rightarrow 0} \frac{\mathbf{Prob}(5 < \text{total
rainfall today in millimeters}<5+\epsilon)}{\epsilon} = 0.16
\end{equation*}
As a less cumbersome notation I prefer $P_D(5)=0.16$ or
$P_R(5)=0.16$, where $P$ denotes either a probability mass function
or a probability density function. I only use a subscript when it
is necessary to specify which function I mean.
In general I use the following conventions:
\begin{symbdescription}
\item[$X$] Upper case indicates a random variable. Although the
notation does not suggest it, the notion of a random variable
includes a set of possible values or outcomes and a probability
distribution for those values.
\item[$x$] Lower case indicates an \emph{outcome} or value of a
random variable.
\item[${\mathcal X}$] Occasionally I use a calligraphic font to
indicate the \emph{alphabet} or set of all possible values of a
random variable $X$.
\item[$\ts{X}{1}{T}$] A stochastic process indexed by the sequence
$[1,2,3,\ldots,T]$, \ie,\\
$\ti{X}{1},\ti{X}{2}, \ldots, \ti{X}{T}$.
\item[$\ts{x}{1}{T}$] A particular possible outcome of the stochastic
process $\ts{X}{1}{T}$.
\item[$X^*$] The set of $X$ sequences of arbitrary length.
\item[$\ti{X}{t}$] The random variable that results from picking a
single component of a stochastic process.
\item[$P(x)$] The probability (or density) that a random variable
will have the particular value $x$. I do not put a subscript on
$P$ when the context permits me to drop it without ambiguity.
\item[$P_{\ti{X}{t}} \left(x \right)$] The probability that the
value of $\ti{X}{t}$ is $x$.
\item[$P_{\ti{X}{t+1}|\ti{X}{t}} \left(x_1|x_2 \right)$] The
conditional probability that the value of $\ti{X}{t+1}$ is $x_1$
given that the value of $\ti{X}{t}$ is $x_2$.
\item[$\mu(\beta)$] The probability that an outcome is in the
\emph{set} $\beta$. I occasionally use this notation from
measure theory in Chapter~\ref{chap:toys}.
\item[$P \left(x|\theta \right)$] Rather than a subscript, I
occasionally use a conditioning variable to specify one of many
possible probability distributions.
\end{symbdescription}
\section*{Symbols}
The following symbols usually have the meanings described below:
}
\cleardoublepage%
\markboth{\nomname}{\nomname}%% Required to get correct page heading labels.
\printnomenclature
% End ``Notation'' material
\chapter*{Bibliography}
\addcontentsline{toc}{chapter}{Bibliography}%
\bibliographystyle{plain}
\bibliography{hmmds}
%%% \printindex prints the label ``Index'' already, and also seems to
%%% do a \clearpage first.
%%%
\clearpage
\addtocounter{page}{1}
\addcontentsline{toc}{chapter}{Index}%
\addtocounter{page}{-1}
\printindex[default][Page numbers set in \textbf{bold} type indicate a
principal or defining entry.]
\end{document}
%%%---------------
%%% Local Variables:
%%% eval: (load-file "hmmkeys.el")
%%% eval: (TeX-PDF-mode)
%%% End: