\documentstyle[12pt, ml99sub, epsf]{article}

\title{Sample-Based Hidden Markov Models\thanks{This paper has only been submitted to ICML-99}}
\author{Sebastian Thrun and John C.~Langord}
\date{}

\begin{document}

\maketitle

\begin{center}
Robot Learning Laboratory\\
School of Computer Science\\
5000 Forbes Ave.\\
Pittsburgh, PA 15213-3891, USA
\end{center}

\begin{abstract}
\noindent
We present a learning algorithm for hidden Markov models
with continuous state and observation spaces.  All necessary
probability density functions are approximated using samples, along
with density trees generated from such samples.  A Monte Carlo version
of Baum-Welch (EM) is employed to learn models from data, just as in
regular HMM learning.  Regularization during learning is obtained
using an exponential shrinking technique. The shrinkage factor, which
determines the effective capacity of the learning algorithm, is
annealed down over multiple iterations of Baum-Welch, and early
stopping is applied to select the right model.  We prove that under
mild assumptions, Monte Carlo Hidden Markov Models converge to a local
maximum in likelihood space, just like conventional HMMs. In addition,
we provide empirical results obtained in a gesture recognition domain,
which illustrate the appropriateness of the approach in practice.
\end{abstract}

\noindent
{\bf Keywords:} {\em Hidden Markov Models, Sampling, Monte Carlo Methods, Shrinkage, Density Trees, Gesture Recognition} \\

\noindent
{\bf Email address of contact author:}  thrun@cs.cmu.edu\\

\noindent
{\bf Phone number of contact author:} +1 (412) 268-8077  \\

\noindent
{\bf Electronic version:} gzipped PostScript emailed to icml99@ijs.si
\newpage


\section{Introduction}


We present a new algorithm for Hidden Markov Models. 


We present a new Hidden Markov Model which supports real-valued state
and observation spaces. It is capable of learning an almost
unrestricted range of Markov models, using non-parametric statistics.



Our approach uses sampling to approximate all densities.


parameteric vs non-parametric



Thorughout the last decade, HMMs have been applied successfully to a
large range of temporal signal processing problems, for tasks such as
modeling, filtering, classification and prediction of time sequences
in a range of partially observable, stochastic environments.  Hidden
Markov models are often the method of choice in areas such as speech
recognition \cite{Lee90aABBREV,Lee89aABBREV,Rabiner89aABBREV}, natural
language processing \cite{Charniak93aABBREV}, robotics
\cite{Meila96aABBREV,Koenig96aABBREV,Shatkay97aABBREV}, biological
sequence analysis
\cite{Henderson96aABBREV,Krogh94aABBREV,Pedersen96aABBREV}, and time
series analysis \cite{Hannaford91aABBREV,Weigend93aABBREV}.

Previous HMM algoroithms, however, were all subject to discrete or
parametric assumptions.  By using non-parametric sampling methods,
MCHMMs offer five primary advantages over previous work:
\begin{enumerate}
\item
{\bf Real-valued spaces.} 
\item
{\bf Not confined to specific parametic density.}
\item
{\bf Built-in complexity control.}
\item
{\bf Place computation where needed.}
\item
{\bf Resource adaptive.}
\end{enumerate}
We prove convergence of MCHMMs to local maxima in likelihood space,
thereby extending the well-known convergence of the Baum-Welch
algorithm, which only apply to discrete HMMs, to a much larger range
of representations.  We also present empiricial results obtained in a
gesture recognition domain, which validate the approach in practice.



\end{document}
