DE19934845A1 - On-line estimating of Hidden-Markov model, calculating parameters of model from auxiliary sizes with at least three indices, and not through elements of time series directly - Google Patents

Abstract

The Hidden-Markov model is estimated from a time series of input- and/or output values, whereby parameters are determined from one or several auxiliary sizes with at least three indices, not however through elements of the time series directly. The auxiliary sizes are calculated after an initialisation through repeated iterative application of a function involving a multi-dimensional real vector, whose elements are calculated either as a sum of certain elements of the auxiliary sizes, or through an iterative function. The method involves estimating a Hidden-Markov model from a time series of input- and/or output values, whereby parameters of the model are determined from one or several auxiliary sizes with at least three indices, and perhaps other sizes, not however through elements of the time series directly. The auxiliary sizes are calculated after an initialisation through repeated iterative application of a function of time, the input- and/or output values, and an multi-dimensional real vector, whose elements are calculated either as a sum of certain elements of the auxiliary sizes, or according to an initialisation through an iterative function.

Description

The invention is a method for estimating hidden Markov models (HMM) with low memory requirements and for online estimation of hidden Markov models from a one- or multi-dimensional, time-discrete series of Input-output value pairs. According to de initialization, an operator is used for each time step. Output value pair and the current estimate of the machine depends. With the on- line guessing is done regularly, e.g. B. for each time step, one from the auxiliary variable new current estimate of the machine calculated after learning off-line iterated over all elements of the time series.

1. Technical field

In the analysis of time series. e.g. B. in speech and font recognition, the Process monitoring and control; Hidden Markov models become successful applied. The models must be estimated using sample time series.

2. State of the art

To estimate hidden Markov models from time series are mostly Maximum likelihood estimator related. The parameters of a model are chosen so that the probability that the sample time series from the HMM be generated if the model is true, maximum. For time series fe The Baum-Welch algorithm is usually used for the longest lengths [room 66]. He however requires storage space that is proportional to the total length of the time series hen × number of states of the HMM is large. No time series are fixed Lengths ahead, but a process that generates time series, so the output must time series of the process artificially divided into time series of finite length the. This can be avoided using online algorithms. A generic one Algorithm [Titterington 84] for the online estimation of stochastic models subsequently an algorithm for hidden Markov processes [Krishnamurthy 84]  developed. Other algorithms that are not the likelihood of the machine maximize [Collins 93] were developed. In none of the publications known to us A method is specified in which the model parameters are derived from one or several auxiliary size (s) with at least 3 indices and possibly others Quantities are calculated, and the auxiliary quantities are calculated iteratively so that no parts of the time series need to be saved.

3. Underlying problem

The invention relates to a method and a device for estimating hidden Markov models with a low memory requirement and for on-line estimating of hidden Markov models and stochastic automatons from time-discrete time series of output symbols or input-output symbol pairs. In the following, both model types are referred to as hidden Markov models. We also use the term "symbol" to refer to symbols in the narrower sense, as well as numbers or numerical values. At E any deterministic or stochastic process, which at any time t ∈ 0, 1, ... generates a symbol x (t) ∈ U from a finite set U, which is an input for the hidden Markov model . At M an ergodic hidden Markov process with S internal states. At any point in time, it changes from an internal state i ∈ S to an internal state j ∈ S with the probability a _ij (x (t)). An output symbol y ∈ V is output, where V is any quantity. The probability or density of probability with non-finite thickness of V to output the output symbol y at the transition from i to j, if the input symbol bol x was received p _ij (y | x), is from the input symbol x, from the output symbol y, from i and j and dependent on a finite number of internal parameters v. At time 0, the probability of being in state i is π 0 | i. For the special case of finite sets of input symbols and output values, the p _ij (y | x) are themselves the internal parameters. The aim is to estimate the hidden Markov model from a series of input-output pairs of fixed length, or from a process that generates input-output pairs, ie to determine the internal parameters v.

4. Invention

In the following, only the case of a hidden Markov model with a finite number of input and output symbols is considered. This case contains all the essential procedural steps. In a hidden Markov model, in which U and V are finite sets, integers between 1 and | U | without restriction of generality or | V |, where |. | denote the thickness of the respective set, the parameters of the model are the conditional transition probabilities p _{i, j} (y | x), i, j ∈ S, y ∈ U and x ∈ V and the start vector π 0 | i.

The parameters are iteratively estimated from an auxiliary variable NT | i, j, k (y | x), i, j ∈ S, x ∈ U and y ∈ V, which are derived from a time series of input and output symbols (x (t ), y (t)), t = 1 ... T are calculated recursively, starting from a first, possibly random estimate p _{i, j} (y | x) and π 0 | i.

An alternative calculation method (with the same result) is the iteration of the π ^{τ in} addition to the N-tensors, so that π ^{τ is} calculated as instead of from equation 3

The new estimate of the parameters (marked with an overline) is

The new estimate of the starting vector is

These calculations according to Eq. (2) - (6) are repeated until an abort criterion is met. e.g. B. max _{i, j, y, x} (p _{i, j} (y | x) - p _{i, j} (y | x)) ² <d with suitably chosen d <0.

This method for memory-efficient estimation of HMM from a time series can be modified to a method for on-line estimation of HMM. It is regularly, for. B. after each receipt of an input-output value pair, the current estimate of p is changed according to equations 2 and 3. This results in the following procedural steps:

• 1. select (y | x).  
• 2. choose stochastic vector π ⁰ .
• 3. set τ = 0.
• 4. new guess p _{i, j} (y | x):
  
• 5. compute π τ | i: = ∈ (τ) Σ _{i, j∈S} Σ _x∈U Σ _y∈V N τ | i, j, k (y | x)
• 6. compute N τ + 1 | i, j, k (y | x) according to equation 2.
• 7. τ → τ + 1.
• 8. go to 4.

Here ∈ (τ) denotes any real-valued function with 0 ≦ ∈ (τ), which can be interpreted as a learning rate and on which the convergence of the model parameters and their fluctuations depend. An example of choosing ∈ (τ) is ∈ (τ) = 1 / τ. By choosing a constant learning rate ∈ (τ) = ∈∀ _t , an exponentially decaying dependency of the model parameters on past input-output value pairs can be realized.

To avoid numerical problems, one can step after step 6

• 6a. multiply all N τ + 1 | i, j, k (y | x) by 1 / Σ _i∈S π τ | i

insert because N ^τ

and π ^τ

are determined only down to a common factor. (see equation 7).

Alternatively, step 5 can be replaced by:

• V. calculate π τ | i: = ∈ (τ) Σ _j∈S a _{i, j} (y (τ) | x (τ)) π τ-1 | j.

Then instead of step 6a. be carried out:

• Via. multiply all N τ + 1 | i, j, k (y | x) and π τ | i by 1 / Σ _i∈S π τ | i.

This method can also be used for other types of HMM, e.g. B. Hidden Markov models with Gaussian output probability and without ne input symbols. This is shown below. For hidden Markov models with Gaussian output probability and without input symbols, the conditional probability is to output the value y at time t and to go to state j if the model is in state i

The parameters of the model are α _ij , µ _i and σ 2 | i. They can be calculated from the following auxiliary variables: N τ | i, j, k, M τ | i, k (y) and S τ | i, k (y), which in turn are calculated iteratively after initialization:

The new estimates of the parameters of the HMM (marked by an overline) are calculated as

Otherwise, the procedure is analogous to that described above.

This procedure can be varied in the calculations described above only for some of the parameters, e.g. B. the transition probabilities other parameters are estimated using other methods. Wei Furthermore, the procedure can be modified by adding all or some sizes can only be calculated approximately.  

5. Industrial applicability

The specified methods can be used for all uses in which hidden Marlov models from a time series are estimated to be used.

6. Beneficial effects

The method for off-line estimation is characterized in that in the opposite independent of the usual forward-backward procedure on the length of the time series, and therefore essential for typical applications is lower, whereas in the forward-backward procedure which has been customary to date, Memory requirement is proportional to the length of the time series. The online procedure is characterized in that the elements of the time series, based on them the model is to be estimated, does not need to be saved. this makes possible the implementation of the process using integrated electronic components (IC's) that have little memory, e.g. B. using only one chip. Help The on-line method is the determination of complex sizes, the model parameter ter from simple measured values. e.g. B. for process monitoring at any time possible.

7. Description of the figures

Figure No. 1: Any autonomous deterministic or stochastic pro zeß E generates symbol chains x, which represent the input of the HMM. The Hidden Markov process HMM with internal parameters v is dependent from the input symbol x received to a new state and gives egg ne output value y. The observer observes the input symbol x and the Output value y, but not the internal states and the internal parameters of the machine.

Figure No. 2: A hidden Markov process, here as an example with 3 states and a finite set of output symbols V, is shown. Upon receipt of an input symbol, the process changes from its current state i to a new state j and outputs an output value y ∈ V with probability p _{i, j} (y | x).

literature

[Titterington 84] DM Titterington. Recursive parameter estimation using in complete data. JR Statist. Soc. B 46, 257 (1984).
[Krishnamurthy 84] V. Krishnamurthy, JB Moore. On-line estimation of Hid den Makov Model parameters based on the Kullback-Leibler information measure. IEEE. Transact. on signal. Proc 41, 2557 (1993).
[Collins 93] IB Collins, V. Krishnamurthy, JB Moore. On-line estimation of hidden Makov models via recursive prediction error techniques. IEEE. Transacton signal. Proc 41, 2557 (1993). [Tree 66] LE Tree. T. Petrie. Ann. Math. Statist. 30, 1 554 (1966).
[Stiller 98) JC Stiller. Hidden Markov Models: Unsupervised Learning and Classification. Diss., Univ. Kiel (1998).

Claims (13)

1. A method for estimating hidden Markov models with low memory requirements and for on-line estimating hidden Markov models from a time series of input and output values or from output values, characterized in that parameters v of the model from a or more auxiliary variables (n) N ^l (y | x) and possibly other variables with at least 3 indices, but not directly from elements of the time series, and the auxiliary variables are calculated after an initialization by repeated iterative application of a function G ^l are expressed as N ^{l; t + 1} (y | x): = G ^l (N ^{l; t} (y | x), x (t + 1), y (t + 1), t, π ^τ , v), where N ^{l; t} denotes the lth auxiliary variable belonging to time t, x (t) the input value belonging to time t and y (t) the output value belonging to time t, π ^t denotes an s-dimensional real vector, the elements of which either calculated as a sum over certain elements of the auxiliary variables N ^{l; t} , or after an initialization by iterative repeated t times Application of a function B are calculated as π ^{t + 1} = B (π ^t , x (t + 1), y (t + 1), v), where s is the number of states of the hidden Markov model. 2. The method according to claim 1, characterized in that π t + 1 | j = Σ s | i∈S π t | ip _{i, j} (y (t + 1) | x (t + 1); v) / C (π ^t ) applies, where C is a real function, π t | j the jth coordinate of the vector π after t iterations, v the current estimate of the parameters of the model and p _{i, j} (y | x; v) the probability of the model transitioning to state j and outputting the output value y when the model is in state i, the input symbol is x and the parameters are v. 3. The method according to at least one of claims 1-2, characterized in that π t + 1 | j = Σ s | i∈S π t | ip _{i, j} (y (t + 1) | x (t + 1 ); v) / (Σ _i∈S Σ s | j∈S π t | ip _{i, j} (y (t + 1) | x (t + 1); v) applies. 4. The method according to at least one of claims 1-3, characterized in. that for π ^t and at least one of the auxiliary quantities N ^l : π τ + 1 | i: = ∈ (τ) Σ _{i, j∈S} Σ _x∈U Σ _y∈V N l, τ | i, j, k ( y | x) at ∈ (τ) is any real-valued function with. 5. The method according to claim 4, characterized in that ∈ (τ) = 1 / τ. 6. The method according to claim 4, characterized in that ∈ (t) = ∈ applies to all t <t _c , where ∈ is an arbitrary, non-negative real number and t _{c is} an arbitrary, non-negative integer. 7. The method according to at least one of claims 1-5, characterized indicates that the value range of the input symbols has the thickness 1.   8. The method according to at least one of claims 1-7, characterized indicates that the range of values of the output symbols is a finite set is. 9. The method according to at least one of claims 1-7, characterized in that for at least one of the auxiliary variables N ^l : N l; τ + 1 | i, j, k (y | x) = h _{i, j, k} ( (y | x) (x (τ + 1) | y (τ + 1)), t) + g _{i, j, k} (π τ | i δ _{y, y (τ + 1)} δ _{x, x (τ +1)} p _{i, j} (x | y) δ _{j, k,} t) where h _{i, j, k} and g _{i, j, k} for all i, j, k arbitrarily reelwertige functions. 10. The method according to at least one of claims 1-9, characterized in that the following applies to at least one of the auxiliary variables N ^l : N l; τ + 1 | i, j, k (y | x) = ((y | x) (y (τ + 1) | x (τ + 1)), t) + ∈ (τ) δ _{y, y (τ + 1)} δ _{x, x (τ + 1)} p τ | i, j (y | x) δ _{j, k} Σ _{l, m∈S} Σ _x∈U Σ _y∈V N l; τ | l, m, i (y | x), where ∈ (τ) is an arbitrary real function. 11. The method according to claim 10, characterized in that ∈ (t) = ∈ applies to all t <t _c , where ∈ is an arbitrary, non-negative real number and t _{c is} an arbitrary, non-negative integer. 12. The method according to at least one of claims 1-11, characterized ge indicates that parameters of the hidden Markov process a priori Information is available so that the calculations are simplified can. 13. Device, characterized in that it has at least one of the procedural uses ren according to claims 1-12 in a digital or analog manner.