Large scale multi-label classification via metalabeler

ABSTRACT

The explosion of online content has made the management of such content non-trivial. Web-related tasks such as web page categorization, news filtering, query categorization, tag recommendation, etc. often involve the construction of multi-label categorization systems on a large scale. Existing multi-label classification methods either do not scale or have unsatisfactory performance. In this work, we propose MetaLabeler to automatically determine the relevant set of labels for each instance without intensive human involvement or expensive cross-validation. Extensive experiments conducted on benchmark data show that the MetaLabeler tends to outperform existing methods. Moreover, MetaLabeler scales to millions of multi-labeled instances and can be deployed easily. This enables us to apply the MetaLabeler to a large scale query categorization problem in Yahoo!, yielding a significant improvement in performance.

REFERENCES

• 1: Lijuan Cai , Thomas Hofmann, Hierarchical document categorization with support vector machines, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031186]
• 2: Rich Caruana , Alexandru Niculescu-Mizil, An empirical comparison of supervised learning algorithms, Proceedings of the 23rd international conference on Machine learning, p.161-168, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143865]
• 3: Soumen Chakrabarti , Byron Dom , Rakesh Agrawal , Prabhakar Raghavan, Scalable feature selection, classification and signature generation for organizing large text databases into hierarchical topic taxonomies, The VLDB Journal — The International Journal on Very Large Data Bases, v.7 n.3, p.163-178, August 1998 [doi>10.1007/s007780050061]
• 4: Susan Dumais , Hao Chen, Hierarchical classification of Web content, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.256-263, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345593]
• 5: Saso Džeroski , Bernard Ženko, Is Combining Classifiers with Stacking Better than Selecting the Best One?, Machine Learning, v.54 n.3, p.255-273, March 2004 [doi>10.1023/B:MACH.0000015881.36452.6e]
• 6: Rong-En Fan , Kai-Wei Chang , Cho-Jui Hsieh , Xiang-Rui Wang , Chih-Jen Lin, LIBLINEAR: A Library for Large Linear Classification, The Journal of Machine Learning Research, 9, p.1871-1874, 6/1/2008
• 7: R.-E. Fan and C.-J. Lin. A study on threshold selection for multi-label classication. 2007.
• 8: Nadia Ghamrawi , Andrew McCallum, Collective multi-label classification, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099591]
• 9: Nathalie Japkowicz , Shaju Stephen, The class imbalance problem: A systematic study, Intelligent Data Analysis, v.6 n.5, p.429-449, October 2002
• 10: Shuiwang Ji , Lei Tang , Shipeng Yu , Jieping Ye, Extracting shared subspace for multi-label classification, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401939]
• 11: Thorsten Joachims, Text Categorization with Suport Vector Machines: Learning with Many Relevant Features, Proceedings of the 10th European Conference on Machine Learning, p.137-142, April 21-23, 1998
• 12: I. Katakis, G. Tsoumakas, and I. Vlahavas. Multilabel text classification for automated tag suggestion. In Proceedings of the ECML/PKDD 2008 Discovery Challenge, 2008.
• 13: S. Sathiya Keerthi , S. Sundararajan , Kai-Wei Chang , Cho-Jui Hsieh , Chih-Jen Lin, A sequential dual method for large scale multi-class linear svms, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401942]
• 14: Daphne Koller , Mehran Sahami, Hierarchically Classifying Documents Using Very Few Words, Proceedings of the Fourteenth International Conference on Machine Learning, p.170-178, July 08-12, 1997
• 15: David D. Lewis , Yiming Yang , Tony G. Rose , Fan Li, RCV1: A New Benchmark Collection for Text Categorization Research, The Journal of Machine Learning Research, 5, p.361-397, 12/1/2004
• 16: Tie-Yan Liu , Yiming Yang , Hao Wan , Hua-Jun Zeng , Zheng Chen , Wei-Ying Ma, Support vector machines classification with a very large-scale taxonomy, ACM SIGKDD Explorations Newsletter, v.7 n.1, p.36-43, June 2005 [doi>10.1145/1089815.1089821]
• 17: Tie-Yan LIU , Yiming YANG , Hao WAN , Qian ZHOU , Bin GAO , Hua-Jun ZENG , Zheng CHEN , Wei-Ying MA, An experimental study on large-scale web categorization, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062891]
• 18: Andrew McCallum , Ronald Rosenfeld , Tom M. Mitchell , Andrew Y. Ng, Improving Text Classification by Shrinkage in a Hierarchy of Classes, Proceedings of the Fifteenth International Conference on Machine Learning, p.359-367, July 24-27, 1998
• 19: Kunal Punera , Joydeep Ghosh, Enhanced hierarchical classification via isotonic smoothing, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367518]
• 20: Ryan Rifkin , Aldebaro Klautau, In Defense of One-Vs-All Classification, The Journal of Machine Learning Research, 5, p.101-141, 12/1/2004
• 21: Juho Rousu , Craig Saunders , Sandor Szedmak , John Shawe-Taylor, Kernel-Based Learning of Hierarchical Multilabel Classification Models, The Journal of Machine Learning Research, 7, p.1601-1626, 12/1/2006
• 22: Lei Tang , Huan Liu, Bias Analysis in Text Classification for Highly Skewed Data, Proceedings of the Fifth IEEE International Conference on Data Mining, p.781-784, November 27-30, 2005 [doi>10.1109/ICDM.2005.34]
• 23: Lei Tang , Huan Liu , Jianping Zhang , Nitin Agarwal , John J. Salerno, Topic taxonomy adaptation for group profiling, ACM Transactions on Knowledge Discovery from Data (TKDD), v.1 n.4, p.1-28, January 2008 [doi>10.1145/1324172.1324173]
• 24: Lei Tang , Jianping Zhang , Huan Liu, Acclimatizing Taxonomic Semantics for Hierarchical Content Classification, 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.1150446]
• 25: Ioannis Tsochantaridis , Thomas Hofmann , Thorsten Joachims , Yasemin Altun, Support vector machine learning for interdependent and structured output spaces, Proceedings of the twenty-first international conference on Machine learning, p.104, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015341]
• 26: G. Tsoumakas and K. Ioannis. Multi label classification: An overview. International Journal of Data Warehousing and Mining, 3:1--13, 2007.
• 27: Grigorios Tsoumakas , Ioannis Vlahavas, Random k-Labelsets: An Ensemble Method for Multilabel Classification, Proceedings of the 18th European conference on Machine Learning, September 17-21, 2007, Warsaw, Poland [doi>10.1007/978-3-540-74958-5_38]
• 28: N. Ueda and K. Saito. Parametric mixture models for multi-labeled text. In NIPS, pages 721--728, 2002.
• 29: Rong Yan , Jelena Tesic , John R. Smith, Model-shared subspace boosting for multi-label classification, 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.1281281]
• 30: Yiming Yang, A study of thresholding strategies for text categorization, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.137-145, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383975]
• 31: Kai Yu , Shipeng Yu , Volker Tresp, Multi-label informed latent semantic indexing, 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.1076080]
• 32: Bianca Zadrozny , Charles Elkan, Transforming classifier scores into accurate multiclass probability estimates, 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.775151]
• 33: Min-Ling Zhang , Zhi-Hua Zhou, ML-KNN: A lazy learning approach to multi-label learning, Pattern Recognition, v.40 n.7, p.2038-2048, July, 2007 [doi>10.1016/j.patcog.2006.12.019]
• 34: Shenghuo Zhu , Xiang Ji , Wei Xu , Yihong Gong, Multi-labelled classification using maximum entropy method, 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.1076082]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.m MISCELLANEOUS

General Terms:
Algorithms, Experimentation

Keywords:
hierarchical classification, large scale, meta model, metalabeler, multi-label classification, query categorization