6.8.1 Decoding and Learning in MEMMs

Like HMMs, the MEMM uses the Viterbi algorithm to perform the task of decoding (inference). Concretely, this involves filling an $ N \times T $ array with the appropriate values for $ P(t|t_{i-1}, word_i) $, maintaining backpointers as we proceed. As with HMM Viterbi, when the table is filled we simply follow pointers back from the maximum value in the final column to retrieve the desired set of labels. The requisite changes from the HMM-style application of Viterbi only have to do with how we fill each cell. Recall

from Eq. 6.23 that the recursive step of the Viterbi equation computes the Viterbi value of time t for state j as:

$$ v_{t}(j)=\max_{i=1}^{N}v_{t-1}(i)a_{ij}b_{j}(o_{t});1\leq j\leq N,1

which is the HMM implementation of

$$ v_{t}(j)=\max_{i=1}^{N}v_{t-1}(i)P(s_{j}|s_{i})P(o_{t}|s_{j})1\leq j\leq N,1

The MEMM requires only a slight change to this latter formula, replacing the a and b prior and likelihood probabilities with the direct posterior:

$$ v_{t}(j)=\max_{i=1}^{N}v_{t-1}(i)P(s_{j}|s_{i},o_{t})\quad1\leq j\leq N,1

Fig. 6.22 shows an example of the Viterbi trellis for an MEMM applied to the ice-cream task from Sec. 6.4. Recall that the task is figuring out the hidden weather (Hot or Cold) from observed numbers of ice-creams eaten in Jason Eisner's diary. Fig. 6.22 shows the abstract Viterbi probability calculation assuming that we have a MaxEnt model which computes $ P(s_i|s_{i-1},o_i) $ for us.

Learning in MEMMs relies on the same supervised learning algorithms we presented for logistic regression and MaxEnt. Given a sequence of observations, feature functions, and corresponding hidden states, we train the weights so as to maximize the log-likelihood of the training corpus. As with HMMs, it is also possible to train MEMMs in semi-supervised modes, for example when the sequence of labels for the training data is missing or incomplete in some way: a version of the EM algorithm can be used for this purpose.

6.9 SUMMARY

This chapter described two important models for probabilistic sequence classification: the Hidden Markov Model and the Maximum Entropy Markov Model. Both models are widely used throughout speech and language processing.

Hidden Markov Models (HMMs) are a way of relating a sequence of observations to a sequence of hidden classes or hidden states which explain the observations.

• The process of discovering the sequence of hidden states given the sequence of observations is known as decoding or inference. The Viterbi algorithm is commonly used for decoding.

• The parameters of an HMM are the A transition probability matrix and the B observation likelihood matrix. Both can be trained using the Baum-Welch or forward-backward algorithm.

• A MaxEnt model is a classifier which assigns a class to an observation by computing a probability from an exponential function of a weighted set of features of the observation.

MaxEnt models can be trained using methods from the field of convex optimization although we don't give the details in this textbook.

• A Maximum Entropy Markov Model or MEMM is a sequence model augmentation of MaxEnt which makes use of the Viterbi decoding algorithm.

• MEMMs can be trained by augmenting MaxEnt training with a version of EM.

BIBLIOGRAPHICAL AND HISTORICAL NOTES

As we discussed at the end of Ch. 4, Markov chains were first used by Markov (1913, 2006), to predict whether an upcoming letter in Pushkin's Eugene Onegin would be a vowel or a consonant.

The Hidden Markov Model was developed by Baum and colleagues at the Institute for Defense Analyses in Princeton (Baum and Petrie, 1966; Baum and Eagon, 1967).

The Viterbi algorithm was first applied to speech and language processing in the context of speech recognition by Vintsyuk (1968), but has what Kruskal (1983) calls a

'remarkable history of multiple independent discovery and publication'. $ ^{2} $ Kruskal and others give at least the following independently-discovered variants of the algorithm published in four separate fields:

The use of the term Viterbi is now standard for the application of dynamic programming to any kind of probabilistic maximization problem in speech and language processing. For non-probabilistic problems (such as for minimum edit distance) the plain term dynamic programming is often used. Forney Jr. (1973) is an early survey paper which explores the origin of the Viterbi algorithm in the context of information and communications theory.

Our presentation of the idea that Hidden Markov Models should be characterized by three fundamental problems was modeled after an influential tutorial by Rabiner (1989), which was itself based on tutorials by Jack Ferguson of IDA in the 1960s. Jelinek (1997) and Rabiner and Juang (1993) give very complete descriptions of the forward-backward algorithm, as applied to the speech recognition problem. Jelinek (1997) also shows the relationship between forward-backward and EM. See also the description of HMMs in other textbooks such as Manning and Schütze (1999). Bilmes (1997) is a tutorial on EM.

While logistic regression and other log-linear models have been used in many fields since the middle of the 20th century, the use of Maximum Entropy/multinomial logistic regression in natural language processing dates from work in the early 1990s at IBM (Berger et al., 1996; Della Pietra et al., 1997). This early work introduced the maximum entropy formalism, proposed a learning algorithm (improved iterative scaling), and proposed the use of regularization. A number of applications of MaxEnt followed. For further discussion of regularization and smoothing for maximum entropy models see (inter alia) Chen and Rosenfeld (2000), Goodman (2004), and Dudík and Schapire (2006).

Although the second part of this chapter focused on MaxEnt-style classification, numerous other approaches to classification are used throughout speech and language processing. Naive Bayes (Duda et al., 2000) is often employed as a good baseline method (often yielding results that are sufficiently good for practical use); we'll cover naive Bayes in Ch. 20. Support Vector Machines (Vapnik, 1995) have been successfully used in text classification and in a wide variety of sequence processing applications. Decision lists have been widely used in word sense discrimination, and decision trees (Breiman et al., 1984; Quinlan, 1986) have been used in many applications in speech processing. Good references to supervised machine learning approaches to classification

tion include Duda et al. (2000), Hastie et al. (2001), and Witten and Frank (2005).

Maximum Entropy Markov Models (MEMMs) were introduced by Ratnaparkhi (1996) and McCallum et al. (2000).

There are many sequence models that augment the MEMM, such as the Conditional Random Field (CRF) (Lafferty et al., 2001; Sutton and McCallum, 2006). In addition, there are various generalizations of maximum margin methods (the insights that underlie SVM classifiers) to sequence tasks.

Baum, L. E. (1972). An inequality and associated maximization technique in statistical estimation for probabilistic functions of Markov processes. In Shisha, O. (Ed.), Inequalities III: Proceedings of the Third Symposium on Inequalities, University of California, Los Angeles, pp. 1–8. Academic Press.

Baum, L. E. and Eagon, J. A. (1967). An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology. Bulletin of the American Mathematical Society, 73(3), 360–363.

Baum, L. E. and Petrie, T. (1966). Statistical inference for probabilistic functions of finite-state Markov chains. Annals of Mathematical Statistics, 37(6), 1554–1563.

Berger, A., Della Pietra, S. A., and Della Pietra, V. J. (1996). A maximum entropy approach to natural language processing. Computational Linguistics, 22(1), 39–71.

Bilmes, J. (1997). A gentle tutorial on the EM algorithm and its application to parameter estimation for gaussian mixture and hidden markov models. Tech. rep. ICSI-TR-97-021, ICSI, Berkeley.

Breiman, L., Friedman, J. H., Olshen, R. A., and Stone, C. J. (1984). Classification and Regression Trees. Wadsworth & Brooks, Pacific Grove, CA.

Chen, S. F. and Rosenfeld, R. (2000). A survey of smoothing techniques for ME models. IEEE Transactions on Speech and Audio Processing, 8(1), 37–50.

Darroch, J. N. and Ratcliff, D. (1972). Generalized iterative scaling for log-linear models. The Annals of Mathematical Statistics, 43(5), 1470–1480.

Della Pietra, S. A., Della Pietra, V. J., and Lafferty, J. D. (1997). Inducing features of random fields. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(4), 380–393.

Dempster, A. P., Laird, N. M., and Rubin, D. B. (1977). Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, 39(1), 1–21.

Duda, R. O., Hart, P. E., and Stork, D. G. (2000). Pattern Classification. Wiley-Interscience Publication.

Dudík, M. and Schapire, R. E. (2006). Maximum entropy distribution estimation with generalized regularization. In Lugosi, G. and Simon, H. U. (Eds.), COLT 2006, Berlin, pp. 123–138. Springer-Verlag.

Eisner, J. (2002). An interactive spreadsheet for teaching the forward-backward algorithm. In Proceedings of the ACL Workshop on Effective Tools and Methodologies for Teaching NLP and CL, pp. 10–18.

Forney Jr., G. D. (1973). The Viterbi algorithm. Proceedings of the IEEE, 61(3), 268–278.

Goodman, J. (2004). Exponential priors for maximum entropy models. In ACL-04.

Hastie, T., Tibshirani, R., and Friedman, J. H. (2001). The Elements of Statistical Learning. Springer.

Hofstadter, D. R. (1997). Le ton beau de marot. Basic Books.

Jelinek, F. (1997). Statistical Methods for Speech Recognition.

MIT Press.

Kruskal, J. B. (1983). An overview of sequence comparison. In Sankoff, D. and Kruskal, J. B. (Eds.), Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison, pp. 1–44. Addison-Wesley, Reading, MA.

Lafferty, J. D., McCallum, A., and Pereira, F. C. N. (2001). Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In ICML 2001, Stanford, CA.

Levitt, S. D. and Dubner, S. J. (2005). Freakonomics. Morrow.

Malouf, R. (2002). A comparison of algorithms for maximum entropy parameter estimation. In CoNLL-2002, pp. 49–55.

Manning, C. D. and Schütze, H. (1999). Foundations of Statistical Natural Language Processing. MIT Press.

Markov, A. A. (1913). Essai d'une recherche statistique sur le texte du roman "Eugene Onegin" illustrant la liaison des epreuve en chain ('Example of a statistical investigation of the text of "Eugene Onegin" illustrating the dependence between samples in chain'). Izvistia Imperatorskoi Akademii Nauk (Bulletin de l'Académie Impériale des Sciences de St.-Pétersbourg), 7, 153–162. English translation by Morris Halle, 1956.

Markov, A. A. (2006). Classical text in translation: A. A. Markov, an example of statistical investigation of the text Eugene Onegin concerning the connection of samples in chains. Science in Context, 19(4), 591–600. Translated by David Link.

McCallum, A., Freitag, D., and Pereira, F. C. N. (2000). Maximum Entropy Markov Models for Information Extraction and Segmentation. In ICML 2000, pp. 591–598.

Needleman, S. B. and Wunsch, C. D. (1970). A general method applicable to the search for similarities in the amino-acid sequence of two proteins. Journal of Molecular Biology, 48, 443–453.

Quinlan, J. R. (1986). Induction of decision trees. Machine Learning, 1, 81–106.

Rabiner, L. R. (1989). A tutorial on Hidden Markov Models and selected applications in speech recognition. Proceedings of the IEEE, 77(2), 257–286.

Rabiner, L. R. and Juang, B. H. (1993). Fundamentals of Speech Recognition. Prentice Hall.

Ratnaparkhi, A. (1996). A maximum entropy part-of-speech tagger. In EMNLP 1996, Philadelphia, PA, pp. 133–142.

Reichert, T. A., Cohen, D. N., and Wong, A. K. C. (1973). An application of information theory to genetic mutations and the matching of polypeptide sequences. Journal of Theoretical Biology, 42, 245–261.

Sakoe, H. and Chiba, S. (1971). A dynamic programming approach to continuous speech recognition. In Proceedings of the Seventh International Congress on Acoustics, Budapest, Budapest, Vol. 3, pp. 65–69. Akadémiai Kiadó.

Sankoff, D. (1972). Matching sequences under deletion-insertion constraints. Proceedings of the Natural Academy of Sciences of the U.S.A., 69, 4–6.

Sutton, C. and McCallum, A. (2006). An introduction to conditional random fields for relational learning. In Getoor, L. and Taskar, B. (Eds.), Introduction to Statistical Relational Learning. MIT Press.

Vapnik, V. N. (1995). The Nature of Statistical Learning Theory. Springer-Verlag.

Viterbi, A. J. (1967). Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Transactions on Information Theory, IT-13(2), 260–269.

Vintsyuk, T. K. (1968). Speech discrimination by dynamic programming. Cybernetics, 4(1), 52–57. Russian Kibernetika 4(1):81-88 (1968).

Wagner, R. A. and Fischer, M. J. (1974). The string-to-string correction problem. Journal of the Association for Computing Machinery, 21, 168–173.

Witten, I. H. and Frank, E. (2005). Data Mining: Practical Machine Learning Tools and Techniques. Morgan Kaufmann. 2nd ed.

7

PHONETICS

(Upon being asked by Director George Cukor to teach Rex Harrison, the star of the 1964 film "My Fair Lady", how to behave like a phonetician:)

“My immediate answer was, ‘I don’t have a singing butler and three maids who sing, but I will tell you what I can as an assistant professor.’”

Peter Ladefoged, quoted in his obituary, LA Times, 2004

The debate between the “whole language” and “phonics” methods of teaching reading to children seems at very glance like a purely modern educational debate. Like many modern debates, however, this one recapitulates an important historical dialectic, in this case in writing systems. The earliest independently-invented writing systems (Sumerian, Chinese, Mayan) were mainly logographic: one symbol represented a whole word. But from the earliest stages we can find, most such systems contain elements of syllabic or phonemic writing systems, in which symbols are used to represent the sounds that make up the words. Thus the Sumerian symbol pronounced ba and meaning “ration” could also function purely as the sound /ba/. Even modern Chinese, which remains primarily logographic, uses sound-based characters to spell out foreign words. Purely sound-based writing systems, whether syllabic (like Japanese hiragana or katakana), alphabetic (like the Roman alphabet used in this book), or consonantal (like Semitic writing systems), can generally be traced back to these early logo-syllabic systems, often as two cultures came together. Thus the Arabic, Aramaic, Hebrew, Greek, and Roman systems all derive from a West Semitic script that is presumed to have been modified by Western Semitic mercenaries from a cursive form of Egyptian hieroglyphs. The Japanese syllabaries were modified from a cursive form of a set of Chinese characters which were used to represent sounds. These Chinese characters themselves were used in Chinese to phonetically represent the Sanskrit in the Buddhist scriptures that were brought to China in the Tang dynasty.

Whatever its origins, the idea implicit in a sound-based writing system, that the spoken word is composed of smaller units of speech, is the Ur-theory that underlies all our modern theories of phonology. This idea of decomposing speech and words into smaller units also underlies the modern algorithms for speech recognition (trans-scribining acoustic waveforms into strings of text words) and speech synthesis or text-to-speech (converting strings of text words into acoustic waveforms).

In this chapter we introduce phonetics from a computational perspective. Phonetics is the study of linguistic sounds, how they are produced by the articulators of the human vocal tract, how they are realized acoustically, and how this acoustic realization can be digitized and processed.

We begin with a key element of both speech recognition and text-to-speech systems: how words are pronounced in terms of individual speech units called phones. A speech recognition system needs to have a pronunciation for every word it can recognize, and a text-to-speech system needs to have a pronunciation for every word it can say. The first section of this chapter will introduce phonetic alphabets for describing these pronunciations. We then introduce the two main areas of phonetics, articulatory phonetics, the study of how speech sounds are produced by articulators in the mouth, and acoustic phonetics, the study of the acoustic analysis of speech sounds.

We also briefly touch on phonology, the area of linguistics that describes the systematic way that sounds are differently realized in different environments, and how this system of sounds is related to the rest of the grammar. In doing so we focus on the crucial fact of variation in modeling speech; phones are pronounced differently in different contexts.

7.1 SPEECH SOUNDS AND PHONETIC TRANSCRIPTION

The study of the pronunciation of words is part of the field of phonetics, the study of the speech sounds used in the languages of the world. We model the pronunciation of a word as a string of symbols which represent phones or segments. A phone is a speech sound; phones are represented with phonetic symbols that bear some resemblance to a letter in an alphabetic language like English.

This section surveys the different phones of English, particularly American English, showing how they are produced and how they are represented symbolically. We will be using two different alphabets for describing phones. The International Phonetic Alphabet (IPA) is an evolving standard originally developed by the International Phonetic Association in 1888 with the goal of transcribing the sounds of all human languages. The IPA is not just an alphabet but also a set of principles for transcription, which differ according to the needs of the transcription, so the same utterance can be transcribed in different ways all according to the principles of the IPA. The ARPAbet (Shoup, 1980) is another phonetic alphabet, but one that is specifically designed for American English and which uses ASCII symbols; it can be thought of as a convenient ASCII representation of an American-English subset of the IPA. ARPAbet symbols are often used in applications where non-ASCII fonts are inconvenient, such as in on-line pronunciation dictionaries. Because the ARPAbet is very common for computational representations of pronunciations, we will rely on it rather than the IPA in the remainder of this book. Fig. 7.1 and Fig. 7.2 show the ARPAbet symbols for transcribing consonants and vowels, respectively, together with their IPA equivalents.

| ARPAbet Symbol | IPA Symbol | Word | ARPAbet Transcription |

| --- | --- | --- | --- |

| [p] | [p] | parsley | [p a a r s l i y] |

| [t] | [t] | tea | [t i y] |

| [k] | [k] | cook | [k u h k] |

| [b] | [b] | bay | [b e y] |

| [d] | [d] | dill | [d i h l] |

| [g] | [g] | garlic | [g a a r l i x k] |

| [m] | [m] | mint | [m i h n t] |

| [n] | [n] | nutmeg | [n a h t m e h g] |

| [ng] | [ŋ] | baking | [b e y k i x ng] |

| [f] | [f] | flour | [f l a w a x r] |

| [v] | [v] | cloye | [k l o w v] |

| [th] | [ \theta ] | thick | [th i h k] |

| [dh] | [ð] | those | [dh o w z] |

| [s] | [s] | soup | [s u w p] |

| [z] | [z] | eggs | [e h g z] |

| [sh] | [ʃ] | squash | [s k w a a s h] |

| [zh] | [ʒ] | ambrosia | [a e m b r o w z h a x] |

| [ch] | [tʃ] | cherry | [ch e h r i y] |

| [jh] | [dʒ] | jar | [j h a a r] |

| [l] | [l] | licorice | [l i h k a x r i x s h] |

| [w] | [w] | kiwi | [k i y w i y] |

| [r] | [r] | rice | [r a y s] |

| [y] | [j] | yellow | [y e h l o w] |

| [h] | [h] | honey | [h a h n i y] |

| [q] | [ʔ] | $ \underline{\text{uh}} $-oh | [q ah q ow] |

| --- | --- | --- | --- |

| [dx] | [r] | bu $ \underline{\text{tt}} $er | [b ah dx axr ] |

| [nx] | [r] | wi $ \underline{\text{nn}} $er | [w ih nx axr] |

| [el] | [l] | tab $ \underline{\text{le}} $ | [t ey b el] |

Many of the IPA and ARPAbet symbols are equivalent to the Roman letters used in the orthography of English and many other languages. So for example the ARPAbet phone [p] represents the consonant sound at the beginning of platypus, puma, and pachyderm, the middle of leopard, or the end of antelope. In general, however, the mapping between the letters of English orthography and phones is relatively opaque; a single letter can represent very different sounds in different contexts. The English letter c corresponds to phone [k] in cougar [k uw g axr], but phone [s] in cell [s eh

| [ax] | [ə] | lot $ \underline{\text{us}} $ | [l ow dx ax s] |

| --- | --- | --- | --- |

| [axr] | [ə'r] | heath $ \underline{\text{er}} $ | [h eh dh axr] |

| [ix] | [i] | tul $ \underline{\text{i}} $p | [t uw l ix p] |

| [ux] | [u] | d $ \underline{\text{u}} $de $ ^{1} $ | [d ux d] |

1]. Besides appearing as c and k, the phone [k] can appear as part of x (fox [f aa k s]), as ck (jackal [jh ae k el] and as cc (raccoon [r ae k uw n]). Many other languages, for example Spanish, are much more transparent in their sound-orthography mapping than English.

7.2 ARTICULATORY PHONETICS

The list of ARPAbet phones is useless without an understanding of how each phone is produced. We thus turn to articulatory phonetics, the study of how phones are produced, as the various organs in the mouth, throat, and nose modify the airflow from the lungs.