Memory-Based Learning: Using Similarity for Smoothing

Memory-Based Learning: Using Similarity for Smoothing Jakub Zavrel and Walter Daelemans Computational Linguistics Tilburg University PO Box 90153 5000 LE Tilburg The Netherlands {zavrel, walt er}@kub, nl Abstract This paper analyses the relation between the use of similarity in Memory-Based Learning and the notion of backed-off smoothing in statistical language model- ing. We show that the two approaches are closely related, and we argue that feature weighting methods in the Memory-Based paradigm can offer the advantage of au- tomatically specifying a suitable domain- specific hierarchy between most specific and most general conditioning information without the need for a large number of pa- rameters. We report two applications of this approach: PP-attachment and POS- tagging. Our method achieves state-of-the- art performance in both domains, and al- lows the easy integration of diverse infor- mation sources, such as rich lexical repre- sentations. 1 Introduction Statistical approaches to disambiguation offer the advantage of making the most likely decision on the basis of available evidence. For this purpose a large number of probabilities has to be estimated from a training corpus. However, many possible condition- ing events are not present in the training data, yield- ing zero Maximum Likelihood (ML) estimates. This motivates the need for smoothing methods, which re- estimate the probabilities of low-count events from more reliable estimates. Inductive generalization from observed to new data lies at the heart of machine-learning approaches to disambiguation. In Memory-Based Learning 1 (MBL) induction is based on the use of similarity (Stanfill & Waltz, 1986; Aha et al., 1991; Cardie, 1994; Daelemans, 1995). In this paper we describe how the use of similarity between patterns embod- ies a solution to the sparse data problem, how it 1The Approach is also referred to as Case-based, Instance-based or Exemplar-based. relates to backed-off smoothing methods and what advantages it offers when combining diverse and rich information sources. We illustrate the analysis by applying MBL to two tasks where combination of information sources promises to bring improved performance: PP- attachment disambiguation and Part of Speech tag- ging. 2 Memory-Based Language Processing The basic idea in Memory-Based language process- ing is that processing and learning are fundamen- tally interwoven. Each language experience leaves a memory trace which can be used to guide later pro- cessing. When a new instance of a task is processed, a set of relevant instances is selected from memory, and the output is produced by analogy to that set. The techniques that are used are variants and extensions of the classic k-nearest neighbor (k- NN) classifier algorithm. The instances of a task are stored in a table as patterns of feature-value pairs, together with the associated "correct" out- put. When a new pattern is processed, the k nearest neighbors of the pattern are retrieved from memory using some similarity metric. The output is then de- termined by extrapolation from the k nearest neigh- bors, i.e. the output is chosen that has the highest relative frequency among the nearest neighbors. Note that no abstractions, such as grammatical rules, …

Content truncated to 500 words