Unsupervised Learning of Word Boundary with Description Length Gain

Unsupervised Learning of Word Boundary with Description Length Gain Chunyu Kit t$ Dept. of Chinese, Translation and Linguistics City University of Hong Kong t ctckit@cityu, edu. hk Yorick Wilks t Department of Computer Science University of Sheffield t yorick@dcs, shef. ac. uk Abstract This paper presents an unsupervised approach to lexical acquisition with the goodness measure de- scription length gain (DLG) formulated following classic information theory within the minimum de- scription length (MDL) paradigm. The learning algorithm seeks for an optimal segmentation of an utterance that maximises the description length gain from the individual segments. The resultant segments show a nice correspondence to lexical items (in particular, words) in a natural language like English. Learning experiments on large-scMe corpora (e.g., the Brown corpus) have shown the effectiveness of both the learning algorithm and the goodness measure that guides that learning. 1. Introduction Detecting and handling unknown words properly has become a crucial issue in today's practical nat- ural language processing (NLP) technology. No matter how large the dictionary that is used in a NLP system, there can be many new words in running/real texts, e.g., in scientific articles, news- papers and Web pages, that the dictionary does not include. Many such words are proper names and special terminology that provide critical infor- mation. It is unreliable to rest on delimiters such as white spaces to detect new lexical units, be- cause many basic lexical items contain one or more spaces, e.g., as in "New York", "Hong Kong" and "hot dog". It appears that unsupervised learning techniques are necessary in order to alleviate the problem of unknown words in the NLP domain. There have been a number of studies on lex- ical acquisition from language data of different types. Wolff attempts to infer word bound- aries from artificially-generated natural language sentences, heavily relying on the co-occurrence frequency of adjacent characters [Wolff1975, Wolff 1977]. Nevill-Manning's text compression program Sequitur can also identify word bound- aries and gives a binary tree structure for an identified word [Nevill-Mmming 1996]. de Mar- cken explores unsupervised lexical acquisition from Enghsh spoken and written corpora and from a Chinese written corpus [de Marken 1995: de Marken 1996]. In this paper, we present all unsuper- vised approach to lexical acquisition within the minimum description length (MDL) paradigm [Rissanen 1978, Rissanen 1982] [Rissanen 1989], with a goodness measure, namely, the descrip- tion length gain (DLG), which is formulated in [Kit 1998] following classic information theory [Shannon 1948, Cover and Thomas 1991]. This measure is used, following the MDL princi- ple, to evaluate the goodness of identifying a (sub)sequence of characters in a corpus as a lex- ical item. In order to rigorously evaluate the ef- fectiveness of this unsupervised learning approach, we do not limit ourselves to the detection of un- known words with respect to ally given dictionary. Rather, we use it to perform unsupervised lexi- cal acquisition from large-scale English text cor- pora. Since it is a learning-via-compression ap- proach, the algorithm can be further extended to …

Content truncated to 500 words