Mining Search Engine Clickthrough Log for Matching N-gram Features

Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, pages 524–533, Singapore, 6-7 August 2009. c⃝2009 ACL and AFNLP Mining Search Engine Clickthrough Log for Matching N-gram Features Huihsin Tseng, Longbin Chen, Fan Li, Ziming Zhuang, Lei Duan, Belle Tseng Yahoo! Inc., Santa Clara, CA 95054 {huihui,longbin,fanli,ziming,leiduan,belle}@yahoo-inc.com Abstract User clicks on a URL in response to a query are extremely useful predictors of the URL’s rele- vance to that query. Exact match click features tend to suffer from severe data sparsity issues in web ranking. Such sparsity is particularly pro- nounced for new URLs or long queries where each distinct query-url pair will rarely occur. To remedy this, we present a set of straightforward yet informative query-url n-gram features that al- lows for generalization of limited user click data to large amounts of unseen query-url pairs. The method is motivated by techniques leveraged in the NLP community for dealing with unseen words. We find that there are interesting regulari- ties across queries and their preferred destination URLs; for example, queries containing “form” tend to lead to clicks on URLs containing “pdf”. We evaluate our set of new query-url features on a web search ranking task and obtain improve- ments that are statistically significant at a p-value < 0.0001 level over a strong baseline with exact match clickthrough features. 1 Introduction Clickthrough logs record user click behaviors, which are a critical source for improving search relevance (Bilenko and White, 2008; Radlinski et al., 2007; Agichtein and Zheng, 2006; Lu et al. 2006). Previous work (Agichtein et al., 2006) demonstrated that clickthrough features (e.g., IsNextClicked and IsPreviousClicked) can lead to substantial improvements in relevance. Such features summarize query-specific user interac- tions on a search engine. One commonly used clickthrough feature is generated based on the following observation: if a URL receives a large number of first and last clicks across many user sessions, then it indicates that this URL might be a strongly preferred destination of a query. For example, when a user searches for “yahoo”, they tend to only click on the URL www.yahoo.com rather than other alternatives. This results in www.yahoo.com being the first and last clicked URL for the query. We refer to such behavior as being navigational clicks (NavClicks). Features that use exact query and URL string matches (e.g., NavClick, IsNextClicked and IsPrevious- Clicked) are referred to as exact match features (ExactM) for the remainder of this paper. The coverage of ExactM features is sparse, espe- cially for long queries and new URLs. Many long queries are either unique or very low fre- quency. Hence, the improvements from ExactM features are limited to the more popular queries. In addition, ExactM features tend to be weighted heavily in the ranking of results when they are available. This introduces a bias where the rank- ing models tend to strongly favor older URLs over new URLs even when the latter otherwise appear to be more relevant. By inspecting the clickthrough logs, we observed that unseen query-url pairs are …

Content truncated to 500 words