Memory-based learners classify data based on their similarity to data that they have seen earlier. They have been used for a variety of natural language processing tasks with good results, for example for grapheme-to-phoneme conversion [Hoste et al.(2000)], stress assignment [Daelemans et al.(1994)] and word class tagging [Van Halteren et al.(2001)]. These natural language processing tasks are classification tasks: they require an assignment of a class to each character or to each word. Shallow parsing is more complicated than that: it requires sequences of words to be grouped together and be classified.
We believe that all natural language tasks can be performed successfully by memory-based learners. Identifying and classifying sequences of words can be converted to a classification task by using special tag sets, for example the IOB tag set proposed by [Ramshaw and Marcus(1995)]. Parsing requires different processing levels and these can be simulated by cascading several memory-based learners which have been trained on different subtasks [Daelemans(1995)]. The idea of using memory-based methods for processing natural language has recently led to the emergence of a new paradigm: Memory-Based Language Processing (MBLP) to which a special issue of the Journal of Experimental & Theoretical Artificial Intelligence was devoted [Daelemans(1999)].
The goal of this paper is to test the theoretic ideas about memory-based learning applied to natural language tasks, in particular its application to shallow parsing. We will implement the ideas of [Daelemans(1995)], show what problems need to be solved, test memory-based shallow parsers and compare their performance with those of other systems. The tasks which we will examine are identification of base noun phrases, recognition of phrases of arbitrary types, finding clauses, discovering embedded noun phrases and full parsing. Memory-based learning performs well on natural language tasks that require output that has relatively little structure. In this paper we will investigate whether we can obtain equally good results when it is applied to tasks requiring more complex outputs.