Automating Feature Set Selection for Case-Based Learning of Linguistic Knowledge

Claire CardieEMNLP 1996 · OpenReview

Abstract

This paper addresses the issue of "algorithm vs. representation" for case-based learning of linguistic knowledge. We first present empirical evidence that the success of case-based learning methods for natural language processing tasks depends to a large degree on the feature set used to describe the training instances. Next, we present a technique for automating feature set selection for case-based learning of linguistic knowledge. Given as input a baseline case representation, the method modifies the representation in response to a number of predefined linguistic biases by adding, deleting, and weighting features appropriately. We apply the linguistic bias approach to feature set selection to the problem of relative pronoun disambiguation and show that the case-based learning algorithm improves as relevant biases are incorporated into the underlying instance representation. Finally, we argue that the linguistic bias approach to feature set selection offers new possibilities for case-based learning of natural language: it simplifies the process of instance representation design and, in theory, obviates the need for separate instance representations for each linguistic knowledge acquisition task. More importantly, the approach offers a mechanism for explicitly combining the frequency information available from corpus-based techniques with linguistic bias information employed in traditional linguistic and knowledge-based approaches to natural language processing.

Introduction

The field of Natural Language Processing (NLP) often faces a tension between the choice of learning algorithm and the representation of the data. Case-Based Learning (CBL), a "lazy" learning paradigm that solves new problems by retrieving similar past instances, is particularly sensitive to this "algorithm vs. representation" bottleneck. If cases are described with irrelevant or redundant features, similarity metrics fail, and the model's ability to generalize is severely compromised.

Traditionally, feature engineering for linguistic tasks has been a manual, labor-intensive process. Researchers must design bespoke feature sets for every task, from part-of-speech tagging to coreference resolution. While statistical methods like decision trees offer some automated pruning, they often lack the structural insights necessary for complex linguistic phenomena. This paper proposes a middle ground: an automated technique for feature set selection that leverages broad linguistic and cognitive biases to tune a general baseline representation.

Methods: The Linguistic Bias Approach

The core learner employed is a k-nearest neighbor (k-NN) algorithm. To overcome the limitations of manual feature selection, the author introduces a novel Linguistic Bias framework. Instead of human-designed rules, the system modifies a baseline representation according to three predefined biases:

  1. Recency Bias: This reflects the cognitive tendency to associate pronouns with the most recent noun phrases. It is implemented by relabeling features based on their distance from the target (scanning right-to-left) and applying a weighting scheme that favors closer constituents.
  2. Restricted Memory Bias: Inspired by Miller’s "Magical Number Seven," this bias limits the number of features the algorithm considers. By forcing the model to focus on a small subset of cues, it effectively filters out statistical noise.
  3. Subject Accessibility Bias: Drawing from psycholinguistic research, this bias recognizes that the subject of a sentence remains highly accessible in memory. The system boosts the weight of the "subject" feature to reflect this prominence.

The implementation follows a three-step process: relabeling attributes, applying weights, and discarding low-weight features to satisfy memory constraints.

Recency weighting mechanism for linguistic features.

Experimental Setup

The methodology was validated using two primary datasets from the Message Understanding Conferences:

  • MUC-5 (TIPSTER Joint Ventures): Used for lexical tagging tasks, including part-of-speech and semantic class tagging.
  • MUC-3 (Latin American Terrorism): Used for the relative pronoun disambiguation task, consisting of 241 instances.

Performance was measured using 10-fold cross-validation to ensure the robustness of the results across different data splits.

Key Results and Discussion

The experiments yielded two major insights. First, representation is indeed critical; even a simple k-NN algorithm's accuracy can fluctuate significantly based on the feature set. For instance, in general semantic tagging, accuracy jumped from 67.1% to 80.6% with proper feature selection.

Impact of automated feature selection on lexical tagging accuracy.

Second, the "less is more" principle proved effective. The Restricted Memory Bias, when combined with recency weighting, improved performance by narrowing the search space to the most relevant features. This suggests that throwing away information can be beneficial if the remaining features are highly predictive.

In the relative pronoun (RP) disambiguation task, the baseline CBL model achieved 76.2% accuracy, while a default "choose most recent" strategy reached 74.3%. Hand-coded heuristics by domain experts achieved 80.5%. Remarkably, the CBL model using the combined Linguistic Bias approach (Recency + Memory Limit of 5 + Subject Weighting) reached 84.2%, significantly outperforming human-designed rules.

Conclusion

The linguistic bias approach offers a promising path toward task-independent baseline representations. By incorporating all available knowledge sources and allowing the framework to prune and weight them automatically, developers can simplify the design of instance representations and potentially move toward a single, parser-dependent baseline for multiple tasks.

Future work should focus on validating these results on larger corpora and automating the selection of the biases themselves, perhaps through meta-learning. Exploring additional biases, such as "minimal attachment" or "lexical preference," could further enhance the system's ability to handle complex syntactic ambiguities.

Summary updated

Abstract

This paper addresses the issue of "algorithm vs. representation" for case-based learning of linguistic knowledge. We first present empirical evidence that the success of case-based learning methods for natural language processing tasks depends to a large degree on the feature set used to describe the training instances. Next, we present a technique for automating feature set selection for case-based learning of linguistic knowledge. Given as input a baseline case representation, the method modifies the representation in response to a number of predefined linguistic biases by adding, deleting, and weighting features appropriately. We apply the linguistic bias approach to feature set selection to the problem of relative pronoun disambiguation and show that the casebased learning algorithm improves as relevant biasses are incorporated into the underlying instance representation. Finally, we argue that the linguistic bias approach to feature set selection offers new possibilities for case-based learning of natural language: it simplifies the process of instance representation design and, in theory, obviates the need for separate instance representations for each linguistic knowledge acquisition task. More importantly, the approach offers a mechanism for explicitly combining the frequency information available from corpus-based techniques with linguistic bias information employed in traditional linguistic and knowledge-based approaches to natural language processing.
BibTeX
@inproceedings{cardie1996automating,
  author = {Claire Cardie},
  title = {{Automating Feature Set Selection for Case-Based Learning of Linguistic Knowledge}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {1996},
  url = {https://openreview.net/forum?id=ByVRXzGdZB},
}
Figure