Browse Prior Art Database

# Efficient Computation of the Frequency Distribution of an Output Symbol As Generated by a Discrete-Output Hidden Markov Model

IP.com Disclosure Number: IPCOM000101063D
Original Publication Date: 1990-Jun-01
Included in the Prior Art Database: 2005-Mar-16
Document File: 2 page(s) / 67K

IBM

## Related People

Bahl, LR: AUTHOR [+4]

## Abstract

Given a discrete-output hidden Markov model, M, and an output alphabet a , a ,....,a , we may wish to compute the probability that the model M generates precisely n of some output symbol a. The invention herebelow represents an efficient means of computing the required probabilities.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Efficient Computation of the Frequency Distribution of an Output Symbol As Generated by a Discrete-Output Hidden Markov Model

Given a discrete-output hidden Markov model, M, and an
output alphabet a , a ,....,a , we may wish to compute the
probability that the model M generates precisely n of some output
symbol a.  The invention herebelow represents an efficient means of
computing the required probabilities.

Let M have L states.  We will assume that states can be
connected via null and non-null arcs, but we shall require the
constraint that the states be numbered in such a way that each null
arc goes from a lower-numbered state to a higher-numbered state.

(Image Omitted)

Let P  (s, n¯ t) denote the probability that at time t, state s
is active and precisely n instances of output symbol a  have been
generated.  Let N(s) denote the set of states that lead to state s
via a null arc, and R(s) denote the set of states that lead to state
s via a non-null arc.  Note that N(s) and R(s) need not be mutually
exclusive.  Let T(k ¯ j) denote the (transition) probability of going
from state j to state K, and let O(a  ¯ j,k) denote the (output)
probability of producing symbol a  during the transition from state j
to state k.

The probability that the model M generates precisely n
instances of symbol ay is
Setting
we see that p  (L,n - t) can easily be calculated by taking advantage
of the following recursive equations.
If t > O,
If t >...