TL;DR
This paper introduces a novel method for selecting sentences to train statistical natural language parsers, focusing on "representativeness" alongside informativeness. By adapting Zipf's Principle of Least Effort to sentence length, their "Zipfian sampling" approach consistently matches or outperforms existing methods, significantly improving the efficiency of building large annotated datasets.
What Problem Does This Paper Address?
Training high-performance statistical natural language parsers, like those used for parsing sentences into grammatical structures, requires massive amounts of manually annotated data. Creating these datasets is incredibly time-consuming and expensive. Active learning offers a solution by allowing the model to intelligently select the most valuable sentences to be annotated, rather than relying on random sampling. However, existing active learning methods primarily focus on "informativeness" (how much a sentence helps the model learn) and can sometimes select unusual sentences that might not reflect the true distribution of language. This can lead to degraded performance. This paper addresses the need for active learning strategies that also consider "representativeness" – ensuring the selected sentences accurately reflect the characteristics of the target language data.
Methods
The core contribution is a new metric for estimating sentence representativeness. This metric is derived from a modification of Zipf's Principle of Least Effort, which suggests that shorter sentences are more likely to be uttered. The authors adapt a previously proposed formula (Sigurd et al., 2004) that models the relative frequencies of sentence lengths in English, based on empirical data from the Brown corpus. This formula, termed "fzipf-eng," is used as a proxy for representativeness.
The paper then integrates this "fzipf-eng" metric with several established informativeness measures (tree entropy, lowest best probability, unparsed/entropy, and two-stage active learning) to create combined active learning strategies. For example, when using tree entropy, sentences are selected based on the product of their "fzipf-eng" score and their tree entropy. They also compare their approach against length-balanced sampling, another representativeness-focused method.
Datasets
- Brown Corpus (Francis and Kučera, 1967): Used to empirically validate the fitted formula for sentence length frequency.
- CCGbank (Hockenmaier and Steedman, 2005): The primary dataset used for training and evaluating the statistical parser.
- WSJ Sections 02-21 (39604 sentences): Used for training the parser.
- WSJ Section 23 (2407 sentences): Used for testing the parser.
The paper does not introduce new benchmark datasets.
Key Insights and Ideas
- Representativeness Matters: The paper strongly argues that representativeness is a crucial, often overlooked, criterion in active learning for NLP, alongside informativeness.
- Zipf's Principle as a Proxy: Adapting Zipf's Principle of Least Effort to sentence length provides a theoretically grounded and empirically validated way to estimate how representative a sentence is of the overall language distribution.
- Model Independence: The "fzipf-eng" metric is model-independent, meaning it's not affected by the current state or potential errors of the parser being trained. This makes it a robust measure.
- Flexibility: The numerical nature of the "fzipf-eng" metric allows for easy combination with other informativeness and diversity measures, offering flexibility in designing active learning strategies.
Key Results
Experiments were conducted using a wide-coverage CCG parser on the CCGbank dataset. The authors evaluated performance using the labeled f-score of predicate-argument dependencies.
- Zipfian sampling consistently performed well: In most comparisons, the proposed Zipfian sampling method either matched or significantly outperformed alternative representativeness-based methods, including length-balanced sampling.
- Competitive with Informativeness: When combined with tree entropy, Zipfian sampling performed nearly as well as pure informativeness-based active learning. With the two-stage active learning method, length-balanced sampling performed comparably to Zipfian sampling.
- Substantial Outperformance: In all other comparisons, Zipfian sampling substantially outperformed its alternatives.
- Efficiency Gains: The paper measures efficiency using "Percentage Reduction in Utilized Data" (PRUD), indicating how much less data is needed to reach a certain performance level compared to random sampling. Table 1 shows PRUD values for various combinations of informativeness and representativeness measures, with Zipfian sampling generally achieving higher PRUD values.
Limitations and Future Work
- Limited Scope of Comparison: The authors acknowledge that they could not test against "sample density" due to the lack of a trivial distance metric for CCG parses. They also excluded multi-learner and ensemble methods due to the assumption that they rely on diverse models, which the C&C parser's models were not.
- Future Directions: The authors suggest extending their work by experimenting with the excluded methods, using other parsers, exploring different languages, and investigating other "Zipfian cues" of language, such as word frequencies.
Summary updated