Formalizing Word Sampling for Vocabulary Prediction as Graph-based Active Learning

Yo Ehara, Yusuke Miyao, Hidekazu Oiwa, Issei Sato, Hiroshi NakagawaEMNLP 2014 · OpenReview

Abstract

Accurately estimating a second-language (L2) learner's vocabulary size is a critical task in language assessment. Traditional methods rely on frequency-based heuristics, sampling words from discrete "bins" to infer broader knowledge. This paper formalizes this process as a graph-based non-interactive active learning problem. By representing vocabulary as a graph where edges denote similar difficulty and merging multiple data sources, the proposed framework achieves significantly higher prediction accuracy with fewer test items than traditional methods.

Introduction

Vocabulary prediction aims to estimate the total number of words a learner knows based on their responses to a small sample of test items. Given the vastness of natural language vocabularies, efficient sampling is essential. Historically, educators have used frequency tiers (e.g., the top 1,000 most common words) as a proxy for difficulty, assuming that knowledge of a few words in a tier implies knowledge of the rest. However, these heuristics are rigid and struggle to account for learners with specialized domain knowledge or the variability between different linguistic corpora.

Methodology: Vocabulary as a Graph

The researchers reframed word sampling by representing the vocabulary as a graph where each node is a word and edges connect words of similar difficulty.

Formalizing Traditional Heuristics

A key contribution of this work is the mathematical proof that traditional frequency-bin sampling is a special case of graph-based learning. In this view, each frequency tier is represented as a "multi-complete graph"—a set of disjoint cliques where all words within a tier are connected to each other, but no edges exist between tiers.

Figure 1: Mapping traditional word frequency lists to a graph-based representation.

Non-Interactive Active Learning

Unlike standard active learning, which adaptively selects the next query based on previous answers, this study focuses on non-interactive active learning. This approach selects an optimal set of test words a priori, making it suitable for static paper-based tests. The goal is to select a subset of nodes that best represents the structure of the entire graph.

Figure 5: The process of selecting representative nodes (words) from the graph for testing.

Graph Merging

The framework's flexibility comes from its ability to merge different graphs by adding their adjacency matrices. The authors combined general frequency graphs (from the BNC and COCA corpora) with domain-specific graphs (using WordNet 3.0) to identify and connect words related to specific fields, such as computer science. Prediction is performed using the Learning with Local and Global Consistency (LLGC) algorithm, which propagates the "known/unknown" labels from the sampled words across the edges of the merged graph.

Experimental Results

The framework was evaluated using response data from 15 ESL learners tested on nearly 12,000 words.

  • Efficiency: With a sample size of only 10 words, the merged graph method (BNC + Domain + COCA) achieved 75.23% accuracy, significantly outperforming the traditional frequency-based baseline of 64.15%.
  • Cold-Start Performance: The graph-based approach is particularly robust when very few samples are available, outperforming standard supervised models like Support Vector Machines (SVM) and Logistic Regression (LR) which lack the structural prior knowledge provided by the graph.
  • Qualitative Success: The "BNC + Domain" graph successfully identified specialized terms (e.g., "input", "client") as high-value test samples for learners with technical backgrounds, a feat impossible for standard frequency-only models.

Conclusion

By formalizing word sampling as graph-based active learning, this research bridges the gap between traditional educational heuristics and modern machine learning. The ability to merge disparate knowledge sources into a single graph structure allows for more personalized and accurate vocabulary assessment. Future work will focus on automating graph construction from raw text to eliminate the need for manual domain-specific edge creation.

Summary of: Yo Ehara, Yusuke Miyao, Hidekazu Oiwa, Issei Sato, Hiroshi Nakagawa. "Formalizing Word Sampling for Vocabulary Prediction as Graph-based Active Learning." EMNLP 2014.

Summary updated

BibTeX
@inproceedings{ehara2014formalizing,
  author = {Yo Ehara and Yusuke Miyao and Hidekazu Oiwa and Issei Sato and Hiroshi Nakagawa},
  title = {{Formalizing Word Sampling for Vocabulary Prediction as Graph-based Active Learning}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2014},
  url = {https://openreview.net/forum?id=kJ076GkSm8K},
}
Figure