Abstract: Masato Hagiwara, Hisami Suzuki. Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics.
2009.
Introduction
Search query correction is a critical component of modern information retrieval, but historically, most research has focused on English. Japanese poses a uniquely difficult challenge due to its highly complex writing system, which blends four character types: hiragana, katakana, kanji, and the Roman alphabet.
As shown in Figure 1, a single word can have numerous valid spellings, abbreviations, and synonyms across different scripts. For example, foreign loanwords transliterated into katakana often result in half a dozen valid spelling variations. Standard query correction relies on string edit distance (fixing typos), but this fails when a user types an abbreviation (e.g., "MS" for "Microsoft") or a synonym. While distributional similarity—looking at the surrounding context words a query appears with—can help identify synonyms, search query logs are notoriously short, noisy, and sparse.
Methodology
The authors propose a unified probabilistic model that handles both orthographic (spelling) and semantic (synonym) alterations. The core innovation lies in Orthographically Augmented Semantic Kernels.
To address the sparseness of distributional similarity, the researchers model queries and their context patterns as a bipartite graph. They apply semantic kernels (von Neumann and Exponential) to simulate a random walk through this graph. The major innovation is augmenting this graph with string edit distance: if two queries share no exact context patterns, but their context patterns are spelled similarly, the kernel creates a weak link between them.
As illustrated in Figure 3, this approach allows the graph-walking algorithm to jump between nodes that are spelled similarly (like "YouTube" and "You+Tube"), successfully bridging the sparse gaps in user query logs. Finally, a Maximum Entropy (ME) model combines all these features—language model probabilities, edit distances, and kernel-based semantic similarities—to score and select the best query alteration.
Datasets and Evaluation
The authors utilized a subset of Japanese search query logs from Live Search (now Bing) containing over 1 million unique queries. To build a gold-standard benchmark, they mined logs for successive queries by the same user where the second query resulted in a click, resulting in a verified dataset of 6,489 query-alteration pairs.
Key Results
The Maximum Entropy model utilizing the augmented exponential kernel (ME-Exp+) achieved the best performance with 75.14% accuracy, significantly outperforming the baseline Source-Channel (SC) model (71.12%). When evaluated against multiple valid references, the accuracy of the ME-Exp+ model reached nearly 80% (79.81%).
Conclusion
By using orthographic similarity to smooth out semantic similarity, the model successfully captures user intent beyond simple typo correction. While contextual information in query logs remains sparse, this unified approach provides a robust framework for tackling the multi-script complexities of Japanese web search.
Summary updated