Cover image for Markov models for pattern recognition : from theory to applications
Title:
Markov models for pattern recognition : from theory to applications
Personal Author:
Publication Information:
Berlin, GW : Springer, 2008
Physical Description:
xii, 248 p. : ill. ; 24 cm.
ISBN:
9783540717669

Available:*

Library
Item Barcode
Call Number
Material Type
Status
Searching...
30000010195544 Q327 F56 2008 Open Access Book
Searching...

On Order

Summary

Summary

Markov models are used to solve challenging pattern recognition problems on the basis of sequential data as, e.g., automatic speech or handwriting recognition. This comprehensive introduction to the Markov modeling framework describes both the underlying theoretical concepts of Markov models - covering Hidden Markov models and Markov chain models - as used for sequential data and presents the techniques necessary to build successful systems for practical applications. Additionally, the actual use of the technology in the three main application areas of pattern recognition methods based on Markov- Models - namely speech recognition, handwriting recognition, and biological sequence analysis - are demonstrated.


Author Notes

Gernot A. Fink is professor for Pattern Recognition in Embedded Systems at the University of Dortmund, Germany, where he also heads the Intelligent Systems Group at the Robotics Research Institute.


Table of Contents

1 Introductionp. 1
1.1 Thematic Contextp. 3
1.2 Functional Principles of Markov Modelsp. 3
1.3 Goal and Structure of the Bookp. 5
2 Application Areasp. 7
2.1 Speechp. 7
2.2 Writingp. 14
2.3 Biological Sequencesp. 22
2.4 Outlookp. 26
Part I Theory
3 Foundations of Mathematical Statisticsp. 33
3.1 Random Experiment, Event, and Probabilityp. 33
3.2 Random Variables and Probability Distributionsp. 35
3.3 Parameters of Probability Distributionsp. 37
3.4 Normal Distributions and Mixture Modelsp. 38
3.5 Stochastic Processes and Markov Chainsp. 40
3.6 Principles of Parameter Estimationp. 41
3.6.1 Maximum Likelihood Estimationp. 41
3.6.2 Maximum a posteriori Estimationp. 43
3.7 Bibliographical Remarksp. 44
4 Vector Quantizationp. 45
4.1 Definitionp. 46
4.2 Optimalityp. 47
Nearest-Neighbor Conditionp. 47
Centroid Conditionp. 48
4.3 Algorithms for Vector Quantizer Designp. 50
Lloyd's Algorithmp. 50
LBG Algorithmp. 52
k-Means-Algorithmp. 53
4.4 Estimation of Mixture Density Modelsp. 55
EM algorithmp. 56
4.5 Bibliographical Remarksp. 59
5 Hidden Markov Modelsp. 61
5.1 Definitionp. 61
5.2 Modeling Emissionsp. 63
5.3 Use Casesp. 65
5.4 Notationp. 67
5.5 Evaluationp. 68
5.5.1 The Production Probabilityp. 68
Forward Algorithmp. 69
5.5.2 The "Optimal" Production Probabilityp. 71
5.6 Decodingp. 74
Viterbi Algorithmp. 75
5.7 Parameter Estimationp. 76
5.7.1 Foundationsp. 76
Forward-Backward Algorithmp. 78
5.7.2 Training Methodsp. 79
Baum-Welch Algorithmp. 80
Viterbi trainingp. 86
Segmental k-Meansp. 88
5.7.3 Multiple Observation Sequencesp. 90
5.8 Model Variantsp. 91
5.8.1 Alternative Algorithmsp. 91
5.8.2 Alternative Model Architecturesp. 92
5.9 Bibliographical Remarksp. 92
6 n-Gram Modelsp. 95
6.1 Definitionp. 95
6.2 Use Casesp. 96
6.3 Notationp. 97
6.4 Evaluationp. 98
6.5 Parameter Estimationp. 100
6.5.1 Redistribution of Probability Massp. 101
Discountingp. 101
6.5.2 Incorporation of More General Distributionsp. 104
Interpolationp. 104
Backing Offp. 106
6.5.3 Optimization of Generalized Distributionsp. 107
6.6 Model Variantsp. 109
6.6.1 Category-Based Modelsp. 109
6.6.2 Longer Temporal Dependenciesp. 111
6.7 Bibliographical Remarksp. 112
Part II Practice
7 Computations with Probabilitiesp. 119
7.1 Logarithmic Probability Representationp. 120
7.2 Lower Bounds for Probabilitiesp. 122
7.3 Codebook Evaluation for Semi-Continuous HMMsp. 123
7.4 Probability Ratiosp. 124
8 Configuration of Hidden Markov Modelsp. 127
8.1 Model Topologiesp. 127
8.2 Modularizationp. 129
8.2.1 Context-Independent Sub-Word Unitsp. 129
8.2.2 Context-Dependent Sub-Word Unitsp. 130
8.3 Compound Modelsp. 131
8.4 Profile HMMsp. 133
8.5 Modeling Emissionsp. 136
9 Robust Parameter Estimationp. 137
9.1 Feature Optimizationp. 139
9.1.1 Decorrelationp. 140
Principal Component Analysis Ip. 141
Whiteningp. 144
9.1.2 Dimensionality Reductionp. 147
Principal Component Analysis IIp. 147
Linear Discriminant Analysisp. 148
9.2 Tyingp. 152
9.2.1 Model Subunitsp. 153
9.2.2 State Tyingp. 157
9.2.3 Tying in Mixture Modelsp. 161
9.3 Initialization of Parametersp. 163
10 Efficient Model Evaluationp. 165
10.1 Efficient Evaluation of Mixture Densitiesp. 166
10.2 Beam Searchp. 167
10.3 Efficient Parameter Estimationp. 170
10.3.1 Forward-Backward Pruningp. 170
10.3.2 Segmental Baum-Welch Algorithmp. 171
10.3.3 Training of Model Hierarchiesp. 173
10.4 Tree-like Model Organizationp. 174
10.4.1 HMM Prefix Treesp. 174
10.4.2 Tree-like Representation for n-Gram Modelsp. 175
11 Model Adaptationp. 181
11.1 Basic Principlesp. 181
11.2 Adaptation of Hidden Markov Modelsp. 182
Maximum-Likelihood Linear-Regressionp. 184
11.3 Adaptation of n-Gram Modelsp. 186
11.3.1 Cache Modelsp. 187
11.3.2 Dialog-Step Dependent Modelsp. 187
11.3.3 Topic-Based Language Modelsp. 187
12 Integrated Search Methodsp. 189
12.1 HMM Networksp. 192
12.2 Multi-Pass Searchp. 193
12.3 Search Space Copiesp. 194
12.3.1 Context-Based Search Space Copiesp. 195
12.3.2 Time-Based Search Space Copiesp. 196
12.3.3 Language-Model Look-Aheadp. 197
12.4 Time-Synchronous Parallel Model Decodingp. 198
12.4.1 Generation of Segment Hypothesesp. 199
12.4.2 Language Model-Based Searchp. 200
Part III Systems
13 Speech Recognitionp. 207
13.1 Recognition System of RWTH Aachen Universityp. 207
13.2 BBN Speech Recognizer BYBLOSp. 209
13.3 ESMERALDAp. 210
14 Character and Handwriting Recognitionp. 215
14.1 OCR System by BBNp. 215
14.2 Duisburg Online Handwriting Recognition Systemp. 217
14.3 ESMERALDA Offline Recognition Systemp. 219
15 Analysis of Biological Sequencesp. 221
15.1 HMMERp. 222
15.2 SAMp. 223
15.3 ESMERALDAp. 224
Referencesp. 227
Indexp. 245