Learning Distributed Linguistic Classes

In: Proceedings of CoNLL-2000 and LLL-2000, pages 55-60, Lisbon, Portugal, 2000. Learning Distributed Linguistic Classes Stephan Raaijmakers Netherlands Organisation for Applied Scientific Research (TNO) Institute for Applied Physics Delft The Netherlands raaijmakers@tpd, tno. nl Abstract Error-correcting output codes (ECOC) have emerged in machine learning as a success- ful implementation of the idea of distributed classes. Monadic class symbols are replaced by bit strings, which are learned by an ensem- ble of binary-valued classifiers (dichotomizers). In this study, the idea of ECOC is applied to memory-based language learning with local (k- nearest neighbor) classifiers. Regression analy- sis of the experimental results reveals that, in order for ECOC to be successful for language learning, the use of the Modified Value Differ- ence Metric (MVDM) is an important factor, which is explained in terms of population den- sity of the class hyperspace. 1 Introduction Supervised learning methods applied to natu- ral language classification tasks commonly op- erate on high-level symbolic representations, with linguistic classes that are usually monadic, without internal structure (Daelemans et al., 1996; Cardie et al., 1999; Roth, 1998). This contrasts with the distributed class encoding commonly found in neural networks (Schmid, 1994). Error-correcting output codes (ECOC) have been introduced to machine learning as a principled and successful approach to dis- tributed class encoding (Dietterich and Bakiri, 1995; Ricci and Aha, 1997; Berger, 1999). With ECOC, monadic classes are replaced by code- words, i.e. binary-valued vectors. An ensem- ble of separate classifiers (dichotomizers) must be trained to learn the binary subclassifications for every instance in the training set. During classification, the bit predictions of the vari- ous dichotomizers are combined to produce a codeword prediction. The class codeword which has minimal Hamming distance to the predicted codeword determines the classification of the in- stance. Codewords are constructed such that their Hamming distance is maximal. Extra bits are added to allow for error recovery, allowing the correct class to be determinable even if some bits are wrong. An error-correcting output code for a k-class problem constitutes a matrix with k rows and 2 k-1-1 columns. Rows are the code- words corresponding to classes, and columns are binary subclassifications or bit functions fi such that, for an instance e, and its codeword vector C fi(e) = ~-i(c) (1) (~-i(v) the i-th coordinate of vector v). If the minimum Hamming distance between ev- ery codeword is d, then the code has an error- correcting capability of [-~J. Figure 1 shows the 5 x 15 ECOC matrix, for a 5-class problem. In this code, every codeword has a Hamming distance of at least 8 to the other codewords, so this code has an error-correcting capability of 3 bits. ECOC have two natural interpreta- 011000100000001] 01101001011101 ~ 10100011101011 11001110110001 11110100011011 Figure h ECOC for a five-class problem. tions. From an information-theoretic perspec- tive, classification with ECOC is like channel coding (Shannon, 1948): the class of a pattern to be classified is a datum sent over a noisy com- munication channel. The communication chan- nel consists of …

Content truncated to 500 words