隐马尔科夫模型的分析和应用_隐马尔可夫的应用

HHMM

隐马尔科夫模型

5星 · 超过95%的资源需积分: 10 128 浏览量更新于2023-03-03 评论 1 收藏 1002KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

Machine Learning, 32, 41–62 (1998)

1998 Kluwer Academic Publishers, Boston. Manufactured in The Netherlands.

The Hierarchical Hidden Markov Model:

Analysis and Applications

SHAI FINE fshai@cs.huji.ac.il

Institute of Computer Science, Hebrew University, Jerusalem 91904, Israel

YORAM SINGER singer@research.att.com

AT&T Labs, 180 Park Avenue, Florham Park, NJ 07932

NAFTALI TISHBY tishby@cs.huji.ac.il

Institute of Computer Science, Hebrew University, Jerusalem 91904, Israel

Editor: David Haussler

Abstract. We introduce, analyze and demonstrate a recursive hierarchical generalization of the widely used

hiddenMarkovmodels,whichwenameHierarchicalHiddenMarkov Models (HHMM). Our model is motivatedby

the complex multi-scale structure which appears in many natural sequences, particularly in language, handwriting

and speech. We seek a systematic unsupervised approach to the modeling of such structures. By extending the

standard Baum-Welch (forward-backward) algorithm, we derive an efﬁcient procedure for estimating the model

parameters from unlabeled data. We then use the trained model for automatic hierarchical parsing of observation

sequences. We describe two applications of our model and its parameter estimation procedure. In the ﬁrst

application we show how to construct hierarchical models of natural English text. In these models different levels

of the hierarchy correspond to structures on different length scales in the text. In the second application we

demonstrate how HHMMs can be used to automatically identify repeated strokes that represent combination of

letters in cursive handwriting.

Keywords: statistical models, temporal pattern recognition, hidden variable models, cursive handwriting

1. Introduction

Hidden Markov models (HMMs) have become the method of choice for modeling stochas-

tic processes and sequences in applications such as speech and handwriting recognition

(Rabiner & Juang, 1986, Nag et al., 1985) and computational molecular biology

(Krogh et al., 1993, Baldi et al., 1994). Hidden Markov models are also used for natu-

ral language modeling (see e.g. (Jelinek, 1985)). In most of these applications the model’s

topology is determined in advance and the model parameters are estimated by an EM proce-

dure (Dempster et al., 1977), known as the Baum-Welch (or forward-backward) algorithm

in this context (Baum & Petrie, 1966). Some recent works has explored the inference of the

model structure as well (Stolcke & Omohundro, 1994). In most of the above applications,

however, there are difﬁculties due to the multiplicity of length scales and recursive nature

of the sequences. Some of these difﬁculties can be overcome using stochastic context free

grammars (SCFG). The parameters of stochastic grammars are difﬁcult to estimate since

typically the likelihood of observed sequences induced by a SCFG varies dramatically with

small changes in the parameters of the model. Furthermore, the common algorithm for

parameter estimation of SCFGs, called the inside-outside algorithm (Lari & Young, 1990),

has a cubic time complexity in the length of the observed sequences.

42 S. FINE, Y. SINGER AND N. TISHBY

In this paper we present a simpler alternative to SCFGs that utilizes the self-similar and

hierarchical structure of natural sequences, namely, the hierarchical hidden Markov model.

Our primary motivation is to enable better modeling of the different stochastic levels and

length scales that are present in the natural language, whether speech, handwriting, or text.

Another important property of such models is the ability to infer correlated observations

overlongperiods in theobservationsequencevia the higherlevels ofthehierarchy. We show

how to efﬁciently estimate the model parameters through an estimation scheme inspired

by the inside-outside algorithm. The structure of the model we propose is fairly general

and allows an arbitrary number of activations of its submodels. This estimation procedure

can be efﬁciently approximated so that the overall computation time is only quadratic in

the length of the observations. Thus long time correlations can be captured by the model

while keeping the running time reasonable. We demonstrate the applicability of the model

and its estimation procedure by learning a multi-resolution structure of natural English text.

The resulting models exhibit the formation of “temporal experts” of different time scales,

such as punctuation marks, frequent combinations of letters, and endings of phrases. We

also use the learning algorithm of hierarchical hidden Markov models for unsupervised

learning of repeated strokes that represent combinations of letters in cursive handwriting.

We then use submodels of the resulting HHMMs to spot new occurrences of the same letters

combination in unlabeled data.

The paper is organized as follows: In Section 2 we introduce and describe the hierarchical

hidden Markov model. In Section 3 we derive the estimation procedure for the parameters

of the hierarchical hidden Markov model. In Section 4 we describe and demonstrate two

applications that utilize the model and its estimation scheme. Finally, in Section 5 we

discuss related work, describe several possible generalizations of the model, and conclude.

In order to keep the presentation simple, most of the technical details are deferred to the

technical appendices. A summary of the symbols and variables used in the paper is given

in Appendix C.

2. Model description

Hierarchical hidden Markov models (HHMM) are structured multi-level stochastic pro-

cesses. HHMMs generalize the standard HMMs by making each of the hidden states an

“autonomous” probabilistic model on its own, that is, each state is an HHMM as well.

Therefore, the states of an HHMM emit sequences rather than a single symbol. An HHMM

generates sequences by a recursive activation of one of the substates of a state. This substate

might also be composed of substates and would thus activate one of its substates, etc. This

process of recursive activations ends when we reach a special state which we term a pro-

duction state. The production states are the only states which actually emit output symbols

through the usual HMM state output mechanism: an output symbol emitted in a production

state is chosen according to a probability distributionoverthe set of output symbols. Hidden

states that do not emit observable symbols directly are called internal states. We term the

activation of a substate by an internal state a vertical transition. Upon the completion of

a vertical transition (which may include further vertical transitions to lower level states),

control returns to the state which originated the recursive activation chain. Then, a state

transition within the same level, which we call a horizontal transition, is performed. The

THE HIERARCHICAL HIDDEN MARKOV MODEL 43

set of states and vertical transitions induces a tree structure where the root state is the node

at the top of the hierarchy and the leaves are the production states. To simplify notation we

restrict our analysis to HHMMs with a full underlying tree structure, i.e., all the leaves are

at the same distance from the root state. The analysis of HHMMs with a general structure is

a straightforward generalization of the analysis presented here. The experiments described

in this paper were performed with a general topology.

We would like to note in passing that every HHMM can be represented as a standard

single level HMM. The states of the HMM are the production states of the corresponding

HHMM with a fully connected structure, i.e., there is a non-zero probability of moving from

any of the states to any other state. The equivalent HMM lacks, however, the multi-level

structure which we exploit in the applications described in Section 4.

We now give a formal description of an HHMM. Let Σ be a ﬁnite alphabet. We denote

by Σ

∗

the set of all possible strings over Σ. An observation sequence is a ﬁnite string from

∗

denoted by

O = o

···o

. A state of an HHMM is denoted by q

(d ∈{1,...,D})

where i is the state index and d is the hierarchy index. The hierarchy index of the root is

1 and of the production states is D. The internal states need not have the same number

of substates. We therefore denote the number of substates of an internal state q

by |q

Whenever it is clear from the context, we omit the state index and denote a state at level d

by q

. In addition to its model structure (topology), an HHMM is characterized by the state

transition probability between the internal states and the output distribution vector of the

production states. That is, for each internal state q

(d ∈{1,...,D−1}), there is a state

transition probability matrix denoted by A

=(a

), where a

= P (q

d+1

) is the

probability of making a horizontal transition from the ith state to the jth, both of which are

substates of q

. Similarly, Π

= {π

d+1

)} = {P (q

d+1

)} is the initial distribution

vector over the substates of q

, which is the probability that state q

will initially activate

the state q

d+1

.Ifq

d+1

is in turn an internal state, then π

d+1

) may also be interpreted

as the probability of making a vertical transition: entering substate q

d+1

from its parent

state q

. Each production state q

is solely parameterized by its output probability vector

= {b

(k)}, where b

(k)=P(σ

)is the probability that the production state

will output the symbol σ

∈ Σ. The entire set of parameters is denoted by

λ = {λ

}

d∈{1,...,D}

= {{A

}

d∈{1,...,D−1}

, {Π

}

d∈{1,...,D−1}

, {B

}} .

An illustration of an HHMM with an arbitrary topology and parameters is given in Figure 1.

To summarize, a string is generated by starting from the root state and choosing one of

the root’s substates at random according to Π

. Similarly, for each internal state q that is

entered, one of q’s substates is randomly chosen according to q’s initial probability vector

. The operation proceeds with the chosen substate which recursively activates one of

its substates. These recursive operations are carried out until a production state, q

,is

reached at which point a single symbol is generated according to a state output probability

vector, B

. Then control returns to the state activated q

. Upon the completion of a

recursive string generation, the internal state that started the recursion chooses the next

state in the same level according to the level’s state transition matrix and the newly chosen

state starts a new recursive string generation process. Each level (excluding the top) has

THE HIERARCHICAL HIDDEN MARKOV MODEL 45

Estimating the parameters of a model: Given the structure of an HHMM and one or

more observation sequences {

}, ﬁnd the most probable parameter set λ

of the

model, λ

= arg max

P ({

}|λ).

Solutions for the above problems for HHMMs are more involved than for HMMs, due to

the hierarchical structure and multi-scale properties. For instance, the most probable state

sequence given an observation sequence is a multi-resolution structure of state activations

instead of a simple sequence of indices of the mostly probable states to be reached. We

now present the solutions to these problems, starting with the simplest. We will be using

the following terminology: we say that state q

started its operation at time t if the (pos-

sibly empty) sub-sequence o

···o

t−1

was generated before q

was activated by its parent

state, and the symbol o

was generated by one of the production states reached from q

Analogously, we say that state q

ﬁnished its operation at time t if o

was the last symbol

generated by any of the production states reached from q

, and control was returned to q

from q

d+1

end

3.1. Calculating the likelihood of a sequence

Since each of the internal states of an HHMM can be viewed as an autonomous model

which can generate a substring of the observation using its substates, an efﬁcient likelihood

evaluation procedure should be recursive. For each state q

we calculate the likelihood

of generating a substring ω, denoted by P (ω|λ, q

). Assume for the moment that these

probabilities are provided except for the the root state q

. Let

i =(i

,...,i

) be the

indices of the states at the second level that were visited during the generation of the

observation sequence

O = o

,...,o

of length T . Note that the last state entered

at the second level is q

end

, thus q

= q

end

. Let τ

be the temporal position of the

ﬁrst symbol generated by state q

, and let the entire list of these indices be denoted by

¯τ =(τ

,τ

,...,τ

). Since q

was activated by q

at the ﬁrst time step and q

end

was

the last state from the second level that was activated, we have τ

=1and τ

= T . The

likelihood of the entire sequence given the above information is,

P (

O|¯τ,

i, λ)=

)P(o

···o

−1

,λ)a

P(o

···o

−1

,λ)a

···P(o

l−2

···o

l−1

−1

l−2

,λ)a

l−2

l−1

P(o

l−1

···o

l−1

,λ)a

l−1

end

In order tocalculatetheunconditionedlikelihood we need tosumoverallpossible switching

times τ and state indices I. Clearly this is not feasible since there are exponentially many

such combinations. Fortunately, the structure of HHMMs enables us to use dynamic pro-

gramming to devise a generalized version of the Baum-Welch algorithm. The generalized

forward probabilities, α(·), are deﬁned to be

α(t, t + k, q

d−1

)=P(o

···o

t+k

ﬁnished at t + k | q

d−1

started at t) .

That is, α(t, t + k, q

d−1

) is the probability that the partial observation sequence

···o

t+k

was generated by state q

d−1

and that q

was the last state activated by q

d−1

剩余21页未读，继续阅读

紫潇芷清

2013-09-15

是一篇关于隐马尔科夫模型的英文文献

nicolas_7608

粉丝: 0
资源: 2

会员权益专享

隐马尔科夫模型的分析和应用

评论8

会员权益专享

最新资源

隐马尔科夫模型的分析和应用

评论8

隐马尔科夫模型Python实现

隐马尔可夫matlab源码

隐马尔科夫模型.pdf

隐马尔科夫模型在语音识别上的应用

用学术语言解释一下隐马尔科夫模型

r语言 hmm隐马尔科夫链

马尔科夫链预测matlab

马尔科夫时间序列预测

基于隐马尔科夫链搭建sinsy歌声合成系统

nlp算法的机器学习模型

条件随机场入门(一) 概率无向图模型_人工智能_清晨随笔-csdn博客

一般中文分词采用什么方法

probability and computing中文版

gsoc17-hhmm：贝叶斯分层隐马尔可夫模型应用于金融时间序列，这是Google Summer of Code 2017的研究复制项目

隐马尔科夫模型HMM的介绍以及应用

马尔可夫及隐马尔可夫模型的应用

应用优化的隐马尔可夫模型预测蛋白质结构类

隐马尔可夫模型的简介以及实例介绍以及三个主要算法

隐马尔可夫

隐马尔科夫模型及其在自然语言处理中的应用

会员权益专享

最新资源