Mining for the most certain predictions from dyadic data

ABSTRACT

In several applications involving regression or classification, along with making predictions it is important to assess how accurate or reliable individual predictions are. This is particularly important in cases where due to finite resources or domain requirements, one wants to make decisions based only on the most reliable rather than on the entire set of predictions. This paper introduces novel and effective ways of ranking predictions by their accuracy for problems involving large-scale, heterogeneous data with a dyadic structure, i.e., where the independent variables can be naturally decomposed into three groups associated with two sets of elements and their combination. These approaches are based on modeling the data by a collection of localized models learnt while simultaneously partitioning (co-clustering) the data. For regression this leads to the concept of "certainty lift". We also develop a robust predictive modeling technique that identifies and models only the most coherent regions of the data to give high predictive accuracy on the selected subset of response values. Extensive experimentation on real life datasets highlights the utility of our proposed approaches.

REFERENCES

• 1: Deepak Agarwal , Srujana Merugu, Predictive discrete latent factor models for large scale dyadic 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.1281199]
• 2: Christopher M. Bishop , Cazhaow S. Quazaz, Bayesian Inference of Noise Levels in Regression, Proceedings of the 1996 International Conference on Artificial Neural Networks, p.59-64, July 16-19, 1996
• 3: Christopher M. Bishop, Pattern Recognition and Machine Learning (Information Science and Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 4: M. Blum, R. Floyd, V. Pratt, R. Rivest, and R. Tarjan. Time bounds for selection. J. Comput. Syst. Sci., 7(4):448--461, 1973.
• 5: G. Cawley, N. Talbot, and O. Chapelle. Estimating predictive variances with kernel ridge regression. In Machine Learning Challenges '06, pages 56--77, 2006.
• 6: C. Chow. On optimum recognition error and reject tradeoff. IEEE Transactions on Information Theory, 16:41--46, 1970.
• 7: Meghana Deodhar , Joydeep Ghosh, A framework for simultaneous co-clustering and learning from complex 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.1281222]
• 8: Meghana Deodhar , Gunjan Gupta , Joydeep Ghosh , Hyuk Cho , Inderjit Dhillon, A scalable framework for discovering coherent co-clusters in noisy data, Proceedings of the 26th Annual International Conference on Machine Learning, p.241-248, June 14-18, 2009, Montreal, Quebec, Canada [doi>10.1145/1553374.1553405]
• 9: C. Ferri and J. Hernandez-Orallo. Cautious classifiers. In ROCAI '04, pages 27--36, 2004.
• 10: J. Fox. Applied Regression Analysis, Linear Models, and Related Methods. Sage Publications, 1997.
• 11: T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning. Springer, New York, 2001.
• 12: T. Heskes. Practical confidence and prediction intervals. In NIPS '97, pages 176--82, 1997.
• 13: J.Leonard, M.Kramer, and L.Ungar. Using radial basis functions to approximate a function and its error bounds. IEEE Transactions on Neural Networks, 3:4:624--627, July 1992.
• 14: J. Johnston. Econometric Methods. New York: McGraw-Hill, 1963.
• 15: B. Kim and M. Sullivan. The effect of parent brand experience on line extension trial and repeat purchase. Marketing Letters, pages 181 -- 193, 1998.
• 16: Jon Kleinberg , Eva Tardos, Algorithm Design, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2005
• 17: A. Nix and A. Weigend. Estimating the mean and variance of the target probability distribution. In Neural Networks '94, pages 55--60, 1994.
• 18: Tadeusz Pietraszek, On the use of ROC analysis for the optimization of abstaining classifiers, Machine Learning, v.68 n.2, p.137-169, August 2007 [doi>10.1007/s10994-007-5013-y]
• 19: P. Seetharaman, A. Ainslie, and P. Chintagunta. Investigating household state dependence effects across categories. JMR, pages 488 -- 500, 1999.
• 20: David Shepard Associates, New Direct Marketing: How to Implement a Profit-Driven Database Marketing Strategy, McGraw-Hill, Inc., New York, NY, 1999
• 21: Durga L. Shrestha , Dimitri P. Solomatine, Machine learning approaches for estimation of prediction interval for the model output, Neural Networks, v.19 n.2, p.225-235, March 2006 [doi>10.1016/j.neunet.2006.01.012]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms

Keywords:
co-clustering, dyadic data, ranking predictions, regression