9.2.2 General form of an HMM
--------------------------------------------------------- 324
9.3 The Three Fundamental Questions for HMMs
--------------------- ------- -------------- ---- 325
9.3.1 Finding the probability of an observation
--------------------------------------------- 325
9.3.2 Finding the best state sequence
----------------------------------------------------- 331
9.3.3 The third problem: Parameter estimation
--------------------------------------------- 333
9.4 HMMs: Implementation, Properties, and Variants
--------------------------------------------
336
9.4.1 Implementation
----------------------------------------------------------------- 336
9.4.2 Variants
----------------------------------------------------------------------- 337
9.4.3 Multiple input observations
-------------------------------------------------------
338
9.4.4 Initialization of parameter values
--------------------------------------------------- 339
9.5 Further Reading
---------------------------------------------------------------------- 339
10 Part-Of-Speech Tagging
------------------------------------------------------------------- 341
10.1 The Information Sources in Tagging
----------------------------------------------------- 343
10.2 Markov Model Taggers
--------------------------------------------------------------- 345
10.2.1 The probabilistic model
--------------------------------------------------------- 345
10.2.2 The Viterbi algorithm
----------------------------------------------------------- 349
10.2.3 Variations
-------------------------------------------------------------------- 351
10.3 Hidden Markov Model Taggers
--------------------------------------------------------- 356
10.3.1 Applying HMMs to POS tagging
-------------------------------------------------- 357
10.3.2 The effect of initialization on HMM training
----------------------------------------- 359
10.4 Transformation-Based Learning of Tags
-------------------------------------------------- 361
10.4.1 Transformations
--------------------------------------------------------------- 362
10.4.2 The learning algorithm
----------------------------------------------------------
364
10.4.3 Relation to other models
--------------------------------------------------------- 365
10.4.4 Automata
---------------------------------------------------------------------
368
10.4.5 Summary
----------------------------------------------------------------- --- 369
10.5 Other Methods, Other Languages
-------------------- -- ------------ --------------------- 370
10.5.1 Other approaches to tagging
------------------------------------------------------ 370
10.5.2 Languages other than English
----------------------------------------------------- 371
10.6 Tagging Accuracy and Uses of Taggers
---------------- -- ----------- ----------------- ---- 371
10.6.1 Tagging accuracy
-------------------------------------------------------------- 371
10.6.2 Applications of tagging
----------------------- - --------------- ------------------ 374
10.7 Further Reading
--------------------------------------------------------------------- 377
10.8 Exercises
-------------------------------------------------------------------------- 379
11 Probabilistic Context Free Grammars
-------------------------------------------------------- 381
11.1 Some Features of PCFGs
-------------------------------------------------------------- 386
11.2 Questions for PCFGs
----------------------------------------------------------------- 388
11.3 The Probability of a String
------------------------------------------------------------- 392
11.3.1 Using inside probabilities
--------------------------------------------------------
392
11.3.2 Using outside probabilities
------------------------------------------------------- 394
11.3.3 Finding the most likely parse for a sentence
----------------------------------------- 396
11.3.4 Training a PCFG
------------------------ ---- --------------- ------------------- 398
11.4 Problems with the Inside-Outside algorithm
-----------------------------------------------
401
11.5 Further Reading
--------------------------------------------------------------------- 402
11.6 Exercises
-------------------------------------------------------------------------- 404
12 Probabilistic Parsing
--------------------------------------------------------------------- 407
12.1 Some Concepts
--------------------------------------------------------------------- 408
12.1.1 Parsing for disambiguation
------------------------------------------------------- 408
12.1.2 Treebanks
-------------------------------------------------------------------- 412
12.1.3 Parsing models vs. language models
------------- - -------- ------------- ------- -- --- 414
