Markov Processes on Curves.
We study the classification problem that arises when two variablesone continuous (x), one discrete (s)evolve jointly in time. We suppose that the vector x traces out a smooth multidimensional curve, to each point of which the variable s attaches a discrete label. The trace of s thus partitions the curve into different segments whose boundaries occur where s changes value. We consider how to learn the mapping between the trace of x and the trace of s from examples of segmented curves. Our approach is to model the conditional random process that generates segments of constant s along the curve of x. We suppose that the variable s evolves stochastically as a function of the arc length traversed by x. Since arc length does not depend on the rate at which a curve is traversed, this gives rise to a family of Markov processes whose predictions are invariant to nonlinear warpings (or reparameterizations) of time. We show how to estimate the parameters of these modelsknown as Markov processes on curves (MPCs)from labeled and unlabeled data. We then apply these models to two problems in automatic speech recognition, where x are acoustic feature trajectories and s are phonetic alignments.
Introduction
The automatic segmentation of continuous trajectories poses a challenging
problem in machine learning. The problem arises whenever a multi-dimensional
trajectory fx(t)jt 2 [0;  ]g must be mapped into a sequence
of discrete labels segmentation performs this mapping by
specifying consecutive time intervals such that
and attaching the labels sk to contiguous arcs along the trajectory. The
learning problem is to discover such a mapping from labeled or unlabeled
examples.
In this paper, we study this problem, paying special attention to the
fact that curves have intrinsic geometric properties that do not depend on
the rate at which they are traversed (do Carmo, 1976). Such properties
include, for example, the total arc length and the maximum distance
between any two points on the curve. Given a multidimensional trajectory
these properties are invariant to reparameterizations
monotonic function that maps the interval [0;
into itself. Put another way, the intrinsic geometric properties of the curve
are invariant to nonlinear warpings of time.
The study of curves requires some simple notions from differential
geometry. As a matter of terminology, we refer to particular parameterizations
of curves as trajectories. We regard two trajectories x1(t) and
x2 (t) as equivalent to the same curve if there exists a monotonically increasing
function f for which x1 be precise, we mean
the same oriented curve: the direction of traversal matters.) Here, as in
what follows, we adopt the convention of using x(t) to denote an entire
trajectory as opposed to constantly writing out fx(t)jt 2 [0;  ]g. Where
necessary to refer to the value of x(t) at a particular moment in time, we
use a different index, such as x(t1 ).
Let us now return to the problem of automatic segmentation. Consider
two variables-one continuous (x), one discrete (s)-that evolve jointly in
time. We assume that the vector x traces out a smooth multidimensional
curve, to each point of which the variable s attaches a discrete label. Note
that the trace of s yields a partition of the curve into different components;
in particular, the boundaries of these components occur at the points
where s changes value. We refer to such partitions as segmentations and
to the regions of constant s as segments; see figure 1.
Our goal in this paper is to learn a probabilistic mapping between trajectories
x(t) and segmentations s(t) from labeled or unlabeled examples.
Consider the random process that generates segments of constant s along
the curve traced out by x. Given a trajectory x(t), let Pr[s(t) j x(t)] denote
the conditional probability distribution over possible segmentations.
Suppose that for any two equivalent trajectories x(t) and x(f(t)), we have
the identity:
Eq. (1) captures a fundamental invariance-namely, that the probability
that the curve is segmented in a particular way is independent of the
rate at which it is traversed. In this paper, we study Markov processes
with this property. We call them Markov processes on curves (MPCs)
because for these processes it is unambiguous to write Pr[s j x] without
providing explicit parameterizations for the trajectories, x(t) or s(t). The
distinguishing feature of MPCs is that the variable s evolves as a function
of the arc length traversed along x, a quantity that is manifestly invariant
to nonlinear warpings of time.
Invariances and symmetries play an important role in statistical pattern
recognition because they encode prior knowledge about the problem
domain (Duda & Hart, 1973). Most work on invariances has focused on
spatial symmetries in vision. In optical character recognition, for example,
researchers have improved the accuracy of automatically trained classifiers
by incorporating invariances to translations, rotations, and changes of
scale (Simard, LeCun, & Denker, 1993). This paper focuses on an invariance
associated with pattern recognition in dynamical systems. Invariance
to nonlinear warpings of time arises naturally in problems involving the
segmentation of continuous trajectories. For example, in pen-based hand-writing
recognition, this invariance captures the notion that the shape of
start
t=t

Figure

1: Two variables-one continuous (x), one discrete (s)-evolve jointly
in time. The trace of s partitions the curve of x into different segments whose
boundaries occur where s changes value. Markov processes on curves model the
conditional distribution, Pr[sjx].
a letter does not depend on the rate at which it is penned. Likewise, in
automatic speech recognition (Rabiner & Juang, 1993), this invariance
can be used to model the effects of speaking rate. Thus, in addition to
being mathematically interesting in its own right, the principled handling
of this invariance has important consequences for real-world applications
of machine learning.
The main contributions of this paper are: (i) to postulate eq. (1) as
a fundamental invariance of random processes; (ii) to introduce MPCs
as a family of probabilistic models that capture this invariance; (iii) to
derive learning algorithms for MPCs based on the principle of maximum
likelihood estimation; and (iv) to compare the performance of MPCs for
automatic speech recognition versus that of hidden Markov models (Ra-
biner & Juang, 1993). In terms of previous work, our motivation most
closely resembles that of Tishby (1990), who several years ago proposed
a dynamical system approach to speech processing.
The organization of this paper is as follows. In section 2, we begin
by reviewing some basic concepts from differential geometry. We then
introduce MPCs as a family of continuous-time Markov processes that
parameterize the conditional probability distribution, Pr[s j x]. The processes
are derived from a set of differential equations that describe the
pointwise evolution of s along the curve traced out by x.
In section 3, we consider how to learn the parameters of MPCs in
both supervised and unsupervised settings. These settings correspond to
whether the learner has access to labeled or unlabeled examples. Labeled
examples consist of trajectories x(t), along with their corresponding segmentations

The ordered pairs in eq. (2) indicate that s(t) takes the value sk between
times the start and end states are used to mark endpoints.
Unlabeled examples consist only of the trajectories x(t) and the boundary
values:
f(start;
Eq. (3) specifies only that the Markov process starts at time
terminates at some later time  . In this case, the learner must infer its own
target values for s(t) in order to update its parameter estimates. We view
both types of learning as instances of maximum likelihood estimation and
describe an EM algorithm for the more general case of unlabeled examples.
In section 4, we describe some simple extensions of MPCs that significantly
increase their modeling power. We also compare MPCs to other
probabilistic models of trajectory segmentation, such as hidden Markov
models. We argue that MPCs are distinguished by two special proper-
ties: the natural handling of invariance to nonlinear warpings of time,
and the emphasis on learning a segmentation model Pr[sjx], as opposed
to a synthesis model Pr[xjs].
Finally, in section 5, we apply MPCs to the problem of automatic
speech recognition. In this setting, we identify the curves x with acoustic
feature trajectories and the segmentations s with phonetic alignments.
We present experimental results on two tasks-recognizing New Jersey
town names and connected alpha-digits. On these tasks, we find that
MPCs generally match or exceed the performance of comparably trained
hidden Markov models. We conclude in section 6 by posing several open
questions for future research.
Markov processes on curves
Markov processes on curves are based fundamentally on the notion of
arc length. After reviewing how to compute arc lengths along curves, we
show how they can be used to define random processes that capture the
invariance of eq. (1).
2.1 Arc length
Let g(x) define a D \Theta D matrix for each point x 2 R D ; in other words,
to each point x, we associate a particular D \Theta D matrix g(x). If g(x)
is non-negative definite for all x, then we can use it as a metric to compute
distances along curves. In particular, consider two nearby points
separated by the infinitesimal vector dx. We define the squared distance
between these two points as:
Arc length along a curve is the non-decreasing function computed by
integrating these local distances. Thus, for the trajectory x(t), the arc
length between the points x(t1) and x(t2) is given by:
dt
\Theta
where
dt [x(t)] denotes the time derivative of x. Note that the arc
length between two points is invariant under reparameterizations of the
smooth monotonic function
of time that maps the interval
In the special case where g(x) is the identity matrix for all x, eq. (5)
reduces to the standard definition of arc length in Euclidean space. More
generally, however, eq. (4) defines a non-Euclidean metric for computing
arc lengths. Thus, for example, if the metric g(x) varies as a function of
x, then eq. (5) can assign different arc lengths to the trajectories x(t) and
is a constant displacement.
2.2 States and lifelengths
The problem of segmentation is to map a trajectory x(t) into a sequence
of discrete labels s1 these labels are attached to contiguous arcs
along the curve of x, then we can describe this sequence by a piecewise
constant function of time, s(t), as in figure 1. We refer to the possible
values of s as states. In what follows, we introduce a family of random
processes that evolve s as a function of the arc length traversed along the
curve traced out by x. These random processes are based on a simple
premise-namely, that the probability of remaining in a particular state
decays exponentially with the cumulative arc length traversed in that state.
The signature of a state is the particular way in which it computes arc
length.
To formalize this idea, we associate with each state i the following
quantities: (i) a metric g i (x) that can be used to compute arc lengths,
as in eq. (5); (ii) a decay parameter  i that measures the probability
per unit arc length that s makes a transition from state i to some other
state; and (iii) a set of transition probabilities a ij , where a ij represents the
probability that-having decayed out of state i-the variable s makes a
transition to state j. Thus, a ij defines a stochastic transition matrix with
zero elements along the diagonal and rows that sum to one: a
1. Note that all these quantities-the metric g i (x), the decay
parameter  i , and the transition probabilities a ij -depend explicitly on
the state i with which they are associated.
Together, these quantities can be used define a Markov process along
the curve traced out by x. In particular, let p i (t) denote the probability
that s is in state i at time t, based on its history up to that point in time.
A Markov process is defined by the set of differential equations:
dt
\Theta
\Theta
The right hand side of eq. (6) consists of two competing terms. The first
term computes the probability that s decays out of state i; the second
computes the probability that s decays into state i. Both probabilities
are proportional to measures of arc length, and combining them gives the
overall change in probability that occurs in the time interval [t; t
The process is Markovian because the evolution of p i depends only on
quantities available at time t; thus the future is independent of the past
given the present.
Eq. (6) has certain properties of interest. First, note that summing
both sides over i gives the identity
This shows that p i
remains a normalized probability distribution: i.e.,
times.
Second, suppose that we start in state i and do not allow return visits: i.e.,
j. In this case, the second term of eq. (6) van-
ishes, and we obtain a simple, one-dimensional linear differential equation
for It follows that the probability of remaining in state i decays exponentially
with the amount of arc length traversed by x, where arc length
is computed using the matrix g i (x). The decay parameter,  i , controls
the typical amount of arc length traversed in state i; it may be viewed
as an inverse lifetime or-to be more precise-an inverse lifelength. Fi-
nally, noting that arc length is a reparameterization-invariant quantity, we
therefore observe that these dynamics capture the fundamental invariance
of eq. (1).
2.3 Inference
Let a0i denote the probability that the variable s makes an immediate
transition from the start state-denoted by the zero index-to state i;
put another way, this is the probability that the first segment belongs to
state i. Given a trajectory x(t), the Markov process in eq. (6) gives rise
to a conditional probability distribution over possible segmentations, s(t).
Consider the segmentation in which s(t) takes the value sk between times
and tk , and let
dt
\Theta
denote the arc length traversed in state sk . From eq. (6), we know that the
probability of remaining in a particular state decays exponentially with
this arc length. Thus, the conditional probability of this segmentation is
given by:
Y
Y
as k s k+1
where we have used s0 and sn+1 to denote the start and end states of the
Markov process. The first product in eq. (8) multiplies the probabilities
that each segment traverses exactly its observed arc length. The second
product multiplies the probabilities for transitions between states sk and
sk+1 . The leading factors of s k
are included to normalize each state's
duration model.
There are many important quantities that can be computed from the
distribution, Pr[sjx]. Of particular interest is the most probable segmentation

Given a particular trajectory x(t), eq. (9) calls for a maximization over all
piecewise constant functions of time, s(t). In practice, this maximization
can be performed by discretizing the time axis and applying a dynamic
programming (or forward-backward) procedure. The resulting segmentations
will be optimal at some finite temporal resolution, \Deltat. For example,
let ff i (t) denote the log-likelihood of the most probable segmentation, ending
in state i, of the subtrajectory up to time t. Starting from the initial
condition
\Theta
is the discrete delta function. Also, at each time step, let \Psi j (t+
\Deltat) record the value of i that maximizes the right hand side of eq. (10).
Suppose that the Markov process terminates at time  . Enforcing the
endpoint condition s   we find the most likely segmentation by
back-tracking:
These recursions yield a segmentation that is optimal at some finite temporal
resolution \Deltat. Generally speaking, by choosing \Deltat to be sufficiently
small, one can minimize the errors introduced by discretization. In prac-
tice, one would choose \Deltat to reflect the time scale beyond which it is
not necessary to consider changes of state. For example, in pen-based
handwriting recognition, \Deltat might be determined by the maximum pen
velocity; in automatic speech recognition, by the sampling rate and frame
rate.
Other types of inferences can be made from the distribution, eq. (8).
For example, one can compute the marginal probability, Pr
that the Markov process terminates at precisely the observed time. Simi-
larly, one can compute the posterior probability,
end], that at an earlier moment in time, t1 , the variable s was in state i.
These inferences are made by summing the probabilities in eq. (8) over all
segmentations that terminate precisely at time  . This sum is performed
by discretizing the time axis and applying a forward-backward procedure
similar to eqs. (10-11). These algorithms have essentially the same form
as their counterparts in hidden Markov models (Rabiner & Juang, 1993).
3 Learning from examples
The learning problem in MPCs is to estimate the parameters f i
in eq. (6) from examples of segmented (or non-segmented) curves. Our
first step is to assume a convenient parameterization for the metrics, g i (x),
that compute arc lengths. We then show how to fit these metrics, along
with the parameters  i and a ij , by maximum likelihood estimation.
3.1 Parameterizing the metric
A variety of parameterizations can be considered for the metrics, g i (x).
The simplest possible form is a Euclidean metric, where g i (x) does not
have any dependence on the point x. Such a metric has the virtue of
simplicity, but it is not very powerful in terms of what it can model. In
this paper, we consider the more general form:
where \Phi i (x) is a positive scalar-valued function of x, and oe i is a positive-definite
matrix with joe 1. Eq. (12) is a conformal transformation
(Wald, 1984) of a Euclidean metric-that is, a non-Euclidean metric in
which all the dependence on x is captured by a scalar prefactor.
conformal transformation is one that locally preserves angles, but not
distances.) Eq. (12) strikes one possible balance between the confines
of Euclidean geometry and the full generality of Riemannian manifolds.
The determinant constraint joe imposed to avoid the degenerate
solution 0, in which every trajectory is assigned zero arc length.
Note that we have defined the metric g i (x) in terms of the inverse of oe
this turns out to simplify the parameter reestimation formula for oe i , given
later in the section.
The form of the metric determines the nature of the learning problem
in MPCs. For the choice in eq. (12), one must estimate the functions
the matrices oe i , the decay parameters  i and the transition
probabilities a ij . In this section, we will consider the functions \Phi i (x) as
fixed or pre-determined, leaving only the parameters oe i ,  i , and a ij to be
estimated from training data. Later, in section 4.2, we will suggest a particular
choice for the functions \Phi i (x) based on the relationship between
MPCs and hidden Markov models.
3.2 Labeled examples
Suppose we are given examples of segmented trajectories, fx ff (t); s ff (t)g,
where the index ff runs over the examples in the training set. As short-
hand, let I iff (t) denote the indicator function that selects out segments
associated with state i:
I iff
Also, let ' iff denote the total arc length traversed by state i in the ffth
example:
Z
dt I iff (t)
\Theta
In this paper we view learning as a problem in maximum likelihood esti-
mation. Thus we seek the parameters that maximize the log-likelihood:
ff
iff
is the overall number of observed transitions from state i to
state j. Eq. (15) follows directly from the distribution over segmentations
in eq. (8). Note that the first two terms measure the log-likelihood
of observed segments in isolation, while the last term measures the log-likelihood
of observed transitions.
Eq. (15) has a convenient form for maximum likelihood estimation.
In particular, for fixed oe i , there are closed-form solutions for the optimal
values of  i and a ij ; these are given by:
ff
These formulae are easy to interpret. The transition
probabilities a ij are determined by observed counts of transitions, while
the decay parameters  i are determined by the mean arc lengths traversed
in each state.
In general, we cannot find closed-form solutions for the maximum likelihood
estimates of oe i . However, we can update these matrices in an iterative
fashion that is guaranteed to increase the log-likelihood at each step.
Denoting the updated matrices by ~ oe i , we consider the iterative scheme
(derived in the appendix):
ff
Z
dt I iff (t)
x ff
ff
\Theta
x ff2
where the constant c i is determined by the determinant constraint j~oe
1. The reestimation formula for oe i involves a sum and integral over all
segments assigned to the ith state of the MPC. In practice, the integral is
evaluated numerically by discretizing the time axis. By taking gradients
of eq. (15), one can show that the fixed points of this iterative procedure
correspond to stationary points of the log-likelihood. A proof of monotonic
convergence is given in the appendix.
In the case of labeled examples, the above procedures for maximum
likelihood estimation can be invoked independently for each state i. One
first iterates eq. (18) to estimate the matrix elements of oe i . These parameters
are then used to compute the arc lengths, ' iff , that appear in eq. (14).
Given these arc lengths, the decay parameters and transition probabilities
follow directly from eqs. (16-17). Thus the problem of learning given
labeled examples is relatively straightforward.
3.3 Unlabeled examples
In an unsupervised setting, the learner does not have access to labeled ex-
amples; the only available information consists of the trajectories x ff (t),
as well as the fact that each process terminates at some time  ff . The goal
of unsupervised learning is to maximize the log-likelihood that for each
trajectory x ff (t), some probable segmentation can be found that terminates
at precisely the observed time. The appropriate marginal probability
is computed by summing Pr[s(t)jx(t)] over allowed segmentations, as
described at the end of section 2.3.
The maximization of this log-likelihood defines a problem in hidden
variable density estimation. The hidden variables are the states of the
Markov process. If these variables were known, the problem would reduce
to the one considered in the previous section. To fill in these missing val-
ues, one can use the Expectation-Maximization (EM) algorithm (Baum,
1972; Dempster, Laird, & Rubin, 1976). Roughly speaking, the EM algorithm
works by converting the maximization of the hidden variable
problem into a weighted version of the problem where the segmentations,
s ff (t), are known. The weights are determined by the posterior probabil-
ities, Pr[s ff (t)jx ff (t); s ff ( ff derived from the current parameter
estimates.
We note that eqs. (10-11) suffice to implement an extremely useful
approximation to the EM algorithm in MPCs. This approximation is to
compute, based on the current parameter estimates, the optimal segmen-
tation, s
ff (t), for each trajectory in the training set; one then re-estimates
the parameters of the Markov process by treating the inferred segmen-
tations, s
ff (t), as targets. This approximation reduces the problem of
parameter estimation to the one considered in the previous section. It
can be viewed as a winner-take-all approximation to the full EM algo-
rithm, analogous to the Viterbi approximation for hidden Markov models
(Rabiner & Juang, 1993).
Essentially the same algorithm can also be applied to the intermediate
case of partially labeled examples. In this setting, the state sequences are
specified, but not the segment boundaries; in other words, examples are
provided in the form:
The ability to handle such examples is important for two reasons: first,
because they provide more information than unlabeled examples, and sec-
ond, because complete segmentations in the form of eq. (2) may not be
available. For example, in the problem of automatic speech recognition,
phonetic transcriptions are much easier to obtain than phonetic align-
ments. As before, we can view the learning problem for such examples
as one in hidden variable density estimation. Knowledge of the state sequence
is incorporated into the EM algorithm by restricting the forward-backward
procedures to consider only those paths that pass through the
desired sequence.
4 Observations
In this section, we present some extensions to MPCs and discuss how they
relate to other probabilistic models for trajectory segmentation.
4.1 Extensions to MPCs
MPCs can accomodate more general measures of distance than the one
presented in eq. (4). For example, let
xj denote the unit tangent
vector along the curve of x, where j
simple extension of
eq. (4) is to consider d'
x, where g(x; u) depends not only
on the point x, but also on the tangent vector u. This extension enables
one to assign different distances to time-reversed trajectories, as opposed
to the measure in eq. (5), which does not depend on whether the curve
is traversed forwards or backwards. More generally, one may incorporate
any of the vector invariants
dt
into the distance measure. These vectors characterize the local geometry
at each point along the curve; in particular, eq. (20) gives the point x for
the unit tangent vector u for the local curvature for
etc. Incorporating higher-order derivatives in this way enables one to use
fairly general distance measures in MPCs.
The invariance to nonlinear warpings of time can also be relaxed in
MPCs. This is done by including time as a coordinate in its own right-
i.e., by operating on the spacetime trajectories computing
generalized arc lengths, d'
z T G(x)
z, where
G(x) is a spacetime metric-a (D+1)-dimensional square matrix for each
point x. The effect of replacing
x by
z is to allow stationary portions of
the trajectory to contribute to the integral
R
d'. The admixture of
space and time coordinates in this way is an old idea from physics, originating
in the theory of relativity, though in that context the metric is
negative-definite (Wald, 1984). Note that this extension of MPCs can
also be combined with the previous one-for instance, by incorporating
both tangent vectors and timing information into the distance measure.
4.2 Relation to hidden Markov models and previous
work
Hidden Markov models (HMMs), currently the most popular approach to
trajectory segmentation, are also based on probabilistic methods. These
models parameterize joint distributions of the form:
Y
There are several important differences between HMMs and MPCs (be-
sides the trivial one that HMMs are formulated for discrete-time pro-
cesses). First, the predictions of HMMs are not invariant to nonlinear
warpings of time. For example, consider the pair of trajectories x t and y t ,
where y t is created by the doubling operation:
ae
y
Both trajectories trace out the same curve, but y t does so at half the rate
as x t . In general, HMMs will not assign these trajectories the same like-
lihood, nor are they guaranteed to infer equivalent segmentations. This
is true even for HMMs with more sophisticated durational models (Ra-
biner & Juang, 1993). By contrast, these trajectories will be processed
identically by MPCs based on eqs. (5-6).
The states in HMMs and MPCs are also weighted differently by their
inference procedures. On one hand, in HMMs, the contribution of each
state to the log-likelihood grows in proportion to its duration in time
(i.e., to the number of observations attributed to that state). On the
other hand, in MPCs, the contribution of each state grows in proportion
to its arc length. Naturally, the weighting by arc length attaches a more
important role to short-lived states with non-stationary trajectories. The
consequences of this for automatic speech recognition are discussed in
section 5.
HMMs and MPCs also differ in what they try to model. HMMs parameterize
joint distributions of the form given by eq. (21). Thus, in HMMs,
parameter estimation is directed at learning a synthesis model, Pr[xjs],
while in MPCs, it is directed at learning a segmentation model, Pr[sjx].
The direction of conditioning on x is a crucial difference. In HMMs,
one can generate artificial trajectories by sampling from the joint distribution
Pr[s; x]; MPCs, on the other hand, do not provide a generative
model of trajectories. The Markov assumption is also slightly different
in HMMs and MPCs. HMMs observe the conditional independence
such that the state, s t+1 , is independent of
the observation, x t , given the previous state, s t . By contrast, in MPCs the
evolution of p i (t), as given by eq. (6), depends explicitly on the trajectory
at time t-namely, through the arc length [
x] 1=2 .
While MPCs do not provide a generative model of trajectories, we
emphasize that they do provide a generative model of segmentations. In
particular, one can generate a state sequence s0s1s2
the start state and sn+1 is the end state, by sampling from the transition
probabilities a ij . (Here, the sequence length n is not fixed in advance,
but determined by the sampling procedure.) Moreover, for each state
sk , one can generate an arc length 'k by sampling from the exponential
distribution,
Together, these sampled values of sk
and 'k define a segmentation that can be grafted onto any (sufficiently
long) trajectory x(t). Importantly, this interpretation of MPCs allows
them to be combined hierarchically with other generative models (such as
language models in automatic speech recognition).
Finally, we note that one can essentially realize HMMs as a special
case of MPCs. This is done by computing arc lengths along spacetime
trajectories as described in section 4.1. In this setting,
one can mimic the predictions of HMMs by setting the oe i matrices to have
only one non-zero element (namely, the diagonal element for delta-time
contributions to the arc length) and by defining the functions \Phi i (x) in
terms of the HMM emission probabilities Pr(xji) as:
This equation sets up a correspondence between the emission log-probabilities
in HMMs and the arc lengths in MPCs. Ignoring the effects of transition
probabilities (which are often negligible), an MPC initialized by
eq. (23) and this singular choice of oe i will reproduce the segmentations
of its "parent" HMM. This correspondence is important because it allows
one to bootstrap an MPC from a previously trained HMM. (Also, despite
many efforts, we have not found a more effective way to estimate the
functions \Phi i (x).)
In terms of previous work, our motivation for MPCs resembles that
of Tishby (1990), who several years ago proposed a dynamical systems
approach to speech processing. Because MPCs exploit the notion that
trajectories are continuous, they also bear some resemblance to so-called
segmental HMMs (Ostendorf, Digalakis, & Kimball, 1996). MPCs nevertheless
differ from segmental HMMs in two important respects: (i) the
treatment of arc length-particularly, the estimation of a metric g i (x) for
each hidden state of the Markov process, and (ii) the emphasis on learning
a segmentation model Pr[sjx], as opposed to a synthesis model, Pr[xjs],
that is even more complicated than the one in ordinary HMMs.
5 Automatic speech recognition
The Markov processes in this paper were conceived as models for automatic
speech recognition (Rabiner & Juang, 1993). Speech recognizers
take as input a sequence of feature vectors, each of which summarizes the
acoustic properties of a short window of speech. Acoustic feature vectors
typically have ten or more components, so that a particular sequence of
feature vectors can be viewed as tracing out a multidimensional curve.
The goal of a speech recognizer is to translate this curve into a sequence
of words, or more generally, a sequence of sub-syllabic units known as
phonemes. Denoting the feature vectors by x t and the phonemes by s t ,
we can view this problem as the discrete-time equivalent of the segmentation
problem in MPCs.
5.1 Invariances of speech
Though HMMs have led to significant advances in automatic speech recog-
nition, they are handicapped by certain weaknesses. One of these is the
poor manner in which they model variations in speaking rate (Siegler &
Stern, 1995). Typically, HMMs make more errors on fast speech than
slow speech. A related effect, occurring at the phoneme level, is that
consonants are confused more often than vowels. Generally speaking,
consonants have short-lived, non-stationary acoustic signatures; vowels,
just the opposite. Thus, at the phoneme level, we can view consonantal
confusions as a consequence of locally fast speech.
It is tempting to imagine that HMMs make these mistakes because
they do not incorporate an invariance to nonlinear warpings of time.
While this oversimplifies the problem, it is clear that HMMs have systemic
biases. In HMMs, the contribution of each state to the log-likelihood
grows in proportion to its duration in time. Thus decoding procedures
in HMMs are inherently biased to pay more attention to long-lived states
than short-lived ones. In our view, this suggests one plausible explanation
for the tendency of HMMs to confuse consonants more often than vowels.
MPCs are quite different from HMMs in how they weight the speech
signal. In MPCs, the contribution of each state is determined by its arc
length. The weighting by arc length attaches a more important role to
short-lived but non-stationary phonemes, such as consonants. Of course,
one can imagine heuristics in HMMs that achieve the same effect, such
as dividing each state's contribution to the log-likelihood by its observed
(or inferred) duration. Unlike such heuristics, however, the metrics g i (x)
in MPCs are estimated from each state's training data; in other words,
they are designed to reweight the speech signal in a way that reflects the
statistics of acoustic trajectories.
Admittedly, it is oversimplistic to model the effects of speaking rate
by an invariance to nonlinear warpings of time. The acoustic realization
(i.e., spectral profile) of any phoneme does depend to some extent on
the speaking rate, and certain phonemes are more likely to be stretched
or shortened than others. An invariance to nonlinear warpings of time
also presupposes a certain separation of time scales: on one hand, there
is the time scale at which acoustic features (such as spectral energies,
formant bandwidths, or pitch) are extracted from the speech signal; on
the other, there is the time scale at which these features tend to vary.
These time scales need to be well separated for MPCs to have a meaningful
interpretation. Whether this is true obviously depends on the choice of
acoustic features.
Despite these caveats, we feel that MPCs provide a compelling alternative
to traditional methods. While we have motivated MPCs by
appealing to the intrinsic geometric properties of curves, we emphasize
that for automatic speech recognition, it is critically important to relax
the invariance to nonlinear warpings of time. This is done by computing
arc lengths along spacetime trajectories, as described in section 4.1. This
extension allows MPCs to incorporate both movement in acoustic feature
space and duration in time as measures of phonemic evolution. Both of
these measures are important for speech recognition.
5.2 Experiments
Both HMMs and MPCs were used to build connected speech recogniz-
ers. Training and test data came from speaker-independent databases of
telephone speech. All data was digitized at the caller's local switch and
transmitted in this form to the receiver. For feature extraction, input
telephone signals (sampled at 8 kHz and band-limited between 100-3800
were pre-emphasized and blocked into 30ms frames with a frame shift
of 10ms. Each frame was Hamming windowed, autocorrelated, and processed
by a linear predictive coding (LPC) cepstral analysis to produce a
vector of 12 liftered cepstral coefficients (Rabiner & Juang, 1993). The
feature vector was then augmented by its normalized log energy value,
as well as temporal derivatives of first and second order. Overall, each
frame of speech was described by 39 features. These features were used
differently by HMMs and MPCs, as described below.
Recognizers were evaluated on two tasks. The first task was recognizing
New Jersey town names (e.g., Hoboken). The training data for this
task (Sachs et al, 1994) consisted of 12100 short phrases, spoken in the
seven major dialects of American English. These phrases, ranging from
two to four words in length, were selected to provide maximum phonetic
coverage. The test data consisted of 2426 isolated utterances of 1219 New
Jersey town names and was collected from nearly 100 speakers. Note that
the training and test data for this task have non-overlapping vocabularies.
Baseline recognizers were built using 43 left-to-right continuous-density
HMMs, each corresponding to a context-independent English phone. Phones
were modeled by three-state HMMs, with the exception of background
mixture components HMM error rate (%) MPC error rate (%)

Table

1: Error rates on the task of recognizing New Jersey town names versus
the number of mixture components per hidden state.
noise, which was modeled by a single state. State emission probabilities
were computed by Gaussian mixture models with diagonal covariance ma-
trices. Different sized models were trained using
mixture components per hidden state; for a particular model, the number
of mixture components was the same across all states. Mixture model
parameters were estimated by a Viterbi implementation of the Baum-Welch
algorithm. Transition probabilities were assigned default values; in
particular, all transitions allowed by the task grammar were assumed to
be equally probable. (This assumption simplifies the forward-backward
procedure in large state spaces.)
MPC recognizers were built using the same overall grammar. Each
hidden state in the MPCs was assigned a metric g i
(x). The
functions \Phi i (x) were initialized (and fixed) by the state emission probabilities
of the HMMs, as given by eq. (23). The matrices oe i were estimated
by iterating eq. (18). We computed arc lengths along the 14 dimensional
spacetime trajectories through cepstra, log-energy, and time. Thus each
oe i was a 14 \Theta 14 symmetric matrix applied to tangent vectors consisting
of delta-cepstra, delta-log-energy, and delta-time. Note that these MPCs
made use of both extensions discussed in section 4.1. Curiously, our best
results for MPCs were obtained by setting  as opposed to estimating
the values of these decay parameters from training data. We suspect
this was due to the highly irregular (i.e., non-exponential) distribution of
arc lengths in the state representing silence and background noise. As in
the HMMs, transition probabilities were assigned default values.

Table

1 shows the results of these experiments comparing MPCs to
HMMs. The error rates in these experiments measure the percentage of
town names that were incorrectly recognized. For various model sizes (as
measured by the number of mixture components), we found the MPCs
to yield consistently lower error rates than the HMMs. The graph in
figure 2 plots these error rates versus the number of modeling parameters
per hidden state. This graph shows that the MPCs are not outperforming
the HMMs merely because they have extra modeling parameters
(i.e., the oe i matrices). The beam widths for the decoding procedures in
these experiments were chosen so that corresponding recognizers activated
roughly equal numbers of arcs.
The second task in our experiments involved the recognition of connected
alpha-digits (e.g., N Z 3 V J 2). The training and test
data consisted of 14622 and 7255 utterances, respectively. Recognizers
parameters per state
error
rate
NJ town names

Figure

2: Error rates for HMMs (dashed) and MPCs (solid) on New Jersey town
names versus the number of parameters per hidden state.
mixture components HMM error rate (%) MPC error rate (%)

Table

2: Word error rates on the task of recognizing connected alpha-digits
versus the number of mixture components per hidden state.
were built from 285 sub-word HMMs/MPCs, each corresponding to a
context-dependent English phone. The recognizers were trained and evaluated
in the same way as the previous task, except that we measured word
error rates instead of phrase error rates. The results, shown in table 2 and
figure 3, follow a similar pattern as before, with the MPCs outperforming
the HMMs.
6 Discussion
The experimental results in the previous section demonstrate the viability
of MPCs for automatic speech recognition. Nevertheless, several issues
require further attention. One important issue is the problem of feature
selection-namely, how to extract meaningful trajectories from the speech
signal. In this work, we used the same cepstral features for both MPCs
and HMMs; this was done to facilitate a side-by-side comparison. It is
doubtful, however, that cepstral trajectories (which are not particularly
smooth) provide the most meaningful type of input to MPCs. Intuitively,
one suspects that pitch contours or formant trajectories would provide
smoother, more informative trajectories than cepstra; unfortunately, these
types of features are difficult to track in noisy or unvoiced speech. Further
work in this area is needed.
Another important issue for MPCs is learning-namely, how to param-
parameters per state
error
rate
alpha-digits

Figure

3: Word error rates for HMMs (dashed) and MPCs (solid) on connected
alpha-digits versus the number of parameters per hidden state.
eterize and estimate the metrics g i (x) from trajectories x(t). We stress
that the learning problem in MPCs has many more degrees of freedom
than the corresponding one in HMMs. In particular, whereas in HMMs
one must learn a distribution Pr(xji) for each hidden state, in MPCs one
must learn a metric g i (x). The former is a scalar-valued function over
the acoustic feature space; the latter, a matrix-valued function. It is fair
to say that we do not understand how to parameterize metrics nearly as
well as probability distributions. Certainly, MPCs have the potential to
exploit more sophisticated metrics than the one studied in this paper.
Moreover, it is somewhat unsatisfactory that the metric in eq. (12) relies
on a trained HMM for its initialization.
On a final note, we emphasize that the issues of feature selection and
parameter estimation in MPCs are not independent. The cepstral front
end in today's speech recognizers is extremely well matched to the HMM
back end; indeed, one might argue that over the last decade of research,
each has been systematically honed to compensate for the other's failings.
It seems likely that future progress in automatic speech recognition will
require concerted efforts at both ends. Thus we hope that besides providing
an alternative to HMMs, MPCs also encourage a fresh look at the
signal processing performed by the front end.
Reestimation formula
In this appendix we derive the reestimation formula, eq. (18) and show
that it leads to monotonic increases in the log-likelihood, eq. (15). Recall
that in MPCs, the probability of remaining in a state decays exponentially
as a function of the arc length. It follows that maximizing the
log-likelihood in each state is equivalent to minimizing its arc length. For
the choice of metric in eqs. (12) and (23), the learning problem reduces
to optimizing the matrices oe i . For simplicity, consider the arc length of a
z

Figure

4: The square root function is concave and upper bounded by p
The bounding tangents are shown for
single trajectory under this metric:
Z dt
\Theta
Here we have written the arc length '(oe) explicitly as a function of the
matrix oe, and we have suppressed the state index for notational convenience

Our goal is to minimize '(oe), subject to the determinant constraint
1. Note that the matrix elements of oe \Gamma1 appear nonlinearly in
the right hand side of eq. (24); thus it is not possible to compute their
optimal values in closed form. As an alternative, we consider the auxiliary
Z dt
ae
x
\Theta
oe
where ae is a D \Theta D positive-definite matrix like oe. It follows directly from
the definition in eq. (25) that trivially, we
observe that Q(ae; ae)  Q(ae; oe) for all positive definite matrices ae and oe.
This inequality follows from the concavity of the square root function, as
illustrated in figure 4.
Consider the value of ae which minimizes Q(ae; oe), subject to the determinant
constraint We denote this value by ~
Because the matrix elements of ae \Gamma1 appear linearly in Q(ae; oe), this minimization
reduces to computing the covariance matrix of the tangent vector
x, as distributed along the trajectory x(t). In particular, we have:
~ oe /
Z dt
x
where the constant of proportionality is determined by the constraint
To minimize '(oe) with respect to oe, we now consider the iterative
procedure where at each step we replace oe by ~
oe. We observe that:
Q(~oe; oe) due to concavity
Q(oe; oe) since ~
with equality generally holding only when ~ In other words, this
iterative procedure converges monotonically to a local minimum of the
arc length, '(oe). Extending this procedure to combined arc lengths over
multiple trajectories, we obtain eq. (18).

Acknowledgements

The authors thank F. Pereira for many helpful comments about the presentation
of these ideas.



--R

An inequality and associated maximization technique in statistical estimation for probabilistic functions of a markov process.
Maximum likelihood from incomplete data via the em algorithm.
Differential Geometry of Curves and Sur- faces
Pattern Classification and Scene Analysis.
From HMMs to segment models: a unified view of stochastic modeling for speech recognition.
Fundamentals of Speech Recognition.
United States English subword speech data.
On the effects of speech rate in large vocabulary speech recognition systems.
Efficient pattern recognition using a new transformation distance.
A dynamical system approach to speech process- ing
General Relativity.
--TR
Fundamentals of speech recognition
Efficient Pattern Recognition Using a New Transformation Distance

--CTR
Yon Visell, Spontaneous organisation, pattern models, and music, Organised Sound, v.9 n.2, p.151-165, August 2004
automatic speech recognition;markov processes on curves;hidden Markov models