DE19934845A1

DE19934845A1 - Verfahren zum Schätzen von Hidden-Markov-Modellen mit geringem Speicherbedarf und zum on-line-Schätzen von Hidden-Markov-Modellen

Info

Publication number: DE19934845A1
Application number: DE19934845A
Authority: DE
Inventors: Jan Christopher Stiller; Guenter Radons
Original assignee: Individual
Current assignee: Individual
Priority date: 1998-07-25
Filing date: 1999-07-24
Publication date: 2000-03-16

Abstract

Verfahren zum Schätzen von Hidden-Markov-Modellen mit geringem Speicherbedarf und zum on-line-Schätzen von Hidden-Markov-Modellen. Es wird ein Verfahren zum Schätzen von Hidden-Markov-Modellen mit geringem Speicherbedarf und zum on-line-Schätzen von Hidden-Markov-Modellen angegeben, bei dem mindestens eine mit mindestens 3 Indizes behafteten Hilfsgröße(n) in Abhängigkeit von dem letzten Ein-Ausgabewertpaar iteriert wird, aus der (bzw. denen) aktuelle Schätzungen der Modellparameter berechnet werden können, so dass beim on-line-Schätzen kein Teil der Zeitreihe gespeichert werden muss, und der Speicherbedarf nicht von der Länge der Zeitreihe abhängt und somit meist wesentlich geringer als bei anderen Verfahren ist. Das Verfahren ist allgemein zum Schätzen von Hidden-Markov-Modellen aus Zeitreihen oder aus Prozessen, die Zeitreihen generieren, geeignet. Die Vorteile dieses Verfahrens wirken sich insbesondere bei langen Zeitreihen oder langandauernden Prozessen oder bei beschränkter Speicherkapazität positiv aus.

Description

Die Erfindung ist ein Verfahren zum Schätzen von Hidden-Markov-Modellen (HMM) mit geringem Speicherbedarf und zum on-line-Schätzen von Hidden- Markov-Modellen aus einer ein- oder mehrdimensionalen zeitdiskreten Reihe von Ein-Ausgabewertpaaren. Auf eine mehrdimensionale Hilfsgröße wird nach de ren Initialisierung für jeden Zeitschritt ein Operator angewandt, der vom Ein- Ausgabewertpaar und der aktuellen Schätzung des Automaten abhängt. Beim on- line-Schätzen wird regelmäßig, z. B. zu jedem Zeitschritt, aus der Hilfsgröße eine neue aktuelle Schätzung des Automaten berechnet, beim off-line-Lernen nachdem über alle Elemente der Zeitreihe iteriert wurde.

1. Technisches Gebiet

In der Analyse von Zeitreihen. z. B. in der Sprach- und Schrifterkennung, der Prozeßüberwachung und -kontrolle; werden Hidden-Markov-Modelle erfolgreich angewandt. Die Modelle müssen anhand von Beispielzeitreihen geschätzt werden.

2. Stand der Technik

Zum Schätzen von Hidden-Markov-Modellen aus Zeitreihen werden meist Maximum-Likelihood-Schätzer verwandt. Die Parameter eines Modells werden so gewählt, daß die Wahrscheinlichkeit, daß die Beispielzeitreihen von dem HMM generiert werden, wenn das Modell wahr ist, maximal werden. Bei Zeitreihen fe ster Längen wird meist der Baum-Welch-Algorithmus angewandt [Raum 66]. Er benötigt jedoch Speicherplatz, der proportional der Gesamtlängen der Zeitrei hen × Anzahl der Zustände des HMMs groß ist. Liegen keine Zeitreihen fester Längen vor, sondern ein Prozeß, der Zeitreihen generiert, so muß die Ausgabe zeitreihe des Prozesses künstlich in Zeitreihen endlicher Länge aufgeteilt wer den. Mittels on-line-Algorithmen läßt sich dies vermeiden. Einem generischen Algorithmus [Titterington 84] für die on-line-Schätzung stochastischer Modelle folgend wurde ein Algorithmus für Hidden-Markov-Prozesse [Krishnamurthy 84] entwickelt. Auch andere Algorithmen, die nicht die Likelihood des Automaten maximieren [Collins 93], wurden entwickelt. In keiner uns bekannten Veröffentli chung ist ein Verfahren angegeben, bei dem die Modellparameter aus einer oder mehreren mit mindestens 3 Indizes behafteten Hilfgröße(n) und evtl. anderer Größen berechnet werden, und die Hilfgrößen iterativ berechnet werden, so daß keine Teile der Zeitreihe gespeichert werden müssen.

3. Zugrundeliegendes Problem

Die Erfindung betrifft ein Verfahren sowie eine Einrichtung zum Schätzen von Hidden-Markov-Modellen mit geringem Speicherbedarf und zum on-line-Schätzen von Hidden-Markov-Modellen und stochastischen Automaten aus zeitdiskreten Zeitreihen von Ausgabesymbolen bzw. Ein-Ausgabesymbolpaaren. Im Folgenden werden beide Modelltypen als Hidden-Markov-Modelle bezeichnet. Ferner benen nen wir mit dem Begriff "Symbol" sowohl Symbole im engeren Sinne, als auch Zahlen oder numerische Werte. Bei E ein beliebiger deterministischer oder stocha stischer Prozeß, der zu jedem Zeitpunkt t ∈ 0, 1, ... ein Symbol x(t) ∈ U aus einer endlichen Menge U erzeugt, das eine Eingabe für das Hidden-Markov-Modell dar stellt. Bei M ein ergodischer Hidden-Markov-Prozeß mit S internen Zuständen. Zu jedem Zeitpunkt geht er von einem internen Zustand i ∈ S zu einem internen Zustand j ∈ S mit der Wahrscheinlichkeit a_ij (x(t)) über. Dabei wird ein Ausgabe symbol y ∈ V ausgegeben, wobei V eine beliebige Menge ist. Die Wahrscheinlich keit bzw. Wahrscheinlichkeitsdichte bei nicht endlicher Mächtigkeit von V, beim Übergang von i nach j das Ausgabesymbol y auszugeben, wenn das Eingabesym bol x empfangen wurde p_ij(y|x), ist vom Eingabesymbol x, vom Ausgabesymbol y, von i und j und von endlich vielen internen Parametern v abhängig. Zum Zeit punkt 0 ist die Wahrscheinlichkeit, im Zustand i zu sein, π 0|i. Für den Spezialfall endlicher Mengen der Eingabesymbole und Ausgabewerte sind die p_ij(y|x) selbst die internen Parameter. Ziel ist es, aus einer Reihe von Eingabe-Ausgabe-Paaren fester Länge, oder aus einem Prozeß, der Eingabe-Ausgabe-Paare generiert, das Hidden-Markov-Modell zu schätzen, d. h. die internen Parameter v zu bestimmen.

4. Erfindung

Im Folgenden wird zunächst nur der Fall eines Hidden-Markov-Modells mit end lich vielen Eingabe- und Ausgabesymbolen betrachtet. Dieser Fall enthält al le wesentlichen Verfahrensschritte. Bei einem Hidden-Markov-Modell, bei dem U und V endliche Mengen sind, ohne Einschränkung der Allgemeinheit ganze Zahlen zwischen 1 und |U| bzw. |V|, wobei |.| die Mächtigkeit der jeweiligen Menge bezeichne, sind die Parameter des Modells die bedingten Übergangswahr scheinlichkeiten p_i,j(y|x), i,j ∈ S, y ∈ U und x ∈ V und der Startvektor π 0|i.

Die Parameter werden iterativ aus einer Hilfgröße N T|i,j,k(y|x), i,j ∈ S, x ∈ U und y ∈ V, geschätzt, die aus einer Zeitreihe von Eingabe- und Ausgabesym bolen (x(t), y(t)), t = 1...T rekursiv berechnet werden, wobei von einer ersten, evtl. zufälligen Schätzung p_i,j(y|x) und π 0|i ausgegangen wird.

Eine alternative Berechnungsweise (mit demselben Ergebnis) ist die Iteration der π^τ zusätzlich zu den N-Tensoren, so daß π^τ statt aus Gleichung 3 berechnet wird als

Die neue Schätzung der Parameter (durch Überstrich gekennzeichnet) ist

Die neue Schätzung des Startvektors ist

Diese Berechnungen nach Gl. (2)-(6) werden solange wiederholt, bis ein Ab bruchkriterium erfüllt wird. z. B. max_i,j,y,x(p_i,j(y|x) - p_i,j(y|x))² < d mit geeignet gewähltem d < 0.

Dieses Verfahren zum speichereffizienten Schätzen von HMM aus einer Zeitreihe kann modifiziert werden zu einem Verfahren zum on-line-Schätzen von HMM. Dabei wird regelmäßig, z. B. nach jedem Empfang eines Ein-Ausgabewertpaares, die aktuelle Schätzung von p gemäß den Gleichungen 2 und 3 geändert. Dies ergibt im einzelnen folgende Verfahrensschritte:

1. wähle (y|x).
2. wähle stochastischen Vektor π⁰.
3. setze τ = 0.
4. schätze p_i,j(y|x) neu:
5. berechne π τ|i: = ∈(τ) Σ_i,j∈S Σ_x∈UΣ_y∈VN τ|i,j,k (y|x)
6. berechne N τ+1|i,j,k(y|x) gemäß Gleichung 2.
7. τ → τ + 1.
8. gehe zu 4.

Dabei bezeichnet ∈(τ) eine beliebige reellwertige Funktion mit 0 ≦ ∈(τ), die sich als Lernrate interpretieren läßt und von der die Konvergenz der Modellparame ter und ihre Fluktuationen abhängen. Ein Beispiel für die Wahl von ∈(τ) ist ∈(τ) = 1/τ. Durch Wahl einer konstanten Lernrate ∈(τ) = ∈∀_t läßt sich eine exponentiell abklingende Abhängigkeit der Modellparameter von zeitlich zurück liegenden Eingabewert-Ausgabewert-Paaren realisieren.

Um numerische Probleme zu vermeiden, kann man nach Schritt 6 Schritt

6a. multipliziere alle N τ+1|i,j,k(y|x) mit 1/Σ_i∈Sπ τ|i

einfügen, da N^τ

und π^τ

nur bis auf einen gemeinsamen Faktor bestimmt sind. (siehe Gleichung 7).

Alternativ kann Schritt 5 ersetzt werden durch:

V. berechne π τ|i: = ∈(τ) Σ_j∈S a_i,j(y(τ)|x(τ))π τ-1|j.

Dann muss statt Schritt 6a. ausgeführt werden:

VIa. multipliziere alle N τ+1|i,j,k(y|x) und π τ|i mit 1/Σ_i∈Sπ τ|i.

Dieses Verfahren kann auch für andere Typen von HMM verwandt werden, z. B. Hidden-Markov-Modelle mit Gauß'scher Ausgabewahrscheinlichkeit und oh ne Eingabesymbole. Dies wird im Folgenden gezeigt. Für Hidden-Markov-Modelle mit Gauß'scher Ausgabewahrscheinlichkeit und ohne Eingabesymbole ist die be dingte Wahrscheinlichkeit, den Wert y zum Zeitpunkt t auszugeben und zum Zustand j zu gehen, wenn das Modell in dem Zustand i ist

Die Parameter des Modells sind α_ij, µ_i und σ 2|i. Sie können aus folgenden Hilfs größen berechnet werden: N τ|i,j,k, M τ|i,k(y) und S τ|i,k(y), die wiederum nach der In itialisierung iterativ berechnet werden:

Die neuen Schätzungen der Parameter des HMM (durch Überstrich gekennzeich net) werden berechnet als

Ansonsten wird analog zu oben beschriebenem Verfahrensablauf vorgegangen.

Dieses Verfahren kann variiert werden, in dem oben beschriebene Rechnungen nur für einige der Parameter, z. B. die Übergangswahrscheinlichkeiten, ausgeführt werden, andere Parameter jedoch mit anderen Verfahren geschätzt werden. Wei terhin kann das Verfahren abgewandelt werden, indem alle oder einige Größen nur approximativ berechnet werden.

5. Gewerbliche Anwendbarkeit

Die angegebenen Verfahren können bei allen Verwendungen, in denen Hidden- Marlov-Modelle aus einer Zeitreihe geschätzt werden, eingesetzt werden.

6. Vorteilhafte Auswirkungen

Das Verfahren zum off-line-Schätzen zeichnet sich dadurch aus, daß im Gegen satz zur üblichen Forward-Backward-Prozedur der Speicherbedarf unabhängig von der Länge der Zeitreihe, und damit für typische Anwendungen wesentlich geringer ist, während bei der bisher üblichen Forward-Backward-Prozedur der Speicherbedarf proportional zur Länge der Zeitreihe ist. Das on-line-Verfahren zeichnet sich dadurch aus, daß die Elemente der Zeitreihe, auf deren Grundlage das Modell zu schätzen ist, nicht gespeichert werden müssen. Dies ermöglicht die Implementierung des Verfahrens mithilfe integrierter elektronischer Bauteile (IC's), die nur über wenig Speicher verfügen, z. B. mittels nur eines Chips. Mithilfe des on-line-Verfahrens ist die Bestimmung komplexer Größen, der Modellparame ter aus einfachen Meßwerten. z. B. zur Prozeßüberwachung, zu jedem Zeitpunkt möglich.

7. Figurenbeschreibung

Figur Nr. 1: Ein beliebiger autonomer deterministischer oder stochastischer Pro zeß E generiert Symbolketten x, welche die Eingabe des HMM darstellen. Der Hidden-Markov-Prozeß HMM mit internen Parametern v geht in Abhängigkeit vom jeweils erhaltenen Eingabesymbol x in einen neuen Zustand über und gibt ei ne Ausgabewert y aus. Der Beobachter beobachtet das Eingabesymbol x und den Ausgabewert y, nicht jedoch die internen Zustände und die internen Parameter des Automaten.

Figur Nr. 2: Ein Hidden-Markov-Prozeß, hier als Beispiel mit 3 Zuständen und endlicher Menge der Ausgabesymbole V, ist dargestellt. Bei Empfang eines Ein gabesymbols geht der Prozeß von seinem aktuellen Zustand i in einen neuen Zustand j über und gibt einen Ausgabewert y ∈ V aus mit Wahrscheinlichkeit p_i,j(y|x).

Literatur

[Titterington 84] D. M. Titterington. Recursive parameter estimation using in complete data. J. R. Statist. Soc. B 46, 257 (1984).
[Krishnamurthy 84] V. Krishnamurthy, J. B. 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] I. B. Collins, V. Krishnamurthy, J. B. Moore. On-line estimation of Hidden Makov Models via recursive prediction error techniques. IEEE. Transacton Signal. Proc 41. 2557 (1993).[Baum 66] L. E. Baum. T. Petrie. Ann. Math. Statist. 30, 1 554 (1966).
[Stiller 98) J. C. Stiller. Hidden-Markov-Modelle: Unüberwachtes Lernen und Klassifikation. Diss., Univ. Kiel (1998).

Claims

1. Verfahren zum Schätzen von Hidden-Markov-Modellen mit geringem Speicherbedarf und zum on-line-Schätzen von Hidden-Markov-Modellen aus einer Zeitreihe von Eingabe- und Ausgabewerten oder von Ausgabewer ten, dadurch gekennzeichnet, daß Parameter v des Modells aus einer oder mehreren mit mindestens 3 Indizes behafteten Hilfsgröße(n) N^l(y|x) und evtl. anderer Größen, nicht jedoch durch Elemente der Zeitreihe di rekt, berechnet werden und die Hilfsgrößen nach einer Initialisierung durch wiederholte iterative Anwendung einer Funktion G^l berechnet werden als N^l;t+1(y|x) := G^l(N^l;t(y|x), x(t+1), y(t+1), t, π^τ, v), wobei N^l;t die zur Zeit t gehörige l-te Hilfsgröße, x(t) den zur Zeit t gehörige Eingabewert und y(t) den zur Zeit t gehörigen Ausgabewert bezeichnet, π^t einen s-dimensionalen reellen Vektor bezeichnet, dessen Elemente entweder als Summe über be stimmte Elemente der Hilfsgrößen N^l;t berechnet werden, oder nach einer Initialisierung durch t-fach wiederholte iterative Anwendung einer Funkti on B berechnet werden als π^t+1 = B(π^t, x(t+1), y(t+1),v), wobei s die Anzahl der Zustände des Hidden-Markov-Modells ist.

2. Verfahren gemäß Anspruch 1, dadurch gekennzeichnet, daß π t+1|j = Σ s|i∈S π t|i p_i,j(y(t+1)|x(t+1); v) / C(π^t) gilt, wobei C eine reel le Funktion ist, π t|j die j-te Koordinate des Vektors π nach t Iterationen, v die aktuelle Schätzung der Parameter des Modells und p_i,j(y|x; v) die Wahrscheinlichkeit des Modells in den Zustand j überzugehen und den Ausgabewert y auszugeben, wenn das Modell im Zustand i ist, das Eingabesymbol x ist und die Parameter v sind, bezeichnet.

4. Verfahren gemäß mindestens einem der Ansprüche 1-3, dadurch ge kennzeichnet. daß für π^t und mindestens eine der Hilfsgrößen N^l gilt: π τ+1|i := ∈(τ) Σ_i,j∈S Σ_x∈UΣ_y∈VN l,τ|i,j,k(y|x) bei ∈(τ) eine beliebige reell wertige Funktion mit ist.

5. Verfahren gemäß Anspruch 4, dadurch gekennzeichnet, daß ∈(τ) = 1/τ ist.

6. Verfahren gemäß Anspruch 4, dadurch gekennzeichnet, daß ∈(t) = ∈ gilt für alle t < t_c, wobei ∈ eine beliebige, nicht negative reelle Zahl und t_c eine beliebige, nicht negative ganze Zahl ist.

7. Verfahren gemäß mindestens einem der Ansprüche 1-5, dadurch gekenn zeichnet, daß der Wertebereich der Eingabesymbole die Mächtigkeit 1 hat.

8. Verfahren gemäß mindestens einem der Ansprüche 1-7, dadurch gekenn zeichnet, daß der Wertebereich der Ausgabesymbole eine endliche Menge ist.

9. Verfahren gemäß mindestens einem der Anspüche 1-7, dadurch gekennzeichnet, daß für mindestens eine der Hilfsgrößen N^l gilt: 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) wobei h_i,j,k und g_i,j,k für alle i,j,k beliebig reelwertige Funktionen sind.

11. Verfahren gemäß Anspruch 10, dadurch gekennzeichnet, daß ∈(t) = ∈ gilt für alle t < t_c, wobei ∈ eine beliebige, nicht negative reelle Zahl und t_c eine beliebige, nicht negative ganze Zahl ist.

12. Verfahren gemäß mindestens einem der Ansprüche 1-11, dadurch ge kennzeichnet, daß über Parameter des Hidden-Markov-Prozesses a-priori- Informationen vorliegen, so daß die Berechnungen vereinfacht werden können.

13. Einrichtung, dadurch gekennzeichnet, daß sie mindestens einer der Verfah ren gemäß Ansprüchen 1-12 in digitaler oder analoger Weise nutzt.