@device(postscript)
@libraryfile(Mathematics10)
@libraryfile(Accents)
@style(fontfamily=timesroman,fontscale=11)
@pagefooting(immediate, left "@c<Technical Report 1996>",
center "@c<Computer Science>",
right "@c<Carnegie Mellon>")
@heading(Approximation of Graphical Probabilistic Models by Iterative
Dynamic Discretization and its Application to Time-Series Segmentation)
@heading(CMU-CS-96-166)
@center(@b(Lonnie Dale Chrisman))
@center(September 1996 - Ph.D. Thesis)
@center(FTP: Unavailable)
@blankspace(1)
@begin(text)

Most artificial intelligence applications must cope with
uncertainty. Recent developments with graphical probabilistic models such as
Bayesian networks have introduced useful methods for reasoning explicitly
about degrees of uncertainty.  This thesis explores a method 
called @i(iterative dynamic discretization) for approximating
probabilistic inference in graphical networks. Continuous variables
(or variables with enormous sample spaces) are replaced by discrete
variables with a small number of possible values, and then the simplified
discrete model is solved using exact propagation methods. The results of
this computation are then used to find an improved  discretization for the
problem instance, and the process is iterated. The algorithm can be viewed
as applying Gibbs sampling to the space of possible discretizations,
obtaining a method for combining stochastic simulation methods with
exact propagation. Alternatively, it can be viewed as an instance of
approximate iterative  knowledge-based model construction (KBMC).

The thesis applies iterative dynamic discretization to a model-based
time-series segmentation problem. A formalism for modeling qualitative
signal shapes, durations, transitions, and uncertainty in multi-dimensional
time series, called a Hidden Segmented Semi-Markov Model (HSSMM),
is introduced and used to define a probabilistic model for the
time-series segmentation task. This is converted to a graphical
probabilistic model and solved by iterative dynamic discretization.
Iterative dynamic discretization is found to require substantially
fewer iterations compared to Gibbs sampling.

@blankspace(2line)
@begin(transparent,size=10)
@b(Keywords:@ )@c<Iterative dynamic discretization, model-based time-series
segmentation, approximation of graphical probabilistic models,
continuous variables in probabilistic models, discretization of
continuous variables, Bayesian networks, Markov fields, Gibbs sampling,
focused Gibbs sampling, exact propagation, clique-marginal propagation,
combination of Gibbs sampling and exact propagation, knowledge-based model
construction, Hidden Segmented Semi-Markov Models (HSSMMs), Hidden segmented
generalized Semi-Markov Models (HSGSMMs).>
@end(transparent)
@blankspace(1line)
@end(text)
@flushright(@b[(188 pages)])