Discovery of Term Variation in Japanese Web Search Queries

Hisami Suzuki, Xiao Li, Jianfeng GaoEMNLP 2009 · OpenReview

Abstract

Identifying term variations in Japanese web search queries is a significant challenge due to the language's complex writing system. This paper presents a statistical model built on the MART algorithm to identify a broad range of variants, including spelling mistakes, script alternates, transliterations, and abbreviations. By mining user session and click-through logs, the system generates candidates and learns semantic similarity features. The proposed method achieves 70% precision with over 60% recall, representing a 38% error reduction over baseline methods.

The Challenge of Japanese Query Variation

In web search, query expansion helps users find relevant results by including related terms. While this often involves simple typos or stemming in English, Japanese presents a unique hurdle. The Japanese writing system employs four distinct scripts: Hiragana, Katakana, Kanji, and the Roman alphabet. A single concept can be represented in numerous valid ways across these scripts.

Traditional edit distance metrics often fail because variations may look entirely different on the surface while being phonetically identical. Furthermore, Kanji characters can have multiple pronunciations depending on context. The scope of variations handled by this research is broad, ranging from simple spelling mistakes to complex semantic relations.

Table 1: Categories of term variations with examples in English and Japanese.

Methodology: Mining User Behavior

The researchers framed term variation identification as a binary classification task. Their approach relies on two primary pillars: candidate generation from logs and discriminative modeling.

Smart Candidate Generation

Rather than relying on exhaustive dictionary lookups, the system mines user logs to find potential variations:

  • Session Logs: Identifying "re-writes" where a user issues a second query within a short timeframe that leads to a click.
  • Click-Through Logs: Using a Random Walk algorithm on a bipartite graph of queries and URLs. If different queries frequently lead to the same URL, they are likely variations.

Discriminative Modeling with MART

The core of the system is the Multiple Additive Regression Trees (MART) algorithm. The model utilizes 39 features, including:

  • Phonetic Similarity: Levenshtein distance applied to Romanized (phonetic) versions of queries.
  • Semantic Similarity: Likelihood ratios derived from query logs.
  • Character Type Features: Indicators for specific script transitions (e.g., Kanji to Katakana).

Key Results and Performance

The MART-based model significantly outperformed linear models like Maximum Entropy, suggesting that the interactions between linguistic features and script types are non-linear and complex.

Figure 2: Precision and recall curves relative to the confidence threshold of the model.

The system achieved a precision of 70% at a recall level of approximately 60%. A key finding was the importance of semantic features; removing them caused a substantial spike in error rates. This confirms that user behavior data—the "wisdom of the crowd"—is a vital signal for resolving linguistic ambiguity in search.

Conclusion

This research demonstrates that combining phonetic string similarity with behavioral data from search logs is highly effective for identifying Japanese term variations. While challenges remain—particularly with extreme abbreviations and Kanji ambiguity—the 38% error reduction marks a significant step forward in improving search intent recognition for multi-script languages. Future work will explore character-dependent edit operations to further refine the model's accuracy.

Summary updated

Abstract

In this paper we address the problem of identifying a broad range of term variations in Japanese web search queries, where these variations pose a particularly thorny problem due to the multiple character types employed in its writing system. Our method extends the techniques proposed for English spelling correction of web queries to handle a wider range of term variants including spelling mistakes, valid alternative spellings using multiple character types, transliterations and abbreviations. The core of our method is a statistical model built on the MART algorithm (Friedman, 2001). We show that both string and semantic similarity features contribute to identifying term variation in web search queries; specifically, the semantic similarity features used in our system are learned by mining user session and click-through logs, and are useful not only as model features but also in generating term variation candidates efficiently. The proposed method achieves 70% precision on the term variation identification task with the recall slightly higher than 60%, reducing the error rate of a naive baseline by 38%.
BibTeX
@inproceedings{suzuki2009discovery,
  author = {Hisami Suzuki and Xiao Li and Jianfeng Gao},
  title = {{Discovery of Term Variation in Japanese Web Search Queries}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2009},
  url = {https://openreview.net/forum?id=B1VygGfubB},
}
Figure