Improving classification accuracy using automatically extracted training data

ABSTRACT

Classification is a core task in knowledge discovery and data mining, and there has been substantial research effort in developing sophisticated classification models. In a parallel thread, recent work from the NLP community suggests that for tasks such as natural language disambiguation even a simple algorithm can outperform a sophisticated one, if it is provided with large quantities of high quality training data. In those applications, training data occurs naturally in text corpora, and high quality training data sets running into billions of words have been reportedly used.

We explore how we can apply the lessons from the NLP community to KDD tasks. Specifically, we investigate how to identify data sources that can yield training data at low cost and study whether the quantity of the automatically extracted training data can compensate for its lower quality. We carry out this investigation for the specific task of inferring whether a search query has commercial intent. We mine toolbar and click logs to extract queries from sites that are predominantly commercial (e.g., Amazon) and non-commercial (e.g., Wikipedia). We compare the accuracy obtained using such training data against manually labeled training data. Our results show that we can have large accuracy gains using automatically extracted training data at much lower cost.

REFERENCES

• 1: R. Agrawal , A. Halverson , K. Kenthapadi , N. Mishra , P. Tsaparas, Generating labels from clicks, Proceedings of the Second ACM International Conference on Web Search and Data Mining, February 09-12, 2009, Barcelona, Spain [doi>10.1145/1498759.1498824]
• 2: Galen Andrew , Jianfeng Gao, Scalable training of L¹-regularized log-linear models, Proceedings of the 24th international conference on Machine learning, p.33-40, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273501]
• 3: R. A. Baeza-Yates, L. Calderon-Benavides, and C. N. Gonzalez-Caro. The intention behind web queries. In SPIRE, pages 98--109, 2006.
• 4: Michele Banko , Eric Brill, Scaling to very very large corpora for natural language disambiguation, Proceedings of the 39th Annual Meeting on Association for Computational Linguistics, p.26-33, July 06-11, 2001, Toulouse, France [doi>10.3115/1073012.1073017]
• 5: Steven M. Beitzel , Eric C. Jensen , Ophir Frieder , David Grossman , David D. Lewis , Abdur Chowdhury , Aleksandr Kolcz, Automatic web query classification using labeled and unlabeled training data, 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.1076138]
• 6: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 7: Honghua (Kathy) Dai , Lingzhi Zhao , Zaiqing Nie , Ji-Rong Wen , Lee Wang , Ying Li, Detecting online commercial intention (OCI), Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135902]
• 8: 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]
• 9: Thorsten Joachims , Laura Granka , Bing Pan , Helene Hembrooke , Filip Radlinski , Geri Gay, Evaluating the accuracy of implicit feedback from clicks and query reformulations in Web search, ACM Transactions on Information Systems (TOIS), v.25 n.2, p.7-es, April 2007 [doi>10.1145/1229179.1229181]
• 10: Mirella Lapata , Frank Keller, Web-based models for natural language processing, ACM Transactions on Speech and Language Processing (TSLP), v.2 n.1, p.3-es, February 2005 [doi>10.1145/1075389.1075392]
• 11: 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]
• 12: Fabrice Muhlenbach , Stéphane Lallich , Djamel A. Zighed, Identifying and Handling Mislabelled Instances, Journal of Intelligent Information Systems, v.22 n.1, p.89-109, January 2004 [doi>10.1023/A:1025832930864]
• 13: Preslav Nakov , Marti Hearst, Using the web as an implicit training set: application to structural ambiguity resolution, Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, p.835-842, October 06-08, 2005, Vancouver, British Columbia, Canada [doi>10.3115/1220575.1220680]
• 14: Umaa Rebbapragada , Carla E. Brodley, Class Noise Mitigation Through Instance Weighting, Proceedings of the 18th European conference on Machine Learning, September 17-21, 2007, Warsaw, Poland [doi>10.1007/978-3-540-74958-5_71]
• 15: David Yarowsky, Unsupervised word sense disambiguation rivaling supervised methods, Proceedings of the 33rd annual meeting on Association for Computational Linguistics, p.189-196, June 26-30, 1995, Cambridge, Massachusetts [doi>10.3115/981658.981684]
• 16: X. Zeng and T. R. Martinez. A noise filtering method using neural networks. In Proceedings of the International Workshop of Soft Computing Techniques in Instrumentation, Measurement and Related Applications, pages 26--31, 2003.
• 17: X. Zhu. Semi-supervised learning literature survey. Technical Report 1530, Computer Sciences, University of Wisconsin-Madison, 2005.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation

Keywords:
automatically labeled data, classification, query intent