Files
DissLiteratur/storage/KSYQMSA5/.zotero-ft-cache
Johannes Paehr c4354c0441 init
2025-10-18 15:35:31 +02:00

3104 lines
240 KiB
Plaintext
Raw Permalink Blame History

This file contains invisible Unicode characters
This file contains invisible Unicode characters that are indistinguishable to humans but may be processed differently by a computer. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
Leitfaden der Informatik Gernot A. Fink
Mustererkennung mit Markov-Modellen
Leitfaden der Informatik
Herausgegeben von Prof. Dr. Bernd Becker, Freiburg Prof. Dr. Friedemann Mattern, Zurich Prof. Dr. Heinrich Muller, Dortmund Prof. Dr. Wilhelm Schafer, Paderborn Prof. Dr. Dorothea Wagner, Karlsruhe Prof. Dr. Ingo Wegener, Dortmund
Die Leitfaden der Informatik behandeln • Themen aus der Theoretischen, Praktischen und Technischen Informatik entsprechend dem aktuel-
len Stand der Wissenschaft in einer systematischen und fundierten Darstellung des jeweiligen Gebietes . • Methoden und Ergebnisse der Informatik, aufgearbeitet und dargestellt aus Sicht der Anwendungen in einer fOr Anwender verstandlichen, exakten und prazisen Form. Die Bande der Reihe wenden sich zum einen als Grundlage und Erganzung zu Vorlesungen der Informatik an Studierende und Lehrende in Informatik-Studiengangen an Hochschulen, zum anderen an "Praktiker", die sich einen Oberblick Ober die Anwendungen der Informatik (-Methoden) verschaffen wollen; sie dienen aber auch in Wirtschaft, Industrie und Verwaltung tatigen Informatikern und Informatikerinnen zur Fortbildung in praxisrelevanten Fragestellungen ihres Faches.
Gernot A. Fink
Mustererkennung mit Markov-Modellen
Theorie - Praxis Anwendungsgebiete
Teubner
B. G. Teubner Stuttgart· Leipzig' Wiesbaden
Bibliografische Information der Deutschen Bibliothek Die Deutsche Bibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliographie; detaillierte bibliografische Daten sind im Internet uber <http://dnb.ddb.de> abrufbar.
Dr.-Ing. habil. Gernot A. Fink Geboren 1965 in Nurnberg, von 1985 bis 1991 Studium der Informatik and der Friedrich-AlexanderUniversitat in Erlangen. Seit 1991 wissenschaftlicher Mitarbeiter in der Arbeitsgruppe Angewandte Informatik an der Technischen Fakultat der Universitat Bielefeld. Promotion 1995 uber Integration von Spracherkennung und Sprachverstehen. 2002 Habilitation im Fach Angewandte Informatik. Seine Forschungsinteressen umfassen die automatische Sprach- und Handschrifterkennung, das Verstehen gesprochener Sprache, die multi-modale Mensch-Maschine-Interaktion sowie die statistische Analyse genetischer Sequenzen.
1. Auflage Oktober 2003
Aile Rechte vorbehalten © B. G. Teubner Verlag / GWV Fachverlage GmbH, Wiesbaden 2003
Der B. G. Teubner Verlag ist ein Unternehmen der Fachverlagsgruppe BertelsmannSpringer. www.teubner.de
Das Werk einschlieBlich aller seiner Teile ist urheberrechtlich geschutzt. Jede Verwertung auBerhalb der engen Grenzen des Urheberrechtsgesetzes ist ohne Zustimmung des Verlags unzulassig und strafbar. Das gilt insbesondere fUr Vervielfaltigungen, Obersetzungen, Mikroverfilmungen und die Einspeicherung und Verarbeitung in elektronischen Systemen .
Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten waren und daher von jedermann benutzt werden durften.
Umschlaggestaltung: Ulrike Weigel, www.CorporateDesignGroup .de
Gedruckt auf saurefreiem und chlorfrei gebleichtem Papier.
ISBN-13:978-3-519-00453-0
e-ISBN-13:978-3-322-80065-7
DOl : 10.1007/978-3-322-80065-7
Vorwort
Die Entwicklung von Mustererkennungsmethoden auf der Basis sogenannter Markov-Modelle ist eng verknupft mit dem technologischen Fortschritt im Bereich der automatischen Spracherkennung. Allerdings kommen Markov-Ketten- und Hidden-Markov-Modelle heute auch in vielen anderen Anwendungsfeldem zum Einsatz, wo es urn die Modellierung und Analyse zeitlich organisierter Daten wie z.B. genetischer Sequenzen oder handschriftlicher Texte geht. Trotzdem werden MarkovModelle in Monographien praktisch ausschlieBlich im Kontext der automatischen Spracherkennung behandelt und nicht als ein allgemeines, vieWiltig einsetzbares Instrumentarium der statistischen Mustererkennung.
Dieses Buch stellt dagegen den Formalismus der Markov-Ketten- und Hidden-Markov-Modelle in den Mittelpunkt der Betrachtungen. Am Beispiel der drei Hauptanwendungsgebiete dieser Technologie - namlich der automatischen Spracherkennung, der Handschrifterkennung sowie der Analyse genetischer Sequenzen - wird gezeigt, we1che Anpassungen an das jeweilige Einsatzgebiet erforderlich sind und wie diese in aktuellen Mustererkennungssystemen umgesetzt werden. Neben der Behandlung der theoretischen Grundlagen der Modellbildung liegt ein wesentlicher Schwerpunkt des vorliegenden Werks auf der Darstellung der fUr den erfolgreichen praktischen Einsatz unabdingbaren algorithmischen Losungen. Daher wendet sich dieses Buch sowohl an Fachleute aus dem Bereich Mustererkennung als auch an Studentinnen und Studenten mit einem entsprechenden Studienschwerpunkt, die sich mit Fragen der Sprach- oder Schrifterkennung bzw. der Bioinformatik oder vergleichbaren Problemstellungen beschiiftigen und ein tiefergehendes Verstandnis fUr den Einsatz statistischer Methoden in diesen Bereichen erwerben mochten.
Entstanden ist dieses Werk als Habilitationsschrift in der Arbeitsgruppe Angewandte Informatik an der Technischen Fakultat der Universitat Bielefeld. Mein besonderer Dank gilt Prof. Dr.-Ing. Heinrich Niemann (Universitat Erlangen), der im Studium mein Interesse an Mustererkennung geweckt hat, und meinem Betreuer Prof. Dr.-Ing. Gerhard Sagerer, der mir die Moglichkeit gegeben hat, im Rahmen vieler interessanter Projekte in dieses Forschungsfeld hineinzuwachsen. Ihnen beiden und Prof. Dr. Dieter Metzing danke ich daruber hinaus fUr die Erstellung der Gutachten.
Ganz herzlich bedanken mochte ich mich auch bei all jenen, die mich bei der Erstellung dieses Buchs durch Anregungen, Kritik und Hilfe bei der technischen AusfUhrung untersttitzt haben. Dazu zahlen insbesondere meine Kollegen Prof. Dr.-Ing. Franz Kummert, Thomas Plbtz, Markus Wienecke und Dr.-Ing. Britta Wrede. Fur die kompetente Beratung zu Fragen der Bioinformatik und speziell dem Themenkomplex der Analyse biologischer Sequenzen danke ich Kerstin Koch und Steffen Neumann. Martin Ellermann gilt mein Dank fur die Unterstutzung bei der Erstellung von Graphiken sowie der umfangreichen und teilweise nichttrivialen Literaturrecherche und -aufbereitung.
Bielefeld, im August 2003
Cernot A. Fink
Meinen Eltern
Inhalt
1
Einleitung
13
1.1
Thematischer Kontext
14
1.2
Funktionsprinzipien von Markov-Modellen
15
1.3
Zielsetzung und Aufbau
17
2
Anwendungen
19
2.1
Sprache
19
2.2
Schrift .
25
2.3
Biologische Sequenzen .
33
2.4
Ausblick. . . . . . . .
37
I Theorie
39
3
Grundlagen der Statistik
41
3.1
Zufallsexperiment, Ereignis und Wahrscheinlichkeit
41
3.2
Zufallsvariable und Wahrscheinlichkeitsverteilungen
43
3.3
Parameter von Wahrscheinlichkeitsverteilungen ..
45
3.4
Normalverteilungen und Mischverteilungsmodelle
46
3.5
Stochastische Prozesse und Markov-Ketten
47
3.6
Prinzipien der Parameterschatzung .
49
3.6.1 Maximum-Likelihood-Schatzung
49
3.6.2 Maximum-a-posteriori-Schatzung
51
3.7
Literaturhinweise . . .
51
4
Vektorquantisierung
53
4.1
Definition .
53
4.2
Optimalitat
55
4.3
Algorithmen zum Design von Vektorquantisierern
57
8
4.4
4.5 5 5.1
5.2 5.3
5.4 5.5
5.5.1
5.5.2 5.6
5.7 5.7.1
5.7.2
5.7.3 5.8
5.8.1
5.8.2 5.9 6 6.1 6.2 6.3 6.4
6.5 6.5.1
Lloyd-Algorithmus . . LBG-Algorithmus .. k-means-Algorithmus
Schatzung von Mischverteilungsmodellen . EM-Algorithmus .
Literaturhinweise . . . . .
Hidden-Markov-Modelle
Definition . . . . . . . .
Emissionsmodellierung .
Verwendungskonzepte
Notation ...... .
Bewertung ..... . Die Produktionswahrscheinlichkeit Forward-Algorithmus . . . . . . . Die "optimale" Produktionswahrscheinlichkeit
Dekodierung . . . . Viterbi-Algorithmus
Parameterschatzung Grundlagen . . . . . Forward-Backward-Algorithmus. Trainingsverfahren . . . . Baum-Welch-Algorithm us Viterbi- Training . . . . . Segmental k-Means .. . Mehrere Observationsfolgen
Modellvarianten ..... . Alternative Algorithmen . . Alternative Modellarchitekturen
Literaturhinweise . .
n-Gramm-Modelle
Definition . . . . . .
Verwendungskonzepte
Notation
Bewertung
Parameterschatzung Umverteilung von Wahrscheinlichkeitsmasse Discounting. . . . . . . . . . . . . . . . . .
Inhalt
58 59
61
62 63
66
67
67
69
70
72
73 73 74 76
79 80
81 82
83
85 85 91 93 95
96 96 97
97
99
99
100
101
102
104 105 105
Inhalt
9
6.5.2 Einbeziehung allgemeinerer Verteilungen
107
Interpolation . . . . . . . . . . . . . . .
108
Backing-Off . . . . . . . . . . . . . . .
110
6.5.3 Optimierung verallgemeinerter Verteilungen
111
6.6
Modellvarianten ........ .
113
6.6.1 Kategoriemodelle. . . . . . . . .
113
6.6.2 Uingere zeitliche Abhangigkeiten
115
6.7
Literaturhinweise . . . . . . . . .
116
II Praxis
117
7
Rechnen mit Wahrscheinlichkeiten
119
7.1
Logarithmische Wahrscheinlichkeitsreprasentation
119
7.2
Untere Schranken fUr Wahrscheinlichkeiten . . . .
122
7.3
Codebuchauswertung fUr semi-kontinuierliche HMMs
123
7.4
Wahrscheinlichkeitsverhaltnisse . . . . . . . . .
124
8
Konfiguration von Hidden-Markov-Modellen
127
8.1
Modelltopologien. . . . . . . . . . . . .
127
8.2
Modelluntereinheiten. . . . . . . . . . .
128
8.2.1 Kontextunabhangige Wortuntereinheiten .
129
8.2.2 Kontextabhangige Wortuntereinheiten
130
8.3
Verbundmodelle
131
8.4
Proiile-HMMs
133
8.5
Emissionsmodellierung .
135
9
Robuste Parameterschatzung
137
9.1
Merkmalsoptimierung . . . .
139
9.1.1 Dekorrelation . . . . . . . . .
140
Hauptachsentransformation I .
141
Whitening ......... .
145
9.1.2 Dimensionsreduktion. . . . .
146
Hauptachsentransformation II
146
Lineare Diskriminanzanalyse
147
9.2
Tying . ....... .
151
9.2.1 Modelluntereinheiten .
152
9.2.2 Zustandstying. . . . .
155
9.2.3 Tying in Mischverteilungsmodellen
159
9.3
Parameterinitialisierung ..... .
161
10
10
10.1
10.2
10.3 10.3.1 10.3.2 10.3.3
10.4 10.4.1 10.4.2
Effiziente Modellanswertung
Effiziente Auswertung von Mischverteilungen .
Beam Search . . . . . . . . .
Effiziente Parameterschatzung Forward-Backward-Pruning . Segmentweiser Baum-Welch-Algorithmus . Training von Modellhierarchien .
Baumformige Modellorganisation Priifixbaum flir HMMs . . . . . . Baumrepriisentation flir n-Gramm-Modelle
11 11.1 11.2
11.3 11.3.1 11.3.2 11.3.3
Modellanpassung
Grundprinzipien
Adaption von Hidden-Markov-Modellen Maximum-Likelihood Linear-Regression
Adaption von n-Gramm-Modellen . Cache-Modelle . . . . . . . . . Dialogschrittabhiingige Modelle Topic-basierte Sprachmodelle
12
12.1
12.2
12.3 12.3.1 12.3.2 12.3.3
12.4 12.4.1 12.4.2
Integrierte Suchverfahren
HMM-Netzwerke.
Mehrphasensuche .
Suchraumkopien Kontextbasierte Suchraumkopien Zeitbasierte Suchbaumkopien . . Language-ModeJ Look-Ahead . .
Zeitsynchrone parallele Modelldekodierung . Generierung von Segmenthypothesen Sprachmodellbasierte Suche . . . . . . . . .
III Systeme
13
Spracherkennung
13.1 Erkennungssystem der RWTH Aachen
13.2 BBN-Spracherkennungssystem BYBLOS
13.3 ESMERALDA . . . . . . . . . . . . . .
Inhalt
163 163 165 168 168 169 170 171 171 172
177 177 178 180 182 183 183 184
185 188 189 190 190 191 192 193 194 195
197
200 200 202 203
Inhalt
11
14
Schrifterkennung
207
14.1 OCR-System von BBN .
207
14.2 Duisburger on-line Handschrifterkennungssystem .
209
14.3 ESMERALDA off-line Erkennungssystem
210
15
Analyse biologischer Sequenzen
213
15.1 HMMER
213
15.2 SAM ..
214
Literaturverzeichnis
216
Sachverzeichnis
230
1 Einleitung
Die Erfindung der ersten Rechenmaschinen und auch die Entwicklung der ersten elektronischen Universalrechenautomaten war getrieben von der Idee, den Menschen bei bestimmten ArbeitsabUiufen zu entlasten. Man dachte damals allerdings tatsachlich "nur" an das Rechnen und noch keineswegs an Handreichungen im Haushalt. Die entwickelten Rechenmaschinen sollten also Aufgaben libernehmen, die der Mensch selbstverstandlich auch zu erledigen vermochte, die aber durch ein automatisches System wesentlich ausdauernder und damit zuverlassiger und billiger ausgefUhrt werden konnen.
Die rasant fortschreitende Entwicklung der Computertechnologie lieB es bald schon zu, von wesentlich ehrgeizigeren Zielen zu traumen. 1m Bestreben sogenannte "klinstliche Intelligenz" (KI) zu schaffen, schickte man sich an, die Fahigkeiten des Menschen in bestimmten Bereichen zu libertrumpfen. Ais Intelligenz wurde damals im wesentlichen die Losung mathematischer oder anderer formal definierter Probleme durch symbolische Verfahren angesehen. Prototypischer Untersuchungsgegenstand war daher lange Zeit das Schachspiel. Der Sieg des Schachcomputers Deep Blue gegen Weltmeister Kasparov im Jahr 1997 bedeutete flir die Firma IBM auch eine wichtige WerbemaBnahme. Er bewies letztendlich aber nur, dass Schachspielen wohl doch keine so typische Intelligenzleistung ist, da sich in dieser Disziplin mit relativ brachialer Rechenleistung auch der beste menschliche Experte schlagen lasst. In dem flir menschliche Fahigkeiten zentralen Bereich des Verstehens von Sprache konnten dagegen aIle aus den Urspriingen der KI-Forschung hervorgegangenen symbolischen und regelbasierten Verfahren nur bescheidene Erfolge verbuchen.
Inzwischen ist ein radikaler Paradigmenwechsel abgeschlossen, der dazu geflihrt hat, dass typisch menschliche Intelligenz nicht mehr auf symbolischer Ebene gesehen wird, sondern vielmehr in Fahigkeiten zur Verarbeitung unterschiedlicher sensorischer Eingabedaten. Hierzu zahlen unter anderem die Kommunikation mit gesprochener Sprache, die Interpretation visueller Eindrlicke und die Interaktion mit der physikalischen Umwelt durch Bewegung, Tasten und Greifen. Sowohl auf dem Gebiet der automatischen Bild- und Sprachverarbeitung als auch der Robotik wurden schon seit vielen Jahrzehnten erste Losungen mit einem ingenieurwissenschaftlichen Hintergrund erarbeitet. Seit sich durch den erfolgreichen Einsatz statistischer Methoden gezeigt hat, dass automatisch trainierbare Systeme ihre "festverdrahteten" regelbasierten Pendants an Flexibilitat und Leistungsfahigkeit deutlich libertreffen konnen, erhalt das Konzept des Lernens in diesen Forschungsbereichen besondere Aufmerksamkeit. Auf diesem Gebiet ist das Vorbild Mensch noch unschlagbar. So muss man sich derzeit damit begnligen, die entsprechenden menschlichen Fahigkeiten unter stark eingeschrankten Rahmenbedingungen in Rechenanlagen rudimentar nachzubilden.
Zentral fUr aIle automatisch lernenden Verfahren ist die VerfUgbarkeit von Beispieldaten, aus denen die Parameter der erstellten Modelle abgeleitet werden konnen. Es sind daher keine komplexen symbolischen Regelwerke erforderlich, urn die typischen Eigenschaften der betrachteten Daten zu
14
1 Einleitung
beschreiben. Vielmehr werden diese wiihrend der wiederholten Priisentation von Trainingsbeispielen durch Lernalgorithmen automatisch extrahiert.
Die wohl bekannteste Klasse von lernenden Verfahren sind die sogenannten ktinstlichen Neuronalen Netze, deren Bausteine extrem vereinfachten Modellen menschlicher Nervenzellen entsprechen - den Neuronen. Ais universeller Funktionsapproximator ist dieser Formalismus sehr miichtig, aber auch ftir manche Anwendungen zu allgemein. Daher haben sich andere statistische Formalismen etablieren konnen, die besonders gut an bestimmte Einsatzgebiete angepaBt sind. Speziell flir die statistische Modellierung zeitlich organisierter Daten werden tiberwiegend Markov-Modelle eingesetzt.
Das bekannteste Anwendungsgebiet dieser Technologie ist die automatische Spracherkennung. In den Anfiingen der entsprechenden Forschung konkurrierte sie lange mit symbolischen Ansiitzen. Die Verftigbarkeit groBer Sprachstichproben liiutete jedoch den Siegeszug statistischer Verfahren ein. Mittlerweile stellen daher Hidden-Markov-Modelle zur Beschreibung akustischer Ereignisse in Kombination mit Markov-Ketten-Modellen zur statistischen Modellierung von Wortfolgen auf symbolischer Ebene die Standardtechnologie zur Erstellung erfolgreicher Spracherkennungssysteme dar.
Erst in jtingster Zeit eroberten diese Verfahren ein sowohl thematisch wie sensorisch verwandtes Aufgabenfeld. Die automatische Erkennung handschriftlicher Texte liisst sich ebenso wie die Spracherkennung als Segmentierungsproblem zeitlich organisierter Sensordaten auffassen. Die Zeitachse liiuft dabei entweder entlang der zu verarbeitenden Textzeile oder entlang der Schriftlinie selbst. Mit diesem "Trick" lassen sich die aus dem Bereich der automatischen Spracherkennung bekannten statistischen Modellierungstechniken meist mit nur geringftigigen Anpassungen auf das Problemfeld der Handschriftverarbeitung tibertragen.
Ein drittes wichtiges Anwendungsfeld von Markov-Modellen flihrt aus dem Bereich der MenschMaschine-Interaktion heraus. Die Bioinformatik beschiiftigt sich schwerpunktmiiBig mit zellbiologischen Abliiufen und deren Simulation oder Analyse mit Hilfe von Methoden der Informatik. Spezielles Augenmerk richtet sich derzeit auf die Interpretation des menschlichen Genoms. Aus Sicht der statistischen Mustererkennung handelt es sich dabei - und bei daraus abgeleiteten Zellprodukten wie z.B. RNA oder Proteinen - urn im wesentlichen linear aufgebaute Symbolfolgen. Obwohl zur Analyse solcher biologischer Sequenzen schon relativ lange statistische Techniken eingesetzt werden, wurde die Bioinformatik-Forschung erst vor wenigen lahren auf Hidden-Markov-Modelle aufmerksam. Der Erfolg der entsprechenden Verfahren in diesem Anwendungsgebiet war so groB, dass inzwischen mehrere Programmpakete zur Anwendung von Markov-Modellen sowie Bibliotheken vorgefertigter Modelle ftiT verschiedene Analysezwecke existieren.
1.1 Thematischer Kontext
Den thematischen Kontext flir die Behandlung von Markov-Modellen bildet das Forschungsfeld der Mustererkennung (vgl. [Nie 83, Nie 90]). Ais Muster werden dabei primiir Messwerte bestimmter Sensoren wie z.B. Bilder oder Sprachsignale bezeichnet. Allerdings lassen sich Mustererkennungsmethoden auch auf andere Eingabedaten anwenden, wie z.B. die symbolisch repriisentierte Erbinformation in DNA-Striingen.
1.2 Funktionsprinzipien von Markov-Modellen
15
Urn ftir den Erkennungsprozess wesentliche Eigenschaften der Daten von stOrenden bzw. irrelevanten zu trennen, werden die betrachteten Muster in eine Merkmalsreprasentation tiberftihrt. Dies schlieBt in der Regel verschiedene Vorverarbeitungsschritte ein, die dazu dienen, die Signale ftir die ktinftige Verarbeitung zu "verbessern", also z.B. die Beleuchtung in einem Bild oder die Lautstlirke einer sprachlichen AuBerung zu normieren.
Nach der Merkmalsextraktion erfolgt die Segmentierung der Daten. Bei Bildern werden hier z.B. Regionen ahnlicher Farbe oder Textur ermittelt. Diese Segmente werden anschlieBend durch Klassifikation einer bestimmten Musterklasse zugeordnet. Man erhlilt also auf dieser Ebene erstmals eine einfache symbolische Beschreibung der Daten. Allerdings lassen sich nicht ftir aIle ProblemsteIlungen Segmentierung und Klassifikation so klar trennen. Bei der Verarbeitung gesprochener Sprache ist es z.B. nicht m6glich, eine Segmentierung zu erzeugen, ohne zu wissen, was eigentlich gesprochen wurde, da Wortgrenzen nicht akustisch markiert sind. Vielmehr lasst sich erst nach Bekanntwerden der tatsachlichen AuBerung auf die Grenzen zwischen den beteiligten Einheiten zuruckschlieBen1• Zur L6sung solcher Mustererkennungsaufgaben sind daher integrierte Segmentierungsund Klassifikationsverfahren erforderlich, die jedoch in ihrer Komplexitat tiblicherweise deutlich tiber isoliert anzuwendende Methoden hinausgehen.
Die einfache symbolische Reprasentation von Mustern, die nach dem Klassifikationsschritt vorliegt, reicht fur viele Mustererkennungsanwendungen nicht aus, da keinerlei strukturelle Eigenschaften reprasentiert sind. Solche zu erzeugen ist das Ziel der Musteranalyse, die ausgehend von den Klassifikationsergebnissen versucht, strukturierte Interpretationen ftir Muster zu berechnen. Bei Bildern k6nnte dies z.B. eine Beschreibung der betrachteten Szene sein, die neben der Klassifikation einzeIner elementarer Objekte auch deren relative Lage zueinander sowie deren Zusammensetzung zu komplizierteren Gebilden angibt. 1m Bereich der Sprachverarbeitung besteht die Analyse einer AuBerung in der Regel darin, ftir diese eine Bedeutungsreprasentation zu erzeugen, die die Basis eines Mensch-Maschine-Dialogs oder der automatischen Ubersetzung in eine andere Sprache sein kann.
1.2 Funktionsprinzipien von Markov-Modellen
Die einfachste Form der Markov-Modelle bilden die sogenannten Markov-Ketten-Modelle, die zur statistischen Beschreibung von Symbol- oder Zustandsfolgen verwendet werden k6nnen. Entwickelt wurden sie von dem russischen Mathematiker Andrej Andrejewitsch Markov (1856 - 1922), nach dem sie auch benannt sind. Er setzte sie Anfang des vorigen Jahrhunderts erstmals ein zur statistischen Analyse der Buchstabenabfolge im Text von "Eugen Onegin", einer Versnovelle von Alexander Puschkin [Mar 13].
Die Funktionsweise dieser Modellvariante lasst sich auch am Beispiel von Texten sehr gut verdeutlichen. Die Zustande des Modells sind dabei identisch mit den W6rtern eines bestimmten Lexikons, aus dem die untersuchten Wortfolgen gebildet werden. Markov-Ketten-Modelle geben dann an, wie wahrscheinlich das Auftreten eines Wortes in einem bestimmten textuellen Kontext ist.
1In den ersten kommerziellen Diktiersystemen der Firmen IBM und Dragon Systems wurde dieses Dilemma durch einen Verfahrenstrick gelost. Man verlangte einfach yom Benutzer, zwischen Wortem jeweils kleine Pausen beim Sprechen zu machen. So lie8en sich Au8erungen zuerst durch Detektion der Pausen in Worter segmentieren und diese anschlie8end klassifizieren.
16
1 Einleitung
Durch Auswertung dieser Wahrscheinlichkeit fUr eine Folge von Wortern ergibt sieh die Gesamtwahrscheinlichkeit fUr den betrachteten Textabschnitt. Mit einem geeignet gewiihlten Modell lassen sieh so z.B. plausible - d.h. wahrscheinliche - von unplausiblen - d.h. weniger wahrscheinlichen Satzen einer Sprache unterscheiden. 1m Gegensatz zu einer formalen Sprachdefinition Wlt diese ZugehOrigkeitsentscheidung allerdings nieht deterministisch, sondern probabilistisch aus. Liegen z.B. mehrere Modelle fUr verschiedene Textsorten vor, so kann man die Erzeugungswahrscheinlichkeit auch als Basis einer Klassifikationsentscheidung nutzen. 1m einfachsten Fall entscheidet man sieh ftir diejenige Textsorte, deren zugehOriges Modell fUr einen bestimmten Textabschnitt die groBte Wahrscheinlichkeit liefert.
Bei den sogenannten Hidden-Markov-Modellen wird das Konzept einer statistisch modellierten Zustandsfolge urn zustandsspezifische Ausgaben des Modells erweitert. Man geht davon aus, dass nur diese sogenannten Emissionen beobachtbar sind, die zugrundeliegende Zustandsfolge jedoch versteckt (engl. hidden) ist, woraus sich auch die Bezeichnung dieser Modellvariante ableitet. Ftir die statistischen GesetzmaBigkeiten, die der Generierung der Zustandsfolge und der Emissionen zugrunde liegen, gelten starke Einschrankungen. 1m Wesentlichen lasst sieh ein Hidden-MarkovModell als statistisch angereicherter, generierender endlicher Automat ansehen. Sowohl die Ubergange zwischen Zustanden als auch die Erzeugung von Ausgaben erfolgt in Abhangigkeit von bestimmten Wahrscheinlichkeitsverteilungen.
Urn eine solches generativ formuliertes Modell ftir die Analyse bereits vorliegender Daten einsetzen zu konnen, bedarf es eines gedanklichen Tricks. Man nimmt dabei zuerst an, dass die zu untersuchenden Daten von einem nattirlichen Prozess erzeugt wurden, der vergleichbaren statistischen GesetzmaBigkeiten gehorcht. Dann versucht man diesen mit den Moglichkeiten von Hidden-MarkovModellen moglichst genau nachzubilden. Gelingt dies, lassen sich anhand des ktinstliehen Modells Rtickschltisse auf den realen Prozess ziehen. Dies kann zum einen die Wahrscheinlichkeit betreffen, mit der vorliegende Daten erzeugt werden. Zum anderen ist der Rtickschluss auf die internen Vorgange im Modell zumindest probabilistisch moglich. Man kann namlich diejenige Zustandsfolge bestimmen, die am wahrscheinlichsten eine bestimmte Folge von Emissionen erzeugt.
Ordnet man ganzen Modellen die Bedeutung zu, Klassen von Mustern zu reprasentieren, so lasst sieh der Formalismus zur Klassifikation einsetzen. Das weitaus verbreitetere Vorgehen ist jedoch, Teile eines groBeren Gesamtmodells - also Zustiinde oder Zustandsgruppen - mit bedeutungstragenden Segmenten der zu untersuchenden Daten zu identifizieren. Durch die Aufdeckung der Zustandsfolge ist dann eine Segmentierung der Daten mit gleichzeitiger Klassifikation in die gewahlten Einheiten moglich.
Bei der automatischen Erkennung gesprochener Sprache entsprechen die Ausgaben des Modells dem akustischen Sprachsignal bzw. seiner parametrischen Merkmalsreprasentation. Die Modellzustande definieren dagegen elementare akustische Ereignisse wie z.B. Laute einer bestimmten Sprache. Folgen von Zustanden entsprechen dann Wortern und ganzen sprachlichen AuBerungen. Kann man also fUr ein gegebenes Sprachsignal die erwartete interne Zustandsfolge rekonstruieren, so lasst sieh diesem Signal die - hoffentlich korrekte - gesprochene Wortfolge zuordnen und damit das Segmentierungs- und Klassifikationsproblem integriert losen.
Diese Moglichkeit, Segmentierung und Klassifikation in einem integrierten Formalismus zu behandeln, stellt die herausragende Starke von Hidden-Markov-Modellen dar. Das eingangs aufgezeigte Dilemma, dass die Klassifikation eine Segmentierung voraussetzt, aber oft eine Segmentierung nur mit dem Wissen urn das Klassifikationsergebnis moglich ist, kann so elegant umgangen werden.
1.3 Zielsetzung und Aufbau
17
Wegen dieser wichtigen Eigenschaft werden Verfahren auf der Basis von Hidden-Markov-Modellen auch als segmentierungsfrei bezeichnet.
Sowohl Markov-Ketten- als auch Hidden-Markov-Modelle haben gegentiber symbolischen Ansiitzen den entscheidenden Vorteil, dass die erforderlichen Modellparameter automatisch anhand von Beispieldaten trainiert werden konnen. Allerdings garantiert diese Moglichkeit allein noch nicht den Erfolg dieser Modellierungsmethode. Statistische Parameterschiitzungen liefern niimlich nur dann zuverliissige Ergebnisse, wenn ausreichend viele Trainingsbeispiele vorliegen. Leistungsfiihige Markov-Modelle lassen sich daher nur erstellen, wenn flir das Parametertraining Stichproben von betriichtlichem Umfang zur Verfligung stehen. Auch konnen durch die Trainingsalgorithmen lediglich die Parameter der Modelle, nicht jedoch deren Konfiguration - d.h. die Struktur und die Anzahl der freien Parameter - automatisch bestimmt werden. HierftiT sind auch im Rahmen statistischer Verfahren die Erfahrung von Experten und umfangreiche experimentelle Untersuchungen erforderlich. AuBerdem setzen viele der bekannten Schiitzverfahren das Vorliegen eines initialen Modells voraus, das dann schrittweise verbessert wird. Die Wahl des Startpunkts kann daher die Leistungsfiihigkeit des fertigen Markov-Modells entscheidend beeinflussen. SchlieBlich bieten Markov-Ketten- und Hidden-Markov-Modelle unterschiedliche Modellierungsmoglichkeiten, so dass sie vielfach in Kombination zum Einsatz kommen. Dies erfordert in der konkreten technischen Umsetzungjedoch komplexe algorithmische LOsungen, die weit tiber eine einfache Verrechnung von Wahrscheinlichkeitswerten hinausgehen.
Der erfolgreiche Einsatz von Markov-Modell-basierten Techniken flir Mustererkennungsaufgaben erfordert daher die Losung einer Reihe von verfahrenstechnischen Problemen, die deutlich tiber die reine technische Umsetzung der zugrundeliegenden mathematischen Theorie hinausgehen.
1.3 Zielsetzung und Autbau
Die extensive Anwendung und damit auch die umfangreiche Weiterentwicklung von Mustererkennungsmethoden auf der Basis von Markov-Modellen erfolgte im Bereich der automatischen Spracherkennung. Dort stellt heute die Kombination von Hidden-Markov-Modellen ftiT die akustische Analyse und Markov-Ketten-Modellen flir die Restriktion moglicher Wortfolgen das beherrschende Paradigma dar. Dies erkliirt auch die Tatsache, dass die Behandlung dieser Methoden in Monographien fast immer an den Themenkomplex der Spracherkennung gekoppelt ist (vgl. [Hua 90, ST 95, Jel 97, Fur 00, O'S 00, Hua 01]).
Ihre Anwendung in weiteren Einsatzgebieten wie z.B. der Schrifterkennung oder der Analyse biologischer Sequenzen erschlieBt sich dagegen erst aus der entsprechenden Spezialliteratur. Dies gilt tiberraschenderweise auch flir die Darstellung von Markov-Ketten-Modellen, die tiblicherweise als statistische Sprachmodelle bezeichnet werden. Mit Ausnahme der neu erschienenen Monographie von Huang und Kollegen [Hua 01] werden die erforderlichen Grundlagen und Algorithmen fast ausschlieBlich in eng auf Detailfragen fokussierten Artikeln in Fachzeitschriften und Konferenzbiinden behandelt. Mnlich verhiilt es sich mit Fragestellungen, die sich im Zusammenhang mit der praktischen Anwendung der Markov-Modell-Technologie ftir Mustererkennungsaufgaben ergeben. Hierzu ziihlen vor allem die erfolgreiche Konfiguration der Modelle, die Behandlung effizienter AIgo-
18
1 Einleitung
rithmen, Methoden zur Anpassung der Modellparameter an veranderte Einsatzgebiete sowie die Kombination von Markov-Ketten- und Hidden-Markov-Modellen in integrierten Suchprozessen.
Das vorliegende Werk verfolgt daher zwei Ziele. Zum einen sollen Markov-Modelle in Bezug auf ihren mittlerweile auBerst breiten Anwendungskontext dargestellt werden. Zum anderen soIl die Behandlung sieh nicht nur auf den theoretischen Kern der Modellbildung konzentrieren, sondern aIle aus heutiger Sicht relevanten technologischen Aspekte mit einschlieBen.
Zu Beginn des Buchs steht in Kapitel 2 ein Uberblick tiber die moglichen Anwendungsgebiete der Markov-Modell-Technologie. Ais prototypisches Einsatzgebiet wird dabei zuerst die automatische Erkennung gesprochener Sprache betrachtet, bevor die beiden weiteren Hauptanwendungsfelder Schrifterkennung sowie die Analyse biologischer Sequenzen vorgestellt werden. Das Kapitel schlieBt mit einem Ausblick auf einige der vielen weiteren Einsatzm6glichkeiten von MarkovModellen.
Teil I dieses Buchs liefert den formalen Rahmen flir die Behandlung von Markov-Modellen. Zu Beginn steht eine kurze Einftihrung in relevante Grundbegriffe der Wahrscheinlichkeitsrechnung und Statistik. AuBerdem werden grundlegende Methoden zur Vektorquantisierung und Schatzung von Mischverteilungsmodellen vorgestellt, die zur Modellierung hochdimensionaler Daten eingesetzt werden. AnschlieBend erfolgt die formale Beschreibung der beiden Vertreter der Markov-ModellTechnologie, namlich von Hidden-Markov-Modellen und Markov-Ketten-Modellen, die oft auch als n-Gramm-Modelle bezeichnet werden. Das Augenmerk richtet sich dabei nieht so sehr darauf, aIle moglichen Varianten der entsprechenden Formalismen zu behandeln, als vielmehr darauf, ein in sich stimmiges Gesamtkonzept der theoretischen Grundlagen zu prasentieren.
Thema des zweiten Teils sind verschiedene wiehtige Aspekte des praktischen Einsatzes von Verfahren auf der Basis von Markov-Modellen. Zu Beginn steht der robuste Umgang mit den bei diesen statistischen Methoden allgegenwartigen Wahrscheinlichkeitsgr6Ben. Kapitel 8 behandelt die Konfiguration von Hidden-Markov-Modellen flir bestimmte Anwendungsfalle. 1m Anschluss daran wird die robuste Schatzung der erforderlichen Modellparameter erlautert. Kapitel 10 stellt die wiehtigsten Methoden zur effizienten Verwendung von Markov-Modellen vor. Die Anpassung der Modelle an unterschiedliche Einsatzgebiete ist Thema von Kapitel 11. Den Abschluss von Teil II bildet schlieBlieh die Behandlung von Algorithmen zur Suche in den hochkomplexen L6sungsraumen, die sich bei der integrierten Anwendung von Markov-Ketten- zusammen mit Hidden-Markov-Modellen ergeben.
Der Kreis zu den Anwendungen von Markov-Modellen schlieBt sieh in Teil III. Hier werden ausgewahlte Systeme aus den Hauptanwendungsgebieten Spracherkennung, Handschriftverarbeitung und Analyse biologischer Sequenzen vorgestellt. Dabei stehen die in diesen Systemen erfolgreieh realisierte Kombination unterschiedlicher Verfahrensaspekte im Vordergrund.
2 Anwendungen
2.1 Sprache
Die Interaktion mittels gesprochener Sprache stellt die vorherrschende Modalitat zur Kommunikation von Menschen untereinander dar. Mit Hilfe sprachlicher A.uBerungen konnen Emotionen vermittelt, Ironie zum Ausdruck gebracht, schlicht "Konversation" gemacht oder Informationen tibermittelt werden. Dieser letzte Aspekt steht bei der automatischen Verarbeitung von Sprache bei weitem im Vordergrund. Mit gesprochener Sprache lassen sich Informationen einigermaBen mtihelos und mit einer relativ hohen "Datenrate" von bis zu 250 Wortern pro Minute vermitteln bzw. tibertragen. Damit tibertrifft diese Modalitat prinzipiell aIle anderen Kommunikationsmoglichkeiten des Menschen z.B. durch Gestik, Handschrift oder Tastatureingabe beztiglich Einfachheit der Anwendung und Effizienz. Daraus wird in der Literatur vielfach gefolgert, dass gesprochene Sprache auch die beste Losung zur Kommunikation mit automatischen Systemen sei. Dies darf jedoch bezweifelt werden, wie die Vorstellung eines GroBraumbiiros, in dem aIle Mitarbeiter auf ihre Rechner einreden, oder die nur per Sprache und nicht per einfachem Knopfdruck bedienbare Kaffeemaschine zeigen.
Es gibtjedoch eine Reihe von Szenarien, in denen Mensch-Maschine-Kommunikation mit gesprochener Sprache - gegegenenfalls unter Einbeziehung weiterer Modalitaten - sinnvoll zum Einsatz kommen kann. Dabei wird entweder das Ziel verfolgt, ein bestimmtes Gerat zu steuern oder von diesem Informationen zu erlangen. Beispiele fiir solche Informationssysteme bilden automatische Auskunftssysteme, tiber die telefonisch Fahrplan- oder Veranstaltungsinformationen abgefragt und eventuell auch sofort die zugehOrigen Bahn-, Kino- oder Theaterkarten bestellt werden konnen. Zu den Steuerungsanwendungen zahlen die Bedienung von Mobiltelefonen, die auf Zuruf des Namens bzw. der Telefonnummer die entsprechende Verbindung hersteIlen, die Maschinensteuerung in einem industriellen Kontext, der die Verwendung anderer Modalitaten ausschlieBt, und auch die Kontrolle sogenannter nicht-sicherheitsrelevanter Funktionen im Fahrzeug, wie z.B. Radio oder Klimaanlage. Ais sehr speziellen Fall der Geratesteuerung kann man auch die automatische Transkription gesprochener Texte in Diktiersystemen ansehen. Diese Anwendung wurde zwar nicht zur "Killerapplikation" von Sprachtechnologie, hat deren Entwicklungsprozess aber entscheidend beeinflusst.
Urn sprachliche Mensch-Maschine-Kommunikation moglich zu machen, mtissen gesprochene A.uBerungen auf eine geeignete rechnerinterne symbolische Beschreibung abgebildet werden, auf deren Grundlage dann die Aktionen des automatischen Systems erfolgen. Dazu muss zuerst das physikalische Korrelat gesprochener Sprache - d.h. die geringfiigigen A.nderungen des Luftdrucks durch die Schallausbreitung - digital reprasentiert werden. Mit Hilfe eines Mikrophons wird der Schalldruck in eine elektrisch messbare GroBe umgewandelt, deren zeitlicher Verlauf dem Schallsignal entspricht. Zu deren moglichst exakter Reprasentation in digitaler Form wird der entsprechende
20
2 Anwendungen
s p r a:
E n U
N
Abb. 2.1 Beispiel eines digitalisierten Sprachsignals mit Markierung der von Expertenhand ermittelten Lautsegmente des isoliert gesprochenen Wortes "Spracherkennung".
Funktionsverlauf abgetastet, d.h . es werden in einem bestimmten Zeittakt die jeweiligen analogen Werte bestimmt und anschlieBend quantisiert, d.h. auf einen endlichen Wertevorrat abgebildet. Die Kombination von Abtastung und Quantisierung bezeichnet man als Digitalisierung. Bei gesprochener Sprache arbeitet man in der Regel mit Abtastraten von 11 bis 16 kHz und speichert die einzelnen quantisierten Messwerte mit einer Genauigkeit von 8 bis 16 bit.
Abbildung 2.1 zeigt exemplarisch ein digitalisiertes Sprachsignal. Flir sehr einfache Sprachverarbeitungsanwendungen reicht diese Information manchmal bereits aus. So lasst sich die Namenswahl in einem Mobiltelefon auf der Basis des direkten Vergleich des aktuellen Signals mit einigen wenigen gespeicherten Referenzsignalen realisieren. Bei komplexen Anwendungen ist es jedoch unerlasslich, aus dem Signal zuerst eine geeignete symbolische Zwischenreprasentation zu erzeugen, bevor eine Interpretation der Daten im Anwendungskontext erfolgt.
Neben der Realisierung als akustisches Signal existiert flir Sprache auch die duale Reprasentation in Form von Schrift. Obwohl sich eine Reihe von Eigenschaften gesprochener Sprache, wie z.B . Lautstarke, Geschwindigkeit oder Klangfarbe, schriftlich nicht reprasentieren lassen, kann man doch immer den zentralen Informationsgehait in orthographischer Form angeben. Diese "Kodierung" des akustischen Signals lasst sich auch in Rechnern leicht reprasentieren und verarbeiten. Daher gehort es in komplexeren sprachverarbeitenden Systemen zum Standard, Sprachsignale zuerst auf eine textuelle Reprasentation abzubilden. Diesen Verarbeitungsschritt bezeichnet man als Spracherkennung. Das sogenannte Sprachverstehen setzt auf den Ergebnissen der Spracherkennung auf, die z.B. aus einer Folge von Wortern bestehen, und versucht auf dieser Basis eine symbolische Bedeutungsreprasentation flir die betrachtete AuBerung zu erzeugen. Bei Auskunftssystemen wird
2.1 Sprache
21
dabei unter anderem die Intention des Benutzers ermittelt und die wesentlichen Parameter seiner Anfrage extrahiert. Ein automatisches Dialogsystem der Bahn muss z.B. eine Fahrplanauskunft von einer Fahrkartenbestellung unterscheiden und in beiden Hillen den Abfahrts- und Zielort sowie den gewiinschten Reisezeitpunkt bestimmen. Zur syntaktisch-semantischen Analyse von textuell repdisentierten Sprachbeispielen wurden im Rahmen der linguistischen Forschung zahlreiche Ansatze entwickelt (vgl. z.E. [Win 83]). Daher kommen zur Interpretation von sprachlichen AuBerungen fast ausschlieBlich regelbasierte Verfahren zum Einsatz, die entweder direkt auf linguistischen Theorien aufsetzen oder durch diese motiviert sind (vgl. z.B. [Kum 98]).
Die Abbildung eines Sprachsignals auf dessen textuelle Reprasentation, wie es Ziel der Spracherkennung ist, gelingt dagegen nicht mit rein symbolischen Verfahren. Hauptgrund dafiir ist die groBe Variabilitat bei der Realisierung selbst prinzipiell identischer sprachlicher AuBerung durch verschiedene Sprecher bzw. in unterschiedlichen Umgebungen. AuBerdem sind auf der Signalebene Grenzen zwischen akustischen Einheiten nur in Ausnahmefallen markiert.
Die elementare Beschreibungseinheit fiir sprachliche Ereignisse ist das sogenannte Phon, das einen einzelnen sprachliche Laut bezeichnet. 1m Gegensatz zu einem Phonem, der kleinsten bedeutungsunterscheidenden Einheit, definieren Phone akustisch unterscheidbare "Bausteine" sprachlicher AuBerungen. Die verwendeten Kategoriensysteme sind auf der Basis der Artikulation der entsprechenden sprachlichen Einheiten entwickelt worden (vgl. z.B. [Koh 95]). Dabei legt man ein Modell des Spracherzeugungsprozesses zugrunde, dessen Prinzipien im folgenden kurz skizziert werden sollen.
Zuerst wird - im allgemeinen durch Ausatmen - ein Luftstrom aus der Lunge erzeugt, der den durch die Stimmbander und Stimmritzen gebildeten Stimmapparat im Kehlkopf passiert. 1st diese sogenannte Glottis geschlossen, entsteht eine Folge periodischer Druckimpulse, wahrend bei geoffneter Glottis die vorbeistromende Luft nur ein weiBes Rauschen verursacht. Dieses stimmhafte bzw. stimmlose Anregungssignal wird dann im sogenannten Vokaltrakt in seiner spektralen Zusammensetzung modifiziert, so dass ein bestimmter sprachlicher Laut gebildet wird. Der Vokaltrakt besteht aus Mund-, Nasen- und Rachenraum und kann je nach bffnung des Unterkiefers bzw. Stellung der Zunge und des Gaumensegels in seiner Form verandert werden. Die beiden groben Lautklassen Vokale und Konsonanten lassen sich, vereinfacht ausgedriickt, dadurch unterscheiden, dass bei ersteren immer eine stimmhafte Anregung erfolgt und der Vokaltrakt hierfiir ledigJich einen Resonanzraum bildet. Bei weitestmoglicher bffnung erhait man z.E. einen A-Laut wie in "Sprache" (in phonetischer Umschrift1 / Spra: x@/). Konsonanten entstehen dagegen durch eine Engebildung im Vokaltrakt wahlweise mit einer stimmhaften oder stimmlosen Anregung. Liegt z.B. die Zungenspitze hinter dem Zahndamm an, so wird entweder ein stimmhafter oder ein stimmloser S-Laut wie in "reisen" bzw. "reij3en" erzeugt (/raIz@n/ bzw. /raIs@nl).
Sprachliche AuBerungen entstehen immer als Folge solcher elementaren Laute. Allerdings liegen diese Einheiten darin nicht diskret vor und sind daher keineswegs einfach zu segmentieren. Da die Artikulationsorgane ihre Stellung nicht von einem Laut zum nachsten instantan andern konnen, erfolgt dies in kontinuierlichen Bewegungen. Daher spiegeln Sprachsignale den gleichmaBigen Ubergang zwischen den charakteristischen Eigenschaften der aufeinanderfolgenden Laute wider. Bei starker Idealisierung der realen Verhaltnisse kann man annehmen, dass in sorgfaltig artikulierter, langsamer Sprache die typischen Eigenschaften eines Lautes in dessen Zentrum ausgepragt sind.
lSofern im Rahmen dieses Buchs phonetische Umschriften sprachlicher AuBerungen angegeben sind, verwenden diese das SAMPA-Symbolinventar, das als maschinenlesbare Version des IPA (International Phonetic Alphabet) speziell fUr die automatische Verarbeitung im Rechner entwickelt wurde [Well.
22
2 Anwendungen
Die Randbereiche des entsprechenden Signalabschnitts sind dagegen durch die benachbarten Laute beeinftusst. Diese gegegenseitige Beeinftussung von Lauten im Sprachftuss bezeichnet man als Koartikulation, deren Effekte unter realen Bedingungen auch tiber mehrere Laute hinweg andauern konnen. In Abbildung 2.1 ist eine Segmentierung des Beispielsignals gezeigt. Da aber auch von Experten die Segmentgrenzen nicht zweifelsfrei festgelegt werden konnen, ist die Abgrenzung der einzelnen Laute gegeneinander im allgemeinen nicht eindeutig definiert.
Die inhiirente Kontinuitat von Sprache macht eine rein datengetriebene Segmentierung ohne Modellwissen praktisch unmoglich. Daher werden heute ausschlieBlich sogenannte "segmentierungsfreie" Methoden auf der Basis von Markov-Modellen zur Spracherkennung eingesetzt. Obwohl das digitalisierte Sprachsignal selbst bereits eine lineare Folge von Abtastwerten darstellt, setzen die statistischen Modelle gesprochener Sprache immer auf einer geeigneten Merkmalsreprasentation auf. Diese versucht, die charakteristischen Eigenschaften sprachlicher Einheiten, die tiberwiegend durch die spektrale Zusammensetzung des Signals gegeben sind, parametrisch zu beschreiben. Da auf dieser Ebene noch keine Segmentierungsinformation vorliegt, muss die Merkmalsextraktion in Bereichen erfolgen, deren Eigenschaften moglichst wenig tiber die Zeit variieren und daher moglichst kurz sind. Andererseits mtissen diese Abschnitte aber auch lang genug sein, damit aussagekraftige spektrale Charakteristika berechnet werden konnen. Man unterteilt das Sprachsignal daher in kurze Abschnitte konstanter Lange von ca. 16 bis 25 ms, die Frames genannt werden. Urn nicht wichtige Information durch diese elementare Segmentierung des Signals an den Randern der Frames zu verlieren, lasst man diese tiblicherweise sich gegenseitig tiberlappen. Als Quasistandard hat sich eine Framerate von 10 ms etabliert. Bei 20 ms Framelange wtirden sich die Signalabschnitte dabei jeweils zur Halfte tiberlappen. Abbildung 2.2 zeigt eine soIche Einteilung eines Sprachsignals in Frames mit 16 ms Lange am Beispiel eines Ausschnitts aus dem aus Abbildung 2.1 bekannten Beispielsignal.
Ftir jeden Frame werden Merkmale berechnet. Man erhalt so eine Folge hochdimensionaler Vektoren kontinuierlicher Merkrnalswerte, die mit den Emissionen eines Hidden-Markov-Modells identifiziert werden. Allen Merkrnalsberechnungsverfahren ist gemeinsam, dass sie ein MaB fUr die Signalenergie verwenden sowie ein abstraktes Modell der spektralen Zusammensetzung des betreffenden Signalausschnitts generieren. Als Quasi-Standard daftir hat sich die ursprlinglich zur Analyse seismischer Signale entwickelte cepstrale2 Analyse etabliert ([Bog 63], vgl. auch [ST 95, S. 58ff] [Hua 01, S. 306ff]). Das sogenannte Model1spektrum charakterisiert implizit die Form des Vokaltrakts bei der Stimmbildung und lasst damit Rlickschliisse auf den artikulierten Laut zu3. Die Kombination der Frameeinteilung eines Sprachsignals und der lokal ausgeftihrten Merkmalsberechnung bezeichnet man als Kurzzeitanalyse. In Abbildung 2.2 sind Ergebnisse eines soIchen Vorgehens beispielhaft dargestellt, wobei als hypothetische Merkmalsextraktionsvorschrift die Berechnung eines geglatteten Leistungsdichtespektrums verwendet wurde.
Durch das Training von Hidden-Markov-Modellen flir akustische Einheiten versucht man die statistischen Eigenschaften der durch die Kurzzeitanalyse erzeugten Merkmalsvektorfolgen nachzubilden. Ublicherweise verfolgt man dabei einen modularen Ansatz zur Beschreibung komplexerer sprachlicher Strukturen. Auf der Basis von Modellen ftir elementare Einheiten wie z.B. Laute
2Begriffe wie cepstrum, saphe oder auch a/anysis wurden von den Autoren als Kunstworter aus spectrum, phase bzw. analysis abgeleitet. 3Fiir eine ausfiihrliche Beschreibung verschiedener Merkmalsextraktionsverfahren siehe z.B. [ST 95, Kapitel 3 S. 45ff1 oder [Hua 01, Kapitel 6 S. 275ff1
2.1 Sprache
23
\0 ms • I
------_ 16ms
.. :I
I
Abb. 2.2 Frameeinteilung des in Abbildung 2.1 markierten Signalausschnitts im Ubergangsbereich zwischen den Lauten I a: I und I xl mit zugehoriger hypothetischer Merkmalsreprasentation.
konstruiert man durch Hintereinanderschaltung Worter. Eine beliebige Abfolge von Wortmodellen aus einem gegebenem Lexikon definiert dann ein Modell fUr sprachliche AuBerungen einer bestimmten Anwendungsdomane. Das Gesamtmodell ist dabei wieder ein Hidden-Markov-Modell. Die Segmentierung einer als Folge von Merkmalsvektoren vorliegenden AuBerung in die entsprechende Wortfolge erhalt man durch Berechnung der optimalen Zustandsfolge durch das Modell. Diese verlauft durch bestimmte Wortmodelle, die per constructionem Teil des AuBerungsmodells sind, so dass man die optimale textuelle Reprasentation leicht angeben kann. Diese wird jedoch im allgemeinen nur eine Naherung des tatsachlich Gesprochenen sein.
Urn bei der Suche nach dieser Losung nicht beliebige Wortfolgen betrachten zu miissen, die unter Umstanden im betrachteten Anwendungskontextzu einem groBen Teil wenig plausibel sein konnen, lassen sich zusatzlich zu der Modellierung auf akustischer Ebene mit Hilfe von Markov-KettenModellen statistische Restriktionen auf symbolischer Ebene einbringen. Man spricht dann von der
24
2 Anwendungen
Verwendung eines sogenannten Sprachmodells. Prinzipielilassen sich flir diesen Zweck auch rein symbolische Verfahren wie z.B. formale Grammatiken verwenden. Allerdings fiihrt die Kombination zweier statistischer Techniken in der Regel zu leistungsfahigeren Gesamtsystemen. Daher hat sich die Kombination von Hidden-Markov-Modellen flir die akustische Modellierung und MarkovKetten-Modellen fiir die Sprachmodellierung im Bereich der automatischen Spracherkennung als Standardvorgehen etabliert.
Die Schwierigkeit einer konkreten Spracherkennungsaufgabe kann anhand der Restriktionen abgeschatzt werden, die fiir die zu erwartenden sprachlichen AuBerungen gelten. Je eingeschrankter, desto einfacher und je variabler, desto schwieriger wird die erforderliche Modellierung. Deutlich vereinfacht wird das Problem, wenn die betrachteten Sprachdaten nur von ein und demselben Sprecher stammen. Man spricht in diesem Fall von sprecherabhiingiger Erkennung. Als sprecherunabhiingig werden dagegen Systeme bezeichnet, die naherungsweise in der Lage sind, AuBerungen aus einem breiten Personenkreis zu verarbeiten. Vereinfachen lasst sich die Erkennung auch durch die Einschrankung des betrachteten Vokabulars. Sollen nur wenige Kommandoworter erkannt werden, kann dies vergleichsweise leicht und zuveriassig geschehen. Die Dekodierung eines umfangreichen Wortschatzes von mehreren 10000 Wortem erfordert dagegen einen drastisch erhohten Aufwand. Daher arbeiten handelsiibliche Diktiersysteme sprecherabhangig, urn auch mit sehr groBen Lexika akzeptable Erkennungsleistungen erbringen zu konnen. Telefonische Auskunftssysteme miissen dagegen sprecherunabhangig sein und verwenden daflir in der Regel ein stark auf die konkrete Anwendung eingeschranktes Vokabular.
Aber nicht nur der Umfang des Wortschatzes beeinftusst die erzielbare Erkennungsleistung. Ublicherweise verwendet man bei groBen Erkennungslexika statistische Sprachmodelle zur Restriktion der moglichen bzw. wahrscheinlichen Wortfolgen. Je nachdem, wie gut diese Einschrankungen wahrend der Modelldekodierung greifen, vereinfacht sich auch das Erkennungsproblem. Besonders gut gelingt dies bei AuBerungen aus klar abgegrenzten Anwendungsgebieten, in denen eventuell auch formalisierte Sprachstrukturen verwendet werden. Daher wurden die ersten kommerziell verfligbaren Diktiersysteme in Anwaltskanzleien und Arztpraxen eingesetzt.
Zusatzlich zum Umfang des Losungsraums beeinftusst auch der jeweilige Sprechstil entscheidend die Qualitat der Erkennungsergebnisse. In Laborexperimenten arbeitet man haufig mit nach gegebenen Texten vorgelesenen Sprachsignalen, die dadurch weniger Variabilitat in der akustischen Auspragung aufweisen als das in spontaner Sprache der Fall ist. Bei dieser nimmt im allgemeinen die Sorgfalt in der Artikulation ab, und Verschleifungen zwischen aufeinanderfolgenden Lauten nehmen zu. In bestimmten Kontexten werden einzelne Laute oder ganze Lautgruppen moglicherweise gar nicht realisiert. AuBerdem konnen spontansprachliche Effekte wie z.B. Wortabbriiche oder Hasitationen auftreten, die natiiriich in der Modellbildung beriicksichtigt werden miissen.
Eine weitere groBe Schwierigkeit flir Spracherkennungssysteme stellt die Veranderung der Umgebungsbedingungen dar, in denen die Signaldaten erfasst werden. Dies kann zum einen den Aufnahmekanal selbst betreffen, der durch die technischen Losungen zur Signalerfassung und die akustischen Eigenschaften des Aufnahmeraumes gegeben ist. Daher wird bei handelsiiblichen Diktiersystemen vielfach das speziell erforderliche Mikrophon dem Programmpaket beigelegt. Auch funktionieren viele Systeme nur in ruhiger Biiroumgebung gut und nicht in einer riesigen Messehalle. In so1chen offentlichen Raumen kommen dariiberhinaus noch SWrgerausche hinzu, die sich gleich in zweifacher Weise negativ auf die Systemleistung auswirken. Zum einen iiberlagem sie das eigentliche Sprachsignalund beeinftussen damit die extrahierten Merkmalsreprasentationen. Zum anderen
2.2 Schrift
25
nimmt auch der jeweilige Sprecher das Storgerausch wahr und verandert darautbin im allgemeinen seine Artikulation. Dieses Phanomen wird nach seinem Entdecker als Lombard-Effekt bezeichnet [Lorn 11]. Daher stellt die robuste Erkennung sprachlicher AuBerungen im Fahrzeug, wo starke und teilweise nicht vorhersehbare Nebengerausche auftreten, eine besondere Herausforderung ftir aktuelle Spracherkennungssysteme dar.
In der jahrzehntelangen Forschung auf dem Gebiet der Spracherkennung wurden durch immer weitere Verfeinerungen bei den statistischen Methoden sowie durch spezielle anwendungsabhangige Techniken beachtliche Leistungen im Umgang mit den vielfaltigen Schwierigkeiten der automatischen Erkennung gesprochener Sprache erbracht. Dennoch existiert heute kein System, das beliebige AuBerungen beliebiger Personen zu einem beliebigen Thema in beliebiger Umgebung erkennen konnte - aber diese Anforderung erfilllt selbst das menschliche Vorbild nicht. Doch auch bei weniger ehrgeizigen Zielen wie der Erstellung sprecherabhangiger Diktiersysteme sind die tatsachlichen Systemleistungen begrenzt und bleiben weit hinter den Versprechungen mancher Hersteller zurtick [Fla 00]. Das Problem der automatischen Spracherkennung ist daher noch keineswegs ge16st, und es wird auch in Zukunft groBer Forschungsanstrengungen und moglicherweise neuartiger Verfahren bedtirfen, urn Systeme zu schaffen, die naherungsweise die Leistungsfahigkeit eines menschlichen Zuhorers erreichen.
2.2 Schrift
Bei Schrift denkt man im europaischen Kulturkreis immer zuerst an Buchstabenalphabete und speziell an die weit verbreitete Lateinscheift, in der auch dieses Werk abgefasst ist. Alphabetschriften folgen im wesentlichen dem phonographischen Prinzip, bei dem durch die vergleichsweise wenigen Zeichen der Scheift die Lautstruktur der betreffenden Sprache wiedergegeben wird4 . Selbst wenn dieses Vorgehen filr einen westlichen Leser aufgrund seiner kulturellen Pragung als das einzig sinnvolle erscheint, existieren auch heute noch vollig andere Herangehensweisen bei der Verschriftung von Sprache5• Prominentestes Beispiel ist die chinesische Schrift, die nach dem Prinzip der Logographie arbeitet. Dabei steht jedes der komplexen Schriftsymbole filr ein bestimmtes Wort der chinesischen Sprache. Es bedarf daher wenigstens einiger tausend Zeichen, urn Texte der chinesischen Alltagssprache z.B. in den Printmedien zu schreiben. Dass eine solche in unseren Augen komplizierte Schriftform auch im Computerzeitalter nicht durch eine Alphabetschrift verddingt wird, zeigt eindrucksvoll das Beispiel des Japanischen, das als Schrift einer Hochtechnologienation selbstverstandlich auch im Umgang mit Computem verwendet wird. Japanische Texte werden in einer Mischung aus chinesischen Schriftsymbolen (Kanji) ftir die Wiedergabe von Wortstammen und zwei daraus durch Vereinfachung abgeleiteten Silbenschriften geschrieben, die wieder dem phonographischen Prinzip folgen. Zeichen der Hiragana-Schrift dienen zur Schreibung grammatikalischer Elemente; in Katagana schreibt man Namen und Fremdworter.
Geschriebene Texte konnen unabhangig yom jeweiligen Schriftsystem entweder maschinell erstellt, d.h. gedruckt werden, oder handschriftlich mit Stift oder Pinsel zu Papier gebracht werden. Dabei
4Durch die historische Entwicklung der Sprachen ist die Beziehung zur jeweiligen Aussprache in der heutigen Schreibung nur mehr oder weniger explizit erhalten geblieben. 5Eine umfassende Ubersicht tiber historische und heute noch gebrliuchliche Schriftsysteme sowie deren Entwicklung und Beziehung untereinander gibt [Haa 91J.
26
2 Anwendungen
existieren fiir beide Formen der Schrift unterschiedliche Schriftstile. Bei der maschinellen Schreibung ist die Form der Zeichen yom Prinzip her nicht eingeschrankt. Dagegen will man bei Handschrift diese auch moglichst einfach und fllissig zu Papier bringen konnen. Daher gibt es neben der Druckschrift eines bestimmten Schriftsystems auch eine fiir die manuelle Schreibung angepaBte Kursivschrift.
1m Gegensatz zur Erkennung gesprochener Sprache erfolgt die automatische Verarbeitung von Schrift nur zum Teil im Kontext der Mensch-Maschine-Kommunikation. Vielmehr liegen die Ursprlinge der Technologie und ein GroBteil der heute industriell relevanten Anwendungen im Bereich der Automatisierungstechnik. Da wir im Rahmen dieses Buchs nicht das Ziel verfolgen wollen, die automatische Schriftverarbeitung umfassend fiir aile noch existierenden Schriftsysteme zu behandeln, wollen wir uns im folgenden auf die Betrachtung der gelaufigen Alphabetschriften und dabei als typische Vertreterin die Lateinschrift beschranken. Flir eine Darstellung der Techniken, die zur Verarbeitung von z.B. japanischen, chinesischen oder arabischen Texten zum Einsatz kommen, sei der interessierte Leser auf die entsprechende Spezialliteratur verwiesen (vg\. z.B. [Bun 97, Kapitel 10 bis 15]). Das Vorgehensprinzip bleibt dabei im wesentlichen unverandert. Man tragt jedoch bei der Auswahl von Methoden und der Kombination der Verarbeitungsschritte der jeweils speziellen Auspragung des Schriftbildes Rechnung.
Die klassische Anwendung von automatischer Schriftverarbeitung ist die sogenannte optische Zeichenerkennung (eng\. optical character recognition), die meist mit dem aus dem entsprechenden englischsprachigen Begriff abgeleiteten Acronym OCR bezeichnet wird (vg\. z.B. [Mor 98]). Dabei ist es das Ziel, maschinell geschriebene Texte, die optisch erfasst und anschlieBend digitalisiert wurden, automatisch zu "lesen", d.h. das Schriftabbild in eine rechnerinterne symbolische Reprasentation des Textes zu liberfiihren. Die Ausgangsdaten sind also Abbilder von Dokumentseiten wie z.B. dieser hier, die mit Hilfe eines Scanners bei einer typischen Auflosung von 300 bis 2400 Punkten pro Zoll in ein digitales Bild umgewandelt werden. Aufgrund der bildhaften Natur der Eingabedaten dominieren im Bereich der OCR daher Methoden der automatischen Bildverarbeitung.
Vor Beginn der eigentlichen Texterkennung ist in jedem Faile eine Analyse des Dokumentlayouts erforderlich. Dabei werden innerhalb des vorliegenden Seitenabbildes Textbereiche, aber auch andere Elemente der Dokumentstruktur wie z.B. Uberschriften oder Graphiken identifiziert. AnschlieBend konnen die Textbereiche in Paragraphen, einzelne Zeilen und wegen der normalerweise hohen Prazision bei der Erstellung maschinengeschriebener Texte in der Regel auch in einzelne Zeichen segmentiert werden. Sind die Abbilder der Schriftsymbole auf diese Weise isoliert worden, konnen sie mit beliebigen Techniken der Musterklassifikation auf ihre symbolische Reprasentation abgebildet werden (vg\. z.B. [Sch 77]). Die Ergebnisse der Klassifikation werden in der Regel einem oder mehreren Nachbearbeitungsschritten unterzogen. Dabei wird versucht, durch die Einbeziehung von Kontextrestriktionen z.B. in Form eines Lexikons, Fehler auf Zeichenebene soweit wie moglich zu korrigieren (vg\. z.B. [Den 97]).
Die Komplexitat der Verarbeitungsaufgabe wird, wie im Bereich der automatischen Spracherkennung auch, durch die Variabilitat der zu erwartenden Eingabedaten bestimmt. Da die Verarbeitung hauptsachlich auf Zeichenebene erfolgt und der Wort- oder Dokumentkontext lediglich bei der Nachbearbeitung eingebracht wird, ist die GroBe des verwendeten Lexikons von untergeordneter Bedeutung. Die Variabilitat der Daten ergibt sich zum einen durch Unterschiede im jeweiligen Schriftbild, wie es durch den Druck erzeugt wird. Zum anderen verandern SWrungen bei der optischen Erfassung der Dokumente das Aussehen einzelner Zeichen und Textabschnitte unter
2.2 Schrift
27
Umstanden ganz entscheidend. 1m Druckprozess selbst kann der Schriftschnitt (normal, fett oder kursiv), der Schrifttyp (z.B. Times, Helvetica oder Courier) oder die BuchstabengroBe variiereno Ungleich groBere Schwierigkeiten fUr die automatische Verarbeitung ergeben sich, wenn das Schriftabbild nur in schlechter Qualitat erfasst werden kann. Dies kann z.B. durch Alterung oder eine vergleichbare Beeintrachtigung wie z.B. Verschmutzung des Ausgangsdokuments selbst bedingt sein. Aber auch durch die wiederholte Reproduktion oder Dbertragung eines Dokuments z.B. per Fax oder mit Hilfe von Kopiergeraten wird die mogliche Qualitat der Ausgangsdaten fUr die automatische Zeichenerkennung reduziert. In diesem FaIle ist eine Segmentierung auf Zeichenebene in der Regel nicht mehr mit der erforderlichen Zuverlassigkeit moglich, so dass bei der Verarbeitung solcher "gest6rter" Dokumentabbilder (engl. degraded documents) segmentierungsfreie Methoden auf der Basis von Markov-Modellen wesentliche Vorteile gegeniiber klassischen Verfahren der OCR bilden (vgl. z.B. [Elm 98]).
Wesentlich schwieriger wird das Problem der automatischen Zeichenerkennung auch, wenn die betrachteten Texte nicht maschinell, sondern handschriftlich erstellt wurden. Insbesondere die Verwendung von Kursivschrift, die bei Alphabetschriften in der Regel die einzelnen Zeichen zu einem durchgehenden Schriftzug verbindet, macht eine zuverlassige Segmentierung auf Buchstabenebene praktisch unmoglich. Daher dominieren in diesem Bereich mittlerweile segmentierungsfreie Verfahren auf der Basis von Markov-Modellen. Allerdings ist das maschinelle Lesen groBerer handschriftlicher Dokumente wohl auch wegen der enormen Schwierigkeit dieser Aufgabe derzeit nicht anwendungsrelevant. Auch im wissenschaftlichen Bereich existieren zur Zeit nur wenige diesbeziigliche Forschungsvorhaben. Ein Beispiel eines historischen Briefes in Kursivschrift zeigt Abbildung 2.3. Dagegen sieht man in Abbildung 2.4 ein typisches Dokument, wie es zum Aufbau eines groBen Korpus handschriftlicher Texte auf Initiative der Universitat Bern erhoben wurde [Mar 99a].
Die Komplexitat bei der Verarbeitung handschriftlicher Dokumente entsteht durch die gegeniiber maschinell geschriebenen Texten ungleich hOhere Variabilitat des Schriftbildes. Die einzelnen Buchstaben unterscheiden sich, ahnlich wie Laute in gesprochener Sprache, auch bei wiederholter Realisierung durch ein und dieselbe Person, je nach Vorkommenskontext und am deutlichsten zwischen unterschiedlichen Schreibern. Da ohne geeignete Restriktion der moglichen Buchstabenfolgen bei der automatischen Erkennung handschriftlicher Texte keine befriedigenden Ergebnisse zu erzielen sind, ist auch der verwendete Wortschatz bzw. vergleichbares Kontextwissen von groBer Bedeutung.
Eine industriell besonders wichtige Anwendung der automatischen Schrifterkennung ist das maschinelle Lesen von Anschriften in Postverteileranlagen. Hierbei entsteht die wesentliche Schwierigkeit durch den auch in der heutigen Zeit noch groBen Anteil handgeschriebener Adressen. In der Praxis lasst sich deswegen nur teilweise eine automatische Sortierung der Vertriebsstiicke erreichen, weil Erkennungsfehler durch fehlgeleitete Post enorme Kosten verursachen konnen. Man nimmt daher eine sehr hohe Riickweisungsrate in Kauf, urn die Fehlerrate solcher Systeme so gering wie moglich halten zu konnen. Die zuriickgewiesenen Vertriebsstiicke miissen dann manuell zugeordnet werden.
Leistungsflihige Verfahren zur automatischen Adressauswertung sind insbesondere fiir maschinell geschriebene Postanschriften schon seit vielen lahren im praktischen Einsatz. Die Qualitat der Ergebnisse hangt dabei aber nicht allein von einer moglichst guten Klassifikationsleistung auf Zeichenebene abo Es ist dariiberhinaus extrem wichtig, strukturelle und inhaltliche Beziehungen zwischen den einzelnen Elementen einer Postanschrift, wie Postleitzahl, Orts- und StraBenname sowie Hausnummer und ggf. Zustellbezirk, in geschickter Weise auszuniitzen. Nach der Einfiihrung eines neuen automatischen Anschriftenlesesystems wird in den USA derzeit mehr als die Halfte der hand-
28
2 Anwendungen
# " %1-
1'17"-
~d.4r eY;d.u(
~../ -47~.t...;... J',I/J",,~~/v'1/-­
*. ".t _,~_* rn~·J ..t~ 4n£c_~~_U --. 6. -«'-";-c
t!l,../<~. ~. "'""~- ...:. .9i.:a'c.- .
.Id~,.;.., ........ .t:1.,....;f'- -;, I'u.~~; ~..,,~~ _..,~
.;., ..f,., .;?;t~;,..t •tJ-/7 J , l'':--".e~"..,..;..., ~,-... J&J-.w,~
,L'tZ n .",:~.u. ,d,.;. ;';";'-"G:r, /£:-.#'v.t ....._.o:e.. ~r _"L .£~_4-­ (,J, .tJ Mu .c.- O,d_eelX'.... ,(,~~ ,..:... ~ '.,/.,.('_ J::'u!.;,.. .c-.
"u'rh,;',r-. ~/ ".,,':"c a..,fi~e. J,./.!..t:.f ..........,;.. ,./ ~ .~..;4~u; $ .
~,.,/e·'/..·~d a"'l'''d'...(...~ 'n ..xu" t4J~/'"J..., ",:f..-.at/~_ ._. ~._
d""';,P- ~ t?-....-.~&. 'u<",.....1 ..?IC .ur.t'-.. ~.... ~'k_ __.~....
.x,. d .6 ~'e.A. ~;",,;_~ _I~ ~&. • 4la t1Sd4 a4 ,-d ,.,....;. I~, -. ~ _u•.(u/_ Fc.,-.,!ur ___
,/!tU'_, ~d~ ~i~'~;,"""'u...I !i1c__ . 4J &U/""--.; / ...... 'c /.-...v...
.. # __ __ .... ..... .:.(..., 1-. ~L e..c d-. 1£ f." ~
~ ~~ .---..~_ ~
;;. . -"'~"""e. .L_, ...;.... t:f),..-f':r---; /",,,,;"h~<.I"" ...r..... f-.....: .eli' .yJu_
"'" L,_'e~<-"",~ ",.......... -'- ,/,.....,-., 't. ~J #..te. __ "';"")'< .,.,A.......-
~'~04 E....:f._ ~ .~~ ~,~~e.(/-~ .r.;w'U,,(_'t!.- ~~/&. ~/r~... ~<-
"" ~. > ,(......,. ,-.It? d-. I~ -"~/~ K,';4'I, J _ ~ ~'....I_ ...."."';..'"
;"..,L/ <q .f.....,~/~ ~u 1'/-rl!...:,L", ___".'
7'teu.,(",. ~ "...~~ a!,.~ • .:s~'~/~.1 ~Ir~eh., ~~,n,_~
f·--L....;,-_ ~ ""'-. .",".d,,~..u__ c2-/.,.f......,-e. ......... ...,;., -..- _~_
~--, ,.",,/,(/,Ad.uu7 c!_ ';"~c;';...-7 U-. .,f~-w~-:-
Abb. 2.3 Beispiel eines digitalisierten handschriftlichen Dokurnents. Es handelt sich dabei urn einen Brief der Marie von Ebner-Eschenbach an Herrman von Reischach, Wien, 30. Janner 1876, der aus [May 99, S. Ill] entnommen wurde (Abdruck mit freundlicher Genehmigung des Philipp Reclam Jun. Verlags).
2.2 Schrift
29
Sentence Database
C03·Q03
TI.a.U i. DO~ • lUmed P'-Y. III ba.t bKD «Incch"Cd clll'o,~hgu' in ltortu. ohut.'" ,·int UUl4 .nd
....iD and . .&in it I. 'hl!' viloAl quaiitlf Q( ,111' uCJry. fUld daft ulArria:yr uf Ill. CI'illt1U
chUlltU'.... to cb.clr but-kgroUutJ. wthkh brill"" llt fillU "" ".yic.lly IV lili . In FUll)'. whic:b
,,1.0 1.11lJ1. it. '_""w;"1"G tomOrrow. tbe director. ,.ir. JOtbul\ Loglm. fUfC!'ITI[lud hut (Nt ~
or • &.cr Cl"G&CO the armc.phue
cil)".
#ud J-Itlh ..., n¢ a
~. # /1r.P.J ,f,u.fl ~'*"
~Mul -</) ~ t?/?I.( ?VUMa / cwu:-f ~
~ ~ .# ~ .fk ~ fU4';I-~u oj ..;/c£
4~/ and ,,Ik ~R o(?h CL/f./ral ~
4 1vt 4c7 -f/ud -da?~ ~
.fk
fUm /JI7 ~ "w- ¥. 1/7 7eu~ ~
aJ.u7 ~ 46 ~ 471",6HtMJ" 4k ~.hr~
.b J~ ~" ,z&":P~ ~ tIcu4d -h
'~Ak~~ ot4at
Abb.2.4 Beispieldokument aus der durch das Institut fUr Informatik und Angewandte Mathematik der UniversiUit Bern erhobenen Stichprobe handschriftlicher Dokumente [Mar 99a]. 1m oberen Teil der Seite ist der zu schreibende Textabschnitt und eine Identifikationsnumrner maschinell vorgedruckt. Darunter findet sich dann die jeweilige handschriftliche Version (Abdruck mit freundlicher Genehmigung).
30
2 Anwendungen
Abb. 2.5 Beispiel eines handschriftlich ausgefiillten Uberweisungsformulars, bei dem einzelne Druckbuchstaben in GroBschreibung in dafiir vorgesehene Felder eingetragen werden miissen.
geschriebenen Adressen automatisch ausgewertet, wobei die geschatzte Fehlerrate unter 3 Prozent liegt [D' A 00] .
AusschlieBlich mit der Verarbeitung handschriftlicher Eingaben befassen sich Verfahren zur automatischen Auswertung von Formularen. Die Komplexitat der Erkennungsaufgabe kann dabei durch geeignete technische MaBnahmen zur Einschrankung der Variabilitat des Schriftbildes deutlich reduziert werden. Immer vorgesehen werden spezielle Felder zur Schreibung einzelner Worter oder auch kurzer Phrasen. AuBerdem wird der Schriftstil haufig auf die ausschlieBliche Verwendung von Druckbuchstaben (engl. hand printed characters) eingeschrankt, von denen meist nur die GroBschreibung verwendet werden darf. Den eingeschranktesten Schreibstil erhalt man, wenn zusatzlich pro Buchstabe ein einzelnes Schriftfeld vorgeben wird. Abbildung 2.5 zeigt dies am Beispiel eines Uberweisungsformulars.
Anders als in Europa spielen vor allem im amerikanischen Zahlungsverkehr Schecks eine herausragende Rolle. Es existiert daher eine Vielzahl von Ansatzen zur automatischen Auswertung des handschriftlich eingetragenen Zahlungsbetrags (engl. legal amount) sowie seiner numerischen Entsprechung (engl. courtesy amount) und des Ausstellungsdatums (vgl. z.B. [Lam 95]). Bei dieser Erkennungsaufgabe ist zwar das Lexikon auf wenige Eintrage wie Zahlworter und Ziffern beschrankt. Aus diesen diirfen aber langere Folgen ohne nennenswerte Abfolgerestriktionen gebildet werden. Der verwendete Schriftstil unterliegt ebenfalls keinen Restriktionen. Es ist also die Verwendung handgeschriebener Druckbuchstaben, von Kursivschrift oder auch einer beliebigen Mischung dieser
2.2 Schrift
31
0., ~~rCf!0 ••••• ,
0 0 0
0
0
oo~ 0 0
0
o
• • • 00
~...
r • •
I~•
t:.. t:.V,-.:: ~
.....0 •
..t...•• ,
• ••
'\~ ..fi•.~• ...
••••
_
00
Abb. 2.6 Beispiel fUr die on-line erfasste Stifttrajektorie des handschriftlichen Wortes "Bielefeld". Die GroBe der Kreise urn die jeweilige Stiftposition kodiert bei den schwarz gezeichneten pen-down Schriftztigen den Anpressdruck und sonst die Entfemung zur Schreibunterlage.
Stile moglich. Man spricht in diesem FaIle auch von uneingeschrankter Handschrift (engl. unconstrained handwriting).
Allen bisher vorgestellten Methoden zur Schriftverarbeitung ist gemeinsam, dass Dokumente nach ihrer Fertigestellung digital erfasst und dann unabhangig von ihrem Entstehungsprozess weiterverarbeitet werden, was man als sogenannte off-line (Hand-)Schriftverarbeitung bezeichnet. Zur automatischen Verarbeitung handschriftlicher Dokumente existieren im Gegensatz dazu auch sogenannte on-line Methoden, bei denen die Stiftbewegung bereits wahrend des Schreibvorgangs aufgezeichnet wird. Hierzu sind spezielle Sensoren wie z.B. drucksensitive Tabletts oder LCD-Anzeigen erforderlich und im allgemeinen auch die Verwendung spezieller Schreibgerate. Ais Reprasentation des geschriebenen Textes erhalt man im wesentlichen eine Folge zweidimensionaler Messpunkte der Stiftposition, die die Trajektorie des Stiftes wahrend des Schreibvorgangs kodieren. Bei einfachen Geraten, wie sie z.B. in sogenanten PDAs (engl. personal digital assistant) zum Einsatz kommen, erhalt man diese Positionsmessungen nur, wenn der Stift die Sehreibunterlage bertihrt. Man spricht dann von sogenannten pen-down Sehriftztigen. Wird der Stift dagegen abgehoben (pen-up), konnen nur aufwendigere Graphiktabletts mit Hilfe induktiver Verfahren die Bewegung eines daflir spezialisierten Stifts auch in einer kleinen Umgebung der Sehreibunterlage noch verfolgen. Solche Gerate liefem zudem tiblieherweise den Anpressdruck und auch die Neigung der Stiftspitze zusatzlich zu den Positionsmessungen. Abbildung 2.6 zeigt am Beispiel des Wortes "Bielefeld" eine mogliche Stifttrajektorie. Dabei wird der Anpressdruek bzw. die Hohe der Stiftspitze tiber der Schreibunterlage durch die GroBe der Kreise urn die einzelnen Stiftpositionen angegeben.
Gegentiber der off-line Schriftverarbeitung haben on-line Methoden den Vorteil, dass sie die zusatzlich verfligbare zeitliche Organisation des Sehreibvorgangs im Erkennungsprozess bertieksichtigen konnen. Dadurch ist z.B. ausgeschlossen, dass sich benachbarte Zeichen im Sehriftbild tiberlappen und daher bei der automatischen Segmentierung nieht oder nur schwer trennbar sind. Wesentlieh ist die Dynamikinformation aueh flir die Verifikation von Unterschriften. Sie reprasentiert eine hochgradig sehreiberspezifische Eigenart der Unterschrift, die sich auch von Experten nicht durch Naehahmung eines vorliegenden Schriftbildes falschen lasst.
Das Hauptanwendungsfeld flir on-line Handschrifterkennung ist jedoch die Mensch-Maschine-Interaktion. Besonders zur Bedienung extrem kleiner portabler Rechner, die mit einer Tastatur nicht mehr sinnvoll moglich ware, hat sich diese Form der Texteingabe und Geratesteuerung etabliert. Allerdings wird das Problem in der Regel so weit wie moglich vereinfacht, urn mit den beschrank-
32
2 Anwendungen
ten Ressourcen eines PDA, Organizers oder Smart-Phones befriedigende ErkennungsqualWiten bei gleichzeitig ausreichend schneller Reaktionszeit erzielen zu konnen. So setzt man beim PalmPilot und vergleichbaren Geraten derzeit auf eine Erfassung lediglich einzelner Schriftzeichen in speziell dafur vorgesehenen Eingabefeldem. AuBerdem muss dabei ein speziell fur die Belange der automatischen Erkennung optimierter Schriftstil verwendet werden. Bei leistungsfahigeren Geraten ist in der Regel auch die Eingabe ganzer handgeschriebener Worter moglich.
Inspiriert durch den Erfolg Markov-Modell-basierter Verfahren im Bereich der Erkennung gesprochener Sprache wurde in letzter Zeit das prinzipielle Vorgehen dieser Technik auch auf Probleme der automatischen Schrifterkennung ubertragen. Ais segmentierungsfreie Verfahren kommen diese Techniken vorwiegend dort zum Einsatz, wo das "klassische" Vorgehen der OCR, zuerst auf Zeichenebene zu segmentieren und anschlieBend zu klassifizieren, zu unzuverlassig ist oder komplett fehlschlagt. Daher werden Markov-Modelle hauptsachlich zur Segmentierung handschriftlicher Dokumente im on-line und off-line Bereich eingesetzt und nur vereinzelt zur Verarbeitung maschinell geschriebener Texte. Almlich wie bei der automatischen Spracherkennung setzt man HiddenMarkov-Modelle zur statistischen Beschreibung des Schriftbildes einzelner Buchstaben oder ganzer Worter ein und Markov-Ketten-Modelle zur Restriktion der moglichen Folgen elementarer Einheiten auf Zeichen- oder Wortebene.
Grundvoraussetzung fur die Anwendbarkeit dieser Verfahren ist es, dass sich die betrachteten Signaldaten als lineare Folge reprasentieren lassen. 1m Bereich der on-line Handschriftverarbeitung ist dies leicht moglich. Durch den zeitlichen Verlauf des Schreibprozesses selbst ist eine zeitliche Ordnung der Positionsmesswerte gegeben, die die entsprechenden Sensoren liefem. Die Zeitachse des Signals lauft daher gewissermaBen entlang des Schriftzugs. Dann lassen sich wie bei der Kurzzeitanalyse von Sprachsignalen lokal charakteristische Eigenschaften durch Merkmalsvektoren beschreiben. Dabei werden hauptsachlich Formeigenschaften der Schriftlinie wie Schreibrichtung oder Kriimmung ausgewertet. Die Schreibgeschwindigkeit wird dagegen in reinen Erkennungssystemen in der Regel normiert, urn durch unterschiedliche Schreiber verursachte Variationen der Signalcharakteristik ausschlieBen zu konnen.
Schwieriger ist es, ein vergleichbares Vorgehen fUr die Linearisierung von off-line Dokumenten zu definieren, da es sich hier prinzipiell urn zweidimensionale bildhafte Daten handelt. Allerdings kann man in der Regel mit groBer Sicherheit eine Segmentierung des betrachteten Dokuments in einzelne Textzeilen erzeugen. Bei der Analyse von Formularen ist die Isolation der Feldinhalte, die in der Regel nur einzelne Worter oder Phrasen umfassen, noch einfacher moglich. Man kann dann eine hypothetische Zeitachse parallel zur Textrichtung definieren. Entlang dieser wird dann versucht, lokale Eigenschaften des Schriftbildes durch Merkmalsvektoren zu beschreiben. Man zerlegt zu diesem Zweck eine Textzeile ublicherweise in eine Folge von teilweise uberlappenden schmalen Bildausschnitten, die damit yom Prinzip her den aus dem Bereich der Spracherkennung bekannten Frames entsprechen. Fur jedes dieser Fenster wird dann eine Merkmalsreprasentation erzeugt. Allerdings existiert im Bereich der off-line Schriftverarbeitung hierfiir kein allgemein anerkanntes Verfahren. Vielfach werden lokale strukturelle Eigenschaften berechnet, wie z.B. die Anzahl der Linienenden oder Bogen, die in einem bestimmten Schrift-Frame liegen. Die Folge der so erzeugten Merkmalsvektoren wird dann - wie bei der Spracherkennung - mit den Emissionen der HiddenMarkov-Modelle fUr Zeichen oder Worter identifiziert.
2.3 Biologische Sequenzen
33
2.3 Biologische Sequenzen
Die Erbinformation aller lebenden Organismen, die ihr Wachstum, ihren Stoffwechsel und zu einem groBen Teil auch ihr Verhalten beeinftusst, ist in einer symbolischen Sequenz kodiert. Dabei handelt es sieh in den meisten Hillen urn das Makromolekul Desoxyribonukleinsiiure (DNA)6, dessen Strlinge aus einer Folge sogenannter Basen bestehen. Es existieren nur vier verschiedene solcher Basen (Adenin, Guanin, Cytosin und Thymin), die paarweise komplementar sind, und daher zuslitzlich zu den chemischen Bindungen innerhalb eines DNA-Strangs auch Paarbindungen ·zu anderen Basen eingehen konnen. Damit entsteht die "leiterformige" Struktur der doppelstrlingigen DNA. Da die Paarbildung der Basen eindeutig ist, enthlilt bereits ein einzelner DNA-Strang die vollstlindige Erbinformation. 1m Doppelstrang ist sie daher redundant kodiert.
Bei hOher entwiekelten Lebewesen wie z.B. Sliugetieren liegt die DNA nieht als eine komplette Sequenz vor, sondem ist auf sogenannte Chromosomen verteilt. Der Mensch besitzt davon 23 Paare, die jeweils Erbinformationen von vliterlicher bzw. mutterlicher Seite enthalten. Die Gesamtheit der DNA-Strlinge in allen Chromosomen bezeiehnet man als das Genom. Jede Zelle eines Lebewesens enthlilt eine identische Kopie dieser gesamten Erbinformation. Der Umfang des Genoms steht in grobem Zusammenhang mit der Komplexitlit des jeweiligeri Lebewesens. Wlihrend die Erbinformation von Bakterien nur einige Millionen Basenpaare enthlilt, umfasst das menschliche Genom ca. 3 Milliarden Basenpaare.
Allerdings hat der GroBteil der DNA-Sequenz keine oder keine bisher verstandene zellbiologische Funktion. In diesem "uberftussigen" Zusatzmaterial sind die elementaren Informationseinheiten der Erbsubstanz eingebeUet - die sogenannten Gene. Deren relevante "Nutzinformation", die die Funktionalitat eines Gens kodiert (eng\. coding region) ist in der Regel in mehrere sogenannte Exons aufgeteilt, die von Introns unterbrochen werden. Man geht derzeit davon aus, dass das menschliche Genom ca. 30000 bis 40000 Gene enthlilt [IHG 01].
Zur Steuerung der meisten zellbiologischen Funktionen werden Gene in Proteine "ubersetzt" in einem Prozess, den man als Expression bezeichnet. Die je nach Bedarf gebildeten Proteine beeinftussen dann den Stoffwechsel sowie das Wachstum der Zelle und steuem ihre Vermehrung bei der Zellteilung.
Urn ein bestimmtes Gen zu exprimieren, wird zuerst die auf der doppelstrlingigen DNA vorliegende Erbinformation abgelesen und in die liquivalente Darstellung der einstrlingigen Ribonukleinsiiure (RNA) umgesetzt, die auch eine Sequenz von Basen darstellt. Dieser Vorgang, den man als Transkription bezeichnet, beginnt vor der eigentliehen DNA-Sequenz, die die Information eines bestimmten Gens enthlilt, in einer sogenannten Promoter-Region. In der entstehenden Roh-Version der RNA ist allerdings die kodierende Region eines Gens im allgemeinen noch durch Introns ohne bekannte Funktion unterbrochen. Daher wird die RNA in einem anschlieBenden Modifikationsprozess "gereinigt" wobei die Introns entfemt werden. Die bereinigte RNA bezeiehnet man als messenger RNA oder kurz als mRNA.
Aus der mRNA wird schlieBlich in einem weiteren Umsetzungsprozess, den man als Translation bezeichnet, ein bestimmtes Protein erzeugt, das letztendlich die Funktionalitlit des zugrundeliegenden Gens realisiert. 1m Gegensatz zu DNA und RNA bestehen Proteine aus einer Folge von 20
6Anstatt des deutschsprachigen Akronyms DNS wollen wir hier die gebrliuchlichere "intemationale" Abktirzung DNA verwenden. Sie ergibt sich durch die englische Entsprechung acid von "Sliure".
34
Aminosauresequenz
MALSAEDRALVRALWKKLGSNVGVYTTEALERTFLAFPATKTYFSHLDLS PGSSQVRAHGQKVADALSLAVERLDDLPHALSALSHLHACQLRVDPASFQ LLGHCLLVTLARHYPGDFSPALQASLDKFLSHVISALVSEYR
2 Anwendungen
DNA-Sequenz
atggcgctgt ccgcggagga ccgggcgctg gtgcgcgccc tgtggaagaa gctgggcagc aacgtcggcg tctacacgac agaggccctg gaaaggacct tcctggcttt ccccgccacg aagacctact tctcccacct ggacctgagc cccggctcct cacaagtcag agcccacggc cagaaggtgg cggacgcgct gagcctcgcc gtggagcgcc tggacgacct accccacgcg ctgtccgcgc tgagccacct gcacgcgtgc cagctgcgag tggacccggc cagcttccag ctcctgggcc actgcctgct ggtaaccctc gcccggcact accccggaga cttcagcccc gcgctgcagg cgtcgctgga caagttcctg agccacgtta tctcggcgct ggtttccgag taccgctga
Abb.2.7 Ausschnitt aus der Arninosauresequenz und der zugrundeliegenden DNA-Sequenz des Proteins Hamoglobin gemiiB der SWISS-PROT-Datenbank [Bai 00]. Einzelne Arninosauren sind durch GroBbuchstaben, Basen durch Kleinbuchstaben kodiert.
verschiedenen Aminosiiuren. In der mRNA-Sequenz kodiert ein Tripel von Basen - ein sogenanntes Codon - eine bestimmte Aminosaure7• Durch spezielle Start- und Stop-Codons wird kontrolliert, tiber we1chen Bereich der mRNA sich der Translationsprozess erstreckt. Nach der Erzeugung der Aminosauresequenz bilden Proteine durch Faltung eine charakteristische dreidimensionale Struktur aus, die einen wesentlichen Teil ihrer Funktionalitat ausmacht. Am Beispiel des Hamoglobin zeigt Abbildung 2.7 eine Teilkette der Aminosauresequenz eines Proteins sowie deren Darstellung als Folge von Codons auf der Ebene der DNA.
1m Gegensatz zu Sensorsignalen, die immer mit Messungenauigkeiten behaftet sind, lassen sich die symbolischen Folgen von DNA-Sequenzen oder Proteinen vom Prinzip her exakt angeben. Daher konnte man annehmen, dass symbolische und regelbasierte Verfahren zur Genomanalyse vollstandig ausreichen. Allerdings bereitet die Sequenzierung eines Genoms in der Praxis enorme Schwierigkeiten (vgl. [Ewe 01, Kapitel5, S. 147ff]). Daher kann auch nach Abschluss des "Human-GenomProjekts" die Erbinformation der untersuchten menschlichen Zellen noch nicht vollstlindig und mit letzter Sicherheit angegeben werden. Zudem ist die genetische Information in der Folge der Basenpaare nicht eindeutig kodiert und unterliegt vielfaltigen zufalligen Variationen innerhalb einer Familie von Organismen und auch innerhalb einer Spezies. Noch weitgehend unbekannt ist daher bei komplexen Genomen wie dem menschlichen die genaue Anzahl und Position der einzelnen Gene. Bei den exprimierten Proteinen ist es auBerdem wesentlich flir das Verstandnis ihrer Wirkungsweise, das sogenannte Expressionsmuster zu betrachten, d.h. unter we1chen Bedingungen sie aus den jeweiligen Genen erzeugt werden, und die ausgebildete dreidimensionale Struktur zu untersuchen. Diese kann sich in funktional vergleichbarer Weise aus unterschiedlichen Aminosauresequenzen ergeben.
Die eben aufgezeigten - aus heutiger wissenschaftlicher Sicht - zum groBen Teil zufalligen Variatio-
= 7Die Entsprechung zwischen Codons und Aminosauren ist nicht eindeutig, da bei 4 Basen 43 64 mogliche Tripel existie-
reno
2.3 Biologische Sequenzen
35
nen innerhalb biologischer Sequenzen haben dazu geftihrt, dass vorwiegend statistische Methoden zu deren Untersuchung und Modellierung eingesetzt werden.
Je nachdem auf welcher Datengrundlage die Analyse genetischen Materials ansetzt, sind verschiedene Verfahrensschritte relevant. Geht man VOn sogenannter genomic DNA, also gewissermaBen roher Erbinformation aus, so mtissen zuniichst die kodierenden Regionen VOn Genen gefunden und die dort vorliegenden DNA-Sequenzen anschlieBend - wie bei der Erstellung der mRNA - VOn Introns gereinigt werden.
Werden zu diesem Zwecke Markov-Modell-basierte Verfahren eingesetzt, so erstellt man einzelne Hidden-Markov-Modelle ftir Promoter-Regionen sowie Exons und Introns. Eine Segmentierung der betrachteten DNA-Sequenz erlaubt es dann, Gene zu lokalisieren und deren codierende Region in bereinigter Darstellung zu extrahieren (vgl. [Hau 96, Kro 98]). Aber auch auf der Basis VOn Markov-Ketten-Modellen, die Restriktionen ftir das Vorkommen einzelner Basen in verschiedenen genetischen Kontexten definieren, lassen sich Gene innerhalb VOn DNA-Sequenzen identifizieren [Sal 98, Ohl 99].
Geht man direkt VOn mRNA aus, ist dieser erste Verfahrensschritt nicht erforderlich, da nur jeweils ein Gen transkribiert wird und die finale mRNA auch schon bereinigt wurde. Allerdings erfolgt je nach Lebenszyklus einer Zelle nur die Expression einiger weniger Gene, so dass auf der Basis VOn mRNA die Untersuchung eines kompletten Genoms praktisch unmoglich ist.
Hiiufig betrachtet man erst das Endprodukt des Transkriptions- und Translationsprozesses selbst, niimlich die Proteine. Dabei ist das Ziel nicht eine Segmentierung, sondern das Finden verwandter Sequenzen. Am einfachsten ist der Proteinvergleich, wenn man diese nur paarweise betrachtet. Urn die statistischen Veriinderungen der Sequenzen erfassen zu konnen, wurden schon lange vor dem Einsatz VOn Hidden-Markov-Modellen Wahrscheinlichkeiten ftir die Zuordnung vOn Aminosiiuren an bestimmten Positionen der Sequenz sowie deren Einftigung oder Loschung definiert. Man kann dann eine Aminosiiuresequenz einer anderen positionsweise zuordnen und erhiilt ein sogenanntes Alignment. Die logischen Positionen dieser Abbildung zweier Proteine aufeinander stehen dabei meist in direktem Zusammenhang zur ausgebildeten dreidimensionalen Struktur.
Wesentlich anspruchsvoller ist es, das Sequenzalignment auf mehrere Proteine einer Familie anzuwenden. Die Ergebnisse solcher Bemtibungen werden in Form von sogenannten multiplen Alignments festgelegt. Sie werden in der Regeljedoch nicht automatisch bestimmt, sondern von Expertenhand erstellt. Allerdings lassen sich aus vorliegenden mutiplen Alignments automatisch die charakteristischen Eigenschaften der jeweiligen Gruppe iihnlicher Sequenzen ableiten und z.B. durch Hidden-Markov-Modelle beschreiben (vgl. [Kro 94b, Edd 95, Edd 98, Dur 00]). Diese sogenannten Profile konnen dann dazu verwendet werden, in entsprechenden Datenbanken automatisch nach weiteren verwandten Proteinen zu suchen. Abbildung 2.8 zeigt am Beispiel verschiedener Globine ein von Experten erstelltes multiples Alignment.
Die Detektion neuer Gene durch Segmentierung eines Genoms oder die Erweiterung einer Familie VOn Proteinen urn neue Mitglieder mit Hilfe statistischer Vergleiche kann nattirlich nicht die zellbiologische Funktion der neu entdeckten Strukturen aufzeigen. Diese muss letztendlich in biologischen Experimenten nachgewiesen werden. Allerding lassen sich aus dem strukturellen Vergleich biologischer Sequenzen und den dabei festgestellten Ahnlichkeiten Hypothesen tiber die Wirkungsweise von Genen oder Proteinen ableiten, die dann wesentlich gezielter experimentell tiberprtift werden konnen.
36
2 Anwendungen
Helix
AAAAAAAAAAAAAAA BBBBBBBBBBBBBBBBCCCCCCccccc DDDDDDDEE
HBA..HUMAN ---------VLSPADKTNVKAAWGKVGA--HAGEYGAEALERMFLSFPTTKTYFPHF-DLS-----HGSA
HBBJnJ.MAN --------VHLTPEEKSAVTALWGKV----NVDEVGGEALGRLLVVYPWTQRFFESFGDLSTPDAVMGNP
MYG_PHYCA ---------VLSEGEWQLVLHVWAKVEA--DVAGHGQDILIRLFKSHPETLEKFDRFKHLKTEAEMKASE
GLB3_CHITP ----------LSADQISTVqASFDKVKG------DPVGILYAVFKADPSlMAKFTQFAG-KDLESIKGTA
GLB5_PETMA PIVDTGSVAPLSAAEKTKIRSAWAPVYS--TYETSGVDILVKFFTSTPAAQEFFPKFKGLTTADQLKKSA
LGB2_LUPLU --------GALTESQAALVKSSWEEFNA--NIPKHTHRFFILVLEIAPAAKDLFS-FLK-GTSEVPQNNP
GLBI_GLYDI ---------GLSAAQRQVlAATWKDIAGADNGAGVGKDCLIKFLSAHPQMAAVFG-FSG----AS---DP
Helix
EEEEEEEEEEEEEEEEEEE
FFFFFFFFFFFF FFGGGGGGGGGGGGGGGGGGG
HBA..HUMAN QVKGHGKKVADALTNAVAHV---D--DMPNALSALSDLHAHKL--RVDPVNFKLLSHCLLVTLAAHLPAE
HBBJnJ.MAN KVKAHGKKVLGAFSDGLAHL---D--NLKGTFATLSELHCDKL--HVDPENFRLLGNVLVCVLAHHFGKE
MYG_PHYCA DLKKHGVTVLTALGAILKK----K-GHHEAELKPLAQSHATKH--KIPIKYLEFISEAIIHVLHSRHPGD
GLB3_CHITP PFETHANRIVGFFSKIIGEL--P---NlEADVNTFVASHKPRG---VTHDQLNNFRAGFVSYMKAHT--D
GLB5_PETMA DVRWHAERIINAVNDAVASM--DDTEKMSMKLRDLSGKHAKSF--QVDPQYFKVLAAVIADTVAAG----
LGB2_LUPLU ELQAHAGKVFKLVYEAAIQLQVTGVVVTDATLKNLGSVHVSKG---VADAHFPVVKEAILKTIKEVVGAK
GLB1_GLYDI GVAALGAKVLAQIGVAVSHL--GDEGKMVAQMKAVGVRHKGYGNKRlKAQYFEPLGASLLSAMEHRIGGK
Helix
HHHHHHHHHHHHHHHHHHHHHHHHHH
HBA..HUMAN FTPAVHASLDKFLASVSTVLTSKYR------
HBBJnJ.MAN FTPPVQAAYQKVVAGVANALAHKYH------
MYG_PHYCA FGADAQGAMNKALELFRKDlAAKYKELGYQG
GLB3_CHITP FA-GAEAAWGATLDTFFGMIFSKM-------
GLB5_PETMA -----DAGFEKLMSMICILLRSAY-------
LGB2_LUPLU WSEELNSAWTIAYDELAIVIKKEMNDAA---
GLB1_GLYDI MNAAAKDAWAAAYADISGALISGLQS-----
Abb. 2.8 Multiples Alignment der Aminosauresequenz von sieben Globinen verschiedener Lebewesen nach [Kro 94b]. Es sindjeweils die in der SWISS-PROT-Datenbank [Bai 00] verwendeten Bezeichner angegeben. Die mit Helix bezeichnete Zeile definiert die Zuordnung zur dreidimensionalen Struktur der Proteine. Loschungen von Aminosauren an bestimmten Positionen sind mit - bezeichnet.
Solche Bemtihungen sind eingebettet in das Bestreben von Biologen und seit einigen lahren auch Bioinformatikern, die Funktionsweise biologischer Organismen erklliren zu konnen. Speziell ein exaktes Verstandnis des menschlichen Metabolismus liegt im fundamentalen Interesse der Arzneimittelindustrie. Auf genetischer Ebene konstruierte und gegegenenfalls speziell auf ein bestimmtes Individuum abgestimmte Wirkstoffe lassen - so die Hoffnung der Wissenschaftler - eine in ihrer Wirkungsweise enorm verbesserte Bekampfung von Krankheiten zu, ohne gleichzeitig die teilweise dramatischen Nebenwirkungen klassischer Medikamente zu verursachen. Daher wird die Sequenzierung immer neuen genetischen Materials und dessen detaillierte Analyse beztiglich Aufbau und zellbiologischer Funktion vor allem von der Pharma-Industrie vorangetrieben.
2.4 Ausblick
37
2.4 Ausblick
Markov-Modelle stellen einen Formalismus dar, der wegen des uberragenden Erfolgs dieser Technik bei der automatischen Sprachverarbeitung einen groBen Bekanntheitsgrad im Bereich der Mustererkennung und daruber hinaus erreicht hat. Daher ware es ein aussichtsloses Unterfangen, versuchen zu wollen, aIle jemals mit diesen Methoden bearbeiteten Fragestellungen aufzuzahlen. Wir wollen uns daher auf die wichtigsten Themengebiete konzentrieren, fUr die Markov-Modelle neben der automatischen Spracherkennung, der Schriftverarbeitung und der Analyse von biologischen Sequenzen in gr6Berem Umfang zur Anwendung kommen.
Ahnlich wie bei der Verarbeitung von Sprachsignalen, die lediglich eine Folge von Messwerten des Schalldruckpegels darstellen, lassen sich Hidden-Markov-Modelle zur Analyse anderer Messreihen einsetzen, wie sie bei der Materialprufung oder in regelungstechnischen Systemen auftreten (vgl. z.B. [Sch 93, Wei 00]).
Vergleichbar mit der on-line Handschrifterkennung ist die automatische Erkennung menschlicher Gesten (vgl. z.E. [Sta 95, Wi195, Bra 97, Nam 97, Eic 98]). Die Trajektorien der Hande und Arme einer Person und eventuell auch die jeweilige Handpostur mussen allerdings vor einer statistischen Analyse des Bewegungsablaufs mit aufwendigen Bildverarbeitungsmethoden aus entsprechenden Bildsequenzen extrahiert werden. Insofern sind diese Verfahren im Aufbau vergleichbar mit einem auf der Basis der Verfolgung von Schreibbewegungen [Mun 96] entwickelten video-basierten online Handschrifterkennungssystem [Wie 01, Fin 01].
Ais Verallgemeinerung der Gestenerkennung kann man die Erkennung menschlicher Handlungen bzw. menschlichen Verhaltens ansehen. So werden in [Yam 92] z.B. Bewegungsablaufe beim Tennisspielen und in [Bre 97] beim Gehen analysiert. Die erlernten Modelle werden in [Hov 96] verwendet, urn die Bewegungsmuster durch einen Roboter nachahmen und damit die demonstrierte Handlung ausfUhren zu lassen. Sehr spezielle menschliche Handlungen stellen Veranderungen des Gesichtsausdrucks dar, wie sie z.B. in [Hoe 00, Lie 97] analysiert werden.
Bei allen diesen Verfahren werden aus den Eingangsbildsequenzen zuerst lineare Folgen von Merkmalsvektoren erzeugt, auf denen dann Markov-Modell-basierte Techniken ansetzen. Allerdings wurden in der Literatur auch Verfahren vorgeschlagen, den Formalismus von Hidden-Markov-Modellen so zu erweitern, dass direkt eine Modellierung zweidimensionaler Eingabedaten m6glich wird (vgl. z.B. [Sam 94, Eic 99, Li 00]).
Bei praktisch allen bisher angesprochenen Ansatzen kommen Hidden-Markov-Modelle alleine und nicht in Kombination mit Markov-Ketten-Modellen zum Eisatz. Dies ist im wesentlichen dadurch bedingt, dass fur Anwendungen wie z.B. Gesten- oder Handlungserkennung nur ein sehr kleines Inventar von Segmentierungseinheiten verwendet wird und daher probabilistische Einschrankungen der entsprechenden Symbolfolgen nicht von unmittelbarer Bedeutung sind.
Auf rein symbolischer Ebene werden dagegen Markov-Ketten-Modelle zur Beschreibung von Zustandsfolgen ohne Erganzung durch Hidden-Markov-Modelle eingesetzt. Ein wichtiger Anwendungsbereich ist das Information-Retrieval, wo statistische Modelle von Texten durch MarkovKetten beschrieben werden (vgl. z.B. [Pon 98]). Da eine kompakte Beschreibung im Prinzip einer Komprimierung entspricht, bilden dieselben Prinzipien auch die Grundlage verschiedener Methoden zur Textkompression (vgl. [Bel 90]). In leicht veranderterForm werden Markov-Ketten Model-
38
2 Anwendungen
Ie als sogenannte Markov-Entscheidungsprozesse unter anderem zur Lasung von Planungsaufgaben verwendet (vgl. z.B. [Dea 95]).
Teil I
Theorie
Vorbemerkungen
In den folgenden Kapiteln 3 bis 6 des ersten Teils dieses Buchs sollen die theoretischen Grundlagen von Markov-Modellen vorgestellt werden. Am Anfang steht ein kurzer Uberblick tiber die wichtigsten Konzepte der Wahrscheinlichkeitsrechnung und Statistik, die flir das Verstandnis der weiteren Ausflihrungen erforderlich sind. AnschlieBend werden unter dem thematischen Rahmen der Vektorquantisierung Methoden zur Beschreibung von Datenverteilungen in hochdimensionalen Vektorraumen vorgestellt. GewissermaBen als statistische Erweiterung klassischer Vektorquantisierungstechniken werden dabei auch Verfahren zur Schatzung von Mischverteilungsmodellen auf der Basis von Normalverteilungsdichten behandelt. 1m Kapitel 5 schlieBt sich die formale Darstellung von Hidden-Markov-Modellen und der zu deren Anwendung erforderlichen Algorithmen an. Dabei werden nur typische Vertreter dieser Modellierungstechnik behandelt. Die wichtigsten Varianten von Hidden-Markov-Modellen werden dagegen nur kurz in Abschnitt 5.8 vorgestellt, wo der interessierte Leser auch weiterftihrende Literaturhinweise findet. Thema von Kapitel 6 sind Markov-Ketten-Modelle, die in ihrer speziellen Auspragung ftir Mustererkennungsaufgaben als nGramm-Modelle bezeichnet werden. 1m Gegensatz zu Hidden-Markov-Modellen ist der theoretische Hintergrund hier weniger umfangreich. Daher liegt der Schwerpunkt der Darstellung auf algorithmischen Losungen, die eine zuverlassige Schatzung der erforderlichen Modellparameter erlauben. Dabei konzentrieren wir uns auf Methoden, die aus heutiger Sieht als Standard angesehen werden konnen, auch wenn gerade in diesem Bereich eine Vielzahl unterschiedlichster Verfahren vorgeschlagen wurde. Ebenso wie bei der Darstellung von Hidden-Markov-Modellen werden wichtige Modellierungsalternativen im Ausblick des Kapitels kurz vorgestellt.
Obwohl ein tiefergehendes Verstandnis der Anwendung von Markov-Modellen ftir Mustererkennungsaufgaben erst bei gleichzeitiger Betrachtung der praxisrelevanten Aspekte moglich ist, wird im Rahmen der folgenden formalen Darstellung versucht, den theoretischen Kern dieser Methoden ohne storende Querbeztige und Verweise in linear aufeinander aufbauender Weise zu prasentieren. Der anschlieBende zweite Teil dieses Buchs widmet sich dann intensiv den Problemstellungen, die sich beim praktischen Einsatz von Hidden-Markov- und n-Gramm-Modellen ergeben.
3
Grundlagen der Statistik
Viele in natiirlichen Prozessen zu beobachtende Ereignisse unterliegen keiner klaren GesetzmaBigkeit, sondern zeigen ein zufalliges Verhalten. Uber einen einzelnen solchen Vorgang konnen daher keine Aussagen gemacht werden. Allerdings lassen sich auch bei zufiilligen Prozessen gewisse RegelmaBigkeiten beobachten, wenn man ihr Verhalten in haufiger Wiederholung betrachtet und vom Einzelfall abstrahiert. Die Wahrscheinlichkeitsrechnung stellt zur Behandlung von GesetzmaBigkeiten, die solchen zufalligen Vorgangen zugrundeliegen, die notwendigen mathematischen Modelle bereit. Die Statistik behandelt dartiberhinaus das Problem, wie die Parameter solcher Modelle aus Beobachtungen abgeleitet werden konnen.
1m folgenden sollen einige wichtige Grundbegriffe der Wahrscheinlichkeitsrechnung und Statistik eingeflihrt werden, die flir die weitere Betrachtung von Markov-Modellen relevant sind. Die DarsteHung will dabei die wesentlichen Prinzipien verdeutlichen. Ftir eine mathematisch exakte formale Behandlung oder Herieitung von Begriffen sei der Leser daher auf die umfangreiche Spezialliteratur verwiesen.
3.1 Zufallsexperiment, Ereignis und Wahrscheinlichkeit
Die Ausflihrung eines Vorgangs mit zufalligem Ausgang wird formal als ZuJallsexperiment bezeichnet. Dies kann z.B. das Werfen eines Wtirfels oder auch die Beobachtung der Borsenkurse sein. Das Ergebnis eines einzelnen Experiments ist in diesen Fallen im Rahmen gewisser Moglichkeiten ungewiss - die Augenzahl eins bis sechs beim Wtirfeln oder steigende, fallende oder behauptete Aktienkurse. Es lassen sich nur GesetzmaBigkeiten bei einer langfristigen und vom Einzelfall abstrahierten Betrachtung aufstellen.
Ein zuJalliges Ereignis A entspricht einem einzelnen Ergebnis oder einer Menge von moglichen Ergebnissen des Zufallsexperiments, z.B. dem Auftreten einer Sechs, einer geraden Augenzahl oder einem tiber einer bestimmten Mindestmarke liegenden Aktienkurs. Ein solches Ereignis A tritt ein, wenn bei einem konkreten Versuch das Ergebnis des Zufallsexperiments in der Menge A liegt.
n Das sichere Ereignis ist die Gesamtmenge aller moglichen Ergebnisse eines Zufallsexperiments,
die auch als Ereignisraum bezeichnet wird. Ereignisse, die genau einem moglichen Ergebnis des Zufallsexperiments entsprechen, werden als Elementarereignisse bezeichnet. Auf Ereignisse lassen sich die tiblichen Mengenoperationen Vereinigung, Durchschnitt und Komplement (beztiglich des sicheren Ereignisses n) anwenden.
Die relative Haufigkeit f(A) eines Ereignisses A, das bei der N-fachen Wiederholung eines Zu-
42
3 Grundlagen der Statistik
fallsexperiments m-mal auftritt, ergibt sich als Quotient aus seiner absoluten Haufigkeit' c(A) = m und der Gesamtanzahl der Versuche N:
f(A) = c(A) = m
N N
Eine pragmatische Herleitung2 des Wahrscheinlichkeitsbegriffs baut direkt auf der relativen Haufigkeit eines Ereignisses A auf. Man verallgemeinert diesen namlich dahingehend, dass von der konkreten Beobachtungsdauer abstrahiert und die zugrundeliegende GesetzmaBigkeit fUr das Auftreten des Ereignisses A als seine Wahrscheinlichkeit peA) definiert wird. Es ist unmittelbar plausibel,
dass mit wachsender Beobachtungsdauer die relative Haufigkeit f (A) immer weniger variieren und
einem einheitlichen, konstanten Wert zustreben wird - der Wahrscheinlichkeit P (A). Diese Beziehung wird auch vom sogenannten "Gesetz der groBen Zahlen" untermauert3.
Von der bedingten Wahrscheinlichkeiten P(AIB) eines Ereignisses A spricht man, wenn vor der Beobachtung von A bereits die Information vorliegt, dass das Ereignis B eingetreten ist. Diese Wahrscheinlichkeit fUr das Auftreten von A unter der Bedingung B lasst sich aus der Verbundwahrscheinlichkeit fUr das gleichzeitige Auftreten von A und B sowie der unbedingten Wahrscheinlichkeit fUr B wie folgt bestimmen4 :
P(AIB) = peA, B) PCB)
Da P(AIB) bestimmt wird nach der Beobachtung des Ereignisses B, nennt man diese GroBe auch a-posteriori-Wahrscheinlichkeit. Die unbedingte Wahrscheinlichkeit eines Ereignisses dagegen, die vor der Einschrankung durch Zusatzbedingungen gilt, heiBt dann auch a-priori- Wahrscheinlichkeit.
Sofern die Beobachtung von B keine Information Uber das Auftreten von A liefert, heiBen die Ereignisse A und B statistisch unabhiingig. Die bedingte Wahrscheinlichkeit ist somit gleich der unbedingten, es gilt also:
P(AIB) = peA) und PCB) = P(BIA) falls A, B sind statistisch unabhangig
Die Verbundwahrscheinlichkeit lasst sich fUr statistisch unabhangige Ereignisse einfach als Produkt der Einzelwahrscheinlichkeiten angeben:
peA, B) = peA) PCB) falls A, B sind statistisch unabhangig
Eine wichtige Beziehung fUr das Rechnen mit bedingten Wahrscheinlichkeiten stellt die sogenannte Bayes-Regel dar:
P(BIA) = P(AIB)P(B) peA)
(3.1)
I Als mathematische Symbole fiir absolute und relative Haufigkeiten eines Ereignisses A verwenden wir hier in Anlehnung an die englischsprachigen Begriffe count und frequency die Symbole c(A) und f(A).
2 In der mathematischen Fachliteratur wird der Wahrscheinlichkeitsbegriff dagegen in der Regel axiomatisch definiert, d.h. tiber die Spezifikation der ihm zugrundeliegenden Eigenschaften.
3Das von Bernoulli formulierte "Gesetz der groBen Zahlen" besagt: Die Wahrscheinlichkeit dafiir, dass die relative Haufigkeit eines Ereinisses A urn mehr als eine beliebige, aber feste Schwelle E von seiner Wahrscheinlichkeit P(A) abweicht, wird verschwindend klein, wenn die Anzahl der Beobachtungen beliebig groB wird - also gegen unendlich geht.
4Statt der Mengenschreibweise fur die Verbundwahrscheinlichkeit P(A n B) verwendet man in der Literatur hiiufig die vereinfachte Notation P(A, B) fiir die Vereinigung bzw. konjunktive Verkntipfung von Ereignissen.
3.2 ZufaIlsvariable und Wahrscheinlichkeitsverteilungen
43
Mit ihrer Hilfe Uisst sich aus der bedingten Wahrscheinlichkeit P(AIB) unter Zuhilfenahme des Modellwissens tiber die Ereignisse A und B in Form der zugehorigen a-priori Wahrscheinlichkeiten die a-posteriori Wahrscheinlichkeit P(BIA) ftir B berechnen. Die Abhangigkeit in den Wahrscheinlichkeitsausdrticken wird damit also quasi umgedreht.
Legt man eine disjunkte Zerlegung des Ereignisraums n in Ereignisse B l , B 2 , .•• , Bn zugrunde,
so lautet die Bayes-Regel in ihrer allgemeinen Form:
P(BjIA) = P~AIBj)P(Bj) = !(AIBj)P(Bj )
(3.2)
I: I: P(A, Bi )
P(AIBi)P(Bi )
i=l
i=l
3.2 Zufallsvariable und Wahrscheinlichkeitsverteilungen
Eine Vereinfachung des mathematischen Umgangs mit zufalligen Ereignissen lasst sich dadurch erreichen, dass diese in geeigneter Weise auf die Menge lRder reellen Zahlen abgebildet werden. Zufallsexperimente werden dann durch sogenannte ZuJalisvariable reprasentiert, die zufallig Werte aus lR annehmen konnen. Eine Zufallsvariable X, die nur endlich viele oder auch abziihlbar unendlich viele Werte Xl, X2, . .. ,XN annimmt, bezeichnet man als diskret. Sogenannte kontinuierliche ZuJalisvariable konnen dagegen prinzipiell jeden beliebigen Wert X E lR annehmenS•
Die Charakterisierung von Zufallsvariablen erfolgt tiber deren Verteilungsfunktion. Die Verteilungsfunktion Fx(x) einer Zufallsvariablen X gibt zujedem moglichen Wert X an, wie groB die Wahrscheinlichkeit daftir ist, dass von X angenommene Werte kleiner oder gleich X sind:
Fx(x) = P(X :::; x)
1m diskreten Falliasst sich Fx (x) leicht tiber die Wahrscheinlichkeiten Pi derjenigen Elementarereignisse Ai berechnen, die den diskreten Werten Xi der Zufallsvariable zugeordnet wurden. Die Verteilungsfunktion ergibt sich einfach als Summe tiber aBe Pi, die zu Werten Xi kleiner oder gleich X gehoren:
1m kontinuierlichen Fall geht die Summe in dieser Berechnungsvorschrift in ein Integral tiber und die integrierte kontinuierliche Funktion px(x) verliert ihre Bedeutung als Wahrscheinlichkeit von Elementarereignissen.
f x
Fx(x) = px(t) dt
-00
5Die Bezeichnung kontinuierlich wurde hier in Anlehnung an die engJischsprachige Literatur gewiihIt. Mit diesem Begriff kann der wesentliche Unterschied zur diskreten Version deutlicher gemacht werden, als durch die in der deutschen Statistikliteratur iibliche Bezeichnung stetige Zufallsvariable.
44
3 Grundlagen der Statistik
Man bezeichnet Px (x) dann als Wahrscheinlichkeitsdichte oder kurz als Dichte der Zufallsvariable X. Genau wie Wahrscheinlichkeiten sind Dichtewerte stets nichtnegativ. Allerdings konnen sie auch Werte groBer als 1 annehmen. Lediglich die Gesamtflache unter der Dichtefunktion muss gleich 1 sein. Die Wahrscheinlichkeit eines Ereignisses ergibt sich als Integral der Dichtefunktion tiber ein geeignetes Intervall der reellen Zahlen. Die Wahrscheinlichkeit dafiir, dass eine beliebige kontinuierliche Zufallsvariable einen konkreten Wert annimmt, ist somit immer gleich Null.
Das Konzept der Zufallsvariable lasst sich auch auf vektorwertige GroBen verallgemeinern. Zur Vereinfachung der Darstellung wollen wir uns dabei im weiteren auf den wichtigeren kontinuierlichen Fall beschranken. Die diskreten Entsprechungen ergeben sich vollig analog wie bei eindimensionalen ZufallsgroBen.
Eine vektorwertige n-dimensionale ZufallsgroBe X ist formal betrachtet ein Zufallsvektor, der aus n einzelnen Zufallsvariablen Xi besteht. Die Verteilungsfunktion des Zufallsvektors X, die durch
gegeben ist, erhait man auf der Basis einer gemeinsamen Dichtefunktion Px (x) der einzelnen Zufallsvariablen Xi:
J J... J Xl X2
Fx(x) =
Xn
PX(h,t2, ... tn)dtl,dt2, ... dtn
-00 -00
-00
Die Dichtefunktion PXi einer einzelnen Zufallsvariable Xi ergibt durch Integration tiber aile tibrigen
Komponenten als Randverteilung der gemeinsamen Dichtefunktion Px gemaB:
! PXi (x) =
PX (Xl, X2, ... Xn)dXI, ... dXi-l, dXiH, ... dXn
(Xl ,...Xi-l ,Xi+l , ... xn)EIRn-l
Sofern die einzelnen Zufallsvariablen Xi statistisch unabhangig sind, ergibt sich die gemeinsame Dichtefunktion des Zufallsvektors als das Produkt der Komponentendichten:
n
px(x) =PX(XI,X2, ... Xn) = IIPxi(xi)
i=l
Injedem Falliasst sich die Verbunddichte Px jedoch in Verallgemeinerung des Begriffs der bedingten Wahrscheinlichkeit als Produkt bedingter Dichtefunktionen darstellen. Zur Veranschaulichung dieses Vorgehens wollen wir hier nur den einfachen zweidimensionalen Fall betrachten. Ftir die Verbunddichte eines Zufallsvektors geiten dann die folgenden Beziehungen:
px(x)
PX(XI, X2) PX1 (xd PX21xl (x2I xI) PX2(X2) PX1 lx2(xllx2)
1m allgemeinen n-dimensionalen Fall ergeben sich dagegen n! verschiedene Moglichkeiten zur Aufteilung von Px in bedingte Dichtefunktionen.
3.3 Parameter von Wahrscheinlichkeitsverteilungen
45
3.3 Parameter von Wahrscheinlichkeitsverteilungen
Zur groben Charakterisierung von Wahrscheinlichkeitsverteilungen bzw. der jeweils zugrundeliegenden Zufallsvariable verwendet man die aus der konkreten Verteilungsfunktion abgeleiteten Parameter Erwartungswert und Varianz. Der Erwartungswert £ {X} einer Zufallsvariable bzw. der zugehorigen Wahrscheinlichkeitsverteilung gibt den im statistischen Mittel von X angenommenen Wert an. Er kann bei vollstandiger Kenntnis der Verteilung als erstes Moment der Dichtefunktion berechnet werden:
f00
£{X} = xpx(x) dx
-00
Flir diskrete Verteilungen ergibt sich die folgende Beziehung:
00
£{X} = LXiPi
i=l
Bei bekanntem Erwartungswert charakterisiert die Varianz einer Verteilung die zu erwartende Streu-
ung der von der Zufallsvariable angenommenen Werte um £ {X}. Sie kann als Erwartungswert des
quadratischen Abstands der Werte der Zufallsvariable von ihrem Erwartungswert berechnet werden, was dem zweiten zentralen Moment der Verteilung entspricht:
f00
Var{X} = £{(X - £{X})2} = (x - £{X})2pX(X) dx
-00
1m diskreten Fall ergibt sich in Analogie zum Erwartungswert die Berechnungsvorschrift:
00
Var{X} = L(Xi - £{X})2pi
i=l
Durch einfache algebraische Umformungen lasst sich zeigen, dass die Varianz einer Verteilung auch alternativ liber die folgende Beziehung ermittelt werden kann, was vor aHem in praktischen Anwendungen Vorteile bietet:
(3.3)
Flir Zufallsvektoren, die wir im weiteren einfach als vektorwertige Zufallsvariablen behandeln wollen, lassen sich ebenso wie flir eindimensionale GroBen Momente der Verteilung definieren. Den Erwartungswert eines ZufaHsvektors erhalt man als direkte Verallgemeinerung des eindimensionalen Falls aus folgender Beziehung:
f £{X} = xpx(x)dx
"'ERn
46
3 Grundlagen der Statistik
Die Varianz einer mehrdimensionalen Verteilung wird durch die sogenannte Kovarianzmatrix beschrieben, die wie folgt definiert ist:
f Var{X} = £{(X - £{X}) (X - £{X})T}
=
(x-£{X})(x-£{X}fPx(x)dx
wEIRn
Anstatt des quadratischen Abstandes einer skalaren GroBe vom Erwartungswert wird dabei das auBere Produkt der jeweiligen Vektordifferenz gebildet. Sind die Komponenten Xi eines Zufallsvektors X statistisch unabhangig, so enthalten die Hauptdiagonalenelemente der Kovarianzmatrix Var{X} die Varianzen Var{Xi} der einzelnen Verteilungen und die ubrigen Elemente der Matrix verschwinden.
Mnlich wie bei eindimensionalen Verteilungen lasst sich die Berechnungsvorschrift fUr die Kovarianzmatrix wie folgt umformen:
Var{X} = £{X XT} - £{X} £{X}T
(3.4)
3.4 Normalverteilungen und Mischverteilungsmodelle
1m diskreten Fall lasst sich die Verteilung einer bestimmten ein- oder mehrdimensionalen Zufalls-
variable prinzipiell dadurch definieren, dass man fur jedes Ergebnis x der ZufallsgroBe die entspre-
chende Wahrscheinlichkeit P(x) in einer Tabelle speichert. Fur kontinuierliche Verteilungen ist ein solches Vorgehen nicht moglich, da die entsprechenden Dichten sehr allgemeine stetige Funktionen sein konnen. Daher kann man in diesem Fall nur mit parametrisch definierten Modellen arbeiten, die auch fur diskrete Wahrscheinlichkeitsverteilungen deutlich kompaktere Beschreibungen liefem.
Die im Kontext von Markov-Modellen wichtigste parametrische Verteilung ist die fur kontinuierliche Zufallsvariable definierte Normalverteilung, die nach ihrem Entdecker auch haufig als Gauj3Verteilung bezeichnet wird. Fur eine skalare ZufallsgroBe, die dieser Verteilung genugt, ergibt sich die folgende Dichtefunktion6:
N(xIJL, (72) = ~ e 27r(72
(3.5)
Die beiden Parameter JL und (72 der Dichtefunktion entsprechen genau dem Erwartungswert und der Varianz der Normalverteilung. Fur n-dimensionale Zufallsvariable erhalt man unter Verwendung eines Mittelwertvektors JL und einer Kovarianzmatrix K die multivariate Normalverteilungsdichte gemaB:
(3.6)
6Diese Formel war zusarnmen mit dem typischen Funktionsverlauf der Gau8-Dichte auf dem bis zur Euro-Einfiihrung giiltigen 10 DM-Schein abgedruckt.
3.5 Stochastische Prozesse und Markov-Ketten
47
Dabei bezeichnet K-1 die Inverse sowie 127rKI die Determinante der mit dem Faktor 27r skalierten
Kovarianzmatrix.
Mit Hilfe von Normalverteilungsdichten lassen sich viele nattirliche Prozesse beschreiben, da man haufig annehmen darf, dass diese bei gentigend langer Beobachtungszeit einer GauB-Verteilung gehorchen. Allerdings weist die Normalverteilung nur ein Haufungsgebiet im Bereich des Mittelwertvektors auf und fallt von dort aus exponentiell abo Es handelt sich also urn eine unimodale Dichte. Will man Verteilungen mit mehreren Haufungsgebieten parametrisch reprasentieren, reicht dieses einfache Modell daher nicht mehr aus.
Es lasst sich jedoch zeigen, dass man sogar allgemeine kontinuierliche Dichtefunktionen p(x) durch
eine geignete Linearkombination unendlich vieler einzelner Normalverteilungen im Prinzip beliebig genau approximieren kann [Yak 70]:
LCi00
p(x)= N(xll'i' Ki) i=1
LCi00
mit
= 1
i=1
Ublicherweise betrachtet man bei solchen Mischverteilungsmodellen aber nur eine endliche Summe
von K Komponentendichten:
LCiK
p(x) ~ p(xI8) =
N(xll'i,Ki)
(3.7)
i=1
Die Parameter dieses Modells, namlich die Mischungsgewichte Ci sowie die Mittelwertvektoren I'i und Kovarianzmatrizen Ki der einzelnen Normalverteilungsdichten, fasst man tiblicherweise zu einem Parametersatz () zuammen. Dabei tiberwiegt die praktische Handhabbarkeit eines solchen vergroberten Modells bei weitem den notwendigerweise entstehenden Verlust in der Reprasentationsgenauigkeit.
3.5 Stochastische Prozesse und Markov-Ketten
Obwohl die von Zufallsvariablen tiber einen langeren Zeitraum erzeugten Ergebnisse zufallig variieren, bleiben doch die Eigenschaften des Erzeugungsprozesses - die der Zufallsvariablen zugrundeliegende Wahrscheinlichkeitsverteilung - unverandert. Urn eine Variation dieser Charakteristiken mathematisch behandeln und das Verhalten von stochastischen Ablaufen mit tiber die Zeit veranderlichen Eigenschaften beschreiben zu konnen, bedient man sich stochastischer Prozesse.
Ein stochastischer Prozess ist definiert als eine Folge von Zufallsvariablen 8 1 ,82 , ..., die dabei Werte St aus einem diskreten oder kontinuierlichen Wertevorrat gemaB individueller Wahrscheinlichkeitsverteilungen annehmen. Man spricht daher von kontinuierlichen oder diskreten stochastischen Prozessen. Da in diesem Buch ausschlieBlich diskrete stochastische Prozesse eine Rolle spielen, erfolgt die weitere Behandlung nur ftir diesen einfacheren Fall. Weiterhin kann man die durch einen solchen Prozess erzeugte Folge diskreter Werte auch als das Einnehmen diskreter Zustiinde verstehen. Daher spricht man im Kontext diskreter stochastischer Prozesse haufig von Zustanden und durch den Prozess erzeugten Zustandsfolgen.
48
3 Grundlagen der Statistik
Die zur Zufallsvariable St zum Zeitpunkt t gehOrige Verteilungsfunktion kann im allgemeinen vom Zeitpunkt t selbst sowie von den Werten 81,82, ... 8t-1, 8t+1, ... abhangen, die von den tibrigen Zufallsvariablen eingenommen wurden. Dieses sehr machtige Konzept wird jedoch tiblicherweise in einer Reihe von Punkten eingeschrankt.
Ein stochastischer Prozess heiBt stationiir, wenn die absolute Zeit t flir das Verhalten keine Rolle spielt, also nicht als Bedingung in die Wahrscheinlichkeitsverteilungen eingeht. Er heiBt dartiberhinaus kausal, wenn zusatzlich die Verteilung einer Zufallsvariable St nur von bereits vergangenen Zustanden 81, 82, ... 8t-1 abhangt. Die Wahrscheinlichkeitsverteilung flir einen dis]qeten, stationaren und kausalen stochastischen Prozess lasst sich also wie folgt angeben:
Sofern die Zuordnung von konkreten Werten 8t zu den entprechenden ZufaIlsvariablen St im jeweiligen Kontext eindeutig ist, lasst sich diese Beziehung auch einfacher darsteIlen als:
Die Kausalitat des Prosesses steIlt eine wesentliche Einschrankung dar, die ftir die Beschreibung zeitlicher Ablaufe allerdings auch auf der Hand liegt. Iedoch kann hierbei immer noch mit fortschreitender Zeit t und damit wachsender Lange der Zustandsfolge eine prinzipieIl beliebig lange Abhangigkeit der Verteilungen entstehen.
Unter der sogenannten Markov-Eigenschaft versteht man nun die zusatzliche Einschrankung, dass sich die Abhangigkeit der Prozesseigenschaften nur auf eine endliche Vergangenheit beschrankt - im FaIle eines einfachen stochastischen Prozesses sogar nur auf den unmittelbaren Vorgangerzustand. Die Wahrscheinlichkeitsverteilungen eines diskreten, stationaren, kausalen und einfachen stochastischen Prozesses, der auch als Markov-Kette 1. Ordnung bezeichnet wird, lasst sich daher angeben als:
Sofern die Gesamtereignismenge, also der betrachtete Zustandsraum, endlich ist, kann man diese Beschreibung auch kompakt zu einer Matrix von Zustandsiibergangswahrscheinlichkeiten zusammenfassen, die den Prozess komplett beschreibt:
A = [aij] = [P(St = jlSt-1 = i)]
Markov Ketten hoherer Ordnung, d.h. mit langerer zeitlicher Abhangigkeit der Verteilungen, bieten von ihrem Verhalten her keine prinzipiell erweiterten Moglichkeiten gegentiber Markov-Ketten 1. Ordnung. Der langere Kontexteinfluss lasst sich namlich immer durch eine Erweiterung des Zustandsraums in einen einzelnen Zustand kodieren (vgl. z.B. [Dur 00, S. 72]). Allerdings ist eine solche Reorganisation nicht immer wtinschenswert oder moglich, so dass bei der statistischen Modellierung von Symbolfolgen auch Markov-Ketten hoherer Ordnung zum Einsatz kommen, wie wir noch in Kapitel6 sehen werden.
3.6 Prinzipien der Parameterschiitzung
49
3.6 Prinzipien der Parameterschatzung
Urn ein statistisches Modell zur Beschreibung bestimmter naturlicher Prozesse einsetzen zu kannen, mussen die freien Parameter in geeigneter Weise bestimmt werden. Eine wesentliche Voraussetzung daflir biiden von Experten formulierte Vorerwartungen, die im wesentlichen den Typ des verwendeten Modells festiegen. Die zweite wichtige Grundiage sind konkrete Beobachtungen des zu beschreibenden Prozesses. Dabei kann es sich urn tatsachliche Messwerte oder auch abgeleitete GraBen handein.
Unter Zugrundelegung des ausgewahlten Modelltyps kannen dann auf dieser Stichprobe von Beispieidaten Schatzwerte fur die Modellparameter berechnet werden. Deren konkrete Auspragung hangt jedoch auch davon ab, welches Optimierungskriterium das jeweilige Schatzverfahren einsetzt.
3.6.1 Maximum-Likelihood-Schatzung
Die verbreitetste Methode zur Schatzung der Parameter statistischer Modelle stellt die sogenannte Maximum-Likelihood-Schiitzung (ML) dar. Auf der Basis einer vorliegenden Stichprobe w =
{Xl, X2, ... XT} werden in Abhangigkeit yom Typ des gesuchten Modells Schatzwerte 0fur dessen
Parameter so bestimmt, dass die Wahrscheinlichkeit - bzw. im kontinuierlichen Fall der Dichtewert - flir die Beobachtung der Daten maximiert wird.
Wir wollen im folgenden zur Vereinfachung der Betrachtungen davon ausgehen, dass die Stichprobe Werten einer Folge Xl, X 2 , ... XT von Zufallsvariablen entspricht, die einer identischen WahrscheinIichkeitsverteiIung gehorchen, deren Parameter gesucht sind. Die einzeinen Zufallsvariablen Xi sind dabei statistisch unabhangig. Daher erhalt man die Gesamtwahrscheinlichkeit der Daten ais Produkt der Anteile der identisch parametrisierten einzeinen Verteilungen:
T
p(wlfJ) = p(Xl' X2,··· xTlfJ) = IIp(Xtl fJ )
t=l
Bei der Maximierung dieser GraBe durch Variation der Parameter fJ stellen nicht die maglichen Werte der Zufallsvariablen, sondern die Modellparameter selbst die Veranderlichen dar. Dies macht man durch die Einflihrung der sogenannten Likelihood-Funktion explizit:
L(fJlw) = L(fJlxl' X2, ... XT) = p(wlfJ)
Ziel der Maximum-Likelihood-Schatzung ist es, den Wert der Likelihood-Funktion flir einen bestimmten Typ des Modells und eine gegebene Stichprobe w in Abhangigkeit von fJ zu maximieren:
OML = argmaxL(fJlw)
fJ
Dabei wendet man das Standardverfahren zur Lasung von Extremwertaufgaben an, indem die AbIeitung von L(fJlw) nach den Modellparametern fJ gebiidet und nullgesetzt wird. In den meisten
praktischen Fallen findet man genau ein Extremum 0, das dann dem ML-Schatzwert flir die gesuch-
ten Modellparameter entspricht. 1m allgemeinen ist das Ergebnis jedoch nicht eindeutig bestimmt.
50
3 Grundlagen der Statistik
Haufig ergibt sich eine mathematisch einfachere Behandlung dieser Extremwertaufgabe dadurch, dass nicht die Likelihood-Funktion, sondern deren Logarithmus betrachtet wird.
OML = argmaxlnL(9Iw)
9
Durch die Anwendung einer monotonen Funktion bleibt das Extremum unverandert. Insbesondere aber flir statistische Modelle auf der Basis exponentieller Dichten wie der Normalverteilung ergeben sich dadurch deutliche Vereinfachungen.
Wir wollen zur Veranschaulichung des Prinzips der ML-Schatzung ein einfaches Beispiel betrachten. Auf einer Stichprobe w = {Xl, X2, ... XT} sollen die Parameter einer eindimensionalen Normalverteilungsdichte geschiitzt werden. Die logarithmische Likelihood-Funktion ist dann gegeben durch:
I IT
InL(9Iw) = In N(XtlfL, 0-2 )
t=l
Ais Ableitungen dieser Funktion nach den beiden Veranderlichen fL und 0-2 erhiilt man:
a
OfL InL(9Iw)
a
00-21nL (9I w)
Durch Nullsetzen dieser Gleichungen ergeben sich als Schatzwerte fl fur den Mittelwert und iJ2 flir
die Varianz der gesuchten Normalverteiung mit Hilfe des ML-Verfahrens die folgenden Werte: 1 T
r LXt t=l
Diese beiden GroBen bezeichnet man auch als den empirischen Erwartungswert bzw. die empirische Varianz einer nur durch eine Stichprobe gegebenen Wahrscheinlichkeitsverteilung.
1m vektorwertigen Faile erhalt man zur Berechnung der Schatzwerte flir den Mittelwertvektor fl
und die Kovarianzmatrix k einer multivariaten GauB-Dichte die folgenden Beziehungen:
1 T
r LXt t=l
T
T
r r 1~ ",(Xt -
ILA)(Xt -
ILA)T =
I
"~ ,
Xt
X
T t
-
IALIAL T
t=l
t=l
(3.8) (3.9)
3.7 Literaturhinweise
51
Wenn man davon ausgehen kann, dass die tatsachliche Verteilung der Daten dem zugrundegelegten Modelltyp entspricht, und die verfiigbare Stichprobe geniigend groB ist, bietet die ML-Schatzung
einige vorteilhafte Eigenschaften. Die berechneten Schatzwerte 8M!.. fiir die unbekannten Vertei-
lungsparameter konvergieren gegen die tatsachlichen Parameter 0* , wenn der Stichprobenumfang gegen unendlich geht:
lim 8M!.. = 0*
T-+oo
AuBerdem weisen die ML-Schatzwerte die geringstmogliche Varianz auf, so dass kein anderes Verfahren eine Schatzung liefem kann, die naher an den tatsachlichen Parametem liegt.
3.6.2 Maximum-a-posteriori-Schatzung
1m Gegensatz zur Maximum-Likelihood-Schatzung legt die sogenannte Maximum-a-posterioriSchiitzung (MAP) als Optimierungskriterium die a-posteriori-Wahrscheinlichkeit der Modellparameter bei gegebenem Modelltyp und vorliegender Stichprobe zugrunde.
o 8MAP = argmaxp(Olw)
Formt man diese Gleichung mit Hilfe der Bayes-Regel urn, so erhalt man folgende Beziehung:
~
OMAP
=
argomaxp(Olw)
=
argmax 0
p(wIO)p(O) ()
pw
Die Dichtefunktion p(w) der Beispieldaten selbst ist unabhangig von den gesuchten Modellparametem 0 und kann daher bei der Maximierung vemachlassigt werden. Es ist jedoch erforderlich, Erwartungen iiber die konkrete Auspragung der Modellparameter in Form einer geeigneten a-prioriVerteilung p(0) zu formulieren.
Aus diesem Grunde bietet die MAP-Schatzung gegeniiber dem ML-Verfahren Vorteile, wenn nur sehr wenige Beispieldaten vorliegen. Die ML-Schatzung ist dann zwar die optimale Moglichkeit, Schatzwerte allein aus den Daten abzuleiten. Aufgrund des geringen Stichprobenumfangs sind die Ergebnisse jedoch im allgemeinen sehr unzuverlassig, da keinerlei Vorerwartungen beriicksichtigt werden. Bei der Anwendung des MAP-Prinzips werden diese dadurch einbezogen, dass die apriori-Verteilung p(0) Teil des Optimierungskriteriums ist. Stark vereinfacht ausgedriickt, erreicht man mit diesem Vorgehen, dass Modellparameter, flir die nur wenige Trainingsbeispiele vorliegen, hauptsachlich aus den Vorerwartungen und solche, die aus umfangreichem Material geschatzt werden konnen, vorwiegend aufgrund der Beispieldaten bestimmt werden.
3.7 Literaturhinweise
Zum Thema Statistik existieren unzahlige Monographien, von denen viele Einflihrungscharakter haben oder sogar explizit als Lehrbuch konzipiert sind. Eine sehr gelungene und iibersichtliche Einflihrung in die Grundlagen der Statistik geben Beyer et al. [Bey 99a]. Von den behandelten
52
3 Grundlagen der Statistik
Themen her iihnlich, aber besonders knapp und schon fast mit dem Charakter eines Taschenbuchs widmen sich Lehn & Wegmann [Leh 00] dem Thema. Eine deutlich umfangreichere Behandlung der wesentlichen Grundlagen der Statistik findet man dagegen bei Schlittgen [Sch OOb]. Ais reines Nachschlagewerk enthiilt auch das bekannte Taschenbuch der Mathematik von Bronstein et al. die wichtigsten statistischen Grundbegriffe [Bro 99].
Unter der Vielzahl englischsprachiger Statistik-Monographien sticht das Werk von Larsen & Marx [Lar 01] durch seinen gelungenen Autbau, seine anschaulich Darstellung und die vielen Beispiele heraus. Gute Einfiihrungen in die speziell fiir Mustererkennungsaufgaben relevanten Grundbegriffe und Verfahren der Statistik findet man auBerdem in den klassischen Werken von Fukunaga [Fuk 72] oder Duda & Hart [Dud 73] bzw. auch in [Hua 01, KapiteI3].
4 Vektorquantisierung
Bei der Verarbeitung von Signaldaten im Rechner ergibt sich immer das Problem, diese Daten in einerseits moglichst kompakter aber andererseits auch hinreichend genauer Weise digital darzustellen. Da digitale Repriisentationen notwendigerweise auch endlich sind, ist es daher Ziel eines sogenannten Vektorquantisierers, Vektoren aus einem Eingabedatenraum auf eine endliche Menge typischer Reprasentanten abzubilden. Dabei sollte moglichst keine ftir die weitere Verarbeitung relevante Information verloren gehen. Den Aufwand zur Speicherung oder Ubertragung vektorwertiger Daten versucht man daher durch die Elimination darin enthaltener redundanter Information zu reduzieren.
Eine solche Kodierung wird auf Sprache z.B. angewandt, urn sie tiber kapazitatsbegrenzte digitale Telefonnetze zu tibertragen. Bei Bilddaten versucht man diese moglichst kompakt z.B. im Speicher einer Digitalkamera abzulegen oder auch als komplette Spielfilme digital an private Haushalte zu tibertragen.
Obwohl bei der Kodierung von Daten deren Bedeutung prinzipiell nicht von Interesse ist, erhlilt man die geeignetsten Reprasentationen dann, wenn "ahnliche" Datenvektoren bei der Kodierung zusammengefasst und "verschiedene" separat reprasentiert werden. Aus dieser Sichtweise entspricht das Ziel der Kodierung dem der sogenannten Clusteranalyse, die versucht, die Haufungsgebiete einer unbekannten Datenverteilung zu ermitteln und adaquat zu beschreiben. Die naherungsweise parametrische Reprasentation allgemeiner Wahrscheinlichkeitsverteilungen erfolgt in der Regel mit Hilfe von Mischverteilungen auf der Basis von Normalverteilungsdichten (vgl. Abschnitt 3.4 Seite 46). Bei diesem Vorgehen modellieren die einzelnen GauB-Dichten die Haufungsgebiete der betrachteten Daten, und die entsprechenden Mittelwertvektoren konnen als Reprasentanten eines statistischen Quantisierungsprozesses angesehen werden.
In den folgenden Abschnitten wollen wir zuerst den Begriff des Vektorquantisierers formal definieren und Bedingungen flir dessen Optimalitat ableiten. AnschlieBend werden die wichtigsten Algorithmen zur Erstellung von Vektorquantisierern vorgestellt. In Abschnitt 4.4 wird schlieBlich als Verallgemeinerung der Problemstellung die untiberwachte Schatzung von Mischverteilungsmodellen behandelt.
4.1 Definition
Ein Vektorquantisierer - oder kurz Quantisierer - Q ist definiert als die Abbildung eines k-dimensionalen Vektorraums lRk in eine endliche Teilmenge Y c lRk:
54
4 Vektorquantisierung
= Die Menge Y YI, Y2, ... YN der Reprasentanten- oder Prototypenvektoren Yi bezeichnet man
auch als das Codebuch. Die GroBe N des Codebuchs ist dabei die wesentliche KenngroBe zur Charakterisierung einer Klasse von Vektorquantisierem1•
Mitjedem Vektorquantisierer Q der GroBe N ist immer auch eine Partition des betrachteten Vektor-
raums rn.k in Zellen RI , R2 , ••• RN assoziiert. Dabei liegen in derZelle Ri aIle diejenigen Vektoren x E rn.k, die yom Quantisierer dem Prototypenvektor oder Codewort Yi zugeordnet wurden. Man
erhalt die jeweilige Zelle also als Urbild des Prototypenvektors bezogen auf die Abbildung Q des
Vektorquantisierers:
Da ein Quantisierer Q jedem Vektor x des Eingaberaums genau einen Prototypen Yi zuordnet,
definiert er dadurch implizit eine vollstandige, disjunkte Zerlegung des rn.k in Zellen Rio d.h.:
und
Das Verhalten eines Quantisierers Q ist dann eindeutig definiert durch die Angabe des verwendeten Codebuchs Y und der zugehOrigen Partition {~} des betrachteten Vektorraums.
In der Praxis kann man einen Vektorquantisierer als eine Kombination eines Kodierers C und eines
= Dekodierers D beschreiben. Mit der Indexmenge I {I, 2, ... N} ergibt sich:
und D:IH-Y
Die Quantisierungsvorschrift Q ergibt sich somit als Hintereinanderausfiihrung des Kodierungs-
und des anschlieBenden Dekodierungsschritts:
Q=DoC
Diese Darstellung ist besonders dann sinnvoll, wenn es urn die kompakt kodierte Dbertragung von Daten geht. Prinzipiell geniigt es dann, ein aufeinander abgestimmtes Paar von Kodierer und Dekodierer zu verwenden und auf dem Dbertragungskanal nur die Indizes der quantisierten Daten zu iibermitteln2• Da sichergestellt sein muss, dass der Dekodierer zur Rekonstruktion der Datenvektoren aus den Quantisierungsindizes das korrekte Codebuch verwendet, muss dies bei praktischen Anwendungen im Rahmen der Dateniibermittlung mit iibertragen werden. Die GroBe des Codebuchs ist daher bei der Betrachtung der erforderlichen Kanalkapazitat und der insgesamt erreichten Kompressionsrate mit zu beriicksichtigen.
Wesentlicher "Nachteil" des Quantisierungsprozesses ist, dass im allgemeinen ein Vektor x E rn.k
auf einen von ihm verschiedenen Prototypenvektor Y abgebildet wird. Es entsteht daher bei jeder
11m Englischen bezeichnet man einen Vektorquantisier, der ein Codebuch mit N Repriisentantenvektoren verwendet, als N-level quantizer. 1m Deutschen existiert hierfiir kein iiquivalenter Ausdruck. Insbesondere sollte man diese Bezeichnung nicht mit der des mehrstujigen Vektorquantisierers verwechseln, der das Quantisierungsergebnis in mehreren aufeinanderfolgenden Verarbeitungsschritten erzeugt. 2Bei Vektorquantisierem mit variabler Datenrate werden auch die Quantisierungsindizes selbst in komprimierter Form iibertragen, z.B. durch die Verwendung einer Huffman-Codierung (vgl. z.B. [Ger 92, Kapitel 17, S. 631ff]).
4.2 OptimaliUit
55
einzelnen Quantisierung ein individueller Quantisierungsfehler E(xIQ) in Abhangigkeit von der verwendeten Quantisierungsvorschrift Q, der mit Hilfe eines geeigneten AbstandsmaBes d(·, .) fUr vektorwertige Daten angegeben werden kann3:
E(xIQ) = d(x, Q(x))
Generelle Aussagen tiber die Reproduktionsqualitat eines bestimmten Quantisierers Q lassen sich
jedoch nur aus einer globalen Betrachtung der Quantisierungsfehler ableiten. Zu diesem Zweck
bestimmt man den im statistischen Mittel zu erwartenden Quantisierungsfehler:
J t(Q) = t'{E(XIQ)} = t'{d(X,Q(X))} = d(x,Q(x))p(x)dx
(4.1)
ffik
Dabei geht man davon aus, dass sich die statistischen Eigenschaften der betrachteten Vektoren x mit Hilfe einer Zufallsvariable X beschreiben lassen, die der Dichtefunktion p(x) gentigt.
4.2 Optimalitat
Obwohl die CodebuchgroBe eines Vektorquantisierers in der Praxis einen wesentlichen Konfigurationsparameter darstellt, betrachtet man Bedingungen fUr die Existenz optimaler Quantisierungsvorschriften immer bei festgelegter Anzahl N von Prototypenvektoren. Als Qualitatsmerkmal ist dann allein die erreichte Reproduktionsgtite ausschlaggebend. Ziel ist es also, denjenigen Vektorquantisierer zu bestimmen, der bei gegebener fester CodebuchgroBe fUr eine bestimmte Verteilung der Eingabedaten den minimalen mittleren Quantisierungsfehler erreicht.
Da ein Vektorquantisierer, wie schon oben erwahnt, durch Angabe von Codebuch und zugehoriger Partition definiert wird, lassen sich von beiden Komponenten ausgehend Kriterien formulieren, wie die jeweils andere optimal zu wahlen ist. Eine geschlossene Beschreibung der Optimalitat von Codebuch und Partition ist dagegen nicht moglich.
Die sogenannte Niichster-Nachbar-Bedingung beschreibt die optimale Wahl der Partition {Ri} bei gegebenem Codebuch Y. Jede einzelne Zelle muss dabei so festgelegt werden, dass sie aile diejenigen Vektoren x E IRk enthalt, die yom korrespondierenden Prototypenvektor Yi minimalen Abstand haben:
(4.2)
Das bedeutet, dass der entsprechende Quantisierer Q einen Vektor x seinem nachsten Nachbarn im
Codebuch zuordnet:
Q(x) = Yi falls d(x, Yi) ::; d(x, Yj) Vj ::f. i
(4.3)
Ftir den Fall, dass ein Vektor x gleichen Abstand von zwei (oder mehr) Codebuchvektoren hat, kann
er einer der Zellen beliebig zugeordnet werden. Der entstehende Quantisierungsfehler
d(x, Q(x)) = mind(x, y) yEY
(4.4)
3Wird statt eines aIIgemeinen AbstandsmaBes hierbei der euklidische Abstand verwendet, erhalt man den Quantisierungs-
fehler €(xIQ) = Ilx - Q(x)ll·
56
4 Vektorquantisierung
wird dadurch nicht veranderfl.
Es lasst sich leicht zeigen, dass die Quantisierung von Vektoren mit Hilfe der Nachster-NachbarRegel (4.3) bei gegebenem Codebuch Y den mittleren zu erwartenden Quantisierungsfehler minimiert. Dazu wird der aus Gleichung (4.1) bekannte Ausdruck zur Bestimmung von l(Q) wie folgt nach unten abgeschatzt5:
f f l(Q) = d(x,Q(x))p(x)dx ~ {~ird(x,y)}p(x)dx
ffik
ffik
Der Vergleich dieses Ergebnisses mit Gleichung (4.4) zeigt, dass mit der Nachster-Nachbar-Bedingung genau diese untere Schranke des mittleren Quantisierungsfehlers erreicht wird. Daher ist die auf der Basis von Gleichung (4.2) definierte Partition optimal fur das gegebene Codebuch.
Die optimale Wahl eines Codebuchs Y bei gegebener Partition {Ri} wird durch die sogenannte Zentroid-Bedingung definiert. FUr eine Zelle ~ der Partition ist jeweils derjenige Vektor Yi der optimale Reprasentant, der Zentroid dieser Zelle ist:
Der Zentroid einer Zelle R ist dabei definiert als derjenige Vektor y* E R, von dem aIle anderen Vektoren x E Rim statistischen Mittel minimalen Abstand haben, d.h.:
= y* cent(R) falls £{d(X,y*)IX E R}:::; £{d(X,y)IX E R} "Iy E R
Die Zufallsvariable X dient dabei wieder zur Charakterisierung der Verteilung der Datenvektoren
x im Eingaberaum.
Sofern der Zentroid von R eindeutig definiert ist6 lasst sich dieser auch wie folgt angeben:
cent(R) = argmin£{d(X,y)IX E R}
(4.5)
yER
Fur die gebrauchIichen elliptisch symmetrischen AbstandsmaBe der Form (x - y) T K- 1(x - y),
die auch den eukIidischen Abstand Ilx - YII als Spezialfall enthalten, sofern keine SkaIierung des
Raumes mit einer inversen Streuungsmatrix K- 1 erfolgt, ist der Zentroid einer Zelle identisch mit
dem bedingten Erwartungswert der Datenvektoren beschrankt auf diese Region:
cent(R) = £{XIX E R} = Lx p(xlx E R)dx
Da aIle Vektoren in der Zelle R vom Zentroiden minimalen mittleren Abstand haben, minimiert die Verwendung des Zentroiden als Reprasentantenvektor auch den mittleren Quantisierungsfehler fUr
4In [Ger 92. S. 350] wird fiir soJche Fiille vorgeschlagen. die Zuordnung zum Codebuchvektor Yi mit demjeweils kleinsten Index i vorzunehmen. 5Diese Abschiitzung des mittleren Quantisierungsfehlers ist moglich. wei! beide Faktoren d(·, .) und p(:z:) des Integranden nichtnegative Werte annehmen. Zur Minimierung muss daher d(·, .) nur lokal fiir jedes :z: minimal gewiihlt werden. 6Je nach Vertei!ung der Dichtevektoren kann es vorkommen. dass der Zentroid in bestimmten Hillen nieht eindeutig definiert ist. Das Minimum des mittleren Abstandes wird dann fiir mehrere verschiedene Reprasentantenvektoren in gleicher Weise erreicht.
4.3 Algorithmen zum Design von Vektorquantisierem
57
die betreffende Zelle. Werden aIle Codebuchvektoren so bestimmt, minimiert die Quantisierung mit Hilfe dieses Codebuchs fUr die vorgegebene Partition den im statistischen Mittel durch den Quantisierer verursachten Fehler. Das Codebuch ist somit ftir die vorliegende Partition optimal gewahlt.
Dies lasst sich leicht zeigen durch Berechung des mit Hilfe der Zentroid-Bedingung erreichten mittleren Quantisierungsfehlers:
L 1 L 1 N
€( Q) =
N
d(x, Yi)p(X )dx = P(X E Ri) d(x, Yi)p(xlx E Ri)dx
i=l Ri
i=l
Ri
Der Gesamtfehler ergibt sich durch Integration tiber die in den jeweiligen Zellen entstehenden Anteile und der Summation tiber aIle Zellen der Partition. Dieser Ausdruck lasst sich umformen durch die EinfUhrung der a-priori Wahrscheinlichkeit P(X E Ri) einer Zelle und der bedingten Dichte p(xlx E Ri) von Vektoren beschrankt auf diese Region.
Da aIle Zellen disjunkt sind und die Summe nur nichtnegative Summanden umfasst, konnen alle N Terme unabhangig voneinander minimiert werden:
Wie der Vergleich mit der Definition des Zentroiden in Gleichung (4.5) zeigt, kann diese Minimierung leicht dadurch erreicht werden, dass der Reprasentantenvektor Yi als Zentroid der Zelle Ri gewahlt wird, da genau dieser den mittleren Abstand zu den tibrigen Vektoren der Zelle minimiert.
Ftir einen optimalen Quantisierer hangen also Codebuch und Partition unmittelbar voneinander abo Zur Parametrisierung des Verfahrens ist daher die Angabe des Codebuchs ausreichend. Die Partition des Eingaberaums ergibt sich implizit durch die optimale Wahl der Quantisierungsoperation mit Hilfe der Nachster-Nachbar-Regel. In der Praxis identifiziert man daher tiblicherweise das verwendete Codebuch begrifflich mit dem zugehOrigen Vektorquantisierer.
4.3 Algorithmen zum Design von Vektorquantisierern
Obwohl im vorangegangenen Abschnitt Bedingungen fUr die Optimalitat einer Partition bei gegebenem Codebuch bzw. die des Codebuchs ftir eine vorliegende Partition angegeben wurden, existiert keine geschlossene analytische Losung zur Bestimmung eines optimalen Vektorquantisierers bestimmter GroBe fUr eine vorliegende Verteilung von Datenvektoren. Allerdings lassen sich iterative Methoden angeben, die ausgehend von einem vorgegebenen initialen Quantisierer diesen schrittweise verbessern und so versuchen, einen nilierungsweise optimalen Vektorquantisierer zu bestimmen. Alle diese Methoden konnen jedoch nicht garantieren, die optimale Losung dieses Problems tatsachlich zu finden, und sind daher nur suboptimal.
Ein weiteres Problem bei der Erstellung von Vektorquantisierern besteht darin, dass deren Qualitat
von der Verteilungsdichte p(x) der betrachteten Datenvektoren abhangt. In der Praxis ist diese je-
doch in der Regel nicht bekannt und kann daher nicht exakt parametrisch beschrieben werden. Man
= geht aber immer davon aus, dass eine geeignete Stichprobe w {Xl, X2, •.. XT} von Beispiel-
vektoren vorliegt, anhand derer die erforderlichen Parameter der tatsachlichen Verteilungsfunktion
58
4 Vektorquantisierung
= Gegeben sei eine Stichprobe w
{Xl, X2, ... XT} von Beispielvektoren, die
gewilnschte CodebuchgroBe N sowie eine untere Schranke Aemin filr die relative Ver-
besserung des Quantisierungsfehlers
1. lnitialisierung
wahle ein geeignetes initiales Codebuch yO der GroBe N
y? (z.B. durch zufallige Auswahl von N Vektoren aus w)
initialisiere Interationszahler m +- 0
2. Optimierung der Partition
bestimme fUr das aktuelle Codebuch ym die optimale Partition durch Klassifikati~
= on aller Vektoren Xt mit t 1 ... T in Zellen R'{' = {xly'{' = argmind(x,y)}
yEym
bestimme dabei den mittleren Quantisierungsfehler
€(ym) = ~ LT: min d(xt, y) t=l yEYm
3. Aktualisierung des Codebuchs
= flir aile Zellen R'{' mit i 1 ... N berechne neue Reprasentanten yf+1 = cent(R'{') diese bilden das neue Codebuch ym+1 = {yf+111 ~ i ~ N}
4. Terminierung
berechne die relative Abnahme des Quantisierungsfehlers seit der letzten Iteration
_ €(ym-1) _ €(ym)
Aem -
e(ym)
falls die relative Abnahme groB genug war, d.h. Aem > Aemin
setze m +- m + 1 und weiter mit Schritt 2
sonstEnde!
Abb. 4.1 Lloyd-Algorithmus zum Design von Vektorquantisierern
naherungsweise bestimmt werden konnen. Diese Stichprobe wird im Rahmen der im folgenden vorgestellten Algorithmen zum Design von Vektorquantisierem anstatt des gesamten Eingabedatenraumes IRk betrachtet.
Lloyd-Algorithm us
Die Idee des sogenannten Lloyd-Algorithmus besteht darin, die duale Sichtweise auf Vektorquantisierer auszuniltzen und mit Hilfe der im vorangegangenen Abschnitt definierten Methoden abwechselnd Partition bzw. Codebuch optimal zu ermitteln. Durch eine Iteration dieses Verfahrens wird zwar nicht notwendigerweise der global optimale Quantisierer erzeugt, aber es lasst sich zeigen, dass eine Folge von Vektorquantisierem entsteht, die immer kleinere mittlere Quantisierungsfehler erreichen.
Der Algorithmus, der in Abbildung 4.1 zusammengestellt ist, erzeugt flir eine gegebene Stichprobe w einen Vektorquantisierer der GroBe N, d.h. ein Codebuch mit N Reprasentantenvektoren. Zu
Beginn des Verfahrens wird ein geeignetes initiales Codebuchs yO gewahlt, was allerdings heu-
ristisch erfolgen muss. Obwohl die Wahl dieses Startpunkts die Optimierung natlirlich beeinflusst,
4.3 Algorithmen zum Design von Vektorquantisierem
59
erzielt man mit der zufalligen Auswahl von N Vektoren aus der Stichprobe in der Praxis brauchbare Ergebnisse. Durch den im nachsten Abschnitt vorgestellten Algorithmus wird dieser Nachteil des Lioyd-Algorithmus weitestgehend vermieden.
1m nachsten Verarbeitungsschritt wird flir das jeweils aktuelle Codebuch ym die optimale Partition der Stichprobe berechnet. Die Zuordnung jedes Elements Xt E W zu einer Zelle der Partition
entspricht der Klassifikation in diejenige Klasse Ri, von deren zugehorigen Reprasentanten yi
der betreffende Vektor minimalen Abstand hat. Da die Entscheidung tiber den Abbruch des Verfahrens auf der Basis des erreichten Quantisierungsfehlers erfolgt, wird dieser im Klassifikationsschritt mit berechnet. Ausgehend von der neu berechneten Partition kann im Anschluss die Aktualisierung des Codebuchs erfolgen. Das neue Codebuch ym+l besteht dabei einfach aus den Zentroiden der
optimalen Zellen bzw. Klassengebiete Ri. Das Verfahren terminiert, wenn durch die Optimierung
des Codebuchs keine ausreichende relative Verbesserung des Quantisierungsfehlers mehr erreicht wurde. Die untere Schranke Afmin ist dabei ein Parameter des Algorithmus, der yom Anwender vorgegeben werden muss7 •
Der bei weitern tiberwiegende Teil des Aufwands dieser Methode entsteht bei der Klassifikation aller Vektoren der Stichprobe wahrend der Optimierung der Partition in Schritt 2. Die Berechnung eines aktualisierten Codebuchs ist dagegen ohne nennenswerten Aufwand moglich8. Es ist daher sinnvoll, diesen Schritt in jedem Fall auszuflihren, auch wenn der ermittelte Quantisierungsfehler eigentlich ftir das vorherige Codebuch gilt.
LBG-Algorithmus
Der problematischste Aspekt des Lioyd-Algorithmus ist dessen Initialisierung. Es liegt daher nahe, diesen Teil des Vektorquantisierungsdesigns so zu modifizieren, dass die Ergebnisse nicht durch ein schlecht gewahltes initiales Codebuch negativ beeinftusst werden konnen. Der nach den Initialen seiner Erfinder Linde, Buzo & Gray benannte LBG-Algorithmus [Lin 80] konstruiert daher nicht direkt den gewtinschten Vektorquantisierer der GroBe N, sondern eine Folge von Quantisierern mit wachsender Anzahl von Codebuchvektoren.
Der Algorithmus, der in Abbildung 4.2 zusammengefasst ist, beginnt mit der Wahl eines initialen Codebuchs. Da zu diesem Zeitpunkt noch nicht die volle Anzahl von Reprasentantenvektoren benutzt werden muss, existiert hierflir eine einfache und robuste Moglichkeit. Man beschrankt sich namlich auf die Verwendung eines trivialen Quantisierers mit genau einem Reprasentantenvektor. Da dann die gesamte Stichprobe der zugehorigen Zelle einer trivialen Partition entspricht, besteht dieses Codebuch genau aus dem Zentroiden der Stichprobe9.
Urn im Laufe des Verfahrens die gewtinschte ZieicodebuchgroBe zur erreichen, bedient sich der Algorithmus einer Methode zur Aufteilung existierender Codebuchklassen in jeweils zwei neue
7Eigene Experimente haben gezeigt, dass eine relative Verbesserung des Quantisierungsfehlers urn weniger als ein Promille keine ftir praktische Anwendungen relevanten Verbesserungen des Codebuchs mehr bewirk!. 8Bei Verwendung des euklidischen AbstandsmaBes muss lediglich der empirische Mittelwert der Zellen bestimmt werden.
= Man erhiilt den Zentroiden daher gemaB cent(R) 111 La:ER:n. Die Summation tiber die in der jeweiligen Zelle ent-
haltenen Vektoren kann leicht bereits wahrend der Klassifikation inkrementell erfolgen, so dass zum Abschluss nur noch die Normierung auf die Gesamtanzahl der Vektoren erforderlich is!. 9Zur Beschleunigung des Verfahrens in der Startphase kann man auch ein kleines Codebuch mit NO ~ N zuf<illig ausgewahlten Vektoren verwenden ohne die Ergebnisse des Algorithmus nachteilig zu beeinflussen.
60
4 Vektorquantisierung
Gegeben sei eine Stichprobe w
{Xl, X2, ... XT} von Beispielvektoren, die
gewiinschte CodebuchgroBe N sowie eine untere Schranke ~€min flir die relative Ver-
besserung des Quantisierungsfehlers
1. Initialisierung
wahle ein geeignetes initiales Codebuch yO der GroBe NO
(z.B. trivial als yO = {cent(w)} mit NO = 1)
initialisiere Interationszahler m f- 0
2. Splitting
erzeuge aus dem aktuellen Codebuch ym ein neues Codebuch mit Nm+l = 2 N m Reprasentanten
ym+l = {Yl + €, Yl - €, Y2 + €, Y2 - €, ... YN"' + €, YN"' - €}
mit einem geeigneten, betragsmaBig kleinen "StOrvektor" €
3. Optimierung
optimiere das neu erzeugte Codebuch ym+l mit dem Lloyd-Algorithmus
4. Terminierung
falls die gewiinschte Klassenanzahl noch nicht erreicht ist
setze m f- m + 1 und weiter mit Schritt 2
sonstEnde!
Abb. 4.2 LBG-Algorithmus zum Design von Vektorquantisierem
Zellen. Dazu wird zu allen urspriinglichen Reprasentantenvektoren Yi ein geeigneter, betragsmaBig kleiner "StOrvektor" € addiert bzw. von ihnen subtrahiert, so dass sich zwei neue Codebuchvektoren
Yi +€ und Yi - € ergeben. Insgesamt liefert diese Operation ein neues Codebuch, das doppelt soviele
Reprasentantenvektoren umfasst wie das urspriinglichelO.
Natiirlich kann nicht erwartet werden, dass das so erzeugte Codebuch bezogen auf den erreichten Quantisierungsfehler optimal ist. Daher wird es im dritten Schritt des Verfahrens mit dem aus dem vorangegangenen Abschnitt bekannten Lloyd-Algorithmus (Schritte 2 bis 4) optimiert. Falls die gewiinschte CodebuchgroBe noch nicht erreicht ist, wendet man die Aufteilung von Codebuchklassen emeut auf den aktuellen Quantisierer an.
Gegeniiber dem Verfahren nach Lloyd bietet der LBG-Algorithmus den entscheidenden Vorteil, dass die Initialisierungsprozedur klar definiert ist. Dadurch wird vermieden, dass eine zufallige, aber ungliickliche Wahl des Startcodebuchs dazu fiihrt, dass der Algorithmus nur ein unbefriedigendes lokales Optimum beziiglich des erzeugten Quantisierers erreicht. Lediglich der zu Klassenaufteilung erforderliche StOrvektor muss in geeigneter Weise angegeben werden. Durch die schrittweise Konstruktion immer groBerer Codebiicher reduziert das Verfahren auch den erforderlichen Klassifikationsaufwand. Solange zu Beginn des Algorithmus nur sehr grobe Schatzwerte der Parameter des Vektorquantisierers vorliegen, arbeitet die Methode mit sehr kleinen Codebiichem. Diese sind effizienter auszuwerten als der letztendliche vollstandige Quantisierer. 1m Laufe des kontinuierlichen Codebuchwachstums kommen verfeinerte und aufwendigere Modelle dann zum Einsatz, wenn bereits eine gute Approximation der gewiinschten Quantisierungsvorschrift vorliegt.
IOEs ist auch mogJich, nur soviele Klassen aufzuteilen, dass die gewtinschte CodebuchgroBe erreicht wird, oder nur solche, die lokal einen besonders groBen Quantisierungsfehler verursachen. In beiden Hillen muss aber darauf geachtet werden, dass nicht zu kleine Zellen entstehen.
4.3 Algorithmen zum Design von Vektorquantisierem
61
= Gegeben sei eine Stichprobe w {Xl, X2, ... XT} von Beispielvektoren und die
gewiinschte CodebuchgroBe N
1. Initialisierung
wahle als initiales Codebuch yO die ersten N Vektoren der Stichprobe
yO = {Xl,X2, ... XN}
initialisiere Interationszahler m t- 0
2. Iteration
fiir aIle noch nicht bearbeiteten Vektoren Xt, N < t ~ T
(a) Klassifikation
bestimme fiir Xt den optimalen Reproduktionsvektor y"!' im aktuellen Codebuch ym
y"!' = argmind(xt, y)
yEY'"
(b) Aktualisierung der Partition
bestimme die neue Partition durch Aktualisierung der Zelle des ermittelten
Codebuchvektors
R,,!,-+1 = { Rj U {Xt} fallsj = i
J
R'f!l
sonst
J
(c) Aktualisierung des Codebuchs
bestimme ein neues Codebuch durch Aktualisierung des Reprasentanten der
im vorangegangenen Schritt veranderten Zelle
= y.m+l -_ J
{cent(Rj+1)
yj
fallsj sonst
i
Abb. 4.3 k-means-Algorithmus zum Design von Vektorquantisierem
k-means-Algorithmus
Sowohl der Algorithmus nach Lloyd als auch der LBG-Algorithmus eignen sich gut zum Design von Vektorquantisierem. AUerdings erfordem beide Verfahren die mehrfache. aufwendige Klassifikation aller Vektoren der Stichprobe wiihrend der erforderlichen Optimierungsschritte. Mit dem sogenannten k-means-Algorithmus existiert dagegen ein Verfahren. das mit nur einem Verarbeitungsdurchlauf auf den vorliegenden Daten ein naherungsweise optimales Codebuch erzeugt. Die von MacQueen entwickelte Methode [Mac 67] entstand eigentlich aus dem Gedanken heraus. fiir die Charakterisierung einer Datenverteilung nicht nur einen empirischen Mittelwert. sondem eben k Mittelwerte (eng!. k means) zu verwenden. Diese Mittelwertvektoren entsprechen aber genau den Reprasentanten eines Vektorquantisierers der GroBe k.
Abbildung 4.3 zeigt den zugehorigen Algorithmus. Aus Griinden der Konsistenz mit der Notation der iibrigen Verfahren werden wir die GroBe des Codebuchs dabei mit N bezeichnen und nicht mit k wie in der Originalarbeit.
Da es Ziel des Verfahrens ist. jeden Datenvektor Xt nur genau einmal zu betrachten. erhalt man eine verbliiffend einfache Initialisierungsvorschrift. Das initiale Codebuch besteht namlich aus den ersten N Vektoren der Stichprobe. Die folgenden Verarbeitungsschritte erinnem uns an die beiden Optimierungsphasen des Lloyd-Algorithmus. Allerdings werden sie beim k-means-Verfahren
62
4 Vektorquantisierung
einzeln fUr jeden Vektor ausgefuhrt. Ein Vektor Xt wird also zuerst gemliB der Nlichster-Nachbar-
Regel dem optimalen Reproduktionsvektor Yi im aktuellen Codebuch ym zugeordnet. Direkt im
Anschluss werden dann die Parameter des Vektorquantisierers aktualisiert. Man geht dabei davon
aus, dass durch die Zuordnung des Vektors Xt zur Zelle Ri+1 nur diese verlindert wird. Daher
reicht es aus, fUr diese Zelle einen neuen Reprlisentantenvektor Yi+l zu berechnen. Nach einmali-
gem Durchlaufen der Stichprobe liegt das erzeugte Codebuch vor.
Man konnte nun annehmen, dass eine solche Codebuchschlitzung nicht zu befriedigenden Ergebnissen fuhrt. In der Praxis ist die Methode jedoch erstaunlich leistungsflihig und ungleich effizienter als der Lloyd- oder LBG-Algorithmus. Die mit dem k-means-Algorithmus erzeugten Vektorquantisierer stehen dabei bezuglich der Qualitlit in der Regel nicht hinter den Ergebnissen der anderen Verfahren zuruck. Sofern es sich bei der betrachteten Stichprobe urn eine zuflillig und unabhlingig voneinander generierte Folge von Vektoren handelt, llisst sich fUr das Verfahren asymptotische Konvergenz gegen die optimale Losung zeigen, wenn die StichprobengroBe gegen unendlich geht [Mac 67]. In der Praxis bedeutet dies, dass die Methode besonders gut bei sehr groBen Stichproben funktioniert, die keine oder nur geringe Korrelationen zwischen aufeinanderfolgenden Vektoren aufweisen.
Obwohl sich der k-means-Algorithmus fundamental von dem Verfahren nach Lloyd unterscheidet, wird letzterer in der Literatur hliufig flilschlicherweise als k-means-Algorithmus bezeichnetll . Sofern die oben genannten Voraussetzungen gegeben sind, schlligt die k-means-Methode mit ihrer, bezogen auf die GroBe der Stichprobe, linearen Komplexitlit hinsichtlich der Effizienz aIle in mehreren Verarbeitungsphasen optimierenden Verfahren wie den Lloyd- und den LBG-Algorithmus bei weitem. Trotzdem ist die Qualitlit der erzeugten Vektorquantisierer vergleichbar.
4.4 Schiitzung von Mischverteilungsmodellen
Das Ergebnis eines Vektorquantisierungsverfahrens beschreibt eine gegebene Datenverteilung lediglich mit Hilfe der N Reprlisentantenvektoren des erzeugten Codebuchs. Eine deutlich genauere Darstellung erhlilt man bei der Verwendung eines MischverteilungsmodeIls, da dann auch lokaIe Streuungseigenschaften mit erfasst werden konnen. Wegen der mathematisch relativ einfachen Handhabbarkeit werden dabei als Komponentendichten in der Regel Normalverteilungen eingesetzt (vgl. auch Abschnitt 3.4).
Die einfachste, wenn auch qualitativ schlechteste Methode zur Schlitzung eines solchen Mischverteilungsmodells fur eine gegebene Stichprobe baut direkt auf dem Ergebnis eines Vektorquantisierungsprozesses auf. Nach Abschluss der Codebucherzeugung werden fUr aIle Zellen Ri der letztendlichen Partition die Parameter einer Normalverteilungsdichte geschlitzt. Der erforderliche Mittelwertvektor JLi ist dabei identisch mit dem bereits bekannten Zentroiden Yi. Es muss also lediglich eine empirische Kovarianzmatrix fUr aIle Vektoren der jeweiligen Zelle berechnet werden (vgl. Gleichung (3.9) Seite 50):
L Ki = (x - JLi)(X - JLif
mERi
11 siehe auch die Literaturhinweise in Abschnitt 4.5 auf Seite 66
4.4 Schatzung von Mischverteilungsmodellen
63
Deutlich bessere Ergebnisse erzielt man, wenn bereits beim Quantisierungsprozess die durch die Kovarianz bedingte Verzerrung des Vektorraums berucksichtigt wird. Der sogenannte MahalanobisAbstand (vgl. z.B. [Nie 83, S. 178], [Hua 01, S. 166]) stellt die entsprechende Erweiterung des euklidischen AbstandsmaBes dar:
Wie der Vergleich mit Gleichung (3.6) auf Seite 46 zeigt, entspricht dieser Ausdruck nahezu vollsHindig dem Exponentialterm einer Normalverteilungsdichtefunktion. Der Schritt zur Berucksichtigung einer so1chen Verteilung im Quantisierungsprozess ist daher nicht mehr weit.
Da aber eine Dichtefunktion im Gegensatz zu einem Abstand ein ZugehorigkeitsmaB darstellt, muss daflir die Zuordnung von Vektoren zu Codebuchklassen modifiziert werden. Ein Vektor Xt wird
dann derjenigen Zelle Ri zugeordnet, deren korrespondierende Normalverteilung N (x IJLi' K i ) den
maximalen Dichtewert liefert.
Ri = {xli = argmaxN(xIJLj' K j )} j
Diese Modifikation der Quantisierungsvorschrift fuhrt dazu, dass mit herkommlichen Methoden zum Vektorquantisierungsdesign auch Mischverteilungsmodelle erstellt werden konnen. Allerdings gehen die Verfahren immer noch davon aus, dass der mittlere Quantisierungsfehler minimiert werden solI, was flir eine Verteilungsdichte kein angemessenes Optimierungskriterium darstellt.
Anschaulich lasst sich dies an der Tatsache machen, dass zur Berechnung der Parameter einer Normalverteilung nur Vektoren aus einem begrenztem Gebiet eingehen - namlich der betreffenden Zelle. Die Dichtefunktion selbst ist aber fur den gesamten betrachteten Vektorraum definiert und liefert flir aIle moglichen Vektoren Dichtewerte, die allerdings eventuell beliebig klein werden.
EM-Algorithm us
Zur korrekten Schatzung von GauB'schen Mischverteilungsmodellen bedient man sich daher des sogenannten EM-Algorithmus [Dem 77]. Dieser stellt ein sehr allgemeines Verfahren dar, statistische Modelle mit verborgenen Zufallsvariablen iterativ zu optimieren. Da die allgemeine Betrachtung des Verfahrens mathematisch recht aufwendig und mitunter wenig anschaulich ist, wollen wir uns an dieser Stelle auf die konkrete Auspragung der Methode beschranken, die zur Schatzung von Mischverteilungsmodellen auf der Basis von Normalverteilungsdichten angewandt wird. Ein Modell mit N Komponentendichten ist wie folgt definiert (vgl. Gleichung (3.7) Seite 47):
N
L p(xIB) = Ci N(xIJLi' K i )
i=l
Den Parametersatz bestehend aus den a-priori Wahrscheinlichkeiten Ci der einzelnen Musterklassen sowie den Dichteparametern JLi und Ki wollen wir dabei zuammenfassend mit Bbezeichnen.
Der EM-Algorithmus verfolgt prinzipiell immer das Ziel, die Wahrscheinlichkeit der beobachteten
= Daten w {Xl, X2, •.. xr} in Abhangigkeit yom jeweiligen Modell zu maximieren. Die Tatsache,
64
4 Vektorquantisierung
Gegeben sei eine Stichprobe w = {Xl, X2, ... XT} von Beispielvektoren, die
gewtinschte Anzahl N von Basisverteilungsdiehten sowie eine untere Sehranke ~Lmin
ftir die relative Verbesserung der Likelihood-Funktion
1. Initialisierung
wahle initiale Parameter 0° = (c?, JL?, KP) des Misehverteilungsmodells initialisiere Interationszahler m +- 0
2. Schiitzung
berechne ftir jeden Vektor X E w mit dem aktuellen Modell om Sehatzwerte flir
die a-posteriori Wahrscheinliehkeiten der Musterklassen
I: P(wilx,om) = ci N(xIJLi,Ki) cj N(xIJLj, Kj)
j
bereehne ftir das aktuelle Modell om die Likelihood der Daten
L(omlw) = Inp(x1, X2, ... , xTlom) = L: In L: cj N(xIJLj, Kj)
mEw j
3. Maximierung
I : bereehne aktualisierte Parameter om+1
=
Km+1) (C~+l '1.
,
f"AImt H
,
'l.
P(wil x ,om)
mEw
Iwl
I: P(wil x ,om) X
4. Terminierung
mEw
berechne die relative Anderung der Likelihood seit der letzten Iteration
~L _ L(omlw) - L(om-1Iw)
m -
L(omlw)
falls die relative Verbesserung groB genug war, d.h. ~Lm > ~Lmin
setze m +- m + 1 und weiter mit Schritt 2
sonstEnde!
Abb.4.4 EM-Algorithmus zur Schatzung von Mischverteilungsmodellen.
dass die abhangige Variable dieser GroBe der Parametersatz 0 und nieht die Stichprobe ist, spiegelt
sieh im Ubergang zur sogenannten Likelihood-Funktion wider:
Da die Anwendung einer monotonen Funktion das Ergebnis der Maximierungsaufgabe nieht verandert und die Behandlung von Normalverteilungsdichten durch Logarithmierung deutlich vereinfaeht
4.4 Schatzung von Mischverteilungsmodellen
65
wird, verwendet man iiblicherweise den Logarithmus von L'(9Iw), den wir im weiteren vereinfachend als Likelihood-Funktion bezeichnen wollen:
L L(9Iw) = InL'(9Iw) = Inp(xl, X2, .. · xT19) = Inp(xI9)
mEw
Seinen Namen leitet der EM-Algorithmus von den beiden Hauptverarbeitungsphasen ab, in denen er vorgeht. Zuerst werden die Werte der nieht beobachtbaren WahrscheinlichkeitsgroBen in Abh1ingigkeit vom aktuellen Modell und den gegebenen Daten gesch1itzt. Dieser Schritt wird als expectation oder schlicht E-step bezeiehnet. AnschlieBend werden neue Modellparameter berechnet, die die Zielfunktion, d.h. die Likelihood des Modells, lokal maximieren. Man spricht dabei yom maximization oder M-step.
Zur Sch1itzung von Mischverteilungsmodellen mit Hilfe des EM-Algorithmus muss eine Stiehprobe von Beispieldaten vorliegen und die gewiinschte Anzahl von Verteilungen vorgegeben sein. Die versteckten Zufallsvariablen sind dabei die unbekannten Zuordnungen von Datenvektoren zu einzelnen Normalverteilungsdiehten bzw. Musterklassen.
Zur Initialisierung des Verfahrens, dessen Ablauf in Abbildung 4.4 dargestellt ist, mussen zunachst geeignete Startparameter fUr das Mischverteilungsmodell bestimmt werden. Wegen der gegenuber Vektorquantisierem erhOhten Modellkomplexitat ist hierbei keine zufaIlige Festlegung moglich, da das Verfahren in diesem Punkt auBerst sensitiv ist. Allerdings kann mit einem der beiden eingangs skizzierten einfachen Verfahren auf Vektorquantisierungsbasis leieht ein brauchbares initia-
les Mischverteilungsmodell bestimmt werden. Neben den initialen Basisverteilungsparametem JL?
Kf = und mussen lediglich noch die Mischungsgewichte e? r~~j I berechnet werden, die den
gesch1itzten a-priori Wahrscheinlichkeiten P (Wi) der korrespondierenden Musterklassen Wi entsprechen.
1m E-step des Algorithmus werden in Abhangigkeit vom aktuellen Modell 9m die Walrrscheinlichkeiten fur die Zuordnung eines Vektors zu einer der Codebuchklassen Wi bestimmt. Diese aposteriori Wahrscheinlichkeiten lassen sich fUr beliebige Vektoren x E W wie folgt berechnen:
= = P(wiI9m ) p(XIWi,9m )
P(wiI9m ) p(XIWi,9m )
p(xI9m )
~j P(wjI9m ) p(xlwj,9m )
er =
N(xIJLr,Kf)
~j ej N(xIJLr,Kf)
Dabei wird zunachst die Bayes-Regel zur Umformung des Ausdrucks angewandt. Da die Dichte-
funktion p(x 19m ) genau durch das aktuelle Modell beschrieben wird, kann diese im zweiten Schritt
durch die Mischverteilung selbst ersetzt werden.
AuBerdem wird wahrend der Sch1itzung der a-posteriori Wahrscheinlichkeiten sinnvollerweise auch die Likelihood des aktuellen Modells als Summe uber die logarithmierten Diehtewerte der Mischverteilung berechnet.
Ausgehend von diesen Zuordnungswahrscheinlichkeiten zwischen Merkmalsvektoren und Musterklassen werden im nachsten Verarbeitungsschritt, dem M-step, neue Diehteparameter so bestimmt, dass sie die Likelihood des aktuellen Modells fUr die gegebenen Beispieldaten maximieren. Man
66
4 Vektorquantisierung
erhiilt die folgenden Beziehungen zur Neuschiitzung der a-priori Wahrscheinlichkeiten Ci, sowie der Mittelwertvektoren J..ti und der zugeh6rigen Kovarianzmatrizen Ki:
mEw
mEw mEw mEw
Genauso wie beim Vektorquantisierungsdesign ist es auch beim EM-Algorithmus notwendig, in geeigneter Weise fiber die Terminierung des Verfahrens zu entscheiden. In Analogie zum Abbruchkriterium des LIoyd-Algorithmus bietet es sieh im FaIle von MischverteiIungsmodeIlen an, diese
Entscheidung anhand der relativen Verbesserung der Likelihood L(Blw) zu treffen, die man ffir die
aktueIlen ModeIlparameter bei gegebener Stichprobe erhiilt.
1m Unterschied zur klassischen Vektorquantisierung erfolgt beim EM-Algorithmus die Zuordnung von Merkmalsvektoren und Musterklassen - den einzelnen Mischungsverteilungen - nieht eindeutig per Klassifikationsentscheidung, sondem probabilistisch. Man bezeichnet daher die Schiitzung von MischverteiIungsmodeIlen mit diesem Verfahren auch aIs "weiehe Vektorquantisierung".
4.5 Literaturhinweise
Eine umfassende DarsteIlung des Themas Vektorquantisierung findet sieh in der grundlegenden Monographie von Gersho & Gray [Ger 92], an der sich auch die Behandlung des Problemkreises in diesem Kapitel teilweise orientiert [Ger 92, Kapitel 10, S. 309ffund Kapitel 11, S. 345ft]. Eine gute zusammenfassende DarsteIlung findet man in [Hua 01, Kapitel 4.4, S. 163ft].
Der k-means-Algorithmus zur ErsteIlung von Vektorquantisierem wurde von MacQueen entwiekeit [Mac 67]. Nach den InitialeD seiner Erfinder Linde, Buzo & Gray wurde der LBG-Algorithmus benannt [Lin 80]. DarsteIlungen dieser Methode findet man auch in [Ger 92, S. 361f], [Fur 00, S. 395f] oder [Hua 01, S. 169ft]. Die Urheberschaft des Uoyd-Algorithmus ist dagegen nieht eindeutig zu kliiren. Spiitere Beschreibungen des Verfahrens findet man z.B. in [Lin 80] oder [Ger 92, S. 362ft]. In der Literatur wird die Methode hiiufig fiilschlicherweise als k-means-Algorithmus bezeichnet (vgl. z.B. [Rab 93, S. 125], [JeI 97, S. 11], [Fur 00, S. 394f]. [Hua 01, S. 166ft]), obwohl sie sieh von diesem Verfahren fundamental unterscheidet (siehe auch Abschnitt 4.3 Seite 57). Der EMAlgorithmus zur Schiitzung der Parameter statistischer ModeIle mit verborgenen ZufaIlsvariablen geht auf Dempster, Laird & Rubin zurfick [Dem 77]. Zusammenfassende DarsteIlungen dieser sehr aIlgemeinen Methode sowie Beweise ihrer Konvergenz findet man z.B. in [Hua 90, S. 29ft], [ST 95, S. 102ft], [Hua 01, 170ft].
5 IDdden-Markov-Modelle
1m Bereich der Mustererkennung betrachtet man Signale haufig als das Produkt statistisch agierender Quellen. Das Ziel der Signalanalyse ist es daher, die statistischen Eigenschaften dieser angenommenen Signalquellen moglichst genau zu modellieren. Als Basis der Modellbildung stehen dabei lediglich die beobachteten Beispieldaten sowie einschrankende Annahmen uber die Freiheitsgrade des Modells zur Verfiigung. Das zu bestimmende Modell solI aber nicht nur die Generierung gewisser Daten moglichst exakt replizieren, sondem auch Ansatzpunkte zur Segmentierung der Signale in bedeutungstragende Einheiten liefem konnen. Hidden-Markov-Modelle sind in der Lage, beide angesprochenen Modellierungsaspekte zu behandeln. In einem zweistufigen stochastischen Prozess kann Seginentierungsinformation aus den internen Modellzustlinden gewonnen werden, wohingegen die Generierung der Signal datenselbst in der zweiten Schicht erfolgt. Der hohe Verbreitungsgrad dieser Modellierungstechnik geht hauptsachlich auf deren erfolgreichen Einsatz und konsequente Weiterentwicklung im Bereich der automatischen Spracherkennung zuruck. In diesem Forschungsfeld haben Hidden-Markov-Modelle de facto aIle konkurrierenden Ansatze verdrangt und stellen das dominierende Verarbeitungsparadigma dar. Ihre besonders gute Eignung zur Beschreibung zeitlich organisierter Prozesse oder Signale hat insbesondere dazu gefiihrt, dass die ebenfalls sehr erfolgreiche Technik der neuronalen Netzwerke nur in vereinzelten Fallen zur Spracherkennung und bei vergleichbaren Segmentierungsproblemen eingesetzt wurde. Allerdings existiert eine ganze Reihe hybrider Systeme aus einer Kombination von Hidden-MarkovModellen und neuronalen Netzwerken, die versuchen, die Vorteile beider Modellierungstechniken zu nutzen (siehe Abschnitt 5.8.2).
5.1 Definition
Hidden-Markov-Modelle (HMMs) beschreiben einen zweistufigen stochastischen Prozess. In der ersten Stufe handelt es sich urn einen diskreten stochastischen Prozess, der stationlir, kausal und einfach ist. Die betrachtete Zustandsmenge ist dabei endlich. Der Prozess beschreibt also probabilistisch die Zustandsubergange in diesem diskreten, endlichen Zustandsraum. Er kann somit veranschaulicht werden als endlicher Automat mit Kanten zwischen beliebigen Zustanden, die mit Ubergangswahrscheinlichkeiten beschriftet sind. Das Verhalten des Prozesses zu einem bestimmten Zeitpunkt t ist nur yom unmittelbar vorher eingenommenen Zustand abhangig und kann wie folgt charakterisiert werden:
68
5 Hidden-Markov-Modelle
In der zweiten Stufe wird dann zusatzlich zu jedem Zeitpunkt t eine Ausgabe oder Emission Ot generiert. Die Wahrscheinlichkeitsverteilung daftir ist nur vom jeweils aktuell eingenommenen Zustand St abhangig und nicht von weiteren vergangenen Zustanden oder EmissionenI .
Diese Folge von Emissionen ist als Einziges vom Verhalten des Modells beobachtbar, die eingenommene Zustandsfolge dagegen nicht. Diese ist sozusagen "versteckt" (eng!. hidden), woraus sich auch der Begriff Hidden-Markov-Modelle ableitet. Von der AuBensicht auf das Modell- d.h. der Beobachtung der Ablaufe - rtihrt auch die gangigere Bezeichnung fUr die Folge 0 1 , O2 ... OT der Emissionen als Beobachtungs- oder Observationsfolge her. Einzelne Glieder der Folge wollen wir im weiteren als Observationen bezeichnen.
Das Verhalten von HMMs wird in der Mustererkennungsliteratur ausschlieBlich tiber einem endlichen Zeitraum der Lange T betrachtet. Ftir die Initialisierung des Modells zu Beginn dieser Periode dienen Startwahrscheinlichkeiten, die die Zustandsverteilung zum Zeitpunkt t = 1 beschreiben. Ein aquivalent formuliertes Terminierungskriterium fehlt dagegen tiblicherweise. Das Erreichen eines beliebigen Zustands zum Zeitpunkt T beendet also die Aktionen des Modells, und es wird kein weiteres deklaratives oder statistisches Kriterium angewandt, urn Endzustande auszuzeichnen2•
Ein Hidden-Markov-Modelll. Ordnung, das tiblicherweise als A bezeichnet wird, ist daher vollstandig beschrieben durch:
• eine endliche Menge von Zustanden {s 11 :S s :S N}, die in der Literatur meist nur mit ihren
Indizes bezeichnet werden, • eine Matrix A von Zustandstibergangswahrscheinlichkeiten
• einen Vektor 1T' von Zustandsstartwahrscheinlichkeiten
• und zustandsspezifische Emissionsverteilungen
Die Emissionsverteilungen mtissen je nach Typ der Modellausgabe unterschieden werden. 1m einfachsten Fall stammen die Emissionen aus einem diskreten Inventar {01, 02, ... OM} und haben also symbolischen Charakter. Die bj(Ok} sind dann diskrete Wahrscheinlichkeitsverteilungen, die man zu einer Matrix B von Emissionswahrscheinlichkeiten zusammenfassen kann:
Bei dieser Wahl der Emissionsmodellierung spricht man von sogenannten diskreten HMMs.
1In der Tradition der IBM-Forschung werden HMMs leicht modifiziert notiert. Die Emissionen erfolgen bei Zustandsiibergiingen, d.h. an den Kanten des Modells (vgl. z.B. [Jel 97, S. 17]). Diese Formulierung ist jedoch hinsichtlich ihrer Beschreibungsmoglichkeiten absolut iiquivalent zu der hier verwendeten und in der Literatur verbreiteteren Version, wie auch in [Jel 97, S. 35f] gezeigt wird. 2In [Hua 90, S. 150] werden analog zu den Startwahrscheinlichkeiten auch Terminierungswahrscheinlichkeiten verwendet. Bei den zur Analyse von biologischen Sequenzen eingesetzten HMM-Architekturen sind in der Regel spezielle nichtemittierende Start- und Endzustiinde vorgesehen (siehe auch Abschnitt 8.4 Seite l33).
5.2 Emissionsmodellierung
69
Handelt es sich bei den Observationen dagegen urn vektorwertige GroBen x E IR.n erfolgt die
Beschreibung der Emissionsverteilungen auf der Basis kontinuierlicher Dichtefunktionen:
Aktuelle Anwendungen von HMMs flir Signalanalyseaufgaben verwenden ausschlieBlich diese sogenannten kontinuierlichen HMMs, auch wenn die Notwendigkeit zur Modellierung kontinuierlicher Verteilungen die KomplexiUit des Formalismus deutlich erhOht.
5.2 Emissionsmodellierung
Die Beschreibung der Modellemissionen mit diskreten Wahrscheinlichkeitsverteilungen wird in der Literatur liblicherweise zur Einflihrung von HMMs verwendet. Anwendung findet diese Variante auch flir die Analyse von biologischen Sequenzen, da hier auf einem diskreten Symbolinventar von in der Regel 20 Aminosauren aufgesetzt werden kann (vgl. z.B. [Kro 94a]). Flir Signalverarbeitungsanwendungen dagegen werden diskrete Modelle heute kaum noch eingesetzt, da sie einen vorgeschalteten Quantisierers erfordern, urn aus kontinuierlichen Merkmalsreprasentationen von Sprachsignalen oder Handschriftdaten diskrete Observationsfolgen zu erzeugen.
Die Vermeidung dieses Quantisierungsschritts bzw. seine Einbeziehung in die Modellbildung erhOht deutlich die Machtigkeit des HMM-Formalismus. Allerdings ist es dafiir notwendig, kontinuierliche Verteilungen im IR.n geeignet zu reprasentieren. Eine direkte Darstellung durch eine empirische Verteilung wie im diskreten Fall ist hier nicht moglich. Parametrische Beschreibungen sind jedoch nur flir eine kleine Anzahl von Verteilungsklassen bekannt, wie z.B. flir die Normal- oder GauBVerteilung. Flir den gewlinschten Einsatzzweck kommen allerdings solche "einfachen" Modelle kaum in Frage, da es sich ausnahmslos urn unimodale Verteilungen handelt. Mit einem einzigen im Bereich des Erwartungswerts angesiedelten Haufungsgebiet lassen sich nur extrem "gutartige" Daten beschreiben.
Urn beliebige kontinuierliche Verteilungen mit im allgemeinen mehreren komplexen Haufungsgebieten dennoch behandeln zu konnen, bedient man sich daher approximativer Verfahren. Die bekannteste und verbreitetste Technik besteht in der Verwendung von Mischverteilungen (engl. mixture densities) auf der Basis von GauB-Dichten. Man kann namlich zeigen, dass sich jede allgemeine kontinuierliche Verteilung p(x) durch eine Linearkombination von i.a. unendlich vielen Basis-Normalverteilungen beliebig genau approximieren lasst [Yak 70]:
00
p(x)
L Ck N(xiJLk' Kk)
k=l
M
L Ck N(xiJLk' K k)
k=l
Wird flir die Approximation nur eine endliche Anzahl M von Basisverteilungen (engl. mixtures) verwendet, entsteht ein Approximationsfehler, der jedoch durch die geeignete Wahl der Verteilungsanzahl klein gehalten werden kann. Ais Normierungsrandbedingungmlissen sich die nichtnegativen Mischungsgewichte zu Eins summieren.
und
70
5 Hidden-Markov-Modelle
Die allgemeine Form der kontinuierlichen HMMs verwendet daher pro Zustand j eine Mischverteilung zur Beschreibung der Emissionsdichte:
Mj
Mj
L Cjk N(xllLjk' Kjk) = LCjk9jk(X)
(5.1)
k=l
k=l
Die Anzahl M j der verwendeten Mischungskomponenten pro Zustand kann dabei variieren. Jede dieser Normalverteilungen, die im weiteren kurz als gjk(X) bezeichnet werden, besitzt auBerdem
einen eigenen Parametersatz, bestehend aus Mittelwertvektor ILjk und Kovarianzmatrix Kjk .
Man kann ein kontinuierliches HMM auch als diskretes Modell mit zustandsspezifischer "weicher" Quantisierungsstufe auffassen. Die diskrete Ausgabeverteilung findet sich in den Mischungsgewichten wieder, und die verwendeten Basisverteilungen definieren die Quantisierung der Daten. 1m Unterschied zu einem diskreten HMM werden hierbeijedoch keine "harten" Entscheidungen getroffen, sondern es gehen die Dichtewerte aller verwendeten Normalverteilungen in die Berechnung ein.
Da sich bei kontinuierlichen HMMs die Parameteranzahl gegenuber dem diskreten Fall drastisch erhOht, wurde eine Reihe von Techniken entwickelt, urn durch die gemeinsame Nutzung von Modellierungsanteilen die Parameteranzahl zu reduzieren. Solche Methoden werden in Ermangelung eines geeigneten deutschen Begriffs in der Regel als tying (engl.) bezeichnet, und in Abschnitt 9.2 ab Seite 151 noch ausfuhrlicher beschrieben.
Den groBten Bekanntheitsgrad erreichten die von Huang und Kollegen entwickelten sogenannten semi-kontinuierlichen HMMs (engl. semi-continuous bzw. tied-mixture models) [Hua 89, Hua 90]. Bei ihnen wird nur ein einziger Satz von Basisverteilungen zur Konstruktion aller zustandsspezifischen Emissionsdichten verwendet:
M
M
bj(x) = LcjkN(xllLk,Kk) = LCjk9k(X)
(5.2)
k=l
k=l
Dieser globale Vorrat von Komponentendichten gk (x) wird oft auch als Codebuch bezeichnet, da in dieser Modellvariante die Beziehung zu diskreten Modellen mit vorgeschalteter Quantisierung am deutlichsten hervortritt. Die Definition der Emissionsdichten erfolgt analog zur kontinuierlichen Variante. Allerdings entHillt die Zustandsabhlingigkeit bei den Parametern der zugrundeliegenden Normalverteilungen. Auch besteht bei semi-kontinuierlichen HMMs jede der Mischverteilungen aus derselben Anzahl M von Basisdichten.
5.3 Verwendungskonzepte
Der Einsatz von HMMs fur Mustererkennungsaufgaben beruht immer auf der grundlegenden Annahme, dass es sich bei den betrachteten Mustern urn Ausgaben eines - zumindest prinzipiell vergleichbaren stochastischen Modells handelt, und dass dessen Eigenschaften mit HMMs hinreichend gut nachgebildet werden konnen. Eine wesentliche Fragestellung, die an ein vorliegendes HMM gerichtet werden kann, ist daher, wie gut das Modell ein gegebenes Muster - also eine bestimmte Observationsfolge - beschreibt. Zu
5.3 Verwendungskonzepte
71
diesem Zweck muss die Produktionswahrscheinlichkeit P(OI>') der Daten bei bekanntem Modell - oder eine Niiherung davon - berechnet werden. Diese GroBe gibt zum einen an, wie gut ein zur
= Modellierung bestimmter Beispieldaten 0 0 1 , O2 , .•• OT erstelltes Modell >. in der Lage ist,
deren statistische Eigenschaften zu beschreiben. Andererseits Hisst sie sich aber auch als Basis einer Klassifikationsentscheidung heranziehen.
Liegen zwei oder mehr HMMs >'i vor, die die statistischen Eigenschaften von Mustern aus unter-
schiedlichen Klassen ni nachbilden, kann die Klassifikation einer gegebenen Sequenz von Testdaten 0 in diejenige Klasse nj erfolgen, die die a-posteriori Wahrscheinlichkeit P(>'jIO) maximiert.
(5.3)
Bei der Auswertung dieses Ausdrucks stellt die Wahrscheinlichkeit P(0) der Daten selbst eine fur
die Klassifikation - bzw. die Maximierung von P(>'iIO) - irrelevante, da von >'i unabhangige
und somit konstante GroBe dar. Es genugt daher fur die Bestimmung der optimalen Klasse, nur den
Zahler aus Gleichung (5.3) zu betrachten.
Allerdings mussen hierfur zusatzlich noch die a-priori Wahrscheinlichkeiten P(>'i) der einzelnen Modelle angegeben werden. Zur Vereinfachung werden diese daher haufig vernachlassigt, so dass
die Klassifikationsentscheidung allein auf der Basis der Produktionswahrscheinlichkeit P (0 I>'i)
getroffen wird.
Ein solches Vorgehen kann zur Klassifikation einzelner, nicht weiter zu segmentierender Testdatensatze mit Hilfe von getrennt vorliegenden Modellen zur Beschreibung unterschiedlicher Klassen eingesetzt werden. Auf diese Weise lassen sich z.B. Einzelworterkennungsaufgaben losen oder 10kale Ahnlichkeiten in biologischen Sequenzen analysieren (vgl. [Dur 00, S. 87ffJ).
Die reine Auswertung der Produktionswahrscheinlichkeit ermoglicht jedoch ausschlieBlich Klassifikationsentscheidungen auf bereits vollstandig segmentierten Daten. Daher ist im Kontext der HMM-Technologie eine andere Verwendungsweise von groBerer Bedeutung, die die integrierte Segmentierung und Klassifikation von Datensequenzen erlaubt. Hierbei geht man davon aus, dass die Moglichkeit besteht, einzelne bedeutungstragende Einheiten einer Observationsfolge mit Teilstrukturen eines groBeren Modells zu assoziieren. In der Regel wird dies mittels eines konstruktiven Ansatzes erreicht. Zuerst werden kleine Modelle fUr bestimmte elementare segmentale Einheiten erzeugt, wie z.B. fUr Sprachlaute, Buchstaben oder kurze Aminosauresequenzen. Diese lassen sich dann unter Berucksichtigung bestimmter Abfolgerestriktionen zu groBeren Verbundmodellen zusammensetzen. In der Spracherkennung konstruiert man so aus Einzellauten Worter und schlieBlich ganze AuBerungen. In der Bioinformatik werden Modelle fUr Familien von Proteinen aufgebaut.
Bei einem solchen komplexen HMM liefert die Produktionswahrscheinlichkeit P(01>') kaum noch
relevante Information uber die betrachteten Daten. Vielmehr mussen hier die internen Ablaufe bei
= der Erzeugung der Observationsfolge 0 0 1 , O2 , ••• OT mit dem Modell >. aufgedeckt werden, = d.h. die dabei eingenommene Zustandsfolge s 81, 82, ... 8T. Auf dieser Basis kann dann ein
Ruckschluss auf die beteiligten Teilmodelle sowie eine Segmentierung der Observationsfolge in diese Einheiten erfolgen. In einem stochastischen Formalismus ist dies jedoch nur probabilistisch
72
5 Hidden-Markov-Modelle
maglich. Man ermittelt also diejenige Zustandsfolge 8*, die bei gegebenem Modell ). die Produktionswahrscheinlichkeit P(O, 8*1).) fUr die Daten maximiert. Dieses Verfahren wird in der Regel als Dekodierung bezeichnet, da man die Generierung von Observationen durch das Modell als die Kodierung der internen Zustandsfolge in beobachtbare Einheiten auffassen kann.
SchlieBlich ist noch die wichtige Frage zu kHiren, wie uberhaupt ein Modell erzeugt werden kann, das die statistischen Eigenschaften bestimmter Daten gut genug nachbildet, urn zu Klassifikationsoder Erkennungszwecken eingesetzt zu werden. Zwar Hisst sich durch Betrachtung der Produktionswahrscheinlichkeit bewerten, wie gut ein gegebenes Modell vorliegende Daten beschreibt, es ist jedoch kein Algorithmus bekannt, der das fUr einen bestimmten Zweck optimale Modell aufgrund von Beispieldaten erzeugen kannte. Es gelingt lediglich, ein bereits bestehendes Modell ). zu
verbessern, so dass das optimierte Modell Adie verwendeten Beispieldaten mit - im statistischen
Sinne - gleicher oder haherer Qualitat reprasentiert. Wie bei den meisten iterativen Optimierungsverfahren ist auch hierbei die Wahl eines geeigneten Startmodells von entscheidender Bedeutung.
Die oben skizzierten Verwendungskonzepte werden in der Literatur vielfach als drei fundamentaIe Problemstellungen fUr HMMs formuliert3. Das sogenannte Evaluierungsproblem beschaftigt sich mit der Fragestellung, wie fur ein bestimmtes Modell die Wahrscheinlichkeit ermittelt werden kann, mit der dieses eine gegebene Observationsfolge erzeugt. Den Ruckschluss auf die internen Ablaufe von HMMs betrachtet das sogenannte Dekodierungsproblem. Die schwierige Suche nach dem zur Beschreibung bestimmter Beispieldaten und damit fUr eine bestimmte Anwendung optimalen Modell bezeichnet man schlieBlich als Trainingsproblem.
Folgt man klassischen Darstellungen von HMMs, die zum uberwiegenden Teil durch Rabiner gepragt wurden [Rab 89], so existiert zur Lasung jedes dieser Probleme ein Algorithmus. Dabei bleibt jedoch vallig unberticksichtigt, dass vielfach alternative Methoden existieren und einzelne Algorithmen sich auch zu verschiedenen Zwecken einsetzen lassen. Daher wird im folgenden die restriktive Strukturierung der HMM-Theorie in Paare von Problemen und zugeharigen Algorithmen durchbrochen. Die Darstellung orientiert sich vielmehr am jeweiligen Verwendungszweck, d.h. es werden Methoden zur Bewertung, zur Dekodierung und zur Parameterschatzung vorgestellt.
5.4 Notation
In der Literatur findet man bei formalen Beschreibungen von HMMs eine relativ einheitliche Notation. Start- und Ubergangswahrscheinlichkeiten, das Modell selbst sowie viele der in den folgenden Abschnitten vorgestellten abgeleiteten GraBen werden mit einheitlichen Symbolen bezeichnet. Diese "Standardisierung" ist wohl zum groBen Teil durch den Einfluss des klassischen Artikels [Rab 89] von Rabiner zu erklaren.
Die Notationskonsistenz hart allerdings auf, sobaId man von diskreten zu kontinuierlichen Modellen ubergeht. Prinzipbedingt kannen die Emissionen nun nicht mehr mit diskreten Wahrscheinlichkeitsverteilungen, sondern nur durch kontinuierliche Dichtefunktionen beschrieben werden. Als weitere Konsequenz gehen viele abgeleitete Wahrscheinlichkeitswerte in Dichtewerte tiber.
3Die Idee zur Charakterisierung der Einsatzmoglichkeiten von HMMs in Form von drei fundamentalen Probiemstellungen solI auf Jack Ferguson, Institute for Defense Analyses, Alexandria, VA, USA, zuriickgehen, wie Rabiner in [Rab 89] ohne weiteren Beleg angibt.
5.5 Bewertung
73
Urn eine moglichst groBe Einheitliehkeit der HMM-Notation zu erreichen, behalten wir im folgenden die "diskrete" Sichtweise auf die Modelle bei, solange eine Unterscheidung bzw. spezialisierte Behandlung kontinuierlicher Modellen nieht notwendig ist. Dies bedeutet, dass grundsatzlich von Wahrscheinlichkeiten die Rede sein wird, auch wenn diese im kontinuierlichen Fall gegebenenfalls Dichten sein mlissten. Die Emissionen der Modelle werden in diesen Hillen auch einheitlich als
Folge 0 von Elementen 0 1 , O2 , ... OT bezeiehnet.
Die Unterscheidung zwischen diskreten und kontinuierlichen Modellen erfolgt ausschlieBlich auf der Basis der Werte, die diese Zufallsvariablen Ot annehmen konnen. 1m diskreten Fall bezeichnen
wir die Observationssymbole als Ok, im kontinuierlichen dagegen als Vektor x E mN. In Ana-
= logie zur Wahrscheinlichkeitsschreibweise P(Ot Ok) verwenden wir flir Dichten die Notation = = p(Ot x) bzw. p(Ot Xt). Letztere lasst sieh dann durch Weglassen der expliziten Angabe der
Zufallsvariable Ot in die in der Literatur libliche Notation p(Xt) flir kontinuierliche Emissionen
eines HMMs liberflihren.
Diese Konventionen bewirken zwar keine absolute Konsistenz in der Notation, aber, wie Duda & Hart [Dud 73, S. 173] schon so treffend bemerken4 •.•
... we shall recall Emerson's remark that a foolish consistency is the hobgoblin of little minds and proceed.
5.5 Bewertung
Das verbreitetste MaB zur Bewertung der Genauigkeit, mit der ein HMM die statistischen Eigenschaften bestimmter Daten beschreibt, stellt die sogenannte Produktionswahrscheinlichkeit dar. Sie gibt die Wahrscheinlichkeit daflir an, dass die betrachtete Observationsfolge in beliebiger Weise, also entlang einer beliebigen Zustandsfolge, von einem bestimmten Modell generiert wird. Ein lihnliches, aber leicht modifiziertes Bewertungsverfahren ergibt sich, wenn man nur diejenige Zustandsfolge betrachtet, die die groBte Generierungswahrscheinlichkeit fUr die vorliegenden Daten liefert.
5.5.1 Die Produktionswahrscheinlichkeit
Zur Berechnung der Produktionswahrscheinlichkeit P (0 I>.) einer bestimmten Observationsfolge
o bei gegebenem Modell >. wollen wir zunachst eine intuitiv einfache, aber ziemlich ineffiziente
Methode betrachten.
Da die Emission von Observationen Ot nur von Modellzustanden aus erfolgen kann, muss eine Ob-
= servationsfolge 0 1 , O2 , ••• OT entlang einer korrespondierenden Zustandsfolge s 81, 82, ... 8T
gleicher Lange erzeugt werden. Die Wahrscheinlichkeit hierflir ergibt sich als das Produkt der Emissionswahrscheinlichkeiten entlang der Zustandsfolge, da das Modell gegeben ist und auch die konkrete Zustandsfolge als fest angenommen wird.
T
P(Ols,>') = IIbs,(Ot)
(5.4)
t=1
40riginalzitat von Ralph Waldo Emerson (Amerikanischer Philosoph, 1803 -1882) aus dem Essay "SelfReliance " (1841).
74
5 Hidden-Markov-Modelle
Die Wahrscheinlichkeit, dass ein gegebenes Modell >. eine beliebige Zustandsfolge durchHiuft, er-
gibt sich wiederum einfach als das Produkt der entsprechenden Zustandsubergangswahrscheinlichkeiten. Am Beginn der Foige muss im Prinzip die entsprechende Startwahrscheinlichkeit 1TSl verwendet werden. Die Notation lasst sich allerdings durch die Definition von aOi := 1Ti und So := 0 deutiich vereinfachen.
II II T
T
P(sl>') = 1TS1 a St - 1,St = a St _ 1,St
(5.5)
t=2
t=l
Durch Zusammenfassung der Gleichungen (5.4) und (5.5) lasst sich sofort ermitteln, mit welcher
Wahrscheinlichkeit ein gegebenes Modell >. eine bestimmte Observationsfolge 0 auf eine bestimm-
te Weise - d.h. entlang einer bestimmten Zustandsfolge s - erzeugt.
IIT
P(O,sl>') = P(Ols,>')P(sl>') = aSt_1,Stbst(Ot)
(5.6)
t=l
Durch Verschrankung der Berechnungsvorschriften entsteht ein Ausdruck, der unmittelbar die internen Modellablaufe widerspiegelt: abwechselnd erfolgen Zustandsubergange gemaB a St _ 1,St und die Erzeugung von zustandsabhangigen Emissionen gemaB bst (Ot).
Aufgrund ihrer statistischen Formulierung sind HMMs prinzipiell in der Lage, eine gegebene Ob-
servationsfolge 0 entiang jeder beliebigen Foige von Zustanden s gleicher Lange zu erzeugen,
wenn auch eventuell mit beliebig geringer Wahrscheinlichkeit. Daher mussen zur Berechnung der
Produktionswahrscheinlichkeit P (0I>.) einer bestimmten Observationsfolge 0 aile Zustandsfolgen
der Lange T durch das Modell als "magliche Verursacher" betrachtet werden. Die Gesamtwahr-
scheinlichkeit ergibt sich also als Summe uber aile Wahrscheinlichkeiten, die Observationsfolge 0
und eine spezielle Zustandsfolge s zu erzeugen.
L L P(OI>') = P(O, sl>') = P(Ols, >')P(sl>')
S
s
Diese "brute-force" Methode besteht also darin, aile maglichen Zustandsfolgen der Lange T durch
das Modell aufzuzahlen, die Produktionswahrscheinlichkeit P(Ols, >.) entiang einer speziellen Fol-
ge zu berechnen und die Ergebnisse aufzusummieren. Der Aufwand dieses konzeptionell einfachen
Verfahrens ist jedoch mit OCTNT) exponentiell in der Lange der Observationsfolge, weswegen es
fur praktische Zwecke nicht in Frage kommt.
Forward-Algorithm us
Die groBe Verbreitung der HMM-Technologie ist wesentlich darauf zuruckzufuhren, dass fUr diesen Formalismus effiziente Algorithmen zur Lasung der wichtigsten Problemstellungen bekannt sind. All diese Verfahren nutzen die fUr HMMs geltende Markov-Eigenschaft aus, also ihr begrenztes
"Gedachtnis", das nur die Speicherung eines internen Zustandes erlaubt. 1st von einem Modell >.
ein bestimmter Zustand j zum Zeitpunkt t eingenommen worden, so ist es fur das weitere Verhalten des Modells unerheblich, auf welchem Pfad dieser Zustand erreicht wurde und welche Ausgaben
dabei generiert wurden. Zumjeweils nachsten Zeitpunkt t+ 1 genugt es daher, aile zum vorangegan-
genen Zeitpunkt t maglichen Zustande - namlich die N Zustande des Modells - zu betrachten.
5.5 Bewertung
75
Man definiert: at(i) = P(Ol, O2 , ••• Ot, St = il>')
1. Initialisierung
al(i) := 7ribi(OI)
2. Rekursion fur alle Zeitpunkte t, t = 1 ... T - 1:
at+l(j) := L {at(i) aij} bj(Ot+d i
3. Rekursionsabschluss
N
P(OI>') = L aT(i)
i=1
Abb.5.1 Forward-Algorithmus zur Berechnung der Produktionswahrscheinlichkeit P(OI'>') einer Observati-
onsfolge 0 bei gegebenem Modell .>..
Man kann also die fUr HMMs notwendigen elementaren Berechnungen immer streng entlang der Zeitachse parallel fUr aile Modellzustande durchfuhren.
Fur die Berechnung der Produktionswahrscheinlichkeit P(01>') flihrt dieses Prinzip auf den soge-
nannten Forward-Algorithmus5, dessen Berechnungsablauf in Abbildung 5.1 zusammengefasst ist. Man definiert als sogenannte Vorwiirtsvariablen at(i) die Wahrscheinlichkeit, bei gegebenem Mo-
dell >. den Anfang der betrachteten Observationsfolge bis Ot zu erzeugen und zum Zeitpunkt t den
Zustand i zu erreichen.
(5.7)
Auf der Basis dieser GroBe lasst sich ein induktives Verfahren zur Berechnung der Produktionswahrscheinlichkeit fur die gesamte Observationsfolge angeben. Es lauft, wie eingangs skizziert, parallel flir alle Modellzustande entlang der Zeitachse abo Das entstehende Rechenschema ist in Abbildung 5.2 graphisch veranschaulicht.
Fur die Initialisierung der Berechnung bzw. die Verankerung der Induktion mussen die Vorwlirts-
= variablen al (i) zum Beginn der Zeitachse, d.h. zum Zeitpunkt t 1, bestimmt werden. Die Wahr-
scheinlichkeit dafur, die erste Observation 0 1 zu generieren und zum Anfangszeitpunkt Zustand i zu erreichen, ergibt sich als Produkt der Startwahrscheinlichkeit 7ri flir Zustand i und der Emissionswahrscheinlichkeit bi (01 ) der Observation in diesem Zustand:
Fur den weiteren Berechnungsverlauf kann man davon ausgehen, dass gemliB des Induktionsprin-
zips die Berechnung der at (i) flir alle vergangenen Zeitpunkte t moglich ist. Es genugt daher, eine Vorschrift anzugeben, wie aus diesen GroBen die Vorwartsvariablen at+l (j) zum jeweils nachsten
Zeitpunkt ermittelt werden konnen.
Um auf beliebige Weise die um eine Observation Ot+! verlangerte Anfangssequenz der Observationsfolge 0 1 , O2 , ••• ,Ot, Ot+l zu erzeugen und Zustand j zu erreichen, mussen alle Moglichkeiten
SWie sein Name schon andeutet existiert zum Forward-Algorithmus ein passendes Gegenstlick, das als BackwardAlgorithmus bezeichnet wird. Zusammen bilden sie den sogenannten Forward-Backward-Algorithmus, der im Rahmen des HMM-Parametertrainings in Abschnitt 5.7 noch insgesamt vorgestellt werden wird.
76 Zustande
5 Hidden-Markov-Modelle
j
o
0
t +1
Zeit
Abb.5.2 Rechenschema zur Bestimmung der Vorwartsvariablen at(i) mit Hilfe des Forward-Algorithmus
betraehtet werden, 01, O2 , .•. ,Ot zu generieren, was genau den at(i) entsprieht, und dann einen Zeitsehritt weiterzusehalten. Die Vorwartsvariable at+! (j) ergibt sich daher als Summe der at(i) tiber alle mogliehen Vorgangerzustande i inklusive der jeweiligen Ubergangswahrseheinliehkeit aij zum aktuellen Zustand. Zusatzlieh muss die Observation Ot+! gemaB bj(Ot+d erzeugt werden:
(5.8)
Am Ende der Bereehnungen zum Zeitpunkt T erhalt man N versehiedene Wahrseheinliehkeiten aT (i), auf beliebige Weise die Observationsfolge 0 zu generieren und Zustand i zu erreiehen. Die insgesamte Produktionswahrseheinliehkeit P(OIA) erhalt man daraus als Summe iiber alle diese Wahrseheinliehkeitsanteile.
L N
P(OIA) = aT(i)
i=l
5.5.2 Die "optimale" Produktionswahrscheinlichkeit
Zur mathematiseh exakten Ermittlung der Gesamtproduktionswahrseheinliehkeit war es unabdingbar, alle mogliehen Pfade durch das jeweilige Modell bei der Berechnung einzubeziehen. Fiir die Bewertung der Modellierungsgiite eines HMMs ist diese summarisehe Betrachtung jedoch nicht
5.5 Bewertung
77
= = Man definiert: 8t (i)
max P(OI, O2 , ... Ot, 81, 82,.·. 8t-l' 8t il>')
1. lnitiaIisierung
81(i) = 1Tibi(Od
2. Rekursion
flir aIle Zeitpunkte t, t = 1 ... T - 1: = 8t+1(j) m~x{8t(i)aij} bj(OtH)
t
3. Rekursionsabschluss
P*(OI>') = P(O, 8*1>') = m~8T(i) t
Abb. 5.3 Algorithmus zur Berechnung der maximalen Produktionswahrscheinlichkeit p. (OIA) einer Observationsfolge 0 entlang des hierfiir optimalen Pfades bei gegebenem Modell A.
notwendigerweise das einzig sinnvolle Vorgehen. Es geht dabei namlich die Moglichkeit verloren, die Spezialisierung der Modellierungsanteile innerhalb des Gesamtmodells zu beurteilen. Betrachtet man dagegen nur die jeweils optimale Moglichkeit, mit einem gegebenen Modell eine bestimmte Observationsfolge zu erzeugen, so lasst sieh ein im Mittel befriedigendes von einem im Einzelfall guten Modell unterscheiden.
Lasst man Effizienzgesiehtspunkte auBer Acht, so kann man die optimaIe Produktionswahrschein-
lichkeit P*(OI>') - d.h. die optimale Wahrscheinlichkeit P(O, 8*1>') die Observationsfolge ent-
lang eines speziellen Pfades zu erzeugen - durch Maximierung tiber aile durch Gleichung 5.6 gegebenen Einzelproduktionswahrscheinlichkeiten ermitteln.
P*(OI>') = P(O, 8*1>') = maxP(O, 81>') 8
Ein effizientes Verfahren zur Berechnung dieser GroBe erhalt man in leiehter Abwandlung des Forward-Algorithmus unter Anwendung der dort bereits beschriebenen Uberlegungen zum endlichen Gedachtnis von HMMs. Die resultierende Methode, deren Berechnungsablaufe in Abbildung 5.3 zusammengefasst sind, ist Teil des Viterbi-Algorithmus, dessen Ziel allerdings die Bestimmung des optimalen Pfades selbst ist. Daher wird an dieser Stelle nur ein Teilaspekt des Verfahrens beschrieben und der Gesamtalgorithmus im Rahmen der Modelldekodierung im folgenden Abschnitt 5.6 vorgestellt.
Ais HilfsgroBe definiert man ftir dieses Verfahren mit 8t (i) die maximale Wahrscheinlichkeit, das Anfangssegment der Observationsfolge bis zum Zeitpunkt t entlang eines beliebigen Pfades mit Endzustand i zu erzeugen.
(5.9)
Das rekursive Schema zur Berechnung dieser partiellen Pfadwahrscheinlichkeiten 8t (i) lauft vollig analog zur Auswertung der Vorwiirtsvariablen Qt(i) beim Forward-Algorithmus abo Abbildung 5.4
= veranschaulicht graphisch das entstehende Verfahren. Zum Zeitpunkt t 1 erhiilt man die initialen
81(i) trivialerweise als Produkt aus der Startwahrscheinlichkeit 1Ti des jeweiligen Zustands und der Emissionswahrscheinlichkeit bi (01 ) des ersten Elements der Observationsfolge. Eine Optimierung tiber variable Anteile der Zustandsfolge ist noch nieht notwendig.
78 Zustande
o
o
?3, ~
\ max \ \
?3~ C)", \0
j
O;)~8H,(j)
~ ~'(i)O""
,
,
/
c
~ / ':, /
0
0
5 Hidden-Markov-Modelle
t
t+l
Zeit
Abb.5.4 Rechenschema zur Bestimmung der partiellen Pfadwahrscheinlichkeiten 8t (i)
Da die Wahrscheinlichkeiten der jeweils optimalen Teilpfade 6t (i) fUr aIle vergangenen Zeitpunkte gemaB Induktionsprinzip als bekannt vorausgesetzt werden konnen, miissen lediglich die optimalen Wahrscheinlichkeiten 6t+l (i) der urn ein Element verlangerten Pfade berechnet werden. Hierzu werden aIle moglichen Vorganger ides jeweiligen Zustands j betrachtet, und die maximale Wahrscheinlichkeit ermittelt, einen der bis dorthin reichenden Pfade gemaB der Ubergangswahrscheinlichkeit aij zum aktuellen Zustand fortzusetzen. Die aktuelle Observation Ot+l muss dann noch gemaB bj(Ot+d erzeugt werden.
6t+l(j) = m,ax{6t(i)aij}bj (Ot+d
Die optimale Produktionswahrscheinlichkeit P* (0I'>") erhalt man nach Abschluss der Berechnungen als Maximum iiber alle optimalen Moglichkeiten 6T(i), einen bestimmten Zustand i zum Endzeitpunkt T zu erreichen, da bei HMMs iiblicherweise aIle moglichen Zustande auch als Abschluss eines giiltigen Pfades durch das Modell in Frage kommen6.
P*(OI'>") = P(O, 8*1'>") = m,ax6T(i)
Man erhalt somit analog zum Forward-Algorithmus ein BewertungsmaB fiir die Modellierungsgiite eines Modells .>.. in Abhangigkeit von Beispieldaten O. Dabei wird im Gegensatz zur Produktionswahrscheinlichkeit nur die optimale Generierungsmoglichkeit der Observationsfolge beriicksichtigt.
6Sofem speziell ausgezeichnete Endzustiinde verwendet werden sollen (vgl. z.B. [Dur 00, S. 51]), muss die Maximierung auf diese Zustandsmenge eingeschrankt werden. Altemativ oder auch zusatzlich lassen sich optionale Terminierungswahrscheinlichkeiten bei der abschlieBenden Bewertungsauswahl beriicksichtigen (vgl. z.B. [Hua 90, S. 150]).
5.6 Dekodierung
79
Allerdings kann die optimale Zustandsfolge s* selbst aufgrund der bislang dargestellten Berechnungschritte allein nicht bestimmt werden.
Insbesondere im Bereich der Spracherkennung wird die WahrscheinIichkeit P* (OIA) des optimalen Pfades haufig anstatt der GesamtproduktionswahrscheinIichkeit P ( 0 IA) verwendet. Dieses Vorgehen kann dadurch gerechtfertigt werden, dass die WahrscheinIichkeit zur Generierung der Daten 0 entlang des optimalen Pfades s* die zur Bestimmung von P(0IA) notwendige Summation fiber aIle moglichen Pfade dominiert und damit stark mit dieser GroBe korreliert ist [Mer 91]. AuBerdem ist die Berechnung der partiellen PfadwahrscheinIichkeiten dt (i) in der Praxis deutlich effizienter als die der Vorwartswahrscheinlichkeiten. Wie noch in Kapitel 7 ausfUhrlicher erliiutert werden wird, transformiert man fibIicherweise beim Rechnen mit HMMs die WahrscheinIichkeitswerte in den 10garithmischen Bereich. Die zur Bestimmung der 8t (i) notwendigen MultipIikationen gehen dabei in Summationen fiber. Die Maximierungen werden durch eine solche monotone Abbildung nicht beeinflusst. Die zur Berechnung der VorwiirtswahrscheinIichkeiten erforderIiche Summation von WahrscheinIichkeitswerten ist dagegen im 10garithmischen Bereich nur mit einigem Aufwand zu realisieren.
5.6 Dekodierung
Sofern die einzelnen Zustiinde eines Modells fUr bestimmte bedeutungstragende Segmente der modellierten Daten stehen, reicht die Betrachtung eines globalen GfitemaBes, wie z.B. der Produktionswahrscheinlichkeit, fUr eine Analyse nicht mehr aus. Vielmehr gilt es, die internen Abliiufe wiihrend der Erzeugung der Observationsfolge aufzudecken. Da dies aber prinzipiell entlang jeder beliebigen Zustandsfolge geschehen kann, ist ein solcher Rfickschluss nur probabilistisch moglich. Man bestimmt daher diejenige Zustandsfolge s* , die bei gegebenem Modell mit maximaler a-posteriori Wahrscheinlichkeit die Observationen erzeugt.
= s* argmaxP(sIO, A)
B
(5.10)
Die a-posteriori Wahrscheinlichkeit einer bestimmten Zustandsfolge s in der rechten Seite der Gleichung 5.10 liisst sich mit Hilfe der Bayes-Regel wie folgt umformen:
P( 10 A) = P(O, slA)
s,
P(OIA)
(5.11)
Ffir eine Maximierung dieser GroBe ist der Beitrag der Produktionswahrscheinlichkeit P(0IA) jedoch unerheblich, da er bei festem Modell und gegebener Observationsfolge konstant ist. Unter Ausnutzung dieser Tatsache liisst sich Gleichung (5.10) vereinfachen und die optimale Zustandsfolge wie folgt ermitteln:
= = s* argmaxP(sIO, A) argmaxP(O, slA)
B
B
Dieser optimale Pfad s* entspricht genau derjenigen Zustandsfolge, ffir die sich die maximale Wahrscheinlichkeit P*(OIA) zur Erzeugung der Observationsfolge ergibt. Zur Bestimmung von s* konnte man daher im Prinzip den im vorangegangenen Abschnitt 5.5.2 skizzierten "brute force"
80
5 Hidden-Markov-Modelle
Mandefiniert:Ot(i) = max P(Ol,02, ... Ot,Sl,S2, ... St-l,St =iIA)
81,S2,.··St-l
1. Initialisierung
(h(i) := 7l"ibi(Ol)
1/Jl (i) := 0
2. Rekursion
fUr aIle Zeitpunkte t, t = 1 ... T - 1:
Ot+l (j) := m!,J.X {Ot (i)aij} bj (Ot+1)
3. Rekursionsabschluss
P*(OIA) = P(O, 8*IA) = m!,J.XoT(i) ST := argmaxoT(j)
j
4. Riickverfolgung des optimalen Pfades
1/Jt+1(j) := argmax{Ot(i)aij} i
fUr aIle Zeitpunkte t, t = T - 1 ... 1:
= st 1/Jt+1 (st+1 )
Abb. 5.5 Viterbi-Algorithmus zur Bestimmung der optimalen Zustandsfolge s*, die die Produktionswahrscheinlichkeit P(0, s*IA) einer Observationsfolge 0 bei gegebenem Modell A maximiert.
Ansatz zur Ermittlung der optimalen Produktionswahrscheinlichkeit verwenden. Nach Aufzahlung aller moglichen Zustandsfolgen der Lange T und Berechnung der fUr diese jeweils geltenden Produktionswahrscheinlichkeiten mit Hilfe von Gleichung (5.6) wahIt man diejenige Zustandsfolge 8* mit maximaIer Wahrscheinlichkeit aus. Da dieses Verfahren jedoch exponentielle Komplexitat O(TNT) in der Lange der Zustandsfolge aufweist, ist es fUr praktische Anwendungen ungeeignet. Vielmehr erweitert man die in Abschnitt 5.5.2 beschriebene Methode zur effizienten Berechnung von P(0,8* IA) so, dass nicht nur die optimale Bewertung, sondem auch die zugehOrige Zustandsfolge 8* ermittelt werden kann.
Viterbi-Algorithmus
Die effiziente Berechnung der optimalen Zustandsfolge 8* mit Hilfe des sogenannten Viterbi-AIgorithmus verwendet ein induktives Verfahren,das dem Forward-Algorithmus sehr ahnlich ist und sich ebenfalls die Markov-Eigenschaft zunutze macht. Wie bereits in Abschnitt 5.5.2 erlautert, definiert
man Wahrscheinlichkeiten Ot (i) fUr partiell optimaIe Pfade, die das Anfangssegment der Observationsfolge bis Ot mit maximaler Wahrscheinlichkeit erzeugen und in Zustand i enden.
Das Schema zur Berechnung der Ot (i) entspricht weitgehend dem zur Bestimmung der Vorwartsvariablen at (i) mit dem einzigen Unterschied, dass anstatt der Summation tiber die in den Vorganger-
zustanden vorliegenden Wahrscheinlichkeitsanteile eine Maximierung erfolgt. Der resultierende AIgorithmus zur Berechnung des optimalen Pfades ist in Abbildung 5.5 dargestellt.
Ahnlich wie bei der Dynamischen Zeitverzerrung (engl. dynamic time warping), die einen optimaIen Zuordnungspfad zwischen zwei Mustem in einem vergleichbaren Schema berechnet (vgl. z.B. [ST 95, S. 122ft] bzw. [Hua 90, S. 71ft]), ist jede Entscheidung bei der Berechnung der Ot (i)
5.7 Parameterschatzung
81
nur lokal optimal. Die global optimale Wahrscheinlichkeit ist genauso wie die insgesamt optimale Zustandsfolge s* erst nach Auswertung der OT(i) bekannt, d.h. nach Betrachtung der Observationsfolge auf ihrer gesamten Lange. Derjenige Zustand, der OT (i) maximiert, bildet den Abschluss der optimalen Zustandsfolge. Die Ubrigen Folgeglieder mUssen nun yom Ende der Folge her anhand der flir die Berechnung der Ot (i) getroffenen Entscheidungen ermittelt werden. Hierzu definiert man sogenannte "RUckwartszeiger" '¢t (j) entlang der partiellen Pfade, die fUr jedes entsprechende Ot (j) den jeweils optimalen Vorgangerzustand speichern.
'¢t(j) = argmaxot_l(i)aij
i
Der optimale Pfad kann dann, beginnend mit
Sr = argmax£lT(i), i
rekursiv gemaB
in umgekehrter zeitlicher Reihenfolge aufgebaut werden7.
FUr den praktischen Einsatz bedeutet diese Umkehrung der Richtung des Berechnungsablaufs eine wichtige Einschrankung. Die optimale Zustandsfolge kann namlich erst nach Erreichen des Endes der Observationsfolge, also nach Kenntnis der Gesamtheit der zu analysierenden Daten bestimmt werden. Insbesondere flir interaktive Systeme ist es jedoch oft wUnschenswert, RUckmeldungen an den Benutzer in Form von Teilergebnissen - d.h. nach einer Entscheidung flir ein Prafix der optimalen Zustandsfolge - schon wahrend der laufenden Berechnungen geben zu konnen. Solche inkrementelle Dekodierungsverfahren konnen allerdings im allgemeinen nur suboptimale Losungen finden (siehe auch Seite 206).
5.7 Parameterschatzung
FUr alle Einsatzgebiete von HMMs waren idealerweise Modelle zu verwenden, die die statistischen Eigenschaften bestimmter Daten moglichst gut nachbilden. Leider ist jedoch, wie schon in Abschnitt 5.3 erwahnt, kein Verfahren bekannt, das zu einer gegebenen Stichprobe ein in irgendeiner Hinsicht optimales Modellliefern kann. Sofern es jedoch mit Hilfe von Experten-Know-How gelingt, eine geeignete Modellstruktur - d.h. die Anzahl der Zustande und Art der Emissionsverteilungen - vorzugeben und deren freie Parameter mit sinnvollen initialen Werten zu belegen, kann eine iterative Optimierung des Modells in Bezug auf die betrachteten Daten erfolgen. Diese schrittweise Verbesserung der Modellparameter bis zu einer flir den jeweiligen Einsatzzweck ausreichenden Qualitat bezeichnet man Ublicherweise als Training des Modells.
7Die Entscheidung flir den optimalen Vorgangerzustand ist i.a. nicht eindeutig. Es konnen mehrere identisch bewertete Foigen 8;; existieren, die Gleichung (5.6) maximieren. Bei der praktischen Berechnung ist daher eine Regel ZUT Aufiosung dieser Ambiguitat notwendig, wie z.B. die Bevorzugung von Zustanden mit kleinerem Index.
82
5 Hidden-Markov-Modelle
5.7.1 Grundlagen
Die im folgenden vorgestellten Verfahren unterscheiden sich im wesentlichen bezuglich des verwendeten QualitatsmaBes zur Bewertung der Modellierungsgute eines bestimmten Modells. Beim sogenannten Baum-Welch-Algorithmus erfolgt dies anhand der Produktionswahrscheinlichkeit P (a 1A). Dagegen wird beim Viterbi-Training und dem eng verwandten segmental-k-means Algorithmus nur
a, die Wahrscheinlichkeit P( 8* IA) der jeweils optimalen Zustandsfolge betrachtet.
Allen diesen Verfahren liegt das Prinzip zugrunde, die Parameter eines gegebenen Modells A einer Wachstumstransformation zu unterwerfen, d.h. die Modellparameter so zu modifiiieren, dass
die Bewertung PC ... I.A) des veranderten Modells .A diejenige des Ausgangsmodells ubertrifft. Es
besteht allerdings die Moglichkeit, dass ein bestimmtes Modell bezuglich des jeweiligen Optimierungsverfahrens einen Fixpunkt darstellt, so dass keine Bewertungsverbesserung mehr moglich ist und das jeweilige QualiMsmaB gleich bleibt8. 1m allgemeinen garantieren die Parameterschatzverfahren daher nur ein monotones Wachstum der Modellierungsgute:
Intuitiv betrachtet beruhen die angesprochenen Parameterschiitzverfahren darauf, die Aktion des Modells bei der Erzeugung einer Observationsfolge zu "beobachten". Die aktualisierten Zustandsubergangs- und Emissionswahrscheinlichkeiten werden dann einfach durch die relativen Haufigkeiten der entsprechenden Ereignisse ersetzt. Aufgrund der statistischen Formulierung von HMMs ist der Ruckschluss auf interne Abliiufe jedoch - wie schon an anderer Stelle festgestellt - nur probabilistisch moglich. Man kann aber in Abhangigkeit yom gegebenen Modell und der betrachteten Observationsfolge die erwartete Anzahl relevanter Ereignisse - d.h. von Zustandsubergangen und Emissionen - ermitteln. Wenn man aus Einfachheitsgrunden nur diskrete Modelle betrachtet9 und keine separaten Schatzformeln fUr Startwahrscheinlichkeiten angibtlO , lassen sich die aktualisierten Modellparameter yom Prinzip her wie folgt bestimmen:
erwartete Anzahl der Ubergange von Zustand i nach j erwartete Anzahl der Ubergange von Zustand i aus
erwartete Anzahl der Emissionen von Ok in Zustand i erwartete Gesamtanzahl der Emissionen in Zustand i
Urn auf die zu erwartenden Zustandsiibergange bzw. Emissionen des Modells riickschlieBen zu konnen, ist es notwendig, die Wahrscheinlichkeit dafUr zu ermitteln, dass zu einem gegebenem Zeitpunkt t yom Modell ein bestimmter Zustand i eingenommen wurde. Diese wollen wir im folgenden kurz als Zustandswahrscheinlichkeit bezeichnen.
Fur ihre Bestimmung existieren zwei grundlegend unterschiedliche Moglichkeiten. Betrachtet man
pea, als Optimierungskriterium nur die Wahrscheinlichkeit
8*IA), die Observationsfolge entlang
des dafUr optimalen Pfades zu erzeugen, lasst sich direkt uberpriifen, ob ein bestimmter Zustand i
8In der Praxis bedeutet dies, dass sich das gewiihlte BewertungsmaB im Rahmen der verfiigbaren Reehengenauigkeit nieht mehr messbar veriindert. 9Die Optimierung allgemeiner kontinuierlieher Misehverteilungen ist natiirlieh mit allen Trainingsverfahren moglieh, stellt jedoeh dabei immer den komplexesten Teil des Verfahrens dar. !ODie aktualisierten Startwahrseheinliehkeiten iri konnen als Spezialfall der Obergangswahrseheinliehkeiten ILij aufgefasst und daher analog bereehnet werden.
5.7 Parameterschatzung
83
= zu einem Zeitpunkt t vorlag. Die Zustandswahrscheinlichkeit P*(St ilO, A) nimmt daher nur
die Werte Null und Eins an und kann tiber eine auf der optimalen Zustandfolge s* operierende
charakteristische Funktion definiert werden:
I falls s; = i und s* = argmaxP(s, 0IA)
P* (St = ilO, A) = Xt(i) = {
s
o sonst
(5.12)
1st das GtitemaB jedoch die Produktionswahrscheinlichkeit P(OIA), bei der aIle maglichen Pfade durch das Modell betrachtet werden, so gestaltet sich die Berechnung der a-posteriori Wahrscheinlichkeit eines Zustands zu einem gegebenen Zeitpunkt etwas aufwendiger.
Forward-Back ward-Algorithm us
Zur Berechnung der a-posteriori Wahrscheinlichkeit P(St = ilO, A) eines Zustandes i zum Zeitpunkt t bei gegebener Observationsfolge 0 und bekanntem Modell A lieBe sich nattirlich ein "bruteforce" Ansatz verwenden. Allerdings haben wir in Abschnitt 5.5 mit den Vorwartsvariablen (}:t(i) bereits GraBen kennengelernt, die in begrenztem Umfang Aussagen tiber das Vorliegen eines Zustandes zu einem bestimmten Zeitpunkt machen. Es fehlt lediglich die Wahrscheinlichkeit fur die Erganzung des Restes der partiellen Observationsfolge yom aktuellen Zustand aus.
Diese GroBe wird als Ruckwiirtsvariable bezeichnet. Sie gibt die Wahrscheinlichkeit dafur an, bei gegebenem Modell A yom Zustand j aus die partielle Observationsfolge Ot+!, 0t+2, ... OT ab
Zeitpunkt t + 1 zu erzeugen.
(5.13)
Sie lasst sich effizient mit dem Gegensttick des Forward-Algorithmus berechnen - dem sogenannten Backward-Algorithmus - und bildet das Pendant zur Vorwartsvariable (}:t(i). Beide Algorithmen zusammen werden in der Literatur haufig als Einheit betrachtet und als Forward-BackwardAlgorithmus bezeichnet.
Urn die gesuchte Zustandswahrscheinlichkeit P(St = ilO, A) auf der Basis der Vorwarts- und Rtickwartsvariablen zu bestimmen, schreiben wir diese mit Hilfe der Bayes-Regel wie folgt urn:
P(S = '10 A) = P(St = i, °IA)
t z,
P(OIA)
(5.14)
Die Produktionswahrscheinlichkeit P(OIA) kann mit Hilfe des Forward-Algorithmus berechnet werden. Der Zahler der rechten Seite von Gleichung (5.14) entspricht direkt dem Produkt aus korrespondierenden Vorwarts- und Rtickwartsvariablen (vgl. Gleichungen (5.7) bzw. (5.13»:
P(St = i, 0IA)
P(Ol, O2 , ••• Ot, St = iIA)P(Ot+!, Ot+2, ... OTISt = i, A) = (}:t (i) !3t (i)
Die a-posteriori Wahrscheinlichkeit des Zustandes i zum Zeitpunkt t, die tiblicherweise als "ft (i) bezeichnet wird, kann daher wie folgt berechnet werden:
.
.
(}:t (i)!3t (i)
"ft(z) = P(St = zlO, A) = P(OIA)
(5.15)
84
Man definiert: aAi) = P(Ol, O2 , ... Ot, St = il>') 1. Initialisierung
a1(i) := 'lribi(Ol) 2. Rekursion
fUr aIle Zeitpunkte t, t = 1 ... T - 1: at+1 (j) := L {at(i)aij} bj(OtH)
i 3. Rekursionsabschluss
N
P(OI>') = L aT(i) i=l
Abb. 5.6 Forward-Backward-Algorithmus
5 Hidden-Markov-Modelle
f3T(i) := 1 bzw. t = T - 1 ... 1: f3t(i) := Laij bj (Ot+l)f3tH(j)
j N
P(OI>') = L 'lri bi(01)f31(i)
i=l
Die Auswertung der Rtickwiirtsvariablen f3t (i) entspricht - wie ihr Name schon andeutet - fast einer Spiegelung des Forward-Algorithmus. Die Verankerung des induktiven Berechnungsverfahrens erfolgt am Ende des durch die Observationsfolge definierten ZeitintervaIls zum Zeitpunkt T. Trivialerweise ist die Wahrscheinlichkeit, von einem beliebigen Zustand zum Zeitpunkt Taus keine weiteren Observationen mehr zu erzeugen, Eins.
f3T(i) := 1
Setzt man gemaB Induktionsannahme die 13tH (j) ftir aIle zuktinftigen Zeitpunkte t + 1 als bekannt
voraus, so kann man durch Betrachtung aIler moglicher FortfUhrungen einer Zustandsfolge yom aktuellen Zustand i aus die folgende rekursive Berechnungsvorschrift fUr die Rtickwartsvariablen f3t (i) ableiten:
I > f3t(i) := ij bj (Ot+df3tH(j)
j
(5.16)
Zum Abschluss des Verfahrens erhalt man - wie beim Forward-Algorithmus auch - die Produktionswahrscheinlichkeit P(01>') durch Summation tiber aIle Rtickwartsvariablen 131 (i) zum Zeit-
punkt t = 1 und Berticksichtigung der Startwahrscheinlichkeit sowie der Generierung der ersten
Observation 0 1 im jeweiligen ZustandI I:
L N
P(OI>') = 'lri bi(Odf31(i) i=l
In Abbildung 5.6 sind beide Algorithmen zusammenfassend dargesteIlt, urn die auBerordentliche Symmetrie der Berechnungsablaufe zu verdeutlichen. Das fUr die Rtickwartsvariablen entstehende Rechenschema ist in Abbildung 5.7 graphisch veranschaulicht.
11 Die Tatsache. dass sich die Produktionswahrscheinlichkeit P (0 I)..) sowohl iiber den Vorwlirts- als auch den Riickwartsalgorithmus gewinnen lasst, kann in der Praxis zur Uberpriifung der Berechnungen auf Konsistenz und Genauigkeit ausgenutzt werden.
5.7 Parameterschiitzung
85
Zustlinde
o
0
j
o
t
t+l
Zeit
Abb. 5.7 Rechenscherna zur Bestirnrnung der Rtickwiirtsvariablen f3t (i) mit Hilfe des Backward-Algorithrnus
5.7.2 Trainingsverfahren
Die probabilistische Moglichkeit zur Definition der Zustandswahrscheinlichkeit via 'Yt (i) bzw. ihre deterministische Variante Xt (i) bilden die Basis fOr die im folgenden behandelten Trainingsverfahren. Mit Hilfe der zeitlichen Zuordnung zwischen Modellzustiinden und Elementen der Observationsfolge lassen sich nicht nur Zustandsubergangswahrscheinlichkeiten schiitzen, sondern auch die Parameter der zustandsspezifischen Emissionsverteilungen. Ftir diskrete Modelle kann man hierftir ebenfalls einfache Schiitzgleichungen angeben. Die erhOhte Komplexitiit bei der Verwendung von Mischverteilungsmodellen zur Emissionsmodellierung ist dadurch bedingt, dass auch bei isolierter Betrachtung zu deren Berechnung keine geschlossenen Losungen existieren. Vielmehr mussen iterative Optimierungsstrategien zum Einsatz kommen, die sich jedoch mit den fur HMMs insgesamt angewandten Trainingsverfahren kombinieren lassen.
Baum-Welch-Algorithmus
Das verbreitetste Verfahren zur Optimierung von HMMs stellt der sogenannte Baum-Welch-Algorithmus dar. Ais Optimierungskriterium verwendet er die Gesamtproduktionswahrscheinlichkeit
P (0 I>.). Er verbessert also ein gegebenes Modell >. in Abhiingigkeit von bestimmten Beispieldaten
86
5 Hidden-Markov-Modelle
o so, dass das optimierte Modell ~ die Trainingsmenge mit gleicher oder groBerer Wahrscheinlich-
keit erzeugt:
P(OI~) ~ P(OI>')
Die Gleichheit der beiden Ausdriicke gilt nur dann, wenn mit den Parametern des Ausgangsmodells
>. bereits ein lokales Maximum der Optimierung im Raum aller moglichen Modelle erreicht wurde.
Bei diesem Verfahren werden alle Modellparameter durch ihre bedingten Erwartungswerte, bezo-
gen auf das gegebene Ausgangsmodell >. und die Trainingsdaten 0, ersetzt. Der Baum-Welch-
Algorithmus stellt somit eine Variante des EM-Algorithmus dar, der im allgemeinen Parameter mehrstufiger stochastischer Prozesse mit versteckten Zustandsvariablen nach dem Maximum-Likelihood-Kriterium optimiert ([Dem 77], siehe auch Abschnitt 4.4 Seite 62).
Die Grundlage des Verfahrens bilden einige GroBen, die autbauend auf den Vorwarts- und Riick-
wartsvariablen im statistischen Sinne Riickschliisse auf die internen Ablaufe eines Modells >. bei
der Generierung vorliegender Daten 0 zulassen. Neben der mit "It (i) bezeichneten a-posteriori Wahrscheinlichkeit peSt = ilO, >.) fUr das Auftreten eines Zustands i zum Zeitpunkt t werden
a-posteriori Wahrscheinlichkeiten flir Zustandsiibergange und - flir kontinuierliche Modelle auf Mischverteilungsbasis - auch Wahrscheinlichkeiten flir die Auswahl einzelner Mischverteilungskomponenten M t zu einem bestimmten Zeitpunkt benotigt.
Die a-posteriori Wahrscheinlichkeit peSt = i, StH = jlO, >.) eines Ubergangs von Zustand i nach j zum Zeitpunkt t, die iiblicherweise mit 'Yt(i, j) bezeichnet wirdl2, liisst sich in Anlehnung an Gleichung (5.15) flir "It (i) wie folgt berechnen:
'Yt(i,j) = peSt = i, StH = jlO, >.) =
=
peSt =i,St+l =j,ol>') _ at(i)aij bj (Ot+d13tH(j)
P(OI>')
-
P(OI>')
Der Zahler des letztendlichen Ausdrucks flir "It (i, j) gibt dabei die Wahrscheinlichkeit an, die Observationsfolge zu erzeugen, unter der Einschriinkung, dass ein Ubergang von Zustand i nach j zum Zeitpunkt t stattfindet. Die Biindelung der Berechnungspfade durch das Modell ist in Abbildung 5.8
graphisch veranschaulicht.
In der Literatur erfolgt die Definition der Zustandswahrscheinlichkeit hiiufig erst auf der Basis der a-posteriori Wahrscheinlichkeiten flir Zustandsiibergiinge. Die Wahrscheinlichkeit "It (i), dass zum Zeitpunkt t iiberhaupt Zustand i eingenommen wird, ergibt sich niimlich prinzipiell auch als Randverteilung von "It (i, j) durch Summation iiber alle moglichen Zustandsnachfolger.
N
N
'Yt(i) =P(St =iIO,>') = LP(St =i,StH =jIO,>.) = L'Yt(i,j)
j=l
j=l
Allerdings kann diese Beziehung nur flir Zeitpunkte t < T ausgeniitzt werden, da 'Yt(i,j) nur
ffir diese definiert ist. In der Praxis wird man daher 'Yt(i) entweder direkt per Gleichung (5.15) berechnen oder eine geeignete Erweiterung der Definition von 'Yt(i, j) vornehmen miissen.
12Aufgrund des engen Bedeutungszusammenhangs und urn die Notation nicht unn(!tig mit unterschiedlichen Symbolen
zu Ilberfrachten, wird die Zustandswahrscheinlichkeit einstellig mit "Yt (i) und die Zustandsllbergangswahrscheinlichkeit zweistellig mit "Yt (i, j) bezeichnet.
5.7 Parameterschatzung
87
Zustlinde
o
j
o
o
o
o
t
t+ 1
Zeit
Abb.5.8 Rechenschema zur Bestimmung von "(t(i, j)
Auf def Basis def 'Yt konnen nun fUr HMMs mit diskreten Emissionsverteilungen alle aktualisierten Parameter>' berechnet werden. Die im statistischen Mittel zu erwartende Anzahl von Zustandstiberglingen von i nach j erhlilt man als Summe der Einzeltibergangswahrscheinlichkeiten 'Yt(i, j) tiber alle in Frage kommenden Zeitpunkte13 t = 1,2, ... T - 1. Normiert man diese GroBe auf die erwartete Gesamtanzahl von Uberglingen vom Zustand i aus, so erhlilt man die verbesserten
Schlitzwerte aij fUr die Ubergangswahrscheinlichkeiten des Modells:
T-l
L:: P(St = i, St+l = jlD, >.)
aiJ' = .t.=:l.::.::....=----------
T-l
L:: P(St = ilD, >.)
t=l
T-l
L:: 'Yt (i, j)
t=l
T-l
L:: 'Yt(i)
t=l
(5.17)
Als Spezialfall der Ubergangswahrscheinlichkeiten erhlilt man die folgende einfache Beziehung zur Bestimmung verbesserter Startwahrscheinlichkeiten:
iri = P(SI = ilD, >.) = 'Yl(i)
(5.18)
Die verbesserten diskreten Emissionswahrscheinlichkeiten ergeben sich im wesentlichen analog dazu. Zuerst berechnet man die erwartete Anzahl von Emissionen eines bestimmten Symbols Ok im
13Da HMMs nach gangiger Auffassung beim Erreichen des Endes der Observationsfolge zum Zeitpunkt T keinen Ubergang in einen ausgezeichneten Endzustand dur~hfiihren. ist hier die Einschrankung auf aile kleineren Zeitpunkte notwendig.
88
5 Hidden-Markov-Modelle
Zustand i, indem man die Ubereinstimmung von Ok mit dem jeweiligen Element der Observationsfolge zusatzlich zum Vorliegen des betreffenden Zustands fordert. Normiert auf die erwartete Gesamtanzahl von Emissionen, die yom Zustand j aus generiert werden, erhalt man Schatzwerte bj(Ok) der diskreten Emissionswahrscheinlichkeiten gemaB:
T
L: P(St = j,Ot = oklD, >.)
L: P(St = jlD, >.)
bj (Ok) = -t=_I_-:::T::--_ _ _ _ _ _ _ = _t:_o-::;::-=_O_k______
L: P(St = jlD, >.)
t=1
L: P(St = jlO, >.)
t=1
L: 'Yt(j)
t: Ot=Ok
T
L: 'Yt(j)
t=1 (5.19)
Da eindeutig festgestellt werden kann, ob ein bestimmtes Observationssymbol Ok zu einem gegebe-
nen Zeitpunkt t vorlag, tragen die Wahrscheinlichkeiten P(St = j,Ot = OkID, >.) nur dort positive
Anteile zur Summe im Zahler VOn Gleichung (5.19) beL AIle anderen Terme verschwinden, und die Summation kann entsprechend eingeschrankt und vereinfacht werdenl4.
Bei der Emissionsmodellierung mit Mischverteilungen gilt es, im Gegensatz dazu die Parameter der Mischungsverteilungen selbst - also der einzelnen Normalverteilungsdichten - sowie die Mischungsgewichte zu optimieren. Betrachtet man die Auswertung der Mischungsverteilungen als eine Art Quantisierung, die eine probabilistische Abbildung der Observationen auf abstrakte aber noch nicht bedeutungstragende symbolhafte Einheiten hersteIlt, so ist unmittelbar einzusehen, dass die Berechnung aktualisierter Mischungsgewichte analog zu der von diskreten Emissionswahrscheinlichkeiten erfolgen kann.
Hierzu definiert man ahnlich zur Zustandswahrscheinlichkeit eine HilfsgroBe ~t (j, k) die die Wahrscheinlichkeit daflir angibt, zum Zeitpunkt t im Zustand j die k-te Mischverteilungskomponente zur Erzeugung der kontinuierlichen Observation Ot zu verwendenl5:
N
L: O'.t-l(i) aij Cjk gjk(Ot) (Jt(j) = = = = ~t(j, k) P(St j, Mt kiD, >.) =i=:..::...I_ _--=--:~-:-----­
P(OI>')
(5.20)
Mit Hilfe von Gleichung (5.20) lasst sich eine Schatzgleichung fUr die Mischungsgewichte wie folgt angeben:
T
L: P(St = j, Mt = kiD, >.)
CA jk = - T _ .t,=~I~=- _ _ _ _ _ __
L: P(St = jlD, >.)
t=1
T
L: ~t(j,k)
t=1
T
L: 'Yt(j)
t=1
(5.21)
Die Aktualisierung der Parameter der k-ten Mischverteilungskomponente gjk(X) von Zustand j - also des Mittelwertvektors JLjk und der Kovarianzmatrix Kjk - erfolgt analog zu den in Abschnitt 4.4 Seite 62 vorgestellten Schatzgleichungen flir Mischverteilungsmodelle. Die a-posteriori
14Da zu einem gegebenen Zeitpunkt t das Symbol Ok in der Observationsfolge entweder vorlag oder nicht, nimmt die
Wahrscheinlichkeit peSt = j, Ot = Ok 10, A) entweder den Wert Null an, oder ist gleich peSt = jlO, A) d.h. 'Yt(j).
= 15Piir Zeitpunkt t 1 muss in Gleichung (5.20) der Term LN at-lei) aij durch die Startwahrscheinlichkeit 7rj des ent-
i=1
sprechenden Zustands ersetzt werden.
5.7 Parameterschiitzung
89
Wahrscheinlichkeit P(Wi Ix, (}) der einzelnen Musterklassen muss lediglich durch den Term et (j, k)
ersetzt werden. 1m Unterschied zu den in Abschnitt 3.6 Seite 49 vorgestellten Schiitzgleichun-
= gen (3.8) und (3.9) fUr einzelne Normalverteilungsmodelle gehen Observationen Ot Xt nicht
eindeutig, sondem probabilistisch in den Berechnungsprozess ein. Die Wahrscheinlichkeit dafUr, dass ein bestimmter Observationsvektor Xt zur Schiitzung der Parameter von 9jk (x) herangezogen
= = werden solI, entspricht genau der Wahrscheinlichkeit P (St j, Mt kiD, A), dass die betreffende
Mischungskomponente zur Erzeugung der Ausgabe zum fraglichen Zeitpunkt ausgewiihlt wurde.
Es ergeben sich daher die folgenden Vorschriften zur Berechnung aktualisierter Mittelwertvektoren
itjk und Kovarianzmatrizen Kjk der einzelnen Komponentendichten.
T
T
itjk
= = = = L P(St j, Mt kiD, A) Xt = t=l = T
L et(j, k) Xt
:::t=::.;l:::-_ __ T
L P(St j, Mt kiD, A)
L et(j, k)
t=l
t=l
= = T
L P(St j, Mt kiD, A) (Xt - ftjk)(Xt - ftjk)T
t=l
.
T
L P(St = j, Mt = kiD, A)
t=l
(5.22) (5.23)
=
FUr die in der Praxis einfachere Berechnung dieser GroBen bei nur einmaligem Durchlaufen der Observationsfolge liisst sich die Schiitzgleichung (5.23) fUr die Kovarianzmatrix Kjk der Mischungskomponente unter Ausnutzung der Beziehung (3.4) von Seite 46 wie folgt umschreiben:
LT P(St = j, Mt = kiD, A) Xt X ;
t=l
A AT
T
- JLjkJLjk
L P(St = j, Mt = kiD, A)
t=l
T
L et(j, k) Xt X ;
= t=l T
A AT
- JLjkJLjk
L et(j, k)
t=l
(5.24)
Bei semi-kontinuierlichen Modellen wird, wie in Abschnitt 5.2 eingefUhrt, fUr alle Modellzustiinde ein gemeinsamer Satz von Komponentendichten 9k(X) fUr die Mischverteilungsmodelle verwendet. Da die Mischungsgewichte jedoch nach wie vor zustandsspezifisch sind, ergibt sich fUr sie in diesem FaIle keine veriinderte Berechungsvorschrift. Zur Schiitzung der Parameter JLk und Kk der gemeinsam verwendeten Basisverteilungen 9k (x) muss jedoch berUcksichtigt werden, dass die Wahrscheinlichkeit zur Auswahl einer speziellen Dichte zu einem bestimmten Zeitpunkt bei semi-
90
5 Hidden-Markov-Modelle
Man definiert:
= P(St = iIO,'\)
at (i) aij bj (OtH) 13tH (j)
'Yt(i,i) = P(St = i, StH = iIO,'\) -
P(OI'\)
et(j, k) = P(St = i, Mt = kIO,'\)
N
I: at(i) aij Cjk gjk(Ot) f3t(j)
==i=~l~_ _ _ _~~~_ _ _ __ _
P(OI'\)
1. Initialisierung
Wahle ein geeignetes Startmodell ,\ = (1t", A, B) mit Initialwerten 7ri flir Start-
bzw. aij flir Ubergangswahrscheinlichkeiten sowie Gewichten Cjk und Basisdich-
ten 9jk(X) = N(xlJ.tjk, K jk ) zur Definition der Emissionsdichten bjk(X) =
I:Cjkgjk(X).
k
2. Optimierung
Berechne aktualisierte Schatzwerte >. = (7r,..4., B) der Modellparameter:
T-l
I: 'Yt(i,i) = t=l
o,ij T-l
I: 'Yt(i)
t=l
1Ti = 'Yl(i)
T
I: et(j, k)
CA jk
=
t=l
':"-;;;T---
I: 'Yt(j)
t=l
° 3. Terminierung falls durch das aktualisierte Modell >. das GiitemaB P ( I>') gegeniiber ,\ deutlich verbessert wurde setze ,\ +-- >. und weiter mit Schritt 2 sonstEnde!
Abb.5.9 Baum-Welch-Algorithmus zur Parameterschatzung fiir allgemeine kontinuierliche HMMs. Anpassungen flir diskrete oder semi-kontinuierliche Modelle siehe Text.
5.7 Parameterschatzung
91
kontinuierlichen Modellen unabhiingig von einem konkreten Zustand ist. Sie ergibt sich aus Glei-
chung (5.20) als Randverteilung von et(j, k) durch Summation tiber aIle moglichen Zustande:
P(Mt = kIO,A) = et(k) = L6(j,k)
j
Ersetzt man nun in den Gleichungen (5.22) und (5.24) die Wahrscheinlichkeitsgewichtung der Ob-
servationsvektoren durch et (k), so erhalt man folgende Schatzgleichungen fUr ILk und K k bei semi-
kontinuierlichen Modellen:
T
T
l: P(Mt = klO, A) Xt l: et(k) Xt
jLk
=
t=l
T
=
t=l
T
l: P(Mt = klO, A)
l: et(k)
t=l
t=l
T
T
l: P(Mt = klO, A) xtxT
l: et(k) xtxT
Kk
=
t=l
T
~ ~T t=l
- ILkILk =
T
~ ~T
- ILkILk
l: P(Mt = kIO,A)
l: et(k)
t=l
t=l
(5.25) (5.26)
Die Aktualisierung der Modellparameter gemaB den Schatzgleichungen (5.17), (5.18) und (5.19) fUr diskrete Modelle, unter Anwendung von (5.17), (5.18), (5.21), (5.22) und (5.24) filr solche mit kontinuierlichen Emissionsdichten sowie mit Hilfe von (5.17), (5.18), (5.21), (5.25) und (5.26) ftir semikontinuierlichen Modelle entspricht einem Schritt in einem iterativ optimierenden Trainingsprozess. Ausgehend von einem vorgegebenen initialen Modell A0 muss die Neuschatzung der Parameter so lange wiederholt werden, bis das resultierende Modell eine hinreichende Beschreibungsgtite erreicht hat bzw. keine weiteren Verbesserungen mehr zu erwarten sind. FUr "voIr' kontinuierliche Modelle ist der gesamte Algorithmus in Abbildung 5.9 zusammengestellt.
Viterbi· Training
1m Gegensatz zum Baum-Welch-Algorithmus wird beim sogenannten Viterbi-Training lediglich die
= Wahrscheinlichkeit P* (0 IA) P (0, 8* IA), die Observationsfolge entlang des bestbewerteten Pfa-
des 8* zu erzeugen, durch den Trainingsprozess verbessert. Man kann zeigen, dass das Verfahren ausgehend von einem bestehenden Modell A eine Wachstumstransformation der Parameter realisiert, so dass das veranderte Modell ). eine groBere oder wenigstens gleichbleibende Wahrscheinlichkeit ftir denjeweils optimalen Pfad liefert (vgl. [ST 95, S. 139f]):
P*(OI).) ~ P*(OIA)
Das Verfahren folgt der zu Beginn dieses Unterkapitels gezeichneten intuitiven Vorstellung yom Prinzip des HMM-Trainings in zwei Arbeitsphasen. Zunachst wird mit dem Viterbi-Algorithmus die optimale Zustandsfolge 8* filr die Trainingsdaten mit Hilfe der vorliegenden Modellparameter berechnet. 1m zweiten Schritt werden die Schatzwerte zur Aktualisierung der Modellparameter auf der Basis der empirischen Verteilungen bestimmt, die sich durch die explizite Zuordnung von Observationen und einzelnen Modellzustanden entlang der optimalen Zustandsfolge ergeben.
92
5 Hidden-Markov-Modelle
Man definiert:
falls s; = i und s* = argmaxP(s, 0IA)
8
sonst
1. Initialisierung
Wahle ein geeignetes Startmodell A = (7r, A, B) mit Initialwerten 7fi fur
Start- bzw. aij fUr Ubergangswahrscheinlichkeiten sowie diskreten Emissions-
wahrscheinlichkeiten bj (Ok).
.
2. Segmentierung
Berechne mit Hilfe des Viterbi-Algorithmus (siehe Abbildung 5.5 Seite 80) die
optimale Zustandsfolge s* zur Erzeugung der Daten 0 bei geg. Modell A.
3. Optimierung
Berechne aktualisierte Schatzwerte >. = Crr,..4., iJ) fur aile Modellparameter (au-
Ber 7r, Erlauterung siehe Text):
T-1
L: Xt (i) Xt+1 (j)
t=l = ~
aiJ'
.:..::..~:-----­
T-1
L: Xt (i)
t=l
b~ . ( ) -
J Ok -
L: Xt(j)
t: at =Ok
T
L: Xt(j)
t=l
4. Terminierung
falls durch das aktualisierte Modell >. das GutemaB P* (0I>.) gegenuber A deutlich
verbessert wurde
setze A+-->' und weiter mit Schritt 2
sonstEnde!
Abb. 5.10 Viterbi-Training zur Parameterschatzung fUr diskrete HMMs. Erweiterung fUr kontinuierliche Modelle siehe Text.
Diese Zuordnung lasst sich mit Hilfe der Zustandswahrscheinlichkeit Xt(i) aus Gleichung (5.12) formal beschreiben, deren Berechnung lediglich der Auswertung einer charakteristischen Funktion auf der optimalen Zustandsfolge s* entspricht. Ersetzt man in den Schatzgleichungen des BaumWeich-Algorithmus die dort verwendete probabilistische Version 'Yt(i) durch die eindeutige Zuordnung mit Hilfe von Xt(i), so erhalt man die im Rahmen des Viterbi-Trainings anzuwendenden Vorschriften zur Berechnung aktualisierter Parameter diskreter Modelle. Schatzwerte fur die Zustandsubergangswahrscheinlichkeiten, die prinzipiell durch Auszahlung der Zustandspaare in der optimalen Foige gewonnen werden konnen, ergeben sich gemaB:
T-1
L: P(St = i, St+1 = jls*, 0, A)
iiij =
t=1
...::......::........T=--.,-1---------
L: P(St = ils*, 0, A)
t=1
T-1
L: Xt(i)Xt+1 (j)
t=1
T-1
L: Xt(i)
t=1
(5.27)
Sinnvolle Schatzungen fUr Startwahrscheinlichkeiten erhalt man mit Hilfe des Viterbi-Trainings allerdings nicht. Ais Spezialfall von Gleichung (5.27) wurde man fur die Startwahrscheinlichkeit
5.7 Parameterschatzung
93
?fsi des ersten Zustands si der optimalen Folge den Wert Eins und Null fUr aIle anderen Zustande erhalten. Da aber die Startwahrscheinlichkeiten in praktischen Anwendungen kaum einen Einfiuss ausiiben, bedeutet dies keine relevante Einschrankung des Verfahrens.
Die diskreten Emissionswahrscheinlichkeiten werden direkt durch die empirisch ermittelten Verteilungen bestimmt. Letztere erhalt man durch einfache Auszahlung aller Observationssymbole Ok, die iiber die optimale Zustandsfolge einem bestimmten Modellzustand zugeordnet wurden:
L P(St = ils*, 0, A)
bA • (
) _ _ t :_o....:.'_=--'Ok=----_ _ _ _ __
J Ok -
T
L P(St = ils*, 0, A)
t=l
L Xt(j)
t: O,=Ok
(5.28)
Der Gesamtalgorithmus fUr das Viterbi-Training diskreter HMMs ist in Abbildung 5.10 zusammengestellt.
Die Neuschatzung kontinuierlicher Mischverteilungsmodelle mit Hilfe des Viterbi-Trainings gestaltet sich allerdings deutlich schwieriger, da keine analytischen Verfahren bekannt sind, aus Trainingsbeispielen optimale Parameter solcher Modelle zu bestimmen. Man geht zwar in der Regel davon aus, dass die Anzahl M j der verwendeten Basisverteilungen gleich bleibt, aber dennoch kann eine Neuschatzung der Mischungsgewichte Cjk sowie der Komponentendichten gjk (x) nicht direkt erfolgen.
In [WeI 92] wird hierzu das Maximum-Likelihood-Kriterium zur Verbesserung der optimalen Pro-
duktionswahrscheinlichkeit P(0, s* IA) in Abhangigkeit der Modellparameter A angewandt. Diese
Optimierung kann getrennt fUr die Ubergangswahrscheinlichkeiten aij, wie in Gleichung (5.27), und die Emissionsdichten bj (x) erfolgen. Zwar erhalt man ein System von Einschrankungsgleichungen, jedoch keine explizite Beziehung zur Berechnung aktualisierter Modellparameter. Dies muss vielmehr in einem komplexen eingebetteten Optimierungsprozess erfolgen.
Segmental k-Means
Der sogenannte segmental k-means-Algorithmus16 ist von der theoretischen Herleitung her mit dem im vorangegangenen Abschnitt vorgestellten Viterbi-Training identisch [Jua 90]. Ais Optimierungs-
kriterium dient ebenfalls die Produktionswahrscheinlichkeit P (0, s* IA) der Trainingsdaten entlang
des optimalen Pfades durch das Modell. In der praktischen Anwendung bietet er jedoch mit der Einbettung eines Verfahrens zur Vektorquantisierung - namlich des k-means-Algorithmus - eine Lasung fUr das Problem an, Parameter fUr Mischverteilungsmodelle allein auf Beispieldaten zu schatzen. Dieser praktische Aspekt wird in [Jua 90] zwar erwahnt, jedoch nicht ausgearbeitet wie z.B. in [Lee 90].
Das Verfahren lauft genauso wie des Viterbi-Training in zwei Phasen abo In einem ersten Schritt wird eine Segmentierung der Trainingsdaten mit dem bestehenden Modell erzeugt. AnschlieBend kannen aus den entstandenen Zuordnungen zwischen Merkmalsvektoren und Modellzustanden ohne Beriicksichtigung der urspriinglichen Parameter neue Emissionsdichten geschatzt werden. Der entstehende Algorithmus ist in Abbildung 5.11 zusammengestellt.
16Wir verzichten bei der Bezeichnung dieses Verfahrens auf eine Ubersetzung des Englischen segmental in deutsch "segrnentweise", urn in Kornbination mit means keinen unniitig gemischtsprachigen Begriff zu erzeugen.
94
5 Hidden-Markov-Modelle
Gegeben sei die Anzahl M j der pro Modellzustand zu schatzenden Mischverteilungs-
= komponenten (haufig wahlt man M j M identisch fUr alle Zustande j)
1. Initialisierung Wahle ein geeignetes Startmodell A = (7r, A, B)
2. Segmentierung
Berechne mit Hilfe des Viterbi-Algorithmus (siehe Abbildung 5.5 Seite 80) die optimale Zustandsfolge s* zur Erzeugung der Daten 0 bei geg. Modell A.
Berechne aktualisierte Ubergangswahrscheinlichkeiten ELij :
3. Neuschatzung Fur alle Zustande j, 0 ::; j ::; N: (a) Clusteranalyse Berechne auf der Teilstichprobe X (j) ein Vektorquantisierungscodebuch Y = {Yl, ... YMj } und die zugehorige Partition {Rl' ... RMj } z.B. mit Hilfe des k-means-Algorithmus (siehe Abbildung 4.3 Seite 61) (b) Berechnung der Modellparameter Berechne aktualisierte Emissionsparameter:
4. Terminierung
falls durch das aktualisierte Modell ,\ das GutemaB P* (0 1,\) gegenuber A deutlich
verbessert wurde
setze A+-'\ und weiter mit Schritt 2
sonstEnde!
Abb. 5.11 segmental-k-means-Algorithmus zur Pararneterschiitzung ftiT kontinuierliche HMMs.
Wie bei allen Trainingsverfahren fur HMMs mussen vor Beginn der Optimierungen geeignete initiale Modellparameter gewahlt werden. Allerdings lasst sich das Verfahren so erweitern, dass fUr HMMs mit eingeschrankter Modellstruktur auch eine Initialisierung moglich ist. Dieser Aspekt des segmental-k-means-Algorithmus wird in Abschnitt 9.3 Seite 161 ausfuhrlicher dargestellt.
1m nachsten Schritt wird mit Hilfe des Viterbi-Algorithmus fur die betrachteten Observationen die optimale Zustandsfolge berechnet. Wie beim Viterbi-Training konnen auf dieser Basis bereits Schatzwerte fUr die Ubergangswahrscheinlichkeiten des aktualisierten Modells berechnet werden
5.7 Parameterschatzung
95
(siehe Gleichung (5.27». AuBerdem erhalt man eine Zuordnung zwischen Merkmalsvektoren Xt und entsprechenden Modellzustanden, die sich formal aus der diskreten Zustandswahrscheinlichkeit Xt(i) ableiten lassen (siehe Gleichung 5.12 Seite 83). Alle einem bestimmten Zustand i zugeordneten Vektoren wollen wir zu einer Teilfolge X (i) der betrachteten Stichprobe zusammenfassen:
Diese bilden die Grundlage fUr die Neuschatzung der Emissionsdichten. Daftir wird zunachst mit einem prinzipiell beliebigen Verfahren zur Vektorquantisierung17 eine Clusteranalyse der jeweiligen Teilfolge X (i) vorgenommen. Die Parameter der Emissionsverteilungen des korrespondierenden Modellzustands ergeben sich dann genauso, wie im Falle der einfachen Schatzung von Mischverteilungsmodellen (siehe Abschnitt 4.4 Seite 62). Allerdings ist es wie bei der Vektorquantisierung auch notwendig, die Anzahl der gewtinschten Codebuchklassen bzw. Mischverteilungskomponenten vorzugeben.
Geht man davon aus, dass pro Modellzustand j genau eine Mischverteilung mit M j individuellen Basisdichten zur Emissionsmodellierung verwendet wird, so ergeben sich die Mittelwertvektoren JLjk direkt aus den Zentroiden der M j Codebuchklassen, die durch Vektorquantisierung fUr die Teilstichprobe X (j) bestimmt wurden. Die Kovarianzmatrizen berechnet man als empirische Kovarianz der Merkmalsvektoren, die einem bestimmten Prototypenvektor zugeordnet wurden. Die erforderlichen Mischungsgewichte entsprechen den a-priori-Wahrscheinlichkeiten der einzelnen Codebuchklassen.
Da beim segmental-k-means-Algorithmus in jedem Optimierungsschritt die Parameter eines HMMs inklusive der komplexen Mischverteilungsmodelle komplett neu berechnet werden und zwar nur auf der Basis der Beispielvektoren, konvergiert das Verfahren deutlich schneller als eine entsprechende Neuschatzung mit dem Baum-Welch-Algorithmus.
5.7.3 Mehrere Observationsfolgen
In der Regel untergliedern sich die zum Parametertraining verwendeten Stichproben in einzelne Abschnitte - bei der Spracherkennung in AuBerungen oder Turns bzw. bei der biologischen Sequenzanalyse in Teilsequenzen. Aus Sicht des HMM-Formalismus handelt es sich dabei urn einzelne Observationsfolgen. Urn auch auf einer solchen Menge von Einzelfolgen Modellparameter schatzen zu konnen, mtissen die Trainingsverfahren nicht grundsatzlich modifiziert werden. Lediglich die zur Aktualisierung der Parameter gesammelten Statistiken mtissen tiber alle betrachteten Observationsfolgen hinweg akkumuliert werden. Man erhalt dann modifizierte Schatzgleichungen mit einer zusatzlichen auBeren Summation tiber alle Observationsfolgen, die bei der Darstellung der einzelnen Verfahren in den vorangegangenen Abschnitten jedoch aus Grtinden der Ubersichtlichkeit weggelassen wurde. (vgl. z.B. [Hua 90, S. 157fJ, [ST 95, S. 146fJ).
Am Beispiel der Neuschiitzung der Mittelwertvektoren kontinuierlicher Emissionsdichten soll das zugrundeliegende Prinzip kurz erlautert werden. Wir gehen dabei davon aus, dass zum Training der
17 Aus Effizienzgrilnden bietet es sich an, hierfllr den k-means-Algorithmus zu verwenden, da dieser gute Ergebnisse bereits innerhalb eines einzelnen Optirnierungsschritts liefert. Prinzipiell ktinnen aber auch andere Algorithmen zum Vektorquantisierungsdesign eingesetzt werden.
96
5 Hidden-Markov-Modelle
Modelle eine Stichprobe w = {0 1 , 0 2 , ..• OL} von L einzelnen Observationsfolgen 0 1 vorliegt. Man erhait aktualisierte Mittelwertvektoren in diesem FaIle gemaB:
L T
L: L: ~Hj, k) Xt
1=1 t=l
fljk = L T
L: L: ~f(j, k)
1=1 t=l
Die inneren Summen im Zahler bzw. Nenner dieses Ausdrucks entsprechen dabei der ursprlinglichen Berechnungsvorschrift (5.22) Seite 89, bei der lediglich eine Observationsfolge betrachtet wurde. Die Zuordnungswahrscheinlichkeit ~~(j, k) von Merkmalsvektoren und Mischverteilungskomponenten muss allerdings in Abhangigkeit von der jeweiligen l-ten Observationsfolge 0 1 berechnet werden. Die gesammelten Statistiken werden anschlieBend liber aIle Teilfolgen der Stichprobe aufsummiert.
5.8 Modellvarianten
Aufgrund ihrer weiten Verbreitung und der inzwischen langen Entwicklungsgeschichte sind flir Hidden-Markov-Modelle eine Reihe von Varianten in der algorithmischen Behandlung bzw. der Modelle selbst vorgeschlagen worden. Die wichtigsten dieser Aspekte sollen im folgenden kurz skizziert werden. Flir eine ausflihrlichere Behandlung der entsprechenden Methoden sei der interessierte Leser auf die angegebene weiterflihrende Literatur verwiesen.
5.8.1 Alternative Algorithmen
AIle Erkennungssysteme mit impliziter Segmentierung, die auf HMMs setzen, verwenden zur Modelldekodierung prinzipiell den Viterbi-Algorithmus. Unterschiede ergeben sich lediglich durch notwendige Effizienzverbesserungen (siehe Abschnitt 10.2 Seite 165) bzw. die Einbeziehung weiterer Modellierungsanteile wie z.B. statistischer Sprachmodelle (vg!. Kapitel12 Seite 185).
Flir die Parameterschatzung existieren dagegen neben den etablierten Verfahren, die im vorangegangenen Abschnitt beschrieben sind, eine Reihe alternativer Ansatze. Die bekannteste Verfahrensgruppe wendet Methoden zum diskriminativen Training an. Ahnlich wie beim Viterbi-Training ist es dabei intuitiv betrachtet das Ziel, die Wahrscheinlichkeit des optimalen Pfades durch das Modell flir gegebene Daten zu verbessern. Allerdings geschieht dies nicht isoliert, sondern es wird gleichzeitig versucht, die Wahrscheinlichkeit aller konkurrierenden AiternativlOsungen zu verringern. Auf diese Weise soIl eine hahere Trennscharfe der Modelle erreicht werden, was jedoch einen drastisch erhahten Trainingsaufwand erfordert. Mathematisch betrachtet, erfolgt eine Maximierung der Transinformation (eng!. maximum mutual information (MMI», weshalb diese Verfahren auch haufig unter dem entsprechenden Klirzel in der Literatur zu finden sind (vg!. z.B. [Cho 90], [Hua 90, S. 213f], [ST 95, S. 90ff], [Hua 01, S. 150ff]). Diesen Methoden eng verwandt ist eine als korrektiyes Training (eng!. corrective training) bezeichnete Technik [Bah 93].
5.9 Literaturhinweise
97
5.8.2 Alternative Modellarchitekturen
Neben der "klassischen" HMM-Architektur existieren vielfaltige Varianten, die mit speziellen Modifikationen versuchen, Einschrankungen der Modellierung zu vermeiden bzw. zu kompensieren. Besonders die Verbesserung der mit Hilfe von einfachen Ubergangswahrscheinlichkeiten nur sehr unzureichenden Dauermodellierung von HMMs ist das Ziel einer Reihe von Ansatzen (vgl. z.B. [Lev 86, Bur 96], [Hua 01, S. 406ff]). 1m Hauptanwendungsfeld der HMMs stellen jedoch die Ubergangswahrscheinlichkeiten im Vergleich zu den Emissionsdichten relativ unbedeutende Modellierungsanteile dar. Aus diesem Grund und wegen des meist deutlich erhOhten Rechenaufwandes alternativer Dauermodellierungsverfahren konnte sich noch keine der vorgeschlagenen Techniken bisher als Standardverfahren etablieren.
Die bekannteste Modifikation der klassischen HMM-Architektur stellen zweifellos hybride Systeme aus einer Kombination von HMMs und neuronalen Netzwerken (NN) dar (vgl z.B. [Mor 95], [Hua 01, S. 458f]). Die eingesetzten neuronalen Netzwerke dienen dabei entweder als Vektorquantisierer in Kombination mit diskreten HMMs [Rig 94], als Ersatz fUr die Emissionsmodellierung auf der Basis von Mischverteilungen [Rot 00] oder direkt zur Schatzung von a-posteriori Wahrscheinlichkeiten flir einzelne Zustande [Mor 95]. Die Kombination der so gewonnenen Bewertungen mit den HMM-Wahrscheinlichkeiten ist dabei jedoch durchaus problematisch und erfordert spezielle Umsetzungsvorschriften.
Aufgrund der hOheren Modellierungsfreiheitsgrade, die durch das Wegfallen der Restriktion auf Mischverteilungsmodelle entstehen, lassen solche hybriden Systeme ein verbessertes Leistungspotential erwarten, das in der Literatur auch immer wieder exemplarisch demonstriert wird. Allerdings mussen daflir die meist schlechten Konvergenzeigenschaften des Trainings neuronaler Netzwerke in Kauf genommen werden. Auch erfolgt die Optimierung dieser Parameter ublicherweise getrennt yom eigentlichen HMM und nicht integriert, wie bei den klassischen Modellarchitekturen auf Mischverteilungsbasis. Da auBerdem fur HMMINN-Hybrid-Systeme keine einheitlichen Designstrategien existieren, haben sich diese Verfahren bislang nicht als echte oder gar bessere Alternative neben Standardarchitekturen etablieren kannen.
5.9 Literaturhinweise
Hidden-Markov-Modelle wurden nach dem russischen Mathematiker Andrej Andrejewitsch Markov (1856 - 1922) benannt [Mar 13]. Werke aus dem Bereich der mathematischen Fachliteratur behandeln vorwiegend die theoretischen Aspekte dieser Modelle. Das Hauptanwendungsgebiet von HMMs, in dem sie erfolgreich eingesetzt und konsequent weiterentwickelt wurden, stellt die automatische Spracherkennung dar. Daher ist die Behandlung von HMMs in Monographien auch fast immer an diesen Themenkomplex gekoppelt.
Besonders gelungen ist die Darstellung des Themas in der neuen Monographie von Huang, Acero & Hon [Hua 01]. Auch Schukat-Talamazzini gibt eine gute Einfuhrung in die Lasung von Spracherkennungsproblemen mit HMMs [ST 95]. Leider ist das Werk derzeit im Buchhandel vergriffen. Der theoretische Kern der Modellbildung wird weiterhin in dem teilweise veralteten Werk von Rabiner & Juang [Rab 93] sowie der Monographie von Jelinek [Jel 97] behandelt. Eine Einflihrung in HMMs aus der Sicht der Bioinformatik geben Durbin et al. [Dur 00].
98
5 Hidden-Markov-Modelle
In allen oben genannten Werken findet man Beschreibungen der fUr HMMs relevanten Algorithmen. Eine zusammenfassende Darstellung bietet auch der klassiche Artikel von Rabiner [Rab 89], der einen graBen EinfluB auf die HMM-Literatur und die darin verwendete Notation hatte.
Der Viterbi-Algorithmus ist nach seinem Entwickler benannt und geht auf dessen Arbeiten im Bereich der Kodierungstheorie zuruck [Vit 67]. Eine ausfUhrliche friihe Darstellung und Analyse des Verfahrens enthiilt [For 73]. Spiitere Beschreibungen findet man z.B. in [ST 95, S. 132f], [Hua 90, S. 151f] oder [Hua 01, S. 387ff]. Das verbreitetste Verfahren zur Parameteschiitzung von HMMs ist der Baum-Welch-Algorithmus, der von Baum und Kollegen entwickelt wurde [Bau 70]. Obwohl der Algorithmus mit Sicherheit nach seinen Erfindern benannt wurde, existiert keine zugiingliche Veroffentlichung mit einem Koautor Welch. Das Verfahren stellt eine Variante des EM-Algorithmus dar [Dem 77]. Die Beziehungen zwischen beiden Algorithmen werden z.B. in [ST 95, S. 136ff] dargestellt. Einen Beweis der Konvergenz des Baum-Welch-Algorithmus findet man neben [Bau 70] z.B. auch in [Hua 90, S. 158ff]. Das Prinzip des Verfahrens ist weiterhin in [ST 95, S. 136ff], [Hua 90, S. 152ff] und [Hua 01, S. 389ff] beschrieben. Das Viterbi-Training als alternatives Verfahren zur Parameterschiitzung fiir HMMs wird z.B. in [ST 95, S. 139f] beschrieben. Speziell fiir kontinuierliche HMMs wurde die Methode in [WeI 92] ausgearbeitet. Yom Prinzip her vergleichbar ist der segmental k-means Algorithmus, der von Juang & Rabiner entwickelt wurde [Jua 90]. Eine knappe Beschreibung der Methode findet sich auch in [Rab 93, S. 427]
6 n-Gramm-Modelle
Ein statistisches Sprachmodell in seiner allgemeinsten Form definiert eine Wahrscheinlichkeitsverteilung uber einer Menge von Symbolfolgen aus einem endlichen Inventar. Ais "Sprachmodell" bezeichnet man diese Verfahren deshalb, weil ihre Entstehung und Verbreitung eng mit der statistischen Modellierung von Texten sowie der Restriktion moglicher Worthypothesenfolgen bei der Spracherkennung verknupft ist.
Ein besonders einfaches, aber dennoch sehr leistungsfahiges Konzept zur formalen Beschreibung von statistischen Sprachmodellen bildet deren Reprasentation durch Markov-Ketten. Hierauf basiert die heute verbreitetste Version dieser Modelle, die sogenannten n-Gramm-Modelle. Ebenfalls gut erforscht, aber deutlich komplexer ist die Beschreibung der statistischen Eigenschaften von Symbolfolgen mit stochastischen Grammatiken, da das Parametertraining solcher Modelle auBerordentlich aufwendig ist. Zudem muss die Festlegung der Strukturregeln durch Experten erfolgen, da hierfUr keine allgemeinen Inferenzmethoden bekannt sind. Aus diesen Grunden ist die Verbreitung stochastischer Grammatiken fUr Musteranalysezwecke gering geblieben, weshalb auch der Begriff Sprachmodell (engl. language model) in der Literatur meist als Synonym fUr n-Gramm-Modelle verwendet wird. Diese sollen daher auch im folgenden als einzige Klasse statistischer Sprachmodellierungstechniken betrachtet werden. Fur andere Verfahren sei der Leser auf die entsprechende Spezialliteratur verwiesen.
6.1 Definition
Ein statistisches n-Gramm-Modell entspricht einer Markov-Kette n-l-ter Ordnung. Die Wahrscheinlichkeit P(w) einer bestimmten Symbolfolge w = WI, W2, ... , WT der Lange T wird zuerst gemaB der Bayes-Regel in ein Produkt bedingter Wahrscheinlichkeiten zerlegt.
I IT
P(w) = P(WdP(W2Iwd··· P(wTl wl, ... ,WT-l) = P(WtI Wl, ... ,Wt-l)
t=1
Bei dieser Faktorisierung entstehen aber - wie schon bei der EinfUhrung stochastischer Prozesse erlautert - mit zunehmender Lange T der Symbolfolge moglicherweise bedingte Wahrscheinlichkeiten mit beliebig langen Abhangigkeiten. Daher begrenzt man fUr praktische Anwendungen die
100
6 n-Gramrn-Modelle
maximale KontextHinge auf n - 1 Vorgangersymbole. Motiviert durch eine zeitliche Ordnung der Symbol- oder Wortfolgen bezeichnet man diesen Kontext haufig auch als Geschichte (engl. history).
IIT
I P(w) ~ P( Wt Wt-n+l,···, Wt-l)
t=l
...
nSymbole
Das jeweils vorhergesagte Symbol Wt und die zugehOrige Geschichte bilden dabei ein Tupel von n Symbolen, weshalb man von n-Gramm-Modellen spricht. Eine konkretes n-Tupel von Symbolen heiBt n-Gramm und wird im Bereich der Sprachmodellierung meist als Ereignis (engl. event) bezeichnet.
Ein gegebenes n-Gramm-Modell definiert also Wahrscheinlichkeiten zur Vorhersage bzw. Bewertung des Auftretens von Symbolen aus einem endlichen Inventar innerhalb einer Folge auf der Basis eines Kontexts von n - 1 bekannten vorangegangenen Folgegliedem. Aus diesen einzelnen Anteilen lasst sich direkt die Wahrscheinlichkeit einer bestimmten Folge insgesamt berechnen. Die Gesamtheit der bedingten Wahrscheinlichkeitsverteilungen bildetdas statistische Sprachmodell, das im Gegensatz zu HMMs in der Literatur nicht explizit mit einem mathematischen Symbol bezeichnet wird. Daher wird in den weiteren Ausfiihrungen ebenfalls auf eine explizite Benennung verzichtet, sofem die implizite Zuordnung der Wahrscheinlichkeiten zum jeweiligen Modell eindeutig ist.
Da mit wachsender Kontextlange neben den prinzipiellen Schwierigkeiten, ein solches Modell zu schatzen und praktisch einzusetzen, auch noch der notwendige Speicheraufwand extrem ansteigt, stellen die verbreitetste Variante von n-Gramm-Modellen Bi- und Tri-Gramme dar. Bereits 4-Gramm-Modelle sind dagegen kaum mehr in statistischen Erkennungssystemen anzutreffen, wohingegen im Bereich der Spracherkennung ein Bi-Gramm-Modell als Erganzung der HMMModellierung heute als Standard anzusehen ist. In den neueren Anwendungsfeldem statistischer Modellierungstechniken wie Handschrift-, Gestik- und biologische Sequenzanalyse haben statistische Sprachmodelle derzeit noch keine oder nur geringe Verbreitung erfahren. Dies ist wohl hauptsachlich dadurch bedingt, dass in diesen Forschungsfeldem im Gegensatz zur Spracherkennung die allgemeine Verfiigbarkeit hinreichend groBer Stichproben noch nicht gegeben ist.
6.2 Verwendungskonzepte
Genau wie bei HMMs beruht die Verwendung statistischer Sprachmodelle zur Beschreibung von Texten oder anderen Symbolsequenzen auf der Annahme, dass deren zugrundeliegendes Erzeugungsprinzip statistischen GesetzmaBigkeiten gehorcht, die sich mit Markov-Ketten beschreiben oder wenigstens hinreichend genau annlihem lassen.
Daher ist auch fUr n-Gramm-Modelle eine relevante Fragestellung, wie gut ein gegebenes Modell bestimmte vorliegende Daten zu beschreiben vermag. Hierzu muss im wesentlichen die Wahrscheinlichkeit dieser Symbolfolge - oder eine daraus abgeleitete informationstheoretische GroBe - mit Hilfe des verwendeten Modells berechnet werden. Man kann dann Riickschliisse auf die Qualitat des Sprachmodells ziehen oder auch verschiedene Modelle hinsichtlich ihrer Eignung zur Beschreibung