Conditional Random Fields for Word Hyphenation

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 366–374, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics Conditional Random Fields for Word Hyphenation Nikolaos Trogkanis Computer Science and Engineering University of California, San Diego La Jolla, California 92093-0404 tronikos@gmail.com Charles Elkan Computer Science and Engineering University of California, San Diego La Jolla, California 92093-0404 elkan@cs.ucsd.edu Abstract Finding allowable places in words to insert hyphens is an important practical prob- lem. The algorithm that is used most of- ten nowadays has remained essentially un- changed for 25 years. This method is the TEX hyphenation algorithm of Knuth and Liang. We present here a hyphenation method that is clearly more accurate. The new method is an application of condi- tional random fields. We create new train- ing sets for English and Dutch from the CELEX European lexical resource, and achieve error rates for English of less than 0.1% for correctly allowed hyphens, and less than 0.01% for Dutch. Experiments show that both the Knuth/Liang method and a leading current commercial alterna- tive have error rates several times higher for both languages. 1 Introduction The task that we investigate is learning to split words into parts that are conventionally agreed to be individual written units. In many languages, it is acceptable to separate these units with hyphens, but it is not acceptable to split words arbitrarily. Another way of stating the task is that we want to learn to predict for each letter in a word whether or not it is permissible for the letter to be followed by a hyphen. This means that we tag each letter with either 1, for hyphen allowed following this letter, or 0, for hyphen not allowed after this letter. The hyphenation task is also called ortho- graphic syllabification (Bartlett et al., 2008). It is an important issue in real-world text processing, as described further in Section 2 below. It is also useful as a preprocessing step to improve letter-to- phoneme conversion, and more generally for text- to-speech conversion. In the well-known NETtalk system, for example, syllable boundaries are an input to the neural network in addition to letter identities (Sejnowski and Rosenberg, 1988). Of course, orthographic syllabification is not a fun- damental scientific problem in linguistics. Nev- ertheless, it is a difficult engineering task that is worth studying for both practical and intellectual reasons. The goal in performing hyphenation is to pre- dict a sequence of 0/1 values as a function of a se- quence of input characters. This sequential predic- tion task is significantly different from a standard (non-sequential) supervised learning task. There are at least three important differences that make sequence prediction difficult. First, the set of all possible sequences of labels is an exponentially large set of possible outputs. Second, different in- puts have different lengths, so it is not obvious how to represent every input by a vector of the same fixed length, as is almost universal in su- pervised learning. Third and most important, …

Content truncated to 500 words