Estimating rates of rare events at multiple resolutions

ABSTRACT

We consider the problem of estimating occurrence rates of rare eventsfor extremely sparse data, using pre-existing hierarchies to perform inference at multiple resolutions. In particular, we focus on the problem of estimating click rates for (webpage, advertisement) pairs (called impressions) where both the pages and the ads are classified into hierarchies that capture broad contextual information at different levels of granularity. Typically the click rates are low and the coverage of the hierarchies is sparse. To overcome these difficulties we devise a sampling method whereby we analyze aspecially chosen sample of pages in the training set, and then estimate click rates using a two-stage model. The first stage imputes the number of (webpage, ad) pairs at all resolutions of the hierarchy to adjust for the sampling bias. The second stage estimates clickrates at all resolutions after incorporating correlations among sibling nodes through a tree-structured Markov model. Both models are scalable and suited to large scale data mining applications. On a real-world dataset consisting of 1/2 billion impressions, we demonstrate that even with 95% negative (non-clicked) events in the training set, our method can effectively discriminate extremely rare events in terms of their click propensity.

REFERENCES

• 1: A. Dempster, N. Laird, and D. Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society, Series B, 39(1): 1--39, 1977.
• 2: George Edward Pelham Box , Gwilym Jenkins, Time Series Analysis, Forecasting and Control, Holden-Day, Incorporated, 1990
• 3: D. B. Rubin. Multiple Imputation for Nonresponse in Surveys. Wiley, New York, US, 2004.
• 4: D. K. Agarwal, J. Silander, A. E. Gelfand, R. E. Dewar, and J. Mickelson. Tropical deforestation in madagascar: Analysis using hierarchical, spatially explicit, bayesian regression models. Ecological Modelling, 185(1):105--131, 2005.
• 5: H. C. Huang and N. Cressie. Multiscale graphical modeling in space: applications to command and control. In Proceedings of the Spatial Statistics Workshop, New York: Springer Lecture Notes in Statistics, Springer Verlag Publishers, 2000.
• 6: J. N. Darroch and D. Ratcliff. Generalized iterative scaling for log-linear models. The Annals of Mathematical Statistics, 43(5):1470--1480, 1972.
• 7: K. C. Chou, A. S. Willsky, and R. Nikoukhah. Multiscale systems, kalman filters, and riccati equations. IEEE Transactions on Automatic Control, 39:479--492, 1994.
• 8: N. Cressie. Statistics for Spatial Data. John Wiley, New York, 1990.
• 9: N. V. Chawla, K. W. Bowyer, L. O. Hall, and W. P. Kegelmeyer. Smote: Synthetic minority over sampling technique. Journal of Artificial Intelligence Research, 16:321--357, 2002.
• 10: Ping Li , Kenneth W. Church, A Sketch Algorithm for Estimating Two-Way and Multi-Way Associations, Computational Linguistics, v.33 n.3, p.305-354, September 2007 [doi>10.1162/coli.2007.33.3.305]
• 11: S. Hill, D. Agarwal, R. Bell, and C. Volinsky. Building an effective representation for dynamic graphs. Journal of Computational and Graphical Statistics, 15:584--608, 2006.
• 12: S. Openshaw and P. Taylor. A million or so correlation coefficients. In In N. Wrigley (Ed.), Statistical Methods in the Spatial Sciences, London, pages 127--144, 1979.
• 13: S. Pandey, D. Agarwal, D. Chakrabarti, and V. Josifovski. Bandits for taxonomies: A model based approach. In Siam International Conference on Data Mining, Minnesota(to appear), 2007.
• 14: C. Wang, P. Zhang, R. Choi, and M. D. Eredita. Understanding consumers attitude toward advertising. pages 1143--1148, 2002.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.m Miscellaneous

Additional Classification:
  E. Data
  E.0 GENERAL

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.4 Hypertext/Hypermedia

Keywords:
clickthrough rate, contextual matching, hierarchy, imputation, internet advertising, maximum entropy, tree-structured markov model