Finding Structure via Compression

m m / / / / / / / / / / / / / / / / / Finding Structure via Compression Jason L. Hutchens Dept. of E&E Engineering University of Western Australia Nedlands W.A. 6907, Australia hut ch~ciips, ee. uwa. edu. au Michael D. Alder Dept. of Mathematics University of Western Australia Nedlands W.A. 6907, Australia mike©maths, uwa. edu. au Abstract A statistical language model may be used to segment a data sequence by thresholding its instantaneous entropy. In this paper we de- scribe how this process works, and we apply it to the problem of discovering separator sym- bols in a text. Our results show that language models which bootstrap themselves with struc- ture found in this way undergo a reduction in perplexity. We conclude that these techniques may be useful in the design of generic gram- matical inference systems. 1 Introduction The modelling of a symbol sequence requires some assumptions about the nature of the process which generated it, and the modelling of English text would, for example, commonly make the assumption that the text consists of words, short strings which usually recur and which are separated by whitespace, and punctuation symbols. The whitespace symbol (which we shall represent explicitly by A) and its distinctive function do not seem to occur in spoken English, and would not seem to be essential in writ- ten English. We are concerned with finding such structure using weak assumptions, rather than be- ing given it as part of a model. In this paper we show that a statistical model may be used to do just that, and our results indicate that a model which bootstraps itself using this structure undergoes a reduction in perplexity. 2 Entropic Chunking A predictive model M is a model which, when pre- sented with a sequence of symbols s, is able to make a prediction about the next symbol in the sequence in the form of a probability distribution over the al- phabet E (for the purposes of this investigation, is the set of ASCII characters). We assume that the estimated probability distribution is smoothed to avoid the zero-frequency problem. The specifics of the model are unimportant; the methods presented in this paper are intended to be generic, but it is clear that n-th order Markov models, for n less than the length of s, would qualify. The information of a symbol w with respect to a statistical model M and a context s is defined in Equation 1. Intuitively we may think of the infor- mation as the surprise the model experiences upon receipt of the symbol w; it is low if the model's expectations are vindicated, high if they are erro- neous (Shannon and Weaver, 1949). I(w[M, s) = - log 2 P(w[M, s) (1) The entropy of a language model, defined in Equa- tion 2, is the expected value of the information. The entropy is a measure of the model's uncertainty about the future; it will be low if the model expects …

Content truncated to 500 words