Finding Representations for Memory-Based Language Learning

Finding Representations for Memory-Based Language Abstract Constructive induction transforms the representation of instances in order to produce a more accurate model of the concept to be learned. For this purpose, a vari- ety of operators has been proposed in the literature, including a Cartesian product operator forming pair- wise higher-order attributes. We study the effect of the Cartesian product operator on memory-based lan- guage learning, and demonstrate its effect on general- ization accuracy and data compression for a number of linguistic classification tasks, using k-nearest neighbor learning algorithms. These results are compared to a baseline approach of backward sequential elimination of attributes. It is demonstrated that neither approach consistently outperforms the other, and that attribute elimination can be used to derive compact representa- tions for memory-based language learning without no- ticeable loss of generalization accuracy. Introduction Learning Stephan Raaijmakers raaijmakers@inl, nl Institute for Dutch Lexicology (INL) P.O. Box 9515 2300 RA Leiden The Netherlands Daelemans et al., 1997]. Successful attribute elimina- tion leads to compact datasets, which possibly increase classification speed. Constructive induction, on the other hand, tries to exploit dependencies between at- tributes, by combining them into complex attributes that increase accuracy of the classifier. For instance- based algorithms, this approach has been demonstrated to correct invalid independence assumptions made by the algorithm [Pazzani, 1998]: e.g., for the Naive Bayes classifier (Duda & Hart, 1973), the unwarranted as- sumption that in general the various attributes a, = v, are independent, and form a joint probability model for the prediction of the class C: It is a widely held proposition that inductive learn- ing models, such as decision trees [Quinlan, 1993] or k- nearest neighbor models [Aha, Kibler & Albert, 1991], are heavily dependent upon their representational bi- ases. Both decision tree algorithms and instance-based algorithms have been reported to be vulnerable to ir- relevant or noisy attributes in the representation of ex- emplars, which unnecessarily enlarge the search space for classification [John, 1997]. In general, there are two options for dealing with this problem. Attribute elimination (or selection) can be applied in order to find a minimal set of attributes that is maximally in- formative for the concept to be learned. Attribute elimination can be seen as a radical case of attribute weighting [Scherf & Brauer, 1997, Aha, 1998], where attributes are weighted on a binary scale, as either rel- evant or not; more fine-grained methods of attribute weighting take information-theoretic notions ifito ac- count such as information gain ratio [Quinlan, 1993. l-I P(a, = v, I C) P(C) t P(C I a~ = v~A...Aa, = v,) = P(a~ = v~ A... ^ a,, = v,) (I) Constructive induction thus can be used to invent re- lationships between attributes that, apart fl'om possi- bly offering insight into the underlying structure of the learning task, may boost performance of the resulting classifier. Linguistic tasks are sequential by nature, as language processing is a linear process, operating on sequences with a temporal structure (see e.g. Cleere- mans (1993) for motivation for …

Content truncated to 500 words