Entropy as an Indicator of Context Boundaries: An Experiment Using a Web Search Engine

Entropy as an Indicator of Context Boundaries —An Experiment Using a Web Search Engine— Kumiko Tanaka-Ishii Graduate School of Information Science and Technology, University of Tokyo kumiko@i.u-tokyo.ac.jp Abstract. Previous works have suggested that the uncertainty of tokens coming after a sequence helps determine whether a given position is at a context boundary. This feature of language has been applied to unsupervised text segmentation and term extraction. In this paper, we fundamentally verify this feature. An experiment was performed using a web search engine, in order to clarify the extent to which this assumption holds. The verification was applied to Chinese and Japanese. 1 Introduction The theme of this paper is the following assumption: The uncertainty of tokens coming after a sequence helps determine whether a given position is at a context boundary. (A) Intuitively, the variety of successive tokens at each character inside a word mono- tonically decreases according to the offset length, because the longer the preced- ing character n-gram, the longer the preceding context and the more it restricts the appearance of possible next tokens. On the other hand, the uncertainty at the position of a word border becomes greater and the complexity increases, as the position is out of context. This suggests that a word border can be detected by focusing on the differentials of the uncertainty of branching. This assumption is illustrated in Figure 1. In this paper, we measure this uncertainty of successive tokens by utilizing the entropy of branching (which we mathematically define in the next section). This assumption dates back to the fundamental work done by Harris [6] in 1955, where he says that when the number of different tokens coming after every prefix of a word marks the maximum value, then the location corresponds to the morpheme boundary. Recently, with the increasing availability of corpora, this characteristic of language data has been applied for unsupervised text segmenta- tion into words and morphemes. Kempe [8] reports an experiment to detect word borders in German and English texts by monitoring the entropy of successive characters for 4-grams. Many works in unsupervised segmentation utilise the fact that the branching stays low inside words but increases at a word or mor- pheme border. Some works apply this fact in terms of frequency [10] [2], while others utilise more sophisticated statistical measures: Sun et al. [12] use mutual information; Creutz [4] use MDL to decompose Finnish texts into morphemes. R. Dale et al. (Eds.): IJCNLP 2005, LNAI 3651, pp. 93–105, 2005. c ⃝ Springer-Verlag Berlin Heidelberg 2005 94 K. Tanaka-Ishii This assumption seems to hold not only at the character level but also at the word level. For example, the uncertainty of words coming after the word sequence, “The United States of”, is small (because the word America is very likely to occur), whereas the uncertainty is greater for the sequence “computa- tional linguistics”, suggesting that there is a context boundary just after this term. This observation at the word level has been applied to term extraction …

Content truncated to 500 words