An EM Algorithm for Asynchronous Input/Output Hidden Markov Models
An EM Algorithm for Asynchronous Input/Output Hidden Markov Models
复制标题
异步输入/输出隐马尔可夫模型的EM算法
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
Yoshua Bengio
中科院分区：
文献类型：
--
作者：
Samy Bengio;Yoshua Bengio
在输入序列映射到输出序列的学习任务中，输入和输出序列通常是不同步的。例如，在语音识别中，声学序列比音素序列长。输入输出隐马尔可夫模型已经被提出来表示给定相同长度的输入序列的输出序列的分布。我们在这里将该模型扩展到异步序列的情况，并显示期望最大化序列数据的监督学习算法最小化依赖于输入和输出序列对的训练准则通常假设输入和输出序列是同步的，即每个输入序列与相应的输出序列具有相同的长度。例如，循环网络Rumelhart等人可以用来将输入序列映射到输出序列，例如在每个时间步上最小化di的平方另一个例子是最近提出的专家连接主义结构的循环混合，它被解释为一个概率模型，称为输入输出隐马尔可夫模型IOHMM Bengio和Frasconi Bengio和Frasconi。该模型表示了当给定相同长度的输入序列时，使用隐马尔可夫模型中的隐藏状态变量和马尔可夫独立性假设，输出序列的分布摘要Levinson et al拉宾为了简化IOHMMs是一种概率分布传感器佩雷拉等歌手与输入和输出变量可以是离散和连续价值然而在许多顺序问题,试图将输入序列映射到一个输出序列输入和输出序列的长度可能不等于输入和输出序列可以在不同时间尺度的行为例如在一个语音识别的问题想要将声信号映射到音素序列，每个音素大约对应于声信号的子序列，因此输入声序列通常比输出音素序列长，并且输入和输出之间的对齐通常不可用。与hmm相比，iohmm中的发射和转移概率随输入序列的时间而变化转移概率和发射概率通常更好地匹配，这减少了语音识别hmm中观察到的一个问题，因为输出比hmm中的转移在更高的维度空间中，转移概率的动态范围远小于发射概率的动态范围，因此识别过程中不同路径之间的选择主要受发射而不是转移概率的影响对于复杂的分布，例如使用人工神经网络来表示转移和发射分布，可以使用广义的EM算法或似然梯度上升算法。最后，我们提出了一种类似于Viterbi算法的识别算法，将给定的输入序列映射到可能的输出序列输入序列u u uT同样y S输出序列y y y在本文中,我们考虑的情况下输出比输入序列短序列的更一般的情况下是一个简单的扩展这个模型使用空不花任何时间的转换,将讨论在摘要和其他地方IOHMMs我们引入一个离散的隐藏状态变量xt将允许我们简化分布P y ju T使用马尔可夫链的独立性假设状态序列x是与输入序列同步u以生成输出比输入序列短序列我们会状态不发出一个输出以及国家在时间t时,发出一个输出系统处于一个非发射状态没有产生输出可以因此存在许多序列的状态对应于不同短长度输出序列时构思的生成模型输出给定输入异步IOHMM作品在时间t一个初始状态如下x是选择根据x和输出序列的长度分布P s在其他时间初始化步骤t州xt rst选择根据分布P xtjxt ut使用状态转换在前面的时间步xt和当前输入ut如果xt是一个发射状态然后输出序列的长度增加,年代和某事输出y从排放采样分布P ysjxt ut的参数因此模型初始状态概率我px和输出和转换条件分布模型的参数P ysjxt ut和P xtjxt ut自不同长度的输入和输出序列是我们将介绍另一个隐藏变量t speci卡莉代表输入和输出之间的对齐和t意味着年代输出已经发出在时间t让我们rst形式化独立假设和条件分布的形式代表憎恨的模型条件概率P y ju T可以写成求和的条款P y x T T T /所有可能的状态序列x,这样发射状态的数量在每一个序列S输出序列的长度P y ju T x x T S P y x T T居所有S输出一定是发出的时间T T S隐藏状态xt离散值一套夜间每一项P y x T T ju对应于一个特定的状态和相应的序列对齐这个概率可以写成初始状态概率P x乘以产品因素/ xt步骤t如果状态我是一个发射状态因素是P xtjxt ut ysjxt ut否则因素只是P xtjxt ut, s是输出的输出序列中位置排放在时间t输出发射时间t时我们总结表的符号和德不附加符号用于介绍了论文中使用的符号表年代大小输出序列的T输入序列的大小N的州数目IOHMM我j T模块的输出计算P xt ijxt j b ut i S T模块的输出计算P ysjxt我ut x我初始的概率状态子T如果xt子了,否则这些指标变量给状态序列T女士如果系统发出S女士th输出在时间T T否则这些指标变量为输入输出校准ei是真的如果状态我发出P ei是错误的否则t意味着rst年代rst输出已经发出在时间t t k如果t th输入符号是k t k否则k如果年代th输出符号是k s k否则pred我所有的前任州州我succ是所有我的继任者的状态马尔可夫链的条件独立性假设在这个模型意味着状态变量序列的xt总结苏地过去P xtjx t u t P xtjxt ut和P ysjx t u P ysjxt ut假设是类似于用于摘要和马尔可夫过程的独立性假设是一样的在同步IOHMMs根据这两个假设条件概率可以e地表示和计算递归地使用一个中间变量i s t def P xt我t s y s ju t输出序列的条件概率可以表示这个变量的L def P y ju t X
In learning tasks in which input sequences are mapped to output sequences it is often the case that the input and output sequences are not synchronous For example in speech recognition acoustic sequences are longer than phoneme sequences Input Output Hidden Markov Models have already been proposed to represent the distribution of an output sequence given an input sequence of the same length We extend here this model to the case of asynchronous sequences and show an Expectation Maximization algorithm for training such models Introduction Supervised learning algorithms for sequential data minimize a training criterion that depends on pairs of input and output sequences It is often assumed that input and output sequences are synchronized i e that each input sequence has the same length as the corresponding output sequence For instance recurrent networks Rumelhart et al can be used to map input sequences to output sequences for example minimizing at each time step the squared di erence between the actual output and the desired output Another example is a recently proposed recurrent mixture of experts connectionist ar chitecture which has an interpretation as a probabilistic model called Input Output Hidden Markov Model IOHMM Bengio and Frasconi Bengio and Frasconi This model represents the distribution of an output sequence when given an input sequence of the same length using a hidden state variable and a Markovian independence assumption as in Hidden Markov Models HMMs Levinson et al Rabiner in order to simplify the distribution IOHMMs are a form of probabilistic transducers Pereira et al Singer with input and output variables which can be discrete as well as continuous valued However in many sequential problems where one tries to map an input sequence to an output sequence the length of the input and output sequences may not be equal Input and output sequences could behave at di erent time scales For example in a speech recognition problem where one wants to map an acoustic signal to a phoneme sequence each phoneme approximately corresponds to a subsequence of the acoustic signal therefore the input acoustic sequence is generally longer than the output phoneme sequence and the alignment between inputs and outputs is often not available In comparison with HMMs emission and transition probabilities in IOHMMs vary with time in function of an input sequence Unlike HMMs IOHMMs with discrete outputs are discriminant models Furthermore the transition probabilities and emission probabilities are generally better matched which reduces a problem observed in speech recognition HMMs because outputs are in a much higher dimensional space than transitions in HMMs the dynamic range of transition probabilities is much less than that of emission probabilities Therefore the choice between di erent paths during recognition is mostly in uenced by emission rather than transition probabilities In this paper we present an extension of IOHMMs to the asynchronous case We rst present the proba bilistic model then derive an exact Expectation Maximization EM algorithm for training asynchronous IOHMMs For complex distributions e g using arti cial neural networks to represent transition and emission distributions a Generalized EM algorithm or gradient ascent in likelihood can be used Finally a recognition algorithm similar to the Viterbi algorithm is presented to map given input sequences to likely output sequences The Model Let us note u for input sequences u u uT and similarly y S for output sequences y y yS In this paper we consider the case in which the output sequences are shorter than the input sequences The more general case is a straightforward extension of this model using empty transitions that do not take any time and will be discussed elsewhere As in HMMs and IOHMMs we introduce a discrete hidden state variable xt which will allow us to simplify the distribution P y ju T by using Markovian independence assumptions The state sequence x is taken to be synchronous with the input sequence u In order to produce output sequences shorter than input sequences we will have states that do not emit an output as well as states that do emit an output When at time t the system is in a non emitting state no output can be produced Therefore there exists many sequences of states corresponding to di erent shorter length output sequences When conceived as a generative model of the output given the input an asynchronous IOHMM works as follows At time t an initial state x is chosen according to the distribution P x and the length of the output sequence s is initialized to At other time steps t a state xt is rst picked according to the transition distribution P xtjxt ut using the state at the previous time step xt and the current input ut If xt is an emitting state then the length of the output sequence is increased from s to s and the sth output ys is sampled from the emission distribution P ysjxt ut The parameters of the model are thus the initial state probabilities i P x i and the parameters of the output and transition conditional distribution models P ysjxt ut and P xtjxt ut Since the input and output sequences are of di erent lengths we will introduce another hidden variable t speci cally to represent the alignment between inputs and outputs with t s meaning that s outputs have been emitted at time t Let us rst formalize the independence assumptions and the form of the conditional distribution rep resented by the model The conditional probability P y ju T can be written as a sum of terms P y x T T ju T over all possible state sequences x T such that the number of emitting states in each of these sequences is S the length of the output sequence P y ju T X x T S P y x T T ju T All S outputs must have been emitted by time T so T S The hidden state xt takes discrete values in a nite set Each of the terms P y x T T ju T corresponds to a particular sequence of states and a corresponding alignment this probability can be written as the initial state probabilities P x times a product of factors over all the time steps t if state xt i is an emitting state that factor is P xtjxt ut P ysjxt ut otherwise that factor is simply P xtjxt ut where s is the position in the output sequence of the output emitted at time t when an output is emitted at time t We summarize in table the notation we have introduced and de ne additional notation used in this paper Table Notation used in the paper S size of the output sequence T size of the input sequence N number of states in the IOHMM a i j t output of the module that computes P xt ijxt j ut b i s t output of the module that computes P ysjxt i ut i P x i initial probability of state i zi t if xt i zi t otherwise These indicator variables give the state sequence ms t if the system emits the s th output at time t ms t otherwise These indicator variables give the input output alignment ei is true if state i emits so P ei ei is false otherwise t s means that the rst s rst outputs have been emitted at time t t k if the t th input symbol is k t k otherwise s k if the s th output symbol is k s k otherwise pred i is the set of all the predecessors states of state i succ i is the set of all the successors states of state i The Markovian conditional independence assumptions in this model mean that the state variable xt summarizes su ciently the past of the sequence so P xtjx t u t P xtjxt ut and P ysjx t u t P ysjxt ut These assumptions are analogous to the Markovian independence assumptions used in HMMs and are the same as in synchronous IOHMMs Based on these two assumptions the conditional probability can be e ciently represented and computed recursively using an intermediate variable i s t def P xt i t s y s ju t The conditional probability of an output sequence can be expressed in terms of this variable L def P y ju T X