Real-time ranking with concept drift using expert advice

ABSTRACT

In many practical applications, one is interested in generating a ranked list of items using information mined from continuous streams of data. For example, in the context of computer networks, one might want to generate lists of nodes ranked according to their susceptibility to attack. In addition, real-world data streams often exhibit concept drift, making the learning task even more challenging. We present an online learning approach to ranking with concept drift, using weighted majority techniques. By continuously modeling different snapshots of the data and tuning our measure of belief in these models over time, we capture changes in the underlying concept and adapt our predictions accordingly. We measure the performance of our algorithm on real electricity data as well as asynthetic data stream, and demonstrate that our approach to ranking from stream data outperforms previously known batch-learning methods and other online methods that do not account for concept drift.

REFERENCES

• 1: Alekh Agarwal , Soumen Chakrabarti , Sunny Aggarwal, Learning to rank networked entities, 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.1150409]
• 2: Avrim Blum, On-line Algorithms in Machine Learning, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.306-325, January 1998
• 3: Avrim Blum, Empirical Support for Winnow and Weighted-MajorityAlgorithms: Results on a Calendar Scheduling Domain, Machine Learning, v.26 n.1, p.5-23, Jan. 1997 [doi>10.1023/A:1007335615132]
• 4: Olivier Bousquet , Manfred K. Warmuth, Tracking a small set of experts by mixing past posteriors, The Journal of Machine Learning Research, 3, 3/1/2003
• 5: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 6: 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]
• 7: Nicolò Cesa-Bianchi , Yoav Freund , David Haussler , David P. Helmbold , Robert E. Schapire , Manfred K. Warmuth, How to use expert advice, Journal of the ACM (JACM), v.44 n.3, p.427-485, May 1997 [doi>10.1145/258128.258179]
• 8: F. Chu and C. Zaniolo. Fast and light boosting for adaptive mining of data streams. In Proceedings of the Pacific-Asia Knowledge Discovery and Data Mining Conference pages 282--292, 2004.
• 9: V. Dani, O. Madani, D. Pennock, S. Sanghai, and B. Galebach. An empirical comparison of algorithms for aggregating expert predictions. In UAI 2006.
• 10: Carlotta Domeniconi , Dimitrios Gunopulos, Incremental Support Vector Machine Construction, Proceedings of the 2001 IEEE International Conference on Data Mining, p.589-592, November 29-December 02, 2001
• 11: Pedro Domingos , Geoff Hulten, Mining high-speed data streams, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.71-80, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347107]
• 12: Yoav Freund , Raj Iyer , Robert E. Schapire , Yoram Singer, An efficient boosting algorithm for combining preferences, The Journal of Machine Learning Research, 4, p.933-969, 12/1/2003
• 13: Yoav Freund , Robert E. Schapire , Yoram Singer , Manfred K. Warmuth, Using and combining predictors that specialize, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.334-343, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258616]
• 14: Glenn Fung , Olvi L. Mangasarian, Data selection for support vector machine classifiers, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.64-70, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347105]
• 15: J. Gama and G. Castillo. Learning with local drift detection. In ADMA pages 42--55, 2006.
• 16: J. Gama, P. Medas, G. Castillo, and P. P. Rodrigues. Learning with drift detection. In SBIA pages 286--295, 2004.
• 17: João Gama , Pedro Medas , Pedro Rodrigues, Learning decision trees from dynamic data streams, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico [doi>10.1145/1066677.1066809]
• 18: P. Gross, A. Boulanger, M. Arias, D. L. Waltz, P. M. Long, C. Lawson, R. Anderson, M. Koenig,M. Mastrocinque, W. Fairechio, J. A. Johnson, S. Lee, F. Doherty, and A. Kressner. Predicting electricity distribution feeder failures using machine learning susceptibility analysis. In AAAI 2006.
• 19: David P. Helmbold , Darrell D. E. Long , Tracey L. Sconyers , Bruce Sherrod, Adaptive disk spin—down for mobile computers, Mobile Networks and Applications, v.5 n.4, p.285-297, Dec. 2000 [doi>10.1023/A:1019129116852]
• 20: Geoff Hulten , Laurie Spencer , Pedro Domingos, Mining time-changing data streams, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.97-106, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502529]
• 21: Daniel Kifer , Shai Ben-David , Johannes Gehrke, Detecting change in data streams, Proceedings of the Thirtieth international conference on Very large data bases, p.180-191, August 31-September 03, 2004, Toronto, Canada
• 22: R. Klinkenberg. Meta-learning, model selection, and example selection in machine learning domains with concept drift. In LWA pages 164--171, 2005.
• 23: Ralf Klinkenberg , Thorsten Joachims, Detecting Concept Drift with Support Vector Machines, Proceedings of the Seventeenth International Conference on Machine Learning, p.487-494, June 29-July 02, 2000
• 24: R. Klinkenberg and I. Renz. Adaptive information ?ltering: Learning in the presence of concept drifts, 1998.
• 25: R. Klinkenberg and S. Rüping. Concept drift and the importance of example. In Text Mining pages 55--78. Jürgen Franke, Gholamreza Nakhaeizadeh, and Ingrid Renz, 2003.
• 26: Jeremy Z. Kolter , Marcus A. Maloof, Using additive expert ensembles to cope with concept drift, Proceedings of the 22nd international conference on Machine learning, p.449-456, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102408]
• 27: Yi Li , Philip M. Long, The Relaxed Online Maximum Margin Algorithm, Machine Learning, v.46 n.1-3, p.361-387, 2002 [doi>10.1023/A:1012435301888]
• 28: N. Littlestone and M. K. Warmuth. The weighted majority algorithm. In IEEE Symposium on Foundations of Computer Science pages 256--261, 1989.
• 29: P. M. Long and R. A. Servedio. Martingale boosting. In COLT pages 79--94, 2005.
• 30: O. L. Mangasarian , David R. Musicant, Large Scale Kernel Regression via Linear Programming, Machine Learning, v.46 n.1-3, p.255-269, 2002 [doi>10.1023/A:1012422931930]
• 31: N. Oza and S. Russell. Online bagging and boosting. In Artificial Intelligence and Statistics 2001 pages 105--112. Morgan Kaufmann, 2001.
• 32: Nikunj C. Oza , Stuart Russell, Experimental comparisons of online and batch versions of bagging and boosting, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.359-364, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502565]
• 33: F. Rosenblatt. The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review 65(1):386--407, 1958.
• 34: C. Rudin. Ranking with a p-norm push. In COLT pages 589--604, 2006.
• 35: M. Scholz and R. Klinkenberg. An ensemble classi?er for drifting concepts. In Proceedings of the Second International Workshop on Knowledge Discovery in Data Streams pages 53--64, 2005.
• 36: M. Severo and J. Gama. Change detection with kalman ?lter and cusum. In Discovery Science pages 243--254, 2006.
• 37: K. Stanley. Learning concept drift with a committee of decision trees, 2001.
• 38: W. Nick Street , YongSeog Kim, A streaming ensemble algorithm (SEA) for large-scale classification, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.377-382, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502568]
• 39: Paul E. Utgoff , Neil C. Berkman , Jeffery A. Clouse, Decision Tree Induction Based on Efficient Tree Restructuring, Machine Learning, v.29 n.1, p.5-44, Oct. 1997 [doi>10.1023/A:1007413323501]
• 40: Volodimir G. Vovk, Aggregating strategies, Proceedings of the third annual workshop on Computational learning theory, p.371-386, August 06-08, 1990, Rochester, New York, United States
• 41: Haixun Wang , Wei Fan , Philip S. Yu , Jiawei Han, Mining concept-drifting data streams using ensemble classifiers, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956778]
• 42: Gerhard Widmer , Miroslav Kubat, Learning in the presence of concept drift and hidden contexts, Machine Learning, v.23 n.1, p.69-101, April 1996 [doi>10.1023/A:1018046501280]
• 43: Ying Yang , Xindong Wu , Xingquan Zhu, Mining in Anticipation for Concept Change: Proactive-Reactive Prediction in Data Streams, Data Mining and Knowledge Discovery, v.13 n.3, p.261-289, November 2006 [doi>10.1007/s10618-006-0050-x]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.m Miscellaneous

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms, Experimentation, Performance

Keywords:
concept drift, data streams, online learning, ranking