Entropy of search logs: how hard is search? with personalization? with backoff?

ABSTRACT

How many pages are there on the Web? 5B? 20B? More? Less? Big bets on clusters in the clouds could be wiped out if a small cache of a few million urls could capture much of the value. Language modeling techniques are applied to MSN's search logs to estimate entropy. The perplexity is surprisingly small: millions, not billions.

Entropy is a powerful tool for sizing challenges and opportunities. How hard is search? How hard are query suggestion mechanisms like auto-complete? How much does personalization help? All these difficult questions can be answered by estimation of entropy from search logs.

What is the potential opportunity for personalization? In this paper, we propose a new way to personalize search, personalization with backoff. If we have relevant data for a particular user, we should use it. But if we don't, back off to larger and larger classes of similar users. As a proof of concept, we use the first few bytes of the IP address to define classes. The coefficients of each backoff class are estimated with an EM algorithm. Ideally, classes would be defined by market segments, demographics and surrogate variables such as time and geography

REFERENCES

• 1: Chris Anderson, The Long Tail: Why the Future of Business Is Selling Less of More, Hyperion, 2006
• 2: Krishna Bharat , Andrei Broder, A technique for measuring the relative size and overlap of public Web search engines, Proceedings of the seventh international conference on World Wide Web 7, p.379-388, April 1998, Brisbane, Australia
• 3: Stanley F. Chen , Joshua Goodman, An empirical study of smoothing techniques for language modeling, Proceedings of the 34th annual meeting on Association for Computational Linguistics, p.310-318, June 24-27, 1996, Santa Cruz, California [doi>10.3115/981863.981904]
• 4: N. Chomsky. Syntactic Structures. The Hague/Paris: Mouton, 1957.
• 5: K. Church and W. Gale. A comparison of the enhanced good-turing and deleted estimation methods for estimating probabilities of english bigrams. Computer Speech and Language, 5(1):19--54, 1991.
• 6: Kenneth W. Church , Robert L. Mercer, Introduction to the special issue on computational linguistics using large corpora, Computational Linguistics, v.19 n.1, March 1993
• 7: Kenneth Church , Bo Thiesson, The wild thing!, Proceedings of the ACL 2005 on Interactive poster and demonstration sessions, p.93-96, June 25-30, 2005, Ann Arbor, Michigan [doi>10.3115/1225753.1225777]
• 8: Corinna Cortes , Daryl Pregibon, Signature-Based Methods for Data Streams, Data Mining and Knowledge Discovery, v.5 n.3, p.167-182, July 2001 [doi>10.1023/A:1011464915332]
• 9: A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of Royal Statist. Soc. B, 39:1--38, 1977.
• 10: Devanshu Dhyani , Wee Keong Ng , Sourav S. Bhowmick, A survey of Web metrics, ACM Computing Surveys (CSUR), v.34 n.4, p.469-503, December 2002 [doi>10.1145/592642.592645]
• 11: R. Gallager. Claude E. Shannon: A retrospective on his life, work, and impact. IEEE Transactions on Information Theory, 47(7):2681--2695, 2001.
• 12: A. Gulli , A. Signorini, The indexable web is more than 11.5 billion pages, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062789]
• 13: Glen Jeh , Jennifer Widom, Scaling personalized web search, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775191]
• 14: 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]
• 15: Rosie Jones , Daniel C. Fain, Query word deletion prediction, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860538]
• 16: Rosie Jones , Benjamin Rey , Omid Madani , Wiley Greiner, Generating query substitutions, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135835]
• 17: S. Katz. Estimation of probabilities from sparse data for the language model component of a speech recognizer. IEEE Transactions on Acoustics, Speeech and Signal Processing, 35(3):400--401, 1987.
• 18: S. Lawrence and C. L. Giles. Searching the World Wide Web. Science, 280(5360):98--100, 1998.
• 19: S. Lawrence and C. L. Giles. Accessibility of information on the web. Nature, 400(6740):107--109, 1999.
• 20: Steve Lawrence , C. Lee Giles, Accessibility of information on the Web, intelligence, v.11 n.1, p.32-39, Spring 2000 [doi>10.1145/333175.333181]
• 21: Filip Radlinski , Thorsten Joachims, Query chains: learning to rank from implicit feedback, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081899]
• 22: C. Sagan. Billions and Billions: Thoughts on Life and Death at the Brink of the Millennium. New York: Random House, 1997.
• 23: C. Shannon. A mathematical theory of communication. Bell Systems Technical Journal, 27:379--423, 623¿656, 1948.
• 24: C. Shannon. Prediction and entropy of printed english. Bell Systems Technical Journal, 30:50--64, 1951.
• 25: Xuehua Shen , Bin Tan , ChengXiang Zhai, Context-sensitive information retrieval using 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.1076045]
• 26: Xuehua Shen , Bin Tan , ChengXiang Zhai, UCAIR: a personalized search toolbar, 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.1076193]
• 27: Kazunari Sugiyama , Kenji Hatano , Masatoshi Yoshikawa, Adaptive web search based on user profile constructed without any effort from users, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988764]
• 28: Bin Tan , Xuehua Shen , ChengXiang Zhai, Mining long-term search history to improve search accuracy, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150493]
• 29: Jaime Teevan , Susan T. Dumais , Eric Horvitz, Personalizing search via automated analysis of interests and activities, 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.1076111]
• 30: Ryen W. White , Gary Marchionini, Examining the effectiveness of real-time query expansion, Information Processing and Management: an International Journal, v.43 n.3, p.685-704, May, 2007 [doi>10.1016/j.ipm.2006.06.005]
• 31: Chengxiang Zhai , John Lafferty, A study of smoothing methods for language models applied to Ad Hoc information retrieval, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.334-342, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384019]

INDEX TERMS

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

General Terms:
Measurement

Keywords:
demographics, entropy, personalization with backoff, search difficulty, search log