Learning in Natural Language: Theory and Algorithmic Approaches

In: Proceedings of CoNLL-2000 and LLL-PO00, pages 1-6, Lisbon, Portugal, 2000. Learning in Natural Language: Theory and Algorithmic Approaches* Dan Roth Department of Computer Science University of Illinois at Urbana-Champaign 1304 W Springfield Ave., Urbana, IL 61801 danr@cs, uiuc. edu Abstract This article summarizes work on developing a learning theory account for the major learning and statistics based approaches used in natural language processing. It shows that these ap- proaches can all be explained using a single dis- tribution free inductive principle related to the pac model of learning. Furthermore, they all make predictions using the same simple knowl- edge representation - a linear representation over a common feature space. This is signifi- cant both to explaining the generalization and robustness properties of these methods and to understanding how these methods might be ex- tended to learn from more structured, knowl- edge intensive examples, as part of a learning centered approach to higher level natural lan- guage inferences. 1 Introduction Many important natural language inferences can be viewed as problems of resolving phonetic, syntactic, semantics or pragmatics ambiguities, based on properties of the surrounding context. It is generally accepted that a learning compo- nent must have a central role in resolving these context sensitive ambiguities, and a significant amount of work has been devoted in the last few years to developing learning methods for these tasks, with considerable success. Yet, our un- derstanding of when and why learning works in this domain and how it can be used to support increasingly higher level tasks is still lacking. This article summarizes work on developing a learning theory account for the major learning approaches used in NL. While the major statistics based methods used in NLP are typically developed with a * This research is supported by NSF grants IIS-9801638, SBR-9873450 and IIS-9984168. Bayesian view in mind, the Bayesian principle cannot directly explain the success and robust- ness of these methods, since their probabilistic assumptions typically do not hold in the data. Instead, we provide this explanation using a sin- gle, distribution free inductive principle related to the pac model of learning. We describe the unified learning framework and show that, in addition to explaining the success and robust- ness of the statistics based methods, it also ap- plies to other machine learning methods, such as rule based and memory based methods. An important component of the view devel- oped is the observation that most methods use the same simple knowledge representation. This is a linear representation over a new feature space - a transformation of the original instance space to a higher dimensional and more expres- sive space. Methods vary mostly algorithmicly, in ways they derive weights for features in this space. This is significant both to explaining the generalization properties of these methods and to developing an understanding for how and when can these methods be extended to learn from more structured, knowledge intensive ex- amples, perhaps hierarchically. These issues are briefly discussed and we emphasize the impor- tance of …

Content truncated to 500 words