Smoothing clickthrough data for web search ranking

ABSTRACT

Incorporating features extracted from clickthrough data (called clickthrough features) has been demonstrated to significantly improve the performance of ranking models for Web search applications. Such benefits, however, are severely limited by the data sparseness problem, i.e., many queries and documents have no or very few clicks. The ranker thus cannot rely strongly on clickthrough features for document ranking. This paper presents two smoothing methods to expand clickthrough data: query clustering via Random Walk on click graphs and a discounting method inspired by the Good-Turing estimator. Both methods are evaluated on real-world data in three Web search domains. Experimental results show that the ranking models trained on smoothed clickthrough features consistently outperform those trained on unsmoothed features. This study demonstrates both the importance and the benefits of dealing with the sparseness problem in clickthrough data.

REFERENCES

• 1: Eugene Agichtein , Eric Brill , Susan Dumais, Improving web search ranking by incorporating user behavior information, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148177]
• 2: Subutai Ahmad , Volker Tresp, Some Solutions to the Missing Feature Problem in Vision, Advances in Neural Information Processing Systems 5, [NIPS Conference], p.393-400, November 30-December 03, 1992
• 3: Ricardo Baeza-Yates , Alessandro Tiberi, Extracting semantic relations from query logs, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281204]
• 4: Christopher M. Bishop, Neural Networks for Pattern Recognition, Oxford University Press, Inc., New York, NY, 1995
• 5: Peter F. Brown , Peter V. deSouza , Robert L. Mercer , Vincent J. Della Pietra , Jenifer C. Lai, Class-based n-gram models of natural language, Computational Linguistics, v.18 n.4, p.467-479, December 1992
• 6: Burges, C.J., Ragno, R.,&Le, Q.V. 2006. Learning to rank with nonsmooth cost functions. In NIPS, pp. 395--402.
• 7: Chris Burges , Tal Shaked , Erin Renshaw , Ari Lazier , Matt Deeds , Nicole Hamilton , Greg Hullender, Learning to rank using gradient descent, Proceedings of the 22nd international conference on Machine learning, p.89-96, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102363]
• 8: Chen, S. and Goodman, J. 1998. An empirical study of smoothing techniques for language modeling. Technical Report TR-10-98, Harvard University.
• 9: Nick Craswell , Martin Szummer, Random walks on the click graph, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277784]
• 10: Mark Dredze , Koby Crammer , Fernando Pereira, Confidence-weighted linear classification, Proceedings of the 25th international conference on Machine learning, p.264-271, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390190]
• 11: Jianfeng Gao , Haoliang Qi , Xinsong Xia , Jian-Yun Nie, Linear discriminant model for information retrieval, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076085]
• 12: Ghahramani, Z. and Jordan, M.I. 1994. Supervised learning from incomplete data via an EM approach. In NIPS, pp.
• 13: Good, I.J. 1953. The population frequencies of species and the estimation of population parameters. Biomerika, 40 (3-4): 237--264.
• 14: Goodman, J. 2001. A bit of progress in language modeling (extended version). Technical Report MSR-TR-2001-72, Microsoft Research.
• 15: Goodman, J. and Gao, J. 2000. Language model size reduction by pruning and clustering. In ICSLP, pp. 176--182.
• 16: Hastie, T., Tibshirani, R. and Friedman, J. 2001. The elements of statistical learning. Springer-Verlag, New York.
• 17: Kalervo Järvelin , Jaana Kekäläinen, IR evaluation methods for retrieving highly relevant documents, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.41-48, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345545]
• 18: Thorsten Joachims, Optimizing search engines using clickthrough data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775067]
• 19: Thorsten Joachims , Laura Granka , Bing Pan , Helene Hembrooke , Geri Gay, Accurately interpreting clickthrough data as implicit feedback, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076063]
• 20: Katz, S.M. 1987. Estimation of probabilities from sparse data for the language model of a speech recognizer. IEEE Trans on Acoustics, Speech and Signal Processing, ASSP-35(3): 400--401.
• 21: Xiao Li , Ye-Yi Wang , Alex Acero, Learning query intent from regularized click graphs, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390393]
• 22: Roderick J A Little , Donald B Rubin, Statistical analysis with missing data, John Wiley & Sons, Inc., New York, NY, 1986
• 23: Yuting Liu , Bin Gao , Tie-Yan Liu , Ying Zhang , Zhiming Ma , Shuyuan He , Hang Li, BrowseRank: letting web users vote for page importance, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390412]
• 24: Lowe, D. and Webb, A.R. 1990. Exploit prior knowledge in network optimization: an illustration from medical prognosis. Network: Computation in Neural Systems, 1(3):299--323.
• 25: Qiaozhu Mei , Dengyong Zhou , Kenneth Church, Query suggestion using hitting time, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA [doi>10.1145/1458082.1458145]
• 26: Filip Radlinski , Thorsten Joachims, Active exploration for learning rankings from clickthrough data, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281254]
• 27: Query clustering using user logs, ACM Transactions on Information Systems (TOIS), v.20 n.1, p.59-81, January 2002 [doi>10.1145/503104.503108]
• 28: Gui-Rong Xue , Hua-Jun Zeng , Zheng Chen , Yong Yu , Wei-Ying Ma , WenSi Xi , WeiGuo Fan, Optimizing web search using web click-through data, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031192]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

General Terms:
Algorithms, Experimentation

Keywords:
clickthrough data, discounting, learning to rank, random walk, smoothing, web search