Learning in Natural Language

Dan RothIJCAI 1999 · OpenReview

Abstract

Statistics-based classifiers in natural language are developed typically by assuming a generative model for the data, estimating its parameters from training data and then using Bayes rule to obtain a classifier. For many problems the assumptions made by the generative models are evidently wrong, leaving open the question of why these approaches work.

This paper presents a learning theory account of the major statistical approaches to learning in natural language. A class of Linear Statistical Queries (LSQ) hypotheses is defined and learning with it is shown to exhibit some robustness properties. Many statistical learners used in natural language, including naive Bayes, Markov Models and Maximum Entropy models are shown to be LSQ hypotheses, explaining the robustness of these predictors even when the underlying probabilistic assumptions do not hold. This coherent view of when and why learning approaches work in this context may help to develop better learning methods and an understanding of the role of learning in natural language inferences.

Introduction

In Natural Language Processing (NLP), it is standard practice to build classifiers using generative probabilistic models. For instance, a part-of-speech tagger might utilize a Markov Model that assumes a word's tag depends solely on the immediately preceding tag. However, language is inherently characterized by long-range, global dependencies that violate these local independence assumptions.

Despite these fundamentally flawed assumptions, models like Naive Bayes and Hidden Markov Models (HMMs) perform remarkably well in practice. This paper addresses the central paradox: if the underlying generative models produce poor estimates of the actual probability distributions of sentences, why do the resulting classifiers remain so robust?

The Linear Statistical Query (LSQ) Framework

To resolve this mystery, the research applies computational learning theory—specifically Probably Approximately Correct (PAC) learning and the Statistical Queries (SQ) model—to standard NLP algorithms.

The paper introduces a formal class of hypotheses termed Linear Statistical Queries (LSQ). Unlike traditional learning algorithms that process individual training examples to find a consistent hypothesis, an LSQ algorithm learns by querying an "oracle" for aggregate statistics about the data. For example, it might ask: "What fraction of examples possess feature $X$ and label $Y$?" This approach allows for a specific tolerance of error in the statistics. The algorithm then constructs a linear discriminator over these features based on the returned values.

By mapping widely used NLP models into this LSQ framework, the author can analyze their theoretical properties using established learning theory proofs regarding Vapnik-Chervonenkis (VC) dimension and noise tolerance.

Why "Wrong" Models Succeed

Bounded Complexity and Generalization

The success of models like Naive Bayes is not due to the accuracy of their probabilistic assumptions, but rather the simplicity those assumptions impose. The false assumptions result in a linear classifier with very low expressive power (low VC dimension). The author proves that the VC dimension of LSQ hypotheses is strictly bounded by the number of features used. This low complexity prevents the model from overfitting to noise in the training data, allowing it to generalize effectively to unseen text.

Distributional Robustness

Because LSQ algorithms rely on aggregate statistics with a margin of error rather than memorizing specific data points, they possess inherent mathematical robustness. The paper establishes a theorem of distributional robustness: an LSQ algorithm trained on a distribution $D$ will maintain its performance on a test distribution $D'$, provided the variation distance between the two distributions remains within a specific tolerance $\gamma$. This explains why NLP models often survive the "domain shift" common when moving from one corpus to another.

Probabilistic Models as Feature Selectors

In this light, generative probabilistic assumptions (such as Markov assumptions) serve a different purpose than originally intended. They do not need to be true; instead, they act as a heuristic guide to help engineers select a simple, effective set of features for a linear classifier. The "probability" values are merely weights in a linear decision boundary.

Mapping Traditional Models to LSQ

The paper formally demonstrates that several pillars of statistical NLP are exact instances of LSQ algorithms:

  • Naive Bayes: The weights are derived directly from statistical queries regarding feature-label co-occurrences.
  • Markov Models: These function as LSQ algorithms where queries are made over n-gram transitions.
  • General Bayesian Classifiers: Even those with hidden variables can be viewed through the LSQ lens.

One notable exception is the Maximum Entropy (ME) model. While ME models are linear predictors, their optimal coefficients typically require iterative approximation rather than direct, single-pass statistical queries. Thus, while structurally similar, optimal ME models are not strictly LSQ algorithms.

Conclusion

This theoretical framework suggests that researchers in NLP should shift their focus. Rather than striving for perfectly accurate probabilistic density estimation—a goal that is likely impossible given the complexity of language—the focus should be on developing better feature selection methods and applying learning theory to higher-level natural language inferences. Understanding the LSQ nature of these models provides a coherent view of why simple statistical methods remain the backbone of the field despite their theoretical inaccuracies.

Summary updated

Abstract

Statistics-based classifiers in natural language are developed typically by assuming a generative model for the data, estimating its parameters from training data and then using Bayes rule to obtain a classifier. For many problems the assumptions made by the generative models are evidently wrong, leaving open the question of why these approaches work. This paper presents a learning theory account of the major statistical approaches to learning in natural language. A class of Linear Statistical Queries (LSQ) hypotheses is defined and learning with it is shown to exhibit some robustness properties. Many statistical learners used in natural language, including naive Bayes, Markov Models and Maximum Entropy models are shown to be LSQ hypotheses, explaining the robustness of these predictors even when the underlying probabilistic assumptions do not hold. This coherent view of when and why learning approaches work in this context may help to develop better learning methods and an understanding of the role of learning in natural language inferences.
BibTeX
@inproceedings{roth1999learning,
  author = {Dan Roth},
  title = {{Learning in Natural Language}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
  url = {https://openreview.net/forum?id=ByVORmMdWr},
}
Figure